EP4558904A1 - Stockage de données haute densité basé sur des techniques de stockage à structure logarithmique - Google Patents

Stockage de données haute densité basé sur des techniques de stockage à structure logarithmique

Info

Publication number
EP4558904A1
EP4558904A1 EP23752111.7A EP23752111A EP4558904A1 EP 4558904 A1 EP4558904 A1 EP 4558904A1 EP 23752111 A EP23752111 A EP 23752111A EP 4558904 A1 EP4558904 A1 EP 4558904A1
Authority
EP
European Patent Office
Prior art keywords
log
documents
structured
tree
key
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
EP23752111.7A
Other languages
German (de)
English (en)
Inventor
Sarath LAKSHMAN
Apaar GUPTA
Rohan Ashok SURI
Scott David Lashley
John Sae Liang
Srinath Duvuru
David James Oliver RIGBY
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Couchbase Inc
Original Assignee
Couchbase Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US18/223,540 external-priority patent/US12287771B2/en
Application filed by Couchbase Inc filed Critical Couchbase Inc
Publication of EP4558904A1 publication Critical patent/EP4558904A1/fr
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2246—Trees, e.g. B+trees
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G06F16/2455—Query execution
    • G06F16/24552—Database cache management
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/28—Databases characterised by their database models, e.g. relational or object models

