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

2024-06-07 23:04

本文主要是介绍美团面试:百亿级分片,如何设计基因算法?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

尼恩说在前面

在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,小伙伴实现了 逆天改命

另外,尼恩也给一线企业提供 《DDD 的架构落地》企业内部培训,目前给不少企业做过内部的咨询和培训,效果非常好。

在这里插入图片描述

尼恩技术圣经系列PDF

  • 《NIO圣经:一次穿透NIO、Selector、Epoll底层原理》
  • 《Docker圣经:大白话说Docker底层原理,6W字实现Docker自由》
  • 《K8S学习圣经:大白话说K8S底层原理,14W字实现K8S自由》
  • 《SpringCloud Alibaba 学习圣经,10万字实现SpringCloud 自由》
  • 《大数据HBase学习圣经:一本书实现HBase学习自由》
  • 《大数据Flink学习圣经:一本书实现大数据Flink自由》
  • 《响应式圣经:10W字,实现Spring响应式编程自由》
  • 《Go学习圣经:Go语言实现高并发CRUD业务开发》

……完整版尼恩技术圣经PDF集群,请找尼恩领取

《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》PDF,请到下面公号【技术自由圈】取↓↓↓

这篇关于美团面试:百亿级分片,如何设计基因算法?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1040553

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Python中的可视化设计与UI界面实现

《Python中的可视化设计与UI界面实现》本文介绍了如何使用Python创建用户界面(UI),包括使用Tkinter、PyQt、Kivy等库进行基本窗口、动态图表和动画效果的实现,通过示例代码,展示... 目录从像素到界面:python带你玩转UI设计示例:使用Tkinter创建一个简单的窗口绘图魔法:用

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第