忘掉 Snowflake！感受一下性能高出 587 倍的全局唯一 ID 生成算法
NightTeam · 2020-07-03 18:20:27 +08:00 · 21371 次点击这是一个创建于 1603 天前的主题，其中的信息可能已经有所发展或是发生改变。
文章作者：「夜幕团队 NightTeam 」 - 韦世东
润色、校对：「夜幕团队 NightTeam 」 - Loco
本文首发于「 NightTeam 」微信公众号，如需转载请在微信端发消息告知。
今天我们来拆解 Snowflake 算法，同时领略百度、美团、腾讯等大厂在全局唯一 ID 服务方面做的设计，接着根据具体需求设计一款全新的全局唯一 ID 生成算法。这还不够，我们会讨论到全局唯一 ID 服务的分布式 CAP 选择与性能瓶颈。
已经熟悉 Snowflake 的朋友可以先去看大厂的设计和权衡。
百度 UIDGenertor： https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
美团 Leaf： https://tech.meituan.com/2017/04/21/mt-leaf.html
腾讯 Seqsvr： https://www.infoq.cn/article/wechat-serial-number-generator-architecture
全局唯一 ID 是分布式系统和订单类业务系统中重要的基础设施。这里引用美团的描述：
在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯一 ID 来标识一条数据或消息，数据库的自增 ID 显然不能满足需求；特别一点的如订单、骑手、优惠券也都需要有唯一 ID 做标识。
这时候你可能会问：我还是不懂，为什么一定要全局唯一 ID ？
我再列举一个场景，在 MySQL 分库分表的条件下，MySQL 无法做到依次、顺序、交替地生成 ID，这时候要保证数据的顺序，全局唯一 ID 就是一个很好的选择。
在爬虫场景中，这条数据在进入数据库之前会进行数据清洗、校验、矫正、分析等多个流程，这期间有一定概率发生重试或设为异常等操作，也就是说在进入数据库之前它就需要有一个 ID 来标识它。
全局唯一 ID 应当具备什么样的属性，才能够满足上述的场景呢？
美团技术团队列出的 4 点属性我觉得很准确，它们是：
- 全局唯一性：不能出现重复的 ID 号，既然是唯一标识，这是最基本的要求；
- 趋势递增：在 MySQL InnoDB 引擎中使用的是聚集索引，由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能；
- 单调递增：保证下一个 ID 一定大于上一个 ID，例如事务版本号、IM 增量消息、排序等特殊需求；
- 信息安全：如果 ID 是连续的，恶意用户的爬取工作就非常容易做了，直接按照顺序下载指定 URL 即可；如果是订单号就更危险了，竞争对手可以直接知道我们一天的单量。所以在一些应用场景下，会需要 ID 无规则、不规则。
看上去第 3 点和第 4 点似乎还存在些许冲突，这个后面再说。除了以上列举的 ID 属性外，基于这个生成算法构建的服务还需要买足高 QPS 、高可用性和低延迟的几个要求。
业内常见的 ID 生成方式有哪些？
大家在念书的时候肯定都学过 UUID 和 GUID，它们生成的值看上去像这样：
6F9619FF-8B86-D011-B42D-00C04FC964FF
由于不是纯数字组成，这就无法满足趋势递增和单调递增这两个属性，同时在写入时也会降低写入性能。上面提到了数据库自增 ID 无法满足入库前使用和分布式场景下的需求，遂排除。
有人提出了借助 Redis 来实现，例如订单号=日期+当日自增长号，自增长通过 INCR 实现。但这样操作的话又无法满足编号不可猜测需求。
这时候有人提出了 MongoDB 的 ObjectID，不要忘了它生成的 ID 是这样的： 5b6b3171599d6215a8007se0，和 UUID 一样无法满足递增属性，且和 MySQL 一样要入库后才能生成。
难道就没有能打的了吗？
大名鼎鼎的 Snowflake
Twitter 于 2010 年开源了内部团队在用的一款全局唯一 ID 生成算法 Snowflake，翻译过来叫做雪花算法。Snowflake 不借助数据库，可直接由编程语言生成，它通过巧妙的位设计使得 ID 能够满足递增属性，且生成的 ID 并不是依次连续的，能够满足上面提到的全局唯一 ID 的 4 个属性。它连续生成的 3 个 ID 看起来像这样：
563583455628754944
563583466173235200
563583552944996352
Snowflake 以 64 bit 来存储组成 ID 的 4 个部分：
1 、最高位占 1 bit，值固定为 0，以保证生成的 ID 为正数；
2 、中位占 41 bit，值为毫秒级时间戳；
3 、中下位占 10 bit，值为工作机器的 ID，值的上限为 1024 ；
4 、末位占 12 bit，值为当前毫秒内生成的不同 ID，值的上限为 4096 ；
Snowflake 的代码实现网上有很多款，基本上各大语言都能找到实现参考。我之前在做实验的时候在网上找到一份 Golang 的代码实现：
代码可在我的 Gist 查看和下载。
Snowflake 存在的问题
snowflake 不依赖数据库，也不依赖内存存储，随时可生成 ID，这也是它如此受欢迎的原因。但因为它在设计时通过时间戳来避免对内存和数据库的依赖，所以它依赖于服务器的时间。上面我们提到了 Snowflake 的 4 段结构，实际上影响 ID 大小的是较高位的值，由于最高位固定为 0，遂影响 ID 大小的是中位的值，也就是时间戳。
试想，服务器的时间发生了错乱或者回拨，这就直接影响到生成的 ID，有很大概率生成重复的 ID 且一定会打破递增属性。这是一个致命缺点，你想想，支付订单和购买订单的编号重复，这是多么严重的问题！
另外，由于它的中下位和末位 bit 数限制，它每毫秒生成 ID 的上限严重受到限制。由于中位是 41 bit 的毫秒级时间戳，所以从当前起始到 41 bit 耗尽，也只能坚持 70 年。
再有，程序获取操作系统时间会耗费较多时间，相比于随机数和常数来说，性能相差太远，这是制约它生成性能的最大因素。
一线企业如何解决全局唯一 ID 问题
长话短说，我们来看看百度、美团、腾讯（微信）是如何做的。
百度团队开源了 UIDGenerator 算法.
它通过借用未来时间和双 Buffer 来解决时间回拨与生成性能等问题，同时结合 MySQL 进行 ID 分配。这是一种基于 Snowflake 的优化操作，是一个好的选择，你认为这是不是优选呢？
美团团队根据业务场景提出了基于号段思想的 Leaf-Segment 方案和基于 Snowflake 的 Leaf-Snowflake 方案.
出现两种方案的原因是 Leaf-Segment 并没有满足安全属性要求，容易被猜测，无法用在对外开放的场景（如订单）。Leaf-Snowflake 通过文件系统缓存降低了对 ZooKeeper 的依赖，同时通过对时间的比对和警报来应对 Snowflake 的时间回拨问题。这两种都是一个好的选择，你认为这是不是优选呢？
微信团队业务特殊，它有一个用 ID 来标记消息的顺序的场景，用来确保我们收到的消息就是有序的。在这里不是全局唯一 ID，而是单个用户全局唯一 ID，只需要保证这个用户发送的消息的 ID 是递增即可。
这个项目叫做 Seqsvr，它并没有依赖时间，而是通过自增数和号段来解决生成问题的。这是一个好的选择，你认为这是不是优选呢？
性能高出 Snowflake 587 倍的算法是如何设计的？
在了解 Snowflake 的优缺点、阅读了百度 UIDGenertor 、美团 Leaf 和腾讯微信 Seqsvr 的设计后，我希望设计出一款能够满足全局唯一 ID 4 个属性且性能更高、使用期限更长、不受单位时间限制、不依赖时间的全局唯一 ID 生成算法。
这看起来很简单，但吸收所学知识、设计、实践和性能优化占用了我 4 个周末的时间。在我看来，这个算法的设计过程就像是液态的水转换为气状的雾一样，遂我给这个算法取名为薄雾（ Mist ）算法。接下来我们来看看薄雾算法是如何设计和实现的。
位数是影响 ID 数值上限的主要因素，Snowflake 中下位和末位的 bit 数限制了单位时间内生成 ID 的上限，要解决这个两个问题，就必须重新设计 ID 的组成。
抛开中位，我们先看看中下位和末位的设计。中下位的 10 bit 的值其实是机器编号，末位 12 bit 的值其实是单位时间（同一毫秒）内生成的 ID 序列号，表达的是这毫秒生成的第 5 个或第 150 个 数值，同时二者的组合使得 ID 的值变幻莫测，满足了安全属性。实际上并不需要记录机器编号，也可以不用管它到底是单位时间内生成的第几个数值，安全属性我们可以通过多组随机数组合的方式实现，随着数字的递增和随机数的变幻，通过 ID 猜顺序的难度是很高的。
最高位固定是 0，不需要对它进行改动。我们来看看至关重要的中位，Snowflake 的中位是毫秒级时间戳，既然不打算依赖时间，那么肯定也不会用时间戳，用什么呢？我选择自增数 1,2,3,4,5,...。中位决定了生成 ID 的上限和使用期限，如果沿用 41 bit，那么上限跟用时间戳的上限相差无几，经过计算后我选择采用与 Snowflake 的不同的分段：
缩减中下位和末位的 bit 数，增加中位的 bit 数，这样就可以拥有更高的上限和使用年限，那上限和年限现在是多久呢？中位数值的上限计算公式为 int64(1<<47 - 1)，计算结果为 140737488355327 。百万亿级的数值，假设每天消耗 10 亿 ID，薄雾算法能用 385+ 年，几辈子都用不完。
中下位和末位都是 8 bit，数值上限是 255，即开闭区间是 [0, 255]。这两段如果用随机数进行填充，对应的组合方式有 256 * 256 种，且每次都会变化，猜测难度相当高。由于不像 Snowflake 那样需要计算末位的序列号，遂薄雾算法的代码并不长，具体代码可在我的 GitHub 仓库找到：
聊聊性能问题，获取时间戳是比较耗费性能的，不获取时间戳速度当然快了，那 500+ 倍是如何得来的呢？以 Golang 为例（我用 Golang 做过实验），Golang 随机数有三种生成方式：
- 基于固定数值种子的随机数；
- 将会变换的时间戳作为种子的随机数；
- 大数真随机；
基于固定数值种子的随机数每次生成的值都是一样的，是伪随机，不可用在此处。将时间戳作为种子以生成随机数是目前 Golang 开发者的主流做法，实测性能约为 8800 ns/op 。
大数真随机知道的人比较少，实测性能 335ns/op，由此可见性能相差近 30 倍。大数真随机也有一定的损耗，如果想要将性能提升到顶点，只需要将中下位和末位的随机数换成常数即可，常数实测性能 15ns/op，是时间戳种子随机数的 587 倍。
要注意的是，将常数放到中下位和末位的性能是很高，但是猜测难度也相应下降。
薄雾算法的依赖问题
薄雾算法为了避开时间依赖，不得不依赖存储，中位自增的数值只能在内存中存活，遂需要依赖存储将自增数值存储起来，避免因为宕机或程序异常造成重复 ID 的事故。
看起来是这样，但它真的是依赖存储吗？
你想想，这么重要的服务必定要求高可用，无论你用 Twitter 还是百度或者美团、腾讯微信的解决方案，在架构上一定都是高可用的，高可用一定需要存储。在这样的背景下，薄雾算法的依赖其实并不是额外的依赖，而是可以与架构完全融合到一起的设计。
薄雾算法和 Redis 的结合
既然提出了薄雾算法，怎么能不提供真实可用的工程实践呢？在编写完薄雾算法之后，我就开始了工程实践的工作，将薄雾算法与 KV 存储结合到一起，提供全局唯一 ID 生成服务。这里我选择了较为熟悉的 Redis，Mist 与 Redis 的结合，我为这个项目取的名字为 Medis 。
性能高并不是编造出来的，我们看看它 Jemeter 压测参数和结果：
以上是 Medis README 中给出的性能测试截图，在大基数条件下的性能约为 2.5w/sec 。这么高的性能除了薄雾算法本身高性能之外，Medis 的设计也作出了很大贡献：
- 使用 Channel 作为数据缓存，这个操作使得发号服务性能提升了 7 倍；
- 采用预存预取的策略保证 Channel 在大多数情况下都有值，从而能够迅速响应客户端发来的请求；
- 用 Gorouting 去执行耗费时间的预存预取操作，不会影响对客户端请求的响应；
- 采用 Lrange Ltrim 组合从 Redis 中批量取值，这比循环单次读取或者管道批量读取的效率更高；
- 写入 Redis 时采用管道批量写入，效率比循环单次写入更高；
- Seqence 值的计算在预存前进行，这样就不会耽误对客户端请求的响应，虽然薄雾算法的性能是纳秒级别，但并发高的时候也造成一些性能损耗，放在预存时计算显然更香；
- 得益于 Golang Echo 框架和 Golang 本身的高性能，整套流程下来我很满意，如果要追求极致性能，我推荐大家试试 Rust ；
Medis 服务启动流程和接口访问流程图下所示：
感兴趣的朋友可以下载体验一下，启动 Medis 根目录的 server.go 后，访问 http://localhost:1558/sequence 便能拿到全局唯一 ID 。
高可用架构和分布式性能
分布式 CAP （一致性、可用性、分区容错性）已成定局，这类服务通常追求的是可用性架构（ AP ）。由于设计中采用了预存预取，且要保持整体顺序递增，遂单机提供访问是优选，即分布式架构下的性能上限就是提供服务的那台主机的单机性能。
你想要实现分布式多机提供服务？
这样的需求要改动 Medis 的逻辑，同时也需要改动各应用之间的组合关系。如果要实现分布式多机同时提供服务，那么就要废弃 Redis 和 Channel 预存预取机制，接着放弃 Channel 而改用即时生成，这样便可以同时使用多个 Server，但性能的瓶颈就转移到了 KV 存储（这里是 Redis ），性能等同于单机 Redis 的性能。你可以采用 ETCD 或者 Zookeeper 来实现多 KV，但这不是又回到了 CAP 原点了吗？
至于怎么选择，可根据实际业务场景和需求与架构进行讨论，选择一个适合的方案进行部署即可。
领略了 Mist 和 Medis 的风采后，相信你一定会有其他巧妙的想法，欢迎在评论区留言，我们一起交流进步！
夜幕团队成立于 2019 年，团队包括崔庆才（静觅）、周子淇（ Loco ）、陈祥安（ CXA ）、唐轶飞（大鱼｜ BruceDone ）、冯威（妄为）、蔡晋（悦来客栈的老板）、戴煌金（咸鱼）、张冶青（ MarvinZ ）、韦世东（ Asyncins ｜奎因）和文安哲（ sml2h3 ）。
涉猎的编程语言包括但不限于 Python 、Rust 、C++、Go，领域涵盖爬虫、深度学习、服务研发、逆向工程、软件安全等。团队非正亦非邪，只做认为对的事情，请大家小心。
第 1 条附言 · 2020-07-04 12:57:15 +08:00
看到大家都很热切讨论这个话题，文章作者自己和团队都很开心。希望大家根据需求场景进行思想交锋，那些为喷而喷和为标题而喷的就不必了，标题起不好也没机会跟大家学习讨论，理智一点。
 |
