Skip to content

Latest commit

 

History

History
828 lines (608 loc) · 58.5 KB

DDIA.md

File metadata and controls

828 lines (608 loc) · 58.5 KB
Raw
DocId: 10 	r1
Links 
  Forward: 20 
  Forward: 40   Forward: 60 
Name  
  Language  
    Code: 'en-us'     Country: 'us'     
Language 
    Code: 'en' 
  Url: 'http://A' 
Name 
  Url: 'http://B' 
Name 
  Language 
    Code: 'en-gb'     Country: 'gb'


# Name.Language.Code
# value  r  d
# en-us  0  2  -- r=0是因为没有重复
# en     2  2  -- r=2是因为`Name.Language`重复,所以可以认为级别就是层级
# NULL   1  1  -- 需要加这层的原因是为了表明下面的en-gn是在第三个Name中而不是第二个
# en-gn  1  2  -- r=1是因为`Name`重复
# NULL   0  1

# r: 重复级别  d: 定义级别

任何小于字段路径中重复字段和可选字段数的definition level都表示 NULL

将一条记录分解为若干列的算法实现

procedure DissectRecord(RecordDecoder decoder, FieldWriter writer, int repetitionLevel):
  Add current repetitionLevel and definition level to writer
  seenFields = {} // empty set of integers
  while decoder has more field values
 	FieldWriter chWriter =
		child of writer for field read by decoder
 	int chRepetitionLevel = repetitionLevel
 	if set seenFields contains field ID of chWriter
 		chRepetitionLevel = tree depth of chWriter
 	else
 		Add field ID of chWriter to seenFields
 	end if
 	if chWriter corresponds to an atomic field
 		Write value of current field read by decoder
 		using chWriter at chRepetitionLevel
 	else
 		DissectRecord(new RecordDecoder for nested record 
 				read by decoder, chWriter, chRepetitionLevel)
 	end if
 end while
end procedure

-- 查询SQL
SELECT DocId AS Id,
	COUNT(Name.Language.Code) WITHIN Name AS Cnt,
	Name.Url + ',' + Name.Language.Code AS Str
FROM t
WHERE REGEXP(Name.Url, '^http') AND DocId < 20 ;


-- 查询结果
Id: 10
Name
	Cnt: 2
	Language
		Str: 'http://A,en-us'
		Str: 'http://A,en'
Name
	Cnt: 0		

-- 输出schema
message QueryResult{
	require int64 Id;
	repeated group Name{
		optional uint64 Cnt;
		repeated group Language{
			optional string Str;
		}
	}
}

-- 算法实现
procedure ConstructFSM(Field[] fields):
for each field in fields:
	maxLevel = maximal repetition level of field
	barrier = next field after field or final FSM state otherwise
 	barrierLevel = common repetition level of field and barrier
 	for each preField before field whose
 			repetition level is larger than barrierLevel:
 		backLevel = common repetition level of preField and field
 		Set transition (field, backLevel) -> preField
 	end for
 	for each level in [barrierLevel+1..maxLevel]
 			that lacks transition from field:
 		Copy transition's destination from that of level-1
 	end for
 	for each level in [0..barrierLevel]:
 		Set transition (field, level) -> barrier
 	end for
end for
end procedure

现今很多应用程序都是 数据密集型(data-intensive) 的,而非 计算密集型(compute-intensive)的. 因此CPU很少成为这类应用的瓶颈,更大的问题通常来自数据量、数据复杂性、以及数据的变更速度.

可靠性、可扩展性、可维护性

可靠性(Reliability): 系统在困境(adversity)(硬件故障、软件故障、人为错误)中仍可正常工作(正确完成功能,并能达到期望的性能水准) 可扩展性(Scalability): 有合理的办法应对系统的增长(数据量、流量、复杂性). 讨论可扩展性意味着考虑诸如"如果系统以特定方式增长, 有什么选项可以应对增长？"和"如何增加计算资源来处理额外的负载？"等问题. 可维护性(Maintainability): 许多不同的人(工程师、运维)在不同的生命周期,都能高效地在系统上工作(使系统保持现有行为,并适应新的应用场景)

Twitter推送系统

  1. 第一版: SQL关联查询
  2. 第二版: 提前计算、存储每个用户需要查看的关注的人的推文收件箱 消耗计算: 平均一条推文平均会发送75个关注者,所以每秒4.6K的发推写入,变成每秒345K的写入 缺点: 有的用户有超过3000w的粉丝,他们发推文会导致3000w次的写入!!!
  3. 第三版: 两种方法的混合.大多数用户发的推文会被扇出写入其粉丝主页时间线缓存中.但是少数拥有海量粉丝的用户(即名流) 会被排除在外.当用户读取主页时间线时,分别地获取出该用户所关注的每位名流的推文,再与用户的主页时间线缓存合并, 如第一版所示.

延迟和响应时间的区别

延迟(latency) 和 响应时间(response time)经常用作同义词,但实际上它们并不一样.响应时间是客户所看到的,除了实际处理 请求的时间( 服务时间(service time) )之外,还包括网络延迟和排队延迟.延迟是某个请求等待处理的持续时长,在此期间它处于 休眠(latent) 状态,并等待服务

TODO 表结构的规范化和非规范化

关系模型的一个关键洞察是: 只需构建一次查询优化器,随后使用该数据库的所有应用程序都可以从中受益. 如果你没有查询优化器的话,那么为 特定查询手动编写访问路径比编写通用优化器更加容易--不过从长期看通用解决方案更好

声明式查询语言适合并行执行,命令式查询语言并不是特别合适

两大类存储引擎: 日志结构(log-structured)的存储引擎和面向页面(page-oriented)的存储引擎

面向页面: B树 日志结构: asd

SSTables(Sorted String Table)和LSM树

SSTables: 存储: 按键排序、归档、压缩 搜索: 存储时按规则分块 + 内存字节扫描. 如果字符长度是定长(通常不是),那么可以用二分查找.因为定长的话可以知道每条记录的分界点 (前一条记结束,后一条记录开始的地方) LSM树的基本思想: 保存一系列在后台合并的SSTables,简单而有效.即使数据集比可用内存大得多,它仍能继续正常工作.由于数据按排序顺序存储, 因此可以高效地执行范围查询(扫描所有高于某些最小值和最高值的所有键),并且因为磁盘写入是连续的,所以LSM树可以支持非常高的写入吞吐量

WAL(write-ahead-log)在MySQL中叫"重做日志"(redo log)

B树有个优点是每个键只存在于索引中的一个位置,而日志结构化的存储引擎可能在不同的段中有相同键的多个副本. 这意味着在实现事务语义时方便 太多了: 在许多关系型数据库中,事务隔离是通过在键范围上使用锁来实现的.

反直觉的是,内存数据库的性能优势并不是因为它们不需要从磁盘读取的事实.即使是基于磁盘的存储引擎也可能永远不需要从磁盘读取, 因为操作系统缓存最近在内存中使用了磁盘块.相反,它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销

