猜解leveldb写性能

四月 17, 2012
storage

如题,猜测。

我们知道leveldb的很出色,随机读写的性能可以分别达到 164,000 ops/sec 和 129,000 ops/sec,这是官方的Benchmarks数据。

leveldb最关键的核心技术在于基于level思想的sstable文件compact策略,因为这种设计,大大的改善了Random Writes的性能。levledb的memtable/immutable是一个skiplist链表,而skiplist insert的时间复杂度是O(logn),也就是说,insert的时间复杂度是随着问题规模的增长而线性上升的,呵呵,不知到大家注意到没。

高性能kv的实现现在跑的比较火的就数lsm-tree,主要的思路就是先在内存里cache到某个阀值然后dump到磁盘,再由其他线程或者进程来进行compact操作,于是首先会引出的第一个问题是:

1、sstable文件的管理以及如何执行compact的操作,这个地方直接影响到读性能,这也是为什么采用lsm-tree的key-value存储引擎读性能一直提升不上去的原因,尤其是一些老旧数据的检索。

我当初也主要没考虑过在skiplist这一部分做过优化,毕竟skiplist主要还是内存操作。

但是leveldb的作者可不是这么想的,这种想法可真是so easy但是又很难引起大家的注意:就是靠缩小问题的规模来达到提升insert性能的目的。我今晚在食堂吃饭,想到这点的时候就没差点笑喷了,有意思,哈哈 ^_^

但是如果这样做的话会导致sstable文件会非常的多,而且会产生大量的小文件,所以如果没有一套非常优秀的compact策略的话只有傻子才会这样做,我当初在研究lsm论文后,采用的思想是直接dump大sstable文件,sstable文件量小,容易管理,查询性能也比较好,当然后来也意识到很多问题,这是后话了。

所以Jeff Dean和Sanjay Ghemawat设计了一种基于level的compact策略,然后让memtable达到一个非常小的阀值后直接dump成小文件,由后台进程来进行compact管理。memtable的阀值由 write_buffer_size(include/leveldb/options.h)控制,默认是4mb左右,假设key是20bytes,value是80bytes,这个阀值可以容纳4w个entries左右。

根据skiplist的查找时间复杂度O(logn),我在本机上做了一个简单的测试,主要计算随着规模的增长每随机插入一条数据的开销。

测试环境:

Date: Tue Apr 17 23:45:07 2012
CPU: 2 * Pentium(R) Dual-Core CPU T4400 @ 2.20GHz
CPUCache: 1024 KB
System: Centos Linux 2.6.32-220.el6.i686 #1 SMP Tue Dec 6 16:15:40 GMT 2011 i686 i686 i386 GNU/Linux

实际上只使用了一个CPU,测试结果

测试代码:https://github.com/pipul/coutune/tree/master/skiplist

很明显,随着skiplist的cardinality不断变大,插入每条数据的开销越来越多,不过当n趋向无穷大的时候,这种变化会渐趋不明显。而在刚开始的时候,insert开销抖增。所以,想要获得最好的random writes性能,skiplist的cardinality尽量控制到百万级别以下

2012数据库技术交流会

四月 15, 2012
Programming practices

分享几个大会的PPT,一时拿不全,后续慢慢补上。

内容很精彩,这几天实在太累了,因为住的地方,还有中午吃饭很成问题,干脆中午不吃饭,挨到晚上再吃点,哈哈。因为有时吃饭回来连门口都挤不进去了,酱油实在太多了。不过很好,可以结识更多的朋友。

再分享一张会场的图片,哈哈,前面最左边穿白色短袖T恤的是我

wordpress latex的bug

四月 2, 2012
Programming practices

latex for wordpress 插件的这个bug,因为目录不可写的情况下仍然尝试从LaTex Image server获取formula image,过多的进程以及处于等待数据状态的socket,可能导致httpd进程崩溃。

昨晚休息之前手机就收到linode的警告,说DISK io rate已经超过阈值,可惜实在太累,只好倒头就睡,顾不上这么多了。早上7点多陈老师消息过来,说web服务器无法访问,而这时linode的警告又来了,这次不但说DISK,连CPU都出问题了。然后我意识到,服务器可能被攻击了。
勉强通过ssh登录vps服务器,发现一堆httpd进程,这倒没什么,top一下cpu进程持续100%,查了apache的日志,很奇怪 access_log/error_log 的内容关于 May 2这天的日志都是空的,也就是从早上凌晨开始到现在,没有一个人访问过我们的服务器,我们的RP再低,也不至于这种情况吧。。。

