(KO) PostgreSQL SSI와 술어 잠금 — 직렬화 스냅샷 격리, SIREAD 잠금, rw-충돌 그래프

학술적 배경
DBMS 공통 설계 패턴
PostgreSQL의 구현
소스 코드 가이드
소스 검증 (2026-06-05 기준)
PostgreSQL 너머 — 비교 설계와 연구 프론티어
출처

학술적 배경

스냅샷 격리(Snapshot Isolation, SI)는 트랜잭션마다 특정 시점의 일관된 데이터베이스 뷰를 제공한다. 읽기는 쓰기를 막지 않고, 쓰기도 읽기를 막지 않는다. Database System Concepts(Silberschatz, 7판, §19.6)는 SI를 MVCC 기반의 낙관적 기법으로 분류한다. 그러나 SI는 완전한 직렬화 가능성을 보장하지 않는다. 대표적인 반례가 쓰기 왜곡(write skew) 이상 현상이다. 두 병행 트랜잭션이 서로 겹치는 데이터를 읽은 뒤 각자 다른 부분을 쓰면, 결과가 어떤 직렬 실행과도 일치하지 않는 상태가 발생한다.

이론적 해법은 Making Snapshot Isolation Serializable(Fekete 외, ACM TODS 2005, README-SSI의 참고문헌 [2])에서 제시됐다. 핵심 관찰은 SI에서 발생하는 모든 이상 현상이 의존성 그래프 안에 **위험 구조 (dangerous structure)**를 포함한다는 점이다. 위험 구조란 rw-충돌 에지 두 개가 연속으로 이어진 형태를 말한다.

Tin ──rw──► Tpivot ──rw──► Tout

Tout이 Tpivot과 Tin보다 먼저 커밋해야 이 구조가 실제 이상 현상으로 이어진다. wr- 또는 ww-의존성은 탐지에 불필요하다. rw-충돌만 추적해도 이상 현상을 빠짐없이 잡아낼 수 있다. 이 패턴을 감시하다가 완성되는 시점에 트랜잭션 하나를 중단하면, SI 위에서도 직렬화 가능성을 달성할 수 있다. 이 접근법이 **직렬화 스냅샷 격리(Serializable Snapshot Isolation, SSI)**다.

Cahill, Röhm, Fekete(SIGMOD 2008, README-SSI의 참고문헌 [1])는 최초의 실용적 SSI 알고리즘을 제시하고, 순수 SI 대비 오버헤드가 작음을 입증했다. PostgreSQL은 9.1 버전에서 SSI를 도입했다. 구현은 논문 프로토타입과 여러 부분에서 다르며, PostgreSQL의 기존 아키텍처에서 비롯된 차이점은 README-SSI의 “Innovations” 절에 열거되어 있다. 핵심 그래프 감시 아이디어는 동일하다.

다중 버전 직렬화 그래프와 위험 구조

위험 구조 주장을 정밀하게 이해하려면 SSI 문헌의 기반인 **다중 버전 직렬화 그래프(multi-version serialization graph, MVSG)**를 떠올리는 것이 도움이 된다. 노드는 커밋된 트랜잭션이고, 에지는 겉으로 드러나는 실행 순서를 인코딩한다. README-SSI는 Fekete 외의 분류를 따라 에지 세 종류를 구별한다.

wr-의존성 — T1 ─wr─► T2: T2가 T1이 쓴 버전을 읽는다. T1이 T2의 스냅샷보다 먼저 커밋했으므로 이 에지는 항상 커밋 순서와 일치한다.
ww-의존성 — T1 ─ww─► T2: T2가 T1이 쓴 버전을 덮어쓴다. 마찬가지로 T1이 먼저 커밋된다.
rw-충돌(rw-반의존성) — T1 ─rw─► T2: T1이 읽은 버전을 T2가 덮어쓴다(또는 T2의 쓰기가 먼저 반영됐다면 T1의 읽기 술어에 걸렸을 것이다). 이 에지는 시간을 거슬러 향할 수 있다는 점이 핵심이다. T1이 T2의 쓰기 이전 상태를 읽었기 때문에 순서상 먼저 실행된 것처럼 보이지만, 실제로는 T2보다 늦게 커밋할 수도 있다.

스케줄이 직렬화 가능한 충분 필요 조건은 MVSG가 비순환이라는 것이다. SI 아래에서 실제 커밋 순서와 반대 방향을 가질 수 있는 에지는 rw-반의존성뿐이다. 따라서 순환을 닫을 수 있는 에지도 rw-반의존성뿐이다. 이것이 쓰기 왜곡의 핵심 구조다. 두 트랜잭션이 서로의 “이전” 상태를 읽고 서로 다른 행을 쓰면 T1 ─rw─► T2 ─rw─► T1 순환이 생긴다.

Fekete, Liarokapis, O’Neil, O’Neil & Shasha(Making Snapshot Isolation Serializable, ACM TODS 30:2, 2005 — README-SSI의 [2])는 가장 날카로운 구조적 결론을 증명했다. SI 스케줄의 MVSG에 존재하는 모든 순환은 연속한 rw-반의존성 에지 두 개를 포함한다. 즉 rw-에지 하나가 들어오고 하나가 나가는 Tpivot이 반드시 존재한다. 가운데 트랜잭션이 피벗이다. Cahill 외의 SIGMOD 2008 기여는 이 정리를 저렴한 런타임 검사로 바꾼 것이다. 전체 그래프를 구체화해 순환을 찾는 대신, rw-반의존성만 증분 추적하면서 피벗이 인바운드·아웃바운드 rw-에지를 모두 갖게 될 때 실패를 선언한다. 모든 피벗이 실제 순환 위에 있지는 않으므로 **거짓 양성(false positive)**이 발생하지만, 거짓 음성은 없다. README-SSI는 이 절충을 명시한다. “거짓 양성 비율이 실제 환경에서 낮으므로, 탐지 오버헤드를 낮게 유지하는 허용 가능한 절충이다.”

커밋 순서 정제(Theorem 2.1)

단순 피벗 검사는 너무 이른 중단을 유발한다. Fekete 외의 Theorem 2.1은 PostgreSQL이 활용하는 타이밍 조건을 덧붙인다. 실제 순환 위에 있는 위험 구조 Tin ─rw─► Tpivot ─rw─► Tout에서 Tout이 셋 중 가장 먼저 커밋해야 한다는 것이다. PostgreSQL은 아웃 측 파트너가 실제로 커밋하기 전까지는 누구도 중단하지 않는다 (OnConflict_CheckForSerializationFailure의 SXACT_FLAG_DOOMED/커밋 시점 검사). 커밋 순서는 SerCommitSeqNo로 이미 추적되고 있으므로, 이 정제 하나로 거짓 양성 상당 부분이 제거된다.

Berenson 외와 “ANSI SERIALIZABLE”의 한계

PostgreSQL이 SSI를 필요로 하게 된 연원은 Berenson, Bernstein, Gray, Melton, O’Neil & O’Neil, A Critique of ANSI SQL Isolation Levels (SIGMOD 1995)로 거슬러 올라간다. 이 논문은 ANSI SQL-92 격리 수준 정의—P1/P2/P3(더티 읽기, 반복 불가능 읽기, 팬텀) 현상으로 기술된—가 모호하고, 결정적으로 스냅샷 격리를 특정하지 못한다는 점을 보였다. SI는 세 가지 ANSI 현상을 모두 차단하면서도 쓰기 왜곡(A5B)과 읽기 전용 트랜잭션 이상 현상을 허용한다. 따라서 벤더가 SI를 “SERIALIZABLE”로 표기해도 진정한 직렬화 가능성을 위반할 수 있었다. PostgreSQL은 9.1 이전이 정확히 그 상황이었다. SSI가 이 간격을 닫았다. REPEATABLE READ는 기존 SI 동작을 유지하고(ANSI REPEATABLE READ 정의보다 실제로 강하다), SERIALIZABLE은 rw-반의존성 모니터를 추가한다.

읽기 전용 트랜잭션 최적화

