数据库中间件分片算法之stringhash

前言

又是一个夜黑风高的晚上,带上无线耳机听一曲。突然很感慨一句话:生活就像心电图,一帆风顺就证明你挂了。 就如同我们干运维的,觉得很简单的事情,有时候能干出无限可能。还是言归正传吧,这一次我们来说说stringhash分区算法。

1.hash分区算法
2.stringhash分区算法
3.enum分区算法
4.numberrange分区算法
5.patternrange分区算法
6.date分区算法
7.jumpstringhash算法

StringHash分区算法的配置

<tableRule name="rule_hashString">
    <rule>
        <columns>name</columns>
        <algorithm>func_hashString</algorithm>
    </rule>
</tableRule>

<function name="func_hashString" class="StringHash">
    <property name="partitionCount">3,2</property>
    <property name="partitionLength">3,4</property>
    <property name="hashSlice">0:3</property>
</function>

和之前的hash算法一样。需要在rule.xml中配置tableRule和function。

  • tableRule标签,name对应的是规则的名字,而rule标签中的columns则对应的分片字段,这个字段必须和表中的字段一致。algorithm则代表了执行分片函数的名字。
  • function标签,name代表分片算法的名字,算法的名字要和上面的tableRule中的<algorithm>标签相对应。class:指定分片算法实现类。property指定了对应分片算法的参数。不同的算法参数不同。

1.partitionCount:指定分区的区间数,具体为 C1 +C2 + ... + Cn
2.partitionLength:指定各区间长度,具体区间划分为 [0, L1), [L1, 2L1), ..., [(C1-1)L1, C1L1), [C1L1, C1L1+L2), [C1L1+L2, C1L1+2L2), ... 其中,每一个区间对应一个数据节点。
3.hashSlice:指定参与hash值计算的key的子串。字符串从0开始索引计数

接下来我们来详细介绍一下StringHash的工作原理。我们以上面的配置为例。

1.在启动的时候,两个数组点乘做运算,得到取模数。

2.两个数组进行叉乘,得出物理分区表。

3.根据hashSlice二维数组,把分片字段的字符串进行截取。

字符串截取的范围是hashSlice[0]到hashSlice[1]。比如我这里设置0,3。‘buddy'这个字符串就会截取出bud,类似数据库中的substring函数。

4.将截取出来的字符串做hash,这个hash的计算方法我研究了一下dble的源代码。源代码如下:

 /**
  * String hash:s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] <br>
  * h = 31*h + s.charAt(i); => h = (h << 5) - h + s.charAt(i); <br>
  *
  * @param start hash for s.substring(start, end)
  * @param end   hash for s.substring(start, end)
  */
 public static long hash(String s, int start, int end) { 
     if (start < 0) {
         start = 0;
     }
     if (end > s.length()) {
         end = s.length();
     }
     long h = 0;
     for (int i = start; i < end; ++i) {
         h = (h << 5) - h + s.charAt(i);
     }
     return h;
 }

这段源代码的意思其实上面有解释。算法是s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]。然后接下来它说明h = 31*h + s.charAt(i)是等同于h = (h << 5) - h + s.charAt(i)。大家是不是还是云里雾里的。你可以去看文章结尾关于这一点的详细解释。

这里我们把这个公式分解一下,根据上述的公式,我们能推导出下列算术式:
i=0 -> h = 31 * 0 + s.charAt(0)
i=1 -> h = 31 * (31 * 0 + s.charAt(0)) + s.charAt(1)
i=2 -> h = 31 * (31 * (31 * 0 + s.charAt(0)) + s.charAt(1)) + s.charAt(2)
i=3 -> h = 31 * (31 * (31 * (31 * 0 + s.charAt(0)) + s.charAt(1)) + s.charAt(2)) + s.charAt(3)
.......以此内推

假设我们的字符串是"buddy",我们截取0-3字符串,我们来算一下。根据上面的函数来写段java代码编译运行。

public class test {
        public static void main(String args[]) {
                String Str = new String("buddy");
                System.out.println(hash(Str,0,3));
        }

public static long hash(String s, int start, int end) {
     if (start < 0) {
         start = 0;
     }
     if (end > s.length()) {
         end = s.length();
     }
     long h = 0;
     for (int i = start; i < end; ++i) {
         h = (h << 5) - h + s.charAt(i);
     }
     return h;
   }
}

[root@mysql5 java]# javac test.java 
[root@mysql5 java]# java test
97905

