diff options
Diffstat (limited to 'docs/research/090-tables.md')
| -rw-r--r-- | docs/research/090-tables.md | 99 |
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만 개로 만든다. 표를 한 번에 들이는 길이 필요하다. |