README-SSI의 SSI 알고리즘 절에는 Cahill/Fekete 논문에는 없는 정제가 기록되어 있다. Tin이 읽기 전용이라면, Tout이 Tin의 스냅샷 획득 이전에 커밋한 경우에만 이상 현상이 가능하다는 것이다. README-SSI에 재현된 증명은 다음과 같이 관찰한다. 순환에서 읽기 전용 Tin으로 들어오는 에지는 rw- 또는 ww-에지일 수 없다. 읽기 전용 트랜잭션은 아무것도 쓰지 않기 때문이다. 따라서 그 에지는 wr-의존성이고, 선행자가 Tin의 스냅샷 이전에 커밋했음을 강제한다. “Tout이 먼저 커밋” 규칙과 결합하면, Tout이 Tin의 스냅샷 이전에 커밋했어야 한다. 이것이 DEFERRABLE READ ONLY 안전 스냅샷의 근거이며, 일반 읽기 전용 트랜잭션이 충돌 부기의 상당 부분을 건너뛸 수 있는 이유다. Ports & Grittner, Serializable Snapshot Isolation in PostgreSQL(VLDB 2012)이 이 엔지니어링 정제들과 측정 오버헤드의 권위 있는 기록이다.

**술어 잠금(predicate locking)**은 SSI의 전제 조건이다. 읽기가 쓰기보다 먼저 발생할 때 rw-충돌을 탐지하려면, 각 트랜잭션이 무엇을 읽었는지를 기록해야 한다. 개별 튜플이 아니라 해당 스캔이 반환했을 튜플 집합을 포괄하는 “술어”를 커버해야 한다. 이후 그 술어 범위에 쓰는 행위가 잠재적 rw-충돌이 된다. 술어 잠금의 정확한 구현은 어렵기 때문에, PostgreSQL은 물리적 객체(관계, 페이지, 튜플)에 대한 잠금으로 술어를 보수적으로 근사한다. 거짓 양성 rw-충돌이 일부 발생하는 대신 구현이 단순해진다. Hellerstein, Stonebraker & Hamilton의 Architecture of a Database System(§6.5.3, “Next-Key Locking: Physical Surrogates for Logical Properties” — README-SSI 의 [3])이 이 물리적 대리 기법의 표준 참고 문헌이며, SIREAD 잠금은 그 비블록 변형이다.

DBMS 공통 설계 패턴

SSI는 PostgreSQL 고유 설계가 아니라 일반적인 프레임워크다. MVCC 엔진이 SSI를 구현할 때 공통적으로 채택하는 설계 관습이 있다.

트랜잭션별 충돌 레코드

직렬화 가능 트랜잭션마다 스냅샷 이상의 부기가 필요하다. 나가는 rw-충돌 목록(내가 읽은 뒤 상대방이 나중에 쓴 경우)과 들어오는 rw-충돌 목록(상대방이 읽은 뒤 내가 나중에 쓴 경우)이다. 어떤 트랜잭션에 충돌-인(in)과 충돌-아웃(out)이 동시에 존재하고, 아웃 측 상대가 이미 커밋했다면 위험 구조가 성립한다.

잠금 단위 승격

읽은 튜플 하나하나를 메모리에 추적하는 것은 규모가 커지면 불가능하다. 표준적인 해결책이 다중 단위 잠금 계층이다. 먼저 튜플 단위로 잠금을 시도하고, 누적 개수가 임계치를 넘으면 페이지 단위 잠금으로 승격하며, 페이지 잠금도 넘치면 관계 전체 잠금으로 승격한다. 잠금 단위가 거칠수록 거짓 양성 충돌이 늘지만 메모리 사용량이 제한된다.

SIREAD 잠금 대 헤비웨이트 잠금

SSI용 술어 잠금은 헤비웨이트(S2PL형) 잠금과 근본적으로 다르다. 블록하지 않는다는 점이다. SIREAD 잠금은 잠금이라기보다 플래그에 가깝다. “이 트랜잭션이 이 객체를 읽었다”는 사실을 기록해, 나중에 같은 객체에 쓰는 트랜잭션이 rw-충돌을 발견할 수 있게 한다. 대기 큐도 없고 블로킹도 없고 데드락도 없다. 구조체와 코드 경로는 일반 잠금 관리자와 반드시 분리된다.

커밋된 트랜잭션 상태의 수명

트랜잭션의 충돌 정보는 트랜잭션 자체보다 오래 살아야 한다. 커밋된 트랜잭션도 아직 커밋하지 않은 병행 직렬화 가능 트랜잭션의 위험 구조 일부일 수 있기 때문이다. 상태를 언제 회수할지에 대한 정책이 필요하다. 표준 접근법은 가장 오래된 활성 직렬화 가능 트랜잭션의 스냅샷 xmin보다 오래되지 않은 모든 트랜잭션의 상태를 유지하는 것이다.

DEFERRABLE READ ONLY 최적화

읽기 전용 트랜잭션은 그 자체로 쓰기 왜곡 이상 현상을 일으킬 수 없다. 모든 병행 읽기-쓰기 트랜잭션이 나가는 충돌 없이 커밋을 마친 뒤 시작한다면, 그 스냅샷은 **안전(safe)**하다. 안전한 스냅샷 위에서는 술어 잠금 추적을 건너뛸 수 있다. READ ONLY DEFERRABLE 트랜잭션은 안전한 스냅샷이 생길 때까지 시작을 미룬다. 지연 비용이 있지만, 그 트랜잭션에 대한 SSI 오버헤드를 완전히 제거한다.

PostgreSQL의 구현

PostgreSQL의 SSI 구현은 거의 전부 storage/lmgr/predicate.c(약 4,700줄)에 들어 있다. 같은 디렉터리의 README-SSI가 권위 있는 설계 문서다. 아래는 핵심 아키텍처 선택을 요약한 것이다.

공유 메모리 구조

SSI를 떠받치는 공유 메모리 객체는 여섯 가지다.

flowchart TD
  PX["PredXactList\n(PredXact)\nactiveList + availableList\nSxactGlobalXmin, WritableSxactCount\nLastSxactCommitSeqNo"]
  SX["SERIALIZABLEXACT[]\n(풀 할당)\nvxid, topXid, xmin, flags\noutConflicts, inConflicts\npredicateLocks"]
  SXH["SerializableXidHash\nxid -> SERIALIZABLEXACT*"]
  PLT["PredicateLockTargetHash\nPREDICATELOCKTARGETTAG -> PREDICATELOCKTARGET\n(타깃 해시로 파티셔닝)"]
  PL["PredicateLockHash\n(PREDICATELOCKTARGET*, SERIALIZABLEXACT*) -> PREDICATELOCK"]
  SLRU["SerialSlruCtl\n오래된 커밋 트랜잭션 상태\nxid -> SerCommitSeqNo"]
  PX -- "풀" --> SX
  SX -- "조회" --> SXH
  SX -- "잠금 목록" --> PL
  PLT -- "앵커" --> PL
  PX -- "오버플로" --> SLRU

PredXactList는 전역 카운터와 두 개의 free/active SERIALIZABLEXACT 슬롯 목록을 담는 단일 공유 구조체다. SerializableXidHash는 트랜잭션의 최상위 XID를 SERIALIZABLEXACT로 매핑해, 쓰기 트랜잭션이 읽기 트랜잭션의 레코드를 빠르게 찾을 수 있게 한다. 술어 잠금 테이블은 헤비웨이트 잠금 테이블처럼 파티셔닝되어 있다. NUM_PREDICATELOCK_PARTITIONS개의 파티션이 각자 LWLock으로 보호된다.

SERIALIZABLEXACT — 트랜잭션별 SSI 레코드

// SERIALIZABLEXACT — src/include/storage/predicate_internals.h
typedef struct SERIALIZABLEXACT
{
    VirtualTransactionId vxid;
    SerCommitSeqNo prepareSeqNo;
    SerCommitSeqNo commitSeqNo;
    union {
        SerCommitSeqNo earliestOutConflictCommit;
        SerCommitSeqNo lastCommitBeforeSnapshot;
    } SeqNo;
    dlist_head  outConflicts;      /* rw-conflicts where this txn is the reader */
    dlist_head  inConflicts;       /* rw-conflicts where this txn is the writer */
    dlist_head  predicateLocks;    /* SIREAD locks held */
    dlist_head  possibleUnsafeConflicts; /* for READ ONLY safe-snapshot tracking */
    TransactionId topXid;
    TransactionId finishedBefore;
    TransactionId xmin;
    uint32      flags;             /* SXACT_FLAG_* bitmask */
    int         pid;
    int         pgprocno;
} SERIALIZABLEXACT;

주요 플래그는 SXACT_FLAG_COMMITTED, SXACT_FLAG_DOOMED(다음 검사에서 중단 예정), SXACT_FLAG_READ_ONLY, SXACT_FLAG_RO_SAFE(조기 잠금 해제 가능), SXACT_FLAG_CONFLICT_OUT(먼저 커밋한 트랜잭션으로의 충돌-아웃 보유)이다.