列存储适用于OLAP是因为分析类型的查询语句中通常不会像OLTP一样的拿非常多行,并且OLAP对应的数据仓库中的数据非常之巨大,所以如果用 行存储的话性能简直不敢想象的低,一个查询语句下去可能会把内存占满. 还有就是OLAP常用统计函数,这种情况下列存储在硬盘中的数据摆放都是 顺序的,顺序读比随机读快一个量级(参考4KB顺序读和4KB随机读测速). 还有,列存储压缩数据会比较简单.

列族: 在每个列族中,它们将一行中的所有列与行键一起存储,并且不使用压缩.

列存储索引和行存储索引区别: 行索引中的多个索引(二级索引)的存储将每一行保存在一个地方(聚簇索引或堆文件); 列索引直接存值;

LSM树的思路同样适用于行存储和列存储

编码

XML和CSV不能区分数字和字符串. JSON虽然能区分,但是不区分整数和浮点数,而且不能指定精度. XML和JSON对Unicode字符串有很好的支持,但是它们不支持二进制数据字符编码. 通常会进行Base64后传输,但会增加约33%的数据大小.

PS: 让不同的组织达成一致的难度超过了其它大多数的问题

Thrift的CompactProtocol(三种二进制协议中的一种)还算有趣,虽然都是些别的地方已经有的编码思路 Protobuf在对数组|列表进行编码时和其它协议不一样,它是通过重复字段的重复标记来实现的. 它有个好处,可以将单值改为多值字段,它是兼容的 Avro是一种之前没有见过的编码思路. 附一张图: https://s2.loli.net/2022/06/02/FclZpVqRtP8SiX6.png

我的看法: 越是扣字节的编码兼容起来越麻烦(Avro),但性能非常好

SOAP优点: 给Producer/Consumer双方提供了契约(对于微服务来说很喜欢这个,有专门的契约测试)、安全调用、事务(两阶段)

本地函数调用和RPC的区别: 可预测性、异常原因、幂等、执行时间、数据编码(大对象)、代码优化(我自己想到的)

分布式数据

复制数据的变更算法: 单领导者、多领导者、无领导者

同步复制的优点是,从库保证有与主库一致的最新数据副本.如果主库突然失效,我们可以确信这些数据仍然能在从库上上找到. 缺点是,如果同步从库没有响应(比如它已经崩溃,或者出现网络故障,或其它任何原因),主库就无法处理写入操作.主库必须 阻止所有写入,并等待同步副本再次可用

因此,将所有从库都设置为同步的是不切实际的:任何一个节点的中断都会导致整个系统停滞不前.实际上,如果在数据库上启用 同步复制,通常意味着其中一个跟随者是同步的,而其他的则是异步的.如果同步从库变得不可用或缓慢,则使一个异步从库同步. 这保证你至少在两个节点上拥有最新的数据副本:主库和同步从库.

​通常情况下,基于领导者的复制都配置为完全异步. 在这种情况下,如果主库失效且不可恢复,则任何尚未复制给从库的写入都会丢失. 这意味着即使已经向客户端确认成功,写入也不能保证持久(Durable). 优点是即使所有的从库都落后了,主库也可以继续处理写入.

Redis和Dynamo的高可用实现: Gossip

传统的复制型关系数据库系统都将关注点放在保证副本的强一致性. 虽然强一致性可以给应用的写入操作提供方便的编程模型,但导致系 统的扩展性和可用性非常受限,无法处理网络分裂的情况

单领导者

复制数据的几种方法

基于语句的复制: INSERT、UPDATE、DELETE等都会转发给每个从库. 缺点是: 非确定性函数(rand()、now())在每个副本上会生成不同值; "自增列"会在每个副本上产生不同的效果; 传输预写日志(WAL): 缺点是它记录的东西很底层: 哪些磁盘块中的哪些字节发生了更改. 如果数据库将其存储格式从一个版本更改为另一个 版本,通常不可能在主库和从库上运行不同版本的数据库软件 逻辑日志复制(基于行): 1. 对于插入的行,日志包含所有列的新值. 2. 对于删除的行,日志包含足够的信息来唯一标识已删除的行.通常是主键,但是如果表上没有主键,则需要记录所有列的旧值. 3. 对于更新的行,日志包含足够的信息来唯一标识更新的行,以及所有列的新值(或至少所有已更改的列的新值). 修改多行的事务会生成多个这样的日志记录,后面跟着一条记录,指出事务已经提交.MySQL的二进制日志(当配置为使用基于行 的复制时)使用这种方法. 如果要将数据库的内容发送到外部系统的话这一点很个用,这种技术被称为"数据变更捕获"(change data capture). 基于触发器的复制: 允许注册在数据库系统中发生数据更改(写入事务)时自动执行的自定义应用程序代码.

异步复制下的数据不一致解决方法

  1. 读用户可能已经修改过的内容时,都从主库读;这就要求有一些方法,不用实际查询就可以知道用户是否修改了某些东西. 举个例子,社交网络上的用户个人资料信息通常只能由用户本人编辑,而不能由其他人编辑.因此一个简单的规则是:从主库读取用户自己的档案 ,在从库读取其他用户的档案.

  2. 如果应用中的大部分内容都可能被用户编辑,那这种方法就没用了,因为大部分内容都必须从主库读取(扩容读就没效果了).在这种情况下 可以使用其他标准来决定是否从主库读取.例如可以跟踪上次更新的时间,在上次更新后的一分钟内,从主库读.还可以监控从库的复制延迟,防 止任向任何滞后超过一分钟到底从库发出查询.

  3. 客户端可以记住最近一次写入的时间戳,系统需要确保从库为该用户提供任何查询时,该时间戳前的变更都已经传播到了本从库中.如果当前 从库不够新,则可以从另一个从库读,或者等待从库追赶上来. 时间戳可以是逻辑时间戳(指示写入顺序的东西,例如日志序列号)或实际系统时钟(在这种情况下,时钟同步变得至关重要;).

  4. 如果您的副本分布在多个数据中心(出于可用性目的与用户尽量在地理上接近),则会增加复杂性.任何需要由领导者提供服务的请求都必须 路由到包含主库的数据中心.

