1 of 13

DEX: Scalable Range Indexing on Disaggregated Memory

Baotong Lu1, Kaisong Huang2, Chieh-Jan Mike Liang1, Tianzheng Wang2, Eric Lo3

​

1 Microsoft Research Asia �2 Simon Fraser University�3 The Chinese University of Hong Kong

2 of 13

From Monolithic to Disaggregated

DEX: Scalable Range Indexing on Disaggregated Memory

2

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

…

Fast Interconnect (RDMA)

…

Memory Servers

Compute Servers

Monolithic Servers

Network

Advantages

​

  • High Resource Utilization
  • High Elasticity

3 of 13

First Step Towards A Disaggregated Tree Index

Opportunity: leverage local resources to reduce remote accesses

DEX: Scalable Range Indexing on Disaggregated Memory

3

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

RDMA Network

Compute Servers

Memory Servers

Caching tree nodes

Operation offloading

Latency: RDMA access (2μs) > Local DRAM access (100ns)

Traffic sources: index traversals, etc.

4 of 13

Challenge 1: Rudimentary Caching

​

​

​

​

​

​

​

​

DEX: Scalable Range Indexing on Disaggregated Memory

4

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

​

Disk/SSD-based Caching

Compute-server Caching for

Disaggregated Memory

“I/O” latency

100μs – 10ms

2--3μs

Replacements/second

​

​

18X Gap

LRU

Compute

DRAM Cache

DRAM Cache

. . .

. . .

Memory

Leaf Node

. . .

. . .

RDMA

Caching

. . .

High contention

5 of 13

Challenge 2: Unprincipled Offloading

Cost-aware offloading is imperative

    • What, when, and how much to offload

DEX: Scalable Range Indexing on Disaggregated Memory

5

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

Compute

DRAM Cache

Inner Node

. . .

. . .

Leaf Node

. . .

RDMA

DRAM Cache

Inner Node

. . .

. . .

Memory

. . .

Offload

Offload

  • Massive concurrent offloading from compute servers
    • Limited compute power in memory servers

6 of 13

Challenge 3: Excessive Inconsistency

    • Distributed synchronization across compute
    • Cache coherence across compute
    • Data consistency between caching

and offloading

​

​

DEX: Scalable Range Indexing on Disaggregated Memory

6

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

Compute

DRAM Cache

Inner Node

. . .

. . .

Leaf Node

. . .

2

RDMA

DRAM Cache

Inner Node

. . .

. . .

Memory

1

3

. . .

​

A distributed MESI coherence protocol is expensive

2

3

​

RDMA locking is unscalable [1]

1

[1] Design Guidelines for Correct, Efficient, and Scalable Synchronization using One-Sided RDMA (Sigmod 23)

1

7 of 13

DEX: Scalable Disaggregated Memory Index

DEX: Scalable Range Indexing on Disaggregated Memory

7

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

Compute

DRAM Cache

Inner Node

. . .

. . .

Leaf Node

. . .

RDMA

DRAM Cache

Inner Node

. . .

. . .

Memory

. . .

  • Rudimentary Caching
  • Unprincipled Offloading
  • Excessive Inconsistency
  • Logical Partitioning to Reduce Most Inconsistency
  • Scalable Compute-Side Caching
  • Opportunistic Offloading

8 of 13

Compute-Side Logical Partitioning

DEX: Scalable Range Indexing on Disaggregated Memory

8

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

​

Shared Everything

Consistency Overhead

Large

Load-balance

Easy

Logical Partitioning

Low

Low-cost repartition

RDMA

…

…

Key range: [0-X)

Key range: [Z, +∞)

Key range: [X, Y)

“Cache”

Compute

servers

Memory

servers

Globally accessible B+-treeree

Partition key ranges among compute servers

Low-cost repartition

  • Flush dirty caches
  • Repartition metadata

Physical Partitioning

Low

High-cost repartition

9 of 13

Scalable Compute-Side Caching

Randomized cooling policy [1]

    • Low-cost hotness tracking
    • Unscalable for fast replacements

​

  • Hash table to rank cooling pages
    • Simple but effectively scalable

​

​

​

​

​

DEX: Scalable Range Indexing on Disaggregated Memory

9

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

… , key, …

N4, …

…, ptr, N9…

… , key, …

N1, …

…, ptr, N8,…

… , key, …

N6, …

…, value …

… , key, …

N8,

…, ptr, …

Cooling

FIFO

…

Bucket 0

Head

Tail

Bucket N

Cooling Map

… , key, …

N9,

…, value, …

Cooling

Cache

[1] LeanStore: In-Memory Data Management Beyond Main Memory(ICDE 18)

… , key, …

N9, …

…, value …

… , key, …

N8, …

…, ptr,…

FIFO

10 of 13

Opportunistic Offloading

DEX: Scalable Range Indexing on Disaggregated Memory

10

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

RDMA Network

Leaf Node

Compute

Servers

Memory

Servers

Leaf Node

 

Cache

miss

Offloading latency

One-sided RDMA latency

11 of 13

Evaluation Setup

Hardware Platform

    • Intel Xeon Gold 6242R CPUs
    • Four compute/memory servers
    • 100Gbps Mellanox ConnectX-5

YCSB Workloads

    • 200 million KV records

Competitors

    • Sherman: B+-Tree based [SIGMOD 22]
    • SMART: Radix-Tree based [OSDI 23]

​

DEX: Scalable Range Indexing on Disaggregated Memory

11

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

​

Compute Server

Memory Server

CPU cores

36 cores

4 cores

DRAM size

256MB – 1GB

64GB

12 of 13

Multi-thread Scalability Across Machines

DEX: Scalable Range Indexing on Disaggregated Memory

12

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

DEX: winner and near-linear scalability

SMART: unscalable due to unscalable cache replacements

Sherman: unscalable due to frequent RDMA-based locking

13 of 13

Summary

  • Designing range indexes on disaggregated memory is challenging due to excessive remote accesses
  • DEX: holistic design to effectively leverage local resources on disaggregated memory
    • Logical partitioning to reduce consistency overhead
    • Scalable compute-side caching
    • Cost-aware opportunistic offloading

​

​

​

DEX: Scalable Range Indexing on Disaggregated Memory

13

B. Lu, K. Huang, M. Liang, T. Wang, E. Lo

Open source at: https://github.com/baotonglu/dex

Thank you!

Contact me: baotonglu@microsoft.com