Definitions

  • This disclosure relates in general to databases, and in particular to a high-density data storage system based on log-structured merge trees and log-structured object storage.
  • Embodiments of a di sclosed system, computer-implemented method, and computer readable storage medium use a write-optimized high data density key- value storage engine.
  • the system uses a hybrid key-value storage engine that combines log structured merge trees (LSM Trees) and a segmented log-structured object storage.
  • LSM Trees log structured merge trees
  • the system performs efficient garbage collection of stale document versions.
  • the system separates index and document data to minimize write amplification.
  • the storage engine also performs a scalable and incremental compaction.
  • the system stores a set of documents in log- structured object store comprising sequence numbers and document values.
  • the log- structured object store stores documents of the set of documents in a sorted order and comprises an index for accessing a document given a sequence number.
  • the system stores a log-structured merge tree that maps keys to sequence numbers for accessing documents of the set of documents.
  • the system receives a query statement for querying a database that is managed by the data management system.
  • the query statement specifies a key.
  • the system searches the key in a cache memory. If the key is not found in the cache memory, the system searches for the key in the log-structured merge tree.
  • the system obtains a document sequence number by matching the key from the log-structured merge tree.
  • the system obtains a document value from a log-structured object store that maintains documents sequence numbers and document values.
  • the system returns the document value to the requestor.
  • the write amplification in the LSM tree is minimized by separating the storage of the sequence number from document values.
  • the system stores a first log-structured merge-tree mapping keys to sequence numbers for accessing documents of the set of documents and maintains a delete list using a second log-structured merge-tree.
  • the delete list comprises a list of stale document sequence numbers and corresponding sizes per log segment.
  • the system determines 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. If the fragmentation exceeds a threshold, the system initiates a compaction operation for the log segment.
  • the system is able to efficiently determine the measure of fragmentation of the log segment based on the delete list using a second log-structured merge-tree.
  • Embodiments include non-transitory storage media storing instructions that cause one or more computer processes to perform steps of the processes disclosed herein .
  • Embodiments include, computer systems including computer processors and non- transitory storage media storing instructions of the processes.
  • FIG. 1 shows an overall architecture of a distributed database system according to an embodiment.
  • FIG. 2 shows the interactions between various components of the database system according to an embodiment.
  • FIG. 3 A shows the system architecture of a key-value storage engine according to an embodiment.
  • FIG. 3B shows the interactions between different components of the system architecture of a key- value storage engine according to an embodiment.
  • FIG. 4 shows a flowchart illustrating a process for processing queries according to an embodiment.
  • FIG. 5 illustrates the process of performing mutations on the database, according to an embodiment.
  • FIG. 6 illustrates the process of compaction using an example, according to an embodiment.
  • FIG. 7 illustrates the log structure object store representation of the database according to an embodiment.
  • FIG. 8 illustrates use of a delete list for performing delete operations according to an embodiment.
  • FIG. 11 shows a flowchart illustrating the process of garbage collection according to an embodiment.
  • FIG. 12 illustrates storing information describing hot or cold writes according to an embodiment.
  • FIG. 13 is a high-level block diagram illustrating a functional view of a typical computer system according to an embodiment.
  • the figures depict various embodiments for purposes of illustration only. One skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the embodiments described herein.
  • Embodiments of the system improve storage efficiency in handling large data volume per node, thereby allowing storage capacity to be increased without having to add additional nodes.
  • the system supports higher data density and higher write throughput by using a storage engine architecture that lowers write amplification and avoids expensive compaction operations that rewrite the whole database.
  • the vBucket key-value store supports various features that can be invoked using application programming interfaces (APIs).
  • a write document API receives as input, a list of documents and persists it to the key-value store. Every document update has a monotonically increasing sequence number generated by the data service.
  • a read document API performs a batch read of a list of documents referenced by the document key. These are individual key lookup operations.
  • a change feed API exposes a change log interface to the vBucket, It provides an ordered stream of document mutations by sequence number. This change log is a backend for several services within the database to consume changes and keep them in sync with the document changes.
  • a rollback API allows to revert the database to a prior checkpointed state. Accordingly, the database keeps few prior checkpoints of the data in-order for rollback to go back in time and revert to the older version.
  • the vBucket key-value store uses single writer, multiple readers concurrency model.
  • FIG. 2 show's the interactions between various components of the database system according to an embodiment.
  • the data service maintains an in-memory hash table based document cache for each vBucket.
  • the actively read and recently written documents are stored in the cache.
  • Each document in the cache can be retrieved by the document key of the document. If the document is not present in the cache, the system retrieves the document using the key- value store.
  • DCP database change protocol
  • the system implements a copy-on-write B+Tree (also referred to as COW B+Tree) that is an adaptation of B+Tree for log structured storage model.
  • a copy-on-write B+Tree also referred to as COW B+Tree
  • COW B+Tree a copy-on-write B+Tree
  • the log structured write model performs better for spinning disks as well as SSDs.
  • B+Tree comprises intermediate pages and leaf pages. The leaf page stores key record pairs and intermediate pages store key -value pairs with value being the file offsets of pointing pages within the same file.
  • the system implements a B+Tree modification that involves read-modify-write scheme for the B+Tree page.
  • the system locates the leaf page where the record key belongs by traversing the tree from root page, navigating through the intermediate nodes.
  • the system makes a copy of the page in-mcmory and makes the modifica tion in the page to add or remove the record.
  • the new version of the page is appended to the database file. Since the location of the leaf page has changed to a new off set, the system updates the intermediate node that points to the leaf node. Similarly, all the intermediate pages up to the root page are rewritten to update the new page locations.
  • a record is modified or added, the system may have to copy a leaf node, an intermediate node, and root node.
  • the older version of the pages become stale in toe file as the current B+Tree points to the recently updated pages.
  • the modification in the page is performed in the units of a single page. Therefore, even if a single record is added or removed, the page in the unit of disk block size needs to be rewritten. Every leaf page modification results in multiple pages to be rewritten thereby causing write amplification.
  • the system reduces toe write amplification cost by batching of writes.
  • the system performs the modification in a single rewrite.
  • the rewrites of several intermediate pages may also be combined.
  • the system performs write queuing and deduplication before applying a batch of updates to the B+tree to reduce write amplification.
  • toe system determines the root B+Tree page offset of the current version of the tree. From the root page, the system determines the file offsets for the intermediate pages and further locates the leaf page.
  • the system performs a compaction operation using a background thread.
  • the system obtains the current B+tree root offset and opens a B+tree iterator.
  • the system opens a new database file and performs a B+Tree bulk load operation to the new file to rebuild the B+tree.
  • tire writes may be still ongoing with the old database file.
  • the compactor operates on a point-in-time version of the B+tree.
  • the system runs a catchup phase to replay over the new additions/deletions that happened to the B+Tree from the point-in-time version used by the compactor up to the latest B+Tree in the database file.
  • the old database file is removed, and writers and readers switch to the new database file. The space is reclaimed.
  • FIG. 3A shows the system architecture of a key-value storage engine according to an embodiment.
  • the key- value storage engine includes a write-cache 310, a write-ahead log 320. a LSM tree index 330, a log structured object store 340, and an index block cache 350.
  • the storage engine follows a log-structured storage model which is optimized for point lookups by key as well as providing a changelog from the database efficiently.
  • the storage engine design puts emphasis on storage efficiency to achieve performance with large database size to achieve high data density per node.
  • the storage engine achieves high write transaction throughput by maintaining low write amplification, scalable compactions while not regressing on the read performance.
  • FIG. 3B shows the interactions between different components of the system architecture of a key- value storage engine according to an embodiment.
  • the write-cache 310 is an in-memory component used to buffer key-value pairs and provide large sequential writes to the persistent storage.
  • the write-cache is also used during lookup for key-value pairs.
  • the write cache may be implemented using a lock-free skip list. Fixed memory is configured for the write-cache and is internally split into two skip lists as active and immutable. When the system reaches the configured memory limit, the cache is flushed to the key index and log-structured object storage on the SSD.
  • the write-ahead log (WAL) 320 is an append-only log where the incoming key-value pair writes are initially written to provide durability'. Writes are initially buffered in the write-cache and also written to the write-ahead log. The write API returns only after issuing an fsync (file sync operation) on the write-ahead log file. Periodically, the space used by the write-ahead log is reclaimed when the write-cache is flushed.
  • the LSM Tree index 330 is an index for the documents stored on a log structured object store is organized as an LSM Tree.
  • the LSM Tree index stores document key, document sequence number, and size metadata as key-value pairs.
  • tire LSM Tree is initially looked up to obtain the document sequence number which is used to read the document value from the log-structured object storage.
  • the LSM tree index maintains bloom filters to optimize the lookup I/O.
  • the log-structured object store 340 provides persistent storage for the documents by organizing them on an append-only segmented log.
  • the log-structured store maintains an index that allows querying of a document by sequence number.
  • the log-structured store also allows range query by sequence number essentially providing a changelog for the document database.
  • the index block cache 350 is a read cache that is maintained in RAM for caching the recently read index blocks from the LSM Tree as well as the log-structured object store.
  • a least recently used (LRU) eviction policy is used to manage the cache.
  • This cache does not keep the actual document data, but only the index blocks used to locate the documents on log-structured storage.
  • the system maintains a vBucket level document cache.
  • This object-level managed cache is more efficient than block-level cache for document objects.
  • the unit ofcaching in a block cache is of size, 4 KB.
  • the document cache can perform the caching at a single document level and avoid wasting memory for keeping cold documents grouped in a physical block on the SSD.
  • the storage engine includes a by Key Index (also referred to as a key index), a bySeq Index (also referred to as a sequence index), and a value store.
  • the byKey Index serves the purpose of answering point-lookup based on document key.
  • the bySeq index receives and processes range queries based on document sequence based ranges for a vBucket.
  • FIG. 4 shows a flowchart illustrating a process for processing queries according to an embodiment.
  • the system receives 410 a query for accessing data from the database.
  • the query specifies a key.
  • the query may be received from a client device.
  • the system searches 420 for the key in the cache memory. If the system finds the key in the cache memory, the system accesses the value corresponding to the key from the cache and returns the value to the client device as the result of the query. If the key is not found in the cache the system searches for the key using the by Key index represented as an LSM tree.
  • the system obtains a document sequence number from the byKey index.
  • the system further searches for the document in the log-structured object store using the document sequence number.
  • the system obtains a document value from the log- structured object store using the document sequence number.
  • the system returns the document value to the client device that sent the query.
  • FIG. 5 illustrates the process of performing mutations on the database, according to an embodiment.
  • the system receives, from a client device, a request to perform a mutation operation to a database that is managed by the system.
  • the system stores information describing the mutation operation in a cache memory.
  • the system maintains two lists in the cache memory, a list indexed by keys and a list indexed by sequence numbers.
  • the system writes the mutation to a write-ahead log.
  • the system tracks the number of mutation records in the cache memory. If the number of records stored in the cache memory exceed a threshold, the system stores the content of the cache memory in a persistent storage. This operation is performed by (1) converting key-value pairs into key index for a log-structured merge tree (LSM tree) and (2) appending documents to a tail log-segment of a log-structured object store. The system clears the cache memory' and returns an indication to the client device that the mutation operation has successfully performed to the database.
  • LSM tree log-structured merge tree
  • FIG. 6 illustrates the process of compaction using an example, according to an embodiment.
  • FIG. 6 shows the LSM tree before and after compaction.
  • the intermediate node 610 is identified and merged with the leaf level nodes 620a and 620b.
  • the system uses LSM Tree for implementing the byKey index. If the document value is placed along with the key in the byKey index, when LSM Tree runs compaction operations to maintain the tree balance for read and space amplification, a value gets rewritten many times (Up to 40 times for a 4 level tree). To overcome unnecessary write amplification, the storage engine places values in a separate log structured storage and uses sequence number based logical addressing. Instead of actual values, a value pointer is stored in the byKey index in the place of value along with the key. The system maintains a separate storage system tuned for storing large values. When the value storage internal segments (unit of storage) become fragmented, the system cleans the segments by rewriting the values to a new segment.
  • a value pointer is a physical offset derived based on a segment’s position within the blocks of the segment, when valid values are rewritten to a new segment, the original value pointers become invalid.
  • the system updates the corresponding value pointer offsets in the byKey Index. While cleaning a value store segment, the system determines whether each value is valid or not by performing a lookup into the byKey index. This involves an I/O (input/output) operation per value.
  • the system asynchronously propagates deletes to bySeq index as well as value store.
  • value store uses value__pointer to mark the delete bitmaps.
  • the bySeq index is implemented as a log that always grows at the tail.
  • compaction is performed for byKey index, it generates a list of seq numbers to be removed from the bySeq index.
  • the byKey Index provides a facility for lazy deletion of entries from the bySeq index.
  • the system uses an LSM Tree for the bySeq index and a memory table (write cache) accumulates operations to be applied for the LSM Tree. Both update mutations as well as delete sequence entries coming from the byKey LSM Tree compaction are accumulated by the memory table. Once the memory table becomes full, the operations of the memory' table are written out to level-0 and as levels become bigger, they get compacted to the next level and so on until it reaches the final level.
  • FIG. 7 illustrates the log structure object store representation of the database according to an embodiment.
  • the log structure object store comprises multiple log segments 720.
  • Each log segment 720 has an index 710 by sequence number to fetch entri es of the log.
  • the system uses a segmented append only fog for document storage. All mutations of the documents and deletions of the documents (tombstones) are appended in this log. Each document version or modification has a unique sequence number generated by the server.
  • the log comprises fog segments with predefined sizes.
  • the storage engine maintains a tail log file. As writes occur, document mutations are appended to the tail log. Once the tail log file reaches the size threshold, a current tog file is made immutable, and a new tail log file is initialized.
  • a tail log file may also be referred to herein as a fog segment.
  • the stored documents in the log are also indexed by the document mutation sequence number.
  • the indexing scheme is based on copy-on-write B+Tree. Since die inserts are keyed by sequence number and the writes always happen in monotonic order, tire index structure doesn’t incur significant write amplification.
  • the system uses ssTable representation for log segment implementation. An ssTable is also referred to as a sorted string table. The list of log segments along with stalling and ending sequence numbers are maintained in memory.
  • the ssTable uses a BTree or B+Tree representation and may use a bloom filter to determine whether a record or a document is present in die ssTable or not.
  • the ssTable stores the key or a sequence number to identify the document.
  • the system looks up the in-memory sorted list to locate the log segment. Then, the system uses the ssTable B+Tree to locate the document from the log segment.
  • the tail log segment can be viewed as a streaming ssTable where new documents are always appended on writes. Since the key is sequence number of 64 bytes, the size of the index B+tree is small compared to the total data stored in the log. Since the document versions are stored contiguously on SSDs via large size log segments, the database change log API issues large sequential reads from the SSD.
  • the system achieves high read throughput.
  • the system When a document is updated multiple times, the system generates different versions with unique sequence numbers.
  • the log can contain multiple versions of the same key.
  • the older versions of the same document are considered stale.
  • the sy stem garbage collects stale versions to reclaim space.
  • the log-structured object store uses a write buffer to issue large writes to the tail log segment. This also limits the write amplification of tire index B+tree as a larger number of records are always filled within B+tree pages.
  • FIG. 8 illustrates use of a delete list for performing delete operations according to an embodiment.
  • the byKey index provides the list of sequence numbers to be removed during periodic compactions.
  • the system generates a delete list 810 per segment 720 that allows the system to clean segments incrementally by using the metadata provided by the delete list.
  • the ratio of the number of elements in the delete list vs number of entries in the segment file provides an approximate fragmentation.
  • the system maintains an append only sequence delete list file per log segment, that is sufficient to compute fragmentation in each log segment.
  • delete sequences appear in random order and may span across several segments. If it spans across all the segments, it requires fsyncQ per delete list file equal to tire number of segments and is very expensive.
  • the fsync() operation forces a physical write of data from the cache to the secondary storage (or disk) and is therefore very'' expensive since it requires significant input/output (I/O).
  • I/O input/output
  • the system uses an LSM Tree to store delete seq list.
  • FIG. 9 illustrates die use of an LSM tree to store delete sequence list according to an embodiment.
  • the LSM tree 910 may store the delete sequence list using one or more levels. This allows the sy stem to store the delete sequence number list in a cost effective manner.
  • a range query is executed in the delete sequence list LSM Tree.
  • the system stores sorted string tables (also referred to as ssTables) based on key-value pairs.
  • the ssTables for the delete list LSM is created when byKey index compaction is performed. As values get garbage collected during compaction, those sequence numbers along with some additional metadata can be appended to a temporary file. The same temporary file can be used across multiple compactions. Once the temporary file becomes sufficient in size, it can be sorted and a new delete list ssTable can be created. This ssTable can be directly injected to the level-0 of the delete list LSM Tree.
  • the specialized value store provided the ability to maintain low write amplification for large values by performing log segment garbage collection based on fragmentation in the log segments. This method avoids rewrites due to the LSM "free multiple levels of compaction.
  • the sequence log described above works similar to the value store. The sequence log has log segments based on a threshold size. Instead of physical log offset, sequence log provides lookup based on a sequence number facilitated by a sequence number index. If the system stores values along with the keys in the sequence log, each segment can be rewriten based on the fragmentation in the log.
  • the system stores value sizes along with the delete list sequence numbers.
  • the system adds the value sizes to compute total fragmentation in a segment.
  • An in-memory usage counter is maintained per segment.
  • the in-memory counter is updated every time a delete list ssTable is pushed to the LSM Tree.
  • the usage counter values for each log segment are snapshotted along with every ssTable push to the sequence delete LSM free.
  • the log segment cleaning involves querying the delete list LSM and rewriting the log segment by filtering out the sequence numbers listed by delete list query . This operation is similar to LSM ssTable compaction. These operations do not involve any expensive lookup into the byKey index (causing 1 IOP per lookup).
  • the overall solution is implemented as an extension of the cus tomized LSM Tree.
  • the level based compaction algorithm looks for overflowing levels based on level size ratio for performing compaction operation.
  • Typical, size multiplier is 10.
  • F IG. 10 il lustrates determining a logical size of the delete values for determining whether to perform compaction according to an embodiment.
  • the system may compute a logical size 1010 based on the sum of value sizes (from each delete seq). This makes the delete list ssTables sizes comparable to the bottom level special log data segments. If the system does not compute logical sizes without considering value sizes, delete list level may never compact with special bottom level as the size ratios diverge widely.
  • the delete list contains seqnum and value size (total 16 bytes) vs each corresponding key-value pair may be in KBs.
  • the system may rewrite some of the values which may have already marked as deleted in the upper levels of delete list LSM. So, the system performs a query on log segment sequence range on the LSM Tree to perform the log segment rewrite.
  • FIG. 11 shows a flowchart illustrating the process of garbage collection according to an embodiment.
  • the system stores a set of documents in the log-structured object store and further stores 1110 a log-structured merge-tree T1 mapping keys to sequence numbers for accessing documents of the set of documents.
  • the log-structured object store comprises a plurality of log segments.
  • the system further stores 1120 a second log-structured merge-tree T2 for maintaining a delete list.
  • the delete list comprises a list of stale document sequence numbers and corresponding sizes per log segment.
  • the system determines 1130 a measure of fragmentation of the log segment based on sizes of deleted documents of the log segment from the log-structured merge-tree T2. If tire fragmentation for a log segment exceeds a threshold, the system initiates 1140 a compaction operation for the log segment.
  • the system implements the delete list LSM Tree on top of the log-structured storage log segments to form a master LSM Tree. Instead of using the ssTable sizes for the LSM Tree level size thresholds, the system uses a logical size using the document size information encoded in the delete list LSM Tree. Each ssTable has a logical size which is the sum of all document sizes encoded in the key-value pair. The logical size is used for computing the level size and triggering compactions. This modification normalizes the size of log segments and the delete list LSM tree ssTables.
  • the delete list LS M Tree level size targets are also derived based on the total file size of the log-structured store.
  • the head side of the log behaves similar to separate cold log in special value store.
  • the disclosed systems and methods simplify the number of moving parts in the system by unifying large value storage to sequence tree.
  • the disclosed systems and methods save the lookup I/O per item required for value relocation (for valid items).
  • the disclosed systems and methods eliminate duplicate key storage in value store (reduces space amplification).
  • the disclosed systems and methods save the additional CPU required for value store writes, relocations, overhead of maintaining hot-cold classification and cleaning operation.
  • the write amplification savings due to separate value store are also applicable in unified seq tree. For seq tree iterations, earlier lookup into key Index and a read from value store were required for fetching a separated i tem. With sequence log, an additional one I/O can be saved.
  • the sy stem maintains a delete list memory table (also referred to as a memtable), the memory table could be used to accumulate a delete list when seq tree reads are performed.
  • the system merges delete list and log segments. For each valid seq item, the system checks it against the key index. If a seq is not found in the keyindex, the system may place an insert into the delete list memory table.
  • the delete list is populated asynchronously during seq tree reads. This is much simpler and robust than only relying on key Index compaction to generate ssTables for delete list. The delete list can be inconsistent and it will be auto repaired on the next set of reads.
  • the techniques disclosed herein improve the storage efficiency and capacity of the database system.
  • the system allows the database to store a significantly larger amount of data per node.
  • the database sy stem is able to store a larger amount of data without having to add additional nodes to the distributed system.
  • the system is able to achieve the same performance with significantly smaller main memory. This is achieved as a result of storing only sequence numbers in the LSM tree instead of document values. The sequence numbers occupy significantly less storage, thereby reducing the memory requirement.
  • the system performs a scalable compaction that does not require rewrite of the entire database.
  • the system supports much higher write rate for the database and is optimized for write operations.
  • the system addresses the problem of write amplification that causes a much larger amount of data to be written to the storage for every write operation.
  • the system reduces the amount of data that is written to the storage for a write operation.
  • FIG. 13 is a high-level block diagram illustrating a functional view of a typical computer system according to an embodiment. Illustrated are at least one processor 1302 coupled to a chipset 1304. Also coupled to the chipset 1304 are a memory' 1306, a storage device 1308, a keyboard 1310, a graphics adapter 1312, a pointing device 1314, and a network adapter 1316. A display 1318 is coupled to the graphics adapter 1312. In one embodiment, the functionality of the chipset 1304 is provided by a memory controller hub 1320 and an I/O controller hub 1322. In another embodiment, the memory 1306 is coupled directly to the processor 1302 instead of the chipset 1304.
  • a computer 1300 can have different and/or other components than those shown in FIG. 13.
  • the computer 1300 can lack certain illustrated components.
  • a computer system 1300 acting as a server computer may lack a keyboard 1310 and a pointing device 1314.
  • the storage device 1308 can be local and/or remote from the computer 1300 (such as embodied within a storage area network (SAN)).
  • SAN storage area network
  • the computer 1300 is adapted to execute computer modules for providing the functionality described herein.
  • module refers to computer program instruction and other logic for providing a specified functionality.
  • a module can be implemented in hardware, firmware, and/or software.
  • a module can include one or more processes, and/or be provided by only part of a process.
  • a module is typically stored on the storage device 1308, loaded into the memory 1306, and executed by the processor 1302.
  • a client device 115 may be a mobile phone with limited processing power, a small display 1318, and may lack a pointing device 1314.
  • the server computer in contrast, may comprise multiple blade servers working together to provide the functionality described herein.
  • Certain embodiments described herein include process steps and instructions described in the form of an algorithm. It should be noted that the process steps and instructions of the embodiments could be embodied in software, firmware or hardware, and when embodied in software, could be downloaded to reside on and be operated from different platforms used by real time network operating systems.
  • An apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored on a computer readable medium that can be accessed by the computer.
  • a computer program may be stored in a non-transitory computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of media suitable for storing electronic instructions, and each coupled to a computer system bus.
  • the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability.
  • the embodiments are well suited for a wide variety of computer network systems over numerous topologies. Within this field, the configuration and management of large networks comprise storage devices and computers that are communicatively coupled to dissimilar computers and storage devices over a network, such as the Internet. [0098] Finally, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, foe disclosure of the embodiments is intended to be illustrative, but not limiting.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Computational Linguistics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

