CUBRID Lock Manager — 코드 수준 심층 분석

이 문서의 위치: 상위 분석서 cubrid-lock-manager.md가 설계 의도와 이론적 배경을 다룬다면, 이 문서는 코드 수준에서 모든 분기와 필드를 추적하는 심층 분석서다. 각 챕터는 독립적으로 읽을 수 있지만, 순서대로 읽으면 lock 요청 한 건이 커널 안에서 거치는 전체 생애주기를 따라갈 수 있다.

목차:

Ch	제목	상태
1	자료구조 전체 지도	✅
2	초기화와 메모리 관리	✅
3	Lock 획득 — lock_internal_perform_lock_object 완전 해부	✅
4	Lock 변환과 재진입	✅
5	Lock 해제와 NON2PL 프로토콜	✅
6	Lock Escalation	✅
7	Suspend/Resume와 Timeout	✅
8	Deadlock Detection — WFG 구축과 Cycle 탐지	✅
9	특수 경로들 — instant lock, composite lock, lock_scan	✅

Chapter 1: 자료구조 전체 지도

Lock manager의 모든 동작은 다섯 개의 구조체 위에서 벌어진다. 이 챕터에서는 각 구조체의 모든 필드를 코드와 함께 짚고, 필드 간 포인터 관계를 지도로 그린다. 이후 챕터의 흐름을 따라가려면 이 지도가 머릿속에 있어야 한다.

1.1 다섯 핵심 구조체 — 전체 관계

flowchart TB
  subgraph GLOBAL["lk_Gl (LK_GLOBAL_DATA) — 시스템 전체에 하나"]
    HT["m_obj_hash_table\n(lockfree hashmap)"]
    TLT["tran_lock_table[0..N]\n(LK_TRAN_LOCK 배열)"]
    FREE["obj_free_entry_list\n(LF_FREELIST)"]
    WFG["TWFG_node[] / TWFG_edge[]\n(데드락 감지용)"]
  end

  subgraph RES["LK_RES — lockable resource 하나"]
    KEY["key: LK_RES_KEY"]
    AGG["total_holders_mode\ntotal_waiters_mode"]
    HL["holder -> waiter -> non2pl"]
  end

  subgraph ENTRY["LK_ENTRY — lock 한 건"]
    E_RES["res_head -> LK_RES"]
    E_MODE["granted_mode / blocked_mode"]
    E_LINK["next (resource 쪽)\ntran_next/tran_prev (tran 쪽)"]
    E_CLASS["class_entry -> 상위 class"]
  end

  subgraph TRAN["LK_TRAN_LOCK — 트랜잭션 하나의 lock 현황"]
    ROOT["root_class_hold"]
    CLS["class_hold_list"]
    INST["inst_hold_list"]
    POOL["lk_entry_pool\n(로컬 풀, 최대 10개)"]
    N2PL["non2pl_list"]
  end

  HT --> RES
  TLT --> TRAN
  RES -.-> ENTRY
  TRAN -.-> ENTRY
  ENTRY --> RES
  ENTRY --> TRAN

Figure 1-1 — 다섯 구조체의 관계. 화살표는 포인터 방향이다. LK_ENTRY가 LK_RES(resource 뷰)와 LK_TRAN_LOCK(transaction 뷰) 양쪽에 동시에 연결되는 것이 핵심이다.

1.2 `LK_RES_KEY` — lock resource의 식별자

어떤 객체에 lock을 걸 것인가를 식별하는 key다. hash table의 조회 key로 쓰인다.

// struct lk_res_key — src/transaction/lock_manager.h
struct lk_res_key
{
  LOCK_RESOURCE_TYPE type;   /* INSTANCE, CLASS, ROOT_CLASS */
  OID oid;                   /* target object's OID */
  OID class_oid;             /* owning class OID (instance only) */
};

필드	크기	설명
`type`	`enum` (4B)	`LOCK_RESOURCE_INSTANCE`, `LOCK_RESOURCE_CLASS`, `LOCK_RESOURCE_ROOT_CLASS` 중 하나. `LOCK_RESOURCE_OBJECT`는 폐기됨.
`oid`	8B (`pageid` 4B + `slotid` 2B + `volid` 2B)	lock 대상 객체의 식별자.
`class_oid`	8B	instance lock에서만 유효. class/root-class lock에서는 NULL OID.

type은 oid와 class_oid로부터 결정된다. lock_create_search_key가 이 규칙을 구현한다:

// lock_create_search_key — src/transaction/lock_manager.c
static LK_RES_KEY
lock_create_search_key (OID * oid, OID * class_oid)
{
  LK_RES_KEY search_key;
  // ... OID copying ...

  if (oid != NULL && OID_IS_ROOTOID (oid))
    {
      search_key.type = LOCK_RESOURCE_ROOT_CLASS;
    }
  else if (class_oid == NULL || OID_IS_ROOTOID (class_oid))
    {
      search_key.type = LOCK_RESOURCE_CLASS;
    }
  else
    {
      search_key.type = LOCK_RESOURCE_INSTANCE;
    }
  return search_key;
}

도출 규칙을 표로 정리하면 다음과 같다:

조건	`type`	의미
`oid`가 root OID	`ROOT_CLASS`	데이터베이스 전체를 대표하는 root class
`class_oid`가 NULL 또는 root OID	`CLASS`	테이블(class) 자체에 대한 lock
그 외	`INSTANCE`	테이블 안의 개별 행(instance)에 대한 lock

hash table 비교 시 type은 무시되고 oid만 비교한다. lock_res_key_compare는 OID_EQ(&k1->oid, &k2->oid)만 체크하고 type은 assert로만 확인한다. 하나의 OID가 두 가지 resource type으로 동시에 존재할 수 없다는 불변식에 의존하는 것이다.

1.3 `LK_RES` — lock resource (lockable object 하나의 상태)

하나의 lockable object(database, class, instance)에 대한 모든 lock 상태를 담는다. LK_RES_KEY로 hash table에서 조회된다.

// struct lk_res — src/transaction/lock_manager.h
struct lk_res
{
  LK_RES_KEY key;              /* hash key — see 1.2 */
  LOCK total_holders_mode;     /* aggregate mode of all current holders */
  LOCK total_waiters_mode;     /* aggregate mode of all current waiters */
  LK_ENTRY *holder;            /* head of granted-lock linked list */
  LK_ENTRY *waiter;            /* head of blocked-lock linked list */
  LK_ENTRY *non2pl;            /* head of early-released-lock tracking list */
  pthread_mutex_t res_mutex;   /* per-resource mutex */
  LK_RES *hash_next;           /* hash-bucket collision chain */
  LK_RES *stack;               /* lock-free freelist retired stack */
  UINT64 del_id;               /* lock-free reclamation epoch ID */
};

각 필드의 역할:

필드	역할	존재 이유
`total_holders_mode`	grant된 모든 lock의 LUB(least upper bound)	compatibility check를 O(1)로 만든다. holder list를 순회하지 않고 이 값 하나와 비교하면 된다.
`total_waiters_mode`	대기 중인 모든 lock의 LUB	starvation guard: 새 요청이 holder와만 호환되더라도, 이미 대기 중인 더 강한 요청을 건너뛰는 것을 방지한다.
`holder`	grant된 `LK_ENTRY`의 singly-linked list	`LK_ENTRY.next`로 연결. 여러 트랜잭션이 동시에 같은 resource를 hold할 수 있다(예: 다수의 S_LOCK).
`waiter`	block된 `LK_ENTRY`의 singly-linked list	FIFO 순서. 맨 앞이 가장 먼저 대기한 요청이다.
`non2pl`	READ COMMITTED에서 조기 해제된 S lock의 흔적	같은 트랜잭션이 나중에 다시 읽을 때 conflict detection에 사용한다.
`res_mutex`	resource별 mutex	holder/waiter/non2pl list 조작 시 보호. resource 단위이므로 서로 다른 resource에 대한 lock 요청은 완전히 병렬로 처리된다.

total_holders_mode의 재계산 시점: holder list에 entry가 추가되거나, 제거되거나, 변환될 때마다 전체 holder list를 순회하여 LUB를 다시 계산한다. 이 과정은 res_mutex 아래에서 실행되므로 resource 단위로 직렬화된다.

1.4 `LK_ENTRY` — lock 한 건 (dual-threaded record)

Lock manager에서 가장 중요한 구조체다. lock 한 건을 나타내되, resource 뷰와 transaction 뷰 양쪽에 동시에 연결된다.

// struct lk_entry — src/transaction/lock_manager.h
struct lk_entry
{
  struct lk_res *res_head;     /* back-pointer to owning resource */
  THREAD_ENTRY *thrd_entry;    /* requesting thread (valid only when blocked) */
  int tran_index;              /* owning transaction's index */
  LOCK granted_mode;           /* currently granted mode */
  LOCK blocked_mode;           /* requested mode when blocked */
  int count;                   /* re-entrance counter */
  UINT64 del_id;               /* lock-free reclamation */
  LK_ENTRY *stack;             /* freelist retired stack */
  LK_ENTRY *next;              /* resource view: next in holder/waiter list */
  LK_ENTRY *tran_next;         /* transaction view: next lock of same tran */
  LK_ENTRY *tran_prev;         /* transaction view: prev lock of same tran */
  LK_ENTRY *class_entry;       /* parent class's LK_ENTRY (for instance locks) */
  int ngranules;               /* count of instance locks below this class lock */
  int instant_lock_count;      /* instant lock request count */
  int bind_index_in_tran;
  XASL_ID xasl_id;             /* query plan ID that requested this lock */
};

LK_ENTRY는 grant된 holder, block된 waiter, non2pl marker라는 세 가지 역할 중 하나를 맡는다. 역할에 따라 유효한 필드가 달라진다:

필드	holder (grant됨)	waiter (block됨)	non2pl	설명
`res_head`	✓	✓	✓	항상 유효. 이 lock이 어떤 resource에 속하는지.
`thrd_entry`	NULL	✓	NULL	waiter에서만 유효. resume할 thread를 가리킨다.
`tran_index`	✓	✓	✓	이 lock을 소유한 트랜잭션.
`granted_mode`	현재 mode	`NULL_LOCK`	해제 전 mode	holder에서는 실제 lock mode. waiter에서는 아직 grant되지 않았으므로 NULL_LOCK.
`blocked_mode`	`NULL_LOCK`	요청 mode	`NULL_LOCK`	waiter에서는 요청 중인 mode. conversion wait 중에는 holder가 `blocked_mode != NULL_LOCK`일 수 있다. `granted_mode`가 현재 hold 중인 mode이고, `blocked_mode`가 upgrade 대상 mode다.
`count`	>= 1	1	0	재진입 카운터. 같은 트랜잭션이 같은 resource와 mode를 n번 요청하면 count가 n이 된다. non2pl에서는 항상 0.
`next`	holder list 내 다음	waiter list 내 다음	non2pl list 내 다음	resource 뷰 연결. singly-linked.
`tran_next`/`tran_prev`	✓	—	✓	transaction 뷰 연결. doubly-linked. waiter는 transaction hold list에 포함되지 않는다.
`class_entry`	상위 class의 `LK_ENTRY`	—	—	instance lock에서 class lock으로의 한 단계 역참조. escalation에 사용된다.
`ngranules`	하위 instance lock 수	—	—	class lock에서만 의미 있다. escalation 임계값과 비교. instance lock에서는 0.
`instant_lock_count`	instant mode lock 수	—	—	`lock_start_instant_lock_mode` / `lock_stop_instant_lock_mode`가 관리.

핵심 불변식: granted_mode와 blocked_mode의 배타적 사용

Entry in holder list:
  granted_mode = actual held mode (S, X, IS, IX, ...)
  blocked_mode = NULL_LOCK (normal) or upgrade-target mode (conversion wait)

Entry in waiter list:
  granted_mode = NULL_LOCK
  blocked_mode = requested mode

필드 쌍을 상태로 읽어라. entry는 (자원, 트랜잭션)당 하나다. 필드 쌍과 entry가 꿰인 리스트의 조합이 곧 그 자원에 대한 트랜잭션의 상태다 — holder list의 X/–: 일반 holder · holder list의 IX/SIX: upgrader(일부만 획득, 대기 중인 목표 보유) · waiter list의 –/X: waiter(아직 아무것도 획득하지 못함). 용어 주의: blocked_mode는 대기 중인 목표(pending target)이지 “의도(intention)“가 아니다 — 그 단어는 intention mode인 IS/IX/SIX의 몫이다.

이 불변식은 두 초기화 함수가 강제한다:

// lock_initialize_entry_as_granted — src/transaction/lock_manager.c
static void
lock_initialize_entry_as_granted (LK_ENTRY * entry_ptr, int tran_index,
                                  LK_RES * res, LOCK lock)
{
  entry_ptr->granted_mode  = lock;       /* actual mode */
  entry_ptr->blocked_mode  = NULL_LOCK;  /* not waiting */
  entry_ptr->count         = 1;
  // ...
}

// lock_initialize_entry_as_blocked — src/transaction/lock_manager.c
static void
lock_initialize_entry_as_blocked (LK_ENTRY * entry_ptr, THREAD_ENTRY * thread_p,
                                  int tran_index, LK_RES * res, LOCK lock)
{
  entry_ptr->granted_mode  = NULL_LOCK;  /* not yet granted */
  entry_ptr->blocked_mode  = lock;       /* requested mode */
  entry_ptr->count         = 1;
  // ...
}

conversion wait은 양쪽 필드가 모두 non-NULL인 예외적 상태다. 예를 들어 tran 7이 S_LOCK을 hold한 상태에서 X_LOCK으로 upgrade를 요청하면:

granted_mode = S_LOCK (여전히 hold 중)
blocked_mode = X_LOCK (upgrade 대기 중)
entry는 holder list에 그대로 남아 있되, lock_position_holder_entry에 의해 재배치된다. Ch. 4에서 자세히 다룬다.

1.5 `LK_TRAN_LOCK` — 트랜잭션 하나의 lock 전체 현황

// struct lk_tran_lock — src/transaction/lock_manager.c
struct lk_tran_lock
{
  pthread_mutex_t hold_mutex;    /* protects hold lists */
  LK_ENTRY *inst_hold_list;     /* instance lock hold list */
  LK_ENTRY *class_hold_list;    /* class lock hold list */
  LK_ENTRY *root_class_hold;    /* root class lock (at most one) */
  LK_ENTRY *lk_entry_pool;      /* local pool of reusable LK_ENTRY */
  int lk_entry_pool_count;       /* current count in pool */
  int inst_hold_count;           /* number of instance locks held */
  int class_hold_count;          /* number of class locks held */

  LK_ENTRY *waiting;             /* currently blocked lock entry (at most one) */

  pthread_mutex_t non2pl_mutex;  /* protects non2pl_list */
  LK_ENTRY *non2pl_list;         /* early-released lock tracking list */
  int num_incons_non2pl;         /* inconsistent non2pl count */

  bool lock_escalation_on;       /* escalation-in-progress guard */
  bool is_instant_duration;      /* instant lock mode on/off */
};

hold list를 세 개로 분리한 이유:

flowchart TB
  TRAN["LK_TRAN_LOCK (tran #7)"]
  ROOT["root_class_hold\n(최대 1개)"]
  CLS["class_hold_list\n-> entry(class A, IX)\n-> entry(class B, IS)\n-> ..."]
  INST["inst_hold_list\n-> entry(row A.1, X)\n-> entry(row A.2, S)\n-> ..."]

  TRAN --> ROOT
  TRAN --> CLS
  TRAN --> INST

Figure 1-2 — 세 갈래 hold list 분리. root/class/instance를 분리하면 “이 트랜잭션이 class A에 어떤 lock을 갖고 있는가?”라는 질문에 class list만 순회하면 된다. 전체 lock을 모두 스캔하는 대신 O(class 수)로 답할 수 있다.

필드	설명
`hold_mutex`	inst/class/root hold list 조작 시 사용. `res_mutex`와는 별개다. 한 트랜잭션이 서로 다른 resource의 lock을 조작할 때 교차 잠금이 필요하다.
`lk_entry_pool`	트랜잭션별로 최대 `LOCK_TRAN_LOCAL_POOL_MAX_SIZE = 10`개의 `LK_ENTRY`를 로컬 캐시한다. `lock_get_new_entry`가 이 풀을 먼저 확인하고, 비어 있을 때만 global `obj_free_entry_list`로 넘어간다. 목적: OLTP 핫 패스에서 global freelist에 대한 경합을 줄이는 것이다.
`waiting`	이 트랜잭션이 현재 block되어 있는 단일 `LK_ENTRY`. 한 트랜잭션은 한 번에 최대 한 개의 lock에서만 대기할 수 있다(하나의 thread가 하나의 lock 요청에서 suspend).
`non2pl_list`	READ COMMITTED에서 S lock이 조기 해제될 때 `LK_ENTRY`가 이 리스트로 이동한다. 다른 트랜잭션이 같은 resource에 X lock을 시도할 때 이 리스트를 확인하여 비일관성을 감지한다.
`lock_escalation_on`	escalation 진행 중 재진입 방지 guard.
`is_instant_duration`	`lock_start_instant_lock_mode`로 켜진다. 이 mode에서 획득한 lock은 statement 종료 시 해제된다.

1.6 `LK_GLOBAL_DATA` — 전역 싱글턴 `lk_Gl`

시스템 전체에 정확히 하나의 인스턴스가 존재한다. 모든 lock 상태의 루트다.

// struct lk_global_data — src/transaction/lock_manager.c
struct lk_global_data
{
  int max_obj_locks;                          /* max lock count set at init */
  lk_hashmap_type m_obj_hash_table;           /* OID -> LK_RES lockfree hashmap */
  LF_FREELIST obj_free_entry_list;            /* global LK_ENTRY freelist */

  int num_trans;                              /* number of initialized transactions */
  LK_TRAN_LOCK *tran_lock_table;             /* per-tran LK_TRAN_LOCK array */

  pthread_mutex_t DL_detection_mutex;         /* deadlock detection guard */
  struct timeval last_deadlock_run;           /* timestamp of last deadlock scan */
  LK_WFG_NODE *TWFG_node;                    /* WFG node array (per-tran) */
  LK_WFG_EDGE *TWFG_edge;                    /* WFG edge array */
  int max_TWFG_edge;                          /* max edge array size */
  int TWFG_free_edge_idx;                     /* next free edge index */
  int global_edge_seq_num;                    /* edge creation sequence number */

  short no_victim_case_count;
  bool verbose_mode;
  std::atomic_int deadlock_and_timeout_detector;
};

LK_GLOBAL_DATA lk_Gl;   /* global instance — file scope */

전체 메모리 할당 전략:

flowchart TB
  REQ["lock 요청 -> LK_ENTRY 필요"]
  LP["1. 트랜잭션 로컬 풀\n(lk_entry_pool, 최대 10개)"]
  GF["2. global freelist\n(obj_free_entry_list)"]
  MA["3. malloc으로 새 블록 할당"]

  REQ --> LP
  LP -- "비어 있음" --> GF
  GF -- "비어 있음" --> MA

  REL["lock 해제 -> LK_ENTRY 반환"]
  LP2["1. 로컬 풀에 반환\n(10개 미만이면)"]
  GF2["2. global freelist에 반환"]

  REL --> LP2
  LP2 -- "풀이 가득 참" --> GF2

Figure 1-3 — 3단계 LK_ENTRY 할당/반환 전략. 할당: 로컬 풀 -> global freelist -> malloc. 반환: 역순. lock_get_new_entry와 lock_free_entry가 이를 구현한다.

1.7 Lock mode — 12가지 `LOCK` enum과 두 정적 테이블

// enum LOCK — src/transaction/lock_table.h
typedef enum
{
  NA_LOCK = 0,
  INCON_NON_TWO_PHASE_LOCK = 1,  /* NON2PL */
  NULL_LOCK = 2,
  SCH_S_LOCK = 3,
  IS_LOCK = 4,
  S_LOCK = 5,
  IX_LOCK = 6,
  BU_LOCK = 7,
  SIX_LOCK = 8,
  U_LOCK = 9,
  X_LOCK = 10,
  SCH_M_LOCK = 11,
  LOCK_COUNT    /* = 12 */
} LOCK;

모든 mode 판단을 주도하는 두 개의 12x12 정적 테이블이 있다:

lock_Comp[requested][current] — 호환성 테이블:

LOCK_COMPAT_YES: 새 요청이 기존 lock과 공존 가능
LOCK_COMPAT_NO: 충돌 — 새 요청은 대기해야 함
LOCK_COMPAT_UNKNOWN: 실제로 발생할 수 없는 조합 (assert로 보호)

lock_Conv[requested][current] — 변환 테이블:

같은 트랜잭션이 이미 current를 hold하고 requested를 요청할 때, 결과 mode는 lock_Conv[requested][current](두 mode의 LUB)
NA_LOCK 결과: 이 변환은 정의되지 않음 (assert 실패)

// inline accessors — src/transaction/lock_table.h
inline LOCK
lock_conv (LOCK requested, LOCK current)
{
  assert (lock_Conv[requested][current] != NA_LOCK);
  return lock_Conv[requested][current];
}

inline LOCK_COMPATIBILITY
lock_compat (LOCK requested, LOCK current)
{
  assert (lock_Comp[requested][current] != LOCK_COMPAT_UNKNOWN);
  return lock_Comp[requested][current];
}

변환 예시 (lock_Conv에서 직접 읽을 수 있다):

현재 hold	새 요청	결과 (LUB)	의미
`IS_LOCK`	`IX_LOCK`	`IX_LOCK`	intention shared -> intention exclusive upgrade
`S_LOCK`	`IX_LOCK`	`SIX_LOCK`	shared + intention exclusive = SIX
`S_LOCK`	`X_LOCK`	`X_LOCK`	shared -> exclusive upgrade
`IX_LOCK`	`S_LOCK`	`SIX_LOCK`	IX + S = SIX (대칭)
`U_LOCK`	`X_LOCK`	`X_LOCK`	update -> exclusive upgrade

1.8 포인터 관계 요약 — 하나의 lock이 연결되는 모든 곳

하나의 LK_ENTRY가 연결되는 모든 경로:

flowchart LR
  subgraph Resource["LK_RES (resource R)"]
    direction TB
    RH["holder list"]
    RW["waiter list"]
    RN["non2pl list"]
  end

  subgraph Tran["LK_TRAN_LOCK (tran T)"]
    direction TB
    TI["inst_hold_list"]
    TC["class_hold_list"]
    TR["root_class_hold"]
    TN["non2pl_list"]
  end

  E["LK_ENTRY\n(tran T, resource R)"]

  RH -- "next" --> E
  E -- "res_head" --> Resource
  TI -- "tran_next/prev" --> E
  E -- "class_entry" --> CE["LK_ENTRY\n(tran T, class of R)"]
  CE -- "ngranules++" --> CE

Figure 1-4 — 하나의 LK_ENTRY에 관련된 모든 포인터 관계. next는 resource 뷰, tran_next/tran_prev는 transaction 뷰, class_entry는 세분화 계층의 다리, res_head는 역참조다.

1.9 챕터 요약 — 핵심 포인트

LK_ENTRY는 dual-threaded record다. 하나의 lock 사실이 resource 뷰(next)와 transaction 뷰(tran_next/tran_prev) 양쪽에 동시에 존재한다.
total_holders_mode와 total_waiters_mode가 O(1) 호환성 체크를 가능하게 한다. 새 요청은 전체 holder list를 순회하는 대신 두 개의 aggregate 값만 비교하면 된다.
granted_mode와 blocked_mode의 조합이 entry의 상태를 결정한다:
- granted != NULL_LOCK, blocked == NULL_LOCK -> 정상 holder
- granted == NULL_LOCK, blocked != NULL_LOCK -> waiter
- granted != NULL_LOCK, blocked != NULL_LOCK -> conversion wait 중인 holder
메모리 할당은 3단계: 로컬 풀(10개) -> global freelist -> malloc.
**resource별 res_mutex**가 resource 단위의 직렬화를 제공하므로, 서로 다른 resource에 대한 lock 요청은 완전히 병렬로 진행된다.

Chapter 2: 초기화와 메모리 관리

Lock manager는 서버 시작 시 lock_initialize에 의해 한 번 부트스트랩되고, lock_finalize에 의해 해체된다. 이 챕터에서는 초기화 순서를 단계별로 추적한 뒤, 런타임 메모리 관리 — 3단계 할당 전략과 lockfree 인프라와의 통합 — 을 살펴본다.

2.1 `lock_initialize` — 최상위 진입점

// lock_initialize — src/transaction/lock_manager.c
int
lock_initialize (void)
{
  error_code = lock_initialize_tran_lock_table ();  /* step 1 */
  lock_initialize_object_hash_table ();              /* step 2 */
  error_code = lock_initialize_object_lock_entry_list (); /* step 3 */
  error_code = lock_initialize_deadlock_detection (); /* step 4 */
  // ... env-var checks for verbose/dump mode ...
  lock_deadlock_detect_daemon_init ();               /* step 5 */
  return error_code;
}

순서가 중요하다. step 1이 step 4보다 먼저 완료되어야 하는 이유는 lock_initialize_deadlock_detection이 lk_Gl.num_trans(step 1에서 설정)를 읽어 WFG node 배열 크기를 결정하기 때문이다.

flowchart LR
  INIT["lock_initialize"]
  S1["1. tran_lock_table\nMAX_NTRANS 슬롯\n+ 각 10개 entry"]
  S2["2. obj_hash_table\nlockfree hashmap\nMAX(10K, NTRANS*300)"]
  S3["3. obj_free_entry_list\nlockfree freelist"]
  S4["4. deadlock detection\nTWFG_node[num_trans]"]
  S5["5. deadlock daemon\n100ms 루프"]

  INIT --> S1 --> S2 --> S3 --> S4 --> S5

Figure 2-1 — lock_initialize 순서. 각 단계는 이전 단계의 출력에 의존한다. deadlock daemon(step 5)이 마지막인 이유는 모든 자료구조가 준비된 후에야 실행할 수 있기 때문이다.

2.2 Step 1 — `lock_initialize_tran_lock_table`

트랜잭션별 lock 상태 테이블을 할당하고 초기화한다.

// lock_initialize_tran_lock_table — src/transaction/lock_manager.c
static int
lock_initialize_tran_lock_table (void)
{
  num_trans = MAX_NTRANS;
  lk_Gl.tran_lock_table =
    (LK_TRAN_LOCK *) malloc (SIZEOF_LK_TRAN_LOCK * num_trans);
  memset (lk_Gl.tran_lock_table, 0, SIZEOF_LK_TRAN_LOCK * num_trans);

  for (i = 0; i < num_trans; i++)
    {
      tran_lock = &lk_Gl.tran_lock_table[i];
      pthread_mutex_init (&tran_lock->hold_mutex, NULL);
      pthread_mutex_init (&tran_lock->non2pl_mutex, NULL);

      /* pre-fill local entry pool */
      for (j = 0; j < LOCK_TRAN_LOCAL_POOL_MAX_SIZE; j++)  /* = 10 */
        {
          entry = (LK_ENTRY *) malloc (sizeof (LK_ENTRY));
          lock_initialize_entry (entry);
          entry->next = tran_lock->lk_entry_pool;
          tran_lock->lk_entry_pool = entry;
        }
      tran_lock->lk_entry_pool_count = LOCK_TRAN_LOCAL_POOL_MAX_SIZE;
    }
  return NO_ERROR;
}

주목할 점:

MAX_NTRANS개의 슬롯이 미리 할당된다. 이는 컴파일 타임 상수이며 런타임 파라미터가 아니다. 실제 활성 트랜잭션 수와 무관하게 0부터 MAX_NTRANS - 1까지 모든 tran_index에 LK_TRAN_LOCK이 할당된다.
각 슬롯에 10개의 LK_ENTRY가 미리 할당된다. 직접 malloc으로 할당되어 lk_entry_pool singly-linked list에 들어간다. 이것이 Ch. 1 section 1.6의 Tier 1 로컬 풀이다.
트랜잭션당 두 개의 mutex: hold_mutex(세 hold list 보호)와 non2pl_mutex(non2pl list 보호). 분리된 이유는 lock 해제 시 서로 다른 코드 경로에서 hold list와 non2pl list를 동시에 조작할 수 있기 때문이다.
나머지 필드는 모두 memset으로 0 초기화된다. 이는 곧: inst_hold_list = NULL, class_hold_list = NULL, root_class_hold = NULL, waiting = NULL, non2pl_list = NULL, lock_escalation_on = false, is_instant_duration = false.

