Shirakami: A Hybrid Concurrency Control Protocol for Tsurugi Relational Database System

이 논문은 짧은 트랜잭션과 긴 읽기 - 쓰기 트랜잭션을 동시에 처리해야 하는 복잡한 워크로드를 위해, Tsurugi 관계형 데이터베이스 시스템에 구현되어 PostgreSQL 대비 19.7 배 낮은 지연 시간과 Shirakami-OCC 대비 680 배 높은 처리량을 달성한 하이브리드 동시성 제어 프로토콜 'Shirakami'를 제안합니다.

핵심

🏭 배경: 데이터베이스라는 거대한 공장

데이터베이스를 거대한 공장의 창고라고 상상해 보세요. 이 창고에는 수많은 물건 (데이터) 이 쌓여 있고, 직원들 (트랜잭션) 이 물건을 찾아오거나 (읽기), 새로운 물건을 넣거나 (쓰기) 작업을 합니다.

이 공장에는 두 가지 종류의 직원이 있습니다.

1. 빠른 배달부 (짧은 거래, Short Transactions):

   • "이 물건 하나만 가져와!" "가격만 수정해!"
   • 아주 짧고 빠르게 끝나는 작업입니다. 하루에 수만 번씩 반복됩니다.
   • 예시: 쇼핑몰에서 주문하기, 계좌 이체하기.

2. 거대한 정리꾼 (긴 거래, Long Transactions):

   • "창고에 있는 모든 물건을 다 꺼내서, 종류별로 분류하고, 가격을 다시 계산해서 새로운 목록을 만들어줘!"
   • 아주 많은 데이터를 읽고, 복잡한 계산을 하며, 결과를 다시 저장해야 합니다. 시간이 오래 걸립니다.
   • 예시: 매달 말에 모든 고객의 사용량을 합산해서 요금을 계산하기, 공장 재고 전체를 다뤄서 원가 계산하기.

🚨 문제: 서로 부딪히는 상황

기존의 데이터베이스 (예: 포스트지스) 는 이 두 직원을 동시에 일하게 하면 큰 문제가 생깁니다.

• 상황: 거대한 정리꾼이 창고 전체를 뒤지고 있을 때, 빠른 배달부들이 "여기서 물건 좀 꺼내줘!"라고 계속 요청합니다.
• 결과:
  • 정리꾼은: 배달부들이 자꾸 방해해서 일을 못 하고, 결국 "아, 내가 잘못했나?" 하고 일을 다 취소하고 (Abort) 처음부터 다시 시작해야 합니다.
  • 배달부들은: 정리꾼이 길을 막고 있어서 기다려야 하거나, 정리꾼이 일을 취소하는 바람에 자신도 일을 못 합니다.
  • 최종: 공장이 마비되고, 처리 속도가 느려집니다.

기존 기술들은 "짧은 일"만 잘 하거나, "긴 일"만 잘 하도록 설계되어 있어, 둘을 섞어서 처리하는 데는 한계가 있었습니다.

✨ 해결책: 시라카미 (Shirakami) 프로토콜

이 논문은 **'시라카미'**라는 새로운 규칙을 제안합니다. 시라카미는 두 가지 다른 규칙을 하나로 합친 하이브리드 (혼합) 시스템입니다.

1. 두 가지 역할 분담 (S-LTX 와 S-OCC)

시라카미는 직원을 두 팀으로 나누어 관리합니다.

• 팀 A (S-LTX): 거대한 정리꾼을 위한 팀

  • 특징: 아주 넓은 공간을 확보해 줍니다. 정리꾼이 일을 할 때, 다른 사람이 방해하지 못하게 미리 "이 구역은 내가 정리 중이야"라고 표시해 둡니다 (Write Preservation).
  • 비유: 정리꾼이 창고를 정리할 때, "이 시간 동안 이 구역은 내가 독점해서 정리할 거야"라고 미리 공지하고, 다른 배달부들은 그 구역에 들어오지 못하게 막습니다. 하지만 정리꾼이 일을 마칠 때까지 기다리는 게 아니라, 정리꾼이 일을 시작할 때부터 미리 준비를 해둡니다.
  • 핵심: 정리꾼이 일을 멈추지 않고 계속 진행할 수 있게 합니다.

