Compressed block map of densely-populated data structures

• US 9,582,198 B2
• Filed: 09/19/2013
• Issued: 02/28/2017
• Est. Priority Date: 08/26/2013
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Earl, William
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): Wang, Edward
• Application Number:
  US14/032,121
• Publication Number:
  US 20150058577A1
• Time in Patent Office: 1,258 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• 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/0688 Non-volatile semiconductor memory arrays

Abstract

Embodiments of the disclosure provide techniques for creating a compressed mapping structure in a system of resources. For example, a distributed resources system may use delta encoding to store, in memory, numerous entries of dense data structures in the system. In a compressed block of such entries, the distributed resources system encodes the key of each entry as the delta from the key of the previous entry. The content of each entry is encoded similarly. The distributed resources system suppresses the leading zero bits of each resulting field.

Claims

1. A method for storing key-value entries of a block map in a host computer system of a system of resources, the method comprising:

given a current entry having a current key having one or more fields and a current payload and a previous entry having a previous key and a previous payload, encoding each of the one or more fields in the current key as a first delta from a corresponding field in the previous key and encoding the current payload as a second delta from the previous payload;

removing leading zero bits in each resulting encoded field of the current key and leading zero bits in the encoded current payload; and

inserting the encoded one or more fields of the current key and the encoded current payload into a datastore residing in memory of the host computer system,

wherein the previous entry and the current entry are successive entries of the block map.

2. The method of claim 1, wherein the one or more fields corresponds to an object identifier, an offset, and a length, and wherein the current payload corresponds to block addresses of a solid state drive.

3. The method of claim 1, wherein the system of resources provides a software-defined virtual storage area network.

4. The method of claim 1, wherein the datastore maintains a cache of recently referenced entries.

5. The method of claim 1, wherein the current entry is addressed with an index block.

6. The method of claim 1, wherein the datastore is a logical block addressing table.

7. A non-transitory computer-readable storage medium storing instructions, which, when executed on a processor, performs an operation for storing key-value entries of a block map in a host computer system of a system of resources, the operation comprising:

given a current entry having a current key having one or more fields and a current payload and a previous entry having a previous key and a previous payload, encoding each of the one or more fields in the current key as a first delta from a corresponding field in the previous key and encoding the current payload as a second delta from the previous payload;

removing leading zero bits in each resulting encoded field of the current key and leading zero bits in the encoded current payload; and

inserting the encoded one or more fields of the current key and the encoded current payload into a datastore residing in memory of the host computer system,

wherein the previous entry and the current entry are successive entries of the block map.

8. The computer-readable storage medium of claim 7, wherein the one or more fields corresponds to an object identifier, an offset, and a length, and wherein the current payload corresponds to block addresses of a solid state drive.

9. The computer-readable storage medium of claim 7, wherein the system of resources provides a software-defined virtual storage area network.

10. The computer-readable storage medium of claim 7, wherein the datastore maintains a cache of recently referenced entries.

11. The computer-readable storage medium of claim 7, wherein the current entry is addressed with an index block.

12. The computer-readable storage medium of claim 7, wherein the datastore is a logical block addressing table.

13. A system, comprising:

a processor and

a memory hosting a module, which, when executed on the processor, performs an operation for storing key-value entries of a block map in a host computer system of a system of resources, the operation comprising;

given a current entry having a current key having one or more fields and a current payload and a previous entry having a previous key and a previous payload, encoding each of the one or more fields in the current key as a first delta from a corresponding field in the previous key and encoding the current payload as a second delta from the previous payload;

removing leading zero bits in each resulting encoded field of the current key and leading zero bits in the encoded current payload; and

inserting the encoded one or more fields of the current key and the encoded current payload into a datastore residing in memory of the host computer system,

wherein the previous entry and the current entry are successive entries of the block map.

14. The system of claim 13, wherein the one or more fields corresponds to an object identifier, an offset, and a length, and wherein the current payload corresponds to block addresses of a solid state drive.

15. The system of claim 13, wherein the system of resources provides a software-defined virtual storage area network.

16. The system of claim 13, wherein the datastore maintains a cache of recently referenced entries.

17. The system of claim 13, wherein the current entry is addressed with an index block.