1
optional 2020-07-03 18:29:07 +08:00  4
snowflake 最大的有点就是分布式（除了初始化需要获取 nodeid ），用时间戳保证递增。
如果能接受单机，直接 incr+随机数不就好了吗。 |
 |
2
aec4d 2020-07-03 18:38:06 +08:00 via iPhone 2
符合单调递增特性？用随机数替代了取时间函数就声称 587 倍性能。而且这类东东可能设计考虑根本不是性能问题，天天就想搞个大新闻
|
 |
3
ryd994 2020-07-03 18:39:55 +08:00 via Android 1
“由于不是纯数字组成，这就无法满足趋势递增和单调递增这两个属性”
？？？？？ 看得出这是 16 进制吗？ 16 进制可不可以转换为 2 进制？ uuid1 包含了机器 id 和时间，可以做到每个机器生成的 uuid 单调递增。还有其他算法。 uuid1 的缺点是操作系统的时间精度太低。所以无法保证在大请求量的情况下还能单调递增 这才是 snow flakes 等算法的起源 |
 |
4
Varobjs 2020-07-03 18:40:10 +08:00 via Android 1
直接发招聘不好吗
|
 |
5
iyaozhen 2020-07-03 18:49:28 +08:00 1
Snowflake 的好处是这个 jar 包 每个实例模块都可以引入，还能保证各个节点生成的 id 不重复。
你这个是相当于发号中心了 |
|
6
iyaozhen 2020-07-03 18:51:33 +08:00
你这个严重依赖 redis 很不靠谱，实际使用中 redis 容易出问题
|
 |
