Methods and systems for key sharding of objects stored in distributed storage system

• US 9,767,130 B2
• Filed: 08/08/2015
• Issued: 09/19/2017
• Est. Priority Date: 12/31/2014
• Status: Active Grant

• Current Assignee: Nexenta by DDN, Inc.
• Original Assignee: Nexenta Systems Incorporated (DataDirect Networks Incorporated)
• Inventors: Bestler, Caitlin, Novak, Robert E., Aizman, Alexander
• Primary Examiner(s): Okeke, Izunna
• Assistant Examiner(s): Zarrineh, Shahriar
• Application Number:
  US14/821,697
• Publication Number:
  US 20160191509A1
• Time in Patent Office: 773 Days
• Field of Search: 713163
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/2255 Hash tables
• 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/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• 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/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 63/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 63/0807 using tickets, e.g. Kerberos cryptographic mechanisms or cryptographic arrangements for entity authentication using tickets or tokens H04L9/3213
• CPC Class Codes: H04L 63/0853 using an additional device, e.g. smartcard, SIM or a different communication terminal cryptographic mechanisms or cryptographic arrangements for entity authentication involving additional secure or trusted devices H04L9/3234
• CPC Class Codes: H04L 63/0876 based on the identity of the terminal or configuration, e.g. MAC address, hardware or software configuration or device fingerprint
• 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]
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

The present disclosure also provides systems and methods for sharding objects stored in a distributed storage system. In accordance with one embodiment disclosed herein, a key sharding technique is used. Key sharding is an advantageously efficient technique when dealing with an object containing a collection of key-value records. In accordance with an embodiment of the invention, referenced chunks identified by the key shards may each store a subset of the collection of the key-value records, and the key-value records in the subset have key hashes that have a range of matching bits in common. One embodiment disclosed herein provides a method of performing a delta edit of a named object stored in a distributed storage system in which a payload of the named object is stored in key shards. Other embodiments, aspects and features are also disclosed.

Claims

1. A method of performing a delta edit of a named object stored in a distributed storage system, the method comprising:

storing, in the distributed storage system, a payload of the named object in key shards that are defined by key-shard chunk references, wherein the payload for the named object comprises a collection of key-value records, and wherein referenced chunks identified by the key shards each stores a subset of the collection of the key-value records, where the key-value records in the subset have key hashes that have a range of matching bits in common;

receiving, by a gateway server, a request for a set of delta edits to be applied to the named object, wherein each delta edit specifies addition or deletion of at least one key-value record;

determining, by the gateway server, relevant key shards to which the delta edits apply; and

updating the relevant key shards, while not updating other key shards for the named object,

wherein updating the relevant key shards comprises;

obtaining a name hash identifying token for the named object;

generating a plurality of key hash identifying tokens corresponding to the plurality of key-value records;

determining negotiating groups for the relevant key shards using the name hash identifying token and the plurality of key hash identifying tokens;

multicasting, by the gateway server, put requests to the negotiating groups for the relevant key shards, wherein the multicast put request specifies a cryptographic hash of a referenced chunk that is to be used as a base for a new chunk to be created;

collecting, by the gateway server, responses from the negotiating groups;

selecting rendezvous groups based on the responses from the negotiating groups;

initiating rendezvous transfers to the rendezvous groups; and

each addressed target server in a rendezvous group applying a delta edit to a copy of the referenced chunk to create a new chunk and calculating a content hash identifying token for the new chunk.

2. The method of claim 1, wherein updating the relevant key shards further comprises:

collecting content hash identifying tokens for the new chunks from target servers in each rendezvous group; and

verifying that the content hash identifying tokens match for each rendezvous group.

3. The method of claim 2, wherein updating the relevant key shards further comprises:

updating the content hash identifying token for each key-shard chunk reference that defines a relevant key shard in a new version of the named object; and

putting the new version of the named object to the distributed storage system.

4. A distributed storage system, the system comprising:

a network;

a plurality of storage servers interconnected by the network; and

