Defragmentation for log structured merge tree to improve read and write amplification
US11971859B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 28, 2022 |
| Grant date | Apr 30, 2024 |
| Priority date | — |
| Expiry date | Apr 28, 2042 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/183
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques are provided for implementing a defragmentation process during a merge operation performed by a re-compaction process upon a log structured merge tree. The log structured merge tree is used to store keys of key-value pairs within a key-value store. As the log structured merge tree fills with keys over time, the re-compaction process is performed to merge keys down to lower levels of the log structured merge tree to re-compact the keys. Re-compaction can result in fragmentation because there is a lack of spatial locality of where the re-compaction operations re-writes the keys within storage. Fragmentation increases read and write amplification when accessing the keys stored in different locations within the storage. Accordingly, the defragmentation process is performed during a last merge operation of the re-compaction process in order to store keys together within the storage, thus reducing read and write amplification when accessing the keys.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.