Compaction of documents in a high density data storage system
A system stores multiple documents in a log-structured object store, each document associated with a sequence number and a document value. The log-structured object store includes multiple log segments, each storing documents within a defined sequence number range. A first log-structured merge-tree is maintained to map document keys to corresponding sequence numbers, while a second log-structured merge-tree maps sizes of stale documents to their sequence numbers. A ratio is determined between the size of stale documents and the total size of documents in at least one log segment. In response to the ratio exceeding a predetermined threshold, a compaction operation is initiated to delete stale documents and consolidate active documents into a reduced number of log segments using the reclaimed space. The first and second log-structured merge-trees are updated based on the compaction results to reflect the current state of the data.
1 . A computer-implemented method for maintaining data in a data management system, the computer-implemented method comprising:
storing a plurality of documents in a log-structured object store, each document associated with a sequence number and a document value, wherein the log-structured object store comprises a plurality of log segments, each log segment storing a subset of documents that were written within a sequence number range;
maintaining, in a first log-structured merge-tree, mapping document keys associated with documents to corresponding sequence numbers, the documents including active documents and stale documents;
maintaining, in a second log-structured merge-tree, mapping sizes of stale documents to stale document sequence numbers;
determining a ratio between a size of stale documents and a total size of all documents stored in at least one log segment exceeds a predetermined threshold based on the first log-structured merge-tree and the second log-structured merge-tree;
performing a compaction operation on the log-structured object store, comprising:
deleting stale documents in the log-structured object store; and
consolidating active documents into fewer number of log segments using space freed up from the deleted stale documents; and
updating the first log-structured merge-tree and the second log-structured merge-tree based on the compacted log segment.
2 . The computer-implemented method of claim 1 , wherein the sequence numbers are monotonically increasing values assigned based on an order in which the documents were written to the log-structured object store.
3 . The computer-implemented method of claim 1 , wherein the compaction operation further comprises generating a sorted list of sequence numbers associated with stale documents and performing a sort-merge with the documents in the log segment to identify the stale documents.
4 . The computer-implemented method of claim 1 , further comprising maintaining an in-memory counter for each log segment, the in-memory counter tracking a cumulative size of stale documents in a respective log segment.
5 . The computer-implemented method of claim 1 , wherein performing the compaction operation further comprises rewriting a log segment while skipping documents identified by the second log-structured merge-tree as stale.
6 . The computer-implemented method of claim 1 , wherein the first log-structured merge-tree comprises a byKey index mapping document keys to sequence numbers, and the second log-structured merge-tree comprises a delete list storing key-value pairs of sequence number and document size.
7 . The computer-implemented method of claim 1 , wherein the documents are stored in the log-structured object store in a sequential, append-only manner.
8 . The computer-implemented method of claim 1 , further comprising determining a fragmentation value for a log segment based on the ratio between a cumulative size of stale documents and a total size of all documents in the log segment.
9 . The computer-implemented method of claim 1 , wherein the compaction operation is performed asynchronously by a background thread to avoid blocking write operations to the log-structured object store.
10 . The computer-implemented method of claim 1 , wherein updating the first log-structured merge-tree comprises updating document key to sequence number mappings for active documents consolidated during compaction.
11 . The computer-implemented method of claim 1 , further comprising maintaining a metadata snapshot of the first log-structured merge-tree and the second log-structured merge-tree for crash recovery, the metadata snapshot comprising a pointer to a last persisted write-ahead log offset.
12 . The computer-implemented method of claim 1 , wherein the log-structured object store comprises a tail log segment configured to store newly written documents, and wherein older segments are made immutable once a size threshold is reached.
13 . The computer-implemented method of claim 1 , wherein the second log-structured merge-tree is implemented using a sequence-indexed LSM Tree and supports range queries over sequence numbers corresponding to stale documents.
14 . A non-transitory computer readable storage medium storing instructions that when executed by one or more computer processors, cause the one or more computer processors to perform steps for maintaining data in a data management system, the steps comprising:
storing a plurality of documents in a log-structured object store, each document associated with a sequence number and a document value, wherein the log-structured object store comprises a plurality of log segments, each log segment storing a subset of documents that were written within a sequence number range;
maintaining, in a first log-structured merge-tree, mapping document keys associated with documents to corresponding sequence numbers, the documents including active documents and stale documents;
maintaining, in a second log-structured merge-tree, mapping sizes of stale documents to stale document sequence numbers;
determining a ratio between a size of stale documents and a total size of all documents stored in at least one log segment exceeds a predetermined threshold based on the first log-structured merge-tree and the second log-structured merge-tree;
performing a compaction operation on the log-structured object store, comprising:
deleting stale documents in the log-structured object store; and
consolidating active documents into fewer number of log segments using space freed up from the deleted stale documents; and
updating the first log-structured merge-tree and the second log-structured merge-tree based on the compacted log segment.
15 . The non-transitory computer readable storage medium of claim 14 , wherein the sequence numbers are monotonically increasing values assigned based on an order in which the documents were written to the log-structured object store.
16 . The non-transitory computer readable storage medium of claim 14 , wherein the compaction operation further comprises generating a sorted list of sequence numbers associated with stale documents and performing a sort-merge with the documents in the log segment to identify the stale documents.
17 . The non-transitory computer readable storage medium of claim 14 , further comprising maintaining an in-memory counter for each log segment, the in-memory counter tracking a cumulative size of stale documents in a respective log segment.
18 . The non-transitory computer readable storage medium of claim 14 , wherein performing the compaction operation further comprises rewriting a log segment while skipping documents identified by the second log-structured merge-tree as stale.
19 . The non-transitory computer readable storage medium of claim 14 , wherein the first log-structured merge-tree comprises a byKey index mapping document keys to sequence numbers, and the second log-structured merge-tree comprises a delete list storing key-value pairs of sequence number and document size.
20 . A computer system comprising:
one or more computer processors; and
a non-transitory computer readable storage medium storing instructions that when executed by one or more computer processors, cause the one or more computer processors to perform steps for maintaining data in a data management system, the steps comprising:
storing a plurality of documents in a log-structured object store, each document associated with a sequence number and a document value, wherein the log-structured object store comprises a plurality of log segments, each log segment storing a subset of documents that were written within a sequence number range;
maintaining, in a first log-structured merge-tree, mapping document keys associated with documents to corresponding sequence numbers, the documents including active documents and stale documents;
maintaining, in a second log-structured merge-tree, mapping sizes of stale documents to stale document sequence numbers;
determining a ratio between a size of stale documents and a total size of all documents stored in at least one log segment exceeds a predetermined threshold based on the first log-structured merge-tree and the second log-structured merge-tree;
performing a compaction operation on the log-structured object store, comprising:
deleting stale documents in the log-structured object store; and
consolidating active documents into fewer number of log segments using space freed up from the deleted stale documents; and
updating the first log-structured merge-tree and the second log-structured merge-tree based on the compacted log segment.