타임스탬프 오더링으로 트랜잭션 순서를 제어하는 방법

대기 없이 트랜잭션 실행 순서를 지키는 방식

Timestamp Ordering은 트랜잭션마다 고유한 타임스탬프를 부여하고, 그 순서에 맞춰 연산을 허용하거나 거부하는 동시성 제어 프로토콜이다. 타임스탬프는 시스템 시계의 물리적 시간이나 논리적 계수기로 할당할 수 있다.

핵심은 대기시키지 않는다는 점이다. 이미 더 최근의 트랜잭션이 처리한 데이터에 과거 순서의 트랜잭션이 접근하려 하면 해당 트랜잭션을 철회한다. 이 방식으로 직렬화 가능성을 보장하고 교착상태를 원천적으로 막는다. 낙관적 동시성 제어 방식의 하나로도 볼 수 있다.

타임스탬프 부여 경로

시스템 시계를 사용할 때는 트랜잭션이 시작한 시점의 시간값을 타임스탬프로 삼는다.

⤢✕

논리적 계수기를 사용하는 방식에서는 새 트랜잭션마다 카운터를 증가시키고, 증가한 값을 순서 식별자로 사용한다.

⤢✕

데이터 항목에 남기는 읽기·쓰기 이력

각 데이터 항목 x는 두 개의 타임스탬프를 관리한다.

Read_TS(x): x를 성공적으로 읽은 가장 최근(Youngest) 트랜잭션의 타임스탬프
Write_TS(x): x를 성공적으로 기록한 가장 최근 트랜잭션의 타임스탬프

타임스탬프가 작은 트랜잭션은 먼저 실행된 것으로 간주한다. 이 순서와 충돌하는 연산은 거부 또는 철회되며, 결과적으로 직렬성(Serializability)을 유지한다.

읽기 요청은 최근 쓰기 이력과 비교한다

트랜잭션 T가 x를 읽을 때는 Write_TS(x)와 TS(T)를 비교한다.

⤢✕

Write_TS(x) > TS(T)라면 T보다 더 최근인 트랜잭션이 이미 x를 수정한 상태다. 이는 "Too-Late-Read" 문제에 해당하므로 T를 철회하고 새 타임스탬프로 다시 시작한다.

반대로 Write_TS(x) ≤ TS(T)이면 읽기를 허용하고, Read_TS(x)는 max(Read_TS(x), TS(T))로 갱신한다.

쓰기 요청은 읽기와 쓰기 이력을 함께 확인한다

쓰기에서는 더 최근 트랜잭션의 읽기 또는 쓰기 기록이 있는지 모두 확인해야 한다.

⤢✕

Read_TS(x) > TS(T)이면 더 최근 트랜잭션이 이미 x를 읽은 것이므로 "Too-Late-Write" 문제가 발생한다. T는 철회 후 재시작한다.

Write_TS(x) > TS(T)인 경우도 더 최근 트랜잭션이 x를 수정한 상태이므로 철회한다. 두 조건에 모두 해당하지 않을 때만 쓰기를 수행하고 Write_TS(x)를 TS(T)로 바꾼다.

Thomas의 쓰기 규칙이 바꾸는 철회 조건

Thomas의 쓰기 규칙(Thomas's Write Rule)은 기본 타임스탬프 프로토콜을 확장해 Blind Write에서 불필요한 트랜잭션 철회를 줄인다.

Read_TS(x) > TS(T)이면 기존처럼 T를 철회한다. 다만 Write_TS(x) > TS(T)인 경우에는 T의 쓰기 연산만 무시하고 트랜잭션 자체는 철회하지 않는다. 나머지 경우에는 기존 규칙대로 쓰기를 수행한다.

⤢✕

교착상태를 피하는 대신 감수할 비용

트랜잭션은 잠금을 기다리지 않고 충돌 시 즉시 철회되므로 교착상태가 발생하지 않는다. 타임스탬프 순서에 따른 직렬화도 가능하다. 재시작한 트랜잭션에 새 타임스탬프를 할당하면 언젠가는 실행될 수 있어 기아 상태를 방지할 수 있으며, 복잡한 교착상태 감지나 해결 메커니즘도 필요하지 않다.

반면 한 트랜잭션의 롤백이 다른 트랜잭션의 연쇄 롤백으로 이어질 수 있다. 충돌이 생길 때마다 대기 대신 철회하므로 시스템 부하가 높은 환경에서는 철회와 재시작이 빈번해져 성능이 저하될 수 있다. 모든 트랜잭션에 고유한 타임스탬프를 할당해야 하는 오버헤드도 있다.

분산 환경과 버전 관리에 연결되는 지점

분산 데이터베이스에서는 여러 노드에 흩어진 데이터의 일관성을 유지하면서 각 노드가 독립적으로 동작해야 한다. 글로벌 타임스탬프를 기준으로 트랜잭션을 조정하는 구조가 이를 뒷받침할 수 있다.

⤢✕

PostgreSQL과 같은 DBMS의 타임스탬프 기반 MVCC는 데이터 항목의 여러 버전을 유지해 동시성을 높인다.

⤢✕

멀티버전 타임스탬프 오더링(MVTO)도 여러 버전을 유지한다. 읽기 연산이 쓰기 연산을 차단하지 않으므로 읽기 전용 트랜잭션의 성능을 높일 수 있다. 타임스탬프 기반 낙관적 동시성 제어에서는 검증 단계에서 타임스탬프로 충돌을 감지하고, 읽기·쓰기 집합 기반 검증과 타임스탬프 오더링을 결합한다.

규칙을 반영한 간단한 구현

class DataItem:
    def __init__(self, value):
        self.value = value
        self.read_ts = 0
        self.write_ts = 0

class TransactionManager:
    def __init__(self):
        self.current_ts = 0
        self.data_items = {}

    def start_transaction(self):
        self.current_ts += 1
        return self.current_ts

    def read_item(self, ts, item_id):
        if item_id not in self.data_items:
            self.data_items[item_id] = DataItem(None)

        item = self.data_items[item_id]

        # 타임스탬프 오더링 규칙 적용
        if item.write_ts > ts:
            print(f"Transaction {ts} aborted: item {item_id} was written by a younger transaction")
            return None  # 트랜잭션 철회

        # 읽기 타임스탬프 갱신
        item.read_ts = max(item.read_ts, ts)
        return item.value

    def write_item(self, ts, item_id, value):
        if item_id not in self.data_items:
            self.data_items[item_id] = DataItem(None)

        item = self.data_items[item_id]

        # 타임스탬프 오더링 규칙 적용
        if item.read_ts > ts:
            print(f"Transaction {ts} aborted: item {item_id} was read by a younger transaction")
            return False  # 트랜잭션 철회

        if item.write_ts > ts:
            print(f"Transaction {ts} aborted: item {item_id} was written by a younger transaction")
            return False  # 트랜잭션 철회

        # 쓰기 수행 및 타임스탬프 갱신
        item.value = value
        item.write_ts = ts
        return True