Flash registry with on-disk hashing
A plurality of computing devices are communicatively coupled to each other via a network, and each of the plurality of computing devices is operably coupled to one or more of a plurality of storage devices. Each computing device is operable to access one or more memory blocks within the storage devices and maintain a registry over the same one or more memory blocks. The registry may be adaptively resized according to the access of the one or more memory blocks.
1 . A system comprising:
a registry of a plurality of memory blocks, wherein:
the registry is configured to be adaptively resized,
the registry comprises one or more registry blocks,
each registry block comprises a split level and one or more keys,
each of the one or more keys comprises an identical number of bits,
each of the one or more keys comprises an index,
each index comprises a specified number of bits, and
the split level corresponds to the specified number.
2 . The system of claim 1 , wherein the plurality of memory blocks comprises non-volatile memory.
3 . The system of claim 1 , wherein the plurality of memory blocks comprises flash memory.
4 . The system of claim 1 , wherein the registry is configured to be resized as the one or more memory blocks are written.
5 . The system of claim 1 , wherein the registry is configured to be resized as the one or more memory blocks are read.
6 . The system of claim 1 , wherein each of the one or more keys in each of the one or more registry blocks is associated with a key-value entry of one or more key-value entries.
7 . The system of claim 6 , wherein the one or more key-value entries are configured to be added to a registry block of the one or more registry blocks until a number of the one or more key-value entries exceeds a predetermined capacity, at which time the registry block is configured to be split and a new registry block is added to the one or more registry blocks.
8 . The system of claim 6 , wherein the one or more key-value entries are configured to be removed from a registry block of the one or more registry blocks until a number of the one or more key-value entries is at or below a predetermined level, at which time the registry block is configured to be merged with another registry block of the one or more registry blocks.
9 . The system of claim 8 , wherein each registry block is identified by the index and the split level.
10 . The system of claim 1 , wherein the storage network comprises a failure resilient address space distributed across a plurality of storage devices.
11 . A method comprising:
maintaining a registry of one or more memory blocks; and
adaptively resizing the registry, wherein:
the registry comprises one or more registry blocks,
each registry block comprises a split level and one or more keys,
each of the one or more keys comprises an identical number of bits,
each of the one or more keys comprises an index,
each index comprises a specified number of bits, and
the split level corresponds to the specified number.
12 . The method of claim 11 , wherein the plurality of memory blocks comprises non-volatile memory.
13 . The method of claim 11 , wherein the plurality of memory blocks comprises flash memory.
14 . The method of claim 11 , wherein the registry is resized as the one or more memory blocks are written.
15 . The method of claim 11 , wherein the registry is resized as the one or more memory blocks are read.
16 . The method of claim 11 , wherein each of the one or more keys in each of the one or more registry blocks is associated with a key-value entry of one or more key-value entries.
17 . The method of claim 16 , wherein the method comprises:
adding the one or more key-value entries to a registry block of the one or more registry blocks; and
if a number of the one or more key-value entries exceeds a predetermined capacity, splitting the registry block and adding a new registry block to the one or more registry blocks.
18 . The method of claim 16 , wherein the method comprises:
removing the one or more key-value entries from a registry block of the one or more registry blocks; and
if a number of the one or more key-value entries is at or below a predetermined level, merging the registry block with another registry block of the one or more registry blocks.
19 . The method of claim 18 , wherein each registry block is identified by the index and the split level.
20 . The method of claim 11 , wherein the plurality of memory blocks comprises a failure resilient address space distributed across a plurality of storage devices.