1.需求的由来几乎所有的业务系统都有生成记录标识的需求，例如：（1）消息标识：message-id（2）订单标识：order-id(3)PostID：tiezi-id的记录ID往往是数据库中唯一的主键，数据库上会建立一个簇索引(clusterindex)，即物理存储按该字段排序。对这条记录标识的查询，往往有分页或排序的业务需求，例如：（1）拉***一页消息：selectmessage-id/orderbytime/limit100（2）拉***一页order:selectorder-id/orderbytime/limit100(3)拉***单页post:selecttiezi-id/orderbytime/limit100所以经常会有时间字段，在时间字段中创建一个普通的索引（非聚簇索引）就可以了。我们都知道普通索引存储的是指向实际记录的指针，其访问效率会比聚簇索引慢。如果recordidentifiers在生成的时候基本可以按照时间排序，这个时间字段的索引查询可以省略：selectmessage-id/(orderbymessage-id)/limit100同样，这样做的前提是message-id的生成基本上随着趋势时间的增加而增加。这就引出了记录标识生成的两个核心需求（也就是上面提到的三个XXX-id）：（1）全局唯一性（2）趋势顺序这也是本文要讨论的核心问题：如何高效的生成已排序趋势的全局唯一ID。2.常用方法、不足及优化【常用方法一：利用数据库的auto_increment生成全局唯一的增量ID】优点：（1）简单，利用数据库已有的功能（2）可以保证唯一性（3）可以保证递增（4）固定步长缺点：（1）可用性难以保证：数据库常见的架构是一主多从+读写分离，生成自增ID是写请求，主要如果主数据库挂了，数据库将无法工作。(2)Expansion性能差，性能上限：因为写入是单点的，数据库主库的写入性能决定了ID生成性能的上限，难以扩展提升方法：（1）增加主库，避免写入单点（2）数据层面裁剪，保证每个主库生成的ID不重复数据库生成的ID不同（上图中，库0生成0,3,6,9...，库1生成1,4,7,10，库2生成2,5,8,11...)改进的架构保证了可用性，但缺点是：(1)ID生成的“绝对递增性”丢失：访问0库先生成0、3，再访问1库生成1，可能会在很短的时间内造成ID生成。绝对增加（这个问题不大，我们的目标是趋势增加，而不是绝对增加）（2）数据库写压力还是很大的，每生成一个ID，都要访问数据库才能解决上面两个问题，第二种常见的解决方法【常见方法二：单点批量ID生成服务】分布式系统之所以难，最重要的原因之一就是“没有全局时钟，很难保证绝对定时”。要保证绝对定时，或者只能使用单点服务，使用本地时钟来保证“绝对定时”。数据库写压力大，因为每次生成ID都要访问数据库，可以批量降低数据库写压力。如上图所述，数据库采用双主来保证可用性，数据库中只存储当前ID的最大值，比如0。ID生成服务假设每次批量取6个ID，服务访问数据库，将当前ID的最大值修改为5，这样应用访问ID生成服务请求ID，ID生成服务不需要每次访问数据库。0、1、2、3、4、5的ID依次分布。发送ID后，ID的最大值改为11，可以重新分配6,7,8,9,10,11这些ID删除，这样数据库的压力就降低到1/6原来的。优点：（1）保证了ID生成的绝对增量顺序（2）大大降低了数据库的压力，ID生成每秒可以生成几万、几十万缺点：（1）服务还是单点（2）如果服务挂了，服务重启后，连续生成的id可能不连续，中间会出现空洞（服务内存存储0,1,2,3,4,5,和数据库中的max-id为5，3点重启服务，下次从6开始分配，4和5就变空了，不过这个问题不大）（3）虽然几十每秒可以生成几千个或者几十万个ID，还是有性能限制的，横向扩展是不可能的。改进方法：常见的单点服务高可用优化方案是“备用服务”，也称为“影子服务”，所以我们可以通过以下方法来优化以上缺点（一）：如图上面，external提供的服务为主服务，还有一个一直处于待机状态的影子服务。当主服务宕机时，影子服务在上面。这个切换过程对调用者是透明的，可以自动完成。常用的技术是vip+keepalived，这里就不展开了。【常用方法3：uuid】虽然上述生成ID的方案性能有很大的提升，但是因为是单点系统，所以总是有性能上限的。同时，在以上两种方案中，无论是数据库还是服务生成ID，都需要业务方Application进行远程调用，比较耗时。有没有办法在本地生成ID，性能高，延迟低？uuid是一种常见的解决方案：stringID=GenUUID();优点：（1）ID在本地生成，无需远程调用，延迟低（2）扩展性好，基本没有性能上限缺点：（1）无法保证递增的趋势（2）UUID太长，常以字符串表示，索引作为主键查询效率低。常见的优化方案是“转换为两个uint64整数存储”或者“减半存储”（减半后不能保证唯一性）【常用方法4：获取当前毫秒数】uuid是一种本地算法，生成性能高，但是它不能保证趋势会增加，因为StringID检索效率低。有没有可以保证增量的本地算法？获取当前毫秒数是一种常见的解决方案：uint64ID=GenTimeMS();优点：（1）本地生成ID，无需远程调用，延迟低（2）生成的ID有增加的趋势（3）生成的ID为整数，建立索引后查询效率高。缺点：（1）如果并发超过1000，会产生重复的ID。我会去这个缺点。命运，无法保证ID的唯一性。当然，使用微秒可以降低碰撞的概率，但每秒最多只能生成1,000,000个ID。多了就会有冲突，所以用微秒并不能从根本上解决问题。【常用方法五：Snowflake-like算法】Snowflake是Twitter开源的一种分布式ID生成算法。它的核心思想是：一个long类型的ID，用41位作为毫秒数，10位作为机器号，12位作为毫秒内的序号。该算法理论上每秒最多可以生成1000*(2^12)个ID，即每秒400W个ID，完全可以满足业务需求。借鉴snowflake的思想，结合各个公司的业务逻辑和并发度，可以实现自己的分布式ID生成算法。例如，假设某公司ID生成器服务需求如下：（1）单机峰值并发量小于1W，预计单机峰值并发量小于10W未来5年（2）有2个机房，未来5年机房数量预计小于4台（3）每个机房机器数量小于100台（4）在目前有5个业务线有ID生成需求，未来业务线数量预计在10（5）个以内。分析过程如下：（1）高位取自2016年1月1日到现在的毫秒数（假设系统ID生成器服务在这个时间后上线），假设系统已经至少运行10年，至少需要10年*365天*24小时*3600秒*1000毫秒=320*10^9，大约39位预留给毫秒数（2）峰值单机每秒并发量小于10W，即单机每毫秒平均峰值并发量小于100，每毫秒内序号预留了近7位(3)如果5年内机房数量小于4台，机房标识预留2位（4）每个机房少于100台机器，每个机房服务器标识预留7位（5）业务线少大于10，4位保留给64位l这样设计的ogo可以保证：（1）每个业务线、每个机房、每台机器产生的ID是不同的（2）同一台机器每毫秒内产生的ID是不同的（3）在同一台机器上，在同一毫秒，生成的ID通过序号区分，保证生成的ID不同（4）把毫秒数放在首位，保证生成的ID是递增趋势的缺点：（1）由于到“没有全局时钟”，分配给每个服务器的ID是绝对递增的，但是从全局来看，生成的ID只是递增的（有的服务器早，有的服务器晚）***一个容易出现的问题忽略：生成的ID，比如message-id/order-id/tiezi-id，数据量大的时候往往需要分库分表。这些ID通常用作取模型、数据库和表的基础。分表后数据是统一的，ID的生成往往需要“取模随机性”，所以我们通常把每秒内的序号放在ID的末尾，以保证生成的ID是随机的。而如果，当我们跨越毫秒的时候，序号总是归0，这样就会使得序号为0的ID更多，导致取模生成的ID不均匀。解决办法就是每次不是把序号返回0，而是返回一个0到9的随机数，这个地方。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】
