대표적인 CC 기법으로는 Timestamp, OCC, MVCC가 있다.
그 중 OCC의 논문에 대해 리뷰를 진행해보겠다.
추가로 만약 Database에 관심이 있다면 CMU의 앤디 파블로 교수의 Advanced Database Systems 강의를 꼭 수강해보길 바란다. 이 강의만 잘 들어도 DB에 대해 많은 공부가 된다.
https://youtu.be/BShOt5gYiPs?si=rrOZJtUF2I_dsyvc
논문: https://dl.acm.org/doi/10.1145/319566.319567
Introduction
- Non-locking Concurrency Control
- 트랜잭션 롤백에 의존
- 충돌 발생 횟수가 적다고 가정
- Phase
- Read
- 읽기 작업: 제약 없이 실행 가능
- 쓰기 작업: 로컬 복사본 생성 → 여기에 쓴다
- 결과를 반환하는 쿼리의 경우 쓰기 작업으로 간주된다
- Validation
- Write
- 로컬 복사본에 있던 변경 내용을 글로벌 상태로 업데이트
- 검증 단계가 성공해야 Write 가능
- Write가 완료되면, 해당 트랜잭션의 모든 작업이 DB에 영구적으로 반영되며 트랜잭션을 종료한다
- 쓰기 이후 clean up 진행 (delete set과 local copy 삭제)
- Read
Read and Write Phase
Local Copy 관리
- Root Node
- Global name을 가지며 모든 트랜잭션이 동일한 이름으로 인식한다.
- Global Object
- 트랜잭션 간에 공유되는 공용 데이터
- 트리 구조의 모든 노드는 기본적으로 global이므로, 내가 수정한 내용을 다른 트랜잭션도 참조할 수 있다
- OCC에서는 Root Node의 Global name과 다른 이름을 가진다
- global name을 가진 root node는 다른 트랜잭션이 참조할 수 있다 (트랜잭션은 root node의 global name만 알고 있다.)
- 하지만 Local copy는 올바른 이름을 가지지 않으므로 다른 트랜잭션이 접근할 수 없다
- Write Phase에서 local copy가 global object로 ‘교환’되어야 global object로 승격될 수 있다.
Data Integrity를 유지하기 위한 조건
- 루트 노드가 생성/삭제되지 않음
- 삭제된 노드로의 Dangling Pointer가 남아있지 않음
- 생성된 노드로 새로운 포인터를 작성하여 접근이 가능함
- 각 트랜잭션은 이를 각자 준수해야 한다
Exchange
- 객체는 Physical Address가 아닌 Name으로 참조된다.
- 두 객체의 Descriptor에서 Physical Address만 교환하면 끝난다.
Validation
- Locking은 worst case에서만 필요하다. 즉, OCC의 validation은 worst case에서만 실패한다.
- 트랜잭션이 완료되기 전에 Data Integrity를 검사한다
Serial Equivalence (직렬성 등가성)
- 어떤 순서로 트랜잭션을 직렬화하더라도 동일한 결과가 나와야 한다
- 충돌 여부를 검증하기 위해 Read set과 Write set을 비교한다
- TrxNo를 기반으로 트랜잭션의 순서를 지정하여 Serial Equivalence를 확인한다
- 각 트랜잭션은 각자 Integrity를 유지하도록 설계되어 있으므로, 트랜잭션 실행 후의 데이터 역시 무결성을 유지한다.
- 검증 성공 조건 (하나만 충족하면 됨)
- T1의 write phase가 T2의 read phase 이전에 완료될 경우
- T1의 write set이 T2의 read set과 겹치지 않고, T1의 write phase가 T2의 write phase 이전에 완료될 경우
- 이전에 쓴 애를 내가 읽기 않았고, 이전 트랜잭션이 이미 다 썼을 때
- write phase는 set가 겹치지 않더라고 반드시 직렬화되어야 함
- T1의 write set이 T2d의 read or wirte set과 겹치지 않고, T1의 read phase가 T2의 read phase 이전에 완료될 경우
- 이전에 쓴 애를 내가 읽거나 쓰지 않았고, 이전 애가 먼저 validation 시작했을 때
Transaction Number
- 트랜잭션 번호가 작은 트랜잭션이 반드시 선행해야 한다.
- 읽기 단계 후에 번호를 할당하여 Validation을 가능한 한 빠르게 수행할 수 있다 (Optimistic Approach)
- 실패 시, Rollback (다시 시작되며 새로운 TrxNo를 부여받게 된다)
Starvation
- 반복적으로 Validation을 실패하는 트랜잭션
- 해당 트랜잭션을 재시작하면서, 전체 DB를 잠금 상태로 설정 (Write-Lock)
Serial Validation
- 검증 성공 조건 1, 2를 기반으로 작동됨(3은 사용되지 않으므로 write phase는 항상 직렬로 실행되어야 함)
트랜잭션의 종료 (tend)
- 검증: write set이 다른 트랜잭션과 겹치면 검증 실패
- 검증 성공: write phase 실행 후 trx_no++;
- TrxNo은 검증이 성공한 경우에만 할당 (실패 시 다른 트랜잭션이 번호 재사용)
- 검증 실패: abort, rollback
- 검증 성공: write phase 실행 후 trx_no++;
- Critical Section 밖에서 검증하여 병렬성을 극대화 할 수도 있음 (생략) (multi-processor)
Query(읽기 전용 트랜잭션)
- Write Phase 불필요 → TrxNo 불필요
- 단순히 start_tn ~ finish tn 사이의 write set만 확인하면 된다.
- start_tn: read phase가 시작될 때의 tn
- finish_tn: read phase가 종료될 때의 tn
- 내가 시작~끝까지의 모든 트랜잭션, 즉 영향을 줄 수도 있는 트랜잭션을 모두 식별
- 다른 트랜잭션의 쓰기 작업만 검증하여 내가 읽은 데이터가 변경되지 않았는지만 확인하면 된다.
- if (start_tn == finish_tn): 즉시 검증 완료 → Optimistic Approach가 최적인 경우
Parallel Validation
- 검증 조건2 ⇒ start_tn+1 ~ fisnish_tn에 대해 검증
- 검증 조건3 ⇒ active trx(read phase만 완료하고 write phase는 완료X)가 자신의 read/write set과 충돌하지 않는지
- active trx: 내 tn보다 작은 임시 tn을 받은 트랜잭션들
- 성공 시, write phase → tnc++; → active에서 자신 제거
Application
B-tree
- 매우 큰 tree도 깊이는 별로 깊지 않다.
- Insert 작업은 특정 레벨에서 한 개의 노드만 읽거나 쓴다.
- 충돌 확률이 매우 적다 (생략)
- Read/Write Set의 크기가 제한적이므로 Validation이 빠르게 수행된다
Pros
- Locking Overhead 제거
- 충돌하지 않는 경우 추가적인 Overhead가 거의 발생하지 않는다
- Deadlock 제거
- 검증 실패 시 단순히 롤백하게 된다
- Query Dominant System (일기 전용 트랜잭션)에 적합하다
- 대부분의 트랜잭션이 읽기만 한다면 Validation Overhead가 최소화된다.
Limitations
- 충돌이 잦을 경우, 롤백이 자주 발생하게 되어 성능이 저하된다
- Validation/Write Phase에서 Bottleneck 발생 가능
Conclusion
- 충돌이 드문 환경에서 유용하게 사용된다
- Locking 기반 방법에 비해 병렬성이 놓고 Mulit-Processor 환경에서 성능 극대화
- 하지만, 충돌 빈도가 높을 경우 효율이 떨어진다
"Concurrency 검증할 바엔 그냥 다 롤백시켜버리겠다"
... 열심히 읽었지만 결국 큰 맥락은 이런 의도를 전반적으로 깔고 진행하기 때문에 Validation이 그렇게 복잡하게 진행되진 않는다.
오히려 Locking에 소요되는 시간을 고려하면 이게 나을 수도 있겠다.
하지만 이것도 CC라 봐야 할지 싶은 것도 사실이다.
아마 요즘 CC는 대부분 Locking 기반이라 더욱 그렇게 느껴지는 것 같다.