목차

0. 문제 — lock manager는 무엇을 위해 존재하는가
1. 이론 — 2PL 단계와 변형, MGL, lub; 모든 DBMS lock manager의 공통분모
2. 자료구조 — OID 키, LK_ENTRY dual-view, lk_Gl, 부트와 메모리 계층
3. 잠금 요청의 일생 — PATH A–G, 변환과 UPR, 해제와 NON2PL, 에스컬레이션, 일시 중단/재개
4. 데드락 — WFG 구성, 사이클 스캔, 여섯 기준 victim 선택
5. 특수 경로 — instant probe, composite lock, hint / demote / subclass

출처: cubrid-lock-manager.md (설계 의도) + cubrid-lock-manager-detail.md (코드 수준 심층 분석).
부록 A: Lock vs Latch 심층 비교. 부록 B: 잠금 테이블 해시 함수.

보수적으로 시작 — 한 번에 트랜잭션 하나

자명하게 올바른 스케줄러: 데이터베이스 전체에 exclusive lock(배타 잠금) 하나.

• 구성 자체로 직렬 — 모든 트랜잭션이 데이터베이스를 독점하므로 잘못될 길이 없다. 비용: 10 s 배치 뒤에 갇힌 10 ms 읽기는 자기 작업의 1,000배를 기다려야 한다.
• 해법은 스위치가 아니라 다이얼: 배제 단위를 데이터베이스 → 클래스 → 행으로 줄여, 겹치지 않는 작업끼리 병렬로 돌게 한다. 같은 다이얼이 intention 모드와 에스컬레이션에서 다시 등장한다.
• 입도를 줄이면 인터리빙이 따라온다 — 방금 들여보낸 다섯 가지를 다음 슬라이드가 정리한다.

문제 — lock manager는 무엇을 위해 존재하는가

조율 없이 공유 데이터 위에서 트랜잭션을 인터리빙하면 ACID의 I (Isolation, 격리성) 가 무너진다 — 정확히 다섯 가지 고전적 이상 현상이 나타난다:

• 목표: 동시성은 지키면서 직렬화 가능(serializable) 하게 — 모든 결과가 직렬 실행(앞 슬라이드)이 낼 수 있던 결과여야 한다.
• lock manager의 역할: "이 객체를 읽는/쓰는 중" 이라 선언하는 원시 수단인 잠금을 제공하고 충돌을 중재한다(허가 · 큐 대기 · 에스컬레이션 · victim 중단).
• 잠금만으로는 부족하다: 접근할 때마다 잡았다 놓으면 여전히 깨진다 — T₁이 R을 놓는 순간 T₂가 끼어든다. 빠진 조각은 잠금 시점의 규율 → 다음 슬라이드.
• 격리 수준(RC / RR / Serializable)은 조정 가능한 트레이드오프 — 어떤 이상 현상을 감수하고 동시성을 얻을지 정한다.

2PL — 두 단계, 하나의 lock point

인터리빙을 허용하면서도 어떤 직렬 실행과 동등하게 남으려면? 고전적인 답:

• 성장 단계 (growing phase): 어떤 잠금이든 획득해도 된다. 하나라도 해제하는 순간 수축 단계가 시작된다.
• 수축 단계 (shrinking phase): 해제만 허용된다. 추가 획득은 없다.
• 그 전환점이 lock point — 꼭 커밋 시점일 필요는 없지만, 이 점을 기준으로 정렬된 모든 것이 스케줄을 결정한다.
• 정리 (Eswaran 1976): 모든 트랜잭션이 2PL을 지키면 결과 스케줄은 직렬화 가능하다.

2PL은 어떤 잠금을 쥐느냐가 아니라 lock(R) / unlock(R) 호출의 시점을 다스리는 규율이다.

2PL 변형 — basic, strict, rigorous

• rigorous가 더 얹어 주는 것: S까지 포함해 모든 잠금을 커밋까지 쥐면 직렬화 순서가 커밋 순서와 일치한다 — 복제본과 로그 리더가 관측한 순서를 그대로 신뢰할 수 있다. 대가: 읽기 잠금이 커밋까지 writer를 막는다.
• 연쇄 중단 (cascading abort): T₁이 커밋 전에 R의 X lock을 풀고 T₂가 R을 읽은 뒤 T₁이 중단되면 T₂도 중단해야 한다. Strict 2PL은 이를 구조적으로 차단한다.
• CUBRID는 X lock에 strict 2PL을 쓴다 — 모든 X lock은 커밋까지 간다. 읽기는 MVCC: 일반 SELECT는 사용자 테이블에서 행 잠금을 잡지 않는다. RC-vs-RR의 S lock 해제 노브는 MVCC-비활성 클래스(루트, serial, collation, HA apply-info)에만 적용된다 — lock_unlock_object_by_isolation.

"Strict"는 WAL 복구가 전제하는 선이다 — 중단 시 undo가 통하는 이유는 아직 누구도 우리의 쓰기를 보지 못했기 때문이다.

예제 — 중단 하나가 하류 전체를 끌어내린다

T1은 basic 2PL을 글자 그대로 따른다 — 그런데도 다른 두 트랜잭션을 오염시킨다:

• §문제의 dirty read가 실제 피해로 이어지는 모습: 쓰기가 커밋 전에 노출됐으니, 롤백 하나가 모든 하류 reader에게 재귀적으로 연쇄된다.
• 처방은 단순하다: X lock을 커밋까지 보유(strict 2PL). 누구도 내 쓰기를 미리 읽을 수 없으니 연쇄는 시작조차 못 한다. CUBRID는 X lock에 이를 무조건 적용한다.

2PL의 비용 — 그리고 네 가지 표준 대응책

• 보장: 직렬화 가능한 스케줄 — 이상 현상 없음.
• 비용 #1: 경합. 수축 단계가 길어지면 워크로드가 직렬화된다.
• 비용 #2: 데드락. hold-and-wait + 순환 의존은 일반적으로 피할 수 없다.
• 네 가지 표준 대응책:
  • 타임아웃 — 구현은 싸지만, 부하가 높으면 오탐이 잦다.
  • Conservative 2PL — 일을 시작하기 전에 모든 잠금을 선획득. 데드락 자체가 없지만, 호출자가 자기 working set을 미리 알아야 한다.
  • Waits-for graph 사이클 스캔 ← CUBRID의 주 탐지기 (lock_detect_local_deadlock).
  • 타임스탬프 회피 — wait-die, wound-wait. 트랜잭션 나이로 누가 기다릴지 정한다; 분산 설계(Spanner, CockroachDB)에 흔하고 단일 DBMS에는 드물다.

