利用一致性哈希水平拆分MySql单表

标签： 利用 一致性 哈希 | 发表时间：2015-03-13 16:32 | 作者：snoopyxdy
出处：http://snoopyxdy.blog.163.com
Sharding（切片） 不是一门新技术，而是一个相对简朴的软件理念，就是当我们的数据库单机无法承受高强度的i/o时，我们就考虑利用 sharding 来把这种读写压力分散到各个主机上去。

所以Sharding 不是一个某个特定数据库软件附属的功能，而是在具体技术细节之上的抽象处理，是Horizontal Partitioning 水平扩展(或横向扩展)的解决方案，其主要目的是为突破单节点数据库服务器的 I/O 能力限制，注意这里是突破单点数据库服务器的“I/O”能力。

在MySql 5.1 中增加了对单表的 PARTITION（分区）支持，可以把一张很大的单表通过 partition 分区成很多物理文件，避免每次操作一个大文件，可以对读写新能有所提升，下面是一个 partition 分区的例子。

一张游戏的日志表，有几千万行的数据，记录了接近一年的游戏物品获取日志，如果不对它进行 partition 分区存储，每次统计和分析日志都会消耗大量的时间。然后我们新建一张分区表，把老的日志数据导入到新的数据，统计分析的时间就会节约很多。
     
      
CREATE TABLE `xxxxxxxx` (     
      
`crttm` int(11) NOT NULL,     
      
`srvid` int(11) NOT NULL,     
      
`evtid` int(11) NOT NULL,     
      
`aid` int(11) NOT NULL,     
      
`rid` int(11) NOT NULL,     
      
`itmid` int(11) NOT NULL,     
      
`itmnum` int(11) NOT NULL,     
      
`gdtype` int(11) NOT NULL,     
      
`gdnum` int(11) NOT NULL,     
      
`islmt` int(11) NOT NULL,  
      
KEY `crttm` (`crttm`),  
      
  KEY `itemid` (`itmid`),  
      
  KEY `srvid` (`srvid`),  
      
  KEY `gdtype` (`gdtype`)  
      
) ENGINE=myisam DEFAULT CHARSET=utf8  
      
PARTITION BY RANGE (crttm)   
      
(  
      
PARTITION p201303 VALUES LESS THAN (unix_timestamp('2014-04-01')),  
      
PARTITION p201304 VALUES LESS THAN (unix_timestamp('2014-05-01')),  
      
PARTITION p201305 VALUES LESS THAN (unix_timestamp('2014-06-01')),  
      
PARTITION p201306 VALUES LESS THAN (unix_timestamp('2014-07-01')),  
      
PARTITION p201307 VALUES LESS THAN (unix_timestamp('2014-08-01')),  
      
PARTITION p201308 VALUES LESS THAN (unix_timestamp('2014-09-01')),  
      
PARTITION p201309 VALUES LESS THAN (unix_timestamp('2014-10-01')),  
      
PARTITION p201310 VALUES LESS THAN (unix_timestamp('2014-11-01')),  
      
PARTITION p201311 VALUES LESS THAN (unix_timestamp('2014-12-01')),  
      
PARTITION p201312 VALUES LESS THAN (unix_timestamp('2015-01-01')),  
      
PARTITION p201401 VALUES LESS THAN (unix_timestamp('2015-02-01'))  
      
); 
对于这种业务场景，使用 mysql 的 partition 就已经足够了，但是对于 i/o 非常频繁的大表，单机垂直升级也已经支撑不了，存储已经不是影响其性能的主要原因，这时候就要用到sharding了。

我们一般会将一张大表的唯一键作为 hash 的 key，比如我们想要水平拆分的是一张拥有3千万行数据的用户表，我们可以利用唯一的字段用户id作为拆分的依据，这样就可以依据如下的方式，将用户表水平拆分成3张，下面是伪代码，将老的用户数据导入到新的3个被水平拆分的数据库中。
    
if userId % 3 == 0:
    
	#insert data in user_table (user_table_0 databaseip: 127.0.0.1)
    
     
