Welcome to Borui's Blog!

时间无多,疾步前行

Designing Data-Intensive Applications读书笔记(7)

2018-04-08

Borui

DDIA

读书笔记分布式

Transactions

Transactions

现实中的数据系统,会有很多故障发生:

数据系统或者硬件随时有可能故障,包括写操作正在执行时.
应用程序随时可能宕机.
网络故障使得应用无法连接数据库,或者数据库节点之间无法连接.
客户端获取到的数据只被部分更新.
客户端之间的竞态条件导致难以预料的bug.

事务用来简化容错机制实现.事务机制使得一些读和写原子写入,要么都成功,要么都失败.如果失败了,应用层可以安全地进行重试.有了事务,应用的错误处理会变得非常简单,不用担心部分写入成功部分写入失败了.事务并不是一个自然规律,事务的产生是有原因的,就是为了应用访问数据库时,能简化编程模型.通过使用事务,应用层无需关心潜在的错误可能和并发问题.当然也并非所有的应用都需要事务,有时候可以通过弱化事务保证甚至完全抛弃事务,来获得更高的性能和可用性.那么到底我们的程序要不要使用事务呢?这里需要深入了解事务究竟能带来什么样的安全保证以及伴随这些保证牺牲了什么.尽管事务看起来很直观,实际上有很多微秒但是重要的细节.

难以掌握的事务概念

几乎所有的关系型数据库和一些非关系型数据都实现了事务.2000年末nosql开始流行,通过提供新的数据模型和默认提供备份和分区来改善关系型数据库的现状.然而事务却被忽略了,很多新兴的数据库完全抛弃了事务,或者重新定义事务,使得事务包含了较弱的保证.

ACID的含义

事务提供的安全保证通常被描述为ACID,代表了Atomicity, Consistency, Isolation, and Durability,是为数据库容错机制提出的精确术语.但是实际上,一个数据库的ACID实现不同于另一个数据库系统的实现,单就隔离性而言都有很多模棱两可的地方.因此ACID的实现有时候可能会和你的期望是不一致的.不满足ACID条件的系统有时被称为BASE,也就是Basically Available, Soft state, and Eventual consistency.

Atomicity

事实上,原子代表那些无法被切割成更小部分的东西.在不同的计算机分支里,原子代表着相似但又有微秒差别的东西.例如,在多线程语言里,如果一个线程执行一个原子操作,这意味着另一个线程不会看到执行到一半的结果,系统只可能处在执行前或者执行后的状态,没有办法处在中间状态.相比之下,在ACID语境下,原子性不是关于并发的,它不是用来表示多个进程同事访问同一个数据,这部分是通过I,也就是isolation.

ACID的原子性描述了如果一个客户端执行多个写操作,而其中某个写操作发生了错误.如果这些写操作被组合成一个原子的事务,那么该事务由于某个写操作的错误从而无法提交完成,因此这个事务就需要被取消.那么事务里包含的任何写操作都需要被丢弃.如果没有原子性,当错误发生时很难定位哪些操作已经执行成功,而哪些操作还未执行.应用程序可以尝试重试,但这导致一些操作被执行两次,从而出现重复或者不正确的数据.原子性简化了这个问题,如果一个事务被取消了,那么应用程序可以确信没有发生任何的更改,可以安全地进行重试操作.

Consistency

一致性这个词汇被严重的滥用了:

在异步化的复制系统里,副本一致性和最终一致性被提出来.
一致性hash是一种分区的方法,一些系统用它来进行重新调整.
在CAP理论里,一致性被用来代表线性一致性.
在ACID环境下,一致性是指数据库处于”好状态”的特定于应用程序的概念.

这一个词就有四个不同的含义,在ACID环境下,如果当前数据库在不变量约束下是正确的,然后开始一个事务,然后事务中所有的写操作都是保证了这个约束,那么我们可以确信不变量约束始终是安全的.怎么理解呢?具体可以参考这里如何理解数据库事务中的一致性的概念.核心在于,一致性是一种应用层的特性,即应用程序从一个正确的状态迁移到另一个正确的状态,这时我们说应用程序保持了一致性,所谓正确的状态是应用层也就是开发者定义的,而不是数据库的特性.而事务就是通过AID手段来保持一致性的,状态的迁移不是瞬时的,是有中间过程的,而事务能够保证状态的安全迁移.

Isolation

大部分的数据库会被客户端并发访问同一行记录,这时候就会遇到并发问题(竞态条件).因此隔离性的含义就是说,并发执行中的事物之间都是互相隔离的.经典数据库教材里将隔离性定义成可串行化,这意味着每个事物都能保证整个数据库只有它自己在运行.数据库来保证,当事物提交的时候,得到的最终结果和事务一个接着一个的运行结果是一样的,尽管事实上他们是并发运行的.但是实际上,数据库很少采用可可串行化这个隔离级别,因为太伤性能了.

Durability

数据库系统本身的目的就是为了提供一个安全存储数据的地方,防止数据的丢失.事务的持久化是指一旦事务提交成功,数据一定不会被丢失.在单机系统中,持久化通常是指数据被写入磁盘中,通常这个持久化过程会包含预写式日志或者相似的结构,从而当磁盘数据损坏后可以恢复.而在分布式系统中,持久化意味着数据被拷贝到了一些节点上,为了保证持久化,数据库必须等这些写操作和备份都完成了,才能让一个事务成功提交.当然,百分百的数据安全是不存在的,如果不巧你所有备份的磁盘都挂掉了,你的数据就一定丢失了.

单目标与多目标操作

总的来说,在ACID中,原子性和隔离性描述的都是在同一个事务里,如果一个客户端执行多个写请求数据库应该怎么做.

原子性:如果写序列执行过程中发生了错误,事务应该回滚,而写操作带来的影响应该被丢弃.也就是说事务保证你不用担心部分失败,要么都成功要么都失败.
隔离性:并发执行的事务不应该影响彼此.例如如果一个事务执行了多个写操作,另一个事务要么看到全部的写入,要么什么也看不到.

多目标事务需要确定哪些读和写操作是隶属于相同的事务的,在关系型数据库里主要是基于客户端的TCP连接,任何连接中的开始事务和提交事务声明之间的操作都被认为是同一个事务.而对于很多非关系型数据库,则没有提供这种接口出来.

单目标写入

当单个目标写入时,原子性和隔离性就会起作用,这是数据库默认的操作.原子性可以通过日志恢复来实现.隔离性可以通过目标上加锁,来保证只有一个线程能写入.

一些数据库还提供一些更复杂的单目标原子操作,例如自增长,类似的还有CAS.

当多个客户端试着同时写入同一个目标时,这些操作能防止更新的丢失.但是通常意义上来说他们并不是事务,有时被称为轻量级事务.事务是一种将多个操作行为或者多目标操作集中到一个执行单元的机制.

多目标事务

许多分布式数据系统都放弃了多目标事务的实现,因为很难跨分区实现,而且在高可用和高性能的场景需求下,多目标事务会成为瓶颈.但是我们的系统不可能只依赖kv数据库或者单目标操作.

在关系型数据库中,某个table依赖的外键要更新,那么就需要多目标事务同事更新他们.
在文档型数据库中,当非规范化的信息更新时,会涉及到多个文档内容的更新,也需要事务.
对于存在辅助索引的数据库,索引的更新操作也需要事务保护.

处理错误和取消操作

事务一个关键的特性就是,当错误发生时可以被取消然后安全的重试.而对于无主副本架构里,设计原则就是数据库尽最大能力去做,但是不会回滚已经做过的事情.因此这就需要客户端去处理异常信息.

重试操作是一种简单并且有效的错误处理机制,但是并不完美:

如果事务实际上成功了,但是网络失败了,这是客户端认为还是失败了,这时候如果重试会导致事务执行两次,除非你有额外的去重机制.
如果错误是由于系统超载了,那么重试事务其实会加重问题.因此我们可以尝试限制重试次数,使用指数退避,或者把超载错误和其他错误分开对待.
面对瞬时异常(例如死锁了,违反隔离性了,网络问题啊)重试是有意义的,但是对于永久性错误(违反了约束条件)重试是毫无意义的.
如果事务执行除了数据库外还有副作用,并且即使取消事务了副作用仍然会发生,那么重试就会有问题.比如事务开启了就会发送邮件出去.(这有点儿分布式事务的意味,为了解决这个问题,可以引入两阶段提交)
重试的时候客户端进程挂掉了,那么很显然数据也就没了.

弱隔离级别

如果两个事务触及的相同数据，它们可以安全的并行运行。竞态条件只在一个事务读取数据同时另一个事务并发更改该数据时起作用，或者两个事务同时试图更改同样的数据。长久以来，数据库通过事务的隔离性将并发问题隐藏掉，使得开发者不需要考虑并发问题。实际上,可串行化的隔离级别很少被真正使用,因为太损耗性能了,因此很多数据库选择提供较弱一些的隔离机制,能够解决部分并发问题.这些隔离机制比较难理解,也有可能会导致比较微妙的bug.由于弱隔离性导致的并发bug不仅仅是理论上的,也是在真实环境中存在的.

不同的隔离级别下,有些竞态条件会被触发,有些则不会.

读已提交

最基本的隔离级别就是读已提交,有两个基本保证

当从数据库读取数据时,你只能看到已经写入的数据(没有脏读)
当写入数据库时,你只能复写已经被提交的写入(没有脏写)

没有脏读

当事务执行过程中,写入了一些数据但是还没有提交或者取消,如果其他事务可以读到这些写入数据,那么这就叫做脏读(dirty reads).对于读已提交级别的事务,应该能够避免脏读的发生,当事务没有提交前,写入数据对于其他的事务将是不可见的,当事务完成提交后,对于其他事务则是立即可见.脏读的意义:

当一个事务在更新若干个目标时,如果有脏读,意味着其他事务只能看到部分更新.看到部分更新中的状态,这会导致用户在其他事务里做出错误的选择.
如果事务取消了,那么事务中的写操作都会被回滚.如果数据库允许脏读,那么其他事务看到的数据很有可能晚些时候就被回滚了,那么其他事务的结果就会变得匪夷所思.

没有脏写

如果两个事务同时进行写操作呢?我们无法知晓写的顺序是什么,但很明显后续的写操作将会覆盖前者.不过,如果前一个写入是一个尚未提交的事务的一部分,那么后一个写入就复写了未提交的数据,因此这就造成了脏写(dirty writes).读已提交隔离级别必须能够避免脏写,通常会在前一个写入操作的事务提交或者取消后,才继续进行后一个写入操作.这样避免了一些问题:

当事务进行多目标更新时,脏写会导致错误的输出.例如两个人同时同买一辆车,需要更新数据库将车锁定给一个人,然后还要在写入一份该车的账单给他.如果发生了脏写,那么就会导致车锁定了一个人,但是账单被另一个人的记录复写了.
但是读已提交无法避免计数器并发自增长的问题.因为这不是一个脏读问题,但是结果仍然是不对的.

实现读已提交

数据库通过行锁来实现防止脏写:当一个失误试图修改一个特定目标时(可以是一行或者文档),必须首先获取到目标上的锁,然后直到事务提交或者取消.任何目标的锁都只能被一个事务获取.

脏读怎么解决呢?一种可选的方案就是采用相同的锁,任何一个事务想要读取目标必须获取锁,读完后释放锁.但是这种方法实际工作性能并不好,一个长时间运行的写入事务会阻塞许多只读的事务操作.应用程序中一个部分慢,结果导致不相干的功能因为等待锁也变慢了,所以这是不可取的.大部分数据库采用这样一种策略:任何目标被写入时,数据负责记录旧值,当其他事务读取时直接返回旧值,当新值事务被提交了,其他事务才会读到新值.