CUBRID는 WFG 탐지를 주 메커니즘으로 삼고, WFG 유지가 늦어질 때는 요청별 타임아웃으로 보완한다.

세 가지 이론적 구성 요소

순수 S/X 잠금을 넘어, 모든 실전 lock manager를 빚는 세 가지 이론:

1. Intention 모드 (IS, IX, SIX) — multi-granularity locking. 거친 입도의 잠금이 그 아래 미세한 잠금을 잡겠다는 의도를 선언한다 — 두 트랜잭션이 같은 테이블의 다른 행을 잠가도 테이블 수준의 거짓 충돌이 없다.
2. 호환성 행렬 — 2×2 (S, X) → 5×5 (intention 추가) → CUBRID는 12×12 (BU, SCH-S/M, U, NON2PL 추가).
3. 변환 (conversion) — 자기 잠금의 재요청은 자신과의 데드락이 아니라 업그레이드가 되어야 한다. 새 모드는 보유 모드와 요청 모드의 least upper bound (lub).
   정의. lock-mode 격자에서 lub(A, B)는 A와 B를 동시에 만족하는 가장 작은 모드. 예: lub(S, IX) = SIX, lub(IS, S) = S, lub(S, X) = X.

Part II의 자료구조가 이 세 조각을 LK_ENTRY + lock-mode 행렬 + 변환 테이블로 구현한다.

Intention 모드는 왜 존재하는가

Intention 모드(IS, IX, SIX)가 없으면 클래스 입도 잠금은 양자택일이다:

Intention 모드는 둘을 한 번에 푼다. 클래스에 IX를 잡는 것은 "아래 어딘가의 행에 X를 잡겠다"는 선언이다. 그러면:

• 다른 행의 writer 둘은 클래스에 IX를 나란히 쥔다 — 충돌 없음 (IX ∧ IX = ✓).
• DDL은 SCH-M을 잡고, SCH-M은 IX와 충돌한다 — writer들이 DDL 커밋을 기다리되, writer끼리의 미세 입도 동시성은 보존된다.
• 클래스 전체에 S가 필요한 reader는 여전히 IX와 충돌한다 — 누군가 행을 쓰는 중이니 올바르다.

IS/IX/SIX가 없으면 MGL은 S/X 전용으로 퇴화한다. 있으면 같은 호환성 행렬 하나로 행 입도 데이터 동시성 + 클래스 입도 DDL 보호를 함께 얻는다.

일곱 가지 공통 DBMS 패턴

1. Lock vs latch 분리 — lock = 논리적, 트랜잭션 수명, 외부 잠금 테이블(LK_ENTRY); latch = 물리적, 마이크로초, 페이지 내부(PGBUF_LATCH). 심화: 부록 A
2. 자원 해싱 — OID, 또는 (relation, key range)
3. 집계 모드 캐시 — total_holders_mode (O(holders) → O(1))
4. Dual-view 스레딩 — 자원 뷰 + 트랜잭션 뷰
5. MGL + intention 모드 — IS, IX, S, SIX, X
6. 변환 (lub) 테이블 — S + IX = SIX
7. FIFO 큐 + starvation guard — holders ∧ waiters

일곱 중 어느 것도 CUBRID의 발명이 아니다 — 진지한 엔진이라면 모두 같은 일곱 개의 다이얼을 맞춘다. Part II에서 CUBRID가 각 다이얼을 어디에 놓았는지 본다.

개요 — 잠금 요청은 어떻게 흐르는가

• 두 입도, 예외 하나. 먼저 클래스에 intent를 잡고, 행 잠금은 쓰기와 MVCC-비활성 읽기에만 실제로 걸린다 — MVCC 테이블의 일반 읽기는 건너뛴다 (스냅샷 가시성).
• 호환성 검사는 양면이다 — 허가된 모드 그리고 대기 큐 (starvation guard). 일시 중단은 셋 중 하나로 끝난다: 해제자의 허가, 타임아웃, 데드락 victim 롤백.
• 해제 시점은 범위별이다. 구문 단위 해제는 RC에서 MVCC-비활성 클래스의 S lock에만 존재한다; 그 밖의 전부 — X, 클래스, intent — 는 커밋까지 간다.

모든 것에 OID로 이름 붙이기

• OID = (volid, pageid, slotid) — C 구조체 db_identifier; 위의 튜플은 예시다.
• 입도 계층 = OID 계층: 루트 클래스 → 클래스 → 인스턴스.
• 모든 부모→자식 화살표가 그대로 intention lock의 부모/자식 간선이다 — 두 계층은 1:1로 겹친다.

세 가지 핵심 타입

// src/transaction/lock_manager.h
struct lk_res_key { LOCK_RESOURCE_TYPE type; OID oid; OID class_oid; };

struct lk_res {
  LK_RES_KEY key;
  LOCK       total_holders_mode;   // aggregate of granted modes
  LOCK       total_waiters_mode;   // aggregate of waiting modes
  LK_ENTRY  *holder, *waiter, *non2pl;
  pthread_mutex_t res_mutex;
};

struct lk_entry {
  LK_RES   *res_head;
  int       tran_index;
  LOCK      granted_mode, blocked_mode;
  int       count;                 // re-entrant counter
  LK_ENTRY *next;                  // resource list (holder or waiter)
  LK_ENTRY *tran_next, *tran_prev; // transaction list
  LK_ENTRY *class_entry;           // parent class, one hop
  int       ngranules;             // children below this intention lock
};

필드 쌍 셋에 주목: 두 집계 모드 (O(1) 호환성 — §행렬), LK_ENTRY의 두 모드 필드 (변환 상태 — §PATH F/G), 그리고 두 연결 고리 next vs tran_next/prev (§dual-view).

LK_TRAN_LOCK — 트랜잭션 하나의 잠금 상태

// struct lk_tran_lock — src/transaction/lock_manager.c
struct lk_tran_lock {
  LK_ENTRY *inst_hold_list, *class_hold_list, *root_class_hold;
  LK_ENTRY *waiting;             // the one lock this txn is blocked on
  LK_ENTRY *lk_entry_pool;       // local LK_ENTRY pool, max 10
  LK_ENTRY *non2pl_list;         // early-released lock shadows (RC)
  bool      lock_escalation_on;  // escalation re-entrance guard
  bool      is_instant_duration; // instant-lock mode flag
};

• 입도별로 쪼갠 세 개의 hold list — "클래스 A에 내가 뭘 잡고 있지?"는 class_hold_list만 걷는다: 전체 잠금 수가 아니라 O(보유 클래스 수).
• waiting은 단수다 — 트랜잭션은 한 번에 하나의 잠금에만 블로킹된다.
• 10개짜리 로컬 풀, 에스컬레이션 가드, instant 플래그는 각각 메모리 / 에스컬레이션 / 특수 경로 슬라이드에서 다시 등장한다.

