The best way to control Claude Code, Codex and more from any computer or phone

main
ts 501 lines 18.5 KB
Raw
1 import { RuntimeContext } from "alchemy/RuntimeContext";
2 import * as Effect from "effect/Effect";
3 /**
4 * The compaction alarm job (DESIGN.md §12.1) — the v2 storage plane.
5 *
6 * v1 keeps every object's bytes in a DO SQLite row, which caps a repo at the
7 * 10 GB DO limit and puts all clone bandwidth behind one single-threaded
8 * object. Compaction moves those bytes into **immutable, content-addressed
9 * R2 packs** and leaves only the index behind:
10 *
11 * ```
12 * objects.location: 'row' → 'pack'
13 * objects.zdata: BLOB → NULL (bytes now live in R2)
14 * objects.pack_id / pack_offset: (where in R2 they live)
15 * ```
16 *
17 * The pack we write is a **real git packfile** (`PACK`, version 2, count,
18 * then `varint(type,size) + zdata` per entry, then the SHA-1 trailer), so it
19 * can later be served verbatim as a clone bundle or a `packfile-uris`
20 * target. That works only because objects are stored **pre-deflated**: a
21 * pack entry is the stored bytes with a small header in front, so compaction
22 * is a copy, never a recompression.
23 *
24 * `pack_offset` deliberately addresses each object's **zdata span**, not its
25 * entry header — a read is then one ranged R2 GET returning exactly the
26 * bytes a `location='row'` object would have held (see `ObjectStore`).
27 *
28 * Bounded per run and alarm-re-armable, like the purge job: at most
29 * {@link MAX_OBJECTS_PER_RUN} objects / {@link MAX_BYTES_PER_RUN} bytes are
30 * moved per alarm, and the job reports whether more remain.
31 */
32 import type { BlobStoreError, BlobStoreShape } from "../BlobStore.ts";
33 import {
34 concatBytes,
35 bytesToHex,
36 encodeTypeSize,
37 makeSha1,
38 type PackEntryType,
39 } from "../Protocol/ObjectCodec.ts";
40 import { StoreError } from "../Protocol/Store.ts";
41 import { packKey, isWirePackId, packKeyOf } from "../Store/Keys.ts";
42 import { LIVE_OBJECTS } from "../Store/ObjectStore.ts";
43 import type { SqlClient } from "../Store/Sql.ts";
44
45 /** Objects moved per alarm run. */
46 export const MAX_OBJECTS_PER_RUN = 2_000;
47
48 /**
49 * Byte budget per alarm run (assembled in memory before the R2 put). Well
50 * under the 128 MB isolate limit; the streaming-multipart upgrade lifts it.
51 */
52 export const MAX_BYTES_PER_RUN = 32 * 1024 * 1024;
53
54 /**
55 * Loose-bytes threshold that arms compaction (DESIGN.md §12.1).
56 */
57 // Measured (DESIGN §22): a 44k-object repo left loose serves its dynamic
58 // path at ~3 MB/s from 44k SQLite point reads, and every metadata scan
59 // walks pages dense with inline zdata. Packing early is what makes reads
60 // window-coalesced and keeps the objects table small.
61 export const COMPACT_BYTES_THRESHOLD = 64 * 1024 * 1024;
62
63 /** Loose-object-count threshold that arms compaction. */
64 export const COMPACT_COUNT_THRESHOLD = 4_000;
65
66 /**
67 * Only blobs (git type 3) are ever moved into R2 packs. Commits, trees and
68 * tags stay `location='row'` in SQLite for the life of the repo.
69 *
70 * Measured (DESIGN §22): a fetch's want→have closure is a tree walk, and a
71 * tree walk over pack storage is the worst access pattern a window cache
72 * can see — trees are tiny and, packed in oid order, scattered across
73 * every 4 MiB window of every pack. On a 15.6k-object repo the walk alone
74 * cost 12 s of TTFB (27 s before batching); the same walk over rows is a
75 * handful of batched SELECTs. Trees + commits are a few percent of a
76 * repo's bytes, so keeping them local buys sub-second negotiation for
77 * every incremental fetch at negligible storage cost.
78 */
79 export const BLOB_TYPE = 3;
80
81 /** Outcome of one compaction run. */
82 export interface CompactOutcome {
83 /** Objects moved into the pack this run. */
84 readonly moved: number;
85 /** Bytes of zdata moved. */
86 readonly bytes: number;
87 /** sha1 of the pack written (the rows' `pack_id`), else `undefined`. */
88 readonly packId: string | undefined;
89 /** True when loose objects remain — the caller re-arms the alarm. */
90 readonly more: boolean;
91 }
92
93 /** Dependencies of {@link runCompactJob}. */
94 export interface CompactJobOptions {
95 readonly repoId: string;
96 readonly sql: SqlClient;
97 readonly blobs: BlobStoreShape;
98 readonly maxObjects?: number | undefined;
99 readonly maxBytes?: number | undefined;
100 }
101
102 interface LooseRow extends Record<string, string | number | ArrayBuffer | null> {
103 readonly oid: string;
104 readonly type: number;
105 readonly size: number;
106 readonly zsize: number;
107 readonly zdata: ArrayBuffer | null;
108 }
109
110 const runR2 =
111 (what: string) =>
112 <A>(effect: Effect.Effect<A, BlobStoreError, RuntimeContext>): Effect.Effect<A, StoreError> =>
113 effect.pipe(
114 Effect.mapError((error) => StoreError.make({ reason: `${what}: ${error.reason}` })),
115 Effect.provide(RuntimeContext.phantom),
116 );
117
118 const PACK_SIGNATURE = new Uint8Array([0x50, 0x41, 0x43, 0x4b]); // "PACK"
119
120 /** `PACK` + version 2 + object count. */
121 const packHeader = (count: number): Uint8Array => {
122 const header = new Uint8Array(12);
123 header.set(PACK_SIGNATURE, 0);
124 new DataView(header.buffer).setUint32(4, 2);
125 new DataView(header.buffer).setUint32(8, count);
126 return header;
127 };
128
129 /**
130 * Compacts up to one run's worth of loose objects into a single immutable
131 * R2 pack and repoints their rows at it.
132 *
133 * Ordering note: the R2 put happens **before** the row flip, so a crash in
134 * between leaves an unreferenced pack (harmless, content-addressed, GC-able)
135 * rather than rows pointing at bytes that do not exist.
136 */
137 export const runCompactJob = (
138 options: CompactJobOptions,
139 ): Effect.Effect<CompactOutcome, StoreError> =>
140 Effect.gen(function* () {
141 const maxObjects = options.maxObjects ?? MAX_OBJECTS_PER_RUN;
142 const maxBytes = options.maxBytes ?? MAX_BYTES_PER_RUN;
143
144 // Oldest-first by oid keeps runs deterministic and re-runnable.
145 const rows = yield* options.sql.all<LooseRow>(
146 `SELECT oid, type, size, zsize, zdata FROM objects
147 WHERE location = 'row' AND type = ${BLOB_TYPE} AND ${LIVE_OBJECTS}
148 ORDER BY oid LIMIT ?`,
149 maxObjects + 1,
150 );
151 const eligible = rows.slice(0, maxObjects);
152 if (eligible.length === 0) {
153 return { moved: 0, bytes: 0, packId: undefined, more: false };
154 }
155
156 // Assemble the pack, recording each object's zdata offset as we go.
157 const chunks: Array<Uint8Array> = [];
158 const placements: Array<{ oid: string; offset: number; zsize: number }> = [];
159 let offset = 0;
160 let budget = 0;
161 const push = (bytes: Uint8Array) => {
162 chunks.push(bytes);
163 offset += bytes.length;
164 };
165
166 const included: Array<LooseRow> = [];
167 for (const row of eligible) {
168 if (row.zdata === null) continue; // location='row' with NULL zdata: skip
169 const zdata = new Uint8Array(row.zdata);
170 if (budget > 0 && budget + zdata.length > maxBytes) break;
171 included.push(row);
172 budget += zdata.length;
173 push(
174 yield* Effect.sync(() =>
175 // Row types are the 1..4 non-delta git types (the ingest path only
176 // ever stores those), which is exactly `PackEntryType`.
177 encodeTypeSize(row.type as PackEntryType, row.size),
178 ),
179 );
180 placements.push({ oid: row.oid, offset, zsize: zdata.length });
181 push(zdata);
182 }
183 if (included.length === 0) {
184 return { moved: 0, bytes: 0, packId: undefined, more: false };
185 }
186
187 const header = packHeader(included.length);
188 const body = [header, ...chunks];
189 // One pass: the raw digest is the pack trailer, its hex is the pack id
190 // (content-addressed, so a retried run rewrites the identical key).
191 const trailer = yield* Effect.sync(() => {
192 const hash = makeSha1();
193 for (const chunk of body) hash.update(chunk);
194 return hash.digest();
195 });
196 const trailerHex = yield* Effect.sync(() => bytesToHex(trailer));
197
198 const total = body.reduce((sum, chunk) => sum + chunk.length, 0) + trailer.length;
199 const pack = yield* Effect.sync(() => {
200 const out = new Uint8Array(total);
201 let at = 0;
202 for (const chunk of body) {
203 out.set(chunk, at);
204 at += chunk.length;
205 }
206 out.set(trailer, at);
207 return out;
208 });
209
210 // Offsets recorded above are relative to the start of the entry stream;
211 // shift them past the 12-byte header to get absolute file offsets.
212 const packId = trailerHex;
213 const key = packKey(options.repoId, packId);
214 yield* runR2(`blob put ${key}`)(options.blobs.put(key, pack, { contentLength: pack.length }));
215
216 yield* options.sql
217 .transactionSync((raw) => {
218 for (const placement of placements) {
219 raw.exec(
220 `UPDATE objects
221 SET location = 'pack', pack_id = ?, pack_offset = ?, zdata = NULL
222 WHERE oid = ? AND location = 'row' AND ${LIVE_OBJECTS}`,
223 packId,
224 placement.offset + header.length,
225 placement.oid,
226 );
227 }
228 })
229 .pipe(Effect.asVoid);
230
231 return {
232 moved: included.length,
233 bytes: budget,
234 packId,
235 more: rows.length > maxObjects || included.length < eligible.length,
236 };
237 });
238
239 /**
240 * True when the repo has enough loose bytes/objects to be worth compacting
241 * (DESIGN.md §12.1 thresholds).
242 */
243 export const shouldCompact = (
244 sql: SqlClient,
245 options?: {
246 readonly bytesThreshold?: number | undefined;
247 readonly countThreshold?: number | undefined;
248 },
249 ): Effect.Effect<boolean, StoreError> =>
250 Effect.gen(function* () {
251 const row = yield* sql.first<{ n: number; bytes: number }>(
252 `SELECT COUNT(*) AS n, COALESCE(SUM(zsize), 0) AS bytes
253 FROM objects WHERE location = 'row' AND type = ${BLOB_TYPE} AND ${LIVE_OBJECTS}`,
254 );
255 if (row === undefined) return false;
256 return (
257 row.bytes >= (options?.bytesThreshold ?? COMPACT_BYTES_THRESHOLD) ||
258 row.n >= (options?.countThreshold ?? COMPACT_COUNT_THRESHOLD)
259 );
260 });
261
262 // ─────────────────────────────────────────────────────────────────────────────
263 // Geometric pack merging (DESIGN.md §21, Continuity learnings)
264 // ─────────────────────────────────────────────────────────────────────────────
265
266 /**
267 * Merge whenever a pack is smaller than FACTOR × the sum of all packs
268 * smaller than it — the classic geometric invariant. Holding it bounds
269 * pack count at O(log(total bytes)), which bounds the fan-out of ranged
270 * reads on the serving path.
271 */
272 export const GEOMETRIC_FACTOR = 2;
273
274 /** Per-run ceiling on merged input, keeping a run inside the alarm budget. */
275 export const MAX_MERGE_INPUT_BYTES = 96 * 1024 * 1024;
276
277 export interface MergeOutcome {
278 /** Source packs merged this run (0 = the invariant already holds). */
279 readonly packs: number;
280 /** Objects now pointing at the merged pack. */
281 readonly moved: number;
282 /** Bytes of merged pack written. */
283 readonly bytes: number;
284 readonly packId: string | undefined;
285 /**
286 * R2 keys of the source packs, now unreferenced. NOT deleted here: an
287 * in-flight read planned before the row flip may still hold spans into
288 * them, so the caller deletes these on a LATER run (grace period).
289 */
290 readonly pendingDelete: ReadonlyArray<string>;
291 /** More merging remains (input cap hit); re-arm the alarm. */
292 readonly more: boolean;
293 }
294
295 const noMerge: MergeOutcome = {
296 packs: 0,
297 moved: 0,
298 bytes: 0,
299 packId: undefined,
300 pendingDelete: [],
301 more: false,
302 };
303
304 /**
305 * Restores the geometric invariant over a repo's compacted packs by
306 * merging the smallest run of violating packs into one.
307 *
308 * Merging is pure concatenation — our packs store non-delta entries
309 * (varint header + zdata), so a merged pack is `header(Σcounts) +
310 * body₁ + … + bodyₙ + sha1`, and every row's offset shifts by a single
311 * per-source delta (the bytes of bodies concatenated before it). No
312 * recompression, no delta re-resolution: O(bytes) of blob IO plus one
313 * UPDATE per source pack.
314 *
315 * Ordering matches {@link runCompactJob}: the merged pack is written
316 * before the row flip (a crash between leaves an unreferenced,
317 * content-addressed, GC-able pack), and source packs are only deleted by
318 * the caller on a later run.
319 */
320 export const runGeometricMergeJob = (options: {
321 readonly repoId: string;
322 readonly sql: SqlClient;
323 readonly blobs: BlobStoreShape;
324 readonly maxInputBytes?: number | undefined;
325 }): Effect.Effect<MergeOutcome, StoreError> =>
326 Effect.gen(function* () {
327 const maxInput = options.maxInputBytes ?? MAX_MERGE_INPUT_BYTES;
328
329 const rows = yield* options.sql.all<{ pack_id: string; n: number }>(
330 `SELECT pack_id, COUNT(*) AS n FROM objects
331 WHERE location = 'pack' AND pack_id IS NOT NULL
332 GROUP BY pack_id`,
333 );
334 if (rows.length < 2) return noMerge;
335
336 // Exact byte sizes from the store (offsets are absolute file offsets,
337 // so the merge math needs real lengths, not row sums).
338 const packs: Array<{ id: string; count: number; size: number }> = [];
339 for (const row of rows) {
340 const meta = yield* runR2(`merge head ${row.pack_id}`)(
341 options.blobs.head(packKeyOf(options.repoId, row.pack_id)),
342 );
343 // A pack R2 lost (or a crash orphaned) cannot be merged; skip it —
344 // reads through it will surface the real error on their own path.
345 if (meta !== null) {
346 packs.push({ id: row.pack_id, count: row.n, size: meta.size });
347 }
348 }
349 if (packs.length < 2) return noMerge;
350 packs.sort((a, b) => a.size - b.size);
351
352 // Geometric scan from the smallest: everything up to the last
353 // violation must merge.
354 let cumulative = 0;
355 let mergeCount = 0;
356 for (let i = 0; i < packs.length; i++) {
357 if (i >= 1 && packs[i]!.size < GEOMETRIC_FACTOR * cumulative) {
358 mergeCount = i + 1;
359 }
360 cumulative += packs[i]!.size;
361 }
362 if (mergeCount < 2) return noMerge;
363
364 // Cap the run's input; ≥2 sources or there is nothing useful to do.
365 let inputBytes = 0;
366 let take = 0;
367 while (take < mergeCount && inputBytes + packs[take]!.size <= maxInput) {
368 inputBytes += packs[take]!.size;
369 take++;
370 }
371 if (take < 2) return noMerge;
372 const sources = packs.slice(0, take);
373 const more = take < mergeCount;
374
375 // Read + validate each source, strip framing, record body deltas.
376 const bodies: Array<Uint8Array> = [];
377 const deltas: Array<{ id: string; delta: number }> = [];
378 // Promoted wire packs (DESIGN §22.5) also carry the push's trees,
379 // commits and delta entries, so they are REWRITTEN rather than
380 // concatenated: only the rows that reference them are copied, each as
381 // a regenerated typeSize header + its compressed span, and every row
382 // is repointed individually.
383 const rewrites: Array<{ oid: string; offset: number }> = [];
384 let totalCount = 0;
385 let bodyOffset = 0;
386 for (const source of sources) {
387 const object = yield* runR2(`merge get ${source.id}`)(
388 options.blobs.get(packKeyOf(options.repoId, source.id)),
389 );
390 if (object === null) return noMerge; // vanished mid-run: retry later
391 const bytes = yield* runR2(`merge read ${source.id}`)(object.bytes);
392 if (isWirePackId(source.id)) {
393 const rows = yield* options.sql.all<{
394 oid: string;
395 type: number;
396 size: number;
397 zsize: number;
398 pack_offset: number;
399 }>(
400 `SELECT oid, type, size, zsize, pack_offset FROM objects
401 WHERE location = 'pack' AND pack_id = ? ORDER BY pack_offset`,
402 source.id,
403 );
404 const pieces: Array<Uint8Array> = [];
405 let at = bodyOffset;
406 for (const row of rows) {
407 if (row.pack_offset + row.zsize > bytes.length) {
408 return yield* StoreError.make({
409 reason: `merge: ${row.oid} points past the end of wire pack ${source.id}`,
410 });
411 }
412 const head = encodeTypeSize(row.type as PackEntryType, row.size);
413 pieces.push(head, bytes.subarray(row.pack_offset, row.pack_offset + row.zsize));
414 rewrites.push({ oid: row.oid, offset: 12 + at + head.length });
415 at += head.length + row.zsize;
416 }
417 const body = concatBytes(pieces);
418 totalCount += rows.length;
419 bodies.push(body);
420 bodyOffset += body.length;
421 continue;
422 }
423 if (
424 bytes.length < 32 ||
425 bytes[0] !== 0x50 ||
426 bytes[1] !== 0x41 ||
427 bytes[2] !== 0x43 ||
428 bytes[3] !== 0x4b
429 ) {
430 return yield* StoreError.make({
431 reason: `merge: pack ${source.id} is not a packfile`,
432 });
433 }
434 const view = new DataView(bytes.buffer, bytes.byteOffset);
435 totalCount += view.getUint32(8);
436 deltas.push({ id: source.id, delta: bodyOffset });
437 const body = bytes.subarray(12, bytes.length - 20);
438 bodies.push(body);
439 bodyOffset += body.length;
440 }
441 const header = packHeader(totalCount);
442 const trailer = yield* Effect.sync(() => {
443 const hash = makeSha1();
444 hash.update(header);
445 for (const body of bodies) hash.update(body);
446 return hash.digest();
447 });
448 const packId = yield* Effect.sync(() => bytesToHex(trailer));
449 const merged = yield* Effect.sync(() => {
450 const out = new Uint8Array(12 + bodyOffset + 20);
451 out.set(header, 0);
452 let at = 12;
453 for (const body of bodies) {
454 out.set(body, at);
455 at += body.length;
456 }
457 out.set(trailer, at);
458 return out;
459 });
460
461 const key = packKey(options.repoId, packId);
462 yield* runR2(`merge put ${key}`)(
463 options.blobs.put(key, merged, { contentLength: merged.length }),
464 );
465
466 // One additive UPDATE per source: new_offset = old_offset + delta
467 // (old header and new header are both 12 bytes, so they cancel).
468 let moved = 0;
469 yield* options.sql
470 .transactionSync((raw) => {
471 for (const { id, delta } of deltas) {
472 raw.exec(
473 `UPDATE objects
474 SET pack_id = ?, pack_offset = pack_offset + ?
475 WHERE location = 'pack' AND pack_id = ?`,
476 packId,
477 delta,
478 id,
479 );
480 }
481 for (const { oid, offset } of rewrites) {
482 raw.exec(
483 `UPDATE objects SET pack_id = ?, pack_offset = ? WHERE oid = ?`,
484 packId,
485 offset,
486 oid,
487 );
488 }
489 })
490 .pipe(Effect.asVoid);
491 moved = sources.reduce((sum, source) => sum + source.count, 0);
492
493 return {
494 packs: sources.length,
495 moved,
496 bytes: merged.length,
497 packId,
498 pendingDelete: sources.map((source) => packKeyOf(options.repoId, source.id)),
499 more,
500 };
501 });