Monthly Archive: May 2021

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的方法和各自存在的问题。

0

无leader replication的实现和问题介绍

我们在前面的《多leader replication的实现及常见问题介绍》和《分布式系统之leader-followers Replication深入介绍》分别介绍了多leader和单leader的情况,也许你会好奇是否有无leader的实现呢?答案是肯定的,本文就来深入介绍无leader replication的实现和相关的问题。 其实最早期的时候有很多无leader的实现,就是任何节点都可以进行写。后来慢慢大家就不太使用这个实现了,直到Amazon推出了它的Dynamo系统,这一实现又再次流行起来。现在Riak,cassandra以及Voldermort都是开源的无leader的数据库实现。 如何处理有节点出问题的写 在有leader的架构中,当有节点出现问题(假如在leader上),我们需要做failover,然后才能继续写。而在一个没有leader的结构中,failover就不存在,所以当有节点出问题时,整个流程如下图所示:客户端会给每一个节点发送写的请求,我们现在假设三个节点中有一个失败了,并且我们认为大多数节点写成功就是一个成功写,这里有两个节点写成功了,所以整个写操作是成功的,因此对user1234来说,这个写是ok的。 这样的实现问题很明显,比如说现在节点3恢复了,这个时候,任何到replica3的读都会有问题,因为它丢失了在出问题那段时间的写操作。一个比较简单的解决方案就是,读操作也不是只发送给一个节点,我们同时给三个节点发送,然后根据返回数值所在的version来决定谁是最新的,谁最新我们就使用谁。 读修复和反熵(Anti-entropy) 在分布式系统中,我们希望每一个replica最终都是一样的,所以就希望上文提到的replica3在回来之后能够通过一定的手段修复,就是得到它offline这段时间发生的写操作。那么如何才能达到这个效果呢?一般有以下的方法: 读修复(read pair) 当客户端从多个replica中读取数据的时候,它能看到哪个是最新的,哪些是还有问题的。所以这个时候一个比较常见的方法就是把它看到的最新的值写到它看到的有问题的节点中。这种方法在读比较多的时候很有效,其实可以想象,假如没有读,就没有 机会去比较和重写。 反熵 这个就是后台会有一个线程来不停地检查各个replica之间的差别,当发现有数据差别的时候,就会进行修复,这个和leader不同的是,这个修复不是顺序的,而且可能delay比较大。 Quorums读和写 我们在上面的例子中提到三个节点,有两个写成功,并且我们的读也是两个的话,就可以保证读到最新的写。其实这种读写我们称之为Quorums读和写。准确来讲,假如我们有n个节点,然后写的节点是w个,读的节点是r个,那么quorums读写就是保证w+r>n即可,因为这就意味着我们的读写节点必然有一个是交叉的。也就意味着肯定能读到最新的内容。 就如上图所示,n=5,w=3,r=3,这样哪怕有两个节点是有问题的,我们仍然可以看到replica3包含了最新的写的内容,同时它也被读操作读到了。 虽然上面的定义中是要求w+r>n,其实在现实中,我们很多时候的实现还是会选择>n/2,因为这就基本意味着两者的和肯定大于n了。 但是,是否w+r>n我们就一定什么问题也没有了呢?其实并不尽然,下面是一些常见的可能出问题的情况: 假如写和读同时发生,而这个写只写到了某一些节点,就很难说读到的是不是最新的值了。 假如写是部分成功的,比如说w=3,但是只有两个节点成功了,这个写是失败的,但是并没有去roll back成功的两个写,那么这时读的值很难确定是不是最新的了。 假如一个有新的值的节点突然出现问题了,然后我们从有旧的值得节点来进行replica,这个时候存有新的值的节点就被覆盖成旧的值了,这也就破坏了我们提到的quorum的要求了。 所以,尽管这种方法看起来不错,但是还是有可能会出现这样或那样的问题。 Sloppy Quorum和Hinted Handoff 我们在上文中提到的w+r>n 其实是一种严格的quorum要求,那么假如现实中我们在写的时候w设置的3,但是只有2个节点写成功了,是接受这个写的结果还是直接返回错误呢?你当然可以选择直接返回错误,但是其实还有一种实现就是在这种情况下,我们在n个节点之外再找一个节点去写一下,也保证写了w个节点,只是这里可能有不在n个节点中的节点出现,我们称这种情况为Sloppy Quorum。 当出问题的节点回来之后,任何写到第三节点的值我们需要再写回这个节点,这个过程我们称之为hinted handoff。...