elif userId % 3 == 1:
     
	#insert data in user_table (user_table_1 databaseip: 127.0.0.2)
    
else:
    
	#insert data in user_table (user_table_2 databaseip: 127.0.0.3)
我们还会对每一个被拆分的数据库，做一个双主 master 的副本集备份，至于backup，我们则可以使用 percona的cluster来解决。它是比 mysql m/s 或者 m/m 更靠谱的方案。

所以最后拆分的拓扑图大致如下：
利用一致性哈希水平拆分MySql单表 - snoopyxdy - snoopyxdy的博客
 
随着我们的业务增长，数据涨到5千万了，慢慢的发现3个sharding不能满足我们的需求了，因为服务器紧张，所以这时候BOSS打算再加2个sharding，以后会慢慢加到10个sharding。

所以我们得在之前的3台sharding服务器上分别执行导入数据代码，将数据根据新的hash规则导入到每台sharding服务器上。几乎5千万行数据每行都移动了一遍，如果服务器够牛逼，Mysql每秒的插入性能能高达 2000/s，即使这样整个操作，都要让服务暂停8个小时左右。这时候DBA的脸色已经不好看了，他应该是已经通宵在导数据了。

那有没有一种更好的办法，让添加或者删除 sharding 节点对整个分片系统的数据迁移量降低呢？

我们可以利用一致性哈希算法，把用户id散列到各个 sharding 节点，这样就可以保证添加和删除节点数据迁移影响较小。关于什么是一致性哈性算法，参考我的另一篇博客：

这里介绍一个Node.js模块，hashring，github主页地址如下，上面有demo和api文档：
这是一个使用的demo代码，我翻译了注释，供大家参考：
    
    
     
// 加载模块，返回HashRing的构造函数
     
var HashRing = require('hashring');
     
      
     
//实例化HashRing，这个例子中，我们把各个服务器均匀的添加了，没有设置权重
     
// 设置了最大的缓冲区 10000
     
var ring = new HashRing([
     
    '127.0.0.1',
     
    '127.0.0.2',
     
    '127.0.0.3', 
     
    '127.0.0.4'
     
  ], 'md5', {
     
    'max cache size': 10000
     
  });
     
      
     
//我们获取这个字符串的服务器ip
     
var server = ring.get('foo bar banana'); // returns 127.0.0.x
     
console.log(server)
     
      
     
// 如果你想把数据冗余的存储在多个服务器上
     
ring.range('foo bar banana', 2).forEach(function forEach(server) {
     
  console.log(server); // do stuff with your server
     
});
     
      
     
// 对环上移除或新增加一台服务器
     
ring.add('127.0.0.7').remove('127.0.0.1');
     
      
     
var server = ring.get('foo bar banana'); // returns 127.0.0.x
     
console.log(server)
接下来我们就要验证这种方式的可行性。
第一，假如我们有3万条数据，根据一致性哈希算法存储好了之后，这个算法是否能够较平均的将3万条数据分散到3台sharding服务器上。
第二，当数据量增加到5万，然后我们增加2台sharding服务器后，这个算法移动的数据量和最终每台服务器上的数据分布是如何的。

connHashStep1.js将3万用户数据通过一致性哈希算法存储在3台服务器上
    
    
var HashRing = require('hashring');
    
var ring = new HashRing([
    
    '127.0.0.1',
    
    '127.0.0.2',
    
    '127.0.0.3', 
    
  ], 'md5', {
    
    'max cache size': 10000
    
  });
    
     
    
var record = {
    
      '127.0.0.1':0,
    
    '127.0.0.2':0,
    
    '127.0.0.3':0
    
};
    
var userMap = {}
    
     
    
for(var i=1; i<=30000; i++){
    
	var userIdStr = i.toString();
    
	var server = ring.get(userIdStr);
    
	userMap[userIdStr] = server;
    
	record[server]++;
    
}
    
     
    
console.log(record);
第一次利用一致性hash之后，每台服务器存储的用户数据。
    