2.3 Step 2 — `lock_initialize_object_hash_table`

LK_RES_KEY -> LK_RES 매핑을 위한 lockfree hashmap을 설정한다.

// lock_initialize_object_hash_table — src/transaction/lock_manager.c
static void
lock_initialize_object_hash_table (void)
{
  lk_Gl.max_obj_locks = 10000;  /* LK_INITIAL_OBJECT_LOCK_TABLE_SIZE */
  const int obj_hash_size =
    MAX (lk_Gl.max_obj_locks, LK_MIN_OBJECT_LOCKS);
    /* LK_MIN_OBJECT_LOCKS = MAX_NTRANS * 300 */

  lk_Gl.m_obj_hash_table.init (
    obj_lock_res_Ts, THREAD_TS_OBJ_LOCK_RES,
    obj_hash_size, block_size, block_count,
    lk_Obj_lock_res_desc);
}

hash table은 lockfree_hashmap<LK_RES_KEY, LK_RES>로, CUBRID의 lockfree 인프라가 제공하는 범용 lockfree hash table이다(cubrid-lockfree-hashmap.md 참조). lock manager는 자신만의 동작을 LF_ENTRY_DESCRIPTOR를 통해 주입한다:

// lk_Obj_lock_res_desc — src/transaction/lock_manager.c
LF_ENTRY_DESCRIPTOR lk_Obj_lock_res_desc = {
  offsetof (LK_RES, stack),      /* retired-entry stack pointer */
  offsetof (LK_RES, hash_next),  /* hash collision chain */
  offsetof (LK_RES, del_id),     /* epoch ID for reclamation */
  offsetof (LK_RES, key),        /* key location */
  offsetof (LK_RES, res_mutex),  /* per-entry mutex */
  LF_EM_USING_MUTEX,             /* each LK_RES has its own mutex */
  LF_ENTRY_DESCRIPTOR_MAX_ALLOC,
  lock_alloc_resource,           /* malloc + pthread_mutex_init */
  lock_dealloc_resource,         /* pthread_mutex_destroy + free */
  lock_init_resource,            /* zero out holders/waiters/non2pl */
  lock_uninit_resource,          /* assert lists are empty */
  lock_res_key_copy,
  lock_res_key_compare,          /* OID_EQ only — type is assert-checked */
  lock_res_key_hash,             /* delegates to LK_OBJ_LOCK_HASH macro */
  NULL                           /* no insert callback */
};

hash 함수(lock_res_key_hash -> LK_OBJ_LOCK_HASH -> lock_get_hash_value)를 자세히 볼 필요가 있다:

// lock_get_hash_value — src/transaction/lock_manager.c
static unsigned int
lock_get_hash_value (const OID * oid, int htsize)
{
  if (oid->slotid <= 0)
    {
      addr = oid->pageid - oid->slotid;
    }
  else
    {
      next_base_slotid = 2;
      while (next_base_slotid <= (unsigned) oid->slotid)
        next_base_slotid *= 2;

      addr = oid->pageid
             + (htsize / next_base_slotid)
               * (2 * oid->slotid - next_base_slotid + 1);
    }
  return (addr % htsize);
}

단순한 modulo hash가 아니다. 양수 slotid에 대해 van Emde Boas 스타일의 비트 인터리브를 사용하여, 같은 페이지 안의 연속 slot ID들을 서로 다른 hash bucket에 분산시킨다. 의도는 이렇다: 같은 heap page에 있는 행들(scan 순서대로 함께 lock되는 경향이 있다)이 hash table 전체에 퍼지도록 하여, bucket chain 경합을 줄이는 것이다.

slotid <= 0인 경우(index key — unique index의 last-key OID는 slotid = -1 을 사용한다)는 더 단순한 pageid - slotid 계산으로 대체한다.

계산 예시 — page 100에 있는 행들의 hash 분포:

htsize = 6000(작은 예시)이라 가정하자. 같은 heap page(pageid=100)에 있는 6개 행(slotid 1-6):

OID (pageid, slotid)	next_base_slotid	addr 계산식	addr	bucket (addr % 6000)
(100, 1)	2	100 + (6000/2) * (2*1 - 2 + 1) = 100 + 3000	3100	3100
(100, 2)	4	100 + (6000/4) * (2*2 - 4 + 1) = 100 + 1500	1600	1600
(100, 3)	4	100 + (6000/4) * (2*3 - 4 + 1) = 100 + 4500	4600	4600
(100, 4)	8	100 + (6000/8) * (2*4 - 8 + 1) = 100 + 750	850	850
(100, 5)	8	100 + (6000/8) * (2*5 - 8 + 1) = 100 + 2250	2350	2350
(100, 6)	8	100 + (6000/8) * (2*6 - 8 + 1) = 100 + 3750	3850	3850

6개 행 모두 서로 다른 bucket에 떨어진다(3100, 1600, 4600, 850, 2350, 3850). 단순한 pageid * 31 + slotid hash였다면 6개가 인접한 bucket에 몰렸을 것이다. van Emde Boas 스타일의 stride 덕분에, heap page scan으로 행 1, 2, 3, … 순서로 lock을 걸 때 넓게 분산된 bucket을 hit하여, 동시 scan 환경에서 hash chain 경합을 최소화한다.

lock 요청 후의 hash table 구조:

flowchart TB
  subgraph HT["m_obj_hash_table (lockfree hashmap, 6000 buckets)"]
    B850["bucket 850"]
    B1600["bucket 1600"]
    B3100["bucket 3100"]
    B3850["bucket 3850"]
    BDOT["..."]
  end

  R1["LK_RES\nkey: (100,4) class\ntotal_holders: IX\nholder -> waiter -> non2pl"]
  R2["LK_RES\nkey: (100,2) inst\ntotal_holders: X\nholder -> ..."]
  R3["LK_RES\nkey: (100,1) inst\ntotal_holders: S\nholder -> ..."]
  R4["LK_RES\nkey: (200,3) inst\ntotal_holders: S\nholder -> ..."]

  B850 --> R1
  B1600 --> R2
  B3100 --> R3
  R3 -. "hash_next\n(충돌)" .-> R4
  B3850 -. "비어 있음" .-> EMPTY["NULL"]

Figure 2-2 — page 100과 200의 행을 lock한 후의 hash table. 각 bucket은 LK_RES chain을 가리킨다. 대부분의 bucket에는 단일 entry만 있다(hash 함수의 목표). 충돌(여기서 bucket 3100: OID (100,1)과 (200,3)이 우연히 충돌)은 hash_next singly-linked chain으로 해결한다. 각 LK_RES는 자체 res_mutex를 가지므로, 서로 다른 bucket을 접근하는 thread는 절대로 경합하지 않는다.

OID에서 lock grant까지의 전체 흐름 (hash table의 역할):

flowchart LR
  OID["OID (100, 2, 5)\npageid=100, slotid=2, volid=5"]
  KEY["lock_create_search_key\n-> LK_RES_KEY\n  type=INSTANCE\n  oid=(100,2,5)\n  class_oid=(50,1,5)"]
  HASH["lock_res_key_hash\n-> bucket 1600"]
  FIND["m_obj_hash_table\n.find_or_insert\n(lockfree)"]
  RES["LK_RES 발견/생성\nres_mutex 획득"]
  CHECK["total_holders_mode,\ntotal_waiters_mode와\n호환성 체크"]

  OID --> KEY --> HASH --> FIND --> RES --> CHECK

Figure 2-3 — OID에서 호환성 체크까지의 흐름. lockfree hashmap이 global lock 없이 OID를 LK_RES로 resolve한다. resource별 res_mutex는 LK_RES를 찾은 후에야 획득되므로, critical section이 하나의 resource 범위로 좁혀진다.

2.4 Step 3 — `lock_initialize_object_lock_entry_list`

LK_ENTRY 할당을 위한 lockfree freelist(3단계 전략의 Tier 2)를 설정한다.

// lock_initialize_object_lock_entry_list — src/transaction/lock_manager.c
static int
lock_initialize_object_lock_entry_list (void)
{
  block_count = 1;
  block_size = (int) MAX ((lk_Gl.max_obj_locks * LK_ENTRY_RATIO), 1);
  /* LK_ENTRY_RATIO = 0.1f */

  ret = lf_freelist_init (&lk_Gl.obj_free_entry_list,
                           block_count, block_size,
                           &obj_lock_entry_desc, &obj_lock_ent_Ts);
  return ret;
}

LK_ENTRY descriptor는 LK_RES descriptor와 한 가지 결정적인 차이가 있다:

// obj_lock_entry_desc — src/transaction/lock_manager.c
LF_ENTRY_DESCRIPTOR obj_lock_entry_desc = {
  offsetof (LK_ENTRY, stack),
  offsetof (LK_ENTRY, next),
  offsetof (LK_ENTRY, del_id),
  0,                              /* no key — not in a hash table */
  0,                              /* no mutex offset */
  LF_EM_NOT_USING_MUTEX,          /* ← key difference */
  // ...
  lock_alloc_entry,               /* plain malloc */
  lock_dealloc_entry,             /* plain free */
  // ...
};

LK_ENTRY가 LF_EM_NOT_USING_MUTEX를 사용하는 이유는 자체 mutex를 갖지 않기 때문이다. 보호는 소속 LK_RES.res_mutex 또는 LK_TRAN_LOCK.hold_mutex가 제공한다. 어떤 list를 통해 entry를 조작하느냐에 따라 달라진다.

2.5 Step 4 — `lock_initialize_deadlock_detection`

// lock_initialize_deadlock_detection — src/transaction/lock_manager.c
static int
lock_initialize_deadlock_detection (void)
{
  pthread_mutex_init (&lk_Gl.DL_detection_mutex, NULL);
  gettimeofday (&lk_Gl.last_deadlock_run, NULL);

  lk_Gl.TWFG_node =
    (LK_WFG_NODE *) malloc (SIZEOF_LK_WFG_NODE * lk_Gl.num_trans);
  for (i = 0; i < lk_Gl.num_trans; i++)
    {
      lk_Gl.TWFG_node[i].DL_victim = false;
      lk_Gl.TWFG_node[i].checked_by_deadlock_detector = false;
      lk_Gl.TWFG_node[i].thrd_wait_stime = 0;
    }

  lk_Gl.TWFG_edge = NULL;   /* allocated lazily on first use */
  lk_Gl.max_TWFG_edge = 0;
  lk_Gl.TWFG_free_edge_idx = -1;
  lk_Gl.global_edge_seq_num = 0;
  return NO_ERROR;
}

주목할 점:

WFG node는 트랜잭션별로 할당된다 — tran_index당 하나의 LK_WFG_NODE. step 4가 lk_Gl.num_trans에 의존하므로 step 1 이후에 실행되어야 하는 이유가 바로 이것이다.
WFG edge는 지연 할당된다. TWFG_edge는 NULL로 시작하여 lock_add_WFG_edge가 처음 호출될 때(최초의 실제 lock wait 발생 시) 할당된다. 초기 크기는 LK_MID_TWFG_EDGE_COUNT = 1000이고, 최대는 MAX_NTRANS * MAX_NTRANS다.
**DL_detection_mutex**는 deadlock detection 실행을 직렬화한다. 한 번에 하나의 deadlock scan만 실행된다.

2.6 Step 5 — `lock_deadlock_detect_daemon_init`

// lock_deadlock_detect_daemon_init — src/transaction/lock_manager.c
void
lock_deadlock_detect_daemon_init ()
{
  cubthread::looper looper =
    cubthread::looper (std::chrono::milliseconds (100));
  cubthread::entry_callable_task *daemon_task =
    new cubthread::entry_callable_task (deadlock_detect_task_execute);
  lock_Deadlock_detect_daemon =
    cubthread::get_manager ()->create_daemon (looper, daemon_task,
                                              "deadlock-detect");
}

daemon은 100ms마다 루프를 돌며 반복당 세 가지 작업을 수행한다 (deadlock_detect_task_execute 안에서):

인터럽트 체크 — 외부에서 중단된 트랜잭션의 thread를 resume.
timeout 체크 — lock wait가 wait_msecs 데드라인을 초과한 thread를 resume (lock_force_timeout_expired_wait_transactions).
deadlock detection — 마지막 실행 이후 경과 시간이 PRM_ID_LK_RUN_DEADLOCK_INTERVAL을 초과하고, 최소 두 개의 thread가 suspend되어 있을 때만 lock_detect_local_deadlock을 실행한다. 경합이 낮을 때 불필요한 WFG scan 비용을 회피하기 위함이다.

100ms 루프 주기는 timeout 체크의 정밀도다. wait_msecs = 50인 lock wait는 50ms가 아닌 최대 100ms 이내에 감지된다. deadlock scan 자체는 설정 가능한 interval 파라미터에 의해 제어되므로 더 낮은 빈도로 실행된다.

2.7 `lock_finalize` — 해체

// lock_finalize — src/transaction/lock_manager.c
void
lock_finalize (void)
{
  free_and_init (lk_Gl.TWFG_node);        /* WFG nodes */
  lock_finalize_tran_lock_table ();         /* per-tran state */
  pthread_mutex_destroy (&lk_Gl.DL_detection_mutex);
  lk_Gl.m_obj_hash_table.destroy ();       /* lockfree hashmap */
  lf_freelist_destroy (&lk_Gl.obj_free_entry_list); /* lockfree freelist */
  lock_deadlock_detect_daemon_destroy ();   /* stop daemon */
}

lock_finalize_tran_lock_table은 각 LK_TRAN_LOCK을 순회하며 두 mutex를 destroy하고, lk_entry_pool에 남아 있는 모든 entry를 free로 해제한다. 주의: hold list는 순회하지 않는다. lock_finalize 실행 시점에 모든 트랜잭션은 이미 lock을 해제했거나 강제 abort되어 있어야 한다.

2.8 런타임 3단계 `LK_ENTRY` 할당

section 2.2와 2.4의 초기화에 대응하는 런타임 할당/반환이다. 모든 lock 획득은 LK_ENTRY가 필요하고, 모든 해제는 하나를 반환한다.

// lock_get_new_entry — src/transaction/lock_manager.c
static LK_ENTRY *
lock_get_new_entry (int tran_index, LF_TRAN_ENTRY * tran_entry,
                    LF_FREELIST * freelist)
{
  LK_TRAN_LOCK *tran_lock = &lk_Gl.tran_lock_table[tran_index];

  /* Tier 1: check local pool (no synchronization needed) */
  if (tran_lock->lk_entry_pool)
    {
      lock_entry = tran_lock->lk_entry_pool;
      tran_lock->lk_entry_pool = lock_entry->next;
      tran_lock->lk_entry_pool_count--;
      return lock_entry;
    }

  /* Tier 2+3: lockfree global freelist (may malloc internally) */
  return (LK_ENTRY *) lf_freelist_claim (tran_entry, freelist);
}

// lock_free_entry — src/transaction/lock_manager.c
static void
lock_free_entry (int tran_index, LF_TRAN_ENTRY * tran_entry,
                 LF_FREELIST * freelist, LK_ENTRY * lock_entry)
{
  LK_TRAN_LOCK *tran_lock = &lk_Gl.tran_lock_table[tran_index];

  /* Tier 1: return to local pool if not full */
  if (tran_lock->lk_entry_pool_count < LOCK_TRAN_LOCAL_POOL_MAX_SIZE)
    {
      lock_uninit_entry (lock_entry);
      lock_entry->next = tran_lock->lk_entry_pool;
      tran_lock->lk_entry_pool = lock_entry;
      tran_lock->lk_entry_pool_count++;
    }
  else
    {
      /* Tier 2: retire to global freelist (epoch-based reclamation) */
      lf_freelist_retire (tran_entry, freelist, lock_entry);
    }
}

왜 하나의 global freelist 대신 3단계를 사용하는가?

Tier	구조	동기화 비용	사용 시점
1	`lk_entry_pool` (트랜잭션별, 최대 10개)	제로 — 소유 트랜잭션만 접근	핫 패스: 10개 이하의 lock을 획득/해제하는 짧은 OLTP 트랜잭션
2	`obj_free_entry_list` (global lockfree)	lockfree CAS — `lf_freelist_claim`/`retire`	로컬 풀이 비었을 때(할당) 또는 가득 찼을 때(반환)
3	`malloc` / `free`	커널 syscall	global freelist의 사전 할당 블록이 소진되었을 때

3-5개 행을 접근하는 전형적인 OLTP 트랜잭션에서는, 모든 lock entry가 Tier 1에서 나오고 Tier 1로 돌아간다. global freelist에는 경합이 전혀 발생하지 않는다. Tier 2는 트랜잭션당 10개의 동시 lock을 초과하는 batch 작업의 spillover를 흡수한다. Tier 3(malloc)은 초기 ramp-up이나 극단적 부하 시에만 발생하는 cold path다.

2.9 Lockfree 통합 — 두 개의 트랜잭션 시스템

Lock manager는 두 개의 독립적인 lockfree 트랜잭션 시스템에 참여하며, 각각 별도의 epoch 카운터를 갖는다:

시스템 ID	관리 대상	사용처
`THREAD_TS_OBJ_LOCK_RES`	`LK_RES` (hash table entry)	`m_obj_hash_table.find_or_insert`, `erase_locked`
`THREAD_TS_OBJ_LOCK_ENT`	`LK_ENTRY` (lock entry)	`lock_get_new_entry`, `lock_free_entry`

리소스를 할당하거나 해제하는 모든 lock manager 함수는 먼저 thread의 참여 핸들을 얻는 것으로 시작한다:

LF_TRAN_ENTRY *t_entry_res =
  thread_get_tran_entry (thread_p, THREAD_TS_OBJ_LOCK_RES);
LF_TRAN_ENTRY *t_entry_ent =
  thread_get_tran_entry (thread_p, THREAD_TS_OBJ_LOCK_ENT);

LK_RES와 LK_ENTRY의 del_id 필드는 객체가 retire될 때 (lf_freelist_retire 또는 hashmap erase를 통해) 설정된다. retire된 객체는 epoch 카운터로 추적되는 모든 동시 reader가 retirement epoch를 지나갈 때까지 물리적으로 해제되지 않는다. 이는 cubrid-lockfree-transaction.md에 기술된 표준 hazard-pointer / epoch-based reclamation 패턴이다.

lockfree vs. mutex 보호 경계:

연산	메커니즘
Hash table lookup/insert (`LK_RES` by OID)	lockfree hashmap
`LK_ENTRY` global pool 할당	lockfree freelist (`lf_freelist_claim`)
`LK_ENTRY` 로컬 풀 할당	동기화 없음 (트랜잭션별, 단일 thread)
retire된 entry의 메모리 회수	lockfree epoch-based (`del_id`)
holder/waiter/non2pl list 조작	`res_mutex` (resource별)
트랜잭션 hold list 조작	`hold_mutex` (트랜잭션별)
트랜잭션 non2pl list 조작	`non2pl_mutex` (트랜잭션별)

경계가 명확하다: LK_RES를 찾거나 생성하는 것은 lockfree이고, 그 안의 내용(holder/waiter list)을 조작하는 것은 mutex로 보호된다. 서로 다른 resource에 대한 동시 lock 요청은 hash 수준에서 절대 경합하지 않으며, 할당 측면에서도 공유하지 않는 로컬 풀 entry만 사용한다.

2.10 챕터 요약 — 핵심 포인트

초기화 순서가 중요하다. 트랜잭션 테이블(step 1)이 deadlock detection(step 4)보다 먼저 완료되어야 한다. WFG가 num_trans를 기준으로 크기가 결정되기 때문이다.
**hash table 크기는 MAX(10000, MAX_NTRANS * 300)**으로, 하드코딩된 공식이며 조정 가능한 파라미터가 아니다. hash 함수는 van Emde Boas 스타일의 분산을 사용하여 연속 slot ID를 서로 다른 bucket에 배치한다.
각 트랜잭션은 초기화 시 10개의 LK_ENTRY를 미리 받는다. 이것이 대부분의 OLTP lock 요청을 동기화 없이 처리하는 Tier 1 로컬 풀이다.
WFG edge는 최초 lock wait 시 지연 할당된다. 시작 시에는 할당하지 않는다. 이는 읽기 전용 워크로드에서 메모리 낭비를 방지한다.
deadlock daemon은 100ms마다 루프를 돈다. 그러나 전체 WFG cycle scan은 (a) 설정된 interval이 경과하고 (b) 최소 두 개의 thread가 suspend되어 있을 때만 실행한다. timeout 체크는 매 반복마다 수행한다.
lockfree 경계: hash lookup/insert와 global freelist claim/retire는 lockfree다. 그 아래 — holder/waiter list 조작, transaction hold list 갱신 — 는 resource별 또는 트랜잭션별 mutex로 직렬화된다.

Chapter 3: Lock 획득

이 챕터에서는 lock 획득 경로의 모든 분기를 추적한다. public API (lock_object, lock_scan)에서 내부 핵심 함수 lock_internal_perform_lock_object까지 전부 다룬다. 이 챕터를 읽고 나면 임의의 resource 상태와 요청 파라미터 조합에 대해 정확히 어떤 일이 벌어지는지 예측할 수 있어야 한다.

3.1 두 가지 public 진입점 — `lock_object`와 `lock_scan`

Lock manager는 두 가지 주요 API를 노출한다. 차이는 세분화 수준의 의도에 있지, 메커니즘에 있지 않다. 둘 다 결국 lock_internal_perform_lock_object를 호출한다.

flowchart LR
  SCAN["lock_scan(class_oid, class_lock)\nclass 수준: IS 또는 IX\nclass 자체에 거는 lock"]
  OBJ["lock_object(oid, class_oid, lock)\n어떤 수준이든: root, class, instance"]

  SCAN --> IPLK["lock_internal_perform_lock_object\n(실제 작업)"]
  OBJ --> PREP["준비 계층:\n1. Root OID? -> root 직접 lock\n2. Class lock? -> root에 IX/IS 먼저\n3. Instance lock? -> class에 IX/IS 먼저"]
  PREP --> IPLK

Figure 3-1 — 두 진입점이 같은 내부 함수로 수렴한다. lock_scan은 class 수준 lock을 위한 얇은 래퍼다. lock_object는 내부 함수를 호출하기 전에 다중 세분화 계층 준비 작업을 수행한다.

**lock_scan**이 더 단순하다. instance 수준 작업 없이 class-level lock (일반적으로 SELECT에 IS_LOCK, DML에 IX_LOCK)을 획득한다:

// lock_scan — src/transaction/lock_manager.c (simplified)
int
lock_scan (THREAD_ENTRY * thread_p, const OID * class_oid,
           int cond_flag, LOCK class_lock)
{
  root_class_entry = lock_get_class_lock (thread_p, oid_Root_class_oid);
  granted = lock_internal_perform_lock_object (
    thread_p, tran_index, class_oid,
    NULL,            /* class_oid = NULL → this IS a class lock */
    class_lock, wait_msecs,
    &class_entry, root_class_entry);
  return granted;
}

**lock_object**는 OID에 따라 세 가지 경우를 처리한다:

flowchart TD
  A["lock_object(oid, class_oid, lock)"]
  A --> B{"OID_IS_ROOTOID(oid)?"}
  B -- "yes" --> C1["Case 1: ROOT_CLASS\nroot 직접 lock\nclass_entry = NULL"]
  B -- "no" --> D{"OID_IS_ROOTOID(class_oid)?"}
  D -- "yes" --> C2["Case 2: CLASS\n1. root에 IX/IS 확보\n   (아직 없으면)\n2. class 자체를 lock"]
  D -- "no" --> C3["Case 3: INSTANCE\n1. class에 IX/IS 확보\n   (아직 없으면)\n2. class lock이 요청을\n   포함하는지 확인\n3. instance를 lock"]

  C1 --> IPLK["lock_internal_perform_lock_object"]
  C2 --> IPLK
  C3 --> IPLK

Figure 3-2 — lock_object의 세 가지 분기. 각 경우는 다중 세분화 계층을 존중한다: instance lock은 class에 intention lock이 필요하고, class lock은 root에 intention lock이 필요하다.

intention lock mode는 요청된 lock에서 도출된다:

// lock_object — src/transaction/lock_manager.c
if (lock <= S_LOCK)
  new_class_lock = IS_LOCK;    /* read intent */
else
  new_class_lock = IX_LOCK;    /* write intent */

Case 3의 핵심 최적화: lock_internal_perform_lock_object를 instance에 대해 호출하기 전에, lock_object는 lock_is_class_lock_escalated(old_class_lock, lock)을 확인한다. 이미 hold 중인 class lock이 instance 요청을 포함할 만큼 강하면(예: class에 X를 hold하면 어떤 instance lock이든 불필요), 즉시 LK_GRANTED를 반환한다.

3.2 호출자 지도 — 누가 lock manager를 호출하고 왜 호출하는가

Lock manager는 서비스 계층이다. 내부 상태 머신에 들어가기 전에 누가 API를 호출하고 어떤 맥락에서 호출하는지 파악하면 도움이 된다. 이 지도는 획득과 해제 API를 모두 다루며, Ch. 5에서도 다시 참조된다.

flowchart TB
  subgraph Callers["상위 계층 호출자"]
    LOC["locator_sr.c (41회)\n객체 fetch / store / DDL"]
    BT["btree.c (13)\n인덱스 순회, FK 검증"]
    HEAP["heap_file.c (8)\nheap scan, page 접근"]
    LOG["log_manager.c (5)\ncommit / rollback"]
    BOOT["boot_sr.c (5)\n서버 시작 / DDL"]
    SCAN["scan_manager.c (4)\nheap/index scan 반복"]
    QE["query_executor.c (4)\n쿼리 실행, instant lock mode"]
    SER["serial.c (4)\nNEXT VALUE / CURRENT VALUE"]
    CAT["system_catalog.c (4)\n카탈로그 접근"]
    STAT["statistics_sr.c (4)\nALTER INDEX 통계"]
  end

  subgraph LockAPI["Lock Manager API"]
    LO["lock_object\n(모든 수준)"]
    LS["lock_scan\n(class 수준)"]
    LH["lock_hold_object_instant\n(probe, block 없음)"]
    LC["lock_classes_lock_hint\n(batch class lock)"]
    UO["lock_unlock_object"]
    UDN["lock_unlock_object_donot_move_to_non2pl"]
    UA["lock_unlock_all"]
  end

  LOC --> LO & UO & UDN & LC
  BT --> LO & UDN
  HEAP --> LO & LS & UO
  LOG --> UA
  BOOT --> LO & UO
  SCAN --> LO & UO & LH
  QE --> LO & UO
  SER --> LO & UO
  CAT --> LO & UDN
  STAT --> LO & UO

Figure 3-3 — 호출자 지도. 괄호 안의 숫자는 대략적인 호출 지점 수다. locator_sr.c가 가장 많은 호출자다 — 클라이언트가 시작하는 모든 객체 접근을 중개한다. log_manager.c는 lock_unlock_all의 유일한 호출자다(commit/rollback).

주요 호출자 패턴:

호출자	Lock API	일반적인 mode	맥락
`locator_sr.c`	`lock_object`, `lock_unlock_object`, `lock_classes_lock_hint`	DDL에 SCH_M, DML에 S/X, intention에 IS/IX	객체 fetch(`xlocator_fetch`), store(`xlocator_force`), class 생성/drop
`btree.c`	`lock_object`, `lock_unlock_object_donot_move_to_non2pl`	instance OID에 S/X	인덱스 key lock, FK 검증 — FK 검증 실패 행은 클라이언트에 노출되지 않으므로 `donot_move_to_non2pl` 사용
`heap_file.c`	`lock_scan`, `lock_object`, `lock_unlock_object`	`lock_scan`으로 IS, 행별 S/X	heap scan 시작(`lock_scan`으로 class IS), fetch 시 행별 lock
`scan_manager.c`	`lock_object`, `lock_hold_object_instant`, `lock_unlock_object`	행에 S 또는 X, instant probe	heap/index scan: `lock_hold_object_instant`로 비블로킹 probe, 실패 시 `lock_object`로 fallback
`query_executor.c`	`lock_start_instant_lock_mode`, `lock_stop_instant_lock_mode`	(mode 제어, 직접 lock이 아님)	WHERE 절 평가 — instant mode 구간
`serial.c`	`lock_object(X_LOCK)`, `lock_unlock_object`	serial instance OID에 X	`NEXT VALUE` / `CURRENT VALUE` — RC에서 non2pl 경로의 주요 사용자
`log_manager.c`	`lock_unlock_all`	(전부 해제)	`log_commit` / `log_abort` — 일괄 해제의 유일한 호출자