1

多leader replication的实现及常见问题介绍

我们在前面的文章中介绍的都是单leader的实现。也就是说所有的写操作都会通过这个leader来实现。虽然说这是一种比较常见的实现方法,但是它也尤其局限性,比如说leader可能会有问题,比如网络问题等,这个时候就会有一段时间没法进行写操作。或者说当写操作很重的时候,所有的写的load都需要到leader这边,无形中就加重了leader的traffic。本文就来介绍一种多leader的实现方案。 顾名思义,多leader实现方案就是可以同时有多个节点成为leader,所有的写操作可以同时通过这些节点来进行。当其中一个leader在写的时候,另外的leader就和follower一样,也需要从它这边进行replication。 多leader的使用场景 多leader其实并不是一个比较常见的方案。那么一般在什么情况下,我们会考虑多leader的方案呢? 多数据中心的操作 假如我们的数据库是在多个数据中心的时候(实际上为了防止但数据中心出问题,一般的数据库都会分布在不同的数据中心),假如使用单leader的实现,那么leader就会在一个数据中心,从而使得所有的写都得通过那个数据中心。 而假如是多leader的实现,我们就可以在每一个数据中心放一个leader,这样在每一个数据中心中,还是单leader的情况,但是这个数据库则是多leader的情况。具体的架构如下图所示: 下面我们来看看这样的实现有什么好处: 性能 单leader的情况下,所有的写都需要到leader那边,显然跨数据中心的访问性能不会很好。而多leader的情况下,所有的读操作可以直接访问本地的数据中心,虽然需要在数据中心进行数据replication,但是数据中心之间的延迟其实对用户来说是黑盒,所以对用户来说性能是有提升的。 数据中心宕机的容忍性 单leader的情况下,如果有数据中心宕机,那么需要通过failover来找到新的leader,然后可以继续服务。多leader的情况下,单个数据中心的宕机不影响整体的写操作,无需做额外的failover也可以继续进行写操作。 网络问题的容忍性 同样的,但leader其实受leader所在数据中心的网络情况所影响,而相对来说多leader则可以更好的容忍单个数据中心网络的问题。 虽然看起来多leader的实现有很多好处,但其实它也有其问题,那就是冲突写,比如两个写同时发生在两个不同的leader上,并且彼此冲突,该如何进行处理,这个问题我们后面会详细介绍一些处理的方案。 Offline操作的应用 另外一个多leader replication常见的场景就是offline操作,比如你有一个应用哪怕没有网络也希望能够持续工作。 比如说你手机中的日历程序,你希望安排你的日程,比如添加事项,看看后面哪天有哪些安排。这些操作哪怕是在没有网络的时候也希望能够正常工作。只要当这个设备能够再次访问网络的时候我们能够成功同步这些就可以了。其实这就是一个多leader的场景,你可以把你的设备想象成一个数据中心,有网络的时候,就是正常的多leader同步。没有网络的时候,本地的leader也支持读、写操作。当再次有网络的时候能够做跨数据中心(设备)的replication。 协同写操作的应用 另外一个常见的使用场景就是会有多人同时写一个文档。比如说Google Doc,它支持同时有多个人来编辑。这种常见就和上面的比较类似,我们不希望一个人的写去影响另外一个人的写,所以这里通常就会写入本地leader,然后进行多节点的同步。 处理写冲突 我们上面提到多leader最大的问题就是写冲突,毕竟两个leader完全有可能同时修改同样的内容,如下图所示: 这里User1通过Leader1修改了title到B,但是User2又通过leader2修改了title到C,这个时候在他们进行replication的时候就会出现了冲突的问题,究竟是该改成B还是改成C呢? 避免冲突 假如我们现在能够想到一个简单的方法来避免冲突,那么这个问题就自然而然解决了。比如所有修改title的请求全部要到同一个leader来处理,这就可以规避掉上文提到的写冲突。这个方案还是蛮常见的,比如说用户的资料只能他自己能修改,而所有这个用户修改自己资料的请求我们全部指向同一个leader,这样就可以实现冲突的避免。 但是世事显然不会总是这么一帆风顺,比如说有时候某一个数据中心突然就出问题了,那么无可避免的,你就只能把所有的写操作都指向另外数据中心,这样就还是会出现写冲突。 收敛到一致状态 多leader其实很难说谁是最后写的,所以最终应该是什么样的内容有时很难讲,就像上面的例子一样,你说最终title应该是B还是C呢?这个时候就需要一些额外手段来辅助判断: 给每一个写一个独有的ID(比如使用timestamp,UUID等等),然后比较他们的大小。大得获胜。当这个ID使用的时间,那我们称这种方法为最后写的获胜(Last write wins LWW)。这个方法听起来不错,但也有其问题,我们在后面的文章中再具体讨论。...

