DBDB in Rust, inspired by 500lines/dbdb

RAII模式的文件锁

• 如何处理FileStorage中的File字段加文件锁
• 为FileStorage实现cluFlock::FromElement和Deref
• 如果lock对象是&mut File，在使用时出现自引用问题, 所以使用了File::try_clone()
• 跨多个调用，需要维护Guard变量，但不使用，合适吗？

递归类型定义

• 树节点

  Rc<RefCell<T>>就可以看成是Python的变量名，采用引用计数回收内存

• 代理节点的递归

  打算给Agent写一个trait，Agent<T>，然后每个TreeNode的左右子节点指向Agent的泛型，使用时用TreeNode<V, N>确定TreeNode的具体类型，这样就可以设置不同的V和N，得到不同行为的store、get、get_mut

• 利用DBTree trait分离具体的树实现，LogicalTree只用来管理Storage的并发，读写请求都直接转给DBTree

  但是，DBTree工作需要传入Storage的独占引用，DBTree本身也要mut，就给LogicalTree造成了所有权的冲突。解决选择：1. 把Storage Rc化. 2. Storage放入DBTree，直接利用本身已经Rc的NodeAgentCell。第二种实际就是未设计DBTree时的方案，每次操作只会使用Storage的独占引用，DBTree则由NodeAgentCell作为根节点来表示，每次操作克隆一份，用完直接销毁就好。因此，似乎这里应该选择第一种方案，DBTree借出独占引用，然后使用共享所有权的Storage。

  但两个方式都没有逃过Rc的范围，那这种两个mut对象的协作的场景有更好的解决方案吗？

• 共享Storage后，运行时显示BorrowMutError，重复借出独占引用，调用栈定位到put方法：

  if self.guard.is_none() {
      self.begin()?;
      let storage = self.storage.clone();
      let storage = &mut *storage.borrow_mut();
      self.tree.insert(key, value, storage)?;
      self.commit()?;
  }
      ...

  确实commit中也向storage索要了独占引用。第一反应是insert之后drop(storage);，不过错误依旧。想起来借用检查是和作用域相关的，所以改成下面这样就没问题了

  if self.guard.is_none() {
      self.begin()?;
      {
          let storage = self.storage.clone();
          let storage = &mut *storage.borrow_mut();
          self.tree.insert(key, value, storage)?;
      }
      self.commit()?;
  }
      ...

  记下来作为之后理解drop和运行时检查的材料

类型参数(type parameter)和关联类型(associated type)该怎么选？

关联类型更强调与trait的实现类型的唯一对应。实现类型一旦确定，关联类型就不要改变了。如果使用类型参数，那么对同一个实现类型，可以用impl语句多次实现。

但也不能说实现类型只有一个关联类型。比如类型参数和关联类型同时使用时。

trait Foo<T> {
    type Inner;
    fn foo(&self, t: T) -> Self::Inner;
}

struct F;

impl Foo<i32> for F {
    type Inner = i32;
    fn foo(&self, t: i32) -> Self::Inner {
        t + 42
    }
}


impl Foo<String> for F {
    type Inner = String;
    fn foo(&self, t: String) -> Self::Inner {
        format!("String:{:?} 42", t)
    }
}

fn main() {
    let f = F;
    println!("{}", f.foo("answer".to_owned()));
    println!("{}", f.foo(12));
}

一般来说先从关联类型入手，当需要更高的灵活性时采用类型参数 关联类型的Trait绑定还是还在proposal阶段？

树的大小

处理 insert 和 delete 时不能采用 node.size = node.left.size + node.right.size 的方式来更新size，因为访问查找路径外的size字段都会引起一次多余的IO，太不划算。所以给insert delete的返回值加一个usize，指示是否真的插入或删除了一个节点，方便修改当前节点的size

当然delta_size可以通过先find一次来去掉。

这个方式的成本在于，每次会多一次遍历。但是好处是，比如，如果删除不存在的key，先find就不会产生delete，也就不会修改树，commit时就不会有真正的写入发生。insert时也可以通过检查，避免相同值导致的树落盘。

这样一考虑，应该先find。其实多一次的遍历也完全发生在内存中，会比较快，相比IO的消耗(即使顺序写)，这个成本也小一些。