scan_manager.c가 lock_hold_object_instant를 사용하는 이유: heap 또는 index scan 중에 scan manager는 먼저 비블로킹 instant probe를 시도한다. probe가 실패하면(lock 충돌) 대기가 가능한 full lock_object 경로로 fallback한다. 이 낙관적 우선 패턴은 대부분 경합이 없는 행에 대해 thread suspend를 피한다.

3.3 `lock_internal_perform_lock_object` — 완전한 상태 머신

이것이 핵심 함수다(약 700줄). 네 가지 최상위 시나리오를 처리한다:

flowchart TD
  START["lock_internal_perform_lock_object\n(oid, class_oid, lock, wait_msecs)"]

  START --> DISPATCH{"instance lock?\n(class_oid != NULL\n&& !root)"}
  DISPATCH -- "yes (instance)" --> ESC["lock_escalate_if_needed\n(class lock으로 승격 가능)"]
  ESC --> SUBSUME{"class lock이\n요청을 포함?"}
  SUBSUME -- "yes" --> GRANT_FAST["return LK_GRANTED\n(instance lock 불필요)"]
  SUBSUME -- "no" --> HASH

  DISPATCH -- "no (class/root)" --> FAST{"lock_find_class_entry\n(이미 hold 중?)"}
  FAST -- "found" --> CONV["goto lock_tran_lk_entry\n(변환 경로)"]
  FAST -- "not found" --> HASH

  HASH["hash table에서 find_or_insert\n(lockfree, 반환 시 res_mutex 획득됨)"]

  HASH --> EMPTY{"resource가 비어 있나?\n(holder/waiter/non2pl 없음)"}
  EMPTY -- "yes" --> PATH_A["PATH A: 새 resource\n무조건 grant"]
  EMPTY -- "no" --> SCAN_HOLDER{"holder list에서\n내 tran_index 검색"}
  SCAN_HOLDER -- "not found" --> NEW_REQ["나는 holder가 아님"]
  SCAN_HOLDER -- "found" --> CONV

  NEW_REQ --> COMPAT{"holders AND waiters와\n호환?"}
  COMPAT -- "yes" --> PATH_B["PATH B: 호환\n즉시 grant"]
  COMPAT -- "no" --> ZERO{"wait_msecs ==\nZERO_WAIT?"}
  ZERO -- "yes" --> PATH_C["PATH C: Timeout\n즉시 반환"]
  ZERO -- "no" --> PATH_D["PATH D: waiter로\nenqueue, suspend"]

  CONV --> CONV_CHECK{"new_mode ==\ngranted_mode?"}
  CONV_CHECK -- "yes" --> PATH_E["PATH E: 재진입\ncount만 증가"]
  CONV_CHECK -- "no" --> CONV_COMPAT{"다른 holder들과\n호환?"}
  CONV_COMPAT -- "yes" --> PATH_F["PATH F: 변환 grant\n즉석 upgrade"]
  CONV_COMPAT -- "no" --> CONV_ZERO{"wait_msecs ==\nZERO_WAIT?"}
  CONV_ZERO -- "yes" --> PATH_C
  CONV_ZERO -- "no" --> PATH_G["PATH G: 변환 block\nblocked_mode 설정, 재배치, suspend"]

Figure 3-4 — lock_internal_perform_lock_object의 완전한 상태 머신. 7개 경로(A-G)가 resource 상태, holder 여부, 호환성, wait 정책의 모든 조합을 커버한다.

각 경로의 진입 조건:

경로	이미 holder인가?	resource 상태	호환성	wait 정책	결과
A	No	비어 있음 (holder, waiter, non2pl 없음)	N/A	어떤 것이든	무조건 grant
B	No	비어 있지 않음	`lock_compat(req, total_holders) == YES` AND `lock_compat(req, total_waiters) == YES`	어떤 것이든	즉시 grant
C	No	비어 있지 않음	holder 또는 waiter와 비호환	`ZERO_WAIT` 또는 `FORCE_ZERO_WAIT`	timeout 반환
D	No	비어 있지 않음	holder 또는 waiter와 비호환	`wait_msecs > 0` 또는 `INFINITE_WAIT`	waiter로 enqueue, suspend
E	Yes	—	`lock_conv(req, granted) == granted` (upgrade 불필요)	어떤 것이든	count 증가, 반환
F	Yes	—	`lock_conv(req, granted) != granted` AND `lock_compat(new_mode, group_mode_of_others) == YES`	어떤 것이든	즉석 upgrade
G	Yes	—	`lock_conv(req, granted) != granted` AND `lock_compat(new_mode, group_mode_of_others) == NO`	`wait_msecs > 0` 또는 `INFINITE_WAIT`	`blocked_mode` 설정, 재배치(UPR), suspend

참고:

PATH C는 zero-wait으로 변환이 block된 holder에도 적용된다(같은 timeout 로직이 변환 분기에서도 발동).
PATH E는 lock_find_class_entry 빠른 경로를 통해 도달했을 때 res_mutex를 획득하지 않는다. 이 빠른 경로는 hold_mutex(트랜잭션별)를 획득하여 class hold list를 순회하지만, 더 무거운 resource별 res_mutex는 피한다.
PATH F와 G 모두 캐시된 total_holders_mode가 아닌, 다른 holder들을 순회하여(자기 자신 제외) group_mode를 계산한다.

3.4 PATH A — 새 resource, 무조건 grant

가장 빠른 경로다. find_or_insert가 막 생성한 LK_RES이므로 이전 holder, waiter, non2pl entry가 없다.

// PATH A — src/transaction/lock_manager.c (annotated)
if (res_ptr->holder == NULL && res_ptr->waiter == NULL
    && res_ptr->non2pl == NULL)
  {
    lock_initialize_resource_as_allocated (res_ptr, NULL_LOCK);

    entry_ptr = lock_get_new_entry (tran_index, t_entry_ent,
                                    &lk_Gl.obj_free_entry_list);
    lock_initialize_entry_as_granted (entry_ptr, tran_index,
                                      res_ptr, lock);
    /* instant lock tracking */
    if (is_instant_duration)
      entry_ptr->instant_lock_count++;

    res_ptr->holder = entry_ptr;          /* sole holder */
    entry_ptr->class_entry = class_entry; /* link to parent */
    lock_increment_class_granules (class_entry);
    lock_insert_into_tran_hold_list (entry_ptr, tran_index);
    res_ptr->total_holders_mode = lock;

    pthread_mutex_unlock (&res_ptr->res_mutex);
    *entry_addr_ptr = entry_ptr;
    return LK_GRANTED;
  }

단계별 진행:

3단계 풀에서 LK_ENTRY 할당 (Ch. 2 section 2.8).
granted로 초기화 (granted_mode = lock, blocked_mode = NULL_LOCK).
res_ptr->holder에 삽입 (유일한 entry — list가 비어 있었다).
class_entry 역참조 설정 및 상위 entry의 ngranules 증가.
lock_insert_into_tran_hold_list로 트랜잭션 hold list에 삽입.
total_holders_mode = lock (유일한 holder이므로 LUB 불필요).
res_mutex 해제 후 반환.

3.5 PATH B — 기존 resource, 호환, 즉시 grant

Resource에 이미 holder나 waiter가 있지만, 새 요청이 total_holders_mode와 total_waiters_mode 양쪽 모두와 호환된다.

// PATH B — src/transaction/lock_manager.c (annotated)
compat1 = lock_compat (lock, res_ptr->total_waiters_mode);
compat2 = lock_compat (lock, res_ptr->total_holders_mode);
if (compat1 == LOCK_COMPAT_YES && compat2 == LOCK_COMPAT_YES)
  {
    entry_ptr = lock_get_new_entry (...);
    lock_initialize_entry_as_granted (entry_ptr, tran_index,
                                      res_ptr, lock);
    /* position in holder list per UPR */
    lock_position_holder_entry (res_ptr, entry_ptr);

    /* update aggregate mode */
    res_ptr->total_holders_mode =
      lock_conv (lock, res_ptr->total_holders_mode);

    lock_insert_into_tran_hold_list (entry_ptr, tran_index);
    lock_update_non2pl_list (thread_p, res_ptr, tran_index, lock);

    pthread_mutex_unlock (&res_ptr->res_mutex);
    return LK_GRANTED;
  }

핵심 불변식: 이중 호환성 체크. 새 요청은 total_holders_mode와 total_waiters_mode 양쪽 모두를 통과해야 한다. holder만 체크하면 S 요청들이 대기 중인 X 요청을 건너뛸 수 있다. 이것이 Ch. 1 section 1.3의 starvation guard다.

**lock_update_non2pl_list**는 모든 성공적인 grant 시 호출된다. resource의 non2pl list를 순회하며, 새로 grant된 lock이 다른 트랜잭션의 non2pl entry의 기록된 mode와 비호환이면 해당 entry를 INCON_NON_TWO_PHASE_LOCK으로 표시한다. 이것이 Ch. 5에서 기술하는 conflict detection trigger다.

3.6 PATH C — 비호환, zero-wait timeout

호출자가 LK_ZERO_WAIT 또는 LK_FORCE_ZERO_WAIT(조건부 lock 요청)을 지정한 경우, 함수는 block하지 않는다:

// PATH C — src/transaction/lock_manager.c (annotated)
if (wait_msecs == LK_ZERO_WAIT || wait_msecs == LK_FORCE_ZERO_WAIT)
  {
    pthread_mutex_unlock (&res_ptr->res_mutex);
    if (wait_msecs == LK_ZERO_WAIT)
      {
        /* create a temporary blocked entry just for the error message */
        p = lock_get_new_entry (...);
        lock_initialize_entry_as_blocked (p, thread_p, ...);
        lock_set_error_for_timeout (thread_p, p);  /* ← sets ER_LK_... */
        lock_free_entry (..., p);
      }
    return LK_NOTGRANTED_DUE_TIMEOUT;
  }

두 zero-wait mode의 차이:

LK_ZERO_WAIT (값 0): 에러 메시지와 함께 timeout. 에러 진단 정보 (xasl_id, bind_index_in_tran을 lock_set_error_for_timeout으로)를 채우기 위한 임시 LK_ENTRY를 생성한 뒤 즉시 해제한다.
LK_FORCE_ZERO_WAIT (값 -2): 에러 설정 없이 조용히 timeout. 실패를 정상적인 결과로 기대하는 조건부 lock probe에 사용된다.

3.7 PATH D — 비호환, waiter로 enqueue

표준 blocking 경로다. 새 요청을 grant할 수 없고, 호출자가 대기하겠다고 했다.

// PATH D — src/transaction/lock_manager.c (annotated)
/* allocate and initialize as blocked */
entry_ptr = lock_get_new_entry (...);
lock_initialize_entry_as_blocked (entry_ptr, thread_p, tran_index,
                                  res_ptr, lock);

/* append at the END of the waiter list (FIFO) */
prev = NULL;
for (i = res_ptr->waiter; i != NULL; i = i->next)
  prev = i;
if (prev == NULL)
  res_ptr->waiter = entry_ptr;
else
  prev->next = entry_ptr;

/* update aggregate waiter mode */
res_ptr->total_waiters_mode =
  lock_conv (lock, res_ptr->total_waiters_mode);

goto blocked;  /* → suspend thread */

blocked: 라벨에서 thread가 suspend된다:

blocked:
  /* release res_mutex, then suspend */
  pthread_mutex_unlock (&res_ptr->res_mutex);
  ret_val = lock_suspend (thread_p, entry_ptr, wait_msecs);

resume 후, lock_suspend의 반환값이 결과를 결정한다:

`ret_val`	의미	동작
`LOCK_RESUMED`	해제자가 lock을 grant함	`lock_conversion_treatement`으로 계속
`LOCK_RESUMED_TIMEOUT`	wait가 timeout됨	`lock_internal_perform_unlock_object`가 waiter를 제거, `LK_NOTGRANTED_DUE_TIMEOUT` 반환
`LOCK_RESUMED_ABORTED`	deadlock victim으로 선정됨	같은 cleanup, `LK_NOTGRANTED_DUE_ABORTED` 반환
`LOCK_RESUMED_INTERRUPT`	서버 종료	`LK_NOTGRANTED_DUE_ERROR` 반환

핵심 세부사항: 누가 waiter를 grant하는가? suspend된 thread는 resume 시 호환성을 다시 체크하지 않는다. 대신, holder가 lock을 해제할 때 (lock_internal_perform_unlock_object, Ch. 5), 해제자가 lock_grant_blocked_holder와 lock_grant_blocked_waiter를 호출하여 waiter list를 순회하고, 갱신된 total_holders_mode에 대해 호환성을 체크하고, grant 가능한 waiter를 holder list로 옮긴 뒤 깨운다. resume된 thread는 자신의 entry가 이미 holder list에 있고 granted_mode가 설정된 것을 발견한다.

3.8 PATH E — 재진입 (같은 tran, 같거나 더 약한 mode)

트랜잭션이 이미 hold 중인 lock을 요청하고, 변환 결과 (lock_conv(requested, granted))가 현재 granted mode와 같으면, 실제 upgrade가 불필요한 no-op다. count만 증가시킨다:

// PATH E — src/transaction/lock_manager.c
lock_tran_lk_entry:
  new_mode = lock_conv (lock, entry_ptr->granted_mode);
  if (new_mode == entry_ptr->granted_mode)
    {
      entry_ptr->count += 1;
      /* instant lock tracking ... */
      return LK_GRANTED;       /* no res_mutex needed */
    }

lock_find_class_entry 빠른 경로를 통해 도달했을 때는 res_mutex가 필요 없다. lock_find_class_entry는 hold_mutex(트랜잭션별 mutex)를 획득하여 class_hold_list를 안전하게 순회하지만, res_mutex는 건드리지 않는다. count 증가 자체는 트랜잭션당 한 번에 하나의 thread만 lock manager에 있을 수 있으므로 안전하다.

3.9 PATH F — 변환 즉시 grant

트랜잭션이 이미 lock을 hold하지만 더 강한 mode를 요청한다. 변환 결과 (new_mode)가 granted_mode와 다르지만, 다른 모든 holder와 호환된다:

// PATH F — src/transaction/lock_manager.c (annotated)
/* compute aggregate of OTHER holders (excluding myself) */
group_mode = NULL_LOCK;
for (i = res_ptr->holder; i != NULL; i = i->next)
  {
    if (i != entry_ptr)
      group_mode = lock_conv (i->granted_mode, group_mode);
  }

compat1 = lock_compat (new_mode, group_mode);
if (compat1 == LOCK_COMPAT_YES)
  {
    entry_ptr->granted_mode = new_mode;  /* upgrade in place */
    entry_ptr->count += 1;
    res_ptr->total_holders_mode =
      lock_conv (lock, res_ptr->total_holders_mode);
    lock_update_non2pl_list (...);
    pthread_mutex_unlock (&res_ptr->res_mutex);
    goto lock_conversion_treatement;
  }

PATH B와의 핵심 차이: 호환성 체크 대상이 total_holders_mode(자기 자신의 mode 포함)가 아닌 group_mode(다른 holder만)다. 트랜잭션은 자기 자신과 충돌할 수 없다.

lock_conversion_treatement [sic — 소스의 오타]은 class lock 변환 이후의 정리를 담당한다. class lock이 upgrade되면(예: IS->X), 이제 불필요해진 instance lock들이 제거된다:

이전 class mode	새 class mode	동작
`IS`	`S`, `SIX`, 또는 `X`	모든 S instance lock 제거
`IX`	`SIX`	모든 S instance lock 제거
`IX`	`X`	모든 X instance lock 제거
`SIX`	`X`	모든 X instance lock 제거

3.10 PATH G — 변환 block (Upgrader Positioning Rule)

변환이 다른 holder들과 비호환이고, 트랜잭션이 대기해야 한다. 가장 복잡한 경로다. entry가 holder list에 그대로 남아 있으면서(이전 mode를 여전히 hold) 대기 중인 upgrade를 알리기 위해 재배치되기 때문이다:

// PATH G — src/transaction/lock_manager.c (annotated)
entry_ptr->blocked_mode = new_mode;  /* ← both fields now non-NULL */
entry_ptr->count += 1;
entry_ptr->thrd_entry = thread_p;

res_ptr->total_holders_mode =
  lock_conv (lock, res_ptr->total_holders_mode);

/* remove from current position in holder list */
/* ... unlink entry_ptr ... */

/* reposition per Upgrader Positioning Rule (UPR) */
lock_position_holder_entry (res_ptr, entry_ptr);

goto blocked;  /* → suspend thread */

핵심 불변식: granted_mode != NULL_LOCK AND blocked_mode != NULL_LOCK. 이것이 Ch. 1 section 1.4의 conversion-wait 상태다. entry는 holder list에 남아 있고(다른 트랜잭션이 호환성 체크에서 이전 granted_mode를 본다), 대기 중인 upgrade가 표시되어 있다.

Upgrader Positioning Rule (UPR): lock_position_holder_entry는 entry의 blocked_mode와 다른 holder들의 mode 간 호환성을 기준으로 entry를 배치한다. 목표는 불필요한 대기를 줄이는 수준이 아니다. grant pass (lock_grant_blocked_holder)는 holder list의 앞쪽만 스캔하고 첫 비-upgrading holder에서 멈추기 때문에, 일반 holder 뒤에 놓인 upgrader는 이후의 어떤 release에서도 검사되지 않는다 — 배치는 튜닝이 아니라 liveness 요구사항이다(§3.11 참조). holder list에서 세 후보 위치(ta, tb, tc)를 우선순위 순서로 평가하고, 가장 좋은 위치에 entry를 삽입한다.

3.11 Upgrader Positioning Rule (UPR) — `lock_position_holder_entry` 심층 분석

lock_position_holder_entry는 holder list에서 새 entry 또는 재배치되는 entry가 어디에 삽입될지 결정한다. holder list는 단순 FIFO가 아니다. conversion-waiting holder(upgrader)가 비-upgrading holder 앞에 오도록 정렬된다. 이 순서가 holder가 lock을 해제할 때 어떤 waiter가 다음으로 grant될 수 있는지에 직접 영향을 미친다.

배치가 곧 정확성인 이유 — 묻힌 upgrader. lock_grant_blocked_holder는 holder list를 앞에서부터 걷다가 blocked_mode == NULL_LOCK인 첫 entry(일반 holder)에서 멈춘다 (while (holder != NULL && holder->blocked_mode != NULL_LOCK)). 이 조기 종료가 release마다 도는 스캔을 싸게 만들지만, 모든 upgrader가 앞 구간에 모여 있을 때만 건전하다. UPR 없이 naive append를 하면 class-grain 타임라인에서 실패가 재현된다. 각 entry는 granted/blocked(– = NULL_LOCK)로 표기한다:

t	사건	holder list (앞 → 뒤)
1	T5 `IS`, T3 `IX`, T2 `IX` — 모두 호환	`T5 IS/–` → `T3 IX/–` → `T2 IX/–`
2	T3가 `SIX`로 upgrade; T2의 `IX`와 충돌 → `blocked_mode`만 기록하고 제자리에서 suspend	`T5 IS/–` → `T3 IX/SIX` → `T2 IX/–`
3	T2 commit — grant pass가 T5에서 시작: `blocked = –` ⇒ 아무도 검사하지 않고 종료	`T5 IS/–` → `T3 IX/SIX`
4	`SIX ∧ IS`는 호환 — T3는 grant 가능한데도 lock timeout 또는 deadlock victim까지 잠든다	영원히 그대로

이 예시에 intention mode가 필요하다는 점에 주의: 단순 S → X 버전으로는 버그가 재현되지 않는다 — 앞에 선 일반 S holder는 X 목표도 막고 있고, 그가 release하면 리스트에서 빠지므로 upgrader가 어차피 선두가 된다. liveness 실패는 남아 있는 일반 holder의 granted mode가 upgrade 목표와 호환일 때만 생긴다 — 예: IX → SIX upgrader 앞에 선 IS.

blocked_mode에 따른 두 가지 경우:

Case 1: blocked_mode == NULL_LOCK (일반 grant, upgrade 아님)

entry는 대기 중인 upgrade가 없는 일반 holder다. 모든 upgrader 뒤에, 다른 일반 holder 앞에 삽입된다:

// Case 1 — src/transaction/lock_manager.c
if (entry_ptr->blocked_mode == NULL_LOCK)
  {
    prev = NULL;
    i = res_ptr->holder;
    while (i != NULL)
      {
        if (i->blocked_mode == NULL_LOCK)
          break;       /* ← stop at the first non-upgrader */
        prev = i;
        i = i->next;
      }
    /* insert after prev (i.e., after all upgraders) */
  }

결과적인 holder list 순서: [upgraders...] [plain holders...].

Case 2: blocked_mode != NULL_LOCK (conversion wait — upgrader)

entry가 upgrader다. 세 후보 삽입 지점을 우선순위 순서로 평가한다:

// Case 2 — src/transaction/lock_manager.c (annotated)
ta = tb = tc = NULL;  /* three candidates */

for each holder i in the list:
  if (i is also an upgrader)  /* i->blocked_mode != NULL_LOCK */
    {
      /* ta: first upgrader whose blocked_mode is COMPATIBLE
             with my blocked_mode */
      compat1 = lock_compat (me->blocked_mode, i->blocked_mode);
      if (ta == NULL && compat1 == YES)
        ta = i;

      /* tb: first upgrader where my blocked_mode is compatible
             with its granted_mode, BUT its blocked_mode is
             INCOMPATIBLE with my granted_mode */
      compat1 = lock_compat (me->blocked_mode, i->granted_mode);
      compat2 = lock_compat (i->blocked_mode, me->granted_mode);
      if (ta == NULL && tb == NULL
          && compat1 == YES && compat2 == NO)
        tb = i;
    }
  else  /* i is a plain holder */
    {
      /* tc: first plain (non-upgrading) holder */
      if (tc == NULL)
        tc = i;
    }

/* choose insertion point by priority: ta > tb > tc */
if (ta != NULL)      prev = tap;   /* before ta */
else if (tb != NULL) prev = tbp;   /* before tb */
else if (tc != NULL) prev = tcp;   /* before tc */
/* else: append at the end (prev from the loop) */

세 후보의 의미:

후보	조건	의미	왜 그 앞에 삽입하는가
ta	내 `blocked_mode`가 `i`의 `blocked_mode`와 호환	나와 이 upgrader가 호환되는 upgrade를 원함	둘 다 진행할 수 있다. 나를 먼저 놓으면 해제자가 나를 더 빨리 grant할 수 있고 상대를 block하지 않음
tb	내 `blocked_mode`가 `i`의 `granted_mode`와 호환이지만, `i`의 `blocked_mode`가 내 `granted_mode`와 비호환	내가 상대가 가진 것과 충돌하지 않지만, 상대가 내가 가진 것과 충돌	내가 뒤에 가면 상대가 내 granted_mode에 block되고 나는 상대의 blocked_mode에 block — deadlock. 나를 앞에 놓으면 이를 회피
tc	첫 번째 일반(비-upgrading) holder	upgrader와 일반 holder 사이의 경계	모든 upgrader는 비-upgrader보다 앞에 있어야 함

우선순위 ta > tb > tc: ta가 최선(호환되는 upgrader끼리 그룹). tb는 fallback(upgrader 간 deadlock 회피). tc는 마지막 수단(적어도 upgrader 영역에 머무르기).

tb 케이스를 따라가 보면. 배치되는 entry가 new = IX→SIX, 기존 upgrader가 i = IS→X라고 하자. SIX ∧ IS = ✓(i가 쥔 mode는 new를 막지 않는다)이지만 X ∧ IX = ✗(new가 쥔 mode는 new가 쥐고 있는 한 i를 막는다). grant pass는 upgrader 영역의 호환되는 prefix만 grant하고 첫 실패에서 멈추므로, 순서가 모든 것을 결정한다:

upgrader 영역 내 순서	grant pass의 동작	결과
`[ new, i ]` — tb의 선택	`new`: `SIX ∧ IS = ✓` → grant; `i`는 `new`의 commit 때 차례가 온다	전진
`[ i, new ]`	`i`: `X ∧ IX = ✗` → 정지 — `new`는 grant 가능한데도 검사받지 못함	둘 다 잠듦 — timeout까지 wedge

한 방향으로만 충돌하는 쌍에게 생존 가능한 순서는 단 하나다: 상대가 쥔 채로도 grant될 수 있는 쪽이 앞에 선다.

실제 예시:

Holder list before UPR:
  [T3: granted=S, blocked=X] → [T5: granted=IS, blocked=NULL] → [T8: granted=S, blocked=NULL]
   ^^ upgrader                   ^^ plain holder                   ^^ plain holder

New entry: T7 wants to upgrade (granted=IX, blocked=SIX)

평가:

T3 (upgrader): lock_compat(SIX, X) -> NO. ta 아님. lock_compat(SIX, S) -> NO. tb도 아님.
T5 (plain): tc = T5 (첫 번째 plain holder).

결과: ta 없음, tb 없음, tc = T5. T5 앞에 삽입:

After UPR:
  [T3: granted=S, blocked=X] → [T7: granted=IX, blocked=SIX] → [T5: granted=IS, blocked=NULL] → [T8: granted=S, blocked=NULL]
   ^^ upgrader                   ^^ upgrader (new)                ^^ plain holder                   ^^ plain holder

UPR가 유지하는 holder list 순서 불변식:

flowchart LR
  subgraph HL["Holder list 순서"]
    direction LR
    U1["upgrader 1\ngranted + blocked"]
    U2["upgrader 2\ngranted + blocked"]
    UN["..."]
    P1["plain holder 1\ngranted만"]
    P2["plain holder 2\ngranted만"]
    PN["..."]
    U1 --> U2 --> UN --> P1 --> P2 --> PN
  end

Figure 3-5 — Holder list 순서 불변식. upgrader(blocked_mode != NULL_LOCK인 entry)가 항상 plain holder 앞에 배치된다. upgrader 사이의 순서는 blocked_mode의 호환성으로 결정되어 upgrader 간 deadlock을 최소화한다.

UPR이 정확성에 중요한 이유: holder가 lock을 해제하고 lock_grant_blocked_holder가 holder list를 앞에서 뒤로 스캔할 때, 호환되는 목표를 가진 upgrader들이 앞에 그룹되어 있으면 한 번의 패스로 함께 grant할 수 있다. UPR이 없으면 뒤쪽에 새로 도착한 upgrader가 앞의 upgrader와 deadlock에 빠질 수 있다. grant 순서가 잘못되기 때문이다.

3.12 구체적 시나리오 — 세 트랜잭션이 한 행을 두고 경합

flowchart LR
  subgraph T0["초기 상태"]
    H0["holder: T5 (S)"]
    W0["waiter: --"]
    AGG0["holders=S\nwaiters=NULL"]
  end

  subgraph T1["T7이 S 요청 (PATH B)"]
    H1["holder: T5 (S), T7 (S)"]
    W1["waiter: --"]
    AGG1["holders=S\nwaiters=NULL"]
  end

  subgraph T2["T9가 X 요청 (PATH D)"]
    H2["holder: T5 (S), T7 (S)"]
    W2["waiter: T9 (X)"]
    AGG2["holders=S\nwaiters=X"]
  end

  subgraph T3["T12가 S 요청 (PATH D!)"]
    H3["holder: T5 (S), T7 (S)"]
    W3["waiter: T9 (X), T12 (S)"]
    AGG3["holders=S\nwaiters=SIX"]
  end

  T0 --> T1 --> T2 --> T3

Figure 3-6 — 4단계 경합 시나리오. T7의 S 요청은 호환(PATH B). T9의 X 요청은 holder와 waiter 호환 모두 실패(PATH D). T12의 S 요청은 total_holders_mode와는 호환(S vs S = yes)이지만 total_waiters_mode와 비호환(S vs X = no)이므로 T12도 block(PATH D). 이것이 starvation guard의 작동이다: T9의 대기 중인 X가 T12의 추월을 방지한다.