另一种复杂的情况是:如果同一个用户从多个设备请求服务,例如桌面浏览器和移动APP.这种情况下可能就需要提供跨设备的写后读一致性: 如果用户在某个设备上输入了一些信息,然后在另一个设备上查看,则应该看到他们刚输入的信息. 在这种情况下,还有一些需要考虑的问题:

  1. 记住用户上次更新时间戳的方法变得更加困难,因为一台设备上运行的程序不知道另一台设备上发生了什么.元数据需要一个中心存储.

  2. 如果副本分布在不同的数据中心,很难保证来自不同设备的连接会路由到同一数据中心.(例如,用户的台式计算机使用家庭宽带连接 ,而移动设备使用蜂窝数据网络,则设备的网络路线可能完全不同.如果你的方法需要读主库,可能首先需要把来自同一用户的请求路由到同一 个数据中心.

单调读: 如果先前读取到较新的数据,后续读取不会得到更旧的数据. 实现单调读取的一种方式是确保每个用户总是从同一个副本进行读取(不同的用户可以从不同的副本读取).

多领导者

应用场景: 在单个数据中心内部使用多个主库很少是有意义的,因为好处很少超过复杂性的代价.

优点: 容忍网络延迟以及部分数据中心的主节点崩溃; 更快(可以让不同的数据中心更靠近不同地方的用户); 缺点: 数据冲突;

由于多主复制在许多数据库中都属于改装的功能,所以常常存在微妙的配置缺陷,且经常与其他数据库功能之间出现意外的反应. 例如自增主键、触发器、完整性约束等,都可能会有麻烦.因此,多主复制往往被认为是危险的领域,应尽可能避免

处理数据冲突:

  1. LWW(last write wins)
  2. 保留冲突,用程序或者跟用户提示这个异常

PS: "冲突解决"这个问题在协同软件中经常碰到,我知道的有operational transformation和Conflict-free replicated datatypes(CRDT)

多主复制拓扑

适用场景:应用程序在断网之后仍然需要继续工作(比如钉钉的在线文档,无网络时本地代表的就是一个数据库).

多主复制在同时编辑一条数据时处理起来不如单主,"协同编辑"场景就是个例子

几种拓扑图: https://s2.loli.net/2022/06/03/4QwR3mnSDqjdxMX.png

All-to-all: 每个领导者将其写入每个其他领导 Circular: 每个节点接收来自一个节点的写入,并将这些写入(加上自己的任何写入)转发给另一个节点. MySQL只支持这种 Start: 指定的根节点将写入转发给所有其他节点

为了防止无限复制循环,每个写入都被标记了所有已经通过的节点的标识符.当一个节点收到用自己的标识符标记的数据更改时, 该数据更改将被忽略,因为节点知道它已经被处理.

冲突的解决通常适用于单个行或文档层面,而不是整个事务

无主复制

Dynamo、Riak、Cassandra、Voldemort都是无主数据库.

发定人数很有讲究,分"松散的法定人数"(人数可能不包含在集群中"主节点")、"法定人数"(人数全是集群节点中的"主节点")

TODO 捕获"此前发生"关系

分区

术语: 分区(partition)在MongoDB,Elasticsearch和Solr Cloud中被称为分片(shard),在HBase中称之为区域(Region), Bigtable中则是表块(tablet),Cassandra和Riak中是虚节点(vnode), Couchbase中叫做虚桶(vBucket).但是分区(partition) 是约定俗成的叫法

散列似乎和范围检索天生就是相对的.

一种简单处理热Key的方法: 在主键的开始或结尾添加一个随机数,只要一个两位数的十进制随机数就可以将主键分散为100种不同的主键, 从而存储在不同的分区中. 将主键进行分割之后,任何读取都必须要做额外的工作,因为他们必须从所有100个主键分布中读取数据并将 其合并.此技术还需要额外的记录:只需要对少量热点附加随机数;对于写入吞吐量低的绝大多数主键来是不必要的开销.因此,您还需要 一些方法来跟踪哪些键需要被分割

两种用二级索引对数据库进行分区的方法: 基于文档的分区(document-based)和基于关键词(term-based)的分区

基于文档的分区: 每个分区是完全独立的. 每个分区维护自己的二级索引,仅覆盖该分区中的文档.它不关心存储在其他分区的数据.无 论何时您需要写入数据库(添加,删除或更新文档),只需处理包含您正在编写的文档ID的分区即可.出于这个原因,文档 分区索引也被称为本地索引(local index).

		  它被广泛使用在: MongoDB,Riak,Cassandra,Elasticsearch,SolrCloud和VoltDB

		  缺点: 如果同时使用多个二级索引做条件时性能不太行.

基于关键词的分区: 覆盖所有分区数据的全局索引,而不是给每个分区创建自己的次级索引(本地索引). 当然,全局索引也会进行分区的.

		  缺点: 写入速度较慢且较为复杂,因为写入单个文档现在可能会影响索引的多个分区(文档中的每个关键词可能位于不同的分
		  区或者不同的节点上);   它还需要分布式事务...

		  支持的数据库: Riak、Oracle

PS: HBase为了减少实现的复杂度而放弃了次级索引

再平衡

固定数量的分区: 创建比节点更多的分区,并为每个节点分配多个分区; 即: 分区数固定,节点再平衡负责的分区. 例: 运行在10个节点的集群上的数据库可能会从一开始就被拆分为1,000个分区,因此大约有100个分区被分配给每个节点. 此时 集群中加一个节点,那么之前的10个节点会匀一些分区给新节点 动态分区: 当分区增长到超过配置的大小时,会被分成两个分区,每个分区约占一半的数据; 如果大量数据被删除并且分区缩小到某个阈值以下,则可 以将其与相邻分区合并;

	 优点: 动态分配负载

按节点比例分区: 每个节点具有固定数量的分区.在这种情况下,每个分区的大小与数据集大小成比例地增长,而节点数量保持不变,但是当增加节 点数时,分区将再次变小.由于较大的数据量通常需要较大数量的节点进行存储,因此这种方法也使每个分区的大小较为稳定

"全自动重新平衡"可以很方便,因为正常维护的操作工作较少.但是,这可能是不可预测的.再平衡是一个昂贵的操作,因为它需要重新路由 请求并将大量数据从一个节点移动到另一个节点.如果没有做好,这个过程可能会使网络或节点负载过重,降低其他请求的性能

请求路由

分区与节点之间的关系变动后,需要一个机制让客户端以及所有节点都知道这个状态,不然一个Key请求过来到底如何精准路由是个问题.

有"统一配置中心"、"共识"两个思路.

统一配置中心: Zookeeper 共识: 流言协议(gossip protocol)、Raft、Zab、Paxos

Cassandra和Riak在节点之间使用流言协议(gossip protocol)来传播群集状态的变化.请求可以发送到任意节点,该节点会转发到包含所请 求的分区的适当节点.这个模型在数据库节点中增加了更多的复杂性,但是避免了对像ZooKeeper这样的外部协调服务的依赖.

事务

ACID: 原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性(Durability)

原子性: 不能让另一个线程看到该操作的一半结果(中间状态). 能够在错误时中止事务,丢弃该事务进行的所有写入变更的能力. 一致性: 对数据的一组特定陈述必须始终成立,即"不变量". 所以这个C是应用程序的属性,不是数据库的属性(银行转账的例子). 隔离性: 用于描述并发. 同时执行的事务是相互隔离的: 它们不能相互冒犯.传统的数据库教科书将隔离性形式化为可序列化(Serializability), 这意味着每个事务可以假装它是唯一在整个数据库上运行的事务.数据库确保当事务已经提交时,结果与它们按顺序运行(一个接一个)是 一样的,尽管实际上它们可能是并发运行的

	在Oracle中有一个名为"可序列化"的隔离级别,但实际上它实现了一种叫做快照隔离(snapshot isolation) 的功能,这是一种比可
	序列化更弱的保证

持久性: 持久性是一个承诺,即一旦事务成功完成,即使发生硬件故障或数据库崩溃,写入的任何数据也不会丢失

"事务"通常被理解为,将多个对象上的多个操作合并为一个执行单元的机制

ACID数据库基于这样的哲学: 如果数据库有违反其原子性,隔离性或持久性的危险,则宁愿完全放弃事务,而不是留下半成品. 相反,无主复制的数据存储,主要是在"尽力而为"的基础上进行工作.可以概括为"数据库将做尽可能多的事,运行遇到错误时,它不会 撤消它已经完成的事情" ——所以,从错误中恢复是应用程序的责任

基础的事务隔离级别: 读已提交(Read Committed)

它保证:

  1. 从数据库读时,只能看到已提交的数据(没有脏读(dirty reads))
  2. 写入数据库时,只会覆盖已经写入的数据(没有脏写(dirty writes))

但它不能防止"计数器增量"的安全性.

脏读: 一个事务读取另一个事务的未被执行的写入 不可重复读: 同一个事务中读两次同一条记录,记录值不一样 可重复读: 和"快照隔离"相似 写入偏差: 两个实际同时检查一个约束然后保存数据(页面上的"连击"),最终数据库针对这两条数据都保存成功 幻读: 一个事务中的写入会改变另一个事务的搜索查询的结果 .快照隔离避免了只读查询中幻读.

快照隔离(snapshot isolation)

是"不可重复读"最常见的解决方案.想法是: 每个事务都从数据库的一致快照(consistent snapshot)中读取——也就是说,事务可以看 到事务开始时在数据库中提交的所有数据.即使这些数据随后被另一个事务更改,每个事务也只能看到该特定时间点的旧数据.

PostgreSQL、使用InnoDB引擎的MySQL、Oracle、SQL Server等都支持

数据库必须可能保留一个对象的几个不同的提交版本,因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态.因为它并排 维护着多个版本的对象,所以这种技术被称为多版本并发控制(MVCC, multi-version concurrentcy control)

防止丢失更新

如果应用从数据库中读取一些值,修改它并写回修改的值(读取-修改-写入序列),则可能会发生丢失更新的问题.如果两个事务同时执行, 则其中一个的修改可能会丢失,因为第二个写入的内容并没有包括第一个事务的修改)这种模式发生在各种不同的情况下:

  1. 增加计数器或更新账户余额(需要读取当前值,计算新值并写回更新后的值)
  2. 在复杂值中进行本地修改: 例如,将元素添加到JSON文档中的一个列表(需要解析文档,进行更改并写回修改的文档)
  3. 两个用户同时编辑wiki页面,每个用户通过将整个页面内容发送到服务器来保存其更改,覆写数据库中当前的任何内容.