Un système utilise un moteur de stockage de valeur-clé hybride qui utilise un arbre de fusion à structure logarithmique et un magasin d'objets à structure logarithmique segmentée. Le système effectue une récupération de mémoire de versions de documents périmés évitant une consultation d'index pendant le compactage de segment de journal. Le système sépare les données d'index et de document pour réduire au minimum une amplification d'écriture. Le système maintient une liste de suppression à l'aide d'un arbre de fusion structuré en journal pour stocker des numéros de séquences de documents périmés et des tailles correspondantes par segment de journal. Pour chaque segment de journal de la pluralité de segments de journal, le système détermine une mesure de fragmentation du segment de journal sur la base de tailles de documents supprimés du segment de journal à partir du second arbre de fusion structuré en journal. Si la fragmentation dépasse un seuil, le système initie une opération de compactage pour le segment de journal.
EP23752111.7A 2022-07-20 2023-07-19 Stockage de données haute densité basé sur des techniques de stockage à structure logarithmique Pending EP4558904A1 (fr)

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
IN202241041486 2022-07-20
US18/223,540 US12287771B2 (en) 2022-07-20 2023-07-18 High density data storage based on log structured storage techniques
US18/223,541 US12292872B2 (en) 2022-07-20 2023-07-18 Compaction of documents in a high density data storage system
PCT/US2023/028103 WO2024020070A1 (fr) 2022-07-20 2023-07-19 Stockage de données haute densité basé sur des techniques de stockage à structure logarithmique