3.13 진단 필드 — `xasl_id`와 `bind_index_in_tran`

성공적인 획득의 맨 마지막(LK_GRANTED를 반환하는 모든 경로)에서:

// lock_internal_perform_lock_object — src/transaction/lock_manager.c
end:
  if (entry_ptr != NULL && ret_val == LK_GRANTED)
    lock_event_set_xasl_id_to_entry (tran_index, entry_ptr);

현재 실행 중인 쿼리의 plan ID와 statement index를 entry에 기록한다. 이들은 읽기 전용 진단 필드로, lock 동작에 영향을 미치지 않는다. 유일한 소비자는 event log 서브시스템(event_log_sql_string, event_log_bind_values)으로, timeout과 deadlock 리포트에 이 값들을 출력하여 DBA가 어떤 쿼리가 lock wait를 유발했는지 식별할 수 있게 한다.

3.14 성능 분석 — 경로별 획득 비용

모든 경로의 비용이 같지 않다. 아래 표는 가장 저렴한 것부터 가장 비싼 것 순서로 정렬한다:

경로	비용	동기화	발생 조건
E (재진입, class 빠른 경로)	O(1)	`hold_mutex`만 — `res_mutex` 없음, hash lookup 없음	같은 tran이 같은 class에 같거나 더 약한 mode를 재요청. OLTP에서 가장 빈번.
E (재진입, hash 경유)	O(1) + hash lookup	`res_mutex`	같은 tran이 같은 instance에 같거나 더 약한 mode를 재요청.
A (새 resource)	O(1) + hash insert	lockfree `find_or_insert` + `res_mutex`	이전에 lock된 적 없는 OID에 대한 최초 lock.
B (호환 grant)	O(1) compat check	`res_mutex`	새 holder, aggregate mode와 호환.
F (변환 grant)	O(holders)	`res_mutex`	upgrade 필요, 자기 자신 제외한 `group_mode` 계산 필수.
D (enqueue + suspend)	O(waiters) + thread suspend	`res_mutex` + thread mutex + context switch	비호환 — thread가 잠든다.
G (변환 block)	O(holders) + suspend	`res_mutex` + UPR 재배치 + context switch	upgrade가 다른 holder와 비호환.

핵심 성능 관찰:

1. class entry 빠른 경로(PATH E)는 hash table을 완전히 우회한다.

lock_object → lock_find_class_entry (hold_mutex만)
            → found → lock_tran_lk_entry → count++ → return

OLTP에서 가장 뜨거운 경로다. 모든 DML statement는 lock_scan이 이미 획득한 class intention lock(IS/IX)을 재요청한다. 비용은 hold_mutex lock/unlock 1회 + class_hold_list linked list 순회(보통 10개 미만) + 정수 증가 1회다. hash lookup 없음, res_mutex 없음.

2. O(1) aggregate mode 체크가 PATH B에서 holder별 스캔을 제거한다.

total_holders_mode / total_waiters_mode가 없으면 모든 새 lock 요청마다 전체 holder list를 순회하여 호환성을 체크해야 한다. 캐시된 aggregate를 사용하면 PATH B는 테이블 조회 2회로 끝난다:

compat1 = lock_Comp[lock][res_ptr->total_waiters_mode];  // O(1)
compat2 = lock_Comp[lock][res_ptr->total_holders_mode];  // O(1)

트레이드오프: total_holders_mode는 holder list가 변경될 때마다 재계산해야 한다(Ch. 5 section 5.6에서 O(holders)). 그러나 안정 상태의 OLTP에서 grant가 release보다 훨씬 빈번하므로 순이익이 크다.

3. 모든 instance lock 요청마다 escalation 체크를 하지만 비용이 저렴하다.

lock_escalate_if_needed -> lock_check_escalate는:

hold_mutex lock/unlock 1회
정수 비교 1회 (ngranules < threshold)
false 반환 (일반적인 경우 — escalation 불필요)

총합: 약 100ns. 이는 대안 — 무제한 instance lock 누적 — 의 결과(메모리 압박, O(n) hold list 순회)보다 훨씬 낫기 때문에 허용 가능하다.

4. hash 함수의 slot 분산 설계가 동시 scan에서 성과를 낸다.

같은 heap page의 연속 OID(slotid 1, 2, 3, …)가 서로 다른 hash bucket에 떨어진다(Ch. 2 section 2.3, Figure 2-2). 같은 테이블을 병렬로 scan하는 두 thread가 서로 다른 res_mutex 인스턴스를 hit하므로 hash 수준에서 절대 경합하지 않는다. 단순 hash였다면 같은 bucket에 몰려서 scan이 직렬화되었을 것이다.

3.15 챕터 요약 — 핵심 포인트

두 public API, 하나의 내부 함수. lock_scan은 class 수준 intention lock을 처리하고, lock_object는 세 가지 resource type 모두를 다중 세분화 준비와 함께 처리한다. 둘 다 lock_internal_perform_lock_object로 수렴한다.
**7개 경로(A-G)**가 resource 상태, holder 여부, 호환성, wait 정책의 모든 조합을 커버한다.
이중 호환성 체크 (PATH B/D): 새 요청은 total_holders_mode와 total_waiters_mode 양쪽 모두와 호환되어야 한다. waiter 체크가 starvation guard다.
**재진입(PATH E)**은 class entry 빠른 경로에서 도달 시 mutex 없이 count만 증가시킨다.
**변환(PATH F/G)**은 다른 holder만을 대상으로 체크한다(자기 자신 제외). block된 변환은 granted_mode와 blocked_mode를 모두 설정하고, entry를 holder list에 남긴 채 UPR에 따라 재배치한다.
waiter는 해제자가 grant한다. resume된 thread가 호환성을 다시 체크하지 않는다.
**lock_update_non2pl_list**는 resource에 이전 상태가 있는 성공적인 grant(PATH B, F) 시 호출되어 충돌하는 non2pl entry를 decache 알림 대상으로 표시한다. PATH A(새 resource)는 이를 건너뛴다 — non2pl list가 비어 있다.

Chapter 4: Lock 변환과 재진입

Chapter 3에서 변환과 재진입이 획득 상태 머신의 어디에 나타나는지 (PATH E/F/G) 다루었다. 이 챕터에서는 메커니즘 자체에 집중한다: 변환 테이블의 작동 방식, 재진입 counting과 unlock의 상호작용, block된 변환이 grant되는 방법, class lock upgrade 이후의 정리 작업.

4.1 변환이 발생하는 시점 — trigger 조건

변환은 트랜잭션이 이미 hold 중인 resource에 대해 lock을 요청할 때 발생한다. 함수는 holder list에서 일치하는 tran_index를 스캔하여 이를 감지한다:

// lock_internal_perform_lock_object — src/transaction/lock_manager.c
entry_ptr = res_ptr->holder;
while (entry_ptr != NULL)
  {
    if (entry_ptr->tran_index == tran_index)
      break;    /* ← found: I am already a holder */
    entry_ptr = entry_ptr->next;
  }

발견되면 lock_tran_lk_entry:(변환 경로)로 점프한다. 발견되지 않으면 새 lock 요청(PATH A-D)이다.

class lock의 경우 hash table을 완전히 우회하는 빠른 경로가 있다: lock_find_class_entry는 트랜잭션의 class_hold_list를 순회한다 (resource의 holder 수가 아닌 hold 중인 class 수만큼 O):

// lock_find_class_entry — src/transaction/lock_manager.c
entry_ptr = tran_lock->class_hold_list;
while (entry_ptr != NULL)
  {
    if (OID_EQ (&entry_ptr->res_head->key.oid, class_oid))
      break;
    entry_ptr = entry_ptr->tran_next;
  }

이 빠른 경로는 재진입(PATH E)에서 find_or_insert와 res_mutex를 우회한다. hold_mutex(트랜잭션별 mutex)를 획득하여 리스트를 안전하게 순회하지만, 더 무거운 resource별 res_mutex는 피한다. 이것이 가장 빈번한 변환 시나리오다.

4.2 변환 테이블 — `lock_Conv[requested][current]`

변환 결과는 요청된 mode와 현재 hold mode의 least upper bound(LUB)다:

new_mode = lock_conv (lock, entry_ptr->granted_mode);
// equivalent to: new_mode = lock_Conv[lock][entry_ptr->granted_mode];

전체 12x12 테이블은 lock_table.c에 있다. 실제로 중요한 부분:

requested ↓ \ current ->	IS	S	IX	SIX	U	X
IS	IS	S	IX	SIX	—	X
S	S	S	SIX	SIX	U	X
IX	IX	SIX	IX	SIX	—	X
SIX	SIX	SIX	SIX	SIX	—	X
U	—	U	—	—	U	X
X	X	X	X	X	X	X

읽는 법: lock_Conv[S][IX] = SIX는 “IX를 hold하고 S를 요청하면 결과는 SIX”라는 뜻이다.

NA_LOCK entry(—로 표시)는 해당 조합이 정의되지 않으며 assert 실패를 유발한다는 뜻이다. 실제로 발생하면 안 되는 조합이다(예: U_LOCK은 S_LOCK을 이미 hold할 때만 요청됨).

4.3 재진입 — PATH E 상세

재진입은 가장 빈번한 변환이다: 트랜잭션이 이미 hold 중인 것과 같거나 더 약한 mode를 요청한다. 변환 결과가 현재 mode와 같으므로 실제 upgrade가 불필요하다.

// PATH E — lock_tran_lk_entry in lock_internal_perform_lock_object
new_mode = lock_conv (lock, entry_ptr->granted_mode);
if (new_mode == entry_ptr->granted_mode)
  {
    entry_ptr->count += 1;   /* ← just bump the counter */
    // ... instant lock tracking ...
    return LK_GRANTED;
  }

count 필드는 올바른 unlock 동작에 결정적이다. 각 lock_object 호출이 count를 증가시키고, 각 lock_unlock_object 호출이 감소시킨다. count가 0에 도달해야만 lock이 실제로 해제된다. 이는 내부 호출자가 외부 호출자가 아직 필요한 lock을 실수로 해제하는 것을 방지한다.

중첩 재진입 예시:

lock_object(oid=R1, mode=S)   → count=1, granted_mode=S
  lock_object(oid=R1, mode=S) → count=2, granted_mode=S  (PATH E)
  lock_unlock_object(R1, S)   → count=1, lock STAYS
lock_unlock_object(R1, S)     → count=0, lock RELEASED

4.4 즉시 변환 — PATH F 상세

new_mode != granted_mode(실제 upgrade 필요)일 때, 함수는 **다른 holder만 (자기 자신 제외)**에 대해 호환성을 체크해야 한다:

// PATH F — lock_internal_perform_lock_object (annotated)
group_mode = NULL_LOCK;
for (i = res_ptr->holder; i != NULL; i = i->next)
  {
    if (i != entry_ptr)          /* ← skip myself */
      group_mode = lock_conv (i->granted_mode, group_mode);
  }

compat1 = lock_compat (new_mode, group_mode);
if (compat1 == LOCK_COMPAT_YES)
  {
    /* upgrade in place */
    entry_ptr->granted_mode = new_mode;
    entry_ptr->count += 1;
    res_ptr->total_holders_mode =
      lock_conv (lock, res_ptr->total_holders_mode);
    lock_update_non2pl_list (...);
    goto lock_conversion_treatement;
  }

왜 자기 자신을 제외하는가? 트랜잭션은 자신의 lock과 충돌할 수 없다. T가 S를 hold하고 X를 요청할 때, total_holders_mode가 SIX일 수 있다 (다른 트랜잭션이 IX를 hold하므로). 그러나 group_mode(다른 holder만)는 IX일 수 있고, lock_compat(X, IX) == NO이므로 변환이 block된다. 자기 자신을 제외하지 않으면 total_holders_mode = SIX를 사용하여, 유일한 S holder가 요청 트랜잭션 자신일 때조차 변환이 불가능하다고 잘못 결론내릴 것이다.

구체적 예시:

Resource R: holder list = [T5(IX), T7(S)]
T7 requests X_LOCK on R.

new_mode = lock_conv(X, S) = X
group_mode = T5's granted_mode = IX
lock_compat(X, IX) = NO → PATH G (blocked)

But if R only had: [T7(S)]
group_mode = NULL_LOCK
lock_compat(X, NULL) = YES → PATH F (granted, upgrade S→X)

4.5 block된 변환 — PATH G 상세

upgrade가 다른 holder와 비호환일 때, entry는 dual-field 상태에 진입한다. 이것이 block된 변환의 정의적 특징이다:

// PATH G — lock_internal_perform_lock_object (annotated)
entry_ptr->blocked_mode = new_mode;   /* upgrade target */
entry_ptr->count += 1;
entry_ptr->thrd_entry = thread_p;

/* update total_holders_mode to reflect the REQUESTED mode */
res_ptr->total_holders_mode =
  lock_conv (lock, res_ptr->total_holders_mode);

/* remove from current position, reposition per UPR */
// ... unlink entry_ptr from holder list ...
lock_position_holder_entry (res_ptr, entry_ptr);

goto blocked;   /* → lock_suspend */

block된 변환 중의 핵심 불변식:

granted_mode = 이전 mode (여전히 유효 — 다른 트랜잭션이 호환성 체크에서 이 값을 본다)
blocked_mode = 새 mode (대기 중인 upgrade)
entry가 holder list에 남아 있다 (waiter list가 아님)
thread는 suspend 상태

total_holders_mode에 아직 grant되지 않은 요청 mode가 포함된다. 이는 보수적이다: 새 요청이 가능한 가장 강한 경합 상황을 보도록 보장한다. 트레이드오프는 이전 mode와 이론적으로 공존 가능한 일부 요청이 block된다는 것이다. 이는 의도적이다. upgrader의 starvation을 방지한다.

4.6 block된 변환의 grant — `lock_grant_blocked_holder`

holder가 lock을 해제하면(Ch. 5), 해제 경로가 lock_grant_blocked_holder를 호출한다. 이 함수는 holder list를 앞에서 뒤로 스캔한다(UPR가 upgrader를 앞에 배치하는 이유가 바로 이것이다):

// lock_grant_blocked_holder — src/transaction/lock_manager.c (annotated)
static void
lock_grant_blocked_holder (THREAD_ENTRY * thread_p, LK_RES * res_ptr)
{
  holder = res_ptr->holder;
  while (holder != NULL && holder->blocked_mode != NULL_LOCK)
    {
      /* compute aggregate of all holders AFTER this one */
      mode = NULL_LOCK;
      for (h = holder->next; h != NULL; h = h->next)
        mode = lock_conv (h->granted_mode, mode);

      compat = lock_compat (holder->blocked_mode, mode);
      if (compat == LOCK_COMPAT_NO)
        break;                    /* ← stop granting */

      /* grant the conversion */
      holder->granted_mode = holder->blocked_mode;
      holder->blocked_mode = NULL_LOCK;

      /* reposition: move from upgrader zone to plain-holder zone */
      // ... reposition per UPR ...

      lock_update_non2pl_list (...);
      lock_resume (holder, LOCK_RESUMED);   /* wake up */

      holder = next;
    }
}

알고리즘은 upgrader만 순회한다(blocked_mode == NULL_LOCK인 첫 entry에서 멈춘다). 각 upgrader에 대해 list에서 뒤에 있는 holder들의 aggregate를 계산한다(앞이 아님). 이 비대칭이 UPR가 가능하게 하는 것이다: 앞에 있는 호환 upgrader들은 뒤에 있는 mode와 충돌하지 않으므로 함께 grant될 수 있다.

Grant 순서:

granted_mode = blocked_mode (upgrade 적용)
blocked_mode = NULL_LOCK (더 이상 upgrader가 아님)
UPR에 따라 plain-holder 영역으로 재배치
conflict detection을 위한 lock_update_non2pl_list
lock_resume(LOCK_RESUMED)로 suspend된 thread 깨우기

4.7 block된 waiter의 grant — `lock_grant_blocked_waiter`

block된 holder를 grant한 후, 해제 경로가 lock_grant_blocked_waiter를 호출한다. 이 함수는 waiter list를 앞에서 뒤로 스캔한다:

// lock_grant_blocked_waiter — src/transaction/lock_manager.c (annotated)
static int
lock_grant_blocked_waiter (THREAD_ENTRY * thread_p, LK_RES * res_ptr)
{
  waiter = res_ptr->waiter;
  while (waiter != NULL)
    {
      compat = lock_compat (waiter->blocked_mode,
                            res_ptr->total_holders_mode);
      if (compat == LOCK_COMPAT_NO)
        break;                    /* ← stop granting */

      /* grant the waiter */
      waiter->granted_mode = waiter->blocked_mode;
      waiter->blocked_mode = NULL_LOCK;

      /* move from waiter list to holder list */
      // ... remove from waiter list ...
      lock_position_holder_entry (res_ptr, waiter);

      /* update aggregates */
      res_ptr->total_holders_mode =
        lock_conv (waiter->granted_mode, res_ptr->total_holders_mode);

      /* add to transaction hold list */
      lock_insert_into_tran_hold_list (waiter, owner_tran_index);

      lock_update_non2pl_list (...);
      lock_resume (waiter, LOCK_RESUMED);

      waiter = next;
    }

  /* recompute total_waiters_mode from remaining waiters */
  if (change_total_waiters_mode)
    {
      mode = NULL_LOCK;
      for (w = res_ptr->waiter; w != NULL; w = w->next)
        mode = lock_conv (w->blocked_mode, mode);
      res_ptr->total_waiters_mode = mode;
    }
}

lock_grant_blocked_holder와의 핵심 차이:

관점	`lock_grant_blocked_holder`	`lock_grant_blocked_waiter`
스캔 대상	holder list (upgrader)	waiter list
호환성 체크 기준	해당 entry 뒤에 있는 holder들의 aggregate	`total_holders_mode` (모든 holder)
grant 시	`granted_mode = blocked_mode` (in-place)	waiter list에서 holder list로 이동
중단 조건	첫 번째 비호환 upgrader	첫 번째 비호환 waiter

두 호출의 순서가 중요하다: block된 holder(upgrader)가 먼저 grant되어 total_holders_mode가 변경될 수 있다. 그런 다음 block된 waiter가 갱신된 total_holders_mode에 대해 체크된다. 이는 upgrader가 새 waiter보다 우선순위를 갖도록 보장한다. upgrader가 먼저 왔고 이미 더 약한 lock을 hold하고 있기 때문이다.

4.8 변환 후 정리 — `lock_conversion_treatement`

class lock 변환이 grant된 후(PATH F, 또는 resume 후 PATH G), 더 강해진 class lock에 의해 포함되는 instance lock이 제거된다:

// lock_conversion_treatement — src/transaction/lock_manager.c
if (entry_ptr->res_head->key.type == LOCK_RESOURCE_CLASS
    && lock_conversion == true)
  {
    new_mode = entry_ptr->granted_mode;
    switch (old_mode)
      {
      case IS_LOCK:
        if (IS_WRITE_EXCLUSIVE_LOCK (new_mode)
            || new_mode == S_LOCK || new_mode == SIX_LOCK)
          lock_remove_all_inst_locks (thread_p, tran_index,
                                      oid, S_LOCK);
        break;

      case IX_LOCK:
        if (new_mode == SIX_LOCK)
          lock_remove_all_inst_locks (..., S_LOCK);
        else if (IS_WRITE_EXCLUSIVE_LOCK (new_mode))
          lock_remove_all_inst_locks (..., X_LOCK);
        break;

      case SIX_LOCK:
        /* new_mode == X_LOCK */
        lock_remove_all_inst_locks (..., X_LOCK);
        break;
      }
  }

무엇이 제거되고 왜:

이전 class lock	새 class lock	제거되는 instance lock	이유
IS	S, SIX, X	모든 S instance lock	class S가 instance S를 포함
IX	SIX	모든 S instance lock	SIX = S + IX; S 부분이 instance S를 포함
IX	X	모든 X instance lock	class X가 모든 것을 포함
SIX	X	모든 X instance lock	이미 S+IX였고, 이제 전체 X

이것은 메모리 최적화다: 포함된 instance LK_ENTRY가 해제되고 class entry의 ngranules가 감소한다. 이 정리가 없으면 class lock escalation이 중복 instance entry를 남겨두어 메모리를 낭비하고 hold list 순회를 느리게 한다.

4.9 구체적 시나리오 — 변환 생애주기

flowchart LR
  subgraph S1["1. T7이 row R에 S hold"]
    H1["holder: T7(S, count=1)"]
    AGG1["holders=S"]
  end

  subgraph S2["2. T5가 R에 S 획득 (PATH B)"]
    H2["holder: T7(S), T5(S)"]
    AGG2["holders=S"]
  end

  subgraph S3["3. T7이 X 요청 (PATH G)"]
    H3["holder: T7(S, blocked=X), T5(S)"]
    AGG3["holders=X\n(보수적)"]
  end

  subgraph S4["4. T5가 S 해제"]
    H4["holder: T7(X, count=2)"]
    AGG4["holders=X"]
  end

  S1 --> S2 --> S3 --> S4

Figure 4-1 — 변환 생애주기. Step 3: T7의 S->X 변환이 T5의 S에 의해 block됨(PATH G). total_holders_mode가 X(보수적)로 변경. Step 4: T5가 해제하면 lock_grant_blocked_holder가 T7의 upgrade를 grant: granted_mode가 X, blocked_mode가 NULL_LOCK이 되고 T7의 thread가 resume. count=2인 이유는 원래 S 요청과 X 요청 각각이 증가시켰기 때문.

4.10 성능 분석 — 변환 비용

재진입(PATH E)은 거의 공짜이고, 실제 변환은 O(holders)다.

시나리오	비용	병목
재진입 (같거나 더 약한 mode)	O(1): `lock_conv` 테이블 조회 + `count++`	없음 — list 순회 없음, compat check 없음
변환 grant(PATH F)	O(holders): 자기 자신 제외한 `group_mode` 계산을 위해 holder list 순회 필수	self-exclusion 루프. 100명의 holder가 있는 resource면 100회 반복.
변환 block(PATH G)	O(holders) + UPR 재배치 + suspend	PATH F와 동일 + UPR 순회 + context switch
Grant cascade(`lock_grant_blocked_holder`)	O(upgraders x holders-after-each)	resume 시 각 upgrader가 뒤에 있는 모든 holder에 대해 compat 체크. k개 upgrader와 n개 전체 holder면 최악 O(k x n).

왜 group_mode 계산이 O(1)이 아니고 O(holders)인가:

새 lock 요청(PATH B)에서는 aggregate total_holders_mode로 충분하다 — O(1) 체크. 그러나 변환(PATH F/G)에서는 aggregate에 요청 트랜잭션 자신의 mode가 포함되어 있으므로 제외해야 한다. aggregate LUB에서 하나의 mode를 “빼는” O(1) 방법은 없다. LUB는 역연산이 불가능하다. 그래서 코드가 holder list를 순회하며 entry_ptr를 건너뛰고 aggregate를 처음부터 다시 계산한다.

이것이 허용 가능한 이유:

변환은 새 grant나 재진입보다 빈도가 낮다(대부분의 lock 요청은 신규 또는 재진입).
resource당 holder 수는 보통 적다(OLTP에서 10 미만).
순회는 res_mutex 아래에서 실행되며 이는 resource별이다. 다른 resource는 영향 없다.

변환 후 정리(lock_conversion_treatement)는 O(instance locks)다:

class lock이 upgrade되면(IS->S, IX->X 등), lock_remove_all_inst_locks는 트랜잭션의 inst_hold_list를 순회하며 해당 class의 지정된 mode의 모든 instance lock을 제거한다. 이는 O(해당 class의 instance 수)가 아닌 O(트랜잭션이 hold한 전체 instance lock) 이다. 리스트가 class별로 분할되지 않기 때문이다. 3개 class에 걸쳐 5000개의 instance lock을 hold한 트랜잭션이 1000개만 해당 class에 속하더라도 5000개 전부를 검사한다.

4.11 챕터 요약 — 핵심 포인트

변환은 holder가 같은 resource를 다른 mode로 다시 요청할 때 trigger된다. 변환 테이블(lock_Conv)이 두 mode의 LUB를 계산한다.
**재진입(PATH E)**이 일반적인 경우다. 같거나 더 약한 mode면 count만 증가. class 빠른 경로에서는 res_mutex도 불필요.
count가 unlock 깊이를 제어한다. 각 lock_object가 증가시키고, 각 lock_unlock_object가 감소시킨다. count가 0이 되어야 lock이 실제로 해제된다.
**즉시 변환(PATH F)**은 다른 holder만 체크한다(자기 자신 제외). 이는 트랜잭션이 자기 자신과 deadlock에 빠지는 것을 방지한다.
**block된 변환(PATH G)**은 granted_mode와 blocked_mode를 모두 설정하고, holder list에 남아 UPR에 따라 재배치된다. total_holders_mode는 보수적으로 요청 mode를 포함한다.
Grant 순서: upgrader 먼저, 그 다음 waiter. lock_grant_blocked_holder가 upgrader를 앞에서 뒤로 스캔한 후, lock_grant_blocked_waiter가 갱신된 total_holders_mode에 대해 waiter list를 스캔한다.
변환 후 정리는 upgrade된 class lock에 의해 포함되는 instance lock을 제거하여 메모리를 해제하고 hold list 크기를 줄인다.

Chapter 5: Lock 해제와 NON2PL 프로토콜

이 챕터에서는 전체 unlock 경로를 추적한다. public API에서 내부 해제 메커니즘까지, 그리고 READ COMMITTED에서 조기 해제된 lock을 추적하는 NON2PL 프로토콜까지 다룬다.

5.1 세 가지 public unlock 진입점

flowchart LR
  UO["lock_unlock_object\n(oid, class_oid, lock, force)"]
  UDN["lock_unlock_object_donot_move_to_non2pl\n(oid, class_oid, lock)"]
  UA["lock_unlock_all\n(commit/rollback)"]

  INT["lock_internal_perform_unlock_object\n(entry, release_flag, move_to_non2pl)"]

  UO --> INT
  UDN --> INT
  UA --> INT

Figure 5-1 — 세 가지 unlock 진입점. release_flag와 move_to_non2pl 파라미터로 구분되며, lock의 완전 제거 여부와 non2pl 그림자 레코드 생성 여부를 제어한다.

진입점	`release_flag`	`move_to_non2pl`	사용 시점
`lock_unlock_object(force=true)`	false	true	강제 mid-transaction 해제
`lock_unlock_object(force=false)`	false	true	isolation에 따른 해제 (section 5.2 참조)
`lock_unlock_object_donot_move_to_non2pl`	false	false	btree FK 검증, 카탈로그 조회 — 호출자가 stale cache 위험 없음을 앎
`lock_unlock_all`	true	false	commit/rollback — 무조건 전부 해제

5.2 Unlock 호출자 패턴 (전체 지도는 Ch. 3 section 3.2)

전체 호출자 지도(Figure 3-3)는 Ch. 3 section 3.2에 있다. unlock에 특화된 패턴을 강조한다:

Unlock API	주요 호출자	이 variant를 쓰는 이유
`lock_unlock_object(force=false)`	`locator_sr.c`, `heap_file.c`, `scan_manager.c`	표준 isolation 기반 해제 — section 5.3의 4단계 필터 적용
`lock_unlock_object(force=true)`	`locator_sr.c` (DDL rollback), `serial.c`	isolation 체크를 우회하는 강제 해제 — 호출자가 lock이 반드시 해제되어야 함을 앎
`lock_unlock_object_donot_move_to_non2pl`	`btree.c` (FK 검증), `system_catalog.c`, `locator_sr.c`	클라이언트에 노출되지 않는 행 — stale cache 위험 없으므로 non2pl 추적 건너뜀
`lock_unlock_all`	`log_manager.c`만	commit/rollback — 무조건 일괄 해제
`lock_stop_instant_lock_mode`	`query_executor.c`	WHERE 평가 종료 시 모든 instant duration lock 해제

5.3 `lock_unlock_object` — isolation 정책 gate

가장 빈번하게 호출되는 unlock 함수다. 내부 함수에 위임하기 전에 isolation level 정책을 구현한다:

// lock_unlock_object — src/transaction/lock_manager.c (annotated)
void
lock_unlock_object (THREAD_ENTRY * thread_p, const OID * oid,
                    const OID * class_oid, LOCK lock, bool force)
{
  if (force == true)
    {
      entry_ptr = lock_find_tran_hold_entry (...);
      lock_internal_perform_unlock_object (thread_p, entry_ptr,
                                           false, true);
      return;
    }

  /* force == false: apply isolation policy */
  if (lock != S_LOCK)
    {
      /* These will not be released. */
      return;                    /* ← X, IX, SIX, etc. stay to commit */
    }

  isolation = logtb_find_isolation (tran_index);
  switch (isolation)
    {
    case TRAN_SERIALIZABLE:
    case TRAN_REPEATABLE_READ:
      return;                    /* nothing to do — S locks held to commit */

    case TRAN_READ_COMMITTED:
      lock_unlock_object_by_isolation (thread_p, tran_index,
                                       isolation, class_oid, oid);
      break;
    }
}

해제를 막는 세 가지 필터:

flowchart TD
  REQ["lock_unlock_object(force=false)"]
  F1{"lock != S_LOCK?"}
  F1 -- "yes (X, IX, ...)" --> KEEP1["유지: write lock은\n절대 조기 해제 안 됨"]
  F1 -- "no (S_LOCK)" --> F2{"isolation >= RR?"}
  F2 -- "yes (RR/SER)" --> KEEP2["유지: S lock을\ncommit까지 보유"]
  F2 -- "no (RC)" --> F3["lock_unlock_object_by_isolation"]
  F3 --> F3A{"root 또는 class OID?"}
  F3A -- "yes" --> KEEP3["유지: class lock은\n절대 조기 해제 안 됨"]
  F3A -- "no" --> F3B{"mvcc_is_mvcc_disabled_class?"}
  F3B -- "yes" --> REL["해제:\nlock_unlock_shared_inst_lock\n(move_to_non2pl=true)"]
  F3B -- "no (MVCC 테이블)" --> KEEP4["유지: snapshot 기반,\n해제할 lock 없음"]

Figure 5-2 — non-forced unlock 경로의 4단계 필터. S lock만, RC에서만, MVCC 비활성 instance OID에서만 실제로 해제된다. 나머지는 전부 commit까지 유지.

핵심 통찰: 전형적인 MVCC 워크로드에서 lock_unlock_object(force=false) 호출의 대다수는 KEEP4에 도달한다. MVCC 활성 테이블은 읽기에 lock이 아닌 snapshot을 사용하기 때문이다. 실제 해제 경로에 도달하는 유일한 lock은 MVCC 비활성 class(serial, root class, collation class, HA apply-info class) 의 S lock이다.

5.4 `lock_internal_perform_unlock_object` — 완전한 흐름

내부 핵심 함수다. entry가 발견되는 위치에 따라 세 가지 경우를 처리한다:

flowchart TD
  START["lock_internal_perform_unlock_object\n(entry_ptr, release_flag, move_to_non2pl)"]

  START --> DEC{"release_flag == false?"}
  DEC -- "yes" --> COUNT["count--\n(+ instant_lock_count-- if instant mode)"]
  COUNT --> EARLY{"blocked_mode == NULL\nAND count > 0?"}
  EARLY -- "yes" --> RET["조기 반환\n(다른 호출자가 이 lock을 아직 필요로 함)"]
  EARLY -- "no" --> MUTEX
  DEC -- "no (release_flag=true)" --> MUTEX

  MUTEX["pthread_mutex_lock(res_mutex)"]
  MUTEX --> FIND_H{"holder list에서\nentry 발견?"}
  FIND_H -- "yes" --> CASE_H["CASE H: holder 해제"]
  FIND_H -- "no" --> FIND_W{"waiter list에서\nentry 발견?"}
  FIND_W -- "yes" --> CASE_W["CASE W: waiter 제거\n(timeout/deadlock victim)"]
  FIND_W -- "no" --> ERR["ERROR: lost transaction"]

  CASE_H --> H_CHECK{"release_flag==false\nAND count > 0?"}
  H_CHECK -- "yes" --> H_BLOCKED["block된 holder 정리:\nblocked_mode = NULL\nUPR에 따라 재배치"]
  H_CHECK -- "no" --> H_RELEASE["완전 해제:\n1. tran hold list에서 제거\n2. class granules 감소\n3. move_to_non2pl이면: lock_add_non2pl_lock\n4. entry 해제"]

  H_RELEASE --> RECOMP["total_holders_mode 재계산"]
  H_BLOCKED --> RECOMP
  RECOMP --> EMPTY{"holder==NULL\nAND waiter==NULL?"}
  EMPTY -- "yes, non2pl==NULL" --> REMOVE["lock_remove_resource\n(hash table에서 삭제)"]
  EMPTY -- "yes, non2pl!=NULL" --> UNLOCK["res_mutex 해제\n(non2pl 때문에 resource 유지)"]
  EMPTY -- "no" --> GRANT["lock_grant_blocked_holder\nlock_grant_blocked_waiter\nres_mutex 해제"]

Figure 5-3 — lock_internal_perform_unlock_object의 완전한 흐름. 조기 반환(count > 0)은 Ch. 4 section 4.3의 재진입 guard다. CASE H가 정상적인 holder 해제다. CASE W는 timeout이나 deadlock 이후의 waiter 제거를 처리한다.

5.5 `release_flag`와 `count`의 상호작용

두 파라미터 release_flag와 count가 함께 lock의 실제 해제 여부를 제어한다:

// lock_internal_perform_unlock_object — src/transaction/lock_manager.c
if (release_flag == false)
  {
    entry_ptr->count--;
    if (lock_is_instant_lock_mode (tran_index))
      entry_ptr->instant_lock_count--;

    if (entry_ptr->blocked_mode == NULL_LOCK && entry_ptr->count > 0)
      return;    /* ← early return: other callers still need this lock */
  }

`release_flag`	감소 후 `count`	`blocked_mode`	결과
false	> 0	`NULL_LOCK`	조기 반환 — lock 유지, 다른 재진입 호출자가 아직 활성
false	> 0	!= `NULL_LOCK`	계속 진행 — timeout/victim으로 정리 중인 block된 holder
false	0	any	계속 진행 — 마지막 참조, 실제 해제로 진행
true	(감소 안 함)	any	계속 진행 — 무조건 해제 (`lock_unlock_all`)

5.6 CASE H — holder 해제 (정상 경로)

entry가 holder list에서 발견되고 count가 0에 도달했거나 release_flag가 true일 때:

// CASE H — lock_internal_perform_unlock_object (annotated)
/* remove from holder list */
if (prev == NULL)
  res_ptr->holder = curr->next;
else
  prev->next = curr->next;

if (release_flag == false && curr->count > 0)
  {
    /* blocked holder cleanup (timeout/victim) */
    curr->blocked_mode = NULL_LOCK;
    lock_position_holder_entry (res_ptr, entry_ptr);
  }
else
  {
    /* full release */
    lock_delete_from_tran_hold_list (curr, tran_index);
    lock_decrement_class_granules (curr->class_entry);

    if (release_flag == false && move_to_non2pl == true)
      lock_add_non2pl_lock (thread_p, res_ptr, tran_index,
                            curr->granted_mode);  /* ← NON2PL creation */

    lock_free_entry (tran_index, t_entry,
                     &lk_Gl.obj_free_entry_list, curr);
  }

/* recompute total_holders_mode */
mode = NULL_LOCK;
for (i = res_ptr->holder; i != NULL; i = i->next)
  {
    mode = lock_conv (i->granted_mode, mode);
    mode = lock_conv (i->blocked_mode, mode);  /* include upgraders */
  }
res_ptr->total_holders_mode = mode;

이 순회가 존재하는 이유 — 그리고 싼 이유. commit은 자기 entry를 검색하지 않는다. lock_unlock_all이 트랜잭션 쪽 hold list를 걸으며 각 LK_ENTRY 포인터를 unlock 경로에 직접 건넨다(dual-view의 보상, §1.4). 남는 순회는 위의 prev 찾기뿐인데, resource 쪽 리스트가 singly linked라서 노드를 빼려면 앞 노드가 필요하기 때문이다. 이 비대칭은 의도된 비용 거래다: 트랜잭션 뷰는 doubly linked (tran_prev)인데 commit이 수천 개의 entry를 하나씩 빼야 하고 각 unlink가 O(1)이어야 하기 때문이고, resource 쪽 holder list는 한 객체의 holder가 보통 몇 개 안 되는 데다 — 같은 res_mutex 구간이 어차피 그 리스트를 다시 걷기 때문에(아래의 aggregate 재계산, 이어서 grant pass) singly linked로 충분하다.

holder 제거 후 남은 상태에 따른 세 가지 결과:

남은 상태	동작
holder 없음, waiter 없음, non2pl 없음	`lock_remove_resource` — hash table에서 `LK_RES` 삭제
holder 없음, waiter 없음, non2pl 있음	`LK_RES` 유지 (`res_mutex` 해제) — non2pl entry가 아직 resource를 필요로 함
holder 또는 waiter 남아 있음	`lock_grant_blocked_holder` -> `lock_grant_blocked_waiter` (Ch. 4 section 4.6-4.7) -> `res_mutex` 해제

5.7 CASE W — waiter 제거 (timeout / deadlock victim)

entry가 holder list에 없지만 waiter list에서 발견될 때 — suspend된 thread가 timeout이나 deadlock detection으로 resume된 경우:

// CASE W — lock_internal_perform_unlock_object (annotated)
/* remove from waiter list */
if (prev == NULL)
  res_ptr->waiter = curr->next;
else
  prev->next = curr->next;

lock_free_entry (..., curr);

if (from_whom != NULL)
  lock_grant_blocked_waiter_partial (thread_p, res_ptr, from_whom);
else
  {
    /* recompute total_waiters_mode from remaining waiters */
    mode = NULL_LOCK;
    for (i = res_ptr->waiter; i != NULL; i = i->next)
      mode = lock_conv (i->blocked_mode, mode);
    res_ptr->total_waiters_mode = mode;
  }

lock_grant_blocked_waiter_partial은 lock_grant_blocked_waiter의 변형으로, 지정된 위치 이후의 waiter만 체크한다. 제거된 waiter가 from_whom 앞에 있었으므로, 그 뒤의 waiter만 이제 grant 가능할 수 있다.

5.8 `lock_unlock_all` — commit/rollback 해제

트랜잭션 종료 시 호출된다. 무조건 전부 해제한다:

// lock_unlock_all — src/transaction/lock_manager.c (annotated)
void
lock_unlock_all (THREAD_ENTRY * thread_p)
{
  /* 1. release all instance locks */
  entry_ptr = tran_lock->inst_hold_list;
  while (entry_ptr != NULL)
    {
      lock_internal_perform_unlock_object (thread_p, entry_ptr,
                                           true,    /* ← release_flag */
                                           false);  /* ← no non2pl */
      entry_ptr = tran_lock->inst_hold_list;  /* re-read head */
    }

  /* 2. release all class locks */
  entry_ptr = tran_lock->class_hold_list;
  while (entry_ptr != NULL)
    {
      lock_internal_perform_unlock_object (thread_p, entry_ptr,
                                           true, false);
      entry_ptr = tran_lock->class_hold_list;
    }

  /* 3. release root class lock */
  if (tran_lock->root_class_hold != NULL)
    lock_internal_perform_unlock_object (thread_p,
                                         tran_lock->root_class_hold,
                                         true, false);

  /* 4. clean up non2pl list */
  while (tran_lock->non2pl_list != NULL)
    {
      entry_ptr = tran_lock->non2pl_list;
      tran_lock->non2pl_list = entry_ptr->tran_next;
      if (entry_ptr->granted_mode == INCON_NON_TWO_PHASE_LOCK)
        tran_lock->num_incons_non2pl -= 1;
      lock_remove_non2pl (thread_p, entry_ptr, tran_index);
    }

  lock_clear_deadlock_victim (tran_index);
}

해제 순서가 의도적이다: instance -> class -> root. 이는 leaf에서 root 방향으로, 2PL의 역순 해제 요구사항에 부합한다. instance lock이 아직 존재하는 상태에서 class lock을 해제하면 다중 세분화 계층이 위반된다.

release_flag = true는 count를 감소시키지 않는다 — 루프가 재진입 깊이를 무시하고 entry를 무조건 해제한다. move_to_non2pl = false인 이유는 commit/rollback 시점에 미래 conflict detection을 위해 해제된 lock을 추적할 필요가 없기 때문이다.

5.9 NON2PL 프로토콜 — 생애주기

NON2PL은 READ COMMITTED에서 직렬화 비일관성을 감지하기 위한 그림자 레코드 메커니즘이다. 이것은 block하는 lock mode가 아니다 — 수동적인 추적 레코드다.

Phase 1: 생성 — lock_add_non2pl_lock

lock_internal_perform_unlock_object가 move_to_non2pl = true로 holder를 해제할 때:

// lock_add_non2pl_lock — src/transaction/lock_manager.c (annotated)
static LK_ENTRY *
lock_add_non2pl_lock (THREAD_ENTRY * thread_p, LK_RES * res_ptr,
                      int tran_index, LOCK lock)
{
  /* check if I already have a non2pl entry on this resource */
  non2pl = res_ptr->non2pl;
  while (non2pl != NULL)
    {
      if (non2pl->tran_index == tran_index)
        break;
      non2pl = non2pl->next;
    }

  if (non2pl != NULL)
    {
      /* merge: upgrade the existing non2pl entry's mode */
      if (non2pl->granted_mode != INCON_NON_TWO_PHASE_LOCK)
        {
          compat = lock_compat (lock, non2pl->granted_mode);
          if (compat == LOCK_COMPAT_NO)
            {
              non2pl->granted_mode = INCON_NON_TWO_PHASE_LOCK;
              tran_lock->num_incons_non2pl += 1;
            }
          else
            non2pl->granted_mode = lock_conv (lock, non2pl->granted_mode);
        }
    }
  else
    {
      /* create new non2pl entry */
      non2pl = lock_get_new_entry (...);
      lock_initialize_entry_as_non2pl (non2pl, tran_index,
                                        res_ptr, lock);
      /* link into resource non2pl list */
      non2pl->next = res_ptr->non2pl;
      res_ptr->non2pl = non2pl;
      /* link into transaction non2pl list */
      lock_insert_into_tran_non2pl_list (non2pl, tran_index);
    }
}

핵심 세부사항: merge 경로. 트랜잭션이 같은 resource에 이미 non2pl entry를 갖고 있으면(예: 같은 RC 트랜잭션에서 같은 serial을 두 번 읽고 매번 S를 해제한 경우), 기존 entry가 복제되지 않고 upgrade된다. 새 mode가 기존 non2pl mode와 비호환이면 INCON_NON_TWO_PHASE_LOCK으로 직접 승격된다.

Phase 2: conflict 표시 — lock_update_non2pl_list

lock이 성공적으로 grant될 때마다(Ch. 3의 PATH B, F) 호출된다. resource의 non2pl list를 순회하며 다른 트랜잭션의 각 entry를 체크한다:

// lock_update_non2pl_list — src/transaction/lock_manager.c (annotated)
curr = res_ptr->non2pl;
while (curr != NULL)
  {
    if (curr->tran_index == tran_index)
      {
        /* same transaction: remove our own non2pl entry */
        lock_delete_from_tran_non2pl_list (curr, tran_index);
        lock_free_entry (..., curr);
      }
    else
      {
        /* different transaction: check for conflict */
        if (curr->granted_mode != INCON_NON_TWO_PHASE_LOCK)
          {
            compat = lock_compat (lock, curr->granted_mode);
            if (compat == LOCK_COMPAT_NO)
              {
                curr->granted_mode = INCON_NON_TWO_PHASE_LOCK;
                tran_lock->num_incons_non2pl += 1;
              }
          }
      }
    curr = curr->next;
  }

두 가지 동작:

같은 트랜잭션: 이전 non2pl entry가 있는 resource에 새 lock을 획득하면, 그 entry를 제거한다. 이제 실제 lock을 hold하므로 그림자가 대체된다.
다른 트랜잭션: 새로 grant된 lock이 다른 트랜잭션의 non2pl granted_mode와 비호환이면 INCON_NON_TWO_PHASE_LOCK으로 승격한다. 의미: “네가 읽고 해제한 행이 다른 트랜잭션에 의해 수정되었다.”

Phase 3: 알림 — lock_notify_isolation_incons

다음 fetch 경계에서 locator_sr.c가 이 함수를 호출한다:

// lock_notify_isolation_incons — src/transaction/lock_manager.c (simplified)
void
lock_notify_isolation_incons (THREAD_ENTRY * thread_p,
    bool (*fun) (const OID *, const OID *, void *), void *args)
{
  if (isolation == TRAN_REPEATABLE_READ
      || isolation == TRAN_SERIALIZABLE)
    return;    /* nothing was released under RR/SER */

  curr = tran_lock->non2pl_list;
  while (tran_lock->num_incons_non2pl > 0 && curr != NULL)
    {
      if (curr->granted_mode == INCON_NON_TWO_PHASE_LOCK)
        {
          ret_val = (*fun) (&curr->res_head->key.class_oid,
                            &curr->res_head->key.oid, args);
          /* remove from non2pl list, free entry */
          tran_lock->num_incons_non2pl -= 1;
        }
      curr = curr->tran_next;
    }
}

콜백(locator_notify_decache)은 표시된 각 OID를 응답에 LC_FETCH_DECACHE_LOCK으로 추가하여, 클라이언트에게 캐시된 사본을 무효화하라고 지시한다.

Phase 4: 정리 — lock_unlock_all

commit/rollback 시, lock_unlock_all이 전체 non2pl list를 순회하며 lock_remove_non2pl로 모든 entry를 제거한다.

5.10 NON2PL 범위 — serial에서만 실질적으로 의미 있는 이유

lock_unlock_object_by_isolation이 범위 gate다:

// lock_unlock_object_by_isolation — src/transaction/lock_manager.c
if (isolation != TRAN_READ_COMMITTED)
  return;                             /* RR/SER: nothing released */

if (OID_IS_ROOTOID (oid) || OID_IS_ROOTOID (class_oid))
  return;                             /* class locks kept */

if (mvcc_is_mvcc_disabled_class (class_oid))
  lock_unlock_shared_inst_lock (...); /* ← non2pl path */
else
  { /* MVCC table: "READ COMMITTED isolation uses snapshot
       instead of locks. We don't have to release anything." */ }

mvcc_is_mvcc_disabled_class가 true를 반환하는 class는 네 종류뿐이다: root class, serial class, collation class, HA apply-info class. 이 중에서 instance OID에 S lock을 걸고 트랜잭션 중간에 해제하는 현실적인 RC 워크로드를 만들어내는 것은 serial뿐이다.

역사적 맥락: non2pl/decache 인프라 전체(locator_notify_decache, LC_FETCH_DECACHE_LOCK, lock_notify_isolation_incons)는 MVCC 이전에 만들어졌다. MVCC 이전에는 모든 instance 읽기가 S lock을 사용했고, RC는 이를 조기 해제했으므로 모든 행에 대해 non2pl 추적이 필요했다. MVCC 도입 후 일반 테이블은 가시성에 snapshot을 사용하고, non2pl 경로는 MVCC 비활성 class에만 좁혀졌다. 인프라는 그대로 남아 있지만 활성 범위는 사실상 RC 환경의 serial 읽기뿐이다.

5.11 instant lock과 NON2PL의 관계

Instant lock은 WHERE 절 평가 중에 획득한 lock이 평가 단계 종료 시 자동으로 해제되는 mode다.

// lock_start_instant_lock_mode — src/transaction/lock_manager.c
void lock_start_instant_lock_mode (int tran_index)
{
  tran_lock->is_instant_duration = true;
}

// lock_stop_instant_lock_mode — src/transaction/lock_manager.c
void lock_stop_instant_lock_mode (THREAD_ENTRY * thread_p,
                                   int tran_index, bool need_unlock)
{
  /* walk instance hold list */
  entry_ptr = tran_lock->inst_hold_list;
  while (entry_ptr != NULL)
    {
      count = entry_ptr->instant_lock_count;
      if (need_unlock)
        while (count > 0)
          {
            lock_internal_perform_unlock_object (thread_p, entry_ptr,
                false, true);   /* ← move_to_non2pl = true */
            count--;
          }
      entry_ptr->instant_lock_count = 0;
      entry_ptr = next_ptr;
    }
  /* same for class hold list ... */
  tran_lock->is_instant_duration = false;
}

NON2PL과의 관계: instant lock은 move_to_non2pl = true로 해제되므로 non2pl에 공급한다. 그러나 non2pl은 instant lock 없이도 존재한다. 모든 RC 환경의 mid-transaction S lock 해제가 같은 경로를 거친다.

호출자: query_executor.c만 instant lock mode를 사용한다 (lock_start_instant_lock_mode / lock_stop_instant_lock_mode). 구체적으로 쿼리 실행의 조건 평가 주변에서 사용된다.

엣지 케이스 — non-instant lock 보호: is_instant_duration == true이고 트랜잭션이 이미 instant_lock_count == 0인 IX 이상의 lock(non-instant lock)을 hold하고 있을 때, 새 요청이 hold 중인 mode와 비호환이면 instant mode가 강제 중단된다(lock_stop_instant_lock_mode(need_unlock=false)). 이는 instant mode 정리 시 non-instant lock이 실수로 해제되는 것을 방지한다.

5.12 성능 분석 — 해제 비용과 grant cascade

대부분의 unlock 호출은 O(1)이다 — count 조기 반환이 지배적.

전형적인 OLTP에서 트랜잭션은 재진입을 통해(Ch. 4 section 4.3) 같은 lock을 여러 번 획득한다. 각 lock_unlock_object는 count만 감소시킨다. mutex 없음, list 조작 없음:

if (release_flag == false)
  {
    entry_ptr->count--;
    if (entry_ptr->blocked_mode == NULL_LOCK && entry_ptr->count > 0)
      return;    /* ← most unlock calls exit here */
  }

count가 0에 도달할 때 — 실제 해제 비용:

단계	비용	비고
`res_mutex` 획득	O(1)	resource별, 대부분 비경합
holder list에서 entry 찾기	O(holders)	singly-linked list 선형 스캔
holder list에서 제거	O(1)	포인터 unlink
tran hold list에서 제거	O(1)	doubly-linked — O(1) unlink
`lock_add_non2pl_lock` (`move_to_non2pl`일 때)	O(해당 resource의 non2pl entry 수)	기존 entry와 merge 여부 확인을 위해 non2pl list 순회
entry를 풀로 반환	O(1)	로컬 풀 또는 lockfree retire
`total_holders_mode` 재계산	O(남은 holders)	전체 남은 holder list를 순회하여 LUB 계산
Grant cascade	O(upgraders + grant 가능한 waiters)	아래 참조

total_holders_mode 재계산이 해제당 O(holders) 비용이다.

mode = NULL_LOCK;
for (i = res_ptr->holder; i != NULL; i = i->next)
  {
    mode = lock_conv (i->granted_mode, mode);
    mode = lock_conv (i->blocked_mode, mode);  /* upgraders too */
  }
res_ptr->total_holders_mode = mode;

이를 O(1)로 최적화할 수 없는 이유는 LUB 연산이 역연산 불가능하기 때문이다. 제거된 mode를 aggregate에서 “빼는” 것이 불가능하여 처음부터 다시 계산해야 한다. 같은 한계가 변환(Ch. 4 section 4.10)에서 O(holders)를 요구하는 이유이기도 하다.

Grant cascade — 하나를 해제하면 여러 개를 깨울 수 있다:

total_holders_mode 재계산 후 해제자가 호출하는 순서:

lock_grant_blocked_holder — O(upgraders x holders-behind-each)
lock_grant_blocked_waiter — O(waiters), 각각 total_holders_mode에 대해 체크
grant된 각 waiter: holder list로 이동 + lock_resume

flowchart LR
  REL["T1이 X_LOCK 해제"]
  RECOMP["total_holders_mode\n재계산\nO(남은 holders)"]
  GBH["grant_blocked_holder\n(각 upgrader 체크)"]
  GBW["grant_blocked_waiter\n(각 waiter를\ntotal_holders_mode와 체크)"]
  WAKE["N개 thread resume\n(N번 context switch)"]

  REL --> RECOMP --> GBH --> GBW --> WAKE

Figure 5-4 — 해제 cascade 비용. 단일 해제가 O(upgraders + waiters) compat check와 N번의 thread wakeup을 유발할 수 있다. 최악의 경우는 많은 waiter가 있는 hot row지만, 이것이 해제가 가장 큰 가치를 제공하는 경우이기도 하다.

최악의 시나리오: 한 X lock holder가 있고 50개의 S lock waiter가 있는 hot row. holder가 해제하면:

total_holders_mode 재계산: O(0) (남은 holder 없음)
grant_blocked_holder: O(0) (upgrader 없음)
grant_blocked_waiter: 50개 waiter 전부 grant 가능(S는 S와 호환) -> 50개 entry를 holder list로 이동, 50번 lock_resume, 50번 context switch

비용이 크지만 불가피하다. 50개 thread가 suspend되어 있었고 깨워야 한다. 대안(각 깨어난 thread가 독립적으로 호환성을 재체크)은 총 O(50^2)의 compat check가 되어 O(50)보다 나쁘다.

Grant 경로에서의 NON2PL 비용:

lock_update_non2pl_list는 모든 성공적인 grant(PATH B, F, 그리고 cascade된 각 grant) 시 호출된다. resource의 non2pl list를 순회한다 — O(resource당 non2pl entry 수). MVCC 워크로드에서 이 list는 거의 항상 비어 있다(non2pl은 RC의 MVCC 비활성 class에서만 존재). 그러나 serial 집약적 워크로드에서는 많은 RC 트랜잭션에 걸쳐 non2pl list가 누적될 수 있다.

5.13 챕터 요약 — 핵심 포인트

세 가지 public unlock API가 release_flag와 move_to_non2pl로 구분된다. lock_unlock_all(commit/rollback)은 release_flag=true로 count 체크를 우회한다.
lock_unlock_object(force=false)는 4개의 필터를 통과해야 실제 해제된다: S lock만, RC에서만, instance만, MVCC 비활성 class만. 실제로는 serial에 해당한다.
count가 해제 깊이를 제어한다. 각 lock_object가 증가, 각 lock_unlock_object가 감소. count가 0이 되어야 lock이 해제된다 — 재진입 guard.
holder 해제 후, 남은 holder list를 순회하여 total_holders_mode를 재계산한 다음, block된 holder와 waiter가 grant된다(Ch. 4 section 4.6-4.7).
Resource 제거: LK_RES는 holder, waiter, non2pl 세 list가 모두 비어야 hash table에서 삭제된다. non2pl만 있는 resource는 살아 있는다.
NON2PL 생애주기: 생성(lock_add_non2pl_lock) -> conflict 표시 (lock_update_non2pl_list) -> 클라이언트 알림 (lock_notify_isolation_incons) -> 정리(lock_unlock_all).
NON2PL 범위는 MVCC 이후 축소되었다. 인프라는 MVCC 이전 시대의 것이고, 오늘날에는 MVCC 비활성 class(실질적으로 serial)만 이 경로를 사용한다.
Instant lock은 move_to_non2pl = true를 통해 non2pl에 공급하지만, 두 메커니즘은 독립적이다. non2pl은 instant lock 없이도 존재하고, instant lock 정리는 기존 non-instant lock을 보호한다.
lock_unlock_all의 해제 순서는 instance -> class -> root -> non2pl로, leaf에서 root 방향이며 2PL의 역순 해제 요구사항에 부합한다.

Chapter 6: Lock Escalation

Lock escalation은 instance lock 수가 임계값을 초과할 때 다수의 세밀한 instance lock을 하나의 거친 class lock으로 대체한다. 메모리 압박 해소 밸브다. 이것이 없으면 100K 행을 건드리는 bulk UPDATE가 100K개의 LK_ENTRY 구조체를 hold하게 된다.

6.1 escalation이 trigger되는 시점

Escalation은 모든 instance lock 요청의 맨 위에서, hash lookup 전에, lock_internal_perform_lock_object 안에서 체크된다:

// lock_internal_perform_lock_object — src/transaction/lock_manager.c
start:
  if (class_oid != NULL && !OID_IS_ROOTOID (class_oid))
    {
      /* instance lock request */
      ret_val = lock_escalate_if_needed (thread_p, class_entry,
                                          tran_index);
      // ... if escalated, class lock subsumes → return LK_GRANTED
    }