0

Replication lag常见问题分析

我们在《分布式系统之leader-followers Replication深入介绍》中深入介绍了replication了基本实现,本文主要来聊一聊replication lag常见的一些问题。 我们知道在leader-follower这样的系统中,写操作只能到leader,而读操作则可以分布在多个follower上进行。这也就意味着在一个读比较多而写比较少的系统中,我们其实可以把多个读的load分散到follower上,从而达到一个read scaling的结构。这个想法很好,但是问题也很明显,就是事实上follower和leader之间其实并不是同步的,也就是说你从follower上读到的内容和leader上的内容有可能是不同的。当然,我们说这种不同可能只是暂时的,比如说你不再往leader上写,一段时间之后,各个follower中的数据也就一样了。这种现象我们通常称之为最终一致(eventual consistency)。而这个delay的时间我们称之为replication lag。显然我们希望replication lag越小越好。 读你自己的写 (Read your own Writes) 在实际产品中一个比较常见的使用场景就是读你自己写的内容。比如说我们在某一个讨论下面发了一条评论,那么我们肯定希望自己能立即看到这条评论,而通常来说写是通过leader去写,而读则是通过follower来读的(当然现实中这种场景也不一定会去读,比如在前端就直接先把这条评论加进去,但是假如你刷新了,那可能还是需要去follower读),所以这里一个要求就是我能读到我写的内容。 我们来看下面这个图,假如用户在他写了之后立即来读,就会有可能读不到这个刚写的数据,看起来就像这个数据丢失了。 这时候我们就需要一个“写后读一致”(read-after-write consistency)的保证。也就是说用户重新加载页面,能够看到他写的内容,这个保证对别的用户没有影响,就是说别的用户重新加载可能看到的还是旧的内容。那么怎么实现这个效果呢,也很多方法,下面我们来列几个常见的: 当读一些用户可能会修改的内容,总是从leader来读。其他的内容还是从follower来读。这就是从business层面来定义哪些从leader读,哪些从follower读。比如说你微信自己的朋友圈,就总是从leader读,假如是别的朋友圈就从follower来读,因为你的朋友圈信息只有你才能修改。 但是假如你的使用场景就是很多东西都可以自己修改,假如按照1的方式来设计的话,你就会发现很多东西都需要从leader来读,这样就不能分散读的压力了,这个时候我们可能可以使用一些别的方法,比如看follower和leader之间的lag,假如lag大于一定的阈值就从leader读,否则就还从follower来读等等。 客户端可以记一个最近的更新时间,假如repica的更新时间是在这个时间之后的,就可以从follower读,否则就还是从leader来读。但是这种方法也有问题,比如你从多个设备登录了微信,从其中一个设备做了修改,那另外一个设备可能就看不到这个修改了。所以我们需要考虑一下更多的情况。 当然实际应用中情况可能比这种还要复杂,比如你可能需要考虑服务器在数据中心的分布,比如你被route到了数据中心A,而leader则在数据中心B,你又决定要从leader中取数据,该如何来实现,这些都是需要考虑的问题。 单调读(Monotonic reads) 另外一个常见的读的问题,就是有时我们会发现我们会读到以前的值。这是怎么回事呢?我们来看下图,这里有一个更新,就是插入了一个comments,在第一次读的时候,用户访问的是follower1,读的时候这个comments的插入在follower1上已经完成了,所以就读到了这条数据。但是当第二次读的时候,用户访问了follower2,而这个时候其实follwer2的这个插入的更新并没有完成,这个时候读的就是一个以前的值。这就造成了我们之前看到的读到以前值的情况。 而单调读就是保证上诉这种情况不会发生。它所保证的就是假如一个用户按顺序读,他读到的值不会变成之前的值。一个常见的来实现这个功能的方法,就是一个用户就一直从某一个follower上读,比如根据用户的user ID来决定他访问的follower。但是假如这个follower出问题了,他不得不redirect到别的follower,还是有可能会遇到类似的问题。 一致前缀读取(Consistent prefix reads) 我们来看这样一个场景: 现在我们假设有第三个人从一个follower上听这个对话,而Poons的replication lag比较大,Cake的replication lag比较小,这个第三个听到的对话可能变成了下面这样: 它具体的时间线可以见下图:...

