Optimization of log-structured merge (LSM) tree-based databases using object solid state drive (SSD) devices

• US 10,445,022 B1
• Filed: 04/26/2018
• Issued: 10/15/2019
• Est. Priority Date: 04/26/2018
• Status: Active Grant

• Current Assignee: Alibaba Group Holding Ltd.
• Original Assignee: Alibaba Group Holding Ltd.
• Inventors: Qui, Sheng, Liu, Fei, Li, Shu
• Primary Examiner(s): Lane, John A
• Application Number:
  US15/963,386
• Publication Number:
  US 20190332329A1
• Time in Patent Office: 537 Days
• Field of Search: None
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0661 Format or protocol conversion arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 7/14 Merging, i.e. combining at least two sets of record carriers each arranged in the same ordered sequence to produce a single set having the same ordered sequence
• CPC Class Codes: G06F 7/32 Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence merging methods in generalG06F7/36 takes precedence

Abstract

The disclosed embodiments are directed to improvements in log-structured merge (LSM) tree databases. In one embodiment, a method is disclosed comprising receiving data to be written to a log-structured merge (LSM) tree, the data including a key and value; determining that an in-memory buffer lacks capacity to store the data to be written; compacting key-ranges stored in at least one level of the LSM tree stored in an object storage device (OSD), each of the key-ranges associated with a respective object identifier; generating a key range object, the key range object including object identifiers associated with a subset of the key-ranges; erasing physical blocks corresponding to each of the object identifiers included in the key range object; and writing the key range object to at least one physical block of the OSD.

Claims

1. A method comprising:

receiving, by a processor, data to be written to a log-structured merge (LSM) tree, the data including a key and value;

determining, by the processor, that an in-memory buffer lacks capacity to store the data to be written;

compacting, by the processor, key-ranges stored in at least one level of the LSM tree stored in an object storage device (OSD), each of the key-ranges associated with a respective object identifier;

generating, by the processor, a key range object, the key range object including object identifiers associated with a subset of the compacted key-ranges;

erasing, by the OSD, physical blocks corresponding to each of the object identifiers included in the generated key range object; and

writing, by the OSD, the generated key range object to at least one physical block of the OSD.

2. A method comprising:

receiving, at an object storage device (OSD), a write request, the write request including a plurality of object identifiers comprising at least one new object identifier and at least one existing object identifier;

erasing, by the OSD, blocks of data associated with the existing object identifier; and

writing, by the OSD, data associated with the existing object identifier and data associated with the new object identifier.

3. The method of claim 2, the erasing blocks of data associated with the existing object identifier comprising invalidating all pages in the blocks of data.

4. The method of claim 3, further comprising triggering, by the OSD, a garbage collection routine, the garbage collection routine bypassing copying of data on the erased blocks of data.

5. The method of claim 2, the receiving a write request comprising receiving a write request generated by a log-structured merge tree database compaction operation.

6. The method of claim 2, further comprising storing, by the OSD, an object-to-PBA (physical block address) mapping.

7. The method of claim 6, further comprising, prior to erasing blocks of data associated with the existing object identifier, identifying, by the OSD, a plurality of blocks in the object-to-PBA mapping using the at least one existing object identifier.

8. The method of claim 6, the writing data associated with the existing object identifier and data associated with the new object identifier further comprising updating the object-to-PBA mapping after writing the data.

9. The method of claim 2, the receiving a write request comprising receiving a key range object, the key range object including a plurality of keys and a plurality of values associated with the plurality of keys.

10. The method of claim 2, the receiving a write request comprising receiving a write request via an object device driver.

11. The method of claim 2, the writing data associated with the existing object identifier and data associated with the new object identifier comprising segmenting the data based on a block size of the OSD and writing the segmented data to a plurality of blocks, the plurality of blocks only storing data written in response to the write request.

12. An apparatus comprising:

a storage medium, the storage medium storing data in a plurality of blocks, each block having a plurality of pages;

an object interface configured to receive commands from an object device driver; and

a controller communicatively coupled to the storage medium and the object interface and configured to receive commands via the object interface, the controller further including stored program comprising;

logic, executed by the controller, for receiving a write request, the write request including a plurality of object identifiers comprising at least one new object identifier and at least one existing object identifier,

logic, executed by the controller, for erasing blocks of data associated with the existing object identifier, and

logic, executed by the controller, for writing data associated with the existing object identifier and data associated with the new object identifier.

13. The apparatus of claim 12, the logic for erasing blocks of data associated with the existing object identifier comprising logic for invalidating all pages in the blocks of data.

14. The apparatus of claim 13, the logic further comprising logic, executed by the controller, for triggering a garbage collection routine, the garbage collection routine bypassing copying of data on the erased blocks of data.

15. The apparatus of claim 12, the logic for receiving a write request comprising logic, executed by the controller, for receiving a write request generated by a log-structured merge tree database compaction operation.

16. The apparatus of claim 12, further comprising a dynamic random access memory for storing an object-to PBA (physical block address) mapping.

17. The apparatus of claim 16, the logic further comprising logic, executed by the controller, for, prior to erasing blocks of data associated with the existing object identifier, identifying a plurality of blocks in the object-to-PBA mapping using the at least one existing object identifier.

18. The apparatus of claim 16, the logic for writing data associated with the existing object identifier and data associated with the new object identifier further comprising logic, executed by the controller, for updating the object-to-PBA mapping after writing the data.

19. The apparatus of claim 12, the logic for receiving a write request comprising logic, executed by the controller, for receiving a key range object, the key range object including a plurality of keys and a plurality of values associated with the plurality of keys.

20. The apparatus of claim 12, the logic for writing data associated with the existing object identifier and data associated with the new object identifier comprising logic, executed by the controller, for segmenting the data based on a block size of the storage medium and writing the segmented data to a plurality of blocks, the plurality of blocks only storing data written in response to the write request.