HyperDex utilizes value-dependent chains for replication. Updates move forward in the chains, while acknowledgements flow in reverse.
To issue a PUT or a GET, the client contacts the head of the chain responsible for the object it is modifying/accessing. If other nodes in the chain fail, the chain will transparently recover. If the point leader fails (the head of the chain), then the client does not know if the operation completed.
This is analogous to a database library opening a socket and sending "BEGIN; INSERT INTO data ("x", "y", "z"); COMMIT" and then the client losing connection (or crashing entirely). There is always some point at which the server may complete, and then the client may immediately crash before receiving notification that the operation is complete. Even if this happens, however, HyperDex's GET and PUT operations are linearizable.
What happens if a crash happens part way through the acknowledgement chain?
For example, in your insert, if the node containing "x" crashes before it receives the ACK from the node containing "y" - do the dangling "y" and "z" insertions ever need to be cleaned up?
Comments
HyperDex utilizes value-dependent chains for replication. Updates move forward in the chains, while acknowledgements flow in reverse.
To issue a PUT or a GET, the client contacts the head of the chain responsible for the object it is modifying/accessing. If other nodes in the chain fail, the chain will transparently recover. If the point leader fails (the head of the chain), then the client does not know if the operation completed.
This is analogous to a database library opening a socket and sending "BEGIN; INSERT INTO data ("x", "y", "z"); COMMIT" and then the client losing connection (or crashing entirely). There is always some point at which the server may complete, and then the client may immediately crash before receiving notification that the operation is complete. Even if this happens, however, HyperDex's GET and PUT operations are linearizable.
What happens if a crash happens part way through the acknowledgement chain?
For example, in your insert, if the node containing "x" crashes before it receives the ACK from the node containing "y" - do the dangling "y" and "z" insertions ever need to be cleaned up?
The chains heal in a similar fashion to chain replication (http://www.cs.cornell.edu/home/rvr/papers/osdi04.pdf).
There will be no dangling insertions.