FastDHT－高效分布式Hash系统

happy_fish100

FastDHT是一个基于键值对（Key Value Pair）的高效的分布式Hash系统，她可以用来存储大量的Key Value Pair，比如可以用来存储文件名映射表、session数据、用户相关数据等等。

FastDHT服务器端底层存储采用Berkeley DB，支持大数据量；网络IO采用libevent，支持大并发连接。FastDHT只用到了BDB最基本的存储功能，数据同步是自己实现的，采用了binlog的复制方式。

FastDHT集群由一个或多个组（group）组成，每个组由一台或多台服务器组成，同组服务器上存储的数据是相同的，数据同步只在同组的服务器之间进行。组内各个服务器是对等的，对数据进行存取时，可以根据key的hash值来决定使用哪台服务器。数据同步采用推（Push）的方式，由源服务器主动将数据同步到本组的其他服务器。

由客户端决定应该选择哪台服务器，为例避免查表，应该根据key的hash code来选择服务器，算法描述如下：
  1. 计算出key的hash值（hash_code）
  2. group_index = hash_code % group_count
  3. new_hash_code = hash_code高16位和低16位互换
  4. server_index = new_hash_code % 组内server_count
计算server_index和group_index时使用了不同的hash code，是因为如果group_count和组内server_count相等，例如都等于2，那么对于一个组来说，任何key值都将选中其中一台固定的服务器（server_index == group_index)。

FastDHT中，key由三部分组成：namespace、object ID和key name。这个设计和数据库的层级划分相似：namespace对应database，object Id对应table，而key对应字段。引入namespace的目的是解决多个使用者（如：应用或产品）之间可能存在的数据冲突问题；引入object Id是便于对object相关的数据（如用户资料）进行组织和管理，以提高整体性能。引入namespace和object ID使得系统具有更大的灵活性，在实际使用中，这两个字段可以设置为空值。在计算key的hash code时，如果namespace和object ID不为空，将这二者合并起来作为hash函数的输入；否则将key作为hash函数的输入。

系统扩容时，为了避免重新进行hash分布（rehash），FastDHT引入了逻辑分组的概念。一个物理分组对应一组服务器，一组服务器（物理分组）上可以有多个逻辑分组。FastDHT的一个服务进程支持多个逻辑分组，每个组对应一个BDB的数据文件。这样的设计为以后的扩容提供了便利。在初期估算出今后需要的大致分组数目（逻辑分组数），然后将逻辑分组对应到物理分组中。扩容时，将一个或多个逻辑分组迁移到新增的物理分组上，只需要拷贝对应的BDB数据文件，并修改相应的配置文件，重启服务器端和客户端程序即可。

FastDHT支持超时（timeout），每个key都有超时属性。这样可以使用FastDHT来存储session数据，比传统的数据库存储方案更加高效和简洁。

附：
google code地址：http://code.google.com/p/fastdht/
源码下载地址：http://code.google.com/p/fastdht/downloads/list

happy_fish100

V1.06支持对key的批量操作，包括批量get、set和delete。
PHP extension支持Class方式，支持多个配置文件（多个独立的FastDHT集群）。
详细的ChangeLog如下：

Version 1.06  2009-02-26
  * in config file conf/fdhtd.conf: add item "min_buff_size"
  * add batch get, can get multi keys once
  * add batch set, can set multi keys once
  * add batch delete, can delete multi keys once
  * php extension add class version, see sub dir php_client/
  * performance enhancement: in function get, delay expires (timeout)
    use partial set
  * php extension support multi config file
  * bug fix: fdht_client_init can be called more than once
  * move global config parameters to fastdht_client.ini

Version 1.05  2009-02-04
  * only start one dead_lock_detect thread to save resource
  * in file php_client/README: add function description
  * in file client/fdht_client.h: add function description / remark

Version 1.04  2009-01-29
  * sync.c: when call socket fail, continue deal (do not exit)
  * client: share a same sock when the ip and port of servers are same
  * client: thread-safe and add muti-thread test program fdht_test_thread.c
  * sync.c: fdht_sync_del return 0 when key not exists (errno: ENOENT)

Version 1.03  2009-01-25
  * BDB env->open add DB_INIT_LOCK flag and add BDB dead_lock_detect thread
  * shared_func.c add urlencode and urldecode functions
  * clear expired keys every interval seconds
  * php_client directory: add test_fastdht.php

Version 1.02  2009-01-18
  * protocol header add field: keep_alive to support persistent connection
  * fdhtd.conf add item: write_to_binlog to enable or disable replication
  * return ENOENT (key not exist) when the key expires
  * client auto reconnect when connection is reset and keep_alive is true
  * add php client extension
  * add README file in sub directories: client and php_client

Version 1.01  2008-12-15
  * fdhtd.conf add parameter: sync_db_time_base, change the default value of
    sync_db_interval to 86400 (one day)
  * remove fdht_global.h dependency of client codes