解决办法: 原子写、显示锁定、自动检测丢失的更新、比较并设置(CAS)

自动检测丢失的更新: "快照隔离"可以直接实现. 显示锁定和CAS: 它们都假设有一个最新的数据副本,但在多主|无主复制的数据库通常无法保证有一份数据的最新副本,所以不适用.

不符合ACID标准的系统有时被称为BASE: 基本可用性(Basically Available)、软状态(Soft State)和最终一致性(Eventual consistency)

分布式系统的麻烦

超时时间公式: $2d + r$ d: 数据包网络时间 r: 处理请求时间

ISDN网络(电路交换网络)属于同步、固定带宽、频率运行(每秒4000帧,每帧16bit),它可以保证"有限延迟"; 而以太网和IP是分组交换协议, 它们是可以从队列中获得,它们针对"突发流量"进行了优化

网络中的可变延迟不是一种自然规律,而只是成本/收益权衡的结果.

一致性与共识

事务隔离主要是为了,避免由于同时执行事务而导致的竞争状态. 而分布式一致性主要关于,面对延迟和故障时,如何协调副本间的状态.

话题:

  1. 最强一致性模型之一: 线性一致性
  2. 分布式系统中的事件顺序的问题,特别是因果关系和全局顺序的问题
  3. 原子地提交分布式事务

线性一致性

在一个线性一致的系统中,只要一个客户端成功完成写操作,所有客户端从数据库中读取数据必须能够看到刚刚写入的值.维护数据 的单个副本的错觉是指,系统能保障读到的值是最近的,最新的,而不是来自陈旧的缓存或副本.换句话说,线性一致性是一个新鲜 度保证(recency guarantee)

可序列化(Serializability): 事务的隔离属性,每个事务可以读写多个对象(行,文档,记录).它确保事务的行为,与它们按照 某种顺序依次执行的结果相同(每个事务在下一个事务开始之前运行完成).这种执行顺序可以与事 务实际执行的顺序不同 线性一致性(Linearizability): 读取和写入寄存器(单个对象)的新鲜度保证.它不会将操作组合为事务,因此它也不会阻止写偏差等 问题(参阅"写偏差和幻读"),除非采取其他措施

可序列化级别大部分使用了三种技术:

  1. 字面意义上地串行顺序执行事务 1.1. Redis;
  2. 两相锁定(2PL, two-phase locking),几十年来唯一可行的选择 2.1. 读时阻塞写,写时阻塞读和写; 其实就是排他锁和共享锁
  3. 乐观并发控制技术,例如可序列化的快照隔离 3.1 乐观锁是一种 3.2 序列化快照隔离(serializable snapshot isolation)非常有趣,它是根据"快照读隔离"所带来的"幻读"问题而提出的解决办法, 即"记录每个活跃事务所读取的记录并在其它事务提交后标记被影响到的记录已经过时",听起来就是件开销非常大的事. 它与SPL相比 的优点就是不需要阻塞. 缺点是对于长时间读取和写入数据的事务很可能会发生冲突并中止更加敏感.

一个数据库可以提供可串行性和线性一致性,这种组合被称为严格的可串行性或强的单副本强可串行性(strong-1SR).基于两阶段锁定的 可串行化实现(参见"两阶段锁定(2PL)"一节)或实际串行执行(参见第"实际串行执行")通常是线性一致性的. 但是,可序列化的快照 隔离(参见"可序列化的快照隔离(SSI)")不是线性一致性的:按照设计,它可以从一致的快照中进行读取,以避免锁定读者和写者之间 的争用.一致性快照的要点就在于它不会包括比快照更新的写入,因此从快照读取不是线性一致性的.

单主复制: 可能是线性一致性. 脑裂、异步复制情况下违反了线性一致性 共识算法: 线性一致性. 多主复制: 非线性一致性. 具有多主程序复制的系统通常不是线性一致的,因为它们同时在多个节点上处理写入,并将其异步复制到其他节点. 因此,它们可能会产生冲突的写入,需要解析(参阅"处理写入冲突").这种冲突是因为缺少单一数据副本人为产生的 无主复制: 也许不是线性一致的. 对于无领导者复制的系统,有时候人们会声称通过要求法定人数读写($w + r&gt; n$)可以获得"强一致性". 这取决于法定人数的具体配置,以及强一致性如何定义(通常不完全正确). 基于时钟(例如,在Cassandra中)的"最后写入胜利"冲突解决方法几乎可以确定是非线性的,由于时钟偏差,不能保证时钟的时间 戳与实际事件顺序一致.松散的法定人数也破坏了线性一致的可能性.即使使用严格的法定人数,非线性一致的行为也是可能的

线性一致性和法定人数

例子图片: https://s2.loli.net/2022/06/04/dGIOEkbF8WRTxQL.png

