​业务开发中你用到了哪些算法（续）？

• 2019 年 12 月 18 日
• 笔记

上次我们一起聊了聊普通 hash 算法在实际中的应用，但是按照一猿小讲的风格，绝不能止于应用，为了能让面试官再喝一壶，还是要稍微升华一下，话不多说，本期的分享正式开始（建议一定要读到最后）。

01. 闷头看代码

一、回首上期，提炼精华。

栗1：假如订单表要分 3 张，首先用当前数据库的时间与某一固定的时间计算出的相差的天数 days；然后用 days % 3 算出当前数据应该放到订单表的下标。

庖丁解牛，解剖栗子。 步骤1：days 是当前时间（key）与某一固定的时间计算出的相差的天数，简化为 days = function(key)； 步骤2：订单表分 3 张，那么订单表的下标 = days % 3； 结论1：int position = function(key) % 3

栗2：假如数据库要分 dbNum 节点，首先用分库依据字段 key 经过 crc32 加工得到值 x；然后用 x % dbNum 算出当前数据落到对应库的下标。

庖丁解牛，解剖栗子。 步骤一：x 是经过 crc32 加工之后的值，简化为 x = function(key)； 步骤二：数据库分 dbNum 节点，那么数据库的下标 = x % dbNum； 结论2：int position = function(key) % dbNum

栗3：假如在 dbNum 个数据库下再分 tableNum 张表，首先用分库依据字段 key 经过 crc32 加工得到值 x；然后用 x % tbaleNum 算出当前数据落到对应表的下标。

庖丁解牛，解剖栗子。 步骤一：x 是经过 crc32 加工之后的值，简化为 x = function(key)； 步骤二：表共分 tableNum 张表，那么当前数据对应表的下标 = x % tableNum； 结论3：int position = function(key) % tableNum

二、抽象共性，沉淀精华。

结论1：int position = function(key) % 3 结论2：int position = function(key) % dbNum 结论3：int position = function(key) % tableNum

通过上述栗子的三个结论，我们很容易得出如下表达式。

long position = function(key) % num

汗颜，一个非常简单的问题，被我讲的那么复杂（实在汗颜）。

三、归根结底、总而言之。

long position = function(key) % num

一定要牢记这个公式，真的很有用呦，后面也会反复用！因为一行简单的表达式，就轻松解决了我们实际应用中分库分表的问题。

02. 低头忆往昔

你有没有经过这样一种场景，在开发、测试环境你开发的 WEB 网站，登录成功后访问其它页面都畅通无阻，但是一旦部署到生产上问题就出现了，网站登录成功后一刷新页面，就会跳转到登录页面让重新登录… … 自己脑补那种闹鬼似的场景吧（有同感的今天一定要点个“在看”）。

估计多数研发人员都遇到过，分析原因无非如下：

分析一：开发、测试环境都是部署一台 WEB 网站服务，登录成功之后，验证其它功能贼啦溜； 分析二：生产环境一般为了屏蔽单点故障，都会部署多份服务，导致请求到一台服务上登录成功后，再请求到另外一台时还是提示未登录，感觉就是见了鬼； 结论：研发人员没有针对 Session 做共享存储，其实也就是没有写到 Redis，也就是说服务端研发人员没有维护 Session 的信息。

但是，这口锅谁来背？其实往往这个时候考虑的不是让谁背锅，而是要快速解决问题，不能让用户拒之于网站千里之外，临时改代码肯定是来不及啦，快而稳的临时解决方式，便是让运维同事在 Nginx 上做一个 ip_hash，而且效果往往会很好。

但是后端研发人员还是需要尽快修复 Bug，因为 ip_hash 的方式不是很推荐使用，另外谨记一点是：研发人员能做的事情，尽量不要依赖外围系统去做。

为什么 ip_hash 能帮我们临时解决会话的问题呢？因为它能够让用户（某 ip）在一段时间内的请求，只请求到固定的某台 WEB 服务器中，这样会话就会保持，就不会再出现网站登录成功之后，再访问其它页面时又重新跳转到登录页面的情况啦。

但是，Nginx 是怎么做到的呢？不妨我们举头望望远方，学学人家是咋实现的。

03.举头望远方

首先下载 nginx-1.17.6 版本的安装包，来个一窥到底（你可以忽略，直接看结果就可以啦）。

下载链接：https://nginx.org/en/download.html?_ga=2.182537958.1901173857.1575548135-854843835.1575548135

其它的细枝末节都可以忽略，主要看圈住的重点，看似很难懂，但是回归本质，把咱们开篇的结论拿来套用一下。

long position = function(key) % num

仔细去看，圈住的两部分不就是在执行 function(key) % num 吗？！只不过算法比我们的稍微复杂了很多，但是目标却是一致的，都是在获取数据应该落地的位置。这里只不过是为了找出用户发起请求的客户端的 IP， 对应的目标机器列表中的序号 p，然后选择出对应的服务器。

到这，估计你会晕菜，不过抽象去看，只要搞懂咱们开篇的那个结论，今晚就可以吃鸡、大吉大利。

举头望远方，远方却流浪，为什么流浪，流浪远方，流浪。铺垫了这么多，是该到升华的时候了。

拿出我们开篇的结论 long position = function(key) % num如果我们把 function(key) 理解成计算 key 的 hash 值（例如咱们用过的 CRC32），然后除以机器的总数（serverListSize），那么总能得出 key 要落到的机器节点下标，进而通过下标得出对应的机器节点 targetServer。

targetServer = serverList[hash(key) % serverList.size]

此时此刻，我们应该想想分布式缓存 memcached 以及上面提到的 Nginx，采用上面的表达式肯定能实现负载，而且很算法很简单。

但是也存在一个致命的问题，如果 server 挂掉或者增加一台节点怎么办呢？serverList.size 就会变化，那 key 对应的机器就要全部变化，如果是缓存，则会导致缓存无法命中，如果是海量数据，岂不是要地崩山摧壮士死？！怎样让影响范围小一点呢，这不就有了一致性 hash。

啥是一致性 hash？说起来其实也很简单。

第一步：先把原来的每一个机器节点鼓捣出 N 个虚拟节点；然后定义一个[0,(2^32)-1]的数值区间； 第二步：接着把机器节点（含虚拟的节点）通过 hash 算法计算出数值，映射到[0,(2^32)-1]的数值区间中（此时脑海中要有一条线，上面铺满了机器节点）； 第三步：然后把请求的 key 通过 hash 算法得到一个数值，然后在 [0,(2^32)-1] 区间中定位一个位置，然后向右找到距离最近的机器节点（此时脑海中依然要有铺满机器节点的那条线）。

啥是 hash环？有些时候面试的时候也会提这个玩意，其实说的还是一致性 hash，为什么这么说呢？因为当请求数据，通过 hash 算法得到一个值，如果这个值超过 2^32-1，则会视为 0，也就是把脑海中的那条 [0,(2^32)-1]的线段首尾相连形成一个环，所以又叫 hash 环。

图片来源于网络，侵之告之删之

一致性 hash 怎么把影响范围降到了更小呢？由于按照上面步骤的设计，即使机器挂了一个机器节点，也只会影响这一台机器上的数据，不会让数据全部受到影响；如果新加一台机器，大部分 key 根据一致性哈希算法定位对应的机器节点都不会发生变化，只有那些计算出的值，离新加节点更近的 key 的数据发生了变化。

升华就到这儿吧，懂就懂了，若不懂就索性把开篇那个结论搞懂，那样也够面试官喝一壶的啦。

04. 远方有希望

今天的分享就到这儿吧，主要想分享闷头看代码、低头忆往昔、举头望远方三点。日常研发要学会闷头看代码，多抽象多思考；事故总结要学会低头忆往昔，多总结多提炼；钻研技术要学会举头望远方，多扩展有深度；相信远方一定会有希望。