1 of 63

Building an Efficient Key-Value Store in a Flexible Address Space

Chen Chen1, Wenshao Zhong1, Xingbo Wu2

1 University of Illinois at Chicago

2 Microsoft Research Cambridge

1

2 of 63

KV Stores

  • The backbone of widely used Internet-based services

2

3 of 63

KV Stores

  • The backbone of widely used Internet-based services
  • Simple interface
    • db.put(“foo”, “abcd”)
    • db.put(“bar”, 0xbee)
    • db.put(“cat”, 2022)
    • db.get(“cat”) => 2022
    • db.scan(“c”, 2) => {“cat”: 2022, “foo”: “abcd”}

3

Point Query

Range Query

Write

4 of 63

KV Stores

  • The backbone of widely used Internet-based services
  • Simple interface
    • db.put(“foo”, “abcd”)
    • db.put(“bar”, 0xbee)
    • db.put(“cat”, 2022)
    • db.get(“cat”) => 2022
    • db.scan(“c”, 2) => {“cat”: 2022, “foo”: “abcd”}

​

  • Major KV stores manage sorted data for range queries

4

Point Query

Range Query

Write

5 of 63

Managing Sorted Data

  • Storing sorted data in structured files

5

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

6 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)

6

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

7 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)

7

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

art

18

8 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)

8

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

art

18

Rewrite the whole file

9 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • Common approach: append writes

9

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

art

18

10 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • Common approach: append writes + indirections

10

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

art

18

Indirection

Application

11 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • Common approach: append writes + indirections
      • Unordered file but sorted index for all keys

11

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

art

18

Indirection

Application

12 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • Common approach: append writes + indirections
      • Unordered file but sorted index for all keys

12

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

art

18

Indirection

Application

Maintaining large index

13 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • Common approach: append writes + indirections
      • Unordered file but sorted index for all keys
      • Indexing sorted leaf nodes (e.g., B+-Tree)

Log-structured sort-merge approach (e.g., LSM)

13

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

art

18

Indirection

Application

Maintaining large index

14 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • Common approach: append writes + indirections
      • Unordered file but sorted index for all keys
      • Indexing sorted leaf nodes (e.g., B+-Tree)

Log-structured sort-merge approach (e.g., LSM)

14

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

art

18

Indirection

Application

Maintaining large index

Repeated rewrites

15 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • Common approach: append writes + indirections
      • Unordered file but sorted index for all keys
      • Indexing sorted leaf nodes (e.g., B+-Tree)

Log-structured sort-merge approach (e.g., LSM)

15

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

art

18

Indirection

Application

Maintaining large index

Semantic gap:

Cannot insert data in-place

Repeated rewrites

16 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)

16

(Simplified) File

foo

abcd

bar

0xbee

cat

2022

Address Space

0

3

11

14

22

25

29

What if we can sort data here?

17 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • In-place updates by sorting in the address space

17

insert

shift

(Simplified) File

Address Space

art

18

bar

0xbee

foo

abcd

cat

2022

0

3

11

14

22

25

33

36

40

18 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • In-place updates by sorting in the address space

18

insert

shift

(Simplified) File

Address Space

art

18

bar

0xbee

foo

abcd

cat

2022

0

3

11

14

22

25

33

36

40

Straightforward

19 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • In-place updates by sorting in the address space
    • Existing effort: insert-range and collapse-range (ext4, XFS, F2FS …)

19

(Simplified) File

Address Space

art

18

bar

0xbee

foo

abcd

cat

2022

0

3

11

14

22

25

33

36

40

20 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • In-place updates by sorting in the address space
    • Existing effort: insert-range and collapse-range (ext4, XFS, F2FS …)
      • Inefficient shifting in extent indexes

20

(Simplified) File

Address Space

art

18

bar

0xbee

foo

abcd

cat

2022

0

3

11

14

22

25

33

36

40

Logical offset -> physical address

21 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • In-place updates by sorting in the address space
    • Existing effort: insert-range and collapse-range (ext4, XFS, F2FS …)
      • Inefficient shifting in extent indexes

21

Updating O(N) extents’ metadata