전역 잠금 테이블 — lk_global_data

전역 셋: 해시 테이블, 10개 로컬 풀을 품은 per-tran 테이블, 오버플로용 공유 freelist. 크기 산정: §부트.

lk_Gl 실전 — 경합 중인 행 하나, 두 개의 뷰

시나리오: T7이 클래스 A의 한 행을 UPDATE하는 중; 같은 행을 노린 T9의 UPDATE는 기다려야 한다.

자원 뷰 — m_obj_hash_table:

트랜잭션 뷰 — tran_lock_table:

• 두 굵은 셀은 동일한 하나의 LK_ENTRY 다 — 자원의 holder list 그리고 T7의 hold list에 동시에 꿰여 있다 (§Dual-view, 두 슬라이드 뒤).
• 두 트랜잭션 모두 클래스 IX를 충돌 없이 쥔다 — 실제 경합은 한 입도 아래에서 벌어진다.

엔트리 초기화 — granted vs blocked

// lock_initialize_entry_as_granted — src/transaction/lock_manager.c
  e->tran_index   = tran;          e->res_head = res;
  e->granted_mode = lock;          // → this entry is a holder
  e->blocked_mode = NULL_LOCK;
  e->count        = 1;             /* list pointers nulled */

// lock_initialize_entry_as_blocked — same file
  e->thrd_entry   = th;            // the thread to suspend
  e->granted_mode = NULL_LOCK;
  e->blocked_mode = lock;          // → this entry is a waiter

• (자원, 트랜잭션)당 엔트리 하나 — 이 필드 쌍과 어느 리스트에 꿰였는가가 곧 상태다. (blocked_mode는 대기 중인 목표지 "intention"이 아니다 — 그 단어는 IS/IX/SIX의 것이다.) 세 번째 생성자는 §NON2PL shadow를 만든다 — 잠금이 아예 아니다.

Dual-View Threading

• 같은 LK_ENTRY가 두 리스트에 동시에 산다.
• 자원 뷰: R을 누가 잡고 있나? → next.   트랜잭션 뷰: T는 뭘 잡고 있나? → tran_next/prev.
• 커밋은 트랜잭션 리스트를 걷는다. 호환성 검사는 자원 쪽 집계를 읽는다.

부트 — lock_initialize, 순서대로 다섯 단계

• 1–4단계가 조립도의 lk_Gl 전역들을 채운다 (색상 일치); 5단계가 유일한 백그라운드 스레드를 띄운다. 함수: lock_initialize_* — 전체 워크스루는 detail ch. 2.
• 순서가 곧 제약이다 — 4단계는 WFG 크기를 num_trans로 결정하는데, 그 값은 1단계에서 정한다.
• 데몬의 100 ms 틱마다 임무 셋: 인터럽트 확인, 타임아웃 확인, (게이트 달린) 데드락 스캔 — 100 ms는 설계상 타임아웃 입도다.

메모리 — 세 계층, 그리고 lockfree 경계

• 3–5행짜리 OLTP 트랜잭션은 1계층을 벗어날 일이 없다 — 할당 경합이 없다.
• 경계: LK_RES를 찾는 것 (해시 find_or_insert)은 lockfree; 그 리스트를 고치는 것은 뮤텍스 구간이다 — 자원마다 res_mutex, 트랜잭션마다 hold_mutex.
• 회수된 엔트리는 epoch 기반(del_id)으로 재활용된다 — CUBRID의 다른 lockfree 모듈과 같은 기계장치다.

12개 모드 어휘

Gray의 5개 모드 (IS / IX / S / SIX / X) + CUBRID의 추가 7개.

SQL 구문은 어떤 잠금 모드가 되는가

구문 하나는 보통 두 개의 잠금을 잡는다: 클래스 입도의 intent — lock_object의 MGL 준비 단계 또는 힙 스캔 시작 시 lock_scan이 심는다 — 그리고 행 입도의 실제 잠금.

• IX 행의 반복은 의도적이다 — 모든 행 수준 쓰기는 같은 클래스 intent 모드를 잡는다. 나머지는 호환성 행렬의 몫이다.

호환성 행렬 + starvation guard

새 요청은 total_holders_mode와 total_waiters_mode 양쪽과 호환되어야 한다 — 후자가 잇따르는 S가 대기 중인 X를 새치기하지 못하게 막는 starvation guard다.

예제 — starvation guard의 작동

어느 CUBRID 테이블에서도 재현 가능한 시나리오 — 긴 reader, 그다음 DDL, 그다음 또 다른 reader (클래스 입도):

• t = 3에서 holder만 검사했다면 T3는 허가됐을 것이다 (IS ∧ IS = ✓) — 끊이지 않는 reader 흐름이 DDL을 영원히 굶기는 구조다. waiter 검사가 T3를 T2 뒤에 줄 세우고, T1이 끝나는 즉시 ALTER가 실행된다.
• 이 시나리오의 행 입도 버전은 MVCC-비활성 행(serial)에만 존재한다 — 일반 MVCC reader는 행 S lock을 잡지 않는다.

PostgreSQL은 같은 규칙을 strong-lock fairness라는 이름으로 싣는다; CUBRID에서는 이중 검사의 total_waiters_mode 쪽이 그 역할이다.

누가 lock manager를 호출하는가

lock manager는 서비스 계층이다: 파일 열 개가 전체 호출 지점의 ~90 %를 차지한다.

진입점 둘, 내부의 일꾼 하나

• lock_scan — 클래스 입도 전용; 읽기는 IS, 쓰기는 IX. 실제 호출 지점은 하나: 힙 스캔 시작.
• lock_object — OID(루트 / 클래스 / 인스턴스)로 분기하며 먼저 부모의 intention lock부터 확보한다.
• 포괄이 주는 fast-out. 이미 쥔 클래스 잠금이 행 요청을 덮으면 — 이를테면 클래스 X가 행 X를 — lock_object는 해시 조회도 LK_ENTRY도 없이 LK_GRANTED를 반환한다. 에스컬레이션 후 남은 40,000행(§에스컬레이션 예제)이 공짜인 이유다. 검사: lock_is_class_lock_escalated.

일꾼의 내부 — 디스패치 트리