再看了看linode后台的监控信息:

也就是说从昨晚6点到现在,CPU一直都是满负荷的而网站几乎没什么流量。但是昨晚这个时候我恰好在撰写blog,说明server应该没啥问题的。我重启了httpd服务,再刷新一下blog,可以正常访问,但是速度很慢,这个昨晚我也明显感觉到了。

我喜欢用latex写数学公式,有时为了查错经常需要刷新页面,所以我猜测会不会是latex的js引擎渲染的问题呢,然后对比测试了一下单独开启js渲染和cache image,结果发现js渲染居然比cache image要快很多很多,但是cache image的时候并没有显示image,可能是cache目录没有写权限。
按常理来说没法理解啊呵呵,没显示我的image又耗掉我那么多性能,联系到今天server的状况,大概是latex for wordpress有问题了。这个插件做了什么事情让server变得那么慢呢?然后看了看它代码。

if (!is_file($cache_formula_path) || filesize($cache_formula_path) < 10) {
  if (!class_exists('Snoopy'))
    require_once (ABSPATH.'/wp-includes/class-snoopy.php');
  $snoopy = new Snoopy;
  $formula_text_html = str_replace('%C2%A0', '%20', 
    rawurlencode(html_entity_decode(preg_replace('/\\label{.*?}/', '', 
    $formula_text))));
  $snoopy->fetch(get_option('latex_img_server').$formula_text_html);
  if (strlen($snoopy->results) < 10)
    $snoopy->fetch('http://www.quantnet.com/cgi-bin/mathtex.cgi?'.rawurlencode(($formula_text)));
  $cache_file = fopen($cache_formula_path, 'w');
  fputs($cache_file, $snoopy->results);
  fclose($cache_file);
}

之所以会导致这个问题,是因为latex for wordpress在做缓存的时候,是不检查目录是否可写的,它只检查文件是否存在或者文件大小小于10bytes,它在目录不可写的时候仍然尝试去下载formula image。如果你的page里有很多20条latex formula的话,httpd就不得不为每个连接创建20个子进程来接收这些数据,并发的情况下可能来不及接收完毕httpd就已经僵死在那里了。
解决的办法也简单,在做缓存的时候,优先检查目录是否具有写权限,如果目录不可写,就不去获取formula image如下:

$fileRWX = fileperms($cache_path);
if (($fileRWX & 0x01B6) == 0x01B6) {
  if (!is_file($cache_formula_path) || filesize($cache_formula_path) < 10) {
    ...
  }
}

更多 fileperms 的用法,请看:http://www.php.net/fileperms

ae的“陷阱”?

四月 1, 2012
Programming practices

ae (redis:ae.h ae.c)  ->  Asynchronous Event (libevent)

redis之后,ae这东西都快要酱成糊了。似乎很多人都在用,antirez 当初没有直接引入libev或者libevent这样的外部库,而是从中抽取了两个文件(就是redis src目录下的 ae.h ae.c 文件)改成适合自己的东西。其实ae不复杂,就是对epoll的API进行了一层简单的封装。

今天在写一个server的时候忽然想到了这个问题,遗留下来的,可惜一直没怎么注意过去看ae的实现而且一直纠结的认为是epoll工作原理的问题以致在理解方面走了很多弯路,很长的一段时间里我一度视ae为epoll的代名词,实际上不是那么一回事。

因为ae(或者说epoll)并发处理的性能实在太好了,好到每当我使用ae的时候都在犹豫要不要在回调函数里给全局变量加锁的笑剧,ae并发处理得那么快,我担心会不同步。举个例子,我用ae监听listenfd描述符,如果有连接来,执行一个回调函数,如 cbfunc(),cbfunc 会accept()返回一个client的sockfd,然后进行某些数据处理,期间会占用到我上面提到的某个全局变量一段时间。但是如果cbfunc()在执行期间,listenfd有有了一个新事件,有新的客户端连接进来了,然后继续执行回调函数cbfunc(),这里注意,是两个cbfunc()在同时执行吗?还是第二个cbfunc()的执行会等待第一个执行完成?如果不是,需要锁吗?