• 팀 B (S-OCC): 빠른 배달부를 위한 팀

  • 특징: 기존에 잘 알려진 '실로 (Silo)' 방식을 개량했습니다.
  • 비유: 배달부들은 서로 부딪히지 않도록 빠르게 움직입니다. 만약 정리꾼이 미리 "이 구역은 정리 중"이라고 표시해 두었다면, 배달부는 그 구역에 들어가지 않고 다른 일을 하거나 잠시 기다렸다가 다시 시도합니다.
  • 핵심: 짧은 일은 기존처럼 아주 빠르게 처리됩니다.

2. 시간대 관리 (Epoch) 와 우선순위

시라카미는 시간을 작은 조각 (Epoch) 으로 나누어 관리합니다.

• 우선순위: 정리꾼 (긴 거래) 이 배달부 (짧은 거래) 보다 우선순위가 높습니다.
• 작동 방식:
  • 정리꾼이 일을 시작하면, 다음 시간대부터는 그 구역이 정리꾼의 것으로 간주됩니다.
  • 배달부들은 정리꾼이 일을 시작하기 전에 미리 그 사실을 알 수 있습니다. 만약 충돌이 예상되면, 배달부는 일을 취소하고 (Abort) 다시 시도합니다.
  • 중요한 점: 정리꾼은 배달부 때문에 일을 취소당하지 않습니다. 반대로, 배달부는 정리꾼을 방해하지 않도록 스스로 길을 비킵니다.

3. 순서 바꾸기 (Order Forwarding) - 시라카미의 마법

가장 흥미로운 부분은 **'순서 바꾸기'**입니다.

• 상황: 정리꾼 (A) 이 물건을 정리하고 있는데, 그보다 나중에 시작한 다른 정리꾼 (B) 이 A 가 정리한 물건을 읽어야 할 때가 있습니다.
• 기존 방식: A 가 먼저 끝내야 B 가 읽을 수 있으니, B 는 A 가 끝날 때까지 기다려야 합니다.
• 시라카미 방식: "아, B 가 A 보다 나중에 시작했지만, B 가 읽어야 할 물건을 A 가 정리하고 있네? 그럼 순서를 바꿔서 B 가 먼저 끝내게 하고, A 는 나중에 끝내자!"
• 비유: 줄을 서서 기다리는 사람들 사이에서, 나중에 온 사람이 먼저 일 처리를 하고, 나중에 온 사람이 먼저 끝내도 괜찮다면 순서를 뒤바꿔서 모두 빠르게 처리해 줍니다. 이렇게 하면 불필요한 대기 시간이 사라집니다.

📊 실험 결과: 얼마나 빨라졌을까?

연구진은 이 시스템을 '츠루기 (Tsurugi)'라는 실제 데이터베이스에 적용해 보았습니다.

1. 전화 요금 계산 (긴 거래 + 짧은 거래):
   • 기존 시스템 (PostgreSQL) 은 1800 초 (30 분) 가 넘게 걸리거나 아예 끝내지 못했습니다.
   • **시라카미 (Tsurugi)**는 19.7 배 더 빠릅니다. (약 90 초 만에 완료)
2. 원가 계산 (BoM):
   • 5.6 배 더 빠릅니다.
3. 긴 거래 처리 능력:
   • 긴 거래만 처리할 때, 시라카미의 '긴 거래 팀 (S-LTX)'은 '짧은 거래 팀 (S-OCC)'보다 680 배 더 많은 일을 처리했습니다.

🎯 결론: 왜 이것이 중요한가요?

우리의 일상생활과 비즈니스는 점점 더 복잡해지고 있습니다.

• **실시간 주문 (짧은 거래)**이 끊이지 않는 동안,
• **매달 말의 대량 정산 (긴 거래)**도 동시에 이루어져야 합니다.

기존 시스템은 이 두 가지를 동시에 하면 "서로 발목이 잡혀서 느려진다"는 문제가 있었습니다. 하지만 시라카미는 이 두 가지를 서로 방해하지 않고, 각자의 특성에 맞춰 최적화하여 동시에 처리할 수 있게 해줍니다.

한 줄 요약:

"빠른 배달부들과 거대한 정리꾼이 같은 공장에서 일할 때, 서로 부딪히지 않고 각자 최고의 속도로 일할 수 있게 해주는 최고의 교통 통제 시스템이 바로 시라카미입니다."

기술 요약