• 두 가지 질문이 모든 요청을 분류한다 — 자원이 비어 있는가? 그리고 요청 트랜잭션인 내가 이미 잡고 있는가? — 이후 각 가지 안에서 호환성이 결정한다; 작은 캡션은 각 결정이 읽는 LK_RES 필드를 가리킨다. (인스턴스 요청은 이 모든 분기 전에 에스컬레이션 검사를 통과한다.)

일꾼의 내부 — 일곱 경로

E가 OLTP 핫 패스다 — class-entry fast path는 해시 조회도 res_mutex도 없이 hold_mutex와 count 증가만으로 끝난다.
F/G는 다른 holder들의 group_mode와 비교한다 — 트랜잭션은 자기 자신과 충돌할 수 없다.

디스패치를 코드로 — 압축판

// lock_internal_perform_lock_object — lock_manager.c
start:      /* re-entered ONLY from the
               sibling branches in D & G */
  find_or_insert (key, &res);            /* lockfree */
  if (res is empty)
    return grant_fresh ();               /* PATH A */
  if (find_mine (res->holder, my_tran))
    goto lock_tran_lk_entry;
  if (compat (lock, res->total_waiters_mode)
      && compat (lock, res->total_holders_mode))
    return grant_immediately ();         /* PATH B */
  if (wait_msecs == ZERO_WAIT)
    return TIMEOUT;                      /* PATH C */
  suspend (); return woken_outcome ();   /* PATH D */

lock_tran_lk_entry:   /* I already hold R */
  new_mode = lock_conv (lock, granted_mode);
  if (new_mode == granted_mode)
    { count++; return GRANTED; }         /* PATH E */
  group = lub_of_OTHER_holders ();
  if (compat (new_mode, group))
    { granted_mode = new_mode;
      return GRANTED; }                  /* PATH F */
  blocked_mode = new_mode;               /* PATH G */
  reposition_per_UPR (); suspend ();

PATH D가 남기는 것 — 자료구조

• 앞의 스냅샷(T7이 X 보유, T9 대기)의 연속: T12의 X는 PATH D에 떨어진다 — FIFO 꼬리, T9 바로 뒤에 새 LK_ENTRY, total_waiters_mode = lub(X, X), 스레드는 일시 중단.
• 깨어남의 약속: 해제자 쪽 스레드가 grant pass를 돌며 T12의 entry를 검사해 holder로 승급시킨 뒤에 깨운다 — 그래서 T12는 깨어날 때 이미 holder다. 아니면 타임아웃 / 데드락 victim으로 (§일시 중단과 재개).
• 이 waiter→holder 관계가 나중에 데드락 탐지기가 WFG 간선으로 읽어 내는 것이다 (Part IV).

잠금 변환 — lub 규칙

• lub = least upper bound. 강도로 정렬된 lock-mode 격자에서 lub(A, B)는 A와 B를 동시에 만족하는 가장 작은 모드.
• 자기 잠금의 재요청은 자신과의 데드락이 아니라 업그레이드여야 한다.
• 규칙: granted_mode ← lub(granted_mode, requested_mode)
  • lub(S, IX) = SIX — 공유 그리고 쓰기 의도가 모두 필요
  • lub(IS, S) = S — S가 이미 IS를 함의
  • lub(S, X) = X — X가 이미 S를 함의
• 구현: 정방 테이블 lock_Conv[requested][current] — src/transaction/lock_table.c.
• 변환 중인 holder는 업그레이드가 성공할 때까지 granted_mode(현재)와 blocked_mode(목표)를 둘 다 설정한다 — 그것이 PATH G다.

예제 A — 충돌 없는 자기 업그레이드 (PATH F)

T1이 같은 행 r을 읽고 나서 쓴다. 전제: r은 MVCC-비활성 클래스(이를테면 serial) 소속 — MVCC 테이블이라면 읽기는 행 S를 잡지 않고, 쓰기는 곧장 X로 간다.

-- autocommit off: the transaction starts with the first statement
SELECT * FROM accounts WHERE id = 5;             -- step 1
UPDATE accounts SET balance = 200 WHERE id = 5;  -- step 2
COMMIT;

• LK_RES의 집계도 함께 바뀐다: total_holders_mode가 S → X. holder 수는 1 그대로.
• 자기 잠금 재요청은 "해제 후 재획득"이 아니다 — 변환 테이블이 그 데드락 위험 시퀀스를 원자적 전이 하나로 대체한다.

왜 중요한가: 변환 테이블이 없으면 업그레이드는 해제-후-재획득이다 — 그 틈에 다른 트랜잭션이 끼어들어 T1을 데드락에 빠뜨릴 창이 열린다.

예제 B — 충돌을 기다리는 자기 업그레이드 (PATH G)

같은 코드, 같은 MVCC-비활성 전제 — 단, T1이 시작할 때 다른 트랜잭션 T2가 이미 행 r에 S를 쥐고 있다.

예제 A와 다른 점: 단계 3의 T1은 holder(S)이면서 동시에 대기 중인 upgrader(목표 X)다. T1은 기다리는 동안 S를 결코 놓지 않는다 — LK_ENTRY에 모드 필드가 둘인 이유다.

자기 업그레이드 — 예제 A vs B 한눈에

같은 LK_ENTRY 모양, 서로 다른 두 코드 경로. 변환 테이블이 둘 다 덮는다: 행렬의 정의된 모든 칸에 lub이 있으므로, 업그레이드해 갈 목표 모드는 언제나 존재한다.

파묻힌 upgrader — holder list의 순서가 중요한 이유

막힌 upgrader는 holder list 안에서 기다린다 (PATH G: 이전 모드를 여전히 보유하므로 waiter 큐 진입 불가) — 해제 때마다 grant pass가 리스트를 앞에서 뒤로 훑다가 첫 plain holder에서 멈춘다: while (holder && holder->blocked_mode != NULL_LOCK).

순진한 삽입 — 그냥 뒤에 붙이기. 클래스 입도 타임라인; 각 엔트리는 granted/blocked로 읽는다 (– = NULL_LOCK):

• plain holder 뒤에 선 upgrader는 이번 해제에도 앞으로의 어떤 해제에도 보이지 않는다 — pass는 zone 경계 너머를 절대 훑지 않는다.
• 위치는 장부 정리가 아니라 정확성의 문제다. upgrader는 정확히 어디에 서야 하는가? → 다음 슬라이드에서 그림으로, 그다음에 규칙으로.

파묻힌 upgrader — 같은 타임라인을 그림으로

• 패널 ②가 버그다: while 검사가 plain T5에서 실패한다 — T3의 자격은 계산조차 되지 않는다.
• 패널 ③이 비용이다: 허가 가능한 업그레이드(SIX ∧ IS = ✓)가 타임아웃 또는 데드락 victim이 될 때까지 잠든다.
• 초록 띠가 실제 코드다: UPR이 T3를 잠들기 전에 맨 앞으로 옮긴다 — 바로 다음 해제에서 허가된다.