Publications (1)

Publication Number Publication Date
EP4558904A1 true EP4558904A1 (fr) 2025-05-28

Family

ID=87567670

Family Applications (1)

Application Number Title Priority Date Filing Date
EP23752111.7A Pending EP4558904A1 (fr) 2022-07-20 2023-07-19 Stockage de données haute densité basé sur des techniques de stockage à structure logarithmique

Country Status (2)

Country Link
EP (1) EP4558904A1 (fr)
WO (1) WO2024020070A1 (fr)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12461904B2 (en) * 2024-04-04 2025-11-04 Google Llc Distributed aggregations in bigtable
CN118277392B (zh) * 2024-06-04 2024-08-09 华侨大学 一种基于键值分离的键值存储系统优化方法及装置
CN118643042B (zh) * 2024-08-15 2024-11-22 浙江智臾科技有限公司 一种支持实时更新和即席查询的主键存储引擎及存储方法
CN121636495A (zh) * 2024-08-29 2026-03-10 华为技术有限公司 数据访问方法、存储系统、计算机程序产品及存储介质
CN120973737B (zh) * 2025-07-25 2026-04-03 北京志凌海纳科技股份有限公司 基于固态硬盘的本地块存储引擎的元数据索引存储方法和系统

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP3682340A4 (fr) * 2019-09-12 2020-12-02 Advanced New Technologies Co., Ltd. Systèmes de stockage à structure journalisée

