谈一谈 ID 发号器原理及期使用场景

最近在研究分布式架构方面的技术。看到 ID 发号器这个东西。早在四五年前,就看过一版讲 Java 发号器的东西。当时对这个发号器并不是特别理解。也不知道何种场景会使用到它。于是,今天再度回首这个东西。想看看它到底怎样影响我们的开发生活。

一、数据库自增 ID

在深入了解 ID 发号器之前,我们先来了解一下经常用到的数据库自增 ID。自增 ID 对开发同学来说,是我们非常熟悉的一个东西。

它有三个特性:
1)唯一性。
2)递增性。
3)步长固定。

在我们在编程中,经常会利用到这三个特性。帮助我们编写出健壮的程序。

但是,当我们的数据疯狂增长的时候。数据库的架构势必会发生变化:分库分表。

比如,我们的用户表。我们通过会拿数据库自增 ID 作为用户的 ID。一旦分库分表之后,那么怎样保证这个 ID 的连续性和唯一性呢?

像类似的数据有很多。例如:订单表、资产表。

二、UUID

针对第一点中遇到的问题。于是就有人提出了 UUID 的方案来解决该问题。

以下是百度百科对 UUID 的说明:

UUID 是 通用唯一识别码(Universally Unique Identifier)的缩写,是一种软件建构的标准,亦为开放软件基金会组织在分布式计算环境领域的一部分。其目的,是让分布式系统中的所有元素,都能有唯一的辨识信息,而不需要通过中央控制端来做辨识信息的指定。如此一来,每个人都可以创建不与其它人冲突的UUID。在这样的情况下,就不需考虑数据库创建时的名称重复问题。

但是,UUID 真的是一个很好的解决方案吗?

使用 UUID 会存在以下 4 个问题:
1)UUID 无法保证趋势递增。
2)UUID 过长。往往用 32 位字符串表示,占用数据库空间较大,做主键的时候索引中主键 ID 占据的空间较大。
3)UUID 作为主键建立索引查询效率低,常见优化方案为转化为两个 64 位无符号整数存储。
4)由于使用实现版本的不一样,在高并发情况下可能会出现 UUID 重复的情况。

这 4 个问题我们都很容易理解。

如果 UUID 不行。那么,还有没有其他的解决方案呢?

三、自定义数据库 ID 自增步长

UUID 既然没法很好解决分库分表带来的问题。于是,有人就想了一个低成本的方案。如下图所示:

20180423195308212.jpg

如上图所述,由 1 个数据库变成 4 个库。每个数据库设置不同的 auto_increment 初始值 init,以及相同的增长步长 step,以保证每个数据库生成的ID是不同的,改进后的架构保证了可用性。

但是,它有以下几个缺点:

1)丧失了 ID 生成的“绝对递增性”。但这个问题不大,我们的目标是趋势递增,不是绝对递增;
2)数据库的写压力依然很大。每次生成 ID 都要访问数据库,判断下一次生成的 ID 该多少了。保证连续性、唯一性。
3)可扩展性差。

我们可以想象的是,目前虽然我们的机器只有 4 台,然后由不同的 init 和不同的 step。但是如果我们需要在其中再加一台机器的话,可想而知我们需要手动更新 init 和 step,这是一件比较繁琐的事情!

但有人可能会说了,我们可以直接把 step 设置大一些,假如,我们预期数据最大规模的时候用 100 台数据库服务器就可以了,那我们就可以设置step 为 100。

尽管如此,扩展性还不是很高!

四、SnowFlake 算法

通过以上三大点,我们已经对这个 ID 生成有了一个清晰的认知,它需要满足以下条件:
1)唯一性。
2)有序性。
3)可扩展。
4)高性能。

我们的 Twitter 公司也遇到了这样的问题。于是,Twitter 的工程师就搞了一套算法:SnowFlake。中文称为:雪花算法。

