Method, device and computer program product for event ordering
Event ordering is provided in a distributed file system. For instance, events are generated that are associated with an object collected from nodes in the distributed file system, and an event loop indicates causal dependencies among the events, and comprises one or more reliable edges and unreliable edges. Degrees of reliability of the unreliable edges in the event loop are determined, and then at least one unreliable edge is removed from the event loop based on the determined degrees of reliability. Causal dependencies among the events in the distributed file system are analyzed by using a statistical method, and the most unreliable edge in the event loop can be removed by computing a degree of reliability of each unreliable edge, thereby avoiding the occurrence of the event loop.
1. A method for event ordering, comprising:
generating, by a system comprising a processor and based on a plurality of events associated with an object collected from a plurality of nodes in a distributed file system, an event loop indicating causal dependencies among the plurality of events, the event loop comprising one or more reliable edges and a plurality of unreliable edges;
determining a plurality of degrees of reliability of the plurality of unreliable edges in the event loop; and
removing, based on the plurality of degrees of reliability, at least one unreliable edge of the plurality of unreliable edges from the event loop.
2. The method of claim 1 , further comprising:
collecting a plurality of acyclic event chains that were ordered successfully in history; and
processing the plurality of acyclic event chains; and
storing historical statistical data related to reliable edges and unreliable edges.
3. The method of claim 2 , wherein the processing of the plurality of acyclic event chains comprises:
splitting, based on a predetermined splitting rule, each of the plurality of acyclic event chains into a plurality of sub-event chains.
4. The method of claim 3 , wherein the storing of the historical statistical data related to reliable edges and unreliable edges comprises:
for a given edge in a given sub-event chain, determining whether the given edge is a reliable edge or an unreliable edge;
according to a determination that the given edge is a reliable edge, updating first information related to the reliable edge and the given sub-event chain in a reliable edge table; and
according to a determination that the given edge is an unreliable edge, updating second information related to the unreliable edge and the given sub-event chain in an unreliable edge table.
5. The method of claim 1 , wherein the generating the event loop indicating the causal dependencies among the plurality of events comprises:
identifying the plurality of unreliable edges in the event loop; and
splitting the event loop into a plurality of sub-event chains such that each of the plurality of sub-event chains comprises one unreliable edge, respectively.
6. The method of claim 5 , wherein the determining the plurality of degrees of reliability of the plurality of unreliable edges in the event loop comprises:
determining, based on a preconfigured reliable edge table and an unreliable edge table, a probability of reliability of each of the plurality of unreliable edges in a respective sub-event chain of the plurality of sub-event chains using Bayes theorem.
7. The method of claim 6 , wherein the determining the probability of reliability of each of the plurality of unreliable edges in the respective sub-event chain using Bayes theorem comprises: for a given unreliable edge in a given sub-event chain,
determining a first probability that the given sub-event chain occurs when the given unreliable edge is reliable;
determining a second probability that the given unreliable edge is reliable;
determining a third probability that the given sub-event chain occurs; and
determining, based on the first probability, the second probability and the third probability, a given probability of reliability of the given unreliable edge in the given sub-event chain.
8. The method of claim 7 , wherein the removing the at least one unreliable edge from the event loop comprises:
removing, from the event loop, an unreliable edge having a lowest degree of reliability, resulting in an updated event loop; and
reordering updated events in the updated event loop as an acyclic event chain.
9. An electronic device, comprising:
a processing unit; and
a memory coupled to the processing unit and storing instructions thereon, the instructions, when executed by the processing unit, executing acts of:
generating, based on a plurality of events associated with an object collected from a plurality of nodes in a distributed file system, an event loop indicating causal dependencies among the plurality of events, wherein the event loop comprises one or more reliable edges and a plurality of unreliable edges;
determining a plurality of degrees of reliability of the plurality of unreliable edges in the event loop, resulting in a determined plurality of degrees of reliability; and
removing, based on the determined plurality of degrees of reliability, at least one unreliable edge from the event loop.
10. The device of claim 9 , the acts further comprising:
collecting a plurality of acyclic event chains that were ordered successfully; and
processing the plurality of acyclic event chains; and
storing historical statistical data related to reliable edges and unreliable edges.
11. The device of claim 10 , wherein the processing the plurality of acyclic event chains comprises:
splitting, based on a predetermined splitting rule, each of the plurality of acyclic event chains into a plurality of sub-event chains.
12. The device of claim 11 , wherein the storing the historical statistical data related to reliable edges and unreliable edges comprises:
for a given edge in a given sub-event chain, determining whether the given edge is a reliable edge or an unreliable edge;
according to a first determination that the given edge is a reliable edge, updating first information related to the reliable edge and the given sub-event chain in a reliable edge data structure; and
according to a second determination that the given edge is an unreliable edge, updating second information related to the unreliable edge and the given sub-event chain in an unreliable edge data structure.
13. The device of claim 9 , wherein the generating the event loop indicating the causal dependencies among the plurality of events comprises:
identifying the plurality of unreliable edges in the event loop; and
splitting the event loop into a plurality of sub-event chains such that each of the plurality of sub-event chains comprises one unreliable edge, respectively.
14. The device of claim 13 , wherein the determining the plurality of degrees of reliability of the plurality of unreliable edges in the event loop comprises:
determining, based on a preconfigured reliable edge data structure and an unreliable edge data structure, a probability of reliability of each of the plurality of unreliable edges in a respective sub-event chain using Bayes theorem.
15. The device of claim 14 , wherein determining the probability of reliability of each of the plurality of unreliable edges in the respective sub-event chain using Bayes theorem comprises: for a given unreliable edge in a given sub-event chain,
determining a first probability that the given sub-event chain occurs when the given unreliable edge is reliable;
determining a second probability that the given unreliable edge is reliable;
determining a third probability that the given sub-event chain occurs; and
determining, based on the first probability, the second probability and the third probability, a given probability of reliability of the given unreliable edge in the given sub-event chain.
16. The device of claim 15 , wherein the removing the at least one unreliable edge from the event loop comprises:
removing, from the event loop, an unreliable edge having a lowest degree of reliability, resulting in an updated event loop; and
reordering updated events in the updated event loop as an acyclic event chain.
17. A computer program product tangibly stored on a non-transitory computer-readable medium and comprising computer-executable instructions, when executed, cause a computer to execute operations, comprising:
based on events associated with an object collected from nodes of a distributed file system, generating an event loop indicating causal dependencies among the events, the event loop comprising one or more reliable edges and unreliable edges;
determining respective degrees of reliability of the unreliable edges in the event loop; and
based on the respective degrees of reliability, removing an unreliable edge of the unreliable edges from the event loop.
18. The computer program product of claim 17 , the operations further comprising:
collecting acyclic event chains that have been ordered temporally; and
based on a result of processing the acyclic event chains, storing historical statistical data related to reliable edges and unreliable edges.
19. The computer program product of claim 18 , wherein the processing the acyclic event chains comprises:
based on a defined splitting rule, splitting at least one acyclic event chain of the acyclic event chains into sub-event chains.
20. The computer program product of claim 17 , wherein the generating the event loop indicating the causal dependencies among the events comprises:
identifying a number of the unreliable edges in the event loop; and
splitting the event loop into sub-event chains, resulting in the sub-event chains respectively comprising one unreliable edge of the number of the unreliable edges.