Also Published As

Publication number Publication date
WO2024020070A1 (fr) 2024-01-25

Similar Documents

Publication Publication Date Title
US12287771B2 (en) High density data storage based on log structured storage techniques
US10656859B2 (en) Efficient deduplication for storage systems
US12373440B2 (en) High-performance key-value store
WO2024020070A1 (fr) Stockage de données haute densité basé sur des techniques de stockage à structure logarithmique
US11755427B2 (en) Fast recovery and replication of key-value stores
US12147699B2 (en) Data management system and method of controlling preliminary class
US11741073B2 (en) Granularly timestamped concurrency control for key-value store
US10564850B1 (en) Managing known data patterns for deduplication
US8266114B2 (en) Log structured content addressable deduplicating storage
US9836355B2 (en) Reconstruction of dense tree volume metadata state across crash recovery
US8868624B2 (en) Blob manipulation in an integrated structured storage system
US11829291B2 (en) Garbage collection of tree structure with page mappings
US20160077744A1 (en) Deferred reference count update technique for low overhead volume metadata
US11860840B2 (en) Update of deduplication fingerprint index in a cache memory
US20160139838A1 (en) N-way merge technique for updating volume metadata in a storage i/o stack
CN103092905A (zh) 使用虚拟文件数据对象的列式数据库
CN1559035A (zh) 对迁移和清除候选者的有效查找
CN112131140A (zh) 基于ssd的支持高效存储空间管理的键值分离存储方法
US20250231924A1 (en) Compaction of Documents in a High Density Data Storage System
Wang et al. Bw e-tree: an Evolution of Bw-tree on Fast Storage
Lakshman et al. Magma: A high data density storage engine used in couchbase
CN114528355B (zh) 基于页面的关系数据库的云本机对象存储
Nørvåg Object and log management in temporal log-only object database systems

Legal Events

Date Code Title Description
STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: UNKNOWN

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE INTERNATIONAL PUBLICATION HAS BEEN MADE

PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: REQUEST FOR EXAMINATION WAS MADE

17P Request for examination filed

Effective date: 20241121

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC ME MK MT NL NO PL PT RO RS SE SI SK SM TR

DAV Request for validation of the european patent (deleted)
DAX Request for extension of the european patent (deleted)