(Simplified) File

Address Space

art

18

bar

0xbee

foo

abcd

cat

2022

0

3

11

14

22

25

33

36

40

22 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • In-place updates by sorting in the address space
    • Existing effort: insert-range and collapse-range (ext4, XFS, F2FS …)
      • Inefficient shifting in extent indexes

22

(Simplified) File

Address Space

art

18

bar

0xbee

foo

abcd

cat

2022

0

3

11

14

22

25

33

36

40

3 orders of magnitude gap

23 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • In-place updates by sorting in the address space
    • Existing effort: insert-range and collapse-range (ext4, XFS, F2FS …)
      • Inefficient shifting in extent indexes
      • Rigid block alignment requirements

23

(Simplified) File

Address Space

art

18

bar

0xbee

foo

abcd

cat

2022

0

3

11

14

22

25

33

36

40

24 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • In-place updates by sorting in the address space
    • Existing effort: insert-range and collapse-range (ext4, XFS, F2FS …)
      • Inefficient shifting in extent indexes
      • Rigid block alignment requirements
      • Inability to track shifting data

24

(Simplified) File

Address Space

art

18

bar

0xbee

foo

abcd

cat

2022

0

3

11

14

22

25

33

36

40

The offsets can easily change

25 of 63

Managing Sorted Data

  • Storing sorted data in structured files
  • How to commit new data? e.g., db.put(“art”, 18)
    • In-place updates by sorting in the address space
    • Existing effort: insert-range and collapse-range (ext4, XFS, F2FS …)
      • Inefficient shifting in extent indexes
      • Rigid block alignment requirements
      • Inability to track shifting data

25

(Simplified) File

Address Space

art

18

bar

0xbee

foo

abcd

cat

2022

0

3

11

14

22

25

33

36

40

A more flexible storage abstraction to manage sorted data!

26 of 63

Our Idea: Flexible Address Space

  • Lightweight in-place insertions and deletions
    • Sorting data easily in the address space

26

27 of 63

Our Idea: Flexible Address Space

  • Lightweight in-place insertions and deletions
    • Sorting data easily in the address space
  • Challenges
    • Inefficient shifting in extent index
    • Rigid block alignment requirements
    • Inability to track shifting data

27

28 of 63

Our Idea: Flexible Address Space

  • Lightweight in-place insertions and deletions
    • Sorting data easily in the address space
  • Challenges => The Solution
    • Inefficient shifting in extent index => Index structure with efficient shifting
    • Rigid block alignment requirements => No alignment requirements
    • Inability to track shifting data => Managing shifting data

28

29 of 63

Our Idea: Flexible Address Space

  • Lightweight in-place insertions and deletions
    • Sorting data easily in the address space
  • The solution:

Managing shifting data

​

No alignment requirements

Index with efficient shifting

29

FlexDB

FlexSpace

FlexTree

Persistent

Address

Space

Application

30 of 63

Our Idea: Flexible Address Space

  • Lightweight in-place insertions and deletions
    • Sorting data easily in the address space
  • The solution:

Managing shifting data

​

No alignment requirements

Index with efficient shifting

30

FlexDB

FlexSpace

FlexTree

Persistent

Address

Space

Application

31 of 63

Starting from B+-Tree

  • When managing an address space using a B+-Tree

31

51

23

64

0

23

51

64

Keys are logical offsets

32 of 63

Starting from B+-Tree

  • When managing an address space using a B+-Tree

32

51

23

64

0

23

51

64

Keys are logical offsets

33 of 63

Starting from B+-Tree

  • When managing an address space using a B+-Tree

33

51

23

64

0

23

51

64

Insert a new extent (length = 10) at offset 0

Keys are logical offsets

34 of 63

Starting from B+-Tree

  • When managing an address space using a B+-Tree

34

51

23

64

23

51

64

Insert a new extent (length = 10) at offset 0

0

Insert

35 of 63

Starting from B+-Tree

  • When managing an address space using a B+-Tree

35

51

23

64

0

23

51

64

Insert a new extent (length = 10) at offset 0

0

+10

+10

+10

+10

+10

+10

+10

Shift

