Methods and systems for key-value-tuple-encoded storage

• US 10,185,730 B2
• Filed: 08/08/2015
• Issued: 01/22/2019
• 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): Perveen, Rehana
• Assistant Examiner(s): Onat, Alp
• Application Number:
  US14/821,693
• Publication Number:
  US 20160188591A1
• Time in Patent Office: 1,263 Days
• 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 Key-Value-Tuple-encoded (KVT-encoded) object storage. In accordance with an embodiment of the invention, chunks of objects, storing payload data or metadata, are persistently stored by servers using KVT-encoded storage. Furthermore, the KVT encoding may be applied to advantageously re-structure content within a distributed object storage cluster, especially for object storage systems that allow payload references to be cached extensively. For such systems, it is of considerable value to honor (use as valid) existing chunk references after the underlying content has been re-structured. Further, the KVT encoding taught herein is completely compatible with a fully-distributed object storage cluster. One embodiment relates to a storage server that includes a persistent storage module that provides a key-value application programming interface that encodes multiple key-value-tuple (KVT) entries for one chunk. Other embodiments, aspects and features are also disclosed.

Claims

1. A storage server for a distributed object storage system that stores an object in chunks, the storage server comprising:

a storage server packet processing module that processes requests to put the chunks to, and get the chunks from, the storage server;

a persistent storage module that provides a key-value application programming interface that encodes multiple key-value-tuple (KVT) entries for one chunk; and

a plurality of persistent storage devices for storing the chunks and the multiple KVT entries,

wherein the multiple KVT entries for said one chunk includes a first KVT entry that comprises an index key and an index value, wherein the index key comprises a first storage device key and a first chunk slice type, and wherein the index value comprises a content hash identifying token (CHIT) of a content of said one chunk and an error detection code, and

wherein the multiple KVT entries for said one chunk further includes a second KVT entry that comprises a key and a value, wherein the key comprises a second storage device key and a second chunk slice type.

2. The storage server of claim 1, wherein the multiple KVT entries are persistently stored in that updating any of the multiple KVT entries about the chunk leaves the chunk itself unaltered.

3. The storage server of claim 1, wherein the multiple KVT entries includes a KVT entry for back-reference tracking data.

4. The storage server of claim 1, wherein the multiple KVT entries includes a KVT entry for access history data.

5. The storage server of claim 1,

wherein the content of said one chunk comprises manifest contents, the second storage device key comprises the CHIT of the content, the second chunk slice type comprises a version-manifest type, and the CHIT of the content comprises a CHIT of the manifest contents, and

wherein the first storage device key comprises a name hash identifying token (NHIT) and the first chunk slice type comprises a name index type.

6. The storage server of claim 1,

wherein the content of said one chunk comprises back-references content, the second storage device key comprises the CHIT of the content, the second chunk slice type comprises a back-reference type, and the CHIT of the content comprises a CHIT of the back-references content, and

wherein the first storage device key comprises a CHIT of payload content of a chunk which is associated with the back-references content, and the first chunk slice type comprises a back-reference index type.

7. A method of storing chunks of objects by a storage server in a distributed object storage system, the method comprising:

processing, by a storage server packet processing module, requests to put the chunks to, and get the chunks from, the storage server;

providing, by a persistent storage module, a key-value application programming interface that encodes multiple key-value-tuple (KVT) entries for one chunk; and

storing the chunks and the multiple KVT entries in a plurality of persistent storage devices,

wherein the multiple KVT entries for said one chunk includes a first KVT entry that comprises an index key and an index value, wherein the index key comprises a first storage device key and a first chunk slice type, and wherein the index value comprises a content hash identifying token (CHIT) of a content of said one chunk and an error detection code, and

wherein the multiple KVT entries for said one chunk further includes a second KVT entry that comprises a key and a value, wherein the key comprises a second storage device key and a second chunk slice type.

8. The method of claim 7, wherein the multiple KVT entries are persistently stored in that updating any of the multiple KVT entries about the chunk leaves the chunk itself unaltered.

9. The method of claim 7, wherein the multiple KVT entries includes a KVT entry for back-reference tracking data.

10. The method of claim 7, wherein the multiple KVT entries includes a KVT entry for access history data.

11. The method of claim 7,

wherein the content of one said chunk comprises manifest contents, the second storage device key comprises the CHIT of the content, the second chunk slice type comprises a version-manifest type, and the CHIT of the content comprises a CHIT of the manifest contents, and

wherein the first storage device key comprises a name hash identifying token (NHIT) and the first chunk slice type comprises a name index type.

12. The method of claim 7,

wherein the content of said one chunk comprises back-references content, the second storage device key comprises the CHIT of the content, the second chunk slice type comprises a back-reference type, and the CHIT of the content comprises a CHIT of the back-references content, and

wherein the first storage device key comprises a CHIT of payload content of a chunk which is associated with the back-references content, and the first chunk slice type comprises a back-reference index type.