FastDHT－高效分布式Hash系统

Question

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

Answer 1

存储端与FastDFS类似.同组复制.

Answer 2

不错

Answer 3

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

Answer 4

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客户端，敬请期待。

Answer 5

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

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

Answer 6

为何没有通用的API? 譬如可以直接支持NFS挂载? 或者可以作为模块结合kernel补丁的方式来支持这个文件系统? 我记得lustre就可以.

Answer 7

主要新增功能：提供了日志文件压缩工具 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

Answer 8

先学习学习，再支持一下不迟！

Answer 9

请问LZ这个与 FastDFS 是什么关系 ？