Efficient rename in a lock-coupled traversal of B+tree
Highly concurrent systems use lock-coupling for tree traversal wherein only two levels (parent and current) are locked at any time. The parent lock is released as soon as successful lock is attained on the grandchild. The rename technique described here facilitates using finer grained locking and multiple path traversals by changing lock ownerships.
1. A computer-implemented method, comprising:
representing a namespace of a file system in a single tree structure, the single tree structure being formed of a plurality of nodes, at least some nodes representing respective filenames in the file system;
for each node, the node holding a key of a respective filename; and
renaming a first key with a second key in the single tree structure using lock coupling, including:
locking a subject node and the parent node;
holding in a first state machine a lock of the parent node;
traversing the single tree structure, beginning from the subject node, using lock coupling and searching for the first key and second keys;
upon divergence of the first and second keys, generating a first path and a second path as two independent paths of traversal of the single tree structure, wherein each of the two independent paths of the single tree structure are traversed concurrently, such that the traversal of the first path is independent from the concurrent traversal of the second path, by:
creating a second state machine traversing the single tree structure, beginning from the subject node, using lock coupling and searching for the first key;
creating a third state machine traversing the single tree structure, beginning from the parent node of the subject node, using lock coupling and searching for the second key, wherein the third state machine traverses the single tree structure concurrently with the second state machine,
such that two independent paths from the subject node to succeeding nodes in respective paths of traversal by the second and third state machines result, and the first state machine waits until the second and third state machines complete;
comparing the first and second keys against a minimum key for each node in the respective paths of traversal;
determining whether the first and second keys diverge at a given node;
upon determining the first and second keys diverge at the given node, creating separate execution paths for traversal; and
determining traversal completion of an execution path upon locking a leaf index node.
2. The method of claim 1 wherein the single tree structure is a B+Tree.
3. The method of claim 1 , further comprising:
requesting, by the second state machine, a lock from the first state machine for at least one node along at least one execution path prior to modifying the at least one node; and
granting to the second state machine the lock for the at least one node along the at least one execution path prior to modifying the at least one node.
4. The method of claim 1 , further comprising:
queuing one or more additional state machines behind the first state machine until the first state machine releases the lock for the parent node.
5. The method of claim 1 , further comprising:
generating a first additional state machine and assigning to the first additional state machine a current lock of the given node;
generating a second additional state machine and assigning to the second additional state machine a lock of a parent node of the given node;
the first and second additional state machines being assigned respective ones of the separate execution paths for traversal,
wherein state machine of the parent node of the given node transitions to a pending state waiting for the first additional state machine and the second additional state machine to complete traversal.
6. The method of claim 5 , further comprising
storing an address of a locked leaf node in the state machine of a parent node to the leaf node;
checking, by at least one of the two additional state machines, whether an address for a requested locked leaf node is held by the other state machine; and
preventing a deadlock by returning control to the leaf node's parent state machine without attempting to lock the address of the locked leaf node.
7. The method of claim 5 , further comprising:
upon traversal completion of the second and third state machine, transferring control to the first state machine;
modifying a namespace by deleting the first key and inserting the second key; and
moving a data pointer from the first key to the second key, wherein moving the data pointer includes referencing a memory address associated with the second key.
8. The method of claim 7 , further comprising:
releasing locks held on the nodes of the first and second keys after moving the data pointer from the first key to the second key.
9. A computer system, comprising:
a file system stored in memory, a namespace of the file system being represented in a single tree structure, the single tree structure being formed of a plurality of nodes, at least some nodes representing respective filenames in the file system, and for each node, the node holding a key of a respective filename; and
a processor configured to rename a first key with a second key in the single tree structure using lock coupling, wherein the processor is configured to:
lock a subject node and the parent node;
hold in a first state machine a lock of the parent node;
traverse the single tree structure, beginning from the subject node, using lock coupling and searching for the first key and second keys;
upon divergence of the first and second keys, generate a first path and a second path as two independent paths of traversal of the single tree structure, wherein each of the two independent paths of the single tree structure are traversed concurrently, such that the traversal of the first path is independent from the concurrent traversal of the second path, by:
create a second state machine traversing the single tree structure, beginning from the subject node, using lock coupling and searching for the first key;
create a third state machine traversing the single tree structure, beginning from the parent node of the subject node, using lock coupling and searching for the second key, wherein the third state machine traverses the single tree structure concurrently with the second state machine,
such that two independent paths from the subject node to succeeding nodes in respective paths of traversal by the second and third state machines result, and the first state machine waits until the second and third state machines complete;
compare the first and second keys against a minimum key for each node in the respective paths of traversal;
determine whether the first and second keys diverge at a given node;
upon determining the first and second keys diverge at the given node, create separate execution paths for traversal; and
determine traversal completion of an execution path upon locking a leaf index node.
10. The computer system of claim 9 , wherein:
the single tree structure is a B+Tree; and
the processor is further configured to:
request, by the second state machine, a lock from the first state machine for at least one node along at least one execution path prior to modifying the at least one node; and
grant to the second state machine the lock for the at least one node along the at least one execution path prior to modifying the at least one node.
11. The computer system of claim 9 , wherein the processor is further configured to:
queue one or more additional state machines behind the first state machine until the first state machine releases the lock for the parent node.
12. The computer system of claim 9 , wherein the processor is further configured to:
generate a first additional state machine and assigning to the first additional state machine a current lock of the given node;
generate a second additional state machine and assigning to the second additional state machine a lock of a parent node of the given node;
assign the first additional state machine and the second additional state machine respective ones of the separate execution paths for traversal,
wherein the processor transitions a state machine of the parent node of the given node to a pending state waiting for the first additional state machine and the second additional state machine to complete traversal.
13. The computer system of claim 12 , wherein the processor is further configured to:
store an address of a locked leaf node in the state machine of a parent node to the leaf node;
check, by at least one of the two additional state machines, whether an address for a requested locked leaf node is held by the other state machine; and
prevent a deadlock by returning control to the leaf node's parent state machine without attempting to lock the address of the locked leaf node.
14. The computer system of claim 12 , wherein the processor is further configured to:
upon traversal completion of the second and third state machine, transfer control to the first state machine;
modify a namespace by deleting the first key and inserting the second key; and
move a data pointer from the first key to the second key, wherein moving the data pointer includes referencing a memory address associated with the second key.
15. The computer system of claim 14 , wherein the processor is further configured to:
release locks held on the nodes of the first and second keys after moving the data pointer from the first key to the second key.
16. A computer program product executed by a processor in communication with a file system, the computer program product comprising:
a non-transitory computer readable medium, the computer readable medium comprising program instructions which, when executed by the processor causes:
representing a namespace of said file system in a single tree structure, the single tree structure being formed of a plurality of nodes, at least some nodes representing respective filenames in the file system;
for each node, the node holding a key of a respective filename; and
renaming a first key with a second key in the single tree structure using lock coupling, including:
locking a subject node and the parent node;
holding in a first state machine a lock of the parent node;
traversing the single tree structure, beginning from the subject node, using lock coupling and searching for the first key and second keys;
upon divergence of the first and second keys, generating a first path and a second path as two independent paths of traversal of the single tree structure, wherein each of the two independent paths of the single tree structure are traversed concurrently, such that the traversal of the first path is independent from the concurrent traversal of the second path, by:
creating a second state machine traversing the single tree structure, beginning from the subject node, using lock coupling and searching for the first key;
creating a third state machine traversing the single tree structure, beginning from the parent node of the subject node, using lock coupling and searching for the second key, wherein the third state machine traverses the single tree structure concurrently with the second state machine,
such that two independent paths from the subject node to succeeding nodes in respective paths of traversal by the second and third state machines result, and the first state machine waits until the second and third state machines complete;
comparing the first and second keys against a minimum key for each node in the respective paths of traversal;
determining whether the first and second keys diverge at a given node;
upon determining the first and second keys diverge at the given node, creating separate execution paths for traversal; and
determining traversal completion of an execution path upon locking a leaf index node.