7
xupefei 2020-07-03 18:52:52 +08:00 via iPhone 7
587 倍性能？写篇论文发顶会吧，没人敢拒。
|
 |
8
putaozhenhaochi 2020-07-03 18:58:42 +08:00 via Android 1
新式"键盘党"?
|
 |
9
EPr2hh6LADQWqRVH 2020-07-03 19:00:54 +08:00 11
一知半解，过度设计，好大喜功，芝麻大的事就能吹破天。
文章缺组织乏调理没有重点，语文不过关。 优秀的是自信心特别强。 |
|
10
ryd994 2020-07-03 19:04:48 +08:00 via Android 28
算法民科
1.维护分布式全局递增数，同时满足高性能和高可用，非常困难 2. snow flakes 的最后一部分递增就是为了利用单机内部实现原子递增的性能够高。同时保证唯一性。你用 16 位随机数替换，碰撞问题怎么解决？我很怀疑你的算法在高流量的情况下还能保证唯一性 3. 你还注释用真随机就更搞笑了。真随机必须每一个 bit 都来自熵。/dev/random 才是真随机 /dev/urandom 只是含有部分熵的伪随机数。一台没有用户输入的服务器，除非使用硬件熵源，可用的熵非常有限。也就是说真随机几乎无法实现高性能 4. 获取时间戳不一定就很费性能，配合 CPU 内部计数器时间可以做到高性能。 5. 因为 1，你最后选择了单机。你想避免 Redis 单点，结果你自己又成了单点。你有没有实际测试过靠 Redis 维护单调递增，同时由本地服务 /库来计算 ID 的情况？ |
 |
11
scnace 2020-07-03 19:11:30 +08:00 via Android
看了眼评论 哈哈哈哈 兄弟发到知乎不好嘛
|
|
12
ryd994 2020-07-03 19:16:08 +08:00 via Android
算法方面我是外行，但是正经学过一点分布式
如果说错了请见谅 |
 |
13
sunny352787 2020-07-03 19:35:10 +08:00
@ryd994 用随机数后面就不用看了，碰撞概率太高，给 UUID 算个 CRC 碰撞概率还低点
|
 |
14
catror 2020-07-03 19:59:49 +08:00 via Android
简单概括，中位 redis 自增+低位随机数，就是不知道你把低位分两部分算随机数的意义是啥。
方案也不是不行，但是相比 snowflake，redis 和你的 medis 极大的增加了系统的复杂度和维护难度。 |
 |
15
rainmint 2020-07-03 20:04:59 +08:00 via Android
想问下这流程图是用啥软件画的
|
 |
16
ob 2020-07-03 20:35:58 +08:00 via Android
看完之后，我想到一个简单的办法，用时间戳+uuid 的方式组合一个 id，既满足了你上面提到的 4 点，又能很简单的实现，请问这种方式有什么弊端？（空间占用请忽略）接受各种反驳。。
|
 |
17
olOwOlo 2020-07-03 21:01:05 +08:00
MongoDB 的 ObjectId 是递增的，而且这是个本质上和 Snowflake 性质相同的分布式算法，不需要入库即可生成
|
 |
18
serical 2020-07-03 21:20:13 +08:00
请大家小心是什么👻？不会被打吧？
|
 |
19
tommyzhang 2020-07-03 21:32:16 +08:00
我这里有个直接从神界获取唯一算法加持的包 保证每次调用只要传入阿弥陀佛就可以得到全世界唯一 id 每秒可以生成一百万个唯一 id 少侠你看可否一试？
|
 |
20
NightTeam OP 大家好，看到大家对这个的讨论挺多的，我们基于各种论点一起交流一下。
Snowflake 的优点是分布式这点没看懂，多机的情况下要解决时间一致性问题哦，而且多机情况下的序列号顺序也是要额外解决的。incr + 随机数可以解决递增的问题，这点同意，那在这样的设计下性能的瓶颈既是 Redis 瓶颈又是程序单机瓶颈。 --------------------- 回复 1 楼 snowflake 最大的有点就是分布式（除了初始化需要获取 nodeid ），用时间戳保证递增。 如果能接受单机，直接 incr+随机数不就好了吗。 |
|
21
NightTeam OP 文中单调递增的描述是“下一个 ID 一定大于上一个 ID”，Medis 和 Mist 的设计使生成的 ID 完全符合单调递增特性。你可能没注意看，587 倍性能并不是随机数取代时间戳生成函数，而是常数取代时间戳生成函数。在实测当中它确实提高了性能，这是 benchmark 测试结果，并不是我凭空想象的。就着性能这个话题，如果不追求性能，要分布式何用？另外，高可用是全局唯一 ID 发号服务的底线，无论分布式还是单机，都需要通过冗余手段保证高可用，同时提供服务能力的机器越多，出问题的几率就越大。
另外一个角度看性能问题，如果 1 台机器的性能能抵 5 台机器的性能，是不是可以从设计方面降低实现和维护成本呢？ ----------- 回复 2 楼 @aec4d 符合单调递增特性？用随机数替代了取时间函数就声称 587 倍性能。而且这类东东可能设计考虑根本不是性能问题，天天就想搞个大新闻 |
|
22
NightTeam OP 全局唯一 ID 就是统一的发号中心，你提到的每个实例模块都引入 jar 包的方式（我不懂 Java，不好乱评价）还能保证各个节点生成的 ID 不重复，那真是太厉害了。但是在我看来，无论是统一还是分散的生成渠道，时间依旧是 Snowflake 的缺点，这是要解决的。
另外，提到 Redis 不靠谱、容易出问题，我猜你平时不用 Redis ？ ---------- 回复 5 、6 楼 @iyaozhen Snowflake 的好处是这个 jar 包 每个实例模块都可以引入，还能保证各个节点生成的 id 不重复。 你这个是相当于发号中心了。 你这个严重依赖 redis 很不靠谱，实际使用中 redis 容易出问题。 |
|
23
NightTeam OP |
 |
