Bobcatsfan33/substrate

## 这是什么 Substrate 是以下两个数据库底层的存储引擎： - **[FlockDB](https://github.com/Bobcatsfan33/flockdb)** — 数以千计的小型分析型数据库，它们在对象存储中休眠，并在 250 毫秒内唤醒。为你所有的 40,000 个客户提供一个*真正的*独立数据库，而不是一个 `tenant_id` 列。 - **[LoomDB](https://github.com/Bobcatsfan33/loomdb)** — 一个 agent 原生数据库，其会话即为分支。一个 agent 尝试三种假设，合并有效的那一个，回退无效的那两个——并且每一次写入都会记录其派生来源。 两款产品，两个市场，**一个棘手的问题**： 本仓库一举解决了这个问题。你可能不想直接依赖它——你想要的是上面两个数据库之一。它以开源形式存在，因为一个无人能审计的持久性声明毫无价值。 ## 核心理念 一个页面是一个字节块，其**身份标识即是它的内容**：`PageId = BLAKE3(bytes)`。一个 *manifest* 将逻辑页码映射到这些 id，并且其本身也是内容寻址的。因此，数据库的整个状态就是一个 32 字节的值——这意味着： | 操作 | 实际发生的情况 | 成本 | |---|---|---| | `snapshot()` | 记住一个 `ManifestId` | **O(1)** | | `fork()` | 从一个 `ManifestId` 开启一个新的 head | **O(1)** | | `rewind()` | 将 head 移动到较旧的 `ManifestId` | **O(1)** | | `diff()` | 比较两个已排序的哈希列表 | O(*changed*) | 在上述任何操作中，连一个字节都没有被复制。 ``` use substrate_pager::{Pager, PageStore, StoreConfig}; let db = Pager::in_memory(StoreConfig::default())?; let mut txn = db.begin()?; db.write(&mut txn, 0, b"the original".to_vec())?; let v1 = db.commit(txn)?; // a snapshot is just this id let experiment = db.fork(&v1)?; // copies nothing let mut txn = experiment.begin()?; experiment.write(&mut txn, 0, b"a wild idea".to_vec())?; experiment.commit(txn)?; // Two databases now. The base never noticed. assert_eq!(db.read_head(0)?.as_bytes(), b"the original"); assert_eq!(experiment.read_head(0)?.as_bytes(), b"a wild idea"); ``` 这里的 fork 隔离不是*强制执行*的——而是**结构性的**。一个 manifest 是一个不可变的值，而 fork 持有的是另一个不同的值。不存在任何代码路径可以将写入从 fork 泄漏到其 base 中，这比“我们添加了一个检查”的说法要有力得多。 ## 为什么你应该对此保持怀疑，以及我们是如何应对的 这个引擎开发得非常快，并且很大程度上是由 AI 编写的。如果你打算将无法承受丢失的数据放入其中，这应该让你感到担忧。这也让我们感到担忧。满腔热情并不能作为反驳的证据，所以这里提供的是确凿的证据： **模型 oracle。** 每个核心原语都有第二个实现——一个原始的 map-of-maps，它会在每次 fork 时复制整个数据库，速度慢得离谱，但*显然*是正确的。属性测试针对两者运行随机化的操作序列，并断言它们对每一个字节的判断都是一致的。当它们不一致时，其中一个就是错的，我们会在几毫秒内发现，而不是在你的故障频道里。它已经发现了真实引擎中的一些真实 bug。 **覆盖率引导的 fuzzing。** 相同的不变量，由一个 fuzzer 驱动，它会观察引擎采用哪些分支，并引导向那些没有人触及的分支。每分钟执行 25 万次，而且磁盘上的格式无法在不改变 fuzz 目标的情况下于同一提交中发生改变。 **崩溃注入。** 一个文件系统层，它会在任何字节边界处终止写入——在页面写入内、在 WAL 记录内、在 commit 的 fsync 和 manifest 安装之间。**在 CI 中进行 10,000 次随机化的崩溃与恢复循环**（在本地为 50,000 次），外加针对真实磁盘的运行，此时 `fsync` 是一次真正的系统调用。其属性是：在任何地方崩溃后，恢复的存储等同于**已提交事务的某个前缀**，并且任何被 `commit()` 确认的内容仍然存在。 它已经发现了三个真实的持久化 bug——包括一个非幂等的恢复过程，它本会破坏任何*在从崩溃中恢复时*崩溃的数据库。 **确定性重放。** 同一日志重放两次会产生字节完全相同的 manifest。如果恢复不是确定性的，它就无法验证，这里的其他一切也就毫无意义。 我们宁愿你阅读测试代码，而不是营销辞令。 ## 我们绝不违背的设计规则 这些都写在 [CLAUDE.md](CLAUDE.md) 中，每一条规则的存在都是因为违背它会产生特定的、代价高昂的故障： - **提交顺序是神圣不可侵犯的。** Page bytes → CAS (fsync) → WAL commit record (fsync) → manifest update。在 commit 记录之前的崩溃会留下孤立的页面，由 GC 清理。在它之后的崩溃则是一个已提交的事务。在这两者之间没有任何状态。 - **活跃性来源于 manifest，绝不是计数器文件。** GC 通过读取 manifest 来重新计算哪些数据是活跃的。引用计数文件是关于哪些字节处于活跃状态的第二个事实来源，而损坏的文件会悄悄删除活跃数据。 - **库代码中没有 panic。** 没有 `unwrap`，没有 `expect`。存储引擎中的 panic 是一次计划外的进程死亡，而在 commit 期间的计划外进程死亡正是崩溃恢复机制旨在抵御的灾难。 - **核心层没有 `async`。** 确定性重放和崩溃注入需要确定性的执行。 - **任何地方都没有网络。** 除了一个对象存储客户端，并且 `--features airgap` 在编译时就消除了这种可能性——这是一种审计员可以通过阅读二进制文件来验证的“截肢”手术，而不是一个你可能设置错误的配置标志。 ## 状态 — `substrate-v1.0` · **API 已冻结** **P1–P5 已完成。** API 已冻结并适用 semver：请参阅 [docs/substrate-api.md](docs/substrate-api.md) 了解接口全貌和兼容性承诺。 - `substrate-pager` — 内容寻址页面、CAS、manifests、O(1) 的 fork/snapshot/rewind、三方 diff、崩溃安全的 GC。模型 oracle + fuzz 目标。 - `substrate-wal` — 预写日志和提交协议。确定性、幂等的恢复。**在 CI 中进行 10,000 次崩溃与恢复循环。** - `substrate-store` — 对象存储分层。**将数据库 `sleep()` 到 S3 中，其成本仅为它字节数的价格；将其 `wake()`，第一行数据将在 250 毫秒内返回。** 密钥在 pool 范围内划定，因此即使字节完全相同，两个不同的分类边界也无法共享同一个页面。 ``` let token = db.sleep().await?; // the whole database is now ~20 bytes of meaning // ...wipe the machine... let db = TieredStore::wake(new_disk, remote, &token).await?; // and it's back ``` Manifest 是即时获取的；页面则是延迟获取的，在第一次触及它们的读取操作发生时才会获取。唤醒一个 100 GB 的数据库并不需要移动 100 GB 的数据。 - `substrate-pager` (P4) — **深层的 branch trees。** 层层嵌套的 fork、在深度 8 处折叠的 overlay manifests、merge-base 计算、具名 branches 和 tags。 ### 实测结果（`cargo bench -p substrate-pager`） | 操作 | 目标 | 实测结果 | |---|---|---| | fork | < 1 ms | **98 ns** — 从 100 到 16,384 个页面保持平稳 | | snapshot | < 1 ms | **15 ns** | | 读取单个页面，overlay 深度 8 对比平铺 | < 20 % 开销 | **+1.4 %** (64 KiB pages) | | 三方 diff，1 GiB 逻辑空间，16 个已更改页面 | 与*更改的部分*成比例 | **7.4 ms** | 基准测试在它们刚出现时就捕捉到了两个真实的性能 bug：每次页面读取都在反序列化整个 manifest（**1.9 ms → 180 ns**），并且每次单页面提交都在解析整个 base manifest，因此 overlays 为自己付出了代价却毫无产出（**3.7 ms → 577 µs**）。这两个修复都已包含在内。客观的附加说明记录在 [docs/02 §7.1](docs/02-embedded-single-node-engine-architecture.md) 中。 - **P5** — 强化加固。完整性清理（能发现*没人读过*的页面中的数据腐化）、在安装前**验证副本**的基于对象存储的修复、无库依赖的基于 trait 的指标挂钩，以及已冻结的 v1.0 API 表面层。 - **P6** `substrate-security` — 页面加密（XChaCha20-Poly1305，pool→数据库的密钥层级）和离线授权（Ed25519，已具备 ML-DSA 支持能力）。 **Substrate 已功能完备。** 下一步是建立在此基础上的 FlockDB 和 LoomDB。 暂不包含：SQL（那是 FlockDB 的事），agents（那是 LoomDB 的事）。**API 现已稳定——请放心在此之上构建。** ## 目录结构 ``` crates/ substrate-pager/ pages, CAS, manifests, branch trees, GC (sync — no async, ever) substrate-wal/ segments, commit protocol, recovery (sync) substrate-store/ object storage, tiering, sleep/wake (async, tokio) substrate-security/ encryption at rest, offline licensing testing/ fuzz/ cargo-fuzz targets + crash injection integration/ cross-crate lifecycle tests docs/ the architecture of record — read 02, 03, 04 ``` ## 构建 ``` cargo test --workspace # unit + property + doc tests cargo test --workspace --features substrate-pager/airgap # must pass with no network cargo clippy --workspace --all-targets -- -D warnings cargo +nightly fuzz run --fuzz-dir testing/fuzz pager_ops # the oracle, hostile edition ``` ## 推荐阅读顺序 1. [`docs/04`](docs/04-flockdb-loomdb-unified-roadmap.md) — 为什么是一个引擎和两款产品 2. [`docs/02`](docs/02-embedded-single-node-engine-architecture.md) — 引擎与机群层 (FlockDB) 3. [`docs/03`](docs/03-agent-native-database-architecture.md) — 分支/合并、起源溯源、污染与召回 (LoomDB) 4. [`docs/substrate-api.md`](docs/substrate-api.md) — 已冻结的 v1.0 表面层与兼容性承诺 5. [`docs/threat-model.md`](docs/threat-model.md) — 我们防御什么，以及**我们不防御什么** 6. [`CLAUDE.md`](CLAUDE.md) — 规则，以及每项规则背后的理由 ## 许可证 Apache-2.0。该引擎开源，因为你无法审计的持久化只不过是个传言。