Content addressable storage with reduced latency

A system and method for storing data in a content-addressable system is provided. The system includes a content-addressable storage system and a persistent cache. The persistent cache includes a temporary address generator that is configured to generate a temporary address which is associated with data to be stored in the persistent cache, and a non-content-addressable storage system configured to store and retrieve data in the persistent cache using the temporary address. The persistent cache further comprises an address translator configured to map a temporary address associated with the data in the non-content addressable storage system with a content address associated with the data in the content-addressable storage system.

BACKGROUND

1. Technical Field

The present invention relates to storing data in a content-addressable storage system, and more specifically, to interposing a storage layer between an application and a content-addressable storage system for reducing the latency associated with writing data to the content-addressable storage system.

2. Description of the Related Art

Content-addressable storage (CAS) systems are more complex with respect to writing data than traditional storage systems. Before acknowledging a synchronous write operation, a CAS system calculates a hashkey based on the content of the block, performs a check to determine whether or not a block with identical contents (to the one currently being written) has already been written to the CAS system (e.g., by looking up values in a hash table), and writes the block if it determines that the block is unique. The acknowledgment also returns a content address, which is equal to or derived from the hashkey. The content address is used during read operations to retrieve the block.

The calculation of the hashkey, as well as the check to determine whether or not a block with identical contents was previously stored, contribute significantly to the latency associated with writing data to a CAS system.

SUMMARY

In accordance with the present principles, a system is provided for storing data in a storage system. The system includes a content-addressable storage system and a persistent cache. The persistent cache includes a temporary address generator that configured to generate a temporary address which is associated with data to be stored in the persistent cache, and a non-content-addressable storage system configured to store and retrieve data in the persistent cache using the temporary address. The persistent cache further comprises an address translator configured to map a temporary address associated with the data in the non-content addressable storage system with a content address associated with the data in the content-addressable storage system.

In accordance with the present principles, a method for storing data in a storage system includes determining whether data associated with a write request is to be stored in a non-content-addressable storage system or written directly to a content-addressable storage system. If it is determined that the data is to be stored in the non-content-addressable storage system, a temporary address is generated for the data to be stored in the non-content-addressable store and an acknowledgement that data is persistently stored in the non-content addressable storage system may be sent before the data is written to a content-addressable storage system. In addition, at least one temporary address associated with the data in the non-content-addressable store is mapped with a content address of the data in the content-addressable storage system after the data is written to the content-addressable storage system.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

In accordance with the present principles, a description of a storage system is provided which can reduce the latency associated with accesses to a content-addressable storage system. The system interposes a storage layer comprised of a low latency block store (LLBS) between a content-addressable block store (CABS) and an application which is issuing I/O operations in accordance with a content-addressable API. Rather than writing blocks directly to the CABS, blocks can first be written to the LLBS, acknowledged, and subsequently transferred to the CABS. At some point later in time, the blocks may then be removed from LLBS. In doing such, the disadvantages (e.g., high latency) associated with writing to content-addressable storage are eliminated or mitigated, while the advantages of using content-addressable storage (e.g., de-duplication) are retained.

An LLBS may utilize a solid-state drive or hard disk drive for persistent storage. These devices are optimized to reduce latency associated with I/O operations. In accordance with the principles described herein, the LLBS can store data temporarily and return an acknowledgement to an application so that the application does not experience the delay associated with calculating a hash or searching for values in hash table. The LLBS can also initiate a write to CABS which includes the same data that was written to the LLBS. Writes to the CABS experience high latency because of the delays associated with calculating hashes and looking up values in a hash table. However, the latency is not experienced by the application (or an end user utilizing the application) because the LLBS is able to quickly store the data and return an acknowledgment.

A data processing system suitable for storing and/or executing program code may include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code to reduce the number of times code is retrieved from bulk storage during execution. Input/output or I/O devices and systems (including but not limited to keyboards, displays, pointing systems, etc.) may be coupled to the system either directly or through intervening I/O controllers.

Network adapters may also be coupled to the system to enable the data processing system to become coupled to other data processing systems, remote printers, storage devices, or storage systems through intervening private or public networks. Modems, cable modem and Ethernet cards are just a few of the currently available types of network adapters.

Referring now to the drawings in which like numerals represent the same or similar elements and initially toFIG. 1, a block/flow diagram illustratively depicts a system100for storing data in a content-addressable storage system in accordance with the present principles. As shown therein, an application130stores data in a storage system110. The application130may be executing locally on a computer which comprises storage system110, or may be executing on a client machine that is coupled to a server or other system (e.g., via a network) which comprises storage system110.