1. 문제 정의 (Problem)

현대 비즈니스 환경 (예: 부품 명세서 (BoM) 관리, 통신사 청구 처리) 에서는 **짧은 트랜잭션 (Short Transactions)**과 **긴 읽기 - 쓰기 트랜잭션 (Long Read-Write Transactions)**이 동시에 발생하는 혼합 워크로드가 필수적입니다.

• 기존 프로토콜의 한계:
  • 단순한 OCC (Optimistic Concurrency Control): Silo 나 ERMIA 와 같은 현대적 OCC 는 짧은 트랜잭션에는 탁월하지만, 긴 트랜잭션이 실행될 때 충돌 확률이 급격히 증가하여 많은 트랜잭션이 중단 (Abort) 되거나 재시도되는 문제가 발생합니다.
  • 결정론적 프로토콜 (Deterministic Protocols): 트랜잭션의 실행 순서를 미리 결정하여 긴 트랜잭션을 처리할 수 있지만, 서브쿼리 (Subquery) 가 포함된 동적 SQL 실행에는 적합하지 않으며, 그래프 데이터베이스에 특화된 경우 (Tuskflow 등) 일반 관계형 데이터베이스에는 적용이 어렵습니다.
  • 기존 MVSR (Multiversion View Serializability) 기반: Oze 와 같은 프로토콜은 긴 트랜잭션을 지원하지만, 짧은 트랜잭션 처리 효율이 낮고 프로토콜 전환 시 지연 시간이 발생하는 등 실제 생산 시스템에 적용된 사례가 드뭅니다.
• 핵심 문제: 생산 환경에서 일관성 (Consistency) 을 유지하면서 긴 배치 (Batch) 트랜잭션과 짧은 온라인 트랜잭션을 동시에 효율적으로 처리할 수 있는 프로토콜이 부재합니다.

2. 제안 방법론: 시라카미 (Shirakami) 프로토콜

저자들은 Tsurugi라는 관계형 데이터베이스 시스템의 트랜잭션 처리 모듈로 Shirakami라는 하이브리드 동시성 제어 프로토콜을 제안했습니다. 이는 두 가지 하위 프로토콜을 통합한 방식입니다.

A. 하이브리드 아키텍처

1. Shirakami-LTX (S-LTX): 긴 읽기 - 쓰기 트랜잭션을 위한 프로토콜.
   • 기반: 다중 버전 뷰 직렬화 (Multiversion View Serializability, MVSR) 를 기반으로 하며, 기존 MVTO(Multiversion Timestamp Ordering) 보다 넓은 스케줄링 공간을 제공합니다.
   • 핵심 메커니즘:
     • Write Preservation (WP, 쓰기 보존): 긴 트랜잭션 시작 시 쓰기 예정 영역 (Table level) 을 미리 선언합니다. 짧은 트랜잭션이 이 정보를 확인하여 충돌을 미리 감지하고 중단함으로써 긴 트랜잭션의 실패를 방지합니다.
     • Order Forwarding (순서 전달): 우선순위가 낮은 긴 트랜잭션이 우선순위가 높은 트랜잭션의 쓰기를 읽는 경우, 직렬화 순서를 동적으로 변경 (Forwarding) 하여 두 트랜잭션 모두 커밋될 수 있도록 합니다. 이는 충돌 순열 (False Positive) 을 줄이고 MVSR 의 넓은 스케줄링 공간을 활용합니다.
     • Epoch 기반 동기화: 트랜잭션을 Epoch 단위로 관리하며, S-LTX 는 Epoch 시작 시점에, S-OCC 는 종료 시점에 직렬화 포인트를 가집니다.
2. Shirakami-OCC (S-OCC): 짧은 트랜잭션을 위한 프로토콜.
   • 기반: Silo 프로토콜을 기반으로 하되, S-LTX 와의 공존을 위해 수정되었습니다.
   • 특징: S-LTX 가 선언한 WP 정보를 읽기 단계에서 확인하여 불필요한 충돌을 피하고, S-LTX 의 쓰기 검증 (Write Validation) 시 S-OCC 가 읽은 데이터에 대한 메타데이터를 유지하여 일관성을 보장합니다.

B. 통합 및 우선순위 관리

