id分配是社区类产品的提交环节中必不可少的一步。任何UGC类内容产生时往往需要分配一个对应的id。

    id分配的几种方式 

    方式一：单点自增分配。全局由一个模块来负责生成id，可保证id从0开始连续递增，数据一般放在本地文件。简洁，但致命的问题是单点故障会导致服务整体不可用。

    方式一改进：为该模块提供主从复制的能力，或者干脆将数据放在mysql里，利用mysql的主从复制，都一定程度上增强了可用性，减轻了单点故障的影响。

    方式二：随机/散列分配。通过一些hash算法，比如以时间+随机串为key的md5生成一个唯一的id，关键点在于算法和key的选择要避免冲突。

    最典型的就是UUID，UUID的标准型式包含32个16进位数字，以连字号分为五段，形式为8-4-4-4-12的32个字符，如550e8400-e29b-41d4-a716-446655440000。libuuid提供了以时间或者随机数为基的UUID。UUID的最大缺点是位数太长，128位，在绝大多数应用和语言里对128位整数的支持都不好。

    方式二改进：有条件的进行压缩。twitter的snowflake使用 time - 41 bits + configured machine id - 10 bits + sequence number - 12 bits的形式分配id，共63位，最高部分使用毫秒级的时间戳，保证了一定程度的有序性，机器标示使用10位，最多可容纳1024个分配器，最后的12位序列号可以支持在1ms内产生4096个不重复的id。从工程角度，这些都足够用了。但对系统时间的依赖性非常强，需要关闭ntp的时间同步功能，或者当检测到ntp时间调整后，拒绝分配id。

    我们的需求和多IDC的挑战

    我们的实际情况是：

· 一些老模块依赖于从0开始自增的id，数据在内存或者文件中以id为偏移来存储的。

· 一些系统依赖于id的增长做数据分片，例如按取除后分表，因此要求id在整体上是比较均衡的增长。

· 在多IDC环境，高延迟加不稳定的网络环境，要求各个分配器彼此之间无需协作，或者可以容忍短期内不可协作。

· 对于一些古董级的老系统来说，还在使用32位的id，63位id还是太大了。

    因此，我们需要一种分布式高可用、从0开始自增、基本均衡、能够兼容老系统的id分配方案。

    取模或分段的分布式分配

    基于方案一再改进一步，将整个id空间按取模或分段等分为若干个独立的id子空间，每个id子空间由一个独立的分配器负责。

    优点：简单，各个id分配器无需协作，即使发生网络划分时，也可保证可用性和id的不冲突。

    如果在国际化环境的多IDC里进行部署，需要预先将id空间划分为N份，每个国家里部署若干份。每个IDC内应用只连本IDC的id分配服务。

    在均衡性上的不足：在同一个IDC内，均衡性可以在接入层均衡算法保证，但是在多个IDC里，ID分配器个数的比例和id增长的服务往往是不吻合的，因此在多个IDC内，id是无法保证均衡增长的。

    均衡性上的改进

    将id分配分为两层：

· 上层的“id分配器”对应用暴露，提供一次申请一个id的接口，一般本IDC的应用只连本IDC的id分配器。

·下层的“段分配器”对“id分配器”提供服务。id分配器“知晓”所有IDC的所有段分配器的存在，使用均衡策略向段分配器申请一个id段，当所持有的id段快耗尽时，再请求下一个段。

    唯一性：全局中，根据分片规则，每个段分配器会持有不同的id段。例如下表中，每个段的大小是100，段分配器A持有分片0和分片1。对于每个分片而言，是一个个跳跃的id段。特殊的，当段大小为1时，段分配器就是改进前的id分配器。

    均衡策略：均衡策略在id分配器来实现，简单的讲，是一个轮询策略。每个id分配器会轮询下游段分配器的状态，并选中id段的最小的那个，然后发起id段申请。由于不会加锁，当多个id分配器同时竞争时，可能会出现获取的id段不是全局最小的，可以附加一些策略来调优，比如再多获取一次，并本地排序。从整体上而言，id还是比较均衡的，可满足需求。

    可用性：当发生网络划分时，本IDC的id分配器可以只连接本IDC的段分配器，成功的申请到id段。整个系统可容忍一定时间内不可协作，长时间不可协作的唯一危害是id增长不均衡，此时，就退化为改进前的方案。

    多IDC环境的适应性：id分配器需要和所有IDC的段分配器交互，但是交互频率很低，同时和提供id分配服务是两个独立的阶段，不会受到多IDC网络环境的干扰。

    效果

    改进后的id分配方案成功的满足了图片系统重构过程中的兼容需求，并且部署在全球多个IDC内为图片系统提供全局唯一的id分配服务。

by Lizhe

建议继续学习：

1. 分布式缓存系统 Memcached 入门    (阅读：14422)
2. Zookeeper工作原理    (阅读：10159)
3. GFS, HDFS, Blob File System架构对比    (阅读：9214)
4. Zookeeper研究和应用    (阅读：8347)
5. 分布式日志系统scribe使用手记    (阅读：7882)
6. 一致性哈希算法及其在分布式系统中的应用    (阅读：7752)
7. 分布式哈希和一致性哈希    (阅读：7441)
8. HBase技术介绍    (阅读：6574)
9. 分布式系统的事务处理    (阅读：5724)
10. Memcache分布式部署方案    (阅读：5289)