一、分布式系统带来ID生成挑战 在分布式系统中，往往需要对大量的数据如订单、账户进行标识，以一个有意义的有序的序列号来作为全局唯一的ID。
而分布式系统中我们对ID生成器要求又有哪些呢?

• 全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
• 递增：比较低要求的条件为趋势递增，即保证下一个ID一定大于上一个ID，而比较苛刻的要求是连续递增，如1,2,3等等。
• 高可用高性能：ID生成事关重大，一旦挂掉系统崩溃; 高性能是指必须要在压测下表现良好，如果达不到要求则在高并发环境下依然会导致系统瘫痪。

二、业内方案简介 1. UUID方案
优点：

• 能够保证独立性，程序可以在不同的数据库间迁移，效果不受影响。
• 保证生成的ID不仅是表独立的，而且是库独立的，这点在你想切分数据库的时候尤为重要。

缺点：

• 性能问题：UUID太长，通常以36长度的字符串表示，对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。
• UUID无业务含义：很多需要ID能标识业务含义的地方不使用。
• 不满足递增要求。

2. snowflake方案
snowflake是twitter开源的分布式ID生成系统。 Twitter每秒有数十万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并且在分布式系统中不同机器产生的id必须不同。

文章图片

snowflake的结构如下(每部分用-分开):
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 – 000000000000
第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)，然后是5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点） ，最后12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）
一共加起来刚好64位，为一个Long型。
snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。snowflake的缺点是：

• 强依赖时钟，如果主机时间回拨，则会造成重复ID
• ID虽然有序，但是不连续

snowflake现在有较好的改良方案，比如美团点评开源的分布式ID框架：leaf，通过使用ZooKeeper解决了时钟依赖问题。
3. 基于数据库方案
利用数据库生成ID是最常见的方案。能够确保ID全数据库唯一。其优缺点如下：
优点：

• 非常简单，利用现有数据库系统的功能实现，成本小，有DBA专业维护。
• ID单调自增。

缺点：

• 不同数据库语法和实现不同，数据库迁移的时候或多数据库版本支持的时候需要处理。
• 在单个数据库或读写分离或一主多从的情况下，只有一个主库可以生成。有单点故障的风险。
• 在性能达不到要求的情况下，比较难于扩展。
• 如果涉及多个系统需要合并或者数据迁移会比较麻烦。
• 分表分库的时候会有麻烦。

4. 其他方案简介
通过Redis生成ID(主要通过redis的自增函数)、ZooKeeper生成ID、MongoDB的ObjectID等均可实现唯一性的要求。
三、我们在实际应用中使用的方案 1. 方案简介
实际业务中，除了分布式ID全局唯一之外，还有是否趋势/连续递增的要求。根据具体业务需求的不同，有两种可选方案。
一是只保证全局唯一，不保证连续递增。二是既保证全局唯一，又保证连续递增。
2. 基于ZooKeeper和本地缓存的方案
基于zookeeper分布式ID实现方案有很多种，本方案只使用ZooKeeper作为分段节点协调工具。每台服务器首先从zookeeper缓存一段，如1-1000的id。
此时zk上保存最大值1000，每次获取的时候都会进行判断，如果id小于本地最大值，即id<=1000，则更新本地的当前值，如果id大于本地当前值，比如说是1001，则会将从zk再获取下一个id数据段并在本地缓存。获取数据段的时候需要更新zk节点数据，更新的时候使用curator的分布式锁来实现。
由于id是从本机获取，因此本方案的优点是性能非常好。缺点是如果多主机负载均衡，则会出现不连续的id，当然将递增区段设置为1也能保证连续的id，但是效率会受到很大影响。
实现关键源码如下：