为了形象一下这个过程,我使用了nessDB和redis-cli两个程序来做模拟,因为nessDB就是使用了这个ae,而且nessDB兼容部分redis协议。

我修改了nessDB的db-server.c代码,阻塞第一个client连接10s,看看第二个client是否会先执行还是一直等待第一个client完成任务。

  1. ......
  2. static int cli_tok = 0;
  3. ......
  4. if (cli_tok == 0) {
  5.         cli_tok = fd;
  6.         sleep(10);
  7. }
  8. ......

cli_tok是全局变量,默认初始化为0,cli_tok的作用是标志当前链接是否为第一个连接,因为第一个连上server的client会对cli_tok修改,而修改之后cli_tok的值非0,其他的连接就会跳过sleep(10)的过程。然后启动db-server进程,启动两个redis-cli实例A和B。A先连接上db-server,然后执行一条get命令,然后B再连接上db-server,同样执行一条get命令,结果:

  1. $ ./redis-cli    (A)
  2. redis 127.0.0.1:6379> get fangdong
  3. "fangdong_ok"
  4. (10.00s)
  5. redis 127.0.0.1:6379>
  1. $ ./redis-cli    (B)
  2. redis 127.0.0.1:6379> get fangdong
  3. "fangdong_ok"
  4. (7.17s)
  5. redis 127.0.0.1:6379>

显然,B任务赤裸裸的被A阻塞了。

再看看ae中主要的实现代码

  1. #include "ae.h"
  2. ......
  3. n = epoll_wait(el->efd, el->ready, AE_SETSIZE, tvp ? (tvp->tv_sec*1000 + tvp->tv_usec/1000) : -1);
  4. n = n > 0 ? n : 0;
  5. for (i = 0; i < n; i++) {
  6.         ee = el->ready + i;
  7.         e = &el->events[ee->data.fd];
  8.         if (ee->events & EPOLLIN)
  9.                 mask = mask | AE_READABLE;
  10.         if (ee->events & EPOLLOUT)
  11.                 mask = mask | AE_WRITABLE;
  12.         if (e->mask & mask & AE_READABLE) {
  13.                 rf = 1;
  14.                 e->rcb(el,ee->data.fd,e->data,mask);
  15.         }
  16.         if (e->mask & mask & AE_WRITABLE)
  17.                 if (rf != 1 || e->rcb != e->wcb)
  18.                         e->wcb(el,ee->data.fd,e->data,mask);
  19. }
  20. ......

line:3和line:5的for循环,ae通过调用epoll_wait获得已经准备好了文件描述符表,然后轮询执行该事件注册了的回调函数e->wcb或者e->rcb。很好,问题就出现在这里了,通常在实现server的时候,我们会习惯将数据处理过程放在回调函数里,比如cbfunc(),如果cbfunc()执行比较耗时,那么期间整个进程就阻塞在这里,得不到好的并发性能。

如果要处理长连接的问题,就需要引入业务线程(池),在执行回调函数的时候,将任务打包挂载到业务线程上去处理从而让回调函数尽可能快的瞬间返回。

The Log-Structured Merge-Tree

三月 23, 2012
storage

LSM-tree 是一种相当优秀的思想。它本身是为了优化B树在更新插入时的性能而被提出来的,所以要彻底理解LSM-tree,就要清楚B树的难处。

B树中的update性能

完全不考虑缓冲的情况下,举例一个可以存储10亿关键字的B树,深度为2,那么每次update事务,至少需要四次IO操作才能完成,三次读,一次写。如果根结点常驻内存的话,最少也需要三次IO。如果是插入(插入也算是update的一种)操作,遇到结点满状态,需要对结点分裂,还需要更多的IO才能完成。

即便是到了今天普通PC的磁盘IOPS也就150左右,可以想象,根本无法处理得了大量的并发操作,尤其在海量存储难题面前

LSM-tree 的核心思想

LSM-tree 最原始和质朴的思想,就是在内存里对B树的update操作进行缓存。使用cache的做法似乎不值一提,但在当时来说哪怕1MB的闪存价格都非常昂贵,大部分的数据还是通过磁盘来处理,如果你有这方面的经验,就能理解B树这种传统的数据结构实践起来是多么的困难。而且,The Log-Structured Merge-Tree 这篇论文在提出的时候是1996年,当时的内存容量我猜在5MB左右。

