1 of 33

DoppelGanger++:�Towards Fast Dependency Graph Generation for Database Replay

Wonseok Lee Jaehyun Ha Wook-Shin Han

POSTECH, Korea

Changyoo Park Myunggon Park Juhyeng Han Juchang Lee

SAP Labs Korea

1

2 of 33

1. Database Replay System�2. Problems of Existing Work�3. Our Solution�4. Evaluation

2

3 of 33

Database Replay System (DRS)

DRSs capture workloads on a production system and then replay them in a test system.
It enables to avoid any risks such as performance degradation, bugs, or new resource contention, before realizing system changes in the production system.

3

Production System

Test System

App Servers

REC

Replayer

Capture…

And replay!

workload

Clients

hardware/software

changes

Then detect

Performance degradation
Bugs
Resource contention

4 of 33

Capturing Workload

4

1

2

UPDATE emp SET salary=salary*1.1;

COMMIT;

SELECT * FROM emp WHERE salary > 60000;

5 of 33

Capturing Workload

1. Each user establish a session to the DBMS, before sending the requests.

5

1

2

sessions

UPDATE emp SET salary=salary*1.1;

COMMIT;

SELECT * FROM emp WHERE salary > 60000;

6 of 33

Capturing Workload

2. Each user sends SQL requests to the DBMS, and get the responses.

6

1

2

UPDATE emp SET salary=salary*1.1;

COMMIT;

SELECT * FROM emp WHERE salary > 60000;

U_emp

S_emp

C_emp

r₁

r₂

r₃

7 of 33

Capturing Workload

2. Each user sends SQL requests to the DBMS, and get the responses.

7

1

2

UPDATE emp SET salary=salary*1.1;

COMMIT;

SELECT * FROM emp WHERE salary > 60000;

U_emp

S_emp

C_emp

r₁

r₂

r₃

Timestamp order (SI)

A request

8 of 33

Capturing Workload

2. Each user sends SQL requests to the DBMS, and get the responses.

8

1

2

UPDATE emp SET salary=salary*1.1;

COMMIT;

SELECT * FROM emp WHERE salary > 60000;

U_emp

S_emp

C_emp

r₁

r₂

r₃

Timestamp order (SI)

A request

A Request

U_emp

r₁

Request ID

Request Type

S: Select

U: Update

C: Commit (publish updates of a transaction into database state in snapshot isolation)

Database objects

(tables/partitions)

9 of 33

Replaying Workload

The requests in a session are replayed in the timestamp order.

9

Replay Process

UPDATE emp SET salary=salary*1.1;

COMMIT;

SELECT * FROM emp WHERE salary > 60000;

U_emp

S_emp

C_emp

r₁

r₂

r₃

r₃ returns different results than when capturing.

Q. How to ensure that each request produces the same output as the original run in replay time?

10 of 33

Consistent Replay

The state-of-the-art DRSs supports consistent replay, ensuring output determinism if the test database has no bug.

10

Replay Process

UPDATE emp SET salary=salary*1.1;

COMMIT;

SELECT * FROM emp WHERE salary > 60000;

U_emp

S_emp

C_emp

r₁

r₂

r₃

11 of 33

Dependency Graph

DRSs executes the requests in parallel while preserving the ordering in the dependency graph.

11

U_emp

S_emp

C_emp

r₁

r₂

r₃

Session 1

Session 2

A request B has an incoming edge from a request A if

A is issued before B,
A and B access a common object,
and at least one of them is a commit request, modifying the object (SI).

12 of 33

Database Replay Workflow

Capture
Preprocess (Dependency Graph Generation)
Replay
Analyze

12

13 of 33

Database Replay Workflow

Capture
Preprocess (Dependency Graph Generation)
Replay
Analyze

13

Bottleneck (>50%)!

14 of 33

1. Database Replay System�2. Problems of Existing Work�3. Our Solution�4. Evaluation

14

15 of 33

Generate-and-prune Strategy

In the generation phase, it generates a dependency graph including some redundant edges.
In the pruning phase, it prunes all redundant edges by performing a transitive reduction algorithm.

15

Generate

Prune

16 of 33

Generate-and-prune Strategy

In the generation phase, it generates a dependency graph including some redundant edges.
In the pruning phase, it prunes all redundant edges by performing a transitive reduction algorithm.

16

Generate

Prune

Here, a direct edge (𝑣, 𝑢) is redundant if removing it still allows 𝑣 to be reached from 𝑢 (i.e., their order is preserved due to other paths).

17 of 33

Generate-and-prune Strategy