Version 1.00  2008-12-08
  * fix memory leak in sync.c
  * function enhancement: db recovery when the daemon starts
  * pass (void *)1 to memp_trickle before exit

Version 0.90  2008-12-02
  * use memp_trickle to sync data to BDB file periodically
  * fix bug: mod(%) result maybe < 0
  * sockopt.h / .c add function tcpsetnodelay
  * bug fixed: realloc size and reasign
  * add client set test program: fdht_test_set.c
  * add Makefile.in and make.sh
  * pipe read more bytes once

Version 0.80  2008-11-24
  * add namespace and object ID
  * add expires (timeout)
  * add binlog write buff to increase performance

Version 0.50  2008-10-22
  * support data sync

Version 0.20  2008-09-27
  * framework is done:
    # implement db functions such as get, set, inc and del
    # implement asynchronous IO use libevent

Version 0.10  2008-09-08
  * first version, only implement queue management

happy_fish100

change log:
Version 1.07  2009-03-13
* fastdht_client.ini: add parameter fastdht_client.log_filename
* a header can be recv more than one time (recv header particially)
* for compatible with other language such as Java, change hash function
   return type from unsigned int to int

重要说明，为了使得各种语言（如Java、C）采用相同hash算法得到的hash code相同，对C语言中的hash code算法进行了调整（unsigned int改为signed int）。

预计本周末推出Java客户端，敬请期待。

happy_fish100

FastDHT提供Java client API了，欢迎大家下载和使用。
google code下载地址： http://code.google.com/p/fastdht/downloads/list

[ 本帖最后由 happy_fish100 于 2009-3-14 14:40 编辑 ]

happy_fish100

主要新增功能：提供了日志文件压缩工具 fdht_compress，以减少日志文件占用空间。

Version 1.08  2009-04-12
* common/shared_func.c: rindex change to strrchr, add #include <netinet/in.h>
* use scheduling thread to sync binlog buff / cache to disk, add parameter
   "sync_binlog_buff_interval" to conf file fdhtd.conf
* add restart daemon shell script: restart.sh
* add compress binlog tool
* hash_walk change return type from void to int
* compress binlog tool can be run by scheduler, fdhtd.conf add parameters:
   compress_binlog_time_base and compress_binlog_interval

happy_fish100

原帖由 flat_peach 于 2009-6-19 10:04 发表
请问LZ这个与 FastDFS 是什么关系 ？

FastDHT是分布式Hash存储系统，FastDFS是分布式文件存储系统。
如果你需要相同文件内容的文件只保存一份时，FastDFS使用FastDHT来存储文件的签名（类似MD5）等信息。

happy_fish100

Version 1.09  2009-07-01
* correct php extension error info
* fdht_compress.c: make sure syncing is done
* add shell script: stop.sh, restart.sh modified
* add fdhtd as service in Linux platform
* correct get local ip addresses
* common files do not use global vars like g_network_timeout and g_base_path
* fdht_compress.c: use {base_path}/tmp as sort temporary path instead of /tmp
* sync.c: check binlog file format when reading
* client can use proxy for FastDHT
* cache size not division by g_db_count
* protocol add stat cmd
* client retry connect when connection is not connected and keep_alive is true
* multi db use only one env
* support MPOOL (memory only cache as memcached)
* when max_threads set 1, use process instead of thread
* client use non-block socket to increase performance
* hash.c use chain impl by self
* bugfix: never expired / persistent keys not be cleared when clear expired keys
* inc use thread lock for atomicity
* mpool use rwlock, support multi-threads
* change work thread mode
* stat cmd add more info

happy_fish100

Version 1.10  2009-07-19
* ini reader support HTTP protocol, conf file can be an url
* hash does not use macro: HASH_MALLOC_VALUE, add member is_malloc_value
* sockopt.c sendfile and recvfile support non-block socket
* sync.c call tcpsetnonblock after connect
* bug fix: sockopt.c do not set non-block in function tcpsetserveropt
* fdht_compress.c: change global static variable names to avoid conflict

happy_fish100

原帖由 sopato 于 2009-8-10 01:03 发表
想问问快乐鱼是否做过FASTDHT的压力测试，对于一套TPS超过12000的集群系统来说，FASTDHT合适和胜任吗？

做过压力测试的，MPOOL（纯缓存方式）下和memcached做过对比测试，性能不比memcached差。单机QPS是10K级的。

[ 本帖最后由 happy_fish100 于 2009-8-10 09:00 编辑 ]

happy_fish100

原帖由 airzhutao 于 2009-8-11 10:12 发表
请问put的速度能有多少？楼主用过BAMBOO DHT吗？

MPOOL方式不比memcached慢吧，BDB方式稍稍慢一些。
对BAMBOO DHT没有研究过。今天看了一下BAMBOO DHT，用java写的吧。性能上应该比不过FastDHT。