3

分布式系统之leader-followers Replication深入介绍

我们在前面有简单讲过Replication的作用,简单说就是为在多个机器上保存同样的拷贝来服务的。有了这个拷贝之后我们就可以做很多事情,比如说它可以成为一个读的源从而分散读的压力,它可以在原来数据机器出问题(或者deploy)等的时候作为一个backup等等。 这个想法其实很简单,但真正在我们做这个拷贝的时候,会遇到很多问题,比如说我们是使用同步还是使用异步来进行同步多个拷贝,如何保证多个拷贝之间的一致性等等。那么本文就来从各个方面详细介绍这些内容。 Leaders和Followers 我们把每一个保存数据的节点称之为replica,当我们有多个节点的时候,最明显的一个问题就是怎么去保证每个节点的内容都是一样的呢?其中最常见的方法就是基于leader的模式(也成为master-slave模式或者active/passive模式)。总得来说,它的工作方法如下: 一个节点是leader。所有的写操作都必须经过leader。 其他的节点我们成为follower,每次leader写数据的时候,也把相关的内容发送到每一个follower(replication log),然后每个follower根据这些log来更新本地的数据。 当有读的操作的时候,既可以从leader读也可以从follower读。 同步VS.异步Replication 上面这种方法其实在很多关系型数据库中很常见。这里遇到的一个最大的问题就是使用同步还是异步来进行replication。 就比如上面的这个case,它实现的功能很简单。就是把user id 1234这个用户的picture更新一下,它首先发送了update的请求到了leader的replica上。在这之后,leader会把这个更新的请求分别发送给两个follower的replica,从而最终达到所有的replica上这个用户的picture都更新了的效果。 我们就以这个例子来分析一下同步和异步在这两个上面的差别。如下图所示,我们看到leader的返回是在Follower1 更新完成之后,也就是说follower1是一个同步的更新。而leader并没有等待follower2完成更新再返回,这也就意味着follower2的更新是一个异步的。 从这个图中可以看到follower1和follower2的更新其实都是由一个延时的,尽管大多数时候这个延时都很小,但是当我们遇到网络问题或者别的情况的时候(CPU占用率很高,内存不够等等),这个延时有可能会很大,谁也不能保证什么时候能被更新。 所以,同步更新的好处就是follower其实和leader是同步的,当leader有问题的时候我们甚至可以直接切换到同步更新的follower,当然它的问题也很明显,就是每一个更新(写操作)都需要等待这个follower的更新完成才行,这有可能会导致整个request延迟很久,甚至超时。所以,假如你想做同步的更新,一般来说也不会想让所有的节点都同步,而是选择leader和一个节点是同步的,这样就可以在leader出问题的切换和同步的效率之间达到一个很好的trade off。 当然,事实情况下基于leader的replication基本都是完全使用异步。这样的问题就是leader出问题,那些没有sync到别的node的数据就会丢失。好处就是leader完全不收别的节点的影响,哪怕别的节点都出问题也可以正常独立运行(通常这个时候就会出alert,然后oncall就到了表现的时候了,哈哈)。生产环境中这样的选择其实有很多原因,比如说为了保证随时都有节点是健康的,这些节点通常会分布在不同的地区(数据中心),所以他们之间的通信通常不是那么可靠,如果使用同步就会很容易出现问题等等。 Follower的建立 有时我们需要从无到有建立一个新的follower,这种情况在生产环境中特别常见,比如说机器的磁盘坏了,原有follower的数据就都不能用了,这个时候就需要从头开始建立,或者说某个时刻你没有足够的follower了(比如说数据中心出问题了,或者机器出问题了),你需要在一个新的机器上建立一个 follower,那么如何从头开始来建立一个节点呢? 首先想到的就是从leader上拷贝过来就好了,但是我们知道leader其实是在不停改变的,也就是说随时都在不停地被写入,而数据的拷贝速度不会很快(主要瓶颈在HDD的写入速度上,目前基本在200MB/s左右),所以在这个过程中不允许写可能也不是一个很好的方法。那么一般来说是怎么做的呢?大概会有以下的步骤: 得到一个数据库某一个节点的snapshot(这个snapshot不影响写)。大多数数据库都支持这样的功能。 拷贝这个snapshot到新的follower Follower联系leader去得到所有的在这个snapshot之后的操作(log sequence)。 然后follower根据得到的信息来apply snapshot之后 的操作,我们称这个过程为catch up。 处理节点的中断 我们上文中也提到了任何节点在任何时候都有可能出问题。那么要是真的出问题了,我们一般会怎么处理呢? 假如这个出问题的节点是follower,假如这个问题只是service...

