HK1188858B - Reusable content addressable stores - Google Patents

Abstract

Techniques are described for using chunk stores as building blocks to construct larger chunk stores. A chunk store constructed of other chunk stores (a composite chunk store) may have any number and type of building block chunk stores. Further, the building block chunk stores within a composite chunk store may be arranged in any manner, resulting in any number of levels within the composite chunk store. The building block chunk stores expose a common interface, and apply the same hash function to content of chunks to produce the access key for the chunks. Because the access key is based on content, all copies of the same chunk will have the same access key, regardless of the chunk store that is managing the copy. In addition, no other chunk will have that same access key.

Description

Reusable content addressable storage

Technical Field

The present invention relates to a storage system, and more particularly, to a technique for constructing a composite (composite) chunk store with a plurality of building block chunk stores.

Background

The information used to access the stored digital item is referred to herein as an access key (access key) for the stored item. In a typical file system, stored items are retrieved based on (a) the item's storage location and (b) the item's name or identifier. For example, if a file named "foo.txt" is located in a directory named "c: \ myfiles \ text", the application may use the pathname "c: \ myfiles \ text \ foo.txt" as an access key to retrieve the file from the file system. Since conventional access keys are based on the location of the item to be retrieved, the access key changes as the item moves. In addition, each copy of an item has a different access key because each copy is stored at a different location.

In contrast to conventional file systems, Content Addressable Storage (CAS) systems allow an application to retrieve items from storage based on hash values generated from the contents of the items. Because the CAS system performs storage-related operations on items based on hash values generated from the items 'contents, and the hash values are based on the items' contents rather than where the items are stored, applications requesting the operations can perform operations without knowing the number or location of stored copies of the items. For example, the CAS system may store multiple copies of item X in locations A, B and C. An application desiring to retrieve item X may perform an operation by sending a hash value based on the content of item X to the CAS system. Based on the hash value, the CAS system will provide a copy of item X retrieved from one of locations A, B and C to the application. Thus, the application can obtain item X without knowing where item X is actually stored, how many copies of item X exist, or the particular location where the retrieved copy is actually obtained.

Storing a digital item, such as a file or message, typically involves making a call to a "chip storage system". A slice storage system is a storage system that performs storage operations without understanding the format or content of the digital information itself. Such a storage system is referred to as a chunk storage system because the system handles all forms of digital items as if those items were only opaque chunks (opaque chunks) of data. For example, the same piece storage system may be used by word processing applications, image management applications, and calendar systems to store documents, images, and appointments (appointments), respectively. However, from the perspective of the slice storage system, only one type of item is stored: an opaque sheet of digital information.

The disk storage system may be implemented as a CAS system. For example, a slice storage system may generate hash values for a slice by applying a cryptographic hash function (e.g., MD5, SHA-1, or SHA 2) to the slice. The slice storage system then stores the slice and maintains an index that relates the hash value to the location where the slice is stored. When the application subsequently requests retrieval of the slice, the application provides the hash value to the slice storage system. The slice storage system uses the index to locate a slice associated with the hash value and provides the thus located slice to the requesting application.

The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Accordingly, unless otherwise indicated, these approaches are not to be construed in a manner that would normally qualify as prior art merely by virtue of their inclusion in this section.

Disclosure of Invention

According to one aspect of the present invention, there is provided a composite chunk store comprising a plurality of structure chunk stores; wherein each of the plurality of fabric block tile stores is configured to: exposing the common interface to receive the sheet handling requirements; and using a hash value as an access key for a slice stored in the composite slice storage, the hash value being generated by applying a particular hash function to the content of the slice; wherein the plurality of fabric block tile stores comprises a first tile store and a second tile store; wherein the first slice storage is a different type of slice storage than the second slice storage; wherein the particular hash function used to generate the access key for the slice stored in the composite slice store is the same hash function for all of the plurality of structural block slice stores.