快照隔离和可重复读

不可重复读

由于前后两次读取操作之间,间隔了完整的事务,导致读到的数据不一致.有些时候这个问题是无法容忍的:

备份:备份需要获取整个数据库的一个拷贝,这会花费几个小时来进行,与此同时写操作也在执行中.因此备份中部分是老数据,部分是新数据.当你从一个备份中恢复数据时,这种不一致性就成为永久的了.
分析查询或者完整性检查:每次查询的结果在不同时间点结果都是不一致的.

快照隔离性能够解决不可重复读问题.大体的思想是这样的,每个事务读取的都是数据库的一个一致性的快照,也就是说事务看到的全部数据都是自事务开始就已经被提交的数据.即使数据随后被其他事务更改了,其他事务也只能看到特定时间点的旧数据.

快照隔离性实现

为了解决脏写问题,快照隔离性还是采用了写锁的方式.但是读的时候就不需要锁了.一个基本理念就是读者永远不会阻塞写者,反之亦然.这就使得数据库在处理写操作时,还能够提供长时间运行的读取操作,而两者之间不会互相干扰.

为了解决脏读和不可重复读,快照隔离性采用了之前机制的一个泛化版本.那就是数据库会针对通一个目标,保存不同提交版本的值,因为不同的事务会在不同的时刻去执行.这种机制被称为多版本并发控制(multiversion concurrency control (MVCC))

如果数据库只需要保持读已提交隔离性,那么就只需要保留两个版本,一个已提交的版本,一个重写但尚未提交的版本.不过数据库通常采用MVCC来实现读已提交隔离性.已搬情况下数据表会包含create_by域和delete_by域,分别存储插入时刻的事务id和删除时刻的事务id.

当事务读取时,事务id用来决定读取哪个版本:

在事务开始时,数据库列出全部正在执行中的事务,这些事务里所有的写操作都会被忽略,即使这些事务随后就被提交了.
任何被取消的事务写操作都被忽略.
任何有较大事务编号的写操作都会被忽视,不管他们有没有被提交.
其他的写操作都是可见的.

这些规则也适用于插入和删除操作.除此之外以下的条件也是对的:

当一个读事务开始的时候,插入事务已经提交了.这时数据是可见的.
当数据被标记为删除,或者已经标记为删除了.只要删除事务还没有提交,而读取事务开始了,那么这个数据仍然是可见.

MVCC从不本地更改数据,而是通过新建数据版本,从而能够提供一致的快照.

索引和快照一致性

那么索引如何在多版本数据库里工作呢?一个选择就是索引指向数据的所有版本,然后索引查询的时候将针对当前版本不可见的数据都过滤掉.后续GC会将那些对任何事务都不可见的版本清理掉.

实际上,具体实现细节决定了多版本并发控制的性能.B数索引比较常见的策略是append-only/copy-on-write,当更新时并不复写页面,而是新建一个被更改页面的拷贝,从父节点到根节点都被拷贝出来然后指向新版本的子节点,而不受影响的节点则不必拷贝.于是,每个写事务都会对应一个B数的根,每个根对应了某个时刻下的一致性快照,于是读取操作就不再需要根据事务id来过滤了.不过这仍然需要后台进程来合并和垃圾回收.

丢失更新

读已提交和快照隔离性都解决了在并发写事务中如何保证读事务的正确性.但是忽略了并发写事务的问题.我们只是简单的讨论了脏写的问题,这只是写写冲突的一个特殊类型.还有其他的并发写问题,最常见的就是丢失更新(lost update)问题,当应用程序读取相同的数据,然后更改然后再写回去(read-modify-write),并发执行时就会导致一个更新操作丢失了,因为第二个写操作没有看到第一个更新操作.

原子写操作:许多数据库提供了原子更新操作UPDATE counters SET value = value + 1 WHERE key = 'foo';,对于MongoDB也提供了json文档部分数据的本地更新操作,但是很多写操作并不是只是简单的原子操作,只是原子操作能用的时候最好去用.原子写操作一般使用排他锁实现,数据被读取时其他事务无法读取直到数据更新完成,这被称为cursor stability.不幸的是,ORM框架很容易使得代码不使用原子写操作而导致bug.

显示锁:当原子操作不合适的时候,可以采用显示加锁的方式.

BEGIN TRANSACTION;
SELECT * FROM figures
    WHERE name = 'robot' AND game_id = 222
    FOR UPDATE;
-- Check whether move is valid, then update the position
-- of the piece that was returned by the previous SELECT.
UPDATE figures SET position = 'c4' WHERE id = 1234;
COMMIT;

自动检测丢失更新:无论是原子操作还是显示锁,都是通过将readmodify- write cycles顺序化执行.一种可选的方案能够使得他们并行执行,如果事务管理器发现了丢失更新,就回滚进行重试.结合快照隔离机制很容易实现这种检测,而且一旦数据库实现这种机制,不需要应用层做任何事情.

CAS:对于不提供事务的数据库,可以通过compare-and-set来避免更新丢失.每次更新时,必须确保上一次读到的数据没有被更改,如果被更改了那就需要进行重试操作.但是如果,数据库允许读取旧的快照,这就有问题了,所以采用时必须确保这点.

冲突解决和备份:在多副本的数据库里,丢失更新需要考虑另外的一些事情.锁和cas操作都只能适用于只存在单个最新副本的数据库.这时就只能允许存在数据的多个冲突版本,然后在客户端或者特殊的数据结构里进行解决冲突.而原子操作仍然有效(todo, 没太看明白为什么有效).常用的LWW(last write wins)实际上会导致丢失更新,但是仍然被广泛使用.

写倾斜和幻读

可以把幻读看作是丢失更新的泛化问题.此时两个事务读取了相同的数据,然后再更新数据(事务之间更新的不同的数据).而当更新相同数据时,就会导致脏写或者更新丢失.

原子操作没有用,因为原子操作是针对单个目标,而这里是多个目标.
快照隔离下的丢失更新检测机制也没有用,只有真正的可串行化才可以.
数据库是允许指定约束条件的,但是大部分数据库内置的约束条件,都不能包含多个目标.因此需要通过trigger或者物化视图来实现.
显示使用排他锁是可以的.

写倾斜例子

会议室预定系统:预定会议室前,你需要先查询有没有已经被预定,恰好这时候两个人都在预定,那么都一开始发现没有被预定然后就都进行了预定.
多人游戏:我们可以组织玩家同事移动相同的图形,但是我们没有限制玩家同事将不同的图形移动到相同的地方.
取名字:类似会议预定系统
双花:在记账系统里,可能会存在双花问题.

幻读的套路

幻读问题都有一个固定的模式来产生:

通过select根据某些条件来查询,是否一些条件被满足了.
根据查询的结果,程序继续下一步操作,提交还是取消.
如果程序决定继续运行,就会写入一些数据到数据库里然后提交.

第三步里的写入操作,其实影响了第二步操作的前置条件.也就是说,如果你重复第一步操作,因为第三步的写入已经改变了第一步的结果.事务里的写入操作改变了其他事务里的查询操作结果,这就叫做幻读.

物化冲突

对于上述模式里,如果第三步是修改操作,可以通过在第一步查询时加锁来避免这个问题.但是如果第三步是插入操作,这时第一步里是没办法去加锁的.这时我们需要人工引入锁.

比如,我们提前将可能的插入数据先插入到数据库里,然后将后续的插入操作改成更新操作.这种方式叫做物化冲突,但是如何去物化冲突很难而且容易出错,而且这种机制把解决并发的问题抛向了应用层,除非迫不得已,一般不会用这种方法.

可串行化

隔离级别很难理解,而且在不同的数据库中实现方式还不一致.
面对我们的程序代码,我们很难讲在一个特定的隔离级别下,它是否是安全的.
没有好的工具来帮助我们检测到竞态条件.

为了解决这些问题,终极方案就是可串行化隔离级别,这也是最强的隔离级别.它能够保证事务并行的运行,但最终结果和串行执行是一样的.这种级别下,数据库能够避免所有的竞态条件可能.尽管可串行化那么好,但是为什么我们不用他们呢?主要是因为性能问题,绝大多数数据库采用以下三种方案实现:

按顺序执行任务
两阶段锁
乐观并发控制

我们先从单机来看这个问题,后续再看多节点上的事务.

实际串行执行

最简单的避免并发问题的方式就是抛弃并发,任意时刻只有一个事务按顺序在单个线程里执行.尽管这个方法是如此的明显,但直到2007年左右才被认为是可行的.在过去的30年里多线程被认为是获取良好性能的必要条件,那么什么使得单线程执行成为可能呢?

RAM开始变得足够便宜,于是我们可以大量使用RAM将数据存储在内存里.当所有的事务操作数据都存放在内存里时,事务就可以执行的飞快,而不用等待从磁盘加载数据.
数据库的设计者们发现OLTP事务通常只读写很小数据量的数据.同时长时间运行的分析查询都是典型的只读,可以只运行在一致性的快照里,而不用运行在线性执行的循环里.

设计为单线程执行的系统性能往往比支持并发的系统要好,因为避免了锁的协调开销.但是它的吞吐量受限于单个cpu核,为了重复利用单线程,事务需要区别于传统的形式来构造.

在存储过程里封装事务

早期数据库的事务倾向是,将用户行为的完整流程打包运行,整个过程在一个事务里然后原子提交,很清晰干脆.但是,用户往往不是那么快的做出决定和响应,因此一个事务对应一个HTTP请求.在交互模式下的事务里,很多时间都花费在应用层和数据库的网络传输上,如果我们取消了多线程模式,那么吞吐量将会糟糕透了,数据库大量时间都在等当前事务里的下一个请求,因此这种数据库必须提供多事务并发运行才能维持性能.

因此,单线程线程事务运行系统是不能运行这种交互式的多语句事务.需要应用提前将整个事务代码提交到数据库,这称为存储过程.

存储过程的缺点:

不同的数据库都有不同的存储过程语言,这些语言不同于开发者的编程语言,而且缺少基本的库.
运行在数据库里代码很难管理,相比于应用程序里的代码,很难debug,也比较难以维护版本和部署监控.
数据库比起应用服务器,要对性能更加敏感,因为一个单独的数据库实例要被多个应用服务器使用.一旦一个编写糟糕的存储过程在数据库里运行,造成的影响要被在服务器端造成的影响坏多了.

但是,现代存储过程都开始采用传统编程语言来编写了.使用存储过程和内存数据在单线程里执行全部的事务变得很合理.不需要等待I/O也避免了多并发控制策略的开销,能获得很高的吞吐量.

VoltDB使用存储过程来复制.它在每个副本上执行相同的存储过程,而不是把事务里的写操作从一个节点拷贝到另一个节点.当然这也需要所有的存储过程都是确定的,如果涉及到时间,随机数则需要特殊的API.

分区

但是单线程执行受限于单个CPU核的能力,为了解决这个问题,需要采用分区将数据分不到不同的CPU上.如果我们能找到一种分区方式,使得事务都是执行在单个分区上.只是一旦涉及到跨分区的事务操作,那么数据库就必须跨分区协调事务,而这些存储过程也需要在所有分区上步伐一致的执行,来确保整个系统的串行化运行.这样一来,跨分区事务的协调开销将导致系统很慢.

是否事务能够单分区执行取决于应用程序.简单的kv数据通常能够简单来分区,但是如果数据带有辅助索引,就需要跨分区的协调了.

总结