通过运行程序截取字符串buddy,0-3得到的结果是97905。那么这个结果是怎么算出来的。首先截取0,3,最终截取的是三个字符串bud。索引从0开始计数对应的就是i=2。根据i=2的公式:
i=2 -> h = 31 * (31 * (31 * 0 + s.charAt(0)) + s.charAt(1)) + s.charAt(2)
我们可以查询ascii表
s.charAt(0),是算"b"这个字母的ASCII值,十进制数字为98
s.charAt(1),是算"u"这个字母的ASCII值,十进制数字为117
s.charAt(1),是算"d"这个字母的ASCII值,十进制数字为100

把上述三个值带入到公式得出 31 (31 (31 * 0 + 98) + 117) + 100 = 97905。正好和我们程序计算的值一样。

5.对计算出来的值取模,然后落在指定的分区中。

97905 mod 17 =2 根据取模的值,落在了dn1分区,dn1分区是存放(0,3)的。

6.让我们建表来测试一下,是不是落在第1个分区。


如图所示,当我们执行插入name='buddy',然后再一次查询的name='buddy'的时候,直接路由到了第一个分区。和我们之前计算的结果一致。

注意事项

  1. 该分区算法和hash分区算法有同样的限制(注意事项3除外)
  2. 分区字段为字符串类型

后记

今天介绍的stringhash和hash分区算法大致相同,只不过对于字符串需先计算出hash值。该算法有个经典的数字叫31。这个数字大有来头。《Effective Java》中的一段话说明了为什么要用31,因为31是一个奇质数,如果选择一个偶数的话,乘法溢出信息将丢失。因为乘2等于移位运算。使用质数的优势不太明显,但这是一个传统。31的一个很好的特性是乘法可以用移位和减法来代替以获得更好的性能:31*i==(i<<5)-i。现代的 Java 虚拟机可以自动的完成这个优化。

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

如果你前面没看懂前面那段java代码,现在应该明白(h << 5) - h的结果其实就等于31*h。
今天到这儿,后续将继续分享其他的算法。谢谢大家支持!

Image placeholder
udo982
未设置
  54人点赞

没有讨论,发表一下自己的看法吧

推荐文章
TPC-C解析系列03_TPC-C基准测试之SQL优化

TPC-C是一个非常严苛的基准测试模型,考验的是一个完备的关系数据库系统全链路的能力。这也是为什么在TPC-C的榜单前列,出现的永远只是大家熟知的那几家在业界有着几十年积累、从关系数据库理论开始发展就

敏捷开发流程之Scrum:3个角色、5个会议、12原则

本文主要从Scrum的定义和目的、敏捷宣言、Scrum中的人员角色、Scrum开发流程、敏捷的12原则等几方面帮助大家理解Scrum敏捷开发的全过程。一、Scrum的定义和目的Scrum是一个用于开发

分片技术如何解决区块链系统的可伸缩性问题?

区块链技术的应用可能将改变组织存储数据和执行分布式事务的方式。即使在公共网络上,区块链也可以保证所有参与者都以安全、可靠和可验证的方式访问记录。但是区块链有一个非常明显的限制:可伸缩性。随着交易数量的

实操讲解:使用Keras中的自动编码器进行极端罕见事件分类

在这篇文章中,我们将学习如何实现用自动编码器来构建稀有事件分类器。我们将使用来自此处的真实稀有事件数据集。背景什么是极端罕见的事件?在一个罕见的问题中,我们有一个不平衡的数据集。意思是,我们得到的阳性

笨办法学 Linux Bash:Shell、`.profile`、`.bashrc`、`.bash_history`

Bash:Shell、.profile、.bashrc、.bash_history。 当使用CLI(命令行界面)来使用Linux时,你正在与一个名为shell的程序进行交互。所有你输入的都传递给she

Rust 标准库中的 async/await (async-std)

Rust对齐标准库中的async/await(async-std)简介现在的rust生态中,async/await在rust1.39中已经stable,其他库还有futures已经到0.3.x,还有就

php常用字符串查找函数strstr()与strpos()实例分析

这篇文章主要介绍了php常用字符串查找函数strstr()与strpos(),结合具体实例形式分析了php字符串查找函数strstr()与strpos()的具体功能、用法、区别及相关操作注意事项,需要

String 类的 substring () 方法

截取字符串,在java语言中的用法 1.substring(intbeginIndex) 返回一个新字符串,它是此字符串的一个子字符串。该子字符串始于指定索引处的字符,一直到此字符串末尾。 参数:

Go语言高级编程_5.3 中间件

5.3中间件 本章将对现在流行的Web框架中的中间件(middleware)技术原理进行分析,并介绍如何使用中间件技术将业务和非业务代码功能进行解耦。 5.3.1代码泥潭 先来看一段代码: //mid

Laravel 第八章学习——中间件以及策略