Storage system110comprises a low latency block store (LLBS)150and a content-addressable block store (CABS)160. The CABS160may represent any type of content-addressable storage system. On the other hand, the LLBS150may include a solid-state drive (SSD) or hard disk drive (HDD) which is optimized to reduce latency associated with I/O operations. However, LLBS160is not limited to these types of storage devices, and, in general, may utilize any non-content-addressable storage media that has lower latency than CABS160with respecting to input/output (I/O) operations.

Rather than directly storing data to the CABS160, the application130may initially store data in the LLBS150. Upon successfully storing data to the LLBS150, an acknowledgment is returned to the application130. Since the LLBS150provides for reduced latency, the acknowledgement is returned relatively quickly, or at the least, quicker than CABS160is able to return an acknowledgment.

As can be seen, a content-addressable storage application programming interface (API) permits communication between both the application130and the LLBS150and LLBS150and the CABS160.

Moving on toFIG. 2, a more detailed view of a system200for storing data in a content-addressable storage system is illustratively depicted. Application130sends a write request to LLBS150. Upon receiving a write request from the application130, the cache manager210may forward the request to the non-content addressable storage system235which is configured as a key-value store230which uses the storage device240to store data persistently. To store the data from the write request to the non-content addressable storage system235, the cache manager210obtains a temporary address from the temporary address (“TA”) generator250and this address will be used as the key with which the data may be later retrieved.

The key-value store230is responsible for controlling the manner in which data is stored in the storage device240. The key-value store230stores both the data and its temporary address in storage device240. The data can later be retrieved or read using the temporary address. Storage device240is preferably a low latency system such as a solid-state drive (SSD), hard disk drive (HDD), or other device that provides for a lower latency than CABS160with respect to performing I/O operations.

Upon writing the data to the LLBS150, the cache manager210will forward an acknowledgment to the application130along with the temporary address that can be used to retrieve the data. The cache manager210will write the data, which has already been written to storage device240, to the CABS160as well. In storing the data, the CABS160will compute a hashing value based on the content of the data and perform de-duplication operations (e.g., which may involve looking up values in a hash table). Even if two identical blocks had been written to the LLBS150and each was assigned a separate temporary address, both of these blocks will eventually be mapped to the same content address when the LLBS150transfers the data to the CABS160. Since the LLBS150had previously confirmed a successful write operation, the application130can avoid the latency associated with these hashing and hash table lookup operations while retaining the de-duplication benefits associated with storing data in the CABS160.

After successfully storing the data, the CABS160returns a content address to cache manager210at the LLBS150which reflects where the data is stored in the CABS160. The content address is forwarded to the address translator220which will map the temporary address (reflecting the location of the data in the LLBS150) to the content address (reflecting the location of the data in the CABS160) and store this mapping information in storage device240. In the case where blocks have embedded addresses, the data associated with each embedded address should first be written to the CABS160and mapped to a corresponding content address before the parent block is written to the CABS160. This avoids writing temporary addresses to the CABS160.

Once the mapping of addresses has been persistently written to storage device240, the LLBS150can delete the corresponding data in storage device240. If the application130issues a subsequent read request using the temporary address, the content address associated with the temporary address can first be retrieved by the address translator220, and this information can be used to retrieve the data from the CABS160.

Although data blocks can be removed from the LLBS150in the manner explained above, removing the mapping of a temporary address to a content address may involve the cooperation of the application130. Cooperation of the application130is needed to avoid a situation where the application130requests a block using its temporary address, but neither the block, nor the mapping from that temporary address to the content address, is available at the LLBS150. One way to avoid this situation is to have the application130periodically drop all of its addresses. Once this is done, the LLBS150can delete all of its mappings. After the application130has dropped all of its addresses and the LLBS150has deleted all of its mappings, the application130can access blocks by issuing a read for the labeled block representing the root of a directed acyclic graph, e.g., in the manner explained in United States Patent Application 2010/0070698 which is herein incorporated by reference in its entirety.

While data is typically stored at the LLBS150before being transferred to the CABS160, there may be certain situations where it is preferable for the data to be stored directly in the CABS160. For example, consider the case where application130issues a write request to the LLBS150, but the LLBS150does not have sufficient space available for storing the data. Rather than waiting for the LLBS150to free up space by transferring data to the CABS160, it may advantageous to write the incoming data block directly to the CABS160. It should be noted that this is just one exemplary situation where it may be preferable to store data directly in the CABS160, and that there may be a variety of other situations where data could be written directly to the CABS160.

Since data may sometimes be stored directly to the CABS160, there may be situations where the LLBS150returns a content address, rather than a temporary address, to the application130. This can be handled transparently by the application130. However, the LLBS150needs to be able to distinguish between temporary addresses and content addresses. This can be achieved by reserving a bit in the address which indicates whether the address is a content address or a temporary address.