五分钟法则的由来

五分钟法则是从经济学的角度为降低IT企业运营成本而被提出来的,用术语的话来说,就是 COSTp/COSTm,在今天的说法就是,当页面达到每超过300秒就被访问一次的频率后,就应该将这块页面加载到内存以提升性能。而过去的说法,是指页面没有被频繁使用的话,就不应该将其加载到内存中来,87年的今天是5分钟,96年是1分钟,到了今天可能是十几秒。

COSTm = cost of 1 MByte of memory storage
COSTp = disk arm cost to provide 1 page/second I/O rate, for random pages

COSTm和COSTp非物理设备的价值那么简单,涉及很多因素,尤其是COSTp,比如Google说,每0.5秒的延迟就会有20%的流量损失,你可以想象一下COSTp值多大。

所以,Patrick O'Neil (LSM论文的作者)们要解决的问题,就是怎么有效利用缓存的策略,Patrick O'Neil 的做法是,在内存里维护一个相同的B树,当内存中的B树达到阀值时,然后批量进行 rolling merge

NoSQL运动里的LSM实践

NoSQL运动里谈到的LSM相当于复杂的 Multi-Component LSM-trees,只是存储组件不再使用B树,而是习惯了另一种更加漂亮的数据结构 Skiplist,Google的Bigtable理论模型里用到的就是这个东西,可以看看levelDB的实现,而且mencached,redis,nessDB等也不乏使用。相比传统的B树,Skiplist 最大的特色就是完全平坦化的存储模型,O(logn)的时间复杂度

LSM与skiplist的结合,带来了一种新的存储架构策略,我自个的话说就是:swap和merge-split

以levelDB为例,C0是memtable,是内存中的LSM组件,C2 ~ Ck就是sstable,是常驻磁盘的LSM组件,关于存储的设计可以看看这篇文章 >> KeyValue存储层文件结构的设计  或者 HFile。而C1实质上是sstable在内存中的cache,通常是一个LRU链表。

所谓swap,就是将memtable中的数据直接dump到磁盘形成新的sstable,而meger-split则是删除sstable中过期的数据。这种设计的好处是,无论是插入,更新,还是删除,都可以很轻松的抽象成一个put操作,大大简化了DB的实现逻辑。

但是,这种实现的策略有两个地方限制了其自身可应用的场景,就是update的频率要远大于读取,才能体现出顺序写的性能优势,因为

  • sstable间是无法保证严格有序的,因此查询一个key就不得不在所有的sstable中进行,然后返回最新的数据。用迂回折中的办法,可以对sstable按照timestamp排序,查到最近的一个key并返回。所以bigtable这种模型很可能无法满足精确,实时的海量查询需求
  • 此外,merge-split 还隐藏了另外一个很重要的因素,就是数据文件要达到GB甚至TB级才会有显著的merge-split效果。

要解决这个问题,可以适当改变swap和merge-split的策略。nessDB是个很好的例子。nessDB同样采取LSM的思想,但是不同与上述模型,nessDB确保sstable之间是有序的,对查询操作比较友好。

nessDB是通过牺牲部分写性能来提升查询的效率。memtable在swap的时候并不直接dump成sstable文件,而是合并到现有的sstable文件中去。

LSM的持久化

如果要确保数据不能丢失,为了应对服务器遇不可抗拒外力因素造成的宕机的情况,通常LSM有两次持久化过程,一次是log,,以append形式对所有的update操作先进行日志记录,一旦出现意外情况,即可以恢复log中的内容到memtable,这里实际上相当于重新redo了一系列的事务,除了增加少量的disk存储开销不会带来其他任何影响。第二次是swap,在memtable达到阀值的时候直接dump到磁盘上形成新的sstable,这个过程叫做最终持久化。

 

LSM的论文洋洋洒洒30多页,也算是我看过的最长的一篇论文了,前前后后花了不少时间才算弄明白。其实LSM并不复杂,反而可以说是出奇的简单,Patrick O'Neil在文中列举了很多例子来计算LSM所带来的性能的提升,也许在今天这种情况下是不足论道的,但是Patrick O'Neil迈出了一小步,却是存储难题的一个重大突破。