According to another aspect of the invention, there is provided a method comprising: receiving a first slice operation request at a shared interface of a first slice store, the first slice operation request targeting a particular slice and indicating an access key for the particular slice; wherein the first chunk store is one of a plurality of chunk store arrangements as part of a composite chunk store; wherein the first tile store is a cache tile store; wherein the cache tile store has a cache memory for temporarily storing a copy of a tile for the fabric block tile store; wherein the cache tile storage is not configured to permanently store any tiles for the fabric block tile storage; in response to receiving the first slice operation request, the first slice store uses the access key to determine whether the particular slice is stored in the cache; and in response to determining that the particular slice is not stored in the cache, the first slice store sends a second slice operation request to a second slice store that is part of the composite slice store; wherein the second slice operation requires targeting the particular slice and indicating the access key for the particular slice; in response to receiving the second slice operation requirement, the second slice storage retrieves the particular slice from persistent storage using the access key; wherein the same hash function is applied to the contents of a slice to generate an access key for the slice, regardless of which fabric block slice store in the composite slice store stores the slice; wherein the method is performed by one or more computing devices.

According to yet another aspect of the invention, one or more non-transitory computer-readable media are provided that store instructions that, when executed, cause the method described above to be performed.

Drawings

In the drawings:

FIG. 1 is a block diagram of a compact store according to an embodiment of the present invention;

FIG. 2 is a block diagram of the composite chunk store of FIG. 1, illustrating an example of different types of structural chunk stores that may be combined to form the composite chunk store;

FIG. 3 is a block diagram that illustrates a computer system upon which an embodiment of the invention may be implemented; and

FIG. 4 is a block diagram of a compact store illustrating an example scenario of possible real-world usage according to an embodiment.

Detailed Description

In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

General overview

The present invention provides techniques for using tile stores as building blocks to build larger tile stores. A chunk store composed of other chunk stores is referred to herein as a "composite chunk store". The chunk stores that make up a composite chunk store are referred to herein as building block chunk stores.

A composite chunk store may have any number and type of chunk stores. Moreover, the building block sheet stores in a composite sheet store may be arranged in any manner, thereby forming any number of levels (levels) in the composite sheet store. In a composite chunk store, the chunk store that calls other chunk stores is referred to herein as a middle chunk store.

The fabric block sheet stores belonging to a composite sheet store may be located locally and/or remotely with respect to each other. For example, a single composite chunk store may have structure chunk stores A, B, C and D, where chunk stores A and B are managed by the same computing device, chunk store C is on a different device within the same network as chunk stores A and B, and chunk store D is on a completely different network than chunk stores A, B and C. By allowing the building block sheet store to be distributed across multiple networks, the sheet store belonging to the composite sheet store can be geographically (geographically) deployed in a very flexible manner to achieve performance goals, such as reducing network latency.

According to one embodiment, each of the fabric block chip stores exposes the same interface to receive requests for chip operations. In addition, the middle slice stores are designed to call other fabric block slice stores through the same common interface. Thus, a chunk store can be added to, removed from, or rearranged within a composite chunk store without having to fundamentally change the protocol under which the chunk store interaction occurs.

According to one embodiment, within the composite chunk store, all of the chunk store structures are used with the same hash function to generate access keys for the chunks managed by those chunk store structures. In addition, each slice store applies the hash function (hash function) to the content of the slice to generate an access key for the slice. By using a common hash function across all the fabric chunk pieces, and generating access keys by applying the hash function to the content of the pieces, it is ensured that each piece store within the composite piece store will either provide the correct piece or will not provide any piece, given any access key.

Compact sheet storage example

Referring to fig. 1, there is a block diagram illustrating a compact storage 100 according to an embodiment of the present invention. A composite chunk store 100 includes a number of fabric chunk stores 104, 106, 108, 110, 114, and 116. All of the tile stores 104, 106, 108, 110, 112, 114, and 116 expose the same interface (common interface 102).

A slice operation request from outside an entity to composite slice storage 100 is formed by invoking common interface 102 of one of the fabric block slice storages within composite slice storage 100. FIG. 1 illustrates a case where an external slice operation request 150 is sent directly to the shared interface 102 of any of the slice stores 104, 106, 108, 110, and 116. Upon receiving a slice operation request 150, a slice store may forward (forward) the request to the shared interface 102 of another slice store. For example, upon receiving an external slice operation request 150 through its shared interface 102, slice store 140 may send the slice operation request to shared interface 102 of slice store 108. In turn, slice store 108 may send a slice operation request to slice store 116. Thus, a single external slice operation request 150 may traverse multiple tiers within the composite slice store 100.

