Mitigating causality discrepancies caused by stale versioning
Implementations are provided herein for causally ordering events within a distributed file system. Each node within the distributed file system, when processing an event, can collect object/version pairs associated with event (e.g., an object identifier and an object version number of the object at the time of the event). Object/version pairs can be identified and labeled as reliable or unreliable based on the operation performed on the inode as a part of the event. Relationships between events can be established when two events modify the same object and one event has a lower revision number. If the two object/revision pairs are in a relationship, an unreliable relationship can be deemed a weak edge and a reliable relationship can be deemed a strong edge. Using the strong and weak edges associated with object/revision pairs, a causal order of events can be generated.
1. A method for causally ordering a set of events in a cluster of nodes operating as a distributed file system comprising:
maintaining an event transaction log, wherein events in the event transaction log are associated with an event identifier and each event includes a set of viewed inode number and inode revision number pairs and a set of modified inode number and inode revision number pairs;
generating an inode map based on the event transaction log, wherein the inode map maps event identifiers to inode revision numbers associated with each inode number referenced in the event transaction log;
generating a directed acyclic graph based on the inode map and the event transaction log, wherein a vertex in the directed acyclic graph represents an event identifier and an edge in the directed acyclic graph represents a causal relationship, wherein edges in the directed acyclic graph are strong if the causal relationship is based on the set of modified inode number and inode revision number pairs and weak if the causal relationship is based on an earlier event of the causal relationship being in the set of viewed inode number and inode revision number pairs; and
causally ordering events in the event transaction log based on a topological sort of the directed acyclic graph.
2. The method of claim 1 further comprising: in response to drawing a strong edge that contradicts a weak edge, removing the weak edge from the directed acyclic graph.
3. The method of claim 1 , wherein generating the directed acyclic graph includes not drawing a weak edge between two vertices if a strong edge has already been drawn between the two vertices.
4. The method of claim 1 further comprising: in response to the topological sort indicating a contradictory loop, removing a weak edge from the directed acyclic graph.
5. The method of claim 1 , wherein a weak edge is converted to a strong edge if event associated with the view inode number and inode revision number pair is associated with an exclusive lock.
6. A system comprising at least one storage device and at least one hardware processor configured to:
maintain an event transaction log, wherein events in the event transaction log are associated with an event identifier and each event includes a set of viewed inode number and inode revision number pairs and a set of modified inode number and inode revision number pairs;
generate an inode map based on the event transaction log, wherein the inode map maps event identifiers to inode revision numbers associated with each inode number referenced in the event transaction log;
generate a directed acyclic graph based on the inode map and the event transaction log, wherein a vertex in the directed acyclic graph represents an event identifier and an edge in the directed acyclic graph represents a causal relationship, wherein edges in the directed acyclic graph are strong if the causal relationship is based on the set of modified inode number and inode revision number pairs and weak if the causal relationship is based on an earlier event of the causal relationship being in the set of viewed inode number and inode revision number pairs; and
causally order events in the event transaction log based on a topological sort of the directed acyclic graph.
7. The system of claim 6 , further configured to: in response to drawing a strong edge that contradicts a weak edge, remove the weak edge from the directed acyclic graph.
8. The system of claim 6 , wherein generating the directed acyclic graph includes not drawing a weak edge between two vertices if a strong edge has already been drawn between the two vertices.
9. The system of claim 6 , further configured to: in response to the topological sort indicating a contradictory loop, remove a weak edge from the directed acyclic graph.
10. The system of claim 6 , wherein a weak edge is converted to a strong edge if event associated with the view inode number and inode revision number pair is associated with an exclusive lock.
11. A non-transitory computer readable medium with program instructions stored thereon to perform the following acts:
maintaining an event transaction log, wherein events in the event transaction log are associated with an event identifier and each event includes a set of viewed inode number and inode revision number pairs and a set of modified inode number and inode revision number pairs;
generating an inode map based on the event transaction log, wherein the inode map maps event identifiers to inode revision numbers associated with each inode number referenced in the event transaction log;
generating a directed acyclic graph based on the inode map and the event transaction log, wherein a vertex in the directed acyclic graph represents an event identifier and an edge in the directed acyclic graph represents a causal relationship, wherein edges in the directed acyclic graph are strong if the causal relationship is based on the set of modified inode number and inode revision number pairs and weak if the causal relationship is based on an earlier event of the causal relationship being in the set of viewed inode number and inode revision number pairs; and
causally ordering events in the event transaction log based on a topological sort of the directed acyclic graph.
12. The non-transitory computer readable medium of claim 11 , with program instructions stored thereon to further perform the following acts: in response to drawing a strong edge that contradicts a weak edge, removing the weak edge from the directed acyclic graph.
13. The non-transitory computer readable medium of claim 11 , wherein generating the directed acyclic graph includes not drawing a weak edge between two vertices if a strong edge has already been drawn between the two vertices.
14. The non-transitory computer readable medium of claim 11 , with program instructions stored thereon to further perform the following acts: in response to the topological sort indicating a contradictory loop, removing a weak edge from the directed acyclic graph.
15. The non-transitory computer readable medium of claim 11 , wherein a weak edge is converted to a strong edge if event associated with the view inode number and inode revision number pair is associated with an exclusive lock.