Category: System Design

0

分布式系统硬件基础之漫谈存储设备

我们在分析各种分布式系统场景时不可避免地会讨论到数据的读写,很多时候我们会对数据的读写做很多的优化和特殊处理,而这些操作的背后根源都离不开数据存储的硬件,本文就来和大家谈一谈这其中设计的各种硬件和相应的技术。 Cache和读写 我们都知道把数据放到内存中,这样有读请求过来的时候就可以直接从内存中读取到相关数据(hit cache的情况),而不需要去访问具体的物理磁盘,从而减少了disk I/O的操作。同样地,写也可以写到内存中,只是和读不同的是,内存写终究只是一个中间状态,你最终还是要写到磁盘中才行,所以内存到写操作来说只起到一个delay的作用(当然假如你没有persist保存的情况下,可能也不需要写到磁盘,但我们讨论正常的需要persist保存的情况)。 不过当我们再仔细想一下,其实cache对写并不仅仅是一个delay的作用,它其实还有一些别的好处: 多次写,一次flush:我们很容易就可以想到假如我们对一个数据进行了多次更新,然后再进行一次flush到磁盘,那么这些多次的更新操作其实就只要一次磁盘的写就好了。这从另一个角度减少了磁盘的写操作。 I/O Merge:另外一个好处,就是我们可能有多个数值在内存中被修改了,但我们可以把这些数值集合在一起,一次性更新,这样真正的物理写就可以看成是一次磁盘操作了。 理解了这一点之后,我们再来想想我们之前提到的Write-ahead的logging策略。在write-ahead logging中,内存的修改并没有立即flush到disk中(减少了Random IO的操作),而是写到了一个sequential的log文件中(速度比较快),然后再通过一个后台进程来进行优化写(比如合并之类的)。 这里有人会问为什么Random I/O的操作没有Sequential I/O写的速度快,这是因为对物理磁盘来说,磁头移动是需要时间的,Random I/O就意味着每次要写的偏移地址之间有很大的差别,所以这个磁头需要不停地移动,这显然是很费时间的。而Sequential I/O则不尽然,假如偏移地址是连续的,磁头就不需要不停的移动寻找新的写的偏移,这样就减少了磁头偏移的时间(这里还要看各个厂家的fw的设置,就是sequential写之间的间隔对这个也是有影响的,因为假如sequential写之间间隔时间比较长,那么磁头可能会被reset,所以我们一般认为overlap sequential写是最佳的方案)。 SSD 其实我们上文提到的磁盘准确来讲是HDD,事实上在我们现如今的系统中HDD是最后一层存储,在其和Memory之间还存在另外一种存储介质:SSD。它和HDD不同,不再使用磁头和磁盘来进行存储,它是基于固态电子存储芯片阵列制成的硬盘。简单来说,它有以下优点: 和HDD相比来说,它的random读写的速度都要快很多。一般来说,它的读要比写稍微快一点点。稍后我们来解释这个原因。 Sequential的读写也比HDD速度要快。但是因为HDD的Random 读写比Sequential要差很多,所以单纯比较Sequential的读写速度,SSD提升倍数没有Random读写提升得那么明显,但也有很大的提升。 同步操作有很大的提升。因为HDD只有一个磁头(现在有新的HDD可以支持多个磁头,但是每个磁头也只能访问特定的扇区),所以对于同步操作来说就不能做到真正的同步,说白了还是一个单线程的操作。而SSD则没有这样的限制。 对SSD来说,读操作比较简单,你可以不停地读一个小的单元。但是写操作就比较复杂了,在写之前你必须做一个擦除的操作,而且每次擦除只能是一个block,比如512KB。这个擦除操作还是比较慢的,而且最终会把这个block擦坏了(想象一下,你在一张纸上不停用铅笔写,不停要橡皮擦,最终这张纸的命运就是被擦破)。所以我们对HDD一般讨论的是I/O,而对SSD则一般研究的是寿命。 提到block的擦除,我们就不得不聊一聊SSD的GC(Garbage Collection),其实也很好理解,就是为了让一些block预先准备好了,SSD会回收一些block。这个时候就会有一个数据搬移的过程,比如把几个block中的少量数据(就是数据量不到一个block,但是占用了一个block)移到同一个block中,然后这几个block就可以空出一些出来。这种搬移的操作,其实也是一个新的写的循环,我们称之为Write amplification。你也可以想象,这里的GC操作是需要reserve一些空间来进行的,比如有一个空的block,我们就可以很容易把几个block中的数据搬运过去,假如空的block越来越少,那么搬运的代价就越大。 这也是为什么我们发现当SSD要写满的情况下,性能就会急剧下降。比如你写110GB文件到160GB的SSD和写到同样的320GB的SSD得到的速度可能会有差别,究其根源还是因为需要等待擦除操作。一般来说直接写到一个空的block只需要几百微秒,但是擦除则可能需要几毫秒的时间。 RAID RAID全称廉价磁盘冗余阵列(Redundant Arrays of Independent...

0

分布式文件系统中的MapReduce技术介绍

我们在研究分布式文件系统的实现时,不可避免要讨论MapReduce技术。比较常见的使用这一技术的有HDFS (Hadoop Distributed File System),它是Google文件系统GFS的开源实现。当然很多别的分布式文件系统,比如GlusterFS,QFS(Quantcast File System)以及一些存储服务比如Amazon的S3,Azure Blob Storage以及OpenStack Swift都或多或少有这一技术的影子。本文就来基于HDFS详细介绍一下MapReduce的技术。 分布式文件系统 所谓分布式文件系统,我们可以理解为把文件存储在多个节点中,他们之间通过网络相互连接。从而达到在客户端看起来,这些多个节点就像一台机器一样。为了达到这个效果,HDFS会有一个中心的服务器,我们称之为NameNode,它的作用就是用来知道哪台服务器中存储了哪些文件块,就像大脑一样,我们需要访问某一个文件块的时候,就可以先通过它来确定访问哪一天机器。相应的,在每一台机器上,会运行一个守护进程,它暴露了一个网络服务,这样别的节点就可以通过这个服务访问它上面存储的文件。 和数据库比较类似,为了容错,也会有replication的概念,就是把一个机器上的文件保存多个拷贝在不同的机器上。 MapReduce简介 MapReduce其实说白了是一个编程框架,你可以写相应的代码来处理大的数据集。我们来看这样一个例子:你有一个网站,然后有不同的页面,对应不同的URL,每次有人访问一个页面,就会记录一条记录。 每条记录就是URL和访问的信息,那么现在我们需要对这些记录进行分析,大概的步骤如下: 读出记录的文件,把它们分成一条条记录(比如一行表示一条记录) 调用mapper函数,从每条记录中提出一个key和value对。比如这里我们需要分析每个URL有多少人访问,可以以URL为key,value设为空即可。 根据key来进行排序 调用reducer函数来遍历所有的key-value对,并进行聚合,我们的例子中就是把所有相同的URL合并,并计算有多少条(count函数) 假如我们使用MapReduce来实现这些步骤的话,第一步就是输入格式解析,第二步就是map的操作,第四步是reduce的操作,这两部就是你需要实现相关自定义代码的部分。另外第三步的排序不需要额外来做,因为从map出来的输出就是已经排好序的。 那么第二步和第四步的map/reduce是什么意思呢? Mapper:这个函数对每一个输入的记录都需要调用一次,它主要用来提取键值对。它不保存任何状态,就是对每一个记录这个操作都是独立的。 Reducer:处理Mapper出来的输出,对同样key的值进行处理,比如我们上面的提到的计算同样URL的数目等。 分布式执行 MapReduce最大的特点就是可以在不同的机器上并行执行,而且你不需要写什么特殊的逻辑来处理这个并行操作。 我们来看下面这个图所示的例子,它所示的就是Hadoop中的一个MapReduce的job。这里我们把输入进行partition,标志为m1,m2,m3,然后每一个partition都有一个Mapper进行处理。一般来说在决定mapper的运行的时候,会尽量选择靠近相应输入文件的机器,这样一来就可以减少拷贝输入文件的消耗。通常情况下,相应的机器其实并没有运行map的应用程序,所以会把相应的应用程序包拷贝到对应机器,然后在其上运行应用程序,并输出键值对。 在Map处理好了之后,就需要把同样的键值发送给同一个Reduce进行处理(比如图上的r1,r2,r3)等。需要注意的是我们希望进入reduce的数据是按照某种规则排序的,那么这个排序在哪里实现呢?一般来说各个Map会在它本地先进行排序,然后保存一个有序的输出在他们本地,然后通知reduce说我们这边准备好了。Reduce遍历所有的Map,拷贝相关的数据,在这个过程中再进行 一次全局的排序(merge sort),因为每个map都是排好序的,所以在reduce这一端进行排序的消耗其实是相对还蛮小的。我们把这个过程称之为Shuffle,有点confuse,因为洗牌其实是打乱顺序,而这里其实指的是重新排序。最后reduce再根据他自己的逻辑进行处理就可以了。 MapReduce Workflows 其实单个MapReduce能达到的效果是有限的,在现实中会有很多个MapReduce来组成一个链,我们称之为Workflow来处理实际问题。比如我们上面提到的统计每个URL的数目可以用一个MapReduce实现,但假如我们想知道哪些网页是Top 10访问,就需要再加一个MapReduce来实现。...

1

一文带你了解Windows 性能监控系统的使用

我们现实工作中很多时候想知道当前服务器的各项性能指标,比如说CPU的使用率是多少,还有多少内存,各个磁盘的IO是什么样的情况等等。假如我们使用的是windows操作系统,那么它其实已经内置了一个很强的性能监控系统,本文就来介绍一下我们如何使用这个性能监控系统。 Windows Performance counter系统介绍 总得来说Windows performance counter系统是由这几个方面组成的:Consumer,provider,countersets,counters,instances以及counter value组成。 所谓的Consumer其实就是使用performance数据的模块,我们下面介绍的GUI和代码都属于这部分。 Provider是指产生和publish性能数据的部分。它可以把数据publish给不同的countersets。 Counterset就是一个group,它可以包含一个或多个counters,它会返回多个instance。 Counter就是一个性能的定义,它有一个名字和类型。比如磁盘每秒写IO。 Instance是性能数据的entity,可以包含一个或多个counter值。我们可以这样理解,假设我们是看磁盘的信息,磁盘的每秒的写IO就是一个counter,然后每个磁盘就是一个instance,它可以包含每秒写IO的counter,也可以包含每秒读IO的counter。 Counter value就比较直观了,就是counter的值。 一般来说,Consumer会定期从provider的counterset中收集并记录数据。下面是一个简单的性能API架构图 总得来说V1的架构已经要废弃了,大家尽量还是用V2的架构。 Performance Monitor GUI 我们可以在开始菜单打开Performance Monitor界面,如下图所示,我们可以看到在右边其实有一个系统的总体情况的信息,它包括内存使用的情况,网络的传输状况,磁盘的一些简单信息和各个process的整体信息。这是一个实时的显示。 那么我们如何来真正使用这个工具呢?我们可以在左边Data Collector Sets中点击User Defined,然后创建你关心的Countset, 这里我们使用Create Manually来创建我们关心的Data Collector Set 这里选择Performance Counter 然后点击Add加入我们关心的performance Count,我们这里加入一个Process的%Process...

0

Linearizability一致性介绍二

我们在前面《分布式系统中的Linearizability一致性的概念介绍》介绍了Linearizability的基本概念,本文就来详细介绍一下我们如何来实现Linearizability。 我们再来简单回忆一下Linearizability的介绍,他其实就是说所有的replica都像只有一个一样,那么我们是否有个暴力解,就是真的只有一个拷贝,没有replica,这样不就是Linearizable的了?你是对的,哈哈,不过这个显然不是我们想要的答案,毕竟这样一来,如果这个节点出了任何问题,你整个读写就都不能继续了。 那么我们先来看看各种分布式的模型,看看他们能不能Linearizability: 单leader的replication 在单leader的系统中,假如读都是从leader来的话,或者你使用同步更新replica,那是有可能实现Linearizability的,但是注意也只是有可能,毕竟有可能leader出问题,比如leader自己还认为自己是leader,但事实上已经不是了,这种情况就有可能不是linearizability了。 同步算法(Consensus algorithms) 一些同步算法,它能够防止split brain(多个leader)和stale的replica。这种算法的保证下,就是Linearizable的,这也是我们常见的ZooKeeper的实现方式。 多leader的replication 多leader的replication通常来说都是不linearizable的。因为它们通常都是多个写到不同的leader,然后进行async的replica,这个过程甚至有冲突,所以一般来说它天然就是不Linearizable的。 无leader的replication 在无leader的实现中,一般会有r+w>n这样的设定,看起来是一个很强的一致性设置。但通常来说还是很难说它一定是Linearizable的,这主要取决于他具体是如何实现的。我们后面来详细分析。 Linearizability和Quorums 有人认为严格Quorum的读和写就能保证Linearizability,事实上不尽然,我们来看下面这个例子: 在这里,x的初始值是0。然后有一个Writer去把x更新成1了,这里的write是3个,即w=3,n=3。然后同时Reader A去读,这里r=2,所以它读了replica2和replica3,读出来的值是0或者1。在这之后,Reader B也去读,它读了Replica 1和Replica 2,很不幸,这两个replica都还没有更新,所以读出来的值是0,这里就出现了问题,B在A后面读,但是它竟然读到了一个旧的值。而这里的w+r>n的,所以我们不能简单认为Quorum读写就一定会Linearizable。 CAP理论 不管你是怎样的模型,单leader也好,多leader也罢,基本上都要面临下面这些取舍: 假如你的应用要求Linearizability,那么假如有replica不能和别的replica连接因为各种各样的原因,比如网络等等,那么这些replica就不能处理读请求。 假如你的应用不要求Linearizability,那么任何replica都可能会被读或者写,哪怕他们之间有各种各样的连接问题,都可以继续单独进行工作。 这其实就是著名的CAP理论(Consistency,Availability,Partition tolerance),只能满足其中两个。当然这个理论最大的问题就是partition tolerance只指network连接,或者说节点之间能否通信(不涉及节点延时等等)。这里我就不展开说了,相信很多文章都会介绍这个。 Linearizability和网络延迟 虽然Linearizability很有用,但是事实上并没有多少数据库真的实现Linearizability ,主要原因还是它对性能的影响太大了。尤其在网络延迟很大的情况下,linearizable的读写所消耗的性能都很可观。而且没有什么好的算法可以解决这个问题,除非你不需要Linearizability,Okay这其实也是很多数据库最终的选择。 总结 本文把前一篇文章中没有介绍的内容再补充介绍了一下,希望大家能够对Linearizability有充足的了解。

1

分布式系统中的Linearizability一致性的概念介绍

分布式系统中一致性一直是一个大家热衷讨论的话题,这里的一致性是指假如你同时到两个节点读取数据,你很可能看到的是不同的数据。毕竟发生在一个节点上的写操作同步到另外一个节点总是需要时间的。 我们最常见的说法就是“最终一致性”,也就是说假如没有写操作,所有的节点在一段时间之后就会一致了。目前大多数的数据库都是支持这种一致性的,但是这个一致性非常弱。你仔细想想它其实什么都没有保证,比如你写了一个数,你再去读,读到什么值根本就没有任何保证,只是说你最终能读到一致的值,这个最终是多长时间之后谁也不知道。所以说这样的“最终一致性”其实给应用开发带来了很多困难,也有可能导致很多Bug。 那么有没有什么更强的一致性保证呢?答案是当然有,但是需要注意的是一致性越强,它的性能或者错误容忍度就会越差,毕竟十全十美总是很难。本文就来介绍一种强一致性技术:Linearizability。 概述 我们上面提到在一个“最终一致性”的系统中,你同时访问不同的数据replica,得到的值可能是不同的。那么能否有一种机制保证我们任何时候访问同一个数据replica得到的值一直都是相同的呢?这种保证的就是Linearizability背后的思想:任何时候整个系统就像只有一个拷贝一样,不管你访问哪一个replica,得到的结果都是一样的。 上面这个思想就意味着,当一个client成功完成写之后,所有的client都能够读到刚刚写的数据。为了做到这一点,就意味着我们的读总是最新的值,而不是从stale cache读到的,我们来看下面这个图: 这里就是Alice在读最终分数的时候读到的是一个新的值,而Bob在他后面读,只是读到是另外一个replica的数据,而这个replica的数据还没有更新,就导致哪怕Bob在后面读还是读到了一个旧的值。这就是一个典型的不符合Linearizability的例子。 更加复杂的Linearizability 我们上面理解了Linearizability的基本概念,其实在真正的实现中还是需要更加小心。先来看下面这个例子: 上面这个图中的小柱状体开始表示请求发送的时间,结束表示收到了response,这里我们也可以理解,因为不同的网络延时,各个client的柱状体的时间长短是不一致的。在这个图中,开始的时候x的值是0,然后client A和Client B一直不停的读。整个流程如下: Client A的第一个读的值是0,因为这个时候没有什么别的写发生。 Client A的最后一个读是1,在一个Linearizability的系统中,只要写完成了,就意味着所有的读都能别更新。 中间和写有交叉的读返回值是不确定的,可能是0也可能是1. 这种可能是0也是1的读其实也是不符合Linearizability的要求的,你想假如是只有一个replica,你可能一会读到0一会儿读到1吗?显然是不会的。只会说某一个时刻变成1之后,它就不会再变回0(没有新的写的话)。所以,为了达到这个目的,我们需要再加一些限制,如下图所示: 这里就保证了,只要有一个读到了1,那么随后的所有读都只会读到1,就如上图中箭头所示,Client A在这个时间点读到了1,那么后续的所有的读都必须看到的是1。 我们下面继续来看一个更加复杂的例子,这里引入了一个新的操作cas(x, y, z) => r,这个意思是假如x==y,那么把x设为z,这个操作的结果是r。 总的思想还是一样的,只要写被一个读看到了,那么所有的读都必须看到它。这里还有几个点比较有意思: 最开始的时候Client B读到的值是1,这个读操作和两个写操作有交叉,就是Client A和Client D的操作。这个还是比较合理的,我们可以认为Client D的写操作先到,然后Client A的写,这个时候x就是1了,最后才是client B的读操作。这个顺序虽然和他们的发送操作时间顺序不同,但是可能因为网络延时等等,最终成为这样的顺序是可以接受的。...

0

一文带你了解分布式系统中的真真假假

我们知道分布式系统中各个服务器都是通过网路进行连接的,这样导致的结果就是你很难知道各个服务器的真实状况,比如你判断另外一台服务器是否有问题的唯一办法就是发送一个请求给他,只有收到了回应,你就认为它是好的,假如没有收到回应,你就很难判断对面的服务器是否有问题,因为这个没有回应很可能是发生了网络故障,也可能是对端机器真的出问题了。因此,在分布式系统中我们如何来准确判断这些问题呢?本文就来详细介绍相关的方法。 基于多数的(Majority)事实 很多时候我们一个节点可能不是真的有问题,比如说它正在进行GC,那么在GC的这段时间内它就不能回应任何请求,这个时候从节点本身的来看,它自己是很ok的,没有任何问题。然而从别的节点来看,这个GC的节点就和出问题的节点一模一样,发请求它不回,重试也没有反应。所以别的节点就会认为它是有问题的。从这个角度来看,节点本身其实也是很难知道自己是否问题的。 现在比较流行判断节点是否有问题的算法都是基于多数的决策,比如说我有5个节点,那么大家一起来投票,假如有超过一定数量的节点(一般来说超过半数,这里就是有三个节点)认为它有问题,那么我们就认为这个节点是真的有问题。哪怕这个节点本身是没有问题的,但是只要有多数认为有问题,我们就认为它有问题。这里使用多数来决定是因为多数就意味着不会有冲突,因为一个系统中不可能存在两个多数,只可能有一个。 Leader和Lock 为什么我们要去判断一个节点是否有问题呢?事实上,在分布式系统中,有很多场景会使用到一个只能一个的概念,比如: 一个数据库partition中只能有一个节点是leader 为了防止同时写,只能有一个transaction或者client允许hold 某个object的lock。 一个用户名只能由用户注册,因为它必须唯一。 这些场景都需要我们在设计的时候小心一点,比如说即使一个节点认为它自己是这个选中的唯一(比如认为它自己的leader,认为它拿到这个object的lock等等),也可能大多数别的节点认为它有问题,这个时候假如设计不好的话,就会出问题,我们来看下面这个例子: 这个例子中,我们为了防止有多个client访问同样的数据,会要求每个client在写之后要先抓一下锁。这个锁是一个lease的锁,就是超时会释放的。这里你可以看到Client 1首先申请了这个锁,但是很不幸,在拿到这个锁之后,它立即发生了一个GC,而这个GC发生的时候超过了lease的timeout,这就导致这个锁在lease超时之后被释放了,而client2就拿到了这个锁,做了一个更新。而client1在GC回来之后认为它是拿着这个锁的,所以它直接也去写了,这个时候就出现问题了。这里的问题就是GC回来之后,client1错误地认为它自己还是拿着锁的。 Fencing Tokens 那么如何处理上面这种错误认知呢?一个常见的技术是fencing。如下图所示: 这里做的改变就是每次我们去拿锁的时候会返回一个token值给client,这个token每次拿到锁的时候都会递增。这样在client写的时候必须同时把这个token也发送回来。这样一来storage就可以可根据这个token来判断是否reject旧的token的写。 一个常见的实现方式就是使用ZooKeeper的TransactionID或者node version来作为fencing Token。 拜占庭问题(Byzantine Faults) 上文中说的Fencing Token有一个前提,就是client发过来的token是它真正收到,你可以想象假如client在写的时候发送的token是一个假的token,那么显然fencing Token就也会有问题了。所以对于分布式系统来说,假如有节点说谎,那么问题就会变得更加复杂,我们称这种情况为拜占庭问题,也就是我们常说的拜占庭将军问题。 我们可以简单认为在一个有拜占庭问题的系统中,可能会有那么一两个节点给出的消息是不可靠的。这种不可靠可能是因为: 机器的memory或者CPU registry中的数据因为一些原因出了问题。比如说我们读registry的时候出错了,就返回一个default值,或者任意的值等等。 比如说有一些cheat或者attack发生。这种情况下节点就是不可信的。 当然,在现实中,我们认为这种不可信的问题它发生在比较少的节点,而不是大多数或者所有。所以假如有任何不可信的事情发生在多数节点上(比如有个code的bug,总是把收到的token加一个随机数),那么相应的算法也是没有办法解决这个问题的。 减少谎言的存在 虽然我们认为有谎言的节点是很少的。但是假如我们能够有一些机制去探测或者保护节点,那显然会更好,比如: 网络的包,我们会加一些checksum来检测它是否正确。 对用户的输入值加一些检查,比如看是否在一个合理的范围内。...

1

分布式系统之不可靠时钟揭秘

时钟是一个我们常常会使用的东西,比如我们会用它来确定一个事情发生的时间或者说一个请求花费的时间。然而在分布式系统中,每个机器都有他们自己的时钟,通常来说是由它们本身的硬件来决定的(比如晶振等),它们都不是精确准确的,所以每个机器之间的时钟都或多或少有点差别。所以当我们需要使用不同机器的时钟时,比如比较两个发生在不同机器上事情发生的先后顺序的时候,就很难说哪一个事情是真正先发生哪一个是后发生的。本文就来介绍一下一般如何处理这个问题。 单调时钟(Monotonic)和当天的时间(Time-of-Day Clock) 在现代计算机上,一般有两种时钟,一个是单调时钟另外一个是当天时间。虽然两者都是时钟,但它们其实有很大的差别。 当天时间 所谓当天时间就是我们通常意思上看到的时间,比如现在是几月几日几点几分等。从代码的角度来讲就是类似clock_gettime(CLOCK_REALTIME)返回的值,通常来说这个值会和NTP(Network Time Protocol)进行同步,所以理想状况下各个机器这个值都是差不多,当然现实中每个机器还是不同的,或多或少会有漂移。不过假如漂移过大就会被强制重置从而跳回正确的时间。然而正是因为这种漂移和重置的机制使得这个时钟不太适合用来计算消耗的时间,因为他会不准设置有可能会变成负值。 单调时钟 单调时钟顾名思义就是这个时钟始终往前单调递增。这样一来它就很适合来衡量过去了多长时间。比如说你想看一个请求的时间,可以在发送请求前得到一个时间,然后在得到response之后再获取一个时间,连个时间的差就是你想要的duration。 需要注意的是这个时间的绝对值没有任何意义,所以你要是去比较多个机器的单调时钟是不合适的。 另外对于多CPU的服务器,其实没个CPU的单调时钟也是不同的,只是说一般来说操作系统会帮应用程序处理这个不同,这样一来应用程序就不用担心这个问题。但是有时这个保证也不一定对,所以知道这件事有可能会对一些意想不到的问题有帮助。 NTP对单调时钟也是有影响的,它会看本地的单调时钟的频率,假如本地时钟太快或者太慢它会进行调整(一般的容忍度在0.05%),但是和当天时间不同的是,它只会调整频率,不会让单调时钟跳到很前或者很后。所以,一般来说单调时钟还是一个很好的方法来测量消耗的时长,毫秒级别的精度是没有问题。 时钟的同步和准确性 当天时间是需要进行同步的,因为只有这样它才有真正的意义。然而时钟的同步可能和我们想象的不太一样,我们来看几个例子: 机器上的晶振本身是不准确的,它会漂移。这是一个硬件上的问题,主要会跟环境的温度等等息息相关。Google一般会假设他们的服务器有200ppm的漂移,相当于每30秒有6ms的差别。所以哪怕别的方面都没有问题,这个漂移都是存在的。 机器的时钟和NTP有很大差别的时候,可能会拒绝同步或者被强制重置。这样一来我们就会看到时钟会有一个向前或者向后的跳跃。 假如机器的防火墙设置有问题,那么时钟可能就没有机会和NTP来进行同步了,而我们都不知道这件事。 即使你能够和NTP同步,这个准确度也会因为你的网络延时而有差别。可以想象假如同步的信息收到了网络传输的影响,那么时钟的同步就是不准确的。 NTP服务器本身可能也会有问题,这样一来你拿到的数据可能也不是准确的。 跳跃的秒数会让一分钟的时间发生变化,再也不是60s了,也就是说一分钟可能是59s也可能是61秒,这就很有可能导致系统出现问题。 虚拟机的时间更加复杂,因为多个虚拟机共享CPU,每一个虚拟机在别的机器运行的时候可能都需要暂停几个毫秒,这就使得时间的计算更加困难。 所以精确的时钟在现实中是很难得到的,但是我们仍然可以做一些努力来得到相对精确的时钟,比如依赖于GPS的PTP (Precision Time Protocol),然后很好的控制deploy和监控。当然这样做的代价也很大。 依赖同步时钟的实例 虽然我们知道时钟有这样那样的问题,但是我们仍然有很多情况想要依赖于这个时钟,这该怎么办呢?下面我们从几个例子来具体分析如何处理 有序事件的时间戳 一个常见的例子就是多个节点同时写一个值,常见的做法就是比较一下谁先写谁后写,后写的失败或者覆盖先写的。如下图所示,一个多leader的数据库的写: Client A在Node 1上写了x=1, 然后这个值被replica到节点3。之后Client...

0

分布式系统之怎么都不可靠的网络

当我们聊到分布式系统和单机程序不同之处时第一反应就是多台机器之间的网络问题。多台机器之间的网络连接给我们带来了很多便利,比如我们可以把多个不同地方的机器互联,再也不用担心单台机器带来的性能瓶颈等等。但同时也给我们带来了很多意想不到的问题,本文就来详细介绍为什么我们说网络是不可靠的。 简单Request可能遇到的问题 我们首先来看一下当一个节点发送一个request到另外一个节点,可能会遇到的问题(如下图所示): 你的请求可能直接丢失了。(比如发送时网络突然断了) 你的请求可能会被堵塞在一个queue中,一段时间之后才会被发送。(比如网络负载很重或者接收端的直接过载等) 接收端的节点出问题了(crash或者掉电等等) 接收端的可能出现暂时性的问题,过一段时间才能响应(比如正在做GC等) 接收端处理了你的请求,但是response丢了。 接收端很快处理了你的请求,但是response回复得很慢。 所以从上面的情况来看,一个request出问题,发送端可能压根就不知道发生了什么,是没有发送出去,还是发送出去了接收端没有处理,还是接收端处理了但是response没有能够及时返回。发送端能知道的唯一信息就是一段时间内没有收到response。 正是基于上面的原因,一般来说,这种情况的处理方法就是加一个timeout:一段时间内没有收到response就认为请求出问题了,但是事实上也许接收端还是处理了相关的请求(比如只是response没有能够成功发送回来。) 错误的探测 既然网络是如此地不可靠,那么有很多系统就需要有一个机制来探测网络是否出了问题,比如下面这些场景: 一个负载均衡系统需要停止把请求发送给有问题的节点。 一个单leader的数据库,假如leader出问题了需要重新做leader的选举。 我们上文已经说了,判断一个节点是否真的工作其实比较难,但是在一些特殊场景下判断一个节点的某一个方面是否工作则是有可能做到的: 你可以连接到远端节点,但是没有人在listening,比如说操作系统可以通过返回RST或者FIN包来说明TCP连接已经断了或者拒绝了。 一个节点的process crash了,但是整个操作系统还是正常工作的,我们可以主动通过一个script来通知别的节点process crash了,而不需要使用timeout来判断。 假如你可以访问数据库网络交换机的管理接口,你就可以通过它来探测硬件层面的连接错误。当然这些的前提是你有访问的权限。 假如路由器发现目的IP不能连接,可能会回复你Destination Unreachable的packet。 当然通常来说,我们还是通过心跳机制来进行错误的探测。比如说一段时间没有收到心跳就认为对应的节点有问题了。只是说如何来确定超时是一个值得研究的话题。 超时以及不受控制的延时 假如我们把超时设置得过长,那么在真正出问题到探测到的这段时间内,请求是还会继续发送到这个节点,只是我们会看到很多错误的回复。假如我们把超时设置得很短,那么一个小小的网络波动或者一个负载的波峰都可能导致我们错误地把节点认为是有问题,而这样带来的后果就是把原本属于这个节点的负载转移到了别的节点,这其实也是有问题的(想象极端情况下,很多节点都被认为有问题,从而只有某几个节点在处理请求) 假如我们的网络传输能有一个固定时间的承诺,比如说或每一个包都会在时间d以内完成传输,否则就丢失。然后每个节点都能够在时间r以内完成请求的处理。这样就可以认为我们必然会在时间2d+r内收到response,就可以把超时设置成这个值。 可惜现实中没有这种承诺,下面我们来介绍一下具体的原因: 网络的拥堵和排队 其实就和开车上下班一样,网络包的传输很多时候也会拥堵需要排队: 假如有多个源同时给一个目的发送网络包,那么网络switch就需要把它们排好队,然后一个一个发送到目的地,如下图所示。 在网络包到达之后,假如所有的CPU都很忙,这个时候操作系统就会把收到网络包排队,知道有空闲的CPU可以处理它们。 在一个虚拟机上,有可能CPU会被别的虚拟机在使用,这个时候就会把当前的虚拟机暂停个几十毫秒,而这段时间是不能处理任何网络包的,就只能等待了。 TCP的流控,这里一个节点会控制网络包的发送速度,也就是说包还没有开始发送就被控制了。...

0

一文带你深入理解Serializable隔离最新技术SSI

我们已经在前文了解了数据库的弱隔离以及Serializable隔离的两种技术(串行执行和两阶段锁),每个人都想用Serializable隔离,毕竟它很好的处理了各种冲突。但很多时候又被逼无奈选择弱隔离,原因也很简单,Serializable隔离好虽然好,但是性能消耗太大了,选择它就意味着选择了低的性能。所以人们一直在感叹假如有一种方法能做到Serializable隔离,性能损耗又不大的话就好了。皇天终归不负有心人,一个新的算法横空出世,它就是Serializable Snapshot isolation,简称SSI,它的优点就是能够牺牲很小的性能达到Serializable隔离的效果,这个算法是2008才出现的,不过已经被运用在PostgreSQL的版本9.1和FoundationDB中了。本文就来详细介绍一下这一最新的技术。 悲观和乐观的同步控制 我们在《Transaction Serializable隔离之两阶段锁》中提到的两阶段锁其实就是一个悲观的同步控制策略:任何有可能出现冲突的数据,我们都加锁(不管是不是真的会有冲突),就有点类似多线程的编程。而《Transaction Serializable隔离之串行执行》中提到的串行执行,更是把悲观做到了极致,直接变成串行的单线程编程了。 相比较上面两者来说,SSI则是一种乐观的同步控制:假设所有的同步都是不产生冲突的,每个Transaction都能够互不干扰地执行,只在提交之前进行检查,假如发现了冲突,阻止提交进行重试。只有符合serializable的transaction才能够提交。 其实使用悲观还是乐观的同步控制大家争论了很久,他们在不同的场景下各有其优缺点,比如说乐观的同步控制在一个经常发生冲突的系统中就会带来很糟糕的体验,毕竟你的假设不符合系统的实际情况,这样一来就会有很多重试的处理,从而加大系统的资源消耗,在一些系统资源本就解决极限的情况下反而不如悲观的同步控制,反之亦然。 既然乐观同步控制不是什么新鲜的概念,SSI又有什么优势呢,正如它名字所说的,它是基于Snapshot隔离的,也就是说所有的读是从一个一直的snapshot来获取的。这就和早期别的乐观控制不同,SSI正是基于此来开发了一个算法探测Serialization的冲突从而决定哪个Transaction去abort的。 基于过时假设的决定 我们在之前的《Transaction弱隔离之Write Skew和Phantoms》中讨论过Write Skew,它的流程是一个transaction从数据库中读一些数据,检测相关的结果,然后基于结果决定做一些操作。这里的问题就是在snapshot隔离中,我们读的结果可能已经过时了,也就是说被别的transaction更新了。所以我们之前的基于结果决定做的操作可能不是我们想要的。 当我们读数据的时候,其实数据库并不知道应用程序怎么使用这些数据(你可能只是显示,也可能基于读的结果做某些操作),所以为了安全,数据库一般会说假如有任何transaction改变了你查询的结果就是不valid的。所以为了提供Serializable的隔离,数据库需要能够探测到这种情况,一般怎么做呢?有两种方法: 探测所有基于Stale MVCC object 版本的读(没有提交的写发生在这个读之前) 探测所有影响之前读的写操作(写发生在读之后) 探测Stale MVCC读 还记得我们在《Snapshot的隔离和Repeatable的读》中提到的多版本控制吗?也就是说当一个transaction读的时候,它会忽略也没有提交的写。依然来看我们之前提到的医生值班的例子,Transaction 43开始读的时候,Transaction 42还没有提交,所以它读的时候Alice的on_call还是为true。但是在43提交的时候,42已经提交了,这就意味着提交时候其实42的修改已经生效了,也就是说43看到的内容其实已经是不对的了,这个时候就需要abort 43的操作。 实现也就很简单了,就是在提交之前会检查一下是否有任何写操作提交了,假如有了就需要abort。为什么我们等到提交的时候才检查呢?原因也很简单,因为我们其实并不知道42会对查询到的数据做什么操作,假如只是简单地读,我们完全没有必要去abort 43。这样一来我们就不会出现没有必要的abort操作了。 探测所有影响之前读的写 另外一种情况就是一个transaction修改了之前读的数据。如下图所示: 我们在之前《Transaction Serializable隔离之两阶段锁》中有提到索引区间锁的概念,这里其实使用了类似的技术,如上图所示,Transaction 42和transaction 43同时查询了Shift1234的值班医生,假如我们对Shift_id加一个索引,数据库就可以使用entry1234来记录transaction...

1

Transaction Serializable隔离之两阶段锁

我们在前面的《Transaction Serializable隔离之串行执行》中介绍了Serializable隔离的第一个实现方法:串行执行。本文来介绍第二个实现方法:两阶段锁(Two-Phase Locking)。这个方法也是一个由古到今一直流行的方法,需要注意的是他和我们通常说的两阶段提交(Two-Phase Commit)是完全不同的两个概念,我们会在后面的文章中再详细介绍两阶段提交的概念。 我们都知道锁的作用:就是有transaction想同时写一个object,这个锁可以保证两个写中的一个必须等待另外一个完成。两阶段锁也是类似的,只是说它更加强一点。假如一个object没有人在写,那么多个读可以同时进行。但是只要有人想要写这个object,那么就有下面这样的限制: 假如Transaction A已经读了这个object,Transaction B想要写这个object,那么它就需要等待A提交或者abort。 假如Transaction A已经写了这个object,Transaction B想要读这个Object,那么B必须等待A提交或者Abort。 从上面我们可以看出来,在两阶段锁中,写不仅仅会block别的写,它还会同时block别的读。反过来也是这样。 两阶段锁的实现 目前MySQL和SQL Server都在使用两阶段锁来实现Serializable隔离,DB2使用它来做Repeatable的读隔离。 两阶段锁的具体实现是在数据库中的每一个object上使用一个锁,这个锁有两种模式Shared Mode或者exclusive mode,具体的规则如下所示: 假如一个transaction想要读一个object,它必须首先获得这个锁的shared mode。可以有多个transaction同时以shared mode获得锁,但是假如别的transaction以exclusive 模式获得这个锁,那么所有别的transaction必须等待。 假如一个transaction想要写一个object,它必须获得锁的exclusive mode。这种模式下别的任何transaction都不能以任何形式或者这个锁,假如这个锁以任何形式被获取,都需要等待。 假如一个transaction先读了一个object,再写一个object,就可能需要升级锁,从shared lock升级到exclusive lock。这个升级的过程和单独获取是一样的。 Transaction获得锁之后,需要一直持有,知道transaction提价或者abort了。这也是我们为什么称之为两阶段锁,第一个阶段就是获取锁,第二阶段是释放所有的锁。 从这个实现我们看到,这里有很多锁的操作,也就很容易发生死锁的状况,就是Transaction A在等待Transaction B释放某一个锁,而Transaction B在等待Transaction A释放另外一个锁。对于死锁的状况,数据库会自动检测到,并做相应的处理。 两阶段锁的性能...