0

分布式系统简介(总论)

我们在前面几篇文章中简单介绍了单个服务器对数据的处理,而在现实中数据的存储和获取会涉及到多个机器,也就是说我们会把数据分布在多台机器上,这样做有很多好处: 可扩展性(Scalability) 随着你的数据增加,一个机器可能很难处理日益增长的读写需求,你可以把这些负载分散到多个机上。 容错性/高可靠性(Fault Tolerance/ high availability) 在现实环境中,任何一个机器都有可能出现故障,可能是磁盘故障,网络故障等等,假如你希望某一个或几个机器出现问题,你的产品仍然能够继续工作,那么就需要分布式系统。 延迟(Latency) 假如你的用户遍布全球,那么你肯定希望让你的服务器物理上更加靠近对应的用户,这样才能减少相应的延迟。总得来说,就像我们之前介绍的,当需求增加的时候,你就需要进行扩展,要不是垂直扩展,增加机器的处理能力,要不就是水平扩展,使用更多的机器来处理。前者有尽头,后者则无涯。具体可以参见我之前介绍的《负载均衡》。 Replication和Partitioning 我们在之后将重点来介绍如何水平扩展,通常来说有两者方法来实现水平扩展: Replication 这种方法就是在多个节点(机器)上存放同样的数据,并把它们分布到不到的地方(防止自然灾害等),当一个或几个节点出现问题的时候,保证仍然能有一个节点可以工作。同样的这样的处理也能提高性能。 Partitioning 所谓的partitioning就是把一个大的数据分块存在不同的节点上。 它们两相互是独立的,不过通常我们会同时使用它们,具体的如下图所示: 我们将在后面的文章中来具体详细地介绍如何做replica,如何做partition,以及如何处理数据读写过程中发生的常见问题等。

0

深入浅出理解数据的序列化和反序列化

