Distributed Data Storage System Providing De-duplication of Data Using Block Identifiers

• US 20110219205A1
• Filed: 03/04/2011
• Published: 09/08/2011
• Est. Priority Date: 03/05/2010
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: SolidFire, Inc. (NetApp, Inc.)
• Inventors: Wright, David D.
• Granted Patent: US 8,671,265 B2
• Time in Patent Office: Days
• US Class Current: 711/206
• CPC Class Codes: G06F 12/0284 Multiple user address space allocation, e.g. using different base addresses interprocessor communication G06F15/163
• CPC Class Codes: G06F 15/173 using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/163 Server or database system
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

An access request including a client address for data is received. A metadata server determines a mapping between the client address and storage unit identifiers for the data. Each of the one or more storage unit identifiers uniquely identifies content of a storage unit and the metadata server stores mappings on storage unit identifiers that are referenced by client addresses. The one or more storage unit identifiers are sent to one or more block servers. The one or more block servers service the request using the one or more storage unit identifiers where the one or more block servers store information on where a storage unit is stored on a block server for a storage unit identifier. Also, multiple client addresses associated with a storage unit with a same storage unit identifier are mapped to a single storage unit stored in a storage medium for a block server.

Claims

1. A method for accessing data, the data including one or more storage units, the method comprising:

receiving an access request for data, the access request including a client address for the data;

determining, by a metadata server, a mapping between the client address and one or more storage unit identifiers for the data, each of the one or more storage unit identifiers uniquely identifying content of a storage unit, wherein the metadata server stores mappings on storage unit identifiers that are referenced by client addresses; and

sending the one or more storage unit identifiers to one or more block servers, the one or more block servers servicing the request using the one or more storage unit identifiers, wherein the one or more block servers store information on where a storage unit is stored on a block server for a storage unit identifier,

wherein multiple client addresses associated with a storage unit with a same storage unit identifier are mapped to a single storage unit stored in a storage medium for a block server.

2. The method of claim 1, wherein the access request is a write request, the method further comprising:

determining a block server in the one or more block servers based on a storage unit identifier in the one or more storage unit identifiers, wherein different block servers are associated with different ranges of storage unit identifiers; and

sending the storage unit identifier and the storage unit to the block server associated with the storage unit identifier.

3. The method of claim 2, wherein:

the block server determines if the storage unit identifier already exists on the block server,

the block server does not store the storage unit on the block server if the storage unit identifier already exists on the block server, and

the block server stores the storage unit if the storage unit identifier does not exist on the block server.

4. The method of claim 3, wherein the storage unit is not stored multiple times on a single storage medium on the block server.

5. The method of claim 1, wherein the access request is a read request, the method further comprising:

determining a storage unit identifier in the one or more storage unit identifiers for a storage unit in the one or more storage units;

determining a block server in the one or more block servers that is storing the storage unit based on the storage unit identifier, wherein different block servers are associated with different ranges of storage unit identifiers; and

sending the read request with the storage unit identifier to the determined block server.

6. The method of claim 5, wherein:

the block server identifies a location of the storage unit using the storage unit identifier, and

the block server retrieves the storage unit from the location to satisfy the read request.

7. The method of claim 1, further comprising:

computing a Bloom filter for a plurality of storage unit identifiers on the metadata server; and

sending the Bloom filter to a block server, wherein the block server is configured to use the Bloom filter to test whether storage unit identifiers existing on the block server are present in the Bloom filter,

wherein storage unit identifiers and associated storage units not present in the Bloom filter are deleted from the block server.

8. The method of claim 1, wherein:

the data includes a plurality of storage units associated with the client address, and

the plurality of storage units are stored in a non-contiguous address space on a plurality of block servers.

9. The method of claim 8, wherein the plurality of block servers store storage units associated with different ranges of storage unit identifiers.

10. The method of claim 1, wherein a storage unit identifier in the one or more storage unit identifiers is computed using a hash of content for a respective storage unit.

11. The method of claim 1, further comprising redundantly storing a storage unit in the one or more storage units in multiple storage media, wherein multiple write requests are performed to redundantly store the storage unit.

