和我一起学习leveldb [3 util]
#[概览]
leveldb源码的util中，实现了许多leveldb需要使用的工具，我们先来看一下代码结构(不包含测试代码)：
util
|
+--- random.h <=== 一个简单的随机数生成器
|
+--- status.cc <=== leveldb读写API的返回状态(头文件: include/leveldb/status.h)
|
+--- crc32c.h <=== crc32 hash算法，本系列文章不予分析
+--- crc32c.cc
|
+--- hash.h <=== hash函数，具体的实现类似murmur hash
+--- hash.cc
|
+--- mutexlock.h <=== 封装Mutex
|
+--- options.cc <=== 数据库的属性选项(头文件: include/leveldb/options.h)
|
+--- histogram.cc <=== 直方图，提供给性能评测工具使用
+--- histogram.h
|
+--- coding.h <=== 数字编码的实现(如变长编码)
+--- coding.cc
|
+--- filter_policy.cc <=== filter, (头文件: include/leveldb/filter_policy.h)
|
+--- bloom.cc <=== bloom filter (布隆过滤器)
|
+--- logging.h <=== 日志中的数据处理(用于commitlog)
+--- logging.cc
|
+--- posix_logger.h <=== 系统写日志的操作(可读日志)
|
+--- comparator.cc <=== 比较器(头文件: include/leveldb/comparator.h)
|
+--- env.cc <=== 抽象的系统运行环境(头文件: include/leveldb/env.h)
+--- env_posix.cc <=== 基于posix实现的具体运行环境
|
+--- arena.h <=== arena是一个用于内存分配的环形缓冲区
+--- arena.cc
|
+--- cache.cc <=== LRUCache实现(头文件: include/leveldb/cache.h)
我们还是先从简单的开始入手分析，大骨头留在后面啃。先看status，status类用于存放数据库操作返回状态，这个类的私有成员变量仅仅是一个const char *_state;，它存储的数据结构如下：
+---------------------+----------------+--------------
_state --> | msg_len 4B uint32_t | 1B status code | message ...
+---------------------+----------------+--------------
其中，状态码的编码是：
1
2
3
4
5
6
7
8
enum Code {
kOk = 0,
kNotFound = 1,
kCorruption = 2,
kNotSupported = 3,
kInvalidArgument = 4,
kIOError = 5
};
这个类简单清晰易懂，不需要花费太多口舌，最后再提一点，这个类的operator=的实现，考虑了自己赋值给自己的问题，细节考虑非常到位！类似自我赋值的问题，往往是我们在工程编码中容易疏忽的。
1
2
3
4
5
6
7
8
inline void Status::operator=(const Status& s) {
// The following condition catches both aliasing (when this == &s),
// and the common case where both s and *this are ok.
if (state_ != s.state_) {
delete[] state_;
state_ = (s.state_ == NULL) ? NULL : CopyState(s.state_);
}
}
接下来我们分析MutexLock(util/mutexlock.h)，前一篇中讨论port中的mutex，权且是这里的一个引子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
Typical usage:
void MyClass::MyMethod() {
// do some thing before lock
// Lock
{
MutexLock l(&mu_); // mu_ is an instance variable
// ... some complex code, possibly with multiple return paths ...
}
// do some thing after lock
}
*/
class MutexLock {
public:
explicit MutexLock(port::Mutex *mu) : mu_(mu) {
this->mu_->Lock();
}
~MutexLock() { this->mu_->Unlock(); }
private:
port::Mutex *const mu_;
// No copying allowed
MutexLock(const MutexLock&);
void operator=(const MutexLock&);
};
代码很简洁，利用C++构造函数和析构函数的特性完成加锁和解锁。注意上面的代码中我在原作的注释中做了一点点小修改，我把MutexLock l变量放在了一个单独的花括号块中，于是l的生命周期就存在于这个花括号块中，当执行到花括号结束，l的析构函数就会被自动调用，即完成解锁。这种利用C++的特性完成的加锁解锁，保证了不会出错。例如这段逻辑中如果会包含很多错误处理分支，有各种return, break, goto等等，那么如果以C的方式去写，就会在很多地方去解锁，分支一多，就有可能忘记解锁出现bug（所以写C代码就很容易在多分支出现的时候忘记解锁、释放内存、关闭文件、释放ipc资源等等问题）。另外值得一提的是，Google近几年刚推出的Go语言，直接从语言级提供了一个关键字defer来解决这个问题，不过defer的作用域是函数而不是代码块，因此在Go中如果要用类似的方式，对函数内部的一小段临界区加锁，需要使用一个闭包（匿名函数）来代替代码块。
另外，util中的hash.h/hash.cc是murmur的类似算法实现，murmur hash用得很广泛，像redis,nginx这些鼎鼎大名的开源软件都用到了它(所以以后你要是需要使用hash函数，不妨选择murmur使用，而不是动不动就去用md5/sha1这些开销比较高的hash函数)，不过我不知道leveldb为什么不直接使用这个算法，而是使用了一个类似的算法，估计是Google大牛多，人才济济，有人专门研究hash算法的效率吧。
crc32.h/crc32.cc是标准的crc32，也没有什么可说的。random.h是leveldb自带的随机数发生器，实现了一些比较有趣的功能，例如Skewed(int max_log)，这个函数随机返回[0, 2^(max_log-1)]区间中的一个2的指数值(Uniform(max_log + 1)返回0到max_log，而1«x的值是[2^0, 2^(x-1)]区间中的一个2的幂).
1
2
3
4
5
6
7
8
9
10
// Returns a uniformly distributed value in the range [0..n-1]
// REQUIRES: n > 0
uint32_t Uniform(int n) { return Next() % n; }
// Skewed: pick "base" uniformly from range [0,max_log] and then
// return "base" random bits. The effect is to pick a number in the
// range [0,2^max_log-1] with exponential bias towards smaller numbers.
uint32_t Skewed(int max_log) {
return Uniform(1 << Uniform(max_log + 1));
}
options.h/options.cc是用来存放数据库打开关闭读写的一些选项，其中各个具体的选项将在以后对数据库的分析中谈及，这里也就一笔带过。Histogram.h/Histogram.cc是用于统计的直方图，里面涉及了一些算标准差、斜率之类的简单数学，这个类是用于给一些benchmark提供一个统计工具，跟leveldb本身是无关的，所以这里也就不作分析了。
本篇对util整体做了个大致的介绍，然后分析了其中的一些比较简单的类。接下来我们将讨论变长整数编码，布隆过滤器，leveldb的内置cache，抽象运行环境以及日志(记录系统状态的日志)。
亲爱的童鞋们，如果你们觉得这个系列写得还不错，一定要记住把本博客的地址加入到你的浏览器收藏夹中，并到这里来帮我加一颗小星星哦~