diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | CHECKPOINT.md | 1 | ||||
| -rw-r--r-- | README.md | 3 | ||||
| -rw-r--r-- | benchmarks/bank/bank.aup | 64 | ||||
| -rw-r--r-- | benchmarks/bank/run.py | 117 | ||||
| -rw-r--r-- | benchmarks/bank/sqlite-bank.c | 176 | ||||
| -rw-r--r-- | benchmarks/http/load.c | 44 | ||||
| -rw-r--r-- | docs/research/090-tables.md | 99 | ||||
| -rw-r--r-- | research/experiments/016-tables/2026-09-27-bank-linux-aarch64.jsonl | 15 |
9 files changed, 511 insertions, 9 deletions
@@ -8,5 +8,6 @@ __pycache__/ /benchmarks/http/axum-baseline/target/ /benchmarks/http/load /benchmarks/sample +/benchmarks/bank/sqlite-bank /benchmarks/http/*.pmod /build/ diff --git a/CHECKPOINT.md b/CHECKPOINT.md index d144896..21549e8 100644 --- a/CHECKPOINT.md +++ b/CHECKPOINT.md @@ -18,6 +18,7 @@ | HTTP 서비스 | 보기가 GET, 입력이 POST다(JSON 본문과 그 안의 그룹 객체를 제자리에서 읽는다, 라우터 코드 없음). 앱의 `send`는 이벤트와 함께 저장되고, `--send 출력=URL`로 다른 앱이나 HTTP 끝점에 순서대로 묶어 전해지며, 받는 앱은 번호마다 한 번 적용한다(서버를 죽였다 살려도 정확히 한 번). `--seal 출력=공개키`면 받는 노드의 키로 봉인해(HPKE, 전달선마다 세션 하나, 보내는 노드의 키로 인증) 사이의 중계가 읽지도 바꾸지도 못하고, 받는 노드는 `--sender 이름=키`로 보낸 이를 가린다(봉인 전달 462k/s, 봉인 없이 468k/s). 답은 저장 뒤에 나간다. 상태를 가진 앱은 소유자 스레드 하나가 입력을 적용하고, 연결 스레드는 마지막 저장의 스냅숏으로 보기를 답한다(쓰기가 동기화하는 동안에도 읽기는 기다리지 않는다) | 008 HTTP 호스트, [077](docs/research/077-apps-as-http-services.md), [080](docs/research/080-snapshot-reads.md), [082](docs/research/082-json-in-place.md), [083](docs/research/083-delivery-over-http.md), [086](docs/research/086-sealed-sends.md), [088](docs/research/088-sealed-sessions.md) | | 성능(Pi 5) | 2026-09-27, 같은 기기에서 axum·drogon과 함께 쟀다. 문서 서버(한 스레드): 64 B GET 139k/s(CPU 1초당 140k; axum 127k·63k, drogon 147k·63k), 1 MiB GET 2,362/s(axum 1,304, drogon 754), 충돌 안전 PUT은 axum-atomic의 5.1–5.8배. 앱 서비스: 내구성 있는 쓰기 64연결 21.3k/s(axum·drogon 내구 약 200/s), 합계 GET 126k/s·두 스레드 153k(axum 136k, drogon 151k), 20행 페이지 두 스레드 148k(axum 93k, drogon 138k), 쓰기와 섞인 읽기 119k/s(axum·drogon 내구 1.1–1.4k/s). 유휴 RSS 2.3 MiB(axum 2.8, drogon 10.9), 최대 3.2–5.8 MiB(axum 6.6–9.7, drogon 11.9–78.8) | [075](docs/research/075-http-host-against-axum.md), [077](docs/research/077-apps-as-http-services.md), [080](docs/research/080-snapshot-reads.md), [081](docs/research/081-tail-records.md), [087](docs/research/087-small-reads-and-idle-memory.md) | | 표면과 메신저 | 사람을 위한 표면이 노드 안에서 돈다(`pure-serve --surface`): 마지막 저장의 스냅숏을 제자리에서 읽고, 친 키와 글자는 HTTP 요청과 같은 줄로 소유자에게 간다. Vega의 디스플레이·픽셀이 그 표면이다. 두 노드의 메신저(Vega `examples/messenger.aup`)는 서로에게 봉인·인증해 보내고, 한 줄이 상대 노드에 보이기까지 RAM 저장소에서 p50 0.79 ms·p99 1.1 ms, SD 카드에서 p50 3.5 ms(꼬리는 SD의 동기화) | [설계 010](docs/design/010-surfaces.md), [089](docs/research/089-messenger.md) | +| 표 크기의 상태 | 목록이 영속 B+트리다(변경·키 탐색·저장본 위치 O(log n), 스냅숏 O(1), 1,600만 항목, 런타임 상태 1 GiB). pgbench의 TPC-B 같은 이체(세 표의 행과 이력, 한 트랜잭션)가 10만 계좌에서 RAM 24.5k/s(전: 3만 계좌 3.2k/s), SD 카드 내구 1,339/s(SQLite WAL FULL 84–153/s) | [090](docs/research/090-tables.md) | 키로 나눈 소유자와 저장을 넘길 스레드는 하지 않기로 했다. 이 장치는 동기화를 한 줄로 세워, 나누면 쓰기가 23% 줄고 넘겨도 기기의 일은 줄지 않는다([084](docs/research/084-parallel-syncs.md)). 대신 압축한 파일이 한 주기의 0을 미리 가져 커밋이 새 @@ -15,7 +15,8 @@ are in [075](docs/research/075-http-host-against-axum.md), [077](docs/research/0 [080](docs/research/080-snapshot-reads.md), [081](docs/research/081-tail-records.md), [082](docs/research/082-json-in-place.md), [083](docs/research/083-delivery-over-http.md), [086](docs/research/086-sealed-sends.md), [087](docs/research/087-small-reads-and-idle-memory.md), -[088](docs/research/088-sealed-sessions.md) and [089](docs/research/089-messenger.md); the status table is +[088](docs/research/088-sealed-sessions.md), [089](docs/research/089-messenger.md) and +[090](docs/research/090-tables.md); the status table is [CHECKPOINT.md](CHECKPOINT.md). The source follows the principle below, a small core with the rest selected around it diff --git a/benchmarks/bank/bank.aup b/benchmarks/bank/bank.aup new file mode 100644 index 0000000..acc7938 --- /dev/null +++ b/benchmarks/bank/bank.aup @@ -0,0 +1,64 @@ +# A bank as pgbench's TPC-B-like transaction: accounts, tellers and branches, +# each a list kept in key order, and a history of every transfer. A transfer +# moves a teller's delta into an account, the teller and its branch, and +# records it, all in one event: one transaction over four tables. +record Account { + aid = 0 + bid = 0 + balance = 0 + filler: text +} +record Teller { + tid = 0 + bid = 0 + balance = 0 +} +record Branch { + bid = 0 + balance = 0 +} +record Transfer { + tid = 0 + bid = 0 + aid = 0 + delta = 0 + at = 0 +} + +state accounts: list of Account by aid +state tellers: list of Teller by tid +state branches: list of Branch by bid +state history: list of Transfer + +input branch = message { + bid: u32 +} +input teller = message { + tid: u32 + bid: u32 +} +input account = message { + aid: u32 + bid: u32 +} +input transfer = message { + aid: u32 + tid: u32 + bid: u32 + delta: number +} + +on branch { branches.add(Branch { bid: branch.bid }) } +on teller { tellers.add(Teller { tid: teller.tid, bid: teller.bid }) } +on account { accounts.add(Account { aid: account.aid, bid: account.bid, filler: "" }) } + +on transfer { + accounts[transfer.aid].balance = accounts[transfer.aid].balance + transfer.delta + tellers[transfer.tid].balance = tellers[transfer.tid].balance + transfer.delta + branches[transfer.bid].balance = branches[transfer.bid].balance + transfer.delta + history.append(Transfer { tid: transfer.tid, bid: transfer.bid, aid: transfer.aid, delta: transfer.delta, at: now }) +} + +view accounts_count = accounts.count +view history_count = history.count +view total = sum(b.balance for b in branches) diff --git a/benchmarks/bank/run.py b/benchmarks/bank/run.py new file mode 100644 index 0000000..218c8ec --- /dev/null +++ b/benchmarks/bank/run.py @@ -0,0 +1,117 @@ +#!/usr/bin/env python3 +"""A bank served by pure-serve under pgbench's TPC-B-like transaction. + +bank.aup keeps accounts, tellers and branches as lists in key order and a +history list; a transfer updates one row of each of the three and appends a +history row, in one event. For each --accounts count: a fresh store, the +branches, tellers and accounts of that scale made by posts (timed), then +--seconds of transfers from --connections clients (benchmarks/http/load +transfer), servers on cores 0-2 and the load on core 3. Prints one JSON line +per count: setup time, transfers a second, latency, and server CPU time per +transfer. +""" +import argparse +import http.client +import json +import os +import select +import shutil +import subprocess +import tempfile +import threading +import time +from pathlib import Path + +HERE = Path(__file__).resolve().parent +ROOT = HERE.parents[1] + + +def cpu_seconds(pid): + fields = Path(f'/proc/{pid}/stat').read_text().rsplit(')', 1)[1].split() + return (int(fields[11]) + int(fields[12])) / os.sysconf('SC_CLK_TCK') + + +def post_all(port, path, bodies, threads=8): + """Each body posted once, from threads keep-alive connections.""" + failed = [] + + def worker(part): + connection = http.client.HTTPConnection('127.0.0.1', port, timeout=60) + for body in part: + connection.request('POST', path, body, {'Content-Type': 'application/json'}) + answer = connection.getresponse() + answer.read() + if answer.status != 200: + failed.append((body, answer.status)) + connection.close() + + workers = [threading.Thread(target=worker, args=(bodies[i::threads],)) for i in range(threads)] + for w in workers: + w.start() + for w in workers: + w.join() + assert not failed, failed[:3] + + +def run(serve, module, directory, accounts, seconds, connections, threads): + store = directory / f'bank-{accounts}' + shutil.rmtree(store, ignore_errors=True) + process = subprocess.Popen(['taskset', '-c', '0-2', str(serve), '--module', str(module), '--store', str(store), + '--port', '0', '--threads', str(threads)], stdout=subprocess.PIPE, stderr=subprocess.PIPE) + try: + select.select([process.stdout], [], [], 10) + port = json.loads(process.stdout.readline())['port'] + scale = max(1, accounts // 100000) + began = time.perf_counter() + post_all(port, '/inputs/branch', [json.dumps({'bid': b + 1}).encode() for b in range(scale)], 1) + post_all(port, '/inputs/teller', [json.dumps({'tid': t + 1, 'bid': t // 10 + 1}).encode() + for t in range(10 * scale)], 1) + post_all(port, '/inputs/account', [json.dumps({'aid': a + 1, 'bid': a // 100000 + 1}).encode() + for a in range(accounts)]) + setup = time.perf_counter() - began + used = cpu_seconds(process.pid) + load = subprocess.run(['taskset', '-c', '3', str(ROOT / 'benchmarks' / 'http' / 'load'), str(port), + str(connections), str(seconds), 'transfer', str(accounts), 'keep-alive'], + capture_output=True, text=True, check=True) + result = json.loads(load.stdout) + used = cpu_seconds(process.pid) - used + connection = http.client.HTTPConnection('127.0.0.1', port, timeout=30) + connection.request('GET', '/views/history_count') + history = int(connection.getresponse().read()) + connection.close() + # Every transfer answered is in the history, and those in flight when the load stopped may be too. + assert result['2xx'] <= history <= result['2xx'] + connections, (history, result) + return {'accounts': accounts, 'setup_s': round(setup, 2), 'transfers_per_second': result['requests_per_second'], + 'p50_us': result['p50_us'], 'p99_us': result['p99_us'], 'errors': result['errors'], + 'non_2xx': result['completed'] - result['2xx'], + 'cpu_us_per_transfer': round(used / max(result['2xx'], 1) * 1e6, 1)} + finally: + process.terminate() + process.communicate(timeout=60) + shutil.rmtree(store, ignore_errors=True) + + +def main(): + parser = argparse.ArgumentParser() + parser.add_argument('--aup', type=Path, default=ROOT.parent / 'aup' / 'build' / 'aup') + parser.add_argument('--serve', type=Path, default=ROOT / 'build' / 'pure-serve') + parser.add_argument('--directory', type=Path, default=Path('/dev/shm')) + parser.add_argument('--accounts', default='1000,10000,30000') + parser.add_argument('--seconds', type=float, default=5) + parser.add_argument('--connections', type=int, default=16) + parser.add_argument('--threads', type=int, default=1) + args = parser.parse_args() + work = Path(tempfile.mkdtemp(prefix='pure-bank-')) + try: + module = work / 'bank.pmod' + subprocess.run([str(args.aup), 'build', str(HERE / 'bank.aup'), '-o', str(module)], check=True) + for accounts in (int(a) for a in args.accounts.split(',')): + print(json.dumps({'directory': str(args.directory), **run(args.serve, module, args.directory, accounts, + args.seconds, args.connections, args.threads)}), + flush=True) + finally: + shutil.rmtree(work) + + +if __name__ == '__main__': + main() diff --git a/benchmarks/bank/sqlite-bank.c b/benchmarks/bank/sqlite-bank.c new file mode 100644 index 0000000..e4ab48f --- /dev/null +++ b/benchmarks/bank/sqlite-bank.c @@ -0,0 +1,176 @@ +#define _GNU_SOURCE +/* pgbench's TPC-B-like transaction on SQLite, the same bank as bank.aup for + * comparing with Pure (benchmarks/bank/run.py): + * + * sqlite-bank DATABASE ACCOUNTS THREADS SECONDS full|normal|off + * + * makes pgbench's tables (a branch, 10 tellers and 100,000 accounts a scale; + * ACCOUNTS, at least one scale), then THREADS threads, each with its own + * connection, run the transaction for SECONDS: BEGIN IMMEDIATE; UPDATE + * accounts; SELECT the balance; UPDATE tellers; UPDATE branches; INSERT into + * history; COMMIT, with random ids and delta as pgbench picks them. WAL, with + * synchronous FULL (each commit synced), NORMAL or OFF. Prints one JSON line. */ +#include <pthread.h> +#include <sqlite3.h> +#include <stdatomic.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +static const char *database, *synchronous; +static unsigned accounts, scale; +static double seconds; +static atomic_uint_fast64_t done, failed; +enum { BUCKETS = 64 * 16 }; +static atomic_uint_fast64_t histogram[BUCKETS]; + +static uint64_t now_us(void) { + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return (uint64_t)t.tv_sec * 1000000 + (uint64_t)t.tv_nsec / 1000; +} + +/* Log-linear buckets: 16 a power of two. */ +static unsigned bucket(uint64_t us) { + if (us < 16) return (unsigned)us; + unsigned power = 63 - (unsigned)__builtin_clzll(us); + return (power - 3) * 16 + (unsigned)((us >> (power - 4)) & 15); +} +static uint64_t bucket_value(unsigned index) { + if (index < 16) return index; + unsigned power = index / 16 + 3; + return ((uint64_t)16 + index % 16) << (power - 4); +} +static uint64_t percentile(uint64_t total, double p) { + uint64_t want = (uint64_t)((double)total * p), seen = 0; + for (unsigned i = 0; i < BUCKETS; ++i) { + seen += histogram[i]; + if (seen > want) return bucket_value(i); + } + return 0; +} + +static sqlite3 *open_database(void) { + sqlite3 *db; + char pragmas[160]; + if (sqlite3_open(database, &db) != SQLITE_OK) { fprintf(stderr, "%s\n", sqlite3_errmsg(db)); exit(1); } + sqlite3_busy_timeout(db, 60000); + snprintf(pragmas, sizeof(pragmas), "PRAGMA journal_mode=WAL; PRAGMA synchronous=%s;", synchronous); + if (sqlite3_exec(db, pragmas, NULL, NULL, NULL) != SQLITE_OK) { fprintf(stderr, "%s\n", sqlite3_errmsg(db)); exit(1); } + return db; +} + +static void run(sqlite3 *db, const char *sql) { + char *error = NULL; + if (sqlite3_exec(db, sql, NULL, NULL, &error) != SQLITE_OK) { fprintf(stderr, "%s: %s\n", sql, error); exit(1); } +} + +static sqlite3_stmt *prepare(sqlite3 *db, const char *sql) { + sqlite3_stmt *statement; + if (sqlite3_prepare_v2(db, sql, -1, &statement, NULL) != SQLITE_OK) { fprintf(stderr, "%s\n", sqlite3_errmsg(db)); exit(1); } + return statement; +} + +static uint64_t next_random(uint64_t *state) { + uint64_t x = *state; + x ^= x << 13, x ^= x >> 7, x ^= x << 17; + return *state = x; +} + +static bool step_done(sqlite3_stmt *statement) { + int result = sqlite3_step(statement); + sqlite3_reset(statement); + return result == SQLITE_DONE || result == SQLITE_ROW; +} + +static void *client(void *argument) { + uint64_t random = 0x9e3779b97f4a7c15u * (uintptr_t)argument; + sqlite3 *db = open_database(); + sqlite3_stmt *begin = prepare(db, "BEGIN IMMEDIATE"), *commit = prepare(db, "COMMIT"), + *rollback = prepare(db, "ROLLBACK"), + *account = prepare(db, "UPDATE pgbench_accounts SET abalance = abalance + ?1 WHERE aid = ?2"), + *balance = prepare(db, "SELECT abalance FROM pgbench_accounts WHERE aid = ?1"), + *teller = prepare(db, "UPDATE pgbench_tellers SET tbalance = tbalance + ?1 WHERE tid = ?2"), + *branch = prepare(db, "UPDATE pgbench_branches SET bbalance = bbalance + ?1 WHERE bid = ?2"), + *history = prepare(db, "INSERT INTO pgbench_history (tid, bid, aid, delta, mtime) " + "VALUES (?1, ?2, ?3, ?4, CURRENT_TIMESTAMP)"); + uint64_t stop = now_us() + (uint64_t)(seconds * 1e6); + while (now_us() < stop) { + int aid = (int)(next_random(&random) % accounts) + 1, tid = (int)(next_random(&random) % (10 * scale)) + 1, + bid = (int)(next_random(&random) % scale) + 1, delta = (int)(next_random(&random) % 10001) - 5000; + uint64_t started = now_us(); + sqlite3_bind_int(account, 1, delta), sqlite3_bind_int(account, 2, aid); + sqlite3_bind_int(balance, 1, aid); + sqlite3_bind_int(teller, 1, delta), sqlite3_bind_int(teller, 2, tid); + sqlite3_bind_int(branch, 1, delta), sqlite3_bind_int(branch, 2, bid); + sqlite3_bind_int(history, 1, tid), sqlite3_bind_int(history, 2, bid), sqlite3_bind_int(history, 3, aid), + sqlite3_bind_int(history, 4, delta); + bool ok = step_done(begin) && step_done(account) && step_done(balance) && step_done(teller) && + step_done(branch) && step_done(history) && step_done(commit); + if (!ok) { + step_done(rollback); + ++failed; + continue; + } + ++done; + ++histogram[bucket(now_us() - started)]; + } + sqlite3_stmt *statements[] = {begin, commit, rollback, account, balance, teller, branch, history}; + for (size_t i = 0; i < sizeof(statements) / sizeof(*statements); ++i) sqlite3_finalize(statements[i]); + sqlite3_close(db); + return NULL; +} + +int main(int argc, char **argv) { + if (argc != 6) { + fputs("sqlite-bank DATABASE ACCOUNTS THREADS SECONDS full|normal|off\n", stderr); + return 2; + } + database = argv[1]; + accounts = (unsigned)strtoul(argv[2], NULL, 10); + unsigned threads = (unsigned)strtoul(argv[3], NULL, 10); + seconds = atof(argv[4]); + synchronous = argv[5]; + scale = accounts / 100000 ? accounts / 100000 : 1; + uint64_t began = now_us(); + sqlite3 *db = open_database(); + run(db, "DROP TABLE IF EXISTS pgbench_accounts; DROP TABLE IF EXISTS pgbench_tellers;" + "DROP TABLE IF EXISTS pgbench_branches; DROP TABLE IF EXISTS pgbench_history;" + "CREATE TABLE pgbench_accounts (aid INTEGER PRIMARY KEY, bid INTEGER, abalance INTEGER, filler CHAR(84));" + "CREATE TABLE pgbench_tellers (tid INTEGER PRIMARY KEY, bid INTEGER, tbalance INTEGER, filler CHAR(84));" + "CREATE TABLE pgbench_branches (bid INTEGER PRIMARY KEY, bbalance INTEGER, filler CHAR(88));" + "CREATE TABLE pgbench_history (tid INTEGER, bid INTEGER, aid INTEGER, delta INTEGER, mtime TIMESTAMP," + " filler CHAR(22));"); + run(db, "BEGIN"); + sqlite3_stmt *insert = prepare(db, "INSERT INTO pgbench_branches (bid, bbalance, filler) VALUES (?1, 0, '')"); + for (unsigned b = 1; b <= scale; ++b) sqlite3_bind_int(insert, 1, (int)b), step_done(insert); + sqlite3_finalize(insert); + insert = prepare(db, "INSERT INTO pgbench_tellers (tid, bid, tbalance, filler) VALUES (?1, ?2, 0, '')"); + for (unsigned t = 1; t <= 10 * scale; ++t) sqlite3_bind_int(insert, 1, (int)t), sqlite3_bind_int(insert, 2, (int)((t - 1) / 10 + 1)), step_done(insert); + sqlite3_finalize(insert); + insert = prepare(db, "INSERT INTO pgbench_accounts (aid, bid, abalance, filler) VALUES (?1, ?2, 0, '')"); + for (unsigned a = 1; a <= accounts; ++a) + sqlite3_bind_int(insert, 1, (int)a), sqlite3_bind_int(insert, 2, (int)((a - 1) / 100000 + 1)), step_done(insert); + sqlite3_finalize(insert); + run(db, "COMMIT; PRAGMA wal_checkpoint(TRUNCATE);"); + double setup = (double)(now_us() - began) / 1e6; + pthread_t *thread = calloc(threads, sizeof(*thread)); + uint64_t start = now_us(); + for (unsigned i = 0; i < threads; ++i) pthread_create(&thread[i], NULL, client, (void *)(uintptr_t)(i + 1)); + for (unsigned i = 0; i < threads; ++i) pthread_join(thread[i], NULL); + double elapsed = (double)(now_us() - start) / 1e6; + sqlite3_stmt *count = prepare(db, "SELECT count(*) FROM pgbench_history"); + sqlite3_step(count); + long long history = sqlite3_column_int64(count, 0); + sqlite3_finalize(count); + sqlite3_close(db); + printf("{\"sqlite\":\"%s\",\"synchronous\":\"%s\",\"accounts\":%u,\"threads\":%u,\"setup_s\":%.2f," + "\"transfers_per_second\":%.0f,\"p50_us\":%llu,\"p99_us\":%llu,\"failed\":%llu,\"history\":%lld}\n", + sqlite3_libversion(), synchronous, accounts, threads, setup, (double)done / elapsed, + (unsigned long long)percentile(done, 0.5), (unsigned long long)percentile(done, 0.99), + (unsigned long long)failed, history); + return history == (long long)done ? 0 : 1; +} diff --git a/benchmarks/http/load.c b/benchmarks/http/load.c index d07b2bb..621e99c 100644 --- a/benchmarks/http/load.c +++ b/benchmarks/http/load.c @@ -2,7 +2,7 @@ /* HTTP/1.1 load for Pure's benchmarks: N connections on one epoll thread, * each sending one request at a time and measuring its latency. * - * load PORT CONNECTIONS SECONDS get|put|score|total|page|note|json KEYS [keep-alive|close] [BODY] + * load PORT CONNECTIONS SECONDS get|put|score|total|page|note|json|transfer KEYS [keep-alive|close] [BODY] * get: GET /objects/kI for I in [0, KEYS). * put: connection C edits its own key kC (C mod KEYS), inserting BODY bytes * at 0 with If-Match on the revision it last saw (If-None-Match: * at @@ -11,7 +11,11 @@ * the name as the body), total reads GET /views/total and page GET * /views/leaders?from=0&count=20. note reads GET /views/page (a text state * shown as it is, as in a notes app). json posts {"name":"k","text":"x..."} - * (BODY bytes of text) to POST /inputs/echo as application/json. + * (BODY bytes of text) to POST /inputs/echo as application/json. transfer is + * pgbench's TPC-B-like transaction for benchmarks/bank: POST /inputs/transfer + * {"aid","tid","bid","delta"}, a random account of KEYS, teller and branch of + * the scale (100,000 accounts, 10 tellers and a branch each) and delta in + * [-5000, 5000], as pgbench picks them. * Prints one JSON line: requests/s, statuses, latency percentiles (µs). */ #include <arpa/inet.h> #include <errno.h> @@ -37,7 +41,7 @@ typedef struct { size_t request_size, sent, body_size, body_sent; char *response; size_t received; - uint64_t started, revision; + uint64_t started, revision, random; } Connection; static uint64_t now_us(void) { @@ -69,14 +73,36 @@ static uint64_t percentile(uint64_t total, double p) { } static int port, connections_count, keys; -static enum { GET, PUT, SCORE, TOTAL, PAGE, NOTE, JSON } method; +static enum { GET, PUT, SCORE, TOTAL, PAGE, NOTE, JSON, TRANSFER } method; static bool put, keep_alive; static char *body; static size_t body_bytes; static int epoll_fd; +/* xorshift64: each connection its own sequence. */ +static uint64_t next_random(uint64_t *state) { + uint64_t x = *state; + x ^= x << 13, x ^= x >> 7, x ^= x << 17; + return *state = x; +} + static void prepare(Connection *c) { const char *closing = keep_alive ? "" : "Connection: close\r\n"; + if (method == TRANSFER) { + unsigned scale = keys / 100000 ? (unsigned)(keys / 100000) : 1; + char json[128]; + int length = snprintf(json, sizeof(json), "{\"aid\":%u,\"tid\":%u,\"bid\":%u,\"delta\":%d}", + (unsigned)(next_random(&c->random) % (uint64_t)keys) + 1, + (unsigned)(next_random(&c->random) % (10u * scale)) + 1, + (unsigned)(next_random(&c->random) % scale) + 1, + (int)(next_random(&c->random) % 10001) - 5000); + c->request_size = (size_t)snprintf(c->request, sizeof(c->request), + "POST /inputs/transfer HTTP/1.1\r\nHost: localhost\r\nContent-Type: application/json\r\n" + "Content-Length: %d\r\n%s\r\n%s", length, closing, json); + c->sent = c->received = c->body_sent = c->body_size = 0; + c->started = now_us(); + return; + } if (method == JSON) { c->request_size = (size_t)snprintf(c->request, sizeof(c->request), "POST /inputs/echo HTTP/1.1\r\nHost: localhost\r\nContent-Type: application/json\r\n" @@ -151,15 +177,16 @@ static bool complete(Connection *c, int *status, bool *closing, size_t *length) int main(int argc, char **argv) { if (argc < 6) { - fputs("load PORT CONNECTIONS SECONDS get|put|score|total|page|note|json KEYS [keep-alive|close] [BODY]\n", stderr); + fputs("load PORT CONNECTIONS SECONDS get|put|score|total|page|note|json|transfer KEYS [keep-alive|close] [BODY]\n", + stderr); return 2; } port = atoi(argv[1]); connections_count = atoi(argv[2]); double seconds = atof(argv[3]); - static const char *const methods[] = {"get", "put", "score", "total", "page", "note", "json"}; - for (method = GET; method <= JSON && strcmp(argv[4], methods[method]); ++method) {} - if (method > JSON) { fprintf(stderr, "load: unknown method %s\n", argv[4]); return 2; } + static const char *const methods[] = {"get", "put", "score", "total", "page", "note", "json", "transfer"}; + for (method = GET; method <= TRANSFER && strcmp(argv[4], methods[method]); ++method) {} + if (method > TRANSFER) { fprintf(stderr, "load: unknown method %s\n", argv[4]); return 2; } put = method == PUT; keys = atoi(argv[5]); keep_alive = argc > 6 && !strcmp(argv[6], "keep-alive"); @@ -177,6 +204,7 @@ int main(int argc, char **argv) { Connection *all = calloc((size_t)connections_count, sizeof(*all)); for (int i = 0; i < connections_count; ++i) { all[i].key = i % keys; + all[i].random = 0x9e3779b97f4a7c15u * (uint64_t)(i + 1); all[i].response = malloc(RESPONSE); open_connection(&all[i]); prepare(&all[i]); 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만 개로 만든다. 표를 한 번에 들이는 길이 필요하다. diff --git a/research/experiments/016-tables/2026-09-27-bank-linux-aarch64.jsonl b/research/experiments/016-tables/2026-09-27-bank-linux-aarch64.jsonl new file mode 100644 index 0000000..3a24e16 --- /dev/null +++ b/research/experiments/016-tables/2026-09-27-bank-linux-aarch64.jsonl @@ -0,0 +1,15 @@ +{"lists": "array (before 1421a28)", "directory": "/dev/shm", "accounts": 1000, "setup_s": 0.16, "transfers_per_second": 7870, "p50_us": 1984, "p99_us": 3968, "errors": 0, "non_2xx": 0, "cpu_us_per_transfer": 118.1} +{"lists": "array (before 1421a28)", "directory": "/dev/shm", "accounts": 10000, "setup_s": 2.05, "transfers_per_second": 6371, "p50_us": 2432, "p99_us": 5120, "errors": 0, "non_2xx": 0, "cpu_us_per_transfer": 147.1} +{"lists": "array (before 1421a28)", "directory": "/dev/shm", "accounts": 30000, "setup_s": 12.59, "transfers_per_second": 3245, "p50_us": 4608, "p99_us": 9728, "errors": 0, "non_2xx": 0, "cpu_us_per_transfer": 298.6} +{"lists": "tree", "directory": "/dev/shm", "accounts": 1000, "setup_s": 0.16, "transfers_per_second": 30546, "p50_us": 480, "p99_us": 768, "errors": 0, "non_2xx": 0, "cpu_us_per_transfer": 24.0} +{"lists": "tree", "directory": "/dev/shm", "accounts": 10000, "setup_s": 1.47, "transfers_per_second": 27737, "p50_us": 512, "p99_us": 1088, "errors": 0, "non_2xx": 0, "cpu_us_per_transfer": 27.1} +{"lists": "tree", "directory": "/dev/shm", "accounts": 30000, "setup_s": 4.46, "transfers_per_second": 26413, "p50_us": 544, "p99_us": 960, "errors": 0, "non_2xx": 0, "cpu_us_per_transfer": 29.1} +{"lists": "tree", "directory": "/dev/shm", "accounts": 100000, "setup_s": 15.49, "transfers_per_second": 24485, "p50_us": 576, "p99_us": 896, "errors": 0, "non_2xx": 0, "cpu_us_per_transfer": 32.1} +{"lists": "tree", "directory": "/var/tmp", "connections": 16, "accounts": 100000, "setup_s": 83.32, "transfers_per_second": 1339, "p50_us": 4864, "p99_us": 155648, "errors": 0, "non_2xx": 0, "cpu_us_per_transfer": 49.2} +{"lists": "tree", "directory": "/var/tmp", "connections": 64, "accounts": 100000, "setup_s": 90.02, "transfers_per_second": 962, "p50_us": 8192, "p99_us": 589824, "errors": 0, "non_2xx": 0, "cpu_us_per_transfer": 43.2} +{"sqlite":"3.46.1","directory": "/dev/shm","synchronous":"off","accounts":100000,"threads":16,"setup_s":0.07,"transfers_per_second":39817,"p50_us":21,"p99_us":64,"failed":0,"history":163249} +{"sqlite":"3.46.1","directory": "/dev/shm","synchronous":"full","accounts":100000,"threads":16,"setup_s":0.07,"transfers_per_second":40471,"p50_us":21,"p99_us":58,"failed":0,"history":165788} +{"sqlite":"3.46.1","directory": "/var/tmp","synchronous":"full","accounts":100000,"threads":16,"setup_s":0.35,"transfers_per_second":141,"p50_us":2304,"p99_us":6029312,"failed":0,"history":996} +{"sqlite":"3.46.1","directory": "/var/tmp","synchronous":"normal","accounts":100000,"threads":16,"setup_s":0.29,"transfers_per_second":1243,"p50_us":28,"p99_us":108,"failed":0,"history":25532} +{"sqlite":"3.46.1","directory": "/var/tmp","synchronous":"full","accounts":100000,"threads":1,"setup_s":0.29,"transfers_per_second":153,"p50_us":1792,"p99_us":86016,"failed":0,"history":922} +{"sqlite":"3.46.1","directory": "/var/tmp","synchronous":"full","accounts":100000,"threads":64,"setup_s":0.25,"transfers_per_second":84,"p50_us":4096,"p99_us":9437184,"failed":0,"history":900} |