(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2004/0148306 A1
`Moulton et al.
`(43) Pub. Date:
`Jul. 29, 2004
`
`US 20040148306A1
`
`(54) HASH FILE SYSTEM AND METHOD FOR
`USE IN A COMMONALITY FACTORING
`SYSTEM
`
`(60) Provisional application No. 60/183,762, filed on Feb.
`18, 2000.
`
`Publication Classification
`
`(76)
`
`Inventors: Gregory Hagan Moulton, Irvine, CA
`.
`.
`.
`.
`
`Stephen B‘ Wh“°h‘"’ Tum’ CA
`Correspondence Address:
`HOGAN & HARTSON LLP
`ONE TABOR CENTER, SUITE 1500
`1200 SEVENTEENTH ST
`DENVER, CO 30202 (US)
`
`(21) APP1. No‘;
`
`10/757,753
`
`(22)
`
`Ffled;
`
`Jan_ 14, 2004
`
`Related US, Application Data
`
`(63) Continuation of application No. 09/777,150, filed on
`Feb. 5, 2001, now Pat. No. 6,704,730.
`
`51
`
`Int. Cl.7 ............................ .. G06F 7/00; G06F 12/00
`
`............................................ 707/101, 711/114
`E523 U.s. Cl.
`ABSTRACT
`(57)
`Asystem and method for a computer file system that is based
`and organized upon hashes and/or strings of digits of certain,
`different, or changing lengths and which is capable of
`eliminating or screening redundant copies of aggregate
`blocks of data (or parts of data blocks) from the system. The
`hash file system of the present invention utilizes hash values
`for computer files or file pieces which may be produced by
`a checksum generating program, engine or algorithm such as
`industry standard MD4, MD5, SHA or SHA-1 algorithms.
`Alternatively, the hash values may be generated by a check-
`sum program, engine, algorithm or other means that pro-
`duces an effectively unique hash value for a block of data of
`indeterminate size based upon a non-linear probablistic
`mathematical algorithm.
`
`Enter Fllo Into
`Hash File system
`
`
`
`202
`
`
`
`216
`
`Bmk Flle Into
`Mashed Place:
`
`
`
`211
`
`SPRINGPATH
`SPRINGPATH
`EXHIBIT 1007
`EXHIBIT 1007
`
`

`
`Patent Application Publication
`
`Jul. 29, 2004 Sheet 1 of 10
`
`US 2004/0148306 A1
`
`'_|.U
`Luz
`20
`mm.
`uJ¥
`'25:’—m
`
`

`
`Patent Application Publication Jul. 29, 2004 Sheet 2 of 10
`
`US 2004/0148306 A1
`
`RAINRacks
`
`i
`
`Ii
`
`~.
`
`‘S
`Ez
`
`EE9
`
`'_ flflflflflflflfllflflflfl
`ll?--——
`
`
`=n
`
`nnnnnnnnnnun
`
`.E f
`
`
`
`ilulluimli%uuatooeanrmr'P_r‘
`
`T
`
`
`
`
`_t
`"V
`
`it
`
`1
`
`
`
`.
`
`i
`
`.
`
`
`
`
`
`118
`
`E } gt IEFIIIIIIIIIII
`3§
`§
`flflflflflflflflflflflflfl
`
`A
`
`'
`
`RAINRacks
`
`
`
`
` ul
` ll!-"3
`
`-
`
`g/fig»
`--*x‘
`1 Ni"L1_
`
`tgg
`
`
`
`élntemalNetwprk
`
`EN 1
`
`E
`
`
`
`% unnunnnnunnuu
`
`

`
`Patent Application Publication Jul. 29, 2004 Sheet 3 of 10
`
`US 2004/0148306 A1
`
`8=3:2:23
`
`..2:3:5:range
`
`.5rouge
`
`
`
`2.“.52522.".55..o.u_:E_.6o<
`
`
`
`.9can:u.o=n_
`
`Eusuoéoz.
`
`asogo
`
`TNo...
`
`8:.SIBEN
`
`o_.~
`
`8...2:.35
`
`
`
`88...:28:
`
`N5
`
`.8338:0
`
`Eu8:_u>5-:
`
`a:=.c2_uo.:oo
`
`sac
`
`.3aouea-2.3...92:22
`
`Nwu
`
`ii32-)in:B825.5
`
`9.539230
`
`23
`
`
`
`
`
`
`
`
`
`
`