SIREAD 잠금 구조체

// PREDICATELOCKTARGET — src/include/storage/predicate_internals.h
typedef struct PREDICATELOCKTARGET {
    PREDICATELOCKTARGETTAG tag;    /* db + rel + blkno + offset; field4 invalid => page; field3+4 invalid => relation */
    dlist_head  predicateLocks;
} PREDICATELOCKTARGET;

// PREDICATELOCK — src/include/storage/predicate_internals.h
typedef struct PREDICATELOCK {
    PREDICATELOCKTAG tag;          /* (myTarget*, myXact*) */
    dlist_node  targetLink;
    dlist_node  xactLink;
    SerCommitSeqNo commitSeqNo;    /* set when owner commits; used for summarization */
} PREDICATELOCK;

각 백엔드는 공유 메모리에 접근하지 않고도 잠금 개수를 파악하기 위해 LocalPredicateLockHash(LOCALPREDICATELOCK)를 로컬에 유지한다. 이 해시가 단위 승격 결정의 근거다. 특정 페이지에 대한 튜플 수준 잠금 개수가 max_predicate_locks_per_page를 초과하면, CheckAndPromotePredicateLockRequest가 해당 잠금들을 단일 페이지 잠금으로 올린다.

세 가지 단위에서의 SIREAD 잠금 획득

공개 진입점 세 개는 요청 단위에 맞는 PREDICATELOCKTARGETTAG를 구성해 공통 PredicateLockAcquire로 전달하는 얇은 래퍼다. 차이는 어느 SET_*TAG 매크로를 호출하는지와 조기 종료 조건뿐이다. PredicateLockTID는 로직이 가장 많다. 이 트랜잭션이 직접 쓴 튜플이거나 관계 수준 잠금이 이미 커버하는 경우 건너뛰기 때문이다.

// PredicateLockTID — src/backend/storage/lmgr/predicate.c
void
PredicateLockTID(Relation relation, ItemPointer tid, Snapshot snapshot,
                 TransactionId tuple_xid)
{
    PREDICATELOCKTARGETTAG tag;

    if (!SerializationNeededForRead(relation, snapshot))
        return;

    /* If we wrote it; we already have a write lock. */
    if (relation->rd_index == NULL)
        if (TransactionIdIsCurrentTransactionId(tuple_xid))
            return;

    /* Quick (non-definitive) check for a relation-level lock first. */
    SET_PREDICATELOCKTARGETTAG_RELATION(tag, relation->rd_locator.dbOid,
                                        relation->rd_id);
    if (PredicateLockExists(&tag))
        return;

    SET_PREDICATELOCKTARGETTAG_TUPLE(tag, relation->rd_locator.dbOid,
                                     relation->rd_id,
                                     ItemPointerGetBlockNumber(tid),
                                     ItemPointerGetOffsetNumber(tid));
    PredicateLockAcquire(&tag);
}

PredicateLockAcquire에서 SIREAD 잠금이 실제로 등록된다. 두 가지 단락 조건이 획득을 멱등하게 만들며, README의 규칙(“같은 트랜잭션이 페이지나 관계 잠금을 이미 보유하면 튜플 잠금 시도는 무시된다”)을 구현한다.

// PredicateLockAcquire — src/backend/storage/lmgr/predicate.c
static void
PredicateLockAcquire(const PREDICATELOCKTARGETTAG *targettag)
{
    uint32      targettaghash;
    bool        found;
    LOCALPREDICATELOCK *locallock;

    /* Do we have the lock already, or a covering lock? */
    if (PredicateLockExists(targettag))
        return;
    if (CoarserLockCovers(targettag))
        return;

    targettaghash = PredicateLockTargetTagHashCode(targettag);

    /* Record in the per-backend local table (drives promotion). */
    locallock = (LOCALPREDICATELOCK *)
        hash_search_with_hash_value(LocalPredicateLockHash, targettag,
                                    targettaghash, HASH_ENTER, &found);
    locallock->held = true;
    if (!found)
        locallock->childLocks = 0;

    /* Actually create the lock in shared memory. */
    CreatePredicateLock(targettag, targettaghash, MySerializableXact);

    /* Promote to coarser granularity, or clean up finer locks. */
    if (CheckAndPromotePredicateLockRequest(targettag))
        ; /* promoted: parent acquire deleted this lock and its children */
    else if (GET_PREDICATELOCKTARGETTAG_TYPE(*targettag) != PREDLOCKTAG_TUPLE)
        DeleteChildTargetLocks(targettag);
}

단위 승격 상세

CheckAndPromotePredicateLockRequest는 백엔드 로컬 해시에서 부모 체인 (튜플 → 페이지 → 관계)을 따라 올라가며 각 조상의 childLocks 카운터를 증가시킨다. MaxPredicateChildLocks(max_predicate_locks_per_page / max_predicate_locks_per_relation에서 파생)를 초과한 가장 거친 조상으로 승격한다.

// CheckAndPromotePredicateLockRequest — src/backend/storage/lmgr/predicate.c
static bool
CheckAndPromotePredicateLockRequest(const PREDICATELOCKTARGETTAG *reqtag)
{
    PREDICATELOCKTARGETTAG targettag, nexttag, promotiontag;
    LOCALPREDICATELOCK *parentlock;
    bool        found, promote = false;

    targettag = *reqtag;

    /* check parents iteratively */
    while (GetParentPredicateLockTag(&targettag, &nexttag))
    {
        targettag = nexttag;
        parentlock = (LOCALPREDICATELOCK *)
            hash_search(LocalPredicateLockHash, &targettag, HASH_ENTER, &found);
        if (!found) { parentlock->held = false; parentlock->childLocks = 1; }
        else        parentlock->childLocks++;

        if (parentlock->childLocks > MaxPredicateChildLocks(&targettag))
        {
            promotiontag = targettag;   /* keep climbing for child counts */
            promote = true;
        }
    }

    if (promote)
    {
        PredicateLockAcquire(&promotiontag);   /* acquire coarsest eligible */
        return true;
    }
    return false;
}

트랜잭션 생애주기

스냅샷 획득 — GetSerializableTransactionSnapshot이 SERIALIZABLEXACT를 할당하고 PredXact->activeList에 연결한 뒤 outConflicts, inConflicts, predicateLocks를 초기화한다. 읽기 전용 트랜잭션인데 활성 쓰기 가능 직렬화 가능 트랜잭션이 없다면(WritableSxactCount == 0), 안전한 스냅샷을 즉시 부여하고 추적 기계에 진입하지 않는다.
읽기 — SIREAD 잠금 획득 — 테이블 AM이 PredicateLockRelation, PredicateLockPage, 또는 PredicateLockTID를 호출한다. 이들은 PredicateLockAcquire로 이어져 공유 해시에 PREDICATELOCK을, 로컬 해시에 LOCALPREDICATELOCK을 삽입한다. 더 거친 단위의 잠금이 이미 타깃을 커버하고 있으면 획득 자체가 생략된다.
쓰기 — 충돌-아웃 탐지 — 테이블 AM이 다른 병행 트랜잭션이 쓴 튜플 버전을 읽으면 CheckForSerializableConflictOut을 호출한다. 쓴 트랜잭션의 SERIALIZABLEXACT를 조회해 두 트랜잭션이 병행 중임을 확인하면 FlagRWConflict(MySerializableXact, writer_sxact)를 호출한다. 여기서 MySerializableXact가 읽기 측(아웃 측)이 된다.
쓰기 — 충돌-인 탐지 — 테이블 AM이 튜플을 쓸 때 CheckForSerializableConflictIn을 호출한다. 이 함수는 PredicateLockTargetHash에서 해당 타깃의 SIREAD 잠금을 모두 스캔해, 병행 직렬화 가능 트랜잭션이 보유한 잠금마다 FlagRWConflict(reader_sxact, MySerializableXact)를 호출한다.
위험 구조 확인 — FlagRWConflict는 에지를 기록하기 전에 OnConflict_CheckForSerializationFailure를 먼저 호출한다(아래 전용 절에서 전체 발췌 제시).
커밋 직전 검사 — PreCommit_CheckForSerializationFailure는 커밋 시점에 실행된다. 이 트랜잭션이 Tout 역할이고, 충돌-인 상대방에 위험 구조를 완성하는 충돌-인이 존재하는 경우를 잡아낸다.
잠금 해제와 요약 — ReleasePredicateLocks가 커밋 또는 롤백 시 실행된다. 커밋 시 PREDICATELOCK 항목은 즉시 해제되지 않고 OldCommittedSxact로 이전되며 commitSeqNo가 설정된다. 메모리 압박이 커지면 SummarizeOldestCommittedSxact가 가장 오래된 커밋 트랜잭션의 충돌 상태를 SLRU 기반 직렬 로그(SerialSlruCtl)에 밀어 넣고 RAM을 회수한다. CheckForSerializableConflictOut은 쓴 트랜잭션의 SERIALIZABLEXACT가 해시에 없을 때 직렬 로그를 확인한다 (SerialGetMinConflictCommitSeqNo).