36 of 63

FlexTree: Structure

  • An index structure derived from B+-Tree
    • A new metadata representation scheme

36

51

23

64

0

23

51

64

37 of 63

FlexTree: Structure

  • An index structure derived from B+-Tree
    • A new metadata representation scheme

37

51

+0

+0

23

+0

+0

64

+0

+0

0

23

51

64

A shift value associated with a pointer

38 of 63

FlexTree: Structure

  • An index structure derived from B+-Tree
    • A new metadata representation scheme

38

51

+0

+0

23

+0

+0

64

+0

+0

0

23

51

64

23 + (+0) + (+0) = 23

Adding all the shift values on the path

A shift value associated with a pointer

39 of 63

FlexTree: Operations

  • An index structure derived from B+-Tree
    • A new metadata representation scheme

39

51

+0

+0

23

+0

+0

64

+0

+0

0

23

51

64

Insert a new extent (length = 10) at offset 0

40 of 63

FlexTree: Operations

  • An index structure derived from B+-Tree
    • A new metadata representation scheme

40

51

+0

+0

23

+0

+0

64

+0

+0

0

23

51

64

0

Insert

41 of 63

FlexTree: Operations

  • An index structure derived from B+-Tree
    • A new metadata representation scheme

41

51

+0

+0

23

+0

+0

64

+0

+0

0

23

51

64

0

Shift

+10

+10

+10

+10

+10

42 of 63

FlexTree: Operations

  • An index structure derived from B+-Tree
    • A new metadata representation scheme

42

61

+0

33

+0

64

+0

+0

0

23

51

64

10

Shift

+10

+10

Nodes on the path updated

-> O(logN) cost

​

Logical logging

43 of 63

FlexTree: Operations

  • An index structure derived from B+-Tree
    • A new metadata representation scheme

43

61

+0

33

+0

64

+0

+0

0

23

51

64

10

Shift

+10

+10

23 + (+10) + (+0) = 33

44 of 63

FlexTree: Operations

  • An index structure derived from B+-Tree
    • A new metadata representation scheme

44

61

+0

33

+0

64

+0

+0

0

23

51

64

10

Shift

+10

+10

51 + (+0) + (+10) = 61

search key = 61

search key = 51

search key = 51

45 of 63

Based on FlexTree

  • FlexSpace: Log-structured data storage indexed by FlexTree
    • Supporting read/write/insert-range operations etc.

​

  • FlexDB: Keeping all KV pairs sorted in a FlexSpace

45

46 of 63

FlexDB

  • Keeping all KV pairs sorted in a flexible address space

46

Flexible Address Space

Key Space

Device Address Space

FlexTree

Sparse Index

47 of 63

FlexDB: Sparse Index

  • Managing sorted keys in intervals

47

47

ink

FlexSpace

foo

abcd

bar

0xbee

cat

2022

Address Space

0

3

11

14

22

25

29

…

Interval 1

Interval 2

Interval 3

48 of 63

FlexDB: Sparse Index

  • Managing sorted keys in intervals
  • Indexing the first key (anchor) in each interval

48

48

ink

FlexSpace

foo

abcd

bar

0xbee

cat

2022

Address Space

0

3

11

14

22

25

29

foo

+0

+0

cat

0

11

ink

22

29

49 of 63

FlexDB: Sparse Index

  • Managing sorted keys in intervals
  • Indexing the first key (anchor) in each interval

49

49

ink

FlexSpace

foo

abcd

bar

0xbee

cat

2022

Address Space

0

3

11

14

22

25

29

foo

+0

+0

cat

0

11

ink

22

29

Inserting a new key “bot” into an interval

50 of 63

FlexDB: Sparse Index

  • Managing sorted keys in intervals
  • Indexing the first key (anchor) in each interval

50

50

FlexSpace

bar

0xbee

Address Space

0

3

11

14

22

25

33

foo

+0

cat

0

11

ink

22

29

Inserting a new key “bot” into an interval

ink

foo

abcd

cat

2022

bot

0xfff

36

40

+0

+11

+11

51 of 63

FlexDB: Sparse Index

  • Managing sorted keys in intervals
  • Indexing the first key (anchor) in each interval