According to one embodiment, external slice operation requests 150 may also be directly submitted to any level of slice storage within composite slice store 100. For example, external slice operation request 150 may be sent directly to slice store 116, or directly to slice store 108. The ability of the fabric block piece stores to call each other through the same common interface 102, and the ability of external piece operation requests 150 to be sent directly to any level of piece store of the composite piece store 100 through the same common interface 102, allows the internal composition and arrangement of the composite piece store to be easily customized to the specific needs of the user. Furthermore, custom combinations and arrangements can be easily modified as the needs of the user change.

Generating access keywords

According to one embodiment, all the fabric block chunk stores within the composite chunk store use the same hash function to generate the access key, and the access key for each chunk is generated by applying the hash function to the content of the chunk. According to one embodiment, the hash function is a constant (immutable) hash function, wherein applying the hash function to a given slice always generates the same access key. Examples of hash functions that may be used to generate the access key include, but are not limited to, MD5, SHA-1, and SHA-2.

In many cases, the building block chunk store of a composite chunk store will be distributed across several computers, some of which may be located remotely from others. However, since all the fabric block slice stores use the same hash function, and the hash function generates hash values based on the contents of the slices, the composite slice store does not need to employ complex cache coherency protocols to ensure that all fabric block slices operate under the same access key-slice mapping.

In particular, any of the chunk stores within the composite chunk store that pass an access key will be able to retrieve the correct chunk based on the access key, or will not retrieve any chunk based on the access key. There will be no chunk store that maps access keys to the wrong chunk. In addition, since the access key does not take into account the location of the slice, the access key will not become "invalid" due to the relocation of the corresponding slice, and all copies of the same slice will have the same access key regardless of which fabric block slice manages the copy.

Type of slice storage

A composite chunk store (such as composite chunk store 100) may include a plurality of different types of structural chunk stores. The type of chunk stores that a compact store 100 comprises, and how the chunk stores are arranged within the compact store 100, may be tailored to the particular needs of the user. The type of slice storage that a composite slice store may include, but is not limited to, local slice storage, remote slice storage, caching (caching) slice storage, replicated slice storage, splitter (splitter), intentional error slice storage (intentional error slice storage), and metric-generating slice storage. Fig. 2 is a block diagram illustrating composite chunk store 100 of fig. 1 including a plurality of different types of chunk stores. Each of these types of slice stores will be described in more detail below.

Local slice storage

A local slice store is a slice store that stores slices in the local storage of the machine that issued the external slice operation request 150. In FIG. 2, slice store 110 is a local slice store. In general, performing a slice operation on-chip within the local slice store 110 will consume fewer resources than performing a slice operation on a remote slice store. However, the amount of space available on local memory may be less than the amount of space required to store all of the slices that composite slice storage 100 needs to manage. Thus, compound chunk store 100 includes several additional types of chunk stores that do not occupy local storage of the chunk operation requester.

Cache tile storage

The cache tile store serves as a proxy for one or more other tile stores. In particular, a cache tile store temporarily stores a copy of a subset of tiles (subset) that is permanently stored in one or more other tile stores. For example, in FIG. 2, slice store 106 is shown as a cache slice store that acts as a proxy for slice store 112. Thus, tile store 106 includes a cache that temporarily stores a subset of tiles that exist on a remote storage on which tile store 112 stores the tiles. When a cache tile store 106 receives a request to retrieve a tile, the cache tile store 106 first checks its cache for the requested tile. The cache tile checks its cache by determining if any cache tile is associated with the hash value received in the tile request. For example, such checking may be performed using an index that indicates the locations of those cache tiles having hash values associated with the cache tiles.

If a copy of the requested slice is in the cache, cache slice store 106 provides the slice without forwarding the request to slice store 112. If there is no copy of the requested slice in the cache, the cache slice store 106 calls the shared interface 102 of the slice store 112 to retrieve the requested slice. Cache tile store 106 provides the tile to the requestor when the tile is retrieved from tile store 112, and may store a copy of the tile in its cache. The slice within the cache of cache slice storage 106 that is replaced to provide space for the new slice is selected based on a replacement policy implemented by cache slice storage 106. The particular replacement policy used by the cache tile storage 106 may vary depending on the implementation and may take into account factors such as the most recent access of each cache tile and the frequency with which each cache tile is accessed.

Upon receiving a request to store a slice, the cache slice store 106 calls the shared interface 102 of the slice store 112 to cause the slice store 112 to store the slice. The cache tile store 106 may also store a copy of the tile to be stored in its cache, depending on the caching policy implemented by the cache tile store 106.