顺序执行事务在特定场景下可以成为串行化隔离级别的实现手段:

每个事务必须短小快速,因为一个缓慢的事务会停下所有的事务执行.
活跃数据被限制需要符合内存大小.很少被访问的数据可以被交换到磁盘上,但是磁盘上的数据被访问时,系统将会变慢.
写吞吐量被单个CPU核限制,或者可以将数据分区,限制事务在单分区上进行.
跨分区事务也可能,但限制很多.

两阶段锁

实现串行化最广泛的算法就是两阶段锁,两阶段锁和两阶段提交是不一样的.之前我们通过加锁来避免脏写,当事务并发写相同数据时,锁会等待第一个写操作所在事务结束了才会释放.两阶段提交里,写会阻塞读写,读也会阻塞写,这和快照隔离性的实现是不一样的.

如果事务想读取数据,必须在共享模式获取锁.其他事务被允许同时获取共享模式下的锁.但是如果有事务已经获取了数据的排他锁,则这些事务都要等待.
如果事务想要写入数据,必须获取排他锁.只有当数据上不存在任何锁的时候才能获取成功.
如果事务写读后写,那么需要升级共享锁成为排他锁.
事务获取锁后,直到事务结束都需要继续持有锁.两阶段的含义就是第一段持续获取锁,第二阶段释放所有锁.

由于大量锁的存在,导致很容易产生死锁现象.数据库能够自动检测死锁然后取消部分事务,被取消的事务需要应用程序去重试.

两阶段锁的性能

两阶段锁最大的问题就是性能问题.一部分是由于申请和释放锁的性能问题,但是更重要的原因是因为降低了并发度.传统的关系型数据库并不限制事务的持续时间,因为本身就是为交互式应用设计的,因此当一个事务需要等待另一个事务是,并不知道到底要等多久,一个慢的事务或者一个涉及大量数据获取大量锁的事务,会导致整个系统慢到不可用的地步.

死锁问题在基于锁实现的读已提交隔离级别下也会存在,但是在两阶段提交策略下尤其频繁.而当事务因为死锁而取消重试时,所有事务操作又要重新执行,一旦频繁产生死锁,大量无用功导致系统性能很差.

谓词锁

谓词锁和共享/排他锁有点儿像,但是谓词锁不属于特定的目标,而是属于符合查询条件的全部目标. 谓词锁的核心观点就是,可以锁定那些暂时不存在在数据库里的数据,但是将来这些数据可能会存在.这样包含谓词锁的两阶段锁就能避免各种形式的竞态条件问题.

索引范围锁

谓词锁性能不是特别好,当有许多活跃事务需要锁时,查询相应的谓词锁很浪费时间,因此数据库都改用索引范围锁,这是谓词锁的近似形式.索引范围锁不如谓词锁那么准确,可能会锁住更大的范围,但是消耗要小很多,这也是一种很好的权衡选择.如果找不到合适的索引,那么就会将整个表锁住.

可串行化快照隔离级别(SSI)

可串行化快照隔离级别只比快照隔离级别损耗很小的性能.

悲观与乐观的并发控制

两阶段锁是一种悲观的并发控制.而线性执行则是悲观到家了,将整个数据库用一把大锁锁住.而SSI则是一种乐观的并发控制方法,只有当事务提交的时候,数据库检测是否违反了隔离性,如果违反了那么事务就会取消或者进行重试.

乐观并发控制也不是一个新概念了.当数据库竞争比较激烈的时候,就会导致大量的事务取消,如果系统刚好接近最大吞吐量了,那么重试事务的负载就会让系统近乎崩溃.但是如果竞争没有那么激励,并且性能还有很多冗余,乐观并发控制性能还是很好的.

可交换的原子操作可以降低竞争:例如多个事务并发增加计数器,只要计数器内容不在同一个事务里读取,那么自增的顺序就不是很重要.

SSI实现是基于快照隔离,同一个事务中的读取操作都来自一个数据库的一致性快照.SSI增加了检测可串行化冲突的算法.

检测算法

当应用程序作出查询时,数据库并不知道应用逻辑会如何使用查询结果.为了安全起见,数据库需要作出假设,任何查询结果的更改都会导致食物中的写入无效.换句话说,事务里的读写之间可能会有因果关系.因此数据库必须检测出这样的场景,一个事务在一个过期的许可上进行了操作,那么需要被取消.那么数据库怎么知道查询结果变化了呢?

检测到针对陈旧mvcc对象版本的读操作(读之前,有未提交的写操作)
检测到写操作影响了前面的读取(读取之后有了写操作)

检测陈旧的MVCC读:数据库需要追踪由于mvcc可见性而被忽略的其他事务,当事务想要提交时,数据库需要检测下是否有之前被检测的事务已经提交了,如果有,那么当前事务需要回滚.通过避免不必要的取消,SSI保留了快照隔离性来支持长时间运行的读操作.

检测影响前面读取的写操作:数据库使用索引范围来追踪事务读取相关数据的操作,当事务结束后这些记录就被丢弃了.而当事务写入数据库的时候,会检测读取关联数据的事务对应的索引,然后通知相关事务之前的读取操作可能过时了.当事务提交时会查看影响自己的事务是否已经提交了,如果没有提交那么可以自行提交成功.如果已经提交了,那么就得选择回滚了.

SSI的性能

一如既往,算法的具体实现细节决定了实际的性能.例如,追踪事务的读写粒度需要作出权衡.如果粒度足够细就能够精确的控制事务的回滚,但是记录开销也很大.如果粒度比较粗,速度变快了但是可能会导致不必要的回滚.

对比两段锁,SSI最大优势就是一个事务不必被另一个事务持有的锁挂起来.读写之间互不影响,这使得事务延迟在很大程度上是可以预测的.只读操作不需要任何锁,因此非常适应于读很重的事务.

对比线性执行,SSI不局限于单个CPU核.

事务取消的速度很大程度上影响了SSI的速度.因此这就需要读写事务尽可能相当小.当然,就算事务比较慢,SSI也不像两段锁或者线性执行对这种事务那么敏感.

总结

事务是一种抽象中间层,能够将应用程序从并发问题和软硬件故障中解放出来.大量的错误最终简化成简单的事务回滚,然后应用程序可以选择重试.

注意数据库的隔离级别名称,可以看出来主要是针对并发读写操作来制定的.而针对并发写导致的问题,则不同的隔离级别的处理方式是不同的.例如对于脏写,各个隔离级别都能防止,而更新丢失,则不然.

隔离性主要解决的是并发问题,并发问题和隔离级别的对应关系

并发问题	描述	方案	隔离级别
脏写	一个事务复写了另一个事务尚未复写的内容,那么该事务回滚则另一个事务的写入丢失了	加锁,第二个写操作需要等待第一个写操作的事务完成了才能继续	几乎全部数据库都支持
脏读	一个事务读取了另一个事务尚未提交的写入,当前一个事务回滚,读取的数据就是无效的	保留新旧版本,读取始终读取最新提交的版本,新写入的版本提交后会覆盖旧版本	读已提交
读倾斜(不可重复读)	事务在不同时刻读取的数据不相同,因为中间有事务写入提交了	MVCC同时保留多个版本,然后索引采用写时复制的方式	快照隔离性
更新丢失	读取-修改-写入,基于读取的数据修改后写入,在不同事务里因为看不到对方的修改操作,因此会丢失前一个写入	自动检测机制,读取操作手动加锁,使用cas原子操作	部分快照隔离实现可串行化级别
写倾斜/幻读	事务并发按照条件读取数据,然后根据读取的数据分别作出决定,并将决定写入数据库,写入后导致之前读取的数据集变化了	顺序执行事务,两段锁,SSI	可串行化级别

并发读写隔离

|隔离级别|脏读|不可重复读
读倾斜|实现方案| |-|-|-|-| |读未提交|✔|✔|行级读写锁| |读已提交|✘|✔|行级写锁(写阻塞读写,读不阻塞读写,但效率不可接受)
行级写锁(写只阻塞写)+新旧值
行级写锁+MVCC(退化每个查询生成一个快照)| |可重复读(快照级别隔离)|✘|✘|行级写锁or乐观锁+MVCC(整个事务使用一个快照)|

并发写隔离

|问题|方案|隔离级别| |-|-|-| |脏写|行级锁|最基本功能,各种隔离级别都支持| |更新丢失|原子操作:行级锁or单线程执行
显示加锁:数据库不支持原子操作,因此应用层手动加锁
自动检测更新丢失:检测到写冲突中断事务
CAS操作:需要确保读取不是读取的快照|

Read All

leetcode数组相关

2018-04-04

Borui

算法

leetcode 数组
数组最常用的技巧就是首尾双指针，二分和hash表。

Two sum

一般对于无序的数组问题,都需要考虑空间换取时间.

Median of tow sorted arrays

由于是有序的数组,并且题目指定算法复杂度为O(log(m+n)),因此一定是一个类二分法问题.

此外,这题的难点在于将寻找中位数,转变成寻找第k大小的数.又因为保证复杂度为O(log(m+n)),因此就需要保证每次k值减半.

Containers with most water

这道题的关键在于,容器面积的底和高都是变化的,我们需要找到最大的乘积值.

采用首尾双指针的策略,好处就在,寻找过程中底一直在减小(因为双指针不断靠近),因此我们如果想要找到最大的面积,就必须要求高一定要变大.在这个过程中,我们一定会寻找到最大的乘积值.

x*y=n,当x不断变小时,y值的变化趋向向将直接影响n的变化趋向.这样就把两个不确定的变化,转变成了一个不确定的

3sum

这道题可对比两数之和这道题，这里需要陈列出所有答案。如果继续采用空间换时间，那么就需要固定第一个数，然后演变成在剩下的数组中求取特定两数之和。由于数组无序，因此如何排除重复答案就使得编程实现较为复杂。

此时，不如考虑对数组进行排序，排序的复杂度也就是O(nlog n)。然后固定第一个数，通过首尾指针就可以查找剩下两个数。

编程时，考虑重复的数需要有效地跳过。

3sum closest

这道题和上一道题基本思路一致，但是编写上需要细心

4sum

k sum问题一般解法就是先排序，然后k-2层循环+首尾指针

remove duplicates from sorted array

由于是有序的队列，因此直接往前覆盖就行。但是需要注意边界条件

remove element

简单的进行覆盖就好

search a 2d matrix

这道题目的核心在于，如何使得我们每次选择查询的方向是唯一的。

注意数组的特性，从左到右是有序的，从上到下是有序的，而且每行第一个数大于上一行最后一个数，也就是说每行的数都大于上一行的所有数。当前数小于目标时，可以往左走，也可以往上走。而当前数大于目标时，可以往右走，也可以往下走。

根据我们唯一方向的分析，可以组合出两种策略：
1. 当前数小于目标时，往左走；前数大于目标时，往下走。这时我们的最初位置就是右上角。
2. 当前数小于目标时，往上走；前数大于目标时，往右走。这时我们的最初位置就是左下角。
以上。

find minimum in rotated sorted array

首先，还是观察数组的特征：有序，无重复，旋转后的右侧小于左侧值。

针对这种有序无重复的数组，我们一般会先考虑二分法。由于我们的目标是寻找最小值，因此我们需要不断寻找最小值的范围。这里mid我们向下取整，因此当只有两个数时，中间值将是left的值，我们可以单独考虑两个数的情况，如下只考虑大于等于三个数时的情况：
1. mid大于left值，并且mid大于right值，则情况如下：4,5,6,7,0,1,2,3。目标在右侧。
2. mid大于left值，并且mid小于right值，则情况如下：0,1,2,3,4,5,6,7。目标在左侧。
3. mid小于left值，并且mid小于right值，则情况如下：5,6,7,0,1,2,3,4。目标在左侧。
4. mid小于left值，并且mid大于right值，这种情况不可能，mid小于left说明mid处于翻转后的右半侧，右半侧是有序的，mid只可能小于right。
综上，当mid值小于right值，目标在左半侧。当mid大于left值时，目标在右半侧。

