Conflict Resolution and Garbage Collection in Distributed Databases

A distributed data storage system comprising:

• one or more processors;
• a first key data store at a first location comprising a plurality of first key entries, each first key entry of the plurality of first key entries comprising a corresponding first key having an object identifier, an inverse timestamp, and a source identifier identifying a requester of an associated storage operation represented by that first key entry;
• a second key data store at a second location comprising a plurality of second key entries, each second key entry of the plurality of second key entries comprising a corresponding second key having an object identifier, an inverse timestamp, and a source identifier identifying a requester of an associated storage operation represented by that second key entry;
• and
• a synchronization application executable by the one or more processors to perform operations comprising:
• replicating a set of the first key entries from the first key data store to the second key data store;
• and
• inserting each first key entry from the set of the first key entries into the second key data store based on the object identifier, the inverse timestamp, and the source identifier of the first key included in that first key entry, the set of the first key entries being interwoven with the plurality of second key entries upon insertion to form a plurality of interwoven ordered key entries.

A system comprising:

• means for storing a plurality of first key entries in a first key data store located at a first location, each first key entry of the plurality of first key entries comprising a corresponding first key having an object identifier, an inverse timestamp, and a source identifier identifying a requester of an associated storage operation represented by that first key entry;
• means for storing a plurality of second key entries in a second key data store located at a second location, each second key entry of the plurality of second key entries comprising a corresponding second key having an object identifier, an inverse timestamp, and a source identifier identifying a requester of an associated storage operation represented by that second key entry;
• means for replicating a set of the first key entries from the first key data store to the second key data store;
• and
• means for inserting each first key entry from the set of the first key entries into the second key data store based on the object identifier, the inverse timestamp, and the source identifier of the first key included in that first key entry, the set of the first key entries being interwoven with the plurality of second key entries upon insertion to form a plurality of interwoven ordered key entries.