Different cache tile stores may employ different policies to handle tile operation requests. For example, a cache tile store that employs a "write-through" cache may respond to a tile store request by directly calling another tile store to store the tile. Alternatively, a journal cache tile store may respond to a tile store request by storing the tile in cache without directly accessing additional tile stores. Such a log cache tile stores a trace log of tiles within its cache that have not yet been sent to another tile store for storage. After a period of time, the log cache tile store may be called to perform a batch tile write operation, thereby causing all cache tiles that have not yet been written to be stored by another tile store.

For example, log cache tile storage may be beneficial where the cache is large enough to hold all or most of the frequently requested tiles. For example, assume that cache tile store 106 is a log cache tile store that is cached sufficiently large to store all or nearly all of the frequently requested tiles persistently stored in tile store 112. In these cases, a tile retrieval request received by cache tile store 106 will require little use of the storage device of tile store 112. In addition, since slice store 106 defers slice write operations, slice write operations received by cache slice store 106 will also require little use of the storage devices of slice store 112. Thus, the reservoir devices of the chip storage 112 may be powered down for a longer period of time, thereby reducing the energy consumption of the device and increasing its lifetime.

Remote slice storage

The remote slice store acts as a proxy for another slice store such as, but not limited to, a local slice store or a cache slice store. The interface of the remote slice storage is the same as the interface of the other slice storages. The remote slice storage makes the network and physical location of the other slice storage transparent. In FIG. 2, the slice stores 112 and 116 are shown as remote slice stores.

Copy storage

A replicated chunk store is a chunk store designed to ensure that two or more other chunk stores remain synchronized. In the embodiment shown in FIG. 2, chunk store 108 is a replicated chunk store 108 used to keep the chunk store synchronized with chunk store 116. Therefore, replicated chunk store 108 responds to any chunk store request by calling both chunk stores 114 and 116 to store the chunk. Replicating chunk storage increases the reliability of the composite chunk store 114 by ensuring that replicated chunks are not lost when one of the synchronized chunk stores fails.

For example, if replicated chunk store 108 keeps chunk stores 114 and 116 synchronized, chunks stored in chunk store 114 may be retrieved from chunk store 116 in the event of a failure of chunk store 114, and chunks stored in chunk store 116 may be retrieved from chunk store 114 in the event of a failure of chunk store 116.

Divider

A partitioner is a shard store that forwards requests to other shard stores based on the range to which the hash value associated with the shard operation request belongs. In FIG. 2, the slice store 114 is shown as a splitter that forwards slice operation requests to either the slice store 112 or the slice store 108 according to hash values associated with the slice operation requests. For example, the splitter tile store 104 may be designed to forward all tile operation requests having hash values less than or equal to X to the tile store 112, and to forward all tile operation requests having hash values greater than X to the tile store 108. In this example, the splitter chunk store 104 splits the request between two other chunk stores. However, the partitioner may split the requests it receives into any number of shard stores, with requests associated with different ranges of hash values forwarded to each of the shard stores.

Intentionally faulty chip storage

An intentionally erroneous chunk store is a chunk store designed to at least some time intentionally produce erroneous results. For example, the intentional error chunk store may be designed not to perform actions (actions) on some requests it receives. Alternatively, the intentional error may return an error message, or not acknowledge (acknowledge) its action. For example, a deliberately faulty chunk store may be beneficial in a test environment where it is important to determine how other chunk stores, or the composite chunk store as a whole, will react to a particular fault condition.

Metric-occurrence tile storage

A metric-occurrence chunk store is a chunk store configured to generate metrics related to the operation of other chunk stores. For example, a metric-occurrence tile store may be designed to forward all tile operation requests to other tile stores and track the time elapsed between forwarding the request and receiving the response. This is just one example of the type of metric that a metric-occurrence chunk store may produce. In fact, there is no limitation on the types of metrics that the metric-occurrence chunk store can produce.

Empty storage

An empty chunk store refers to nothing but accepting and receiving requests. Blank storage is useful in various environments. For example, empty storage is useful for testing the topology of a network, where the empty storage is used as a temporary substitute for the yet-to-be-developed storage of slices, similar to method stubs.

Example of a real world usage scenario