find minimum in rotated sorted array ii

这里存在重复的数据了，不过上述的分析还是有效的，但是关于mid与left，right相等的情况，就需要特别考虑了。

当mid=left=right的时候，这个时候最小值可能在任何一个区间里，如1,1,1,0,1或者1,0,1,1,1，因此只能去顺序遍历了。
1. mid等于left值，并且mid大于right值，则情况如下：3,3,0,1。目标在右侧。
2. mid等于left值，并且mid小于right值，则情况如下：0,0,0,1。目标在左侧。
3. mid等于right值，并且mid大于left值，则情况如下：0,1,1,1。目标在左侧。
4. mid等于right值，并且mid小于left值，则情况如下：2,0,1,1。目标在左侧。
search in rotated sorted array

解题报告参考搜索旋转排序数组核心在于，先确定有序区间，然后再做查找判断，对于无法判断是否有序的区间则进行递归查找。

错误1：判断左有序还是右有序的时候，需要>=或者<=，因为mid和left相等或者mid和right相等的时候，也就是说只有一个或者两个元素的时候，左有序或者右有序都是成立的。

search for a range

由于要求时间复杂度为O(log n)，因此可以通过二分分别查找元素的第一次出现和最后一次出现。

查找元素的第一次出现和最后一次出现，编写的核心在于二分时，保证left或者right始终向我们要查找的位置逼近。比如查找第一次出现的位置时，当mid<target，那么left值需要更新到mid+1，这时的left才会时刻往第一次出现的target靠近。查找最后一次出现位置时，需要当mid>target，right值更新到mid-1。

search insert position

二分查找的变种。核心在于找到不变性条件是什么。

spiral-matrix

这道题没有算法难度，但是存在编程难度。

比较精妙的解法是，分别用四个变量来限定边界，然后通过螺旋访问顺序，依次变化边界。

比较通用的方法，就是利用方向数组。

spiral matrix ii

和上面的思路一致，通过螺旋访问数组然后赋值。
Read All
Designing Data-Intensive Applications读书笔记(6)

2018-04-04

Borui

DDIA

读书笔记分布式
- Partitioning
Partitioning

当数据集非常非常大,并且我们需要非常高的吞吐量,我们就需要对数据集进行分片.每份数据都唯一的属于某个数据分区,每个数据分区都是整个大数据集的一小部分.

对数据集进行分区主要是为了可扩展性.不同的分区可以放置在无状态集群的不同节点上,于是一个大的数据集就被放置到许多不同的磁盘上,查询操作被分摊到不同的cpu上.

Partitioning and Replication

分区往往和副本复制在一起工作,最终结果就是不同分区的不同副本分布在不同的节点上.这意味着,一条记录属于一个指定的分区,并且通过存储在不同的节点上来进行容错.

而一个节点上同样存储有不同的分区数据.如果是一个单主架构,那么分区+复制架构如图: 每个分区的leader被分到一个节点上,它的follower被分配到其他节点上,因此每个节点可能是某个分区的leader,也可能是某个分区的follower.

Partitioning of Key-Value Data

分区的目标是想将数据和查询尽可能的均衡的分布在节点上.这样可以得到线性的性能提升.但是如果分配不均匀,例如部分分区分配的数据量过多,则为产生倾斜,极端情况数据都分派到一台节点上,拥有不成比例的高负载的分区称为热点.最简单的方式,就是将节点随机分配,但是这种方法有个巨大的缺点,就是当你想要读取特定数据时,你找不到他在哪个分区上.

Partitioning by Key Range

一种分区方式是,将连续范围的key分配到一个分区里.key的分布不一定是均匀的,因为数据并不一定均匀分布.为了使得数据最终能够均匀分区,因此分区的边界需要根据数据来定.分区的边界可以通过管理员来手工指定,也可以自动来选择.在每个分区里,我们会保持key的有序性,因此我们可以很方便的进行范围查询操作,也可以把kye当做组合索引来查询相关数据(例如key的值是通过年-月-日-时-分-秒这种形式).

不过这种方式的劣势也很明显,就是某种特定的查询模式将导致热点的出现,例如我们的key是时间戳形式,那么我们将频繁写入和查询最近时间戳所在的分区上,而其他分区则都是空闲状态.为了避免这种情况,你需要小心设计key值,key的开始元素可以根据实际情况选定特定分类,这样写入和查询就可以均匀分不到不同的分区上,只是获取某些数据时,需要合并各个分区查询的结果.

Partitioning by Hash of Key

由于存在数据倾斜和热点问题,很多数据库采用hash函数来决定数据的分区.一个好的hash函数能使得倾斜的数据得到均匀的分布.由于只是为了分区,因此key值不需要被强加密,因此md5或者FowlerNoll–Vo函数都可以被采用.许多语言内置了简单hash函数,但不见得适用,因为同一个key值在不同的线程里可能都会有不同的hash值.当选定一个hash函数后,就可以给不同的分区指定不同的hash范围了.分区的边界可以是均匀间隔的,也可以是伪随机的(一致性hash).

一致性hash通过随机选择分区边界来避免中心控制和分布式一致性问题.事实上这种方式效果并不好,很多数据库的文档还称一致性hash其实是不准确的.

不过,通过这种方式,我们没有办法做key的范围查询了,并且分区内的key也不是有序的了.想做范围查询,就需要查询各个分区然后组合结果返回.

Cassandra提供了一种组合两种分区策略的方式,叫做复合主键.复合主键包含若干数据列,只用key的第一部分来进行hash分区,其他的列则用来排序.这样一来虽然无法通过第一列来进行范围查询,但是如果通过为第一列指定特定值,那么通过其他列就可以实现范围查询.

缓解热点

在极端情况下，所有的读写查询都针对一个key到时候，仍然会有热点产生。例如在社交网络里的大v，发表一篇文章，将会得到上百万的读操作。

对于存储系统来说这很难自动去解决数据倾斜问题，因此需要应用层去做。例如在热点key的首尾加上随机数使其被hash到不同的分区里去。但是这会带来一些问题。
1. 读取操作需要从各个分区读取，然后再汇总，增加了工作量。
2. 应用层需要跟踪热点key，从而针对必要的key值进行这种操作。
Partitioning and Secondary Indexes

我们的数据系统并不总是简单的kv系统，只需要通过主key就可以获取所有的信息。我们还需要一些辅助索引来帮助查询。对于关系型数据库和文档型数据库来说，辅助索引很重要。但是对于某些kv系统（例如hbase）由于这会增加系统复杂度而选择抛弃辅助索引。辅助索引有两种实现方式，一种是基于文档的，一种是基于单词的。

Partitioning Secondary Indexes by Document

基于文档的辅助索引，本质上就是每个分区都是相互独立的，只维护自己分区的辅助索引，因此这种方式又被称为本地索引（local index）。但是这种索引方式写入时只需要每个分区维护索引，读的时候就需要从多个分区获取数据并进行合并，这种操作被称为scatter/gather，这使得读取操作很复杂。尽管可以并行从多个分区读取，但仍然存在尾部延迟放大问题。

Partitioning Secondary Indexes by Term

和本地索引不同，我们可以建造一个全局索引（global index），但是我们不能把全局索引保存在一个节点上，这样就会产生性能瓶颈从而违背了分区的初衷。因此全局索引也需要被分区，只不过分区方式和主key不一样。

全局索引分区方式可以类似主key的分区方式，可以基于key的范围也可以基于hash。基于范围可以方便根据辅助索引做范围查询。基于hash则可以得到更好的负载分布。全局索引的好处在于读取操作只需要读取索引指定的分区，劣势在于写入操作会变得复杂，写入一行记录或一篇文章需要更改多个索引分区。

理想情况下，索引应该和数据的更新保持同步。但是对于全局索引这会涉及到多个分区的分布式事务，并不是所有的数据系统都支持。因此实际操作中，辅助索引的更新通常都是异步的。

Rebalancing Partitions

从集群中的一个节点迁移数据到另一个节点的操作被称为再调整。最小的要求是：
1. 重整后，各个节点上的数据仍然是均匀分布的。
2. 当调整期间，系统必须能够继续接受读写请求。
3. 除了必要的数据外没有额外的数据需要迁移，从而保证调整尽可能的快并减少I/O操作。
再调整的策略

之前我们采用hash的时候，也是为hash值指定边界而不是直接对hash进行取模。因为当分区增加或者减少时，取模的结果将和调整前相差很多，从而导致大量的数据迁移，成本太高。

固定分区数量（hash）

我们可以指定超过节点数的分区个数，然后若干个分区指派到一个节点。当增加一个节点的时候，可以将其他的节点上的若干分区指派到新的节点上，从而达到负载均衡。当减少节点的时候，理论如此。这个过程中，只有部分分区的数据需要被迁移，分区的数量没有更改，key到分区的映射也没有更改，更改的只是分区到节点的分配。由于迁移的数据量较多并不是瞬时就能迁移完成的，因此在迁移过程中，分区旧的映射节点仍旧能够接受读写请求。这里可以理解，没有迁移完成的key仍旧由原有节点提供服务，迁移完成的节点由新的节点提供服务，而迁移中的节点可以告知客户端正在迁移。可以通过redis的cluster集群实例来理解：Redis Cluster 分区实现原理

这个方法还有一个优势，就是可以根据不同的硬件能力，给不同的节点分配不同数量的分区。实际中很多系统都是采用固定数量的分区之后就不在更改了，理论上可以分裂或者合并分区，但是固定的分区数量实现上更简单。最好一开始就选定可能的最大值，这需要你预判数据的增长，当然分区也有管理成本因此不适宜设置成太大的值。

当数据的规模非常大且持续增长的时候，分区的数量很难固定下来，因为每个分区包含固定比例的总数据量，随着数据量的增加，每个分区包含的数据量也将增加。如果分区数据量过大，那么重新分配和节点恢复成本就会很大。但是如果每个分区数据集过小，分区数量就会增加，这会增加管理的成本。因此想让数据分区大小合适是很困难的。

动态分区（range）

对于使用key的范围来分区，使用固定的分区数量就不太合适了。因为key的范围一旦预估错误，就会导致有的分区包含全部数据同时其他分区时空的，而重新调整分区配置成本太高。因此对于使用key的范围来分区的数据库，例如Hbase会动态的创建分区。当一个分区的大小增长到预先设置的大小时，就会进行分裂成两个分区，各包含一半数据。如果某个分区大量数据被删或者数据量少于阈值，则会合并分区成一个分区。这有点儿类似B数的操作。

在单机上，有hash，lsm-trees和b-tree索引，在分布式环境则主要是hash和key-range（类似b-tree）

每个分区归属于一个节点，每个节点上存在若干分区。当一个分区过大时会被分裂，分裂后的一个分区会被迁移到其他节点来平衡节点的负载。动态分区的好处就是可以根据数据量来制定分区的数量。不过对于一个空的数据集这会导致只有一个分区，为了解决这个问题需要进行配置来初始化分区，这被称为pre-splitting，这个操作需要对数据可能的分区结构有一个准确的预判。当然动态的分区不仅适用于根据key范围来分区，也适用于hash分区的数据集。

正比节点大小

