Granted Patent B2

US 12,292,872 · App. 18/223,541 · Granted May 6, 2025

Inventors: Sarath Lakshman (Mahe, IN); Apaar Gupta (Bangalore, IN); Rohan Ashok Suri, Jr. (Mumbai, 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

Abstract

Claims (79)

1. A computer-implemented method for maintaining data in a data management system, the computer-implemented method comprising:

storing a set of documents in log-structured object store comprising sequence numbers and document value, wherein the log-structured object store maintains documents sequence numbers and document values, the log-structured object store comprising a plurality of log segments;

storing a first log-structured merge-tree mapping keys to sequence numbers for accessing documents of the set of documents;

maintaining a delete list using a second log-structured merge-tree, the delete list comprising a list of stale document sequence numbers and corresponding sizes per log segment;

responsive to receiving a request to delete a document associated with a key,

identifying a sequence number of the deleted document from the first log-structured merge-tree based on the key value;

retrieving a size of the deleted document based on metadata of the deleted document stored in the log-structured object store based on the sequence number; and

recording the sequence number and the size of the deleted document in the second log-structured merge-tree;

for each log segment from the plurality of log segments, determining a measure of fragmentation of the log segment based on sizes of deleted documents of the log segment from the second log-structured merge-tree; and

responsive to the fragmentation exceeding a threshold, initiating a compaction operation for the log segment.

2. The computer-implemented method of claim 1 , further comprising:

receiving, from a client device, a query statement for querying a database that is managed by the data management system, the query statement specifying a key;

searching the key in a cache memory; and

responsive to determining that the key is not available in the cache memory, searching for the key in the first log-structured merge-tree.

3. The computer-implemented method of claim 2 , further comprising:

obtaining a document sequence number by matching the key from the first log-structured merge-tree;

obtaining a document value from a log-structured object store using the document sequence number; and

returning the document value to the client device.

4. The computer-implemented method of claim 1 , wherein determining the measure of fragmentation of the log segment based on the sizes of deleted documents of the log segment from the second log-structured merge-tree comprises, running a range query in the second log-structured merge-tree to identify deleted documents in the log segment.

5. The computer-implemented method of claim 1 , wherein the measure of fragmentation of the log segment based on the sizes of deleted documents of the log segment from the second log-structured merge-tree is determined as a ratio of a number of deleted elements of the log segment as determined from the second log-structured merge-tree and a number of entries in the log segment.

6. The computer-implemented method of claim 1 , wherein the log-structured object store stores the documents in a sorted order, the log-structured object store comprising an index for accessing the documents given a sequence number.

7. The computer-implemented method of claim 1 , further comprising:

receiving one or more requests for updating documents;

appending updated documents to a current log segment;

responsive to the size of the current log segment exceeding a size threshold, marking the current log segment as immutable; and

initializing a new log segment.

8. 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 set of documents in log-structured object store comprising sequence numbers and document value, wherein the log-structured object store maintains documents sequence numbers and document values, the log-structured object store comprising a plurality of log segments;

storing a first log-structured merge-tree mapping keys to sequence numbers for accessing documents of the set of documents;

maintaining a delete list using a second log-structured merge-tree, the delete list comprising a list of stale document sequence numbers and corresponding sizes per log segment;

responsive to receiving a request to delete a document associated with a key,

identifying a sequence number of the deleted document from the first log-structured merge-tree based on the key value;

retrieving a size of the deleted document based on metadata of the deleted document stored in the log-structured object store based on the sequence number; and

recording the sequence number and the size of the deleted document in the second log-structured merge-tree;

for each log segment from the plurality of log segments, determining a measure of fragmentation of the log segment based on sizes of deleted documents of the log segment from the second log-structured merge-tree; and

responsive to the fragmentation exceeding a threshold, initiating a compaction operation for the log segment.

9. The non-transitory computer readable storage medium of claim 8 , the instructions further causing the one or more computer processors to perform steps comprising:

receiving, from a client device, a query statement for querying a database that is managed by the data management system, the query statement specifying a key;

searching the key in a cache memory; and

responsive to determining that the key is not available in the cache memory, searching for the key in the first log-structured merge-tree.

10. The non-transitory computer readable storage medium of claim 9 , the instructions further causing the one or more computer processors to perform steps comprising:

obtaining a document sequence number by matching the key from the first log-structured merge-tree;

obtaining a document value from a log-structured object store using the document sequence number; and

returning the document value to the client device.

11. The non-transitory computer readable storage medium of claim 8 , wherein determining the measure of fragmentation of the log segment based on the sizes of deleted documents of the log segment from the second log-structured merge-tree comprises, running a range query in the second log-structured merge-tree to identify deleted documents in the log segment.

12. The non-transitory computer readable storage medium of claim 8 , wherein the measure of fragmentation of the log segment based on the sizes of deleted documents of the log segment from the second log-structured merge-tree is determined as a ratio of a number of deleted elements of the log segment as determined from the second log-structured merge-tree and a number of entries in the log segment.

13. The non-transitory computer readable storage medium of claim 8 , wherein the log-structured object store stores the documents in a sorted order, the log-structured object store comprising an index for accessing the documents given a sequence number.

14. The non-transitory computer readable storage medium of claim 8 , the instructions further causing the one or more computer processors to perform steps comprising:

receiving one or more requests for updating documents;

appending updated documents to a current log segment;

responsive to the size of the current log segment exceeding a size threshold, marking the current log segment as immutable; and

initializing a new log segment.

15. 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 set of documents in log-structured object store comprising sequence numbers and document value, wherein the log-structured object store maintains documents sequence numbers and document values, the log-structured object store comprising a plurality of log segments;

storing a first log-structured merge-tree mapping keys to sequence numbers for accessing documents of the set of documents;

maintaining a delete list using a second log-structured merge-tree, the delete list comprising a list of stale document sequence numbers and corresponding sizes per log segment;

responsive to receiving a request to delete a document associated with a key,

identifying a sequence number of the deleted document from the first log-structured merge-tree based on the key value;

retrieving a size of the deleted document based on metadata of the deleted document stored in the log-structured object store based on the sequence number; and

recording the sequence number and the size of the deleted document in the second log-structured merge-tree;

for each log segment from the plurality of log segments, determining a measure of fragmentation of the log segment based on sizes of deleted documents of the log segment from the second log-structured merge-tree; and

responsive to the fragmentation exceeding a threshold, initiating a compaction operation for the log segment.

16. The computer system of claim 15 , the instructions further causing the one or more computer processors to perform steps comprising:

receiving, from a client device, a query statement for querying a database that is managed by the data management system, the query statement specifying a key;

searching the key in a cache memory; and

responsive to determining that the key is not available in the cache memory, searching for the key in the first log-structured merge-tree.

17. The computer system of claim 16 , the instructions further causing the one or more computer processors to perform steps comprising:

obtaining a document sequence number by matching the key from the first log-structured merge-tree;

obtaining a document value from a log-structured object store using the document sequence number; and

returning the document value to the client device.

18. The computer system of claim 15 , wherein determining the measure of fragmentation of the log segment based on the sizes of deleted documents of the log segment from the second log-structured merge-tree comprises, running a range query in the second log-structured merge-tree to identify deleted documents in the log segment.

19. The computer system of claim 15 , wherein the measure of fragmentation of the log segment based on the sizes of deleted documents of the log segment from the second log-structured merge-tree is determined as a ratio of a number of deleted elements of the log segment as determined from the second log-structured merge-tree and a number of entries in the log segment.

20. The computer system of claim 15 , the instructions further causing the one or more computer processors to perform steps comprising:

receiving one or more requests for updating documents;

appending updated documents to a current log segment;

responsive to the size of the current log segment exceeding a size threshold, marking the current log segment as immutable; and

initializing a new log segment.

Assignments (2)

Priority Claims (1)

Continuity (1)

References Cited (13)