Referring to fig. 4, a block diagram illustrating how a composite piece store 400 is configured according to a real-world usage scenario. As shown, a client 402 interacts with the shared interface 102 of the cache tile store 404. The cache tile store 404 in turn requests tiles from a remote tile store 406. The remote tile store 406 sends tile requests to the shared interface 102 of another cache tile store 408 over the network 420. The slice store 408 communicates with the common interface 102 that replicates the slice store 410. Replica slice store 410 is in communication with two local slice stores 412 and 414 where replicas of the slices used by clients 402 may be stored.

Examples of common interfaces

As described above, all of the fabric block chip memories share a common interface 102. Thus, the protocol invoked by the fabric block slice memory does not change based on the nature of the fabric block slice memory. The particular interfaces supported by the fabric block chip memories of a composite chip memory may vary from one implementation to another. For example, in one embodiment, the common interface supports the following calls:

● get (access key) -request retrieval of a slice associated with a particular access key;

● put (content) -the memory that requests the particular content as a slice;

● touch (access key) -update the piece's metadata associated with a particular access key to indicate that the piece has been used or accessed;

● enumerate (access key range) -list all slices whose access keys fall within a particular range.

These are merely some examples of the types of functions that can be invoked through the common interface 102. The techniques described herein are not limited to any particular functionality, or particular parameters thereof.

Metadata

According to one embodiment, metadata about the slices that fall into a composite chunk store is retained within the composite chunk store, although each structural chunk store need not have metadata for each slice.

The metadata retained within the compact store for each slice may include, for example, the size of the slice, and the last access date of the slice. The access key of a slice is also metadata associated with the slice. However, since the access key may be copied from the content of the slice, the access key does not need to be stored explicitly separately from the slice content itself.

According to one embodiment, metadata for a given slice is retained at least by a slice store that persistently stores a primary copy (primarycopy) of the slice. For the tile stores (e.g., local or cache tile stores) that store copies of the tiles, these tile stores also store access key to storage location mappings to access the tiles based on their access keys.

Customization options

Using the building block piece storage described herein, there are virtually an infinite number of ways: in these ways, the structural composite sheet store can be customized to address the needs of a particular user. These requirements may take into account various factors such as performance, distribution, location, cost, etc.

For example, as the system grows, additional cache tile storage may be added between the existing tile storage and users experiencing slow tile retrieval times. As another example, different slice stores may focus on a particular type of slice to meet the user's objectives. For example, a composite chunk store may include one chunk store having relatively small but fast storage that is dedicated to storing frequently accessed ("hot") chunks, and another chunk store having relatively large but slower storage that is dedicated to storing infrequently accessed ("cold") chunks. As the frequency with which a given tile is accessed varies, tiles may be transferred from one tile store to another.

A composite chunk store may also include one chunk store for storing relatively small chunks, and another chunk store for storing relatively large chunks. Metadata associated with the slices, such as size, access frequency, degree of access freshness, etc., may be used as a basis for dividing storage responsibilities between the fabric block chunk stores within a composite chunk store.

The ability to customize the composite sheet store makes it easier to obtain the greatest benefit from the hardware capable of implementing the composite sheet store. For example, a composite slice store may be customized with multiple levels of cache (e.g., different cache slice stores at various levels) to account for how much of each type of storage (e.g., RAM, NAND, SSD, and compact disk) is available.

Further, as new technologies develop (e.g., new memory types), the fabric block slice store may be intended for use with these technologies. Since these fabric block piece stores expose the same common interface and use the same unchanged hash function, existing compact memory can be easily reconfigured to incorporate these new fabric block pieces.

Similarly, if a particular piece store is modified or updated, the old version of the piece store may be replaced with the new version of the piece store with little overhead or reconfiguration. For example, if an improved replicated chunk store is developed, the existing replicated chunk store may be replaced by the improved replicated chunk store without significant modification to the composite chunk store.

Overview of hardware

According to one embodiment, the techniques described herein may be implemented by one or more specific-purpose computing devices. The specific purpose computing device described above may be a hard-wired (hard-wired) implementation of the techniques, or may include digital electronic devices such as one or more Application Specific Integrated Circuits (ASICs) or field programmable gate arrays (FRGAs) programmed continuously to perform the techniques, or may include one or more general purpose hardware processors programmed according to program instructions in firmware, memory, other storage, or a combination to perform the techniques. These special purpose computing devices may also be combined with custom hardwired logic, ASICs, or FPGAs with custom programming to complete the technology.

