Run pgbench's transaction on a bank of 100,000 accounts, beside SQLite (090)

benchmarks/bank/bank.aup keeps accounts, tellers and branches as keyed
lists and a history list; a transfer changes a row of each and appends a
history row in one event, as pgbench's TPC-B-like transaction does in
SQL. run.py makes a scale's rows and drives transfers through the load
generator's new transfer kind; sqlite-bank.c runs the same tables and
SQL on SQLite 3.46.1, a connection a thread, WAL.

With lists as trees, transfers run at 30.5k a second on 1,000 accounts
and 24.5k on 100,000 (RAM store, one connection thread, HTTP and JSON
included), where they ran at 3.2k on 30,000 before. Durable on the SD
card, Pure makes 1,339 a second and SQLite with synchronous=FULL 84 to
153. SQLite in process with no HTTP makes about 40k in RAM: recorded as
it is, with the write amplification of 100,000-row tables on the card
and ad hoc queries as what comes next.

1 files changed, 99 insertions, 0 deletions

diff --git a/docs/research/090-tables.md b/docs/research/090-tables.md
new file mode 100644
index 0000000..f7dbbff
--- /dev/null
+++ b/docs/research/090-tables.md
@@ -0,0 +1,99 @@
+# 090 — 표 크기의 상태: 목록을 영속 트리로
+
+2026-09-27. 외부 피드백 002의 둘째 항목에 답하려고 한 것. 피드백은 Pure가 "키-값 단일 상태 전이에서만 빠르다"는 인상을 깨야
+한다고 했다. SQLite나 Postgres가 하는 여러 표에 걸친 범용 트랜잭션을 같은 기기에서 겨루려다가, 그 인상이 인상만이 아니었음을
+먼저 찾았다.
+
+착수 기준:
+
+- 바꿀 결정: 앱의 상태를 이루는 목록(레코드의 리스트, 키로 정렬된 리스트)을 지금처럼 작은 크기에 맞춘 채 둘지, 표 크기(수십만
+  행)에서도 변경과 스냅숏이 행 수와 무관하게 되도록 바꿀지.
+- 최소 확인: 표준 OLTP 부하(pgbench의 TPC-B 같은 트랜잭션)를 aup 앱으로 쓰고, 계좌 수를 늘려 가며 처리량과 요청당 CPU를
+  잰다. 무작위 모델 대조 검사로 트리의 변경, 되돌리기, 스냅숏 공유, 저장본을 지킨다.
+- 중단 기준: 작은 목록의 앱(할 일, 점수판)이 느려지거나 메모리를 더 쓰면 되돌린다.
+
+## 찾은 것
+
+`benchmarks/bank/bank.aup`는 은행이다. 계좌·창구·지점이 키로 정렬된 목록이고, 이력은 목록이다. 이체 하나가 세 표의 한 행씩을
+바꾸고 이력에 한 행을 더한다. 한 이벤트, 곧 한 트랜잭션이다. 연결 스레드 하나, 클라이언트 16, RAM 저장소에서 쟀다.
+
+| 계좌 수 | 설정 | 이체/s | 이체당 CPU |
+|---:|---:|---:|---:|
+| 1,000 | 0.16 s | 7,870 | 118 µs |
+| 10,000 | 2.05 s | 6,371 | 147 µs |
+| 30,000 | 12.6 s | 3,245 | 299 µs |
+| 100,000 | 만들 수 없음 | — | — |
+
+작은 GET이 요청당 7 µs인데 1,000행에서 이미 118 µs였고, 설정 시간은 행 수의 제곱으로 늘었다. 원인은 셋이다.
+
+- 목록이 항목 포인터 배열 하나였다. 저장본(드래프트)에서 한 항목의 바이트 위치는 **앞 항목들의 크기를 모두 더해** 구했다.
+  바꿀 때마다, 이력에 한 행을 더할 때마다 O(n)이다.
+- 스냅숏(080)이 바뀐 목록의 **포인터 배열 전체를 복사**했다. 저장마다 O(n)이다.
+- 목록은 65,536 항목까지였고, 목록의 저장본은 문서 하나라서 문서 한도(1.38 MiB)에 묶였다. 28바이트 계좌는 51,785개가 끝이다.
+
+## 한 것
+
+**영속 계수 B+트리(`core/module-list.c`).**
+
+- 항목은 팬아웃 32의 B+트리 잎에 있다. 노드마다 아래 항목 수, 그 저장 바이트 수, 첫 항목을 안다. 위치로 찾기, 키로 찾기
+  (노드마다 자식의 첫 키로 이분 탐색), 저장본에서의 위치가 모두 O(log n)이다.
+- 노드는 항목처럼 만들어질 때의 공유 횟수를 적는다. 마지막 공유보다 먼저 만들어진 노드는 스냅숏이 읽을 수 있다. 그래서
+  목록은 그런 노드를 바꾸지 않고, 바꿀 곳까지의 경로를 복사한 뒤 옛 노드를 은퇴시킨다. 은퇴한 노드는 항목과 같은 길로
+  풀린다(그 노드를 읽을 수 있는 스냅숏이 다 풀린 뒤). 공유는 루트와 개수를 넘기는 O(1)이다.
+- 경로 복사는 바꾸려던 일이 실패해도 목록의 판을 올린다. 그러지 않으면 다음 스냅숏이 판이 같다고 옛 사본을 다시 쓰고, 이미
+  은퇴해 풀린 노드를 읽는다.
+- 위치 순서로 읽는 보기와 집계(`each`, `sum ... for`)는 스레드마다의 손가락이 받는다(마지막 잎과 그 시작 위치). 다음 위치가
+  대개 같은 잎에 있다.
+- 되돌리기는 기록한 변경을 거꾸로 적용한다(위치 기반, O(log n)). 되돌리며 다시 넣을 항목에 노드 분할이 필요한데 메모리가
+  없으면 프로세스를 멈춘다. 이벤트를 반쯤 남기지 않고, 저장소에는 마지막 저장이 남는다.
+- 목록 한도는 1,600만 항목(2^24)이다.
+
+**상태 한도(`core/store.h`).** 런타임이 소유하는 값(키가 `.`로 시작하는 상태, 키 없는 메모리 드래프트)은 1 GiB까지 자란다.
+호스트가 통째로 나르는 문서(HTTP 본문)는 전처럼 1.38 MiB다. 저장소 형식은 그대로다(잎 4 KiB, 팬아웃 32, 높이 12까지).
+
+**검사.** `core/test-module.c`의 `list_trees`는 모델 배열과 목록을 나란히 둔다. 6,000 이벤트를 삽입·삭제·필드 변경으로 채우고,
+무작위로 1,195개를 되돌리고 나머지를 확정한다. 목록은 8,983 항목까지 자라고 다시 준다(트리 세 층). 저장본은 50 이벤트마다
+모델의 인코딩과 바이트까지 같다. 스냅숏 넷을 번갈아 들고, 그 뒤의 변경에도 공유한 내용이 그대로인지 본다. 키 목록 13,959
+항목에서 모든 키 탐색이 모델의 이분 탐색과 같다. 기존의 앱 모델 검사(목록 변경 퍼즈, 스레드의 스냅숏 읽기, 저장 동등성, 충돌,
+이전)와 함께 ASan·UBSan 빌드에서도 통과한다. `make check`의 서버 검사 18개, Vega의 검사도 통과한다.
+
+## 장치가 말한 것
+
+**RAM 저장소(CPU).** 같은 부하, 같은 설정([run.py](../../benchmarks/bank/run.py),
+[원시 결과](../../research/experiments/016-tables/2026-09-27-bank-linux-aarch64.jsonl)).
+
+| 계좌 수 | 설정 | 이체/s | 이체당 CPU | 전과 비교 |
+|---:|---:|---:|---:|---:|
+| 1,000 | 0.16 s | 30,546 | 24.0 µs | 3.9× |
+| 10,000 | 1.47 s | 27,737 | 27.1 µs | 4.4× |
+| 30,000 | 4.46 s | 26,413 | 29.1 µs | 8.1× |
+| 100,000 | 15.5 s | 24,485 | 32.1 µs | (전에는 불가) |
+
+행이 100배가 되어도 처리량은 20% 준다(log n). 설정 시간은 파이썬 클라이언트의 속도다(초당 약 6,500 POST).
+
+같은 트랜잭션을 SQLite 3.46.1에서 쟀다([sqlite-bank.c](../../benchmarks/bank/sqlite-bank.c): pgbench의 표와 SQL, 스레드마다
+연결, `BEGIN IMMEDIATE`, WAL). RAM에서 16스레드 초당 약 40,000건이다. SQLite는 프로세스 안에서 돌고 HTTP가 없다. Pure의 수는
+루프백 HTTP와 JSON 해석을 포함한다(요청 하나에 커널 시간이 CPU의 약 70%다, 087). CPU만 보면 SQLite가 앞선다.
+
+**SD 카드(내구).** 둘 다 커밋이 동기화된 뒤에 답한다. SQLite는 WAL에 `synchronous=FULL`, Pure는 이벤트 묶음마다 동기화 한 번이다.
+10만 계좌.
+
+| | 이체/s | p50 | p99 |
+|---|---:|---:|---:|
+| Pure, 16연결 | **1,339** | 4.9 ms | 156 ms |
+| Pure, 64연결 | 962 | 8.2 ms | 590 ms |
+| SQLite FULL, 1스레드 | 153 | 1.8 ms | 86 ms |
+| SQLite FULL, 16스레드 | 141 | 2.3 ms | 6.0 s |
+| SQLite FULL, 64스레드 | 84 | 4.1 ms | 9.4 s |
+
+내구성을 같게 두면 Pure가 6–11배다. 그룹 커밋 덕분이다. SQLite의 `NORMAL`(최근 커밋을 전원 차단에 잃을 수 있다)이 Pure의 내구
+처리량과 비슷하다(초당 1,243건).
+
+## 다음
+
+- **쓰기 증폭.** 64연결이 16연결보다 느리다. 10만 행 표는 문서 하나로 저장된다. 그래서 커밋마다 무작위로 바뀐 행이 든 4 KiB
+  잎을 다시 쓰고, 묶음이 클수록 잎이 는다. 페이지 단위 복사(LMDB·SQLite WAL과 같은 비용)다. 목록의 변경을 행 단위 redo
+  기록으로 커밋하고 저장본은 나중에 한 번에 고치면(체크포인트), 커밋마다 쓰는 바이트가 행 크기가 된다.
+- **임의 질의.** 보기는 모듈에 미리 선언된 것뿐이다. 조인(키 조회), 필터, 집계는 된다. 실행 중에 새 질의를 보내 검증한 뒤
+  스냅숏에서 돌리는 길이 다음이다.
+- **대량 적재.** 10만 행을 이벤트 10만 개로 만든다. 표를 한 번에 들이는 길이 필요하다.