이는 escalation이 모든 instance lock 획득마다 평가된다는 뜻이다. 주기적이거나 지연된 것이 아니다. lock_check_escalate 함수가 임계값 체크를 충분히 빠르게 수행하므로 이 빈도가 정당화된다.

6.2 `lock_check_escalate` — 임계값 체크

// lock_check_escalate — src/transaction/lock_manager.c (annotated)
static bool
lock_check_escalate (THREAD_ENTRY * thread_p, LK_ENTRY * class_entry,
                     LK_TRAN_LOCK * tran_lock)
{
  if (class_entry == NULL)
    return false;

  if (class_entry->granted_mode == BU_LOCK)
    return false;    /* ← bulk update already has class-level lock */

  if (tran_lock->lock_escalation_on == true)
    return false;    /* ← another thread of same tran is escalating */

  superclass_entry = class_entry->class_entry;

  if (superclass_entry != NULL
      && !OID_IS_ROOTOID (&superclass_entry->res_head->key.oid))
    {
      /* class hierarchy: check superclass's ngranules */
      if (superclass_entry->ngranules
          < prm_get_integer_value (PRM_ID_LK_ESCALATION_AT))
        return false;
    }
  else if (class_entry->ngranules
           < prm_get_integer_value (PRM_ID_LK_ESCALATION_AT))
    return false;

  return true;    /* ← escalation needed */
}

escalation을 막는 다섯 가지 조건:

조건	이유
`class_entry == NULL`	class 컨텍스트 없음 (instance lock에서는 발생하면 안 됨)
`granted_mode == BU_LOCK`	bulk update가 이미 class 수준 보호를 가짐
`lock_escalation_on == true`	같은 트랜잭션의 다른 thread가 이미 escalation 중 — 재진입 guard
superclass 계층: `superclass->ngranules < threshold`	class 계층 구조에서 superclass가 granule count를 집계
직접: `class_entry->ngranules < threshold`	일반적인 경우 — 아직 instance lock이 충분히 쌓이지 않음

임계값은 PRM_ID_LK_ESCALATION_AT으로, cubrid.conf에서 설정하는 런타임 구성 파라미터다. class_entry의 ngranules 필드는 instance lock이 grant될 때마다(Ch. 3 PATH A/B) lock_increment_class_granules가 증가시키고, 해제 시(Ch. 5) lock_decrement_class_granules가 감소시킨다.

6.3 `lock_escalate_if_needed` — escalation 절차

lock_check_escalate가 true를 반환하면 실제 escalation이 시작된다:

flowchart LR
  CHK["lock_check_escalate\n-> true"]
  ABORT{"PRM_ID_LK_ROLLBACK\n_ON_LOCK_ESCALATION?"}
  ABORT -- "yes" --> ROLL["트랜잭션 abort\nER_LK_ROLLBACK_ON_LOCK_ESCALATION"]
  ABORT -- "no" --> MODE["escalation된\nclass lock mode 결정"]
  MODE --> TRY["lock_internal_perform_lock_object\n(class_oid, max_class_lock,\nFORCE_ZERO_WAIT)"]
  TRY --> OK{"grant됨?"}
  OK -- "yes" --> UNDO["이전 class lock의\ncount 하나 해제\n(count 균형 유지)"]
  UNDO --> DONE["LK_GRANTED 반환\n(호출자가 subsumption 체크)"]
  OK -- "no" --> FAIL["lock_escalation_on 리셋\n실패 반환\n(정상 경로로 진행)"]

Figure 6-1 — Escalation 절차. escalation된 class lock은 조건부 (FORCE_ZERO_WAIT)로 시도된다. 실패하면(다른 트랜잭션이 충돌하는 class lock을 hold) escalation이 조용히 포기되고 정상 instance lock 경로가 진행된다.

코드:

// lock_escalate_if_needed — src/transaction/lock_manager.c (annotated)
static int
lock_escalate_if_needed (THREAD_ENTRY * thread_p,
                         LK_ENTRY * class_entry, int tran_index)
{
  tran_lock = &lk_Gl.tran_lock_table[tran_index];
  pthread_mutex_lock (&tran_lock->hold_mutex);

  if (lock_check_escalate (...) == false)
    {
      pthread_mutex_unlock (&tran_lock->hold_mutex);
      return LK_NOTGRANTED;   /* ← not an error, just "no escalation" */
    }

  /* option: abort instead of escalating */
  if (prm_get_bool_value (PRM_ID_LK_ROLLBACK_ON_LOCK_ESCALATION))
    {
      er_set (ER_ERROR_SEVERITY, ...,
              ER_LK_ROLLBACK_ON_LOCK_ESCALATION, ...);
      lock_set_tran_abort_reason (tran_index,
                                  TRAN_ABORT_DUE_ROLLBACK_ON_ESCALATION);
      pthread_mutex_unlock (&tran_lock->hold_mutex);
      return LK_NOTGRANTED_DUE_ABORTED;
    }

  /* set re-entrance guard */
  tran_lock->lock_escalation_on = true;

  /* determine escalated mode */
  if (class_entry->granted_mode == NULL_LOCK
      || class_entry->granted_mode == S_LOCK
      || class_entry->granted_mode == X_LOCK
      || class_entry->granted_mode == SCH_M_LOCK)
    {
      /* already strong enough — no instance locks possible */
      tran_lock->lock_escalation_on = false;
      pthread_mutex_unlock (&tran_lock->hold_mutex);
      return LK_GRANTED;
    }

  /* IS → S, IX/SIX → X */
  if (class_entry->granted_mode == IX_LOCK
      || class_entry->granted_mode == SIX_LOCK)
    max_class_lock = X_LOCK;
  else  /* IS_LOCK */
    max_class_lock = S_LOCK;

  pthread_mutex_unlock (&tran_lock->hold_mutex);

  /* attempt the escalated class lock — conditional (no wait) */
  granted = lock_internal_perform_lock_object (
    thread_p, tran_index,
    &class_entry->res_head->key.oid,
    NULL,                 /* class_oid = NULL → this is a class lock */
    max_class_lock,
    LK_FORCE_ZERO_WAIT,  /* ← conditional: don't block */
    &class_entry, NULL);

  if (granted != LK_GRANTED)
    {
      /* escalation failed — fall through to normal instance lock */
      tran_lock->lock_escalation_on = false;
      return granted;
    }

  /* success: undo the extra count from the escalation request */
  lock_internal_perform_unlock_object (thread_p, class_entry,
                                       false, true);

  tran_lock->lock_escalation_on = false;
  return LK_GRANTED;
}

6.4 escalation mode 결정 — 단순 규칙

Mode 결정은 비용이 큰 instance list 스캔을 피하기 위해 의도적으로 단순하다:

현재 class lock	escalation 대상	근거
`IS_LOCK`	`S_LOCK`	instance를 읽고 있었다 -> class S 획득
`IX_LOCK`	`X_LOCK`	instance를 쓰고 있었다 -> class X 획득
`SIX_LOCK`	`X_LOCK`	읽기+쓰기 중이었다 -> class X 획득
`S_LOCK`, `X_LOCK`, `SCH_M_LOCK`	(no-op)	이미 class 수준 — escalation할 instance lock 없음
`NULL_LOCK`	(no-op)	class lock이 없음 — instance lock이 있으면 안 됨

소스의 주석: “shared와 exclusive instance lock을 세는 것은 높은 CPU 사용을 유발할 수 있으므로, 단순 규칙을 사용했다.” instance hold list를 순회하여 모든 instance mode의 정확한 LUB를 계산하는 것은 O(instance locks) 이다 — 바로 escalation이 피하려는 것이다.

6.5 왜 `LK_FORCE_ZERO_WAIT`인가 — 조건부 escalation

escalation된 class lock은 LK_FORCE_ZERO_WAIT(blocking 없음, 에러 메시지 없음)으로 시도된다. 실패하면:

escalation이 조용히 포기된다.
lock_escalation_on이 리셋된다.
호출자(lock_internal_perform_lock_object)가 정상 instance lock 경로로 진행한다.

이는 의도적인 설계다: escalation은 최적화이지 필수가 아니다. class lock을 대기 없이 얻을 수 없으면(다른 트랜잭션이 충돌하는 lock을 hold하므로), 전체 트랜잭션을 class lock 대기에 block시키는 것보다 instance별 lock을 계속하는 것이 낫다. class lock은 충돌의 cascade를 유발할 수 있기 때문이다.

6.6 Escalation 후: instance lock에 일어나는 일

Escalation 성공 후, lock_internal_perform_lock_object의 호출자가 체크한다:

if (ret_val == LK_GRANTED
    && lock_is_class_lock_escalated (
         lock_get_object_lock (class_oid, oid_Root_class_oid),
         lock) == true)
  {
    return LK_GRANTED;   /* class lock subsumes the instance request */
  }

lock_is_class_lock_escalated는 이제 upgrade된 class lock mode가 요청된 instance lock mode를 커버할 만큼 강한지 체크한다(예: class X가 instance S 또는 X를 포함).

기존 instance LK_ENTRY 구조체는 escalation 자체에 의해 즉시 해제되지 않는다. 이들은 나중에 class lock 변환이 처리될 때 lock_conversion_treatement 정리(Ch. 4 section 4.8)를 통해, 그리고 commit 시 lock_unlock_all이 instance hold list를 순회할 때 개별적으로 해제된다.

6.7 `PRM_ID_LK_ROLLBACK_ON_LOCK_ESCALATION` 옵션

일부 애플리케이션은 escalation 대신 abort를 선호한다. class lock은 더 거칠어서 다른 트랜잭션과 예상치 못한 직렬화를 유발할 수 있기 때문이다:

if (prm_get_bool_value (PRM_ID_LK_ROLLBACK_ON_LOCK_ESCALATION))
  {
    er_set (..., ER_LK_ROLLBACK_ON_LOCK_ESCALATION, ...);
    lock_set_tran_abort_reason (tran_index,
                                TRAN_ABORT_DUE_ROLLBACK_ON_ESCALATION);
    return LK_NOTGRANTED_DUE_ABORTED;
  }

이 파라미터가 true이면 escalation 임계값에 도달하면 트랜잭션이 TRAN_ABORT_DUE_ROLLBACK_ON_ESCALATION으로 abort된다. 호출자에서 체크된다:

// lock_internal_perform_lock_object — after lock_escalate_if_needed
if (ret_val == LK_NOTGRANTED_DUE_ABORTED)
  {
    LOG_TDES *tdes = LOG_FIND_TDES (tran_index);
    if (tdes && tdes->tran_abort_reason
        == TRAN_ABORT_DUE_ROLLBACK_ON_ESCALATION)
      goto end;    /* propagate the abort */
  }

6.8 구체적 시나리오 — bulk UPDATE 중 escalation

flowchart LR
  subgraph S1["Escalation 전"]
    CL1["class A: IX_LOCK\nngranules = 4999"]
    IL1["inst locks:\nrow1(X), row2(X),\n..., row4999(X)"]
  end

  subgraph S2["5000번째 행 요청이 escalation trigger"]
    CHK2["lock_check_escalate:\nngranules(4999) >= threshold(5000)?\n아직 아님 -> row5000 정상 grant"]
  end

  subgraph S3["5001번째 행 요청"]
    CHK3["lock_check_escalate:\nngranules(5000) >= threshold(5000)?\nYES -> escalate"]
    ESC3["IX -> X (FORCE_ZERO_WAIT)"]
  end

  subgraph S4["Escalation 후"]
    CL4["class A: X_LOCK\n(모든 instance를 포함)"]
    IL4["inst locks: 아직 존재\n(commit 시 또는\nconversion cleanup으로 해제)"]
  end

  S1 --> S2 --> S3 --> S4

Figure 6-2 — bulk UPDATE 중 escalation. ngranules가 임계값(여기서 5000)에 도달하면 다음 instance lock 요청이 IX에서 X로의 escalation을 trigger한다. class X lock이 향후 모든 instance 요청을 포함하므로 더 이상 instance LK_ENTRY가 생성되지 않는다. 기존 instance entry는 나중에 정리된다.

6.9 챕터 요약 — 핵심 포인트

Escalation은 모든 instance lock 요청마다 체크된다 — lock_internal_perform_lock_object의 맨 위에서, hash lookup 전에.
임계값은 PRM_ID_LK_ESCALATION_AT(설정 가능). class LK_ENTRY의 ngranules 카운터가 현재 instance lock 수를 추적한다.
Escalation mode는 단순 규칙으로 결정된다: IS->S, IX/SIX->X. instance list 스캔 없음 — 그 비용을 피하는 것이 핵심이다.
Escalation은 조건부다 (LK_FORCE_ZERO_WAIT). class lock을 blocking 없이 얻을 수 없으면 escalation이 조용히 포기되고 정상 instance lock 경로가 진행된다.
lock_escalation_on은 재진입 guard다 — 같은 트랜잭션의 여러 thread가 동시에 escalation하는 것을 방지한다.
**PRM_ID_LK_ROLLBACK_ON_LOCK_ESCALATION**은 애플리케이션이 escalation 대신 abort를 선택할 수 있게 하여, class lock이 부과하는 거친 직렬화를 피한다.
기존 instance lock은 즉시 해제되지 않는다 — conversion treatment (Ch. 4 section 4.8)과 commit 시 lock_unlock_all에 의해 정리된다.

Chapter 7: Suspend/Resume와 Timeout

Lock 요청이 즉시 grant될 수 없을 때(Ch. 3의 PATH D 또는 G), 요청 thread는 lock이 사용 가능해지거나 timeout이 만료되거나 deadlock이 감지될 때까지 suspend된다. 이 챕터에서는 suspend/resume 기계와 네 가지 wakeup 경로를 추적한다.

7.1 `lock_suspend` — thread를 재우기

// lock_suspend — src/transaction/lock_manager.c (annotated)
static LOCK_WAIT_STATE
lock_suspend (THREAD_ENTRY * thread_p, LK_ENTRY * entry_ptr,
              int wait_msecs)
{
  /* assert: no page latches held while waiting for a lock */
  assert (lock_is_safe_lock_with_page (thread_p, entry_ptr)
          || !pgbuf_has_perm_pages_fixed (thread_p));

  /* register wait info into the thread entry */
  entry_ptr->thrd_entry->lockwait = (void *) entry_ptr;
  entry_ptr->thrd_entry->lockwait_stime =
    (tv.tv_sec * 1000000LL + tv.tv_usec) / 1000LL;  /* ms */
  entry_ptr->thrd_entry->lockwait_msecs = wait_msecs;
  entry_ptr->thrd_entry->lockwait_state = (int) LOCK_SUSPENDED;

  /* register in WFG for deadlock detection */
  lk_Gl.TWFG_node[entry_ptr->tran_index].thrd_wait_stime =
    entry_ptr->thrd_entry->lockwait_stime;
  lk_Gl.deadlock_and_timeout_detector++;

  /* record which resource we're waiting for (for diagnostics) */
  tdes->waiting_for_res = entry_ptr->res_head;

  /* === actually suspend === */
  thread_suspend_wakeup_and_unlock_entry (entry_ptr->thrd_entry,
                                           THREAD_LOCK_SUSPENDED);

  /* === resumed here === */
  lk_Gl.deadlock_and_timeout_detector--;
  lk_Gl.TWFG_node[entry_ptr->tran_index].thrd_wait_stime = 0;
  tdes->waiting_for_res = NULL;

  /* dispatch on resume reason */
  // ... see §7.3 ...
}

suspend 전 설정되는 핵심 필드:

필드	위치	목적
`thrd_entry->lockwait`	thread entry	대기 중인 `LK_ENTRY`를 가리킨다. non-NULL이면 “이 thread가 lock 대기 중 suspend됨”.
`thrd_entry->lockwait_stime`	thread entry	대기 시작 timestamp(ms). timeout 체크에 사용.
`thrd_entry->lockwait_msecs`	thread entry	timeout 데드라인. `LK_INFINITE_WAIT`(-1)이면 timeout 없음.
`thrd_entry->lockwait_state`	thread entry	`LOCK_SUSPENDED`로 설정. 깨우는 쪽이 resume 이유로 변경.
`TWFG_node[tran].thrd_wait_stime`	WFG node	deadlock daemon이 이 트랜잭션이 대기 중임을 파악하는 데 사용.
`deadlock_and_timeout_detector`	`lk_Gl`	atomic 카운터. 0이면 deadlock daemon이 scan을 건너뜀(대기 중인 thread 없음).

page latch 안전 assert: thread가 lock 대기를 위해 suspend할 때 영구 page latch를 hold하고 있으면 안 된다. page latch를 hold한 채 lock을 기다리면, lock을 hold하고 page latch가 필요한 다른 thread와 deadlock에 빠질 수 있다. 이는 전형적인 latch-lock 순서 위반이다. assert가 이를 개발 단계에서 잡아낸다.

7.2 `lock_resume` — thread 깨우기

// lock_resume — src/transaction/lock_manager.c (annotated)
static void
lock_resume (LK_ENTRY * entry_ptr, int state)
{
  /* The caller is holding the thread entry mutex */
  entry_ptr->thrd_entry->lockwait = NULL;
  entry_ptr->thrd_entry->lockwait_state = (int) state;
  entry_ptr->thrd_entry->resume_status = THREAD_LOCK_RESUMED;
  pthread_cond_signal (&entry_ptr->thrd_entry->wakeup_cond);
  thread_unlock_entry (entry_ptr->thrd_entry);
}

프로토콜: 깨우는 쪽(lock_resume를 호출하는 쪽)이 반드시:

thread entry mutex를 hold (thread_lock_entry).
LK_IS_LOCKWAIT_THREAD(thrd) 확인 — thread가 여전히 suspend 상태.
condition variable을 signal하기 전에 lockwait = NULL과 lockwait_state = state를 설정.
signal 후 mutex 해제.

suspend된 thread는 깨어나면 lockwait_state를 읽어 resume 이유를 판단한다. 깨우는 쪽이 signal 전에 state를 설정하므로 경쟁 조건이 없다.

7.3 Resume dispatch — 여섯 가지 상태

thread_suspend_wakeup_and_unlock_entry가 반환된 후, lock_suspend가 lockwait_state를 읽어 왜 깨어났는지 판단한다:

flowchart LR
  WAKE["thread resume"]
  WAKE --> S1{"lockwait_state?"}
  S1 -- "LOCK_RESUMED" --> R1["lock grant됨\n(해제자가 entry를\nholder list로 이동)"]
  S1 -- "LOCK_RESUMED_ABORTED_FIRST" --> R2["deadlock victim (주)\n트랜잭션 abort,\n다른 thread 완료 대기"]
  S1 -- "LOCK_RESUMED_ABORTED_OTHER" --> R3["deadlock victim (부)\ntimeout으로 취급\n(다른 thread가 abort 처리)"]
  S1 -- "LOCK_RESUMED_DEADLOCK_TIMEOUT" --> R4["deadlock timeout\n(에러 설정, timeout 반환)"]
  S1 -- "LOCK_RESUMED_TIMEOUT" --> R5["일반 timeout\n(wait_msecs 만료)"]
  S1 -- "LOCK_RESUMED_INTERRUPT" --> R6["서버 종료\n(ER_INTERRUPTED)"]

Figure 7-1 — 여섯 가지 resume 상태. LOCK_RESUMED만 lock이 grant되었음을 의미한다. 나머지 상태는 모두 lock_internal_perform_unlock_object를 통한 waiter entry 정리가 필요하다.

상태	설정 주체	의미	반환값
`LOCK_RESUMED`	`lock_grant_blocked_holder` 또는 `lock_grant_blocked_waiter` (Ch. 4 section 4.6-4.7)	lock grant됨 — entry가 이미 holder list에 있음	`LOCK_RESUMED`
`LOCK_RESUMED_ABORTED_FIRST`	`lock_wakeup_deadlock_victim_aborted`	이 thread가 주 deadlock victim — rollback을 수행해야 함	`LOCK_RESUMED_ABORTED`
`LOCK_RESUMED_ABORTED_OTHER`	`lock_wakeup_deadlock_victim_aborted`	같은 트랜잭션의 다른 thread가 이미 abort를 처리 중	`LOCK_RESUMED_DEADLOCK_TIMEOUT`
`LOCK_RESUMED_DEADLOCK_TIMEOUT`	`lock_wakeup_deadlock_victim_timeout`	deadlock victim이 timeout으로 깨워짐 (soft abort)	`LOCK_RESUMED_DEADLOCK_TIMEOUT`
`LOCK_RESUMED_TIMEOUT`	`lock_force_timeout_expired_wait_transactions` (deadlock daemon)	대기 시간이 `lockwait_msecs` 초과	`LOCK_RESUMED_TIMEOUT`
`LOCK_RESUMED_INTERRUPT`	서버 종료	서버가 종료 중 — 모든 waiter가 빠져나가야 함	`LOCK_RESUMED_INTERRUPT`

7.4 suspend된 thread를 깨우는 네 가지 소스

flowchart TB
  subgraph Sources["네 가지 wakeup 소스"]
    S1["1. Lock 해제자\n(lock_grant_blocked_holder\n lock_grant_blocked_waiter)\n-> LOCK_RESUMED"]
    S2["2. Deadlock daemon\n(timeout 체크, 100ms마다)\n-> LOCK_RESUMED_TIMEOUT"]
    S3["3. Deadlock daemon\n(cycle detection)\n-> LOCK_RESUMED_ABORTED_FIRST\n   LOCK_RESUMED_ABORTED_OTHER\n   LOCK_RESUMED_DEADLOCK_TIMEOUT"]
    S4["4. 서버 종료\n(thread 인터럽트)\n-> LOCK_RESUMED_INTERRUPT"]
  end

  S1 --> RESUME["lock_resume(entry, state)"]
  S2 --> RESUME
  S3 --> RESUME
  S4 --> INT["thread wakeup\n(THREAD_RESUME_DUE_TO_INTERRUPT)"]

Figure 7-2 — suspend된 lock 대기 thread를 깨우는 네 가지 소스. 소스 1이 정상 경로다. 소스 2-4는 정리가 필요한 실패 경로다.

7.5 Timeout 체크 — `lock_force_timeout_expired_wait_transactions`

deadlock daemon(Ch. 2 section 2.6)이 100ms 반복마다 각 suspend된 thread에 대해 이를 호출한다:

// lock_force_timeout_expired_wait_transactions — src/transaction/lock_manager.c
static bool
lock_force_timeout_expired_wait_transactions (void *thrd_entry)
{
  thrd = (THREAD_ENTRY *) thrd_entry;
  thread_lock_entry (thrd);

  if (LK_IS_LOCKWAIT_THREAD (thrd))
    {
      /* check for interrupt first */
      if (logtb_is_interrupted_tran (thrd, ...))
        {
          lock_resume ((LK_ENTRY *) thrd->lockwait,
                       LOCK_RESUMED_INTERRUPT);
          return true;
        }

      /* check for timeout */
      if (LK_CAN_TIMEOUT (thrd->lockwait_msecs))
        {
          etime = current_time_ms;
          if (etime - thrd->lockwait_stime > thrd->lockwait_msecs)
            {
              lock_resume ((LK_ENTRY *) thrd->lockwait,
                           LOCK_RESUMED_TIMEOUT);
              return true;
            }
        }

      thread_unlock_entry (thrd);
      return false;    /* not timed out, still waiting */
    }
  // ... thread not waiting ...
}

Timeout 정밀도: daemon이 100ms마다 루프를 돌므로, wait_msecs = 50인 thread가 데드라인 후 최대 100ms 뒤에야 timeout될 수 있다. 이는 의도된 것이다. daemon이 고해상도 타이머를 사용하지 않는다. LK_INFINITE_WAIT(-1) 이면 LK_CAN_TIMEOUT이 false를 반환하여 timeout 경로를 완전히 건너뛴다.

7.6 `tran_next_wait` 체인 — 다중 thread 대기 조율

같은 트랜잭션의 여러 thread가 같은 resource에 lock을 시도할 때, 두 번째 thread는 첫 번째 thread가 이미 대기 중인 것을 발견한다. 두 번째 waiter entry를 만드는 대신, 첫 번째 thread의 tran_next_wait에 자신을 체인한다:

// lock_internal_perform_lock_object — same-tran-already-waiting branch
if (wait_entry_ptr != NULL)   /* another thread of my tran is waiting */
  {
    thrd_entry->tran_next_wait =
      wait_entry_ptr->thrd_entry->tran_next_wait;
    wait_entry_ptr->thrd_entry->tran_next_wait = thrd_entry;

    pthread_mutex_unlock (&res_ptr->res_mutex);
    thread_suspend_wakeup_and_unlock_entry (thrd_entry,
                                             THREAD_LOCK_SUSPENDED);
    goto start;    /* retry after wakeup */
  }

주 waiter가 grant되어 lock_suspend에서 resume될 때, 체인된 모든 thread를 깨운다:

// lock_suspend — after main dispatch, before return
thread_lock_entry (entry_ptr->thrd_entry);
while (entry_ptr->thrd_entry->tran_next_wait)
  {
    p = entry_ptr->thrd_entry->tran_next_wait;
    entry_ptr->thrd_entry->tran_next_wait = p->tran_next_wait;
    p->tran_next_wait = NULL;
    thread_wakeup (p, THREAD_LOCK_RESUMED);
  }
thread_unlock_entry (entry_ptr->thrd_entry);

깨어난 부 thread들은 goto start로 돌아가 전체 lock 획득을 처음부터 재시도한다. 주 thread의 grant를 상속하지 않는다.

7.7 `deadlock_and_timeout_detector` 카운터

// lock_suspend — before and after suspension
lk_Gl.deadlock_and_timeout_detector++;    /* before suspend */
// ... thread sleeps ...
lk_Gl.deadlock_and_timeout_detector--;    /* after resume */

이 atomic 카운터를 deadlock daemon이 체크한다:

// deadlock_detect_task_execute — src/transaction/lock_manager.c
if (lk_Gl.deadlock_and_timeout_detector == 0)
  return;    /* no threads waiting — skip entirely */

카운터가 0이면 lock 대기 중인 thread가 없으므로, timeout시킬 것도 없고 deadlock도 불가능하다. 시스템에 경합이 없을 때 100ms 틱마다 thread map 스캔과 WFG 구축 비용을 회피한다.

7.8 챕터 요약 — 핵심 포인트

lock_suspend는 suspend 전에 thread entry와 WFG node에 5개 필드를 등록한다. page latch 안전 assert가 latch-lock 순서 deadlock을 방지한다.
lock_resume는 signal 전에 lockwait_state를 설정한다 — 프로토콜이 설계상 경쟁 조건이 없다.
여섯 가지 resume 상태가 grant, abort(주/부), deadlock timeout, 일반 timeout, 인터럽트를 구분한다. LOCK_RESUMED만 성공이다.
네 가지 wakeup 소스: lock 해제자(정상 경로), daemon timeout 체크, daemon deadlock detection, 서버 종료.
Timeout 정밀도는 100ms(daemon 루프 주기). lock timeout이 보통 초 단위이므로 허용 가능하다.
다중 thread 대기 조율은 tran_next_wait 체인을 사용한다. 부 thread는 주 waiter에 piggyback하고 wakeup 시 처음부터 재시도한다.
**deadlock_and_timeout_detector**는 daemon의 빠른 조기 종료다 — 0이면 100ms 틱에서 아무 작업도 하지 않는다.

Chapter 8: Deadlock Detection

deadlock daemon(Ch. 2 section 2.6, Ch. 7 section 7.4)이 주기적으로 트랜잭션 waits-for graph(WFG)를 구축하고 cycle을 스캔한다. 이 챕터에서는 전체 detection 파이프라인을 추적한다: WFG 구축, DFS를 통한 cycle detection, victim 선정, 해결.

8.1 전체 파이프라인 — `lock_detect_local_deadlock`

flowchart LR
  P1["Phase 1\nWFG 테이블 초기화\n(node + edge 리셋)"]
  P2["Phase 2\nWFG 구축\n(모든 LK_RES 스캔,\nedge 추가)"]
  P3["Phase 3\nDFS cycle detection\n(TWFG_node 그래프 순회)"]
  P4["Phase 4\nVictim 선정\n(cycle당)"]
  P5["Phase 5\n해결\n(victim 깨우기:\ntimeout 또는 abort)"]

  P1 --> P2 --> P3 --> P4 --> P5