`
`Patent Application Publication Jul. 29, 2004 Sheet 4 of 10
`
`US 2004/0148306 A1
`
`N8
`
`.30
`
`
`92B2292Scosuow_2a_o
`a__wcoE_.E.vocovenom80¢....
`
`
`
`..§§m2.s88....25£3.
`
`.._E3.82..582__s_..._3
`
`
`
`

`
`Patent Application Publication Jul. 29, 2004 Sheet 5 of 10
`
`US 2004/0148306 A1
`
`.vow
`
`Sm
`
`.5...:£3.85__o.285>:3:
`
`
`
`susm58..a_uz=..mussfiw38¢
`
`83255uciagaesoBa82.
`
`Ssuao2.
`
`.iiao:_o>5»:B833.5
`a£u£x.uE.o0
`
`sun
`
`9.3.09ueaeoo8..8..om_s_9o
`ca:32Baseam.._.8_a.>5»:
`
`
`
`
`
`8..
`
`-B82..Sam3...s_u>5.:
`
`E...2
`
`fia3.5E
`
`
`
`
`
`

`
`Patent Application Publication Jul. 29, 2004 Sheet 6 of 10
`
`US 2004/0148306 A1
`
`

`
`Patent Application Publication Jul. 29, 2004 Sheet 7 of 10
`
`US 2004/0148306 A1
`
`
`
` HimtorI2
`
` CompositeDatais(concatenationatdataIndicatedbyhashes)
`Indicatedbyhuhu)
`(dataInmaul!qtpmcasalngofcm:
`
`
`
`
`
`

`
`Patent Application Publication Jul. 29, 2004 Sheet 8 of 10
`
`US 2004/0148306 A1
`
`

`
`Patent Application Publication Jul. 29, 2004 Sheet 9 of 10
`
`US 2004/0148306 A1
`
`cum:.5our
`
`...8.2.<n=2D.85»
`
`32....<E.350O.
`
`

`
`Patent Application Publication Jul. 29, 2004 Sheet 10 of 10
`
`US 2004/0148306 A1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`u:o_E=.oooc._o>>EafisoonE25..N>50.T..3:nEOO«E0....w.30
`.82A;.......
`
`
`
`1.5mmofltan<89.ms:ro_ms:.<32.,0<8:
`
`.
`
`
`
`
`
`..a:con...:._mxu.<nz009x-1mxu.<
`
`
`
`
`
`scaE=u.oo>23:“.Em.._mo..n_.mEoE:uoo>28:“.EsuE
`
`
`.EN..8:
`n:s__u:_.eue..._..80N: z<m_2o_ois::
`
`
`
`m:.3:..Eao..._
`
`
`
`
`

`
`US 2004/0148306 A1
`
`Jul. 29, 2004
`
`HASH FILE SYSTEM AND METHOD FOR USE IN
`A COMMONALITY FACTORING SYSTEM
`
`CROSS REFERENCE TO RELATED PATENT
`APPLICATIONS
`
`[0001] The present invention claims priority from U.S.
`Provisional Patent Application Serial No. 60/183,762 for:
`“System and Method for Decentralized Data Storage” filed
`Feb. 18, 2000, the disclosure of which is herein specifically
`incorporated by this reference.
`
`COPYRIGHT NOTICE/PERMISSION
`
`[0002] Aportion of the disclosure of this patent document
`may contain material which is subject to copyright protec-
`tion. The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document of the patent
`disclosure as it appears in the United States Patent and
`Trademark Office patent
`file or records, but otherwise,
`reserves all copyright rights whatsoever. The following
`notice applies to the software and data and described below,
`inclusive of the drawing figures where applicable: Copy-
`right© 2000, Undoo Technologies.
`
`BACKGROUND OF THE INVENTION
`
`to the
`[0003] The present invention relates, in general,
`field of hash file systems and commonality factoring sys-
`tems. More particularly, the present invention relates to a
`system and method for determining a correspondence
`between electronic files in a distributed computer data
`environment and particular applications therefor.
`
`[0004] Economic, political, and social power are increas-
`ingly managed by data. Transactions and wealth are repre-
`sented by data. Political power is analyzed and modified
`based on data. Human interactions and relationships are
`defined by data exchanges. Hence, the efficient distribution,
`storage, and management of data is expected to play an
`increasingly vital role in human society.
`
`[0005] The quantity of data that must be managed, in the
`form of computer programs, databases, files, and the like,
`increases exponentially. As computer processing power
`increases, operating system and application software
`becomes larger. Moreover, the desire to access larger data
`sets such as multimedia files and large databases further
`increases the quantity of data that is managed. This increas-
`ingly large data load must be transported between comput-
`ing devices and stored in an accessible fashion. The expo-
`nential growth rate of data is expected to outpace the
`improvements in communication bandwidth and storage
`capacity, making data management using conventional
`methods even more urgent.
`
`[0006] Many factors must be balanced and often compro-
`mised in conventional data storage systems. Because the
`quantity of data is extremely large,
`there is continuing
`pressure to reduce the cost per bit of storage. Also, data
`management systems should be scaleable to contemplate not
`only current needs, but future needs as well. Preferably,
`storage systems are incrementally scaleable so that a user
`can purchase only the capacity needed at any particular time.
`High reliability and high availability are also considered as
`data users are increasingly intolerant of lost, damaged, and
`unavailable data. Unfortunately, conventional data manage-
`
`ment architectures must compromise these factors so that no
`one architecture provides a cost-effective, reliable, high
`availability, scaleable solution.
`
`[0007] Conventional RAID (Redundant Array of Indepen-
`dent Disks) systems are a way of storing the same data in
`different places (thus, redundantly) on multiple storage
`devices such as hard disks. By placing data on multiple
`disks,
`input/output
`(“I/O”) operations can overlap in a
`balanced way,
`improving performance. Since the use of
`multiple disks increases the mean time between failure
`(“MTBF”), storing data redundantly also increases fault-
`tolerance. A RAID system relies on a hardware or software
`controller to hide the complexities of the actual data man-
`agement so that a RAID system appears to an operating
`system as a single logical hard disk. However, RAID sys-
`tems are difficult to scale because of physical limitations in
`the cabling and controllers. Also, the availability of RAID
`systems is highly dependent on the functionality of the
`controllers themselves so that when a controller fails, the
`data stored behind the controller becomes unavailable.
`
`Moreover, RAID systems require specialized, rather than
`commodity hardware, and so tend to be expensive solutions.
`
`[0008] NAS (network-attached storage) refers to hard disk
`storage that is set up with its own network address rather
`than being attached to an application server. File requests are
`mapped to the NAS file server. NAS may provide transpar-
`ent I/O operations using either hardware or software based
`RAID. NAS may also automate mirroring of data to one or
`more other NAS devices to further improve fault tolerance.
`Because NAS devices can be added to a network,
`they
`enable scaling of the total capacity of the storage available
`to a network. However, NAS devices are constrained in
`RAID applications to the abilities of the conventional RAID
`controllers. Also, NAS systems do not enable mirroring and
`parity across nodes, and so are a limited solution.
`
`In addition to data storage issues, data transport is
`[0009]
`rapidly evolving with improvements in wide area network
`(“WAN”) and internetworking technology. The Internet, for
`example, has created a globally networked environment
`with almost ubiquitous access. Despite rapid network infra-
`structure improvements, the rate of increase in the quantity
`of data that
`requires transport
`is expected to outpace
`improvements in available bandwidth.
`
`the way data is conventionally
`[0010] Philosophically,
`managed is inconsistent with the hardware devices and
`infrastructures that have been developed to manipulate and
`transport data. For example, computers are characteristically
`general-purpose machines that are readily programmed to
`perform a virtually unlimited variety of functions. In large
`part, however, computers are loaded with a fixed, slowly
`changing set of data that limit their general-purpose nature
`to make the machines special-purpose. Advances in process-
`ing speed, peripheral performance and data storage capacity
`are most dramatic in commodity computers. Yet many data
`storage solutions cannot take advantage of these advances
`because they are constrained rather than extended by the
`storage controllers upon which they are based. Similarly, the
`Internet was developed as a fault tolerant, multi-path inter-
`connected network. However, network resources are con-
`ventionally implemented in specific network nodes such that
`failure of the node makes the resource unavailable despite
`the fault-tolerance of the network to which the node is
`
`

`
`US 2004/0148306 A1
`
`Jul. 29, 2004
`
`connected. Continuing needs exist for high availability, high
`reliability, highly scaleable data storage solutions.
`
`SUMMARY OF THE INVENTION
`
`[0011] Disclosed herein is a system and method for a
`computer file system that
`is based and organized upon
`hashes and/or strings of digits of certain, different, or chang-
`ing lengths and which is capable of eliminating or screening
`redundant copies of the blocks of data (or parts of data
`blocks) from the system. Also disclosed herein is a system
`and method for a computer file system wherein hashes may
`be produced by a checksum generating program, engine or
`algorithm such as industry standard Mcssagc Digest 4
`(“MD4”), MD5, Secure Hash Algorithm (“SHA”) or SHA-1
`algorithms. Further disclosed herein is a system and method
`for a computer file system wherein hashes may be generated
`by a checksum program, engine, algorithm or other means
`that generates a probabilistically unique hash value for a
`block of data of indeterminate size based upon a non-linear
`probablistic mathematical algorithm or any industry stan-
`dard technique for generating pseudo-random values from
`an input text of other data/numeric sequence.
`
`[0012] The system and method of the present invention
`may be utilized, in a particular application disclosed herein,
`to automatically factor out redundancies in data allowing
`potentially very large quantities of unfactored storage to be
`often reduced in size by several orders of magnitude. In this
`regard,
`the system and method of the present invention
`would allow all computers, regardless of their particular
`hardware or software characteristics, to share data simply,
`efficiently and securely and to provide a uniquely advanta-
`geous means for effectuating the reading, writing or refer-
`encing of data. The system and method of the present
`invention is especially efficacious with respect to networked
`computers or computer systems but may also be applied to
`isolated data storage with comparable results.
`
`invention
`[0013] The hash file system of the present
`advantageously solves a number of problems that plague
`conventional storage architectures. For example, the system
`and method of the present invention eliminates the need for
`managing a huge collection of directories and files, together
`with all the wasted system resources that inevitably occur
`with duplicates, and slightly different copies. The mainte-
`nance and storage of duplicate files plagues traditional
`corporate and private computer systems and generally
`requires painstaking human involvement to “cleanup disk
`space”. The hash file system of the present invention effec-
`tively eliminates this problem by eliminating the disk space
`used for copies and nearly entirely eliminating the disk
`space used in partial copies. For example, in a traditional
`computer system copying a gigabyte directory structure to a
`new location would require another gigabyte of storage. In
`particular applications, the hash file system of the present
`invention reduces the disk space used in this operation by up
`to a hundred thousand times or more.
`
`[0014] Currently, some file systems have mechanisms to
`eliminate copies, but none can accomplish this operation in
`a short amount of time which, in technical terms, means the
`system factors copies in O(l) (“on the order of constant
`time”) time, even as the system scales. This means a unit of
`time that is constant as opposed to other systems that would
`require O(N**2), O(N) or O(log(N)) time, meaning time is
`
`related to the amount of storage being factored. Factoring
`storage in non-constant time may be marginally satisfactory
`for systems where the amount of storage is small, but as a
`system grows to large sizes, even the most efficient non-
`constant factoring systems become untenable. The hash file
`system of the present invention is designed to factor storage
`on a scale never previously attempted and in a first imple-
`mentation, is capable of factoring 2 million petabytes of
`storage, with the ability to expand to much larger sizes.
`Existing file systems are incapable of managing data on such
`scales.
`
`the hash file system of the present
`[0015] Moreover,
`invention may be utilized to provide inexpensive, global
`computer system data protection and backup. Its factoring
`function operates very efliciently on typical backup data sets
`because computer file systems rarely change more than a
`few percent of their overall storage between each backup
`operation. Further,
`the hash file system of the present
`invention can serve as the basis for an efficient messaging
`(e-mail) system. E-mail systems are fundamentally data
`copying mechanisms wherein an author writes a message
`and sends it
`to a list of recipients. An e-mail system
`implements this “sending” operation effectively by copying
`the data from one place to another. The author generally
`keeps copies of the messages he sends and the recipients
`each keep their own copies. These copies are often, in turn,
`attached in replies that are also kept (i.e. copies of copies).
`The commonality factoring feature of the present invention
`can eliminate this gross inefficiency while transparently
`allowing e-mail users to retain this familiar copy-oriented
`paradigm.
`
`[0016] Because, as previously noted, most data in com-
`puter systems rarely change,
`the hash file system of the
`present invention allows for the reconstruction of complete
`snapshots of entire systems which can be kept, for example,
`for every hour of every day they exist or even continuously,
`with snapshots taken at even minute (or less) intervals
`depending on the system needs. Further, since conventional
`computer systems often provide limited versioning of files
`(i.e. Digital Equipment Corporation’s VAX® VMS® file
`system), the hash file system of the present invention also
`provides significant advantages in this regard. Versioning in
`conventional systems presents both good and bad aspects. In
`the former instance, it helps prevent accidents, but, in the
`latter, it requires regular purging to reduce the disk space it
`consumes. The hash file system of the present invention
`provides versioning of files with little overhead through the
`factoring of identical copies or edited copies with little extra
`space. For example, saving one hundred revisions of a
`typical document typically requires about one hundred times
`the space of the original file. Using the hash file system
`disclosed herein, those revisions might require only three
`times the space of the original (depending on the document’s
`size, the degree and type of editing, and external factors).
`
`[0017] Still other potential applications of the hash file
`system of the present invention include web-serving. In this
`regard,
`the hash file system can be used to efficiently
`distribute web content because the method of factoring
`commonality (hashing) also produces uniform distribution
`over all hash file system servers. This even distribution
`permits a large array of servers to function as a gigantic web
`server farm with an evenly distributed load. In other appli-
`cations, the hash file system of the present invention can be
`
`

`
`US 2004/0148306 A1
`
`Jul. 29, 2004
`
`used as a network accelerator inasmuch as it can be used to
`
`reduce network traffic by sending proxies (hashes) for data
`instead of the data itself. A large percentage of current
`network traffic is redundant data moving between locations.
`Sending proxies for the data would allow effective local
`caching mechanisms to operate, possibly reducing the traffic
`on the Internet by several orders of magnitude.
`
`[0018] As particularly disclosed herein, the hash file sys-
`tem and method of the present invention may be imple-
`mented using 160 bit hashsums as universal pointers. This
`differs from conventional file systems which use pointers
`assigned from a central authority (i.e.
`in Unix a 32 bit
`“mode” is assigned by the kernel’s file systems in a lock-step
`operation to assure uniqueness). In the hash file system of
`the present invention, these 160 bit hashsums are assigned
`without a central authority (i.e. without locking, without
`synchronization) by a hashing algorithm.
`
`[0019] Known hashing algorithms produce probabilisti-
`cally unique numbers that uniformly span a range of values.
`In the case of the hash function SHA-1, that range is between
`0 and 10e48. This hashing operation is done by examining
`only the contents of the data being stored and, therefore, can
`be done in complete isolation, asynchronously, and without
`interlocking.
`
`[0020] Hashing is an operation that can be verified by any
`component of the system, eliminating the need for trusted
`operations across those components. The hash file system
`and method of the present invention disclosed herein is,
`therefore, functional to eliminate the critical bottleneck of
`conventional large scale distributed file systems, that is, a
`trusted encompassing central authority. It permits the con-
`struction of a large scale distributed file system with no
`limits on simultaneous read/write operations, that can oper-
`ate without risk of incoherence and without the limitation of
`certain conventional bottlenecks.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0021] The aforementioned and other features and objects
`of the present invention and the manner of attaining them
`will become more apparent, and the invention itself will be
`best understood by reference to the following description of
`a preferred embodiment
`taken in conjunction with the
`accompanying drawings, wherein:
`
`[0022] FIG. 1 is a high level illustration of a representa-
`tive networked computer environment in which the system
`and method of the present invention may be implemented;
`
`[0023] FIG. 2 is a more detailed conceptual representation
`of a possible operating environment for utilization of the
`system and method of the present invention wherein files
`maintained on any number of computers or data centers may
`be stored in a decentralized computer system through an
`Internet connection to a number of Redundant Arrays of
`Independent Nodes (“RAIN”) racks located, for example, at
`geographically diverse locations;
`
`[0024] FIG. 3 is a logic flow chart depicting the steps in
`the entry of a computer file into the hash file system of the
`present invention wherein the hash value for the file is
`checked against hash values for files previously maintained
`in a set, or database;
`
`[0025] FIG. 4 is a further logic flow chart depicting the
`steps in the breakup of a file or other data sequence into
`
`hashed pieces resulting in the production of a number of data
`pieces as well as corresponding probabilistically unique
`hash values for each piece;
`
`[0026] FIG. 5 is another logic flow chart depicting the
`comparison of the hash values for each piece of a file to
`existing hash values in the set (or database), the production
`of records showing the equivalence of a single hash value for
`all file pieces with the hash values of the various pieces and
`whereupon new data pieces and corresponding new hash
`values are added to the set;
`
`[0027] FIG. 6 is yet another logic flow chart illustrating
`the steps in the comparison of file hash or directory list hash
`values to existing directory list hash values and the addition
`of new file or directory list hash values to the set directory
`list;
`
`[0028] FIG. 7 is a comparison of the pieces of a repre-
`sentative computer file with their corresponding hash values
`both before and after editing of a particular piece of the
`exemplary file;
`
`[0029] FIG. 8 is a conceptual representation of the fact
`that composite data which may be derived by means of the
`system and method of the present invention is effectively the
`same as the data represented explicitly but may instead be
`created by a “recipe” such as the concatenation of data
`represented by its corresponding hashes or the result of a
`function using the data represented by the hashes;
`
`[0030] FIG. 9 is another conceptual representation of how
`the hash file system and method of the present invention my
`be utilized to organize data to optimize the reutilization of
`redundant sequences through the use of hash values as
`pointers to the data they represent and wherein data may be
`represented either as explicit byte sequences (atomic data) or
`as groups of sequences (composites);
`
`[0031] FIG. 10 is a simplified diagram illustrative of a
`hash file system address translation function for an exem-
`plary 160 bit hash value;
`
`[0032] FIG. 11 is a simplified exemplary illustration of an
`index stripe splitting function for use with the system and
`method of the present invention;
`
`[0033] FIG. 12 is a simplified illustration of the overall
`functionality of the system and method of the present
`invention for use in the backup of data for a representative
`home computer having a number of program and document
`files on Day 1 and wherein one of the document files is
`edited on Day 2 together with the addition of a third
`document file; and
`
`[0034] FIG. 13 illustrates the comparison of various
`pieces of a particular document file marked by a number of
`“sticky bytes” both before and following editing wherein
`one of the pieces is thereby changed while other pieces
`remain the same.
`
`DESCRIPTION OF A REPRESENTATIVE
`EMBODIMENT
`
`In a particular implementation of the hash file
`[0035]
`system and method of the present invention as disclosed
`herein, its application is directed toward a high availability,
`high reliability data storage system that
`leverages rapid
`advances in commodity computing devices and the robust
`
`

