0级事故因使用斐波那契散列，做数据库路由算法

　　作者：小傅哥
　　博客：https：bugstack。cn
　　源码：https：github。comfuzhengweijavaalgorithms
　　沉淀、分享、成长，让自己和他人都能有所收获！
　　2022年，大促备战进行中。为了保障系统在流量洪峰下可以稳定运行，其中一条是需要对分库分表的数据库进行扩容，以满足更大体量的业务承载能力。
　　但扩容计划并不顺利，因为扩容后的数据并没有如预期散列到不同的库表，而是集中到了数据库的少部分表。扩容失败。经检查，因为这个数据库路由算法并不是公司统一使用的算法，而是研发自己基于斐波那契散列实现的。
　　那为什么使用斐波那契散列会出现这样的问题，是斐波那契算法问题？接下来小傅哥就带着大家一起从数学的角度分析下。一、关于斐波那契
　　斐波那契的历史
　　斐波那契数列出现在印度数学中，与梵文韵律有关。在梵语诗歌传统中，人们对列举所有持续时间为2单位的长（L）音节与1单位持续时间的短（S）音节并列的模式很感兴趣。用给定的总持续时间计算连续L和S的不同模式会产生斐波那契数：持续时间m单位的模式数量是F（m1）。
　　斐波那契数列可以由递归关系定义
　　F00，F11，FnFn1Fn2
　　F0F1F2F3F4F5F6F7F8F9F10F11F12F13F14F15F16F17F18F1901123581321345589144233377610987159725844181从F2开始任意一位都是前两位之和。从F2开始任意一位与前一位相比的比值，都无限趋近于（51）20。618因此基于黄金分割的计算应用，也被称为斐波那契应用。
　　那这个就是斐波那契的基本定义和特性，并且基于这样的特性在计算机科学中，斐波那契常用于；伪随机数生成、AVL二叉树、最大公约数、合并排序算法等。
　　而大部分程序员包括小傅哥最开始意识到斐波那契的应用则来自于，Java源码ThreadLocal中HASHINCREMENT0x61c88647这样一个常量的定义。因为这用作数据散列的特殊值0x61c88647就是基于黄金分割点计算得来的，公式：（1L32）（long）（（1L32）（Math。sqrt（5）1））2。
　　那么既然ThreadLocal是基于斐波那契散列计算的下标索引，那为啥数据库路由算法不能使用同样的方式计算散列索引呢？因为通过验证可以得知，斐波那契散列并不满足严格的雪崩标准（SAC）。接下来小傅哥就带着大家一起来使用数据验证下。二、斐波那契计算
　　斐波那契数列可以通过循环、递归以及封闭式表达式（比奈公式）的方式进行计算。读者可在单元测试中验证：https：github。comfuzhengweijavaalgorithms1。循环计算publicdoublefibonacci（intn）｛doublecurrentVal1；doublepreviousVal0；if（n1）return1；intiterationsCountern1；while（iterationsCounter0）｛currentValpreviousVal；previousValcurrentValpreviousVal；iterationsCounter1；｝returncurrentVal；｝2。递归计算publicintfibonacciRecursion（intn）｛if（n1n2）｛return1；｝else｛return（fibonacciRecursion（n1）fibonacciRecursion（n2））；｝｝3。比奈公式publicdoublefibonacciClosedForm（longposition）｛intmaxPosition75；if（position1positionmaxPosition）｛thrownewRuntimeException（Canthandlepositionsmallerthan1orgreaterthan75）；｝doublesqrtMath。sqrt（5）；doublephi（1sqrt）2；returnMath。floor（（Math。pow（phi，position））sqrt0。5）；｝
　　封闭式表达式：与由具有常数系数的线性递归定义的每个序列一样，斐波那契数具有封闭形式的表达式。它被称为比奈公式，以法国数学家雅克菲利普玛丽比内命名，尽管亚伯拉罕德莫弗和丹尼尔伯努利已经知道它。三、散列函数分类
　　散列函数（英语：Hashfunction）又称散列算法、哈希函数，是一种将任意大小的数据映射到固定大小值的计算方式。散列函数计算结果被称为散列值、散列码，也就是对应的HashMap中哈希桶的索引以及数据库中库表的路由信息。
　　例如在Java中对数据的散列算法：HashMap用到的是一次扰动函数下的哈希散列、ThreadLocal用到的斐波那契散列。而通常数据库路由组件用到的是整数模除法散列，这也是实践中最简单和最常用的方法之一。
　　接下来就给大家介绍这几种常用的散列算法，其他更多散列可以参考HashFunction
　　1。除法散列
　　在用来设计散列函数的除法散列法中，通过取K除以M的余数，将关键字K映射到M个槽中的某一个位置上，即散列函数为：h（K）KmodM表格大小通常是2的幂。
　　另外除法散列的一个显着缺点是除法在大多数现代架构（包括x86）上都是微编程的，并且可能比乘法慢10倍。2。乘法散列
　　乘法散列法整体包含两步：用关键字k乘上常数A（0，并去除kA的小数部分用m乘以这个值，再取结果的底floor公式：h（K）Math。floor〔m（aKmod1）〕
　　步骤：假设某计算机的字长为ww位，而kk正好可容于一个字中（k2wk2w）现在选取范围〔0，2w〕内的任意数值ss，ksks即可用R12wR0R12wR0来表示因此（kA）mod1ks2w（kA）mod1ks2w就是将ksks整体向右平移ww位，此时R0R0即为小数部分再乘以2m2m相当于左移mm位，散列值h（k）h（k）为R0R0的前m位。
　　乘法散列只需要单个整数乘法和右移，使其成为计算速度最快的哈希函数之一。但乘法散列可能会在变更计算因子后，较高值的输入位不会影响较低值的输出位，问题体现在元素分散不均，不满足严格的雪崩标准。所以通常在会进行异或操作
　　乘法散列容易受到导致扩散不良的常见错误的影响较高值的输入位不会影响较低值的输出位。在乘法步骤对此进行校正之前，输入上的变换将保留的最高位的跨度向下移动，并将它们异或或加到键上。所以在输入上的变换将保留的最高位的跨度向下移动，并将它们异或操作或者加到键上。例如HashMap的扰动函数。3。斐波那契散列
　　其实斐波那契散列是一种特殊形式的乘法散列，只不过它的乘法因子选择的是一个黄金分割比例值，所以叫做斐波那契散列。
　　斐波那契散列的特性在于将大数映射到小数的计算结果在表空间上是均匀分布的，且计算满足乘法散列效率高。那为什么并不能使用它作为数据库路由算法呢？四、雪崩标准测试
　　在数据库路由实现方面，通常我们都是使用整数模除法散列求模的方式进行元素的索引计算。那既然乘法散列效率高，斐波那契散列分散均匀，为什么不使用这样的方式处理数据库路由算法呢？
　　在检索的资料中并没有一个专门的文章来说明这一事项，这也倒置很多在学习过HashMap、ThreadLocal源码的研发人员尝试把这两种源码中的乘法散列算法搬到数据库路由算法中使用。在保证每次扩容数据库表都是2的次幂的情况下，并没有出现什么样的问题。那么对于这样情况下，是否隐藏着什么潜在的风险呢？
　　那么为了证实斐波那契散列是否可以用在数据库路由散列算法中，我们可以尝试使用严格雪崩标准（SAC）进行验证测试。
　　那么什么是严格雪崩标准（SAC），在密码学中，雪崩效应是密码算法的理想属性，通常是分组密码和密码散列函数，其中如果输入发生轻微变化（例如，翻转单个位），输出会发生显着变化（例如，50输出位翻转）
　　SAC建立在完整性和雪崩的概念之上，由Webster和Tavares于1985年引入。SAC的高阶概括涉及多个输入位。满足最高阶SAC的最大非线性函数，也称为完全非线性函数。
　　简单来说，当我们对数据库从8库32表扩容到16库32表的时候，每一个表中的数据总量都应该以50的数量进行减少。这样才是合理的。
　　好，那么接下来我们就来做下雪崩测试；准备10万个单词用作样本数据。对比测试除法散列、乘法散列、斐波那契散列。基于条件1、2，对数据通过不同的散列算法分两次路由到8库32表和16库32表中，验证每个区间内数据的变化数量，是否在50左右。准备一个excel表，来做数据的统计计算。
　　测试代码publicMapInteger，MapInteger，IntegerhashFunction（intdbCount，inttbCount，LonghashIncrementVal，inthashType）｛intsizedbCounttbCount；System。out。print（库数：dbCount表数：tbCount总值：size幂值：Math。log（size）Math。log（2））；intHASHINCREMENT（int）（（nullhashIncrementVal？size：hashIncrementVal）（Math。sqrt（5）1）2）；System。out。print（黄金分割：HASHINCREMENTsize（double）HASHINCREMENTsize）；MapInteger，MapInteger，IntegermapnewConcurrentHashMap（）；SetStringwordsFileUtil。readWordList（Usersfuzhengwei1024githubjavaalgorithmslogicsrcmainjavamathfibonacci103976个英语单词库。txt）；System。out。println（单词总数：words。size（）r）；for（Stringword：words）｛intidx0；switch（hashType）｛散列：斐波那契散列intidx（size1）（word。hashCode（）HASHINCREMENTHASHINCREMENT）；case0：idx（word。hashCode（）HASHINCREMENT）（size1）；break；散列：哈希散列扰动函数case1：idx（size1）（word。hashCode（）（word。hashCode（）16））；break；散列：哈希散列case2：idx（size1）（word。hashCode（）（word。hashCode（）16））；break；散列：整数求模case3：idxMath。abs（word。hashCode（））size；break；｝计算路由索引intdbIdxidxtbCount1；inttbIdxidxtbCount（dbIdx1）；保存路由结果if（map。containsKey（dbIdx））｛MapInteger，IntegerdbCountMapmap。get（dbIdx）；if（dbCountMap。containsKey（tbIdx））｛dbCountMap。put（tbIdx，dbCountMap。get（tbIdx）1）；｝else｛dbCountMap。put（tbIdx，1）；｝｝else｛MapInteger，IntegerdbCountMapnewHashMap（）；dbCountMap。put（tbIdx，1）；map。put（dbIdx，dbCountMap）；｝｝returnmap；｝整个方法的目的在于得出不同的哈希算法，对10万个单词散列到指定的分库分表中，所体现的结果。1。斐波那契散列1。1最小黄金分割
　　斐波那契散列也是乘法散列的一种体现形式，只不过它选择了一个黄金分割点作为乘积因子。例如ThreadLocal中的0x61c88647。但如果说我们只是按照一个指定范围长度内做黄金分割计算，并拿这个结果当成乘法散列的因子，那么10万单词将不会均匀的散列到8个库，32张表内。如图：TestpublicvoidtesthashFunction0hashnull（）｛MapInteger，MapInteger，Integermapfibonacci。hashFunction（8，32，null，0）；SetIntegerkeysmap。keySet（）；for（Integerkey：keys）｛CollectionIntegervaluesmap。get（key）。values（）；for（Integerv：values）｛System。out。print（v）；｝System。out。println（）；｝｝库数：8表数：32总值：256幂值：8。0黄金分割：21474836472568388607。99609375单词总数：103976
　　如果你的斐波那契散列值是根据库表的值进行黄金切割的，那么在最初的库表范围较小的阶段，将有部分区域无法使用。这是因为得到的黄金分割点的二进制值没法覆盖整个区域，也就做不到合适的乘法散列计算。参考：https：bugstack。cnmdalgorithmlogicmath20221030bits。html《程序员数学：位运算》1。2最小黄金分割
　　基于最小黄金分割的计算，是没法做到均匀散列的。所以你看到的ThreadLocal默认就给你一个0x61c88647而不是随着扩容长度实时计算的切割值。好那么我们接下来也使用这个值来做计算，看看8库到16库后，数据的雪崩结果。TestpublicvoidtesthashFunction0（）｛MapInteger，MapInteger，Integermapfibonacci。hashFunction（8，32，1L32，0）；SetIntegerkeysmap。keySet（）；for（Integerkey：keys）｛CollectionIntegervaluesmap。get（key）。values（）；for（Integerv：values）｛System。out。print（v）；｝System。out。println（）；｝｝分别测试dbCount8、dbCount16库数：8表数：32总值：512幂值：9。0黄金分割：21474836475124194303。998046875单词总数：103976库数：16表数：32总值：512幂值：9。0黄金分割：21474836475124194303。998046875单词总数：103976
　　从8库扩到16库以后，满足50数据变化的，只有2库2表和3库20表。其他数据变化都不满足严格的雪崩测试。1。3任意扩容库表
　　通常情况下做分库分表会考虑到以后的扩容操作，那如果说按照2的次幂扩容第一次是8库32表，之后是16库32表，在之后32库32表。那么这样扩容下去，其实是扛不住的。所以大多数时候希望是从8库扩到9库，而不是一下翻倍。那我们来测试下9库32表，斐波那契散列的分散效果。MapInteger，MapInteger，Integermapfibonacci。hashFunction（9，32，1L32，0）；SetIntegerkeysmap。keySet（）；for（Integerkey：keys）｛CollectionIntegervaluesmap。get（key）。values（）；for（Integerv：values）｛System。out。print（v）；｝System。out。println（）；｝｝库数：9表数：32总值：512幂值：9。0黄金分割：21474836475124194303。998046875单词总数：103976
　　因为9库不满足2的次幂，也就没法直接乘法散列。所以相当于斐波那契散列失效了。这如果是线上的生产环境，将发生灾难性的事故。2。整数求模散列2。1基础散列计算
　　整数求模以数据库表总数为除数，与哈希值的绝对值进行除法散列计算。一般在数据库路由中非常常用。另外如果根据用户ID做散列路由，但由于ID长度波动范围较大，则可以按照指定长度统一切割后使用。TestpublicvoidtesthashFunction3（）｛MapInteger，MapInteger，Integermapfibonacci。hashFunction（8，32，null，3）；SetIntegerkeysmap。keySet（）；for（Integerkey：keys）｛CollectionIntegervaluesmap。get（key）。values（）；for（Integerv：values）｛System。out。print（v）；｝System。out。println（）；｝｝分别测试dbCount8、dbCount16库数：8表数：32总值：512幂值：9。0黄金分割：21474836475124194303。998046875单词总数：103976库数：16表数：32总值：512幂值：9。0黄金分割：21474836475124194303。998046875单词总数：103976
　　在使用除法散列方式后，满足50数据变化的有5个表。看着并不多，但这相当于是斐波那契散列下的3倍。同时其他表数据接近50的也要大于斐波那契散列。2。2任意扩容计算
　　接下来我们任意从8库扩容到9库，看看数据的变化。TestpublicvoidtesthashFunction3（）｛MapInteger，MapInteger，Integermapfibonacci。hashFunction（9，32，null，3）；SetIntegerkeysmap。keySet（）；for（Integerkey：keys）｛CollectionIntegervaluesmap。get（key）。values（）；for（Integerv：values）｛System。out。print（v）；｝System。out。println（）；｝｝库数：9表数：32总值：512幂值：9。0黄金分割：21474836475124194303。998046875单词总数：103976
　　103976（932）361，那么也就说扩容后的数据，基本在361范围波动，就满足了均匀散列的目的。所以在数据库散列算法中，除法散列是较靠谱且稳定的。五、常见面试题散列算法有哪些种？HashMap、ThreadLocal、数据库路由都是用了什么散列算法？乘法散列为什么要用2的幂值作为每次的扩容条件？你有了解过0x61c88647是怎么计算的吗？斐波那契散列的使用场景是什么？TheFibonacciAssociation：https：en。wikipedia。orgwikiTheFibonacciAssociation哈希函数：https：en。wikipedia。orgwikiHashfunction斐波那契数：https：en。wikipedia。orgwikiFibonaccinumberMathematics散列函数：https：zh。wikipedia。orgwikiE695A3E58897E587BDE695B8雪崩效应：https：en。wikipedia。orgwikiAvalancheeffectFibonacciHashing：TheOptimizationthattheWorldForgot（or：aBetterAlternativetoIntegerModulo）：https：probablydance。com20180616fibonaccihashingtheoptimizationthattheworldforgotorabetteralternativetointegermodulo斐波那契数：https：en。wikipedia。orgwikiFibonaccinumberRelationtothegoldenratioC中具有面向对象设计模式的数据结构和算法：https：book。huihoo。comdatastructuresandalgorithmswithobjectorienteddesignpatternsinchtmlpage214。html