(KO) PostgreSQL Free Space Map — 페이지별 재사용 가능 공간 추적

목차

• 이론적 배경
• DBMS 공통 설계
• PostgreSQL의 접근법
• 소스 탐방
• 소스 검증 (2026-06-05 기준)
• PostgreSQL 너머 — 비교 설계와 연구 프론티어
• 출처

이론적 배경

페이지 지향 데이터베이스의 힙 파일은 고정 크기 페이지들의 비순서 집합이다. 튜플은 공간만 있다면 어떤 페이지에든 삽입될 수 있다. 이 자유로움이 정확히 여유 공간 추적을 어렵게 만드는 원인이다. 트랜잭션이 200바이트짜리 행을 삽입하려 할 때 스토리지 엔진은 겉보기엔 단순한 질문에 답해야 한다. “어느 페이지에 넣어야 하는가?” 단순한 두 가지 답은 모두 나쁘다. 항상 마지막 페이지에 추가하면 삭제와 갱신으로 해제된 공간이 낭비되어 파일이 끝없이 커진다(전형적인 “bloat” 실패 패턴이다). 모든 페이지를 스캔하여 여유 공간을 찾는 방법은 정확하지만 삽입마다 O(n) 페이지 읽기를 요구해 대형 릴레이션에서 치명적이다. FSM은 이 질문을 준선형 시간에 답할 수 있게 해주는 자료구조다.

Database System Concepts(Silberschatz, 7판) 저장·파일 구조 장과 Database Internals(Petrov, 2019) 1부 “파일 포맷 / 슬롯 페이지” 장은 두 계층을 구분한다. 슬롯 페이지(slotted page) 는 페이지 내부 레이아웃이다. 페이지 헤더, 앞쪽에서 자라는 라인 포인터 배열, 뒤쪽에서 자라는 튜플 본체, 그 사이의 연속적인 빈 영역으로 구성된다. 한 페이지의 여유 공간은 따라서 라인 포인터 배열 끝과 튜플 영역 시작 사이의 간격(앞으로 추가될 라인 포인터 크기 차감)이라는 단일 파생 수치다. 여유 공간 관리 구조는 페이지 간 계층이다. 각 데이터 페이지에 대략 얼마나 많은 공간이 있는지 기록해 데이터 페이지를 직접 읽지 않고도 적합한 페이지를 찾게 해주는 디렉터리다.

Database Internals는 실제 사용되는 여유 공간 디렉터리 스펙트럼을 설명한다. 페이지당 1비트 비트맵(공간 있음 / 가득 참), 조악한 채움 수준을 담는 페이지당 바이트 또는 워드, ”≥ X 여유가 있는 페이지 찾기” 쿼리를 상위에서 단락할 수 있는 트리 구조 디렉터리가 있다. 설계의 핵심 긴장은 정밀도 대 크기다. 페이지당 정확한 여유 바이트 수를 기록하는 디렉터리는 정밀하지만 크다. 8 KB 페이지 기준 1 TB 테이블이라면 1억 2800만 항목이고 항목당 4바이트면 512 MB짜리 디렉터리가 된다. 캐시에 상주할 만큼 작으려면 디렉터리가 lossy여야 한다. 근사값을 허용하고, 오래됐거나 틀렸을 수 있다는 점을 인정하며, 검증 부담을 호출자에게 넘긴다. 어차피 호출자는 대상 페이지를 잠가야 하기 때문이다.

두 번째 축은 탐색 비용이다. 페이지별 채움 수준을 담은 평면 배열도 적합한 페이지를 찾으려면 O(n)을 스캔해야 한다. 표준 해법은 최대값 트리(tree of maxima) 다. 내부 노드는 자식들의 최대 여유 공간값을 저장하고, ”≥ X” 탐색은 최대값이 X 미만인 서브트리를 가지치기하고 조건을 만족하는 경로만 내려간다. O(n) 대신 O(log n)이다. 구조적으로 이는 “범위 최대 + 점 갱신” 워크로드에 특화된 세그먼트 트리 / 토너먼트 트리다. 점 갱신(한 페이지의 여유 공간 변경)은 새로운 최대값을 상위로 전파하고, 쿼리는 욕심 내려가기로 탐색한다. 같은 모양이 구간 트리, Fenwick 방식 집계, 외부 정렬의 패자 트리에도 나타난다. FSM은 이 아이디어를 디스크 페이지에 적용한 것이다.

세 번째 축은 동시성과 내구성이다. 여유 공간 정보는 근본적으로 힌트다. 정보가 틀려도 최악의 결과는 헛된 페이지 읽기나 약간 더 커진 파일이지 손상되거나 잃어버린 행이 아니다. 이 관찰이 실제 데이터라면 불법일 두 가지 공격적 최적화를 허용한다. 첫째, 디렉터리를 크래시 안전하게 만들 필요가 없다. 크래시 후 재건 또는 자기 교정이 가능하므로 write-ahead log 기록이 불필요하고 대량의 WAL 트래픽이 사라진다. 둘째, 동시 독자들이 경쟁 없는 “다음에 어디 볼까” 포인터를 용인할 수 있다. 오래된 힌트는 두 백엔드를 인접 페이지로 보낼 뿐, 같은 페이지에서 충돌시키지 않는다. FSM 설계의 기예는 근사를 정확성이 허용하는 한계까지 밀어붙이되, 그 결과를 수습할 저렴한 자기 치유 수단을 함께 마련하는 것이다.

DBMS 공통 설계

엔진들 사이에서 여유 공간 디렉터리는 소수의 패턴으로 수렴한다. 얼마나 lossy한지, 그리고 그 손실에서 어떻게 회복하는지가 주된 차이점이다.

페이지 디렉터리 / FSIP(Free Space Inventory Page) 설계. DB2와 여러 상용 엔진은 데이터 파일에 일정 간격으로 특수 디렉터리 페이지를 끼워 넣는다. N번째 페이지마다 FSIP가 위치하고, 그 본체는 뒤따르는 N−1개 데이터 페이지의 채움 수준 코드 배열이다. 탐색은 FSIP를 읽어 후보를 고르고 도착 시 검증한다. 디렉터리가 데이터와 함께 있어 지역성이 좋지만 크기가 테이블에 비례해 선형으로 늘어나고 최상위 가지치기가 없어 많은 FSIP를 읽어야 할 수 있다. Oracle의 ASSM(Automatic Segment Space Management) 은 이를 소규모 비트맵 블록 계층(L1/L2/L3)으로 발전시켜 각 데이터 블록을 몇 개의 채움 버킷(0–25%, 25–50% 등)으로 분류하고 상위 레벨이 하위를 요약해 탐색이 가지치기할 수 있게 한다. 버킷 세분도가 정밀도 조절 손잡이다.