图中,$x$ 的初始值为0,写入客户端通过向所有三个副本($n = 3, w = 3$)发送写入将$x$ 更新为1.客户端A并发地从两个节点组成的 法定人群($r = 2$ )中读取数据,并在其中一个节点上看到新值1.客户端B也并发地从两个不同的节点组成的法定人数中读取, 并从两个节点中取回了旧值0. 仲裁条件满足( $w + r&gt; n$ ),但是这个执行是非线性一致的: B的请求在A的请求完成后开始,但是B返回旧值,而A返回新值. ​ 有趣的是,通过牺牲性能,可以使Dynamo风格的法定人数线性化: 读取者必须在将结果返回给应用之前,同步执行读修复,并且写入者必须 在发送写入之前,读取法定数量节点的最新状态.然而,由于性能损失,Riak不执行同步读修复. Cassandra在进行法定人数读取时,确实在等 待读修复完成;但是由于使用了最后写入为准的冲突解决方案,当同一个键有多个并发写入时,将不能保证线性一致性. 而且,这种方式只能实现线性一致的读写;不能实现线性一致的比较和设置操作,因为它需要一个共识算法.

总而言之,最安全的做法是: 假设采用Dynamo风格无主复制的系统不能提供线性一致性.

CAP定理

分布式系统会遇到的三座大山: NPC

N: Network Delay,网络延迟 P: Process Pause,进程暂停(GC) C: Clock Drift,时钟漂移

任何线性一致的数据库都有这个问题,不管它是如何实现的.这个问题也不仅仅局限于多数据中心部署,而可能发生在任何不可靠的网络上, 即使在同一个数据中心内也是如此. 问题面临的权衡:

  1. 如果应用需要线性一致性,且某些副本因为网络问题与其他副本断开连接,那么这些副本掉线时不能处理请求.请求必须等到网络问题解决, 或直接返回错误.(无论哪种方式,服务都不可用(unavailable)).
  2. 如果应用不需要线性一致性,那么某个副本即使与其他副本断开连接,也可以独立处理请求(例如多主复制).在这种情况下,应用可以在 网络问题前保持可用,但其行为不是线性一致的.

PS: 这两种选择有时分别称为CP(在网络分区下一致但不可用)和AP(在网络分区下可用但不一致).但是,这种分类方案存在一些缺陷,所以 最好不要这样用.

CAP有时以这种面目出现:一致性,可用性和分区容错性:三者只能择其二.不幸的是这种说法很有误导性,因为网络分区是一种错误,所以它并 不是一个选项:不管你喜不喜欢它都会发生. 在网络正常工作的时候,系统可以提供一致性(线性一致性)和整体可用性.发生网络故障时,你必须在线性一致性和整体可用性之间做出选择. 因此,一个更好的表达CAP的方法可以是一致的,或者在分区时可用.一个更可靠的网络需要减少这个选择,但是在某些时候选择是不可避免的. 在CAP的讨论中,术语可用性有几个相互矛盾的定义,形式化作为一个定理并不符合其通常的含义.许多所谓的“高可用”(容错)系统实 际上不符合CAP对可用性的特殊定义.总而言之,围绕着CAP有很多误解和困惑,并不能帮助我们更好地理解系统,所以最好避免使用CAP.

可用性(Availability): 只要收到用户的请求,服务器就必须给出回应(需要加上时间的因素).

CAP相关论文: https://web.archive.org/web/20220126012236/https://zhuanlan.zhihu.com/p/55053121

通常牺牲"线性一致性"的原因是"性能",而不是"容错". "线性一致性"的速度很慢--这始终是事实

一些基础设施CAP的保证

来源: http://jasonwilder.com/blog/2014/02/04/service-discovery-in-the-cloud/

Name Type AP or CP Language Dependencies Integration
Zookeeper General CP Java JVM Client Binding
Doozer General CP Go Client Binding
Etcd General Mixed (1) Go Client Binding/HTTP
SmartStack Dedicated AP Ruby haproxy/Zookeeper Sidekick (nerve/synapse)
Eureka Dedicated AP Java JVM Java Client
NSQ (lookupd) Dedicated AP Go Client Binding
Serf Dedicated AP Go Local CLI
Spotify (DNS) Dedicated AP N/A Bind DNS Library
SkyDNS Dedicated Mixed (2) Go HTTP/DNS Library

General: 通用; Dedicated: 专用

(1) If using the consistent parameter, inconsistent reads are possible (2) If using a caching DNS client in front of SkyDNS, reads could be inconsistent

在我们做微服务架构时需要知道CAP并做出架构设计或选型.比如注册中心常用的Eureka和Zookeepr实现,Eureka是AP的,Zookeeper 是CP的,Spring Cloud之所以推荐Eureka是因为它认为注册中心的场景允许出现短暂的数据不一致情况,可用性要高于强一致性,再比 如数据库HBase与Cassandra,两者同为NoSQL数据,部分需求两者都可满足,但我们要考虑允不允许出现数据不一致,HBase是强一致性的, Cassandra则是弱一致性的,但换来了更好的可用性

兰伯特(Lamport)时间

它提供了一个全序: 如果你有两个时间戳,则计数器值大者是更大的时间戳.如果计数器值相同,则节点ID越大的,时间戳越大

关键思想: 每个节点和每个客户端跟踪迄今为止所见到的最大计数器值,并在每个请求中包含这个最大计数器值.当一个节点收到 最大计数器值大于自身计数器值的请求或响应时,它立即将自己的计数器设置为这个最大值

兰伯特时间与版本向量的区别: 版本向量可以区分两个操作是并发的,还是一个因果依赖另一个;而兰伯特时间戳总是施行一个全序. 从兰伯特时间戳的全序中,你无法分辨两个操作是并发的还是因果依赖的. 兰伯特时间戳优于版本向量的地方是,它更加紧凑

缺点: 当某个节点需要实时处理用户创建用户名的请求时,这样的方法就无法满足了.节点无法马上(right now)决定这个请求是成功还是失败

总之:为了实诸如如用户名上的唯一约束这种东西,仅有操作的全序是不够的,你还需要知道这个全序何时会尘埃落定.如果你有一个 创建用户名的操作,并且确定在全序中,没有任何其他节点可以在你的操作之前插入对同一用户名的声称,那么你就可以安全地宣告操作执行成功.

全序广播是异步的:消息被保证以固定的顺序可靠地传送,但是不能保证消息何时被送达(所以一个接收者可能落后于其他接收者). 相比之下,线性一致性是新鲜性的保证:读取一定能看见最新的写入值

线性一致的CAS(或自增并返回)寄存器与全序广播都都等价于共识问题.也就是说,如果你能解决其中的一个问题,你可以把它转化成为 其他问题的解决方案

分布式事务与共识

节点能达成一致,对于很多场景都非常重要: 领导选举、原子提交、、、

两阶段提交

缺点: 协调者有单点问题,当协调者失联后参数者会不知所措

三阶段提交(Three-Phase Commit)

两阶段提交被称为阻塞(blocking)原子提交协议,因为存在2PC可能卡住并等待协调者恢复的情况.理论上,可以使一个原子提交协议变为 非阻塞(nonblocking)的,以便在节点失败时不会卡住.

3PC假定网络延迟有界,节点响应时间有限;在大多数具有无限网络延迟和进程暂停的实际系统中(见第8章),它并不能保证原子性.

通常,非阻塞原子提交需要一个完美的故障检测器(perfect failure detector)—— 即一个可靠的机制来判断一个节点是否已经崩溃.在具 有无限延迟的网络中,超时并不是一种可靠的故障检测机制,因为即使没有节点崩溃,请求也可能由于网络问题而超时.出于这个原因,2PC仍 然被使用,尽管大家都清楚可能存在协调者故障的问题.

