Tagged: partition

0

多index的Partition处理介绍

我们在上文《Partition的基本概念和实现介绍》中主要分析的是key-value格式的数据,也就是说所有的partition都是基于primary key来决定如何route读写请求的。而实际的系统可能不是只有primary key这么简单,它可能会有第二个index,那么如何处理这种有第二个index数据的partition呢?一般来说有两种常见的方法:一种是基于文档的 document-based partition,另外一种是term-base的partition。 Document-based partition 现在我们来假设你在卖二手车,每一辆车都有一个id,然后你的数据开始就是根据这个id来进行partition的。当你开始卖车了,你希望你的用户可以通过品牌和颜色来搜索车辆,所以你把品牌和颜色做成了第二个index。那么数据在各个partition中的存储可能就如下图所示了: 在插入数据的时候,比如说你加入了一个红色的汽车,首先会根据id分到对应的partition中,同时需要更新这个partition中第二个index的文档,比如你加入的是一辆红色honda,它的id是235,那么就需要把这里的color:red插入235的值,同时还要根据你的生产商对应更新make:Honda的值。 我们可以发现,每次其实根据id找到partition之后,所有的更新就都发生在这个partition了,和别的partition没有关系,所以也称这种方法为local index。 细心的你不难发现,这种方法的更新操作很简单。但是读取操作就有点复杂了,比如你想找到所有的红色汽车,你会发现需要找到所有的partition,然后才能得到所有的红色汽车的结果。正是基于这个原因,我们也称这种实现为Scatter/gather。总得来说虽然我们可以平行访问多个partition,但是它的效率其实并不是很高。不过不管怎样,还是有很多数据库使用这个方式,比如MongoDB,Riak,Cassandra等等。 不过换一个角度来想,假如你的primary key选的比较好,比如说根据make来做partition,然后大多数用户可能会有自己心中的车的品牌,一般基于这个品牌再选择颜色,那么这样的存储其实实现的效率还是不错的。 Term-based partition 和上面方法不同的实现,就是我们把第二个index做成一个global的index,然后把这个global index也partition到不同的节点上,而且partition的方法和primary key可能不同,还是上面的例子,我们可以按照下图的方法来组织第二个index的partition: 说白了,就是把第二个index重新partition,比如上面的color按照字母顺序来进行partition,a-r的字母放在了partition0,其他放在partition1。当然我们也可以使用其它方法来进行partition,比如哈希函数等等,不过这个在这里不重要。 我们来看看这种情况下写该怎么做,比如说我们插入了一个银色的Audi,id是893,那么根据id的partition来看,这个数据是保存在partition1中的,所以,在partition1的primary key index中保存了一行数据,然后根据color的字母来看color该更新哪个partition,这里silver是s开头的,所以也保存在Partition1中,所以更新对应的Partition1中的secondary index中的color:silver。然后再看make,这里是Audi,所以开头的字母是A,那么就和之前不一样了,需要更新的就是Partition0中的secondary index了,所以他会更新Partition0中的make:Audi的数值。 我们可以看到这种方法的写操作其实比之前负责了很多,因为它很有可能就会涉及不同的Partition。那这么做有什么好处呢?答案应该很显然,就是它的读简单了很多了,比如现在我们要搜索所有的红色车辆,就只要找到对应的secondary index所在的Partition(这里就是Partition0)就能找到所有对应的车辆id了,而不需要再去所有partition查询了。 这种实现理论上其实蛮好的,但是现实中一个大的问题就在于一个写操作需要更新多个Partition,既然涉及到多个节点,那么写操作就有可能会有失败和延时,通常来说secondary index的更新是一个异步操作,这也就意味着这里面会有延时,也就是说你刚写入的数据,再立即读就有可能看不到这个数据。比如Amazon的DynamoDB就是这样的实现,在正常情况下,也会有零点秒的延时,至于极端环境这个延时是没有保证的。 总结 本文总结了多index的partition常见的两种处理方式,各有其优缺点(好吧,要是一方没有缺点,那么另外一种肯定也就不会存在了),希望大家看完能对这两个种方法有个大概的了解。