비트맵 여유 공간 관리. 가장 조악한 형태는 페이지당 1~2비트(비어 있음 / 부분적으로 찼음 / 가득 참)를 저장한다. 작고 캐시 친화적이지만 부정확하다. “부분적으로 찼음” 페이지는 작은 튜플은 받아도 큰 튜플은 못 받을 수 있으므로 호출자가 검증해야 하고 맵은 보수적으로 유지해야 한다. SQL Server의 PFS(Page Free Space) 페이지는 중간 경로를 택한다. 페이지당 1바이트에 조악한 채움 비율과 할당 상태 비트를 기록하며 약 8000 페이지마다 PFS 페이지를 둔다. 그 위의 GAM/SGAM 페이지는 익스텐트 단위 할당을 추적한다. 되풀이되는 주제는 페이지당 바이트가 비트 하나(너무 조악)와 정확한 카운트(너무 큼) 사이의 최적점이라는 것이다.

최대값 트리 설계. 준선형 탐색을 위해 엔진들은 페이지별 값 위에 최대값 트리를 쌓는다. 반복되는 두 가지 선택지는 (a) 디렉터리 페이지 내부의 트리(힙 순서 배열로 페이지 내 탐색이 로그 시간)와 (b) 디렉터리 페이지 사이의 트리(상위 디렉터리 페이지의 항목이 하위 디렉터리 페이지를 요약)다. PostgreSQL은 두 계층 모두에 완전히 투자하고 구조적으로 동일하게 만들어, 같은 페이지 내 탐색 코드가 모든 레벨에 적용되는 독특한 방식을 택한다.

내구성 입장. 엔진들은 여유 공간 디렉터리를 복구 가능하게 할지 여부에서 갈린다. 디렉터리 갱신에 WAL을 기록해 복구 후 항상 정확하게 하는 방식은 단순하지만 삽입/삭제 트래픽에 비례한 로그 볼륨을 더한다. 다른 방식은 맵을 재구성 가능한 힌트로 취급해 로깅하지 않는다. 사용 시 검증, 주기적인 배경 재건(통상 VACUUM/유지보수에 포함), 읽기 시 멱등 자기 수리에 의존한다. 비로깅 방식은 일시적 부정확성이라는 작은 위험을 WAL과 잠금 경쟁의 대폭 감소와 교환한다. PostgreSQL은 비로깅 경로를 의도적으로 선택하고 그것을 안전하게 만드는 자기 교정 수단을 문서화한다.

동시성 입장. 여유 공간 디렉터리는 쓰기가 잦은 공유 구조다. 페이지에 삽입하는 모든 트랜잭션은 그 페이지의 항목을 갱신하고 싶어 하고, 대상이 필요한 모든 트랜잭션은 상위 근방을 읽고 싶어 한다. 엔진들은 (i) 탐색에는 공유 잠금, 갱신에만 배타 잠금을 사용하고, (ii) 동시 삽입자들을 “가장 비어 있는” 페이지 하나에 집중시키지 않고 다른 후보 페이지들로 분산시키며, (iii) 경쟁적 힌트 갱신을 허용함으로써 경쟁을 줄인다. PostgreSQL의 라운드로빈 fp_next_slot 포인터는 공유 잠금 아래서도 갱신되며, (ii)와 (iii)의 직접적인 구현이다.

flowchart TD
  subgraph Approx["여유 공간 디렉터리: 정밀도/크기/내구성 트레이드오프"]
    A["페이지당 정확한 바이트 수<br/>정밀하지만 크고 페이징 필요"]
    B["페이지당 바이트 = 256 버킷<br/>PostgreSQL FSM, SQL Server PFS<br/>작고 lossy, 사용 시 검증"]
    C["페이지당 1-2비트<br/>비어 있음 / 부분 / 가득<br/>아주 작고 매우 lossy"]
  end
  B --> D["위에 최대값 트리 쌓기<br/>노드 = 자식의 최대값<br/>>= X 탐색이 서브트리 가지치기<br/>O(log n)"]
  D --> E["내구성 선택"]
  E --> F["WAL 로깅: 크래시 후 항상 정확<br/>로그 볼륨 증가"]
  E --> G["비로깅: 힌트만<br/>사용 시 검증 + VACUUM에서 재건<br/>PostgreSQL의 선택"]

PostgreSQL의 접근법

PostgreSQL은 모든 힙 릴레이션(그리고 요청하는 모든 인덱스 AM)에 별도의 FSM을 제공한다. 메인 데이터 fork 및 visibility map fork와 나란히 같은 RelFileLocator로 주소 지정되는 FSM_FORKNUM fork에 저장된다. 이 fork 기반 설계(8.4에서 고정 크기 공유 FSM을 대체하며 도입됨)는 맵이 릴레이션과 함께 성장하고 함께 잘리며 일반 버퍼 매니저와 smgr 계층으로 읽힌다는 것을 의미한다. 특수한 할당이 없다. fork의 I/O는 postgres-smgr-md.md의 관심사다. 여기서는 “블록 0부터 번호가 매겨진 FSM 페이지 파일”로 취급한다.

페이지당 1바이트, 256 채움 카테고리. 맵은 BLCKSZ/256 바이트 단위로 여유 공간을 기록한다. freespace.c가 양자화를 정의한다.

// freespace.c — category constants
#define FSM_CATEGORIES  256
#define FSM_CAT_STEP  (BLCKSZ / FSM_CATEGORIES)
#define MaxFSMRequestSize  MaxHeapTupleSize

기본 8 KB BLCKSZ에서 FSM_CAT_STEP은 32바이트다. 카테고리 c는 “c·32바이트 이상 (c+1)·32−1바이트 이하의 여유”를 의미한다. 카테고리 0은 “사실상 가득 참”, 카테고리 255는 “MaxFSMRequestSize(= MaxHeapTupleSize) 이상 여유”를 뜻한다. 카테고리 255의 비대칭은 의도적이다. MaxFSMRequestSize에 대한 요청은 완전히 빈 페이지로 충족 가능해야 하므로, 최상위 카테고리는 단계의 정수 배수가 아닌 그 경계에 고정된다. fsm_space_avail_to_cat은 아래로 반올림(페이지는 실제보다 많이 담고 있다고 보고하지 않음)하고 fsm_space_needed_to_cat은 위로 반올림(요청은 절대 과소평가하지 않음)하므로, 맵은 맞는다고 낙관적으로 거짓말하지 않는다.

// freespace.c — fsm_space_needed_to_cat (rounds up; never under-promises)
cat = (needed + FSM_CAT_STEP - 1) / FSM_CAT_STEP;
if (cat > 255)
    cat = 255;
return (uint8) cat;

각 FSM 페이지 안의 이진 최대 힙. FSM 페이지 본체(FSMPageData.fp_nodes)는 완전 이진 트리를 배열 순서로 저장한다. 비리프 노드는 두 자식의 최대값을 담고, 리프는 힙 페이지별 카테고리를 담는다. 헤더는 NonLeafNodesPerPage(= BLCKSZ/2 − 1) 내부 슬롯을 예약하고 나머지는 리프(SlotsPerFSMPage, 8 KB에서 약 4000개)다. 루트 노드 fp_nodes[0]이 따라서 이 FSM 페이지가 커버하는 모든 힙 페이지의 최대 여유 공간 카테고리다. 하강 없이 “여기에 ≥ X인 페이지가 있는가?”에 단일 바이트로 답한다.

