Writing data in a distributed data storage system

• US 9,383,933 B2
• Filed: 08/07/2014
• Issued: 07/05/2016
• Est. Priority Date: 03/05/2010
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Wright, David D.
• Primary Examiner(s): Fan, Hua
• Application Number:
  US14/454,197
• Publication Number:
  US 20140351363A1
• Time in Patent Office: 698 Days
• Field of Search: 709/223
• US Class Current: 1/1
• 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

Methods, systems, and apparatuses, including computer programs encoded on computer-readable media, for receiving a write request that includes data and a client address at which to store the data. The data is segmented into the one or more storage units. A storage unit identifier for each of the one or more storage units is computed that uniquely identifies content of a storage unit. A mapping between each storage unit identifier to a block server is determined. For each of the one or more storage units, the storage unit and the corresponding storage unit identifier is sent to a block server. The block server stores the storage unit and information on where the storage unit is stored on the block server for the storage unit identifier. Multiple client addresses associated with a storage unit with the same storage unit identifier are mapped to a single storage unit.

Claims

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

receiving a write request, the write request including client data and a client address, wherein the client address identifies the client data;

segmenting the client data into the one or more storage units;

computing a storage unit identifier for each of the one or more storage units, wherein the storage unit identifier for each of the one or more storage units uniquely identifies content of a storage unit associated with the storage unit identifier;

determining, by a metadata server, a mapping between each storage unit identifier to a block server; and

for each of the one or more storage units, sending the storage unit and the corresponding storage unit identifier to a block server based upon the mapping between the storage unit identifier to the block server, wherein the block server stores the storage unit and maps the storage unit identifier to where the storage unit is stored on the block server, wherein a storage unit that is associated with multiple client addresses is mapped to a single storage unit and stored on a block server one time, wherein the storage unit is not stored multiple times on a single storage medium on the block server, determining a plurality of storage unit identifiers associated with client data;

for each of the plurality of storage unit identifiers;

determining if the storage unit identifier is present in a Bloom filter; and

adding the storage unit identifier to the Bloom filter based upon the determining the storage unit identifier is not present in the Bloom filter; and

calculating an amount of space used by the client data based upon the Bloom filter.

2. The method of claim 1, wherein the block server determines if the storage unit identifier already exists on the block server, wherein 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 wherein the block server stores the storage unit if the storage unit identifier does not exist on the block server.

3. The method of claim 1, further comprising:

determining a number of unique storage unit identifiers associated with client data; and

calculating an amount of space used by the client data based upon the number of unique storage units identifiers.

4. The method of claim 1, wherein computing a storage unit identifier for each of the one or more storage units comprises computing a hash of content for a respective storage unit.

5. The method of claim 1, further comprising:

for each of the one or more storage units, sending the storage unit and the corresponding storage unit identifier to a second block server to redundantly store the storage unit and the corresponding storage unit identifier on multiple block servers.

6. 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.

7. A non-transitory computer-readable storage medium containing instructions for writing data, the data including one or more storage units, the instructions for controlling a computer system to perform operations comprising:

receiving a write request, the write request including client data and a client address, wherein the client address identifies the client data;

segmenting the client data into the one or more storage units;

computing a storage unit identifier for each of the one or more storage units, wherein the storage unit identifier for each of the one or more storage units uniquely identifies content of a storage unit associated with the storage unit identifier;

determining, by a metadata server, a mapping between each storage unit identifier to a block server; and

for each of the one or more storage units, sending the storage unit and the corresponding storage unit identifier to a block server based upon the mapping between the storage unit identifier to the block server, wherein the block server stores the storage unit and maps the storage unit identifier to where the storage unit is stored on the block server, wherein a storage unit that is associated with multiple client addresses is mapped to a single storage unit and stored on a block server one time, wherein the storage unit is not stored multiple times on a single storage medium on the block server, determining a plurality of storage unit identifiers associated with client data;

for each of the plurality of storage unit identifiers;

determining if the storage unit identifier is present in a Bloom filter; and

adding the storage unit identifier to the Bloom filter based upon the determining the storage unit identifier is not present in the Bloom filter; and

calculating an amount of space used by the client data based upon the Bloom filter.

8. The non-transitory computer-readable storage medium of claim 7, wherein the block server determines if the storage unit identifier already exists on the block server, wherein 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 wherein the block server stores the storage unit if the storage unit identifier does not exist on the block server.

9. The non-transitory computer-readable storage medium of claim 8, wherein the operations further comprise:

determining a number of unique storage unit identifiers associated with client data; and

calculating an amount of space used by the client data based upon the number of unique storage units identifiers.

10. The non-transitory computer-readable storage medium of claim 7, wherein computing a storage unit identifier for each of the one or more storage units comprises computing a hash of content for a respective storage unit.

11. The non-transitory computer-readable storage medium of claim 7, wherein the operations further comprise:

for each of the one or more storage units, sending the storage unit and the corresponding storage unit identifier to a second block server to redundantly store the storage unit and the corresponding storage unit identifier on multiple block servers.

12. The non-transitory computer-readable storage medium of claim 7, wherein the operations further comprise 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. A system comprising:

a metadata server configured to;

receive a write request, the write request including client data and a client address, wherein the client address identifies the client data;

segment the client data into the one or more storage units;

compute a storage unit identifier for each of the one or more storage units, wherein the storage unit identifier for each of the one or more storage units uniquely identifies content of a storage unit associated with the storage unit identifier;

determine a mapping between each storage unit identifier to a block server;

for each of the one or more storage units, send the storage unit and the corresponding storage unit identifier to a block server based upon the mapping between the storage unit identifier to the block server, wherein the block server stores the storage unit and maps the storage unit identifier to where the storage unit is stored on the block server, wherein a storage unit that is associated with multiple client addresses is mapped to a single storage unit and stored on a block server one time, wherein the storage unit is not stored multiple times on a single storage medium on the block server, determining a plurality of storage unit identifiers associated with client data;

determine a plurality of storage unit identifiers associated with client data;

for each of the plurality of storage unit identifiers;

determine if the storage unit identifier is present in a Bloom filter; and

add the storage unit identifier to the Bloom filter based upon the determining the storage unit identifier is not present in the Bloom filter; and

calculate an amount of space used by the client data based upon the Bloom filter; and

store the mapping between each storage unit identifier to the block server.

14. The system of claim 13, wherein the block server determines if the storage unit identifier already exists on the block server, wherein the block server does not store the storage unit on the block server if the storage unit identifier already exists on the block server, wherein the block server stores the storage unit if the storage unit identifier does not exist on the block server.

15. The system of claim 14, wherein the metadata server is further configured to:

determine a number of unique storage unit identifiers associated with client data; and

calculate an amount of space used by the client data based upon the number of unique storage units identifiers.