그냥 전부 보면 안 되나? — UPR 뒤의 거래

전수 스캔도 liveness 버그를 고치긴 한다 — release마다 holder 전원을 검사하면 위치는 의미를 잃는다. 코드가 다른 길을 택한 이유는 hot path다:

• 전형적인 불변식 대 스캔 거래: 배치 비용은 드문 경로(PATH G의 suspend)에서 한 번 — 매 release 경로는 상수로 유지한다.
• 전수 스캔 버전은 prefix break 대신 continue가 필요하고, "다른 holder들"을 ->next만 걷어 계산하는 지름길도 잃는다 — 그 지름길은 허가된 upgrade를 zone 경계로 재배치해 두기 때문에 건전하다.
• holder list의 순서를 읽는 소비자는 이 스캔 하나뿐이다. 집계 재계산, WFG 구축, unlink는 모두 순서 무관.

Upgrader Positioning Rule — 배치 검사

불변식: holder list를 [ upgraders… ][ plain holders… ] 모양으로 유지한다 — 그래야 앞쪽 zone 스캔이 모든 대기 중 업그레이드에 확실히 도달한다. lock_position_holder_entry는 배치할 엔트리 — new 라 부르자 — 를 들고 zone을 걸으며, ta > tb > tc 중 처음 성립하는 것 앞에 삽입하고, 없으면 뒤에 붙인다.

• grant pass도 이 불변식을 지킨다: 방금 허가된 업그레이드는 pass가 계속되기 전에 zone 경계로 재배치된다 (lock_grant_blocked_holder).
• 유래: upgrades-before-new-waiters는 고전적 기법이다 (Gray & Reuter; System R / DB2 계보); ta/tb/tc 검사와 "UPR"이라는 이름은 CUBRID 고유다 (lock_manager.c 소스 주석).

ta vs tb — 묶기, 그리고 살아남는 유일한 순서

ta — 내 목표 ∧ 네 목표 = ✓. 같은 pass에서 함께 허가될 수 있다: 나란히 서면 prefix 스캔이 해제 한 번에 그룹 전체를 거둔다. 배칭 규칙.

tb — 충돌하되, 한 방향만. new = IX→SIX, i = IS→X라 하자:  SIX ∧ IS = ✓ — i의 보유 모드는 나를 막지 않는다 — 그러나 X ∧ IX = ✗ — 내 보유 모드는 내가 쥐고 있는 한 i를 막는다. 순서가 모든 것을 결정한다:

• pass는 호환되는 prefix를 허가하고 첫 실패에서 멈춘다 — 따라서 충돌하는 한 쌍에게 살아남는 순서는 정확히 하나: 상대가 보유 중이어도 허가될 수 있는 쪽이 먼저.

일시 중단과 재개 — 깨어나는 여섯 가지 방법

• 구조적으로 race가 없다: 깨우는 쪽이 thread-entry 뮤텍스 아래에서 시그널 전에 상태를 먼저 기록한다.
• lock_suspend는 페이지 래치를 쥐지 않았음을 단언한다 — 래치를 쥔 채 잠금을 기다리는 것이 고전적 순서 데드락이다 (부록 A).
• 빠른 게이트: 원자적 waiter 카운터(deadlock_and_timeout_detector) 덕에 한가한 100 ms 데몬 틱의 비용은 읽기 한 번이다.
• victim 3행의 차이 — 트랜잭션의 운명과 롤백 주체 — 는 Part IV에서 victim 선택 직후에 푼다.

깨어난 다음 — 재개된 스레드가 하는 일

상태는 여섯이지만 깨어난 지점의 행동은 사실상 셋 — lock_suspend는 switch 하나를 돌리고 판정을 dispatch tree에 돌려준다:

// lock_suspend, after the sleep — lock_manager.c
wake_chained_siblings ();    /* tran_next_wait relay */
switch (lockwait_state) {
  case RESUMED:            /* the grant cascade ran */
    return RESUMED;        /* already a holder — done */
  case ABORTED_FIRST:      /* I own the rollback */
    set_error (UNILATERALLY_ABORTED);
    abort_reason = TRAN_ABORT_DUE_DEADLOCK;
    while (sibling_workers (my_tran) > 0)
      { interrupt; sleep (10 ms); }  /* drain them */
    return ABORTED;
  case ABORTED_OTHER:      /* a sibling is FIRST */
  case DEADLOCK_TIMEOUT:   /* txn survives */
  case TIMEOUT:            /* wait_msecs ran out */
    set_error_for_timeout ();
    return DEADLOCK_TIMEOUT or TIMEOUT;
  case INTERRUPT: return INTERRUPT;
}
// back in lock_internal_perform_lock_object
if (ret != RESUMED)        /* entry still parked — */
  perform_unlock_object (entry);  /* detach my own */

해제로 건너가기 — 시작은 lock_unlock_object

디스패치 트리 이후의 모든 것은 lock_object 안에서 돌았다 — 그리고 획득 쪽은 아무도 깨우지 않는다. 깨우기는 해제 경로의 일이고, 그 진입점이 무엇을 언제 해제할지 정한다:

// lock_unlock_object — src/transaction/lock_manager.c
if (force) {                       // commit / rollback
  lock_internal_perform_unlock_object
    (..., false, true);
  return;
}
if (lock != S_LOCK) return;        // X is commit-bound
switch (logtb_find_isolation (tran_index)) {
  case TRAN_SERIALIZABLE:
  case TRAN_REPEATABLE_READ: return;
  case TRAN_READ_COMMITTED:
    lock_unlock_object_by_isolation (...); break;
}

해제 내부 — grant cascade

세 범위 모두 lock_internal_perform_unlock_object로 집약된다. 해제된 엔트리가 리스트에서 빠진 직후, 정해진 순서대로 허가가 이어진다:

• waiter보다 upgrader 먼저 — pass 1은 upgrader zone을 걷고 (UPR이 여기서 빛을 본다); pass 2는 갱신된 집계를 상대로 FIFO를 걷다가 첫 비호환 엔트리에서 멈춘다.
• 재계산은 O(holders)다: lub은 역연산이 없다 — 집계에서 모드 하나를 뺄 수 없다.

해제 내부 — count, release_flag, 그리고 커밋

// lock_internal_perform_unlock_object — src/transaction/lock_manager.c
if (release_flag == false) {
  entry_ptr->count--;
  if (entry_ptr->blocked_mode == NULL_LOCK && entry_ptr->count > 0)
    return;            /* re-entrance guard: most unlock calls exit here */
}

