Timer services

Abstract

Measures for providing timer services in a network including a cluster of nodes responsible for providing timer services to clients. At a given node in the cluster, a request to provide a timer is received from a client. Configuration of a primary replica of the requested timer on a first node in the cluster to pop after a first time has elapsed is initiated. A first timer replication message is transmitted to a second node in the cluster, the first timer replication message indicating that the second node should configure a first backup replica of the requested timer. A second timer replication message is transmitted to a third node in the cluster, the second timer replication message indicating that the third node should configure a second backup replica of the requested timer. Popping of the primary, first backup or second backup timer replicas includes initiating callback of a given client.

What is claimed is: 
     
       1. A method of managing nodes in a network comprising a cluster of nodes configured to provide replicas of functions for clients in the network, the method comprising:
 receiving, from a client by a node of the network, a request to apply an update to a function, wherein: 
 the function is instantiated as replicas on a plurality of nodes in the cluster, 
 the update request comprises an identifier of the function, the identifier comprising information encoded using a positive probabilistic set usable to respond to an approximate membership query, the positive probabilistic set selected to conform to a data structure having a desired false positive/negative rate, the information being associated with the nodes on which the function has been configured; 
 the nodes on which the function has been configured are determined by a first node in the cluster; and 
 the nodes are determined according to a deterministic process based on the identifier and the nodes in the cluster when the function is replicated; and 
 decoding the encoded information to identify the nodes on which respective replicas of the function have been configured; and 
 transmitting at least one replica function update message to one or more of the identified nodes to instruct update of their respective configured replicas of the function according to the update requested by the client. 
 
     
     
       2. The method according to  claim 1 , wherein the positive probabilistic set comprises a bloom filter, a retouched bloom filter, or a quotient filter. 
     
     
       3. The method according to  claim 2 , wherein the positive probabilistic set comprises a bloom filter configured to generate a positive response when queried for presence of a predetermined identifier for any of the nodes in the plurality of nodes. 
     
     
       4. The method according to  claim 2 , wherein the positive probabilistic set comprises a bloom filter, further comprising generating the bloom filter by:
 for each of the nodes in the plurality of nodes, generating a replica-specific bloom filter based on an identifier for the respective node; and 
 performing a binary OR operation between the replica-specific bloom filters generated for each of the nodes in the plurality of nodes. 
 
     
     
       5. The method according to  claim 4 , wherein generating a replica-specific bloom filter for a node in the plurality comprises performing a hashing operation on a predetermined identifier for the respective node. 
     
     
       6. The method according to  claim 1 , further comprising maintaining a store of identifiers for nodes that are currently in the cluster, wherein the identifiers in the store are determined by comparing the decoded information with identifiers in the store. 
     
     
       7. The method according to  claim 6 , wherein the positive probabilistic set comprises a bloom filter, and the identifiers in the store are determined by:
 calculating which bits in the bloom filter would have to be set if each of the nodes identified in the store is in the plurality of nodes, wherein the calculating comprises looking up identifiers in the maintained store; and 
 checking for presence of the calculated set bits in the bloom filter. 
 
     
     
       8. The method according to  claim 1 , wherein the encoded information is generated according to an additional deterministic process by a node in the cluster prior to receipt of the update request in relation to a previously requested function replica creation process. 
     
     
       9. The method according to  claim 1 , wherein:
 the positive probabilistic set used by the first node to encode the first determined nodes comprises a first bloom filter. 
 
     
     
       10. The method according to  claim 9 , wherein the positive probabilistic set comprises a bloom filter, further comprising:
 determining nodes on which respective replicas of the function are to be updated according to the deterministic process based on the function identifier and nodes that are determined to be in the cluster at the time of receipt of the update request; 
 generating a second bloom filter to encode the determined nodes where the replicas of the function are to be updated; 
 comparing the first bloom filter to the second bloom filter; and 
 in response to the comparison indicating at least one discrepancy, transmitting at least one further replica function update message to at least one further node to instruct update of its configured replica of the function according to the update requested by the client. 
 
     
     
       11. The method according to  claim 1 , wherein the function comprises a timer function. 
     
     
       12. A non-transitory computer readable storage medium comprising computer-executable instructions that, when executed by a processor of a computing device, cause the computing device to perform operations comprising:
 receiving, from a client by a node of a network comprising a cluster of nodes, a request to apply an update to a function, wherein: 
 the function is instantiated as replicas on a plurality of nodes in the cluster, 
 the update request comprises an identifier of the function, the identifier comprising information encoded using a positive probabilistic set usable to respond to an approximate membership query, the positive probabilistic set selected to conform to a data structure having a desired false positive/negative rate, the information being associated with the nodes on which the function has been configured; 
 the nodes on which the function has been configured are determined by a first node in the cluster; and 
 the nodes are determined according to a deterministic process based on the identifier and the nodes in the cluster when the function is replicated; and 
 decoding the encoded information to identify the nodes on which respective replicas of the function have been configured; and 
 transmitting at least one replica function update message to one or more of the identified nodes to instruct update of their respective configured replicas of the function according to the update requested by the client. 
 
     
     
       13. A system for managing nodes in a network comprising a cluster of nodes configured to provide replicas of functions for clients in the network, the system comprising a processor and a memory storing thereon computer executable instructions that, when executed by the processor, cause the system to perform operations comprising:
 receiving, from a client by a node of the network, a request to apply an update to a function, wherein:
 the function is instantiated as replicas on a plurality of nodes in the cluster, 
 the update request comprises an identifier of the function, the identifier comprising information encoded using a positive probabilistic set usable to respond to an approximate membership query, the positive probabilistic set selected to conform to a data structure having a desired false positive/negative rate, the information being associated with the nodes on which the function has been configured; 
 the nodes on which the function has been configured are determined by a first node in the cluster; and 
 the nodes are determined according to a deterministic process based on the identifier and the nodes in the cluster when the function is replicated; and 
 decoding the encoded information to identify the nodes on which respective replicas of the function have been configured; and 
 transmitting at least one replica function update message to one or more of the identified nodes to instruct update of their respective configured replicas of the function according to the update requested by the client. 
 
 
     
     
       14. The system according to  claim 13 , wherein the positive probabilistic set comprises a bloom filter, a retouched bloom filter, or a quotient filter. 
     
     
       15. The system according to  claim 14 , wherein the positive probabilistic set comprises a bloom filter, wherein the bloom filter is configured to generate a positive response when queried for presence of a predetermined identifier for any of the nodes in the plurality of nodes. 
     
     
       16. The system according to  claim 14 , wherein the positive probabilistic set comprises a bloom filter, further comprising generating the bloom filter by:
 for each of the nodes in the plurality of nodes, generating a replica-specific bloom filter based on an identifier for the respective node; and 
 performing a binary OR operation between the replica-specific bloom filters generated for each of the nodes in the plurality of nodes. 
 
     
     
       17. The system according to  claim 16 , wherein generating a replica-specific bloom filter for a node in the plurality comprises performing a hashing operation on a predetermined identifier for the respective node. 
     
     
       18. The system according to  claim 13 , further comprising maintaining a store of identifiers for nodes that are currently in the cluster, wherein the identifiers in the store are determined by comparing the decoded information with identifiers in the store. 
     
     
       19. The system according to  claim 18 , wherein the positive probabilistic set comprises a bloom filter, and the identifiers in the store are determined by:
 calculating which bits in the bloom filter would have to be set if each of the nodes identified in the store is in the plurality of nodes, wherein the calculating comprises looking up identifiers in the maintained store; and 
 checking for presence of the calculated set bits in the bloom filter. 
 
     
     
       20. The system according to  claim 13 , wherein the function comprises a timer function.