12. The method of claim 1, further comprising redundantly storing the mapping between the client address and one or more storage unit identifiers in multiple metadata servers, wherein multiple write requests are performed to redundantly store the mapping.

13. The method of claim 1, further comprising determining an amount of space used for the client address, wherein storage units for the client address are stored on multiple block servers and referenced by multiple client addresses.

14. The method of claim 1, wherein the metadata server comprises a plurality of slice servers, wherein each slice server manages a range of mappings between client addresses and storage unit identifiers for the metadata server.

15. The method of claim 1, wherein the storage medium comprises a solid state storage device.

16. A non-transitory computer-readable storage medium containing instructions for accessing data, the data including one or more storage units, the instructions for controlling a computer system to be operable to:

receive an access request for data, the access request including a client address for the data;

determine, by a metadata server, a mapping between the client address and one or more storage unit identifiers for the data, each of the one or more storage unit identifiers uniquely identifying content of a storage unit, wherein the metadata server stores mappings on storage unit identifiers that are referenced by client addresses; and

send the one or more storage unit identifiers to one or more block servers, the one or more block servers servicing the request using the one or more storage unit identifiers, wherein the one or more block servers store information on where a storage unit is stored on a block server for a storage unit identifier,

wherein multiple client addresses associated with a storage unit with a same storage unit identifier are mapped to a single storage unit stored in a storage medium for a block server.

17. The computer-readable storage medium of claim 16, wherein the access request is a write request, the instructions further operable to:

determine a block server in the one or more block servers based on a storage unit identifier in the one or more storage unit identifiers, wherein different block servers are associated with different ranges of storage unit identifiers; and

send the storage unit identifier and the storage unit to the block server associated with the storage unit identifier.

18. The computer-readable storage medium of claim 17, wherein:

the block server determines if the storage unit identifier already exists on the block server,

the block server does not store the storage unit on the block server if the storage unit identifier already exists on the block server, and

the block server stores the storage unit if the storage unit identifier does not exist on the block server.

19. The computer-readable storage medium of claim 16, wherein the access request is a read request, the method further comprising:

determining a storage unit identifier in the one or more storage unit identifiers for a storage unit in the one or more storage units;

determining a block server in the one or more block servers that is storing the storage unit based on the storage unit identifier, wherein different block servers are associated with different ranges of storage unit identifiers; and

sending the read request with the storage unit identifier to the determined block server.

20. A system comprising:

a metadata server configured to;

store mappings on storage unit identifiers that are referenced by client addresses;

receive an access request for data, the access request including a client address for the data; and

compute one or more storage unit identifiers for the data, each of the one or more storage unit identifiers uniquely identifying content of a storage unit; and

a plurality of block servers wherein block servers are associated with different ranges of storage unit identifiers and store information on where a storage unit is stored on a block server for a storage unit identifier, wherein each block server is configured to;

receive a storage unit in the one or more storage units if a storage unit identifier corresponds to the range of storage unit identifiers associated with the block server; and

service the request using the received storage unit identifier,

wherein multiple client addresses associated with a storage unit with a same storage unit identifier are mapped to a single storage unit stored in a storage medium in a block server.

21. The system of claim 20, further comprising:

a plurality of metadata servers; and

a redirector server, wherein the access request is received and redirected to one of the plurality of metadata servers configured to handle the access request.

22. The system of claim 21, wherein one of the plurality of metadata servers comprises a plurality of slice servers, wherein each slice server manages a range of mappings between client addresses and storage unit identifiers for the metadata server.

23. The system of claim 20, further comprising a plurality of clients, wherein multiple client addresses for access requests from the plurality of clients reference a storage unit stored in a block server with a same storage unit identifier.

24. The system of claim 20, wherein:

the data includes a plurality of storage units associated with the client address, and

the plurality of storage units are stored in a non-contiguous address space on a plurality of block servers.

25. The system of claim 24, wherein the plurality of block servers store storage units associated with different ranges of storage unit identifiers.