Figure 8-1 — 5단계 deadlock detection 파이프라인. 전체 파이프라인이 DL_detection_mutex 아래에서 실행되어 detection run을 직렬화한다. 각 단계는 lk_Gl의 TWFG_node[] / TWFG_edge[] 배열 위에서 작동한다.

8.2 Phase 1 — WFG 테이블 초기화

// lock_detect_local_deadlock — Phase 1
for (i = 1; i < lk_Gl.num_trans; i++)
  {
    lk_Gl.TWFG_node[i].first_edge = -1;
    lk_Gl.TWFG_node[i].tran_edge_seq_num = 0;
    lk_Gl.TWFG_node[i].checked_by_deadlock_detector = true;
  }

lk_Gl.TWFG_edge = &TWFG_edge_block[0];   /* static block, 200 edges */
lk_Gl.max_TWFG_edge = LK_MIN_TWFG_EDGE_COUNT;  /* 200 */
for (i = 0; i < LK_MIN_TWFG_EDGE_COUNT; i++)
  {
    lk_Gl.TWFG_edge[i].to_tran_index = -1;
    lk_Gl.TWFG_edge[i].next = (i + 1);    /* free-list chain */
  }
lk_Gl.TWFG_edge[max - 1].next = -1;
lk_Gl.TWFG_free_edge_idx = 0;
lk_Gl.global_edge_seq_num = 0;
victim_count = 0;

WFG는 매 detection run마다 처음부터 다시 구축된다 — run 간에 증분 유지보수가 없다. edge 배열은 static 블록(TWFG_edge_block[200])으로 시작하며 필요하면 LK_MID_TWFG_EDGE_COUNT(1000) 또는 LK_MAX_TWFG_EDGE_COUNT(MAX_NTRANS^2)까지 성장할 수 있다.

8.3 Phase 2 — 모든 resource를 스캔하여 WFG 구축

함수가 hash table의 모든 LK_RES를 순회하며 세 범주의 대기 관계에 대해 edge를 추가한다:

// lock_detect_local_deadlock — Phase 2 (annotated)
for (res_ptr = iterator.iterate (); res_ptr != NULL; ...)
  {
    /* (a) among holders: upgrader-to-upgrader conflicts */
    for (hi = res_ptr->holder; hi != NULL; hi = hi->next)
      {
        if (hi->blocked_mode == NULL_LOCK) break;  /* end of upgraders */
        for (hj = hi->next; hj != NULL; hj = hj->next)
          {
            /* hj waits for hi? */
            if (incompat(hj->blocked_mode, hi->granted_mode)
                || incompat(hj->blocked_mode, hi->blocked_mode))
              lock_add_WFG_edge (hj→hi, holder=true);

            /* hi waits for hj? */
            if (incompat(hi->blocked_mode, hj->granted_mode))
              lock_add_WFG_edge (hi→hj, holder=true);
          }
      }

    /* (b) from waiters to holders */
    for (hi = res_ptr->holder; hi != NULL; hi = hi->next)
      for (hj = res_ptr->waiter; hj != NULL; hj = hj->next)
        {
          if (incompat(hj->blocked_mode, hi->granted_mode)
              || incompat(hj->blocked_mode, hi->blocked_mode))
            lock_add_WFG_edge (hj→hi, holder=true);
        }

    /* (c) from waiters to other waiters */
    for (hi = res_ptr->waiter; hi != NULL; hi = hi->next)
      for (hj = hi->next; hj != NULL; hj = hj->next)
        {
          if (incompat(hj->blocked_mode, hi->blocked_mode))
            lock_add_WFG_edge (hj→hi, holder=false);
        }
  }

세 가지 edge 범주:

범주	From	To	edge 의미
(a) Holder<->Holder	upgrader hj	upgrader hi	hj의 upgrade가 hi의 granted 또는 blocked mode에 의해 block됨
(b) Waiter->Holder	waiter hj	holder hi	hj가 hi의 granted 또는 blocked mode 때문에 grant될 수 없음
(c) Waiter->Waiter	waiter hj	waiter hi (큐에서 더 앞)	holder가 해제되더라도, hi의 요청(FIFO에서 더 앞)이 비호환이므로 hj가 grant될 수 없음

각 edge의 holder_flag 파라미터는 대상(to_tran_index)이 holder인지를 기록한다. 이는 victim 선정(section 8.6)에서 waiter보다 holder를 abort하는 것을 선호하는 데 사용된다.

8.4 `lock_add_WFG_edge` — edge 할당과 staleness 감지

// lock_add_WFG_edge — src/transaction/lock_manager.c (annotated)
static int
lock_add_WFG_edge (int from_tran_index, int to_tran_index,
                   int holder_flag, INT64 edge_wait_stime,
                   LK_ENTRY * holder, LK_ENTRY * waiter)
{
  /* skip if either transaction is already a victim */
  if (TWFG_node[from].DL_victim || TWFG_node[to].DL_victim)
    return NO_ERROR;

  /* increment global edge sequence number */
  lk_Gl.global_edge_seq_num++;

  /* handle stale transactions: if a node was not checked by the
     detector yet, it might be a new transaction that reused the
     tran_index — clear its old edges */
  if (TWFG_node[from].checked_by_deadlock_detector == false)
    {
      /* recycle old edges to free list */
      // ... chain old edges back to TWFG_free_edge_idx ...
      TWFG_node[from].first_edge = -1;
      TWFG_node[from].checked_by_deadlock_detector = true;
      TWFG_node[from].tran_edge_seq_num = global_edge_seq_num;
    }
  /* same for to_tran_index ... */

  /* allocate edge from free list (may grow the array) */
  alloc_idx = lk_Gl.TWFG_free_edge_idx;
  lk_Gl.TWFG_free_edge_idx = TWFG_edge[alloc_idx].next;

  /* populate edge */
  TWFG_edge[alloc_idx].to_tran_index = to_tran_index;
  TWFG_edge[alloc_idx].edge_seq_num = global_edge_seq_num;
  TWFG_edge[alloc_idx].holder_flag = holder_flag;
  TWFG_edge[alloc_idx].edge_wait_stime = edge_wait_stime;

  /* prepend to from_tran's edge list */
  TWFG_edge[alloc_idx].next = TWFG_node[from].first_edge;
  TWFG_node[from].first_edge = alloc_idx;
}

Edge 배열 성장(3단계):

단계	크기	저장소
초기	`LK_MIN_TWFG_EDGE_COUNT` = 200	static `TWFG_edge_block[200]`
중간	`LK_MID_TWFG_EDGE_COUNT` = 1000	같은 static 블록 (첫 200 재사용 + 확장)
최대	`LK_MAX_TWFG_EDGE_COUNT` = `MAX_NTRANS^2`	`malloc`된 블록 (static에서 복사)

8.5 Phase 3 — DFS cycle detection

Cycle detection은 WFG node/edge 구조 위의 표준 DFS다. ancestor 필드가 DFS 경로를 체인하며, follow-edge가 이미 현재 경로에 있는 node (ancestor != -1)로 이어질 때 cycle이 감지된다:

// lock_detect_local_deadlock — Phase 3 (annotated)
for (k = 1; k < lk_Gl.num_trans; k++)
  {
    TWFG_node[k].current = TWFG_node[k].first_edge;
    TWFG_node[k].ancestor = -1;
  }

for (k = 1; k < lk_Gl.num_trans; k++)
  {
    if (TWFG_node[k].current == -1)
      continue;            /* no outgoing edges — skip */

    s = k;
    TWFG_node[s].ancestor = -2;   /* sentinel: DFS root */

    for (; s != -2; )
      {
        /* skip stale nodes/edges */
        // ... validation checks ...

        if (TWFG_node[s].current == -1)
          {
            /* backtrack: no more edges from s */
            t = TWFG_node[s].ancestor;
            TWFG_node[s].ancestor = -1;
            s = t;
            // advance parent's edge pointer
            continue;
          }

        t = TWFG_edge[TWFG_node[s].current].to_tran_index;

        /* skip stale edges */
        // ... validation checks ...

        if (TWFG_node[t].ancestor != -1)
          {
            /* CYCLE FOUND: s → t, and t is already on the path */
            lock_select_deadlock_victim (thread_p, s, t);
          }
        else
          {
            /* no cycle yet: advance DFS into t */
            TWFG_node[t].ancestor = s;
            s = t;
          }
      }
  }

DFS 중 staleness 체크는 Phase 2 이후 무효화된 edge를 걸러낸다. WFG 구축과 DFS 순회 사이에 트랜잭션이 commit되거나 abort될 수 있다. 세 조건이 node를 무효화한다: checked_by_deadlock_detector == false (새 트랜잭션이 index를 재사용), thrd_wait_stime == 0(더 이상 대기 않음), 또는 edge_seq_num < tran_edge_seq_num(이 tran_index의 이전 incarnation에서 온 edge).

8.6 Phase 4 — victim 선정 전략

Cycle이 발견되면 lock_select_deadlock_victim이 s(back-edge를 발견한 node)와 t(이미 DFS 경로에 있는 node — cycle 시작)로 호출된다:

Cycle: t → ... → s → t

함수는 먼저 cycle을 검증하고(stale edge에 대한 false-cycle 체크), 그런 다음 우선순위 기반 전략으로 victim을 선정한다:

Victim Selection Strategy (from source comments):
  1) Must be a lock holder (holder_flag == true).
  2) Must be an active transaction.
  3) Prefer a transaction that does NOT have deadlock priority.
  4) Prefer a transaction that has written fewer log records.
  5) Prefer a transaction with a closer timeout.
  6) Prefer the youngest transaction (highest tranid).

각 기준이 존재하는 이유:

Holder — holder의 rollback만이 cycle이 기다리는 자원을 푼다. 순수 waiter를 abort하면 edge 하나가 사라질 뿐 아무것도 해제되지 않아 cycle이 그대로 남는다.
Active — 이미 commit / abort 중인 트랜잭션은 어차피 종료 절차에 있고 다시 abort할 수 없다. 골라봐야 해결되는 것이 없다.
Deadlock priority 없음 — priority 플래그는 명시적 보호 장치다. 보호된 트랜잭션은 살아남는다.
로그 레코드 적음 — 가장 싼 rollback.
유한 timeout — 그 응용은 이미 재시도형 실패를 예상하고 있으므로, retryable wake가 가장 덜 놀랍다.
막내 — 버려지는 작업이 가장 적고, 연장자가 항상 동률에서 살아남으므로 오래 달린 트랜잭션이 반복해서 희생되는 기아가 없다 — 시스템 전체로는 항상 전진한다.

TWFG_node의 candidate 필드가 cycle 멤버 중 어떤 것이 적격한 victim인지(최소 하나의 edge에서 holder 쪽에 있는지)를 표시한다. 함수가 ancestor 링크를 통해 cycle을 순회하며, 여섯 기준을 순서대로 적용하여 각 후보를 현재 최선의 victim과 비교한다.

// lock_select_deadlock_victim — src/transaction/lock_manager.c (annotated)
static void
lock_select_deadlock_victim (THREAD_ENTRY * thread_p, int s, int t)
{
  /* Phase A: validate cycle — check for stale edges */
  // walk cycle t → ... → s → t, mark false_dd_cycle if any
  // node/edge is stale; if false cycle, clear ancestors and return

  if (false_dd_cycle == true)
    { /* clear ancestor chain and return */ return; }

  /* Phase B: initialize victim from the edge s→t */
  if (TWFG_edge[TWFG_node[s].current].holder_flag)
    {
      /* t is a holder — candidate for victim */
      if (logtb_is_active (thread_p, logtb_find_tranid (t)))
        {
          victims[victim_count].tran_index = t;
          victims[victim_count].can_timeout =
            LK_CAN_TIMEOUT (logtb_find_wait_msecs (t));
        }
    }

  /* Phase C: walk cycle s → ancestor → ... → t, compare candidates */
  for (v = s; v != t; v = TWFG_node[v].ancestor)
    {
      if (TWFG_node[v].candidate == false)
        continue;    /* not a holder in this cycle — skip */

      tranid = logtb_find_tranid (v);
      if (!logtb_is_active (thread_p, tranid))
        continue;    /* criterion 2: must be active */

      victim_tran_index = victims[victim_count].tran_index;

      if (victim_tran_index == NULL_TRAN_INDEX)
        {
          victim_tranid = tranid;   /* first eligible candidate */
        }
      /* criterion 3: prefer no deadlock priority */
      else if (logtb_has_deadlock_priority (victim_tran_index)
               != logtb_has_deadlock_priority (v))
        {
          if (logtb_has_deadlock_priority (v) == false)
            victim_tranid = tranid;
        }
      else
        {
          tran_log_count = logtb_find_log_records_count (v);
          victim_tran_log_count =
            logtb_find_log_records_count (victim_tran_index);

          /* criterion 4: prefer fewer log records */
          if (tran_log_count < victim_tran_log_count)
            victim_tranid = tranid;
          else if (tran_log_count == victim_tran_log_count)
            {
              /* criterion 5: prefer closer timeout */
              /* criterion 6: prefer youngest (highest tranid) */
              if ((victims[victim_count].can_timeout == false
                   && can_timeout == true)
                  || (same_timeout_policy
                      && LK_ISYOUNGER (tranid, current_victim)))
                victim_tranid = tranid;
            }
        }

      if (victim_tranid != NULL_TRANID)
        {
          victims[victim_count].tran_index = v;
          victims[victim_count].tranid = victim_tranid;
          victims[victim_count].can_timeout = can_timeout;
        }
    }

  /* Phase D: record victim for event log and increment victim_count */
  if (victims[victim_count].tran_index != NULL_TRAN_INDEX)
    {
      /* collect LK_ENTRY pointers along the cycle for event log */
      // ... walk cycle again, store holder/waiter entries ...
      victim_count++;
    }
}

여섯 기준의 순서 적용 (각각이 이전의 tie-breaker):

flowchart TD
  C1{"1. 이 cycle에서\nlock holder인가?"}
  C1 -- "no" --> SKIP["건너뜀"]
  C1 -- "yes" --> C2{"2. 트랜잭션이\n활성인가?"}
  C2 -- "no" --> SKIP
  C2 -- "yes" --> C3{"3. deadlock\npriority가 있는가?"}
  C3 -- "yes (보호됨)" --> KEEP["현재 victim 유지"]
  C3 -- "no (비보호)" --> PREFER["이것을 선호"]
  C3 -- "같음" --> C4{"4. 작성한 log\nrecord가 더 적은가?"}
  C4 -- "yes (작업 적음)" --> PREFER
  C4 -- "같은 수" --> C5{"5. 유한\ntimeout이 있는가?"}
  C5 -- "yes (재시도 가능)" --> PREFER
  C5 -- "같음" --> C6{"6. 더 젊은가\n(높은 tranid)?"}
  C6 -- "yes" --> PREFER
  C6 -- "no" --> KEEP

Figure 8-2 — victim 선정 기준의 결정 트리. 각 기준은 이전의 tie-breaker다. 전체 선호도: 비보호, 적은 작업, 재시도 가능, 가장 젊은 것.

해결 mode:

can_timeout = true (victim의 wait_msecs가 유한): LOCK_RESUMED_DEADLOCK_TIMEOUT으로 깨움 — soft timeout으로 취급, 애플리케이션이 재시도 가능.
can_timeout = false (LK_INFINITE_WAIT): LOCK_RESUMED_ABORTED_FIRST / _OTHER로 깨움 — 트랜잭션을 rollback 해야 함.

8.7 Phase 5 — 해결 (victim 깨우기)

// lock_detect_local_deadlock — Phase 5
for (k = 0; k < victim_count; k++)
  {
    if (victims[k].can_timeout)
      lock_wakeup_deadlock_victim_timeout (victims[k].tran_index);
    else
      lock_wakeup_deadlock_victim_aborted (victims[k].tran_index);
  }

이 함수들(Ch. 7 section 7.3-7.4에서 상세)은 victim의 suspend된 thread를 찾아 적절한 상태로 lock_resume을 호출한다. resume된 thread는 lock_internal_perform_unlock_object(Ch. 5 section 5.7 CASE W)를 통해 waiter entry를 정리한다.

안전망 — no_victim_case_count 에스컬레이션:

60번 연속 deadlock detection run에서 victim을 찾지 못했는데 thread가 여전히 suspend되어 있으면, 시스템은 livelock이나 감지 불가능한 deadlock을 의심한다. 최후 수단으로 thread 하나를 강제 timeout시킨다:

if (victim_count == 0)
  {
    if (lk_Gl.no_victim_case_count >= 60)
      {
        if (css_are_all_request_handlers_suspended ())
          thread_get_manager ()->map_entries (
            lock_victimize_first_thread_mapfunc);
        lk_Gl.no_victim_case_count = 0;
      }
    else
      lk_Gl.no_victim_case_count += 1;
  }

daemon 틱당 100ms이므로, 60번 run은 진행이 없는 약 6초 후에 안전망이 발동한다.

8.8 WFG 자료구조 — Ch. 1 요약 참조

참고로 WFG 구조체(lock_manager.c에 정의):

struct lk_WFG_node
{
  int first_edge;         /* head of outgoing edge list (-1 = none) */
  bool candidate;         /* eligible as victim in current cycle */
  int current;            /* DFS cursor into edge list */
  int ancestor;           /* DFS parent (-1 = not on path, -2 = root) */
  INT64 thrd_wait_stime;  /* wait start time (0 = not waiting) */
  int tran_edge_seq_num;  /* staleness marker */
  bool checked_by_deadlock_detector;  /* false = new tran, clear old edges */
  bool DL_victim;         /* already selected as victim */
};

struct lk_WFG_edge
{
  int to_tran_index;      /* target transaction (-2 = stale edge) */
  int edge_seq_num;       /* creation sequence number */
  int holder_flag;        /* true if target is a holder */
  int next;               /* next edge in same node's list */
  INT64 edge_wait_stime;  /* waiter's wait start time */
  LK_ENTRY *holder;       /* LK_ENTRY of the blocking holder */
  LK_ENTRY *waiter;       /* LK_ENTRY of the blocked waiter */
};

8.9 구체적 시나리오 — 세 트랜잭션 deadlock

flowchart LR
  subgraph Build["Phase 2: WFG 구축"]
    direction LR
    T1["T1: R1에 X hold\nR2에 S 대기"]
    T2["T2: R2에 S hold\nR3에 X 대기"]
    T3["T3: R3에 X hold\nR1에 S 대기"]
    T1 -- "edge: T1이 T2를 대기\n(R2에서 waiter->holder)" --> T2
    T2 -- "edge: T2가 T3를 대기\n(R3에서 waiter->holder)" --> T3
    T3 -- "edge: T3가 T1을 대기\n(R1에서 waiter->holder)" --> T1
  end

  subgraph DFS["Phase 3: T1에서 DFS"]
    D1["T1 방문 (ancestor=-2)"]
    D2["T2 방문 (ancestor=T1)"]
    D3["T3 방문 (ancestor=T2)"]
    D4["T3->T1 edge:\nT1.ancestor != -1\n-> CYCLE 발견"]
    D1 --> D2 --> D3 --> D4
  end

  subgraph Victim["Phase 4: victim 선정"]
    V1["Cycle: T1 -> T2 -> T3 -> T1\n모두 holder\n모두 활성\n가장 젊은 것(최고 tranid) 선택\n-> T3가 victim"]
  end

  subgraph Resolve["Phase 5: 해결"]
    R1["T3.can_timeout?\nyes -> DEADLOCK_TIMEOUT\nno -> ABORTED_FIRST"]
  end

  Build --> DFS --> Victim --> Resolve

Figure 8-3 — 세 트랜잭션 deadlock detection 전체 과정. Phase 2에서 cycle을 형성하는 세 edge를 추가. Phase 3 DFS가 T3의 edge가 T1로 돌아갈 때 cycle 발견. Phase 4에서 T3(기본 victim 전략에 의해 가장 젊은 것) 선정. Phase 5에서 T3를 timeout 또는 abort로 깨움.

8.10 성능 분석 — 매번 전체 재구축이 허용 가능한가?

WFG는 매 detection run마다 처음부터 재구축된다. 이 섹션에서는 실제 비용과 설계 근거를 분석한다.

불필요한 작업을 방지하는 세 gate:

flowchart LR
  TICK["daemon 틱\n(100ms마다)"]
  G1{"deadlock_and_timeout\n_detector == 0?"}
  G1 -- "yes (waiter 없음)" --> SKIP1["완전히 건너뜀\n(atomic read만)"]
  G1 -- "no" --> TIMEOUT["timeout 체크\n(thread map 순회)"]
  TIMEOUT --> G2{"lock_wait_count >= 2?"}
  G2 -- "no (0 또는 1 waiter)" --> SKIP2["WFG 건너뜀\n(deadlock 불가능)"]
  G2 -- "yes" --> G3{"interval 경과?\n(기본 1.0초)"}
  G3 -- "no" --> SKIP3["WFG 건너뜀\n(너무 이름)"]
  G3 -- "yes" --> FULL["전체 WFG 스캔\nlock_detect_local_deadlock"]

Figure 8-4 — WFG 전체 스캔 전의 세 gate. 비경합 워크로드에서 Gate 1이 모든 것을 잡는다 — 비용은 100ms당 atomic read 하나. 경합이 적으면 Gate 2가 단일 waiter 경우를 잡는다. Gate 3은 전체 스캔이 최대 초당 한 번만 실행되도록 보장한다.

전체 스캔이 실행될 때의 비용 분석:

단계	시간 복잡도	실제 비용	병목?
Node 초기화	O(MAX_NTRANS)	수십 us	No
Edge 초기화	O(200) static 블록	무시 가능	No
Hash table 스캔	O(모든 활성 LK_RES)	지배적 비용. 각 resource: `res_mutex` 획득, holder/waiter 스캔, 해제.	Yes
Resource당 edge 구축	O(holders^2 + holders x waiters + waiters^2)	대부분의 resource는 holder 1-2개, waiter 0개 -> resource당 O(1)	드뭄
DFS cycle detection	O(nodes + edges)	nodes <= MAX_NTRANS, edges = 실제 대기 관계	No

Hash table 스캔이 병목이다. 시스템에 100K개의 활성 lock resource가 있으면 스캔이 100K번의 res_mutex lock/unlock을 수행한다. 그러나:

대부분의 resource에는 waiter가 없다 — 스캔이 res_ptr->holder와 res_ptr->waiter를 확인하고, edge를 0개 추가하고, 넘어간다. resource당 비용은 mutex 획득 1회 + 포인터 읽기 수 회 + mutex 해제 1회.
res_mutex는 resource별이다 — resource R1을 스캔하는 동안 다른 thread가 resource R2를 자유롭게 lock/unlock할 수 있다. 스캔이 전체 lock manager를 직렬화하지 않는다.
스캔은 최대 초당 한 번 실행된다(기본 PRM_ID_LK_RUN_DEADLOCK_INTERVAL = 1.0).

설계 트레이드오프 — 전체 재구축 vs. 증분 유지보수:

접근	핫 패스 오버헤드 (lock 획득/해제)	Detection 비용	복잡도
전체 재구축 (CUBRID)	제로 — 획득/해제 시 WFG 기록 관리 없음	O(resources) per scan, 최대 1/초	단순
증분 WFG	모든 block 시 edge 추가, 모든 grant/해제 시 edge 제거	O(DFS만) per scan	높음 — 동시 lock 상태 변경 아래 edge 일관성 유지 필요

CUBRID는 핫 패스 오버헤드 제로를 선택했다. lock 획득이 초당 수만 번 발생하는 OLTP 워크로드에서, 모든 획득에 WFG edge 유지보수를 추가하는 것은 초당 한 번의 전체 스캔보다 총합 비용이 크다. 전체 재구축 접근은 동시 lock 상태 변경 아래에서 그래프 일관성을 유지하는 복잡성도 피한다.

비용이 문제가 될 수 있는 경우:

수만 개의 활성 lock resource 그리고 지속적인 다중 thread 경합(resource당 많은 waiter).
이 시나리오에서 hash table 스캔이 수십 ms 걸릴 수 있다. 완화 방법:
- PRM_ID_LK_RUN_DEADLOCK_INTERVAL 증가 (스캔 빈도 감소 — detection 지연과 낮은 오버헤드 간 트레이드오프).
- PRM_ID_LK_ESCALATION_AT 낮추기 (빨리 escalation — 전체 lock resource 수 감소).
- timeout 기반 fallback(각 lock 요청의 wait_msecs)이 WFG 스캔이 지연되더라도 deadlock을 해결한다.

8.11 챕터 요약 — 핵심 포인트

WFG는 매 detection run마다 처음부터 재구축된다 — 증분 유지보수 없음. 이는 정확성을 단순화하는 대신 O(resources x holders^2) 구축 시간이 든다.
세 범주의 edge가 모든 대기 관계를 포착한다: holder<->holder(upgrader 충돌), waiter->holder, waiter->waiter.
DFS cycle detection이 ancestor 체인을 사용한다. DFS 중 staleness 체크가 동시 commit에 의해 무효화된 edge를 걸러낸다.
Victim 선정은 6개 기준의 우선순위를 사용한다: holder여야 함, 활성이어야 함, deadlock priority 없음, 적은 log record, 가까운 timeout, 가장 젊은 트랜잭션.
두 가지 해결 mode: can_timeout -> soft timeout(재시도 가능), !can_timeout -> abort(rollback 필수).
Edge 배열은 3단계로 성장한다: 200(static) -> 1000(static 확장) -> MAX_NTRANS^2(malloc). static 초기 블록이 저경합 워크로드에서 할당을 피한다.
안전망: victim 없는 60번 연속 run(약 6초)이 thread 하나의 강제 timeout을 trigger하여 서버 hang을 방지한다.

Chapter 9: 특수 경로들

주요 lock 생애주기(획득 -> 변환 -> 해제)는 Chapter 3-5에서 다루었다. 이 챕터에서는 주요 흐름에 맞지 않는 특수 목적 API를 다룬다: instant lock probe, composite lock, lock_scan / lock_classes_lock_hint, lock demotion, lock_subclass.

9.1 `lock_hold_object_instant` — 비블로킹 probe

절대 block하지 않고 LK_ENTRY를 생성하지 않는 경량 lock 체크다. lock이 지금 당장 grant 될 수 있는지를 실제로 획득하지 않고 테스트한다.

// lock_internal_hold_lock_object_instant — src/transaction/lock_manager.c
static int
lock_internal_hold_lock_object_instant (THREAD_ENTRY * thread_p,
    int tran_index, const OID * oid,
    const OID * class_oid, LOCK lock)
{
  /* shortcut: class lock subsumes the request? */
  if (class_oid != NULL && !OID_IS_ROOTOID (class_oid))
    if (lock_is_class_lock_escalated (..., lock))
      return LK_GRANTED;

  /* find (not find_or_insert!) the resource */
  res_ptr = lk_Gl.m_obj_hash_table.find (thread_p, search_key);
  if (res_ptr == NULL)
    return LK_GRANTED;    /* no resource → no contention */

  /* am I already a holder? */
  for (entry_ptr = res_ptr->holder; ...; entry_ptr = entry_ptr->next)
    if (entry_ptr->tran_index == tran_index) break;

  if (entry_ptr == NULL)
    {
      /* not a holder: check compat with holders AND waiters */
      compat1 = lock_compat (lock, res_ptr->total_waiters_mode);
      compat2 = lock_compat (lock, res_ptr->total_holders_mode);
      pthread_mutex_unlock (&res_ptr->res_mutex);
      return (compat1 == YES && compat2 == YES)
             ? LK_GRANTED : LK_NOTGRANTED;
    }
  else
    {
      /* already a holder: check conversion compat */
      new_mode = lock_conv (lock, entry_ptr->granted_mode);
      if (new_mode == entry_ptr->granted_mode)
        { /* re-entrance */ return LK_GRANTED; }
      /* check against other holders */
      // ... same group_mode logic as PATH F (Ch. 3 §3.9) ...
      return compat ? LK_GRANTED : LK_NOTGRANTED;
    }
}

lock_object와의 핵심 차이:

관점	`lock_hold_object_instant`	`lock_object`
`LK_ENTRY` 생성	No	Yes
충돌 시 block	No (`LK_NOTGRANTED` 반환)	Yes (thread suspend)
holder/waiter list 변경	No	Yes
hash 연산	`find` (읽기 전용)	`find_or_insert` (`LK_RES` 생성 가능)
용도	full lock 전의 낙관적 probe	실제 lock 획득

호출자: scan_manager.c가 heap/index scan 중 낙관적 첫 시도로 사용한다. probe가 LK_GRANTED를 반환하면 lock이 성공할 것임을 알고 scan을 진행할 수 있으며, 종종 lock entry를 전혀 생성하지 않아도 된다. LK_NOTGRANTED면 full lock_object 경로로 fallback한다.

9.2 Composite lock — 일괄 다중 객체 locking

Composite lock은 bulk DELETE/UPDATE를 위한 지연된 locking 전략이다. scan 단계에서 각 행에 X lock을 거는 대신(다른 트랜잭션과 deadlock 가능성), OID를 먼저 수집하고 마지막에 모든 lock을 한꺼번에 획득한다.

생애주기:

flowchart LR
  INIT["lock_initialize_composite_lock\n(tran_index, wait_msecs 설정)"]
  ADD["lock_add_composite_lock\n(OID + class_oid 수집)\n행마다 반복"]
  FIN["lock_finalize_composite_lock\n(모든 X lock 획득)\n수가 threshold 이상이면 escalation"]
  ABORT["lock_abort_composite_lock\n(수집된 OID 해제)"]

  INIT --> ADD --> FIN
  ADD -- "에러" --> ABORT
  FIN -- "에러" --> ABORT

Figure 9-1 — Composite lock 생애주기. scan 중 OID를 수집하고, finalization 시 일괄로 lock을 획득한다.

**lock_add_composite_lock**은 class별로 그룹화하여 instance OID를 수집한다:

// lock_add_composite_lock — src/transaction/lock_manager.c (simplified)
int lock_add_composite_lock (... LK_COMPOSITE_LOCK * comp_lock,
                             const OID * oid, const OID * class_oid)
{
  /* find or create per-class bucket */
  for (lockcomp_class = lockcomp->class_list; ...; )
    if (OID_EQ (class_oid, &lockcomp_class->class_oid)) break;

  if (lockcomp_class == NULL)
    {
      /* new class: acquire IX on class immediately */
      lock_internal_perform_lock_object (..., class_oid, IX_LOCK, ...);
      /* allocate OID buffer (up to escalation threshold) */
    }

  /* if class lock already >= X: skip instance OID collection */
  if (lockcomp_class->class_lock_ptr->granted_mode >= X_LOCK)
    return;    /* class lock subsumes everything */

  /* collect the instance OID */
  lockcomp_class->inst_oid_space[num_inst_oids++] = *oid;
  /* if count reaches escalation threshold: stop collecting */
}

**lock_finalize_composite_lock**이 실제 lock을 획득한다:

// lock_finalize_composite_lock — src/transaction/lock_manager.c (simplified)
int lock_finalize_composite_lock (... LK_COMPOSITE_LOCK * comp_lock)
{
  for (each lockcomp_class in class_list)
    {
      if (class already >= X_LOCK
          || num_inst_oids == escalation_threshold)
        {
          /* escalation: X lock on the class */
          lock_internal_perform_lock_object (..., class_oid, X_LOCK, ...);
        }
      else
        {
          /* individual: X lock on each collected instance */
          for (i = 0; i < num_inst_oids; i++)
            lock_internal_perform_lock_object (..., inst_oid[i], X_LOCK, ...);
        }
    }
  lock_abort_composite_lock (comp_lock);  /* free memory */
}

호출자: query_executor.c가 DELETE/UPDATE 쿼리에 composite lock을 사용한다. XASL plan이 LK_COMPOSITE_LOCK 필드를 갖고 있으며, executor가 scan 단계에서 대상 OID를 수집하고 수정 적용 전에 lock_finalize_composite_lock을 호출한다.

Escalation과의 통합: composite lock은 자체 escalation 로직이 있다. class에 대해 수집된 OID 수가 PRM_ID_LK_ESCALATION_AT에 도달하면 OID 수집을 중단하고 finalization 시 class에 X를 획득한다. 이는 표준 escalation(Ch. 6)의 동작을 미러링하되 2단계 접근을 취한다.

9.3 `lock_scan`과 `lock_classes_lock_hint` — class 수준 API

이 두 API는 class 수준에서만 작동하며, instance locking은 없다.

lock_scan(Ch. 3 section 3.1에서 간략히 다룸)은 heap scan을 위한 단일 class lock을 획득한다:

// lock_scan — src/transaction/lock_manager.c
int lock_scan (THREAD_ENTRY * thread_p, const OID * class_oid,
               int cond_flag, LOCK class_lock)
{
  root_class_entry = lock_get_class_lock (thread_p, oid_Root_class_oid);
  return lock_internal_perform_lock_object (
    thread_p, tran_index, class_oid, NULL,
    class_lock, wait_msecs,
    &class_entry, root_class_entry);
}

호출자: heap_file.c가 heap scan 시작 시 lock_scan(class_oid, IS_LOCK)을 호출한다.

**lock_classes_lock_hint**는 미리 구축된 LC_LOCKHINT 배열을 사용하여 여러 class에 한꺼번에 lock을 건다:

// lock_classes_lock_hint — src/transaction/lock_manager.c (simplified)
int lock_classes_lock_hint (THREAD_ENTRY * thread_p,
                            LC_LOCKHINT * lockhint)
{
  /* sort classes for consistent ordering (avoid class-level deadlocks) */
  // ... sort lockhint->classes by OID ...

  for (i = 0; i < lockhint->num_classes; i++)
    {
      lock_internal_perform_lock_object (
        thread_p, tran_index,
        &lockhint->classes[i].oid, NULL,
        lockhint->classes[i].lock, wait_msecs,
        &entry, root_class_entry);
    }
}

호출자: locator_sr.c(xlocator_fetch_lockhint_classes)가 클라이언트가 여러 class를 prefetch할 때 일괄 class locking에 사용한다. 정렬 단계가 중요하다. 일관된 순서로 class lock을 획득하면 같은 class 집합이 필요한 트랜잭션 간의 deadlock을 방지한다.

9.4 Lock demotion — `lock_demote_class_lock`

Demotion은 변환의 역이다: hold 중인 lock을 더 약한 mode로 다운그레이드. 좁은 상황에서만 사용된다.

// lock_demote_class_lock — src/transaction/lock_manager.c (simplified)
int lock_demote_class_lock (THREAD_ENTRY * thread_p,
                            const OID * oid, LOCK lock, LOCK * ex_lock)
{
  entry_ptr = lock_find_tran_hold_entry (thread_p, tran_index, oid, true);
  return lock_internal_demote_class_lock (thread_p, entry_ptr,
                                          lock, ex_lock);
}

lock_internal_demote_class_lock은 granted_mode를 더 약한 mode로 변경하고, total_holders_mode를 재계산하고, lock_grant_blocked_holder / lock_grant_blocked_waiter를 호출하여 demotion이 waiter를 unblock하는지 확인한다.

호출자:

lock_demote_read_class_lock_for_checksumdb — checksumdb 중 경합을 줄이기 위해 class lock을 S->IS로 demote한다. 명시적으로 “checksumdb 전용”으로 문서화됨.
lock_demote_all_shared_class_locks — 특정 트랜잭션 상태 전환 시 모든 S class lock을 IS로 demote하는 내부 함수.

소스의 경고: “트랜잭션 중간에 write lock을 demote하면 recovery 문제가 발생할 수 있다. 특정한 경우에만 주의하여 사용해야 한다.” instance lock의 demotion은 의도적으로 지원하지 않는다.

9.5 `lock_subclass` — class 계층 locking

CUBRID의 class 상속 계층에서 subclass를 locking하려면 superclass에 intention lock이 필요하다:

// lock_subclass — src/transaction/lock_manager.c (simplified)
int lock_subclass (THREAD_ENTRY * thread_p,
                   const OID * subclass_oid,
                   const OID * superclass_oid,
                   LOCK lock, int cond_flag)
{
  /* determine intention lock for superclass */
  if (lock <= S_LOCK)
    new_superclass_lock = IS_LOCK;
  else
    new_superclass_lock = IX_LOCK;

  /* acquire intention lock on superclass if needed */
  if (old_superclass_lock < new_superclass_lock)
    lock_internal_perform_lock_object (..., superclass_oid, NULL,
                                       new_superclass_lock, ...);

  /* acquire the actual lock on the subclass */
  lock_internal_perform_lock_object (..., subclass_oid, NULL,
                                     lock, ..., &subclass_entry,
                                     superclass_entry);
}

이는 lock_object의 instance-on-class locking과 같은 다중 세분화 패턴을 따르되, 계층에서 한 단계 위에서 작동한다: instance-on-class 대신 subclass-on-superclass. class_entry 역참조 체인이 escalation이 계층을 통해 전파되도록 한다.

9.6 `lock_rep_read_tran` — REPEATABLE READ 헬퍼

REPEATABLE READ isolation에서 ALTER TABLE ADD COLUMN NOT NULL을 위한 특수 진입점:

int lock_rep_read_tran (THREAD_ENTRY * thread_p, LOCK lock,
                        int cond_flag);

이 함수는 root class OID에 lock을 걸어 동시 DDL을 방지한다. 좁은 특수 경우이며 새로운 locking 메커니즘을 도입하지 않는다. root OID에 대해 lock_internal_perform_lock_object를 호출할 뿐이다.

9.7 특수 경로 API 호출자 지도

이 API들은 주요 lock_object/lock_unlock_object보다 좁은 호출자 기반을 갖는다(주요 호출자 지도는 Ch. 3 section 3.2).

API	호출자	맥락
`lock_hold_object_instant`	`scan_manager.c` (heap scan, index scan)	full `lock_object` 전의 낙관적 비블로킹 probe. 두 호출 지점: heap OID용 `scan_next_heap_scan`, index OID용 `scan_next_index_scan`.
`lock_initialize/add/finalize_composite_lock`	`query_executor.c`	bulk DELETE/UPDATE. 쿼리 시작 시 `lock_initialize`, scan 중 후보 행마다 `lock_add`, 수정 적용 전 `lock_finalize`.
`lock_scan`	`heap_file.c`	단일 호출 지점: `heap_scancache_start`가 heap scan 전에 class에 IS_LOCK 획득.
`lock_classes_lock_hint`	`locator_sr.c` (`xlocator_fetch_lockhint_classes`)	클라이언트가 여러 class를 prefetch할 때 일괄 class locking. 완료 시 `lock_unlock_classes_lock_hint`와 쌍.
`lock_subclass`	`locator_sr.c` (파티션 테이블의 INSERT/UPDATE), `query_executor.c` (파티션 scan)	superclass에 intention lock과 함께 subclass에 IX/IS 획득. class 계층 / 파티션 작업 시 사용.
`lock_demote_class_lock`	`locator_sr.c` (`xlocator_demote_class_lock`), `btree_load.c` (index load)	bulk 연산 후 class lock demote. 범용이지만 제한적.
`lock_demote_read_class_lock_for_checksumdb`	`locator_sr.c` (`xlocator_check_fk_validity`)	checksumdb 시에만 S->IS demotion. 소스에 명시적으로 “이 함수를 다른 client/thread에 절대 사용하지 마라”고 기재.
`lock_rep_read_tran`	`transaction_sr.c` (`xtran_lock_rep_read`)	RR에서 ALTER TABLE ADD COLUMN NOT NULL을 위한 root class lock. 단일 호출 지점.

9.8 챕터 요약 — 핵심 포인트

**lock_hold_object_instant**는 읽기 전용, 비블로킹 probe다: find (not find_or_insert) 사용, LK_ENTRY 생성 안 함, 절대 block 안 함. scan_manager가 낙관적 locking에 사용.
Composite lock은 X lock 획득을 일괄 finalization 단계로 지연한다. 자체 escalation 로직 통합(수가 threshold에 도달하면 class X). query_executor가 bulk DELETE/UPDATE에 사용.
**lock_scan**은 class 수준 IS/IX lock의 얇은 래퍼다. **lock_classes_lock_hint**는 class 수준 deadlock을 방지하기 위해 locking 전에 class를 정렬한다.
Lock demotion은 의도적으로 class lock에만, 특정 호출자에만 제한된다(checksumdb). 소스가 트랜잭션 중간에 write lock을 demote하는 것에 대해 명시적으로 경고한다.
**lock_subclass**는 다중 세분화 locking을 class 상속 계층으로 확장한다: subclass-on-superclass가 instance-on-class를 미러링한다.

Chapter 10: Serializable conflict handling (first-updater-wins)

lock manager 가 lock 없이 강제하는 유일한 isolation 규칙을 다룬다 — REPEATABLE READ / SERIALIZABLE 에서 write 경로가 내는 ER_MVCC_SERIALIZABLE_CONFLICT 다. §5.3 (lock_unlock_object — isolation 정책 gate) 의 write 측 짝이다. §5.3 은 RR 에서 트랜잭션이 어떤 lock 을 종료까지 보유 하는지를 정하고, 이 규칙은 다른 트랜잭션이 내 스냅샷 아래에서 바꿔버린 행을 내가 수정 하지 못하게 막는다. 감지 기판은 MVCC 가시성(cubrid-mvcc-detail.md)이 제공하고, 직렬화 결정은 여기 산다. (MVCC detail 문서가 이 챕터로 위임하는 이유가 바로 이것이다 — 가시성만으로는 두 writer 를 직렬화할 수 없다.)

10.1 이 에러의 정체

ER_MVCC_SERIALIZABLE_CONFLICT (-1158, base/error_code.h) 는 CUBRID 의 first-updater-wins write-conflict 에러다 — PostgreSQL 의 “could not serialize access due to concurrent update” (SQLSTATE 40001) 에 대응한다. RR/SERIALIZABLE 에서 트랜잭션은 최신 버전이 자기 스냅샷이 보는 버전과 다른 행을 UPDATE/DELETE 할 수 없다. 내 스냅샷 시점 이후 에 동시 트랜잭션이 새 버전을 만들었거나 행을 삭제했으면, 수정은 -1158 로 거부되고 구문이 abort 된다.

별도의 SERIALIZABLE 메커니즘은 없다. TRAN_SERIALIZABLE 단독 분기가 트리 전체에 0개라, 런타임상 RR ≡ SERIALIZABLE 이고 둘 다 isolation > TRAN_READ_COMMITTED 로 동일하게 게이팅된다. 소스는 이 하나의 first-updater-wins 검사 + RR 의 strict-2PL lock 보유(§5.3)로 직렬성을 강제하며, key-range lock 을 추가하지 않는다.

10.2 발생 지점 — `locator_lock_and_get_object_internal`

이 검사는 lock_manager.c 에 없다. UPDATE/DELETE 가 행을 수정용으로 고정할 때 쓰는 locator 의 lock-and-fetch 경로, locator_lock_and_get_object_internal (src/transaction/locator_sr.c) 에 있고, locator_lock_and_get_object_with_evaluation 이 lock_mode = X_LOCK 으로 호출한다. X-lock 을 먼저 잡고, 그 뒤에야 버전을 fetch 해 검사한다:

// locator_lock_and_get_object_internal — src/transaction/locator_sr.c (annotated)
//   1) row OID X-lock 획득: 조건부, 실패 시 무조건(blocking)
if (lock_object (.., oid, class_oid, lock_mode, LK_COND_LOCK) != LK_GRANTED)
  {
    ... pgbuf_ordered_unfix (..);   // page watcher 해제
    if (lock_object (.., oid, class_oid, lock_mode, LK_UNCOND_LOCK) != LK_GRANTED)  // ← write-write WAIT
      goto error;
    heap_prepare_get_context (..);  // page 가 unlatch 됐으니 재-fetch
  }
//   2) 이제서야 최신 버전 fetch 하고 MVCC 헤더 읽기
heap_get_last_version (.., context);
heap_get_mvcc_header (.., context, &recdes_header);
//   3) RR/SERIALIZABLE: 최신 버전을 트랜잭션 스냅샷과 대조 (§10.3)

즉 오늘의 write-write 대기 는 OID-lock 블로킹(LK_UNCOND_LOCK)이고, 아래 스냅샷 검사는 lock 이후의 isolation gate 이지 충돌 감지기가 아니다. (이 순서가 cubrid_cv I13 implicit-update-lock 분석이 뒤집으려는 지점이다.)

10.3 게이트 — RR-eligible 클래스의 RR/SERIALIZABLE

// locator_sr.c (annotated)
if (logtb_find_current_isolation (thread_p) > TRAN_READ_COMMITTED
    && logtb_check_class_for_rr_isolation_err (class_oid))
  {
    MVCC_SNAPSHOT *snap = logtb_get_mvcc_snapshot (thread_p);
    MVCC_SATISFIES_SNAPSHOT_RESULT res = snap->snapshot_fnc (.., &recdes_header, snap);
    ...
  }

두 조건이 모두 성립해야 한다:

isolation > READ COMMITTED — RR 또는 SERIALIZABLE. READ COMMITTED 에서는 이 블록을 통째로 건너뛴다: RC 는 -1158 을 절대 내지 않고, row lock 에서 기다렸다 새 버전을 다시 읽는다.
RR-eligible 클래스 — logtb_check_class_for_rr_isolation_err (src/transaction/log_tran_table.c) 는 클래스가 db_root / _db_user / _db_trigger 가 아닐 때만 true 다. 이들은 table lock 전에 접근되고 lock 으로 일관성을 확보하므로 제외된다. 나머지 카탈로그 클래스는 대부분 MVCC-enabled 이고 검사 대상이다.

10.4 세 갈래

게이트는 트랜잭션 스냅샷(mvcc_satisfies_snapshot, src/transaction/mvcc.c)을 최신 버전 헤더에 돌린다:

최신 버전의 스냅샷 판정	의미	결과
`TOO_OLD_FOR_SNAPSHOT`	내 스냅샷 이전에 삭제 + 커밋 — 나에겐 안 보임	`S_DOESNT_EXIST` (행 “없음”, 충돌 아님)
`TOO_NEW_FOR_SNAPSHOT`	최신 버전 inserter 가 active 이거나 내 스냅샷 이후 커밋 (`MVCC_IS_REC_INSERTER_IN_SNAPSHOT`)	`ER_MVCC_SERIALIZABLE_CONFLICT`
`SNAPSHOT_SATISFIED` 이면서 `MVCC_IS_HEADER_DELID_VALID`	동시 트랜잭션이 최신 버전을 삭제	`ER_MVCC_SERIALIZABLE_CONFLICT`
`SNAPSHOT_SATISFIED`, 미삭제	최신 == 내 가시 버전; 아무도 안 바꿈	통과 — 수정 진행

TOO_NEW_FOR_SNAPSHOT 의 정의는 mvcc_satisfies_snapshot 에 있다: 미삭제 레코드인데 inserter 가 “in snapshot” (active 이거나 스냅샷 이후 커밋) 이면 TOO_NEW 다. 이것이 곧 “동시 트랜잭션이 내가 볼 자격 없는 버전을 만들었다” — first-updater-wins 조건이다.

10.5 시나리오

동시 UPDATE. T1 이 t0 에 스냅샷 → T2 가 행 R 을 UPDATE 하고 t0 이후 커밋 → T1 이 R 을 UPDATE → 최신 버전이 T1 에겐 TOO_NEW → -1158. (T1 이 먼저 T2 의 row X-lock 에 막혔다면, grant 후 재-fetch 에서 새 버전을 보고 조용히 덮어쓰는 대신 -1158 을 낸다.)
동시 DELETE. T2 가 R 을 삭제하고 t0 이후 커밋 → T1 이 UPDATE/DELETE → 최신 버전에 동시 deleter 의 delete-id → -1158. (T2 의 삭제가 t0 이전 커밋이면 TOO_OLD → S_DOESNT_EXIST.)
충돌 없음. t0 이후 동시 수정 없음 → 최신 == 가시 버전 → 수정 진행.

10.6 호출자의 처리

-1158 은 abort 신호이며, 이를 삼키면 안 되는 계층들 — query_executor.c, work_space.c(클라이언트 retry), trigger_manager.c — 이 ER_LK_UNILATERALLY_ABORTED 와 나란히 인식한다. 엔진 내부 retry 는 없다: 트랜잭션이 abort 되고, 새 스냅샷으로 재시도할지는 애플리케이션이 정한다.

10.7 MVCC·escalation 과의 관계

MVCC (cubrid-mvcc-detail.md). MVCC 가 기판을 준다 — record header 의 insert/delete MVCCID 와 mvcc_satisfies_* 분류기. 이 챕터는 isolation 계층이 “최신 버전이 내 가시 버전이 아니다” 를 거부로 바꾸는 곳이다.
Escalation (Chapter 6). 무관하다: escalation 은 lock 단위 (instance→class) 를 바꿔 LK_ENTRY 메모리를 던다. 이 검사를 바꾸지 않는다. escalation 이 일어난 bulk UPDATE 도 RR/SERIALIZABLE 에서 수정 행마다 per-row first-updater-wins 검사를 그대로 돌린다.

10.8 위치 힌트 (cross-module)

이 심볼들은 lock_manager.c 밖에 있다. 함수명으로 anchor 하라 (행 번호는 develop+I8 워크트리, 2026-06 기준 확인, revision 마다 drift).

심볼	파일	행
`ER_MVCC_SERIALIZABLE_CONFLICT` (`-1158`)	`base/error_code.h`	1487
`locator_lock_and_get_object_internal` (발생 지점·게이트)	`transaction/locator_sr.c`	12935 (raise 13041 / 13047)
`locator_lock_and_get_object_with_evaluation` (진입, `X_LOCK`)	`transaction/locator_sr.c`	13099
`mvcc_satisfies_snapshot` (TOO_NEW / TOO_OLD / SATISFIED)	`transaction/mvcc.c`	156
`logtb_check_class_for_rr_isolation_err` (RR-eligible 게이트)	`transaction/log_tran_table.c`	5671

위치 힌트 (이 revision 기준)

심볼	파일	행
타입 (헤더)
`struct lk_entry`	`lock_manager.h`	79
`struct lk_res_key`	`lock_manager.h`	164
`struct lk_res`	`lock_manager.h`	175
`lock_remove_all_inst_locks`	`lock_manager.h`	195
`enum LOCK`	`lock_table.h`	29
`lock_Comp[][]`	`lock_table.c`	67
`lock_Conv[][]`	`lock_table.c`	179
`lock_conv()` / `lock_compat()`	`lock_table.h`	58 / 65
내부 타입 (lock_manager.c)
`struct lk_tran_lock`	`lock_manager.c`	324
`struct lk_global_data`	`lock_manager.c`	361
`lk_Gl` (global instance)	`lock_manager.c`	418
`lk_Obj_lock_res_desc`	`lock_manager.c`	621
`obj_lock_entry_desc`	`lock_manager.c`	592
상수와 매크로
`LK_OBJ_LOCK_HASH`	`lock_manager.c`	84
`LK_MIN_OBJECT_LOCKS`	`lock_manager.c`	433
`LOCK_TRAN_LOCAL_POOL_MAX_SIZE`	`lock_manager.c`	351
`LK_MIN_TWFG_EDGE_COUNT`	`lock_manager.c`	451
`LK_MID_TWFG_EDGE_COUNT`	`lock_manager.c`	453
`LK_MAX_TWFG_EDGE_COUNT`	`lock_manager.c`	455
`LK_MAX_VICTIM_COUNT`	`lock_manager.c`	448
`PRM_ID_LK_ESCALATION_AT`	`system_parameter.h`	(config)
`PRM_ID_LK_ROLLBACK_ON_LOCK_ESCALATION`	`system_parameter.h`	(config)
`PRM_ID_LK_RUN_DEADLOCK_INTERVAL`	`system_parameter.c`	1313
초기화 / 해체
`lock_initialize`	`lock_manager.c`	5627
`lock_finalize`	`lock_manager.c`	5859
`lock_initialize_tran_lock_table`	`lock_manager.c`	1061
`lock_initialize_object_hash_table`	`lock_manager.c`	1121
`lock_initialize_object_lock_entry_list`	`lock_manager.c`	1152
`lock_initialize_deadlock_detection`	`lock_manager.c`	1180
`lock_finalize_tran_lock_table`	`lock_manager.c`	5702
`lock_deadlock_detect_daemon_init`	`lock_manager.c`	5812
`deadlock_detect_task_execute`	`lock_manager.c`	5780
entry 초기화 / hash
`lock_initialize_entry_as_granted`	`lock_manager.c`	920
`lock_initialize_entry_as_blocked`	`lock_manager.c`	940
`lock_initialize_entry_as_non2pl`	`lock_manager.c`	962
`lock_create_search_key`	`lock_manager.c`	641
`lock_res_key_compare`	`lock_manager.c`	844
`lock_res_key_hash`	`lock_manager.c`	884
`lock_get_hash_value`	`lock_manager.c`	1015
`lock_get_new_entry`	`lock_manager.c`	9778
`lock_free_entry`	`lock_manager.c`	9809
획득
`lock_object`	`lock_manager.c`	5945
`lock_object_wait_msecs`	`lock_manager.c`	6273
`lock_scan`	`lock_manager.c`	6303
`lock_subclass`	`lock_manager.c`	6154
`lock_classes_lock_hint`	`lock_manager.c`	6379
`lock_internal_perform_lock_object`	`lock_manager.c`	3223
`lock_find_class_entry`	`lock_manager.c`	1596
`lock_position_holder_entry`	`lock_manager.c`	1743
`lock_is_class_lock_escalated`	`lock_manager.c`	508
grant
`lock_grant_blocked_holder`	`lock_manager.c`	2512
`lock_grant_blocked_waiter`	`lock_manager.c`	2629
`lock_grant_blocked_waiter_partial`	`lock_manager.c`	2758
해제
`lock_unlock_object`	`lock_manager.c`	6630
`lock_unlock_object_donot_move_to_non2pl`	`lock_manager.c`	6613
`lock_unlock_object_lock_internal`	`lock_manager.c`	6580
`lock_unlock_object_by_isolation`	`lock_manager.c`	9841
`lock_unlock_shared_inst_lock`	`lock_manager.c`	4399
`lock_unlock_all`	`lock_manager.c`	6851
`lock_internal_perform_unlock_object`	`lock_manager.c`	3945
NON2PL
`lock_add_non2pl_lock`	`lock_manager.c`	1649
`lock_update_non2pl_list`	`lock_manager.c`	4592
`lock_remove_non2pl`	`lock_manager.c`	539
`lock_notify_isolation_incons`	`lock_manager.c`	7516
instant lock
`lock_start_instant_lock_mode`	`lock_manager.c`	8879
`lock_stop_instant_lock_mode`	`lock_manager.c`	8901
escalation
`lock_escalate_if_needed`	`lock_manager.c`	2974
`lock_check_escalate`	`lock_manager.c`	2907
`lock_increment_class_granules`	`lock_manager.c`	548
`lock_decrement_class_granules`	`lock_manager.c`	550
suspend / resume
`lock_suspend`	`lock_manager.c`	2151
`lock_resume`	`lock_manager.c`	2338
`lock_wakeup_deadlock_victim_timeout`	`lock_manager.c`	2386
`lock_wakeup_deadlock_victim_aborted`	`lock_manager.c`	2442
`lock_force_timeout_expired_wait_transactions`	`lock_manager.c`	7443
deadlock detection
`lock_detect_local_deadlock`	`lock_manager.c`	7696
`lock_add_WFG_edge`	`lock_manager.c`	4670
`lock_select_deadlock_victim`	`lock_manager.c`	4806
`lock_is_local_deadlock_detection_interval_up`	`lock_manager.c`	7622
특수 경로
`lock_hold_object_instant`	`lock_manager.c`	5901
`lock_internal_hold_lock_object_instant`	`lock_manager.c`	3087
`lock_initialize_composite_lock`	`lock_manager.c`	8559
`lock_add_composite_lock`	`lock_manager.c`	8586
`lock_finalize_composite_lock`	`lock_manager.c`	8740
`lock_abort_composite_lock`	`lock_manager.c`	8800
`lock_demote_class_lock`	`lock_manager.c`	4165
`lock_internal_demote_class_lock`	`lock_manager.c`	4188
`lock_rep_read_tran`	`lock_manager.c`	9698