a plurality of storage servers interconnected by the network, wherein the plurality of storage servers includes a gateway server;

wherein the plurality of storage servers store a payload of the named object in key shards that are defined by key-shard chunk references,

wherein the payload for any version of the named object comprises a collection of key-value records,

wherein each key shard stores a subset of the collection of the key-value records in a referenced chunk, where the key-value records in the subset have key hashes that have a range of matching bits in common, and

wherein the system is configured to perform steps including;

receiving a delta-edit request for the named object, wherein the delta-edit request specifies changes to a plurality of key-value records of the payload of the named object;

determining relevant key shards to which the changes apply; and

updating the relevant key shards, while not updating other key shards for the named object,

wherein updating the relevant key shards comprises;

obtaining a name hash identifying token for the named object;

generating a plurality of key hash identifying tokens corresponding to the plurality of key-value records;

determining negotiating groups for the relevant key shards using the name hash identifying token and the plurality of key hash identifying tokens;

multicasting put requests to the negotiating groups for the relevant key shards, wherein the multicast put request specifies a cryptographic hash of a referenced chunk that is to be used as a base for a new chunk to be created;

collecting responses from the negotiating groups;

selecting rendezvous groups based on the responses from the negotiating groups;

initiating rendezvous transfers to the rendezvous groups; and

each addressed target server in a rendezvous group applying a delta edit to a copy of the referenced chunk to create a new chunk and calculating a content hash identifying token for the new chunk.

5. The distributed storage system of claim 4, wherein the changes include insertions of key-value records and/or deletions of key-value records.

6. The distributed storage system of claim 4, wherein the system is further configured to perform steps comprising:

receiving a retrieval request for the named object, wherein the retrieval request specifies a plurality of key-value records of the payload of the named object;

determining the key-shard chunk references that define the key shards that contain any of the plurality of key-value records; and

obtaining content from the relevant key shards, while not obtaining content from other key shards of the named object.

7. A non-transitory computer-readable medium comprising instructions stored thereon, that when executed by one or more processors at a plurality of servers within a distributed storage system, perform the steps of:

storing, in the distributed storage system, a payload of the named object in key shards that are defined by key-shard chunk references, wherein the payload for the named object comprises a collection of key-value records, and wherein referenced chunks identified by the key shards each stores a subset of the collection of the key-value records, where the key-value records in the subset have key hashes that have a range of matching bits in common;

receiving, by a gateway server, a request for a set of delta edits to be applied to the named object, wherein each delta edit specifies addition or deletion of at least one key-value record;

determining, by the gateway server, relevant key shards to which the delta edits apply; and

updating the relevant key shards, while not updating other key shards for the named object,

wherein updating the relevant key shards comprises;

obtaining a name hash identifying token for the named object;

generating a plurality of key hash identifying tokens corresponding to the plurality of key-value records;

determining negotiating groups for the relevant key shards using the name hash identifying token and the plurality of key hash identifying tokens;

multicasting, by the gateway server, put requests to the negotiating groups for the relevant key shards, wherein the multicast put request specifies a cryptographic hash of a referenced chunk that is to be used as a base for a new chunk to be created;

collecting, by the gateway server, responses from the negotiating groups;

selecting rendezvous groups based on the responses from the negotiating groups;

initiating rendezvous transfers to the rendezvous groups; and

each addressed target server in a rendezvous group applying a delta edit to a copy of the referenced chunk to create a new chunk and calculating a content hash identifying token for the new chunk.

8. The non-transitory computer-readable medium of claim 7, wherein updating the relevant key shards further comprises:

collecting content hash identifying tokens for the new chunks from target servers in each rendezvous group; and

verifying that the content hash identifying tokens match for each rendezvous group.

9. The non-transitory computer-readable medium of claim 8, wherein updating the relevant key shards further comprises:

updating the content hash identifying token for each key-shard chunk reference that defines a relevant key shard in a new version of the named object; and

putting the new version of the named object to the distributed storage system.