Lock-Free, Scalable Read Access To Shared Data Structures Using Garbage Collection

A non-transitory computer program product storing instructions, which when executed by at least one data processor, result in operations comprising:

• initiating at least one read operation of at least one object of a data container, the data container comprising an anchor object, a first internal data object and a first garbage collection object, the anchor object comprising a pointer to a versioned structure tree;
• creating, in response to the at least one incompatible write operation, a second internal data object and a second garbage collection object for the data container, the second garbage collection object having a reference to the second internal data object;
• installing the second internal data object in the anchor object;
• and
• passing the first garbage collection object to a garbage collection process so that space used by the first garbage collection object in a database can be reused.

A system comprising:

• at least one data processor;
• memory storing instructions, which when executed by at least one data processor, result in operations comprising:
• initiating at least one read operation of at least one object of a data container, the data container comprising an anchor object, a first internal data object and a first garbage collection object, the anchor object comprising a pointer to a versioned structure tree;
• creating, in response to the at least one incompatible write operation, a second internal data object and a second garbage collection object for the data container, the second garbage collection object having a reference to the second internal data object;
• installing the second internal data object in the anchor object;
• and
• passing the first garbage collection object to a garbage collection process so that space used by the first garbage collection object in a database can be reused;
• and
• an in-memory read-only database storing at least one of the objects, the database storing data in rows with monotonically-increasing row identifiers and using multi-version concurrency control.