import org.apache.curator.framework.CuratorFramework; import org.apache.curator.framework.CuratorFrameworkFactory; import org.apache.curator.framework.recipes.locks.InterProcessSemaphoreMutex; import org.apache.curator.retry.ExponentialBackoffRetry; import org.apache.zookeeper.CreateMode; import org.apache.zookeeper.data.Stat; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import java.io.UnsupportedEncodingException; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; /** * 根据开源项目mycat实现基于zookeeper的递增序列号 * * 只要配置好ZK地址和表名的如下属性 * MINID 某线程当前区间内最小值 * MAXID 某线程当前区间内最大值 * CURID 某线程当前区间内当前值 * * @author wangwanbin * @version 1.0 * @time 2017/9/1 */ public class ZKCachedSequenceHandler extends SequenceHandler { protected static final Logger LOGGER = LoggerFactory.getLogger(ZKCachedSequenceHandler.class); private static final String KEY_MIN_NAME = ".MINID"; // 1 private static final String KEY_MAX_NAME = ".MAXID"; // 10000 private static final String KEY_CUR_NAME = ".CURID"; // 888 private final static long PERIOD = 1000; //每次缓存的ID段数量 private static ZKCachedSequenceHandler instance = new ZKCachedSequenceHandler(); /** * 私有化构造方法,单例模式 */ private ZKCachedSequenceHandler() { }/** * 获取sequence工具对象的唯一方法 * * @return */ public static ZKCachedSequenceHandler getInstance() { return instance; }private Map, Map, String>> tableParaValMap = null; private CuratorFramework client; private InterProcessSemaphoreMutex interProcessSemaphore = null; public void loadZK() { try { this.client = CuratorFrameworkFactory.newClient(zkAddress, new ExponentialBackoffRetry(1000, 3)); this.client.start(); } catch (Exception e) { LOGGER.error("Error caught while initializing ZK:" + e.getCause()); } }public Map, String> getParaValMap(String prefixName) { if (tableParaValMap == null) { try { loadZK(); fetchNextPeriod(prefixName); } catch (Exception e) { LOGGER.error("Error caught while loding configuration within current thread:" + e.getCause()); } } Map, String> paraValMap = tableParaValMap.get(prefixName); return paraValMap; }public Boolean fetchNextPeriod(String prefixName) { try { Stat stat = this.client.checkExists().forPath(PATH + "/" + prefixName + SEQ); if (stat == null || (stat.getDataLength() == 0)) { try { client.create().creatingParentsIfNeeded().withMode(CreateMode.PERSISTENT) .forPath(PATH + "/" + prefixName + SEQ, String.valueOf(0).getBytes()); } catch (Exception e) { LOGGER.debug("Node exists! Maybe other instance is initializing!"); } } if (interProcessSemaphore == null) { interProcessSemaphore = new InterProcessSemaphoreMutex(client, PATH + "/" + prefixName + SEQ); } interProcessSemaphore.acquire(); if (tableParaValMap == null) { tableParaValMap = new ConcurrentHashMap<>(); } Map, String> paraValMap = tableParaValMap.get(prefixName); if (paraValMap == null) { paraValMap = new ConcurrentHashMap<>(); tableParaValMap.put(prefixName, paraValMap); } long now = Long.parseLong(new String(client.getData().forPath(PATH + "/" + prefixName + SEQ))); client.setData().forPath(PATH + "/" + prefixName + SEQ, ((now + PERIOD) + "").getBytes()); if (now == 1) { paraValMap.put(prefixName + KEY_MAX_NAME, PERIOD + ""); paraValMap.put(prefixName + KEY_MIN_NAME, "1"); paraValMap.put(prefixName + KEY_CUR_NAME, "0"); } else { paraValMap.put(prefixName + KEY_MAX_NAME, (now + PERIOD) + ""); paraValMap.put(prefixName + KEY_MIN_NAME, (now) + ""); paraValMap.put(prefixName + KEY_CUR_NAME, (now) + ""); } } catch (Exception e) { LOGGER.error("Error caught while updating period from ZK:" + e.getCause()); } finally { try { interProcessSemaphore.release(); } catch (Exception e) { LOGGER.error("Error caught while realeasing distributed lock" + e.getCause()); } } return true; }public Boolean updateCURIDVal(String prefixName, Long val) { Map, String> paraValMap = tableParaValMap.get(prefixName); if (paraValMap == null) { throw new IllegalStateException("ZKCachedSequenceHandler should be loaded first!"); } paraValMap.put(prefixName + KEY_CUR_NAME, val + ""); return true; }/** * 获取自增ID * * @param sequenceEnum * @return */ @Override public synchronized long nextId(SequenceEnum sequenceEnum) { String prefixName = sequenceEnum.getCode(); Map, String> paraMap = this.getParaValMap(prefixName); if (null == paraMap) { throw new RuntimeException("fetch Param Values error."); } Long nextId = Long.parseLong(paraMap.get(prefixName + KEY_CUR_NAME)) + 1; Long maxId = Long.parseLong(paraMap.get(prefixName + KEY_MAX_NAME)); if (nextId > maxId) { fetchNextPeriod(prefixName); return nextId(sequenceEnum); } updateCURIDVal(prefixName, nextId); return nextId.longValue(); }public static void main(String[] args) throws UnsupportedEncodingException { long startTime = System.currentTimeMillis(); //获取开始时间 final ZKCachedSequenceHandler sequenceHandler = getInstance(); sequenceHandler.loadZK(); new Thread() { public void run() { long startTime2 = System.currentTimeMillis(); //获取开始时间 for (int i = 0; i < 5000; i++) { System.out.println("线程1 " + sequenceHandler.nextId(SequenceEnum.ACCOUNT)); } long endTime2 = System.currentTimeMillis(); //获取结束时间 System.out.println("程序运行时间1：" + (endTime2 - startTime2) + "ms"); } }.start(); for (int i = 0; i < 5000; i++) { System.out.println("线程2 " + sequenceHandler.nextId(SequenceEnum.ACCOUNT)); } long endTime = System.currentTimeMillis(); //获取结束时间 System.out.println("程序运行时间2：" + (endTime - startTime) + "ms"); } }

可以看到，由于不需要进行过多的网络消耗，缓存式的zk协调方案性能相当了得，生成10000个id仅需553ms(两个线程耗时较长者) , 平均每个id消耗0.05ms。
3. 利用zk的永久自增节点策略实现持续递增ID
使用zk的永久sequence策略创建节点，并获取返回值，然后删除前一个节点，这样既防止zk服务器存在过多的节点，又提高了效率；节点删除采用线程池来统一处理，提高响应速度。
优点：能创建连续递增的ID。
关键实现代码如下：

package com.zb.p2p.utils; import com.zb.p2p.enums.SequenceEnum; import org.apache.commons.pool2.PooledObject; import org.apache.commons.pool2.PooledObjectFactory; import org.apache.commons.pool2.impl.DefaultPooledObject; import org.apache.commons.pool2.impl.GenericObjectPool; import org.apache.commons.pool2.impl.GenericObjectPoolConfig; import org.apache.curator.framework.CuratorFramework; import org.apache.curator.framework.CuratorFrameworkFactory; import org.apache.curator.retry.ExponentialBackoffRetry; import org.apache.zookeeper.CreateMode; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import java.util.ArrayDeque; import java.util.Iterator; import java.util.Queue; import java.util.concurrent.ConcurrentLinkedQueue; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; /** * 基于zk的永久型自增节点PERSISTENT_SEQUENTIAL实现 * 每次生成节点后会使用线程池执行删除节点任务 * Created by wangwanbin on 2017/9/5. */ public class ZKIncreaseSequenceHandler extends SequenceHandler implements PooledObjectFactory { protected static final Logger LOGGER = LoggerFactory.getLogger(ZKCachedSequenceHandler.class); private static ZKIncreaseSequenceHandler instance = new ZKIncreaseSequenceHandler(); private static ExecutorService fixedThreadPool = Executors.newFixedThreadPool(1); private GenericObjectPool genericObjectPool; private Queue preNodes = new ConcurrentLinkedQueue<>(); private static String ZK_ADDRESS = ""; //192.168.0.65 private static String PATH = ""; ///sequence/p2p private static String SEQ = ""; //seq; /** * 私有化构造方法,单例模式 */ private ZKIncreaseSequenceHandler() { GenericObjectPoolConfig config = new GenericObjectPoolConfig(); config.setMaxTotal(4); genericObjectPool = new GenericObjectPool(this, config); }/** * 获取sequence工具对象的唯一方法 * * @return */ public static ZKIncreaseSequenceHandler getInstance(String zkAddress, String path, String seq) { ZK_ADDRESS = zkAddress; PATH = path; SEQ = seq; return instance; }@Override public long nextId(final SequenceEnum sequenceEnum) { String result = createNode(sequenceEnum.getCode()); final String idstr = result.substring((PATH + "/" + sequenceEnum.getCode() + "/" + SEQ).length()); final long id = Long.parseLong(idstr); preNodes.add(id); //删除上一个节点 fixedThreadPool.execute(new Runnable() { @Override public void run() { Iterator iterator = preNodes.iterator(); if (iterator.hasNext()) { long preNode = iterator.next(); if (preNode < id) { final String format = "%0" + idstr.length() + "d"; String preIdstr = String.format(format, preNode); final String prePath = PATH + "/" + sequenceEnum.getCode() + "/" + SEQ + preIdstr; CuratorFramework client = null; try { client = (CuratorFramework) genericObjectPool.borrowObject(); client.delete().forPath(prePath); preNodes.remove(preNode); } catch (Exception e) { LOGGER.error("delete preNode error", e); } finally { if (client != null) genericObjectPool.returnObject(client); } } } } }); return id; }private String createNode(String prefixName) { CuratorFramework client = null; try { client = (CuratorFramework) genericObjectPool.borrowObject(); String result = client.create().creatingParentsIfNeeded().withMode(CreateMode.PERSISTENT_SEQUENTIAL) .forPath(PATH + "/" + prefixName + "/" + SEQ, String.valueOf(0).getBytes()); return result; } catch (Exception e) { throw new RuntimeException("create zookeeper node error", e); } finally { if (client != null) genericObjectPool.returnObject(client); } }public static void main(String[] args) { ExecutorService executorService = Executors.newFixedThreadPool(1); long startTime = System.currentTimeMillis(); //获取开始时间 final ZKIncreaseSequenceHandler sequenceHandler = ZKIncreaseSequenceHandler.getInstance("192.168.0.65", "/sequence/p2p", "seq"); int count = 10; final CountDownLatch cd = new CountDownLatch(count); for (int i = 0; i < count; i++) { executorService.execute(new Runnable() { public void run() { System.out.printf("线程 %s %d \n", Thread.currentThread().getId(), sequenceHandler.nextId(SequenceEnum.ORDER)); cd.countDown(); } }); } try { cd.await(); } catch (InterruptedException e) { LOGGER.error("Interrupted thread",e); Thread.currentThread().interrupt(); } long endTime = System.currentTimeMillis(); //获取结束时间 System.out.println("程序运行时间：" + (endTime - startTime) + "ms"); }@Override public PooledObject makeObject() throws Exception { CuratorFramework client = CuratorFrameworkFactory.newClient(ZK_ADDRESS, new ExponentialBackoffRetry(1000, 3)); client.start(); return new DefaultPooledObject<>(client); }@Override public void destroyObject(PooledObject p) throws Exception {}@Override public boolean validateObject(PooledObject p) { return false; }@Override public void activateObject(PooledObject p) throws Exception {}@Override public void passivateObject(PooledObject p) throws Exception {} }

测试结果如下，生成10000个id消耗=9443ms(两个线程耗时较长者), 平均每个id消耗0.9ms。
这还只是单zk连接的情况下，如果使用连接池来维护多个zk的连接，效率将成倍的提升。
四、结语 分布式ID生成器的实现有很多种。目前各方案也都各有特点。我们可以根据业务的具体要求，选择实现合适的方案。
最后 【面试文|分布式id生成策略,我和面试官扯了一个半小时】感谢你看到这里，我是不务正业的程序汪，一个java开发从业者，深耕行业六年了，每天都会分享java相关技术文章或行业资讯
欢迎大家关注和转发文章，也欢迎大家关注我的公众号：程序员麦冬，回复“007”领取200页的Java核心面试资料整理

推荐阅读

• 

  海门大桥
• 

  胃癌|胃癌偏爱这4类人，若你在其中，做好这5点，或许能幸免！
• 

  王者荣耀下载最新版安卓，王者荣耀助手安卓版下载
• 

  电商怎么做 粮油电商是什么意思，粮油是啥
• 

  弈星重塑啦！从围棋的对弈体验入手，天才少年的成长的关键词是：以身入局，____ 王者荣耀8月5日每日一题答案
• 

  安卓 强制前台,手机回收模式下安卓应用如何继续在后台运行?
• 

  电脑调哪几个设置可以让电脑变快速度 电脑调哪几个设置可以让电脑变快
• 

  老款5角硬币图片 「新款5元硬币」
• 

  西瓜汁放冰箱可以保存多久
• 

  qqbot源码分析,nginx源码分析
• 

  梦见抱着男孩
• 

  雨隐村曾经有几位首领 火影忍者手游10月28日每日一题答案
• 

  你看过最好看的美剧是什么？
• 

  php长数据发送 php传输数据的方式
• 

  行政处罚的种类包括人身罚行为罚财产罚和申诫罚 行政处罚的种类
• 

  mysql批量查询语句 mysql查询批量替换
• 

  六月黄吃到什么时候
• 

  小森生活游戏介绍 小森生活好玩吗
• 

  鸡丸的做法大全 鸡丸怎么做
• 

  秦时明月世界怎么转职 秦时明月世界转职业

• 技术分享|Redis 高负载下的中断优化
• 面试|SSM框架讲解（史上最详细的文章）
• 面试|SpringBoot启动流程
• java|找不到kotlin.jvm.functions.Function0的类文件
• java|windows安装Docker与docker-compose套装
• java|hive 读取 map的value
• java|MVVM框架第二篇 Navigation
• nosql|NoSQL之Redis配置与优化
• redis|Redis的主从复制、哨兵模式和集群