Low latency RDMA-based distributed storage

• US 10,375,167 B2
• Filed: 11/20/2015
• Issued: 08/06/2019
• Est. Priority Date: 11/20/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Shamis, Alexander, Suzue, Yutaka, Risvik, Knut Magne
• Primary Examiner(s): Vu, Viet D
• Application Number:
  US14/947,473
• Publication Number:
  US 20170149890A1
• Time in Patent Office: 1,355 Days
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• 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]

Abstract

A “Distributed Storage Controller” applies an RDMA-based memory allocator to implement a distributed thread-safe and lock-free storage system in shared memory distributed across multiple networked computers. The Distributed Storage Controller enables any number of client applications, processes, subroutines, etc., on any number of networked computers to concurrently perform self-directed lock-free allocations, de-allocations, reads, writes, etc., on the shared memory via sequences of one-way RDMA messages (e.g., RDMA reads, RDMA writes, and RDMA atomic compare and swap (CAS) operations) without requiring CPU locks. As such, the CPUs of computing devices hosting the shared memory do not need to be notified of RDMA-based reads, writes or CAS operations on that memory. Consequently, CPU utilization for computing devices hosting any portion of the shared memory is minimal, thereby enabling the Distributed Storage Controller to scale to very large numbers of concurrent accesses by very large numbers of networked computing devices.

Claims

1. A distributed storage system, comprising:

a plurality of networked computing devices in communication via RDMA-enabled NICs;

distribution tables and metadata hosted on one or more of the networked computing devices;

a plurality of memory regions allocated across two or more of the networked computing devices;

a separate instance of an RDMA-based messaging module hosted on each of a plurality of the networked computing devices;

a separate instance of an RDMA-based memory allocator module hosted on each of a plurality of the networked computing devices, each RDMA-based memory allocator module configured to perform allocations and de-allocations of shared memory on any of the networked computing devices; and

applying the RDMA-based memory allocator module of one or more of the networked computing devices and the RDMA-based messaging module of one or more of the networked computing devices in combination with the distribution tables and metadata to concurrently perform any combination of RDMA-based lock-free memory operations on one or more of the plurality of memory regions.

2. The system of claim 1 wherein the lock-free memory operations further comprise any combination of lock-free memory allocations, lock-free memory de-allocations, lock-free memory reads and lock-free memory writes on the distributed storage.

3. The system of claim 2 wherein the lock-free memory allocations further comprise:

applying an instance of the RDMA-based memory allocator module to allocate one or more of the memory regions on one or more of the networked computing devices via a sequence of RDMA messages;

applying an instance of the RDMA-based memory allocator module to allocate one or more memory blocks from one or more of the memory regions via a sequence of RDMA messages; and

applying an instance of the RDMA-based memory allocator module to allocate one or more memory slabs from one or more of the memory blocks via a sequence of RDMA messages.

4. The system of claim 3 wherein each allocated memory region further comprises a metadata section comprising block headers and a free slab map.

5. The system of claim 3 wherein each memory slab further comprises a slab metadata section including a slab checksum value computed from data held in a plurality of memory elements of the memory slab.

6. The system of claim 2 wherein the lock-free memory writes further comprise:

reserving a particular memory slab allocated from a corresponding memory region by performing an RDMA-based CAS operation to flip a bit of a corresponding entry in a memory reservation bitmap; and

performing an RDMA-based write to the reserved memory slab.

7. The system of claim 2 wherein the lock-free memory reads further comprise performing an RDMA-based read operation on a particular memory slab of a particular memory region.

8. The system of claim 1 further comprising:

a separate instance of a co-processor module hosted on one or more of the networked computing devices;

the co-processor module providing an interface for arbitrary client applications to the distributed storage via an instance of the RDMA-based memory allocator module and an instance of the RDMA-based messaging module.

9. The system of claim 8 further comprising applying the co-processor module to provide a B-Tree based key-value store in the distributed storage.

10. The system of claim 1 wherein any of the networked computing devices concurrently acts as any or all of a controller node for hosting the distribution tables and metadata of the distributed storage, a storage node for hosting a plurality of the memory regions of the distributed storage, and a client node for performing any combination of lock-free memory operations on the distributed storage.

11. A computer-implemented process, comprising:

a shared memory comprising a plurality of memory regions allocated on two or more networked computing devices in communication via RDMA-enabled NICs;

a separate instance of an RDMA-based memory allocator module hosted on each of a plurality of the networked computing devices, each RDMA-based memory allocator module configured to perform allocations and de-allocations of shared memory on any of the networked computing devices;

