Network file system-based data storage system
A network file system-based data storage system that converts random I/O requests into a piecewise sequential data structure to facilitate variable length data segment redundancy identification and elimination. For one embodiment of the invention a stateless network file system is employed. For one such embodiment, that provides multiple-client access to stored data, multiple Writes are buffered and then broken into variable length data segments. Redundant segment elimination is then effected. One embodiment of the invention allows sharing of the variable length data segments among files.
1. A file system comprising:
a network file system interface to be coupled to a network to provide multiple-client access and to receive in a random order data blocks of files to be written, wherein each of the data blocks is part of a write I/O request for a given file;
a segment file system, coupled to the network file system interface to convert the randomly ordered data blocks of the write I/O requests into a piecewise sequential data structure for each file by putting the data blocks in order to form a sequential stream for each file;
a segment store, coupled to the segment file system, to segment each of the piecewise sequential data structures into one or more variable-length data segments;
a storage unit, coupled to the segment store unit, implemented in computer hardware to store at least one copy of each unique variable-length data segment; and
a redundant segment unit to identify one or more variable length data segments identical to a stored variable length data segment, create a reference to the stored variable length data segment for each variable length data segment identical to a stored variable length data segment, and store each reference to the storage unit, wherein the redundant segment unit deletes each of the one or more variable length data segments identical to a stored variable length data segment, subsequent to creating the reference to the stored variable length data segment for each variable length data segment identical to a stored variable length data segment.
2. The file system of claim 1 wherein the file server implements a network file system protocol.
3. The file system of claim 2 wherein the network file system protocol is selected from the group consisting of Network File System, Common Internet File System, NetWare Core Protocol, Global File System, Appleshare, InterMezzo File System, and Andrew File System.
4. The file system of claim 1 further comprising:
a garbage collection unit to identify reachable variable-length data segments and unreachable variable length data segments, identification including ascertaining a physical storage area in which the reachable variable-length data segments and the unreachable variable length data segments are stored in the storage unit, copying the reachable variable-length data segments to a new physical storage area and designating the physical storage area as unallocated.
5. The file system of claim 1 wherein the piecewise sequential data structure is buffered and an ordering of the piecewise sequential data structure is effected upon the buffer containing a specified amount of the corresponding data.
6. The file system of claim 1 further comprising:
an index implemented as a sequentially-merged on-disk index in which a merge buffer is stored in a system memory and the index is stored at least partially on a system storage.
7. The file system of claim 6 wherein the index contains a set of fingerprints, each fingerprint corresponding to one of the stored variable-length data segments, the index further containing one or more indicators to indicate the physical storage location of each of the variable-length data segments.
8. The file system of claim 7 wherein each of the one or more indicators is a mapping of each fingerprint to a data container containing the corresponding variable-length data segment.
9. The file system of claim 1 wherein one or more of the stored variable-length data segments is compressed using an entropy compression scheme.
10. The file system of claim 9 wherein the entropy compression scheme is selected from the group consisting of run-length encoding, Huffman coding, Arithmetic coding, Context coding, LZ77, LZ78, LZW, Deflate, Transformation coding, and combinations thereof.
11. A method comprising:
receiving, in a random order at a network file system interface, data blocks of files to be written, where each of the data blocks is part of a write I/O request;
converting the randomly ordered data blocks of the write I/O requests into a piecewise sequential data structure for each file by sorting the unordered data blocks into a sequential stream for each file;
segmenting each of the piecewise sequential data structures into one or more variable-length data segments;
storing at least one of the variable-length data segments;
identifying one or more variable length data segments identical to a stored variable length data segment;
creating a reference to the stored variable length data segment for each variable length data segments identical to a stored variable length data segment;
storing each reference to a storage unit; and
deleting each of the one or more variable length data segments identical to a stored variable length data segment, subsequent to creating the reference to the stored variable length data segment for each variable length data segment identical to a stored variable length data segment.
12. The method of claim 11 further comprising:
identifying reachable variable-length data segments and unreachable variable length data segments, identification including ascertaining a physical storage area in which the reachable variable-length data segments and the unreachable variable length data segments are stored;
copying the reachable variable-length data segments to a new physical storage area; and
designating the physical storage area as unallocated.
13. The method of claim 12 further comprising:
buffering the piecewise sequential data structure; and
effecting an ordering of the piecewise sequential data structure upon the buffer containing a specified amount of the corresponding data.
14. The method of claim 13 further comprising:
determining a set of fingerprints, each fingerprint corresponding to one of the stored variable-length data segments;
determining one or more indicators to indicate the physical storage location of each of the variable-length data segments; and
storing the set of fingerprints and the one or more indicators to an index.
15. The method of claim 14 wherein each of the one or more indicators is a mapping of each fingerprint to a data container containing the corresponding variable-length data segment.
16. The method of claim 11 further comprising:
compressing one or more of the stored variable-length data segments using an entropy compression scheme.
17. The method of claim 16 wherein the entropy compression scheme is selected from the group consisting of run-length encoding, Huffman coding, Arithmetic coding, Context coding, LZ77, LZ78, LZW, Deflate, Transformation coding, and combinations thereof.
18. An article of manufacture comprising:
a computer readable storage medium having associated data, wherein the data, when accessed, results in a machine performing operations comprising:
receiving, in a random order at a network file system interface, data blocks of files to be written, where each of the data blocks is part of a write I/O request;
converting the randomly ordered data blocks of the write I/O requests into a piecewise sequential data structure for each file by sorting the unordered data blocks into a sequential stream for each file;
segmenting each of the piecewise sequential data structures into one or more variable-length data segments;
storing at least one of the variable-length data segments;
identifying one or more variable length data segments identical to a stored variable length data segment;
creating a reference to the stored variable length data segment for each variable length data segment identical to a stored variable length data segment;
storing each reference to a storage unit; and
deleting each of the one or more variable length data segments identical to a stored variable length data segment, subsequent to creating the reference to the stored variable length data segment for each variable length data segment identical to a stored variable length data segment.
19. The article of manufacture of claim 18 wherein the machine performs further operations comprising:
identifying reachable variable-length data segments and unreachable variable length data segments, identification including ascertaining a physical storage area in which the reachable variable-length data segments and the unreachable variable length data segments are stored;
copying the reachable variable-length data segments to a new physical storage area; and
designating the physical storage area as unallocated.
20. The article of manufacture of claim 19 wherein the machine performs further operations comprising:
buffering the piecewise sequential data structure; and
effecting an ordering of the piecewise sequential data structure upon the buffer containing a specified amount of the corresponding data.
21. The article of manufacture of claim 20 wherein the machine performs further operations comprising:
determining a set of fingerprints, each fingerprint corresponding to one of the stored variable-length data segments;
determining one or more indicators to indicate the physical storage location of each of the variable-length data segments; and
storing the set of fingerprints and the one or more indicators to an index.
22. The article of manufacture of claim 21 wherein each of the one or more indicators is a mapping of each fingerprint to a data container containing the corresponding variable-length data segment.
23. The article of manufacture of claim 18 wherein the machine performs further operations comprising:
compressing one or more of the stored variable-length data segments using an entropy compression scheme.
24. The article of manufacture of claim 23 wherein the entropy compression scheme is selected from the group consisting of run-length encoding, Huffman coding, Arithmetic coding, Context coding, LZ77, LZ78, LZW, Deflate, Transformation coding, and combinations thereof.