7月中旬的时候看到了一篇知乎上的关于搭建 pastebin
服务的文章 https://zhuanlan.zhihu.com/p/73961522
作者没有利用redis,而是用rust手撕了一个简易的内存存储,遂引起了我的兴趣,在核心数据结构照着该作者来之外,加入了其他的feature。当然也被 rust
编译器按在地上摩擦了很久。
首选先明确我们的数据库需要实现哪些功能。
- 保存数据
- 根据key读取数据
- 淘汰不常使用的数据
- 过期删除
- 硬盘二级存储
摆上我的项目 repo: https://github.com/fun4wut/naive-pastebin
数据存储
为了同时实现数据保存+淘汰数据,LRU是一个非常好的选择。
故主存储数据结构选用 linked-hashmap
。提供 O(1)
的访问、插入和删除。
过期清除
最简单的过期检测就是定时遍历 LinkedHashMap
,检查数据是否过期,删除所有过期的数据。
这种方法的时间复杂度是 O(n),每个单位操作是访问、判断、删除,有两次哈希表操作。
过期检测的要求是有序遍历过期时间,删除对应的键,插入和删除时不能有大量的移动。因此,答案是平衡树,寻找最小键、插入、删除都是 O(logn)。具体是 BTreeMap
,B 树是多叉平衡树,时间复杂度是 O(Blog(B,n)),少量的堆分配和 CPU 缓存友好性使它实际上比二叉平衡树快很多。
使用 B 树做过期索引会使保存的时间复杂度变为 O(Blog(B,n)),批量淘汰变为 O(nBlog(B,n)),过期删除变为 O(nBlog(B,n)),而查找仍是 O(1).
另起一个线程定时运行过期检测删除机制,为存储加个锁即可。
该部分摘自https://zhuanlan.zhihu.com/p/73961522/#%E6%95%B0%E6%8D%AE%E5%AD%98%E5%82%A8
Key的选择
纳秒时间戳具有自增、不重复的特性,对于一个单机服务来说,它就是完美的发号器。
但是在Web服务的时候,用一串时间戳,未免太丑,我们还需要一个短网址加密。
幸运的是,Rust
已经有了这样的短网址库,没必要自己写了。
https://crates.io/crates/short-crypt
碰撞问题
并发量一高,Key依然会发生碰撞,这里原作者采用的方法是将时间 +1s
,但其实这十分 naive。
采用随机加上0-256个(u8) 个纳秒,即可完美解决问题。
二级存储
被LRU淘汰掉的数据需要有个去处,硬盘无疑是个非常好的选择。
这里参照 redis
的解决方式,首先通过SHA1算法把Key转化成一个40个字符的Hash值,然后把Hash值的前两位作为一级目录,然后把Hash值的三四位作 为二级目录,最后把Hash值作为文件名,类似于“/0b/ee/0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33” 形式。
二级存储采用 懒删除 机制。意思是当用户请求的数据在硬盘时,先查看记录在硬盘里的过期时间,若已过期,将其删除,并返回未找到。
数据备份
内存数据库,数据没有丝毫保障,需要一个备份措施来进行容灾。
主要有两种选择:snapshot
和 log
。
但是由于摸了,这里没做,想了解更多可以自行搜索【逃
Rust踩坑
在使用rust的时候踩了无数的坑,并最终放弃治疗。把遇到的问题和解决问题记录于此。
无法返回局部变量的引用
原因很简单:局部变量在作用域结束之后就会销毁,所以这个引用会成为 野指针。
解决办法:
- 直接返回资源本身(最直接的办法)
- 使用
Box
包装资源,同时返回该Box
- 使用智能指针包装,如
Arc
/Rc
详情参见 http://bryce.fisher-fleig.org/blog/strategies-for-returning-references-in-rust/index.html
泛型trait Deserialize需要生命周期标识
举个例子
pub struct DiskStore<K, V>
where
K: ToArray,
V: Serialize + Deserialize
{
//....
}
这里就会报错。
解决办法:使用 DeserializeOwned
来获得所有权版本的 trait
使用 ? 运算符返回自定义错误
在 rust
中,?
的作用是 unwrap
+ 错误向上传递。
在很多时候,我们的 Error
是自定义的,但是 ?
传递的 Error 并没法转成自定义的 Error。
为此,我们需要实现它们的 From
trait。
impl From<std::io::Error> for StoreError {
fn from(e: std::io::Error) -> Self {
IOErr(e)
}
}
impl From<Box<ErrorKind>> for StoreError {
fn from(e: Box<ErrorKind>) -> Self {
BinCodeErr(e)
}
}
impl From<NoneError> for StoreError {
fn from(_: NoneError) -> Self {
NoneErr
}
}
详情参见 https://lotabout.me/2017/rust-error-handling/
将 可变引用 转化为 非可变引用
let mut tmp = String::from("2333"); // mutable reference
&*tmp // now it's immutable
对两个条件分支下,分别使用不可变应用和可变引用,borrow checker的报错
感觉是生命周期的问题
fn foo(x: &mut u8) -> Option<&u8> {
if let Some(y) = bar(x) {
return Some(y) // comment this out to calm compiler
}
bar(x)
}
fn bar(x: &mut u8) -> Option<&u8> { Some(x) }
报错:
error[E0499]: cannot borrow `*x` as mutable more than once at a time
--> src/main.rs:7:9
|
4 | if let Some(y) = bar(x) {
| - first mutable borrow occurs here
...
7 | bar(x)
| ^ second mutable borrow occurs here
8 | }
| - first borrow ends here
理论上 bar(x)
的生命周期应该在这个分支末尾就已经结束了,但是编译器还是认为 它在函数最后才会被销毁。
解决办法:使用 polonius
编译参数
cargo rustc -- -Z polonius
异步文件IO问题【未解决】
在这个问题上,Windows和Linux给出的性能完全不一样【不清楚原因】
Windows下写操作【并发量为50】:
Linux下写操作【并发量为50】
且先不论Win和Linux的整体性能差距。单看各方式的性能比较,windows下异步是最快的,而linux下异步确实最慢的,阻塞调用竟然最快【???】
总结
这里我想多吐槽一下Rust语言,其实我对Rust的类型系统很有好感, Option/Result
、trait
、 pattern match
、 algebra data type
等等的设计都非常对我口味。
遗憾的是它的所有权机制太硬核了,不碰生命周期还好,一旦涉及到,报错就是十几个一报的。
要求程序员进行内存管理真的太难了,未来一定是属于 GC 的!
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!