三阶段提交和二阶段提交最大的区别:

  1. 于协调者[Coordinator]和参与者[Cohort]都设置了超时机制(在2PC中,只有协调者拥有超时机制,即如果在一定时间内没有收到 cohort的消息则默认失败)

  2. 在2PC的准备阶段和提交阶段之间,插入预提交阶段,使3PC拥有CanCommit、PreCommit、DoCommit三个阶段.说白了,PreCommit 是一个缓冲,保证了在最后提交阶段之前各参与节点的状态是一致的

  3. CanCommit阶段. 协调者向参与者发送commit请求,参与者如果可以提交就返回Yes响应,否则返回No响应

  4. PreCommit阶段. Coordinator根据Cohort的反应情况来决定是否可以继续事务的PreCommit操作. 2.1: 假如Coordinator从所有的Cohort获得的反馈都是Yes响应,那么就会进行事务的预执行: 2.1.1: 发送预提交请求.Coordinator向Cohort发送PreCommit请求,并进入Prepared阶段. 2.1.2: 事务预提交.Cohort接收到PreCommit请求后,会执行事务操作,并将undo和redo信息记录到事务日志中. 2.1.3: 响应反馈.如果Cohort成功的执行了事务操作,则返回ACK响应,同时开始等待最终指令. 2.2: 假如有任何一个Cohort向Coordinator发送了No响应,或者等待超时之后,Coordinator都没有接到Cohort的响应, 那么就中断事务: 2.2.1: 发送中断请求.Coordinator向所有Cohort发送abort请求. 2.2.2: 中断事务.Cohort收到来自Coordinator的abort请求之后(或超时之后,仍未收到Cohort的请求),执行事务的中断

  5. DoCommit阶段. 该阶段进行真正的事务提交,也可以分为以下两种情况: 3.1: 执行提交 3.1.1: 发送提交请求.Coordinator接收到Cohort发送的ACK响应,那么他将从预提交状态进入到提交状态.并向所有Cohort发 送doCommit请求. 3.1.2: 事务提交.Cohort接收到doCommit请求之后,执行正式的事务提交.并在完成事务提交之后释放所有事务资源. 3.1.3: 响应反馈.事务提交完之后,向Coordinator发送ACK响应. 3.1.4: 完成事务.Coordinator接收到所有Cohort的ACK响应之后,完成事务. 3.2: 中断事务. Coordinator没有接收到Cohort发送的ACK响应(可能是接受者发送的不是ACK响应,也可能响应超时),那么就会 执行中断事务 3.2.1: 发送中断请求.Coordinator向所有Cohort发送abort请求 3.2.2: 事务回滚.Cohort接收到abort请求之后,利用其在阶段二记录的undo信息来执行事务的回滚操作,并在完成回滚之后 释放所有的事务资源. 3.2.3: 反馈结果.Cohort完成事务回滚之后,向Coordinator发送ACK消息 3.2.4: 中断事务.Coordinator接收到参与者反馈的ACK消息之后,执行事务的中断

在doCommit阶段,如果Cohort无法及时接收到来自Coordinator的doCommit或者rebort请求时,会在等待超时之后,会继续进行事务的提交. (其实这个应该是基于概率来决定的,一句话概括就是,当进入第三阶段时,由于网络超时等原因,虽然参与者没有收到commit或者abort响 应,但是他有理由相信:成功提交的几率很大.)

最本质来讲,3PC避免了状态停滞,在2PC有可能因为各种原因,产生状态停滞.但是3PC会让状态继续下去,虽然有可能继续下去是错的.

3PC的问题是明显的(并没有完全解决2PC的问题3): 即如果进入PreCommit后,Coordinator发出的是abort请求,如果只有一个Cohort 收到并进行了abort操作,而其他对于系统状态未知的Cohort会根据3PC选择继续Commit,那么系统的不一致性就存在了.所以无论是2PC还 是3PC都存在问题.

共识算法和全序广播

全序广播非正式地讲需要满足两个安全属性:

  1. 可靠交付: 没有消息丢失,如果消息被传递到一个节点,它将被传递到所有节点

  2. 全序交付: 消息以相同的顺序传播给每一个节点

全序网络在机器出现故障时也要保证机器恢复后消息能够及时通过并送达

全序广播相当于重复进行多轮共识(每次共识决定与一次消息传递相对应):

  1. 由于"一致同意"属性,所有节点决定以相同的顺序传递相同的消息.
  2. 由于"完整性"属性,消息不会重复.
  3. 由于"有效性"属性,消息不会被损坏,也不能凭空编造.
  4. 由于"终止"属性,消息不会丢失.

违反及时性,"最终一致性"; 违反完整性,"永无一致性"

批处理

MapReduce中Reducer才会输出结果文件到HDFS.

Hadoop MapReduce没有工作流(workflow)概念,所以不能向unix中的管道(pipeline)一样直接将一个进程的输出作为另一个进程 的输入,仅用一个很小的内存缓冲区. 不过流处理就很像了

当我们在讨论连接的时候,我们指的是在数据集中解析某种关联的全量存在. 例如我们假设一个作业是同时处理所有用户的数据,而非仅仅是为某个 特定用户查找数据.

表|仓库连接问题的处理

最简单的方法是逐个遍历活动事件,并为每个遇到的用户ID查询用户数据库. 更好的方法是获取用户数据库的副本(例如,使用ETL进程从数据库 备份中提取数据),并将它和用户行为日志放入同一个分布式文件系统中.然后可以将用户数据库存储在HDFS中的一组文件中,而用户活动记录 存储在另一组文件中,并能用MapReduce将所有相关记录集中到同一个地方进行高效处理

把查询关联数据任务作为一组MapReduce,它可以很好的帮你在不影响应用逻辑的情况下能透明地重试失败的任务.

处理倾斜

社交网络中,大多数用户可能会与几百人有连接,但少数名人可能有数百万的追随者.这种不成比例的活动数据库记录被称为 关键对象(linchpin object)或热键(hot key)

由于MapReduce作业只有在所有Mapper和Reducer都完成时才完成,所有后续作业必须等待最慢的Reducer才能启动.

解决方法:

  1. 检测热键技术 + 多Reducer处理. PS: 后期再进行key的处理的时候,你需要把所有和hot key相关的reduce都再次进行重复发送才行

Reduce端连接和Map端连接

Reducer中执行实际的连接逻辑,被称为Reduce端连接.Mapper扮演着预处理输入数据的角色: 从每个输入记录中提取键值,将键值对分配给 Reducer分区,并按键排序. Reduce端方法的优点是不需要对输入数据做任何假设: 无论其属性和结构如何,Mapper都可以对其预处理以备连接.然而不利的一面是,排序 ,复制至Reducer,以及合并Reducer输入,所有这些操作可能开销巨大.当数据通过MapReduce阶段时,数据可能需要落盘好几次,取决于可用的内 存缓冲区. 另一方面,如果你能对输入数据作出某些假设,则通过使用所谓的Map端连接来加快连接速度是可行的.这种方法使用了一个阉掉Reduce与排 序的MapReduce作业,每个Mapper只是简单地从分布式文件系统中读取一个输入文件块,然后将输出文件写入文件系统,仅此而已.

