美团面试:百亿级分片,如何设计基因算法?

随笔1个月前发布 阿翔
40 0 0

文章很长,且持续更新,建议收藏起来,慢慢读!疯狂创客圈总目录 博客园版 为您奉上珍贵的学习资源 :

免费赠送 :《尼恩Java面试宝典》 持续更新+ 史上最全 + 面试必备 2000页+ 面试必备 + 大厂必备 +涨薪必备
免费赠送 :《尼恩技术圣经+高并发系列PDF》 ,帮你 实现技术自由,完成职业升级, 薪酬猛涨!加尼恩免费领
免费赠送 经典图书:《Java高并发核心编程(卷1)加强版》 面试必备 + 大厂必备 +涨薪必备 加尼恩免费领
免费赠送 经典图书:《Java高并发核心编程(卷2)加强版》 面试必备 + 大厂必备 +涨薪必备 加尼恩免费领
免费赠送 经典图书:《Java高并发核心编程(卷3)加强版》 面试必备 + 大厂必备 +涨薪必备 加尼恩免费领

免费赠送 资源宝库: Java 必备 百度网盘资源大合集 价值>10000元 加尼恩领取


美团面试:百亿级分片,如何设计基因算法?

尼恩特别说明: 尼恩的文章,都会在 《技术自由圈》 公号 发布, 并且维护最新版本。 如果发现图片 不可见, 请去 《技术自由圈》 公号 查找

尼恩说在前面

在40岁老架构师 尼恩的读者交流群(50+)中,最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格,遇到很多很重要的架构类/设计类的场景题:

1.说说分库分表的基因算法?

2.大厂常用的基因算法,是如何设计的?

3.百亿级分片,如何设计基因算法?

最近有小伙伴在面试美团,又遇到这一个问题。小伙伴支支吾吾的说了几句,卒。

所以,尼恩给大家做一下系统化、体系化的梳理,使得大家内力猛增,可以充分展示一下大家雄厚的 “技术肌肉”,让面试官爱到 “不能自已、口水直流”,然后实现”offer直提”。

当然,这道面试题,以及参考答案,也会收入咱们的 《尼恩Java面试宝典PDF》V171版本,供后面的小伙伴参考,提升大家的 3高 架构、设计、开发水平。

最新《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF,请关注本公众号【技术自由圈】获取,回复:领电子书

分库分表背景知识

问题1:为什么分库分表?

大家都知道,当一个表(比如订单表) 达到500万条或2GB时,需要考虑水平分表。

为啥? 读写并发高场景,单服务器单一数据库CPU、内存、网络IO压力大。

所以,需要分库,一个库拆成多个库。

同时,数据量大,单表存不下,需要分表,一张表拆分成多个表。

总之,分库分表的原因是:

数据量大,选分表;

并发高,选分库;

海量存储+高并发,分库+分表。

具体实操,请参考尼恩的硬核架构视频

问题2:如何做数据库水平拆分?

分库和分表, 主要还是 对数据的水平拆分,对数据的垂直拆分的重要程度弱太多,所以这个不做介绍。

水平分片又称为横向拆分。

相对于垂直分片,它不再将数据根据业务逻辑分类,而是通过某个字段(或某几个字段),根据某种规则将数据分散至多个库或表中,每个分片仅包含数据的一部分。

例如:根据主键分片,偶数主键的记录放入0库(或表),奇数主键的记录放入1库(或表),如下图所示。

美团面试:百亿级分片,如何设计基因算法?

水平分片从理论上突破了单机数据量处理的瓶颈,并且扩展相对自由,是数据分片的标准解决方案。

对数据的水平拆分 ,核心的设计是:

1: 用哪个字段拆分表,
2: 用什么路由策略寻找目标库表。

分片键的设计目标、建议

数据库水平拆分的字段叫分片键。分片键也称为 Sharding key

关于分片键的选择,我们需要选择具有共性的字段是最基本的要求,也是就尽量能覆盖绝大多数查询场景。

同时分片键也应具有足够庞大的基数以及唯一性,从而使 Shard 可灵活规划,具备较好的扩展性。

举个反例,如果选取布尔类型的字段为分片键,那么分片最多只能存在两份,这就陷入了非常尴尬的局面,基本失去了 Sharding 的意义。

如何做 Sharding key的设计呢?

最常见的情况是:用表的单个字段做分片键,

复杂情况是:可以用两个或多个字段组合成分片键。

Sharding key的设计目标:

合理选择 Sharding key,避免大多数的查询变成重量级操作,比如:

跨库查询
全表路由

40岁老架构师尼恩的建议是:

合理选择 Sharding key, 尽一切可能减少 全表路由、跨库查询,
从而使得大部分查询在 单库实现结果闭环,从而减少 多库之间大的数据合并和二次排序, 从而提升分库分表的吞吐量和性能。

分片键的设计建议:

选择具有共性的字段作为分片键,即查询中高频出现的条件字段;
分片字段应具有高度离散的特点,分片键的内容不能被更新;
可均匀各分片的数据存储和读写压力,避免片内出现热点数据;
尽量减少单次查询所涉及的分片数量,降低数据库压力;
最后,不要更换分片键,更换分片键需重分布数据,代价较大。

分片键的设计原则

选择查询频率最高的字段

分片键要能覆盖绝大多数查询场景,它决定了数据查询的效率。

正例:单号,id,时间字段

反例:姓别、商品类别

分片键不可以更新

分片键如果更新了,按原来的路由算法会计算出不同的库表地址,旧的数据无法正确读取

分片键不可以更换

分片键更换,意味着数据要重新分布,代价昂贵。

分片字段应有离散特性

分片键越离散,越容易把数据均匀分布在不同库表。

分片键的设计方案

按分片键的查询可以直接定位到目标库表,那么不按分片键的查询,是否只能遍历所有库表了呢?

举例:

电商领域有用户表和订单表。

订单表按订单号分库分表,

同时订单表有用户id字段。

假如查询某个用户(比如user-id=200)的订单,怎么查呢?

此时,如果无法预知这个用户的数据存在订单的哪个库表,那么,其实就需要走 全表路由, 把请求路由到 这个表的所有的数据分片。

全表路由 具体如下图所示:

美团面试:百亿级分片,如何设计基因算法?

前面讲到,Sharding key的设计目标:

合理选择 Sharding key,避免大多数的查询变成重量级操作,比如:

跨库查询
全表路由

合理选择 Sharding key, 尽一切可能减少 全表路由、跨库查询, 从而使得大部分查询在 单库实现结果闭环,从而减少 多库之间大的数据合并和二次排序, 从而提升分库分表的吞吐量和性能。

如何去掉这里的 全表路由,提升查询效率呢?

针对这种非分片键的查询,有几种设计思路提升查询效率:

1 索引法

索引法的思路是,把非分片键和分片键的映射关系保存起来,

查询数据时,先从这个映射关系查找分片键,再用分片键路由到目标库表。

索引表

额外建一张表保存订单号和用户id的映射关系。

美团面试:百亿级分片,如何设计基因算法?

优点:实现简单

缺点:

查询数据多查一次索引表,性能低。

索引表可能会很大,甚至索引表本身要分表。

缓存映射关系

尼恩的3高架构宇宙中,有一条亘古不变的天条: 性能不够,缓存来凑。

既然索引表性能低,那么 用Redis保存订单号和用户id的映射关系。

美团面试:百亿级分片,如何设计基因算法?

优点:查询速度比索引表快。

缺点:数据量大时,占用大量内存,缓存不断淘汰,命中率低,没有命中缓存还是得查索引表。

无论是用索引表还是用Redis,都无法在大数据量下有效查找分片键。

2 基因法

基因法的思路是,把非分片键到分片键的映射关系内嵌在非分片键字段,嵌入到非分片键的这部分内容就是基因。

基因法是大厂常常使用的方案,

比如,将买家 ID 融入到订单 ID 中,作为订单 ID 后缀。这样,指定买家的所有订单就会与其订单在同一分片内了,如下图所示。

美团面试:百亿级分片,如何设计基因算法?

再具体一点:

假如订单表用订单号%16路由,分16库表。

用户下单生成订单号时,订单号的最后4个bit位,通过位运算,设置为用户id的最后4bit位,那么,订单号的最后4个bit位就是订单号的用户基因。

此情此景,如果在 查询某个用户的订单,就不用全表路由了。

现在是单片路由,直接根据用户id的最后4bit位,路由到订单的目标库表。

美团面试:百亿级分片,如何设计基因算法?

3 基因法的理论基础

如果对一个10进制的数字按10取模,取模的结果只与这个数字最后1位有关:

199%10=9

19999%10=9

1234567899%10=9

同理,按100(10^2)取模,取模的结果只与这个数字最后2位有关:

199%100=99

19999%100=99

1234567899%100=99

同理,一个二进制的数字,按2^n取模,只与这个数字最后n位有关:

例:n=3,2^3=1000

10001111%(1000)=111, 即十进制的143%8=7

10011111%(1000)=111, 即十进制的159%8=7

因此,订单表用订单号%16分库分表,对16(2^4)取模的结果只和二进制订单号的最后4位有关,这4位决定了数据落在哪个库表上。

4 数字类型的分片键设计

假如订单号是雪花算法生成的long类型数字,要在雪花算法的64个bit位中预留4位,用uid的后4位填充。

美团面试:百亿级分片,如何设计基因算法?

5 字符串类型分片键设计

假如订单号是一个字符串,将uid后4bit位转为字符串后拼接在订单号后面即可。

按某个业务规则生成的订单号:ORDER20240101

带有uid基因的订单号:ORDER20240101-0,ORDER20240101-15

美团面试:百亿级分片,如何设计基因算法?

6 基因法的优缺点:

优点:无论按照分片键还是按某个非分片键查数据,都可以直接定位到目标库表,性能比索引法高。

缺点:需要提前规划好库表容量,不方便扩容。

扩展方案设计:多个非分片键的组合查询

基因法解决了单个非分片键的数据查询路由问题,减少了全表路由的出现。

但是,如果有多个非分片键查询,是否要在分片键中融入多个基因呢?

No。

分片键的设计不应过于复杂,况且,即使能融入多个基因,又如何支持多个非分片键组合条件查询呢?

数据库不支持任意字段任意组合的高性能查询,这不是数据库的长项,应该用ES、ClickHouse等其他中间件来解决这类问题。

具体方案,请参见尼恩的文章:

字节面试:百亿级存储,怎么设计?只是分库分表?

说在最后:有问题找老架构取经

分库分表问题是高频问题,面试的时候如果大家能对答如流,如数家珍,基本上 面试官会被你 震惊到、吸引到。

最终,让面试官爱到 “不能自已、口水直流”。offer, 也就来了。

在面试之前,建议大家系统化的刷一波 5000页《尼恩Java面试宝典》V174,在刷题过程中,如果有啥问题,大家可以来 找 40岁老架构师尼恩交流。

另外,如果没有面试机会,可以找尼恩来帮扶、领路。

大龄男的最佳出路是 架构+ 管理
大龄女的最佳出路是 DPM,

美团面试:百亿级分片,如何设计基因算法?

女程序员如何成为DPM,请参见:

DPM (双栖)陪跑,助力小白一步登天,升格 产品经理+研发经理

领跑模式,尼恩已经指导了大量的就业困难的小伙伴上岸。

前段时间,领跑一个40岁+就业困难小伙伴拿到了一个年薪100W的offer,小伙伴实现了 逆天改命

技术自由的实现路径:

实现你的 架构自由:

《吃透8图1模板,人人可以做架构》

《10Wqps评论中台,如何架构?B站是这么做的!!!》

《阿里二面:千万级、亿级数据,如何性能优化? 教科书级 答案来了》

《峰值21WQps、亿级DAU,小游戏《羊了个羊》是怎么架构的?》

《100亿级订单怎么调度,来一个大厂的极品方案》

《2个大厂 100亿级 超大流量 红包 架构方案》

… 更多架构文章,正在添加中

实现你的 响应式 自由:

《响应式圣经:10W字,实现Spring响应式编程自由》

这是老版本 《Flux、Mono、Reactor 实战(史上最全)》

实现你的 spring cloud 自由:

《Spring cloud Alibaba 学习圣经》 PDF

《分库分表 Sharding-JDBC 底层原理、核心实战(史上最全)》

《一文搞定:SpringBoot、SLF4j、Log4j、Logback、Netty之间混乱关系(史上最全)》

实现你的 linux 自由:

《Linux命令大全:2W多字,一次实现Linux自由》

实现你的 网络 自由:

《TCP协议详解 (史上最全)》

《网络三张表:ARP表, MAC表, 路由表,实现你的网络自由!!》

实现你的 分布式锁 自由:

《Redis分布式锁(图解 – 秒懂 – 史上最全)》

《Zookeeper 分布式锁 – 图解 – 秒懂》

实现你的 王者组件 自由:

《队列之王: Disruptor 原理、架构、源码 一文穿透》

《缓存之王:Caffeine 源码、架构、原理(史上最全,10W字 超级长文)》

《缓存之王:Caffeine 的使用(史上最全)》

《Java Agent 探针、字节码增强 ByteBuddy(史上最全)》

实现你的 面试题 自由:

4800页《尼恩Java面试宝典 》 40个专题

免费获取11个技术圣经PDF:

美团面试:百亿级分片,如何设计基因算法?

© 版权声明

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...