动态分区下，分区的数量和数据量大小成正比。分裂和合并操作的存在使得分区的大小保持在最大值和最小值之间。在固定分区下，分区的大小和数据集的大小成正比。无论哪种情况，分区数量都和节点数量没有直接关联。于是第三种选择，就是使得分区的数量正比于节点数量，也就是说每个节点有固定的分区数量。当节点的数量不变的话，随着数据量的增加每个分区大小也会随着增长。而当节点数量增加分区的大小就会变小。

当一个新节点加入集群，它随机选择固定数量的现存分区进行分裂，分裂后的分区一半保留在原节点，另一半由新的节点监管。随机的方法可能会导致分裂不均匀，但是当平均分配到较大数量的分区上时，新的节点会得到一个相对合理的负载。

随机选择分区的边界需要基于hash的分区方式。实际上这种方式最接近原始的一致性哈希的定义。

自动化or手工

重分配是自动化还是手工完成呢？这两者之间有一个梯度，完全自动化和完全手工化。实际上很多数据库建议自动化的分区分配，但是需要管理员在分区分配生效前提交分配操作。完全自动化当然是很方便，但是结果是不可预期的，重新分配本身就是成本很高的操作，因为需要重新路由请求和迁移大量数据在节点之间，如果操作不当就会造成严重的后果。尤其是配合故障检测，会导致错误产生。因此最好配合人工去操作。

Request Routing

由于数据分区了，因此客户端想要获取某个分区时怎么知道数据在哪个分区呢？这被称为服务发现，不单单是在数据库系统中。
1. 运行客户端连接任一一个节点（通过轮询来负载均衡）。如果该节点保留有该数据，则直接处理请求。否则将请求转发到合适的节点，然后接收到响应再把响应返回给客户端。
2. 所有的客户端请求先发送到路由层，路由层来决定哪个节点应该处理请求然后将请求直接发送到节点。路由层并不处理任何请求，只是用来做分区发现负载均衡的。
3. 需要客户端来知道分区的分配，从而直接将请求发送到合适的节点。
所有这些方法有一个问题，就是做路由选择的组件如何知道分区到节点的变化呢？有一些协议可以在分布式系统得到一致性但是它们很难实现。

许多分布式数据库依赖于一个独立的协调服务，例如zookeeper来保持对集群元数据的记录。zk上保持有分区到节点的映射，其他的路由选择组件通过订阅zk来获取这些信息，当有分区关系更改时，zk可以通知路由选择组件。

部分数据库使用gossip protocol。请求被发送到任意一个节点上，然后节点负责将请求转发到合适的包含请求分区的节点上。这种方法增加了数据节点实现的复杂度，但避免了外部依赖协调服务。

对于路由层和发送到任意节点这两种方法，无论哪种都需要客户端找到连接的ip地址。由于地址的变更不像分区到节点的变化那么快，因此可以通过dns来加速查询。

并行查询

之前文章都只是提到简单的读写单个key，实际上大规模并行处理（massively parallel processing——MPP）的关系型数据库在查询操作上更加复杂。

总结

本章主要描述了各种分区的方法，当存储数据量较大并且单节点处理数据不再适用的时候，就需要进行分区。分区的目标在于将数据和查询负载分布到多台机器上，避免热点（高负载节点）的存在。这需要选择合适的分区模式以及重调整分区。

有两种主要的分区方法：
1. 基于key范围分区。这里key值是排序的，一个分区包含从小到大的全部key值。排序使得客户端做范围查询成为可能，但是也容易造成热点。这种方法下，分区重分配通常采用将范围分裂成两个子范围的方式。
2. 基于hash分区。将每个key应用hash函数，然后每个分区包含一定hash范围。这种方式破坏了分区内部的有序性，使得范围查询不是很高效，但是使得分区分布更加平均。当时使用这种方式分区时，重新调整通常是采用固定的分区数量，然后将若干分区指派到每个节点上，然后调整时需要将整个分区内容进行迁移。当然也可以采用动态分区方式。
除此之外，还可以采用混合方法，例如使用组合key。使用key的一个部分进行hash分区，其他部分用于排序。

除了针对主key分区，还可以针对辅助索引进行分区。主要有两种方法：
1. 文档分区索引，又叫本地索引。索引和分区数据存在一起，因此写时只需要修改一个分区内容，但是读取时则需要scatter/gather全部分区。
2. 基于词汇索引，又叫全局索引。索引值包含所有分区的主键。当写入文档时，需要修改多个分区上的索引记录，但读取时只需要读取一个分区上的索引记录。
Read All
垃圾收集器

2018-03-23

Borui

JVM

JVM GC
垃圾收集器

系列文章基础知识

CMS垃圾收集器

详解CMS垃圾回收机制

G1垃圾收集器

下文是我看到的比较好的介绍G1垃圾收集器入门的文章.

G1垃圾收集器入门, github版本:G1垃圾收集器入门

深入理解 Java G1 垃圾收集器

G1垃圾回收器详解

Garbage First G1收集器理解和原理分析

JVM之OopMap和RememberedSet 看完这篇文章,有些新的感悟,就是gc roots和可回收的gc roots还是有区别的.因为当进行年轻代回收时,老年代的对象都是有效的,那么被老年代引用的年轻代对象,其实也不可以被回收.

R大的一些回复
Read All

Designing Data-Intensive Applications读书笔记(5)

2018-03-22

Borui

DDIA

读书笔记分布式

Replication

Replication

Replication意味着将一份数据的副本保存在不同的机器上.为什么要备份呢?

保证你的数据更靠近你的用户(用以减少延迟,比如CDN).
当部分数据失效了,系统能够持续工作.
增加可读机器的数量,提供更好的读效率(提高了读操作的吞吐量).

数据的复制最大的困难在于处理复制数据的更新变化,也就是保持副本的一致性.遇到的问题有很多,包括是同步还是一部进行备份操作?如何处理失败的备份?这一章主要讲述了三种备份架构,以及一致性问题.

Leaders and Followers

在多副本的情景下,我们如何确保我们的数据都存在于所有的副本机器上呢?最常用的架构就是leader-based replication,也被称为active/passive或者master–slave replication.

一台副本机器被指派为leader,所有的客户端的写操作请求,都必须发送到leader副本机器上,leader会先把数据写到本地磁盘上.
其他的副本机器被称为followers.leader除了负责将数据写入本地磁盘,还需要将数据的变化发送给所有的followers,一般都是以replication log或者change stream的形式.所有的followers从leader那里获取到日志,然后更新自己本地的数据文件,并且保持和leader一致的处理顺序.
当一个客户端想要从数据库读取数据时,它可以把请求发送给任意leader或者followers.但是写操作必须发送给leader.

需要关系型数据库内置的复制模式就是这种模式.一些非关系型数据库也采用这种模式.不近数据库使用这种模式,就连分布式的消息代理Kafka也采用这种模式.

同步异步复制

复制的一个重要的细节就是,是同步复制还是异步复制.一般复制操作都是很快的,但是很难保证复制操作到底会延迟多久.

同步复制的优势是保证所有的followers都和leader是一致的,就算leader挂掉了,随便一个follower都能顶上.但是劣势也很明显,如果某个follower由于某种原因迟迟没有回应,那么这次写操作就会被阻塞,直至这个follower恢复正常.实际上,同步复制是不可操作的,任意一个follower的故障就会将整个服务阻塞,因此如果你在一个数据库配上设置为同步,通常意味着其中一个follower是同步的,而其他follower的复制操作仍然是异步的.当一个同步的follower不可用的时候,就会将一个异步的follower升级为同步follower,这样做的好处是,始终保证数据存在至少两个节点上,这种方式被称为semi-synchronous.

通常情况下,leader-based模式都是完全异步进行复制.这意味着如果leader发生了故障,会导致一些写入的数据不可读从而丢失了.但是完全异步的复制有这样一个优势,就是就算所有的follower都故障了,leader仍然能够提供服务.弱化数据的保障看起来不是一个好的选择,但是异步复制正在被广泛使用,尤其是有很多follower分布在世界各地的时候.

chain replication是一种异步复制.节点按照链式排列,而不是传统的星状排列.

所有的读操作必须发送到尾节点(primary节点)上.
所有的写操作发送到头结点,然后写入成功操作发送到下一个节点,直至发送到尾节点,由尾节点响应客户端.

新加follower

从leader上复制某个时间点的快照.
将快照复制到新增的follower上.
接着follower需要连接上leader,并且请求快照之后所有的数据变化.这就需要快照指明复制日志的具体位置.
然后follower需要执行快照以后的日志内容,直到追上leader,这个时候就可以正常的工作了.

处理节点故障

follower故障

由于follower都从leader那里同步了复制日志,因此可以很容易的通过复制日志进行恢复.恢复后还需要从leader那里获取故障之后发生的数据变化日志.执行完这些后,follower就能正常对外提供服务了.

leader故障

leader出现故障比较麻烦.首先需要新选择一个follower作为新的leader,然后客户端需要被重新配置,将写操作发往新的leader,最后其他的follower需要从新的leader同步数据.这被称为故障转移.故障转移操作可以是手动的,也可以是自动的,自动的操作如下:

首先需要确定leader是否真的失效了,由于故障原因很多,例如leader崩溃了,断电了,网络问题或者其他.常用的策略就是通过心跳检测,来确认进程是否还活着.
选择一个新的leader.新的leader可以通过一个选举过程选择,也可以是之前的leader指定的.最好是数据变化最接近原来的leader的follower被选为新的leader.如何让所有的节点同意这个新的leader,是一个一致性(consensus)问题.
重新配置系统使用这个新的leader.客户端需要发送写操作到新的leader上,然后旧的leader即使恢复了,也要变成follower,并且认可新的leader.

故障转移过程里伴随着很多异常:

如果采用了异步复制策略,新的leader也许会丢失之前写到旧的leader还没来及发送给其他follower的请求.最简单的措施就是,丢弃这些写操作.
但是丢弃写操作将会导致很多问题,比如主键被重复使用了.
在选择新leader的时候,可能会发生脑裂问题.安全起见,系统应该有一个机制就是自动关闭其中一个leader,保证系统只有一个leader.
心跳的时长该怎么选择呢?如果心跳时长太长,导致故障恢复的时间会变长,如果心跳时长太短,会导致不必要的故障恢复操作.

由于这些问题并不是那么容易解决,因此很多时候,故障转移操作都是管理员手动去操作.节点故障,不可靠网络,节点一致性权衡,持久化,可用性以及延迟都是分布式系统不可避免的问题.

复制日志实现

基于语句的复制

最简单的实现就是,将请求里的操作发送给各个follower,对于关系型数据库,就是将增删改查操作都发送给follower,让follower再执行一遍.尽管这个方法听起来很靠谱,但是操作起来就会发现问题.

如果执行语句中包含非确定的函数,例如now(),rand(),那么数据肯定就不一致了.
如果执行的语句需要依赖数据的当前状态,那么执行的顺序就非常重要了.一旦要求了执行顺序,那么并发执行事务就会很麻烦.
有些执行的语句包含有副作用.除非这些副作用是确定的.

实际上,也不是没办法解决,对于那些非确定的操作,leader提前将这些操作的结果写回来替代这些操作.不过,其他的复制方法更好,所以不采用这些方法.

预写日志的方式

leader可以将预写日志发送给follower,然后让follower重复执行日志内容.主要的问题在于,这些日志内容都是二进制格式,并且与存储引擎紧密相关.因此如果主从机器上的存储引擎版本不同,都有可能导致复制问题.这看起来是个小问题,但是想一下,如果版本是可以兼容的,那么我们可以做到无宕机升级操作,但是如果版本不兼容,那么我们不得不进行停机操作进行升级更新.

