聊聊partition的方式

本文主要聊一下开源主流产品的partition方式。

partition

一般来说,数据库的繁忙体现在:不同用户需要访问数据集中的不同部分,这种情况下,我们把数据的各个部分存放在不同的服务器/节点中,每个服务器/节点负责自身数据的读取与写入操作,以此实现横向扩展,这种技术成为分片,即sharding。

理想情况下,不同的节点服务于不同的用户,每个用户只需要与一个节点通信,并且很快就能获得服务器的响应。当然理想情况比较罕见,为了获得近乎理想的效果,必须保证需要同时访问的那些数据都存放在同一个节点上,而且节点必须排布好这些数据块,使得访问速度最优。

分片可以极大地提高读取性能,但对于要频繁写的应用,帮助不大。另外,分片对改善故障恢复能力并没有帮助,但是它减少了故障范围,只有访问这个节点的那些用户才会受影响,其余用户可以正常访问。虽然数据缺失了一部分,但是还是其余部分还是可以正常运转。

问题点

1.怎样分片/路由

怎样存放数据,才能保证用户基本上只需要从一个节点获取它。如果使用的是面向聚合的数据库而非面向元组的数据库,那么就非常容易解决了。之所以设计聚合这一结构,就是为了把那些经常需要同时访问的数据存放在一起。因此,可以把聚合作为分布数据的单元。

另外还要考虑的是:如何保持负载均衡。即如何把聚合数据均匀地分布在各个节点中,让它们需要处理的负载量相等。负载分布情况可能随着时间变化,因此需要一些领域特定的规则。比如有的需要按字典顺序,有的需要按逆域名序列等。 很多NoSQL都提供自动分片(auto-sharding)功能,可以让数据库自己负责把数据分布到各个分片,并且将数据访问请求引导到适当的分片上。

2.怎样rebalance

在动态增减机器或partition的情况下,如果重新rebalance,使数据分布均匀或者避免热点访问

分片方式

这里主要分为两大类,一类是哈希分片(hash based partitionning),一类是范围分片(range based partitioning)

1.哈希分片(hash based partitionning)

通过哈希函数来进行数据分片,主要有Round Robbin、虚拟桶、一致性哈希三种算法。

A、Round Robbin 俗称哈希取模算法,H(key) = hash(key) mode K(其中对物理机进行从0到K-1编号,key为某个记录的主键,H(key)为存储该数据的物理机编号)。好处是简单,缺点是增减机器要重新hash,缺乏灵活性。它实际上是将物理机和数据分片两个功能点合二为一了,因而缺乏灵活性。 B、虚拟桶 membase在待存储记录和物理机之间引入了虚拟桶,形成两级映射。其中key-partition映射采用哈希函数,partition-machine采用表格管理实现。新加入机器时,只需要将原来一些虚拟桶划分给新的机器,只要修改partition-machine映射即可,具有灵活性。 C、一致性哈希 一致性哈希是分布式哈希表的一种实现算法,将哈希数值空间按照大小组成一个首尾相接的环状序列,对于每台机器,可以根据IP和端口号经过哈希函数映射到哈希数值空间内。通过有向环顺序查找或路由表(Finger Table)来查找。对于一致性哈希可能造成的各个节点负载不均衡的情况,可以采用虚拟节点的方式来解决。一个物理机节点虚拟成若干虚拟节点,映射到环状结构的不同位置。

哈希分片的好处是可以使数据均匀分布,但是可能造成数据无序不方面range mongo2.4版本+支持hash partition

2.范围分片(range based partitioning)

这个是根据key排序来分布的,比如字典按24个首字母来分,这个的好处是方便range,但是容易造成数据分布不均匀以及热点访问问题(比如个别节点的数据访问量/查询/计算量大,造成负载特别高)。

Bigtable,hbase、2.4版本之前的mongo都使用此方式。

索引分片策略(secondary indexes)

除了数据本身要分片外,索引也需要分片。比较著名的两个反向索引分片策略就是document-based partitioning以及term-based partitioning。然后再此两个基本的策略之上衍生出了hybrid的方案。

1.local index(document-based partitioning)