中间件 Laravel中间件(Middleware)为我们提供了一种非常棒的过滤机制来过滤进入应用的HTTP请求,例如,当我们使用Auth中间件来验证用户的身份时,如果用户未通过身份验证,则Auth中

Express 官网文档翻译-3.2-开发中间件

为Express应用开发中间件概述中间件函数本质上是一些可以在应用的请求-响应周期内,访问请求对象 (req),响应对象 (res),和next方法的函数。next方法是Express路由中的一个方法

Laravel 第八章学习——中间件以及策略

中间件Laravel中间件(Middleware) 为我们提供了一种非常棒的过滤机制来过滤进入应用的HTTP请求,例如,当我们使用Auth中间件来验证用户的身份时,如果用户未通过身份验证,则Auth中

Express 官网文档翻译-3.3-使用中间件

使用中间件Express框架是一个由路由和中间件构成的web开发框架,它内置的功能很少:Express应用程序本质上是一系列中间件函数调用。中间件 函数本质上是一些可以在应用的请求-响应周期内,访问 

干货 | 揭秘京东数科强一致、高性能的分布式事务中间件JDTX

导读:在分布式数据库、云原生数据库、NewSQL等名词在数据库领域层出不穷的当今,变革——在这个相对稳定的领域已愈加不可避免。相比于完全革新,渐进式增强的方案在拥有厚重沉淀的行业则更受青睐。同所有分布

理解Vue中间件管道

通常,在构建SPA时,需要保护某些路由。例如假设有一个只允许经过身份验证的用户访问的dashboard路由,我们可以通过使用auth中间件来确保合法用户才能访问它。在本教程中,我们将学到怎样用Vue-

MySQL 数据库操作:创建和查看数据库

数据库是数据的集合。MySQL允许我们高效地存储和检索数据库中的数据。在MySQL中,我们可以使用CREATEDATABASE语句创建数据库。但是,如果数据库已经存在,则会引发错误。为了避免该错误,我

MySQL 数据库操作:删除数据库

使用MySQL的DROPDATABASE命令可以很容易的删除一个数据库。数据库删除的同时,所属的数据表将一起被删除。如果删除的数据库不存在,则会引发错误。为了避免错误的发生,可以在DROPDATABA

平安科技数据库总经理汪洋:开源数据库在平安的应用实践

本文转自| 平安科技数据库产品团队2019年5月9日,平安科技数据库产品及存储产品部总经理在第十届数据库技术大会DTCC上分享了《开源数据库在平安的应用实践》,本文根据演讲内容整理,围绕以下几个方面进

2019数据库趋势研究:谁是最受青睐的数据库?

哪些数据库在2019年最受青睐?本文向DeveloperWeek的数百名业内人士咨询了当前NoSQL与SQL的使用情况,得到了有关MySQL、MongoDB、PostgreSQL、Redis和其他方面

2019数据库趋势研究:谁是最受青睐的数据库?

哪些数据库在2019年最受青睐?本文向DeveloperWeek的数百名业内人士咨询了当前NoSQL与SQL的使用情况,得到了有关MySQL、MongoDB、PostgreSQL、Redis和其他方面

借力中国数据库技术大会 达梦DM8数据库新品正式发布

5月8日—10日,第十届中国数据库技术大会(DTCC2019)如约而至。本届大会以“数据风云,十年变迁”为主题,设定2大主会场及21个技术专场,邀请了来自国内外互联网、金融、教育等行业百余位技术专家,

css right属性不生效怎么办?

cssright属性不生效怎么办?cssright属性不生效是因为元素的position属性值为static,解决方法是将元素的position属性的值改为relative、absolute、fixe

阿里提出针对多目标优化的全新算法框架,同时提升电商推荐场景 GMV 和 CTR

在推荐系统中,多目标优化一直是热门话题,阿里巴巴的XiaoLin、HongjieChen等人针对推荐中的多目标优化问题提出了一种基于帕累托效率的优化算法框架,并应用在电商推荐场景中,对GMV和CTR

MongoDB数据库因安全漏洞,导致Family Locator泄露二十多万名用户数据

摘要:本月第二次,未受保护的MongoDB数据库因大量安全漏洞而导致敏感信息泄露,受欢迎的家庭跟踪应用程序FamilyLocator已经暴露了超过238,000名用户的实时未加密位置数据。该应用程序非

数据结构与算法分析——开篇以及复杂度分析

开篇 你也许已经发现了,工作了几年,原以为已经是一只老鸟。但看到刚参加工作的同事,你发现,原来自己一直在原地踏步。跟新人相比,你的唯一优势就是对业务更熟悉而已,别的就没有什么优势了。 怎样才能够让自己