// fsm_internals.h — the FSM page body
typedef struct
{
    int     fp_next_slot;                 /* round-robin search start hint */
    uint8   fp_nodes[FLEXIBLE_ARRAY_MEMBER]; /* binary tree: non-leaf then leaf */
} FSMPageData;

FSM 페이지 사이의 팬아웃 트리. 하나의 FSM 페이지는 약 4000개의 힙 페이지를 커버한다. 전체 릴레이션(최대 2^32−1 블록)을 커버하기 위해 PostgreSQL은 FSM 페이지를 고정 높이 트리로 쌓는다. 상위 레벨 FSM 페이지의 리프 슬롯은 하위 레벨 FSM 페이지의 루트를 미러링하므로 “자식의 최대값” 불변식이 페이지 내부와 마찬가지로 페이지 사이에서도 성립한다. 약 4000-way 팬아웃으로 3단계가 4000^3 > 2^32에 도달하므로 기본 BLCKSZ에서 FSM_TREE_DEPTH는 3이다(매우 작은 블록 크기에서는 4). 레벨 0이 하단(힙 페이지당 리프 하나), 레벨 FSM_ROOT_LEVEL이 루트이며, 루트 FSM 페이지는 항상 물리 블록 0이다.

flowchart TD
  R["루트 FSM 페이지 (레벨 2, 물리 블록 0)<br/>fp_nodes[0] = 전체 릴레이션의 최대 여유"]
  R --> L1a["레벨-1 FSM 페이지 #0<br/>약 4000개 레벨-0 페이지 커버"]
  R --> L1b["레벨-1 FSM 페이지 #1"]
  L1a --> L0a["레벨-0 FSM 페이지 #0<br/>4000개 리프 = 4000개 힙 페이지"]
  L1a --> L0b["레벨-0 FSM 페이지 #1"]
  L0a --> H0["힙 블록 0 .. 3999<br/>각 리프 바이트 하나"]
  L0b --> H1["힙 블록 4000 .. 7999"]

설계의 묘미는 두 트리 모두 같은 규칙을 따르므로, 하나의 루틴(fsm_search_avail)이 모든 레벨에서 페이지 내부를 탐색하고 freespace.c는 페이지 사이 이동만 담당한다는 것이다. README는 계약을 명확히 한다. “각 페이지 내의 루트 노드는 그 상위 페이지의 해당 리프 노드와 같은 값을 갖는다.”

탐색, 갱신, 진공. 세 개의 공개 동사가 위에 위치한다. GetPageWithFreeSpace(≥ N바이트인 힙 블록 찾기), RecordPageWithFreeSpace(한 페이지의 기록된 여유 공간 설정), RecordAndGetPageWithFreeSpace(힙이 재시도 시 사용하는 조합 — 실패한 페이지를 기록하고 근처 대안을 하나의 잠금 획득으로 찾기)가 그것이다. FreeSpaceMapVacuum[Range]는 VACUUM이 리프를 갱신한 후 상위 레벨 최대값을 하위 레벨에서 다시 도출한다.

// freespace.c — the public search entry point
BlockNumber
GetPageWithFreeSpace(Relation rel, Size spaceNeeded)
{
    uint8       min_cat = fsm_space_needed_to_cat(spaceNeeded);
    return fsm_search(rel, min_cat);
}

WAL 비로깅, 자기 교정. 쓰기는 MarkBufferDirty가 아닌 MarkBufferDirtyHint를 사용한다. 읽기는 RBM_ZERO_ON_ERROR를 사용하므로 찢기거나 체크섬 실패한 FSM 페이지는 오류 대신 조용히 0으로 초기화된다. 정확성은 아래에서 설명하는 네 가지 메커니즘으로 복원된다. fsm_rebuild_page를 트리거하는 루트 대비 설정값 정합성 검사, fsm_search_avail의 하강 시 손상 검사, 파일 끝 너머 블록 반환을 거부하는 fsm_does_block_exist 가드, VACUUM의 주기적 FreeSpaceMapVacuum이 그것이다. 비로깅의 유일한 예외는 절단(FreeSpaceMapPrepareTruncateRel)이다. 절단된 꼬리가 재생 후 부활하지 않도록 실제 MarkBufferDirty와 선택적 log_newpage_buffer를 사용한다.

소스 탐방

코드는 2단계 트리 경계를 따라 깔끔하게 나뉜다. fsmpage.c는 페이지 내부 이진 트리를 알고 fork나 주소 지정에 대해서는 아무것도 모른다. 페이지를 “SlotsPerFSMPage개 슬롯을 가진 블랙박스”로 취급한다. freespace.c는 페이지 간 팬아웃, 바이트/카테고리 인코딩, 버퍼 I/O, 공개 API를 알고 모든 페이지 내부 연산에서 fsmpage.c를 호출한다. indexfsm.c는 인덱스 페이지 재활용을 위한 공개 API의 얇은 재포장이다.

페이지 내 트리: 설정, 탐색, 재건 (fsmpage.c)

페이지 트리는 세 매크로로 탐색된다. leftchild(x) = 2x+1, rightchild(x) = 2x+2, parentof(x) = (x−1)/2는 루트를 인덱스 0에 두는 완전 이진 트리의 표준 배열 임베딩이다.

fsm_set_avail은 리프를 쓰고 변경을 상위로 전파하다가 최대값이 변하지 않는 첫 번째 부모에서 일찍 멈춘다.

// fsm_set_avail — fsmpage.c (set one leaf, propagate the new max up the spine)
int     nodeno = NonLeafNodesPerPage + slot;
FSMPage fsmpage = (FSMPage) PageGetContents(page);
oldvalue = fsmpage->fp_nodes[nodeno];
if (oldvalue == value && value <= fsmpage->fp_nodes[0])
    return false;                       /* unchanged and not above root: nothing to do */
fsmpage->fp_nodes[nodeno] = value;
do {
    uint8   newvalue = 0;
    nodeno = parentof(nodeno);
    lchild = leftchild(nodeno);
    rchild = lchild + 1;
    newvalue = fsmpage->fp_nodes[lchild];
    if (rchild < NodesPerPage)
        newvalue = Max(newvalue, fsmpage->fp_nodes[rchild]);
    oldvalue = fsmpage->fp_nodes[nodeno];
    if (oldvalue == newvalue)
        break;                          /* parent max didn't move: stop bubbling */
    fsmpage->fp_nodes[nodeno] = newvalue;
} while (nodeno > 0);
if (value > fsmpage->fp_nodes[0])       /* sanity: set value still above root => corrupt */
    fsm_rebuild_page(page);

마지막 검사가 자기 교정 수단 중 첫 번째다. 버블링 후 방금 저장한 값이 여전히 루트보다 크다면, 척추의 어느 부모가 너무 작은 값을 보유하고 있다는 의미(손상)다. 전체 페이지의 내부 노드를 fsm_rebuild_page로 재계산한다.

fsm_search_avail이 페이지 내부 탐색의 핵심이다. 라운드로빈 fp_next_slot 힌트에서 시작해 “탐색 삼각형 확장” 보행을 수행한다. 각 단계에서 한 노드 오른쪽(rightneighbor로 레벨 내 래핑)으로 이동하고 부모로 올라가 커버되는 서브트리를 매번 두 배로 늘리다가 minvalue 이상인 노드를 찾는다. 그런 다음 왼쪽 자식을 우선하면서 만족하는 리프로 내려간다.