24
biu7 2020-07-03 22:10:26 +08:00 1
噢文章作者韦世东？看到这个我就要吐嘈一下他的那本《 Python 3 反爬虫原理与绕过实战》。第二章大量抄官方文档，其他章节极其擅长长话短说与短话长说：花了大量文字来叙述基础环境安装过程，而对于关键部分技术一笔带过。虽说我买这本书也没抱着能学点什么新东西的心态，但是此书质量之低还是惊到我了。
|
 |
25
Mohanson 2020-07-03 22:18:40 +08:00
这种不知所谓的文章居然看完了. 首先佩服作者的勇气, 其次希望作者多看书, 等你大学毕业就会发现你在今天干了一件什么蠢事.
|
|
26
NightTeam OP 1 、维护分布式全局递增函数，同时满足高性能和高可用一点都不困难，困难的是一致性和高可用，业内至今没有办法解决。
2 、Snowflake 的碰撞问题是因为中位用了时间戳，薄雾算法没有用时间戳，所以不会收到单位时间的限制，也不会产生碰撞问题。另外不用担心高流量下的唯一性，Jmeter 5000w 数据测试过了。 3 、真随机数的代码注释是人类主观的注释，是一种泛泛称呼，你要是抬杠的话，我没有什么可以解释的。 4 、获取时间在文中描述的测试代码场景下是比常数耗费时间的，如果能优化那更好。补充一点，在法律领域会采用“一般人”观点，所以我这里描述的获取时间戳耗费性能是相对于常数和随机数的耗费，是一般人观点。 5 、client-server-redis 这样的流程中，必定要经过 server 这一层，预存预取消除的是后面的 Redis 性能影响。后面的那个实测建议原理相同。 ------------------------ 回复 10 楼 @ryd994 内容太多我就不复制了 |
|
27
NightTeam OP 这里跟上面的回答观点一致，不会出现碰撞，遂不用规避
-------------- 回复 13 楼 @sunny352787 用随机数后面就不用看了，碰撞概率太高，给 UUID 算个 CRC 碰撞概率还低点 |
|
28
NightTeam OP 文中提到了中下位和末位是为了防止通过 ID 猜测日订单量。Snowflake 对标的是 Mist 薄雾算法，Medis 对应的是类似美团 Leaf 那样的服务，Snowflake 如果要做成高可用服务，也是需要结合存储和冗余多机的。
----------------- 回复 14 楼 @catror 简单概括，中位 redis 自增+低位随机数，就是不知道你把低位分两部分算随机数的意义是啥。 方案也不是不行，但是相比 snowflake，redis 和你的 medis 极大的增加了系统的复杂度和维护难度。 |
|
29
NightTeam OP |
|
30
NightTeam OP 没让你学到东西真是遗憾，书的好坏主观因素很大，这里我没有什么可以解释的。
------------------ 回复 24 楼 @biu7 噢文章作者韦世东？看到这个我就要吐嘈一下他的那本《 Python 3 反爬虫原理与绕过实战》。第二章大量抄官方文档，其他章节极其擅长长话短说与短话长说：花了大量文字来叙述基础环境安装过程，而对于关键部分技术一笔带过。虽说我买这本书也没抱着能学点什么新东西的心态，但是此书质量之低还是惊到我了。 |
|
31
NightTeam OP 欢迎大家来交流和探讨，大家从不同的角度来看待这个场景与需求，看看思路的交锋能不能碰出新的创意。一些明显灌水的评论和明显抬杠的评论我就不回复了哈。
|
 |
32
ManjusakaL 2020-07-03 22:41:19 +08:00 via Android
@NightTeam 看了下你前面的观点，回复下
1. 真随机数不是抬杠，各个语言的随机数机制的确不一样，他说的没错，如果要保证严格随机，是需要引入硬件熵源，我们之前用过温度传感器来做随机数种子。对于部分语言，随机数种子固定的情况下，ID 可猜 2. Redis 就是不稳定啊，单节点 Redis SLA 实际上没有 MySQL 等传统数据库来的高，常见的利用 Redis 的场合是对数据有一定容忍度的场合，比如缓存等，但是你这个设计中 Redis 的确是一个短板 |
|
33
NightTeam OP 真随机数知识盲区，看到大家说到熵，有空去补充一下。Redis SLA 三个 9 ？
---------------- 回复 32 楼 @ManjusakaL 1. 真随机数不是抬杠，各个语言的随机数机制的确不一样，他说的没错，如果要保证严格随机，是需要引入硬件熵源，我们之前用过温度传感器来做随机数种子。对于部分语言，随机数种子固定的情况下，ID 可猜 2. Redis 就是不稳定啊，单节点 Redis SLA 实际上没有 MySQL 等传统数据库来的高，常见的利用 Redis 的场合是对数据有一定容忍度的场合，比如缓存等，但是你这个设计中 Redis 的确是一个短板 |
 |
34
acerlawson 2020-07-03 23:18:00 +08:00 via iPhone
为啥会快呢…
你拿到号的性能瓶颈是网络 IO，比时间戳慢得多。 持久化的瓶颈是磁盘 IO/Redis，人家不需要这东西。 就算只论发号不考虑拿号，人家怎么就比你慢了？高性能环境下，你自己只能单机 vertical scale 。人家可以线性的 horizontal scale，还没有网络和磁盘的负担。 snowflake 他不香吗？ |
 |
38
ddosakura 2020-07-03 23:32:36 +08:00 via Android
你这个算法啥也没解决啊，对 id 进行>>16，就是单纯的自增了……
|
 |
39
codespots 2020-07-03 23:36:03 +08:00
我不懂算法，对本篇文章看起来也只是一知半解。文章有争议也不是坏事，思想碰撞才能产生火花嘛。关注
|
 |
40
swulling 2020-07-03 23:39:07 +08:00 via iPhone
|
|
41
iyaozhen 2020-07-03 23:39:23 +08:00
@NightTeam “另外，提到 Redis 不靠谱、容易出问题，我猜你平时不用 Redis ？”
我感觉是你没有大规模用过 我说的 redis 不稳定是 redis 这一套链路不稳定，故障的原因很多，单一性不稳定。3 个 9 不是很高，我上层业务要 4 个 9 怎么办？至少得双存储 “你提到的每个实例模块都引入 jar 包的方式（我不懂 Java，不好乱评价）还能保证各个节点生成的 ID 不重复，那真是太厉害了” 不懂 java 没关系呀，就是类似 go import 一个包 你自己也说了“中下位占 10 bit，值为工作机器的 ID，值的上限为 1024” 每个机器 id 不一样 生成的肯定能保证不重复呀 时钟回拨是个问题，但你的做法只是用 redis 来代替本地时间，这个可靠性是降了几个数量级的 |
|
42
optional 2020-07-03 23:42:38 +08:00 4
@NightTeam snowflake 的分布式可以是同机房的分布式，也可以是异地甚至全球的分布式。而且是无网络依赖了，本地就可以生成。 时间问题可以用 GPS 授时（低成本）和原子钟（高成本），至于回拨其实很简单用一个变量记录最后生成事件，回拨就 sleep 就好，因为回拨是个低频的事情，所以偶尔的低性能也能接受。
但是你用 id 服务器后，基本就只能限制在一定范围了，而且还有单点故障。 |
|
43
swulling 2020-07-03 23:44:00 +08:00 via iPhone 3
设计算法精神可嘉，但是要设计一个工程上可用的系统，纸上谈兵是没有什么卵用的。
举个例子，如果说你从来没应用过百度 uidgenerator 或者美团 leaf 这个规模的 id 生成场景，只是脑补算法意义不大。先不提算法本身的问题，就工程上没有实践就没有发言权。 |
 |
