软件开发: 10 2007存档
BerkeleyDB的cache可以采用Hash和BTree两种索引方式，今天测试了这两种方式的存取速度，测试方法是：向bdb中写100万条记录，key是1至100万的数字编号，value分别是32、64、128、256字节的字符串，然后再顺序查询这100万条记录，分别统计写和读的时间，其中bdb版本为4.2。
当cache开到1G大小时，数据如下（其中大小单位为字节，时间单位为秒）：
由于cache非常大，几乎所有的数据都可以放在里面，所以两种索引方式的存取效率基本一样。
如果把cache改为32M，测试结果又如下：
其中“缺”字表示测试无法进行，因为当数据太大时，用Hash索引运行bdb几乎把机器搞死，我不得不中断测试。这组测试看得出：如果使用BTree，随着数据的翻倍，写的时间也近乎翻倍，但读的时间非常稳定，对于数据量大、写少读多的应用（比如bbs、图片服务等）应该尽量使用BTree索引。
总的来看，BerkeleyDB的Hash索引表现古怪，只在小cache小数据量的情况下查询速度快于BTree，可现在哪会有这种情况？还是用BTree索引保险一些。
当cache开到1G大小时，数据如下（其中大小单位为字节，时间单位为秒）：
| Cache为1G时 | ||||
| value大小（字节） | Hash写时间 | Hash读时间 | BTree写时间 | BTree读时间 |
| 32 | 12 | 6 | 4 | 3 |
| 64 | 8 | 4 | 4 | 3 |
| 128 | 7 | 4 | 5 | 3 |
| 256 | 7 | 4 | 6 | 3 |
由于cache非常大，几乎所有的数据都可以放在里面，所以两种索引方式的存取效率基本一样。
如果把cache改为32M，测试结果又如下：
| Cache为32M时 | ||||
| value大小（字节） | Hash写时间 | Hash读时间 | BTree写时间 | BTree读时间 |
| 32 | 11 | 6 | 5 | 39 |
| 64 | 205 | 62 | 17 | 50 |
| 128 | 缺 | 缺 | 44 | 42 |
| 256 | 缺 | 缺 | 186 | 51 |
其中“缺”字表示测试无法进行，因为当数据太大时，用Hash索引运行bdb几乎把机器搞死，我不得不中断测试。这组测试看得出：如果使用BTree，随着数据的翻倍，写的时间也近乎翻倍，但读的时间非常稳定，对于数据量大、写少读多的应用（比如bbs、图片服务等）应该尽量使用BTree索引。
总的来看，BerkeleyDB的Hash索引表现古怪，只在小cache小数据量的情况下查询速度快于BTree，可现在哪会有这种情况？还是用BTree索引保险一些。
今天才第一次使用gdbm，发现在往里面放数据时，进程的内存几乎没有变化，而在取数据时，内存才慢慢变大。虽然数据文件有整整180MB，但遍历完数据后内存也才35MB。看来gdbm是直接把数据写往硬盘了，取的时候又用了一个缓存。
虽然gdbm和mdbm用的都是Per-Ake Larson的动态哈希算法，但mdbm是在共享内存里hash，而gdbm直接hash到硬盘上了，且缓存也不是共享的。这造成gdbm比mdbm读写慢很多，而且如果启动多个进程，gdbm会白白浪费内存空间。
在内存充足的情况下，当然选用mdbm，即使内存不足，也可以选用BerkeleyDB，因为bdb的缓存大小可调而且是共享的。那gdbm用在哪里呢？只能用在需要存取少量数据而对存取性能要求又很低的场合了，有这种场合吗？做为老牌存取库dbm的GNU版本，gdbm面对的是过去内存紧缺的老unix系统，而且那时候共享内存机制还不成熟，所以它就用了一个现在看来如此“弱”的存储策略。
如今大内存的机器比比皆是，在服务器领域dbm估计就此退出舞台了。
虽然gdbm和mdbm用的都是Per-Ake Larson的动态哈希算法，但mdbm是在共享内存里hash，而gdbm直接hash到硬盘上了，且缓存也不是共享的。这造成gdbm比mdbm读写慢很多，而且如果启动多个进程，gdbm会白白浪费内存空间。
在内存充足的情况下，当然选用mdbm，即使内存不足，也可以选用BerkeleyDB，因为bdb的缓存大小可调而且是共享的。那gdbm用在哪里呢？只能用在需要存取少量数据而对存取性能要求又很低的场合了，有这种场合吗？做为老牌存取库dbm的GNU版本，gdbm面对的是过去内存紧缺的老unix系统，而且那时候共享内存机制还不成熟，所以它就用了一个现在看来如此“弱”的存储策略。
如今大内存的机器比比皆是，在服务器领域dbm估计就此退出舞台了。
江湖传说FreeBSD从6.0开始对多线程的支持就比较充分了。我只知道FreeBSD的4.11版对线程的支持非常差，心想都到了6.0了，应该能稳定支持了，但使用结果却不是太圆满：
1.进程启动后用pthread_create创建一个线程，再"ps auxH"一看，居然有6个线程在跑，除去主线程和创建的一个线程，另外4个哪里来的？虽然不影响运行，但是比较疑惑。
2.运行中间程序coredump了，用gdb一调，出来的大多是问号，我是用了g参数编译的，为什么跟踪不到可读的信息？这个对于调试太致命了。
这次另外还发现BerkeleyDB的DB->get函数居然不是线程安全的，必须自己在外部加锁，立中同志怀疑BerkeleyDB是线程安全的，是FreeBSD的pthread库自己有问题，搞死了bdb。这也有可能，但没时间在linux上完整测试了。
log4cpp号称支持多线程，只需在configure的时候加一个 --with-pthreads 参数，结果做压力测试的时候还是coredump了，还是gdb调试一堆问号....
总而言之，FreeBSD 6.0对多线程的支持值得怀疑，大概是开发FreeBSD的都是老unix程序员，天生喜欢多进程而不看重多线程。所以如果没有特殊的需要，还是用linux吧。
1.进程启动后用pthread_create创建一个线程，再"ps auxH"一看，居然有6个线程在跑，除去主线程和创建的一个线程，另外4个哪里来的？虽然不影响运行，但是比较疑惑。
2.运行中间程序coredump了，用gdb一调，出来的大多是问号，我是用了g参数编译的，为什么跟踪不到可读的信息？这个对于调试太致命了。
这次另外还发现BerkeleyDB的DB->get函数居然不是线程安全的，必须自己在外部加锁，立中同志怀疑BerkeleyDB是线程安全的，是FreeBSD的pthread库自己有问题，搞死了bdb。这也有可能，但没时间在linux上完整测试了。
log4cpp号称支持多线程，只需在configure的时候加一个 --with-pthreads 参数，结果做压力测试的时候还是coredump了，还是gdb调试一堆问号....
总而言之，FreeBSD 6.0对多线程的支持值得怀疑，大概是开发FreeBSD的都是老unix程序员，天生喜欢多进程而不看重多线程。所以如果没有特殊的需要，还是用linux吧。
随着存储设备越来越便宜，哈希表以空间换时间的策略也越来越吃香，而其它如二叉树、红黑树、B树，都因为查询速度不够或实现太复杂而在实战中渐渐不被使用。在日益增大的存储需求下，拥有固定slot（桶）数的静态哈希表已经无法适应需要，动态哈希表便应运而生了。
动态哈希表通常是在发生冲突后slot数量翻倍增长，而增长后毕竟哈希函数也变了，所以还要把旧slot里的元素重新放置。这种简单的动态哈希(dynamic hash)算法便是SGI版的STL中hash_map的实现。但如果每次调整slot都要全部重放元素，效率太低，且数据插入的时间也太不均匀：某次插入元素，发生了冲突，于是所有元素重新放置，老半天后这个元素才能插入完毕。作为实时系统，这一突如其来的延时当然是不可忍受的。
为了让数据更新的时间更为均匀，数据库大师Per-Ake Larson便提出了一种新的动态哈希算法，其实中心思想也很简单（“简单是可靠的前提”——Dijkstra）：每次slot数量增长一倍，不是重新放置所有slot中的元素，而只移动一个slot内的元素——就是新增slot的那个兄弟slot（Buddy Slot）。如下：
slot增长前如图a，key为0、6的元素都可以放得下，但当key为12的元素到来时，编号为1的slot里有冲突了，这时需要将slot数翻一倍了，于是变成了图b。此时slot数由原来的4变为了现在的8，但“有效的”slot只有5个：编号分别为0到4。key为12的元素放入4号slot，因为12除8余4。按照一般的Larson策略来讲，4号slot的“兄弟slot”是0号slot，所以在增长完成后0号slot里所有除8余4的元素都要移到“新slot”即4号slot里，举个例子：如果0号slot里有key为16、20、24、28的元素，那key为20、28的元素必须移到4号slot，其它的（16和24）留在0号slot。
只更新一个slot的代价是——查询要稍微复杂些：先用8去除key，如果余数对应的slot“不存在”，则再用4去除，得到正确的slot编号。例如查询6，先 6 mod 8 得6，6号slot还不存在（只是分配了内存，数据结构上还不存在），所以只能再除4，得2，到2号slot去找，找到。图b右下方的公式可能有一些误导：它通过看s(k)是否小于n(<=5)来判断对应的slot是否存在，而在通常的情况下，增长的slot可能不是4号。假如增长的是6号，这时4、5、7号slot是“不存在”的，再用这个公式硬套就不行了。所以关键的判断标准是slot“是否存在”，而不是编号本身是大是小。
Per-Ake Larson的这一经典动态哈希算法以一小点查询时间的损失换来了数据更新的高效和平滑，因此得到了广泛的使用：GNU的gdbm、Berkeley的ndbm、雅虎的mdbm，都是使用这个算法。
动态哈希表通常是在发生冲突后slot数量翻倍增长，而增长后毕竟哈希函数也变了，所以还要把旧slot里的元素重新放置。这种简单的动态哈希(dynamic hash)算法便是SGI版的STL中hash_map的实现。但如果每次调整slot都要全部重放元素，效率太低，且数据插入的时间也太不均匀：某次插入元素，发生了冲突，于是所有元素重新放置，老半天后这个元素才能插入完毕。作为实时系统，这一突如其来的延时当然是不可忍受的。
为了让数据更新的时间更为均匀，数据库大师Per-Ake Larson便提出了一种新的动态哈希算法，其实中心思想也很简单（“简单是可靠的前提”——Dijkstra）：每次slot数量增长一倍，不是重新放置所有slot中的元素，而只移动一个slot内的元素——就是新增slot的那个兄弟slot（Buddy Slot）。如下：
slot增长前如图a，key为0、6的元素都可以放得下，但当key为12的元素到来时，编号为1的slot里有冲突了，这时需要将slot数翻一倍了，于是变成了图b。此时slot数由原来的4变为了现在的8，但“有效的”slot只有5个：编号分别为0到4。key为12的元素放入4号slot，因为12除8余4。按照一般的Larson策略来讲，4号slot的“兄弟slot”是0号slot，所以在增长完成后0号slot里所有除8余4的元素都要移到“新slot”即4号slot里，举个例子：如果0号slot里有key为16、20、24、28的元素，那key为20、28的元素必须移到4号slot，其它的（16和24）留在0号slot。
只更新一个slot的代价是——查询要稍微复杂些：先用8去除key，如果余数对应的slot“不存在”，则再用4去除，得到正确的slot编号。例如查询6，先 6 mod 8 得6，6号slot还不存在（只是分配了内存，数据结构上还不存在），所以只能再除4，得2，到2号slot去找，找到。图b右下方的公式可能有一些误导：它通过看s(k)是否小于n(<=5)来判断对应的slot是否存在，而在通常的情况下，增长的slot可能不是4号。假如增长的是6号，这时4、5、7号slot是“不存在”的，再用这个公式硬套就不行了。所以关键的判断标准是slot“是否存在”，而不是编号本身是大是小。
Per-Ake Larson的这一经典动态哈希算法以一小点查询时间的损失换来了数据更新的高效和平滑，因此得到了广泛的使用：GNU的gdbm、Berkeley的ndbm、雅虎的mdbm，都是使用这个算法。