适用于执行Map端连接的最简单场景是大数据集与小数据集连接的情况.要点在于小数据集需要足够小,以便可以将其全部加载到每个Mapper的 内存中.

Map端连接有好几种优化方式: 广播散列连接、分区散列连接、Map端合并连接、MapReduce工作流与Map端连接、

批处理它不属于事务处理,也不是分析.它和分析比较接近,因为批处理通常会扫过输入数据集的绝大部分.然而MapReduce作业工作流与用于分 析目的的SQL查询是不同的.批处理过程的输出通常不是报表,而是一些其他类型的结构

Google最初使用MapReduce是为其搜索引擎建立索引,虽然Google后来也不仅仅是为这个目的而使用MapReduce. 但如果从构建搜索索引的角度来看,更能帮助理解MapReduce. (直至今日,Hadoop MapReduce仍然是为Lucene/Solr构建索引的好方法)

MapReduce的优点是索引过程很容易理解:文档进,索引出

MapReduce应用大数据集成到系统中更好的解决方案是在批处理作业内创建一个全新的数据库,并将其作为文件写入分布式文件系统中作业的 输出目录,就像上节中的搜索索引一样.这些数据文件一旦写入就是不可变的,可以批量加载到处理只读查询的服务器中.不少键值存储都支持 在MapReduce作业中构建数据库文件,包括Voldemort、Terrapin、ElephantDB和HBase批量加载.

Hadoop开放了将数据不加区分地转储到HDFS的可能性,允许后续再研究如何做进一步处理. 实践经验表明,简单地使数据快速可用——即使它很 古怪,难以使用,使用原始格式——也通常要比事先决定理想数据模型要更有价值

物化中间状态

将这个中间状态写入文件的过程称为物化(materialization). 与Unix管道相比,MapReduce完全物化中间状态的方法存在不足之处:

  1. MapReduce作业只有在前驱作业(生成其输入)中的所有任务都完成时才能启动,而由Unix管道连接的进程会同时启动,输出一旦生成 就会被消费.不同机器上的数据倾斜或负载不均意味着一个作业往往会有一些掉队的任务,比其他任务要慢得多才能完成.必须等待至前驱 作业的所有任务完成,拖慢了整个工作流程的执行.
  2. Mapper通常是多余的:它们仅仅是读取刚刚由Reducer写入的同样文件,为下一个阶段的分区和排序做准备.在许多情况下,Mapper代 码可能是前驱Reducer的一部分:如果Reducer和Mapper的输出有着相同的分区与排序方式,那么Reducer就可以直接串在一起,而不用与 Mapper相互交织.
  3. 将中间状态存储在分布式文件系统中意味着这些文件被复制到多个节点,这些临时数据这么搞就比较过分了.

流处理

了解决MapReduce的这些问题,几种用于分布式批处理的新执行引擎被开发出来,其中最著名的是Spark、Tez和Flink.它们的设计方式有很 多区别,但有一个共同点:把整个工作流作为单个作业来处理,而不是把它分解为独立的子作业 由于它们将工作流显式建模为 数据从几个处理阶段穿过,所以这些系统被称为数据流引擎(dataflow engines).像MapReduce一样,它们 在一条线上通过反复调用用户定义的函数来一次处理一条记录,它们通过输入分区来并行化载荷,它们通过网络将一个函数的输出复制到另一 个函数的输入. 与MapReduce不同,这些功能不需要严格扮演交织的Map与Reduce的角色,而是可以以更灵活的方式进行组合.我们称这些函数为算子 (operators),数据流引擎提供了几种不同的选项来将一个算子的输出连接到另一个算子的输入:

  1. 一种选项是对记录按键重新分区并排序,就像在MapReduce的混洗阶段一样.这种功能可以用于实现排序合并连接和分组,就像在MapReduce 中一样.
  2. 另一种可能是接受多个输入,并以相同的方式进行分区,但跳过排序.当记录的分区重要但顺序无关紧要时,这省去了分区散列连接的工作, 因为构建散列表还是会把顺序随机打乱.
  3. 对于广播散列连接,可以将一个算子的输出,发送到连接算子的所有分区.

这种类型的处理引擎是基于像Dryad和Nephele这样的研究系统,与MapReduce模型相比,它有几个优点:

  1. 排序等昂贵的工作只需要在实际需要的地方执行,而不是默认地在每个Map和Reduce阶段之间出现.
  2. 没有不必要的Map任务,因为Mapper所做的工作通常可以合并到前面的Reduce算子中(因为Mapper不会更改数据集的分区).
  3. 由于工作流中的所有连接和数据依赖都是显式声明的,因此调度程序能够总览全局,知道哪里需要哪些数据,因而能够利用局部性进行优化. 例如,它可以尝试将消费某些数据的任务放在与生成这些数据的任务相同的机器上,从而数据可以通过共享内存缓冲区传输,而不必通过网络复制.
  4. 通常,算子间的中间状态足以保存在内存中或写入本地磁盘,这比写入HDFS需要更少的I/O(必须将其复制到多台机器,并将每个副本写入磁盘). MapReduce已经对Mapper的输出做了这种优化,但数据流引擎将这种思想推广至所有的中间状态.
  5. 算子可以在输入就绪后立即开始执行;后续阶段无需等待前驱阶段整个完成后再开始.
  6. 与MapReduce(为每个任务启动一个新的JVM)相比,现有Java虚拟机(JVM)进程可以重用来运行新算子,从而减少启动开销.

容错

Spark、Flink和Tez避免将中间状态写入HDFS,因此它们采取了不同的方法来容错:如果一台机器发生故障,并且该机器上的中间状态丢失, 则它会从其他仍然可用的数据重新计算. 为了实现这种重新计算,框架必须跟踪一个给定的数据是如何计算的 —— 使用了哪些输入分区？应用了哪些算子？Spark使用弹性分布式 数据集(RDD)的抽象来跟踪数据的谱系,而Flink对算子状态存档,允许恢复运行在执行过程中遇到错误的算子.

RDD(基本上是论文里的): https://zhuanlan.zhihu.com/p/91749572

排序算子不可避免地需要消费全部的输入后才能生成任何输出,因为输入中最后一条输入记录可能具有最小的键,因此需要作为第一条记 录输出.因此,任何需要排序的算子都需要至少暂时地累积状态.但是工作流的许多其他部分可以以流水线方式执行

上面讲的所有存储都有一个假设: 输入是有限的,即已知和有限的大小.

数据库和消息队列在对创建衍生数据的方式有巨大影响: 批处理过程的一个关键特性是,你可以反复运行它们,试验处理步骤, 不用担心损坏输入(因为输入是只读的).而 AMQP/JMS风格的消息传递并非如此:收到消息是具有破坏性的,因为确认可能导 致消息从代理中被删除,因此你不能期望再次运行同一个消费者能得到相同的结果

