Read-modify-write processing of chunks at the storage server level in a distributed object storage system

• US 9,747,319 B2
• Filed: 08/08/2015
• Issued: 08/29/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,698
• Publication Number:
  US 20160191250A1
• Time in Patent Office: 752 Days
• Field of Search: 713168
• 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 provides systems and methods for sharding objects stored in a distributed storage system. Such sharding may be advantageously utilized for an object that stores a collection of key-value records and for otherwise encoded objects. The object sharding techniques disclosed herein advantageously enable a read-modify-write process at the storage server level. One embodiment disclosed herein provides a method of creating a new chunk by modifying a payload of an existing chunk at the storage server level in a distributed object storage system. The method includes validating the new chunk at the gateway server. Other embodiments, aspects and features are also disclosed.

Claims

1. A method of creating a new chunk by modifying a payload of an existing chunk of a named object in a distributed object storage system, the method comprising:

sending a rendezvous transfer from a gateway server to storage servers in a rendezvous group, wherein the rendezvous transfer specifies a change to the payload of the existing chunk, wherein the rendezvous group is a subset of the storage servers in a negotiating group for the existing chunk, and wherein the storage servers in the negotiating group are selected using a name hash identifying token that is generated by applying a predetermined hashing algorithm to the named object;

reading the payload of the existing chunk from a storage device by each of the storage servers in the rendezvous group;

modifying the payload of the existing chunk by applying the specified change to create a new payload by each of the storage servers in the rendezvous group;

applying a cryptographic hash to the new payload to generate a new content hash identifying token by each of the storage servers in the rendezvous group;

writing the new chunk to the storage device by each of the storage servers in the rendezvous group, wherein the new chunk includes the new payload and the new content hash identifying token; and

validating the new chunk by the gateway server,

wherein a payload of the named object is stored in existing chunks which are 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.

2. The method of claim 1, wherein the gateway server cryptographically validates the new chunk without needing to create a memory image of the new chunk.

3. The method of claim 1, further comprising:

sending new content hash identifying tokens from the storage servers in the rendezvous group to the gateway server; and

determining, by the gateway server, whether the new content hash identifying tokens match with each other.

4. The method of claim 3, further comprising:

determining that the new chunk was successfully stored if the new content hash identifying tokens match with each other; and

determining that an error occurred in storing the new chunk if at least one of the new content hash identifying tokens does not match with the others.

5. The method of claim 1,

wherein a payload of a version of the named object is stored in block shards defined by block-shard chunk references, wherein chunks referenced by the block-shard chunk references store non-overlapping byte ranges of the payload of the named object.

6. The method of claim 5, further comprising:

receiving, by the gateway server from a client, a request for a set of delta edits to be applied to the named object, wherein each delta edit specifies a change to the payload for the named object.

7. The method of claim 6, further comprising:

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

updating, by the storage servers, the relevant block shards, while not updating other block shards for the named object.

8. The method of claim 1, further comprising:

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.

9. The method of claim 8, further comprising:

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

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

10. A distributed storage system that stores a payload of a named object in chunks, the system comprising:

a plurality of storage servers; and

a plurality of gateway servers communicatively interconnected with, and providing access to, the plurality of storage servers,

wherein a procedure for creating a new chunk by modifying a payload of an existing chunk comprises;

sending a rendezvous transfer from a gateway server to the storage servers in a rendezvous group, wherein the rendezvous transfer specifies a change to the payload of the existing chunk, wherein the rendezvous group is a subset of the storage servers in a negotiating group for the existing chunk, and wherein the storage servers in the negotiating group are selected using a name hash identifying that is generated by applying a predetermined hashing algorithm to the named object;

reading the payload of the existing chunk from a storage device by each of the storage servers in the rendezvous group;

modifying the payload of the existing chunk by applying the specified change to create a new payload by each of the storage servers in the rendezvous group;

applying a cryptographic hash to the new payload to generate a new content hash identifying token by each of the storage servers in the rendezvous group;

writing the new chunk to the storage device by each of the storage servers in the rendezvous group, wherein the new chunk includes the new payload and the new content hash identifying token; and

validating the new chunk by the gateway server, and

wherein a payload of the named object is stored in existing chunks which are key shards that are defined by key-shard chunk references, wherein the payload for the named object comprises a collection of key-value records, wherein referenced chunks identified by the key shards each stores a subset of the collection of the key-value records, and wherein the key-value records in the subset have key hashes that have a range of matching bits in common.

11. The system of claim 10, wherein the gateway server cryptographically validates the new chunk without needing to create a memory image of the new chunk.

12. The system of claim 10, wherein the procedure for creating the new chunk by modifying the payload of the existing chunk comprises further comprises:

sending new content hash identifying tokens from the storage servers in the rendezvous group to the gateway server; and

determining, by the gateway server, whether the new content hash identifying tokens match with each other.

13. The system of claim 12, wherein the procedure for creating the new chunk by modifying the payload of the existing chunk comprises further comprises:

determining that the new chunk was successfully stored if the new content hash identifying tokens match with each other; and

determining that an error occurred in storing the new chunk if at least one of the new content hash identifying tokens does not match with the others.

14. The system of claim 10, wherein a payload of the named object is stored in existing chunks which are block shards defined by block-shard chunk references, and wherein the block shards store non-overlapping byte ranges of the payload of the named object.

15. The system of claim 14, wherein the procedure for creating the new chunk by modifying the payload of the existing chunk comprises further comprises:

receiving, by the gateway server from a client, a request for a set of delta edits to be applied to the named object, wherein each delta edit specifies a change to the payload for the named object.

16. The system of claim 15, wherein the procedure for creating the new chunk by modifying the payload of the existing chunk comprises further comprises:

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

updating, by the storage servers, the relevant block shards, while not updating other block shards for the named object.

17. The system of claim 10, wherein the procedure for creating the new chunk by modifying the payload of the existing chunk comprises further comprises:

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.

18. The system of claim 17, wherein the procedure for creating the new chunk by modifying the payload of the existing chunk comprises further comprises:

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

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

19. 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:

sending a rendezvous transfer from a gateway server to storage servers in a rendezvous group, wherein the rendezvous transfer specifies a change to the payload of the existing chunk, wherein the rendezvous group is a subset of the storage servers in a negotiating group for the existing chunk, and wherein the storage servers in the negotiating group are selected using a name hash identifying token that is generated by applying a predetermined hashing algorithm to the named object;

reading the payload of the existing chunk from a storage device by each of the storage servers in the rendezvous group;

modifying the payload of the existing chunk by applying the specified change to create a new payload by each of the storage servers in the rendezvous group;

applying a cryptographic hash to the new payload to generate a new content hash identifying token by each of the storage servers in the rendezvous group;

writing the new chunk to the storage device by each of the storage servers in the rendezvous group, wherein the new chunk includes the new payload and the new content hash identifying token; and

validating the new chunk by the gateway server,

wherein a payload of the named object is stored in existing chunks which are 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.

20. The non-transitory computer readable medium of claim 19, wherein the gateway server cryptographically validates the new chunk without needing to create a memory image of the new chunk.