// fsm_search_avail — fsmpage.c (expanding-triangle ascent, then greedy descent)
if (fsmpage->fp_nodes[0] < minvalue)
    return -1;                          /* root says no page qualifies: O(1) miss */
target = fsmpage->fp_next_slot;
if (target < 0 || target >= LeafNodesPerPage)
    target = 0;
target += NonLeafNodesPerPage;
nodeno = target;
while (nodeno > 0) {
    if (fsmpage->fp_nodes[nodeno] >= minvalue)
        break;
    nodeno = parentof(rightneighbor(nodeno)); /* move right, wrap, climb */
}
while (nodeno < NonLeafNodesPerPage) {  /* descend to a leaf, prefer left */
    int childnodeno = leftchild(nodeno);
    if (childnodeno < NodesPerPage && fsmpage->fp_nodes[childnodeno] >= minvalue) {
        nodeno = childnodeno; continue;
    }
    childnodeno++;                      /* try right child */
    if (childnodeno < NodesPerPage && fsmpage->fp_nodes[childnodeno] >= minvalue)
        nodeno = childnodeno;
    else { /* neither child qualifies though parent promised: torn page -> rebuild */ }
}
slot = nodeno - NonLeafNodesPerPage;
fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0);

두 가지 설계 요점이 보인다. 하강의 “부모가 약속했는데 두 자식 모두 조건 불만족” 분기가 두 번째 자기 교정 수단이다. DEBUG1 "fixing corrupt FSM block"을 기록하고, 필요시 배타 잠금으로 업그레이드하고, fsm_rebuild_page를 호출한 후 goto restart한다. fp_next_slot은 공유 잠금 아래서도 갱신된다. 코드 주석은 오염된 힌트가 배타 잠금 비용보다 저렴하다고 명시한다.

// fsm_search_avail — fsmpage.c (torn-page recovery during descent)
BufferGetTag(buf, &rlocator, &forknum, &blknum);
elog(DEBUG1, "fixing corrupt FSM block %u, relation %u/%u/%u",
     blknum, rlocator.spcOid, rlocator.dbOid, rlocator.relNumber);
if (!exclusive_lock_held) {
    LockBuffer(buf, BUFFER_LOCK_UNLOCK);
    LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
    exclusive_lock_held = true;
}
fsm_rebuild_page(page);
MarkBufferDirtyHint(buf, false);
goto restart;

rightneighbor는 2의 보수 트릭으로 래핑을 구현한다. 각 레벨의 가장 왼쪽 노드 인덱스는 2^level − 1이므로 ((x+1) & x) == 0이 오른쪽 이동이 다음 레벨의 가장 왼쪽 노드로 넘어감을 감지하고, 그 경우 부모로 접기한다.

// rightneighbor — fsmpage.c (move right within a level, wrap to parent at the edge)
x++;
if (((x + 1) & x) == 0)     /* (x+1) a power of two => x is leftmost of next level */
    x = parentof(x);
return x;

fsm_rebuild_page는 모든 내부 노드를 아래에서 위로(마지막 비리프부터 루트까지) 재계산한다. fsm_truncate_avail은 슬롯 ≥ n을 0으로 만든 뒤 재건한다. 두 함수 모두 복구 및 절단 경로에서 사용된다. fsm_get_avail과 fsm_get_max_avail(fp_nodes[0] 반환)은 잠금 없는 단일 바이트 읽기다.

페이지 간 탐색과 주소 지정 (freespace.c)

freespace.c는 논리 주소(FSMAddress {level, logpageno}와 slot)로 작업하고 I/O 시점에만 물리 블록으로 변환한다. 네 가지 탐색 도우미는 SlotsPerFSMPage를 팬아웃으로 사용해 페이지 단위로 페이지 내 매크로를 반영한다.

// fsm_get_location / fsm_get_parent / fsm_get_child — freespace.c
addr.level = FSM_BOTTOM_LEVEL;                       /* heap block -> level-0 addr+slot */
addr.logpageno = heapblk / SlotsPerFSMPage;
*slot = heapblk % SlotsPerFSMPage;
/* parent: */ parent.level = child.level + 1;
parent.logpageno = child.logpageno / SlotsPerFSMPage;
*slot = child.logpageno % SlotsPerFSMPage;
/* child: */ child.level = parent.level - 1;
child.logpageno = parent.logpageno * SlotsPerFSMPage + slot;

fsm_logical_to_physical은 논리 주소를 README에 설명된 깊이 우선 물리 블록 레이아웃(루트를 블록 0에, 각 서브트리를 깊이 우선으로 배치)으로 평탄화한다. 대상 앞에 오는 리프 페이지와 상위 페이지를 센다.

// fsm_logical_to_physical — freespace.c (logical (level,logpageno) -> physical block)
leafno = addr.logpageno;
for (l = 0; l < addr.level; l++)
    leafno *= SlotsPerFSMPage;          /* logical page -> its first bottom leaf */
pages = 0;
for (l = 0; l < FSM_TREE_DEPTH; l++) {
    pages += leafno + 1;                /* count pages at each level up to the leaf */
    leafno /= SlotsPerFSMPage;
}
pages -= addr.level;                    /* subtract lower levels not actually traversed */
return pages - 1;                       /* 0-based block number */

fsm_readbuf는 읽기/확장 게이트웨이다. smgr_cached_nblocks[FSM_FORKNUM] 크기 캐시를 참조(느리게 갱신)하고, RBM_ZERO_ON_ERROR로 읽으며, extend가 true일 때 fsm_extend(EB_CREATE_FORK_IF_NEEDED 옵션으로 ExtendBufferedRelTo)로 확장하고, 동시 초기화자에 대비한 재검사 후 잠금 가드 아래서 새로 0으로 초기화된 페이지를 PageInit한다.

탐색 핵심 함수 (fsm_search)

fsm_search는 루트부터 교차 페이지 트리를 내려간다. 각 레벨에서 공유 잠금 아래 페이지를 fsm_search_avail하고, 하강 전 부모를 해제한다(한 번에 페이지 하나만 잠금, README “잠금” 절의 요건). 세 가지가 이를 단순 탐색보다 견고하게 만든다.

// fsm_search — freespace.c (descend root->leaf, repair stale parents, verify EOF)
if (addr.level == FSM_BOTTOM_LEVEL) {
    BlockNumber blkno = fsm_get_heap_blk(addr, slot);
    if (fsm_does_block_exist(rel, blkno)) {     /* (1) guard: block must really exist */
        ReleaseBuffer(buf);
        return blkno;
    }
    /* Block past EOF: zero the slot, restart from root */
    LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
    fsm_set_avail(page, slot, 0);
    MarkBufferDirtyHint(buf, false);
    UnlockReleaseBuffer(buf);
    if (restarts++ > 10000) return InvalidBlockNumber;
    addr = FSM_ROOT_ADDRESS;
}
/* ... at a non-bottom level, if the child search failed the parent was stale: */
parent = fsm_get_parent(addr, &parentslot);
fsm_set_and_search(rel, parent, parentslot, max_avail, 0);  /* (2) self-correct upper node */
if (restarts++ > 10000) return InvalidBlockNumber;          /* (3) emergency valve */
addr = FSM_ROOT_ADDRESS;