44
renyijiu 2020-07-04 00:08:34 +08:00
先不说所谓算法性能倍数问题，从你的工程实践来说，哪里能够体现出你的 587 倍的优势呢？
|
 |
45
locoz 2020-07-04 00:12:44 +08:00 via Android 1
本回复与主题无关，非当事人可以直接跳过。
--- @biu7 #24 你这评价低到让我有点匪夷所思…跟我在第一次看这书内容的时候得到的印象完全不同，于是我刚刚花了二十分钟又大致翻了一下。 第一、二章都是基本操作，内容已经很简单粗暴了，都是些会用到的部分。如果这叫大量抄官方文档的话，那动物园的《 Python 学习手册》、《 Python Cookbook 》这种书就可以称之为全篇抄官方文档了； 然后其他章节基本就是基础知识+引导思路的话语+核心的反爬思路或解决思路。这些地方哪来的关键部分技术一笔带过？明明都是讲的思路，本身就没跟你讲什么技术。 我猜你可能是觉得书里直接给你鼠标轨迹生成算法之类的才叫“讲了关键技术”、才能让你感觉“学到了新东西”？ 不过这种写法对于有一定知识量的人来说感觉“废话多”、“半天讲不到关键点”是很正常的，我这翻了二十分钟已经开始感觉困了，甚至感觉基本操作太多了。但这并不能说明书的质量低，只是因为我的知识量已经覆盖掉这本书的内容而已。 换到你身上，你觉得没什么内容、质量低同样说明不了什么问题。这或许只是因为你弄的东西比较多了所以知识量早已覆盖这些内容，又或许你本身就不是这本书的目标群体，仅此而已。 另外，讲得详细、各种相关资料都贴上是为了能让更多没有相关基础知识的人看懂，引导思路的“废话”多是为了能让没有掌握逆向思维的人慢慢养成逆向思维，这些做法都是很正常的，我写文章的时候也会这样。 每个人的知识量、思维方式、学习能力都不同，甚至是连自己找资料的能力都不同，想要将知识传播给更多人就应该这么做。连最“菜”的人都能看懂的东西，其他人就更加没问题了。 话说这本书从目录上不是就能很清楚地看出是本基础向的书吗？既然你有一定水平又自己感觉不会学到什么东西，那你为什么要买…就很奇怪。 |
 |
46
oneisall8955 2020-07-04 00:22:30 +08:00 via Android
我的理解是通过增加中位长度，并且一定的手段如 redis 获取自增值，来规避雪花基于时间会回拨导致重复或不单调自增的弊端，达到随机和单调。本质上和雪花算法是一样的，只是获取雪花基于机器时间存在弊端，你采取的依赖 redis 自增，使得单调递增控制在自己手里。好处显而易见，弊端大家也懂，依赖外部服务，增加网络 IO 时间（存在 buffer 发号且 client 和 Server 都在内网其实 IO 时间可以忽略吧），有舍有得。另外，大家没必要互相喷吧，作者提供一个思路而已。可能文中写的很自信，这里看不惯别人不谦虚吧。（吐槽下文末请大家小心是什么鬼，辣眼睛）
|
 |
47
misaka19000 2020-07-04 00:25:49 +08:00
楼主这个算法用在多大规模的系统中的？在线上跑了多长时间了？
|
 |
48
Deepseafish 2020-07-04 00:48:52 +08:00
「大家在念书的时候肯定都学过 UUID 和 GUID，它们生成的值看上去像这样：
6F9619FF-8B86-D011-B42D-00C04FC964FF 由于不是纯数字组成，这就无法满足趋势递增和单调递增这两个属性，同时在写入时也会降低写入性能。」 楼主能解释下这段话吗，因果关系是这样的？ |
|
49
Deepseafish 2020-07-04 01:11:32 +08:00
「如果想要将性能提升到顶点，只需要将中下位和末位的随机数换成常数即可，常数实测性能 15ns/op，是时间戳种子随机数的 587 倍。」
原来 587 倍是这么来的，把自己算法中的随机数换成常数，然后和再和自己使用随机数的算法比较。这个标题起的实在是高。 |
|
50
ryd994 2020-07-04 02:48:02 +08:00
@NightTeam #10
"Snowflake 的碰撞问题是因为中位用了时间戳，薄雾算法没有用时间戳，所以不会收到单位时间的限制，也不会产生碰撞问题。另外不用担心高流量下的唯一性，Jmeter 5000w 数据测试过了。" 要保证没有碰撞只有维护某个状态或者维护某种单调递增性。你测试没遇到不代表它不可能发生。 你没有遇到碰撞不排除是占了伪随机数算法的便宜。 我就问你两个独立生成的随机数可不可能有碰撞？这是一个数学问题。 @oneisall8955 喷的是标题党和自大。每个算法都有其适用范围。他这个算法和 snowflakes 解决的完全不是一个问题，去比较性能有什么意义呢？而且，还实现错了。 |
|
51
ryd994 2020-07-04 03:01:42 +08:00
@NightTeam #26
我更倾向于认为是你的实现的性能太低，是时间戳而不是随机数保证了不重复 snowflakes 设计时就指出了依赖时间戳保证唯一性的问题：如果在小于时间戳精度的时间内快速反复生成 ID，就有可能发生碰撞。机器 ID 就是为了规避这个情况。因为单机下维护一致性容易多了。 你倒好，把机器 ID 去掉了。在大规模使用时几乎可以保证会发生碰撞。 |
 |
52
cassyfar 2020-07-04 03:45:44 +08:00 5
纸上谈兵。给我感觉是一群没做过工程的在那玩花活。各种 buzzword，但是一看设计啼笑皆非吧。
自增算法在多分布情况下怎么解决一致性？别告诉我你要用一台机器撑起百万，千万 QPS 吧。 解决一致性我能想到实际的就是锁，但是多线程性能降低不厉害？ 另外存储的运维不严重？性能依赖不过分？我以前的公司做千万 QPS 的 auth，要依赖数据库。工业界没有数据库能达到期望的 availability，只有自己花了 3 年，30 人团队开发了一个。你用一个 reddis，我真的打扰了。 最后的最后，你可能不知道工业界系统设计原则之一，keep it simple 。这不是炫技。 |
 |
54
codingadog 2020-07-04 07:18:56 +08:00 via Android
uuid 是纯数字，当字符串处理的都是异端。
后面就不想看了。 |
 |
55
hpeng 2020-07-04 08:36:22 +08:00 via iPhone
你们网络情况还是太简单了，居然依赖 redis，这不是自找苦吃么，还高可用呢
|
 |
56
jinliming2 2020-07-04 08:39:38 +08:00 via iPhone 1
> 信息安全：如果 ID 是连续的，恶意用户的爬取工作就非常容易做了，直接按照顺序下载指定 URL 即可；如果是订单号就更危险了，竞争对手可以直接知道我们一天的单量。所以在一些应用场景下，会需要 ID 无规则、不规则。
这里说订单号必须 ID 无规则，不然会被竞争对手直接知道一天的单量。 那么我问个问题，你这个算法怎么保证信息安全？因为你中间使用的是自增 id，所以我只需要把中间那个自增 id 取出来，然后每天减一下，就能知道你一天生成了多少 id ？ 中间用时间戳好理解，数值变化一天固定就是变一天的时间戳。但自增 id ？ |
 |