• 동시 실행: S-LTX 와 S-OCC 는 동시에 실행됩니다.
• 우선순위: S-LTX 가 S-OCC 보다 높은 우선순위를 가집니다. S-LTX 는 S-OCC 에 의해 방해받지 않으며, S-OCC 는 S-LTX 와 충돌 시 중단되거나 재시도됩니다.
• 프로토콜 전환 불필요: 시스템이 워크로드에 따라 동적으로 프로토콜을 전환할 필요가 없으며, 두 프로토콜이 자연스럽게 통합되어 안정적인 성능을 제공합니다.

3. 주요 기여 (Key Contributions)

1. 생산 수준의 하이브리드 프로토콜 구현: 이론적인 MVSR 공간과 Silo 기반의 짧은 트랜잭션 처리를 결합하여, 서브쿼리를 포함한 실제 SQL 워크로드를 지원하는 최초의 프로덕션 레벨 구현체를 제시했습니다.
2. Write Preservation 및 Order Forwarding: 긴 트랜잭션의 충돌을 줄이기 위해 쓰기 영역을 미리 선언하고, 우선순위 기반의 순서 전달 기법을 도입하여 긴 트랜잭션의 성공률을 극대화했습니다.
3. Tsurugi RDBMS 개발: Shirakami 를 탑재한 Tsurugi 관계형 데이터베이스 시스템을 개발하고, 이를 오픈소스로 공개했습니다.
4. 성능 검증: 기존 프로토콜 (PostgreSQL, Silo 등) 대비 긴 트랜잭션 처리 성능이 획기적으로 개선되었음을 실험을 통해 입증했습니다.

4. 실험 결과 (Results)

저자들은 Tsurugi 시스템과 Shirakami 프로토콜을 다양한 벤치마크를 통해 평가했습니다.

• Telecommunication Billing Benchmark (통신 청구):
  • 결과: PostgreSQL 대비 **19.7 배 낮은 지연 시간 (Latency)**을 기록했습니다.
  • 특이사항: 64 스레드 환경에서 PostgreSQL 은 1800 초 시간 제한 내에 벤치마크를 완료하지 못했으나, Tsurugi 는 성공적으로 완료했습니다.
• Bill of Materials (BoM) Benchmark:
  • 결과: PostgreSQL 대비 5.6 배 빠른 처리 속도를 보였습니다. (READ COMMITTED 레벨의 PostgreSQL 은 더 빠르지만 데이터 불일치 문제가 발생했습니다.)
• Shirakami 내부 비교 (S-LTX vs S-OCC):
  • 긴 트랜잭션이 포함된 YCSB 기반 워크로드에서 **S-LTX 가 S-OCC 대비 680 배 높은 처리량 (Throughput)**을 기록했습니다.
  • 긴 트랜잭션의 길이가 길어질수록 (1000 ops 이상) S-OCC 는 거의 0 에 가까운 성공률을 보인 반면, S-LTX 는 안정적인 처리량을 유지했습니다.
• TPC-C 벤치마크:
  • Tsurugi (OCC 모드) 는 128 스레드까지 확장성이 입증된 반면, PostgreSQL (SERIALIZABLE) 은 16 스레드 이후 성능이 저하되었습니다.

5. 의의 및 결론 (Significance)

• 실무 적용 가능성: 기존 연구들이 주로 짧은 트랜잭션 (YCSB, TPC-C) 이나 특정 도메인 (그래프 DB) 에 집중했던 반면, Shirakami 는 실제 비즈니스 (BoM, 통신 청구) 에서 발생하는 긴 배치 트랜잭션과 짧은 온라인 트랜잭션의 공존 문제를 해결했습니다.
• 일관성 유지: 긴 트랜잭션 처리 시에도 강한 일관성 (Serializable) 을 유지하면서도, 짧은 트랜잭션의 성능 저하를 최소화했습니다.
• 시스템 완성도: 단순한 프로토콜 제안에 그치지 않고, 인덱스 (Yakushima), SQL 엔진 (Jogasaki), 로그 저장소 (Limestone) 등을 포함한 완전한 데이터베이스 시스템 (Tsurugi) 으로 구현되어 실제 사용 사례를 가지고 있습니다.

결론적으로, Shirakami 는 현대 클라우드 네이티브 환경과 복잡한 비즈니스 로직을 가진 시스템에서 요구되는 하이브리드 워크로드 처리 능력을 갖춘 획기적인 동시성 제어 솔루션입니다.