(1) fsm_does_block_exist 가드는 FSM은 비어 있다고 믿지만 크래시 후 디스크에 도달하지 못한 블록을 반환하지 않도록 막는다. 잘못된 슬롯을 0으로 만들고 탐색을 재시작한다. (2) 리프 탐색이 실패했는데 부모가 여기를 가리켰다면 상위 노드의 최대값이 오래됐다는 의미다. fsm_set_and_search로 부모를 교정해 루프가 다시 함정에 걸리지 않도록 한 뒤 재시작한다. (3) 10000회 반복 비상 밸브가 심각하게 오래된 상위 페이지에서 병적 루핑을 막는다.

fsm_set_and_search는 공유 갱신 기본 함수다. 페이지를 배타 잠금하고, 슬롯을 fsm_set_avail(힌트로 더티 표시)하며, minValue > 0일 때 즉시 같은 페이지를 fsm_search_avail해 기록 후 찾기가 두 번째 잠금 없이 근처 페이지를 반환할 수 있다. RecordAndGetPageWithFreeSpace는 실패한 페이지와 적합한 페이지가 같은 FSM 페이지를 공유할 때 이를 활용해 근처 페이지를 반환한다.

힙 삽입 위치 결정 (hio.c)

RelationGetBufferForTuple이 힙의 페이지 선택 루프다. targetFreeSpace를 계산하고, 캐시된 대상 블록을 시도한 뒤 FSM에 물어보고, 루프를 돈다. 너무 작은 페이지는 보고하고 맞는 페이지를 찾거나 릴레이션을 확장해야 할 때까지 새 후보를 하나의 호출로 가져온다.

// RelationGetBufferForTuple — hio.c (FSM-driven insert placement loop)
if (targetBlock == InvalidBlockNumber && use_fsm)
    targetBlock = GetPageWithFreeSpace(relation, targetFreeSpace);
/* ... loop: lock targetBlock, recheck real free space ... */
pageFreeSpace = PageGetHeapFreeSpace(page);
if (targetFreeSpace <= pageFreeSpace) {
    RelationSetTargetBlock(relation, targetBlock);
    return buffer;                      /* FSM was right: use this page */
}
/* FSM over-promised (stale): record the truth, get another candidate */
targetBlock = RecordAndGetPageWithFreeSpace(relation, targetBlock,
                                            pageFreeSpace, targetFreeSpace);

GetPageWithFreeSpace 주석이 경고하는 “페이지에 공간이 부족할 수 있으니 대비하라”는 계약이 정확히 이것이다. 힙은 어차피 잡아야 하는 페이지 잠금 아래서 검증하고, 교정된 값을 피드백해 FSM이 수렴하도록 한다. 대량 확장 후 RelationAddBlocks는 RecordPageWithFreeSpace와 FreeSpaceMapVacuumRange로 새 페이지의 여유 공간을 기록해 다른 백엔드가 볼 수 있게 한다.

VACUUM 상위 페이지 갱신 (fsm_vacuum_page, vacuumlazy.c의 호출자)

VACUUM은 힙 페이지를 처리하면서 리프를 인라인으로 갱신한다(RecordPageWithFreeSpace가 하단 페이지 내에서 버블링). 상위 페이지는 FreeSpaceMapVacuum[Range]가 호출하는 fsm_vacuum_page로만 갱신된다. 이 함수는 트리를 깊이 우선으로 탐색하고(물리 레이아웃과 일치해 I/O 효율적), 각 내부 슬롯을 자식의 실제 최대값에서 재계산하며, fp_next_slot을 0으로 재설정해 향후 탐색을 낮은 번호 페이지 쪽으로 유도한다(나중 VACUUM의 꼬리 절단 지원).

// fsm_vacuum_page — freespace.c (depth-first refresh of upper nodes from children)
if (addr.level > FSM_BOTTOM_LEVEL) {
    for (slot = start_slot; slot <= end_slot; slot++) {
        if (!eof)
            child_avail = fsm_vacuum_page(rel, fsm_get_child(addr, slot),
                                          start, end, &eof);
        else
            child_avail = 0;
        if (fsm_get_avail(page, slot) != child_avail) {  /* upper node was stale */
            LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
            fsm_set_avail(page, slot, child_avail);
            MarkBufferDirtyHint(buf, false);
            LockBuffer(buf, BUFFER_LOCK_UNLOCK);
        }
    }
}
max_avail = fsm_get_max_avail(page);
((FSMPage) PageGetContents(page))->fp_next_slot = 0;   /* bias toward low pages */

vacuumlazy.c는 스캔 중 주기적으로(인덱스 없는 테이블의 경우 VACUUM_FSM_EVERY_PAGES ≈ 8 GB마다) FreeSpaceMapVacuumRange를 호출하고 스캔 끝에 한 번 더 호출한다. 새로 해제된 공간이 전체 VACUUM 완료를 기다리지 않고 탐색 가능해진다. VACUUM 드라이버 자체는 postgres-vacuum.md에서 다룬다.

인덱스 페이지 재활용 (indexfsm.c)

indexfsm.c는 힙 FSM 전체를 재사용하되 256개 카테고리를 두 가지로 축소한다. 인덱스 페이지는 완전히 비어 있거나 사용 중이거나 둘 중 하나다. GetFreeIndexPage는 BLCKSZ/2(절반 이상이면 “비어 있음”으로 매핑)를 요청하고, 기록 도우미들은 두 상태를 바이트 극단값으로 인코딩한다.

// indexfsm.c — binary free/used encoding over the heap FSM
BlockNumber GetFreeIndexPage(Relation rel) {
    BlockNumber blkno = GetPageWithFreeSpace(rel, BLCKSZ / 2);
    if (blkno != InvalidBlockNumber)
        RecordUsedIndexPage(rel, blkno);    /* claim it atomically-ish */
    return blkno;
}
void RecordFreeIndexPage(Relation rel, BlockNumber b) { RecordPageWithFreeSpace(rel, b, BLCKSZ - 1); }
void RecordUsedIndexPage(Relation rel, BlockNumber b) { RecordPageWithFreeSpace(rel, b, 0); }

nbtree는 이 방식으로 삭제된 페이지를 재활용한다. 재활용 가능하다고 판단된 페이지는 RecordFreeIndexPage로 기록되고, _bt_getbuf의 “빈 페이지 가져오기” 경로가 GetFreeIndexPage로 되돌려 받는다. 재활용 가능성 게이트는 postgres-nbtree.md를 참조한다.

위치 힌트 (2026-06-05 기준, REL_18 273fe94)