{ '127.0.0.1': 9162, '127.0.0.2': 9824, '127.0.0.3': 11014 }
connHashStep2.js将5万用户数据通过一致性哈希算法存储在3台服务器上，然后用户数据5万不改变，新增加2台sharding，查看新的5台sharding的用户数据存储情况以及计算移动的数据条数。
     
var HashRing = require('hashring');
     
var ring = new HashRing([
     
    '127.0.0.1',
     
    '127.0.0.2',
     
    '127.0.0.3', 
     
  ], 'md5', {
     
    'max cache size': 10000
     
  });
     
      
     
var record = {
     
      '127.0.0.1':0,
     
    '127.0.0.2':0,
     
    '127.0.0.3':0
     
};
     
var userMap = {}
     
  
     
for(var i=1; i<=50000; i++){
     
	var userIdStr = i.toString();
     
	var server = ring.get(userIdStr);
     
	userMap[userIdStr] = server;
     
	record[server]++;
     
}
     
      
     
console.log(record);
     
      
     
//新增加2个sharding节点
     
var record2 = {
     
	'127.0.0.1':0,
     
      '127.0.0.2':0,
     
      '127.0.0.3':0,
     
	'127.0.0.4':0,
     
	'127.0.0.5':0,
     
};
     
ring.add('127.0.0.4').add('127.0.0.5')
     
      
     
var moveStep = 0;
     
for(var i=1; i<=50000; i++){
     
	var userIdStr = i.toString();
     
	var server = ring.get(userIdStr);
     
	//当用户的存储server改变，则计算移动
     
	if(userMap[userIdStr] && userMap[userIdStr] != server){
     
		userMap[userIdStr] = server;
     
		moveStep++;
     
	}
     
	record2[server]++;
     
}
     
console.log(record2);
     
console.log('move step:'+moveStep);
5万用户数据，存储在3台服务器上的数目：
     
{ '127.0.0.1': 15238, '127.0.0.2': 16448, '127.0.0.3': 18314 }
当我们sharding增加到5台，存储在5台服务器上的数目：
     
     
{ '127.0.0.1': 8869,
     
  '127.0.0.2': 9972,
     
  '127.0.0.3': 10326,
     
  '127.0.0.4': 10064,
     
  '127.0.0.5': 10769 }
最终我们移动的用户数量：
    
move step:20833
其实你会发现
    
20833 = 10064 + 10769 
也就是说，我们只是将1-3节点的部分数据移动到了4,5节点，并没有多余的移动一行数据。根据上面的示例，如果是5千万数据，利用一致性哈希的算法，添加2个节点，仅需2-3小时就可以完成。

那么什么时候我们需要利用一致性哈希水平拆分数据库单表呢?
1、当我们拥有一个数据量非常大的单表，比如上亿条数据。
2、不仅数据量巨大，这个单表的访问读写也非常频繁，单机已经无法抗住 I/O 操作。
3、此表无事务性操作，如果涉及分布式事务是相当复杂的事情，在拆分此类表需要异常小心。
4、查询条件单一，对此表的查询更新条件常用的仅有1-2个字段，比如用户表中的用户id或用户名。
最后，这样的拆分也是会带来负面性的，当水平拆分了一个大表，不得不去修改应用程序或者开发db代理层中间件，这样会加大开发周期、难度和系统复杂性。

P.S 打算在公司试行这种方案，求大牛指点一二，看看有无错误和遗漏。

相关 [利用 一致性 哈希] 推荐：

利用一致性哈希水平拆分MySql单表

- - snoopyxdy的博客
Sharding（切片） 不是一门新技术，而是一个相对简朴的软件理念，就是当我们的数据库单机无法承受高强度的i/o时，我们就考虑利用 sharding 来把这种读写压力分散到各个主机上去. 所以Sharding 不是一个某个特定数据库软件附属的功能，而是在具体技术细节之上的抽象处理，是Horizontal Partitioning 水平扩展(或横向扩展)的解决方案，其主要目的是为突破单节点数据库服务器的 I/O 能力限制，注意这里是突破单点数据库服务器的“I/O”能力.

