데이터베이스 리플레이 시스템(DRS)은 운영 시스템에서 워크로드를 캡처한 뒤 테스트 시스템에서 이를 재생하여 다양한 시스템 변경을 검증함으로써, 프로덕션 환경에 적용하기 전 어떤 위험도 피할 수 있게 한다. DRS에서의 의존성 그래프 생성은 출력 결정성을 보존하면서 동시성을 최대화하는 데 있어 결정적으로 중요하다. 상용 DBMS에 배치된 최신 의존성 그래프 생성 알고리즘은 generate-and-prune(생성-가지치기) 전략을 사용한다. 이 알고리즘은 워크로드의 각 요청에 대해 역방향 스캔을 수행하여 먼저 의존성 그래프를 생성한 다음, 비용이 큰 순서(전이) 감소(transitive reduction) 알고리즘을 사용하여 모든 중복 간선을 제거(가지치기)한다. 그러나 우리는 이 과정에서 중복 간선을 다수 포함하는 큰 의존성 그래프가 생성되며, 최악의 시간 복잡도가 워크로드 내 요청 수에 대해 이차(quadratic)임을 관찰하였다. 이러한 난제를 해결하기 위해 우리는 DRS를 위한 네 가지 범주의 의존성 그래프를 형식적으로 제안한다. 이어서, SSFS(stateful single forward scan)라는 상태 기반 단일 정방향 스캔 알고리즘을 제시하여, 모든 요청에 대해 단 한 번의 스캔을 수행하면서 상태를 간결하게 유지함으로써 어떤 범주의 의존성 그래프든 생성할 수 있게 한다. 여기서 상태(state)는 효율적인 의존성 그래프 생성을 위해 저장되고 유지되는 정보를 의미한다. 또한 다중 코어 CPU의 연산 역량을 활용하면서 부하를 균형 있게 조절하기 위해 병렬 SSFS도 제안한다. 우리는 선도적인 상용 DBMS에 우리의 DRS를 구현하였다. TPC-C 및 SD 벤치마크와 실제 고객 워크로드를 사용한 광범위한 실험 결과, 우리의 DRS는 최신 기술과 비교하여 의존성 그래프 생성 시간을 최대 두 자릿수(2 orders of magnitude)까지 유의하게 향상시키는 것으로 나타났다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.