1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
# 092 — TPC-C: 같은 트랜잭션, 같은 상태, RAM에서 SQLite의 4배, SD 카드에서 90배
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`)의 저장소는 시작할 때 이미지로 옮겨진다.
**7. 기록을 작게.** 첫 SD 측정의 로그는 트랜잭션당 약 0.52 KB였고, 이 카드의 지속 쓰기(초당 3–8 MB)가 한계였다. 수가
모두 binary64(8바이트)로 적혔지만 TPC-C의 값은 대부분 작은 정수다. 기록은 이제 위치를 varint로, 크기가 2^53 미만인
정수를 zigzag varint로, 그 밖의 수를 표시 1바이트와 8바이트로, text 길이를 varint로 적는다. 주문 줄 삽입은 53바이트에서 약
24바이트로, 재고 필드 설정은 14바이트에서 약 7바이트로 준다. 수는 비트 그대로 돌아온다(-0, 2^53의 경계, 비정규 수까지).
기록이 항목보다 작아져 뒤에 붙기만 하는 목록은 기록 크기 규칙에 닿지 않는다. 그런 목록의 이미지는 로그 크기 규칙이 쓴다.
## 측정
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터미널 | 36,697 | 982,183 | 0.45 / 1.0 ms | 44.3 µs |
| Pure, 64터미널 | 38,509 | 1,029,948 | 1.7 / 4.1 ms | 47.3 µs |
| Pure, 128터미널 | **39,977** | 1,066,231 | 3.2 / 6.7 ms | 49.2 µs |
| SQLite FULL, 1스레드 | 9,529 | 255,250 | 0.15 / 1.1 ms | |
| SQLite FULL, 4스레드 | 9,037 | 242,158 | 0.16 / 1.2 ms | |
16터미널은 바꾸기 전 4,858건에서 7.6배가 됐다. 트랜잭션당 CPU는 213 µs에서 44.3 µs로 줄었다. 이 CPU에는 HTTP와 JSON이
들어 있다. 적재(57만 행)는 Pure 0.71초(이진 행을 한 요청에 1.4 MB씩), SQLite 1.56초(파이썬 `executemany`)다.
**SD 카드(ext4).** 두 쪽 모두 커밋이 장치에 닿은 뒤 답한다.
| | 초당 트랜잭션 | 분당 New-Order | New-Order p50 / p99 |
|---|---:|---:|---:|
| Pure, 16터미널 | 1,743 | 46,471 | 5.4 / 59 ms |
| Pure, 64터미널 | 3,237 | 86,604 | 9.2 / 147 ms |
| Pure, 128터미널 | **4,502** | 120,121 | 15.4 / 246 ms |
| SQLite FULL, 1스레드 | 50 | 1,346 | 4.9 / 492 ms |
| SQLite FULL, 4스레드 | 44 | 1,181 | 4.9 / 1,704 ms |
카드는 상태에 따라 흔들린다. 압축 기록으로 128터미널을 세 번 재니 4,502–6,824건이었다(그 전에는 3,073–5,396건).
SQLite FULL은 44–57건이었다. 로그로 옮기기 전(목록을 트리에 두던 때)에는 30초 가운데 16초가 0이었다. 이제는 매초 처리한다.
SQLite의 `synchronous=NORMAL`(WAL 체크포인트 때만 동기화해 전원이 끊기면 최근 커밋을 잃는다)은 초당 36건(1스레드),
372건(4스레드)이다. `OFF`(동기화 없음)는 8,941건이다. Pure는 내구성을 낮추지 않고도 NORMAL의 12배다.
## 다음
- **기록을 더 작게.** 한 저장 안에서 같은 항목의 설정 여럿(재고의 수량·누계·주문 수)을 한 기록으로 합치고, 이미지도
압축 형식으로 쓰면 SD 카드의 쓰기가 더 준다.
- **덧붙는 목록의 이미지.** 주문 줄처럼 뒤에 붙기만 하는 목록도 체크포인트가 이미지 전체를 다시 쓴다. 바뀐 잎만 새로 쓰는
이미지(이전 이미지와 잎을 나눠 쓰는)가 다음이다.
- **메모리.** 16/64/128터미널을 차례로 20초씩 돌린 뒤 서버의 상주 메모리는 0.5/0.9/1.3 GB다. 대부분 늘어난 주문 줄(약 1,000만
행)이지만 데이터의 약 두 배다. 잎의 채움과 스냅숏이 붙잡는 옛 잎을 잴 것.
- **W > 1과 진짜 tpmC.** 창고가 여럿이면 원격 재고·원격 결제가 생기고, 생각 시간을 두면 규격의 tpmC가 된다.
- **트리 저장소의 압축.** 목록은 이제 트리를 쓰지 않지만 문서와 text는 쓴다. 압축은 여전히 커밋 경로에서 살아 있는 데이터를
통째로 복사한다. 배경에서 복사하고 그동안의 커밋만 옮기는 압축이 필요하다.
|