也称作document-based partitioning.在每个partition本地维护一份关于本地数据的反向索引。这种方式的话,主要使用的是scatter/gather模式,即每次查询需要发送请求给所有的partition,然后每个partition根据本地的索引检索返回,之后汇总得出结果。

  • 好处 简单好维护
  • 缺点 查询比较费劲,比如有n个partition,要查top k,则每个partition都要查top k,总共需要n*k份文档被汇总。

mongo,cassandra,es,solr采用此方案

2.global index(term-based partitioning)

也称作term-based partitioning,这种方式的话,创建的索引不是基于partition的部分数据,而是基于所有数据来索引的。只不过这些全局索引使用range-based partitioning的方式再分布到各个节点上。

  • 好处 读取效率高,因为索引是有序的,基于range parititioning,非常快速找到索引,而且这些索引是全局的,立马就可以定位到文档的位置。
  • 缺点 写入成本比较高,每个文档的写入都需要维护/更新全局的索引。另外一个缺点就是range-partitioning本身的带来的缺点,容易造成数据分布不均匀,造成热点,影响吞吐量。

dynamodb,riak支持此方案

rebalance

当partition所在节点坏掉,或者新增机器的时候,这个时候就涉及到partition的rebalance。原来本应该请求这个node的,现在都需要转移请求另外一个node的过程叫做rebalancing。

rebalancing的目标

  • 均分数据存储以及读写请求,避免热点
  • rebalancing期间不影响正常读写
  • 要尽量快而且尽量少的网络及IO负载来完成

rebalance策略

直接哈希(模数固定)

即key-machine的直接映射,这个的缺点就是:增减机器要重新hash,缺乏灵活性。

两级映射(partition hashing,固定partition数目)

为了提升直接哈希的灵活性,引入了两级映射,即key-partition,partition-matchine/node这样两级,通过partition来解耦key跟machine/node的关联。对于新加入机器时,只需要将原来各个node的一些partition划分给新的机器,只要修改partition-machine映射即可,具有灵活性。

  • 好处 相对于直接哈希来讲,节点增减的时候,只需要调整partiton-matchine的映射关系,客户端无需重新路由。
  • 缺点 固定partition的话,需要一个合理的数目,每个partition大小需要合理确定。相当于这些固定数目的partition要均分整个数据集。如果数据集不断增长的话,如果原来partition个数太少,则每个partition大小则不断增加,造成节点恢复/rebalance相对耗时。如果原来partition个数太多,而数据集后续增长不多,则可能造成有些partition的数据量过少,无法达到均分效果。

Elasticsearch采用此方案,在创建索引的时候需指定shard/partition数目以及replication的数目 Couchbase引入了vBucket的概念在这里可以理解为虚拟的paritition。

动态partition

partition的数目是动态变化的,根据设定的partition大小的阈值,来进行动态的分裂或合并。

hbase采用的就是这种方式

一致性哈希(hash ring)

一致性哈希与前两者有些不同,因为该算法把machine/node也一起进行了hash,然后与key的哈希值一起进行区间匹配,来确定key落在哪个machine/node上面。分布式缓存用到的比较多,比如redis就是用了一致性哈希。

具体如下:

  • 将环形空间总共分成2^32个区
  • 将key跟machine采用某种哈希算法转化为一个32位的二进制数,然后落到对应的区间范围内
  • 每一个key的顺时针方向最近节点,就是key所归属的存储节点。
  • 好处 节点增减的时候,整个环形空间的映射仍然会保持一致性哈希的顺时针规则,所以有一小部分key的归属会受到影响。当节点挂掉的时候,相当于缓存未命中,下次访问的时候重新缓存。
  • 缺点 使用一般的hash函数的话,machine的映射分布非常不均匀,可能造成热点,对于这种情况,引入虚拟节点来解决。也就是借鉴了两级映射的模式,key-vnode,vnode-machine。将一个machine映射为多个vnode,然后分散到环形结构上,这样可以使得vnode分布均匀,然后最后每个machine的存储也相对均匀。

不过引入虚拟节点也会有问题,当新增machine的时候,也就相当于新增多个vnode分散到环上,但是这样子就会造成更多的范围的key需要rebalance。

1、提升单调性(通过环形算法减少增减节点时cache的迁移成本) 2、提升平衡性(通过虚拟节点,尽可能减少节点增减带来的cache分布不均匀问题)

小结

产品

partition方式

索引分片策略

redis

一致性哈希

-

elasticsearch

固定partition两级映射

local index

mongo

2.4版本之前是范围分片,2.4+支持hash分片

local index

kafka

固定partition

-

kafka的key到partition默认采用一致性哈希映射,如果cluster增减node,对之前创建的topic不生效,需要调用reassign-partitions重新分布,避免热点

doc

  • 大数据日知录—数据分片与路由
  • 复制、分片和路由
  • Inverted Index Partitioning Strategies for a Distributed Search Engine
  • Comparison Between Document-based, Term-based and Hybrid Partitioning
  • mongo sharding
  • Elasticsearch Partitioning
  • Partition Rebalance
  • 漫画:什么是一致性哈希?
  • 聊聊一致性哈希
  • 一致性哈希
  • 一致性哈希算法的理解与实践
  • elasticseach日常维护之shard管理
  • Cluster Level Shard Allocation
  • The Authoritative Guide to Elasticsearch Performance Tuning (Part 3)
  • elasticsearch源码分析之Allocation模块
  • 缓存的进化之路—Couchbase的分布式架构
  • How to Rebalance Topics in a Kafka Cluster
  • Kafka Partitioning…
  • kafka重新分配partition

原文发布于微信公众号 - 码匠的流水账(geek_luandun)

原文发表时间:2017-10-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏代码GG之家

google 分屏 横屏模式 按home键界面错乱故障分析(二)

google 进入分屏后在横屏模式按home键界面错乱(二) 你确定你了解分屏的整个流程? ? Android 关机对话框概率没有阴影故障分析 android ...

280100
来自专栏有趣的django

Django REST framework+Vue 打造生鲜超市(五) 六、商品类别数据展示

六、商品类别数据展示 6.1. 商品类别数据接口 (1)商品分类有两个接口: 一种是全部分类:一级二级三级 ?   一种是某一类的分类以及商品详细信息: ?  ...

1.1K80
来自专栏开发 & 算法杂谈

构建动态数据竞争检测平台

之前的文章分别介绍了基于Lockset算法、基于happens-before关系以及基于两者混合的方法。对于这些方法,已有的一些论文中提到的有关实验对比可能都比...

24540
来自专栏Elasticsearch实验室

Elasticsearch查询解析

       Elasticsearch(ES)可用于全文检索、日志分析、指标分析、APM等众多场景,而且搭建部署容易,后期弹性扩容、故障处理简单。ES在一定程...

37580
来自专栏计算机视觉战队

NVIDIA DIGITS

我也忘了在哪里看过几篇类似的文章,为了让更多朋友知道这个好工具,我今天也作为一名合格的搬运工,希望大家努力传播正能量,和大家共同进步!谢谢! NVIDIA为...

34480
来自专栏程序员的SOD蜜

求连续操作(登录)数量(次数)最大的记录(用户)

昨晚上老同事聚会,一个同事说道一个面试问题没有一个人做出来,就是求连续日期登录次数最大的用户,同事说借助 rownumber即可求解,由于是喝酒聊天,也没有说详...

48070
来自专栏腾讯云TStack专栏

FileStore压缩存储(优化篇)

前言 前面已经分析过RBD在Ceph的文件分布,就是将一个完整的块设备,映射成大小相同的数据块,然后通过Crush算法进行Map,最后存储在文件中。FileS...

1K40
来自专栏腾讯安全应急响应中心

短网址安全浅谈

何谓短网址(Short URL)?顾名思义,就是形式上比较短的网址,当前主要是借助短网址来替代原先冗长的网址,方便传输和分享。短网址服务也就是将长网址转换为短网...

54100
来自专栏计算机视觉战队

NVIDIA DIGITS(非常好用的一个框架)

我也忘了在哪里看过几篇类似的文章,为了让更多朋友知道这个好工具,我今天也作为一名合格的搬运工,希望大家努力传播正能量,和大家共同进步!谢谢! NVIDIA为...

44250
来自专栏腾讯云Elasticsearch Service

Elasticsearch底层系列之查询解析

       Elasticsearch(ES)可用于全文检索、日志分析、指标分析、APM等众多场景,而且搭建部署容易,后期弹性扩容、故障处理简单。ES在一定程...

49010

扫码关注云+社区

领取腾讯云代金券