Accelerating distributed transactions on key-value stores through dynamic lock localization

1. A method for accelerating distributed transactions on key-value stores, comprising:

applying one or more policies of dynamic lock-localization, the policies including a lock migration stage that decreases nodes on which locks are present so that a transaction needs fewer number of network round trips to acquire locks, the policies including a lock ordering stage for pipelining during lock acquisition and wherein the order on locks to avoid deadlock is controlled by average contentions for the locks rather than static lexicographical ordering; and

dynamically migrating and placing locks for distributed objects in distinct entity-groups in a datastore through the policies of dynamic lock-localization.

2. The method of claim 1 , comprising applying a lock migration protocol.

3. The method of claim 2 , comprising checking if the object is unlocked and not migrated, and if so placing a destination lock and atomically placing a detour lock if conditions are met.

4. The method of claim 1 , comprising applying a lock release protocol.

5. The method of claim 4 , comprising deleting a detour lock and making an asynchronous request to delete a destination lock if the object is the owner of a migrated lock and otherwise releasing a lock at a place of acquisition.

6. The method of claim 1 , comprising applying a lock ordering protocol.

7. The method of claim 6 , comprising

changing a lock order identification if lock is not acquired;

collecting the lock order identification while executing a lock migration; and

placing locks in a locking stage for a matching lock order identification.

8. The method of claim 1 , comprising applying a decentralized, distributed, protocol for dynamic modification of the lock order.

9. The method of claim 8 , wherein every lock object, which stores the lock information of the data object, maintains two fields: lock-version and lock-order-id.

10. The method of claim 8 , comprising modifying lock-order-ids and lock-version fields whenever an order of two locks is reversed.

11. The method of claim 8 , comprising transmitting changed order on locks to a client as piggybacked information during lock migration.

12. The method of claim 8 , comprising using a lock-version field to check if a lock-order that a client is adhering to, between two locks, is the same as the one present on the locks and if different, no locks are granted and the transaction is ordered to abort.

13. The method of claim 1 , comprising automatically adapt to the mix and frequency of local and distributed transactions.

14. The method of claim 1 , comprising determining a lock-weight w i for every lock-object i, which represents a running average of distributed transaction proportion in the transaction mix at the end of prescribed intervals as follows:

w i ( n )= f*w i ( n− 1)+(1− f )*( c DT ( n )/( c DT ( n )+ c LT ( n )))

where w i (n−1) is the lock-weight calculated after (n−1) st interval, f is a fractional importance given to previous weight, c DT (n) is a count of distributed transactions (DTs) encountered at an n th interval, and c LT (n) is a count of independent local transactions (LTs) encountered at the n th interval.

15. The method of claim 1 , comprising dynamically migrating needed locks onto a single node before the locking stage.

16. A system for accelerating distributed transactions on key-value stores, comprising

a processor;

a data storage device; and

computer code for:

applying one or more policies of dynamic lock-localization, the policies including a lock migration stage that decreases nodes on which locks are present so that a transaction needs fewer number of network round trips to acquire locks, the policies including a lock ordering stage for pipelining during lock acquisition and wherein the order on locks to avoid deadlock is controlled by average contentions for the locks rather than static lexicographical ordering; and

dynamically migrating and placing locks for distributed objects in distinct entity-groups in a datastore through the policies of dynamic lock-localization.

17. The system of claim 16 , comprising computer code for applying a lock migration protocol.

18. The system of claim 17 , comprising computer code for checking if the object is unlocked and not migrated, and if so placing a destination lock and atomically placing a detour lock if conditions are met.

19. The system of claim 16 , comprising computer code for applying a lock release protocol.

20. The system of claim 19 , comprising computer code for deleting a detour lock and making an asynchronous request to delete a destination lock if the object is the owner of a migrated lock and otherwise releasing a lock at a place of acquisition.