In the generation phase, it generates a dependency graph including some redundant edges.
In the pruning phase, it prunes all redundant edges by performing a transitive reduction algorithm.

17

Generate

Prune

inefficient, generating lots of redundant edges

18 of 33

Repetitive Backward Session Scan (RBSS)

For each request, it finds the latest dependent requests in other sessions using a backward scan.

18

C₁

r₉

C₂

r₁₁

S₁

r₂

S₂

r₃

S₃

r₄

S₃

r₅

S₁

r₁

U₁

r₈

U₂

r₁₀

forward scan

Session 1

Session 2

Session 3

backward scans over other sessions (for each request)

...

19 of 33

Problems of RBSS

The time complexity is O(N²) where N is the number of requests.
It first generates a lots of redundant edges, and remove them by expensive transitive reduction algorithm.

19

C₁

r₉

C₂

r₁₁

S₁

r₂

S₂

r₃

S₃

r₄

S₃

r₅

S₁

r₁

U₁

r₈

U₂

r₁₀

Session 1

Session 2

Session 3

...

repeatedly scanned

20 of 33

1. Database Replay System�2. Problems of Existing Work�3. Our Solution�4. Evaluation

20

21 of 33

Our Approach

We formally define dependency graphs based on two types of dominant, redundant edges in the dependency graph.
We propose a novel dependency generation algorithm, SSFS, that can generate any dependency graph we formalized.
We propose a parallel version of SSFS.

21

22 of 33

Two Dominant Redundant Edges

22

Object Transitivity (OT)

Inter-session Transitivity (IT)

A graph without OT and IT is only 5% larger than the minimal one.

23 of 33

Object Transitivity (OT)

OT refers to redundancy due to a path where all requests on the path access a common object.

23

C_2,3

r₁

U₃

r₂

U₂

r₃

U₁

r₄

U₁

r₅

S₁

r₆

C₁

r₇

S₂

r₈

C₃

r₉

S₃

r₁₀

C_1,2

r₁₁

Paths where all requests access Object 1.

Redundant due to Object Transitivity (OT).

24 of 33

Inter-session Transitivity (IT)

IT refers to redundancy due to a path through requests in two sessions.

24

C_2,3

r₁

U₃

r₂

U₂

r₃

U₁

r₄

U₁

r₅

S₁

r₆

C₁

r₇

S₂

r₈

C₃

r₉

S₃

r₁₀

C_1,2

r₁₁

Paths where all requests are in Sessions 1,2

Redundant due to

Inter-session Transitivity (IT)

25 of 33

Taxonomy of the Dependency Graphs

We define the design space of dependency graphs based on the types and orders of pruned redundant edges.
Although G_OTIT (pruning both OT and IT) is the smallest one, we discover that G_IT[OT] (pruning OT first and then pruning IT) is the most desirable one.

25

26 of 33

Stateful Single Forward Scan (SSFS)

SSFS generates a compact dependency graph through a single scan over all requests using a memoization technique.
While scanning each request 𝑟, SSFS generates the incoming edges of 𝑟 from the memo tables and updates them.

26

single forward scan

with states

27 of 33

Parallel SSFS (PSSFS)

We further parallelize SSFS in a divide-and-conquer manner.
It first horizontally splits the workload and generates local dependency graphs.
Using states, it merge adjacent dependency graphs.

27

Dependency Graph

Local Dependency Graph

divide-and-conquer

28 of 33

1. Database Replay System�2. Problems of Existing Work�3. Our Solution�4. Evaluation

28

29 of 33

Experimental Setting

Hardware

Xeon(R) CPU E7-8880 v4 CPUs
1TB RAM
745GB SSD

Workloads

TPC-C
Real-world customer workload
SD-Benchmark (extended ver.)

29

Measures

End-to-end time breakdown
Dependency graph generation time
Graph sizes
Speed-up w.r.t. # of threads

Competitors

SSFS (G_IT, G_OT, G_OTIT, G_IT[OT])
RBSS (RBSS+, RBSSL)

30 of 33

Experimental Results�Overall Time Breakdown

30

TPC-C, 15 minutes, 64 clients

TPC-C, 15 minutes, 256 clients

31 of 33

Experimental Results�Dependency Graph Generation when varying # of clients in TPC-C

31

Dependency Graph Generation Time

Graph Size

32 of 33

Experimental Results�Scalability

32

33 of 33

Conclusion

A taxonomy of the four types of dependency graphs by systematically exploring the design space of dominant redundant edges.
A novel dependency generation algorithm SSFS to scan requests once.
A parallel version of SSFS.

33