【 二、基于全局节点分配方式 】

　　1. 全局节点分配方式介绍

　　就是把所有Key信息与数据库节点之间的映射关系记录下来，保存到全局表中，当需要访问某个节点的时候，首先去全局表中查找，找到以后再定位到相应节点。全局表的存储方式一般两种：

　　(1) 采用节点数据库本身（MySQL/PostgreSQL）存储节点信息，能够远程访问，为了保证性能，同时配合使用 Heap(MEMORY) 内存表，或者是使用 Memcached 缓存方式来缓存，加速节点查找

　　(2) 采用 BDB(BerkeleyDB)、DBM/GDBM/NDBM 这类本地文件数据库，基于 key=>value 哈希数据库，查找性能比较高，同时结合 APC、Memcached 之类的缓存加速。

　　第 一种存储方式是容易查询（包括远程查询），缺点是性能不太好（这个是所有关系型数据库的通病）；第二种方式的有点是本地查询速度很快（特别是hash型数 据库，时间复杂度是O(1)，比较快），缺点是无法远程使用，并且无法在多台机器中间同步共享数据，存在数据一致的情况。

　　我们来描述实施 大概结构：假如我们有10个数据库节点，一个全局数据库用于存储Key到节点的映射信息，假设全局数据库有一个表叫做 AllNode ，包含两个字段，Key 和 NodeID，假设我们继续按照上面的案例，用户ID是Key，并且有一个用户ID为125的用户，它对应的节点，我们查询表获得：
　　  Key  NodeID
　　 13          2
　　 148  5
　　 22  9
　　 125  6

　　可以确认这个用户ID为125的用户，所在的节点是6，那么就可以迅速定位到该节点，进行数据的处理。

　　我们来查看一下分布存储结构图：

　　    (图3)

　　2. 全局节点分布方式的扩容

　　全局节点分配方式同样存在扩容的问题，不过它早就考虑到这个问题，并且这么设计就是为了便于扩容，主要的扩容方式是两种：

　　(1) 通过节点自然增加来分配Key到节点的映射扩容
　　这 种是最典型、最简单、最节约机器资源的扩容方式，大致就是按照每个节点分配指定的数据量，比如一个节点存储10万用户数据，第一个节点存储0-10w用户 数据，第二个节点存储10w-20w用户数据，第三个节点存储20w-30w用户信息，依此类推，用户增加到一定数据量就增加节点服务器，同时把Key分 配到新增加的节点上，映射关系记录到全局表中，这样可以无限的增加节点。存在的问题是，如果早期的节点用户访问频率比较低，而后期增加的节点用户访问频率 比较高，则存在节点服务器负载不均衡的现象，这个也是可以想方案解决的。

　　(2) 通过概率算法来映射Key到节点的的扩容
　　这种方式是在既然有的节点基础上，给每个节点设定一个被分配到Key的概率，然后分配Key的时候，按照每个节点被指定的概率进行分配，如果每个节点平均的数据容量超过了指定的百分比，比如50%，那么这时候就考虑增加新节点，那么新节点增加Key的概率要大于旧节点。
　　一般情况下，对于节点的被分配的概率也是记录在数据库中的，比如我们把所有的概率为100，共有10个节点，那么设定每个节点被分配的数据的概率为10，我们查看数据表结构：
　　NodeID Weight
　　1 10
　　2 10
　　3 10

　　现在新加入了一个 节点，新加入的节点，被分配Key的几率要大于旧节点，那么就必须对这个新加入的节点进行概率计算，计算公式：10х+у=100, у>х，得出：у{10...90}，х{1...9}，x是单个旧节点的概率，旧节点的每个节点的概率是一样的，y是新节点的概率，按照这个计算 公式，推算出新节点y的概率的范围，具体按照具体不同应用的概率公式进行计算。