4.1)Snowflake 算法原理
SnowFlake 产生的 ID 是一个 64位的整型,结构如下:

  unused                                                        datacenter_id          sequence_id
                                                                                           
       │                                                              │                     │
       │                                                              │                     │
       │  │                                                      │    │                     │
       │  │                                                      │    │                     │
       ▼  │◀──────────────────    41 bits  ────────────────────▶ │    ▼                     ▼
    ┌─────┼──────────────────────────────────────────────────────┼────────┬────────┬────────────────┐
    │  0  │ 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0  │ 00000  │ 00000  │ 0000 0000 0000 │
    └─────┴──────────────────────────────────────────────────────┴────────┴────────┴────────────────┘
                                      ▲                                        ▲
                                      │                                        │
                                      │                                        │
                                      │                                        │
                                      │                                        │
                                      │                                        │
                                      │                                        │

                            time in milliseconds                          worker_id

(1)1位:标识部分。正数是 0,负数是1,一般生成的ID为正数,所以为0;

(2)41位:时间戳部分。这个是毫秒级的时间。一般实现上不会存储当前的时间戳,而是时间戳的差值(当前时间-固定的开始时间),这样可以使产生的 ID 从更小值开始;41 位的时间戳可以使用 69 年,(1L << 41) / (1000L 60 60 24 365) = 69年;

(3)10位:数据中心节点部分。Twitter 实现中使用前 5 位作为数据中心标识,后 5 位作为机器标识,可以部署 1024 个节点;

(4)12位:序列号部分。支持同一毫秒内同一个节点可以生成 4096 个ID;

SnowFlake 算法生成的 ID 大致上是按照时间递增的。用在分布式系统中时,需要注意数据中心标识和机器标识必须唯一。这样就能保证每个节点生成的 ID 都是唯一的!

4.2)各种发号器库或实现介绍
Golang 版发号器库
GitHub 地址:https://github.com/bwmarrin/snowflake

package main

import (
    "fmt"
    "github.com/bwmarrin/snowflake"
)

func main() {
    // Create a new Node with a Node number of 1
    node, err := snowflake.NewNode(1)
    if err != nil {
        fmt.Println(err)
        return
    }
    // Generate a snowflake ID.
    id := node.Generate()
    // Print out the ID in a few different ways.
    fmt.Printf("Int64  ID: %d\n", id)
    fmt.Printf("String ID: %s\n", id)
    fmt.Printf("Base2  ID: %s\n", id.Base2())
    fmt.Printf("Base64 ID: %s\n", id.Base64())
    // Print out the ID's timestamp
    fmt.Printf("ID Time  : %d\n", id.Time())
    // Print out the ID's node number
    fmt.Printf("ID Node  : %d\n", id.Node())
    // Print out the ID's sequence number
    fmt.Printf("ID Step  : %d\n", id.Step())
    // Generate and print, all in one.
    fmt.Printf("ID       : %d\n", node.Generate().Int64())
}

输出如下:

Int64  ID: 1062994665390739456
String ID: 1062994665390739456
Base2  ID: 111011000000100001000000010000100100110000000001000000000000
Base64 ID: MTA2Mjk5NDY2NTM5MDczOTQ1Ng==
ID Time  : 1542272652372
ID Node  : 1
ID Step  : 0
ID       : 1062994665390739457

Golang 语言性能非常高。所以,我们可以通过这个库生成 ID。然后,再提供一个 RPC 或 TCP 这样的服务供其他系统调用。

PHP 版发号器
目前我看到的最多的还是 PHP + Swoole 的 ID 发号器方案。如果你有更好的 PHP 发号器库,请留言告诉我。
文章介绍:
分布式ID生成器PHP+Swoole实现(上) - 实现原理
分布式ID生成器PHP+Swoole实现(下) - 代码实现

Redis 发号器
我见过有人用 Redis 做 ID 生成方案。但是,我个人不是很推荐这种做法了。

Java 的我不熟悉。我相信 Java 应该有很多这样的开源方案。

总结

ID 生成器,当前开发的大环境都是使用 Twitter 公司的 SnowFlake 算法。它在分布式架构当中扮演着不可或缺的一部分。

博主 2011 年创建了一个《PHP 初学者官方群》,目前群成员 500 人左右。群号:168159147。为了防止广告,设置为付费入群。欢迎大家加入讨论技术!

标签: 无

精彩评论
  1. 开发者头条 开发者头条

    感谢分享!已推荐到《开发者头条》:https://toutiao.io/posts/wz3gwx 欢迎点赞支持!使用开发者头条 App 搜索 158069 即可订阅《PHP 解说》

发表评论: