首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
NightTeam
V2EX  ›  分享创造

忘掉 Snowflake!感受一下性能高出 587 倍的全局唯一 ID 生成算法

  •  7
     
  •   NightTeam · 39 天前 · 12591 次点击
    这是一个创建于 39 天前的主题,其中的信息可能已经有所发展或是发生改变。

    文章作者:「夜幕团队 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 点属性我觉得很准确,它们是:

    1. 全局唯一性:不能出现重复的 ID 号,既然是唯一标识,这是最基本的要求;
    2. 趋势递增:在 MySQL InnoDB 引擎中使用的是聚集索引,由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能;
    3. 单调递增:保证下一个 ID 一定大于上一个 ID,例如事务版本号、IM 增量消息、排序等特殊需求;
    4. 信息安全:如果 ID 是连续的,恶意用户的爬取工作就非常容易做了,直接按照顺序下载指定 URL 即可;如果是订单号就更危险了,竞争对手可以直接知道我们一天的单量。所以在一些应用场景下,会需要 ID 无规则、不规则。

    看上去第 3 点和第 4 点似乎还存在些许冲突,这个后面再说。除了以上列举的 ID 属性外,基于这个生成算法构建的服务还需要买足高 QPS 、高可用性和低延迟的几个要求。

    业内常见的 ID 生成方式有哪些?

    大家在念书的时候肯定都学过 UUIDGUID,它们生成的值看上去像这样:

    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 条附言  ·  38 天前
    看到大家都很热切讨论这个话题,文章作者自己和团队都很开心。希望大家根据需求场景进行思想交锋,那些为喷而喷和为标题而喷的就不必了,标题起不好也没机会跟大家学习讨论,理智一点。
    156 条回复    2020-07-30 10:23:53 +08:00
    1  2  
    rwx
        101
    rwx   38 天前 via iPhone
    毫秒内的严格递增到底有什么实际意义?就算你能递增的拿号,你能保证递增的使用吗?
    quericy
        102
    quericy   38 天前   ❤️ 2
    评论区一路看下来,楼主的"薄雾"和 Snowflake 本质上还是在 CP 和 AP 间抉择的问题。

    Snowflake 通过时间戳的递增特性实现了不引入单点达到 AP,代价是获取时间戳的性能开销和承担时间回拨的风险;
    "薄雾"通过引入 Redis 来确保"中位"号段全局递增,规避毫秒级时间的冲突和获取开销,代价是引入了新的单点;

    引发质疑的原因除了标题以外,还有 Jmeter 仅仅 5000w 的唯一性测试在缺乏数学论证依据的前提下也说服不了评论区的各位。

    个人感觉更关键在于,楼主的这套方案在分布式系统实际部署中将更加缺乏说服力:
    1,性能瓶颈。举个简单的例子,异地双机房部署的场景下,"薄雾"引入的 redis 单点如何确保对端机房服务的性能表现? Snowflake 只需要做到机器时间对齐,"薄雾"跨机房的网络开销和抖动均会大大拖慢发号性能,网络 IO 的损耗可不是和时间戳获取可不是一个量级的。

    2,可用性。redis 所在机房断网时,异地机房是否还可对外提供服务? Snowflake 的 AP 特性可以在确保时间正确的前提下提供服务,"薄雾"目前的方案依赖 CP 在上述场景下是无法满足可用性的。
    610915518
        103
    610915518   38 天前
    「标题起不好也没机会跟大家学习讨论」

    UC 头条部需要你!
    NightTeam
        104
    NightTeam   38 天前
    下次看完全文再喷哈,闭着眼睛喷是你的习惯吗?
    ------------
    回复 99 楼 @louislivi
    用了 Redis 就会建立 TCP 连接,这效率能比 Snowflake 高?
    NightTeam
        105
    NightTeam   38 天前
    整体中肯,是个好评论。我看大部分矛头都直指“作者思路错误、设计垃圾”,从来没有人看到文章里对另外几个实现方式的描述和欣赏。

    我写篇文章不是要证明我一定对或者谁一定错,大家指出点就可以了,其他人评论里人身攻击要不得。

    1 、要说获取那当然机器上直接读取比通过网络传输来的快。
    2 、Snowflake 做好冗余和负载是可以提供很高效服务的,前提是时间对齐。
    ----------------------
    回复 102 楼 @quericy

    个人感觉更关键在于,楼主的这套方案在分布式系统实际部署中将更加缺乏说服力:
    1,性能瓶颈。举个简单的例子,异地双机房部署的场景下,"薄雾"引入的 redis 单点如何确保对端机房服务的性能表现? Snowflake 只需要做到机器时间对齐,"薄雾"跨机房的网络开销和抖动均会大大拖慢发号性能,网络 IO 的损耗可不是和时间戳获取可不是一个量级的。

    2,可用性。redis 所在机房断网时,异地机房是否还可对外提供服务? Snowflake 的 AP 特性可以在确保时间正确的前提下提供服务,"薄雾"目前的方案依赖 CP 在上述场景下是无法满足可用性的。
    NightTeam
        106
    NightTeam   38 天前
    你这么说,拿号的顺序就不重要了,无可辩驳。
    --------------------
    回复 101 楼 @rwx
    毫秒内的严格递增到底有什么实际意义?就算你能递增的拿号,你能保证递增的使用吗?
    jhdxr
        107
    jhdxr   38 天前
    @NightTeam #75
    > 既然你提到 MD5,那我来提个问题:
    > 1 、MD5 并不是不能破解,业内也有人破解

    你的知识盲区有点多,目前所谓的破解最好情况做到的是在已知明文 A 的情况下可以找到明文 A'满足 md5(A)=md5(A')。
    只给定摘要值,反推明文目前还是做不到的。当然如果你做到了,那就真的顶会随你选了
    constructor
        109
    constructor   38 天前
    好文章,争论地很激烈更是学到不少东西。我想用 Snowflake 生成 MySQL 不可预测的主键 id 看来是合适的。只是单机服务,还有更好的方案吗?
    iyaozhen
        110
    iyaozhen   38 天前
    @NightTeam 机器 ID 用内网 ip 或者机器名转换下就行,可以引入 zk 或者 redis,只是用来做一个启动的时候发号器( docker 场景),这种做法也很常见

    会有低位溢出问题,这个就需要你自己算好,如果机器是预期的的,可以缩小机器 id 使用的位数,再加上评估业务 qps,基本上毫秒内的自增是够用的

    只是 Snowflake 有两个明显缺点:1.趋势递增(非严格递增,这个需要看业务了 2.时间回拨问题(目前简单规避的方法是 sleep,跳过这回拨的几十 ms

    不是说楼主这个有什么致命的问题,自己业务用也没啥问题。但要是把这个东西拿出来说(分享),反正在我们公司要做好被 challenge 的准备
    cassyfar
        111
    cassyfar   38 天前   ❤️ 3
    @NightTeam 我不知道你为什么觉得我是为喷而喷。你们团队一定大牛云集,不然这么啼笑皆非的设计,还心气很高。反驳不了的时候,就扣上“你是喷子”的大帽。
    要我设计,我至少不会加个数据库依赖进去。分布式高 TPS 下,对数据库的写,是非常昂贵且低效的,更何况你这个每一次都要写。当然你说场景只是在帮小学生搭个兴趣网站,那你随便秀,秀上天都行,但请不要贬低 snowflake 来博眼球。
    locoz
        112
    locoz   38 天前
    @cassyfar #111 你说的话确实像为了喷而喷,并且你明显没有好好看别人说的话。给你列一下主要问题:

    1 、你上来第一句就在阴阳怪气地嘲讽,但后面指出的问题确实又并不符合人家所说的实际应用场景,而是以你自己以前的公司的那种场景作为基础在质疑百万、千万 QPS 怎么办。
    这能怎么办?应用场景都不一样啊,人家文章开头就说了是在爬虫的数据处理链路上用,得多大量级的数据才会碰到百万、千万 QPS 还必须硬扛过去的情况?我之前( 19 年左右)在一份报告上看到 360 搜索的爬虫每天爬的页面是 10 亿,均摊下来也就万级 QPS 就够用了。在这种应用场景下说百万、千万 QPS,是要上天?

    2 、人家好好给你举例,问你「你认为怎么做才合适」、「你会怎么设计」的时候你啥都不说;人家文中和回复中都说了的“用了预存预取”你又完全不看,然后你就又开始对数据库操作部分开喷?
    依赖数据库持久化、ID 递增的 ID 生成系统又不是只有他这一个,文章前面提到的美团和腾讯的做法中同样是有数据库 /硬盘 IO 操作和号段预存预取+缓存的机制,你要不顺便把他们也喷一喷?反正在你看来应用场景这种东西是不存在的,只要有数据库依赖就是“垃圾”呢。

    3 、这是个人项目,不是团队项目,代码仓库都是放在个人名下的,文中的描述也是“我”而不是“我们”,他也从来没说过这是团队项目,哪来的“一群”、“你们团队”?

    他标题党当然有问题,主流应用场景有差异的情况下不应拿性能做对比,毕竟没有多大意义,这点不可否认。但你所谓的“心气很高”、“反驳不了就扣帽子”的情况显然是不存在的,这说法放到你身上我觉得倒是挺合适...好好地就事论事不行,非要人身攻击;喷的点有问题还自我感觉良好,人家好好回了又不看,实在🐂🍺。
    locoz
        113
    locoz   38 天前
    @quericy #102 其实就他所说的「在爬虫的数据处理链路上用」这种应用场景而言,异地多机房部署出现的情况概率极低,使用时基本都是单机房下的分布式,瓶颈问题其实没那么严重;而且没有了多机房之后可用性问题也没那么严重了,所以问题也不大。不过对于后端的大部分服务而言,薄雾这东西可能确实没多大的必要使用,毕竟应用场景差异太大。
    byte10
        114
    byte10   37 天前 via Android
    Mongodb 的 objectid 不行??而且还说要入库才能生成。你完全张口就来啊。
    byte10
        115
    byte10   37 天前 via Android
    @cassyfar 嗯,现在猪头很多,还说 mongodb 的 objectid 不合适,我的妈呀,这太菜了
    D3EP
        116
    D3EP   37 天前
    @locoz Snowflake 不够快吗?得是多大的业务量需要千万 QPS ?而且 Snowflake 的可用性不知道高到哪里去了。你猜是时间回退的几率大,还是单台机器故障的几率大?
    locoz
        117
    locoz   37 天前 via Android
    @D3EP #116 这种东西还是结合实际应用场景看。前面不是也说了吗?
    首先他是在爬虫的数据处理链路上用,这种场景没有千万 QPS 的需求;

    然后 Snowflake 多机使用性能肯定够他用,但是 Snowflake 多机生成 ID 的话又会有机器 ID 的问题,
    做不到严格递增,他想要排除掉这个问题;

    而如果单机部署成这种发号器的话,Snowflake 获取时间戳和末位序号范围过低的设计又可能会导致单机生成 ID 的性能满足不了他的需求;

    结合这种需求想到用递增序号搞不是很正常?

    然后他又会有数据对外展示的情况,考虑到这种情况加个随机数操作一下,让大部分人看不出 ID 怎么来的,也让别人的爬虫没法直接按着递增的 ID 爬自己的数据,这东西不就这么出来了?

    至于实际部署时的可用性问题,微信那个不是就给出了个很合适的做法吗?直接做个主备不就完事了?反正单机性能已经完全足够使用了,又哪来的需求会需要将这个发号器也分布式化?爬虫有 IP 就行,跨机房大可不必。

    还是那句话,不要忽略别人说的实际应用场景强行套上自己的需求…
    locoz
        118
    locoz   37 天前 via Android
    @byte10 #114 对于他的需求而言,确实不行…入库才能生成这个倒确实是明显没有了解到位。
    weiqk
        119
    weiqk   37 天前 via Android
    在审慎设计的前提下没什么是自增 id 不能解决的,如果有只能说明系统已经做烂了
    locoz
        120
    locoz   37 天前 via Android
    @byte10 #114 ObjectID 按文档里的说法分新旧两种版本,但两种版本都不适合:
    1 、时间戳+机器 ID+进程 PID+随机数
    做不到严格递增,只能靠时间戳做到趋势递增,完全不适合。
    2 、时间戳+随机数+自增序号
    和他现在这个很像,但随机数在高位,做不到严格递增。而且自增序号只有 3bit 可用空间,比 snowflake 的 12bit 还小,也不适合。

    虽然他并不知道 ObjectID 实际也可以转化为类似的形式,但就实际需求来讲,ObjectID 仍然是不适合的选择。
    byte10
        121
    byte10   37 天前
    Soga,谢谢
    cassyfar
        122
    cassyfar   37 天前
    @locoz 贵司讨论气氛真好,一定要说出你喜欢听到的。你自己数下回答里有几个是不 challenge 的?我只是说话比较直白。很多人已经提到了我想表达的了,是时间回溯出的问题多还是你的数据库依赖出的问题多?

    他哪句话提到了只是给爬虫做得?在原文他只是举了个爬虫的例子。我语文已经差到这田地啦。我也说了,如果只是做某个小应用,你们随便秀。所以你们这不是开始先宣扬秒杀 snowflake,然后感觉不对,说这个只是给爬虫做,无懈可击。

    我再复读下我的理解,你们写了一大堆,最后只做到单主机 service,在工业界就是毫无意义,请不要贬低 snowflake 。

    你迷信美团腾讯,我帮你读一下啊,“强依赖 DB,当 DB 异常时整个系统不可用,属于致命问题。配置主从复制可以尽可能的增加可用性,但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。” 然后你说主从备份就完事了,好一个完事,您是产品经理吗?
    DEVN
        123
    DEVN   36 天前
    其实。
    无论你写出的东西是怎样的。
    别人评论的往往是这个点子和创意是不是原生的。
    如过不是的话自然会有些声音非常刺耳。
    tikazyq
        124
    tikazyq   36 天前
    v2 上大佬太多,被喷正常,我之前发贴各种被喷。
    后来发了一个 github 5k star 的 repo 的帖子,大家都开始支持了😂
    tikazyq
        125
    tikazyq   36 天前   ❤️ 2
    有一些原创的东西放出来发在社区里讨论,本来是好事情,但很多人冥顽不化、固步自封、敝帚自珍,见不得一些新事物,以为自己了解的才是最好的。其实,当你用开放的心态来面对新事物,会进步得更多。

    例如,之前我发了个用 Redis 套壳做 RPC,被很多人吐槽说为什么不用 gRPC 、这方案很奇葩之类的。我一笑了之。不料后来这方案成了我 6k star 开源项目的核心技术之一,而且非常稳定。

    所以啊,当你没有深入了解一门新技术的时候,就要克制自己,多自我批判一下是不是自己的想法太单一了。
    louislivi
        126
    louislivi   36 天前
    @NightTeam 哦哦,看了一下流程图 ,不好意思没仔细看。
    locoz
        127
    locoz   36 天前
    @cassyfar #122 直白跟抬杠是两回事,不要混为一谈谢谢。前面有很多直白的评论,人家没有忽略掉文章中所说的应用场景,而你是完全忽略。

    他文章中没说“只是给爬虫做的”,但他是“面向爬虫场景做的”,能理解这个区别吗?原话写得很清楚:
    “在爬虫场景中,这条数据在进入数据库之前会进行数据清洗、校验、矫正、分析等多个流程,这期间有一定概率发生重试或设为异常等操作,也就是说在进入数据库之前它就需要有一个 ID 来标识它。”

    标题我说了,他确实标题党了,这当然有问题,但是这跟一个东西有没有价值毫无关系。看标题噱头比较大就觉得内容没价值的话,那你怕是会失去很多有一定价值的东西,毕竟标题起不好的文章连火都没机会火。

    “只做到单主机 service”?文章最后那句“至于怎么选择,可根据实际业务场景和需求与架构进行讨论,选择一个适合的方案进行部署即可”你是没看到还是咋的?而且前面举例的美团和腾讯哪个不是按实际应用场景去部署的?不考虑实际应用场景强行套个自己的应用场景抬杠还有理了?

    至于“迷信美团腾讯”就更搞笑了,你说只能这东西只能单机服务,我告诉你美团腾讯也这么搞,有问题?你自己也看到了人家美团知道可能会出问题,但人家还是这么用了,说明什么?嗯?

    任何东西都不可能适用于所有应用场景,就像 Snowflake 在分布式使用的情况下做不到严格递增一样,你拿 Snowflake 往文章中所说的场景上套,一样会得到“毫无意义”这个结论,毕竟连个严格递增都做不到呢 hh 。
    petelin
        128
    petelin   36 天前 via iPhone
    又来 V2EX 找喷了 一 拉黑
    NightTeam
        129
    NightTeam   36 天前
    卧槽,老哥强的一笔
    ----------------
    回复 125 楼 @tikazyq

    有一些原创的东西放出来发在社区里讨论,本来是好事情,但很多人冥顽不化、固步自封、敝帚自珍,见不得一些新事物,以为自己了解的才是最好的。其实,当你用开放的心态来面对新事物,会进步得更多。

    例如,之前我发了个用 Redis 套壳做 RPC,被很多人吐槽说为什么不用 gRPC 、这方案很奇葩之类的。我一笑了之。不料后来这方案成了我 6k star 开源项目的核心技术之一,而且非常稳定。

    所以啊,当你没有深入了解一门新技术的时候,就要克制自己,多自我批判一下是不是自己的想法太单一了。
    NightTeam
        130
    NightTeam   36 天前
    自己测试找到问题了,错在“不可猜测性”,我找时间改改。和部分评论指出的问题一致,原因也相差不多。
    cassyfar
        131
    cassyfar   36 天前
    @locoz 你喜欢硬杠我就陪你。

    面向爬虫做的,原文又是出自哪里,麻烦引用出来的。我只看到了举了个爬虫的例子。

    你是做技术,还是 C 位出道?有价值的东西,标题取得再烂也会被发现,不一定在 v2ex,也会在公司,在业界先被推广。snowflake 是先在 reddit 发个大口号帖子,然后火起来的?浮躁!

    你文章那最后一句话,等于说了什么?方案在哪里?你全篇只说了单机 service 的方案。

    你就继续迷信美团,腾讯呗。你看看你说的这话,有逻辑吗?我知道有这个问题,也不知道怎么解决,但是好像美团在用,应该不是什么大问题。首先不能迷信权威,其次你迷信美团和腾讯至于吗,你让 AWS,GCP 脸往哪搁?

    严格递增真不是什么开天辟地的事,老实讲了,业界应用场景很少有需要严格递增的。不知道你呵呵什么?越看越觉得有意思。
    locoz
        132
    locoz   36 天前 via Android
    @cassyfar #131
    原文前面就给你引用过了,而且我也跟他聊过,就是面向爬虫场景做的。别杠了,没意义。

    ---

    有价值的东西标题再烂也会被发现? V2EX 这个版块下有价值的东西可多了去了,但真的火起来的有多少个?很多有价值的东西帖子下面连评论都没多少、GitHub 上的 star 也没多少,就因为标题起得过于朴素,或者起得让非相关行业人员连意思都看不懂。

    另外再告诉你一个很现实的情况,我之前写的一些被大量爬虫、安全领域的人称之为“入门必看”、“内容清晰”的文章,自己发在知乎上的时候几乎没人看,而一些号主换了个夸张的标题转发到公众号直接就阅读量爆炸了。

    标题起不好,东西很难被更多人看到,这就是现实。不是我浮躁,而是大部分人都浮躁。

    ---

    最后一句话说了什么?说了自己按应用场景选择部署方式,还能说什么?你是觉得别人做个东西分享出来还得给所有人的所有场景都准备好方案呗?人家自己的场景单机就够用了,还要多机做什么?

    迷信?我并不迷信大厂,每个东西的适用场景不同,人家的设计是基于人家的应用场景搞的,并不一定就完全适用于爬虫场景。但人家是用在了核心业务上,人家的架构师总不可能比你菜吧?两个不同公司的核心业务,都选择了这种方案,并且也都用了这么长时间,说明出现的问题完全在可控范围内,借鉴一下当然没问题。

    至于“业界应用场景很少有需要严格递增的”,牛批啊,在你的世界观里很少有需要所以就没价值了?又在忽略一开始说的面向爬虫场景问题,又在用你觉得的应用场景往上套。人家这个场景就是需要严格递增、就是为了解决自己的问题,又不是给你做的东西,是不是开天辟地的东西关你屁事了?这年头开天辟地的东西有几个?你又贡献了几个?

    我说实在的,你觉得没价值、吹破天那你就直接关页面点个拉黑完事了,拿着个自己觉得的应用场景套了半天还感觉良好,人家给你做的东西?

    最后,跟你扯皮太浪费时间了,扯来扯去都意识不到问题的人我觉得没什么必要再说了,走好不送,拉黑拜拜。
    cassyfar
        133
    cassyfar   36 天前
    @locoz 讨论不赢就拉黑 哈哈 理智 那你来 V2EX 是干嘛的呢?这里不适合你这种偏激的喷子。走好不送。
    yeziqing
        134
    yeziqing   35 天前
    @NightTeam 话说这里有些没太看明白薄雾在多机情况下是如何保证顺序的:是每个机子在每次生成 ID 时都需要调用一下 redis,从 redis 拿到一个自增 ID 吗?
    luren123
        135
    luren123   21 天前
    成片再吹,雷声大雨点小,口号造火箭,一看是玩具
    luren123
        136
    luren123   21 天前
    @cassyfar 基本可以说不具有实战价值的 YY 产品
    NightTeam
        137
    NightTeam   19 天前
    @cassyfar #133 自己骂自己可真有意思,您最初在#52 所发表的言论:“纸上谈兵。给我感觉是一群没做过工程的在那玩花活。各种 buzzword,但是一看设计啼笑皆非吧。”,可是刚好适用于您所谓的“偏激的喷子”描述的呢。
    NightTeam
        138
    NightTeam   19 天前
    @yeziqing #134 每个需要获取 ID 的机子会去找发号器取 ID,发号器是中心化的所以就是严格顺序的。
    NightTeam
        139
    NightTeam   19 天前
    @luren123 #135 #136 不要把自己的场景强行套到别人的场景上,这个做法是很可笑的。因为这样做之后,无论什么东西你都只能得出“不具有实战价值”的结论,就像拿刀叉来吃米饭、拿试管来喝水、拿扫把来拖地一样。
    luren123
        140
    luren123   19 天前
    @NightTeam 那就在吹之前好好限定一下自己东西的场景,在限定的场景内再吹。比如我这个是在扫地,且垃圾是塑料的情况下才牛逼。
    yeziqing
        141
    yeziqing   19 天前
    @NightTeam 多谢回答~ 所以可以理解在这种场景下发号器会是一个单点? 也即发号器始终只有一台机子,不过可以有多台不同的机子请求它,获取号码。
    encro
        142
    encro   18 天前
    这种文章,

    我感觉看着看着害人,

    标题 500 倍, 好好的分布式 ID 生成被做成单点,还整段 golang 大数真随机来提高性能。。。

    为了写文章而写文章呢?

    还是作者的真实水平反应?

    标题说要人忘记 snowflake,被质疑又说限定爬虫,根据我做小爬虫的经验也用不上,通常通过 bloom filter 和站点域名来规划的吧,ID 对于爬虫系统来说几乎没用。至于用在订单,订单需要这么长 ID ?
    locoz
        143
    locoz   16 天前
    @luren123 #136
    @encro #138
    不要硬杠,文章开头就提到了“在爬虫场景中,这条数据在进入数据库之前会进行数据清洗、校验、矫正、分析等多个流程,这期间有一定概率发生重试或设为异常等操作,也就是说在进入数据库之前它就需要有一个 ID 来标识它”,已经对场景进行了说明。这种东西也不存在仅限于爬虫场景可以使用而已,所以在一开始就限定场景其实是一种特别蠢的做法,你并不知道别人的其他场景会不会有类似需求可以用到。

    对于一个需要监控、有着多个规范化操作且需要保证严格顺序性的流程来说,为了有个唯一的 ID 用来事后追溯,除了单点的发号器以外你没得选,没得选的核心点在于严格顺序性。如果你写爬虫没有遇到这种场景,那只能说明你的系统庞大程度、爬虫逻辑的复杂程度还没有到需要依靠工具帮你解决问题的情况。
    另外,这个薄雾算法对序号的混淆特性主要体现在 ID 需要对外展示的情况下,如果不需要对外展示,那就单纯一个序号就完事了,并不影响使用。

    ---

    举个比较极端、全面的例子:
    某平台的反爬虫和风控非常恶心人,签名参数的加密算法每次都会变动、代码的混淆方式也每次都会变动,并且对方对 IP ( IP 质量、请求频率等)和设备(设备与 IP 的关联性、设备真实性、请求频率等)也有进行检测,整个流程是关联起来的,缺一不可。
    这种情况下你写一个爬虫就需要有反混淆、提取加密算法、IP 分配、设备分配、IP 设备帐号三者绑定等多个模块,而这些模块都是部分通用的,你不会把他们全集成在一个爬虫程序里,而是分别提供服务。
    那么问题来了,假设某一天你发现有某些数据发生了异常,你怎么查问题?没有全局唯一 ID 的情况下,即使有接入监控也很难查问题,查到吐都不一定能查出来是什么情况导致的;而在有全局唯一 ID 且所有模块都接入了监控的情况下,只需要查这一个 ID 就可以得到整个流程中的所有信息,排查起来会方便很多。

    不要杠什么“这种情况不需要高性能的发号器”,你没有遇到不代表没有;
    也不要杠什么“不会有这么多操作结合的情况”,很多模块是通用的,平台方有没有这么复杂并不影响爬虫方的复杂度;
    更不要杠什么“人家都做了这么多限制你还爬,抓的就是你”,你并不知道人家是不在乎风险还是已经获得了授权,这跟你也没关系。

    说白了,架构设计本身就是充满着妥协的,不结合实际场景来看没有任何意义。Snowflake 、MongoDB 的 ObjectID 这类的算法说白了也就是个时间戳、机器 ID 、序号、随机数之类的东西拼接起来而已,一样很简单粗暴,但这并不影响人家能在特定的场景下起到良好的效果。
    locoz
        144
    locoz   16 天前
    @encro #138 另外,你所说的“通过 bloom filter 和站点域名来规划”跟文中所说的全局唯一 ID 连半毛钱关系都没有...不管是使用场景还是效果都完全不同。
    locoz
        145
    locoz   16 天前
    @yeziqing #137 是啊,就是个单点的东西,如果要避免单点故障就只能舍弃掉 ID 的严格顺序性或者生成性能,没办法的。
    encro
        146
    encro   15 天前
    @locoz

    爬虫通常需要防止重复采集,URL 清洗,动态规划链接时效,
    通常需要通过域名和链接 URL 来查找,
    所以爬虫的 ID 生成也是规则也是基于域名和链接更为理想。
    locoz
        147
    locoz   15 天前
    @encro #142 去重跟 ID 实际上关系并不大,只是说可以用 ID 做去重而已;动态规划链接时效也并不依赖 ID 实现。
    而且你忽略了一点,ID 并不是一定只能有一个,即使是用 ID 做去重也是可以有多个 ID 存在的...另外使用 ID 做去重通常也不会用域名或 URL 做,而是直接对数据内容做一个 Hash,这样去重才能真正起到作用,被吐脏数据之类的也能明显地看出来。
    encro
        148
    encro   15 天前
    @locoz

    对内容做 HASH 和不是 url hash 的用途不一样吧,
    url hash 主要作用是查询 url 是否已被入库,
    content hash 主要是防止重复内容,
    content hash 我感觉如果对方稍微加点东西就失效了。
    locoz
        149
    locoz   15 天前
    @encro #144 一般是双 ID,一个 ID 是对方平台的数据原始 ID 、一个 ID 是用来去重的 Hash,去重依赖第二个,第一个主要用于筛选和清洗。
    稍微加点东西就失效不就体现出这个 ID 的价值了吗?至少你能知道对方什么时候加了东西啊。
    PineappleBeers
        150
    PineappleBeers   15 天前
    虽然外行看不懂,但是觉得评论区很有意思哈哈
    azh7138m
        151
    azh7138m   15 天前   ❤️ 1
    @locoz
    > 得多大量级的数据才会碰到百万、千万 QPS 还必须硬扛过去的情况?

    字节内的 kv 有单机上亿吞吐的设计,感觉大厂内的基础服务应该很容易到这个量级?


    @tikazyq
    > 不料后来这方案成了我 6k star 开源项目的核心技术之一,而且非常稳定

    star 数量和实现的好不好并没有关系。
    antd 的很多实现很扭曲,甚至是反模式的,也不妨碍它有 60k star 。
    locoz
        152
    locoz   15 天前
    @azh7138m #147 你这忽略前半句直接看后半句...?
    “人家文章开头就说了是在爬虫的数据处理链路上用,得多大量级的数据才会碰到百万、千万 QPS 还必须硬扛过去的情况?”
    应用场景不同没有可比性啊。
    hanxiV2EX
        153
    hanxiV2EX   14 天前 via Android
    我以为是那篇旧文章又被置顶了,原来是重新发一次。
    tikazyq
        154
    tikazyq   14 天前
    @azh7138m antd 是非常优秀的框架,因为易用性和稳定性受到欢迎,我的另一个 2k star 项目用的也是 antd 。但可悲的是,目前很多 markdown 项目也有 100k 多的 star,但真正看了深入研究了这些 markdown 项目的有多少,这确实很悲哀,大家都知识焦虑而不自己实践,却在语言框架算法上争得头碰血流、你死我活,企图获取所谓的技术优越感。现在真正静下心来做产品做工具的开发者很少了,我真的感到非常悲哀。

    在这里我只是感慨,在 v2 上有不少人是图嘴上抨击来获取一时快感,真正实践过的报有学习探讨态度的人有多少。不少人自诩为大佬到处指点江山,但在技术贡献上毫无建树。Talk is cheap, show me the code 才是真理好吧
    xrr2016
        155
    xrr2016   13 天前
    不懂就问 Snowflake 和 uuid 啥区别啊?
    tenwx
        156
    tenwx   12 天前
    咋不说 857 倍呢
    1  2  
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1634 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 23:56 · PVG 07:56 · LAX 16:56 · JFK 19:56
    ♥ Do have faith in what you're doing.