57
rrfeng 2020-07-04 09:32:44 +08:00 via Android
这就叫做一本正经的胡说八道。功夫多下在研究算法原理上，不要老想着搞大事做表面文章。
|
 |
58
sujin190 2020-07-04 10:41:29 +08:00
错漏百出，这都敢出来胡说八道，真行
首先 mongo 的 ObjectId 是本机生成的，谁说要写入库才有的，而且是单调递增的 分布式 ID 的首先需求是区分不同进程不同机器，不同机房，好嘛，直接把时间 bit 数加上去了，区分机器进程能力完全丧失，而且实际使用过程中，生成时间并不是平均的，有可能其中一毫秒内生成了几万几十万接下来好几小时都不用了，单毫秒内计数单字节，作死啊 Snowflake 需要手动配置集群机器进程 ID 作为一个分布式专用唯一 ID 生成算法就已经很不方便了，完全让一个微服务分布式系统无状态依赖变成了有状态依赖，而且是一个非常重要的依赖，作死啊，但是算法限制字节数 8 字节确实没用更好方法，但事实上强行限制字节完全没啥意义，多增加的成本并没有多少，但是一个完全无状态依赖又安全的分布式算法对于微服务分布式系统的意义就大多了，不知道省了多少事多少心 所以不清楚不知道还是别出来误人子弟瞎 bb 了 |
 |
59
pigmen 2020-07-04 11:26:11 +08:00 via iPhone
这时候有人提出了 MongoDB 的 ObjectID，不要忘了它生成的 ID 是这样的：5b6b3171599d6215a8007se0，和 UUID 一样无法满足递增属性，且和 MySQL 一样要入库后才能生成。
这句话就错了 mongodb 的 id 是递增的， |
 |
60
respect11 2020-07-04 11:28:27 +08:00
收藏评论
|
|
61
NightTeam OP 要是看上下文和应用场景的话，你就会看到列出的需求是什么。
snowflake 是很香，薄雾并不是为了取代它，而是满足相似的需求。单机 snowflake 会有单位时间发号上限且无法给多个客户端使用，多机（多个客户端，每个端一份 snowflake ？）又没办法保证顺序，全局发号中心都是通过网络传输 ID 的，不通过网络难道光用爱传递吗？ 在这样的需求场景下，snowflake 它正是不香，所以才有了 UIDGenerator 和 Leaf-Snowflake -------------- 回复 34 楼 @acerlawson 为啥会快呢… 你拿到号的性能瓶颈是网络 IO，比时间戳慢得多。 持久化的瓶颈是磁盘 IO/Redis，人家不需要这东西。 就算只论发号不考虑拿号，人家怎么就比你慢了？高性能环境下，你自己只能单机 vertical scale 。人家可以线性的 horizontal scale，还没有网络和磁盘的负担。 snowflake 他不香吗？ |
|
62
NightTeam OP |
 |
63
RemRain 2020-07-04 11:55:01 +08:00
从代码看，increasShift 和 saltShift 的值固定是 16 和 8，故意这么设计的，还是写的有 bug ？
如果是故意这么设计的话，等价于 自增数 + 固定长度的随机数后缀？ |
 |
65
zifangsky 2020-07-04 12:01:07 +08:00
一本正经的胡说八道
|
|
66
NightTeam OP 我猜你可能没有仔细看全文，角度刁钻是好事但也限制了你看到的内容。生成的随机数碰撞了又如何？它并不会影响中位数的递增，自然也不会影响整体递增。
薄雾的分段，中位是负责保持递增的、中下位和末位两段是为了提高猜测难度的。snowflake 的末位是单位时间的序列号，它是受到影响的，大哥你可不可以把整个思路看完再找角度讨论。[手动捂脸]🤦♂️ ------------ 回复 51 、52 楼 @ryd994 要保证没有碰撞只有维护某个状态或者维护某种单调递增性。你测试没遇到不代表它不可能发生。 你没有遇到碰撞不排除是占了伪随机数算法的便宜。 我就问你两个独立生成的随机数可不可能有碰撞？这是一个数学问题。 我更倾向于认为是你的实现的性能太低，是时间戳而不是随机数保证了不重复 snowflakes 设计时就指出了依赖时间戳保证唯一性的问题：如果在小于时间戳精度的时间内快速反复生成 ID，就有可能发生碰撞。机器 ID 就是为了规避这个情况。因为单机下维护一致性容易多了。 你倒好，把机器 ID 去掉了。在大规模使用时几乎可以保证会发生碰撞。 |
|
67
NightTeam OP 就需求论事，如果上升到千万 QPS 又要保证 3 个 9 或者更高的 SLA，那高素质团队自研确实才是出路。你们的业务要求系统稳定和高可用，才会有后面的 3 年 30 人自研存储。脱离需求而喷，还夹带 3 年 30 人千万 QPS 这么准确的数据，你莫不是为了喷而来的？
换一个角度说，在目前大部分 KV 都是 3 个 9 以下的情况下，你认为怎么做才更合适？实际上 Redis 只是实现的样例之一，可以把存储换成 MySQL，因为用了预存预取所以换什么存储都不会影响原有效率但是确实可以提高 SLA 。 你从程序设计或者架构的角度给大家讲解一下，如果是你来做，你根据上面描述的需求你会怎么设计？ ---------------- 回复 52 楼 @cassyfar 纸上谈兵。给我感觉是一群没做过工程的在那玩花活。各种 buzzword，但是一看设计啼笑皆非吧。 自增算法在多分布情况下怎么解决一致性？别告诉我你要用一台机器撑起百万，千万 QPS 吧。 解决一致性我能想到实际的就是锁，但是多线程性能降低不厉害？ 另外存储的运维不严重？性能依赖不过分？我以前的公司做千万 QPS 的 auth，要依赖数据库。工业界没有数据库能达到期望的 availability，只有自己花了 3 年，30 人团队开发了一个。你用一个 reddis，我真的打扰了。 最后的最后，你可能不知道工业界系统设计原则之一，keep it simple 。这不是炫技。 |
|
68
RemRain 2020-07-04 12:15:45 +08:00
我看明白了，这算法本质就是给自增 id 拼个随机数后缀，什么高位低位的，只是设置随机数长度是 16 位：
比如我的 id 是 0x33，最终结果可能就是 0x330A0B 。表面上猜不出下一个 id 了，实际由于随机数长度只有 16 位，最多枚举 65536 次就能猜中 这个算法存在单点问题，两台机器如果不借助外存，生成的 id 有很高的碰撞概率。如果已经借助外存获取自增 id 了，直接 md5(id) 不香吗 |
|
69
NightTeam OP 首先阐明一个观点，两个随机数的安全性自然不高，严格按照安全领域的“一般人学说”来说猜测难度确实低。但你不知道位数分段和随机数的情况下，你写个程序来猜？这个随机是为了挡住部分人，不是所有人（复杂如 RSA 也没有挡住所有人）。
另外看到你列觉了时间戳变化和自增 id 的变化，那按照你的观点把中位挑出来做减法，这样来看的话时间戳和自增有区别吗？你都挑出中位来了，那挑出中位和末位一起计算也不是问题了，同一个难度。 ------------------ 回复 56 楼 @jinliming2 那么我问个问题，你这个算法怎么保证信息安全？因为你中间使用的是自增 id，所以我只需要把中间那个自增 id 取出来，然后每天减一下，就能知道你一天生成了多少 id ？ 中间用时间戳好理解，数值变化一天固定就是变一天的时间戳。但自增 id ？ |
|
70
NightTeam OP 我们来看看时间回拨问题，这里提到 sleep，如果它回拨了 5 秒是不是要 sleep 5 秒？如果它回拨了 20 秒甚至更长时间呢？其他要拿号的客户端就会受到很大的影响。
snowflake 的分布式问题，无论你怎么分布，毫秒的上限现在是固定的，如果并发数高是不是就用不了它了？本地，每个机器一个 snowflake 你如何保证末位的序列号不重叠？拿这就到了递增问题和唯一问题这里来了。 要不然你以为干嘛非得搞个发号中心负责发号？ 单点故障可以通过机器冗余来解决，业内都是这么做的，你能找到其他办法那就更好了 ----------------------------- 回复 42 楼 @optional snowflake 的分布式可以是同机房的分布式，也可以是异地甚至全球的分布式。而且是无网络依赖了，本地就可以生成。 时间问题可以用 GPS 授时（低成本）和原子钟（高成本），至于回拨其实很简单用一个变量记录最后生成事件，回拨就 sleep 就好，因为回拨是个低频的事情，所以偶尔的低性能也能接受。 但是你用 id 服务器后，基本就只能限制在一定范围了，而且还有单点故障。 |
 |
