System and method for lsm compaction
AssigneeSK hynix Inc.
InventorsJongryool KIM, Hyung Jin LIM, Shiju LI, Kevin TANG
Life of this patent
Estimating the term…
Abstract
In a compaction scheme for a log structured merge (LSM) tree, a storage device is configured to: receive a first user data piece from a host; generate a first meta data piece for a highest level of the LSM tree, corresponding to the first user data piece; when the highest level exceeds a set storage limit, trigger a compaction process on the first and second meta data pieces to generate compacted meta data pieces excluding overlapping meta data elements of the second meta data pieces overlapped with the first meta data piece. Through a garbage collection, victim user data elements corresponding to the overlapping meta data elements are deleted.
Claims20
A system comprising:
- a host;
- and
- a storage device including a plurality of memory blocks, coupled to the host and configured to:
- receive a first user data piece from the host;
- store the first user data piece in a particular memory block among the plurality of memory blocks;
- generate a first meta data piece to be stored in a highest level among hierarchical levels of a log structured merge (LSM) tree, the first meta data piece corresponding to the first user data piece;
- when the highest level exceeds a set storage limit in response to determining of the first meta data piece, trigger a compaction process on the first meta data piece and second meta data pieces which have been stored in the highest level and a higher level to generate compacted meta data pieces, the second meta data pieces including overlapping meta data elements overlapped with the first meta data piece, the compacted meta data pieces excluding the overlapping meta data elements;
- store the compacted meta data pieces in the highest level;
- and
- perform a garbage collection on second user data pieces stored in the plurality of memory blocks to delete victim user data elements corresponding to the overlapping meta data elements, the second user data pieces corresponding to the second meta data pieces.
A method for operating a storage device including a plurality of memory blocks and coupled to a host, the method comprising:
- receiving a first user data piece from the host;
- storing the first user data piece in a particular memory block among the plurality of memory blocks;
- generating a first meta data piece to be stored in a highest level among hierarchical levels of a log structured merge (LSM) tree, the first meta data piece corresponding to the first user data piece;
- when the highest level exceeds a set storage limit in response to determining of the first meta data piece, triggering a compaction process on the first meta data piece and second meta data pieces which have been stored in the highest level and a higher level to generate compacted meta data pieces, the second meta data pieces including overlapping meta data elements overlapped with the first meta data piece, the compacted meta data pieces excluding the overlapping meta data elements;
- storing the compacted meta data pieces in the highest level;
- and
- performing a garbage collection on second user data pieces stored in the plurality of memory blocks to delete victim user data elements corresponding to the overlapping meta data elements, the second user data pieces corresponding to the second meta data pieces.
A method for operating a storage device including a plurality of memory blocks and coupled to a host, the method comprising:
- receiving a first user data piece from the host;
- storing the first user data piece in a particular memory block among the plurality of memory blocks;
- generating a first meta data piece to be stored in a highest level among hierarchical levels of a log structured merge (LSM) tree, the first meta data piece corresponding to the first user data piece;
- and
- to avoid compaction of data by the host, performing a compaction process in the storage device on the first meta data piece and second meta data pieces which have been stored in the highest level and a higher level to generate compacted meta data pieces, the second meta data pieces including overlapping meta data elements overlapped with the first meta data piece, the compacted meta data pieces excluding the overlapping meta data elements.
Dependencies are inferred from the claim text.