These specific purpose computing devices may be a desktop computer system, portable computer system, handheld device, network appliance, or any other device in combination with hardwired and/or program logic to implement the techniques. Any portable device with computing capabilities may be used to implement the techniques described herein, including but not limited to mobile devices such as tablets, cell phones, PDAs, and the like.

FIG. 3 illustrates a block diagram of a computer system 300 upon which an embodiment of the invention is implemented. Computer system 300 includes a bus 302 or other communication mechanism for communicating information, and a hardware processor 304 coupled with bus 302 for processing information. The hardware processor 304 may be, for example, a general purpose microprocessor.

Computer system 300 also includes a main memory 306, such as a Random Access Memory (RAM) or other dynamic storage device, coupled to bus 302 for storing information or instructions to be executed by processor 304. Main memory 306 also may be used for storing temporary variables or other intermediate information during execution of instructions by processor 304. These instructions, when stored in a non-transitory storage medium accessible to processor 304, cause computer system 300 to be a specific-purpose machine that is customized to perform specific operations within the instructions.

Computer system 300 further includes a Read Only Memory (ROM) 308 or other static storage device coupled to bus 302 for storing static information and instructions for processor 304. A storage device 310, such as a magnetic disk or optical disk, is provided and coupled to bus 302 for storing information and instructions.

Computer system 300 may be coupled via bus 302 to a display 312, such as a Cathode Ray Tube (CRT), for displaying information to a computer user. An output device 314, such as an alphanumeric or other key, is coupled to bus 302 for communicating information or command selections to processor 304. Another type of user input device is cursor control 316, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 304 and for controlling cursor movement on display 312. This input device typically has two degrees of freedom in two axes (a first axis, e.g., x, and a second axis, e.g., y), which allows the device to specify positions in a plane.

Computer system 300 may implement the techniques described herein using custom hardwired logic, one or more ASICs or FPGAs, firmware, and/or programming logic in combination with the computer system to cause or program computer system 300 to become a specific-purpose machine. According to one embodiment, the techniques described herein are implemented by computer system 300 in response to processor 304 executing one or more sequences of one or more instructions stored in main memory 306. Such instructions may be read into main memory 306 from another storage medium, such as storage device 310. Execution of the sequences of instructions stored in main memory 306 causes processor 304 to perform the process steps described herein. In an alternative embodiment, hard-wired circuitry may be used in place of or in combination with software instructions.

The term "storage medium" as used herein refers to a non-transitory medium that stores data and/or instructions that cause a machine to function in a particular manner. Such a storage medium may include a non-volatile medium and/or a volatile medium. Non-volatile media includes, for example, optical and magnetic disks, such as storage device 310. Volatile media includes dynamic memory, such as main memory 306. Common forms of storage media include, for example: a floppy disk, a flexible disk, hard disk, solid state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH memory (FLASH-EPROM), NVRAM, any other memory chip or cartridge.

Storage media is distinct from but may be combined with transmission media. Transmission media participate in the transfer of information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus 302. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infrared communications.

Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor 304 for execution. For example, the instructions may initially be carried on a magnetic disk or solid state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. Modem local computer system 300 can accept the data on the telephone line and convert the data to an infrared signal using an infrared transmitter. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus 302. Bus 302 carries the data to main memory 306, from which the processor retrieves and executes the instructions. The instructions received by main memory 306 may optionally be stored on storage device 310 either before or after execution by processor 304.

Computer system 300 also includes a communication interface 318 coupled to bus 302. Communication interface 318 provides a two-way data communication coupling to a network link 320 that is connected to a local network 322. For example, communication interface 318 may be an Integrated Services Digital Network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As yet another example, communication interface 318 may be a Local Area Network (LAN) card to provide a data communication to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface 318 sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link 320 typically provides data communication through one or more networks to another data device. For example, network link 320 may provide a connection through local network 322 to a host computer 324 or to data equipment operated by an Internet Service Provider (ISP) 326. The ISP326 in turn provides data communication services through the world wide packet data communication network (now commonly referred to as the "Internet") 328. Local network 322 and Internet 328 are both electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link 320 and through communication interface 318, which carry the digital data to and from computer system 300, are examples of forms of transmission media.