基于日志的消息代理(log-based message brokers)就是"既有数据库的持久存储方式,又有消息传递的低延迟通知". Apache Kafka ,Amazon Kinesis Streams和Twitter的DistributedLog都是基于日志的消息代理. Google Cloud Pub/Sub 在架构上类似,但对外暴露的是JMS风格的API,而不是日志抽象.尽管这些消息代理将所有消息写入磁盘,但通过跨多台机器分区, 每秒能够实现数百万条消息的吞吐量,并通过复制消息来实现容错性

消费者无法跟上生产者发送信息的速度的处理选择: 丢弃信息,进行缓冲或施加背压. 在这种分类法里,基于日志的方法是缓冲的一种 形式,具有很大,但大小固定的缓冲区(受可用磁盘空间的限制).

双写跑不了"数据冲突"的问题. 所以还是用CDC把.

"流"一般来说,可以做三种事:

  1. 你可以将事件中的数据写入数据库,缓存,搜索索引或类似的存储系统,然后能被其他客户端查询.
  2. 你能以某种方式将事件推送给用户,例如发送报警邮件或推送通知,或将事件流式传输到可实时显示的仪表板上. 在这种情况下,人是流的最终消费者.
  3. 你可以处理一个或多个输入流,并产生一个或多个输出流.流可能会经过由几个这样的处理阶段组成的流水线,最后再输出(选项1或2).

这里主要讨论选项3: 处理流以产生其他衍生流.处理这样的流的代码片段,被称为算子(operator)或作业(job)

与批量作业相比的一个关键区别是,流不会结束.这种差异会带来很多隐含的结果.正如本章开始部分所讨论的,排序对无界数据集没有 意义,因此无法使用排序合并联接(请参阅“Reduce端连接与分组”).容错机制也必须改变:对于已经运行了几分钟的批处理作业,可以 简单地从头开始重启失败任务,但是对于已经运行数年的流作业,重启后从头开始跑可能并不是一个可行的选项

复合事件处理

CEP(complex,event processing)是为分析事件流而开发出的一种方法,CEP系统通常使用高层次的声明式查询语言,比如SQL,或者图形用户 界面,来描述应该检测到的事件模式.这些查询被提交给处理引擎,该引擎消费输入流,并在内部维护一个执行所需匹配的状态机.当发现匹配时, 引擎发出一个复合事件(complex event)(因此得名),并附有检测到的事件模式详情. 在这些系统中,查询和数据之间的关系与普通数据库 相比是颠倒的.通常情况下,数据库会持久存储数据,并将查询视为临时的:当查询进入时,数据库搜索与查询匹配的数据,然后在查询完成时丢 掉查询. CEP引擎反转了角色:查询是长期存储的,来自输入流的事件不断流过它们,搜索匹配事件模式的查询.
ES就实现了这个功能: https://developer.aliyun.com/article/776868

TODO HyperLogLog算法

要校正不正确的设备时钟,一种方法是记录三个时间戳:

  1. 事件发生的时间,取决于设备时钟
  2. 事件发送往服务器的时间,取决于设备时钟
  3. 事件被服务器接收的时间,取决于服务器时钟 通过从第三个时间戳中减去第二个时间戳,可以估算设备时钟和服务器时钟之间的偏移(假设网络延迟与所需的时间戳精度相比可 忽略不计).然后可以将该偏移应用于事件时间戳,从而估计事件实际发生的真实时间(假设设备时钟偏移在事件发生时与送往服务器 之间没有变化). 这并不是流处理独有的问题,批处理有着完全一样的时间推理问题.只是在流处理的上下文中,我们更容易意识到时间的流逝.

流处理的容错

在流处理中也出现了同样的容错问题,但是处理起来没有那么直观:等待某个任务完成之后再使其输出可见并不是一个可行选项,因为 你永远无法处理完一个无限的流. 一个解决方案是将流分解成小块,并像微型批处理一样处理每个块.这种方法被称为微批次(microbatching),它被用于Spark Streaming. 批次的大小通常约为1秒,这是对性能妥协的结果:较小的批次会导致更大的调度与协调开销,而较大的批次意味着流处理器结果可见之前的 延迟要更长 微批次也隐式提供了一个与批次大小相等的滚动窗口(按处理时间而不是事件时间戳分窗).任何需要更大窗口的作业都需要显式地将状态从 一个微批次转移到下一个微批次. Apache Flink则使用不同的方法,它会定期生成状态的滚动存档点并将其写入持久存储.如果流算子崩溃,它可以从最近的存档点 重启,并丢弃从最近检查点到崩溃之间的所有输出.存档点会由消息流中的"壁障"(barrier)触发,类似于微批次之间的边界,但不会强 制一个特定的窗口大小 在流处理框架的范围内,微批次与存档点方法提供了与批处理一样的恰好一次语义.但是,只要输出离开流处理器(例如,写入数据库 ,向外部消息代理发送消息,或发送电子邮件),框架就无法抛弃失败批次的输出了.在这种情况下,重启失败任务会导致外部副作用发 生两次,只有微批次或存档点不足以阻止这一问题

在Lambda架构中建议并行运行两个不同的系统: 批处理系统和独立的流系统. 流处理器消耗事件并快速生成对视图的近似更新,批处理 器稍后将使用同一组事件并生成衍生视图的更正版本. 这个设计背后的原因是批处理更简单,因此不易出错,而流处理被认为是不太可靠和 难以容错的. 而且,流处理可以使用快速近似算法,而批处理使用较慢的精确算法.

虽然因果是个很重要的概念,但实际上如果跟踪所有的因果关系是不切实际的

Dynamo

解决数据冲突会带来两个额外问题: 何时解决? 谁来解决? Dynamo针对的主要是需要"永远可写"数据仓库的应用,并且它的"延迟敏感"使得它不能像Chord和Pastry一样使用多跳路由.
Dynamo可以被描述为: 一个零跳(zero hop)分布式哈希表(DHT) 在发生故障并且存在并发更新的场景下,版本会发生分叉 vector clock有一个潜在问题: 如果有多个节点先后参与同一个对象的写操作,那这个对象的clock vector会变得很长. 但在实际中这 不太可能发生,因为写操作只会发生在perference list(存key的值的物理节点列表)的前N个节点中的一个来执行. 只有在网络分裂或多台 服务器挂掉的情况下,写操作才可能由非preference list前N个节点来执行,导致vector clock变长. Dynamo采用了一种vector clock截断 方案: 另外保存一个和(node, counter)对应的时间戳,记录对应的节点最后一次更新该记录的时间.当vector clock里的(node, counter) 数量达到一个阈值(例如,10)时,就删除最老的一项. 这样会带来无法精确判断部分后代的因果关系的问题. Merkle Tree缺点: 每当有节点加入或离开系统时,一些key range会变,因此对应的tree需要重新计算 判断不可达: 节点B只要没有应答节点A的消息,A就可以认为B不可达,即便B可以应答C的消息 TODO 去中心化故障检测协议使用简单的 gossip 风格协议,使得系统内的每个节点都可以感知 到其他节点的加入或离开 写请求由preference list内的前N个节点中的任意一个参与者,好处是可以保证写入的顺序化,坏处是会导致不均匀的负载分布,损害SLA 为了解决这个问题,preference list内的所有N个节点都可以参与写操作,而且为一个写操作之前通常有一个读操作,因此写操作的参与者 都选择为: 前一次读操作返回最快的那个节点,这个信息存储在读操作返回的上下文中