分析sina微博上的一张图

这是一篇牢骚文.只有清然明白我咋的跟大姨妈来了似的全身不爽.

图片

输入数据:100,000,000条。key是6-10字节的变长字符串,a-zA-Z0-9。value是3字节定长。

那么对于输入数据,最节约的存储方法就是key1,'\0',value1,key2,'\0',value2...

原始数据=((6+10)/2+3+1)*100000000 = 1144M

每个页面能存的key的个数=(pageSize-pageHeaderSize)/(keysize+sizeof(page id))。

pageHeaderSize=12+6+44+4+1+1=68

而keysize=(6+10)/2+2+4=14。加2是因为offset array,加4是因为需要存keysize

所以每页最多可以存储(4096-68)/14=287个key。

在leaf pages上,itemsize=sizeof(u_int32_t) + sizeof(u_int32_t) + sizeof(u_char) +(6+10)/2+3=20。

所以每页最多可以存储(4096-68)/20=201个item。

所以leaf page大约有100000000/201 * 1.5=746268 pages  约等于2915M,假设索引有1%的overhead,那么总计约等于2944M。

库文件占比 2900/1144 约等于 253%

写这么多是为了说明我估算出来的东西和他的实验结果大致吻合。

嗯哼? 下面不说细节只列公式

输入集合的取值的可能性的总数=62^10-62^5=839299364952207392 itemSize=(6+10)/2+1+3-prefixLen
itemPerPage=(pagesize-10-prefixLen-1)/itemSize
totalPages = 100000000/itemPerPage
prefixLen >= ln(totalPages)/ln(62)
total size= total pages * pagesize=100000000*(12-prefixLen)*pagesize/(pagesize-prefixLen-11)
当pagesize=4096 时,假设prefixLen 都等于3(这是最保守的估计),可算出 total size大约等于860M。

啰嗦了一半天,我就是想说,如果想节省硬盘,key prefix压缩是一个很有效的手段。如果还想再省,反正来回都是在leaf page的items如何存储上做点小文章。这和数据库技术压根没啥关系,程序员的小技巧罢了。只要大的结构上是对的,最终在细节上来来回回搞这种小优化就可以了。难道要强迫所有的C程序把x=0改成x^=x吗?(完了,我的牢骚又来了)

换个角度想,一个数据库,它的QPS能达到3800,说明什么?凭什么BDB的QPS只有150呢?你觉得它能用什么魔术超过BDB 20多倍??硬盘的随机访问延迟是多少? THUIRDB的硬盘写入速度为什么只有BDB的1/6(库文件大小除以耗时)?

欢迎拿你的好想法来指正我。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