KeyValue存储层文件结构的设计

三月 10, 2012
storage

主要参考了一下HFile存储格式的设计,也可以说完全是HFile的一个简约版。我去除了一些目前暂时可能用不上的结构,毕竟HFile作为HBase数据库底层存储的文件结构,融合了过多的通用特性,比如Meta,另外我还做了一下稍微的修改,比如trailer块中的某些字段。

数据文件主要由四部分组成,连续的Data Block,一块File Info,一块的Index Block,最后是 Trailer 块

 

Data Block 数据块

DATA_BLOCK_MAGIC 主要的作用是数据校验,避免数据损坏带来的意外情况。Block中所有的数据其实整个数据文件的keyvalue都是有序的。Block的大小可以自定义,主要是针对IO性能和解析的粒度。

File Info 数据块

File Info Block 主要记录了整个数据文件的一些基本信息。ItemsNum表示File Info Block里记录的数量,AVG_KEY_LEN 表示平均的 key 长度,其他同理,LASTKET保存了整个数据文件的最后一个Key,方便进行key的检索。

Index Block 索引数据

Index Block 主要是连续的entries组成,每个entry对应一个Data Block,包含了各自所对应的Data Block的偏移量 Offset,Data Block的大小 DataSize,KeyLen和KeyData为每块Data Block的第一个Key。

Trailer 块

数据文件被打开时,首先应该被读取的是Trailer块,Trailer块的长度是固定的,当然这个可以自己修改,理所当然的做法就是给Trailer增加一个Version,解决各版本之间数据格式不兼容的问题。Trailer 结构里主要保存了 File Info 和Index Block等其他结构在文件中的偏移量和数据大小,如下

我写了一个c版本的上述设计的实现,仅关注存储形式而不涉及上层DB的实现逻辑。代码未经测试,谨慎使用

https://github.com/pipul/Hfile

透过BIOS获取Linux/Unix的设备信息

三月 8, 2012
Programming practices

c 的标准里并没有提供读取硬件基本信息方面的API,但是有时候我们需要知道一些系统方面的信息,比如内存的规格,缓存,CPU以及磁盘等等。目前比较常见的方法就是通过读取BIOS信息。下文所述的方法理论上在各种Linux/Unix发行版里是适用的,但是没有仔细代码测试过,而且BIOS信息因各厂商不同而异,难有统一的标准,另一方面,BIOS信息量巨大,我仅作简单的描述

  1. Linux i386, x86-64, ia64
  2. FreeBSD i386, amd64
  3. NetBSD i386, amd64
  4. OpenBSD i386, amd64
  5. BeOS i386
  6. Cygwin i386
  7. Solaris x86
  8. Haiku i586

BIOS表

BIOS信息会在系统刚刚启动的时候加载到内存的0xF0000地址处,以表的形式组成,长度不会超过65536个字节。将那块内存区域的数据拷贝出来就可以看到,首先最前面的是_SM_和_DMI_两个信息头,如下,所有数据都是ASCII码

0x80613f8: "_SM_30370205d"
0x8061402: ""
0x8061403: ""
0x8061404: ""
0x8061405: ""
0x8061406: ""
0x8061407: ""
0x8061408: "_DMI_&3630520"
0x8061412: "16"
0x8061414: ","

还有别忘了上面每个字符串后面其实有一个'',编译器给省略了显示。首先分析_SM_头,挑重要的说。0205 表示SMBIOS信息的版本是2.5,37是_SM_头的长度,单位为字节。还有一个很重要的特性,是为了防止BIOS数据块损坏而起校验作用的,就是_SM_头内所有字节值的和是256的倍数,下面_DMI_的校验和这个也是一样的。_SM_头后紧接着就是_DMI_头,长度固定,15字节,_DMI_头里记录着后面记录的起始地址和长度,36305 两个字节表示长度,20001600 四个字节表示内存中的地址,而 ',' 表示记录的数量,这里 ',' 的值是44

BIOS记录

BIOS记录数据的首地址长度等信息在前面已经提到,这块区域储存了各种计算机设备的基本信息,包括CPU,缓存,内存,磁盘,鼠标,等等。

