Faster tree flattening for a system having non-volatile memory

摘要

Systems and methods are disclosed for efficient buffering for a system having non-volatile memory (“NVM”). A tree can be stored in volatile memory that includes a logical-to-physical mapping between a logical space and physical addresses of the NVM. When the amount of memory available for the tree is below a pre-determined threshold, a system can attempt to reduce the number of data fragments in the NVM, and consequently flatten a portion of the tree. The NVM interface may select an optimal set of entries of the tree to combine. Any suitable approach can be used such as, for example, moving one or more sliding windows across the tree, expanding a sliding window when a condition has been satisfied, using a priority queue while scanning the tree, and/or maintaining a priority queue while the tree is being updated.

主权项

1. A method for faster tree flattening, the method comprising:
detecting that an amount of memory currently available for a tree is below a pre-determined threshold, wherein the tree stores a logical-to-physical mapping between a logical space and physical addresses of a non-volatile memory (“NVM”); moving at least two sliding windows across the tree; maintaining at least two minimum spans corresponding to the at least two sliding windows as the at least two sliding windows move across the tree; determining that the at least two sliding windows have finished moving across the tree; and selecting to flatten a set of entries of the tree based at least in part on a comparison between the at least two minimum spans.