IP Library › Granted Patent US 12705225
Granted Patent B2
US 12705225 · App. 19/097,520 · Granted Aug 11, 2026

Compaction of documents in a high density data storage system

Inventors: Sarath Lakshman (Pandakkal, IN); Apaar Gupta (Domlur, IN); Rohan Ashok Suri (Maharashtra, IN); Scott David Lashley (Portland, OR); John Sae Liang (Palo Alto, CA); Srinath Duvuru (Portland, OR); David James Oliver Rigby (Manchester, GB)
Assignee: Couchbase, Inc.
G06F16/2246G06F12/0253G06F16/2358G06F16/24552G06F16/24561G06F16/93
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12705225
App. No.
19/097,520
Granted
Aug 11, 2026
Kind
B2
Abstract

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.

Claims (46)

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.