rw-충돌 그래프와 위험 구조

flowchart LR
  Tin["Tin\n(읽기 측)"]
  Tpivot["Tpivot\n(읽기+쓰기)"]
  Tout["Tout\n(쓰기 측, 먼저 커밋)"]
  Tin -- "rw-충돌 아웃" --> Tpivot
  Tpivot -- "rw-충돌 아웃" --> Tout

Tout이 Tpivot과 Tin보다 먼저 커밋해야 위험 구조가 실제 이상 현상으로 이어진다(Fekete 외, Theorem 2.1). PostgreSQL은 README-SSI에서 소개된 두 가지 추가 최적화를 활용한다.

Tout-먼저-커밋 가드: 충돌-아웃 상대방이 커밋하기 전까지는 트랜잭션을 중단하지 않는다. 조기 중단을 막는다.
읽기 전용 최적화: Tin이 읽기 전용이라면, Tout이 Tin의 스냅샷 획득 이전에 커밋한 경우에만 이상 현상이 가능하다. 모든 병행 읽기-쓰기 직렬화 가능 트랜잭션이 나가는 충돌 없이 커밋한 뒤 시작한 읽기 전용 트랜잭션은 추적에서 완전히 제외된다 (GetSerializableTransactionSnapshotInt의 SXACT_FLAG_RO_SAFE 경로).

에지 기록: SetRWConflict

에지는 RWConflictPool에서 꺼낸 RWConflictData 하나를 읽기 측의 outConflicts와 쓰기 측의 inConflicts 양쪽에 이중 연결하는 방식으로 기록된다. 별도의 인접 행렬은 없다. 그래프 자체가 SERIALIZABLEXACT마다 달린 두 개의 침입형 목록이다. 풀이 고갈되면 조용한 누락이 아니라 하드 에러가 발생한다. 에지가 빠지면 이상 현상이 놓이기 때문이다.

// SetRWConflict — src/backend/storage/lmgr/predicate.c
static void
SetRWConflict(SERIALIZABLEXACT *reader, SERIALIZABLEXACT *writer)
{
    RWConflict  conflict;

    Assert(reader != writer);
    Assert(!RWConflictExists(reader, writer));

    if (dlist_is_empty(&RWConflictPool->availableList))
        ereport(ERROR,
                (errcode(ERRCODE_OUT_OF_MEMORY),
                 errmsg("not enough elements in RWConflictPool to record a read/write conflict"),
                 errhint("You might need to run fewer transactions at a time or increase \"max_connections\".")));

    conflict = dlist_head_element(RWConflictData, outLink, &RWConflictPool->availableList);
    dlist_delete(&conflict->outLink);

    conflict->sxactOut = reader;                       /* edge tail = reader */
    conflict->sxactIn = writer;                        /* edge head = writer */
    dlist_push_tail(&reader->outConflicts, &conflict->outLink);
    dlist_push_tail(&writer->inConflicts, &conflict->inLink);
}

충돌-아웃: 읽기 측이 병행 쓰기 측을 발견한다

CheckForSerializableConflictOut은 테이블 AM이 다른 트랜잭션의 xmin/xmax를 가진 튜플 버전을 읽을 때 호출된다. 쓰기 측을 최상위 XID로 조회한다. 먼저 SerializableXidHash에서 찾고, 이미 직렬 로그로 요약된 경우 SerialGetMinConflictCommitSeqNo로 확인한다. 읽기 전용 단락 조건은 README-SSI의 원래 최적화를 구현한다.

// CheckForSerializableConflictOut — src/backend/storage/lmgr/predicate.c
void
CheckForSerializableConflictOut(Relation relation, TransactionId xid, Snapshot snapshot)
{
    /* ... lookup SERIALIZABLEXACT *sxact for top-level xid ... */

    /* If this is read-only and the writer committed without an earlier
     * out-conflict, the reader simply appears to run first: no conflict. */
    if (SxactIsReadOnly(MySerializableXact)
        && SxactIsCommitted(sxact)
        && !SxactHasSummaryConflictOut(sxact)
        && (!SxactHasConflictOut(sxact)
            || MySerializableXact->SeqNo.lastCommitBeforeSnapshot < sxact->SeqNo.earliestOutConflictCommit))
    {
        LWLockRelease(SerializableXactHashLock);
        return;
    }

    if (!XidIsConcurrent(xid)) {            /* write was already in our snapshot */
        LWLockRelease(SerializableXactHashLock);
        return;
    }
    if (RWConflictExists(MySerializableXact, sxact)) {   /* no duplicate edges */
        LWLockRelease(SerializableXactHashLock);
        return;
    }
    /* ... FlagRWConflict(MySerializableXact, sxact)  — we are the reader ... */
}

충돌-인: 쓰기 측이 기존 SIREAD 잠금을 탐색한다

CheckForSerializableConflictIn은 튜플을 쓸 때 호출된다. 술어 잠금 해시를 가장 세밀한 단위부터 탐색한다. 튜플 → 페이지 → 관계 순서가 중요한 이유가 있다. 병행 단위 승격은 거친 잠금을 획득한 뒤 세밀한 잠금을 해제하기 때문에, 세밀 → 거친 순으로 탐색하면 누락이 없다.

// CheckForSerializableConflictIn — src/backend/storage/lmgr/predicate.c
void
CheckForSerializableConflictIn(Relation relation, ItemPointer tid, BlockNumber blkno)
{
    PREDICATELOCKTARGETTAG targettag;

    if (!SerializationNeededForWrite(relation))
        return;
    if (SxactIsDoomed(MySerializableXact))
        ereport(ERROR, (errcode(ERRCODE_T_R_SERIALIZATION_FAILURE), /* pivot, during conflict in */ ...));

    MyXactDidWrite = true;

    if (tid != NULL) {            /* finest: tuple */
        SET_PREDICATELOCKTARGETTAG_TUPLE(targettag, relation->rd_locator.dbOid,
            relation->rd_id, ItemPointerGetBlockNumber(tid), ItemPointerGetOffsetNumber(tid));
        CheckTargetForConflictsIn(&targettag);
    }
    if (blkno != InvalidBlockNumber) {    /* page */
        SET_PREDICATELOCKTARGETTAG_PAGE(targettag, relation->rd_locator.dbOid,
            relation->rd_id, blkno);
        CheckTargetForConflictsIn(&targettag);
    }
    SET_PREDICATELOCKTARGETTAG_RELATION(targettag, relation->rd_locator.dbOid,
        relation->rd_id);                 /* coarsest: relation */
    CheckTargetForConflictsIn(&targettag);
}

CheckTargetForConflictsIn은 타깃별 내부 루프다. 해당 타깃에 잠금을 보유한 관련 병행 트랜잭션(소멸 예정이 아니고, 커밋 안 됐거나 최근 커밋) 마다 FlagRWConflict(reader, me)로 인바운드 에지를 기록한다. 이제 내가 쓰는 튜플에 내 SIREAD 잠금이 있다면 제거한다. README의 “쓰기 잠금이 SIREAD 잠금을 대체한다” 최적화다.

// CheckTargetForConflictsIn — src/backend/storage/lmgr/predicate.c
dlist_foreach_modify(iter, &target->predicateLocks)
{
    PREDICATELOCK *predlock = dlist_container(PREDICATELOCK, targetLink, iter.cur);
    SERIALIZABLEXACT *sxact = predlock->tag.myXact;

    if (sxact == MySerializableXact) {
        /* our own SIREAD lock on a tuple we're writing — defer removal */
        if (!IsSubTransaction() && GET_PREDICATELOCKTARGETTAG_OFFSET(*targettag))
            { mypredlock = predlock; mypredlocktag = predlock->tag; }
    }
    else if (!SxactIsDoomed(sxact)
             && (!SxactIsCommitted(sxact)
                 || TransactionIdPrecedes(GetTransactionSnapshot()->xmin, sxact->finishedBefore))
             && !RWConflictExists(sxact, MySerializableXact))
    {
        /* upgrade to exclusive, re-check, then flag the inbound edge */
        FlagRWConflict(sxact, MySerializableXact);
    }
}

