FastDHT－高效分布式Hash系统

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数据，比传统的数据库存储方案更加高效和简洁。