逻辑日志方式

逻辑日志是为了和物理引擎的数据表达格式进行区分.一行逻辑日志内容,通常就是数据库里的一行数据.

对于插入的行,那么日志内容包含每列的最新数据.
对于删除行,日志包含标识该删除行的信息.如果有主键还好,没有主键的情况下,删除行的数据需要被记录下来.
对于update操作,日志包含唯一标识改行的信息,并且包含更新的数据信息.

事务往往会更改多行数据,因此还需要记录事务提交的标识.binlog就是采用这种方式.由于逻辑日志与引擎内部实现无关,因此很容易做到向后兼容,因此避免了预写日志复制的问题.被用于建立数据仓库,索引和填充缓存.这种技术被称为CDC(change data capture)

基于触发器的方式

有些时候,我们只希望复制部分的数据内容,这个时候我们就需要把复制工作上移到应用层来实现了.我们可以利用数据库里的触发器和存储过程来实现.当发生数据变更时,触发器被触发将执行指定的存储过程,将响应的变更写入其他的数据库里.但是这种方式也会带来额外的工作量,并且容易导致更多的bug.

复制日志的问题

我们需要复制操作的一个原因,就是为了能够容忍部分节点故障.当然还有扩张性和低延迟的考虑.主从结构中,写操作都只能到主节点上,读操作可以到任意节点.对于读操作多,写操作少的应用来说,设置很多follower能够极大的提高应用性能.当然在这种场景下,主从结构必须采用异步复制的模式.

然而,既然应用的读是从异步follower上读,那么就会出现follower上的数据落后于leader.因此当发送同一个请求到leader和follower上,就会发现结果可能会不一致,当然如果停止写操作然后等一会儿,follower慢慢会追上leader,然后两者的数据最终会完全一样.这被称为最终一致性(eventual consistency).最终的意思其实就是说,不清楚到底何时会达到一致.一般来说,这个延迟很小,但是如果发生了节点故障或者网络问题,那么这个延迟有可能会很长.当延迟很明显的时候,就会导致一些问题.

写后读一致性.

想象这样一种场景,你提交了一个写操作到leader节点,随后你预览你的写操作,请求被打到了follower上,由于复制延迟,你看不到你提交的写操作.这种被称为read-after-write一致性.

当读取有可能更改的数据时,应该选择从leader节点返回数据.而数据是否可能更改,需要你自己提前去测试.
但是如果应用中所有的操作都可能变化,那么1就不具备可操作性了.这个时候可以选择,在提交写操作后的一段时间内,所有请求都发往leader节点.或者根据可观测的复制延迟,来选择这个时间.
也可以选择让客户端记录最近写操作的时间戳,当请求发送到follower时,只返回时间戳大于写操作时间戳的结果,如果没有就把请求转发给其他副本.或者可以等当前副本满足条件了再返回结果.时间戳可以使用逻辑时间戳(自定的序列号)或者实际系统时钟.
如果副本部署在不同的机房,那么还必须保证发送到leader所在的机房.

当请求来自不同的设备的时候,这个问题会更棘手.因此又衍生出cross-device read-after-write一致性:

不同设备只能记录自己更新的时间戳,没办法获知其他设备的更新时间戳.因此更新时间戳这种元数据还得提供一个中心化的服务来管理.
如果数据分布在不同的机房.那么不同的设备就有可能被分配到不同的机房.那么你需要强制一个用户所有的设备的请求都分发到一个机房里.

单调读一致性

由于读请求会被分发到不同的副本节点上,这会导致前一个请求获取到了数据,后一个请求就没数据了.单调读一致性比强一致性弱,比最终一致性强.

为了保证单调读一致性,就需要保证请求始终发到同一个副本节点上.

一致前缀读一致性

这种一致性要求,读取的顺序必须和写入的顺序是一致的.如果数据库没有分区,那么这种一致性很明显是满足的,但是对于有分区的分布式数据系统,某个分区内部是有序的，但是不同分区之间是无序的。

一种解决方案，是使得有因果关联的写操作都写入同一个分区，但并不是总能做到，因此需要一些算法来跟踪这些因果关联的写操作。

日志延迟问题

当我们工作在最终一致性的系统上时，我们应该思考这样一种情况，当日志复制的延迟增大时，我们的系统还能正常工作么？如果不能的话，那么我们需要依赖一个更强的一致性保证。日志的复制是异步的，而不是我们认为的同步，这是问题出现的根源。

我们可以通过应用层手段来提供更强的一致性，但是这会使得程序变得复杂而且容易出错。或者我们干脆让事务来简化我们的应用层实现，但是分布式的事务受制于性能和可用性，因此最终一致性成为分布式应用系统的最终选择。

Multi-Leader Replication

上一个主题是单主架构，这个架构有个明显的缺点，就是只能写主，如果主节点挂掉了，那么你就不能再写了。因此为了解决这个问题，可以增加主节点形成多主结构。

多主复制场景

在单机房里面部署多主节点，实际上没有什么意义。多主带来的问题和复杂度远比带来的好处多。

多数据中心

我们部署数据库的时候，有时候会部署多个数据中心（也许是为了容错一个数据中心崩溃，也许是为了让数据离用户更近）。每个数据中心都是单主架构，然后多个数据中心之间的主节点之间进行同步数据。

属性	对比
性能	单主节点中，每个写必须连接到主节点所在的数据中心，因此会增加延迟。多主架构中，写操作直接到达本地数据中心的主节点，之后异步同步到其他的数据中心，因此速度上会更快
容错率	如果主节点所在的数据中心故障了，其他数据中心的follower会成为新的主节点。多主架构中，各个数据中心独立运行，副本复制可以等到故障数据中心恢复回来
网络问题	数据中心之间的数据传输走的是公共互联网，稳定性远不如局域网。单主架构对于网络延迟很敏感，网络问题导致同步写操作会很慢。多主节点因为不同数据中心之间是异步复制，因此能很好的容忍网络不稳定。

多主架构有点很多，但是有个很大的问题，就是不同的数据中心会出现并发写问题。需要处理写冲突问题。此外还有自增长主键，触发器以及完整性约束也是个问题。

离线操作

此外，当应用需要在没有联网的情况下工作，也可以采用这种架构。例如多个设备上的app，当离线的时候也应该能够使用，然后再次联网的时候和应用服务器进行同步操作。每个app上的本地数据库可以看做leader，然后后台异步进程进行同步数据。这种场景可以看做是非常极端的多数据中心情况。

协同编辑

实时协同编辑应用运行用户同时编辑一个文档。这种场景其实不是一种数据备份问题，但是和离线操作场景有很多共同点，当编辑文档的时候，文档状态存储在本地，然后异步和其他人进行同步。如果你想保证没有冲突，那么就需要一个同步锁，当一个人编辑时其他人不可编辑，就类似单主架构了。但是为了更快的编辑效率，那么就需要允许大家共同编辑，但这就需要解决冲突问题。

处理写冲突

如果都提交成功了才发现冲突，这个时候再通知用户就太晚了。如果检测完是否有冲突后，再告诉用户是否成功，那么就失去了多主架构的优势。因此如果采用同步的冲突检测，还不如使用单主架构。

冲突避免

避免发生冲突时解决冲突的最好方法。例如单个用户的请求始终发送到某个数据中心，这样就避免了冲突。整体上是多主架构，但是单个用户来看这是单主架构。但是这并不总是有用，例如一个机房崩溃了或者用户搬家了，还是会出现并发写的问题。

收敛到一致性状态

冲突会导致数据不一致，因此我们需要一些方法，使得数据最终一致。

给定每个写操作一个唯一ID，然后最大的ID就是最终的结果。如果我们使用时间戳，这也就是LWW（last write win），当然这个方法会导致数据的丢失。
给每个副本一个唯一的ID，然后大ID的副本数据始终优先于小副本，很明显，这同样会导致数据丢失。
将数据按照字典序连接起来。
保留所有的信息，然后交给客户端去处理冲突。

冲突解决逻辑

解决冲突最合适的方式就是根据应用来定，有很多工具依赖应用程序来解决冲突。

写时解决：当数据库系统发现冲突时，会执行冲突解决代码。这个代码是管理员提供的而且需要快速在后台执行。

读时解决：但冲突发生时，所有的信息被记录。当下一次数据被读取的时候，都发送到客户端，然后交由客户端解决冲突并写会数据库。

冲突解决的规则会变得越来越复杂，例如亚马逊发现购物车冲突时，只会增加购物车而不会删减。已经有一些自动解决冲突的算法，但是还都很不成熟。

什么是冲突

有些冲突很明显，比如同时写同一个属性值。然而有些冲突比较微妙，例如会议室预定系统，预定前都会查询会议室的可用性，但是由于存在于不同的数据中心，因此很有可能会发生冲突。

多主副本拓扑

副本拓扑描述了写操作传播的路径。 Figure 5-8. Three example topologies in which multi-leader replication can be set up

大多数拓扑结构都是all-to-all结构。在环形结构和星状结构可能会存在循环复制，为了避免循环复制，每个节点给定一个唯一标识，然后每个写入请求会携带所有经过的标识，当一个节点收到请求时，如果发现了自己的标识，那么这个请求就会被忽略掉。此外，这两种拓扑结构中，如果存在任一一个节点失败了，就会中断复制路径需要等待人工恢复。因此all-to-all结构应用比较广泛一些。

但是all-to-all结构也会出现问题，因为有些路径快一些有些路径慢一些，会导致同一个节点接收到不同的请求顺序。通过时间戳是不可取的，因为不同节点上的时间戳有可能是不一致的。大部分多主数据库是不提供冲突检查的。

Leaderless Replication

在无主架构中，客户端发送写入请求到若干个副本上。那么当进行读取的时候，同样会将读请求并发地发送到若干个副本上，然后通过version numbers来选择最新的数据。

读时修复与反熵

有两种机制用来修复重新上线的副本节点数据。

读时修复。当客户端从若干副本节点读取到数据后，进行合并然后将最终的数据写回到副本节点。这种方法比较适合读取频繁的场景。
反熵进程。数据库有一个后台进程持续观察副本之间的数据差异并进行复制。不同于单主架构中的副本日志，这个进程在复制操作中是没有任何特定的顺序的，并且数据有延迟。

Quorums机制

如果有n个副本，每个写入请求必须保证有w个节点成功，我们读取的时候至少读取r个节点。只要w+r>n我们就认为最新的数据已经被读取到了。因为至少有一个节点既写入成功了，也被读取到了。符合这个条件的读写操作被称为Quorums读写。如果想要写的时候快一些，那么只需要w=1，那么r=n。如果想要读时快一些，那么就需要w=n，那么r=1。这里注意，一个集群当中存在不止n个节点，但是某个指定的数据只存在于n个节点上。

Quorums一致性的限制

通常w和r会选择超过n/2的节点数，这样就能确保容忍最多n/2个节点失败。当然也可以选择更小点的数，一方面很有可能读取到过期的数据，但另一方面可以得到较低的延迟和更高的可用性。即使满足了w+r>n，也存在一些问题：