플래깅과 위험 구조 탐지기

FlagRWConflict는 단일 병목 지점이다. 먼저 OnConflict_CheckForSerializationFailure로 새 에지가 피벗을 완성하는지 확인한 뒤, 한쪽이 이미 OldCommittedSxact로 요약된 경우 실제 에지 대신 요약 충돌 플래그를 설정한다.

// FlagRWConflict — src/backend/storage/lmgr/predicate.c
static void
FlagRWConflict(SERIALIZABLEXACT *reader, SERIALIZABLEXACT *writer)
{
    Assert(reader != writer);

    /* First, see if this conflict causes failure. */
    OnConflict_CheckForSerializationFailure(reader, writer);

    /* Actually do the conflict flagging. */
    if (reader == OldCommittedSxact)
        writer->flags |= SXACT_FLAG_SUMMARY_CONFLICT_IN;
    else if (writer == OldCommittedSxact)
        reader->flags |= SXACT_FLAG_SUMMARY_CONFLICT_OUT;
    else
        SetRWConflict(reader, writer);
}

탐지기는 새 reader ─rw─► writer 에지가 위험 구조를 닫는 세 가지 방식을 검사한다. 세 번째 경우—읽기 측이 피벗이 되는 경우(T0 ─rw─► reader ─rw─► writer)—가 미묘하다. 읽기 측의 기존 inConflicts를 순회하며 쓰기 측보다 안전하게 먼저 커밋하지 않은 T0를 찾는다.

// OnConflict_CheckForSerializationFailure — src/backend/storage/lmgr/predicate.c
static void
OnConflict_CheckForSerializationFailure(const SERIALIZABLEXACT *reader,
                                        SERIALIZABLEXACT *writer)
{
    bool        failure = false;
    Assert(LWLockHeldByMe(SerializableXactHashLock));

    /* Case 1: writer already committed and has a conflict out (R->W->T2). */
    if (SxactIsCommitted(writer)
        && (SxactHasConflictOut(writer) || SxactHasSummaryConflictOut(writer)))
        failure = true;

    /* Case 2: writer is the pivot — walk its outConflicts for a T2 that
     * committed/prepared first (R->W->T2). */
    if (!failure && SxactHasSummaryConflictOut(writer))
        failure = true;
    else if (!failure) {
        dlist_foreach(iter, &writer->outConflicts) {
            SERIALIZABLEXACT *t2 = dlist_container(RWConflictData, outLink, iter.cur)->sxactIn;
            if (SxactIsPrepared(t2)
                && (!SxactIsCommitted(reader) || t2->prepareSeqNo <= reader->commitSeqNo)
                && (!SxactIsCommitted(writer) || t2->prepareSeqNo <= writer->commitSeqNo)
                && (!SxactIsReadOnly(reader)  || t2->prepareSeqNo <= reader->SeqNo.lastCommitBeforeSnapshot))
            { failure = true; break; }
        }
    }

    /* Case 3: reader is the pivot — walk its inConflicts for a T0
     * (T0->R->W), writer prepared, reader not read-only. */
    if (!failure && SxactIsPrepared(writer) && !SxactIsReadOnly(reader)) {
        if (SxactHasSummaryConflictIn(reader)) failure = true;
        else dlist_foreach(iter, &unconstify(SERIALIZABLEXACT *, reader)->inConflicts) {
            const SERIALIZABLEXACT *t0 = dlist_container(RWConflictData, inLink, iter.cur)->sxactOut;
            if (!SxactIsDoomed(t0)
                && (!SxactIsCommitted(t0)  || t0->commitSeqNo >= writer->prepareSeqNo)
                && (!SxactIsReadOnly(t0)   || t0->SeqNo.lastCommitBeforeSnapshot >= writer->prepareSeqNo))
            { failure = true; break; }
        }
    }

    if (failure) {
        if (MySerializableXact == writer)
            ereport(ERROR, (errcode(ERRCODE_T_R_SERIALIZATION_FAILURE), /* pivot during write */ ...));
        else if (SxactIsPrepared(writer))
            ereport(ERROR, ...);              /* writer prepared: we must be the reader */
        else
            writer->flags |= SXACT_FLAG_DOOMED;   /* defer abort to writer's commit */
    }
}

SXACT_FLAG_DOOMED 분기가 “Tout 먼저 커밋” 원칙의 핵심이다. 패턴이 나타나는 즉시 중단하지 않고 피벗을 소멸 예정으로 표시해, 실제 중단은 나중에(CheckForSerializableConflictIn/Out 또는 PreCommit_*에서) 발생하게 한다. 그때는 아웃 측 파트너가 먼저 커밋했음이 확실해진다.

flowchart TD
  READ["table AM reads a tuple<br/>written by another xact"] --> COUT["CheckForSerializableConflictOut"]
  WRITE["table AM writes a tuple"] --> CIN["CheckForSerializableConflictIn"]
  COUT --> COUTQ{"writer concurrent<br/>and no dup edge?"}
  COUTQ -->|"yes"| FLAG["FlagRWConflict<br/>(reader=me, writer)"]
  CIN --> CTGT["CheckTargetForConflictsIn<br/>tuple -> page -> relation"]
  CTGT --> CINQ{"SIREAD lock by live<br/>concurrent xact?"}
  CINQ -->|"yes"| FLAG2["FlagRWConflict<br/>(reader, writer=me)"]
  FLAG --> OCF["OnConflict_CheckForSerializationFailure"]
  FLAG2 --> OCF
  OCF --> PIVOT{"dangerous structure?<br/>Tin rw Tpivot rw Tout<br/>Tout committed first"}
  PIVOT -->|"no"| REC["SetRWConflict<br/>record edge in pool"]
  PIVOT -->|"yes, I am writer"| ERR["ereport 40001<br/>serialization_failure"]
  PIVOT -->|"yes, writer prepared"| ERR
  PIVOT -->|"yes, otherwise"| DOOM["writer.flags |= SXACT_FLAG_DOOMED<br/>abort deferred to commit"]

커밋 직전: Tout 역할 포착

커밋하려는 트랜잭션이 피벗과 Tin이 아직 커밋하지 않은 구조의 Tout일 수 있다. 에지 기록 시점에는 어느 쪽도 커밋하지 않았기 때문에, 증분 에지 검사가 이 경우를 잡지 못했을 수 있다. PreCommit_CheckForSerializationFailure는 최종 검사를 수행하면서, 커밋 중인 트랜잭션이 아니라 피벗(가까운 충돌 쪽)을 소멸 예정으로 만든다. 커밋 중인 트랜잭션은 계속 진행하고, 피해자 재시도가 성공할 수 있게 한다.

// PreCommit_CheckForSerializationFailure — src/backend/storage/lmgr/predicate.c
void
PreCommit_CheckForSerializationFailure(void)
{
    dlist_iter  near_iter;
    if (MySerializableXact == InvalidSerializableXact)
        return;
    Assert(IsolationIsSerializable());
    LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);

    if (SxactIsDoomed(MySerializableXact) && !SxactIsPartiallyReleased(MySerializableXact)) {
        LWLockRelease(SerializableXactHashLock);
        ereport(ERROR, (errcode(ERRCODE_T_R_SERIALIZATION_FAILURE), /* pivot during commit */ ...));
    }

    /* For each in-edge (nearConflict->sxactOut = the pivot), look for a
     * far edge that closes T_far -> pivot -> me, with the far partner
     * still able to be the apparent-first transaction. */
    dlist_foreach(near_iter, &MySerializableXact->inConflicts) {
        RWConflict nearConflict = dlist_container(RWConflictData, inLink, near_iter.cur);
        if (!SxactIsCommitted(nearConflict->sxactOut) && !SxactIsDoomed(nearConflict->sxactOut)) {
            dlist_foreach(far_iter, &nearConflict->sxactOut->inConflicts) {
                RWConflict farConflict = dlist_container(RWConflictData, inLink, far_iter.cur);
                if (farConflict->sxactOut == MySerializableXact
                    || (!SxactIsCommitted(farConflict->sxactOut)
                        && !SxactIsReadOnly(farConflict->sxactOut)
                        && !SxactIsDoomed(farConflict->sxactOut))) {
                    if (SxactIsPrepared(nearConflict->sxactOut)) {
                        LWLockRelease(SerializableXactHashLock);
                        ereport(ERROR, ...);     /* pivot already prepared: commit suicide */
                    }
                    nearConflict->sxactOut->flags |= SXACT_FLAG_DOOMED;   /* doom the pivot */
                    break;
                }
            }
        }
    }

    MySerializableXact->prepareSeqNo = ++(PredXact->LastSxactCommitSeqNo);
    MySerializableXact->flags |= SXACT_FLAG_PREPARED;
    LWLockRelease(SerializableXactHashLock);
}