51

51

FlexSpace

bar

0xbee

Address Space

0

3

11

14

22

25

33

foo

+0

cat

0

22

ink

22

29

Inserting a new key “bot” into an interval

ink

foo

abcd

cat

2022

bot

0xfff

36

40

+11

52 of 63

FlexDB: Sparse Index

  • Managing sorted keys in intervals
  • Indexing the first key (anchor) in each interval

52

52

FlexSpace

bar

0xbee

Address Space

0

3

11

14

22

25

33

foo

+0

cat

0

22

ink

22

29

ink

foo

abcd

cat

2022

bot

0xfff

36

40

+11

Elastic

In-memory

Easy recovery

53 of 63

FlexDB: Sparse Index

  • Managing sorted keys in intervals
  • Indexing the first key (anchor) in each interval

53

53

FlexSpace

bar

0xbee

Address Space

0

3

11

14

22

25

33

ink

foo

abcd

cat

2022

bot

0xfff

36

40

Extent

Extent

Extent

?

54 of 63

FlexDB: Sparse Index

  • Managing sorted keys in intervals
  • Indexing the first key (anchor) in each interval

54

54

FlexSpace

bar

0xbee

Address Space

0

3

11

14

22

25

33

ink

foo

abcd

cat

2022

bot

0xfff

36

40

Extent

Extent

Extent

flexspace_read_extent(fs, 30)

-> extent at 22

55 of 63

FlexDB: Sparse Index

  • Managing sorted keys in intervals
  • Indexing the first key (anchor) in each interval

55

55

FlexSpace

bar

0xbee

Address Space

0

3

11

14

22

25

33

ink

foo

abcd

cat

2022

bot

0xfff

36

40

cat

0

22

56 of 63

Recap

  • FlexTree enables lightweight data insertions in a flexible address space.
  • FlexDB manages sorted data without using extra persistent indirections.

56

57 of 63

Evaluation: Setup

  • Intel Xeon Silver 4210 w/ 10 cores
  • 64GB RAM
  • Optane 905P SSD
  • Key-Value Sizes:
    • ZippyDB: 91 bytes *
    • UDB: 154 bytes *
    • SYS: 424 bytes **
  • 4 Client Threads

57

* Zhichao Cao, Siying Dong, Sagar Vemuri, and David H. C. Du. “Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook”. In: 18th USENIX Conference on File and Storage Technolo gies (FAST’20). 2020, pp. 209–223.

** Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. “Workload Analysis of a Large-Scale Key-Value Store”. In: SIGMETRICS Per form. Eval. Rev. 40.1 (2012), pp. 53–64.

58 of 63

Evaluation: Disk I/O

  • Write 64GB into an empty store; Zipfian distribution

58

59 of 63

Evaluation: YCSB

  • Starting from a 500GB UDB store; Zipfian distribution

59

Write

Mostly

Read

Only

Read

Latest

Scan

Mostly

Read-modify-write

(RMW)

Read

Mostly

60 sec per

workload

60 of 63

Evaluation: YCSB

  • Starting from a 500GB UDB store; Zipfian distribution

60

Write

Mostly

Read

Only

Read

Latest

Scan

Mostly

Read-modify-write

(RMW)

Read

Mostly

60 sec per

workload

50% Update

50% Read

61 of 63

Evaluation: YCSB

  • Starting from a 500GB UDB store; Zipfian distribution

61

Write

Mostly

Read

Only

Read

Latest

Scan

Mostly

Read-modify-write

(RMW)

Read

Mostly

60 sec per

workload

5% Update

95% Read

62 of 63

Evaluation: YCSB

  • Starting from a 500GB UDB store; Zipfian distribution

62

Write

Mostly

Read

Only

Read

Latest

Scan

Mostly

Read-modify-write

(RMW)

Read

Mostly

60 sec per

workload

5% Insert

95% Scan

63 of 63

Summary

  • Flexible address space enables lightweight data management.
  • FlexDB achieves low WA and high throughput.

​

​

  • The code of this project is available at:

https://github.com/flexible-address-space/flexspace

63