【行业动态】分布式存储的七方面探讨



存储领域内的很多知识,可以归结于7个方面:复制、存储引擎、事务、分析、多核、计算和编译。

什么是分布式存储呢?如果一个存储系统,不管是对象、块、文件、kv、log、olap、oltp,只要对所管理的数据做了Partitioning&Replication,不管姿势对不对,其实都可以归纳于分布式存储。分布式存储就是:Partitioning以多机scale,Replication以灾备容错。

1. 复制

复制是解决可用性,可扩展性和高性能的关键。为了灾备,数据需要冗余存储;为了高可用,服务需要hot standby。缺乏灾备的系统难以在生产环境使用。元数据和数据的维护均离不开复制,复制可转移而不可消除。复制引出了多副本一致性问题,而一致性保证需要考虑各种软件和硬件故障,以及误操作。共识算法和复制日志是解决复制问题的核心,具体涉及:

2`O\ds.R+OZs0

故障检查,租约协议;

o7@#E5uYLX0

选主算法,primary uniqueness invariant,网络隔离,脑裂,双主,拜占庭故障,failfast/failstop,failover;

+DI3a!c,KT0

日志复制,RSM;

A#p G#~F(i0

membership change,或者config change,主机上下线管理,扩缩容;存储产业技术创新战略联盟 W7Z6Ma M.J S

数据复制,data rebalancing,data recovery;存储产业技术创新战略联盟 c*N9QY3gl![9rH

副本放置逻辑和副本路由逻辑;

+z J5YvS `|0

primary和backup之间如何fence?

T ~|/gIZ0

外部一致性,线性一致性;存储产业技术创新战略联盟2o3| u.m ~-s$XW

pipeline,fanout,primary-backup,quorum-based,gossip;存储产业技术创新战略联盟7xCe9r:P5mO8AA

分布式日志,active-standby架构,active-active架构;存储产业技术创新战略联盟D:eiG"y|C-hz'HC

