Methods and Systems for Key Sharding of Objects Stored in Distributed Storage System

• US 20160191509A1
• Filed: 08/08/2015
• Published: 06/30/2016
• 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
• Granted Patent: US 9,767,130 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 an addition or a deletion of a 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.

2. The method of claim 1 further comprising:

obtaining, by the gateway server, a current object version for the named object, wherein the current object version includes key-shard chunk references for a latest version of the named object.

3. The method of claim 2, wherein the current object version is obtained by sending a request including a name of the named object to a negotiating group for version manifests.

4. The method of claim 1, 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; and

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

5. The method of claim 4, wherein a key-value record comprises a key and an associated value, and wherein a key hash identifying token for the key-value record is obtained by applying a hash algorithm to the key.

6. The method of claim 4, wherein updating the relevant key shards comprises:

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; and

initiating rendezvous transfers to the rendezvous groups.

7. The method of claim 6, wherein updating the relevant key shards further comprises:

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

10. A method of retrieving a portion of a named object stored in a distributed object storage system, the method comprising:

storing, in the distributed storage system, a payload of the named object in key shards 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 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, by the gateway server, relevant key shards that need to be obtained in order to fulfill the retrieval request; and

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

11. The method of claim 10, further comprising:

obtaining, by the gateway server, a current object version for the named object, wherein the current object version includes the key-shard chunk references for a latest version of the named object.

12. The method of claim 11, wherein the current object version is obtained by sending a request including a name of the named object to a negotiating group for version manifests.

13. The method of claim 10, further comprising:

determining negotiating groups for the relevant key shards; and

multicasting unnamed chunk search requests to the negotiating groups.

14. The method of claim 13, further comprising:

selecting a rendezvous group of select storage servers in each negotiating group; and

performing a rendezvous transfer from the selected storage servers in the rendezvous group to the gateway server.

15. The method of claim 13, wherein each key-shard chunk reference comprises:

a base key hash identifying token;

a match length; and

a content hash identifying token for a referenced chunk.

16. The method of claim 15, wherein determining a negotiating group for a relevant key shard comprises:

generating a key hash identifying token by applying a hash algorithm to a partition of a key of the key-value record;

adding the key hash identifying token to a name hash identifying token to generate a hash sum; and

using the hash sum to determine the negotiating group for the relevant key shard.

17. 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 include 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, and

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.

18. The distributed storage system of claim 17, wherein a putget broker performs steps comprising:

receiving, by the gateway server, 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, by the gateway server, relevant key shards to which the changes apply; and

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

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

20. The distributed storage system of claim 18, wherein the gateway server performs steps comprising:

receiving, by the gateway server, 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, by the gateway server, 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.