Optimization of log-structured merge (LSM) tree-based databases using object solid state drive (SSD) devices
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
Specification