不知怎么地,前一阵子知乎上对Raft的乱序的问题的讨论就变多了。我觉得其实这个问题可讨论的东西并不多。
Raft作者觉得Multi Paxos太复杂,所以搞了一个Raft。Raft加了很多约束,其中可能最重要的一条就是只能顺序commit。
所以,顺序commit的锅,Raft是得好好背着,翻不了案的。
值得谈一谈的是乱序apply。
能不能乱序apply本质上取决于你的状态机的设计。
比如,考虑rocksdb...
Basic Paxos证明
Basic Paxos协议的证明过程
浅析CAP理论
CAP理论是Eric Brewer在2000年前后提出的一个设计上的折中原则,大意是说,一个系统在Consistency、Availability、Partition Tolerance三者之间无法兼顾,必须舍弃一个。CAP理论作为一个设计折中原则,在后面的几年被人误解,因此Eric Brewer在2012年又写了一篇文章,着重解释了CAP的一些误解,一个系统并非一定要预先在CAP中彻底牺牲一个属性,更多的场景下,没有P发生时,CA可以兼得,而在P发生时,可以选择C或A中的一个,并在P结束后恢复。
LB+Tree:面向3DXPoint优化的B+Tree
《LB+Trees: Optimizing Persistent Index Performance on 3DXPoint Memory》(VLDB20')
这是个设计非常巧妙的数据结构,这里简单描述下核心内容,读者可以直接读原文,行文非常清晰。
Abstract
3DXPoint的有些硬件特性,跟常规NVM差不多:
3DXPoint的访存粒度是64字节Cache Line
3DXPoint比DRAM慢2倍,比SSD快几个数量级
3DXPoint的写比读慢
使用clwb/sfence等特殊指令将数据从CPU...
Dynamo论文阅读笔记
Dynamo: Amazon’s Highly Available Key-value Store
Dynamo这篇论文是2007年出来的,以前读研究生的时候读过,前两天看了一篇NoSQL综述提到了这篇论文,今天重读一遍,简单做些笔记,里面有些东西还只是简单看了下不够深入。
Dynamo系统本身并没有提出新的技术,但是将各种分布式技术融合在一起,构建了一个高性能高可用高可扩展的key-value存储。Dynamo牺牲了强一致性,使用vector clock等方法把数据冲突...
Reconfiguring a State Machine
Reconfiguring a State Machine这篇论文主要讲解成员组reconfigure,即成员变更。发表时间还是2010年,相比Paxos原始论文的发表时间已经过去20年了。本博文先解读这篇论文,Raft做成员变更的方案后面另文阐述。
Reconfiguration是指在分布式系统执行过程中,改变系统内进程(副本)集合的动作。例如,Paxos成员组从(S1,S2,S3)变为(S1,S2)。成员变更可以改变成员组大小(从五个副本改为三个副本),...
RUM Conjecture
《Designing Access Methods: The RUM Conjecture》
这篇论文从读、写、存储空间开销角度总结了access method设计,并提出了一个RUM猜想,认为针对其中两个开销优化,则会导致第三个优化困难。
就RUM猜想本身的可信程度而言,我个人觉得一般,不过这种三角可视化的总结非常有趣,可以一读。
What is RUM Conjecture
作者总结了Access Method的一些trade off,审视了RUM三种开销:R是read overhead,...
Spanner: Becoming a SQL System论文阅读笔记
继2012年在OSDI年发表了Spanner论文《Spanner: Google’s Globally-Distributed Database》之后,Google在SIGMODE'17上发表了第二篇关于Spanner的论文《Spanner: Becoming a SQL System》。从整个的数据库系统角度看,2012年那篇讲是的Spanner的下半部分Storage Engine的一些feature:数据自动分区和全球部署、多副本Paxos高可用、支持外部一致性的分布式事务。2017年这篇主要讲是讲数据库的上半部分...
Calcite论文阅读笔记
Calcite是Apache旗下开源的、支持多种数据源、提供查询处理/查询优化/查询语言的基础软件框架。
Calcite的三个特点:
标准SQL: 工业级的SQL parser, validator, JDBC Driver
查询优化器:将查询表达为关系代数,计划生成,基于代价的优化
数据源适配:融合第三方数据源
SIGMOD18上的Calcite总结论文《Apache Calcite: A Foundational Framework for Optimized Query Processing Ove...
Calvin简介
前面介绍的并发控制算法评估里面,测试也把Cavlin算进来了,这里简单介绍下Calvin。详细的可以参考下原论文 Calvin: Fast Distributed Transactions for Partitioned Database Systems (SIGMOD12')。
Calvin面向的场景是确定性事务,不支持交互式事务。这一点需要特别注意。在互联网很多业务里,这点是不适用的。
Calvin也是一个deterministic的分布式数据库,这里先简单介绍下它的架构。...