Causally ordering distributed file system events
Implementations are provided herein for using inode revision numbers associated with a modified LIN and a set of Parent LINs to causally order transactions within a distributed file system. Any time an inode is changed, its inode revision number can be incremented by 1. When events within file system are processed causing an inode or a set of inodes to be modified, an event transaction log entry can made. The event transaction log entry can denote a description of the event, a set of modified inode and inode revision number pairs, and a set of parent inode and inode revision number pairs. Entries in the event transaction log can be used to build an inode map for each inode implicated in the event transaction log. The inode map can be used to build a set of direct causal dependencies for each transaction in the event transaction log. The set of direct causal dependencies can be used to generate a causal ordering of the transactions in the event transaction log, that in some implementations, can be made available to external services.
1. A method for ordering a set of events in a cluster of nodes operating as a distributed file system comprising:
maintaining an event transaction log, wherein entries in the event transaction log are associated with an event transaction log number, and wherein entries in the event transaction log contain at least one modified inode and inode revision number pair, and a set of parent inodes and parent inode revision number pairs;
generating an inode map wherein the inode map maps each inode referenced in the event transaction log to a set of inode revision numbers and a set of event transaction log numbers based on the event transaction log;
generating a set of direct causal dependencies for each event transaction log number based on the generated inode map; and
ordering the set of events based on the set of direct causal dependencies.
2. The method of claim 1 , wherein maintaining the event transaction log includes:
in response to processing an event associated with an event inode, wherein the event inode is associated with an event inode revision number:
incrementing the event inode revision number;
logging the event inode and the incremented event inode revision number into an event transaction log entry; and
adding a set of parent inodes and associated parent inode revision numbers to the event transaction log entry, wherein the set of parent inodes are based on the event inode.
3. The method of claim 1 , wherein at least two of the events in the set of events are processed in parallel on at least two different nodes among the cluster of nodes.
4. The method of claim 1 , wherein ordering the set of events is further based on applying a topological sort to the set of direct causal dependencies.
5. The method of claim 1 , wherein events in the set of events are based on changes to the metadata associated with at least one inode.
6. The method of claim 1 , further comprising:
assigning sequential transaction numbers to the ordered set of events; and
making available the sequential transaction numbers to other services.
7. A distributed file system comprising a cluster of nodes of nodes that have at least one storage device and at least one hardware processor configured to:
maintain an event transaction log for a set of events, wherein entries in the event transaction log are associated with an event transaction log number, and wherein entries in the event transaction log contain at least one modified inode and inode revision number pair, and a set of parent inodes and parent inode revision number pairs;
generate an inode map wherein the inode map maps each inode referenced in the event transaction log to a set of inode revision numbers and a set of event transaction log numbers based on the event transaction log;
generate a set of direct causal dependencies for each event transaction log number based on the generated inode map; and
order the set of events based on the set of direct causal dependencies.
8. The system of claim 7 , further configured to maintain the event transaction log by:
in response to processing an event associated with an event inode, wherein the event inode is associated with an event inode revision number:
incrementing the event inode revision number;
logging the event inode and the incremented event inode revision number into an event transaction log entry; and
adding a set of parent inodes and associated parent inode revision numbers to the event transaction log entry, wherein the set of parent inodes are based on the event inode.
9. The system of claim 7 , wherein at least two of the events in the set of events are processed in parallel on at least two different nodes among the cluster of nodes.
10. The system of claim 7 , wherein ordering the set of events is further based on applying a topological sort to the set of direct causal dependencies.
11. The system of claim 7 , wherein events in the set of events are based on changes to the metadata associated with at least one inode.
12. The system of claim 7 , further configured to:
assign sequential transaction numbers to the ordered set of events; and
make available the sequential transaction numbers to other services.
13. A non-transitory computer readable medium with program instructions stored thereon to perform the following acts:
maintaining an event transaction log, wherein entries in the event transaction log are associated with an event transaction log number, and wherein entries in the event transaction log contain at least one modified inode and inode revision number pair, and a set of parent inodes and parent inode revision number pairs;
generating an inode map wherein the inode map maps each inode referenced in the event transaction log to a set of inode revision numbers and a set of event transaction log numbers based on the event transaction log;
generating a set of direct causal dependencies for each event transaction log number based on the generated inode map; and
ordering the set of events based on the set of direct causal dependencies.
14. The non-transitory computer readable medium 13 , wherein maintaining the event transaction log further includes:
in response to processing an event associated with an event inode, wherein the event inode is associated with an event inode revision number:
incrementing the event inode revision number;
logging the event inode and the incremented event inode revision number into an event transaction log entry; and
adding a set of parent inodes and associated parent inode revision numbers to the event transaction log entry, wherein the set of parent inodes are based on the event inode.
15. The non-transitory computer readable medium 13 , wherein at least two of the events in the set of events are processed in parallel on at least two different nodes among a cluster of nodes.
16. The non-transitory computer readable medium 13 , wherein ordering the set of events is further based on applying a topological sort to the set of direct causal dependencies.
17. The non-transitory computer readable medium 13 , wherein events in the set of events are based on changes to the metadata associated with at least one inode.
18. The non-transitory computer readable medium of claim 13 , with program instructions stored thereon to further perform the following acts:
assigning sequential transaction numbers to the ordered set of events; and
making available the sequential transaction numbers to other services.