each memory region being allocated by an instance of the RDMA-based memory allocator module hosted on one or more of the networked computing devices;

one or more memory blocks being allocated from each memory region by an instance of the RDMA-based memory allocator module hosted on one or more of the networked computing devices;

one or more memory slabs being allocated from each memory block by an instance of the RDMA-based memory allocator module hosted on one or more of the networked computing devices;

applying one or more of the networked computing devices to host distribution tables and metadata delimiting parameters comprising references to the memory regions, memory blocks and memory slabs of the shared memory; and

applying an instance of the RDMA-based messaging module hosted on one or more of the networked computing devices in combination with the distribution tables and metadata to concurrently perform any combination of RDMA-based lock-free reads and writes on one or more of the memory slabs.

12. The computer-implemented process of claim 11 wherein each RDMA-based lock-free write further comprises:

applying an RDMA CAS operation on a corresponding entry in a memory slab reservation bitmap to reserve the particular memory slab;

applying an RDMA write operation on the particular memory slab following the reservation; and

applying an RDMA CAS operation on the corresponding entry in the reservation bitmap to release the reservation of the particular node following the RDMA write.

13. The computer-implemented process of claim 11 wherein each memory slab further comprises a metadata section comprising a checksum value computed from a combination of the data in each memory element of that memory slab.

14. The computer-implemented process of claim 13 wherein each RDMA-based lock-free read further comprises:

applying an RDMA read operation to read a particular memory slab;

computing a checksum from a combination of the data in each memory element of that memory slab;

comparing the computed checksum to the checksum in the metadata section of the memory slab; and

repeating the read of the memory slab and computation of the checksum until the computed checksum value matches the checksum value in the metadata of the memory slab.

15. The computer-implemented process of claim 11 further comprising:

hosting a separate instance of a co-processor module on one or more of the networked computing devices; and

applying the co-processor module to provide an interface for arbitrary client applications to the shared memory via an instance of the RDMA-based memory allocator module and an instance of the RDMA-based messaging module.

16. The computer-implemented process of claim 11 wherein any of the networked computing devices concurrently acts as any or all of a controller node for hosting the distribution tables and metadata of the shared memory, a storage node for hosting a plurality of the memory regions of the shared memory, and a client node for performing any combination of lock-free memory operations on the shared memory.

17. A computer-readable storage device having computer executable instructions stored therein, said instructions causing a computing device to execute a method comprising:

applying an instance of an RDMA-based memory allocator to allocate a shared memory comprising memory slabs allocated from memory blocks allocated from memory regions hosted by a plurality of networked computing devices in communication via RDMA-enabled NICs, each of the plurality of networked computing devices hosting a separate instance of the RDMA-based memory allocator configured to perform allocations and de-allocations of shared memory on any of the networked computing devices;

each memory slab of the shared memory further comprising a plurality of memory elements and a metadata checksum value computed from each of the memory elements of that memory slab;

applying any of a plurality of the networked computing devices to perform concurrent self-directed lock-free RDMA reads of particular memory slabs of the shared memory;

applying any of a plurality of the networked computing devices to perform concurrent self-directed lock-free RDMA writes to a particular memory slabs of the shared memory following application of an RDMA CAS operation on a corresponding entry in a memory slab reservation bitmap to reserve the particular memory slab; and

applying an RDMA CAS operation on the corresponding entry in the reservation bitmap to release the reservation of the particular memory slab following completion of the RDMA write.

18. The computer-readable storage device of claim 17 wherein any concurrent self-directed RDMA read of any memory slab further comprises:

applying an RDMA read operation to read a particular memory slab;

computing a checksum from a combination of the data in each memory element of that memory slab;

comparing the computed checksum to the metadata checksum value of the memory slab; and

repeating the read of the memory slab and computation of the checksum until the computed checksum value matches the metadata checksum value.

19. The computer-readable storage device of claim 17 further comprising:

hosting a separate instance of a co-processor module on one or more of the networked computing devices; and

applying the co-processor module to provide an interface for arbitrary client applications to the shared memory via an instance of the RDMA-based memory allocator module and an instance of an RDMA-based messaging module hosted on one or more of the networked computing devices.

20. The computer-readable storage device of claim 17 wherein any of the networked computing devices concurrently acts as any or all of a controller node for hosting distribution tables and metadata of the shared memory, a storage node for hosting a plurality of the memory regions of the shared memory, and a client node for performing any combination of lock-free memory operations on the shared memory.