심볼	파일	줄
FSM_CATEGORIES, FSM_CAT_STEP, MaxFSMRequestSize	src/backend/storage/freespace/freespace.c	64–66
FSM_TREE_DEPTH, FSM_ROOT_LEVEL, FSM_BOTTOM_LEVEL	src/backend/storage/freespace/freespace.c	75–78
FSMAddress 구조체	src/backend/storage/freespace/freespace.c	84–88
GetPageWithFreeSpace	src/backend/storage/freespace/freespace.c	136
RecordAndGetPageWithFreeSpace	src/backend/storage/freespace/freespace.c	153
RecordPageWithFreeSpace	src/backend/storage/freespace/freespace.c	193
XLogRecordPageWithFreeSpace	src/backend/storage/freespace/freespace.c	210
GetRecordedFreeSpace	src/backend/storage/freespace/freespace.c	253
FreeSpaceMapPrepareTruncateRel	src/backend/storage/freespace/freespace.c	284
FreeSpaceMapVacuum / FreeSpaceMapVacuumRange	src/backend/storage/freespace/freespace.c	367 / 386
fsm_space_avail_to_cat / fsm_space_needed_to_cat	src/backend/storage/freespace/freespace.c	401 / 441
fsm_logical_to_physical	src/backend/storage/freespace/freespace.c	464
fsm_get_location / fsm_get_parent / fsm_get_child	src/backend/storage/freespace/freespace.c	500 / 526 / 544
fsm_readbuf / fsm_extend	src/backend/storage/freespace/freespace.c	563 / 638
fsm_set_and_search	src/backend/storage/freespace/freespace.c	655
fsm_search	src/backend/storage/freespace/freespace.c	687
fsm_vacuum_page	src/backend/storage/freespace/freespace.c	821
fsm_does_block_exist	src/backend/storage/freespace/freespace.c	935
leftchild / rightchild / parentof 매크로	src/backend/storage/freespace/fsmpage.c	29–31
rightneighbor	src/backend/storage/freespace/fsmpage.c	36
fsm_set_avail	src/backend/storage/freespace/fsmpage.c	62
fsm_get_avail / fsm_get_max_avail	src/backend/storage/freespace/fsmpage.c	121 / 137
fsm_search_avail	src/backend/storage/freespace/fsmpage.c	157
fsm_truncate_avail	src/backend/storage/freespace/fsmpage.c	312
fsm_rebuild_page	src/backend/storage/freespace/fsmpage.c	341
FSMPageData, NonLeafNodesPerPage, SlotsPerFSMPage	src/include/storage/fsm_internals.h	24–61
GetFreeIndexPage / RecordFreeIndexPage / RecordUsedIndexPage	src/backend/storage/freespace/indexfsm.c	37 / 51 / 61
RelationGetBufferForTuple (FSM 호출부)	src/backend/access/heap/hio.c	584 / 737 / 759
VACUUM_FSM_EVERY_PAGES, FreeSpaceMapVacuumRange 호출	src/backend/access/heap/vacuumlazy.c	202 / 1301 / 1488 / 1537

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

확인된 사실

• 여유 공간은 1바이트 = BLCKSZ/256 바이트 단위 256 카테고리로 양자화된다. freespace.c에서 확인: FSM_CATEGORIES 256, FSM_CAT_STEP (BLCKSZ / FSM_CATEGORIES), MaxFSMRequestSize = MaxHeapTupleSize. fsm_space_avail_to_cat은 내림 반올림하고 최상위 이외 값을 254로 상한 처리한다. fsm_space_needed_to_cat은 올림 반올림한다. 카테고리 255는 선두 주석에 따라 정확히 MaxFSMRequestSize에 예약된다. README의 “페이지당 맵 바이트 하나 … 여유 공간을 BLCKSZ/256으로 나눔”과 일치한다.

• FSM 페이지 본체는 완전 이진 최대 힙으로, 비리프 노드 먼저 리프 다음이다. fsm_internals.h에서 확인: fp_nodes[FLEXIBLE_ARRAY_MEMBER], NonLeafNodesPerPage = BLCKSZ/2 − 1, LeafNodesPerPage = NodesPerPage − NonLeafNodesPerPage, SlotsPerFSMPage = LeafNodesPerPage. fsmpage.c의 leftchild/rightchild/parentof 매크로가 루트를 인덱스 0에 두는 배열 임베딩을 확인한다. fsm_get_max_avail은 fp_nodes[0]을 반환한다.

• 기본 BLCKSZ에서 교차 페이지 트리는 고정 높이 3이며 루트는 물리 블록 0이다. 확인: FSM_TREE_DEPTH ((SlotsPerFSMPage >= 1626) ? 3 : 4), FSM_ROOT_LEVEL = FSM_TREE_DEPTH − 1, FSM_BOTTOM_LEVEL 0, FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0}. README의 수식이 fsm_logical_to_physical의 루프와 일치한다. 1626^3 ≥ 2^32−1이 깊이 3의 근거라는 주석이 FSM_TREE_DEPTH 주석에 있다.

• 상위 FSM 페이지의 리프는 그것이 커버하는 하위 FSM 페이지의 루트와 같다. README에 명시(“각 페이지의 루트 노드는 상위 페이지의 해당 리프 노드와 같은 값을 갖는다”)되고 fsm_vacuum_page가 강제 적용한다. fsm_set_avail(page, slot, child_avail)에서 child_avail은 재귀 반환값 = 자식 페이지의 fsm_get_max_avail이다.

• 탐색은 공유 잠금, 갱신은 배타 잠금, 하강 중 한 번에 페이지 하나만 잠근다. fsm_search(BUFFER_LOCK_SHARE, 부모를 UnlockReleaseBuffer/ReleaseBuffer로 해제 후 하강)와 fsm_set_and_search(BUFFER_LOCK_EXCLUSIVE)에서 확인. README “잠금” 절과 일치한다.

• fp_next_slot은 공유 잠금 아래서도 갱신되는 라운드로빈 힌트다. fsm_search_avail에서 확인: fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0), 공유 잠금 갱신을 정당화하는 주석, fsm_internals.h에 fp_next_slot이 int(원자적 페치/저장용)인 이유 설명. fsm_vacuum_page가 0으로 재설정한다.

• FSM은 WAL 로깅 없이 운용된다. 쓰기는 MarkBufferDirtyHint, 읽기는 RBM_ZERO_ON_ERROR다. fsm_set_and_search, fsm_search, fsm_vacuum_page(MarkBufferDirtyHint)와 fsm_readbuf/fsm_extend(RBM_ZERO_ON_ERROR)에서 확인. README “복구” 절에 근거 명시. 유일한 예외는 XLogRecordPageWithFreeSpace다. 체크섬 활성 복구 중 MarkBufferDirtyHint가 no-op이기 때문에 MarkBufferDirty를 사용한다. 인라인 주석에서 확인.

• 세 가지 자기 교정 수단이 WAL 없이 손상을 수리한다. (1) fsm_set_avail: 버블링 후 if (value > fsmpage->fp_nodes[0]) fsm_rebuild_page(page). (2) fsm_search_avail: “두 자식 모두 불만족” 분기가 DEBUG1 "fixing corrupt FSM block"을 기록하고 fsm_rebuild_page 후 goto restart. (3) fsm_search: 하위 탐색 실패 시 fsm_set_and_search(rel, parent, parentslot, max_avail, 0)으로 부모 교정.

