Directory structure for a distributed storage system
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 flash storage devices. Each computing device is operable to access one or more memory blocks within the flash storage devices and maintain a directory structure for managing access to the memory. The directory structure may be adaptively resized according to the addition or removal of one or more associated files stored in memory.
1 . A system comprising:
a non-transitory, computer-readable, recording medium storing instructions executable by a computing device to:
communicate with a storage network comprising a plurality of memory blocks,
maintain a directory structure, comprising a hash set, for managing access to one or more memory blocks of the plurality of memory blocks, wherein:
managing access comprises managing existing files, balancing load and/or redistributing memory blocks according to read/write operations,
the hash set comprises on-disk hashing (ODH) comprising a plurality of buckets and registry blocks,
each registry block stores metadata comprising an outer split level, an outer split index, an inner split level and an inner split index, and
an anti-hash-collision (AHC) key is stored for each entry of the hash set,
shard a particular frontend according to an ID of a particular file, of the existing files, to ensure that the particular file is always accessed via the particular frontend,
redistribute one or more memory blocks according to read/write operations, without creating a new file, wherein the redistribution comprises moving complete registry blocks to a new bucket when increasing an outer split level and decreasing an inner split level such that blocks that have an inner split index that ends with “1” are moved and blocks that have an inner split index that ends with “0” remain,
adaptively resize the directory structure according to the access of the one or more memory blocks, and
redistribute a portion of the directory structure to another computing device to enlarge the hash set and to split or merge buckets according to directory load.
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 access comprises deleting files associated with the directory structure.
5 . The system of claim 1 , wherein the directory structure comprises one or more registry blocks, and wherein each registry block comprises one or more key-value entries, and wherein each key-value entries correspond to one or more files.
6 . The system of claim 5 , wherein key-value entries are added to a registry block of the one or more registry blocks until the number of key-value entries exceeds a predetermined capacity, at which time the registry block is split and a new registry block is added to the one or more registry blocks.
7 . The system of claim 6 , wherein the new registry block is relocated to another computing device.
8 . The system of claim 5 , wherein key-value entries are removed from a registry block of the one or more registry blocks until the number of key-value entries is at or below a predetermined level, at which time the registry block is merged with another registry block of the one or more registry blocks.
9 . The system of claim 1 , wherein the storage network comprises a failure resilient address space distributed across a plurality of storage devices.
10 . The system of claim 8 , wherein each registry block is identified by one or more adaptive indices.
11 . A method comprising:
communicatively coupling a computing device to a storage network comprising a plurality of memory blocks;
maintaining a directory structure for managing access to one or more memory blocks of the plurality of memory blocks, wherein the directory structure comprises a hash set for managing access to one or more memory blocks of the plurality of memory blocks, by managing existing files, balancing load and/or redistributing memory blocks according to read/write operations, wherein the directory structure is implemented as on-disk hashing (ODH) comprising a plurality of buckets and registry blocks, each registry block storing an outer split level, an outer split index, an inner split level, an inner split index, and per-entry anti-hash-collision (AHC) keys;
sharding a particular frontend according to an ID of a particular file, of the existing files, to ensure that the particular file is always accessed via the particular frontend,
adaptively resizing the directory structure according to the access of the one or more memory blocks of the plurality of memory blocks; and
redistributing a portion of the directory structure to another computing device to enlarge the hash set, wherein redistributing comprises moving complete registry blocks between buckets responsive to a bucket split in which the outer split level is increased and the inner split level is decreased such that blocks with inner split index ending in “1” are moved.
12 . The method of claim 11 , wherein the storage network comprises non-volatile memory.
13 . The method of claim 11 , wherein the storage network comprises flash memory.
14 . The method of claim 11 , wherein accessing one or more memory blocks comprises deleting files associated with the directory structure.
15 . The method of claim 11 , wherein the directory structure comprises one or more registry blocks, and wherein each registry block comprises one or more key value entries, and wherein each key-value entries correspond to one or more files.
16 . The method of claim 15 , wherein the method comprises:
adding key-value entries to a registry block of the one or more registry blocks; and
if the number of key-value entries exceeds a predetermined capacity, splitting the registry block and adding a new registry block to the one or more registry blocks.
17 . The method of claim 16 , wherein the method comprises relocating the new registry block to another computing device.
18 . The method of claim 16 , wherein the method comprises:
removing key-value entries from a registry block of the one or more registry blocks; and
if the number of 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 11 , wherein the storage network comprises a failure resilient address space distributed across a plurality of storage devices.
20 . The method of claim 18 , wherein each registry block is identified by one or more adaptive indices.