1

Partition的基本概念和实现介绍

我们在之前的文章中讨论了replication的各种实现,我们都知道replication就是把同样的数据在不同的节点上保存副本。这里有一个问题,就是当数据很大的时候,我们需要把数据分成不同的部分进行保存,这个过程就称之为partition,有时也称之为sharding。 通常来说我们需要进行partition的目的并不是说磁盘的空间不够,而是更多地为了scalability,就是说当数据大了之后,query的量过大后,很多时候磁盘的IO等就会成为一个瓶颈,我们就可以把数据分散到不同的磁盘或者不同的节点上,这样就可以分散query的压力,从而提高性能。 Partition和Replication Partition之后是否就意味着每个磁盘上存储的数据就变小了呢?其实不然,很多时候我们会和replication结合起来,让剩余的磁盘保存别的partition的拷贝,通常情况下会让active的partition分散在不同磁盘或节点上,从而达到balance的目的。 举个leader-follower的例子,它在磁盘和节点上的存储可能如下图所示,理想状况下,我们希望每个节点只有一个leader,其余的是follower(当然出问题的时候,可能就会有多个leader)。 Key-Value数据partition 我们知道partition的目前就是分散访问的压力,那么我们该如何来进行数据的partition呢?你也许会说,我们随机分配就好了啊,随机分配的确有大概率能做到平分访问的负载,但是问题就在于你想访问某一个数据的时候你怎么知道该访问哪个节点呢?你可能仍然需要访问所有的节点,然后才能找到需要的数据,这显然是不合理的。下面我们来看几种常见的partition的方法: 通过key的范围来partition 我们首先会想到的一个partition的方法就是按照某一个key进行排序,然后把某一个段放到一个partition,这样我们查询的时候只要知道这个key就可以知道该去哪里查询数据了,这个方法和图书馆的书架排书是类似的,如下图所示: 这种实现中,我们不需要按照key进行平均分配,原因很简单,就是一般来说数据也不是按照key来均匀分配的,所以我们可以认为的根据数据的情况来分配每个partition的key的范围。假如我们把这些key按照一定顺序排序,那么对于范围的查询就会比较友好,我们可以轻易找到应该访问哪些partition。 这种方法的一个问题就是key的选择,假如你的key没有选择好,可能会导致某些partition的访问非常多,而某些partition的访问则非常少,比如说你选择了时间来做partition,然后你会发现最近保存最近这段时间的partition的访问可能会比保存之前数据的partition访问量大很多,所以key的选择很重要。 通过key的哈希值来partition 为了避免上面纯粹key带来的问题,我们通常会使用一个key的哈希值来进行partition,就是通过一个哈希函数计算出key相关的值,然后再根据这个哈希值来进行partition。这里的哈希函数就会比较重要了,MongoDB使用的是MD5,Cassandra使用的是Murmur3等等。 当哈希值计算出来之后,就可以根据哈希值得访问来进行partition了,如下图所示: 这种方法很好地解决了key的权重问题,但是也带来了新的问题,就是对于key的范围查找很不友好,因为哪怕是一个范围的key它现在也会散列在不同的partition上,从而增加了key的范围查找的难度。 有问题就有解决的方法,有聪明的人说我们可以只把key的前面的部分拿出来做哈希,然后后面的部分可以保证至少这部分范围的key仍然落在同样的partition上。这的确可以解决我们上面提到的范围查找的问题。 热点访问的处理 虽然我们说上面的哈希处理可以有效的处理某个partition访问过多的问题,但事实上并不能完全解决,举个极端的例子,我们所有的访问都是对一个key重复写,那么上面的哈希处理也没有办法很好地护理这种问题。 对于写很热的key,有一个办法就是加一个随机变量到这个key上,从而把对这个key的写分散到不同的partition,不过这样做的问就在于你在读的时候也需要把这些所有的key都读回来。 总结 本文主要介绍了partition的基本概念和key-value形式的几种partition的方法和各自存在的问题。