Referring now toFIG. 3, a block/flow diagram illustrates a method for storing data in a content-addressable storage system in accordance with the present principles. In block310, an application130issues a write request to store data on a storage system110. The storage system110may include both a non-content-addressable system (e.g., LLBS150) and a CABS160as shown inFIGS. 1 and 2.

Upon receiving the write request, the LLBS150will assign a temporary address to the data in block320. The temporary address is used to store and retrieve the data in the non-content addressable storage235. Unlike the content address which will be subsequently assigned by the CABS160, determining a temporary address for storing the data does not involve computing a hash. In one embodiment, the temporary address may be generated by the temporary address generator250inFIG. 2, and used by the key-value store230to store the data.

Next, in block330, the data which is the subject of the write request is stored at the LLBS150along with the temporary address which was assigned to the data block. The manner in which this information is stored may differ. For example, in one embodiment, the non-content addressable store is configured as a key-value store, where the keys are the temporary addresses and the values are the data contents of the write requests. Moreover, althoughFIG. 2discloses a single storage device240for storing both the mapping from temporary address to content addresses and the data retrievable through the temporary address, in other embodiments the mapping between temporary address and content addresses, and the data retrievable through the temporary address may be stored on separate storage devices.

After the data from the application130has been stored in the LLBS150, the LLBS150sends an acknowledgement to that application130which indicates that the data has been successfully stored (block340). The acknowledgement sent from the LLBS150to the application130also includes the temporary address associated with the data to allow the application130to later retrieve the data. As explained above, the storage device240at the LLBS150provides for relatively low latency with respect to storing information when compared to the CABS160. Since the LLBS150is able to write the data to storage device240and return an acknowledgment to the application130more quickly than CABS160would have been able to do so, the latency experienced by the application130is reduced.

Upon forwarding the acknowledgment to the application130, the LLBS150will subsequently write the data to the CABS160in block350. Once the data stored at the LLBS150has been successfully copied to the CABS160, the CABS160will return a content address to the LLBS150. The content address, which is based on the content of the data block being written to CABS160, reflects where the data is written in the CABS160.

As explained above, storing data in a content-addressable system (e.g., CABS160) involves performing latency-intensive operations such as computing a hash and performing de-duplication operations. However, by storing data initially at LLBS150before transferring the data to CABS160, the application130does not have wait for these latency-intensive operations to be performed. Nevertheless, since the data is eventually transferred to the CABS160, the application130is able to appreciate the benefits of the de-duplication performed by the CABS160. Hence, the storage system110of the present application allows an application130to reap the benefits of content-addressable storage while eliminating, or at least mitigating, the disadvantages of storing data in such a system.

After the data is stored in CABS160and the content address is returned to the LLBS150, the content address will be sent to the address translator220which is configured to map the temporary address to the content address and store this information in storage device240(block360). Upon storing the mapping information, the data (which is currently stored in both the LLBS150and the CABS160) may be deleted from the LLBS150in block370. If the application130wishes to read the data at some later point, the read request may include the temporary address of the data. Despite the fact that the data which was previously stored at LLBS150has been deleted from LLBS150, the temporary address may be used by the address translator220to identify the corresponding content address of the data in the CABS160. The data may then be read from the CABS160using the content address.

In block380, the address mapping (i.e., the mappings between the temporary address and the content address) on the LLBS150are periodically removed. This may be advantageous because the mappings stored at LLBS150may grow to be very large in size, thus taking up space in the storage device240which can be used otherwise for storing data. However, before the mapping information can be deleted from the LLBS150, the application130should drop the addresses (or at least the temporary addresses) that are being stored by the application130. This ensures that the application130does not issue a request for data (using the temporary address of the data) at the LLBS150when neither the data itself, nor the mapping of the data, is stored in the LLBS150.

The manner in which the application130is told to drop address may differ. For example, in one embodiment, the LLBS150may monitor the amount of mapping information being stored. Once the size of the mapping information exceeds a certain threshold, the LLBS150may send an “address drop signal” to the application130to tell the application130that the address information being stored by the application130should be dropped. After the application130has dropped the addresses, an acknowledgment may be sent to the LLBS150which indicates such. Upon confirming that the addresses were dropped by the application130, the LLBS150can then delete the mapping information stored on storage device240. Other ways of indicating that addresses should be dropped by the application130are also contemplated.

Having described the preferred embodiments of a system and method for storing data in a content-addressable storage system (which are intended to be illustrative and not limiting), it is noted that modifications and variations can be made by persons skilled in the art in light of the above teachings. It is therefore to be understood that changes may be made in the particular embodiments disclosed which are within the scope of the invention as outlined by the appended claims. Having thus described aspects of the invention, with the details and particularity required by the patent laws, what is claimed and desired protected by Letters Patent is set forth in the appended claims.