V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
bronyakaka
V2EX  ›  程序员

讨论下高并发、连续自增的 id 的生成方案

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

    最近玩绝区零,才开服几分钟就生成了上百万 id ,而且是连续递增的( 1->2->3->4 这种),不知道是怎么实现的。

    我能想到的方案:

    1 、redis string incr 递增,redis 本身线程安全,感觉这个方案可行,就是不知道 qps 有没有 1w 。而且引入 redis 可能不太稳定?并发量十万会不会直接打崩或者阻塞(刚开服瞬间我感觉有这个并发量)。

    2 、雪花 id ,这个肯定不是上面游戏生成的方案,因为雪花 id 不是连续的,不过雪花 id 的 qps 非常高

    3 、给 int 整型加锁,原子化操作,并发是安全的,但是这个就不是分布式了,有单点故障问题,而且 qps 也难说

    4 、本地缓存?纯本地内存操作,加个读写锁,不知道性能怎么样,也有单点故障问题。、

    5 、数据库自增主键?性能应该不够吧

    有经验的懂哥能否讲解一下

    33 条回复    2024-07-11 19:06:48 +08:00
    awalkingman
        1
    awalkingman  
       136 天前
    提前生成好,分发只需要查询修改。
    0608516518
        2
    0608516518  
       136 天前
    如果是绝区零这样的成熟游戏与应用,基本可以确认用的是传统 RDMS (如 MySQL )来保存账号。

    不能只想着分配 id ,别忘了还用户资料、昵称、人物数据等等。这些都得有地方存啊。说来说去,还是数据库赛高。

    我不那么相信 “几分钟就生成了上百万 id”,可能是之前预约用户已经分配、初始化好账号了。如果我是该产品的开发,一定会想出削峰填谷的策略。

    退一万步“几分钟的百万次请求”其实也并不算大,3K QPS 情况下,5 分钟就可以生成 100w 个数据了,3K QPS 插入,在 SSD + 较多核服务器 + user 表 sharding 情况下,还是可以扛住的。但这样搞,技术风险大,压力测试也难做。想必还是用预约玩家的数据已经生成好了
    dwu8555
        4
    dwu8555  
       136 天前
    为什么非要自增不可呢
    chendy
        5
    chendy  
       136 天前
    不要小看了跑在高性能 SSD 上的数据库的性能啊
    Ashe007
        6
    Ashe007  
       136 天前 via iPhone
    一、分布式 ID ( MybatisPlus 、Twitter 、美团)
    二、数据库插入行为由 MQ 或线程池异步执行,避免高并发可能造成的 ID 生成问题
    三、有没有好心人捞个 Java 开发
    crackidz
        7
    crackidz  
       136 天前
    @dwu8555 确实没必要,不过楼主的例子,绝区零是自增的而已
    povsister
        8
    povsister  
       136 天前   ❤️ 12
    我猜是中心发号段+预分配。
    不是来一个帐号发一次,而是一个登录服务器会预取一段号码( 1000-几万个),中心发号器只需要一段段分配就行了。

    这也能解释为啥有人就是登录卡了一下,uid 直接上 100 多万了都。。

    高并发系统嘛,无非就是来来回回几个方案,去中心化,批处理,异步队列。核心就是打散 IO 压力。
    Ashe007
        9
    Ashe007  
       136 天前 via iPhone
    @Ashe007 没有看到连续递增的需求,可能需要根据 Twitter 的雪花算法稍微定制下
    cheneydog
        10
    cheneydog  
       136 天前
    @0608516518 #2 楼主,qps 和 tps 是怎么理解的?生成 id 包括请求-生成-返回才算做完,我认为应该用 tps 吧。
    单算 qps 请求性能不完整吧。
    night98
        11
    night98  
       136 天前
    都是提前分发的,不存在一个单点且可靠的高性能自增方案,A 机器领 2000 ,B 机器领 2000 号段就行了,反正最终是肯定会用完的
    laminux29
        12
    laminux29  
       136 天前
    有没有一种可能,这点数据量,什么都不用考虑,机器就能扛下来?

    假设 1 分钟生成一百万个自增 ID ,平均每秒 16666 个自增 ID 。

    Redis benchmark ,https://openbenchmarking.org/test/pts/redis ,i3-8100T ,每秒 123 万个 request 。

    另外自从 SATA-SSD 普及以来,有没有发现,关于数据库性能的讨论,越来越少了? nvme-SSD 普及后,这类讨论几乎绝迹了。原因是,1 块正规的 SATA-SSD ,性能是 HDD 的 100 多倍,甚至 pcie5-nvme 能达到 2 千多倍。

    建议学软件开发的,一定要经常关注硬件性能测试。
    kenvix
        13
    kenvix  
       136 天前
    游戏开服是一件完全可以预估到并发情况的事情,这种情况就直接按照预估去预分配就可以了
    kenvix
        14
    kenvix  
       136 天前   ❤️ 1
    @dwu8555 #4 有没有一种可能楼主是在问《绝区零是如何实现连续自增 ID 的》😅
    luckyrayyy
        15
    luckyrayyy  
       136 天前
    我理解你以为的是:按照请求顺序,严格顺序递增。实际上不一定是这样,可能前一秒注册的比后一秒 ID 大。
    ZZ74
        16
    ZZ74  
       136 天前
    很多框架啊。都是 8 楼说的那样一个服务生成一大堆,客户端每次拿一批。
    0608516518
        17
    0608516518  
       136 天前
    @cheneydog 哦严格来说确实是 TPS 。只不过站在后端视角,一个 API call 一般也就是一个 transaction 。所以 QPS 与 TPS 基本一致。

    当然你可以说强调数据库写入性能时用 TPS ,强调应用服务器处理请求时,使用 QPS
    lyy780808
        18
    lyy780808  
       136 天前
    不是严格递增的话,数据库主键自增性能也是够的,可以多部署几个数据库实例进行分片,然后写一个提前生成 id 的功能应对开服流量。
    cowcomic
        19
    cowcomic  
       136 天前
    通常不会用 redis ,正常的时候没问题,万一出了问题,就是大问题,这个风险不敢赌
    最好就是关系型数据库,通常就是 ID 分段,用个表管理 ID 段(这个表里可以根据预期预设好),每个实例已有段用完了就拿新的,段内自己做自增,万一故障恢复所需要校验的也不多
    这样无法严格保证一定是小先大后(只要一个段不是特别宽,也很难察觉到),但基本能保证连续,没有跳号
    这样缩容扩容也简单,无脑加减机器就行(严格连续的话,减机器是要做处理的)
    zhangk23
        20
    zhangk23  
       136 天前
    不太可能是实时自增,要我做我肯定是号段分配的,根据地区百分比做服务器权重分发

    甚至我缺德一点给预约玩家提前分一个靠前号段的 id (
    wushenlun
        21
    wushenlun  
       135 天前 via Android
    提前生产 1000w 个,如果余额不够 1000w 就补足到 1000w 。新用户来就直接分配,用不着实时生成
    lazyfighter
        22
    lazyfighter  
       135 天前
    5 分钟 1000w , 每秒钟 tps 是 33333 , 假设 16 张表,每秒 2000 ,如果还多 2 个 mysql 实例,每秒 1000 , 还觉得多再拆表*2 , 每秒钟 500
    diagnostics
        23
    diagnostics  
       135 天前
    广告新思路?好几个《绝区零》的帖子了
    y830CAa5nink4rUQ
        24
    y830CAa5nink4rUQ  
       135 天前
    用 MySQL 的话,有内置的顺序 ID 生成器,非常好用:

    SELECT uuid_short() AS id;

    这个内置 ID 生成器性能非常屌,也不用担心 ID 生成器会挂导致所有服务受影响,因为当你数据库都挂了,那么你什么都挂了。

    这个生成器我目前发现唯一的缺点:有部分云厂商的定制化 MySQL 会返回 19 位的数字,刚刚好超出 Java 里 long 的范围(因为 Java 没有 unsigned ,最数字是 9,223,372,036,854,775,807 )。
    chutianyao
        25
    chutianyao  
       135 天前
    1. REDIS 单实例写 ops 扛 1w 毫无压力, 正常 key 分散的情况下 5-6w 应该可以, 但这种热 key 不确定
    2.预计就是实现了一个 id 生成器, jvm 中预先分配号段, 我之前实现过, 这种简单的接口单机扛百万 qps 毫无压力
    sunny352787
        26
    sunny352787  
       135 天前
    我问下啊,是怎么确定的这个 ID 是连续的呢?
    cloudzhou
        27
    cloudzhou  
       135 天前
    kv 支持下(比如 redis 效率已经很高了),需要中间件配合,设计思路如下:

    1. 不是每次 incr 1 ,而是每次 incr step ,比如 +1000 ,那么就有 (X, X + 1000] 这个区间都可使用

    2. step 的计算方式如下,比如设计成最多 T 时间,incr step ,运行中一直调整 step

    3. 初始状态:step 初始化为 1 ,T 举个例子:1s ,变化倍数 rate: 2

    4. 那么,1s 内如果多次 incr step ,那么 step = step * 2 ,让 step 尽量变长,尽量超过 1s

    5. 当 incr step 间隔时间超过 2s ,那么 step = step / 2 ,让 step 尽量变小,尽量靠近 1s

    6. 在 4/5 结合之下,step 将把 qps 接近 1s ,上下徘徊,算法可以微调

    缺点:

    重启的时候,会丢弃一些 id ,这个也可以细节改进,比如把未使用的 id 返回给 redis
    cloudzhou
        28
    cloudzhou  
       135 天前
    另外一种就是选举领号,设置总分片 X (比如 1000 )
    每个进程都注册 zookeeper ,etcd ,所以总进程是可知的,根据进程数量,可以知道每个进程可占据的分片

    那么,假设完美情况 100 个进程,那么每个进程分配 10 个分片([0-10), [10, 20)...)

    占据 0 分片,每次产生 0 ,10 ,20 ,30...
    占据 1 分片,每次产生 1 ,11 ,21 ,31...

    本地保持状态即可,依赖选择竞争分片
    ----

    以上两个算法,id 增长,但是 id 本身不能体现先后顺序。
    skuuhui
        29
    skuuhui  
       135 天前
    最简单的就是提前生成好塞队列。
    另一种类似多台 id 发放器,生成不同片的 id (单数,双数,末尾是 1 ,2,3 的),虽然他们严格上不连续,但在短时间内并发过程中是连续的。
    就算最差的实现方式都可以用逻辑优化。
    esee
        30
    esee  
       135 天前
    就算只用 mysql ,自增 id 5 分钟跑 100 万 完全轻轻松松啊,你自己搭个 mysql 试一下 5 分钟能插入多少就知道了。mysql 的经验在好的硬件面前已经跟不上了,一块 4k 性能好的 ssd 顶 10 个 dba 不是开玩笑。
    keepme
        31
    keepme  
       135 天前
    如果不是非按严格的顺序自增的话,雪花 id 就行了吧,本地直接生成
    PiersSoCool
        32
    PiersSoCool  
       135 天前
    你们是不是低估了 MySQL 的性能,几分钟几百万个请求,算什么垃圾
    kakawa
        33
    kakawa  
       133 天前
    每个公司都有自己的发号器服务吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2396 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 16:08 · PVG 00:08 · LAX 08:08 · JFK 11:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.