71
fwee 2020-07-04 12:26:39 +08:00
老实说 LZ 文章前半段介绍部分写的不错，后面的算法就是我这个分布式外行也能看出来 snowflake 的价值就是（除时钟外）无状态，你把人家优点给改没了。
我也发明个算法，用 128bits 来表示 id，把 snowflake 每个段增大一倍，估计性能吊打你这个不知道多少倍，容我三个月想个好名字。 |
 |
72
danhahaha 2020-07-04 12:27:19 +08:00
忘掉编程，让灭霸告诉你什么叫做随机吧
|
|
73
NightTeam OP 首先说明，标题起不好根本没有机会跟大家交流讨论。再有，snowflake 确实是时间戳，这里用随机数和常数作为测试，是有问题吗？
[手动滑稽] 大家如果盯着 587 不放，忽略了设计的背景需求和应用场景，那就太可惜了 ----------------------- 回复 49 楼 @Deepseafish 原来 587 倍是这么来的，把自己算法中的随机数换成常数，然后和再和自己使用随机数的算法比较。这个标题起的实在是高。 |
|
74
RemRain 2020-07-04 12:29:21 +08:00
大家也不用嘲讽楼主，这个算法看着不高明，确实能解决问题
我这早年有一个项目干过类似的事，也是不想让用户看出自增 id，不过我们的算法更简单粗暴，是这样设计的： id += rand.Intn(100000) 楼主可以考虑换成这个算法，和你的效果完全一致，但是更好理解 |
|
75
NightTeam OP 是的，它的猜测上限就是 256 * 256，我并没有指望通过两段小随机数屏蔽所有人，如果你盯着这个角度，那确实相当刁钻（你猜测完随机数，是不是还得猜测前面的中位？）。
既然你提到 MD5，那我来提个问题： 1 、MD5 并不是不能破解，业内也有人破解 2 、可以自己生成数和 MD5 值进行对比，也能得到结果（和上面的枚举破解方法相同） 3 、你的意思是要追求很高的隐匿性？那我觉得就不能 64 bit 了，可能会 128，然后为了安全性再做很多的尝试和权衡 -------------------- 回复 68 楼 @RemRain 我看明白了，这算法本质就是给自增 id 拼个随机数后缀，什么高位低位的，只是设置随机数长度是 16 位： 比如我的 id 是 0x33，最终结果可能就是 0x330A0B 。表面上猜不出下一个 id 了，实际由于随机数长度只有 16 位，最多枚举 65536 次就能猜中 这个算法存在单点问题，两台机器如果不借助外存，生成的 id 有很高的碰撞概率。如果已经借助外存获取自增 id 了，直接 md5(id) 不香吗 |
|
76
NightTeam OP 讲道理，snowflake 在单机上确实没有什么大问题，就算单机对号的需求不会突破单位时间的上限，但是时间回拨你不考虑？
机器越多，出现的回拨整体概率是不是也就越大？ 你把 snowflake 的长度增大，可以解决单位时间上限问题，那回拨你永远不考虑了吗？拿到重复的 ID 怎么办？拿到不递增的 ID 怎么办？ 按需求场景来说，如果你的需求对 ID 重复和递增情况无所谓，那你的描述确实是可以的。 ------------------ 回复 71 楼 @fwee 老实说 LZ 文章前半段介绍部分写的不错，后面的算法就是我这个分布式外行也能看出来 snowflake 的价值就是（除时钟外）无状态，你把人家优点给改没了。 我也发明个算法，用 128bits 来表示 id，把 snowflake 每个段增大一倍，估计性能吊打你这个不知道多少倍，容我三个月想个好名字 |
|
77
NightTeam OP 先讲道理，分布式环境下以我粗浅的学识还没见过高明的算法（我看到的算法和协议都是为了场景和需求权衡折中，例如 Raft 、NWR 、Paxos ），我已经说明了我学识浅，后面的人就不用抓着这里喷了哈。
用位和分段组合的方式稍稍比你提出这个好一些，但是本质上确是 id + rand 的结构，没错。 ------------------- @RemRain 大家也不用嘲讽楼主，这个算法看着不高明，确实能解决问题 我这早年有一个项目干过类似的事，也是不想让用户看出自增 id，不过我们的算法更简单粗暴，是这样设计的： id += rand.Intn(100000) 楼主可以考虑换成这个算法，和你的效果完全一致，但是更好理解 |
|
78
NightTeam OP 是的，我看这算是为数不多的中肯评论。我看很多人就是为了标题而喷的，来的时候就带着有色眼镜和高期望，结果看到一个很简单且不高明的设计就开始了。
我没有恶意，只是表达自己的观点和看法，也吸收大家给的建议和看法。这次来 V2EX 我觉得讨论氛围很好，大家都很愿意表达自己的看法，排除一部分为喷而喷和灌水的，我觉得一部分人看了文章并且给出了看法和意见，这我就满足了。 -------------- 回复 46 楼 @oneisall8955 我的理解是通过增加中位长度，并且一定的手段如 redis 获取自增值，来规避雪花基于时间会回拨导致重复或不单调自增的弊端，达到随机和单调。本质上和雪花算法是一样的，只是获取雪花基于机器时间存在弊端，你采取的依赖 redis 自增，使得单调递增控制在自己手里。好处显而易见，弊端大家也懂，依赖外部服务，增加网络 IO 时间（存在 buffer 发号且 client 和 Server 都在内网其实 IO 时间可以忽略吧），有舍有得。另外，大家没必要互相喷吧，作者提供一个思路而已。可能文中写的很自信，这里看不惯别人不谦虚吧。（吐槽下文末请大家小心是什么鬼，辣眼睛） |
|
79
RemRain 2020-07-04 12:47:01 +08:00
```位和分段组合的方式稍稍比你提出这个好一些```
@NightTeam 这个观点不能认同，位操作感觉上更高级一点？还是性能更高一些？ |
|
80
NightTeam OP 在目前领域内 KV 基本都是 3 个 9 的情况下，确实是可以切换到其他存储的，这个设计的预存预取就是为了忽略存储性能影响，以便可以切换存储的。
Snowflake 的机器 ID 并不是为了解决重复问题的，时间戳+序列号才是。单机情况下是没有问题，那多机且每台机器都一份 jar 的话，你如何确保同一时间生成的 ID 不重复？且递增？序列号不共享，它自行按照自己的序号来生成，同一时间不同机器生成的 ID 必定是重复且不递增的。和语言无关。 我这里虚心请教一下，提高可用性的话，除了将 KV 换成其他存储，你还能想到其他办法吗？ ---------------------------- 回复 41 楼 @iyaozhen 我感觉是你没有大规模用过 我说的 redis 不稳定是 redis 这一套链路不稳定，故障的原因很多，单一性不稳定。3 个 9 不是很高，我上层业务要 4 个 9 怎么办？至少得双存储 “你提到的每个实例模块都引入 jar 包的方式（我不懂 Java，不好乱评价）还能保证各个节点生成的 ID 不重复，那真是太厉害了” 不懂 java 没关系呀，就是类似 go import 一个包 你自己也说了“中下位占 10 bit，值为工作机器的 ID，值的上限为 1024” 每个机器 id 不一样 生成的肯定能保证不重复呀 时钟回拨是个问题，但你的做法只是用 redis 来代替本地时间，这个可靠性是降了几个数量级的 |
 |