一致性哈希算法 - Consistent Hashing

- - CSDN博客云计算推荐文章
一、简单介绍一致性哈希算法.         分布式存储中，常常涉及到负载均衡问题，由于有多个数据存储服务器. 因此当一个对象被保存时候，它究竟应该存放到哪个数据存储服务器上面呢.         又例如：现在假设有一个网站，最近发现随着流量增加，服务器压力越来越大，之前直接读写数据库的方式已经不能满足用户的访问，于是想引入 Memcached 作为缓存机制.

一致性哈希算法（consistent hashing）

- - 互联网 - ITeye博客
consistent hashing由来. 在麻省理工学院用作分布式缓存，现在已经扩大到其他领域. 它被设计来解决hash的什么问题. 假设有m个对象需要被映射到n个node上，简单hash就求余映射hash(object)%n->node，就大致均匀的分布到n个node上了. 可是问题在于如果n发生变化（多了或者少了），就必须重新计算保存对象存放到node，这代价未免有点大.

“分布式哈希”和“一致性哈希”的概念与算法实现

- Wolf - 搜索研发部官方博客
　　分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了. 介绍的论文很多，这里做一个入门性质的介绍. 　　两个key point：每个节点只维护一部分路由；每个节点只存储一部分数据. 从而实现整个网络中的寻址和存储. DHT只是一个概念，提出了这样一种网络模型. 并且说明它是对分布式存储很有好处的.

一致性哈希算法与Java实现

- - Java - 编程语言 - ITeye博客
一致性哈希算法是分布式系统中常用的算法. 比如，一个分布式的存储系统，要将数据存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%N，key是数据的key，N是机器节点数，如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了.

一致性哈希算法及其在分布式系统中的应用

- BeerBubble - 博客园-EricZhang&#39;s Technology Blog
本文将会从实际应用场景出发，介绍一致性哈希算法（Consistent Hashing）及其在分布式系统中的应用. 首先本文会描述一个在日常开发中经常会遇到的问题场景，借此介绍一致性哈希算法以及这个算法如何解决此问题；接下来会对这个算法进行相对详细的描述，并讨论一些如虚拟节点等与此算法应用相关的话题.

一个速度快内存占用小的一致性哈希算法

- - 鸟窝
这篇论文中提出在动态变化的Cache环境中，哈希算法应该满足的4个适应条件：：Balance(均衡)、Monotonicity(单调性)、Spread(分散性)、Load(负载). 在分布式缓存系统中使用一致性哈希算法时，某个节点的添加和移除不会重新分配全部的缓存，而只会影响小部分的缓存系统，如果均衡性做的好的话，当添加一个节点时，会均匀地从其它节点移一部分缓存到新的节点上；当删除一个节点的时候，这个节点上的缓存会均匀地分配到其它活着的节点上.

_00013 一致性哈希算法 Consistent Hashing 探讨以及相应的新问题出现解决

- - CSDN博客云计算推荐文章
一般通常会想到的就是哈希取余了吧. 也就是 Hash（userid）% N (N=12)，这样的话也能适当的减小很多压力了，但是这样的话又会产生一些新的问题，增加节点跟减少节点 ：. 假如有一台Redis服务器挂掉了，那么是否这样 Hash（userid）% N (N=12) 哈希取余到该Redis的数据会全部丢失呢.

一致性hash

- - 互联网 - ITeye博客
一致性hash算法 - consistent hashing. 分类：  算法艺术2010-02-02 09:19 69836人阅读  评论(97)  收藏  举报. 算法 cache object 服务器 存储 c. 一致性 hash 算法（ consistent hashing ）.

大数据的一致性

- - 阳振坤的博客
看到了一篇关于数据一致性的文章：下一代NoSQL：最终一致性的末日. (  http://www.csdn.net/article/2013-11-07/2817420 )，其中说到： 相比关系型数据库，NoSQL解决方案提供了shared-nothing、容错和可扩展的分布式架构等特性，同时也放弃了关系型数据库的强数据一致性和隔离性，美其名曰：“最终一致性”.