• fsm_does_block_exist가 크래시 후 팬텀 여유 공간을 막는다. freespace.c에서 확인: fsm_search와 RecordAndGetPageWithFreeSpace 모두 블록 반환 전 이 함수를 호출한다. smgr_cached_nblocks[MAIN_FORKNUM]과 비교하고 RelationGetNumberOfBlocks로 폴백한다. README “복구” 단락에 위험 설명: 관계 확장은 WAL 로깅되지 않아 디스크 상 FSM 슬롯이 재생 후 디스크에 도달하지 못한 PageIsNew 블록을 가리킬 수 있다.

• VACUUM은 리프를 인라인으로 갱신하고 상위 페이지는 주기적으로 갱신한다. vacuumlazy.c가 힙 페이지마다 RecordPageWithFreeSpace를 호출하고 VACUUM_FSM_EVERY_PAGES마다, 그리고 스캔 끝에 FreeSpaceMapVacuumRange를 호출함을 확인. fsm_vacuum_page는 깊이 우선이고 fp_next_slot을 재설정한다.

• 힙 삽입 경로는 FSM 응답을 검증하고 교정값을 피드백한다. RelationGetBufferForTuple(hio.c)에서 확인: 초기 대상은 GetPageWithFreeSpace, 잠금 아래 PageGetHeapFreeSpace 재검사, 미스 시 RecordAndGetPageWithFreeSpace. 함수 헤더 주석이 FSM 정보 오래됨 가능성을 명시하고 재시도 루프를 예고한다.

• indexfsm.c는 힙 FSM을 이진 비어 있음/사용 중 인코딩으로 재사용한다. 확인: RecordFreeIndexPage는 BLCKSZ − 1 기록, RecordUsedIndexPage는 0 기록, GetFreeIndexPage는 BLCKSZ/2를 요청하고 페이지를 사용 중으로 표시. IndexFreeSpaceMapVacuum은 그냥 FreeSpaceMapVacuum을 호출한다.

미해결 질문

1. 실제 환경에서 fp_next_slot 경쟁 완화 효과. 라운드로빈 시작 포인터는 동시 삽입자들을 페이지 전반에 분산시키도록 설계됐지만, 이 문서는 그 효과를 정성적으로만 주장한다. N개 동시 COPY/INSERT 백엔드에서 고정 시작 대비 실제 버퍼 잠금 경쟁 감소량은 측정하지 않았다. 조사 경로: 합성 다중 쓰기 워크로드에서 fsm_search_avail 히트 분포를 계측.

2. 프로덕션에서 손상 자기 수리 경로가 실제로 얼마나 발동되는가. DEBUG1 "fixing corrupt FSM block"과 fsm_set_avail 재건은 크래시 후 찢긴 페이지를 위해 설계됐지만, 실제 빈도(그리고 양성 찢긴 페이지 손실보다 더 깊은 버그를 가리는 경우가 있는지)는 코드에서 알 수 없다. 조사 경로: data_checksums 켜짐 대 꺼짐 플리트에서 DEBUG1 발생률 수집.

3. 심한 변동 아래 오래된 상위 노드의 수렴 동작. fsm_search의 자기 교정 부모 갱신과 10000회 재시작 밸브가 루프를 한정하지만, 다음 FreeSpaceMapVacuum 전까지 상위 페이지가 얼마나 벗어날 수 있는지, 그리고 vacuum 간격 중간에 그 벗어남이 측정 가능한 오배치 / bloat를 유발하는지는 워크로드에 의존적이고 미측정이다. 조사 경로: 격렬한 변동 테이블 중간 vacuum 간격에 GetRecordedFreeSpace와 PageGetHeapFreeSpace를 비교 샘플링.

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

• Fork-as-separate-relation 모델 대 인라인 FSIP 페이지. PostgreSQL은 FSM을 자체 fork(FSM_FORKNUM)에 유지해 맵이 독립적으로 성장·축소되고 힙 페이지와 절대 섞이지 않는다. DB2의 FSIP와 Oracle의 freelist/ASSM 비트맵은 대신 고정 간격으로 테이블스페이스 안에 여유 공간 인벤토리 페이지를 끼워 넣는다. Fork 모델은 추가 smgr 열기와 두 번째 버퍼 집합 비용으로 더 깔끔한 절단 스토리를 얻는다(FreeSpaceMapPrepareTruncateRel이 fork를 힙과 함께 줄인다). Fork 관계 대 인라인 FSIP의 절단 및 크래시 복구를 나란히 비교하면 그 간접 계층이 주는 이점이 선명해질 것이다.

• CUBRID의 파일/익스텐트 여유 공간 관리. CUBRID는 페이지당 양자화 바이트 맵 + 페이지 내 이진 힙 방식이 아닌 파일 매니저/익스텐트 레벨에서 여유 공간을 추적한다. CUBRID의 할당 비트맵과 “numerable file” 섹터 어카운팅을 PostgreSQL의 lossy, 비WAL 바이트 맵과 비교하면 내구성/정밀도 트레이드오프의 틀이 잡힌다. CUBRID 구조는 복구 관리되는 할당 메타데이터인 반면, PostgreSQL FSM은 명시적으로 근사적인 자기 치유 힌트다. CUBRID 파일 매니저 분석은 cubrid 트리(raw/code-analysis/cubrid/file-manager-*)를 참조한다.

• 양자화 바이트 맵 대 정확한 여유 바이트 디렉터리. 256 카테고리 인코딩(FSM_CATEGORIES, FSM_CAT_STEP)은 의도적인 정밀도-크기 교환이다. 페이지당 바이트 하나는 1 TB 테이블 맵을 정확한 4바이트-per-page 디렉터리의 ~512 MB 대신 약 32 MB로 유지한다. 정확한 여유 카운트를 저장하는 엔진은 크기와 디렉터리 페이징 비용을 치른다. PostgreSQL은 약간 다른 크기의 두 요청이 같은 카테고리에 매핑될 수 있고 페이지 잠금 아래 재검사(hio.c의 PageGetHeapFreeSpace)가 반올림 오류를 잡는다는 것을 수용한다. FSM_CAT_STEP 세분도가 현실적인 튜플 크기 혼합에 유발하는 오배치율 정량화는 미측정 과제다.

• 비WAL 힌트 대 로깅된 할당 메타데이터 (ARIES 계보). WAL 로깅 거부(MarkBufferDirtyHint로 쓰기, RBM_ZERO_ON_ERROR로 읽기, 손상 시 재건)는 복구 스펙트럼의 한쪽 극단이다. ARIES 방식 시스템(Mohan et al. 1992; dbms-papers/aries.md)은 공간 맵/페이지 할당 변경에 WAL을 기록해 redo로 정확히 재구성 가능하게 한다. PostgreSQL은 대신 맵을 저렴하게 재도출 가능하게 만들고(VACUUM의 FreeSpaceMapVacuum이 상위 노드를 갱신하고, 힙 재검사가 리프를 즉석에서 수리한다) fsm_does_block_exist로 크래시 후 팬텀 항목을 허용한다. 유일한 WAL 예외인 XLogRecordPageWithFreeSpace는 redo 경로(힙/가시성 맵 재생)가 이미 알고 있는 FSM 값을 씨앗으로 심기 위해서만 존재한다. 각 FSM 자기 치유 수단을 의도적으로 포기한 ARIES 복구 보장에 매핑하는 집중 노트는 연구급 동반 자료가 될 것이다.

