Optimizing flattening in a multi-level data structure
US9977600B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 30, 2017 |
| Grant date | May 22, 2018 |
| Priority date | — |
| Expiry date | Jun 30, 2037 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2212/7201
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A system and method for efficiently maintaining metadata stored among a plurality of solid-state storage devices. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels. Each level stores at least pairs of a key value and a physical pointer value. The levels are sorted by time. New records are inserted in a created new highest (youngest) level. No edits are performed in-place. A data storage controller determines both a cost of searching a given table exceeds a threshold and an amount of memory used to flatten levels exceeds a threshold. In response, the controller incrementally flattens selected levels within the table based on key ranges. After flattening the records in the selected levels within the key range, the records may be removed from the selected levels. The process repeats with another different key range.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.