• 모든 lock_object가 count를 올리고, 모든 unlock이 내린다. 엔트리는 0에서만 해방된다 — 안쪽 중첩 호출이 바깥쪽이 딛고 선 엔트리를 미리 거둘 수 없다.
• lock_unlock_all (커밋 / 롤백; 호출자는 log_manager.c뿐)은 release_flag = true를 넘기고 인스턴스 → 클래스 → 루트 순으로 해제한다 — 잎에서 뿌리로, 획득 순서의 역방향.
• LK_RES는 holder, waiter, 그리고 non2pl 리스트가 모두 비었을 때만 해시 테이블에서 지워진다; shadow만 남은 자원은 살아 있다.

예제 — 같은 타임라인 위의 RC vs RR

범위. 교과서적 2PL 이야기다 — CUBRID에서는 MVCC-비활성 클래스(serial 등)에만 적용된다. MVCC 사용자 테이블이라면 T2는 S lock을 잡지 않고, 같은 이상 현상은 스냅샷 시점으로 해소된다 — cubrid-mvcc.md 참고.

T2가 한 트랜잭션 안에서 두 번 읽는다; 그 사이에 T1이 갱신하고 커밋한다. 두 번째 읽기에서 T2는 무엇을 보는가?

행에서의 격리 수준 — 코드가 실제로 바꾸는 것

• 분기는 잠금 테이블이 아니라 두 술어다: mvcc_is_mvcc_disabled_class (4종 클래스)와 logtb_check_class_for_rr_isolation_err (3개 예외 메타데이터 클래스; 검사는 locator_sr.c에 있다).
• 런타임에서 RR ≡ SERIALIZABLE — 모든 분기가 isolation > TRAN_READ_COMMITTED를 검사한다; SERIALIZABLE은 실질적으로 스냅샷 격리(TRAN_NO_PHANTOM_READ 별칭)이고, write skew는 막지 않는다.
• 결론: 격리 수준이 움직이는 것은 스냅샷 시점 + 쓰기 시점 검사 하나. lock manager의 X-to-commit 규율은 변하지 않는다.

잠금 에스컬레이션

// lock_escalate_if_needed — src/transaction/lock_manager.c
if (!lock_check_escalate (th, class_entry, tran_lock))
  return LK_NOTGRANTED;                          // threshold not reached
if (class_entry->granted_mode == IX_LOCK
    || class_entry->granted_mode == SIX_LOCK)
  max_class_lock = X_LOCK;                       // writer  → class X
else
  max_class_lock = S_LOCK;                       // reader  → class S
granted = lock_internal_perform_lock_object (... , max_class_lock,
            LK_FORCE_ZERO_WAIT, &class_entry, NULL);

• 모든 인스턴스 요청마다 검사된다 — hold_mutex 아래 정수 비교 한 번 (ngranules vs lock_escalation 파라미터), ~100 ns.
• IS → S, IX/SIX → X 선택은 휴리스틱이다 — 행별 S와 X를 일일이 세는 비용이 바로 에스컬레이션이 아끼려는 그 비용이기 때문이다.
• 설계상 조건부: LK_FORCE_ZERO_WAIT는 경합 중인 클래스 잠금 앞에서 에스컬레이션을 조용히 포기한다 — 행 단위 잠금이 그대로 계속된다.
• 옵트아웃: rollback_on_lock_escalation은 잠금 범위를 키우는 대신 트랜잭션을 중단시킨다.

예제 — 대량 DML에서의 에스컬레이션

유지보수 작업 하나가 돈다:

UPDATE accounts SET status = 'archived' WHERE created_at < '2020-01-01';
-- imagine 50,000 rows match

• 메모리가 O(접근한 행 수)에서 O(1)로; 이후 검사는 행렬 조회 한 번.
• accounts의 어떤 행이든 원하는 다른 트랜잭션은 남은 트랜잭션 기간 내내 클래스 X에 막힌다.
• 4단계에서 다른 트랜잭션이 충돌하는 클래스 잠금을 쥐고 있으면 no-wait 시도는 실패한다 — 에스컬레이션은 포기되고 행 단위 잠금이 계속된다.

데드락 — Waits-For Graph

• 탐지 실행마다 잠금 테이블에서 간선(LK_WFG_EDGE)을 유도한다 — 매 스캔에서 새로 만들며, 대기 시점에 온라인으로 유지하지 않는다.
• lock_detect_local_deadlock이 DFS로 그래프를 걷는다; 경로 위의 노드로 향하는 back-edge가 곧 사이클이다.
• "Local" — 분산 데드락은 이 탐지기의 몫이 아니다; 요청별 타임아웃으로 처리한다.

탐지 — 게이트 셋, 페이즈 다섯

• WFG는 실행마다 처음부터 다시 만든다 — lock/unlock 핫 패스에 장부가 전혀 없다; 스캔 비용은 O(활성 자원 수), 최대 초당 한 번 (lock_deadlock_detect_interval).
• 안전망: victim 없는 실행이 60회 연속(~6 s)이면 일시 중단된 스레드 하나를 강제로 타임아웃시켜 탐지 불가 멈춤을 끊는다.

WFG를 코드로 — 탐지기 자신의 자료구조

// lock_manager.c — TWFG: rebuilt into lk_Gl on every detection run
struct lk_WFG_node {              // one slot per transaction
  int   first_edge;               // head of my outgoing edges (-1 = none)
  int   current, ancestor;        // DFS cursor + path parent (phase 3)
  INT64 thrd_wait_stime;          // when this txn started waiting
  int   tran_edge_seq_num;        // stale-edge filter
  bool  checked_by_deadlock_detector, DL_victim;
};
struct lk_WFG_edge {              // one "waits-for" arrow
  int   to_tran_index;            // the txn I wait for
  int   holder_flag;              // target holds? → victim criterion #1
  int   next;                     // next edge of the same from-node
  int   edge_seq_num;   INT64 edge_wait_stime;
  LK_ENTRY *holder, *waiter;      // evidence back in the lock table
};

• 납작한 배열 두 개로 만든 인접 리스트: lk_Gl.TWFG_node[tran_index] + 공유 TWFG_edge[] 풀 하나 — 간선은 포인터가 아니라 인덱스로 이어진다 (first_edge → next).
• 노드는 스레드도 자원도 아닌 트랜잭션이다; 간선 저장소는 계층적으로 확장된다 — 200 (정적) → 1,000 → MAX_NTRANS² (malloc) — 읽기 전용 워크로드는 할당조차 하지 않는다.