Computer system 300 is capable of sending messages and receiving data, including programming code, through the network(s), network link 320 and communication interface 318. In the Internet example, a server 330 might transmit a requested code for an application program through Internet 328, ISP326, local network 322 and communication interface 318.

The received code may be executed by processor 304 as it is received, and/or stored in storage device 310, or other non-volatile storage for later execution.

In the foregoing specification, embodiments of the invention have been described with reference to various specific details, which may vary from one embodiment to another. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. The sole and exclusive indicator of the scope of the invention, and what is intended by the applicants to be the scope of the invention, is the literal and equivalent scope of the set of claims, which issue from this application, and in the specific form in which such claims are defined, including any subsequent correction.

Claims (15)

1. A composite chunk store comprising a plurality of building block chunk stores; wherein each of the plurality of fabric block tile stores is configured to:

exposing the common interface to receive the sheet handling requirements; and

using a hash value as an access key for a slice stored in the composite slice storage, the hash value being generated by applying a hash function to the contents of the slice stored in the composite slice storage;

wherein the plurality of fabric block tile stores comprises a first tile store and a second tile store;

wherein the first slice storage is a different type of slice storage than the second slice storage;

wherein the hash function used to generate access keys for slices stored in the composite slice store is the same hash function for all of the plurality of structural block slice stores.

2. The compact sheet store of claim 1, wherein the first sheet store is configured to invoke a common interface of one or more other of the plurality of fabric block sheet stores in response to a call made to a common interface of the first sheet store.

3. The compact storage of claim 2, wherein the first tile storage is a cache tile storage.

4. The compact storage of claim 3, wherein the first tile storage uses a write-through cache policy.

5. The compact storage of claim 3, wherein the first slice storage uses a journaling caching policy.

6. The compact storage of claim 2, wherein the first chunk storage is a duplicate chunk storage configured such that at least two other chunk storages remain synchronized.

7. The compact sheet storage of claim 2, wherein the first slice storage is a splitter slice storage configured to forward slice operation requests to other fabric block slice storages based on access key ranges in which the access keys determined by the slice operation requests fall.

8. The compact store of claim 1, wherein the first slice store is a local slice store.

9. The compact disk store of claim 1, wherein the first disk store is a remote disk store.

10. The compact storage of claim 1, wherein:

the first sheet store is a sheet store configured for storing sheets exceeding a size; and is

The composite sheet store comprises another structural block sheet store configured for storing sheets smaller than the size.

11. The compact storage of claim 1, wherein:

the first tile store is a tile store configured to store tiles having an access frequency exceeding a threshold; and is

The composite chunk store comprises another fabric chunk store configured to store chunk stores for chunks having access frequencies below the threshold.

12. A method for reusable content addressable storage, comprising:

receiving a first slice operation request at a shared interface of a first slice store, the first slice operation request targeting one slice and indicating an access key for the one slice;

wherein the first chunk store is one of a plurality of chunk store arrangements as part of a composite chunk store;

wherein the first tile store is a cache tile store;

wherein the cache tile store has a cache memory for temporarily storing a copy of a tile for the fabric block tile store;

wherein the cache tile storage is not configured to permanently store any tiles for the fabric block tile storage;

in response to receiving the first slice operation request, the first slice store uses the access key to determine whether the one slice is stored in the cache; and

in response to determining that the one slice is not stored in the cache, the first slice store sends a second slice operation request to a second slice store that is part of the composite slice store;

wherein the second slice operation requires targeting the one slice and indicating the access key for the one slice;

in response to receiving the second slice operation requirement, the second slice storage retrieves the one slice from persistent storage using the access key;

wherein the same hash function is applied to the contents of said one slice to generate an access key for said one slice, regardless of which fabric block chunk store in said composite chunk store stores said one slice;

wherein the method is performed by one or more computing devices.

13. The method of claim 12, wherein:

in the composite sheet storage, the common interface is realized by the storage of various types of structural blocks; and is

The composite slice store comprises at least one splitter slice store.

14. The method of claim 12, wherein:

in the composite sheet storage, the common interface is realized by the storage of various types of structural blocks; and is

The composite chunk store includes at least one replicated chunk store.

15. The method of claim 12, wherein:

in the composite sheet storage, the common interface is realized by the storage of various types of structural blocks; and is

The composite piece store comprises at least one remote piece store.