一般来说,数据的处理有两种类型。一种是在内存中,比如我们常见的结构体,list,数组等等。而另外一种就是把数据写到文件中或者在网络中进行传输,这个时候的数据传输说白了就是比特流,那么接受方如何解析这些接收到的比特流呢?这个时候就需要对数据进行序列化,把相应的数据转化成可以自解释比特流。然后接收方就可以通过反序列化的方法把这些比特流再转化成相应的结构体等等类型。 各种语言自带的格式 很多语言都有自带的序列化方法,比如Java.io.Serializable,Python的pickle等等。它们用起来很方便,但是也存在一定的局限性: 假如序列化是来自于特定的语言,那么反序列化也得是相应的语言。这就给不同语言之间的交流(比如客户端和服务端使用不同语言)带来了困难。 因为允许反序列化时实例化任意的类,所以很容易造成漏洞,给安全攻击带来了可能。 这些语言特定库的向前和向后兼容性一般都不太好。 性能一般来说都不是很好,它们的CPU使用率以及压缩比一般来说都不是很理想。 所以一般来说不太会使用语言自带的序列化和反序列化函数,那么除了语言自带的函数还有哪些选择呢? JSON,XML和CSV 比较常见的不依赖于语言的序列化标准有JSON, XML。前者因为其是浏览器的内置支持格式而流行,后者则有时被大家认为太繁琐和复杂了。当然还有CSV格式也有很多人使用。这些格式其实对人的可读性来说都比较友好,但也各有其问题: 数字的序列化比较差。XML和CSV你基本上很难区分数字和包含数字的字符(除非特殊处理)。JSON虽然好一点,但是它不能区分整数和浮点数。 JSON和XML支持Unicode的字符串,但是不支持binary的字符串。虽然有一些方法来解决这个问题,但是也需要付出相应的代价。 CSV不支持schema,所以都是应用程序自己来决定每行和每列的内容。 除了这些问题外,其实JSON, XML和CSV都还是不错的,目前也还算比较流行。 二进制编码 JSON和XML还是不错的,但是他们的数据有时还是有点冗余,在小量级的数据下这个问题并不是很明显,但是当数据大了之后,这个问题就显得尤为突出。所以在此基础上就出现了很多二进制编码的技术,比如基于JSON的MeessagePack,BSON,BJSON,UBJSON等等,以及基于XML的WBXML等。 我们来以MessagePack为例来看一下如何处理下面这个JSON文档。 第一个byte是0x83,这里前面的4bit 0x80表示这个是一个object,后面的4bit 0x03表示这个里面有3个域。 第二个byte是0xa8,其中前4bit 0xa0是说这个是一个string,长度是由后4bit决定的0x08,也就是8byte的长度。 后面的8个byte就是userName的ASCII编码。 后面的0xa6和之前的0xa8是类似,只是长度这次变成6. 经过这样的编码之后长度就由原来的81byte缩小成了66byte,有大小的好处,但是也牺牲了可读性,究竟值不值得,其实还是仁者见仁,智者见智的事情。这里我们犹豫是否值得的一个重要原因就是其实大小缩小得并不是很明显,下面我们会介绍几种大小减少更明显的方法。 Thrift和Protocol Buffers Thrift和Protocol Buffers和上面的中心思想是类似的,但是他们各自尤其优点。其中Thrift 是由Facebook发明的,而Protocol Buffers(protobuf)是由Google开发的。 我们首先来看看Thrift,它首先需要定义一个Schema如下:...

0

数据库应用之数据分析

在早期数据库发明的时候主要是用来为实现商业功能的,比如说保存订单的信息,支付员工的工资等等。这类需求更多地是面向功能的,它的要求是相关的请求能够快速及时正确的执行,我们称这个流程为联机事务处理(OLTP, Online Transaction Processing)。 而随着数据库发展至今,一个更加常见的应用场景就是数据分析。比如说如何从淘宝订单中分析出商家每个月的销售情况,如何分析出哪些商品是爆款,如何得到某个新的功能给公司带来的点击量的增加等等。我们通常称这个流程为联机分析处理(OLAP, Online analytic processing)。 通常来说OLAP都是由商务部门来使用,最终呈现的形式可能是一个报告,因而它和我们传统的联机事务处理是不同的,它们主要的差别见下表: 场景 OLTP OLAP 读 每次查询的记录数据比较小,通常是查询某个key的情况 大量记录的聚合数据 写 随机访问,希望写的延时很小 批量导入或者event流 主要使用者 终端的用户 内部分析 数据显示方法 当前最新的数据 某段时间的历史数据 数据量级 GB 到TB TB 到PB Data Warehouse 在早期的时候,大家都会使用同样的数据库来进行OLAP的分析,后来越来越多的公司会使用专用的数据库来做这件事情,我们称之为Data warehouse。 当我们要使用一个独立的Data...

0

深入分析数据库中数据的存储和读取