단위 승격

flowchart TD
  T["PredicateLockTID\n(튜플)"] --> P["PredicateLockPage\n(페이지)"]
  P --> R["PredicateLockRelation\n(관계)"]
  T -->|"childLocks > max_predicate_locks_per_page"| CAP["CheckAndPromotePredicateLockRequest\n자식 잠금 삭제,\n더 거친 잠금 생성"]
  P -->|"childLocks > max_predicate_locks_per_relation"| CAP

GUC 파라미터 max_predicate_locks_per_xact, max_predicate_locks_per_relation, max_predicate_locks_per_page가 승격 시점을 결정한다. PredicateLockShmemSize는 이 값들로부터 공유 해시 테이블 크기를 계산한다.

안전 스냅샷과 DEFERRABLE READ ONLY

읽기 전용 트랜잭션의 제외 경로는 두 가지이며, 모두 학술적 배경의 읽기 전용 정리에 근거한다.

즉시 제외는 GetSerializableTransactionSnapshotInt 내부에서 일어난다. 트랜잭션이 READ ONLY이고 활성 쓰기 가능 직렬화 가능 트랜잭션이 없으면 (WritableSxactCount == 0), 위험 구조에 결코 참여할 수 없으므로 SERIALIZABLEXACT 슬롯을 해제하고 SSI 부기 없이 순수 SI로 실행된다. 가능한 불안전 충돌을 등록한 뒤 모든 병행 쓰기 트랜잭션이 소멸 예정임을 확인하면 같은 제외가 적용된다.

// GetSerializableTransactionSnapshotInt — src/backend/storage/lmgr/predicate.c
if (XactReadOnly)
{
    sxact->flags |= SXACT_FLAG_READ_ONLY;

    /* Register all concurrent r/w transactions as possible conflicts; if
     * they all commit without an outgoing conflict to an earlier txn, this
     * snapshot is safe and we can run without tracking predicate locks. */
    dlist_foreach(iter, &PredXact->activeList)
    {
        othersxact = dlist_container(SERIALIZABLEXACT, xactLink, iter.cur);
        if (!SxactIsCommitted(othersxact)
            && !SxactIsDoomed(othersxact)
            && !SxactIsReadOnly(othersxact))
            SetPossibleUnsafeConflict(sxact, othersxact);
    }

    if (dlist_is_empty(&sxact->possibleUnsafeConflicts))
    {
        ReleasePredXact(sxact);                  /* every writer was doomed */
        LWLockRelease(SerializableXactHashLock);
        return snapshot;                         /* immediate opt-out */
    }
}

지연 경로는 READ ONLY DEFERRABLE에 쓰이는 GetSafeSnapshot이다. 추적을 진행하는 대신 기다린다. WAIT_EVENT_SAFE_SNAPSHOT에서 슬립하면서, 병행 쓰기 트랜잭션들이 빠져나가거나(possibleUnsafeConflicts 비움) 이 트랜잭션을 RO_UNSAFE로 표시할 때까지 대기한다. RO_UNSAFE가 설정되면 새 스냅샷으로 재시도한다. 지연 비용이 있지만, 이상 현상 가능성이 증명적으로 없는 읽기 전용 트랜잭션을 얻는다.

// GetSafeSnapshot — src/backend/storage/lmgr/predicate.c
static Snapshot
GetSafeSnapshot(Snapshot origSnapshot)
{
    Snapshot    snapshot;
    Assert(XactReadOnly && XactDeferrable);

    while (true)
    {
        snapshot = GetSerializableTransactionSnapshotInt(origSnapshot, NULL, InvalidPid);
        if (MySerializableXact == InvalidSerializableXact)
            return snapshot;          /* no concurrent r/w xacts; already safe */

        LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);
        MySerializableXact->flags |= SXACT_FLAG_DEFERRABLE_WAITING;
        while (!(dlist_is_empty(&MySerializableXact->possibleUnsafeConflicts)
                 || SxactIsROUnsafe(MySerializableXact)))
        {
            LWLockRelease(SerializableXactHashLock);
            ProcWaitForSignal(WAIT_EVENT_SAFE_SNAPSHOT);
            LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);
        }
        MySerializableXact->flags &= ~SXACT_FLAG_DEFERRABLE_WAITING;

        if (!SxactIsROUnsafe(MySerializableXact)) {
            LWLockRelease(SerializableXactHashLock);
            break;                    /* success: snapshot is safe */
        }
        LWLockRelease(SerializableXactHashLock);
        ReleasePredicateLocks(false, false);   /* unsafe; retry with a new snapshot */
    }

    Assert(SxactIsROSafe(MySerializableXact));
    ReleasePredicateLocks(false, true);
    return snapshot;
}

flowchart TD
  START["READ ONLY DEFERRABLE<br/>GetSafeSnapshot"] --> SNAP["GetSerializableTransactionSnapshotInt"]
  SNAP --> NOXACT{"MySerializableXact<br/>== Invalid?"}
  NOXACT -->|"yes: no concurrent r/w"| SAFE["return snapshot<br/>(SXACT_FLAG_RO_SAFE)"]
  NOXACT -->|"no"| WAIT["set DEFERRABLE_WAITING<br/>ProcWaitForSignal"]
  WAIT --> COND{"possibleUnsafeConflicts<br/>empty?"}
  COND -->|"yes"| SAFE
  COND -->|"flagged RO_UNSAFE"| RETRY["ReleasePredicateLocks<br/>retry new snapshot"]
  RETRY --> SNAP

인덱스 AM 연동

B-tree, GIN, GiST, hash 인덱스 스캔은 각각 다른 방식으로 PredicateLock*을 호출해 인덱스 항목 사이의 “간격(gap)“을 커버한다. 나중에 삽입되는 행이 스캔 범위에 들어올 경우 rw-충돌로 잡아내기 위해서다. B-tree와 GIN은 리프 페이지를 잠근다. GiST는 분할이 상위 레벨로 전파될 수 있으므로 모든 레벨의 페이지를 잠근다. hash는 기본 버킷 페이지를 잠근다. 술어 잠금 지원이 없는 인덱스 AM은 인덱스 관계 전체를 잠근다. 모든 AM의 페이지 분할과 병합은 PredicateLockPageSplit / PredicateLockPageCombine을 호출해 잠금을 새 페이지로 이전한다. 그렇지 않으면 rw-충돌이 조용히 누락된다.

LWLock 획득 순서

SSI 상태를 보호하는 LWLock은 래치 순서 데드락을 막기 위해 고정된 순서로 획득해야 한다(predicate.c 파일 헤더 주석).

SerializableFinishedListLock
  SerializablePredicateListLock
    perXactPredicateListLock  (병렬 쿼리에서만)
      PredicateLockHashPartitionLock(hashcode)
        SerializableXactHashLock
          SerialControlLock
            SLRU per-bank locks

2단계 커밋 지원

AtPrepare_PredicateLocks는 트랜잭션의 술어 잠금 상태를 2PC 상태 파일에 TwoPhasePredicateRecord 항목으로 직렬화한다. 트랜잭션당 TWOPHASEPREDICATERECORD_XACT 하나와 잠금당 TWOPHASEPREDICATERECORD_LOCK 하나다. predicatelock_twophase_recover가 복구 시 상태를 재구성한다. 충돌 목록은 포인터 대신 플래그(SXACT_FLAG_SUMMARY_CONFLICT_IN / SXACT_FLAG_SUMMARY_CONFLICT_OUT)로 요약된다. 재시작 후에는 원래 SERIALIZABLEXACT 객체가 존재하지 않기 때문이다.

소스 코드 가이드

공유 메모리 초기화