`
`US 2004/0148306 A1
`
`Jul. 29, 2004
`
`nature of internetwork technology such as the Internet.
`Particularly disclosed herein is a hash file system that
`manages the correspondence of one or more block(s) of data
`(including but not limited to files, directories, drive images,
`software applications, digitized voice, and rich media con-
`tent) together with one or more symbol(s) for that block of
`data, wherein the symbol may be a number, hash, checksum,
`binary sequence, or other identifier that is derived from the
`block of data itself and is statistically, probabilistically, or
`otherwise effectively unique to that block of data. The
`system itself works on any computer system including,
`without
`limitation: personal computers; supercomputers;
`distributed or non-distributed networks; storage area net-
`works (“SAN”) using IDE, SCSI or other disk buses;
`network attached storage (“NAS”) or other systems capable
`of storing and/or processing data.
`
`In a particular implementation of the hash file
`[0036]
`system disclosed herein, the symbol(s) may be derived using
`one or more hash or checksum generating engines, pro-
`grams, or algorithms, including but not limited to MD4,
`MD5, SHA, SHA-1, or their derivatives. Further, the sym-
`bol(s) may comprise parts of variable or invariable length
`symbols derived using a hash or checksum generating
`engine, program, or algorithm, including but not limited to
`MD4, MD5, SHA, SHA-1, or other methods of generating
`probabilistically unique identifiers based on data content. In
`a particular implementation disclosed herein, file seeks, or
`lookups for retrieving data or checking on the existence/
`availability of data, may be accelerated by looking at all or
`a smaller portion of the symbol, with the symbol portion
`indicating or otherwise providing the routing information for
`finding, retrieving, or checking on the existence/availability
`of the data.
`
`[0037] Further disclosed herein is a system and method for
`a hash file system wherein the symbols allow for
`the
`identification of redundant copies within the system and/or
`allow for the identification of copies within the system
`redundant with data presented to the system for filing and
`storage. The symbols allow for the elimination of, or allow
`for the screening of, redundant copies of the data and/or
`parts of the data in the system or in data and/or parts of data
`presented to the system, without loss of data integrity and
`can provide for the even distribution of data over available
`storage for the system. The system and method of the present
`invention as disclosed herein requires no central operating
`point and balances processing and/or input/output (“I/O”)
`load across all computers, supercomputers, or other devices
`capable of storing and/or processing data attached to the
`system. The screening of redundant copies of the data and/or
`parts of the data provided herein allows for the creation,
`repetitive creation, or retention of intelligent boundaries for
`screening other data in the system, future data presented to
`the system, or future data stored by the system.
`
`[0038] The present invention is illustrated and described in
`terms of a distributed computing environment such as an
`enterprise computing system using public communication
`channels such as the Internet. However, an important feature
`of the present invention is that it is readily scaled upwardly
`and downwardly to meet the needs of a particular applica-
`tion. Accordingly, unless specified to the contrary the
`present invention is applicable to significantly larger, more
`complex network environments as well as small network
`environments such as conventional LAN systems.
`
`[0039] With reference now to FIG. 1, the present inven-
`tion may be utilized in conjunction with a novel data storage
`system on a network 10.
`In this figure, an exemplary
`internetwork environment 10 may include the Internet which
`comprises a global
`internetwork formed by logical and
`physical connection between multiple wide area networks
`(“WANs”) 14 and local area networks (“LANs”) 16. An
`Internet backbone 12 represents the main lines and routers
`that carry the bulk of the data traffic. The backbone 12 is
`formed by the largest networks in the system that are
`operated by major Internet service providers (“ISPs”) such
`as GTE, MCI, Sprint, UUNet, and America Online, for
`example. While single connection lines are used to conve-
`niently illustrate WANs 14 and LANs 16 connections to the
`Internet backbone 12, it should be understood that in reality,
`multi-path,
`routable physical connections exist between
`multiple WANs 14 and LANs 16. This makes internetwork
`10 robust when faced with single or multiple failure points.
`
`It is important to distinguish network connections
`[0040]
`from internal data pathways implemented between periph-
`eral devices within a computer. A “network” comprises a
`system of general purpose, usually switched physical con-
`nections that enable logical connections between processes
`operating on nodes 18. The physical connections imple-
`mented by a network are typically independent of the logical
`connections that are established between processes using the
`network. In this manner, a heterogeneous set of processes
`ranging from file transfer, mail transfer, and the like can use
`the same physical network. Conversely, the network can be
`formed from a heterogeneous set of physical network tech-
`nologies that are invisible to the logically connected pro-
`cesses using the network. Because the logical connection
`between processes implemented by a network is indepen-
`dent of the physical connection, internetworks are readily
`scaled to a virtually unlimited number of nodes over long
`distances.
`
`In contrast, internal data pathways such as a system
`[0041]
`bus, peripheral component interconnect (“PCI”) bus, Intel-
`ligent Drive Electronics (“IDE”) bus, small computer sys-
`tem interface (“SCSI”) bus, and the like define physical
`connections that
`implement special-purpose connections
`within a computer system. These connections implement
`physical connections between physical devices as opposed
`to logical connections between processes. These physical
`connections are characterized by limited distance between
`components, limited number of devices that can be coupled
`to the connection, and constrained format of devices that can
`be connected over the connection.
`
`In a particular implementation of the present inven-
`[0042]
`tion, storage devices may be placed at nodes 18. The storage
`at any node 18 may comprise a single hard drive, or may
`comprise a managed storage system such as a conventional
`RAID device having multiple hard drives configured as a
`single logical volume. Significantly, the present invention
`manages redundancy operations across nodes, as opposed to
`within nodes, so that the specific configuration of the storage
`within any given node is less relevant.
`
`[0043] Optionally, one or more of the nodes 18 may
`implement storage allocation management (“SAM”) pro-
`cesses that manage data storage across nodes 18 in a
`distributed, collaborative fashion. SAM processes prefer-
`ably operate with little or no centralized control for the
`
`

`
`US 2004/0148306 A1
`
`Jul. 29, 2004
`
`system as whole. SAM processes provide data distribution
`across nodes 18 and implement recovery in a fault-tolerant
`fashion across network nodes 18 in a manner similar to
`
`paradigms found in RAID storage subsystems.
`
`[0044] However, because SAM processes operate across
`nodes rather than within a single node or within a single
`computer, they allow for greater fault tolerance and greater
`levels of storage efliciency than conventional RAID sys-
`tems. For example, SAM processes can recover even where
`a network node 18, LAN 16, or WAN 14 become unavail-
`able. Moreover, even when a portion of the Internet back-
`bone 12 becomes unavailable through failure or congestion,
`the SAM processes can recover using data distributed on
`nodes 18 that remain accessible. In this manner, the present
`invention leverages the robust nature of internetworks to
`provide unprecedented availability, reliability, fault toler-
`ance and robustness.
`
`[0045] With reference additionally now to FIG. 2, a more
`detailed conceptual view of an exemplary network comput-
`ing environment in which the present invention is imple-
`mented is depicted. The internetwork 10 of the preceding
`figure (or Internet 118 in this figure) enables an intercon-
`nected network 100 of a heterogeneous set of computing
`devices and mechanisms 102 ranging from a