我们日常的开发或多或少都会和数据库打交道,那么数据库中数据都是如何存储来保证读写的效率呢?本文就来详细地介绍数据库中数据的存储和读写。 最简单的数据库 我们首先来看一个最简单的通过bash来实现的数据库,它就是一个键值数据库,通过Bash函数来实现读写。 这里有两个函数,一个是写函数,就是简单的写入key和value对。另外一个函数是db_get()函数,它可以读出最新写入的一行数据。 我们可以这样使用它,这里我们就是写入了两个key,value,一个是123456,对应的后面的Json格式数据:'{“name”:”San Francisco”,”attractions”:[“Exploratorium”]}’,另外一个键值是42,它对应的是'{“name”:”San Francisco”,”attractions”:[“Golden Gate Bridge”]}’,最后我们可以调用get函数得到42对应的值。这个实现算是简单明了,一目了然了。 那么假如一个键值被设置了多次该怎么保存了,如下图所示: 我们可以看到,42被重写了,这里最简单的实现就是继续往后面加一行,然后在读取的时候从后往前读(后面就是最新的),就可以得到最新的值了。 其实在真正的数据库中,也有类似的实现就是一个不断增加的log文件,我们会不停地往里面写,当然真实的数据考虑的问题会复杂很多,比如写到一半出问题了,或者写出问题了等等。但是总得思想还是类似的。 聪明的你也许会问,假如我要删除一个key怎么办呢?一般来说,对于删除的操作,我们需要插入一个特殊记录在最后,当我们遍历到这个记录的时候,我们就知道,这个key是被删除了。 当然这种实现的另一个问题就是,随着我们不停地写这个文件的大小是不断增加的,哪怕我们是更新一个同样的key,这个文件也是在不断增大,它最终会带来文件大小的问题。对于这个问题的一般解决方法就是做merge的操作,也就是保存最新的记录即可,这个操作在我们key的值比较少的情况下可以大大缩小文件的大小。 当然还有一个问题也许你会比较好奇,为什么要一直重复往最后加,而不是去更新呢?这是一个很好的问题,有这样几个原因: 一直往后面加,其实可以充分利用到HDD的sequential写,假如你对HDD的读写有研究,你就会知道,sequential写的速度和效率要比随机写高很多,这个主要的原因就是磁盘的磁头不需要随机地不停进行改变。即使是SSD,sequential写相对于随机写也会延长SSD的寿命。 并发和crash的恢复会简单很多。你不需要太担心写到一半发生crash的情况。基本只要做好checksum,就可以知道最后有多少log可能是不对的,去除即可,而不用担心某一个地方更新只更新了一半的情况。 这样的实现其实写的效率还是不错的,因为你只要负责在文件最后不停地写就可以了,但是当数据大了之后,读就会成为问题,你找一个key的值,需要从后往前不停地遍历,也就是o(n)的复杂度了,那么有没有什么好的办法来加快这个进程呢?答案显然是有的,这就是我们下面要讨论的哈希索引。 哈希索引 还是以上面的数据库来作为例子,我们知道文件其实存在磁盘上,它是有一个offset的。假如我们能够有一个in-memory的hash表来保存key和offset的对对应关系,那么读的效率显然会提高很多,如下图所示: 有了这个哈希表,我们就可以知道42对应的位置在64 offset,然后就很容易读到对应的内容,而不需要从后往前遍历。这里的哈希索引有一个问题,就是它其实是in-memory的,也就是说假如发生crash,我们得要重新建立它,这就需要重新遍历这个disk来得到所需要的索引,一个比较好的方法就是我们在disk也保存一份哈希索引的备份,这样出了问题,我们也可以快速恢复。 初一听起来这样的哈希索引还是不错,但是细想一下就会发现其实它也有很多问题: 假如key的数目很多,也就意味着我们需要保存到哈希索引中的内容也很多。 范围的查找效率很低,比如说找key001到key002之间的值,就需要遍历所有的key才能找到相应的答案。 那么如何来解决这些问题呢?我们来看看SSTable和LSM-Tree。 SSTable 我们发现上面介绍的数据库实现中,每一行都是一个key value的对,其实不同key之间的顺序并不重要。也就是说在数据库中,key=42的记录在前面还是key=53的记录在前并不影响最终的结果。这样一来,我们可以在merge的时候,按照key的顺序来排序,我们称这种方法为Sorted String Table简称SSTable。 它的实现也很简单,流程如下: 当有写到来,首先写到一个in-memory的平衡树结构中(比如红黑树),这样开始写到memory而不是disk的原因是一般来说,维护一个有序的memory的结构相比维护一个有序的disk文件要方便很多,我们称这个为memtable。 当memtable越来越大,比如说大于一定的阈值,就会写到磁盘中,因为memtable本身是有序的,所以有序地写到磁盘中就相对比较容易了,我们称每次的写入为一个segment。...