심볼	역할
`PredicateLockShmemInit`	시작 시 모든 SSI 공유 메모리 객체 할당
`PredicateLockShmemSize`	GUC 값으로부터 필요한 공유 메모리 크기 계산
`PredXact` (전역 `PredXactList`)	active/available sxact 풀의 루트 포인터
`SerializableXidHash`	XID → `SERIALIZABLEXACT*` 조회
`PredicateLockTargetHash`	`PREDICATELOCKTARGETTAG` → `PREDICATELOCKTARGET*`
`PredicateLockHash`	`(target, sxact)` → `PREDICATELOCK*`
`SerialSlruCtl`	오래된 커밋 트랜잭션 상태용 SLRU 버퍼
`OldCommittedSxact`	요약된 잠금을 쌓는 공유 더미 sxact

트랜잭션 생애주기

심볼	역할
`GetSerializableTransactionSnapshot`	공개 진입점; `GetSerializableTransactionSnapshotInt` 호출
`GetSerializableTransactionSnapshotInt`	`SERIALIZABLEXACT` 할당, READ ONLY용 `possibleUnsafeConflicts` 채우기; `WritableSxactCount == 0`이면 즉시 제외
`GetSafeSnapshot`	`READ ONLY DEFERRABLE` 경로; `WAIT_EVENT_SAFE_SNAPSHOT`에서 안전 스냅샷 대기
`SetPossibleUnsafeConflict`	RO 트랜잭션과 병행 쓰기 트랜잭션을 `possibleUnsafeConflicts`로 연결
`RegisterPredicateLockingXid`	첫 쓰기 시 `MySerializableXact`에 `topXid` 할당
`SerializationNeededForRead`	인라인 게이트: 직렬화 불필요 시 건너뜀
`SerializationNeededForWrite`	쓰기 경로용 인라인 게이트
`ReleasePredicateLocks`	커밋/롤백 정리; 잠금을 `OldCommittedSxact`로 이전
`SummarizeOldestCommittedSxact`	가장 오래된 완료 sxact를 SLRU로 밀고 RAM 회수

SIREAD 잠금 획득

심볼	역할
`PredicateLockRelation`	관계 단위 SIREAD 잠금 획득
`PredicateLockPage`	페이지 단위 SIREAD 잠금 획득
`PredicateLockTID`	튜플 단위 SIREAD 잠금 획득
`PredicateLockAcquire`	`PredicateLockTargetHash` + `PredicateLockHash`에 항목 삽입
`CoarserLockCovers`	더 거친 잠금이 요청 타깃을 이미 커버하는지 확인
`CheckAndPromotePredicateLockRequest`	`LocalPredicateLockHash`를 이용한 단위 승격 결정
`DeleteChildTargetLocks`	승격 후 세밀한 잠금 삭제
`LocalPredicateLockHash`	승격 휴리스틱용 백엔드 로컬 해시(`LOCALPREDICATELOCK`)

충돌 탐지

심볼	역할
`CheckForSerializableConflictOut`	읽기 경로: 쓴 트랜잭션의 xid → sxact 조회 → `FlagRWConflict(me, writer)`
`CheckForSerializableConflictIn`	쓰기 경로: 타깃의 술어 잠금 스캔 → `FlagRWConflict(reader, me)`
`CheckTargetForConflictsIn`	`CheckForSerializableConflictIn`의 단일 타깃 내부 루프
`CheckTableForSerializableConflictIn`	CLUSTER/REINDEX가 테이블 전체 충돌 검사 시 호출
`FlagRWConflict`	실패 검사 후 `SetRWConflict` 호출
`SetRWConflict`	풀에서 `RWConflictData` 할당, `outConflicts`/`inConflicts`에 연결
`OnConflict_CheckForSerializationFailure`	위험 구조 탐지기; `SXACT_FLAG_DOOMED` 설정 또는 ERROR 발생
`PreCommit_CheckForSerializationFailure`	Tout 역할에 대한 커밋 시점 검사

직렬 로그(SLRU 오버플로)

심볼	역할
`SerialControlData`	SLRU 윈도우의 `headPage`, `headXid`, `tailXid`
`SerialAdd`	커밋된 sxact의 `minConflictCommitSeqNo`를 SLRU에 기록
`SerialGetMinConflictCommitSeqNo`	오래된 xid의 충돌 정보를 직렬 로그에서 읽기
`SerialSetActiveSerXmin`	SLRU 테일 전진(오래된 페이지 회수)

주요 구조체와 매크로

심볼	역할
`SERIALIZABLEXACT`	직렬화 가능 트랜잭션별 SSI 부기
`PredXactListData`	전역 카운터와 sxact 풀 목록
`RWConflictData`	방향성 rw-충돌 에지 하나(reader → writer)
`PREDICATELOCKTARGET`	잠금 가능한 물리 객체 하나(관계/페이지/튜플)
`PREDICATELOCK`	(타깃, sxact) 잠금 바인딩 하나
`LOCALPREDICATELOCK`	승격 휴리스틱용 백엔드 로컬 잠금 카운트
`SerCommitSeqNo`	커밋 순서를 나타내는 단조 증가 `uint64`
`SxactIsCommitted`, `SxactIsDoomed`, `SxactIsROSafe`, …	`SXACT_FLAG_*` 테스트 매크로
`TargetTagIsCoveredBy`	한 태그가 다른 태그보다 거친 단위인지 확인하는 매크로
`PredicateLockHashPartitionLock`	타깃 해시 코드로부터 파티션 LWLock 반환

소스 검증 (2026-06-05 기준)

브랜치 REL_18_STABLE, 커밋 273fe94.

심볼	파일	줄
`SERIALIZABLEXACT`	`src/include/storage/predicate_internals.h`	58
`PredXactListData`	`src/include/storage/predicate_internals.h`	144
`RWConflictData`	`src/include/storage/predicate_internals.h`	193
`PREDICATELOCKTARGETTAG`	`src/include/storage/predicate_internals.h`	267
`PREDICATELOCKTARGET`	`src/include/storage/predicate_internals.h`	284
`PREDICATELOCK`	`src/include/storage/predicate_internals.h`	317
`LOCALPREDICATELOCK`	`src/include/storage/predicate_internals.h`	347
`PredicateLockTargetType`	`src/include/storage/predicate_internals.h`	361
`SerialControlData`	`src/backend/storage/lmgr/predicate.c`	345
`SerializationNeededForRead`	`src/backend/storage/lmgr/predicate.c`	516
`SerializationNeededForWrite`	`src/backend/storage/lmgr/predicate.c`	560
`SetRWConflict`	`src/backend/storage/lmgr/predicate.c`	643
`SetPossibleUnsafeConflict`	`src/backend/storage/lmgr/predicate.c`	666
`PredicateLockShmemInit`	`src/backend/storage/lmgr/predicate.c`	1145
`PredicateLockShmemSize`	`src/backend/storage/lmgr/predicate.c`	1357
`GetSafeSnapshot`	`src/backend/storage/lmgr/predicate.c`	1558
`GetSerializableTransactionSnapshot`	`src/backend/storage/lmgr/predicate.c`	1682
`GetSerializableTransactionSnapshotInt`	`src/backend/storage/lmgr/predicate.c`	1764
`RegisterPredicateLockingXid`	`src/backend/storage/lmgr/predicate.c`	1959
`CheckAndPromotePredicateLockRequest`	`src/backend/storage/lmgr/predicate.c`	2326
`PredicateLockAcquire`	`src/backend/storage/lmgr/predicate.c`	2517
`PredicateLockRelation`	`src/backend/storage/lmgr/predicate.c`	2576
`PredicateLockPage`	`src/backend/storage/lmgr/predicate.c`	2599
`PredicateLockTID`	`src/backend/storage/lmgr/predicate.c`	2621
`PredicateLockPageSplit`	`src/backend/storage/lmgr/predicate.c`	3144
`PredicateLockPageCombine`	`src/backend/storage/lmgr/predicate.c`	3229
`ReleasePredicateLocks`	`src/backend/storage/lmgr/predicate.c`	3312
`CheckForSerializableConflictOut`	`src/backend/storage/lmgr/predicate.c`	4023
`CheckTargetForConflictsIn`	`src/backend/storage/lmgr/predicate.c`	4166
`CheckForSerializableConflictIn`	`src/backend/storage/lmgr/predicate.c`	4336
`CheckTableForSerializableConflictIn`	`src/backend/storage/lmgr/predicate.c`	4419
`FlagRWConflict`	`src/backend/storage/lmgr/predicate.c`	4501
`OnConflict_CheckForSerializationFailure`	`src/backend/storage/lmgr/predicate.c`	4536
`PreCommit_CheckForSerializationFailure`	`src/backend/storage/lmgr/predicate.c`	4703

