Lib.rs

具有并发读取器和写入器（写入器相互排除）的事务性磁盘数据结构

此crate基于无std crate sanakirja-core，其目标是实现不同的数据结构。

以下是如何使用它的示例（从64个页面，2个版本开始，下面将详细介绍这意味着什么）。文件会根据需要自动增长。

use sanakirja::*;
let dir = tempfile::tempdir().unwrap();
let path = dir.path().join("db");
let env = Env::new(&path, 1 << 20, 2).unwrap();
let mut txn = Env::mut_txn_begin(&env).unwrap();
let mut db = btree::create_db::<_, u64, u64>(&mut txn).unwrap();
for i in 0..100_000u64 {
    btree::put(&mut txn, &mut db, &i, &(i*i)).unwrap();
}
let root_db = 0;
txn.set_root(root_db, db.db);
txn.commit().unwrap();
let txn = Env::txn_begin(&env).unwrap();
let db: btree::Db<u64, u64> = txn.root_db(root_db).unwrap();
assert_eq!(btree::get(&txn, &db, &50_000, None).unwrap(), Some((&50_000, &(50_000 * 50_000))));
for entry in btree::iter(&txn, &db, None).unwrap() {
  let (k, v) = entry.unwrap();
  assert_eq!(*k * *k, *v)
}

Sanakirja数据库的二进制格式如下

• 在文件初始化时设置了一个固定数量的“当前版本”。如果一个文件有n个版本，那么对于0到n-1之间的所有k（包括），第k个页面（即介于k * 4096和(k+1) * 4096之间的字节位置，也写作k << 12和(k+1) << 12），存储该版本的数据，并称为该版本的“根页面”。

  这是处理并发访问的一种方法：确实，可变事务不会排除读取器，但开始于可变事务提交之前读取的读取器将继续按提交之前的状态读取数据库。然而，这意味着必须保留较旧版本的数据库“存活”，而这里的“当前版本数量”是同时可以保留的版本数量的限制。

  当读取器开始时，它会对表示最新提交版本的文件获取共享文件锁。当写入器开始时，它会对表示最旧提交版本的文件获取独占文件锁。这意味着如果读取器仍在读取该版本，则写入器将等待独占锁。

  在获取锁之后，写入者（也称为“可变事务”或MutTxn）将 youngest committed version 的整个 root 页面复制到 oldest committed version 的 root 页面，从而删除了 oldest version 的 root 页面。

• Root 页面具有以下格式：一个 32 字节的头部（下面将描述），然后是 4064 字节，可按更自由或更受限的格式使用。当前的实现定义了 MutTxn 上的两个方法，MutTxn::set_root 和 MutTxn::remove_root，将此空间视为类型 [u64; 510] 的数组。这些方法的合理用途是引用在文件中分配的不同数据结构，如指向 B 树 root 页面的文件偏移量。

  现在，关于头部，前 16 字节是版本标识符，后面是两个字节：`root` 是当前可变事务（如果有当前可变事务）或下一个可变事务（否则）使用的版本。`n_roots` 字段是版本总数。

  #[repr(C)]
  pub struct GlobalHeader {
      /// Version of Sanakirja
      pub version: u16,
      /// Which page is currently the root page? (only valid for page 0).
      pub root: u8,
      /// Total number of versions (or "root pages")
      pub n_roots: u8,
      /// CRC of this page.
      pub crc: u32,
      /// First free page at the end of the file (only valid for page 0).
      pub length: u64,
      /// Offset of the free list.
      pub free_db: u64,
      /// Offset of the RC database.
      pub rc_db: u64,
  }