Check TPC-C's consistency from one snapshot a side, and measure TPC-C on RAM and an SD card

1 files changed, 187 insertions, 0 deletions

diff --git a/docs/research/092-tpcc.md b/docs/research/092-tpcc.md
new file mode 100644
index 0000000..fec38f4
--- /dev/null
+++ b/docs/research/092-tpcc.md
@@ -0,0 +1,187 @@
+# 092 — TPC-C: 같은 트랜잭션, 같은 상태, RAM에서 SQLite의 4배, SD 카드에서 56배
+
+2026-09-28. 외부 피드백 002의 둘째 항목(범용성)의 마지막 조각. [090](090-tables.md)이 표 크기의 상태와 한 트랜잭션,
+[091](091-queries.md)이 임의 질의를 세웠다면, 여기서는 OLTP의 표준 부하인 TPC-C의 다섯 트랜잭션(New-Order, Payment,
+Order-Status, Delivery, Stock-Level)을 aup 앱 하나로 쓰고, 같은 트랜잭션을 SQL로 쓴 SQLite와 겨룬다. 키-값이 아닌 일반
+트랜잭션이다. 한 트랜잭션이 아홉 표 가운데 여러 표를 읽고, 행을 여럿 바꾸고, 목록을 조각내 훑고, 실패하면 통째로
+되돌려진다.
+
+착수 기준:
+
+- 바꿀 결정: TPC-C를 앱 코드로 쓸 수 있는가(언어), 같은 입력에서 SQLite와 같은 상태로 끝나는가(의미), 그리고 어디서
+  느린가(런타임과 저장). 표현이 모자라면 aup를, 느리면 런타임을, 저장이 막으면 저장소를 고친다.
+- 최소 확인: 같은 입력열(한 터미널, 같은 시드)을 두 쪽에 주고 모든 표의 모든 행을 비교한다(시간만 빼고). 그 뒤에 RAM과 SD
+  카드에서 트랜잭션 비율 45/43/4/4/4로 처리량과 지연을 잰다. 두 쪽 모두 커밋마다 동기화한다(SQLite는 WAL과
+  `synchronous=FULL`).
+- 중단 기준: 상태가 한 행이라도 다르면 재지 않는다.
+
+## TPC-C를 aup로
+
+[tpcc.aup](../../benchmarks/tpcc/tpcc.aup)는 표 아홉 개를 키 있는 목록으로 두고 복합 키를 수 하나로 접는다(구역
+`w*10+d`, 고객 `구역*3000+c`, 주문 `구역*10^7+o`, 주문 줄 `주문*16+번호`, 재고 `w*100000+i`). 다섯 트랜잭션은 규격 2절의
+절차 그대로다. New-Order는 구역의 다음 주문 번호를 올리고, 줄마다 상품 가격을 읽고, 재고를 줄이거나 채우고, 주문 줄을
+넣는다. 없는 상품(주문의 1%)이 나오면 이벤트가 실패하고 그때까지의 변경이 모두 되돌려진다. Delivery는 구역의 가장 오래된
+미배송 주문의 줄들을 조각(`lines[주문*16 .. 주문*16+16]`)으로 훑어 금액을 더한다. Stock-Level은 구역의 마지막 20 주문의
+줄을 조각으로 훑어 재고가 기준보다 적은 상품을 중복 없이 센다(`distinct`).
+
+```aup
+on new_order {
+  let district = districts[new_order.w * 10 + new_order.d]
+  let customer = customers[district.id * 3000 + new_order.c]
+  let order = district.id * 10000000 + district.next_order
+  district.next_order = district.next_order + 1
+  let local = 1
+  let count = 0
+  for l in new_order.lines {
+    let price = items[l.item].price
+    let s = stock[l.supply * 100000 + l.item]
+    if s.quantity >= l.quantity + 10 {
+      s.quantity = s.quantity - l.quantity
+    } else {
+      s.quantity = s.quantity - l.quantity + 91
+    }
+    ...
+    lines.add(Line { id: order * 16 + count, item: l.item, supply: l.supply, quantity: l.quantity,
+                     amount: l.quantity * price })
+  }
+  orders.add(Order { id: order, customer: customer.id, entry: now, lines: count, local: local })
+  new_orders.add(NewOrder { id: order })
+  customer.last_order = order
+}
+```
+
+규격과 다른 점: 고객은 늘 번호로 고른다(성으로 고르지 않는다). 트랜잭션이 읽기만 하는 문자열(이름·주소·데이터)은 뺐다.
+고객은 마지막 주문을 기억한다(Order-Status가 가장 큰 주문 번호를 찾는 대신). Delivery는 구역 하나가 이벤트 하나다
+(2.7.4가 허용). 생각 시간과 입력 시간이 없으므로 수는 tpmC가 아니다(New-Order 수는 적는다). SQLite 쪽
+([sqlite-tpcc.c](../../benchmarks/tpcc/sqlite-tpcc.c))은 규격의 표와 복합 기본 키(`WITHOUT ROWID`)를 쓰고, 같은 차이를
+같은 SQL로 둔다. 터미널마다 연결 하나, 쓰기는 `BEGIN IMMEDIATE`, 읽기(Order-Status, Stock-Level)는 스냅숏 하나에서 한다.
+
+## 같은 트랜잭션, 같은 상태
+
+[run.py](../../benchmarks/tpcc/run.py)는 두 드라이버가 같은 순서로 난수를 뽑게 한다. 한 터미널과 같은 시드면 두 쪽에
+정확히 같은 트랜잭션이 간다. 그 뒤 Pure의 상태는 등록한 질의(`PUT /queries`)로, SQLite의 상태는 SELECT로 읽어 표마다 모든
+행을 비교한다. 이 비교가 처음 잡은 것은 SQLite 드라이버의 버그였다. `sqlite3_bind`를 `reset` 전에 불러 바인딩이 무시됐고
+(`SQLITE_MISUSE`), 구역 번호가 첫 New-Order의 것으로 굳었다. 고친 뒤 2만 트랜잭션(RAM)과 2천 트랜잭션(SD)에서 **아홉
+표의 모든 행이 같다**(주문 9,036, 결제 8,518, 되돌린 주문 90이 두 쪽 모두 같다). 규격 3.3.2의 일관성 조건(창고 YTD = 구역
+YTD 합, 구역의 다음 주문 = 최신 주문 = 최신 미배송 주문 + 1, 미배송 주문 수 = 번호 범위, 주문의 줄 수 합 = 주문 줄 수)은 두
+쪽 모두 모든 측정 뒤에 성립한다.
+
+## 찾은 것
+
+첫 측정(RAM, 16터미널)에서 Pure는 초당 4,858건이었다. 같은 RAM에서 SQLite(프로세스 안, HTTP 없음)는 9,504건이었다. Pure는
+트랜잭션당 CPU를 213 µs 썼다. 샘플러([sample.c](../../benchmarks/sample.c))가 보인 것은 트랜잭션이 아니라 **저장**이었다.
+libc의 memcpy가 41%였고, 트리 저장소의 편집(`chunk_bytes`, `children`, `digest_add`, `write_subtree`)이 그 뒤를 이었다. 목록의
+저장본은 트리 저장소의 문서 하나였고, 필드 하나(8바이트)가 바뀔 때마다 그 문서를 경로 복사로 고쳤다. 4 KiB 잎 하나와
+층마다 자식 배열을 복사하는 일이다. New-Order 하나가 그런 편집을 40–60번 했다. 저장본 반영을 꺼 본 실험에서는 16,210건이
+나왔다. 비용의 70%가 저장이었다.
+
+## 바꾼 것
+
+**1. 목록의 변경을 기록으로(저널).** 목록 연산은 메모리의 항목을 바꾸고 몇 바이트짜리 기록만 남긴다(종류 u8, 위치 u32,
+삽입이면 항목, 설정이면 필드와 값). 이벤트가 실패하면 기록을 표시한 길이로 자르고, 저장은 기록을 붙인다. 이것으로 13,820건.
+
+**2. 안내 노드.** 남은 비용은 B+트리 탐색이었다(`pure_list_seek` 25%). 내부 노드의 이진 탐색이 탐침마다 자식 머리와 그 첫
+잎을 따라가 캐시 미스를 두 번 냈고, 위치로 찾을 때는 자식 32개의 항목 수를 하나씩 역참조했다. 내부 노드가 이제 자식 옆에
+안내(guide)를 둔다. 자식마다 앞선 항목 수(누적)와 첫 키다. 빈 칸은 어떤 위치·키보다 크게 채워, 한 층을 길이가 고정된
+분기 없는 이진 탐색(조건부 선택)으로 찾는다. 큰 목록(13만 항목 초과)의 잎은 키 줄 네 개를 한꺼번에 가져온다. 키 필드가
+아닌 필드의 설정은 스레드의 손가락(마지막 잎)이 공유되지 않은 잎을 가리키면 그 자리에서 바꾼다. 무작위 탐색 시간:
+
+| 항목 | 전 | 후 |
+|---:|---:|---:|
+| 1,000 | 129 ns | 46 ns |
+| 30,000 | 193 ns | 73 ns |
+| 300,000 | 384 ns | 200–233 ns |
+| 1,000,000 | 667 ns | 252 ns |
+
+**3. 수의 읽기와 쓰기.** JSON의 수는 strtod로, 답의 정수 아닌 수는 정밀도 1–17을 차례로 `snprintf`+`strtod`로 시험해 썼다.
+읽기는 이제 Clinger의 빠른 길을 쓴다. 가수 < 2^53이고 10의 지수가 22 이하면 곱셈이나 나눗셈 한 번이 정확히 반올림한다.
+쓰기는 소수 k자리 정수 m을 고른다. 곱의 정확한 오차를 `fma`로 구해 가장 가까운 m을 찾고, m/10^k가 값으로 돌아오면 그 자리가
+`%g`의 자리다. 딱 절반이면 옛 길로 간다. 무작위 값 300만 개(쓰기)와 900만 개(읽기)에서 옛 결과와 비트 단위로 같다
+([test-message-json.c](../../serve/test-message-json.c), `number_texts`).
+
+**4. 모으기는 장치가 기다린 만큼.** 스레드별 CPU를 재니 소유자는 72%만 일하고 있었다. 저장한 라운드 뒤 소유자는 돌아오는
+요청을 모으려고 최대 1 ms(100 µs 조용할 때까지) 기다렸다([081](081-tail-records.md)). 동기화가 수 ms인 SD 카드에서는 저장
+한 번에 더 담게 해 주지만, 동기화가 공짜인 RAM에서는 쉬는 시간이다. 이제 모으는 시간은 직전 저장이 장치를 기다린 시간(벽
+시계 시간에서 스레드 CPU 시간을 뺀 것)을 넘지 않는다. 16/64/128터미널에서 17.9k/25.6k/30.1k건이 22.8k/31.8k/35.8k건이 됐다.
+
+**5. SD 카드가 말한 것.** 같은 저장 구조로 SD 카드에서 재자 30초 가운데 16초 동안 처리가 0이었다. `strace`로 보니 트리
+저장소의 압축이었다. 살아 있는 데이터(25 MB)에 다음 주기의 0 채움까지 42 MB를 새 파일에 쓰고 한 번에 `fsync`했는데, 그
+`fsync`가 10초를 넘겼다. 이 카드는 처음 약 16 MB를 초당 29 MB로 받고 그 뒤로는 **초당 3–8 MB**로 떨어진다. 64 MB를 쓰고
+동기화하는 데 20초가 걸렸다. 커밋의 동기화 지연은 제자리 덮어쓰기 p50 1.2 ms, 파일 끝 덧붙이기 p50 4.5 ms(p90 25 ms)다. 목록
+문서에 기록을 붙이는 방식도 커밋마다 목록마다 꼬리 잎(최대 4 KiB)과 경로를 다시 써서 쓰레기를 계속 만들었고, 그것이 압축을
+불렀다. 수십 MB를 커밋 경로에서 한 번에 쓰는 설계는 이 장치에서 수 초의 정지가 된다.
+
+**6. 이미지와 로그.** 그래서 목록은 트리를 떠났다([008](../design/008-module-format.md) 상태 영속,
+[log.h](../../core/log.h), [store-log.c](../../store/store-log.c)).
+
+- **로그.** 목록을 바꾼 저장마다 항목 하나를 구간 파일(`log-0`, `log-1`, ...)에 붙이고 동기화한다. 구간은 처음 만들 때 통째로
+  할당하고, 이미지가 모두 담은 항목만 가진 구간은 다시 쓴다. 그래서 덧붙이기는 파일을 키우지도 새 블록을 받지도 않고,
+  동기화가 데이터만 쓴다. 항목은 저장 번호, 앞 항목의 번호와 **다이제스트**, 트리도 커밋했는지, 페이로드(바뀐 목록마다 이름과
+  기록)다. 번호는 건너뛰고(목록을 바꾸지 않은 저장) 다시 쓰이므로(거둔 항목), 항목은 번호가 아니라 앞 항목의 다이제스트로
+  이어진다. 구간은 고유한 세대와 이어받는 구간의 세대를 머리에 적는다. 그래서 찢긴 쓰기도, 재사용한 구간에 남은 옛 바이트도
+  이어지지 않는다.
+- **이미지.** 목록의 항목을 파일 하나(`image-이름`)에 통째로 쓴다. 옆에 써서 동기화하고 이름을 바꿔 끼우며, 파일 전체를
+  다이제스트로 확인한다. 이미지는 자기가 담은 저장 번호를 적고, 시작은 이미지를 읽은 뒤 그 번호 뒤의 기록만 다시 한다. 쓰기는
+  256 KiB씩 장치로 흘려보낸다(`sync_file_range`). 그래서 로그의 동기화는 기다릴 것이 적다.
+- **체크포인트.** 목록의 로그 기록이 항목 바이트(최소 1 MiB)를 넘으면 스냅숏에서 이미지를 새로 쓴다. 로그 전체가 모든 목록의
+  항목 바이트(최소 64 MiB)를 넘어도, 로그를 가장 오래 붙잡은 목록의 이미지를 쓴다. pure-serve는 이것을 소유자 밖의 스레드에서
+  한다. 목록이 스냅숏에서 공유되므로 이미지를 쓰는 동안에도 소유자는 계속 이벤트를 적용한다. 목록은 로그에 변경이 적히기 전에
+  이미지를 가진다. 그래서 기록은 언제나 그 목록 이미지의 필드로 읽힌다.
+- **원자성.** 로그 항목이 있고 트리도 커밋하는 저장(수·text·링크·문서도 바꾼 저장)은 번호를 트리의 상태 `seq`에 함께 쓴다.
+  트리도 커밋하는 저장의 항목은 트리가 그 번호(이상)를 가질 때만 센다. 그래서 로그를 먼저 쓰고 트리를 커밋하는 사이에
+  죽어도 둘 다 남거나 둘 다 없다. 트리 커밋이 확실히 실패하면 항목을 거두고, 다음 저장이 같은 번호로 그 자리에 쓴다.
+  동기화가 실패해 저장 여부를 모르면(불확실) 앱은 다시 시작할 때까지 저장하지 않는다.
+- **검증.** [test-log.c](../../store/test-log.c)는 로그를 항목의 모델과 겨룬다. 크기(구간을 넘는 것까지), 거두기, 해제,
+  끝 자르기, 다시 열기를 6,000단계 섞고(다시 열기 1,045번), 시드 40개를 ASan·UBSan으로 돌린다. 구간 파일은 15개를 넘지
+  않는다. [test-module.c](../../core/test-module.c)는 저장 앱과 메모리 앱을 같은 무작위 이벤트로 돌리며 수시로 다시 시작해,
+  체크포인트가 끼어도 매 단계 같음을 본다. 프로세스를 커밋의 모든 단계(로그 쓰기 전, 로그 동기화 전, 트리의 각 단계)에서
+  죽여도, 다시 시작하면 전부 이전 아니면 전부 이후다. 실패(죽지 않고)는 그 저장만 없던 일이 되고, 불확실은 다시 시작할
+  때까지 저장을 막는다. 이전 형식(`PLS1`, `PLS2`)의 저장소는 시작할 때 이미지로 옮겨진다.
+
+## 측정
+
+W=1(창고 하나, 초기 행 약 57만), Raspberry Pi 5(4코어), 서버는 코어 0–2, Pure의 부하 생성기
+([tpcc-load.c](../../benchmarks/tpcc/tpcc-load.c), HTTP/1.1과 JSON)는 코어 3. SQLite 3.46.1은 코어 0–2에서 프로세스 안으로
+돈다(HTTP도 JSON도 없다). 20초(RAM)와 30초(SD), 원시 결과는 [018-tpcc](../../research/experiments/018-tpcc/).
+
+**RAM(tmpfs).** 동기화가 공짜이므로 CPU를 겨룬다.
+
+| | 초당 트랜잭션 | 분당 New-Order | New-Order p50 / p99 | 트랜잭션당 서버 CPU |
+|---|---:|---:|---:|---:|
+| Pure, 16터미널 | 35,863 | 959,979 | 0.45 / 1.3 ms | 45.5 µs |
+| Pure, 64터미널 | 38,564 | 1,031,566 | 1.7 / 3.8 ms | 48.7 µs |
+| Pure, 128터미널 | **39,449** | 1,052,334 | 3.3 / 7.4 ms | 50.0 µs |
+| SQLite FULL, 1스레드 | 9,493 | 254,310 | 0.15 / 1.2 ms | |
+| SQLite FULL, 4스레드 | 9,141 | 244,796 | 0.16 / 1.2 ms | |
+
+16터미널은 바꾸기 전 4,858건에서 7.4배가 됐다. 트랜잭션당 CPU는 213 µs에서 45.5 µs로 줄었다. 이 CPU에는 HTTP와 JSON이
+들어 있다. 적재(57만 행)는 Pure 0.72초(이진 행을 한 요청에 1.4 MB씩), SQLite 1.56초(파이썬 `executemany`)다.
+
+**SD 카드(ext4).** 두 쪽 모두 커밋이 장치에 닿은 뒤 답한다.
+
+| | 초당 트랜잭션 | 분당 New-Order | New-Order p50 / p99 |
+|---|---:|---:|---:|
+| Pure, 16터미널 | 1,465 | 39,149 | 5.6 / 74 ms |
+| Pure, 64터미널 | 3,008 | 80,545 | 8.7 / 221 ms |
+| Pure, 128터미널 | **3,073** | 82,063 | 11.8 / 623 ms |
+| SQLite FULL, 1스레드 | 37 | 1,012 | 5.1 / 557 ms |
+| SQLite FULL, 4스레드 | 55 | 1,425 | 5.1 / 1,245 ms |
+
+카드는 상태에 따라 흔들린다. 같은 카드에서 세 번 잰 128터미널은 3,073–5,396건, SQLite FULL은 48–57건이었다. 로그로 옮기기
+전(목록을 트리에 두던 때)에는 30초 가운데 16초가 0이었고, 이제는 매초 처리한다.
+
+SQLite의 `synchronous=NORMAL`(WAL 체크포인트 때만 동기화해 전원이 끊기면 최근 커밋을 잃는다)은 초당 36건(1스레드),
+372건(4스레드)이다. `OFF`(동기화 없음)는 8,941건이다. Pure는 내구성을 낮추지 않고도 NORMAL의 8배다.
+
+## 다음
+
+- **기록을 더 작게.** 로그는 트랜잭션당 약 0.52 KB다. 이 카드의 지속 쓰기(초당 3–8 MB)에 닿는 양이다. 수가 모두
+  binary64(8바이트)로 적히지만 TPC-C의 값은 대부분 작은 정수다. 정수를 가변 길이로 적고 한 저장에서 같은 항목의 여러 설정을
+  한 기록으로 합치면 절반 아래로 준다.
+- **덧붙는 목록의 이미지.** 주문 줄처럼 뒤에 붙기만 하는 목록도 체크포인트가 이미지 전체를 다시 쓴다. 바뀐 잎만 새로 쓰는
+  이미지(이전 이미지와 잎을 나눠 쓰는)가 다음이다.
+- **메모리.** 16/64/128터미널을 차례로 20초씩 돌린 뒤 서버의 상주 메모리는 0.5/0.9/1.3 GB다. 대부분 늘어난 주문 줄(약 1,000만
+  행)이지만 데이터의 약 두 배다. 잎의 채움과 스냅숏이 붙잡는 옛 잎을 잴 것.
+- **W > 1과 진짜 tpmC.** 창고가 여럿이면 원격 재고·원격 결제가 생기고, 생각 시간을 두면 규격의 tpmC가 된다.
+- **트리 저장소의 압축.** 목록은 이제 트리를 쓰지 않지만 문서와 text는 쓴다. 압축은 여전히 커밋 경로에서 살아 있는 데이터를
+  통째로 복사한다. 배경에서 복사하고 그동안의 커밋만 옮기는 압축이 필요하다.