System for indexing collections of structured objects that provides strong multiversioning semantics

摘要

A multiversioned position-space indexing system is disclosed. The system includes data structures for maintaining a multiversioned position space including a multi-versioned filter merge list which represents many versions of a changing position space in a very compact form and a position shift map which describes how to translate stored positions in many different log-structured merge tree layers into logical positions at a particular timestamp. Each log-structured merge tree layer can be divided into two sublayers: a final sublayer and a correction sublayer. The final sublayer contains index entries added after the layer's start timestamp and remain live as of the layer's final timestamp as well as deletion makers for index entries that were inserted before the layer's start timestamp, but deleted before the layer's final timestamp. The correction layer contains index entries that were both created and deleted between the start and end timestamps of the layer.

主权项

1. A method for multiversioned position-space indexing of a storage system, the method comprising:
creating, by data processing hardware, an empty index; adding, by the data processing hardware, at least one data entry to the index; creating, by the data processing hardware, a new index layer that includes all data entries added since a last layer creation; dividing, by the data processing hardware, the index layer into sublayers; storing, by the data processing hardware, the index entry in a local position space of an appropriate one of the sublayers, associating the entry with a range of positions occupied by an object to which the entry corresponds; creating, by the data processing hardware, a global position space to expose an index snapshot of the index; exposing, by the data processing hardware, index entries and the entries' global positions in the snapshot using a mapping between each layer's local position space and the index's global position space; querying a particular timestamp of the index snapshot; constructing, by the data processing hardware, a liveness map for the particular timestamp before reading any index entries, the liveness map mapping live index entries having positions known to be live at the particular timestamp; and exposing, by the data processing hardware, the live index entries in the constructed liveness map while bypassing all non-live index entries having positions that fall within non-live position ranges.