关于libmemcached中的crc的实现

缘起

libmemcached备受青睐,号称错误信息是很详细的,比所谓的memcache模块强多了;但是,就是因为他的名气大,还是被坑了;所谓的错误信息详细在get操作时完全不存在了,不管是连接失败还是各种超时,得到的错误信息都是NOTFOUND;于是乎,我想自己用PHP写一个memcached的client,起初,我可以之实现我需要的几个方法,鉴于memcache的协议很简单,应该是比较容易完成的。

问题

其实,我1天时间已经完成了memcache的几个简单的协议,出于一些不想说的考虑,当add多个server时,我需要把根据key的hash结果和libmemcached中的完全一样;看了libmemcached中几种hash和distribute的策略,我只想选择一种最简单的hash和distribute策略来实现,我选择了 crc32 + modular; 简而言之,算法就是: crc32(key) % count(server) 就Ok了; 但是,问题是PHP的crc32结果和libmemcached中的crc32结果是不同的,鉴于我的C语言水平有限,不想看和看不懂使得我咨询了一下牛人,没有结果,于是还是硬着头皮看吧。

分析

后面分别贴一下libmemcached和php中crc的实现,这里先说结论了:

二者差别不大,主要差别在于:

PHP中的crc32返回的是一个32位的有符号数,而libmemecached中返回的是前者32位有符号数种的高16位,并且忽略了符号位;

如果用PHP实现一个和libmemcached相同的crc32将是:

或者如下实现:

本来只需要简单的位移操作、异或操作就可以处理的事情,用PHP来实现却需要大量的pack、unpack,对‘test’进行crc32大约需要0.1ms(很慢的),如果用上面实现,大约比该实现快100倍

 

libmemcached:

php中的实现(说明一下: 这里的crc32tab和上面的是一样的):

 

关于crc32_table 的由来,crc32_table是出于提高效率的目的而诞生的,来源于一个神奇的数字 0x04c11db7:

 

参考资料:

http://baike.baidu.com/view/410181.htm?fr=aladdin

http://hi.baidu.com/qyiyunso/item/c06719c5872ed5d5964452ac

http://zh.wikipedia.org/wiki/CRC32

留下评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据