数据密集型应用: 对于一个应用系统, 如果"数据"是其成败的决定性因素, 包括数据的规模, 数据的复杂度或者数据产生与变化的速率等, 我们就可以称为"数据密集型应用系统".
数据密集型应用通常包括:
数据库, 高速缓存, 索引, 流式处理, 批处理
"一项针对大型互联网服务的调查发现, 运维这的配置错误巨人是系统下线的首要原因, 而硬件问题(服务器或网络)仅在10%-25%的故障中有所影响"
引用文献在 Why do Internet services fail, and what can be done about it?
In 1986
he found that operator error was the largest single cause
of failure in deployed Tandem systems, accounting for
42% of failures, with software the runner-up at 25%. We
found strikingly similar percentages at Online and Content.
其中认为操作导致故障占总体故障率的42%.
"如果限制过多, 人们就会想法来饶过它, 这回抵消其正面作用, 因此解决之道在于很好的平衡."
这件事情很有体会, 在360工作的时候, 有个工程师半夜3点要紧急上线, 但没有目标机器权限, 于是利用了提权漏洞获取了root, 结果被通报批评.
临场决定权这件事很重要, 只有这样才能发挥出人最大的效率. 固定死的规矩只适合一成不变的业务. 想要得到灵活性, 就要下放权力. 不能学蒋公打星际.
人的本性不能视而不见. 忽视人的本性妄图用规则去管理的, 跟忽视系统极限盲目优化没什么区别.
推特在12年系统的平均推送速度是4.6k rps, 峰值是 12k rps.
数据来自 The Architecture Twitter Uses To Deal With 150M Active Users, 300K QPS, A 22 MB/S Firehose, And Send Tweets In Under 5 Seconds
就结论而言, Twitter和微博均采用了同样的方案, 大V采用推方案, 普通用户采用拉方案.
支持文档数据模型的主要论点是模式灵活性, 由于局部性而带来较好的性能, 对于某些应用来说, 它更接近于应用程序所使用的数据结构. 关系模型则强在联结操作, 多对一和多对多关系简洁的表达上, 与文档模型抗衡.
该如何选择文档型数据库和关系型数据库?
如果应用数据具有类似文档的结构则优先选择文档型数据库. 高度关联则要考虑图数据库.
这里的比喻很好, 文档数据库是读模式, 而关系数据库是写模式. 读模式类似编程语言中的动态类型检查, 而写模式类似于静态类型检查.
为什么声明式语言更适合并行执行?
因为命令式代码指定了特定的执行顺序, 很难在多核和多台机器上并行优化. 所以数据库查询语言尽可能选择声明式语言而不是API, 可以更多地隐藏细节进行优化, 达成更好的抽象层次.
MongoDB的聚合管道重新发明了SQL, 哈哈哈哈哈哈
没有银弹, 增加新的索引虽然能提升查询性能, 但是写入时的复杂度也会提升, 所以会降低写入速度(并不一定是同步更新索引).
追加日志型存储的优点有:
- 顺序读写性能高, 无论是磁盘还是SSD.
- 不会有更新到一半的脏数据问题
- 不断合并记录可以避免数据碎片化
随之而来的哈希表索引的缺点也有:
- 如果内存装不下, 性能则非常惨
- 哈希冲突处理复杂
- 区间查询效率不高
SSTable (排序字符串表) 的优势是:
由于有序, 所以可以进行稀疏hash, 以此来支持扫描操作并较少hash空间消耗.
同时, 合并过程中由于有序, 可以采用类似合并排序的算法进行合并, 同时由于分段结构, 重复的旧值可以快速被淘汰
记录数据进行压缩后还可以减少磁盘空间和I/O带宽和占用
构建 SSTable 也很简单, 首先内存中保留平衡树(内存表), 内存表达到阈值后进行写盘(size n MB), 同时旧内存表锁定, 新内存表进行写入. 同时后台进行压缩和合并, 丢弃重复值和被删除值.
为避免崩溃, 可以同时维护一个临时表, 内存更新的同时同步到硬盘.
读取时现在内存中查找key, 然后取最新的段文件, 然后是次新的, 以此类推.
SSTable 的衍生品即 LevelDB和RocksDB, Canssandra和HBase也采用了类似的存储结构. 而SSTable是 Google的BigTable论文引入的(SSTable & 内存表).
这个索引结构最初也被称为LSM-Tree
性能优化也有很多手段, 利用BloomFilter提升检索性能, 大小分级和分层压缩来提升存储过程性能(LevelDB采用分层压缩所以叫这个名字). LevelDB和RocksDB采用分层压缩, HBase采用大小分级, Cassandra则二者均支持.
大小分级指较新和较小的SSTable被连续合并到较旧较大的SSTable. 分层压缩则指key的范围(两个key对应的区间)被分裂成更多个小的SSTable, 旧数据被移动到单独的层级(可以逐步进行并节省空间).
B-Tree将数据库分解成固定大小的块或页, 通常为4K, 这是内部读写的最小单元, 更贴近硬件(磁盘).
B-Tree中一个页所包含的子页的引用数量成为分支因子.
B-Tree 时间复杂度为O(logn), 分支因子为500的4K页的4级树可以存储高达256TB的数据.
B-Tree base 的数据库通常由预写日志(write-ahead Log, WAL), 仅支持追加修改, 修改B-Tree会先更新WAL.
B-Tree对应也有一些优化方案, 例如 写时复制来控制崩溃并提升并发性能, 仅保存key的缩略信息节省叶空间, 对树进行布局来提升连续读写性能, 添加额外指针到叶来提升扫描性能, 或采用变体例如分形树来减少磁盘寻道.
通常B-Tree读性能较好, 而LSM-Tree写性能较好.
LSM-Tree的优点有
- B-Tree写入成本相当高, 因为会对整个页进行写入, 而LSM-Tree则是增量写入.
- 二者都存在写放大, B-Tree是数据结构限制, 以及为了可靠性的副本. LSM-Tree则是压缩整理带来的写放大. 而写放大会占用磁盘资源以及如果是SSD的话还会损耗寿命.
- LSM-Tree由于顺序写, 因此拥有更高的I/O性能
- LSM-Tree占用磁盘会更小, 一是可以压缩, 二是B-Tree在页进行分裂的时候, 会留出新的空间, 而这些为了4K对齐, 是全都要写到磁盘上的. 而且会产生碎片.
LSM-Tree的缺点有:
- 进行后台压缩时, 会占用当前磁盘资源, 导致性能抖动, 而B-Tree则有确定的访问性能(类似有GC的语言开始GC了).
- 压缩会随容量增长而越来越消耗资源
- 写入吞吐和压缩需要仔细管理, 因为压缩慢了会导致容量不够用和读取性能降低, 而压缩太快了很有可能占用磁盘性能.
- B-Tree由于键的唯一性而能更好的降低锁的复杂性从而更好的支持事务.
堆文件即最终存放数据的位置, 它可以防止多个索引存在的情况下的数据复制. 当更新大于原有值得情况下较为复杂, 除了树分裂, 重新复制数据以外, 还要更新索引或者添加间接指针.
通常主键会引用堆文件, 而二级索引会引用主键.
这里我不是很理解, "因此可能希望将索引行直接存储在索引中. 这被称为聚集索引". 英文原文也是 "so it can be desirable to store the indexed row directly within an index. This is known as a clustered index." 按说不是把数据存储到索引中么? 索引存储到索引中没看懂.
在InnoDB中, 主键是聚集索引(clustered index). 二级索引引用主键(非聚集索引). 而聚集索引会带来事务上更多处理和额外得性能开销.
最常见的多列索引称为级联索引, 就是简单将两个key拼接到一起. 拼接顺序决定了它的查找模式.
对于多维查询, 标准的K-V索引无法很好的解决. 一种方法是用空格填充曲线进行降维, 然后索引到B-Tree(文献中就是Z-region, UB-Tree). 或使用专门的索引R-Tree
下面的举的商品颜色的例子就非常适合用级联索引, 比如大家经常将RGB色表示为拼接在一起的十六进制.
Lucene能在某个编辑距离内搜索文本, Lucene的内存中索引是key中的字符序列的有限状态自动机类似字典树(即这个索引是值中的字符串生成的FSA), 并且可以转换为Levenshtein自动机, 在给定的编辑距离中更高效的检索.
内存型数据库快不是因为不读写磁盘, 磁盘型数据库也可以通过大内存让操作系统缓存磁盘块. 而是因为它不会把数据结构编码成专门为磁盘设计的结构从而降低开销.
OLTP大多数面向行存储, OLAP则相反, 面向列存储.
只要数据不是很离散, 面向列的存储是非常适合压缩的. 通常可以使用bit图压缩. 并且查询通过位逻辑操作可以很快完成.
列存储同样可以排序, 排序利于检索和压缩, 如同行存储的索引一样. 不同的是列存储并没有指针可以存储. 所以叫做排序而不是索引.
Protobuf 二进制协议本身与fieldTag锚定, 故字段名称本身并不重要, 但字段顺序是固定的, 因此增长只能向后扩张. 对于向后兼容和向前兼容问题, 受影响的会是必须字段, 因为会导致无法删减或无法新增.
Avro 更适合数据模式经常变动和大数据量的情况.
复制日志通常有:
- 基于语句复制, 缺点是如果有非确定性的语句或副作用会导致节点不一致.
- 预写日志, 实现太过底层, 与实现强关联, 不易升级.
- 基于行的逻辑日志复制, MySQL 的binlog可以配置为这种模式.
- 基于触发器, 灵活, 但容易出问题.
关于复制滞后问题:
- 读自己的写可以做到按逻辑区分, 按时间戳区分. 面临的问题有: 逻辑不容易区分或跨数据中心或多客户端等问题.
- 单调读可以避免读取到从副本异步同步不一致的情况.
- 前缀一致读用来避免分区延迟过大的问题.
关于多主问题:
- 多主性能好, 也可以容忍数据中心失效及网络问题. 但其实是把同步问题从整个库层面切换到了每个写单元, 从而面临写冲突问题.
多主情况下的从图解决一般有以下几种方法:
- 避免冲突
- 使其收敛于一致状态, 例如用消息ID, 副本ID, 合并数据, 逻辑延后至应用层. 而延后至逻辑层又分为在写入时执行和在读取时执行.
多主的拓扑结构分为环形, 星型, 全至全结构, 其中环形和星型有hub的概念, 因此当hub故障时, 同步就会滞后. 而全至全结构由于等效链路的耗时不一致会导致覆盖问题.
无主节点复制即quorum机制, 但不同步发生时, 会采用读修复, 但如果有些冷数据不常读取, 这时候就会产生风险(比如一个3node系统, a,b均处于v7, 而c处于v6, 这时b节点离线, 新补充进来的全新节点则无法quorum). 有些实现则会用反熵过程来同步, 但很明显会造成同步滞后.
关于读写quorum, 公式为 w + r > n, 其中w为写节点确认数量, r为至少查询节点数量, n为副本数量. 这个公式意味着写节点确认数量和查询节点数量必须有覆盖重合(防止恰好读取和写入全是不同的节点的情况), 否则就无法进行quorum.
通常读取和写入都会发送到所有的quorum节点, 而阈值的设置是达到该值即可返回的阈值.
quorum 不是银弹, 其自身也有很多问题, 例如宽松quorum会导致数据不一致, 同时发生的事务无法判断先后顺序, 写操作与读操作同时发生会导致读取不确定性, 写时故障会导致脏读, 节点的故障恢复恰好处于读写仲裁边际, 会导致读取的不确定性.
而 quorum 本身也无法保证写后读, 单调读, 前缀读的顺序一致性.
监控旧值对于quorum也非常重要, 如果复制滞后过长, 则需要警惕容量,性能或故障问题. 另外有些只实现了读取修复而没有实现反熵的系统可能会存在非常旧的值.
宽松quorum在集群达不到quorum数量时, 为可用性提供了一些保障, 即把数据临时存放于某些节点, 当集群恢复后, 将数据回传.
针对并发写问题, 解决方案有:
- LWW(last write wins, 最后写入者获胜). 这种方法需要精确时钟, 他会抛弃掉任何中间结果, Cassandra采用这种方式作为唯一的并发写入方案. 如果中间过程不可丢弃, 则这种方法并不适用. 如果需要LWW安全无副作用, 可以采用只允许写入一次的方式, 将并发过程全部记录下来.
如何确定并发? 如果两个操作都不在另一个之前发生(没有明确的互相依赖关系) 则认为时并发的. 注意, 是否并发跟而这发生的相对时钟差距没关系. 因为请求发起端和数据库对时钟有不同的定义(比如网络问题). 而且时钟的粒度也无法很好的定义.
该页的示例中详细描述了事务的前后依赖关系和基于版本的并发控制. 算法工作流程如下:
- 服务器端维护每个主键的版本号, 新的值写入时递增版本号. 并写入新值和版本号.
- 客户端读取主键时, 服务器返回所有的(未被覆盖的)当前值以及版本号, 且要求写之前客户端需要先发送读取请求.
- 客户端写主键, 写请求必须包含之前读取到的版本号, 值, 和新的值合并后的集合. 可以设置为写请求会返回当前所有值. 方便本地更新结果.
- 当服务器端接收到带有版本号的写入时, 判断版本号, 如果服务器版本号低, 则全部覆盖, 如果服务器端版本号高, 则保存所有值, 因为这是并发操作.
这种复杂的版本号控制有专门的数据结构实现, 例如 Riak 支持 CRDT.
到更复杂的多节点无主集群时, 这种情况会被扩展成为版本矢量.
数据分区面临的首要问题是如何将数据均匀分布, 尽可能避免读写热点.
键值模型(基于关键字的区间分区)的数据分区可以倾向区间分布(例如用日期分片), 优点是支持范围查询, 缺点是如果逻辑并不常用区间查询的情况下, 则仍会面临热点问题.
同样也可以使用基于关键字哈希值分区但会丧失范围查询特性, 以及在某些极端情况下(例如单个热点数据), 仍会面临热点问题.
目前最好的方式还是需要依据需求来定制存储方式.
如果需要二级索引, 则索引的高效性仍然面临数据分区同样的问题, 即如果二级索引直接按照区间分布式布置(基于文档的二级索引分区, 本地索引), 则会明显降低查询效率.
而如果基于关键字进行分区(全局索引), 查询效率会高, 但写入效率会降低并且规则复杂且有写放大.
而且为了保证二级索引及时得到更新, 还要引入跨区分布式事务, 性能会进一步降低, 所以目前实现了跨区分布式二级索引的数据库都是异步实现.
节点的离线和新增是很常见的情况, 因此分区再平衡是设计中的重要课题:
- 参考因子有三个, 数据, 分区, 节点.
- 不要用取模, 因为取模会导致所有数据对应分区, 分区对应节点的重新映射. 代价太高.
- 固定数量的分区(Riak, Elasticsearch, Couchbase, Voldemort)不会导致所有数据对应分区的重新映射, 而是会移动对应节点容量的分区, 并且移动过程中旧有分区仍然可以使用. 但缺点是需要提前规划总体分区大小. 分区太大不便于迁移, 分区太小性能低. 而且如果区域划分不当, 仍然会面临数据倾斜导致的热点问题.
- 动态分区(HBase, RethinkDB)会基于设定的节点的最大容量和最小容量进行分区, 但缺点是会面临刚开始数据很小而集群很大的空置问题, 为了解决这个问题, Hbase 和 MongoDB都支持初始分区(预分裂).
- 按节点比例分区(Cassandra, Ketama), 这类分区最大的问题是一次可能要扩容一倍节点, 才能有较好的平衡效果(该结论出自360基础平台部实践经验).
自动再平衡与手动再平衡
- 自动再平衡响应快速, 但如果由第三方风险的情况下(例如突发流量造成节点响应延长), 这时触发自动再平衡则会加重集群压力.
- 除此之外当然有手动再平衡, 以及中间方案: 数据库提出平衡方案, 供管理员手动确认.
从我在CEPH的实践经验来看, 如果节点可靠性并不高(尤其是像CEPH OSD这种, 映射的直接是硬盘), 并且节点数量十分庞大. 那么自动再平衡会是更好的方案. CEPH 为了降低自动再平衡过程中对系统造成压力, 可以配置内部网络和外部网络来区分系统流量和用户流量.
我们回顾微博热搜的挂机事件, 从分区模型来考虑, 如果微博搜索用的是类似Elasticsearch的模型, 那么会是一个固定数量分区方案. 在再平衡过程中(即扩容过程), 首先要增加节点, 然后移动分区. 在分区移动完毕之前, 系统仍然会面临高压力的情况. 尤其是系统特别庞大的情况下, 移动分区很可能在热点事件热度消散后, 分区仍然没有全部移动完毕. 因此分区的粒度决定了集群压力下降曲线的平滑程度和延时. 精确的分区大小和降级策略将会是保证服务可用性的关键.
而数据的分区形式和二级索引的分区形式也会直接影响集群扩容的迅捷程度. 热搜数据注定会是一个头部巨大而尾部特别长的模型. 导致热搜挂掉也是头部数据. 因此为了降低系统查询延时(这将直接影响QPS和CPU占用, 最终影响服务质量). 头部数据的分区形式肯定是基于关键字的hash分区. 由此造成损失范围查询特性是可以接受的. 头部数据应该尽可能分布在多个节点上以提升性能, 并且头部数据应尽可能内聚, 减少跨节点查询. 二级索引也是同样的道理, 应尽可能在单节点完成全部查询以提升性能. 为此Build二级索引可能还需要跨区事务. 这进一步加剧了实现的复杂程度.
整个微博热搜系统实现的复杂度是由于头部热点数据的体积和访问量异常庞大导致的. 而社交网络消息传递的速度则在时间维度上提出了新的挑战, 二级索引虽然是异步的, 但也要快! 不然大家热搜看不到事态的新进展, 慢慢兴趣就丧失掉了. 所以, 这个系统比看上去要难实现太多了.
请求路由则相对简单些, 现在大家要么采用外部方案来做服务发现例如Zookeeper, 或内部集成方案, 例如MongoDB的mongos守护进程, 又或者Cassandra或Riak采用gossip协议来同步集群状态, 最后还有Couchbase这种利用名为moxi路由选择层来学习路由变化.
请求路由策略分为以下几种
- 节点实例完成路由或向其他节点的路由
- 实现一个路由层
- 客户端自我感知
事务提供的安全保证即ACID, 原子性(Actomicity), 一致性(Consistency), 隔离性(Isolation), 持久性(Durability). 如同CAP一样, 这个定义也十分模糊.
其中原子性定义的特征是: 在出错时终止事务, 并将部分完成的写入全部丢弃.
一致性比较模糊, 指的是热河数据的更改必须满足这些状态的约束. 但实际上一致性时应用层定义的.
隔离性意味着并发执行的多个事务相互隔离, 他们不能相互交叉. 经典的数据库教材把隔离定义为可串行化. 但在实践中由于性能问题很少使用串行化隔离.
持久性保证一旦事务提交成功, 即使存在硬件故障或数据库崩溃, 事务写入的任何数据也不会消失.
单对象上实现ACID并不是事务, 事务指的是多个对象聚合为一个逻辑单元的操作. 但如果单对象无法具有事务特性, 则多对象事务也无从谈起.
通常对于关系型数据模型, 缺少规范化的文档类型数据, 以及数据库的二级索引, 这些都需要多对象事务的支持.
ACID 数据库基于: 如果违反ACID则完全放弃整个事务. 而不是部分放弃.
这里特别指出了无主节点复制的数据存储不会完全撤销已完成的操作.
然后这里还黑了一波Django, 说里面的ORM事务出现异常只会抛出异常而不支持安全重试.
这里对安全重试也进行了详细说明.
如果操作的数据不存在依赖关系, 则可以安全的并行执行. 而如果存在竞争条件, 则会引发并发问题. 而并发问题很难通过测试发现. 所以事务隔离的出现是为了隐藏这些细节.
实现可串行化的隔离界别通常对性能损失严重, 所以大多数数据库转而实现弱隔离级别. 甚至一些很流行的关系数据库系统(被认为是ACID兼容)其实采用的也是弱级别隔离. 选择适当的隔离界别才能更好的构筑系统.
读-提交提供如下保证:
脏写即事务中间结果被覆盖(事务隔离性被打破), 这里有个需要注意的地方是, 防止脏写并不意味着事务就一定正确了, 最简单就是两笔订单同时扣款的情况, 这时候需要严格的串行化.
读-提交隔离很流行, Oracle 11g, PostgreSQL, SQL Server2012, MemSQL均是默认配置.
防止脏写通常用行级锁实现. 行级锁是数据库自动实现的.
防止脏读一般会数据库会持有旧值, 在事务执行完毕之前一直返回旧值, 在这里加锁会严重影响性能. 还在使用锁的数据库有 设置后的IBM DB2和 SQL Server.
不可重复读取(nonrepeatable read)或读倾斜(read skew), 指的是事务在执行过程中穿插了其他事务导致实际结果领先于读取到的结果的情况(即稍后会读到正常的数据).
这种情况有时候不是刷新一下就能解决的, 比如文中提到的快照或者分析和完整性检查等. 本质上是要求获取活动的数据库的处于一个所有事务都执行完毕的最终状态的数据.
解决方法是快照级别隔离. 目前 PostgreSQL, MySQL(InnoDB), Oracle, SQLServer等均支持.
实现快照级别隔离通常用写锁来防止脏写, 用版本来控制脏读, 这被称为多版本并发控制 (MVCC, Multi-Version Concurrency Control).
支持快照级别隔离的数据库通常用MVCC顺便实现读-提交隔离. 在读-提交级别下,对每一个不同的查询单独船舰一个快照, 快照级别隔离则是使用一个快照来运行整个事务.
PostgreSQL 具体实现为每个操作均记录created_by和delete_by属性, 形成类似链表的扁平结构, 来控制版本. 通过对比属性值的大小和引用关系,以及最终完成状态, 来确定最终的返回结果.
可见有如下的条件:
其实到PG的那个例子, 就是能读取的版本必须delete_id和create_id均小于(其他事务在进行中, 读取旧版本)等于(这就是我操作的数据)当前版本或为空(没有竞态).
通常实现方式是索引返回所有版本. 然后进行过滤.
优化方案有:
可重复读在System R 1975年定义, PG 和MySQL均称自己的快照级别隔离叫可重复度, Oracle称之为可串行化, 但实际上实现与保证还是有差别. 另, IBM DB2真正实现了可串行化级别的隔离.
防止更新丢失的本质原理是对对象的具有上下文关系的事务操作. 比如举例中的更新账户余额, 需要先读取出来, 扣除开支, 然后写入, 两次事务操作之间有明显的上下文关系.
许多数据库提供原子写操作防止将数据读入本地从而引入更多不确定性因素.
UPDATE counters SET value = value + 1 WHERE key = 'foo'; 这种语句在大多数关系型数据库中是并发安全的. MongoDB和Redis也支持了一部分数据结构的源自写操作.
但上下文关系要求过程与数据库分离的, 那就无法使用原子写操作了. 最简单的状况就是另一端有副作用, 导致它也要参与事务过程. 比如调用多个系统的事务.
通常原子写操作实现方式是对读取对象加独占锁. 这种技术也被称为"游标稳定性".
另一种实现方式是强制所有原子操作都在单线程上进行. 即强制串行化.
这里同时提示了必须要了解ORM是如何运作的, 不能假定它采取了原子写操作.
显式加锁会面临本地逻辑冲突和死锁问题.
自动检测更新丢失指的是先允许并发, 然后检测到了更新丢失风险后, 终止当前事务并退回到防止更新丢失的"读取-修改-写回"方式. 这种方式可以利用快照级别隔离来高效的实现.
PG, Oracle, SQL Server都可以正确实现这个过程. 但MySQL的InnoDB的可重复读不支持检测更新丢失然后终止.
如果快照级别隔离必须防止更新丢失,则MySQL属于没有完全支持快照级别隔离.
更新丢失检测可以自动辨别竞态, 让业务有效避免设计或编写错误.
原子比较在不提供事务支持的数据库中会有作用. 原子比较即在写入时检测对象值, 如果对象值符合期望, 则写入. 但这个需要看数据库的具体实现, 如果对象的值有快照, 那就更要小心了.
这里提到了对于分布式系统, 比如多主节点或者无主节点的多副本数据库, 加锁和原子操作就不适用了. 如果操作间彼此没有竞态或上下文, 即可交换(顺序无关), 那么合并结果就行了.
最后写入者获胜(LWW) 容易丢失更新, 但这是这类数据库的默认配置.
写倾斜即多个事务读取相同的一组对象(读取有快照级别隔离), 然后更新其中不互斥的部分, 互斥发生在更新完毕后的之前的对象的状态. 如果更新的是互斥的部分, 则会发生脏写(结果被覆盖)或者更新丢失(依赖关系丢失).
写倾斜需要真正的可串行化隔离, 所以PG, MySQL(InnoDB), Oracle, SQL Server 都不支持检测写倾斜.
通常的避免写倾斜的方案是增加触发器或物化视图. 较简单的方案是直接加锁.
这里指出了预定会议室这样的例子可以用PG的范围类型来解决.
这里再次树立了写倾斜是如何产生的, 即, 写操作会造成读操作的结果的改变, 即会发生写倾斜. 先写再读同样是等价的操作.
对于可以加锁的情况, 加锁可以避免写倾斜, 但假设如果无法加锁(例如检测是否没有某个值), 则没办法避免写倾斜.
这种在一个事务中会写入改变另一个事务查询结果的现象称为幻读. 快照级别隔离可以避免只读查询(不对读取到的结果造成修改)的幻读, 但是对于读写事务, 无法解决.
对于幻读问题, 可串行化是终极解决方案. 实体化冲突时中间解决方案, 具体的操作即将冲突实体化, 把幻读问题转变为针对数据库中一组具体行的所冲突问题.
例子中举例了订会议室幻读问题可以将会议室使用时间进行分段, 这样幻读问题就变成了对时间段的冲突检测问题.
串行化实际分以下几种
实际串行执行被验证可行是在2007年The End of an Architectural Era(It’s Time for a Complete Rewrite).
而串行化优化主要思路有:
VoltDB/H-Store, Redis, Datomic 采用串行方式执行事务. 由于其可以一定程度避免多线程中锁的开销, 因此可能会比支持并发的系统效率更高.
采用存储过程进行事务封装最大的好处是可以避免交互式事务所造成的资源占用.
传统数据库存储过程由于实现标准, 版本管理, 性能需要优化等问题, 导致不是十分流行.
而最新的存储过程则直接用通用编程语言实现, 例如 VoltDB使用java或Groovy, Datomic 使用java或Clojure, Redis使用Lua.
存储过程在内存型数据库上使用吞吐会比磁盘型数据库好很多.
如果能把串行事务控制在单个分区, 则访问均匀的情况下, 增加节点即可增加性能. 但如果需要执行跨区事务, 则需要全部加锁, VoltDB的测试数据指出跨区事务只有1000TPS.
良好的分区需要在应用层去良好的设计数据结构. 而涉及多个二级索引的情况下, 将会很难处理.
当满足这些约束条件时, 串行执行事务可以实现串行化隔离:
即在读写阶段都加锁. 本质上时精细化串行执行中的可并行部分以提升性能. 当然, 这会让实现变得更复杂.
目前 2PL 已经应用于 MySQL(InnoDB), SQL Server 中的 可串行化隔离. 以及 DB2中的 可重复读隔离.
2PL强调, 只读事务可以持有共享模式锁. 一旦要求写入就要等待(从一开始就要等待), 如果自己要写入就要升级为独占模式锁. 写入型事务只要有写入, 就要用独占模式获取锁. 一旦获得锁后, 要持有到事务结束. 获取和结束后释放锁, 称为两阶段.
而防止死锁主要靠数据库系统自己实现.
2PL如果锁的过多, 则会造成大面积性能下降(竞态占比). 而且具有严重的不确定性.
对于幻读问题, 2PL还要单独处理, 即谓词锁(或属性谓词锁). 它的面积更大, 不属于某个对象, 而是用于描述满足搜索条件的所有查询对象.
由于谓词锁匹配的是范围, 所以属于范围但不存在的数据同样可以进行加锁, 所以可以避免幻读.
由于谓词锁会造成性能问题, 所以大多数使用 2PL 的数据库实际上实现的是区间索引锁(或next-key-locking). 本质上时谓词锁的简化或近似版本.
索引区间锁即对原本的谓词锁的范围进行扩大化和泛化到整个索引上, 从而减少复杂锁条件进行竞态查询时的复杂度. 因为谓词锁是索引区间锁的子集, 所以必然会命中锁.
没有索引区间锁解决不了的问题, 如果有, 就锁表.
SSI 由 Michael J Cahill 博士于 2008年提出. 参考文献: Serializable Isolation for Snapshot Databases
没有银弹, SSI的基本思路是乐观并发控制, 与之相比2PL和串行执行是悲观并发控制机制.
SSI 会在的确发生冲突的时候重试. 所以, 如果业务本身竞态少, 则适合SSI, 否则SSI会发生大量重试, 导致性能占用, 此时反而悲观并发控制会表现得更好.
并且可并发事务SSI会并发执行, 比如原子自增操作. 它试图去并发执行(前提是不会进行读取, 否则就脏读了).
SSI基于快照, 为了避免快照造成的问题, 增加了算法来检测写入之间的串行化冲突来决定终止哪些事务并重试.
SSI具体怎样检测呢? 检测主要是以下几个方面:
SSI在检测时, 会等到提交时才会进行检测, 检测的内容是MVCC可见性造成的忽略的那些写操作, 而等到提交才进行终止, 则像CPU的分支预测规则, 因为是乐观的, 先并发执行.
如果竞态数据本身提交后没有写操作, 即没有写倾斜风险. 则自己的执行结果也可以写入了. 这样就完成了并行. 此外, 对于需要运行很长时间的事务, 也减少了重试成本.
SSI在幻读处理上使用了类似索引区间锁类似的技术, 不过不会阻塞其他事务. 会检测索引区间, 如果索引区间发生了写操作, 则终止并进行重试. 借此可以更早地发现冲突.
粒度决定能性能向哪方面倾斜, 如果粒度过细, 虽然可以很好的检测竞态(细化范围, 缩小范围), 但是会带来开销. 而粗粒度虽然开销少, 但是影响范围会扩大.
SSI在只读查询上无安全不需要锁, 所以读取性能很好.
SSI 与 串行化执行相比, 可以多节点并行化, FundationDB 实现了冲突检测分布在多台机器上以提高吞吐量. 同时对于耗时长的事务也很友好.
这里重新梳理了一些核心概念:
写倾斜和幻读的区别是, 写倾斜的条件实体可能是复杂的关系而并非简单的值. 幻读则包含写倾斜和读取条件实体是简单的值的情况.
实现可串行化由三种不同的方法:
这里说明了单机系统的情况, 只存在正确运行或者故障这两种状态, 不存在中间状态. 而分布式系统会存在中间状态. 我们在编写程序时也应该尽量让状态收束, 这有利于内聚性.
这里列举了云计算和超算时分布式系统模式的两个极端. 超算更趋近于一个巨大的单机系统, 高内聚, 高耦合, 性能高, 可靠性高, 并且故障可以使整个集群停止. 而云计算则正相反, 云计算十分离散, 可靠性低, 但故障不能让整个集群停止, 存在大量的部分失效, 并且与集群规模呈正相关.
这里指出了互联网服务大部分都是无共享系统, 网络均是异步网络. 因此网络的任何节点和阶段均有可能出现问题. 而设置超时机制是通用解决方案.
数据表明网络故障非常频繁, 尽管增加冗余可以控制故障, 但仍热按无法避免人为故障.
这里主要强调了协议级回复与应用级回复不是一回事. 如果消息要跨越层级, 则不同层级的副作用(高层级故障)仍然会使通信失败. END-TO-END ARGUMENTS IN SYSTEM DESIGN
这里指出了尽管可以利用通信往返加上波动范围值来设定超时, 但一旦有大流量, 很有可能就会造成失效. 而失效后的压力转移则可能造成失效扩散.
超时没有标准答案. 而且这里可能包含了更严重的后果, 比如有副作用的调用, 超时会造成副作用重复执行.
这里指出了可能排队的节点, 例如交换机, CPU繁忙, 虚拟机管理器, TCP流量控制,
这里提到了Phi Accrual故障检测器已经在Akka和Cassandra中使用. The ϕ Accrual Failure Detector
这里举了同步电话网络ISDN的例子, 他能保证电路建立时预留通固定信空间. 没有排队. 最大端到端延迟是固定的. 称之为有界延迟.
这里说明了IP通信的优点, 他可以适应通信线路的变化并且可以最大化利用带宽. 本质上是因为IP网络上应用更复杂, 通信空间更难预测和分类. 而电话网络的语音业务一成不变. 所以适合预留固定通信空间.
这里也有一些支持电路交换和分组交换的混合网络的中间型的例子, 比如ATM.
Infiniband与之有一些相似之处, 他在链路层实现端到端的流量控制, 从而减少了网络中的排队, 但仍可能会由于链路拥塞而影响延迟. 然后通过服务质量(QoS, 数据包的优先级和调度)和准入控制(限制发送速率), 最终可以在分组网络上模拟电路交换, 或者说提供统计意义上的有限延迟.
实际上以太网QoS可以实现类似效果, 但通常广域网, 云计算网络并不提供.
延迟的本质时进行资源共享. 虚拟化技术同样不会为客户机分配确定的CPU执行周期, 因此虚拟化的机器性能抖动会更加剧烈.
每台机器都有自己的时钟, 这就带来了本地时间. 常用的时钟同步方法时NTP或者更精准的GPS.
即UNIX时间戳或类似的时间(LINUX上的 clock_gettime(CLOCK_REALTIME)). 这种时间同步后会造成跳跃和存在闰秒问题, 因此不适合测量时间间隔.
单调时钟更适合测量时间间隔. LINUX上的 clock_gettime(CLOCK_MONOTONIC). 单调时钟的绝对值无任何意义, 因此不能跨节点比较.
如果服务器有多路CPU, 则每个CPU都有可能有独立的计时器. 而且不与其他CPU进行同步. 如果进程被调度到不同的CPU上, 操作系统会补偿计时器之间的偏差, 从而为应用层提供统一的单调递增计时器. 但需要谨慎看待这个问题 Time on multi-core, multi-socket servers
通常单调时钟用于测量任务的持续时间, 比如超时.
机器的硬件时钟和NTP也会出现各种各样的问题:
高精度时钟有应用场景, 例如针对金融机构的欧洲法规草案 MiFID II 明确要求所有高频交易基金必须在UTC时间100微秒内同步时钟.
高精度时钟可以曹勇GPS, 精确时间协议(PTP).
这里指出了传统故障可能会使应用趋向于故障, 但时钟失效可能会使应用处于隐式的失效. 导致丢失一部分数据. 并且时钟失效不容易被发现. 因此针对时钟的监控也是必要的.
如果应用使用LWW来决定如何处理并发写入, 则由于时钟同步问题会造成以下问题:
只有时钟源精度远高于被测量对象, 才能避免事件顺序问题.
墙上时钟尽管精度可能很高, 但本身置信程度并不高, 因此应该视作带有置信区间的时间范围.
可以确定时钟源的时钟误差上限. 例如GPS或者原子钟, 通常手册会标明误差上限.
如果是从服务器获取时间, 则误差上限是上次服务器同步以来的时钟漂移范围+NTP服务器不确定性+服务之间的网络耗时(假定第一次同步完全可信).
Google Spanner 中的 TrueTime API 提供了本地时钟的置信区间.
分布式系统需要分布获取单调递增的事务ID(跨所有分区), 事务ID要求必须反映因果关系, 如果大量的小包数据, 则会造成ID分配器瓶颈.
这里举例了Twitter的Snowflake, 但它无法保证因果关系一致的顺序. 比如某些节点分配到的ID使用过快, 则超越了其他节点. 这时其他节点的新数据分配到的ID可能会落后于那个消耗过快的节点.
如果使用墙上时钟, 会面临时钟精度问题.
Google Spanner 基于Turetime API返回的置信区间去比较墙上时钟的置信区间, 来解决跨数据中心的快照隔离问题.
为了却确保事务时间戳反映因果关系, Spanner在提交读取事务之前故意等待置信区间的长度. 这样就能避开置信区间问题. 即让针对时钟精度的采样操作强行大于了时钟精度, 确保不会发生小于时钟精度的采样.
Google 的实践是在每个数据中心都配置了GPS或原子钟, 保证所有时钟同步都在7ms内完成. 除了Google以外, 没有别的主流数据库实现.
这里讲了如果主节点选区采用租约制, 会面时钟不同步, 本地操作超过租约等问题造成不安全的请求处理.
造成线程暂停事件过长的原因有:
再单台机器上编写多线程代码有不少工具可以实现线程安全: 互斥量, 信号量, 原子计数器, 无锁数据结构, 阻塞队列等等. 但这些无法应用到分布式系统.
分布式系统造成的暂停甚至被暂停的节点自己会无感知(没检查时钟).
提供实时保证需要来自软件的多个层面的支持, RTOS, 库函数, 限制动态分配内存, 精确GC, 大量的, 充分的测试和验证.
这里指出了实际上实时系统往往吞吐量较低, 他必须优先考虑并响应高优先级的请求.
目前在一些延迟敏感的系统(如金融交易系统)已经采用了这样的GC方法: 把GC暂停视作节点的一个计划内的临时离线, 当节点启动垃圾回收时, 通知其他节点来接管客户端的请求. 此外系统还可以提前为前端应用发出预警, 应用对等待当前请求完成, 并把接下来的请求调度到其他节点上.
另外的变种是, 支队短期对象GC, 然后定期采取重启策略. 进行滚动重启.
本节主要讲可以对分布式系统做出哪些假设以及系统通常可以提供哪些保证.
节点不能根据自己的信息来判断自身状态(这里举了通信失效, 节点长时间GC的例子), 目前许多分布式算法都依靠法定票数(quorum), 减少对特定节点的依赖.
这里描述了仲裁完毕后已被标记取消权限的主节点继续写入的情况, HBase曾遭遇过该问题: hbase-and-hdfs-understanding-filesystem-usage
想要防止持有过期权限继续写入的问题很简单, 可以引入 fencing token, 程序在写入的时候去识别token, 来防止结果被覆盖.
使用ZooKeeper时可以用事务标识zxid或节点版本cversion来充当fencing token. 这两个都可以满足单调递增的要求.
这里要注意不仅客户端需要自己检查token, 服务端也应该有token的检查机制, 防止客户端问题而造成的错误写入. 比较简单的做法是直接用token给文件命名等.
在不信任的环境中需要达成共识的问题也被称为拜占庭将军问题. 如果某个系统即使发生部分节点故障, 甚至不遵从协议, 或者恶意攻击, 干扰网络, 但仍可继续正常运行, 那么我们称之为拜占庭式容错系统.
这种担忧在某些场景下是合理的:
只有在没有中央决策机制的点对点网络中, 拜占庭容错才更为必要.
软件bug由于其部署形式, 虽然可以被看作拜占庭问题, 但验证环境过于复杂.
由此, 传统的安全措施(认证, 防火墙等) 仍然是防范攻击的主要保护机制.
较弱的防范机制(用于对抗自然因素), 还是有必要的, 例如校验和, 检查用户输入, 多个NTP服务器等.
关于计时方面, 有三种常见的系统模型:
然而我觉得大部分人都不是很明确的区分这几种模型, 通常做法是虽然有超时, 但是却设置个超大的超时, 直到上游或者下游真正的超时才会有所动作甚至无动作导致自己挂掉.
节点失效的模型:
例如对于 fencing token 要求算法有以下特性:
上面的例子中, 唯一性和点掉递增属于安全性, 可用性属于活性.
它们的区别是, 活性的定义中通常会包括暗示"最终"一词. 安全性通常可以理解为"没有发生意外".
区分安全性和活性的一个好处是可以帮助简化处理一些具有挑战性的系统模型.
对于分布式算法, 通常要求在所有可能的系统模型下, 都必须符合安全属性. 而对于活性, 则存在一些必要条件, 假设多数节点正常, 假设网络中断会恢复等等.
这里指出了现实实践和理论模型仍然会有差异, 所以在软件工程实践中, 还要多做一些工作.
节点的中间状态不容忽视, 这里举例了一个由于驱动错误导致网卡只有1kb/s的情况.
这里指出了分布式系统会服务于可扩展性, 容错, 低延迟.
分布式系统最重要的抽象之一就是共识, 所有节点就某一项提议达成一致.
最终一致性: 如果停止更新, 并等待一段时间(长度未知)之后, 最终所有读取请求会返回相同的内容. 最终一致意味着"收敛", 即预期所有的副本最终会收敛到相同的值.
最终一致性意味着写后能立刻读取到是不能保证完成的. 并且这里提醒了如果系统处于中间状态, 则会加剧不确定性.
分布式一致性模型与事务隔离有相似之处, 但总体来讲, 事务隔离主要是为了处理并发执行事务时的各种临界条件, 而分布式一致性则主要是针对延迟和故障来协调副本之间的状态.
可线性化(也称为原子一致性, 强一致性等), 基本的想法式让一个系统看起来好像只有一个数据的副本, 其所有操作都是原子的.
可线性化必须在某一次读取读取到写入值之后, 其他的读取也能读取到新的写入值.
可线性化(Linearizability)与可串行化(Serializability)的区别是:
数据库可以同时支持这两者, 这种组合又被称为严格的可串行化或者强的单副本可串行化(strong one-copy serializability, Strong-1SR), 基于两阶段加锁或实际以串行执行都i是典型的可线性化.
但是可串行化的快照隔离则不是线性化的. 按照设计他可以从一致性快照中读取以避免读,写之间的竞争. 开找不包含快照点创建时刻之后的写入数据, 因此从快照读取肯定不满足线性化.
主节点选举就是可线性化的应用场景之一, ZooKeeper和Etcd都能满足可线性化, 但, 在默认情况下读取可能会读取到旧值, 激活线性化读取 Etcd中称为法定票数读取, ZooKeeper需要读取之前调用sync().
例如唯一性的键, 需要线性化. 外键或属性约束则并不一定要求线性化.
这里指出了如果存在外部逻辑, 则仍要考虑外部逻辑是否正确, 符合线性化.
复制方案中, 有哪些可以满足线性化:
执行quorum的系统, 如果遭到网络延迟, 就有可能造成非线性化. 但如果牺牲性能, 执行读修复, 则仍可以满足线性化. Riak不支持, Cassandra确实会等待读修复完成, 但是他使用LWW, 并发写入一个主键就会失去线性化.
此外, 文中的例子支支持线性化读, 写操作. 但无法支持线性化的"比较和设置", 这需要共识算法支持.
如果是基于多主复制的数据库, 则发生网络分区时, 仍可读写.
如果时基于主从复制的数据可, 则发生分区时, 连接到从数据中心的客户端无法再联系上主节点也就无法完成写入和线性化读取.
这里指出了只要发生网络分区, 甚至网络故障, 就可能存在破坏线性化的情况.
这即CAP描述的情况, 即网络正常时, 可以同时保证一致性(线性化), 和可用性. 一旦发生网络故障, 则要么选择线性, 要么选择可用性.
CAP 应用范围很窄, 她只考虑了一种一致性模型(线性化), 和一种故障(网络分区).
由于CPU本身也有缓存, 因此CPU防卫内存的结果也不是线性化的, 除非使用了内存屏障或者fence指令.
保证线性化后, 读写延迟都要与网络延迟成正比, 线性化的性能势必很差.
之所以反复出现顺序问题, 是因为它有助于保持因果关系.
如果系统服从因果关系所规定的顺序, 我们称之为因果一致性. 例如快照隔离提供了因果一致性.
全序关系支持任何俩个个元素之间进行比较. 即对于任意两个元素, 总是可以指出哪个更大, 哪个更小.
偏序即两个集合之间不是对方的子集, 故无法互相比较.
可线性化数据存在全序操作关系, 可以指出那个操作更优先.
而因果关系可能是并发的, 因此只能叫做偏序关系.
因此根据定义, 可线性化数据存储中不存在并发, 会强制数据排队.
任何的可线性化的系统都将正确地保证因果关系.
但线性化并不是保证因果关系的唯一途径. 因果强一致性认为是, 不会由于网络延迟而显著影响性能, 又能对网络故障提供容错的最强一致性模型.
保证因果一致性通常使用版本向量技术.
可以给定事件时钟, 可以表达因果关系即可. 即, 可以按照与因果关系一致的顺序来创建序列号, 并行操作则可以是任意的序列号.
主从复制数据库中, 主库可以给定序列号, 从库按照复制日志的顺序操作, 结果即可满足因果一致性(虽然会滞后于主节点).
非因果序列可以使用以下方法产生:
Lamport时间戳是一个键值对(计数器, 节点ID), 计数器大的操作时间戳大, 如果计数器相等则节点ID大的判定为大.
Lamport时间戳节点间会互相同步计数器, 而且要求客户端请求带上自己读取到的最大的计数器值. 依据计数器值进行同步. 计数器始终保持最大值.
Lamport可以使因果顺序一致, 但根据其全序关系无法区分两个操作属于并发关系还是因果依赖关系. Lamport时间戳优于版本向量之处在于它更加紧凑和高效.
Lamport时间戳定义了因果顺序一致的全序关系, 但操作互相感知本身是异步的. 因此需要全序关系广播. 比如Lamport时间戳无法完成全局唯一写入这种操作.
分布式系统的一致性挑战在于扩展系统的吞吐量使之突破单一主节点的限制, 一句如何处理主节点失效时的故障切换. 这些问题被称为全序关系广播或原子广播.
全序关系广播通常指节点之间交换消息的某种协议, 需要满足两个基本安全属性:
即使节点或网络出现了故障, 全序关系广播算法的正确实现也必须保证上述两条. 当网络中断, 算法要继续重试, 直到网络修复消息发送成功(而且以正确的顺序发送).
ZooKeeper 和 Etcd 都实现了全序关系广播.
如果每条消息代表数据库写请求, 并且每个副本按照相同的顺序处理这些请求, 那么所有副本可以保持一致(或许有滞后). 该原则也被称为状态机复制.
可以使用全序关系广播实现可串行化事务.
全序关系广播另一个要点是顺序在发送消息时已经确定, 如果消息发送成功, 节点不允许将某条消息插入到先前的某个位置上, 这使得全序关系广播比基于实现戳排序要求更强.
全序关系广播是基于异步模型, 保证消息以固定的顺序可靠地发送, 但是不保证消息何时发送成功(因此某个接收者可能明显落后于其他接收者). 而可线性化则强调就近性: 读取时保证能够看到最新的写入值.
可以通过使用全序关系广播以追加日志的方式, 来实现线性化的原子比较-设置操作, 步骤如下:
如果此时存在并发, 则每个节点都将进行决定哪个请求在先, 选择第一个写请求作为获胜者. 并终止其他请求. 以确保所有节点都同意一个写请求最终要么提交成功, 要么终止. 类似的方法还可以用来在日志之上实现可串行化的多对象事务.
此过程可以确保线性化写入, 但无法保证线性化读取. 这里只提供了顺序一致性, 有时也称为时间线一致性. 它弱于线性化保证.
如果想满足线性化读取, 有以下几个方案:
假设有一个线性化的寄存器来存储一个计数, 然后使其支持原子自增-读取操作, 或者原子比较-设置操作. 来实现全序关系广播:
对于每个要通过全序关系广播的消息, 源自递增并读取该线性化的计数, 然后将其作为序列号附加到消息中. 接下来将消息广播到所有节点, 发生都i是则重新发送. 接收者也严格按照序列化来发送回复消息.
这里与Lamport时间戳的区别是, Lamport时间戳会存在间隙, 全序关系广播不存在间隙, 如果出现了间隙, 则必须等待缺少的数据到达才会继续处理下一个数据.
可以证明, 线性化的原子比较-设置(或自增)寄存器与全序关系广播二者都等价于共识问题.
很多场景都需要集群节点达成某种一致, 例如:
(关于原子提交问题, 原子提交要求所有节点都赞成, 而共识问题则是多数赞成即可. 原子提交与共识可以相互转化, 而非阻塞的源自提交则比共识更难, 参考三阶段提交.)
FLP 结论, FLP表明如果节点存在可能崩溃的风险, 则不存在总是能够达成共识的稳定算法.
FLP结论时基于一部系统模型而做的证明, 这是一个非常受限的模型, 他家顶确定性算法都不能使用任何时钟或超时机制. 如果算法可以使用超时或其他方法来检测崩溃节点(即怀疑可能是误报), 那么可以实现稳定的共识方案.
另外即使算法使用了随机数来检测节点故障也可以绕过FLP结论. 因此FLP结论有其重要的理论意义, 但对于实际的分布式系统通常达成共识是可行的.
原子性可以防止失败的事务破坏系统, 避免形成部分成功夹杂着部分失败. 这对于多对象事务和维护二级索引格外重要.
单节点的事务提交非常依赖数据持久写入磁盘的顺序关系, 先写入数据, 然后再提交记录. 提交或终止的关键点在于磁盘完成日志记录的时刻. 如果完成则安全提交, 否则就近性终止并回滚.
分布式系统操作事务的难点在于, 事务提交不可撤销, 一旦提交就会被其他事务可见, 接入其他客户端会基于此做出相应的决策. 这个原则构成了读-提交隔离的基础. 如果允许事务提交之后还能终止, 会违背之后所有读-提交的事务, 尽而被迫产生级联式的追溯和撤销. 最重要的是, 很可能已经影响到了客户端, 客户端的逻辑很有可能是有状态或副作用的, 撤销变得不可能.
当然已提交事务的效果可以被滞后一笔新的事务来抵消, 即补偿性事务. 不过从数据库的角度看, 前后两个事务完全互相独立. 类似这种跨事务的正确性需要由应用层来负责.
两阶段提交 2PC, 是一种在多节点间实现事务原子提交的算法, 在某些数据库内部使用, 或者以XA事务形式(例如Java Transaction API)或SOAP web服务WS-AtomicTransaction的形式提供给应用程序.
两阶段提交引入了一个新的组件, 协调者(也称为事务管理器), 通常实现为共享库. 运行在请求事务相同进程中, 但也可以是单独的进程或服务. 常见包括Narayana, JTOM, BTM, MSDTC.
当应用程序准备提交事务时, 协调者开始阶段1, 发送一个准备请求到所有节点, 询问是否可以提交. 然后再阶段2根据所有节点的回复选择提交或放弃.
两阶段提交有两关键的不可撤销节点, 答复可以提交的节点必须要保证提交, 协调者做出提交或放弃的决定不可撤销. 这保证了两阶段提交具有原子性.
2PC 存在的问题即协调者的存在, 它让状态收束, 由此将分布式问题转化为单节点上的原子提交问题. 却由此成为了单点. 当协调者故障, 所有节点必须等待协调者恢复. 不可以设置策略为, 如果超时则全部放弃, 这会涉及时钟同步和精度问题.
3PC架顶一个有界的网络延迟和节点在规定时间内响应. 考虑到目前大多数具有无线网络延迟和进程暂停的实际情况, 它无法保证原子性.
有报告显示MySQL的分布式事务比单节点事务要慢10倍以上, 两阶段提交性能下降的主要原因是为了防止崩溃恢复而做的磁盘I/O 以及额外的网络往返开销.
目前有两种截然不同的分布式事务概念:
异构分布式事务旨在无缝集成多种不同的系统, 例如数据库, 消息队列, 其他应用等. 但如果系统中存在非 Exactly-once的部分, 则无法完成事务. 比如有副作用的程序, 不支持事务的邮件发送系统等.
X/Open XA (eXtended Architecture, XA) 是异构环境下实施两阶段提交的一个工业标准. 目前许多传统关系数据库(PG, MySQL, DB2, SQL Server Oracle) 和消息队列(ActiveMQ, HornetQ, MSMQ, IBM MQ) 都支持XA.
XA 并不是网络协议, 而是一个与事务协调者进行通信的C API. 同时也支持其他语言的API绑定.
为什么不可以放弃停止响应的节点, 因为这些节点通常都持有行级独占锁, 防止脏写. 如果要使用可串行化的隔离, 则两阶段锁的数据库还会对事务曾经读取的行持有读-共享锁.
理论上, 如果协调者崩溃后重新启动, 他应该可以从日志中恢复那些停顿的事务. 但在实践中, 孤立的不确定事务确实会发生.
通常可能需要手动回复, 并且和可能处在关键生产环境的中断间隙, 背负着巨大的压力和时间限制.
许多XA的实现都支持某种紧急避险措施称之为启发式决策, 简单来讲就是通过破坏原子性来解决故障. 因此也只应该用于解决故障.
因为事务协调者本身就是一种数据库, 因此需要跟其他重要的数据库一样格外小心:
这样的共识算法必须满足:
最著名的容错是共识算法包括VSR, Paxos, Raft, Zab. 这些算法大部分其实并不是直接使用形式化模型(提议并决定某个值, 同时满足上面4个属性), 相反, 他们是决定了一些劣质, 然后采用全序关系广播算法.
全序关系广播的要点是, 消息按照相同的顺序发送到所有节点, 有且只有一次. 所以, 全序关系广播相当于持续的多伦共识:
VSR, Raft, Zab 都直接采取了全序关系广播, 这笔重复性的一轮公示只解决一个提议更加高效. 而Paxos则有对应的优化版本Multi-Paxos.
主从复制也是一种全序广播, 但由于其主节点唯一, 所以故障中需要人为终止, 因此不满足共识的可终止性.
但即使有主节点选举, 仍然会面临脑裂等问题, 以及全序广播和主节点选举的互相依赖问题. 因此无主节点的系统可以更好地满足共识.
所有共识协议都形成了某种形式的主节点.
共识协议都定义了一个世代编号(Epoch Number), Paxos 是 ballot number, VSP 是 view number, Raft 是 term number. 并保证在每个Epoch里面主节点是唯一确定的.
共识算法为一切不确定的系统带来了明确的安全属性(一致性, 完整性和有效性), 此外它还可以支持容错(只要大多数节点还在工作和服务可达).
共识可以提供全序关系广播, 以容错的方式实现线性化的原子操作.
但代价有:
Zookeeper 的实现其实模仿了Google的Chubby分布式锁服务. 它不单实现了全序广播(因此实现了共识), 还提供了其他很多有趣的特性. 所有这些特性在构建分布式系统时格外重要:
上述特征中, 只有线性化的原子操作才依赖共识. 然而zk有这些功能, 在分布式协调服务中发挥了关键作用.
这里举例了zk可以用于主节点选举, 绑定性的动态负载平衡.
zk适合低频事务, 如果高频, 可以考虑用Apache BookKeeper.
zk, etcd, Consul 还经常用于服务发现. 但关于服务发现是否需要共识还缺乏统一认知.
成员服务用来确定当前哪些节点处于活动状态并属于集群有效成员. 即使由于延迟等原因发生误判, 系统就成员资格问题的决定时全体一致的, 这使得该决议变得有意义.
整合不同系统是大型应用总最为关键的任务之一.
存储与处理数据的系统按照高层次分类可以分为两大类:
这种分类与所使用的数据库无关, 是因使用方式所带来的差异.
按照业务类型, 数据密集型系统分为:
这里用unix工具演示了批处理和流式处理.
演示了用通用语言编写的程序也可以实现类似功能.
这里指出了两者算法上的差别, unix工具利用了排序, 而ruby程序利用了hash表. ruby程序充分利用了内存来提升性能, 而unix工具利用磁盘的不断唤出来节省内存, 但性能没有内存型高.
什么是UNIX哲学:
尽管UNIX工具是不同人编写的, 但他们可以灵活地结合到一起, 那么, UNIX是如何实现这种可组合性的呢?
只有统一接口再能互相通信, 在UNIX中, 接口就是文件.
统一接口的另一个例子是URL和HTTP, 在过去BBS时代, 每个系统都有自己的电话号码和波特率配置, 互相引用甚至都要包括电话号码和调职解调器设置, 用户不得不挂断电话才能拨打其他BBS.
像UNIX工具一样流畅连接多个程序反而是异类, 并不是常态. 你并不能轻松的将自己的购物数据导出并分享到其他地方. 即使是具有相同数据模型的数据库, 从一个数据库中导出数据然后导入到另一个数据库也并非易事. 继承性的缺失导致了数据的巴尔干化(碎片化).
UNIX工具的输入与输出可以进行重定向, 这允许用户对数据得到需要的控制方式. 而程序本身并不关心数据来自哪里和输出到哪里. 这是一种松耦合, 后期绑定或控制反转. 将输入输出的布线连接与程序逻辑分开, 可以更容易将小工具组合成更大的系统.
但 stdin/stdout 也有局限性, 不能输出到网络连接, 如果要打开文件进行读写或另一个程序作为子进程启动, 或打开一个网络连接, 这将减少在shell中输入和输出的灵活性.
UNIX工具成功的原因在于他可以观察事情的进展:
但unix工具只能单机运行, hadoop则是为了多机运行的典型.
这里指出了如果HDFS不采用副本而采用纠删码, 会丧失局部性优势. 因为来自多台机器的数据必须进行合并以重建原始文件.
MapReduce:
MapReduce作业的并行化基于分区实现, 作业输入通常是HDFS中锋的一个目录, 且书大户目录中的每个文件或文件块都被视为一个单独的分区, 可以由一个单独的map任务来处理.
MapReduce调度器会尝试在输入文件副本的某台机器上运行mapper任务, 这个原理被称为将计算靠近数据, 避免网络复制, 减少网络负载提高访问局部性.
框架会分发计算回调所使用的代码(jar包), 然后map任务读入文件进行格式化, mapper的输出是由键值对组成.
Reduce 任务也被分割成块, Map任务数量是由输入决定的, 而Reduce 任务数量是由作业者配置的. 框架使用关键字hash来确定那个reduce任务接受特定的map程序产出的键值对.(这里用了hash就意味着也会发生倾斜问题)
键值对必须进行排序, 如果数据过大, 可能无法再单击上使用常规排序算法, 实际上排序是分段进行的. map会按照关键字hash针对reducer进行分块. 然后数据分区写入本地磁盘的已排序文件中.
当排序和落地完成, 调度器通知reducer开始读取, 按照reducer分区将数据从mapper复制到reducer, 这个过程被称为shuffle.
reduce任务获取数据保持排序并合并. 然后通过关键字和迭代器进行调用逻辑, 最终输出到HDFS.
MapReduce并不是管道, 因此面临复杂业务需要多个MapReduce任务连接起来进行处理, 为了处理作业之间的依赖关系, 已经开发了各种Hadoop工作流调度器, 包括Oozie, Azkaban, Luigi, Airflow, Pinball.
这些调度程序还具有管理功能, 维护大量批处理作业时非常有用. 在构建推荐系统时, 由50-100个MapReduce作业组成的工作流是非常常见的.
Hadoop 的各种高级工具, 例如 Pig, Hive, Casading, Crunch FlumeJava则支持设置多个MapReduce阶段的工作流.
在批处理情况下讨论join, 主要时解决数据集内, 存在关联的所有事件.
这里讲明最佳时间时把外部数据库需要join的数据导入HDFS作为副本处理性能会最佳, 因为hadoop本身设计理念时就近计算的.
mapper进行输出时可以进行按关键字分区, 然会对键值进行排序, 这会让需要join的数据彼此相邻, 甚至可以对需要join的数据进行排序, 这被称为次级排序.
次级排序后, 数据进行reduce会更加方便, 用少量的集合做索引去遍历数据排序好的大量的集合. 这种甚至可以在内存中进行. 这个算法被称为排序-合并join. 因为mapper输出时按照关键字排序的, reducer将来自join两侧的已排序数据合并在一起.
MapReduce模型将计算中的物理网络部分从应用逻辑中分离出来, 所以他避免了在应用代码中处理局部故障(例如节点崩溃). MapReduce会不影响应用程序逻辑的情况下透明的重试.
即Group或count操作, 利用他们可以获得流程性或者统计性的数据.
Pig中的倾斜join方法首先运行一个抽样作业来确定哪些属于热键, 在真正开始join时, mapper将任何与热键有关的记录发送到随机若干个reducer中的一个, 对于join的其他输入, 与热键相关的记录需要被复制到所有处理该关键字的reducer中(用空间换时间了).
Crunch中的共享join与之类似, 不过需要明确指定热键.
也可以采用两阶段MapReduce来减少需要遍历的数据集. 进而提升性能.
reduce端join的好处是, 数据全是必须的, 并且是处理好的. 但缺点时需要复制到reduce端. 这回占用内存和回写磁盘数次.
map端join则指的是直接用一个单独的map作业来整理数据.
广播hash join是指, 把较小部分的数据全量加载到内存称为hash结构去join. Pig的replicated join, hive的mapjoin, Cascading和Crunch等. 也用于仓库查询引擎, 例如Impala.
另一种方法是不读取到内存中, 而是保存在磁盘的只读索引中, 由于频繁读取, 操作系统会自动缓存.
对需要join的数据的索引部分进行hash后分区, 这样就不需要全部载入内存了. 但如果数据数量差距太大, 不是很有作用. 这在hive中被称为 bucketed map join.
即不仅用相同的方式进行分区, 并且基于相同的关键字进行排序. 这样在map过程就可以进行合并了.
reduce端的join输出按关键字进行分区和排序, 而map端join则按照大数据集相同的方式机型分区和排序.
这样在map端join还需要了解map端数据的大小, 排序和分区状况. 这些元数据存储在HCatalog和Hive metastore中.
批处理与分析(OLAP)更为接近, 但不是OLAP.
Google最初使用MapReduce的目的是为其搜索引擎建立索引, 这个索引呗实现为5到10个MapReduce作业的工作流, 后续被替换掉. Hadoop MapReduce仍然是构建Lucene/Solr索引的好方法.
它的原理即Mapper对文档进行分区, Reducer构建分区索引. 但如果需要rebuild则再文档内容变化较少的情况下, 成本会很高.
批处理的常见用途是构建机器学习系统, 如分类器(垃圾邮件过滤器, 异常检测, 图像识别) 和推荐系统(可能认识的人, 可能感兴趣的产品或相关搜索).
这里列举了将Hadoop处理结果直接输出到数据库的不可取之处:
目前更好的解决方案是输出到专用数据库文件, 然后加载到数据库, 例如Voldemort, Terrapin, ElephantDB, HBase.
MapReduce由于输入不可变, 因此可以避免副作用. 其易维护特性如下:
MapReduce并不新鲜, 大规模并行处理(MPP)数据库也实现了类似的操作. 但MapReduce与HDFS的结合使得操作变得具有通用性, 更像一个可以运行任意程序得通用操作系统.
Hadoop更趋向于存储元数据, 而不会具体的针对数据进行特殊的编排或采用数据结构. 而MPP数据库需要针对数据和查询模式进行前期编排.
原始数据具有最大的熵. 仅以原始数据形式收集数据, 之后再考虑模式设计, 从而使收集数据的速度加快, 这种形式也被称为"数据湖"或"企业数据中心".
不加区分存储数据也转移了数据解释得负担, 这将问题的处理者从数据的收集着转移到了数据的使用者. 这种思想的核心在于"可能并不存在一个理想的数据模型", 这被称为寿司原则.
MPP数据库集成程度高, 因此性能优秀. 但并非所有类型的处理都可以合理的表达为SQL查询. 例如如果正在构建机器学习和推荐系统, 或具有相关性排名模型的全文搜索索引, 或执行图像分析, 则很可能需要更具一般性的数据处理模型. 所以不仅需要查询, 还需要编写代码.
Hadoop 平台不仅有Hive这种SQL模型, 还有其他模型的应用. Hadoop生态系统包括可随机访问的OLTP数据库, 如HBase, MPP模式的分析数据库, Impala. Hbase和Impala都不使用MapReduce, 但都使用HDFS进行存储. 尽管他们访问和处理数据的方法差异很大, 但是可以共存并被集成到同一个系统中.
Google拥有混合使用的数据中心, 在线生产服务和离线批处理作业在同一台机器上运行. 这点得到佐证, 360的storm集群是运行在云盘集群(HDFS)上面的. 任务通过容器来实现资源分配. 每个任务具有优先级, 如果优先级较高的任务需要更多资源, 则可以终止(抢占)同一机器上较低优先级的任务以释放资源. 优先级还决定了计算资源的定价: 团队必须为他们使用的资源付费, 而优先级更高的任务花费也会越多.
这种模式可以让资源过度分配以得到最大利用率. 但代价就是MapReduce计算有大约5%被终止的风险. 这个比例比由于硬件问题, 机器重启或其他原因导致的故障率高出一个数量级. 以这样的抢占率, 如果一个作业有100个任务, 每个任务运行10分钟. 那么至少有一个任务在完成之前将被终止的风险大于50%.
这就是MapReduce被设计为容忍意外任务终止的原因. 不是一因为硬件不可靠, 而是这样设计带来的灵活性能够更好地利用集群资源.
而在开源集群调度器中, 抢占的使用情况则相对较少, YARN的CapacityScheduler支持抢占以平衡不同队列的资源分配. 但目前, YARN, Mesos, Kubernetes不支持通过优先级抢占.
MapReduce也有缺点, 比如原生MapReduce API直接使用很复杂, 需要手动实现全部的join算法. 所以有一些上层抽象, 例如 Pig, Hive, Casading, Crunch.
MapReduce执行性能也有问题.
将MapReduce作业中间产生的状态数据写入文件的过程被称为实体化. UNIX系统的例子则是使用缓冲区. MapReduce完全实体化中间状态缺点有:
为了解决这些问题, 新的分布式处理引擎出现了, 例如Spark, Tez, Flink. 他们的设计方式有很多不同之处, 但有一个共同点, 他们把整个工作流作为一个作业来处理, 而不是把他们分解成独立的子作业.
由于通过若干个处理阶段明确地建模数据流, 所以这些系统被称为数据流引擎. 他们如同MapReduce一样, 贩毒调用用户定义的函数来在单个线程上一次护理一条记录. 他们通过对输入进行分区来并行工作, 并将一个功能的输出复制到网络上, 称为另一个功能的输入.
数据流引擎提供了多种不同的选项来连接一个运算符的输出到另一个的输入:
这样的引擎优点有:
而Pig, Hive, Cascading 可以轻松切换到Tez或Spark.
MapReduce由于中间状态持久化可以很方便容错, 而Spark, Flink, Tez则使用其他方法, 如果及其发生故障, 且中甲状态丢失, 则利用其他可用的数据出现重新计算(例如之前的中间状态, 或HDFS上的原始数据).
为了实现重新计算, 框架必须跟踪给定的数据, Spark使用弹性分布式数据集 (RDD, Resilient Distributed Dataset) 抽象来跟踪数据的祖先. 而Flink对运算符状态建立检查点, 从而允许将执行过程中遇到故障的运算符恢复运行.
这里主要面临的问题有运算符不具有确定性所带来的重新计算不一致, 以及计算量非常发达则重新计算不如存储中间状态.
数据流的收束点在上下文依赖的数据(比如排序), 和最终输出. 数据流对MapReduce的改进是不需要将所有中间状态写入文件系统.
批处理环境中查看图也很有趣, 其目标是在整个图上执行某种离线处理或分析, 这种需求经常出现在机器学习应用程序或排名系统中.
最著名的图分析算法之一PageRank, 它试图根据链接至某网页的其他网页来评估该网页的受欢迎程度. 他是确定网络搜索引擎结果呈现顺序的标准之一.
传统的MapReduce并不太适合处理图数据. 实现起来非常低效, 主要是因为MapReduce没有考虑算法的迭代性质.
作为对图数据的批处理优化, 计算的批量同步并行(BSP, bulk synchronous parallel)模型已经流行起来, 典型系统包括Apache Giraph, Spark的Graph X API 和 Flink的Gelly API. 由于最早是Google的Pregel论文将这种处理图的方法普及, 因此它也被称为Pregel模型.
Pregel 的想法与Mapper和Reduce的想法类似, 一个顶点可以"发送消息"到另一个顶点, 通常这些消息沿着图的边被发送.
在每次迭代中, 为每个顶点调用函数, 将所有发送至该顶点的消息传递给它, 定点保存它自己在内存中的状态, 所以函数只需要处理新输入的消息. 如果没收到消息则不需要做任何操作. 并在每一轮迭代中将前一轮的所有消息发送出去.
事实上, 顶点只能通过消息传递进行通信. 这有助于提高Pregel的作业性能. 消息会复制到网络中, 当每一轮结束后, 会定期快照所有顶点的状态. 来完成故障恢复.
顶点是计算单元, 因此顶点之间的通信将会是最大瓶颈. 中间状态往往比原始图大, 最终导致算法变慢.
出于这样的原因, 单机性能可能会更高, 因此选择GraphChi等框架进行单机处理也是一个选择. 而太大的图让然要靠Pregel进行集群处理. 有效并行化图算法是个前沿领域.
这些高级处理框架都提供API, Tez还允许高级语言一致到新的数据流引擎. API 通常使用关系式构建块来表示计算.
与编写执行join的代码相比, 指定join作为关系运算符的优点在于, 框架可以分析join输入的属性, 并自动决定哪个join算法最适合当前的任务. Hive, Spark, Flink利用基于成本的查询优化器来实现这样的功能. 甚至还可以改变join顺序, 使中间状态数量最小化.
但在其他方面MapReduce与SQL有很大的不同, MapReduce基于回调函数思想构建, 其优点在于可以利用现有的库的生态来执行数据分析, 自然语言分析, 图像分析及运行数值或统计算法等.
轻松运行任意代码使MapReduce与MPP数据库的区别.
除了join之外, 声明式的编写方式也有其优点, 例如如果用声明式表示简单的过滤和map操作, 那么查询优化器可以利用面向列的存储格式, 从磁盘仅读取到需要的列, Hive, Spark DataFrames, Impala 也使用向量化执行. Spark生成JVM字节码, Impala使用LLVM为这些内部循环生成本机代码.
在统计和数值算法方面已经出现了可重复使用的实现: Mahout在MapReduce, Spark, Flink上实现了用于机器学习的各种算法. MADlib在关系MPP数据库(Apache HAWQ)中实现了类似的功能.
这里指出了批处理引擎和MPP不断渗透对方的领域, 进而变得更加相似.
分布式批处理框架需要解决的两个主要问题是:
在流处理中, 事件被生产者生成一次, 然后可能由多个消费者处理. 相关的事件通常被组合成主题或流.
为了区分系统, 通常有这两种场景:
许多消息系统直接连接生产者与消费者:
直接传递要求必须在线, 离线即可能丢失数据.
即, 将数据集中在代理软件中. 允许相当的队列长度, 如果长度过长则延迟很明显.
一些消息代理甚至支持两阶段提交协议, 但实际上消息代理与数据库的差异有:
这些消息代理的传统观点体现在JMS和AMQP这样的标准中, 包括RabbitMQ, ActiveMQ, HornetQ, Qpid, TIBCO Enterprise Message Service, IBM MQ, Azure Service Bus, Google Cloud Pub/Sub等.
多个消费者读取同一个Topic时, 有两种消息传递模式:
客户端和网络可能会存在各种问题, 因此如果与客户端的链接关闭或者超时, 而代理没有收到确认, 则认为消息未处理. 如果确认动作在丢失, 则需要原子提交协议.
JMS 和 AMQP 标准要求保留消息顺序, 但负载均衡和重试仍然会导致消息被重新排序.
想要避免可以不适用负载均衡, 但如果消息有上下文依赖, 则就会成为问题.
这里指出了消息代理具有一次性的特征, 无法像批处理一样重试, 也无法像数据库一样存储.
日志是磁盘上一个仅支持追加式修改记录的序列. 我们可以用相同的结构来实现消息代理: 生产者将消息追加到日志的末尾来发送消息, 消费者通过一次读取日志来接收消息, 如果消费者读到日志的末尾, 它就开始等待新消息被追加的通知.
为了提升性能, 可以对日志进行分区, 不同的节点负责不同的分区, 使每个分区称为一个单独的日志, 并且可以独立于其他分区读取和写入. 然后将主题定义为一组分区, 他们都携带相同类型的消息.
在每个分区中, 代理为每个消息分配一个单调递增的序列号或偏移量, 这样的系列号式非常有意义的, 因为分区只能追加, 所有分区内的消息式完全有序的, 不同分区之间则没有顺序保证.
Apache Kafka, Amazon Kinesisi Streams, Twitter DistributedLog 都是这种方式工作的基于日志的消息代理系统.
尽管这些消息代理将所有消息写入磁盘, 但通过在多台机器上进行分区, 能够实现每秒数百万条消息的吞吐量, 并且通过复制消息实现了容错性.
基于日志的消息代理可以将整个分区分配给消费者组中的节点, 而不是将单个消息分配给消费者客户端. 但这样会导致粒度过粗, 进而导致:
因此, 在小溪处理的代价很高, 希望在逐个消息的基础上并行处理, 而消息排序又不那么重要的情况下, JMS/AMQP类型消息代理更可取. 另一方面, 在小溪吞吐量高的情况下, 每个消息处理速度快, 消息顺序又很重要的情况下, 基于日志的方法工作的更好.
消费过程只记录消费者的偏移量, 这样的实现使得吞吐变得高效.
如果持续不断地追加日志, 磁盘空间最终将被耗尽, 为了回收磁盘空间, 日志实际上是被分割成段, 并且不时地将旧段删除或归档保存.
实际上, 日志实现了一个优先大小的缓冲区, 当缓冲区变满时, 就的消息被丢弃, 该缓冲区也被称为循环缓冲区或环形缓冲区. 由于在磁盘上, 因此他可以非常大.
这里指出了, 由于分布式和分区的关系, 系统的消息I/O会很稳定, 而传统消息代理如果持久化, 立刻就会出现瓶颈.
虽然当缓冲区满时, 仍然会丢失数据, 但具有偏移量的特性可以让部署和测试变得极为方便而又具有隔离性.
同样, 还可以操作偏移量从而轻松从想要处理的节点开始操作.
将内容持久化的事实是一个可以被捕获, 存储, 处理的事件.
如果应用使用了多个系统, 除了依赖系统自身的转储, 也可以在应用层实现同步, 比如双重同步, 但这会面临不同步的问题. 即不同的数据存储系系统中的数据版本不同步.
变更数据捕获(CDC, Cange Data Capture), CDC 记录了写入数据库的所有更改, 并且可以复制到其他系统的形式来提取数据. 如果在写入时立即将更改作为一种流来发布, 将会产生不同的结果.
从本质上讲, 变更数据捕获使得一个数据库成为主节点, 并将其他变成从节点.
设置数据库触发器虽然准确, 但开销较大. 解析数据库复制日志是一种更健壮的方法, 但他也带来了挑战, 比如处理模式更改(update).
基于解析复制日志的 LinkedIn Databus, Facebook Wormhole, Yahoo Sherpa 已在大规模环境下得到部署. Bottled Water 使用解码预写日志的API来实习那PG的CDC. Maxwell 和 Debezium 通过解析 binlog 在MySQL上实现CDC. Mongoriver 读取 MongoDB 的 oplog. Oracle GoldenGate 也提供类似的功能.
CDC 是异步的, 所以不会面临阻塞问题, 但会面临复制滞后的全部问题.
build全量数据并不需要数据库的全量修改历史数据, 而需要全量快照即可.
CDC系统也可以使用日志压缩, 因此无论何时重建派生数据系统, 都可以从日志压缩主题的偏移量0的位置启动一个新的消费者, 然后一次扫描日志中的所有消息. 日志确保包含数据库中每个key的最新值. 从而获取数据库内容的完整副本, 而无需针对性的生成快照.
Kafka 支持类似的日志压缩功能.
现在也有很多数据库提供了开放API供CDC使用, 比如 RethinkDB 支持订阅查询结果发生变化的通知. Firebase 和 CouchDB 的数据同步基于change feed并同时提供给应用层. Meteor 使用 Mongodb oplog.
VoltDB 支持事务流连续导出.
Kafka Connect 致力于将广泛的数据库系统变更数据采集工具与kafka集成.
事件溯源是指让应用层顶层事件成为一个不可变的原子消息, 然后针对这个消息去分发逻辑和演化.
这里指出了从系统建模层次, 事件溯源很有用, 但在用户角度, 用户只希望看到之间发生后的状态, 而不是发生的历史.
重放事件日志即可重建系统的当前状态. 如果使用了日志压缩:
事件溯源的哲学是小心的区分事件和命令. 适当的划分事件的粒度有助于更方便地构建系统.
事务日志记录了对数据库所做的所有更改, 告诉追加是更改日志的唯一方法. 从这个角度来看, 数据库的内容保存了日志中最新记录值得缓存. 日志是事实. 数据库是日志子集得缓存. 该缓存子集恰好是来自日志得每个记录和索引值得最新值.
不可变事件可以记录所有过程, 而数据库的最终值会丢失过程数据.
接入事件流可以构成不同的视图, 并且可以在这些视图实现中获得更多的灵活性. 将数据写入形式与读取形式分开, 并允许多个不同的读取视图, 可以获得很大的灵活性. 这个想法有时被称为命令查询责任分离(CQRS, Command Query Responsibility Segregation).
目前可以接入kafka的系统有, Druid 可以直接获取 kafka 中的事件, Pistachio 是一个分布式键值存储, 使用 kafka 作为提交日志, kafka Connect sinks 可以将 kafka 中的数据导出到其他系统.
这里指出了事件日志通常是异步的, 如果作为用户视图可能会有读取不到的情况.
事件的粒度也会影响并发控制, 因为事件很可能是一系列确定事件的集合. 因此有助于将状态同步到一起. 方便原子化.
不变性的数据并不是完美的, 需要根据数据的操作类型进行评估, 只是写的数据很适合这种场景, 而更新和删除频繁的数据则会导致负载很高. 并且由于有全量数据的存在, 还要注意删除数据后的数据泄露问题.
流与批量作业的一个关键区别是, 流不会结束, 这种差别会导致不能使用排序合并join, 容错机制也需要改变, 因为不可重放.
复杂事件处理 (CEP, Complex Event Processing) 是为分析事件流而发展的一种方法, 尤其适用需要搜索特定的事件模式.
CEP 的特征正好与数据库相反, 其查询是永久的, 而数据是暂时的. CEP 的实现包括 Esper, IBM Sphere Streams, Apama, TIBCO StreamBase, SQL stream, Samza.
流分析则更多是统计上的应用.
流分析系统优势使用概率算法, 比如用于设置成员关系的BloomFilter, 用于基数估计的HyperLogLog, 以及各种百分比估值计算法, 概率算法只能产生近似的结果, 但其优点是在流处理器中所需要的内存明显少于精确算法. 流处理本身并没有任何固有的近似处理, 概率算法仅仅是一种优化.
许多开源框架都支持分析, Apache Storm, Spark Streaming, Flink Concord, Samza, Kafka Streams, 以及SASS例如, Google Cloud Dataflow, Azure Stream Analytics.
Samza 和 Kafka Streams 支持维护物化视图.
Elasticsearch 的过滤器功能是实现流式搜索的一种方式.
这里列举了消息传递和 RPC 的异同.
这里指出了如果需要监测一段时间的数据, 加入队列过长, 则计算出来的结果将是严重滞后的.
这里指出了队列顺序并不一定代表时钟顺序. 以及消费速度发生变化的情况, 比如消费端离线后又恢复, 则会由于消费累计数据而产生结果波动.
测量窗口由于数据进入队列的不确定性故很难定义, 而如果显示插入frame来声明窗口终止, 则又会面临多节点的情况下怎样产生frame的问题.
这里指出了在极端情况下, 数据甚至可能会出现隔好几天甚至更久才会提交带服务器的情况.
较好的实践是同时记录这几种时间:
通过服务器接收时间减去客户端发送时间, 就会获得客户端的真实时钟偏移, 然后应用时钟偏移到第一个时间就是事件的真实发生时间.
常见的窗口类型有:
分为三种不同类型的join: 流和流join, 流和表join, 表和表join.
这种场景举例来讲就是在一定窗口周期中, 多组需要关联的消息进行join的情况, 为此窗口周期内的数据需要被缓存以保证能提供join.
与批处理相同, 流处理也会本地缓存表, 但由于流处理是一直运行的, 所以可能需要对表中发生的数据变动进行数据捕获.
这非常像流和流join, 但区别是这种情况可以进行回溯, 即join指定时间的表.
即两个流都需要维护其全量的数据用于确定交换数据的存储位置.
当多个流互相join时, 就无法保证多个流之间的因果顺序性, 进而导致join的结果也变得不确定. 解决方案是配置唯一id, 但这会导致日志无法压缩.
这里指出了流几乎不可重放和停止.
一种方法是分成多个小块, 并像小型批处理一样处理每个块, 这被称为微批处理. 已经用于SparkStreaming. 通常批处理大小为1s. 较小会影响性能, 较大会有较高延迟. 如果作业大小大于窗口大小, 会导致作业分割.
Apache Flink则使用该方法的一个变体, 他定期生成状态滚动检查点. 并将其写入持久化存储. 恢复即从最近的检查点重启. 检查点由消息流中的barrier触发, 类似微批处理的边界,但并不强制特定的窗口大小.
但如果流系统的数据需要join其他系统的数据, 则要注意副作用.
这里指出了流系统为了保持其他联动系统的一致性也需要类似事务的操作, 但与XA不同的是, 流系统通常在内部完成, 并将状态作为值传递给外部系统. 事务协议的开销通过在单个事务中处理多个输入消息来分摊.
利用 kafka 处理消息时也可以变相实现幂等性, 即在存储节点存储数据的同时也存储来自kafka的偏移量. Storm 的 Trident 的状态处理也是基于类似的想法.
而隐患有: 依赖幂等性意味着需要假设重新处理信息是顺序相同的. 处理是确定性的, 并且没有其他节点并发更新同一值. 另外故障迁移也需要fencing措施.
故障重建状态可以保存在远程, 代价是慢, 另一种时保存在本地, 并定期进行复制.
Flink 定期对操作状态执行快照, 并写入HDFS等持久存储中. Samza 和 Kafka Streams 通过状态更改发送到具有日志压缩功能的专用kafka主题来保存状态的副本. VoltDB 通过多节点冗余处理消息来复制状态.
通常一种实现很难同时兼具鲁棒与性能, 如果试图兼顾所有方面, 那唯一可以肯定的是最终的实现一定很糟糕.
在复杂的用用程序中, 不可避免产生软件的组合使用的场景.
这里进一步说明了需要组合.
同步各个副本或组合实例, 用流是理想的选择之一.
基于日志的派生数据是集成不同数据系统的最有前途的方法.
构建一个完全有序的事件日志需要面临:
从形式上讲, 决定时间的全序关系称为全序关系广播, 它等价于共识. 大多数共识算法是针对单节点吞吐量足以处理整个事件流而设计的, 并且这些算法不提供支持多借点共享事件排序的机制.
现有仍然要使用全序关系广播来实现有因果关系事件的排序.
数据整合的目标是确保数据在所有正确的地方以正确的形式结束.
Spark 通过将流分解为微批处理来在批处理引擎之上执行流处理. Flink 则直接在流处理上执行批处理.
重复了派生系统异步是健壮和可伸缩性的基础.
派生数据还可以服务于结构演变.
Lambda 架构建议同时使用批处理与流式系统来最大化每个系统的产出. 当然, 会付出相应的代价.
批处理和流处理可以在同一个系统中实现.
从数据复制的角度, 创建索引与加入新的从节点的数据模式是一致的.
假设没有一个统一的数据模型或存储格式适用于所有的访问模式, 那么最终会:
基于日志的多系统集成要优于同步写.
当没有一种单一的软件能满足所有需求时, 分离和组合的优势才会显现出来.
分析了一些现有实现的不完美之处.
系统之间传递数据多半需要进行一定程度的转换.
目前的趋势是将无状态应用程序裸机与状态管理(数据库)分开: 不把应用程序逻辑放在数据库中, 也不把持久状态放在应用程序中.
维护派生数据的较好做法是利用流系统
讲了同步请求与异步流的区别, 但这里没说如果数据流发生延迟会造成什么影响.
实时写入数据更像尽早求值, 异步读取数据更像惰性求值.
举例了预先计算请求缓存可能不太现实, 进而转向缓存热点可实施性更高.
指出了客户端状态有存在的意义和可能
利用websocket以及基于日志的思路同步客户端.
这里说明了响应式架构与现有数据库的请求模式的差异.
这里讲了换一个角度来看, 读写都是流的话, 那么读写都是针对流上的join操作, 而订阅是对流的持续join操作. 将读取数据纳入流系统也是有实际意义的.
将查询也纳入流也可以方便多分区数据处理.
Exactly-Once 想要保证不出错需要满足幂等性, 而验证幂等性可能就需要维护一些额外的元素, 比如fencing token.
这里指出了通信链路与服务端, 客户端造成的割裂, 进而演化成了不可确定性.
这里演示了引入操作标识符可以解决幂等问题. 即在事务中引入操作标识符.
端到端论点: 只有具备应用程序充分的知识, 并且站在通信系统端点的角度的情况下, 才能完全正确地实现所关注的功能. 因此, 以通信系统本身的特征来提供这种被质疑的功能是不可能的(有时, 由通信系统提供的不完整版本则可能有助于提高性能).
解决端到端问题需要端到端的方案: 从终端云过户客户端一直传递到数据库的唯一标识符.
即, 这是必要的.
这里指出了唯一性约束也可以应用于其他类型的约束例如逻辑限制等.
想要达成唯一性共识, 要么单主节点, 要么分区hash, 异步多主无法实现, 因为这个操作本身需要同步.
日志可以保证顺序, 因此基于日志的分区处理也可以保证唯一性.
这里讲了将事务的中间状态延长, 避免多分区原子提交. 这会面临时效性问题, 接下来就说了时效性问题.
一致性这个属于同时包含了两个需求:
违反时效性会导致变成"最终一致性", 违反完整性则会"永久性不一致"
可靠的流处理系统可以在不需要分布式事务和原子提交协议的情况下保持完整性, 这意味着它可以实现等价的正确性, 同时具有更好的性能和操作鲁棒性:
也有些其他方法来实现较弱的唯一性:
这样的系统还可以提供区域间复制.
同步协调需要根据业务的需求调整, 如果能减少到很小, 则对整个系统的性能都有好处.
传统上, 系统模型采用二元方法处理故障, 假定有些事情可能发生, 而其他事情是不会发生的.
有bug就有任何可能.
可以通过审计来确定数据的完整性.
HDFS和Amazon S3 等大型存储不完全信任磁盘, 他们后台运行进程, 不断读取文件, 将其与其他副本比较, 并将文件从一个磁盘移动到零一个磁盘, 以减轻无提示数据损坏的风险.
审计系统去不断检查未知的损坏是必要的.
基于事件的系统可以提供更好的可审计性. 如果做到了各种幂等性, 就可以通过重新计算来实现审计, 甚至运行以恶冗余的系统.
端到端的检查会更好地检查系统.
写了一些审计系统的使用.