81
so1n 2020-07-04 13:07:41 +08:00 via Android 3
价值:收藏评论
|
 |
82
wdlth 2020-07-04 13:13:07 +08:00
我看 redis 没有用集群的连接方式，是用单机还是靠中间件呢？如果靠中间件的话中间件感觉也有风险。
|
|
83
iyaozhen 2020-07-04 13:37:07 +08:00 1
@NightTeam "它自行按照自己的序号来生成，同一时间不同机器生成的 ID 必定是重复且不递增的" 没啊，机器号不是在系列号的相对高位嘛 即使时间一样、序列号一样 生成的最终 id 也不一样呀 难道我一直用错了？
|
 |
85
daryl 2020-07-04 13:45:10 +08:00
哈哈哈哈，评论才是精华。
|
|
86
acerlawson 2020-07-04 14:02:59 +08:00 via iPhone
@NightTeam
twitter 那个应用场景是 roughly sorted 。 显然，事实就是像你不相信的那样； snowflake 并没有像你一样有“全局发号中心”；每台机子独立跑一个 snowflake，需要 ID 的时候自己按照时间戳生成，就能保证 roughly sorted 。 没有你这个“全局发号中心”这个瓶颈，ID 直接从内存中取而不走网络 IO 。大型数据中心成百上千的机器，全部找一个发号中心还高性能吗，网络不堵吗。相反，snowflake 的并发能力是线性扩张的。 说了这么多，您所谓的 mist 算法就一句话：自增 ID 再套一个 redis 做持久化。 把 redis 这层“薄雾”拨开，就什么也不是了。 |
 |
87
stevenhawking 2020-07-04 14:07:32 +08:00
天下 ID 唯快不破？
依赖 Redis， 再见 👋 |
|
88
optional 2020-07-04 14:08:58 +08:00 via iPhone
@NightTeam 不要假设不存在的场景，回拨主要是因为机器的计时误差，但是不管怎么样回拨 5 秒这样的情况是不存在的。
至于这么毫秒上限，node 数量，无非是在 64bit 的空间里作取舍而已。 如果没有 64bit 的限制 ，扩展到 128bit 这些都不是问题，不过 128 位，uuid 也不错了。 |
|
89
NightTeam OP 不用集中发号，而是每个机器一份 snowflake，你看看它那分段设计，你就知道同一时间生成的 ID 必定是重复的，没有例外。
-------------- 回复 64 楼 @renyijiu 哪里表明 snowflake 多机无法保证顺序？ |
|
90
renyijiu 2020-07-04 14:28:45 +08:00
@NightTeam #89 中下位占 10 bit，值为工作机器的 ID，值的上限为 1024 ；所以每个机器一份 snowflake，机器 ID 是不一样的，同一时间怎么可能重复? 另外算法就是为了分布式设计的，你的修改结果只能应用于全局发号的单点，核心点都已经放弃了
|
|
91
NightTeam OP 哎，怎么还是抓住 Snowflake 机器 ID 这个点在反问呢？做个例子它不香吗？假设 A 、B 两台机器的 ID 为 2 和 1，A 的机器 ID 比 B 的大，你们的意思是 A 上面的 Snowflake 值一定大过 B 的值，因为机器 ID 在高位？？？
针对这个观点，是不是又可以衍生出两个论点： 1 、手动维护机器 ID，如果你要自动分配是不是还得引入 zk 这样的组件？引入是不是还会引发其他问题，增加一些工作量，同时还要确保 id 不会漂移。（ zk 没具体了解过，粗浅认知） 2 、如果末位的数值超过上限，它在位运算的时候就会溢出到高位（当然你不用位运算异或我就没办法了，当我没说），溢出到高位必定导致重复或乱序。 3 、针对第 2 点，我只看过 Golang 的 Snowflake 实现，也就是文中配图的那个实现，如果它的实现出错有问题，那我的第 2 个观点也站不住脚。 4 、当然，可以限制 Snowflake 末位值的长度，限制在 12 bit 内以保证不溢出。那就回到了另一个问题，单位时间的 id 上限。 5 、这只是一个权衡选择，我没有说这个完全可以替代 Snowflake，虽然标题党，但内容没有轻蔑。 |
 |
92
shansing 2020-07-04 15:18:47 +08:00
@NightTeam #75 你提的这三个点可以用 HMAC(SHA256, id, key) 来解决，其中 key 可以设到 256 位。（我只是来看评论的不要喷我，逃）
|
|
93
locoz 2020-07-04 15:47:41 +08:00
|
 |
94
SilentDepth 2020-07-04 16:15:20 +08:00
@NightTeam #91 不对啊？ Snowflake 的机器 ID 低于时间戳 ID 啊？这样不管是哪个机器发的号，在时间尺度上总是递增的。又因为机器 ID 的存在，多机同一时间发的同一批号肯定是不会重复的。
|
 |
95
tairan2006 2020-07-04 16:36:47 +08:00
我还以为楼主写了个新的算法…结果一看依赖 redis，满头问号
|
|
96
locoz 2020-07-04 16:56:26 +08:00
@SilentDepth #94 机器 ID 比末位那个上限是 4096 的序号要高，排序时「机器 ID 更大」的值不就比「机器 ID 小」的值要更大了吗？虽然时间尺度上递增但是满足不了他想要的效果啊。
而且 Snowflake 之所以需要机器 ID 来保证多机同一时间发的同一批号不重复，不就是因为没法统一吗？现在他用一个独立的服务来控制，不就不需要机器 ID 也能保证不重复了吗？ |
 |
97
richardwong 2020-07-04 17:11:45 +08:00
勉强能冲。
|
|
98
SilentDepth 2020-07-04 17:28:56 +08:00
@locoz #96 哦，我明白了，楼主想要的是「严格的顺序递增」。那解决的问题跟 Snowflake 不一样，没法比了。
|
 |
99
louislivi 2020-07-04 17:40:51 +08:00
用了 Redis 就会建立 TCP 连接，这效率能比 Snowflake 高？
|
 |
100
ahu 2020-07-04 17:48:25 +08:00
[Medis]( http://getmedis.com/) 已经哭晕在厕所
 |
Select Language