탐지를 압축 코드로 — 한 번의 실행, 다섯 페이즈

// lock_detect_local_deadlock — lock_manager.c
/* 1 reset */
for (k : every txn slot)
  TWFG_node[k] = { first_edge: -1, checked: true };
/* 2 build */
for (res : every LK_RES)          /* hash iterate */
  for ((blocked, blocking) : holder×holder,
        waiter×holder, waiter×waiter pairs)
    if (!compat (blocked_mode, their mode))
      lock_add_WFG_edge (from, to, holder_flag);
/* 3 DFS */
for (k : every txn)  walk current / ancestor;
  reach a node already on my path → CYCLE
/* 4–5 victims */
lock_select_deadlock_victim ();   /* six criteria */
lock_wakeup_deadlock_victim_* (); /* abort | timeout */

그래프 만들기 — 세 종류의 간선

• 모든 자원의 모든 (blocked, blocking) 쌍이 방향 간선 LK_WFG_EDGE 하나가 된다; 각 간선의 holder_flag가 victim 기준 #1의 입력이다.
• 스캔 도중 커밋된 트랜잭션의 낡은 간선은 DFS 중 시퀀스 번호 검사로 걸러진다; 그런 간선을 포함한 사이클은 거짓으로 판정되어 버려진다.

Victim 선택 — 여섯 가지 기준, 순서대로

1. 사이클 어딘가의 lock holder여야 한다 (holder_flag) — holder의 롤백만이 사이클이 기다리는 것을 풀어 준다; 순수 waiter를 중단시켜도 아무것도 풀리지 않는다.
2. 활성 트랜잭션이어야 한다 — 이미 커밋 / 중단 중인 것은 어차피 나가는 중이어서 다시 중단시킬 수 없다.
3. deadlock priority가 없는 쪽을 우선 — 보호된 트랜잭션은 살아남는다.
4. 로그 레코드를 적게 쓴 쪽을 우선 — 가장 싼 롤백.
5. 타임아웃이 유한한 쪽을 우선 — 해당 애플리케이션은 이미 재시도를 예상한다.
6. 가장 어린 쪽 (가장 큰 tranid)을 우선 — 버리는 작업이 최소이고, 오래된 쪽은 매번 다시 victim이 되는 대신 진행분을 지킨다.

• 해소는 두 모드다: wait_msecs가 유한한 victim은 LOCK_RESUMED_DEADLOCK_TIMEOUT(재시도 가능)으로, 무한 대기 victim은 LOCK_RESUMED_ABORTED_*(롤백)로 깨어난다.
• "가장 최근에 막힌 쪽"이 아니다 — 이 덱의 이전 판(과 상위 문서)은 삽입 순서에서 그렇게 추정했지만, detail 문서가 lock_select_deadlock_victim을 따라 읽으며 낸 결론이다.

victim 해소 — wake state가 셋인 이유

victim은 하나인데 깨어나는 상태는 셋이다. 차이는 트랜잭션의 운명과 누가 뒷정리를 하는가다:

• TIMEOUT / ABORTED의 분기는 victim의 wait_msecs다: 유한이면 그 애플리케이션은 이미 timeout형 실패를 다루므로 트랜잭션을 살려 재시도하게 하고, 무한 대기면 abort가 유일한 출구다.
• FIRST / OTHER가 있는 이유: 한 트랜잭션의 여러 스레드가 동시에 잠금에 잠들어 있을 수 있다 — 탐지기는 전부 깨우지만, "트랜잭션 abort를 책임지는"(소스 주석) 스레드는 정확히 하나여야 한다. 나머지는 timeout으로 통지받아 롤백이 두 번 돌 일이 없다.

예제 — 트랜잭션 둘, 행 둘

설정: accounts (id, balance), 초기값 A.balance = 1000, B.balance = 1000. 두 세션이 동시에 시작한다:

T1은 A에서 B로, T2는 B에서 A로 이체한다. 스케줄은 스케줄러가 둘을 어떻게 인터리빙하느냐에 달렸다 — 그리고 한쪽은 운이 없다.

예제 — 인터리빙이 사이클을 만든다

• t = 4 이후 두 트랜잭션 모두 LOCK_SUSPENDED다.
• 외부 개입 없이는 어느 쪽도 전진하지 못한다 — 잠금 테이블은 길이 2의 사이클을 품은 채 다음 탐지 실행이 찾아내기를 기다린다.

요청별 타임아웃도 결국은 끊겠지만, 수 분의 대기가 낭비된다 — 탐지기는 1초 스캔 주기 안에 해소한다.

예제 — 사이클을 그림으로

• 왼쪽: 구체적인 잠금 테이블 — LK_RES 레코드 둘, 각각 holder 하나와 waiter 하나.
• 오른쪽: 추상화된 WFG — 트랜잭션당 노드 하나, 블로킹 관계당 waiter→holder 간선 하나 (간선 종류 (b)).
• 탐지기는 행 내용을 들여다보지 않는다. 잠금 테이블을 한 번 쓸어 그래프를 만들고, 이후로는 그래프만 걷는다.

예제 — 탐지기가 해소한다

데몬 틱이 게이트를 통과한다 (일시 중단 스레드 둘; 주기 도래):

1. Build. 잠금 테이블 스윕: 행 A에서 간선 T2→T1, 행 B에서 간선 T1→T2.
2. DFS. T1에서 출발 → T2로 → T1으로의 back-edge, T1은 DFS 경로 위에 있다 → 사이클 발견.
3. Victim. 둘 다 holder, 둘 다 활성, deadlock priority 없음, 로그 레코드 수도 갱신 1건씩 동점 — 가장 어린 기준이 T2를 고른다 (나중에 시작).
4. Wake. 무한 대기 기본값에서 T2는 LOCK_RESUMED_ABORTED_FIRST로 재개 → 롤백이 B의 X를 해제한다. (wait_msecs가 유한했다면 재시도 가능한 DEADLOCK_TIMEOUT을 받았을 것.)
5. Cascade. 그 해제가 T1이 기다리던 B의 X를 허가한다 (§grant cascade); T1은 나머지 구문을 실행하고 커밋한다.

실행 중인 트랜잭션에게서 잠금을 빼앗는 일은 결코 없다. 패자는 롤백을 치르고, 승자는 약간의 추가 대기만 느낀다.

예제 — 트랜잭션 셋의 사이클

각 트랜잭션이 행 하나를 쥐고 다음 행으로 손을 뻗는다 — 순환 사슬.

• T1에서 출발한 DFS가 T1→T2→T3를 걷다 T1으로의 back-edge — 깊이 3의 사이클. Victim = T3: 기준 1–5는 동점; 가장 어린 쪽이 결정.
• T3 중단 → R3 해제 → T2 재개 → R2 해제 → T1 재개 — grant cascade 연쇄.