如果一个sloopy quorums，例如写入的w个节点和读取的r个节点是完全不同的节点，那么他们之间就不存在重叠的节点了。
如果两个写操作同时发生了，那么哪一个先发生呢？那么这个时候需要合并并发写入的操作。如果根据时间戳来判定，那么写请求有可能会因为时钟偏移而丢失。（这也是接下来要说的问题）
如果读写操作同时发送，那么写入只是发生在部分副本上，读取操作返回的是旧值还是新值呢？
如果一个写操作，在一部分副本上写入成功了，而在另一部分的副本上写入失败了，并且成功的节点数少于w，在成功的节点上也没有回滚操作。那么这就意味着如果写入失败了，那么接下来的读取操作有可能返回写入值，也有可能不返回。
如果一个保留有新值的节点失败了，恰巧从一个保存旧值的节点上进行了恢复，此时保留有新值的节点数不足w个，因此新值就丢失了。
尽管一切都正确运行了，但由于时延可能会有一些边界情况发生（由于时延，写入操作在读取操作之后才到达服务器）

因此，尽管Quorums机制保证了会有一个读取时最新的值，但实际上并不是那么简单。实际操作中，尽量避免使用这种方法，它只保证了最终一致性，而对于之前提到的各种一致性是不支持的。

监控

我们应该对过时的数据返回进行监控,从而能够及时排查到原因.对于单主系统,通常会有针对数据延迟的度量数据产出,然后给定监控系统进行监控.由于单主系统中,写入是有序的,因此通过对比主从节点的复制日志内容,可以估算出差异.但是对于无主模型,这样的监控有点儿困难.

Sloppy Quorums

对于无主的架构,可以容忍个别节点失败变慢并且无需进行故障恢复.w+r>n的特性使得无主架构具备高可用性和低延迟,并且能够容忍临时的旧数据.但是,Quorums机制并不能够容错,如果因为网络原因导致客户端无法连接服务器,那么就会导致w和r都达不到要求数据量,因此客户端无法正常工作.当在一个很大的集群环境下,客户端只能连接到部分节点,而且这些节点并不是包含当前指定值的节点,这个时候就需要一个权衡:

返回error信息.
接受写请求,忽视原来值存活的节点.

后者就会引发sloppy quorums问题,就是说读写个数都满足必须的w和r个,但是读写处理的节点并不全是存储有指定数据的那个n个节点.举个例子,比如你把自己所在自己家门外面了,然后你跑到邻居家敲门问问能不能借宿一宿.而当网络恢复了正常,那么写入到临时节点的请求就会被发送给原来的指定节点上.这叫做hinted handoff. sloppy quorums能提高可用性,但可能会读取到过期的数据.因此,sloppy quorums只能保证数据被持久化,在数据回写完成前,无法保证能读取到最新的数据.

多机房部署

Cassandra和Voldemort在多机房部署中,n个备份存在于各个机房里,可以通过配置设置各个机房里具体的备份数.所有的写操作被发送到全部备份节点上,但是只需要等待本地机房节点的ack响应.因此可以很好的降低延迟和容忍跨机房的网络中断.而其他机房的写入操作可以异步完成.

而Riak则将n限定在一个本地机房里,然后跨机房的备份节点之间在后台进行异步备份,这和多主结构很相似.

并发写操作

无论是在读时修复还是回写时,都会存在并发写冲突的问题.

happens-before和并发

当B操作依赖于A操作的写入时,我们说B causally dependent A.
当A操作和B操作之间没有任何依赖时,我们认为他们属于并发操作.

因此只要你有两个操作,要么A先发生于B,要么B先发生于A,要么A和B并发.如果存在先发生的关系,你们后发生的操作就应该覆盖先发生的操作,但如果是并发操作,那么我们就需要解决冲突问题.由于分布式系统时钟不同步的问题,因此并发操作和时间没有必然联系.如果说两个操作互相无感知,那么这两个操作就是可并发的.我们需要一个算法来告诉我,两个操作是否是并发的.

这个算法可以这么操作

服务器端为每个key维持一个版本号,每次这个key被重写时就增加版本号,并将新的版本号和值一起保存起来.
当客户端读取一个key时,服务器返回最新的版本号和所有的数据值.也就是说客户端在写之前必须读.
当客户端写入一个key时,请求里必须包含之前读取的版本号,也必须负责合并之前读到的数据值.
当服务器接收到带有特定版本号的写请求时,就可以复写相同版本号或者更低版本号的值.但是必须保留更高版本号的值.

合并值最简单的方式,就是根据版本号和时间戳,但这样会丢失部分数据.还可以取数据值的并集.但是如果允许删除操作的话,就不能只是取并集了,一般删除的时候不会直接进行删除,而是使用一个占位符来指示该值被删除.

版本向量

针对多个副本,需要为每个副本上的key都保持自己独立的版本号,从而形成了版本向量.

总结

副本机制的存在是为了:

高可用性:保证即使在一台机器故障的情况下,系统仍然能够提供服务.
无连接操作:允许应用在网络故障下继续工作.
延迟:将数据存放在离用户更近的位置,加速用户的访问.
可扩展性:通过将读取请求分发到不同副本,提供更高的读取性能.

尽管只是将相同数据的副本保存在多台机器上,却带来了一系列问题,例如并发问题等等.

副本架构有三种:

单主架构:所有客户端将写请求发往主节点,主节点将数据更改操作同步到从节点.读取操作可以发往任一节点.
多主架构:客户端把请求发往任一一个主节点上,然后主节点间进行同步.
无主架构:客户端把请求发往一些节点,并且并行的从一些节点读取数据,来规避读取到过期数据的问题.

每种架构间各有千秋,单主节点很流行因为它很容易理解,并且不存在冲突的问题.多主节点和无主节点更加鲁棒,在应对节点故障,网络分区和延迟峰值问题上.

副本的复制可以是同步的,也可以是异步的.当出现故障时复制方式有很大的影响.当系统顺利运行时,异步复制会更快,但当复制延迟增加并且主节点故障了,这时就会丢失一些已经提交的数据.当复制延迟出现时,会出现一些一致性问题:

读写一致性:用户总能看到他们已经提交的数据.
单调读一致性:当用户看到某个数据后,不应该看到该数据更早的版本.
一致前缀读取一致性:用户会看到因果颠倒的数据.

最后就是并发问题,在多主架构和无主架构,因为允许并发写操作到不同节点,因此会产生冲突.我们提供了一个算法来甄别是否多个操作是并发的,还是有依赖关系的,并且提供merge操作来合并冲突数据.

Read All

Designing Data-Intensive Applications读书笔记(3)

2018-03-21

Borui

DDIA

读书笔记分布式

Storage and Retrieval

Storage and Retrieval

上一篇读书笔记,讲述了数据模型,而本篇笔记主要记录了这些数据模型是如何实现的,也就是存储引擎的实现原理.

数据库本质上就是要做两件事情,存储数据,提供查询.我们作为应用程序开发者为什么要了解数据库是如何存储以及如何查询呢?两个方面,第一,我们需要从众多的引擎中选择适合我们应用的实现,从而更好的实现我们的功能.第二,我们需要了解原理和机制,从而能够进行调优.

存储引擎从本质上来说,主要有两大类别:log-structured和page-oriented

一个简单引擎例子

通过bash实现一个很简单的数据库引擎.

#!/bin/bash
db_set () {
    echo "$1,$2" >> database
}
db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

数据的写入始终采用追加到文件末尾的方式,因此效率很高.磁盘的顺序读写吞吐量很可观

log用来指代顺序追加的记录序列

查询时则是顺序遍历每行数据,然后返回最新的数据行,因此效率不是很高.为了提高查询的效率,因此我们需要引入索引这个概念.索引通过保存一些额外的数据,加速定位我们需要查找的数据项.索引对于原始的主数据来说,是额外的记录信息,因此增加,修改或者删除索引,对于原始主数据是没有任何影响.

顺序追加文件是写数据的最有效的方式了,没有什么好的改进措施了.因此增加索引其实会降低写入的效率,因为在写入数据的同时,还需要维护索引信息.因此,我们必须谨慎选择索引,从而达到最佳的收益,平衡读写的问题.

Hash索引

针对KV数据库的Hash索引,是比较容易理解的索引结构,我们先从它开始认知索引结构.

Bitcask将全部的key以及对应的value位置,保存在内存中,作为系统的索引.因此这种引擎结构,比较适合针对某个key,有大量频繁更写操作的场景.

磁盘限制

我们上文的例子里,都只是往一个日志里追加内容,那么很容易导致文件越来越大,超过磁盘大小.因此我们需要优化我们的方案:

将整个log文件,划分成不同的段,每段限制大小.一旦超过大小限制,则追加到新的段文件中.
由于我们会追加重复的key值,因此可以通过compaction,合并相同key值,保留最新的value值.
通过compaction,段文件会变小,这时可以通过合并段文件,减少段文件的个数.
由于log文件是采用线性追加的方式,因此我们将合并的段文件内容,统一在后台写入到新的段文件里,读取操作还是读取旧的段文件.等到合并操作完成,我们使用新文件替换旧文件.

其他细节

问题	方案
文件格式	采用二进制安全的方式,而不是可阅读的格式
删除记录	给定key设置特殊的value值,来指定该key对应记录被删除
故障恢复	可以通过段文件,恢复索引值.或者实时持久化索引文件,来加速恢复
部分写	文件追加到一半挂掉了,Bitcask通过crc校验来保证数据的完整性和正确性
并发控制	这里采取的策略是只有一个写线程,然后文件只能追加,不能更删

追加文件而不是本地更新数据是不是有些浪费磁盘资源呢?实际上并不是:一来,对于硬盘来说,尤其是机械硬盘,线性追加写的效率要远远高于随机读写的效率.其次,对于追加操作,极大地简化了并发和故障恢复方案.最后,通过compaction(也是线性追加操作)操作,是可以释放磁盘空间,减少磁盘碎片的产生.

当然Hash索引也是有自己的问题的.首先,hash索引存在于内存中,因此如果你有很多的key时,内存容量会成为瓶颈.而如果使用磁盘来存储索引结构,就会造成大量的I/O操作,降低了查询速度.其次,hash索引只能用于单key的查询,无法支持范围查询.

SSTables和LSM-Trees

上文中说道,Hash索引无法进行范围查找,倘若我们能保证我们的key是有序的呢?由于我们是追加文件的操作,文件上无法进行排序,因此我们可以将排序工作放到内存中来.

优势:

在compaction的时候,即使文件超过了内存限制,因为文件内容都是有序的,因此可以采用多路归并排序.当遇到相同key时,由于文件有时间范围,取最新的文件内容作为最终的值.
在查找的时候,不再需要将全部的key都保存到内存里做索引.由于文件都是有序的,因此只需要保存每个文件的范围,然后直接跳到相关文件中查找就行了.也就是说我们只需要一个稀疏索引
针对部分作为整体被写入查询的记录,可以组合并压缩作为整体写入磁盘.这样极大的减少了I/O操作.

SSTable实现过程

当写入数据时,首先写入到内存中,内存中采用平衡树(跳跃表)结构保证key有序,该结构称为memtable
当memtable大于一定阈值后,memtable会被持久化到磁盘上,作为最新的SSTable,而且是有序的.新的数据,写入到新的memtable中.
查询的时候,先查询memtable,再依次按照时间新旧查询SSTable.
通过compaction来删除重新和删除的数据.

然而这里有个问题,就是一旦系统突然崩溃了,那么最新的写入memtable的数据就全部都丢失了.为了防止这个问题.

在写入内存数据前,顺序写入一个日志文件.当memtable持久化到硬盘后,删除对应的日志文件,为新的memtable准备新的日志文件.

这套体系最初来源于LSM-Trees.Lucene,ElasticSearch,Solor都采用相似的结构存储索引文件.

实现优化

由于查询操作需要多次查询,因此可以采用布隆筛,来确认一个key是否存在于数据库中.
size-tiered:Hbase采用这种方式,新的小的sstable被合并到旧的大的sstable中.
leveled: 每个sstable都很小,然后旧的sstable被放到下一层次中.

