很多大的互联网公司数据量很大, 都采用分库分表, 那么分库后就需要统一的唯一 ID 进行存储. 这个 ID 可以是数字递增的, 也可以是 UUID 类型的.
如果是递增的话, 那么拆分了数据库后, 可以按照 id 的 hash, 均匀的分配到数据库中, 并且 MySQL 数据库如果将递增的字段作为主键存储的话会大大提高存储速度. 但是如果把订单 ID 按照数字递增的话, 别人能够很容易猜到你有多少订单了, 这种情况就可以需要一种非数字递增的方式进行 ID 的生成.
想到分布式 ID 的生成, 大家可能想到采用 Redis 进行生成 ID, 使用 Redis 的 INCR 命令去生成和获取这个自增的 ID, 这个没有问题, 但是这个 INCR 的生成 QPS 速度为 200400(官网发布的测试结果), 也就是 20W 这样子, 如果 QPS 没有超过这些的话, 显然使用 Redis 比较合适.
那么我们对于要达到高可用, 高 QPS, 低延迟我们有没有更好的想法呢. 接下来一起看一下 snowflake 算法, 由 Twitter 公司开源的雪花算法.
snowflake 一共 64 位:
1. 第一位不用.
2. 41 位是时间戳. 2^41 以毫秒为单位的话, 可得到 69 年, 非常够用了.
3. 10 位位工作机器, 可以有 2^10=1024 个工作节点, 有的公司将其拆分为 5 位工作中心编码, 5 位分给工作机器.
4. 最后 12 位用于生成递增数据共 4096 个数.
如果用这个理论上的 QPS 上的 QPS 为 409W/S.
这种方式的优点为:
1. QPS 非常高, 性能也非常够. 高性能条件也满足了.
2. 不需要依赖其他第三方的中间件, 比如 Redis. 少了依赖, 可用率提高了.
3. 可以根据自己定制进行调节. 也就是里边的 10 位进行自由分配.
缺点:
1. 此种算法很依赖时钟, 假如时钟进行回拨了, 将有可能生成相同的 ID.
UUID 是采用 32 位二进制数据生成的, 它生成的性能非常好, 但是它是基于机器 Mac 地址生成的, 而且不是分布式的, 所以不是咱们讨论的范畴.
下面咱们看一下一些大公司的分布式 ID 实现机制, 通过生成创建一张表, 采用 8 个 Byte, 64 位进行存储使用, 用这张表记录所产生 ID 的位置, 比如 ID 从 0 开始, 然后使用了 1000 个, 那么数据库里边记录里边的最大值是一千, 同时还有个步长值, 比如 1000, 那么获取下一个值得时候最大值为 2001, 即最大的没有使用的值.
具体的实现步骤如下:
1. 提供一个生成分布式 ID 的服务, 这个 ID 的服务是读取数据库里边的值和步长值计算生成需要的值和范围, 然后服务消费方拿到后进行将号段存储到缓存中使用.
2. 当给到服务调用方之后, 数据库立即更新数据.
这种情况下的优点为:
1. 容灾性能好, 如果 DB 出现问题, 因为数据放到内存中, 还是可以支撑一段时间.
2. 8 个 Byte 可以满足业务生成 ID 使用.
3. 最大值可以自己定义, 这样有些迁移的业务还可以自己定义最大值继续使用.
当然缺点也存在:
1. 当数据库挂了整个系统将不能使用.
2. 号段递增的, 容易被其他人猜到.
3. 如果很多服务同时访问获取这个 ID 或者网络波动导致数据库 IO 升高的时候, 系统稳定性会出现问题.
然后针对上述情况的解决方法是他们采用了双缓存机制, 即将号码段读取到内存中之后开始使用, 当使用到了 10% 的时候重新启动一个新线程, 然后当一个缓存用完了之后去用另一块缓存的数据. 当另一个缓存的数据达到 10% 的时候再重启激动一个新线程获取, 依次反复.
这样做的好处是避免同时访问大量数据库, 导致 I/O 增多. 同时可以通过两个缓存段解决了单一缓存导致很快用完的情况. 当然把这个号段设置成 QPS 大小的 600 倍, 这样数据库挂了 10-20 分钟内还是可以继续提供服务的.
以上一直提到了一个问题, 就是 ID 递增, 咱们如何解决这个问题呢. 就是采用 snowflake, 然后解决里边的时钟问题, 有些公司采用 ZK 去比较当前 workerId 也就是节点 ID 使用的时间是否有回拨, 如果有回拨就进行休眠固定时间, 看是否能赶上时间, 如果能赶上的话, 继续生成 ID, 如果一直没有赶上达到某个值得话, 那么就报错处理. 因为中间 10 位是表示不同的节点, 那么不同的节点生成的 ID 就不会存在递增的情况.
这些思路都是某公司已经实现了的, 如果有兴趣继续研究的话, 那么在 GitHub 上搜索下开源的 Leaf 可以直接拿着使用的.
如果有不对的地方, 还望指正.
来源: https://www.cnblogs.com/huangqingshi/p/11255825.html