每条记录主要有两部分内容,一个是记录头,一个是记录备注,记录头里记录了记录头信息的长度,而记录备注则是连串的字符串,但是没有长度。那么如何确定下一条记录的位置呢,也不难,除了第一条记录之外,此后的每条记录前面必有两个连续的 00 字节。如下

0x806a04c: "013301"
0x806a050: "0102030420345y01J~21˥O355 370-21531206"
0x806a066: "03LENOVO"
0x806a06e: "28747GC"
0x806a076: "ThinkPad SL410"
0x806a085: "LRHVT48"
0x806a08d: ""
0x806a08e: "021702"    /* 0x806a08e - 0x806a04c == 33 */
0x806a092: "01020304"
0x806a097: ""

第一个01是Handle标志,33表示记录头的长度,后面的 01是DMI标志。如果DMI的值是127,表示记录到此结束。Handle标志表示该设备属于哪类设备,有43个值,参考如下:

"BIOS", /* 0 */
"System",
"Base Board",
"Chassis",
"Processor",
"Memory Controller",
"Memory Module",
"Cache",
"Port Connector",
"System Slots",
"On Board Devices",
"OEM Strings",
"System Configuration Options",
"BIOS Language",
"Group Associations",
"System Event Log",
"Physical Memory Array",
"Memory Device",
"32-bit Memory Error",
"Memory Array Mapped Address",
"Memory Device Mapped Address",
"Built-in Pointing Device",
"Portable Battery",
"System Reset",
"Hardware Security",
"System Power Controls",
"Voltage Probe",
"Cooling Device",
"Temperature Probe",
"Electrical Current Probe",
"Out-of-band Remote Access",
"Boot Integrity Services",
"System Boot",
"64-bit Memory Error",
"Management Device",
"Management Device Component",
"Management Device Threshold Data",
"Memory Channel",
"IPMI Device",
"Power Supply",
"Additional Information",
"Onboard Device",
"Management Controller Host Interface", /* 42 */

上面所说的3个字位是记录头里最重要的信息,然后接着是一个00位,00之后的数据,记录了该设备的详细参数,比如缓存的大小,设备厂商,序列号,等等。而且每个设备的记录头组织完全不一样,但是都是固定的,大多类似

0x806a050: "0102030420345y01J~21˥O355 370-21531206"
0x806a066: "03LENOVO"
0x806a06e: "28747GC"
0x806a076: "ThinkPad SL410"
0x806a085: "LRHVT48"

01说明它的值是记录备注的第一条字符串,02表示第二条,03表示第三条,04表示第四条,但是注意:

  1. 并不是每条记录的头部都是这么组织的,有可能01并不表示第一条字段,而是说明其他信息
  2. 每两条字段之间都有一个 00 隔开
  3. 重要的是,记录头里每个固定的位,都是有意义的,可能表示第几条记录,也有可能表示某种其他的意义。

如果想了解得透彻,可以读读dmidecode的代码。

浅谈DB的分层索引

二月 29, 2012
storage

HFile是Hbase的底层存储文件结构,目前有两个版本v1和v2,要理解HFile的设计,这里 http://www.slideshare.net/schubertzhang/hfile-a-blockindexed-file-format-to-store-sorted-keyvalue-pairs,这里 https://issues.apache.org/jira/browse/HBASE-3857

HFile在v2里引入分层索引,是很值得研究的地方,对其他key-value db的设计有借鉴意义,此外,还有 compound Bloom filter,同样很值得思考

 

传统keyvalue数据库索引的设计

将索引结构顺序写到磁盘上,形成一个 Data Index Block,Data Index Block 会在数据库文件被打开时全部加载到内存。这样就可以根据内存中的索引数据检查出某个key具体在哪块block上,如果此块Data block IN_CACHE,就直接从内存里返回数据,如果IN_DISK,就lseek到偏移量处,将整块Block加载到内存,通常会使用lru算法来维护内存中的data block块数据,结构如下

在索引文件太大,1GB,数GB这种情况下,对性能会有很大的影响。因为会有频繁的 Data Block 被swaped到磁盘,又cache到内存。

 

分层索引

所以 HFile 在v2中开始引入了分层索引这一尝试,将索引文件分为 root block index 和 non-root block index 两种。root block index 会在数据库文件打开时被加载到内存。而non-root block index 会根据需要加载到内存,non-root block index 可以只有leaf-index block,或者还会有 intermediate level index block,如果Data Block 数据块个数少,leaf-index block 和 root block index足以,否则就需要加入中间层索引,也就是 intermediate level index block,它在 HFile文件里是可选的。实际情况下索引的层级不会超过两层。

root block index 由连续的entries组成,entry的结构如下,entry的个数会被记录在trailer结构里

如果是single level index,那么root block index里的每个entry就对应一个data block,这和 HFile v1是一样的。如果是two level index,那么root block index里的每个entry就指向每个leaf index block,而每个leaf index block则记录了对应的一系列Data block的偏移量。如果是三层,情况就要更复杂一下,root block index 里的entries指向intermediate level index block,而intermediate level index block则指向leaf index block。

leaf index block和intermediate level index block都以相同的格式封装在non-root block index里。结构类似于root block index,都是由连续的entries组成。

  1. numEntries 整块index block里的entry总数
  2. entryOffsets 每个entry的偏移量都记录在这里,目的是为了方便scan,二分搜索
  3. entries entry的结构和上述root block index里相同,由offset, on-disk size, key 组成

性能问题

HFile工作组目前已经在超过100个节点的集群环境里测试超过1个月时间,性能问题仍然有待考证。

如果lru,分层索引表面上可以解决由于索引文件过大而引起的加重IO负担问题。其实不然,会有一个不好的地方,传统的key-value db索引文件大多是平坦模型,能加载多少的数据,取决于服务器的主存规格。加入分层索引,就有了树的高度,就是b树,如果cache不命中,最坏情况下要都磁盘走两次,一次index block,然后才到data block。

至于这个问题是否成为性能问题的关键,要看实际的测试数据如何了

动态dns那点事

二月 8, 2012
Programming practices

最近在捣腾着家里的老爷机准备搭建一台服务器,因为在 linux 环境中,动态域名解析的事可没 windows 那么方便,就只好自己动手来解决了。主要还是依赖 oray 的服务。

ip 问题

实践证明,不依赖于外界条件,仅从本地环境是无法获取公网ip的。想来也是,内网与外网通信很多本身就是靠NAT地址转换来工作的。服务器发出去的数据包,只包含真实的目的ip地址,而源ip却是由内网分配的,经过路由的时候会被转换。

所以不管用什么途径 gethostbyname() 也好,getaddrinfo() 也好 ,还是靠分析socket套接口的内容来获得 ip 地址等等,均不能获得其公网的 ip。原因很简单,看看你底层硬件网卡所记录的信息就知道了。

 

Linux/C 代码:获取网卡ip地址
  1. int getpubipv4(char *ipv4)
  2. {
  3.     int sockfd;
  4.     struct ifreq ifr;
  5.     if ((sockfd = socket(AF_INET, SOCK_DGRAM, 0)) == -1)
  6.         return(0);
  7.     ifr.ifr_addr.sa_family = AF_INET;
  8.     strncpy(ifr.ifr_name, "eth0", IFNAMSIZ-1);
  9.     ioctl(sockfd, SIOCGIFADDR, &ifr);
  10.     sprintf(ipv4,"%s",
  11.         inet_ntoa(((struct sockaddr_in *)&ifr.ifr_addr)->sin_addr));
  12.     close(sockfd);
  13.     return(0);
  14. }

不过没有关系,获取公网 ip 还有很多方便的办法,查看路由表(原理上应该没有问题,没有实际验证过)和借助第三方API工具,比如 oray 的 checkip 服务就非常的不错,http://ddns.oray.com/checkip  如果你不担心 oray 服务稳定性问题的话。oray 提供的 web 查询服务,我们用代码来模拟一个 http 请求即可完成,大概是这样

GET /checkip HTTP/1.1[CRLF]
Host: ddns.oray.com[CRLF]
Connection: close[CRLF]
User-Agent: oray[CRLF]
Accept-Charset: ISO-8859-1,UTF-8;q=0.7,*;q=0.7[CRLF]
Cache-Control: no-cache[CRLF]
Accept-Language: de,en;q=0.7,en-us;q=0.3[CRLF]
[CRLF]

动态解析

oray 同样提供了非常详细的文档,参考:花生壳 HTTP 协议说明 。错误代码没必要解析那么详细,我也只是简单实现了一下 good ,足已。

 

后话,改善一下代码,写成 deamon,开机自动运行或者写个脚本,chkconfig 做成服务什么的都可以。一个 linux 下动态域名解析的问题就解决了。

BLOOM-FILTER 的误报率

一月 31, 2012
storage

先来解决 false-positives 与 false-negatives 的定义

  • false-positives: 将不属于该集合中的元素错误地以为是该集合中的,为误报
  • false-negatives: 将属于该集合中的元素错误地以为不是该集合中的,此为漏报

Bloom-filter 的设计是,漏报不可能发生,误报允许存在,但是概率要控制在一定的范围内。Bloom-filter 的问题实质上是分析 false-positives 的问题

Bloom 是这样计算的:

经过 kn 次 hash 之后,集合 S 中任意一位为 0 的概率是,也可以说是集合中 0 的比率

(1 - \frac{1}{m})^{kn}


可能为 1 的概率是

p = 1 - (1 - \frac{1}{m})^{kn}

而产生误报的条件是,k 个 hash 的结果都为 1,所以 false-positives 的概率应该是,Bloom 说的

f = p^k = \left(1 - (1 - \frac{1}{m})^{kn}\right)^k

我同样认为 Bloom 的论文中关于 false-positives 的估算是不算妥当,有兴趣的请移步:> ON THE FALSE-POSITIVE RATE OF BLOOM FILTERS 虽然这篇论文我只看了前部分,但是仍然觉得很有意思,Prosenjit Bose 等按照 Bloom 的方法讨论了一种较简单的情况,然后通过枚举计算出与实际误报率之间的偏差偏差。我的看法是,Bloom 的分析建立在非常理想的情况下,不足为奇
此外,我还另从两个角度去思考了一下 false-positives 的问题,仅作为讨论,请指正。

其一:

方便理解,因为 false-positives 是指将不属于这个集合的元素错误的以为是这个集合里的,这个概率用 e 来表示,那么 S 容量的上限为 (1 + e)*n
假设情况相当理想,种种随机。

于是有
经过 kn 次 hash 之后,集合 S 中任意一位可能为 1 的概率是

p = 1 - (1 - \frac{1}{m})^{kn}


所以,

f = p^k = \left(1 - (1 - \frac{1}{m})^{kn}\right)^k

f 是指集合 S 中任意 k 位均为 1 的概率。这是产生一个 false-positive 的必要条件。那么实质上就是计算 S 的可能容量 g 的问题

g = (^{m}_{k}) * f \ge n


因为:

  1. 如果不存在 false-positives,那么 S 的可能容量 g 等于实际容量 n
  2. 如果存在 false-positives,那么 S 的可能容量 g 一定大于实际容量 n

所以 e 的值应该表示为

\frac{g- n}{n} = \frac{(^{m}_{k}) * f - n}{n} = \frac{(^{m}_{k}) * \left(1 - (1 - \frac{1}{m})^{kn}\right)^k - n}{n}

其二:

同理前面已论述,全部元素插入之后,任意 k 位均为 1 的概率是

p^k = \left(1 - (1 - \frac{1}{m})^{kn}\right)^k

但是还不能说这就是 Bloom filter 的误报率,因为这里还包含着很小一部分正确的概率,只有发生错误时存在误报。如果一个元素确定存在,则对应的 k 位均为 1

(\frac{1}{m})^k


所以 false-positive rate 是理应是这样的:

f = \left(1 - (1 - \frac{1}{m})^{kn}\right)^k - n * (\frac{1}{m})^k

上式两边取对数并求 k 偏导可得

ln(f) = k * ln\left(1 - e^{\frac{-kn}{m}}\right) - ln\left(\frac{n}{m^k}\right)

\frac{1}{f}*f^' = ln(1 - e^\frac{-kn}{m}) - \frac{\frac{-kn}{m} * e^\frac{-kn}{m}}{1 - e^\frac{-kn}{m}} - ln(m)

然后令 -kn/m = x, ln(m) = y, 看其在二维坐标图上的分布,以寻求是否存在某种隐藏的关系

 y = ln(1 - e^x) - \frac{e^x*x}{1 - e^x}

Why ?