특수 경로 — instant probe

• "이 잠금, 지금 당장이면 허가될까?" — 같은 이중 집계 호환성 검사를 상태를 전혀 만들지 않고 수행한다.
• 사용자와 워크로드 — 그리고 이유: scan_manager.c, 힙 / 인덱스 스캔의 행 방문. 방문하는 행마다 lock_object를 부르면 해시 find_or_insert에 res_mutex 아래의 리스트 수정까지 행마다 치러야 하는데, 대부분의 행은 경합이 없다. 그래서 스캔은 읽기 전용 probe부터 던지고 충돌 시에만 lock_object로 후퇴한다: 흔한 경로에서 잠금 엔트리 비용을 내지 않는다.

특수 경로 — composite lock

• 사용자와 워크로드 — 그리고 이유: query_executor.c, 대량 DELETE / UPDATE 플랜 (XASL에 실려 온다). 스캔 도중에 각 행의 X를 획득하면 동시 트랜잭션과의 데드락을 유발하고 일시 중단이 스캔 루프 안에 끼인다 — 그래서 스캔은 OID만 수집하고, 모든 X lock은 finalize에서 한 번에 일괄로 획득한다 (detail ch. 9).
• 내장 에스컬레이션: 한 클래스의 수집 OID 수가 lock_escalation 임계값에 닿으면 수집을 멈추고, finalize가 대신 클래스 X를 잡는다.

특수 경로 — NON2PL, 조기 해제된 S lock의 shadow

• shadow는 누구도 막지 않는다 — 호환성 행렬 상의 잠금 모드가 아니라 장부다.
• 존재 이유: RC의 구문 끝 S 해제는 의도된 2PL 위반이다 — 해제 후에도 클라이언트는 더 이상 보호받지 못하는 캐시 사본을 들고 있다. shadow가 그 사실을 기록해 두므로, 이후의 충돌하는 허가가 사본을 낡음으로 표시하고(2단계) 다음 fetch에서 decache하게 만든다(3단계).
• 사용자와 워크로드: serial.c — RC에서의 serial 행 접근 (§누가 lock manager를 호출하는가: NON2PL의 주 사용처). MVCC 이전 모든 RC 읽기가 조기 해제되던 시절의 유산 — 지금은 MVCC-비활성 틈새만 남았다.

특수 경로 — 나머지 API 표면

어느 것도 새 기계장치를 들이지 않는다 — 전부 lock_internal_perform_lock_object로 귀결된다.

슬라이드에 없는 것 — 다음에 읽을 것

분석 문서 둘이 슬라이드가 다루지 못하는 내용을 담는다:

문서	내용
cubrid-lock-manager.md	설계 의도, 이론 코드 매핑, 열린 질문, 위치 힌트
…-detail.md ch. 1–2	모든 구조체 필드; 부트, 해시 함수, lockfree 통합
ch. 3–4	PATH A–G 라인 단위; UPR 심층 분석 (ta / tb / tc 후보)
ch. 5–7	NON2PL과 instant-lock 내부; 일시 중단 / 타임아웃 기계장치
ch. 8–9	WFG 신선도 검사, victim 선택 코드; composite / demote / subclass

두 문서 모두 각자의 updated: 날짜 기준 라인 번호가 달린 위치 힌트 표를 유지한다.
어긋나면: git grep -n '<symbol>' src/transaction/.

CUBRID 너머 — 연구 전선

CUBRID의 다이얼 위치: 교과서 2PL + MGL + WFG 탐지. 충분히 방어 가능한 지점이다.

부록 A — Lock vs Latch 나란히 비교

발음마저 닮은 두 단어, 같은 DBMS 안의 완전히 다른 기계.

Database Internals ch. 5의 첫 번째 철칙: 이 둘을 섞지 마라.

부록 A — 코드로 보는 Lock vs Latch (CUBRID 힙 삽입)

PGBUF_LATCH page (X)              ← physical: nobody else may mutate this page
allocate slot, write record       ← page is now correct in memory
lock_object on (page, slot) OID   ← logical: claim transactional visibility
UNLATCH page                      ← physical exclusion ends here

... continue with the rest of the txn (latch released, lock retained) ...

at commit: lock_unlock_object     ← logical lock finally released

• 페이지 래치는 마이크로초 단위로 산다 — 바이트가 변하는 동안만.
• 행 잠금은 분에서 시간 단위로 산다 — 트랜잭션이 커밋할 때까지.
• 두 시간 척도는 자릿수부터 다르다. 둘을 섞으면 구조적 버그다:
  • 페이지 임계 구역 동안 lock을 보유하면 워크로드 전체가 그 페이지로 직렬화된다.
  • 네트워크 왕복 동안 latch를 보유하면 워크로드 전체가 그 스레드로 직렬화된다.
• B-tree 분할은 latch만 쓴다 — 트랜잭션 가시성과는 무관하다.

부록 B — 잠금 테이블 해시는 모듈로가 아니다

// lock_get_hash_value — src/transaction/lock_manager.c
next_base_slotid = 2;
while (next_base_slotid <= slotid)
  next_base_slotid *= 2;
addr = pageid + (htsize / next_base_slotid)
              * (2 * slotid - next_base_slotid + 1);
return addr % htsize;

• 한 힙 페이지의 연속 슬롯들이 성큼성큼 벌어진다 (van Emde Boas 스타일) — 행을 순서대로 잠그는 스캔이 멀리 떨어진 버킷을 타격하므로 병렬 스캔 사이에 체인 경합이 없다.
• slotid ≤ 0 (인덱스 last-key OID는 -1)이면 단순한 pageid - slotid로 후퇴한다.

부록 C — Q&A: 해제는 엔트리를 어떻게 떼어내는가

"트랜잭션이 커밋할 때 잠금 테이블에서 자기 엔트리를 검색하나요?" — 아니다. 커밋은 자신의 hold list들을 걸으며 엔트리 포인터를 손에 쥔 채 unlock을 부른다 (§dual-view). 남는 순회는 자원의 holder list에서 그 엔트리를 빼내는 일뿐이다:

// lock_internal_perform_unlock_object — src/transaction/lock_manager.c
/* resource-side list is singly linked — find prev to splice */
prev = NULL;  curr = res_ptr->holder;
while (curr != NULL) {
  if (curr->tran_index == tran_index) break;
  prev = curr;  curr = curr->next;
}
if (prev == NULL) res_ptr->holder = curr->next;
else              prev->next = curr->next;