diff options
| author | eunhhu <[email protected]> | 2026-09-26 23:24:31 +0100 |
|---|---|---|
| committer | eunhhu <[email protected]> | 2026-09-26 23:24:31 +0100 |
| commit | 2e7ad9f8488d4f02c688ec24d6d0b571b3fa61ec (patch) | |
| tree | 789183f42e3b68b797e7a09ef2b037e55d34ebfa | |
| parent | a51232af741cb952d7deb72f238c583919ababc0 (diff) | |
| download | pure-2e7ad9f8488d4f02c688ec24d6d0b571b3fa61ec.tar.gz pure-2e7ad9f8488d4f02c688ec24d6d0b571b3fa61ec.zip | |
Write each commit's head just before its bytes: one range per sync (081)
A tree store commit wrote its bytes over the written zeros of the tail
and its head into a slot at the start of the file: two ranges, and on
the Pi's SD card a sync of two ranges costs about twice one (2.4 ms
against 1.2 ms). A commit now writes a 128-byte record (its head) at
the published end and its bytes right after it, then syncs once. Every
16 commits the head also goes into the older slot. The newest commit
is found from the newer slot's head, or from the newest head this
process has seen in the file while its record is still there, along
the records whose bytes are whole; a torn record or bytes end the walk
at the commit before, which the next writer overwrites. Slots of this
format are PURETRE3; files of the earlier one are read and continued.
Store commits went from 220-233/s to 371-396/s (p50 2.5 to 1.3 ms),
and the scoreboard's durable posts from 13-16k/s to 21-26k/s with 64
connections and from 2.2-2.4k/s to 2.9-3.9k/s with 8, measured
alternately with the previous build. The torn head check now tears a
slot (the walk goes on from the other) and the newest record (a new
process sees the commit before); a new check walks 42 commits from the
slots, in a fresh process too, and stops at a damaged record.
| -rw-r--r-- | CHECKPOINT.md | 6 | ||||
| -rw-r--r-- | README.md | 7 | ||||
| -rw-r--r-- | docs/research/081-tail-records.md | 104 | ||||
| -rw-r--r-- | prototypes/connections/store-tree.c | 165 | ||||
| -rw-r--r-- | prototypes/connections/test-tree-store.c | 105 | ||||
| -rw-r--r-- | research/experiments/012-tail-records/2026-09-26-ext4-linux-aarch64.json | 184 | ||||
| -rw-r--r-- | research/experiments/012-tail-records/probe.c | 71 | ||||
| -rwxr-xr-x | research/experiments/012-tail-records/run.py | 69 |
8 files changed, 647 insertions, 64 deletions
diff --git a/CHECKPOINT.md b/CHECKPOINT.md index 641b2ab..08fd936 100644 --- a/CHECKPOINT.md +++ b/CHECKPOINT.md @@ -13,12 +13,12 @@ | 영역 | 확인한 것 | 근거 | |---|---|---| | 앱 표현 | 상태(수, text와 커서·마크, 레코드의 리스트와 키 있는 리스트, 인덱스), 입력(키, text, 필드 있는 메시지, 타이머), 원자적 이벤트 핸들러, 순수 보기(조건식, 표와 걸러진 표, count·sum·max·min·first), `fn`·`use` 라이브러리, text 비교, 시간(`now`, `every`, `floor`, `%`). 로드할 때 타입·스택·합류·커서와 인덱스의 소속을 모두 검증하고 이벤트의 실행량에 상한이 있다 | 008, aup `docs/design/002-dsl-direction.md`, aup `make check`(파이썬 참조 모델 대조, 진단 132건) | -| 영속 | 선언한 상태가 곧 영속 상태다. 트리 저장소에 커밋당 동기화 한 번, 이벤트 묶음마다 저장 한 번. `kill -9` 뒤 확인 응답한 이벤트가 모두 남는다. 레코드·키가 바뀐 모듈로 바꿔도 데이터가 이름으로 옮겨진다 | [076](docs/research/076-one-sync-commit.md), 008 상태 영속·교체 | +| 영속 | 선언한 상태가 곧 영속 상태다. 트리 저장소에 커밋당 동기화 한 번(헤드를 바이트 바로 앞에 두어 한 연속 구간), 이벤트 묶음마다 저장 한 번. `kill -9` 뒤 확인 응답한 이벤트가 모두 남는다. 레코드·키가 바뀐 모듈로 바꿔도 데이터가 이름으로 옮겨진다 | [076](docs/research/076-one-sync-commit.md), [081](docs/research/081-tail-records.md), 008 상태 영속·교체 | | 인터페이스 | 한 명세가 TUI(셀 단위 갱신), CLI, 문장(NUI), 웹 GUI가 된다. 저장하면 실행 중인 앱이 상태를 이어 새 모듈로 바뀐다(`aup watch`, `vega … --watch`) | Vega `docs/design/001-first-component.md`, Vega `make check`(가상 터미널, 헤드리스 Chromium 포함) | | HTTP 서비스 | 보기가 GET, 입력이 POST다(JSON 본문, 라우터 코드 없음). 답은 저장 뒤에 나간다. 상태를 가진 앱은 소유자 스레드 하나가 입력을 적용하고, 연결 스레드는 마지막 저장의 스냅숏으로 보기를 답한다(쓰기가 동기화하는 동안에도 읽기는 기다리지 않는다) | 008 HTTP 호스트, [077](docs/research/077-apps-as-http-services.md), [080](docs/research/080-snapshot-reads.md) | -| 성능(Pi 5) | 문서 서버: 작은 GET 151.6k/s, 1 MiB GET 2,794/s(axum 1,372, drogon 708), 충돌 안전 PUT은 axum-atomic의 5.1–5.8배. 앱 서비스(aup 22줄 대 손으로 쓴 서비스): 내구성 있는 쓰기 약 76배, 20행 JSON GET 145k/s(axum 95k, drogon 144k), 쓰기와 섞인 읽기 149k/s·p99 0.6 ms(axum·drogon 내구 1.1–1.3k/s·p99 111–156 ms), 최대 RSS 3.0–4.1 MiB(axum 6.4, drogon 11.6) | [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) | +| 성능(Pi 5) | 문서 서버: 작은 GET 151.6k/s, 1 MiB GET 2,794/s(axum 1,372, drogon 708), 충돌 안전 PUT은 axum-atomic의 5.1–5.8배. 앱 서비스(aup 22줄 대 손으로 쓴 서비스): 내구성 있는 쓰기 약 76배(그 뒤 저장소 커밋을 한 구간으로 바꿔 64연결 21–26k/s, axum·drogon 내구 약 180/s), 20행 JSON GET 145k/s(axum 95k, drogon 144k), 쓰기와 섞인 읽기 149k/s·p99 0.6 ms(axum·drogon 내구 1.1–1.3k/s·p99 111–156 ms), 최대 RSS 3.0–4.1 MiB(axum 6.4, drogon 11.6) | [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) | -남은 것: macOS 검증, `bool`·`i64`, 저장과 적용의 겹치기(로드맵 단기 2, 080 다음 결정), 앱 라우트의 인증·TLS(문서 +남은 것: macOS 검증, `bool`·`i64`, 꼬리 늘리기·압축을 커밋 밖으로와 열린 부하에서의 저장·적용 겹치기(081 다음 결정), 앱 라우트의 인증·TLS(문서 피어의 TLS는 있다), aup·Vega의 배포 묶음. ## 공개할 작업물과 완료 증거 @@ -5,9 +5,10 @@ in Pure's tree store, every event is a transaction, views are pure functions of state. The same spec becomes a terminal UI, a CLI, spoken sentences and a web page through [Vega](/srv/git/vega.git), and an HTTP service through `pure-serve` (views are GETs, inputs are POSTs with JSON bodies; answers are durable; views are read from a snapshot of -the last save, so reads never wait for a sync). Measurements against axum and drogon on a Raspberry Pi 5 are in -[075](docs/research/075-http-host-against-axum.md), [077](docs/research/077-apps-as-http-services.md) and -[080](docs/research/080-snapshot-reads.md); the status table is [CHECKPOINT.md](CHECKPOINT.md). The text below +the last save, so reads never wait for a sync; a commit is one contiguous write and one sync). Measurements against +axum and drogon on a Raspberry Pi 5 are in [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) and +[081](docs/research/081-tail-records.md); the status table is [CHECKPOINT.md](CHECKPOINT.md). The text below records the earlier document runtime this grew from. A standalone native micro runtime being designed as a small operating diff --git a/docs/research/081-tail-records.md b/docs/research/081-tail-records.md new file mode 100644 index 0000000..fdb6833 --- /dev/null +++ b/docs/research/081-tail-records.md @@ -0,0 +1,104 @@ +# 081 — 헤드를 커밋 바이트 바로 앞에: 동기화가 쓰는 구간을 하나로 + +2026-09-26. [로드맵](../roadmap.md) 단기 2 "저장과 적용의 겹치기"를 재 보다가 바꾼 것. 트리 저장소(`store-tree.c`)의 +파일 형식이 바뀌었다(슬롯 `PURETRE2` → `PURETRE3`, 커밋 레코드 `PUREREC1`). 이전 형식의 파일은 그대로 읽고 이어 쓴다. + +착수 기준: + +- 바꿀 결정: 동기화를 소유자의 경로에서 빼기 위해 저장을 다른 스레드로 넘기고 적용과 겹칠지, 동기화 자체를 줄일지. +- 남은 질문: 소유자의 한 라운드에서 동기화는 몇 %이고 겹쳐서 가릴 수 있는 일은 몇 %인가? 커밋의 동기화가 이 + 장치에서 가장 싼 쓰기(0을 써 둔 곳을 덮어쓰고 `fdatasync`)보다 비싼 까닭은 무엇인가? +- 최소 확인: 라운드를 나눠 재고, 방식별 동기화 비용을 장치에서 번갈아 재고, 바꾼 저장소를 기존 고장·찢김·오라클 + 검사와 새 검사에 통과시킨 뒤 저장소와 HTTP 수준에서 이전 저장소와 번갈아 잰다. +- 중단 기준: 찢긴 커밋이나 잃어버린 커밋을 받아들이는 경우가 하나라도 있으면 되돌린다. + +## 라운드가 쓰는 시간 + +점수판 앱([077](077-apps-as-http-services.md)), 내구성 점수 POST 64연결, 소유자의 라운드 평균(Pi 5, SD 카드의 ext4): + +| | µs | 몫 | +|---|---:|---:| +| `fdatasync` | 3,287 | 71% | +| 다음 요청을 기다리기(답이 클라이언트를 돌아 새 요청이 오고 모이기까지) | 1,149 | 25% | +| 적용, 커밋 쓰기, 게시, 답 돌려주기 | 164 | 4% | + +라운드당 이벤트 61개. 적용을 동기화와 겹쳐 가릴 수 있는 것은 4%다. 게다가 답을 받아야 다음 요청을 보내는 클라이언트 +(닫힌 루프)에서는 앞 동기화 중에 다음 동기화를 준비하면 클라이언트가 두 묶음으로 갈려 동기화 한 번에 담기는 이벤트가 +반으로 준다. 동기화가 라운드를 지배하는 동안에는 모두를 한 번의 동기화에 모으는 지금 방식이 낫다. 그래서 동기화를 +다른 스레드로 넘기기 전에 동기화 자체를 봤다. + +## 장치가 말한 것 + +[076](076-one-sync-commit.md)은 0을 써 둔 꼬리를 덮어써 저널 커밋을 없앴다. 그래도 커밋은 두 곳에 쓴다. 꼬리의 바이트와 +파일 앞 슬롯의 헤드다. 방식별로 40번씩 번갈아 잰 p50(ms, 세 번 반복, [probe.c](../../research/experiments/012-tail-records/probe.c)): + +| 커밋 | 2 KiB | 8 KiB | +|---|---:|---:| +| 바이트, 앞 슬롯에 헤드, `fdatasync` (이전) | 2.40–2.44 | 2.40–2.71 | +| **헤드를 바이트 바로 앞에, `fdatasync`** | **1.19–1.23** | **1.18–1.57** | +| 바이트만, `fdatasync` | 1.20–1.23 | 1.12–1.21 | + +떨어진 두 구간은 한 구간의 두 배 가깝다. 헤드를 바로 앞에 두면 바이트만 쓰는 것과 같다. + +## 바꾼 것 + +- **커밋은 레코드와 바이트다.** 커밋은 공개된 끝에 128 B 레코드(헤드: 순번, 끝, 카탈로그, 바이트의 시작과 + 다이제스트, 레코드 자체의 다이제스트)를 쓰고 바로 뒤에 노드를 쓴 다음 `fdatasync`를 한 번 한다. 한 연속 구간이다. + 다이제스트는 쓰는 동안 갱신되므로 레코드는 노드를 다 쓴 뒤 비워 둔 자리에 쓴다. +- **슬롯은 체크포인트다.** 16커밋마다 헤드를 오래된 슬롯에도 쓴다(그 커밋만 두 구간). 슬롯의 헤드는 이전처럼 자기 + 바이트의 다이제스트가 맞아야 믿는다. +- **최신 커밋 찾기.** 새 슬롯의 믿을 수 있는 헤드에서 시작해, 헤드의 끝에 순번이 하나 큰 레코드가 있고 그 바이트의 + 다이제스트가 맞는 동안 따라간다. 찢긴 레코드나 바이트에서 멈추므로 그 앞 커밋이 최신이다. 쓰는 쪽은 그 위에 쓰고, + 멈춘 자리의 레코드와 바이트를 덮어쓴다. 프로세스는 파일마다 자기가 본 최신 헤드를 기억해 거기서 따라간다(파일의 그 + 자리에 같은 레코드가 그대로 있을 때만). 그래서 커밋마다 슬롯에서 다시 걷지 않는다. +- **새로 고침.** 저장소 핸들은 현재 헤드의 끝에 다음 순번의 레코드가 있는지를 `pread` 하나로 본다. 슬롯의 순번은 + 이전 형식의 커밋을 위해 계속 본다. +- 이전 형식의 파일은 슬롯의 헤드 뒤에 레코드가 없으므로 그대로 읽히고, 새 커밋은 레코드로 이어진다. 이 형식의 슬롯은 + `PURETRE3`이라 이전 빌드는 이 형식을 읽지 않는다. + +## 측정 + +**저장소 단독.** 64개 문서 중 하나의 앞에 16 B를 넣는 커밋 400번 연달아 +([commits.c](../../research/experiments/010-one-sync-commit/commits.c), 이전 저장소 `2ef0d40`과 라운드마다 순서를 바꿔 세 번, +[run.py](../../research/experiments/012-tail-records/run.py), +[원시 결과](../../research/experiments/012-tail-records/2026-09-26-ext4-linux-aarch64.json)): + +| | 헤드를 슬롯에 | 헤드를 레코드로 | +|---|---:|---:| +| 초당 커밋 | 220–233 | **371–396** | +| p50 | 2.48–2.55 ms | **1.26–1.29 ms** | +| p90 | 5.54–6.04 ms | 3.90–4.04 ms | + +**앱 서비스.** 점수판의 내구성 POST, 이전 빌드(2ef0d40)와 번갈아 세 번(4초씩, `run.py --suite app --workloads score`): + +| | 이전 | 레코드 | +|---|---:|---:| +| 64연결, 연결 스레드 1: POST/s | 13,136–16,480 | **21,006–26,080** | +| 64연결, 연결 스레드 3 | 15,127–15,423 | **21,990–25,408** | +| 8연결, 연결 스레드 1 | 2,174–2,344 | **2,912–3,796** | +| 8연결, 연결 스레드 3 | 2,217–2,406 | **3,388–3,870** | +| p50(64연결) | 3.2–3.3 ms | **2.0 ms** | + +소유자의 라운드로 보면 동기화가 평균 3.3 ms에서 1.9 ms로, 한 라운드가 4.6 ms에서 3.0 ms로 줄었다. 동기화의 p50은 +1.24 ms로 탐침과 같다. 평균을 끌어올리는 것은 4 ms를 넘는 4%의 동기화(전체 동기화 시간의 33%)다. 꼬리를 늘린 뒤의 +동기화(5초에 13번, 새로 쓴 0과 새 크기를 함께 내보낸다), 압축(2번), 체크포인트(16커밋마다, 두 구간), 그리고 장치의 +잡음이다. 문서 서버의 내구성 PUT은 같은 빌드끼리도 p99가 0.1–1.1 s로 흔들려(장치 상태) 차이를 가려내지 못했다. 같은 +범위다. + +## 검증 + +- `test-tree-store`: 기존 검사(무작위 오라클, 실패 단계, 단계마다 죽는 프로세스, 잃어버린 커밋, 동기화 중인 헤드, + 압축, 손상, 커밋당 동기화 한 번과 파일 크기 불변)가 그대로 통과한다. 찢긴 헤드 검사는 이제 두 가지다. 새 슬롯을 찢어도 + 다른 슬롯에서 레코드를 따라가 최신 커밋을 찾고, 최신 레코드를 찢으면 새 프로세스는 그 앞 커밋을 보며 다음 쓰기가 찢긴 + 자리에 쓴다. 새 검사 `records`: 42커밋 뒤 슬롯의 헤드는 33이고, 헤드를 모르는 새 프로세스도 최신 커밋을 읽으며, 37번째 + 커밋의 레코드를 손상시키면 36에서 멈추고 다음 커밋이 그 위에 쓴다. ASan·UBSan 빌드에서도 같다. +- `check-tree`(저장소 위의 런타임·splice·비동기·실제 PTY 편집기 검사), `test-module`(상태 영속, 단계마다 죽는 앱), + aup `make check`(모델 대조, `kill -9` 뒤 확인 응답 보존, 저장한 상태로 다시 시작), Vega `make check`가 통과한다. + +## 다음 결정 + +- **꼬리 늘리기와 압축을 커밋 밖으로.** 동기화 시간의 3분의 1이 드문 느린 동기화다. 0을 써 넣는 일과 압축을 저장이 + 없는 틈이나 다른 스레드에서 하면 그만큼 줄 것이다. 다만 0을 새로 쓴 쪽이 아직 내구성이 없는데 커밋이 그 위에 쓰면 안 + 되므로, 늘린 꼬리를 먼저 동기화하는 순서가 필요하다. +- **저장과 적용의 겹치기**는 열린 부하(답을 기다리지 않고 요청이 오는 경우)에서 다시 잰다. 닫힌 루프에서는 위의 까닭으로 + 얻을 것이 없다. diff --git a/prototypes/connections/store-tree.c b/prototypes/connections/store-tree.c index 322a163..146e919 100644 --- a/prototypes/connections/store-tree.c +++ b/prototypes/connections/store-tree.c @@ -3,9 +3,12 @@ * path it changes, so inserting or deleting in a large document costs O(log n) * nodes instead of a whole-document copy. Unchanged extents are shared by old * and new versions. The document catalog is the same structure holding fixed - * records sorted by key. A commit appends its nodes and writes a head naming - * them and their digest into the older of two slots, then syncs once; readers - * take no lock and map one immutable prefix. */ + * records sorted by key. A commit appends a record (its head: where its nodes + * are and their digest) and then its nodes, and syncs once: one contiguous + * range, which a flash device writes about twice as fast as two. Every few + * commits the head also goes into the older of two slots at the start, where + * a reader begins before following the records after it; readers take no + * lock and map one immutable prefix. */ #define _POSIX_C_SOURCE 200809L #ifdef __APPLE__ #define _DARWIN_C_SOURCE @@ -39,7 +42,12 @@ enum { COMPACT_SLACK = 1048576 }; #define LEAF_BIT (UINT64_C(1) << 63) #define MEMORY_BIT (UINT64_C(1) << 62) #define LOCATION (MEMORY_BIT - 1) -static const unsigned char head_magic[8] = {'P','U','R','E','T','R','E','2'}; +/* Slots of this format, and of the one before tail records (still read). */ +static const unsigned char head_magic[8] = {'P','U','R','E','T','R','E','3'}; +static const unsigned char earlier_magic[8] = {'P','U','R','E','T','R','E','2'}; +static const unsigned char record_magic[8] = {'P','U','R','E','R','E','C','1'}; +/* Commits between two heads written to a slot. */ +enum { CHECKPOINT = 16 }; static const unsigned char branch_magic[4] = {'P','T','B','1'}; static const char tree_name[] = "pure.tree"; /* Threads of one process take turns as the writer: the file lock arbitrates @@ -240,9 +248,9 @@ static bool read_at(int fd, unsigned char *bytes, size_t length, uint64_t offset return true; } -static void encode_head(unsigned char out[SLOT], const Head *head) { +static void encode_head(unsigned char out[SLOT], const unsigned char magic[8], const Head *head) { memset(out, 0, SLOT); - memcpy(out, head_magic, sizeof(head_magic)); + memcpy(out, magic, 8); encode64(out + 8, head->seq); encode64(out + 16, head->end); encode64(out + 24, head->catalog); @@ -253,9 +261,10 @@ static void encode_head(unsigned char out[SLOT], const Head *head) { encode64(out + SLOT - 8, digest_of(out, SLOT - 8)); } -static bool decode_head(const unsigned char in[SLOT], Head *head) { - if (memcmp(in, head_magic, sizeof(head_magic)) || decode64(in + SLOT - 8) != digest_of(in, SLOT - 8)) - return false; +/* A slot's head (record false) or a commit record's. */ +static bool decode_head(const unsigned char in[SLOT], bool record, Head *head) { + bool magic = record ? !memcmp(in, record_magic, 8) : !memcmp(in, head_magic, 8) || !memcmp(in, earlier_magic, 8); + if (!magic || decode64(in + SLOT - 8) != digest_of(in, SLOT - 8)) return false; *head = (Head){decode64(in + 8), decode64(in + 16), decode64(in + 24), decode64(in + 32), decode64(in + 40), decode64(in + 48), decode64(in + 56)}; return head->seq && head->end <= (uint64_t)INT64_MAX && head->end <= SIZE_MAX && @@ -274,11 +283,16 @@ static bool decode_head(const unsigned char in[SLOT], Head *head) { enum { UNKNOWN, BROKEN, CHECKED, DURABLE, PUBLISHING }; enum { KNOWN = 32 }; typedef struct { dev_t device; ino_t inode; uint64_t seq, check; int state; } Known; +/* The newest head that counts per file, to follow records from. */ +typedef struct { dev_t device; ino_t inode; Head head; } Newest; +enum { NEWEST = 4 }; static struct { pthread_mutex_t lock; Known heads[KNOWN]; unsigned next; Known publishing; /* written here, not durable yet */ + Newest newest[NEWEST]; + unsigned next_newest; } known = {.lock = PTHREAD_MUTEX_INITIALIZER}; static bool names(const Known *known_head, const struct stat *file, const Head *head) { @@ -310,7 +324,28 @@ static void remember(const struct stat *file, const Head *head, int state) { if (!at) known.heads[known.next++ % KNOWN] = entry; else if (at->state != DURABLE) *at = entry; /* a durable head stays durable */ } + if (state == CHECKED || state == DURABLE) { + Newest *at = NULL; + for (unsigned i = 0; i < NEWEST && !at; ++i) + if (known.newest[i].head.seq && known.newest[i].device == file->st_dev && + known.newest[i].inode == file->st_ino) at = &known.newest[i]; + if (!at) at = &known.newest[known.next_newest++ % NEWEST]; + else if (at->head.seq >= head->seq) at = NULL; + if (at) *at = (Newest){file->st_dev, file->st_ino, *head}; + } + pthread_mutex_unlock(&known.lock); +} + +static bool newest_known(const struct stat *file, Head *out) { + bool found = false; + pthread_mutex_lock(&known.lock); + for (unsigned i = 0; i < NEWEST && !found; ++i) + if (known.newest[i].head.seq && known.newest[i].device == file->st_dev && known.newest[i].inode == file->st_ino) { + *out = known.newest[i].head; + found = true; + } pthread_mutex_unlock(&known.lock); + return found; } #ifdef PURE_STORE_TEST @@ -318,6 +353,7 @@ static void remember(const struct stat *file, const Head *head, int state) { void pure_tree_test_forget(void) { pthread_mutex_lock(&known.lock); memset(known.heads, 0, sizeof(known.heads)); + memset(known.newest, 0, sizeof(known.newest)); known.publishing.state = UNKNOWN; pthread_mutex_unlock(&known.lock); } @@ -339,11 +375,14 @@ static bool whole(int fd, const Head *head) { /* The newest head that counts. A reader passes over the head this process is * still making durable, so the process never answers with a commit that a * crash could take back; a writer never meets one (it is the only writer). */ -static bool pick(int fd, const struct stat *file, const unsigned char *slots[2], bool writer, Head *out) { +static bool pick(int fd, const struct stat *file, const unsigned char *slots[2], bool writer, Head *out, + uint64_t sequences[2]) { Head heads[2]; bool valid[2]; - for (unsigned i = 0; i < 2; ++i) - valid[i] = decode_head(slots[i], &heads[i]) && heads[i].end <= (uint64_t)file->st_size; + for (unsigned i = 0; i < 2; ++i) { + valid[i] = decode_head(slots[i], false, &heads[i]) && heads[i].end <= (uint64_t)file->st_size; + if (sequences) sequences[i] = valid[i] ? heads[i].seq : 0; + } unsigned newest = valid[1] && (!valid[0] || heads[1].seq > heads[0].seq); for (unsigned turn = 0; turn < 2; ++turn) { unsigned slot = turn ? !newest : newest; @@ -362,11 +401,45 @@ static bool pick(int fd, const struct stat *file, const unsigned char *slots[2], return false; } -static bool read_head(int fd, struct stat *file, bool writer, Head *out) { +/* The commit whose record follows head's bytes, if its own bytes are whole. */ +static bool follow(int fd, const struct stat *file, bool writer, const Head *head, Head *out) { + unsigned char record[SLOT]; + uint64_t size = (uint64_t)file->st_size; + Head next; + if (head->end > size || size - head->end < SLOT || !read_at(fd, record, SLOT, head->end) || + !decode_head(record, true, &next) || next.seq != head->seq + 1 || next.start != head->end + SLOT || + next.end > size) return false; + int state = recall(file, &next); + if (state == BROKEN || (state == PUBLISHING && !writer)) return false; + if (state == UNKNOWN) { + bool counts = whole(fd, &next); + remember(file, &next, counts ? CHECKED : BROKEN); + if (!counts) return false; + } + *out = next; + return true; +} + +/* Whether head's record is in the file as it was made. */ +static bool recorded(int fd, const struct stat *file, const Head *head) { + unsigned char stored[SLOT], made[SLOT]; + if (head->start < DATA + SLOT || head->end > (uint64_t)file->st_size) return false; + encode_head(made, record_magic, head); + return read_at(fd, stored, SLOT, head->start - SLOT) && !memcmp(stored, made, SLOT); +} + +/* The newest commit: from the newer slot's head that counts, or from the + * newest this process has seen in the file when its record is still there, + * along the records that follow. sequences gets the slots' (0: none). */ +static bool read_head(int fd, struct stat *file, bool writer, Head *out, uint64_t sequences[2]) { unsigned char slots[BLOCK + SLOT]; - return !fstat(fd, file) && S_ISREG(file->st_mode) && file->st_size >= 0 && - read_at(fd, slots, sizeof(slots), 0) && - pick(fd, file, (const unsigned char *[2]){slots, slots + BLOCK}, writer, out); + Head head, seen; + if (fstat(fd, file) || !S_ISREG(file->st_mode) || file->st_size < 0 || !read_at(fd, slots, sizeof(slots), 0) || + !pick(fd, file, (const unsigned char *[2]){slots, slots + BLOCK}, writer, &head, sequences)) return false; + if (newest_known(file, &seen) && seen.seq > head.seq && recorded(fd, file, &seen)) head = seen; + while (follow(fd, file, writer, &head, &head)) {} + *out = head; + return true; } static bool map_tree(int fd, const struct stat *file, const Head *head, Tree *tree) { @@ -859,7 +932,7 @@ static bool install(int directory, char temporary[96], int fd, Head *head) { struct stat file; head->start = head->end; head->check = digest_end(&(Digest){0}); - encode_head(slot, head); + encode_head(slot, head_magic, head); zero_fill(fd, head->end, tail_end(head->end)); bool ok = write_at(fd, slot, SLOT, 0) && write_at(fd, slot, SLOT, BLOCK) && sync_fd(fd) && !fstat(fd, &file); if (close(fd)) ok = false; @@ -930,7 +1003,7 @@ PureResult pure_store_init(const char *path) { struct stat file; int fd = openat(directory, tree_name, O_RDONLY | O_NOFOLLOW | O_CLOEXEC); if (fd >= 0) { - ok = read_head(fd, &file, true, &head); /* An unreadable file is never replaced. */ + ok = read_head(fd, &file, true, &head, NULL); /* An unreadable file is never replaced. */ close(fd); } else if (errno != ENOENT) ok = false; else { @@ -986,7 +1059,7 @@ PureResult pure_store_select(const char *path, const char *key, size_t offset, bool found; unsigned height; PureResult result = PURE_STORE_ERROR; - if (!read_head(fd, &file, false, &head) || !map_tree(fd, &file, &head, &tree) || + if (!read_head(fd, &file, false, &head, NULL) || !map_tree(fd, &file, &head, &tree) || !find(&tree, (Entry){head.catalog, head.catalog_bytes}, key, &index, &found, &document, &revision)) goto finish; if (!found) { result = PURE_NOT_FOUND; goto finish; } @@ -1046,6 +1119,7 @@ PureResult pure_store_get_range(const char *path, const char *key, size_t offset typedef struct { int directory, lock, fd; Head head; + uint64_t slots[2]; /* the sequences of the slots' heads */ Tree tree; struct stat file; bool turn; /* holds this process's writer turn */ @@ -1082,7 +1156,7 @@ static PureResult open_session(const char *path, Session *session) { if (!lock_writer(session->lock, false)) return errno == EACCES || errno == EAGAIN ? PURE_BUSY : PURE_STORE_ERROR; session->fd = openat(session->directory, tree_name, O_RDWR | O_NOFOLLOW | O_CLOEXEC); - if (session->fd < 0 || !read_head(session->fd, &session->file, true, &session->head)) + if (session->fd < 0 || !read_head(session->fd, &session->file, true, &session->head, session->slots)) return PURE_STORE_ERROR; /* A head this process did not make durable may be the last write of a * writer that died before its sync: make it durable before building on it. */ @@ -1094,10 +1168,14 @@ static PureResult open_session(const char *path, Session *session) { return map_tree(session->fd, &session->file, &session->head, &session->tree) ? PURE_OK : PURE_STORE_ERROR; } +/* A commit's bytes start after room for its record at the published end. */ +static uint64_t commit_start(const Session *session) { return session->head.end + SLOT; } + /* The documents' new nodes are already written at writer. Record each in * the catalog (revisions come in as the base and leave as the new one), then - * write the head and sync once: every document becomes visible at once, or - * none does. Readers of this process see the head only once it is durable. */ + * write the head as the record before them and sync once: every document + * becomes visible at once, or none does. Readers of this process see the + * head only once it is durable. */ #ifdef PURE_STORE_TEST static unsigned long publications; unsigned long pure_tree_test_publications(void) { return publications; } @@ -1130,12 +1208,19 @@ static PureResult publish(Session *session, Writer *writer, size_t count, const if (!written || fault(PURE_AFTER_HEADER) || fault(PURE_BEFORE_FILE_SYNC) || fault(PURE_BEFORE_RENAME)) return PURE_STORE_ERROR; Head published = {session->head.seq + 1, writer->at, catalog.ref, catalog.bytes, session->head.live, - session->head.end, digest_end(&writer->digest)}; - unsigned char slot[SLOT]; - encode_head(slot, &published); + commit_start(session), digest_end(&writer->digest)}; + unsigned char record[SLOT], slot[SLOT]; + encode_head(record, record_magic, &published); + encode_head(slot, head_magic, &published); + /* Every few commits the head goes into the older slot as well: one more + * range for that sync, and fewer records for a reader to follow. */ + uint64_t newer = session->slots[0] > session->slots[1] ? session->slots[0] : session->slots[1]; + unsigned older = session->slots[0] > session->slots[1]; + bool checkpoint = published.seq - newer >= CHECKPOINT; for (size_t i = 0; i < count; ++i) ++revisions[i]; /* Past this point the head may already be visible. */ remember(&session->file, &published, PUBLISHING); - bool durable = write_at(session->fd, slot, SLOT, (published.seq % 2) * BLOCK) && + bool durable = write_at(session->fd, record, SLOT, published.start - SLOT) && + (!checkpoint || write_at(session->fd, slot, SLOT, older * BLOCK)) && !fault(PURE_BEFORE_DIR_SYNC) && sync_data(session->fd); remember(&session->file, &published, durable ? DURABLE : CHECKED); if (!durable) return PURE_UNCERTAIN; @@ -1169,7 +1254,7 @@ static PureResult mutate(const char *path, const char *key, int64_t expected, writer = malloc(sizeof(*writer)); if (!writer || !rebuild(&session.tree, splice ? document : (Entry){0}, splice ? offset : 0, splice ? remove : 0, body, &next)) goto finish; - *writer = (Writer){.fd = session.fd, .at = session.head.end}; + *writer = (Writer){.fd = session.fd, .at = commit_start(&session)}; if (!write_root(&session.tree, writer, &next, false)) goto finish; result = publish(&session, writer, 1, &key, &next, revision); finish: @@ -1191,7 +1276,7 @@ PureResult pure_store_keys(const char *path, bool (*visit)(void *, const char *k Head head; struct stat file; PureResult result = PURE_STORE_ERROR; - if (read_head(fd, &file, false, &head) && map_tree(fd, &file, &head, &tree)) { + if (read_head(fd, &file, false, &head, NULL) && map_tree(fd, &file, &head, &tree)) { Entry catalog = {head.catalog, head.catalog_bytes}, document; unsigned char record[RECORD]; char key[KEY + 1] = {0}; @@ -1249,7 +1334,7 @@ static PureResult load_draft(PureDraft *draft) { uint64_t index; int64_t revision; bool found; - bool ok = read_head(fd, &info, false, &head) && map_tree(fd, &info, &head, &tree) && + bool ok = read_head(fd, &info, false, &head, NULL) && map_tree(fd, &info, &head, &tree) && find(&tree, (Entry){head.catalog, head.catalog_bytes}, draft->key, &index, &found, &document, &revision); close(fd); @@ -1324,18 +1409,18 @@ static PureResult refresh(PureStore *store) { store->inode = info.st_ino; store->head = (Head){0}; } - unsigned char slots[BLOCK + SLOT]; if (store->head.seq) { - /* A newer head lands in the other slot first; a torn or older one there - * cannot be newer. */ + /* The next commit's record follows the head's bytes; a slot shows a + * newer head only for a commit of the earlier format. */ const unsigned char *map = store->mapping->map; - if (decode64(map + (store->head.seq + 1) % 2 * BLOCK + 8) <= store->head.seq) return PURE_OK; - memcpy(slots, map, SLOT); - memcpy(slots + BLOCK, map + BLOCK, SLOT); - } else if (!read_at(store->fd, slots, sizeof(slots), 0)) return PURE_STORE_ERROR; + unsigned char next[16]; + bool newer = decode64(map + 8) > store->head.seq || decode64(map + BLOCK + 8) > store->head.seq || + (read_at(store->fd, next, sizeof(next), store->head.end) && !memcmp(next, record_magic, 8) && + decode64(next + 8) == store->head.seq + 1); + if (!newer) return PURE_OK; + } Head head; - if (!pick(store->fd, &info, (const unsigned char *[2]){slots, slots + BLOCK}, false, &head)) - return PURE_STORE_ERROR; + if (!read_head(store->fd, &info, false, &head, NULL)) return PURE_STORE_ERROR; if (store->mapping && head.seq == store->head.seq && head.check == store->head.check) return PURE_OK; Tree tree; Mapping *mapping = malloc(sizeof(*mapping)); @@ -1601,7 +1686,7 @@ static void commit_group(const char *path, Waiter *first) { if (count) { result = PURE_ALLOCATION; if ((writer = malloc(sizeof(*writer)))) { - *writer = (Writer){.fd = session.fd, .at = session.head.end}; + *writer = (Writer){.fd = session.fd, .at = commit_start(&session)}; bool written = true; for (size_t i = 0; i < count && written; ++i) { /* After compaction a draft's stored references name the old file. */ @@ -1759,7 +1844,7 @@ bool pure_tree_test_shape(const char *path, const char *key, unsigned *height, int64_t revision; bool found = false; *leaves = *small = 0; - bool ok = fd >= 0 && read_head(fd, &file, false, &head) && map_tree(fd, &file, &head, &tree) && + bool ok = fd >= 0 && read_head(fd, &file, false, &head, NULL) && map_tree(fd, &file, &head, &tree) && find(&tree, (Entry){head.catalog, head.catalog_bytes}, key, &index, &found, &document, &revision) && found && root_height(&tree, document, height) && (!document.bytes || shape(&tree, document, *height, true, leaves, small)); diff --git a/prototypes/connections/test-tree-store.c b/prototypes/connections/test-tree-store.c index bdb6573..1130acd 100644 --- a/prototypes/connections/test-tree-store.c +++ b/prototypes/connections/test-tree-store.c @@ -42,8 +42,9 @@ unsigned long pure_tree_test_syncs(void); void pure_tree_test_forget(void); /* The file: head slots in blocks 0 and 1 (sequence at +8, end at +16, - * catalog at +24), commits from DATA_START. */ -enum { KEYS = 4, CAPACITY = 1 << 20, SLOT_BLOCK = 4096, DATA_START = 8192 }; + * catalog at +24), commits from DATA_START, each a 128-byte record (its head) + * and then its bytes. */ +enum { KEYS = 4, CAPACITY = 1 << 20, SLOT_BLOCK = 4096, DATA_START = 8192, RECORD_SIZE = 128 }; typedef struct { unsigned char *bytes; size_t size; int64_t revision; } Oracle; static uint32_t random_value(uint32_t *state) { @@ -77,14 +78,28 @@ static uint64_t published_end(const char *path, const char *key) { return end; } -static uint64_t slot_field(int fd, unsigned slot, unsigned offset) { +static uint64_t field_at(int fd, uint64_t at) { unsigned char bytes[8]; - CHECK(pread(fd, bytes, 8, (off_t)(slot * SLOT_BLOCK + offset)) == 8); + CHECK(pread(fd, bytes, 8, (off_t)at) == 8); uint64_t value = 0; for (unsigned i = 0; i < 8; ++i) value |= (uint64_t)bytes[i] << (8 * i); return value; } +static uint64_t slot_field(int fd, unsigned slot, unsigned offset) { return field_at(fd, slot * SLOT_BLOCK + offset); } + +/* Where the newest head is: the newer slot's, or the last record after it. */ +static uint64_t newest_head(int fd) { + uint64_t at = slot_field(fd, 0, 8) > slot_field(fd, 1, 8) ? 0 : SLOT_BLOCK; + for (;;) { + uint64_t end = field_at(fd, at + 16); + unsigned char magic[8]; + if (pread(fd, magic, 8, (off_t)end) != 8 || memcmp(magic, "PUREREC1", 8) || + field_at(fd, end + 8) != field_at(fd, at + 8) + 1) return at; + at = end; + } +} + static void fill(unsigned char *bytes, size_t size, uint32_t *state) { for (size_t i = 0; i < size; ++i) bytes[i] = (unsigned char)random_value(state); } @@ -255,30 +270,84 @@ static void crashes(const char *path) { } } -/* A torn newest head slot exposes the previous commit, and the next writer - * overwrites that slot and the commit's bytes. */ +static void tear(const char *path, uint64_t at) { + char name[512]; + snprintf(name, sizeof(name), "%s/pure.tree", path); + int fd = open(name, O_RDWR); + unsigned char torn; + CHECK(fd >= 0 && pread(fd, &torn, 1, (off_t)at) == 1); + torn ^= 0x5a; + CHECK(pwrite(fd, &torn, 1, (off_t)at) == 1 && close(fd) == 0); +} + +/* A torn newest record exposes the previous commit to a new process, and the + * next writer overwrites that record and the commit's bytes. A torn slot + * costs only a longer walk: the other slot's head leads along the records. */ static void torn_head(const char *path) { unsigned char first[] = "first", second[] = "second"; int64_t revision; CHECK(pure_store_put(path, "torn", 0, (PureSpan){first, 5}, &revision) == PURE_OK); Oracle o = {first, 5, revision}; + uint64_t record = published_end(path, "torn"); /* where the next commit's record goes */ CHECK(pure_store_put(path, "torn", o.revision, (PureSpan){second, 6}, &revision) == PURE_OK); - char name[512]; - snprintf(name, sizeof(name), "%s/pure.tree", path); - int fd = open(name, O_RDWR); - CHECK(fd >= 0); - off_t newest = slot_field(fd, 0, 8) > slot_field(fd, 1, 8) ? 0 : SLOT_BLOCK; - unsigned char torn; - CHECK(pread(fd, &torn, 1, newest + 20) == 1); - torn ^= 0x5a; - CHECK(pwrite(fd, &torn, 1, newest + 20) == 1 && close(fd) == 0); + tear(path, SLOT_BLOCK + 20); + pure_tree_test_forget(); + expect(path, "torn", &(Oracle){second, 6, revision}); + tear(path, record + 20); + pure_tree_test_forget(); expect(path, "torn", &o); CHECK(pure_store_put(path, "torn", o.revision + 1, (PureSpan){first, 1}, &revision) == PURE_CONFLICT); CHECK(pure_store_put(path, "torn", o.revision, (PureSpan){second, 3}, &revision) == PURE_OK); o = (Oracle){second, 3, revision}; + CHECK(published_end(path, "torn") < record + RECORD_SIZE + 4096); /* it went where the torn one was */ + pure_tree_test_forget(); expect(path, "torn", &o); } +/* Commits are found along their records: from a slot's head, which every + * CHECKPOINT commits moves on, by a new process too; a damaged record ends + * the walk at the commit before it, which the next writer builds on. */ +static void records(const char *path) { + int64_t revision; + uint64_t ends[41]; + char text[16]; + CHECK(pure_store_put(path, "walk", 0, (PureSpan){(const unsigned char *)"0", 1}, &revision) == PURE_OK); + for (unsigned i = 1; i <= 40; ++i) { + ends[i] = published_end(path, "walk"); + snprintf(text, sizeof(text), "%u", i); + CHECK(pure_store_put(path, "walk", revision, (PureSpan){(const unsigned char *)text, strlen(text)}, + &revision) == PURE_OK); + } + char name[512]; + snprintf(name, sizeof(name), "%s/pure.tree", path); + int fd = open(name, O_RDONLY); + CHECK(fd >= 0); + uint64_t newest_slot = slot_field(fd, 0, 8) > slot_field(fd, 1, 8) ? slot_field(fd, 0, 8) : slot_field(fd, 1, 8); + CHECK(close(fd) == 0); + /* 42 commits (the empty file's first): heads in slots at 17 and 33. */ + CHECK(newest_slot == 33); + pure_tree_test_forget(); + expect(path, "walk", &(Oracle){(unsigned char *)"40", 2, 41}); + pid_t child = fork(); + CHECK(child >= 0); + if (!child) { + pure_tree_test_forget(); /* a process that never saw them */ + PureStoredView view; + _exit(pure_store_get(path, "walk", 16, &view) == PURE_OK && view.body.size == 2 && + !memcmp(view.body.data, "40", 2) && view.revision == 41 ? 0 : 1); + } + int status; + CHECK(waitpid(child, &status, 0) == child && WIFEXITED(status) && WEXITSTATUS(status) == 0); + /* Commit 37 ("37", revision 38) has a damaged record: the walk ends at 36. */ + tear(path, ends[37] + 30); + pure_tree_test_forget(); + expect(path, "walk", &(Oracle){(unsigned char *)"36", 2, 37}); + CHECK(pure_store_put(path, "walk", 37, (PureSpan){(const unsigned char *)"x", 1}, &revision) == PURE_OK); + CHECK(revision == 38 && published_end(path, "walk") < ends[38]); + pure_tree_test_forget(); + expect(path, "walk", &(Oracle){(unsigned char *)"x", 1, 38}); +} + /* A reader's view stays byte-identical while another process commits and * compacts; readers take no lock. */ static void isolation(const char *path) { @@ -372,7 +441,7 @@ static void revision_limit(const char *path) { snprintf(name, sizeof(name), "%s/pure.tree", path); int fd = open(name, O_RDWR); CHECK(fd >= 0); - uint64_t catalog = slot_field(fd, slot_field(fd, 0, 8) > slot_field(fd, 1, 8) ? 0 : 1, 24); + uint64_t catalog = field_at(fd, newest_head(fd) + 24); CHECK(catalog >> 63); const unsigned char maximum[] = {255,255,255,255,255,255,255,127}; off_t record = (off_t)(catalog & ((UINT64_C(1) << 62) - 1)); @@ -1046,7 +1115,7 @@ int main(void) { isolation, corruption, many_keys, revision_limit, keys, drafts, typing, draft_conflict, draft_relocation, draft_faults, draft_versions, anonymous_draft, batch, store_handle, threads, grouped, - lost_commit, pending_head, one_sync}; + lost_commit, pending_head, one_sync, records}; for (size_t i = 0; i < sizeof(checks) / sizeof(*checks); ++i) { char path[] = "/tmp/pure-tree-check-XXXXXX"; CHECK(mkdtemp(path) && pure_store_init(path) == PURE_OK); @@ -1057,6 +1126,6 @@ int main(void) { puts("{\"tree_store\":\"random-oracle-balance-held-views-one-byte-amplification-faults-" "process-crash-torn-head-lockless-isolation-compaction-corruption-1024-keys-revision-limit-key-listing-" "draft-oracle-typing-arena-conflict-relocation-commit-faults-held-versions-anonymous-" - "atomic-batch-runtime-keys-store-handle-threads-group-commit-lost-commit-pending-head-one-sync\"}"); + "atomic-batch-runtime-keys-store-handle-threads-group-commit-lost-commit-pending-head-one-sync-records\"}"); return 0; } diff --git a/research/experiments/012-tail-records/2026-09-26-ext4-linux-aarch64.json b/research/experiments/012-tail-records/2026-09-26-ext4-linux-aarch64.json new file mode 100644 index 0000000..457111d --- /dev/null +++ b/research/experiments/012-tail-records/2026-09-26-ext4-linux-aarch64.json @@ -0,0 +1,184 @@ +{ + "rounds": [ + { + "probe": [ + { + "way": "bytes, head in a slot at the start, fdatasync", + "bytes": 2048, + "p50_ms": 2.4, + "p90_ms": 3.11, + "max_ms": 62.79 + }, + { + "way": "head just before the bytes, fdatasync", + "bytes": 2048, + "p50_ms": 1.23, + "p90_ms": 3.85, + "max_ms": 12.27 + }, + { + "way": "bytes only, fdatasync", + "bytes": 2048, + "p50_ms": 1.23, + "p90_ms": 3.86, + "max_ms": 12.2 + }, + { + "way": "bytes, head in a slot at the start, fdatasync", + "bytes": 8192, + "p50_ms": 2.41, + "p90_ms": 4.51, + "max_ms": 24.86 + }, + { + "way": "head just before the bytes, fdatasync", + "bytes": 8192, + "p50_ms": 1.57, + "p90_ms": 4.36, + "max_ms": 56.75 + }, + { + "way": "bytes only, fdatasync", + "bytes": 8192, + "p50_ms": 1.18, + "p90_ms": 1.58, + "max_ms": 1.7 + } + ], + "commits": { + "heads in slots": { + "commits_per_second": 220, + "p50_ms": 2.48, + "p90_ms": 5.99, + "p99_ms": 59.68 + }, + "heads as records": { + "commits_per_second": 371, + "p50_ms": 1.29, + "p90_ms": 3.93, + "p99_ms": 52.98 + } + } + }, + { + "probe": [ + { + "way": "bytes, head in a slot at the start, fdatasync", + "bytes": 2048, + "p50_ms": 2.44, + "p90_ms": 5.4, + "max_ms": 13.3 + }, + { + "way": "head just before the bytes, fdatasync", + "bytes": 2048, + "p50_ms": 1.19, + "p90_ms": 1.76, + "max_ms": 12.16 + }, + { + "way": "bytes only, fdatasync", + "bytes": 2048, + "p50_ms": 1.2, + "p90_ms": 1.56, + "max_ms": 15.32 + }, + { + "way": "bytes, head in a slot at the start, fdatasync", + "bytes": 8192, + "p50_ms": 2.71, + "p90_ms": 8.51, + "max_ms": 23.39 + }, + { + "way": "head just before the bytes, fdatasync", + "bytes": 8192, + "p50_ms": 1.18, + "p90_ms": 1.6, + "max_ms": 32.89 + }, + { + "way": "bytes only, fdatasync", + "bytes": 8192, + "p50_ms": 1.21, + "p90_ms": 3.9, + "max_ms": 74.29 + } + ], + "commits": { + "heads as records": { + "commits_per_second": 372, + "p50_ms": 1.29, + "p90_ms": 4.04, + "p99_ms": 30.55 + }, + "heads in slots": { + "commits_per_second": 229, + "p50_ms": 2.52, + "p90_ms": 5.54, + "p99_ms": 61.86 + } + } + }, + { + "probe": [ + { + "way": "bytes, head in a slot at the start, fdatasync", + "bytes": 2048, + "p50_ms": 2.44, + "p90_ms": 3.94, + "max_ms": 53.75 + }, + { + "way": "head just before the bytes, fdatasync", + "bytes": 2048, + "p50_ms": 1.21, + "p90_ms": 1.85, + "max_ms": 4.43 + }, + { + "way": "bytes only, fdatasync", + "bytes": 2048, + "p50_ms": 1.21, + "p90_ms": 1.57, + "max_ms": 4.0 + }, + { + "way": "bytes, head in a slot at the start, fdatasync", + "bytes": 8192, + "p50_ms": 2.4, + "p90_ms": 3.15, + "max_ms": 36.75 + }, + { + "way": "head just before the bytes, fdatasync", + "bytes": 8192, + "p50_ms": 1.21, + "p90_ms": 4.48, + "max_ms": 33.15 + }, + { + "way": "bytes only, fdatasync", + "bytes": 8192, + "p50_ms": 1.12, + "p90_ms": 1.56, + "max_ms": 32.79 + } + ], + "commits": { + "heads in slots": { + "commits_per_second": 233, + "p50_ms": 2.55, + "p90_ms": 6.04, + "p99_ms": 34.19 + }, + "heads as records": { + "commits_per_second": 396, + "p50_ms": 1.26, + "p90_ms": 3.9, + "p99_ms": 28.43 + } + } + } + ] +} diff --git a/research/experiments/012-tail-records/probe.c b/research/experiments/012-tail-records/probe.c new file mode 100644 index 0000000..83c1ed6 --- /dev/null +++ b/research/experiments/012-tail-records/probe.c @@ -0,0 +1,71 @@ +#define _GNU_SOURCE +/* What a small commit's sync costs by where its head goes, on one device: + * a commit of SIZE bytes written over zeros written earlier (no new size or + * blocks, so no journal commit), 40 times per way. The ways run round-robin + * so device drift reaches all of them alike. + * probe DIRECTORY [SIZE] -> one JSON object per way (milliseconds). */ +#include <fcntl.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <unistd.h> + +static double now_ms(void) { + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return t.tv_sec * 1e3 + t.tv_nsec / 1e6; +} +static int order(const void *a, const void *b) { + double x = *(const double *)a, y = *(const double *)b; + return x < y ? -1 : x > y; +} +enum { WAYS = 3, ROUNDS = 40, HEAD = 128, DATA = 8192 }; +static const char *names[WAYS] = { + "bytes, head in a slot at the start, fdatasync", + "head just before the bytes, fdatasync", + "bytes only, fdatasync", +}; +int main(int argc, char **argv) { + const char *directory = argc > 1 ? argv[1] : "/var/tmp"; + size_t size = argc > 2 ? (size_t)atoi(argv[2]) : 8192; + char path[WAYS][512]; + int fd[WAYS]; + off_t end[WAYS]; + char *bytes = malloc(size), head[HEAD]; + if (!bytes) return 1; + memset(bytes, 'r', size); + for (int w = 0; w < WAYS; ++w) { + snprintf(path[w], sizeof(path[w]), "%s/pure-record-probe-%d", directory, w); + fd[w] = open(path[w], O_RDWR | O_CREAT | O_TRUNC, 0600); + if (fd[w] < 0) return 1; + size_t zeros_size = DATA + (size_t)(ROUNDS + 2) * (size + HEAD); + char *zeros = calloc(1, zeros_size); + if (!zeros || pwrite(fd[w], zeros, zeros_size, 0) != (ssize_t)zeros_size) return 1; + free(zeros); + fsync(fd[w]); + end[w] = DATA; + } + double t[WAYS][ROUNDS]; + for (int r = 0; r < ROUNDS; ++r) + for (int w = 0; w < WAYS; ++w) { + memset(head, 'h' + r % 2, sizeof(head)); + double start = now_ms(); + if (w == 1 && pwrite(fd[w], head, HEAD, end[w]) != HEAD) return 1; + off_t at = end[w] + (w == 1 ? HEAD : 0); + if (pwrite(fd[w], bytes, size, at) != (ssize_t)size) return 1; + end[w] = at + (off_t)size; + if (w == 0 && pwrite(fd[w], head, HEAD, (r % 2) * 4096) != HEAD) return 1; + fdatasync(fd[w]); + t[w][r] = now_ms() - start; + } + for (int w = 0; w < WAYS; ++w) { + qsort(t[w], ROUNDS, sizeof(double), order); + printf("{\"way\":\"%s\",\"bytes\":%zu,\"p50_ms\":%.2f,\"p90_ms\":%.2f,\"max_ms\":%.2f}\n", names[w], size, + t[w][ROUNDS / 2], t[w][ROUNDS * 9 / 10], t[w][ROUNDS - 1]); + close(fd[w]); + unlink(path[w]); + } + free(bytes); + return 0; +} diff --git a/research/experiments/012-tail-records/run.py b/research/experiments/012-tail-records/run.py new file mode 100755 index 0000000..7fc342e --- /dev/null +++ b/research/experiments/012-tail-records/run.py @@ -0,0 +1,69 @@ +#!/usr/bin/env python3 +"""Commit cost by where the head goes (see docs/research/081-tail-records.md). + +Runs probe.c (a small commit's sync with its head in a slot at the start, or +just before its bytes) for 2 KiB and 8 KiB commits, and ../010-one-sync-commit +/commits.c (tree store commit latency) built against the store of --before +(heads in slots) and the current one (heads as records before the bytes), +alternating their order per round so device drift reaches both alike. Prints +one JSON document. +""" +import argparse +import json +import shutil +import subprocess +import sys +import tempfile +from pathlib import Path + +HERE = Path(__file__).resolve().parent +ROOT = HERE.parents[2] +PURE = ROOT / 'prototypes' / 'connections' +COMMITS = HERE.parent / '010-one-sync-commit' / 'commits.c' + + +def build(output, sources): + subprocess.run(['cc', '-O2', '-std=c17', f'-I{PURE}', '-o', str(output)] + [str(s) for s in sources] + ['-lpthread'], + check=True) + + +def main(): + parser = argparse.ArgumentParser() + parser.add_argument('--directory', type=Path, default=Path('/var/tmp'), help='on the device to measure') + parser.add_argument('--before', default='2ef0d40', help='a revision with heads in slots') + parser.add_argument('--rounds', type=int, default=3) + parser.add_argument('--commits', type=int, default=400) + args = parser.parse_args() + with tempfile.TemporaryDirectory() as work: + work = Path(work) + before = work / 'store-tree-before.c' + before.write_text(subprocess.run(['git', '-C', str(ROOT), 'show', f'{args.before}:prototypes/connections/store-tree.c'], + capture_output=True, text=True, check=True).stdout) + build(work / 'probe', [HERE / 'probe.c']) + builds = {'heads in slots': work / 'commits-before', 'heads as records': work / 'commits-after'} + build(builds['heads in slots'], [COMMITS, before]) + build(builds['heads as records'], [COMMITS, PURE / 'store-tree.c']) + results = {'rounds': []} + for round_ in range(args.rounds): + measured = {'probe': [], 'commits': {}} + for size in (2048, 8192): + probe = subprocess.run([str(work / 'probe'), str(args.directory), str(size)], capture_output=True, + text=True, check=True) + measured['probe'] += [json.loads(line) for line in probe.stdout.splitlines()] + names = list(builds) if round_ % 2 == 0 else list(builds)[::-1] + for name in names: + store = Path(tempfile.mkdtemp(dir=args.directory, prefix='pure-commit-cost-')) + shutil.rmtree(store) + try: + run = subprocess.run([str(builds[name]), str(store), str(args.commits)], capture_output=True, text=True, + check=True) + measured['commits'][name] = json.loads(run.stdout) + finally: + shutil.rmtree(store, ignore_errors=True) + results['rounds'].append(measured) + print(json.dumps(measured), file=sys.stderr, flush=True) + print(json.dumps(results, indent=1)) + + +if __name__ == '__main__': + sys.exit(main()) |
