FastDHT－高效分布式Hash系統(tǒng)

happy_fish100

FastDHT是一個(gè)基于鍵值對(duì)（Key Value Pair）的高效的分布式Hash系統(tǒng)，她可以用來(lái)存儲(chǔ)大量的Key Value Pair，比如可以用來(lái)存儲(chǔ)文件名映射表、session數(shù)據(jù)、用戶(hù)相關(guān)數(shù)據(jù)等等。

FastDHT服務(wù)器端底層存儲(chǔ)采用Berkeley DB，支持大數(shù)據(jù)量；網(wǎng)絡(luò)IO采用libevent，支持大并發(fā)連接。FastDHT只用到了BDB最基本的存儲(chǔ)功能，數(shù)據(jù)同步是自己實(shí)現(xiàn)的，采用了binlog的復(fù)制方式。

FastDHT集群由一個(gè)或多個(gè)組（group）組成，每個(gè)組由一臺(tái)或多臺(tái)服務(wù)器組成，同組服務(wù)器上存儲(chǔ)的數(shù)據(jù)是相同的，數(shù)據(jù)同步只在同組的服務(wù)器之間進(jìn)行。組內(nèi)各個(gè)服務(wù)器是對(duì)等的，對(duì)數(shù)據(jù)進(jìn)行存取時(shí)，可以根據(jù)key的hash值來(lái)決定使用哪臺(tái)服務(wù)器。數(shù)據(jù)同步采用推（Push）的方式，由源服務(wù)器主動(dòng)將數(shù)據(jù)同步到本組的其他服務(wù)器。

由客戶(hù)端決定應(yīng)該選擇哪臺(tái)服務(wù)器，為例避免查表，應(yīng)該根據(jù)key的hash code來(lái)選擇服務(wù)器，算法描述如下：
  1. 計(jì)算出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 % 組內(nèi)server_count
計(jì)算server_index和group_index時(shí)使用了不同的hash code，是因?yàn)槿绻鹓roup_count和組內(nèi)server_count相等，例如都等于2，那么對(duì)于一個(gè)組來(lái)說(shuō)，任何key值都將選中其中一臺(tái)固定的服務(wù)器（server_index == group_index)。

FastDHT中，key由三部分組成：namespace、object ID和key name。這個(gè)設(shè)計(jì)和數(shù)據(jù)庫(kù)的層級(jí)劃分相似：namespace對(duì)應(yīng)database，object Id對(duì)應(yīng)table，而key對(duì)應(yīng)字段。引入namespace的目的是解決多個(gè)使用者（如：應(yīng)用或產(chǎn)品）之間可能存在的數(shù)據(jù)沖突問(wèn)題；引入object Id是便于對(duì)object相關(guān)的數(shù)據(jù)（如用戶(hù)資料）進(jìn)行組織和管理，以提高整體性能。引入namespace和object ID使得系統(tǒng)具有更大的靈活性，在實(shí)際使用中，這兩個(gè)字段可以設(shè)置為空值。在計(jì)算key的hash code時(shí)，如果namespace和object ID不為空，將這二者合并起來(lái)作為hash函數(shù)的輸入；否則將key作為hash函數(shù)的輸入。

系統(tǒng)擴(kuò)容時(shí)，為了避免重新進(jìn)行hash分布（rehash），F(xiàn)astDHT引入了邏輯分組的概念。一個(gè)物理分組對(duì)應(yīng)一組服務(wù)器，一組服務(wù)器（物理分組）上可以有多個(gè)邏輯分組。FastDHT的一個(gè)服務(wù)進(jìn)程支持多個(gè)邏輯分組，每個(gè)組對(duì)應(yīng)一個(gè)BDB的數(shù)據(jù)文件。這樣的設(shè)計(jì)為以后的擴(kuò)容提供了便利。在初期估算出今后需要的大致分組數(shù)目（邏輯分組數(shù)），然后將邏輯分組對(duì)應(yīng)到物理分組中。擴(kuò)容時(shí)，將一個(gè)或多個(gè)邏輯分組遷移到新增的物理分組上，只需要拷貝對(duì)應(yīng)的BDB數(shù)據(jù)文件，并修改相應(yīng)的配置文件，重啟服務(wù)器端和客戶(hù)端程序即可。

FastDHT支持超時(shí)（timeout），每個(gè)key都有超時(shí)屬性。這樣可以使用FastDHT來(lái)存儲(chǔ)session數(shù)據(jù)，比傳統(tǒng)的數(shù)據(jù)庫(kù)存儲(chǔ)方案更加高效和簡(jiǎn)潔。

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

todayhero

存儲(chǔ)端與FastDFS類(lèi)似.同組復(fù)制.

tc1987tc

不錯(cuò)

happy_fish100

V1.06支持對(duì)key的批量操作，包括批量get、set和delete。
PHP extension支持Class方式，支持多個(gè)配置文件（多個(gè)獨(dú)立的FastDHT集群）。
詳細(xì)的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

重要說(shuō)明，為了使得各種語(yǔ)言（如Java、C）采用相同hash算法得到的hash code相同，對(duì)C語(yǔ)言中的hash code算法進(jìn)行了調(diào)整（unsigned int改為signed int）。

預(yù)計(jì)本周末推出Java客戶(hù)端，敬請(qǐng)期待。

happy_fish100

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

[ 本帖最后由 happy_fish100 于 2009-3-14 14:40 編輯 ]

5iwww

為何沒(méi)有通用的API? 譬如可以直接支持NFS掛載? 或者可以作為模塊結(jié)合kernel補(bǔ)丁的方式來(lái)支持這個(gè)文件系統(tǒng)? 我記得lustre就可以.

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

方丈大師

先學(xué)習(xí)學(xué)習(xí)，再支持一下不遲！

flat_peach

請(qǐng)問(wèn)LZ這個(gè)與 FastDFS 是什么關(guān)系 ？