DoppelGanger++: Towards Fast Dependency Graph Generation for Database Replay
- Title
- DoppelGanger++: Towards Fast Dependency Graph Generation for Database Replay
- Authors
- HAN, WOOK SHIN; WONSEOK, LEE; HA, JAE HYUN; PARK, CHANGGYOO; PARK, MYUNGGON; HAN, JUHYENG; LEE, JUCHANG
- Date Issued
- 2024-06-09
- Publisher
- ACM SIGMOD
- Abstract
- A database replay system (DRS) captures workloads on a production system and then replays them in a test system to test various system changes, avoiding any risk before realizing them in production. The dependency graph generation in a DRS is crucial in preserving output determinism while maximizing concurrency. The state-of-the-art dependency graph generation algorithm deployed in a commercial DBMS uses a generate-and-prune strategy. It first generates a dependency graph by performing backward scans for each request in a workload. It then prunes all redundant edges using an expensive, transitive reduction algorithm. However, we notice that this generates a large dependency graph that contains many redundant edges and its worst-case time complexity is quadratic to the number of requests in a workload. In order to solve these challenging problems, we formally propose four classes of dependency graphs for DRSs. We then present a stateful single forward scan algorithm, SSFS, to generate any class of dependency graphs by performing a single scan over all requests while succinctly maintaining states. Here, states refer to information that is stored and maintained for efficient dependency graph generation. We also propose the parallel SSFS to utilize the computation power with multi-core CPUs while balancing the loads. We implemented our DRS in a leading commercial DBMS.
Extensive experiments using the TPC-C, SD benchmarks, and a real-world customer workload show that
our DRS significantly improves the dependency graph generation time by up to two orders of magnitude,
compared to the state-of-the-art.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/121773
- Article Type
- Conference
- Citation
- 50th Int’l Conf. on Management of Data (ACM SIGMOD), 2024-06-09
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.