……存储产业技术创新战略联盟(kZle/dF

2. 存储引擎

此处的引擎是指本地的持久化存储引擎,持久化存储引擎要考虑CPU和memory系统和持久化设备之间的速度和带宽差异,可以总结为1-3-5。

qwCMX [5{0

1是指fsync的调用,以及和fsync地位等同的函数的调用。调用次数,调用频率,在多少数据上施加调用等。设备的带宽和利用率是否合理,fsync的调用怎么均摊到更多io次数和吞吐之上呢?存储产业技术创新战略联盟MH#L}5vk?1S ?u

3是指读/写/空间的放大。怎么tradeoff,牺牲一个保住其他两个呢?存储产业技术创新战略联盟s/K Z)z-]#C?@

5是指WAL的5个LSN,分别为prepare point,commit point,apply point,checkpoint,prune point。

j R*pZ;E0

处于prepare point和commit point之间的数据需要group commit;存储产业技术创新战略联盟$d$D:lr0[A7p8F

处于apply point和commit point点之间的提交数据需要apply到内存的数据结构之上以后对读可见;

R F7lR/\8Q#i5@!E0

内存数据结构需要以一定的调度策略存档于持久化设备, checkpoint就是存档点;存储产业技术创新战略联盟 PJ%`s8T[)}(g

recover from crash需要从最近的checkpoint点恢复到commit point;

%f1Jo7DUolB*q y0

而一段checkpoint完成,则截止该checkpoint的日志可以截断,因此存在一个不大于checkpoint的点,是为prune point,截止改点的日志和老的on-disk镜像可以安全删除。

qN{ Z-c/I0

因此这5个点始终保持一条约束:它们之间存在全序关系。

[bkT r$x0

数据结构和算法

内存和磁盘数据的管理,需要用到丰富的数据结构和算法。此外解压缩和编解码算法用于降低数据的size,也很有意思。

6Ho { L,ad0

3. 事务

事务是指ACID,很多存储系统,其实可以用事务做baseline进行分析,看这个系统在原子性,一致性,隔离性和持久化四个方面的设计究竟走多远。其实事务反应了正确性和并发性的折中。作为事务的使用方,理论上(实践上未必),并发访问存储系统时,不需要担心结果不正确的问题。假如这种担忧存在,一定是事务处理上,牺牲了某些正确性,偏向了并发性,将错误处理和选择权交给了使用方处理,使用方需要额外花费心智在客户代码中插入fence代码和做容错处理。存储产业技术创新战略联盟J#q^5Ni K&A*C

存储引擎部分,其实已经或多或少地涉及到了事务处理的提交协议,提交协议主要解决事务的A和D。事务处理的核心是并发控制(concurrency control)协议。并发控制主要解决这样的问题:

$n,] ?o {Ar.Nw0

两个并发事务冲突(读写,写读,写写),应该怎么处理呢?加锁等待还是检测到冲突主动夭折呢?存储产业技术创新战略联盟Q.F*A P_4T*f

已经提交的事务对数据库的影响,怎么对当前outstanding事务的读操作可见呢?

r"{${0B?T)AD0

这两个问题本质是隔离性和一致性,冲突事务加以同步,前置的提交事务对后置outstanding事务可见。

fi9m1s"W3W0

理想的正确性是这样子的:所有的事务,不管是否存在冲突,都一个一个串行执行,时间上没有任何重叠。理想的并发性是这样子的:所有事务都没有冲突,可以以最佳的并行度同时执行。但现实是冲突始终存在,解决冲突,意味着在并行执行的某个环节插入了同步点,需要判断和仲裁是否有冲突。

p8T[x"up*[ Ko0

冲突等待,是lock-based CC协议;冲突夭折重试,是timestamp ordering CC协议。前者就是所谓的悲观事务,后者则为乐观事务。事务处理在Jim Gray的书中和知名教材里其实已经讲得很清楚了。这里只提一下乐观事务的冲突检查的直观性的简单的理解:两个事务存在两种定序方法,一种是由TSO分配的时间戳确定的顺序,一种是由数据依赖(WAW,RAW,WAR)确定顺序。如果这两种顺序破坏事务之间的偏序关系,那么这两个事务必然冲突,可以选择让一个事务夭折并且重试。

r8Y2Q$Dk8K0

定序是一个比较关键的问题,比如乐观事务的begin和commit的时间戳分配,悲观事务的基于时间戳的死锁预防也会用到时间戳的分配。

k(P!T_Ap]Jg'j0

存储系统自身做了partitioning之后,单个partition的事务处理可下沉于本地存储引擎,然而如果一个操作涉及对多个partition的修改,则需要考虑跨partition的事务处理能力。其实分布式事务并没有一个清晰的定义,但蕴含了“跨(across)”的意思,不管是提交协议还是CC协议,都依赖于分布式存储系统的实现或者单机事务的实现。虽然有很多文献中反复用到2PC和3PC,但有时候是指提交协议,有时候是指CC协议,有时候是指提交协议和CC协议的混合体。

;t)h"V*a+c0

事务给存储系统的行为做出了明确的定义和保证,从事务的角度可推测系统的实现,比如加锁的粒度,多版本的管理,全局同步点,怎么处理write-too-late问题。

{-h?%y#HVt0

4. 分析

分析处理涵盖的东西太多了。从一个角度看,是怎么实现SQL语言;从另一个角度看,是怎么实现一个分布式系统由SQL驱动起来工作。一条文本的SQL语句,历经分词,语法分析,访问catalog和语意分析,关系代数的等价变化,形成逻辑的查询计划,然后根据数据的分布,算子自身特点和计算资源状况,生成物理执行计划。存储产业技术创新战略联盟/S c2v|%Pn3O

一条SQL可以对应多个逻辑执行计划,一个逻辑执行计划,对应多个物理执行计划。比如join的顺序,join的算子的实现。谓词过滤时谓词的顺序,谓词是否下沉。一个关系代数的算子,有多种的不同实现算法,而多个关系算子,不同的计算顺序也会有不同的执行效率。根据先验知识,使用启发式的策略;或者利用数据分布的统计信息,采用某种cost估算模型;又或者根据已有执行经验,自适应地调整到最优或者次优的执行计划。

:Qpw-G)S7b"`0

在计算层,通过三大优化策略parallelism,pipelining和batch加速处理。比如数据经过parititioning形成多个partition,放置于多机上,采用MPP的方式,做多机的并行处理。计算的过程可以看成是把关系作为输入,流经执行树的叶子节点,汇聚于根节点,每个节点的对应算子的具体算法实现所输入数据进行处理后输出。从计算模型的角度看,有这么几种情况:存储产业技术创新战略联盟3I^1D%`/Tv;O

tuple-at-a-time:采用了迭代器的模式,当前迭代器执行get_next时,调用child算子对应迭代器的get_next获取计算所需的输入tuple,然后执行一段计算代码,产生一个输出tuple,发射parent算子。

'Lc3z3cq0

full materialization:每个算子接收到全部的输入数据,计算出输出结果,交给下一个算子计算。这种方式类似于批处理。

.|#|`.]dRQ0

vectorized execution:数据在内存中按列存储,以数组表示。选择数组的大小,让其可以在L1 data cache中装得下,然后执行树的每个算子执行tight for-loop按数组处理数据。这样即避免了full materialization过多的资源索取,又能避免tuple-at-a-time的处理单个tuple的overhead,同时对cache更加友好,减少spurious invalidation,提升speculative cache missing的产生。同时简单tight for-loop,编译器能更好点编译成高效执行指令,同时也能更好地填充CPU的指令流水,充分利用CPU的multiple issue的功能加速简单指令的处理。

z3LEr(l.x:T0M0

在存储层,数据采用列式存储,可获得很好的编码效率,降低读放大和空间放大,访问持久化存储的带宽被高效利用,CPU和Memory的带宽增速相对于持久化存储带宽增速表现出了显著的差异,使用CPU的计算交换磁盘带宽,提升了数据的处理能力。

%Q1XH^$udI0

列存,向量化执行引擎,MPP是现代分析性数据库的关键技术。存储产业技术创新战略联盟m*bbdh{

5. 多核

从编程实现的角度看,多核scale,CC协议,共识算法是计算机中比较有挑战,并且是纯自然的问题。即便技术上不深入接触数据库,也对这三个问题相当地痴迷,被数据库技术的吸引加入这个领域,或多或少和这三个问题相关。存储产业技术创新战略联盟Aw5w2dw*y%I0zP

为什么多核如此重要呢?

假设摩尔定律,没有功率墙的限制,世界会怎样呢?显然我们不需要修改老代码,只要增加单核晶体管数量,老代码自然而然会提升。我们撞到了功率墙后,发现需要增加核数以提升计算速度。现在问题来了,我们的代码已经写成了多线程执行,那么随着核数增长,修改worker线程池的大小,老代码的计算能力会随着核数增加而持续增加吗?显然不是这样,因为多核上的scale受到阿姆达尔定律的制约,当代码中串行执行的部分占比1%时,256核机器只能最多加速到72倍,如果是10%,只能最多加速到10倍。显然修改线程池的大小,并不是一个好方法,减少代码中contention才是关键。

1OzEF$dDr0

这种情况下,speedup想要随着核数而scale,发现很多算法,数据结构,CC协议和分析处理的算子实现,需要case-by-case重构以减少contention,重构方式是采用lockfree算法。但是这还不是事实的全部,当面对多核scale时,其实我们面对的是一个新的分布式系统,这个新的分布式系统是以interconnect为网络,以核为计算资源,并且还需要考虑屏蔽内存体系的延迟。如果说原来的分布式系统中,我们倾向于每个机器各干各的,数据做到均衡,计算资源就可以充分利用。对于多核编程同样有这个问题,怎么将原来的任务均匀地拆成多个子任务,然后多个子任务可以齐头并进,几乎同时冲线结束。显然数据拆分不均衡,跨核通信等因素都会造成快核等慢核的问题。同时,多核处理时,倾向于协作完成一个共同的任务,而非各干各的,这种情况下,将任务均匀拆分成子任务的的调度代码,共享的数据结构的访问代码,多核彼此之间等待本身就是同步点,即contention,总之,contention怎么降低呢?存储产业技术创新战略联盟(NugcHM4Kz|

现实中,lockfree算法,怎么描述和验证正确性呢?我们对比其他两个问题的思路,或许有解法。比如共识算法中,采用invariant描述算法;而CC协议中,采用反例(anormaly)攻击算法。或许这两种方法相互结合,能够帮助我们研究lockfree算法。存储产业技术创新战略联盟I$S}e6B0Lk

多核scale的挑战性很大,但这可以让具有优势的传统数据库和数据库的新进入者,处于赛道的同一起跑线,比拼谁的代码case-by-case优化做得好。

*[i ~)m5@yy!o)]0

也有不少团队,在思考异构计算加速数据处理,这同样充满机会。但是,依靠程序员的心智构造精巧而高质量的代码,费时费力。或许的确应该通过编译器的后端技术一劳永逸解决这类问题,现在做不到,不代表未来也做不到。到时候,有人看着前人写得如此复杂的代码,就好比我们现在看到泥板书和带孔的卡片。

E$M']!]}#G;vct0

6. 计算

计算主要讲执行引擎, 执行引擎是一个很大的scope,目前roadmap已经建立,但是缺乏baseline,待两者都ready之后,会补充。

4_6pgAq%["]^;s0

7. 编译

编译对数据库的渗透是全方位的:比如计算引擎在向量化之外可采用编译技术优化性能。数据库中很多case-by-case的性能优化,需要深入研究体系结构,异构计算加速处理也需要使用编译技术。流批DSL脚本使用现有的SQL执行引擎做计算,UDF扩充等。目前动机已经明了,但roadmap和baseline尚未建立,两者ready之后,也会补充进来。存储产业技术创新战略联盟;sS'u1`p


LD%c[p Am0

  最新报道
  • 联盟举办“基于近NVM计算的 
  • “基于近NVM计算的系统软件 
  • 盛世华诞 举国同庆
  • 月满人间 福泽万家
  • 【行业动态】不可变对象存储 
  • 【行业动态】机械盘固态盘能 
  • 存储联盟举办“基于纠删码的 
  • 存储联盟举办“超级存储与蓝 
  • 【行业动态】分布式存储的七 
  • 【行业动态】三个优秀的云存 
  •  
    
     
    存储产业技术创新联盟 | 联系我们 | 京ICP备12012807号-5
    © 2021 Allstor