B-树

B-树基本上是关系型数据的标配引擎实现.

B-树是基于块或者页来实现的,通常是4KB或者更大.每个数据页通过物理地址进行标识,这些标识类似于内存里的指针.任何key的查找,都需要从B-树的根节点进行查找.每个叶子节点包含一些key和标识,这些标识中间的key值,代表了这些标识指代的key值空间范围.叶子节点里,往往包含有具体存储的数据,或者真实数据存在于哪个页中.

具体实现时,B-树的分支系数往往高达好几百.并且当进行数据更改时,直接找到数据页的位置,然后本地进行修改,之后再写回磁盘.为了防止数据崩溃,导致更改丢失,需要在写入页之前先写入write-ahead log(也叫作redo log),这也是一个只允许追加的文件.

实现优化

一些数据库采用写时复制的机制,而不是写入redo log重写数据页的方式.
为了节省页空间,可以不用保存全部的key值,只要提供足够的信息能说明key值范围就行.减少key值大小,使得一个页空间能存更多的key值范围.
尽量保证叶子节点的数据页在磁盘上是顺序的,因为很多时候,需要读的数据范围,可能包含多个叶子节点,顺序的读有利于提供效率.
每个叶子节点和兄弟节点相连,这样在顺序扫描key值时,就不需要再从根节点查找了.
使用分形树索引,分形树索引和B-树很像,不同点在于,每个节点附带有一个缓存队列(FIFO队列),队列里包含了所有的写操作.因此分形树写入很快,只需要将操作追加到缓存队列里.而读的时候,需要将从根节点到叶子节点上的缓存队列操作都执行完毕,才会返回结果.

B-树和LSM-Trees

一般来讲,LSM-Trees写入更快,而B-树读取更快. SSD硬盘采用log-structured算法,将随机写变成顺序操作,因此两种写入模式影响不是特别大.但是在有限的磁盘带宽下,较少的写入以及减少磁盘碎片仍然还是有优势的.

	优势	劣势
LSM-Trees	磁盘利用率更高	1.写入放大,由于compaction和merge的机制.写磁盘的次数越多,在有限的磁盘带宽下,每秒的写入数量越少. 2.compaction操作会阻塞正常的读写操作. 3. 当写入的速度大于compaction的速度时,就会导致磁盘大量被占用,查询速度变慢.
B-树	运行极为稳定	1.数据写入必须写入两次,一次写入redo log,一次写入数据页. 2.会产生磁盘碎片

辅助索引

由于辅助索引里存在多个kv值,因此两种方式实现:

key对应一个value的list
为key增加一个唯一标识来保证唯一性.

辅助索引实现

我们在建立索引的时候,key是用来查找,而value可以包含两种值:一种是实际的数据行.另一种是数据行的引用,在这种方式里,数据行所在的文件被称为heap file,数据行不需要特定的顺序,可以是追加写入的,也可以保存删除数据的记录.后一种方式的好处是,数据始终存储在原地,而我们可以建立多个索引,每个索引值都指向同一个位置.

当更新一个数据的时候.如果新值不大于旧值,我们可以直接在heap file上进行原地修改,索引文件都无需修改.而当新值大于旧值时,要么我们需要更新所有的索引,要么原来的旧值变成一个指向新值的引用值.

从索引再到实际记录,很影响读的性能,因此最好能直接存储数据行,这被称为clusterd index,而辅助索引的值都只是保存聚合索引使用的主键.还有一种索引,介于两者之间,被称为covering index或者index with included columns,这种索引的值只保存了部分数据列.不管哪种索引,都能加速我们的查询,但也给我们的写入带来了格外的工作量.

多列索引

多列索引(concatenated index),其实就是把多列值按序追加组成一个key来建立索引.

全文查找与模糊索引

Lucene存储的时候,使用了一种类似SSTable的结构.但索引则是采用类似字典树的结构.

内存数据库

有很多内存数据出现.为了防止服务崩溃数据丢失,可以采取如下措施:

使用特殊的硬件(有电池供电的内存)
将更改日志写入磁盘.
将快照写入磁盘.
备份内存状态到多台服务器.

虽然会写入磁盘数据,但是内存数据库只是用磁盘来备份数据,读写操作还都是基于内存的.内存数据库的读写速度远远高于磁盘数据库,这并不是因为他们都是基于内存操作,实际上由于操作系统会缓存磁盘块,因此实际上很多时候磁盘数据库的操作也都是在内存里.主要的速度差距来自于,内存数据库不需要将数据编码成可以持久化的格式.

由于基于内存,所以内存数据库可以提供更加丰富而强大的数据结构.通过磁盘交换,内存数据库可以存储远超过内存大小的数据,这种方法叫做anti-caching,在适当的时候将内存数据缓存到磁盘上.这类似操作系统的虚拟内存原理,但是数据库可以比操作系统更有效的管理内存.不过,这种方法仍然要求索引文件必须小于内存限制.

OLTP与OLAP

属性	OLTP	OLAP
主要读模式	每次查询都是少量数据,按照key进行查询	汇集大量的记录数据
主要写模式	随机写入,来自用户的输入数据	批量导入或者事件流
主要用途	终端用户,web应用	内部分析使用
数据需求	数据的实时状态	历史数据
数据规模	GB	TB

数据仓库

数据仓库作为独立的系统,不会影响OLTP系统的操作.数据仓库的数据都是来自各个OLTP系统的只读数据,并被转换成分析有好的格式,然后加载到数据仓库里的.这个过程被称为ETL(Extract-Transform-Load).将数据仓库独立处理,可以很好被优化从而更有效的进行数据分析.

数据仓库通常都是关系型数据库,因为sql很适合做分析使用.虽然都提供sql查询,但是数据仓库和OLTP数据库的内部实现是不同的,都为了更好的提供各自领域的功能,做了不同的调整和优化.

数据仓库的Schema

star模型是最常用的模型,一般都是一个fact表在中心,然后dimension表在周围.类似星状.

Figure 3-9. Example of a star schema for use in a data warehouse.

与star模型类似的叫做雪花(snowflake)模型.雪花模型里,dimension进一步被分割成subdimensions.而星状模型更简单更容易用来分析处理.无论哪种模式,基本上都是以大宽表的形式进行存储.

列存储

在数据仓库里,中心表可能会有上亿行数据,pb级别的数据量,因此存储和查询都是个大问题.而周围的表则要小得多,因此我们需要想办法处理中心表的问题.事实上,虽然中心表很宽,但每次我们查询和分析时往往只关心部分列数据,而不是全部数据.

传统的OLTP数据库都是行数据库,所有数据一行一行的存储.在处理查询部分列数据的问题时,仍然需要将一整行数据查询加载到内存里,然后再处理过滤,返回我们需要的列.而列数据库则是将一列一列的数据存到一起.列结构需要保证每个列文件里数据的排序必须和数据行是一致的,在查询某一行数据时,就需要分别从列文件里查询对应顺序的数据,然后组合成这一行数据.

Figure 3-10. Storing relational data by column, rather than by row.

列压缩

除了减少加载的列数,还可以进一步压缩数据来增加磁盘的吞吐量.由于每一列的数据类型是一致的,因此可以根据不同的数据特征选择压缩方式.在数据仓库里最常用的压缩技巧就是bitmap encoding.通常来说,一列中存储的不同数据个数远远小于数据行数.当不同数据个数很小时,我们的bitmap只需要很小的位数.而当个数较大的时候,意味着0值很多,这个时候我们可以使用run-length编码.

Hbase实际上不是列存储数据库,因为Hbase存在column families的概念,在一个family里,数据还是按照行存储的,并且附带着行键,而且也不进行列压缩.

数据仓库在查询时,往往需要查询海量的数据,因此磁盘带宽是一个很大的瓶颈.除了这个,cpu缓存带宽也是问题,因此需要减少分支错误和bubbles,并且充分利用cpu的SIMD能力.

列存储和压缩减少了从磁盘读取的数据量,提高了磁盘的吞吐量.压缩的数据可以加载到L1缓存里进行遍历,这里没有函数调用,比代码里处理的效率搞多了,压缩的数据也使得更多的数据行可以加载到L1缓存里.此外压缩的列数据可以直接进行位操作.这种操作被称为矢量处理.

列存储排序

由于要求每一列数据拥有和行一致的序列,因此数据的有序性需要管理员提前设定.需要根据经验,把最经常用来查询的列作为第一排序列,当然也可以指定第二排序列,第三排序列.排序除了方便查询,还能够提高压缩的效率.当第一排序列没有多少不同值时,排序使得相同的值排在一起,因此使用简单的run-length编码,可以得到很高的压缩率.尽管这可能会使得第二第三排序列变得混乱,但第一排序列极大得到压缩也是值得的.

列存储写入

列存储的写入,需要类似LSM-Trees,所有的数据先写入内存中,然后再持久化到磁盘上,并通过合并写入新的文件.查询的时候,也得先查询内存,再查询磁盘.

数据魔方与物化视图

由于在做数据分析时,常常会需要一些聚合结果.可以将这些聚合结果持久化成为真正的表格.由于聚合结果需要被更新,因此这使得写入操作变得更加复杂,但是这种物化后的视图,能极大的提高读能力.

总结

OLTP总是面向用户的,因此会有大量的请求.通常针对每次请求,应用程序只涉及到少量的数据,并使用索引键来查询数据.磁盘的寻道速度通常是这类应用的瓶颈.

数据仓库以及其他相似的数据系统,通常大量应用于公司的商业分析上,而不是面向终端用户的.这类系统的请求量并不大,但每次请求都涉及到海量的数据,因此磁盘的带宽是这类应用的瓶颈.因此列式存储逐渐成为流行的解决方案.

OLTP数据系统通常有两类引擎:

log-structured类,只允许追加和删除文件,但不允许更新文件内容.
update-in-place类.将磁盘看做可以覆盖的数据页集合.B-trees是关系型数据库主要的引擎实现.

Read All

3/4

Welcome to Borui's Blog!

Transactions

难以掌握的事务概念

ACID的含义

Atomicity

Consistency

Isolation

Durability

单目标与多目标操作

单目标写入

多目标事务

处理错误和取消操作

弱隔离级别

读已提交

没有脏读

没有脏写

实现读已提交

快照隔离和可重复读

不可重复读

快照隔离性实现

索引和快照一致性

丢失更新

写倾斜和幻读

写倾斜例子

幻读的套路

物化冲突

可串行化

实际串行执行

在存储过程里封装事务

分区

总结

两阶段锁

两阶段锁的性能

谓词锁

索引范围锁

可串行化快照隔离级别(SSI)

悲观与乐观的并发控制

检测算法

SSI的性能

总结

并发读写隔离

并发写隔离

Partitioning

Partitioning and Replication

Partitioning of Key-Value Data

Partitioning by Key Range

Partitioning by Hash of Key

缓解热点

Partitioning and Secondary Indexes

Partitioning Secondary Indexes by Document

Partitioning Secondary Indexes by Term

Rebalancing Partitions

再调整的策略

固定分区数量（hash）

动态分区（range）

正比节点大小

自动化or手工

Request Routing

并行查询

总结

垃圾收集器

CMS垃圾收集器

G1垃圾收集器

Replication

Leaders and Followers

同步异步复制

新加follower

处理节点故障

follower故障

leader故障

复制日志实现

基于语句的复制

预写日志的方式

逻辑日志方式

基于触发器的方式

复制日志的问题

写后读一致性.

单调读一致性

一致前缀读一致性

日志延迟问题