PostgreSQL 너머 — 비교 설계와 연구 프론티어

S2PL 대 SSI. 고전적인 대안은 엄격한 2단계 잠금(S2PL)이다. 읽기마다 공유 잠금을, 쓰기마다 배타 잠금을 획득하고 커밋까지 보유한다. S2PL은 직렬화 가능성을 당연히 보장하지만, 읽기가 쓰기와 블록된다. SSI는 읽기를 전혀 블록하지 않는다. 위험 구조 탐지 시 트랜잭션 하나를 중단하는 비용이 따른다. 읽기 집약적 워크로드에서는 SSI의 처리량이 우세하다. 쓰기가 많고 충돌이 잦은 워크로드에서는, 이미 작업을 수행한 트랜잭션이 중단되는 경우가 줄어들기 때문에 S2PL이 유리할 수 있다.

CockroachDB와 Spanner. CockroachDB는 분산 트랜잭션에 맞게 변형된 SSI 변형을 쓴다. 쓰기-쓰기 충돌에는 write-intent 메커니즘을, 술어 잠금 역할에는 timestamp cache를 활용한다. Google Spanner는 외부 일관성 타임스탬프를 결합한 S2PL을 쓴다. SSI를 구현하지 않는다.

MySQL/InnoDB는 SERIALIZABLE을 S2PL로 구현한다. 읽기에 공유 잠금을 걸고, B-tree 범위 커버리지에 next-key locking을 쓴다. next-key locking은 범위 술어 잠금의 물리적 구현에 해당한다. InnoDB의 trx_sys에는 SERIALIZABLEXACT와 유사한 트랜잭션별 충돌 상태가 있지만, 위험 구조 검사는 없다.

연구 동향: 거짓 양성 감소. PostgreSQL 구현은 rw-충돌만 추적하고 단순한 패턴 매칭을 수행한다. 더 정밀한 구현(Cahill 프로토타입의 상용 엔진 이식 등)은 더 풍부한 그래프를 유지해, 위험 구조가 실제 사이클에 포함되지 않음을 증명할 수 있는 경우 거짓 중단을 줄인다. 충돌 에지당 부기 비용이 높아지는 절충이 따른다.

연구 동향: 쓰기 왜곡 대 갱신 분실. 갱신 분실(lost update) 계열의 이상 현상은 SSI가 아니라 heap AM의 first-updater-wins 메커니즘 (heap_update의 HeapTupleUpdated 경로)이 막는다. SSI는 쓰기 왜곡과 그 일반화된 형태를 대상으로 한다. 두 이상 현상 유형과 스냅샷 격리의 상호작용은 postgres-mvcc-snapshots.md를 참고한다.

이론의 계보. 네 편의 논문이 하나의 연쇄를 이룬다. Berenson 외(SIGMOD 1995)는 ANSI의 현상 기반 정의가 SI를 특정하지 못하며 SI가 “SERIALIZABLE” 레이블이 배제하는 이상 현상(A5B 쓰기 왜곡)을 허용함을 보였다. 이것이 문제를 확립했다. Fekete 외(TODS 2005)는 구조적 정리를 제공했다. SI 스케줄의 모든 순환은 연속한 rw-반의존성 에지 두 개와 피벗을 포함하고, Tout이 먼저 커밋한다(Theorem 2.1). 무엇을 감시할지를 확립했다. Cahill, Röhm & Fekete(SIGMOD 2008)는 정리를 작은 거짓 양성률의 증분 저비용 런타임 모니터로 바꿨다. 저렴하게 감시하는 방법을 확립했다. Ports & Grittner(VLDB 2012)는 PostgreSQL 실현을 기록했다. SLRU 기반 직렬 로그로 RAM 제한, 다중 단위 SIREAD 잠금, 서브트랜잭션의 최상위 XID 처리, 안전 스냅샷/DEFERRABLE 경로, 피벗을 소멸 예정으로 만드는 피해자 선택 규칙이 그 독창적 정제들이다. README-SSI의 “Innovations” 절이 그 인-트리 대응물이다.

거짓 양성의 정량화. README-SSI는 모니터가 보수적임을 솔직히 인정한다. “모든 위험 구조가 실제 순환에 포함되지는 않는다.” 두 가지 설계 선택이 전체 순환 탐색 없이 거짓 양성률을 낮게 유지한다. 첫째, Theorem 2.1의 커밋 순서 가드는 아웃 측 파트너가 커밋하기 전까지 중단하지 않는다. 둘째, rw-충돌 그래프를 논문 프로토타입의 conflictIn/conflictOut 불리언이 아니라 명시적 RWConflictData 에지 목록으로 유지한다. 덕분에 탐지기가 “충돌-아웃이 있다”와 “이 특정 이전 트랜잭션으로의 충돌-아웃이 있다”를 구별한다. 술어 잠금 단위가 거친 것도 거짓 양성의 원인이다. 관계 수준 SIREAD 잠금은 해당 테이블에 대한 모든 쓰기와 충돌한다. 이는 max_predicate_locks_per_* GUC와 플랜 선택(순차 스캔은 관계 전체를 잠그지만 인덱스 스캔은 일부 리프 페이지만 잠근다)으로 조정할 수 있다.

다른 엔진의 SSI. CockroachDB(술어 잠금 대리로 timestamp cache 활용)와 Spanner(S2PL + TrueTime, SSI 없음) 이후, 학술 계통은 중단을 줄이는 직렬화 가능 변형들로 이어졌다. PSSI(Precisely Serializable Snapshot Isolation, Revilak 외)는 실제 의존성 그래프를 추적해 PostgreSQL이 수용하는 rw-전용 거짓 양성을 제거한다. 대신 부기 비용이 높다. Hekaton, Silo 같은 OCC 기반 MVCC 엔진은 에지를 증분 추적하지 않고 커밋 시 읽기 집합을 검증한다. PostgreSQL의 선택—rw-에지 증분 추적과 보수적 피벗 검사—은 충돌당 일정한 비용과 SLRU 스필을 통한 제한된 RAM 사용이라는 이점을 가진다. 인메모리 OCC 시스템의 읽기 집합 검증보다 장기 트랜잭션이 있는 디스크 기반 엔진에 적합한 선택이다.

이 문서의 knowledge/research/dbms-papers/ 기준점은 occ.md(SSI 분석의 전신 프레임워크인 낙관적 동시성 제어 이론), scalable-lock-manager.md (잠금 관리자 확장성; SIREAD의 비블록 설계와 대비), 그리고 README-SSI에 수록된 Cahill/Fekete/Ports-Grittner 논문[1][2]이다.

출처

src/backend/storage/lmgr/predicate.c — SSI 전체 구현
src/include/storage/predicate_internals.h — 공유 메모리 구조체 정의
src/include/storage/predicate.h — 공개 인터페이스 선언
src/backend/storage/lmgr/README-SSI — 인-트리 설계 문서; 주요 참고 자료
Cahill, Röhm, Fekete: Serializable isolation for snapshot databases, SIGMOD 2008 (README-SSI [1])
Fekete, Liarokapis, O’Neil, O’Neil, Shasha: Making Snapshot Isolation Serializable, ACM TODS 30:2, 2005 (README-SSI [2]; Theorem 2.1)
Ports, Grittner: Serializable Snapshot Isolation in PostgreSQL, VLDB 2012 (PostgreSQL 실현과 독창적 정제)
Berenson, Bernstein, Gray, Melton, O’Neil, O’Neil: A Critique of ANSI SQL Isolation Levels, SIGMOD 1995 (SI가 SERIALIZABLE이 아닌 이유; A5B 쓰기 왜곡)
Hellerstein, Stonebraker, Hamilton: Architecture of a Database System, §6.5.3 next-key locking (README-SSI [3])
knowledge/research/dbms-papers/occ.md
knowledge/research/dbms-papers/scalable-lock-manager.md — 잠금 관리자 확장성; 비블록 SIREAD 설계와 대비
knowledge/code-analysis/postgres/postgres-lock-manager.md — 헤비웨이트 잠금 관리자(이 문서의 대비 대상)
knowledge/code-analysis/postgres/postgres-mvcc-snapshots.md — SSI가 연결되는 스냅샷 기계
knowledge/code-analysis/postgres/postgres-xact.md — SSI 진입점을 호출하는 트랜잭션 생애주기
knowledge/code-analysis/postgres/postgres-slru.md — 직렬 로그가 사용하는 SLRU 서브시스템