• 라운드로빈 fp_next_slot 대 파티션 / 백엔드별 할당. 공유 잠금 라운드로빈 시작 포인터는 삽입 지점 경쟁에 대한 PostgreSQL의 경량 대응이다. 더 무거운 방식들 — 백엔드별 자유 리스트, 해시 할당 영역, Oracle ASSM의 여러 freelist 그룹 — 은 bloat와 메타데이터 비용으로 경쟁을 더 줄인다. 다중 쓰기 COPY에서 fp_next_slot 팬아웃을 파티션 할당자와 비교 측정하는 것이 자연스러운 프론티어다(미해결 질문에서도 제기됨).

• 동일 기계로 인덱스 페이지 재활용 (indexfsm.c). 이진 비어 있음/사용 중 인코딩(BLCKSZ-1 대 0, 요청 BLCKSZ/2)으로 힙 FSM을 재사용하는 것은 우아한 경제성이지만, 인덱스 페이지 재사용이 FSM의 lossiness와 비내구성을 그대로 상속한다는 의미이기도 하다. 다른 엔진들은 인덱스 구조를 위해 별도의, 흔히 로깅되는 자유 페이지 리스트를 유지한다. 공유 FSM 방식이 인덱스 페이지 재사용을 측정 가능한 만큼 지연시키는 경우가 있는지(nbtree 자체의 재활용 가능성 게이트 대비, postgres-nbtree.md 참조)는 미측정 상호작용이다.

출처

트리 내 README와 소스 파일 (REL_18_STABLE, 커밋 273fe94)

• src/backend/storage/freespace/README — 설계 문서: 페이지당 맵 바이트 하나(BLCKSZ/256 단위), 페이지 내 이진 최대 힙, 페이지 간 팬아웃 트리, 탐색/갱신 연산, “좋은 특성” 논거, 잠금, 복구(WAL 없음, 찢긴 페이지 허용, 팬텀 블록 위험), 상위 레벨 구조/주소 지정 수학.
• src/backend/storage/freespace/freespace.c — 공개 API(GetPageWithFreeSpace, RecordAndGetPageWithFreeSpace, RecordPageWithFreeSpace, XLogRecordPageWithFreeSpace, GetRecordedFreeSpace), 카테고리 인코딩(fsm_space_avail_to_cat, fsm_space_needed_to_cat), 페이지 간 주소 지정(fsm_logical_to_physical, fsm_get_location, fsm_get_parent, fsm_get_child), 버퍼/확장 도우미(fsm_readbuf, fsm_extend), 탐색/갱신 드라이버(fsm_search, fsm_set_and_search), VACUUM(FreeSpaceMapVacuum/Range, fsm_vacuum_page), 절단(FreeSpaceMapPrepareTruncateRel), 크래시 후 가드(fsm_does_block_exist).
• src/backend/storage/freespace/fsmpage.c — 페이지 내 이진 힙 연산: leftchild/rightchild/parentof/rightneighbor 매크로, fsm_set_avail(리프 설정 + 버블업 + 오버플로 시 재건), fsm_get_avail, fsm_get_max_avail(루트 = fp_nodes[0]), fsm_search_avail(fp_next_slot 기점 탐색 삼각형 확장), fsm_truncate_avail, fsm_rebuild_page.
• src/backend/storage/freespace/indexfsm.c — GetFreeIndexPage, RecordFreeIndexPage, RecordUsedIndexPage, IndexFreeSpaceMapVacuum: 전체 인덱스 페이지를 위한 힙 FSM 이진 비어 있음/사용 중 재사용.
• src/include/storage/fsm_internals.h — FSMPageData(fp_next_slot, fp_nodes[FLEXIBLE_ARRAY_MEMBER]), NodesPerPage, NonLeafNodesPerPage, LeafNodesPerPage, SlotsPerFSMPage, fp_next_slot이 int인 이유.
• src/include/storage/freespace.h, src/include/storage/indexfsm.h — 힙과 인덱스 AM이 소비하는 선언된 공개 인터페이스.
• src/backend/access/heap/hio.c — RelationGetBufferForTuple: GetPageWithFreeSpace 호출, 페이지 잠금 아래 PageGetHeapFreeSpace 재검사, 미스 시 RecordAndGetPageWithFreeSpace 피드백.
• src/backend/access/heap/vacuumlazy.c — 페이지별 여유 공간을 기록하고 FreeSpaceMapVacuumRange를 트리거하는 VACUUM 드라이버(VACUUM_FSM_EVERY_PAGES).

논문과 교재 챕터

• Database Internals(Petrov, 2019) 1부 — 슬롯 페이지 레이아웃, 여유 공간 관리 디렉터리(비트맵, 페이지당 바이트, 트리 구조 맵), 정밀도-크기 / 힌트-내구성 틀(knowledge/research/dbms-general/).
• Database System Concepts(Silberschatz, Korth, Sudarshan, 7판) 저장·파일 구조 장 — 힙 파일 조직, 페이지 선택 문제, 자유 리스트/여유 공간 디렉터리 설계(knowledge/research/dbms-general/).
• Mohan, C. et al. (1992). “ARIES: A Transaction Recovery Method…” ACM TODS 17(1). FSM의 의도적 비WAL 로깅, 자기 치유 설계와 대조되는 로깅 복구 기준선(knowledge/research/dbms-papers/aries.md).

형제 문서 (교차 참조 — 해당 메커니즘은 저기서 소유, 여기서 중복하지 않음)

• postgres-heap-am.md — 힙 삽입 메커니즘. RelationGetBufferForTuple은 FSM 상호작용만 요약하며 전체 재시도/확장 프로토콜은 다루지 않는다.
• postgres-smgr-md.md — fsm_readbuf와 fsm_extend가 탑승하는 smgr/md fork I/O 계층(FSM_FORKNUM, RBM_ZERO_ON_ERROR, 관계 확장).
• postgres-vacuum.md — RecordPageWithFreeSpace와 FreeSpaceMapVacuumRange 호출 빈도를 소유하는 VACUUM 드라이버(lazy_scan_heap). 이 문서는 fsm_vacuum_page 자체만 다룬다.
• postgres-nbtree.md — 삭제된 btree 페이지가 RecordFreeIndexPage로 기록되고 GetFreeIndexPage로 돌아올 시점을 결정하는 인덱스 페이지 재활용 가능성 게이트.
• postgres-buffer-manager.md — MarkBufferDirtyHint, 콘텐츠 잠금, FSM의 공유/배타 페이지 접근이 의존하는 핀/잠금 프로토콜.
• postgres-page-layout.md — PageGetHeapFreeSpace와 페이지의 “여유 공간”이 정확히 무엇을 의미하는지 정의하는 슬롯 페이지 모델.