大多数系统重要的三要素:

  • 可靠性
    • 硬件故障,随机的
    • 软件故障,通过是系统缺陷,难以发现处理
    • 人为的
  • 可扩展性
    • 有效保持系统性能的相关技术策略
    • 增加处理能力的同时,还可以在高负载情况下持续保持系统的高可靠性
  • 可维护性
  • 让工程和运营团队更轻松
  • 好的抽象可以降低复杂性,使系统易于修改和适配
  • 对系统健康状态有好的可观察性和有效的管理方法
  • 其他
    • 功能性需求
    • 非功能性需求

数据系统基础

三种存储模型:

  • 层次结构、文档结构
  • 关系结构
  • 图结构

结构的定义:

  • 读时定义,文档结构
  • 写时定义,关系结构

数据模型和查询语言

关系模型与文档模型

  • 最早的是网状数据,关系模型数据库
  • NoSQL,放弃了关系模型,用来解决特定问题,文档模型、图模型
  • 对象-关系不匹配,阻抗失皆
    • ActiveRcord和Hibernate
    • 可以减少转换所需的代码量,但不能完全隐藏两个系统的差异
  • 存储的演进
    • 1999之前的SQL标准,建议规范化存储,并用外键引用
    • Oracle、DB2、MS-SQL、PG开始支持JSON和XML格式
    • 将工作、教育信息编码为JSON、XML单独存放到数据库中
  • 文档模型非常适合List<String>这种结构
  • 实现系统
    • MongoDB
    • RethinkDB
    • CouchDB
    • Espresso
  • 70年代IBM信息管理系统使用的是层次模型,类似现在的JSON格式
  • 层次结构适合一对多模型,但是多对多不合适,也没法join
  • 为改变层次模型,出现了关系模式、网络模型
  • 网络模型由 为数据系统语言会议做标准版,简称:CODASYL
  • 网络模型和层次模型需要手动指定遍历的路径
  • 关系模型属于声明式的,但底层会有非常巨大的像怪兽版的优化系统
  • 文档模式是读模式(动态),关系模式是写模式(静态)
  • 现在关系型数据库也有支持JSON格式类型,而层次模型也向关系模型靠拢

据查询语言

  • 声明式查询,SQL语言、WEB页面中的html和css分离
  • 命令式,用API模拟SQL查询,WEB页面中用javascript编写查询固定内容
  • MapReduce介于声明式和命令式 之间

图状数据模

  • 属性图模型
    • Neo4j
    • Titan
    • InfiniteGraph
  • 三元存储模型
    • 表达方式为:主体,谓语,客体
    • 主体相当于图中的顶点
    • 语义网 资惊描述框架(Resource Description Framework RDF)
    • 让不同网站以一致的格式发布数据
    • Datomic,采用Datalog查询
    • AllegroGraph
  • 声明式图查询语言
    • Cypher
      • 最早为Neo4j而创建
      • SQL也可以完成类似的查询,但非常笨拙,Cypher需要4行,SQL要29行
    • SPARQL
      • 采用RDF数据模型的三元存储查询语言,比Cypher更早
    • Datalog
      • 比其他两个更古老
      • Hadoop大数据集的实现:Cascalog
      • Prolog的子集
  • 命令式图查询语言
    • Gremlin

采用Cypher查询从美国移民到欧洲的人员名单

MATCH 
  (person) -[:BORN_IN]-> () -[:WITHIN*O .. ]-> (us:Location {name:’United States'}), 
  (person) -[:LIVES_IN]-> () -[:WITHIN*O .. ]-> (eu:Location {name:’Europe'}) 
RETURN person.name 

其他数据模型

  • 基因组数据库软件(两个超长字符串匹配),GenBank
  • 大型强子对撞机(LHC)做超大规模数据分析,要定制一些方案避免硬件成本
  • 全文搜索

存储引擎

Hash索引

  • Riak,其底层存储引擎 Bitcask,使用了hash结构
  • hash表完全放在内存中
  • value指向具体文件中的偏移量
  • 删除是墓碑操作,后台自动做文件压缩(将重复key合并)
  • 有多个文件,可以自动合并
  • 需要有WAL,保证系统崩溃恢复
  • 并发控制,由于是追加的,相对好控制
  • hash表必须完全放在内存中,在磁盘上就不太好使了
  • 另外范围扫描不好实现

SSTables和LSM-Tree

  • 内存中用红黑树/AVL树保证平衡
  • 追加写入,当内存的文件达到阈值时dump到磁盘
  • 后台会有将多个文件做合并
  • 增加布隆过滤器,加速查找
  • 根据Log-StructuredMerge-Tree 论文而来
  • 主流引擎
    • LevelDB
    • RocksDB
    • Riak(BitCask)
    • Cassandra(受谷歌BigTable启发)
    • HBase(同上)
    • Lucene
  • 采用分层压缩(LevelDB)、大小分级(HBase)做优化
  • 反复合并导致写放大,多个文件合并压缩时会占用读/写的磁盘带宽

B树

  • 多级叶子平衡树
  • 分支因子500的4K页4级树可存储256TB
  • 必须有WAL保证可靠性
  • 采用写时复制方式优化(LMDB)
  • 只保存键不存值(B+树)
  • 尝试对叶子节点布局,可以更好的实现范围查询
  • 添加额外指针,方便找到父节点、兄弟节点
  • B树的变体:分形树

其他索引

  • 主键索引、二级索引
  • 在索引中存储值
  • 多列索引
  • 空间索引:R树
  • 全文索引
  • 检查拼写错误:编辑距离
  • 其他模糊搜索:沿着文档分类、机器学习方向发展

OLTP和OLAP

内存数据库

  • Mmecache
  • Redis、Couchbase(异步写,较弱持久性)
  • RAMCloud,开源的,基于WAL
  • VoltDB
  • MemSQL
  • Oracle TimesTen
  • 如果内存足够大,操作系统的缓存中就可以将数据存下
  • 内存的优势可以实现更复杂的操作:Redis
  • 避免内存->磁盘 的编码/解码开销
  • 非易失性存储(no-volatile memory NVM)

数据仓库

  • 星型模型
  • 雪花模型
  • OLAP查询,下钻、切片、切丁
  • 同时支持OLAP和OLTP的数据库:SAP HANA和微软的Sql-Server

相关产品

  • 商业的:Teradata、Vertica、SAP HANA
  • AWS的RedShift是ParAccel的托管版本
  • Dremel系的
    • Hive
    • Spark
    • Impala
    • Presto
    • Tajo
    • Drill

列存储

  • 位图方式的压缩
  • 游程编码
  • SIMD
  • 多列排序,第一列效果最后,后面就慢慢变差了
  • 面向列存储、压缩、排序可以加速读、但写入变慢
  • 通过LSM-tree优化写入,Vertica使用了这种方式
  • C-Store将多个排序后的结果冗余的保存,加速读取

数据编码格式

数据编码格式

  • 特定语言的
    • Java的序列化
    • ruby的Marshal
    • python的pickle
    • Java的Kryo
    • 性能、安全、语言绑定等问题
  • JSON
  • XML
  • CSV(比上面两个要弱一些)
  • 二进制编码

Thrift和Portocol Buffers

  • 跨语言,基于 IDL
  • Thrift有三种编码格式(其中一个只能用于C++),BinaryProtocol、CompactProtocol
  • tag对应IDL中的name,如果不存在则不解析,这样就可以实现兼容了
  • tag后面跟着type,表示string还是int等类型,再后面是长度
  • 类似于80年代的ASN.1
  • 向后兼容(新代码可以读取旧数据)
  • 向前兼容(旧代码可以读取新数据)

Avro

  • 一种基于Avro IDL,用于人工编辑
  • 一种用于JSON,更容易被机器读取
  • 数据和模式是在一起的
  • 没有标签,压缩后数据更小
  • 建立RPC时,可以双方确认一个指定的模式,这样可以做到向前/向后兼容
  • 如果没有指定模式,就使用文件中的模式(模式schema已经内嵌到序列化后的文件中了)

数据流模式

数据流模式

  • 通过数据库
    • 旧版代码读取数据的时候,要小心格式丢失问题
  • 通过服务调用
    • REST,偏向微服务
    • OpenAPI、Swagger
    • SOA,SOAP协议基于HTTP但更重
    • RPC:EJB的RMI、DCOM限于微软、CORBA过于复制
    • RPC不可能做到跟本地函数调用一样,底层会有各种网络问题
    • Thrift和Avro都带有RPC、gRPC使用了Protocol Buffers
    • Finagle使用了Thrift、Rest.li使用了HTTP上的JSON
    • HTTP有庞大的生态,服务器、缓存、LB、proxy、防火墙、监控、调试工具、测试工具
    • REST适用于对外公开API,RPC性能好适应于内部
  • 通过异步消息传递
    • TIBCO、WebSphere、WebMethods
    • RabbitMQ、ActiveMQ、HornetQ、NATS、kafka
    • 分布式Actor框架,本质是Actor框架+消息队列的组合
    • Akka、Orleans、Erlang的OTP

分布式数据系统

数据复制

主要目的

  • 高可用
  • 连接断开与容错
  • 低延迟(较近读取)
  • 可扩展性

主从复制

  • 支持的系统
    • PostGreSQL9+
    • MySQL
    • Oracle Data Guard
    • SQL Server的AlwaysOn Availability Groups
    • MongoDB
    • RethinkDB
    • Espresso
    • Kafka
    • RabbitMQ
  • 同步复制、异步复制、半同步复制(一个同步从+一个异步从)
  • 快照工具 MySQL的innobackupex
  • 主节点失效:节点切换
    • 如何选主、脑裂、如何确认主节点失效、如何设置超时时间
  • 复制日志
    • 基于语句的复制(如果主节点有now()、rand()、副作用的存储过程等会导致不一致)
    • MySQL的statement和row模式
    • WAL的传输,PostgreSQL和Oracle使用
      • WAL日志包含了哪些磁盘块的哪些字节变化,非常底层
    • 逻辑日志复制,MySQL的binlog
    • 基于触发器的复制
      • Oracle的Databus
      • PostgreSQL的Bucardo
      • 通过触发器将数据变更记录到一张表中,然后外部程序处理此表
  • 链式复制,同步复制的一种变体,用于微软的Azure存储

复制延迟

  • 最终一致性
  • 读自己的写:保证用户总能看到自己所提交的最新数据
    • 原因:主库更新后,读从库还是旧数据
    • 需要读主库,保证写后能读到最新数据
    • 通过更新时间戳附带在请求中,来决定由哪个副本处理,但会有时钟问题
    • 同一个账号,A设备更新后、B设备读,得让他们都路由到主库
  • 单调读:用户在某个时间点读到数据之后,保证伺候不会出现比该时间点更早的数据
    • 原因:主库更新后,写读从A(最新的),再读从B(旧数据)
    • 用户hash方式保证每个用户从相同的副本读取
  • 前缀读:保证数据之间的因果关系
    • 原因:先有因(比赛如何了),再有果(1:0),而出现的是先看 果,然后是因
    • 将具有因果事件的关系 都给交固定的分片处理(导致效率不高)
    • 显示的追踪事件的因果关系

多主复制

  • 适用于多数据中心场景,处理节点尽可能靠近用户
  • 可以容忍数据中心失效,仍然网络问题
  • 离线客户端操作,手机、电脑、ipad之间相同同步
  • 协作编辑
  • 相关数据库
    • MySQL的Tungsten Replicator
    • PostgreSQL的BDR
    • Oracle的GoldenGate
  • 处理写冲突
    • 同步检查(有点还原为主从模式了)
    • 异步检测(两个数据中心都写入成功了,再解决就很难了)
    • 避免冲突,对于特定的记录只能通过一个主操作(类似主从模式)
    • 收敛于一致状态
      • 分配时间戳ID、副本唯一ID、足够长的随机数等,实现最后写入获胜
      • 将两个值合并在一起
      • 预定义好耗时和保留冲突,交给应用层处理
    • 写入时执行检查,发现冲突交给应用层处理冲突,如Bucardo
    • 读取时执行检查,发现冲突交给应用层处理冲突,如CoudhDB
  • 自动冲突解决
    • 无冲突的复制数据类型(Confilict-free Replicated Datatypes CRDT)
    • 可合并的持久数据结构(Mergeable persistent data),类似Git版本控制
    • 三向合并功能(three-way merge function),CRDT采用双向合并
    • 操作转换Etherpad和谷歌Dods等写作编辑应用背后的冲突解决算法
  • 拓扑结构
    • 环形拓扑、星形拓扑、树形拓扑、全部-至-全部拓扑
    • MySQL只支持环形拓扑,接着前者,发送给后者
    • 环形、星形拓扑可能因为某一节点发生故障,影响其他节点同步
  • 多主复制可能会出现 前缀一致性(因果关系错乱)这种问题
    • 需要由版本向量来解决

无主复制

  • 节点失效的情况
    • 支持的系统
      • 早期的数据复制就是基于无主节点的
      • 亚马逊内部的Dynamo
      • Riak
      • Cassandra
      • Voldemort
    • 读修复,WRN
      • w写 + r读 > n节点个数
      • n=3,w=2,r=2,一定可以读到最新数据
      • 读取和写入节点中有一个重叠是关键
  • 无主节点的延迟数据副本延迟监控是一个挑战
    • 主从延迟很容易监控
    • 根据n、w、r来预测读取到的旧值期望百分比,但目前还不是很普及
  • sloppy quorum情况下,即使w+r>n也可能出现过期值
    • 某个节点不能写时,临时写入一个节点,这属于n之外的临时写入
    • 只要有w个节点可以,就可以接受新写入
  • Cassandra和Voldemort默认支持跨数据中心复制
  • 并发检测
    • 最后写入者获胜(丢弃并发写入),last write wins LWW,依靠时间戳
    • Cassandra推荐每个写操作唯一主键UUID,这样就没有冲突
    • happends-before关系:A依赖B,B依赖A,A和B为并发(冲突)
    • A和B同时写入,带上版本号,可以将key的多个版本合并
    • 可以覆盖掉低版本的值,但是高版本的相当于是并发(冲突)
    • 如果有多个服务器,则要使用:版本矢量(和矢量时钟有细微差别)

数据分区

键-值的数据分区

键值对

  • 将记录随机分配给所有节点,避免热点问题,但范围读不行
  • 基于关键字区间分区
    • 不一定非要均匀分布
    • 分区边界可以由管理员手动确定
    • 实现系统
      • Bigtable
      • HBase
      • RethinkDB
      • MongoDB2.4之前的版本
    • 每个分区内可以按照关键字排序保存
    • 热点问题,在key前面拼接其他信息,做人为的hash处理
  • 于关键字晗希值分区
    • 哈希函数不需要在加密方面很强
    • Cassandra和MongoDB使用MD5
    • Voldemort使用Fowler-Noll-Vo函数
    • 避免了热点问题,但丧失了区间查询特性
    • MongoDB将查询发给所有分区
    • Riak、Couchbase、Voldemort不支持区间查询
    • 仍然无法避免超级热点问题,在key的前后增加1-3位的随机数
    • 读时要从100个关键字中读取再合并
  • 一致性hash

分区和二级索引

基于文档的分区和二级索引

  • 文档按照key的range做分区
  • 一级索引可以根据关键字查找到指定分区
  • 二级分区,比如查找 汽车颜色,汽车厂商,需要跨多个分区
  • 将查询发往所有分区,然后做合并,也就是分散/聚集
  • 采用的系统
    • MongoDB
    • Riak
    • Cassandra
    • Elasticsearch
    • SolrCloud
    • VoltDB
  • 这种索引,会造成 写放大

基于词条的二级索引

  • 相当于设置了全局索引
  • 二级索引本身也是可以分区的
  • 按照 汽车颜色从a-z做分区,a-r放到0分区,s-z放入1分区
  • 查询颜色只要指定一个分区即可,查询很高效
  • 写入时,会牵扯到多个二级索引,造成 写放大
  • 可能会有分布式事务,所以一般都是异步更新的

分区再平衡

平衡策略

  • hash取模方式不合适
  • 固定数量的分区
    • 10个节点的集群,一开始就创建1K个分区
    • 当节点增加时,自动从每个节点拿走一些分区
    • 实现简单,但分区总量不好预估
    • 实现的系统
      • Riak
      • Elasticsearch
      • Couchbase
      • Voldemort
  • 动态分区
    • 自动分裂、合并
    • 初时只有一个分区,为解决热点问题,可以设置初始分区数量如100个
    • 实现系统
      • HBase
      • RethinkDB
  • 按节点比例分区
    • 每个节点有固定数量的分区,分区大小和和数据集保持正比的增长关系
    • 当节点增加时,分区则会调整变的更小
    • Cassandra增加节点时,将现有节点分区分裂,拿走一半分区
    • 实现系统
      • Cassandra
      • Ketama

平衡操作方式

  • 手动、自动
  • 介于手动和自动之间
    • 生成一个分区分配的建议方案,但需要管理员确认才能生效
    • 实现的系统
      • Couchbase
      • Riak
      • Voldemort

请求路由

三种方式

  • 允许客户端连接任意节点,轮询查询分区,找到就处理,否则继续找下一个
  • 由一个proxy来处理所有请求,后者转发到对应的分区
  • 客户端感知分区和节点的匹配关系

难点

  • 这是一个共识问题
  • 所有参与者都要对元数据信息达成一致
  • 实现
    • LinkedIn的Espresso使用Helix(自层是ZK)管理集群
    • HBase、SolrCloud、Kafka也使用ZK
    • MongoDB依赖自己的mongos充当路由层
    • Cassandra和Riak使用gossip来同步集群状态变化
    • Couchbase不支持自动再平衡,通过moxi的路由层,向集群节点学习最新路由变化
  • 数据仓库的并行查询MPP

事务

在一个苛刻的数据存储环境中,会有许多可能出错的情况:

  • 数据库软件或硬件可能会随时失效(包括正在执行写操作的过程中)
  • 应用程序可能随时崩愤(包括一系列操作执行到中间某一步)
  • 应用与数据库节点之间的链接可能随时会中断,数据库节点之间也存在同样问题
  • 多个客户端可能同时写入数据库,导致数据覆盖
  • 客户端可能读到一些无意义的、部分更新的数据
  • 客户端之间由于边界条件竞争所引入的各种奇怪问题

事务是简化上述问题的首选,目的是简化应用层的编程模型
应用层可以不用考虑某些内部潜在的错误以及复杂的并发性问题,这些都交给数据库负责
ACID:

  • 原子性Atomicity:出错时终止事务,并将部分完成的写入全部丢弃
  • 一致性Consistency:数据有特定的预期状态,任何数据更改必须满足这些状态约束(恒等条件),主要靠应用层维护
  • 隔离性Isolation:并发执行多个事务相互隔离,不能交叉运行,类似于数据库上运行的唯一事务
    • 其他事务看不到其中间结果
  • 持久性Durability:提供一个安全可控的地方来存储数据

单对象和多对象

  • 单条数据更新也可能出现新旧混合的情况
  • 多对象:图数据库,文档数据中多对象更新,二级索引更新

错误和终止

  • 事务已经执行成功,但客户端没有收到ACK,导致重复执行
  • 由于系统负载很高,重试事务会变得更糟糕
  • 临时性故障可以重试,但永久性错误(违反约束)则重试无意义
  • 在数据库之外,事务被中止但如果发送了邮件,仍然有副作用
  • 客户端在重试过程中失败,没有继续重试,则写入的数据可能因此丢失

弱隔离级别

读-提交

  • 避免 脏读
    • 一个事务可以看到其他事务的未提交的中间数据
  • 避免 脏写
    • 第二个写事务覆盖了第一个写事务未提交的数据
    • 第二个写事务回滚将第一个事务未提交的数据覆盖
  • 通过行锁,必须其他事务的读、写同一行数据
    • 一个写事务会导致大量读事务等待,性能大幅度下降
    • 用版本的方式隔离,写时,读不影响
  • 实现系统
    • Oracle 11g
    • SQL Server 2012
    • MemSQL
    • PostgreSQL

可重复读(快照级别隔离)

  • 读-提交 没法解决 可重复读/读倾斜(read skew)问题
  • 一个事务A在t1时刻读取了数据,另一个事务更新了此数据并提交,事务A再读就不对了
  • 实现系统
    • PostgreSQL
    • MySQL的InnoDB引擎
    • Oracle
    • SQL Server
  • 通过锁来防止脏写,对不会阻止读,即可以一写N读并发执行
    • 多版本并发控制 Multi-Version Concurrency Control MVCC
    • 使用一个快照来运行整个事务
    • 当前的事务id > 已经提交的事务id,则可见;正在运行/中止的则不可见
  • 快照级别的索引更新
    • PostgreSQL同一对象不同版本放在一个内存页面上,来避免更新索引
    • CouchDB、Oatomic、LMDB采用追加/写时复制技术
      • 总是创建一个新的修改副本,拷贝必要内容
      • 每个写事务都会创建一个新的B-tree,代表此时的一致性快照
      • 后台线性需要定期压缩和回收
      • 有利于读性能

更新丢失

  • 两个事务同时执行 read-modify-write 可能导致更新丢失
  • 采用原子写
    • UPDATE counters SET value = value + 1 WHERE key =’f00’
    • MongoDB可以原子的更新部分JSON内容
    • Redis可以对优先队列做原子修改
  • 显示加锁
    • SELECT ... FOR UPDATE
  • 自动检测更新丢失
    • 如果数据库的事务管理器检查到更新丢失,则会中止当前事务,退回:读-修改-写 模式
    • PostgreSQL、Oracle、SQL-Sever都支持
    • MySQ的InnoDB引擎的可重复读不支持检测更新丢失
    • 有些观点认为,数据库必须防止更新丢失,否则不能称为快照隔离
  • 不支持事务的数据库一般提供原子更新写CAS方式
  • 多主复制、无主模式下CAS和加锁都不适合了
    • 如果顺序可以交互则可以安全合并,Riak2.0使用此模式
    • 最后写入获胜LWW,可能导致写丢失

写倾斜和幻读

  • 两个事务同时更新一个对象,可能出现 脏写、更新丢失
  • 两个事务同时读取相同一组对象,不同事务更新不同对象,可能出现写倾斜
  • 目前所有数据库都没法防止写倾斜
    • 用真正的串行化执行
    • FOR UPDATE方式读,也可以解决
  • 更多写倾斜的问题
    • 会议室预定(两个事务查询会议室都为空,然后更新)
    • 多人游戏(查询位置,然后多人更新到同一位置)
    • 声明一个用户名(也是查询-写入问题导致的),可以用约束解决
    • 防止双重开支
  • 写倾斜的产生
    • 输入一些匹配条件
    • 根据查询结果,应用层决定下一步的操作
    • 继续执行更新/删除/插入,但是会破坏第一步的匹配条件
    • 对于不存在的对象,如空会议室的预定,则FOR UPDATE也无用(幻读)
  • 实体化冲突检查,把幻读问题转变为针对数据库中一组具体行的锁冲突问题

串行化

目前的实现方式

  • 严格按照串行顺序执行
  • 两阶段加锁
  • 串行化的快照隔离

实际的串行执行

  • 实现系统
    • VoltDB/H-Store
    • Redis
    • Datomic
  • 这些系统完全采用了单线程的方式,但由于在内存中执行,没有上下文切换,速度也很快
  • VoltDB采用单线程的事务方式,实现串行化
    • VoltDB的不是用复制的方式同步,而是在每个节点上执行相同的存储过程
    • 其存储过程编程语言为Java、Groovy
  • 如果数据很多,也可以采用分区的方式,每个分区独立的执行事务
  • 跨事务执行可以实现,但是效率会低几个数量级

两阶段加锁

  • two-phase locking 2PL
  • 先后去共享锁,如果要执行则再获取排它锁,此时所有事务都在等待

谓词锁和区间锁

  • 如果事务A想获取某些满足匹配条件的对象,以共享模式获取谓词锁
  • 如果要插入数据,则首先检查所有旧值和新值是否跟现有任何谓词锁冲突
  • 两阶段加锁 + 谓词锁,可以防止任何形式的写倾斜、幻读,真正实现可串行化
  • 由于谓词锁的性能不行,锁的范围太大
    • 检查123号房间在中午-下午1点是否被占用
    • 谓词锁则锁定了123号房间的所有时间、或者基于时间来锁住范围
  • 区间锁范围没那么大,性能更好一些
  • 区间锁可以防止写倾斜、幻读

可串行化的快照隔离(Serializable Snapshot Isolation SSI)

  • PostgreSQL在9.1之后推出此功能
  • 分布式数据库FoundationDB(可以跨分区执行事务)也采用类似算法
  • 2PL是悲观策略
  • SSI是乐观策略
    • 如果发生潜在冲突则继续执行,当事务提交时会检查是否发生冲突
    • 如果发生冲突则中止,并重试
    • 如果大量并发下,可能性能很差,但并发不多时性能会不错
  • SSI 也是基于版本快照,但是增加了相关算法检查写入之间的串行化冲突,决定哪些事务需要中止
  • 查询和写入之间存在因果关系,必须检查事务是否会修改其他事务的查询结果,并中止
  • 数据库检查是否发生改变
  • 读取是否作用于一个(即将)过期的MVCC对象(读取之间有未提交的写入)
    • 需要跟踪那些由于MVCC可见性规则被忽略的写操作
    • 当事务提交时,数据库会检查是否存在一些当初被忽略的写操作现在已经完成提交
  • 写入是否影响即将完成的读取(读取之后,又有新的写入)
    • 检查到A和B事务都读取同一个对象,但B提交的写跟A有冲突,于是中止
  • SSI需要记录一些读取、写入的元信息,粒度小影响范围小但开销会很大,反之亦然
  • 运行很长时间的事务,产生的冲突的概率会增大,SSI要求读-写型事务尽可能短

分布式系统的挑战

故障与部分失效

  • 单机系统中,如果出问题,则软件崩溃;也就是要么成功,要么失败
  • 后背的设计原则,宁愿使计算机全部崩溃,而不是返回一个错误结果,那样更难排查

构建大规模计算系统的思路

  • 高性能计算(high-performance computing HPC),包含成千上万CPU组成的庞大集群
    • 会有定期checkpoint
    • 可以停机重启
    • 采用专用硬件,节点之间通过共享内存或远程内存直接访问(RDMA)
    • 采用特定网络拓扑,如多维网格、toruses
  • 云计算,一般用通用计算机组成
    • 基于IP和以太网,采用Clos拓扑提供等分带宽
  • 传统企业数据中心位于上面两个极端之间

不可靠的网络

  • 在不可靠的组件上构建可靠的系统
  • 纠错码在各种通讯链路上提供可靠保证
  • TCP在IP之上解决丢包、重传、流控等问题

检查能力

  • LB要能检测出失效的节点
  • 主从复制的分布式数据库,要有自动选主能力
  • 网络不确定性使得判断节点是否失效非常困难
  • 节点在请求的过程中崩溃,则很难知道该节点实际处理了多少数据
  • 进程崩溃,但操作系统正常运行,可通过脚本通知其他节点
  • 超时是故障检查唯一可行的办法,但超时时间设置是一个问题
  • 如果节点能在r时间内完成任务,网络最大延迟为d,那么失效时间为2d + r
  • 超时时间可以设置为动态的

网络拥塞

  • 多个节点发送数据到同一个节点
  • 交换机太繁忙,可能会丢包
  • CPU太繁忙会导致等待很长时间
  • 虚拟化环境,CPU会切换虚拟机,入向的包会进入虚拟机管理器排队
  • TCP的流量控制,会自动限制自己的发送速率

同步和异步网络

  • 数据中心和互联网采用:分组交互网络,异步的
    • 为了突发流量进行了很多优化
    • 有排队的缺点,但能充分利用网络带宽(多个发送方共享带宽)
  • 固定电话,视频采用:电路交互网络,同步的
    • 带宽都固定分配好的,所以没有延迟,非常稳定,平均价格高
  • 混合分组交互和电路交互网络
    • ATM
    • InfiniBand网络(链路层实现流控),通过服务质量(Qos实现优先级和调度),准入控制
    • InfiniBand在分组网络上模拟电路交互
  • 网络中的可变延迟,本质是成本与收益相互博弈的结果

####不可靠的时钟 两种类型的时钟:

  • 测量持续时间,墙上时钟
  • 某个时间点的时钟,单调时钟

时钟同步

  • 计算机中的石英钟会有漂移现象,百万分之一,30秒会有6毫秒偏差,一天有17秒偏差
  • 如果与NTP时钟相差太多,可能会强制倒退,或者跳跃
  • 广域网环境,会导致延迟更大
  • 跨节点的事件,如果依赖本地事件做排序,则顺序会错乱,LWW会导致丢失

谷歌的Spanner

  • 时钟的置信区间
    • 谷歌设置了[start,end]作为一个时间区间,这是一个精准的范围
  • 全局快照的同步时钟
    • 单机版依靠唯一事务ID,可以根据因果关系排序
    • 通过GPS时钟,原子时间做到非常精准,然后给出置信区间
    • 事务ID根据置信区间是否重叠,就能判断是否有依赖
    • 根据时钟同步来处理分布式事务语义也是一个开放的研究领域

进程暂停

  • 获得租约后,暂停了一段时间,导致出现了两个写节点
  • 进程暂停原因
    • GC
    • 虚拟化环境中的虚拟机暂停(从一个主机迁移到另一个主机)
    • 笔记本等终端设备关闭时的暂停
    • 操作系统的上下文切换
    • 磁盘操作读写I/O(可能跟GC同时发生),或者出现SWAP,S3等网络I/O
    • 发送的SIGSTOP信号(要等SIGCONT才能继续运行)
  • 分布式系统的任何节点,执行过程中任何时刻都可能被暂停很长时间
  • 实时操作系统,可以做到及时响应,但吞吐量不高
  • 将GC当做计划内的临时离线,当启动GC前由其他节点来接管请求
  • 定期重启,重启时重新路由节点的流量

知识-真相-谎言

真相由多数节点决定

  • 节点不能根据自己的信息来判断自身的状态
  • 当多数节点认为某个节点A已经挂了(即使A还活着),那么也必须接受A挂掉的现实

分布式锁

  • 为防止GC导致的租约失效问题,采用 fencing令牌
  • 通过ZK的zid,可以获得自增ID,当做token
  • 如果写入的token 小于存储系统当前的token,则拒绝写入
  • 如果存储系统不支持额外的令牌检查,可以将令牌系统内嵌在文件名中

拜占庭故障

  • 航空航天领域,内存或CPU寄存器可能被辐射发生错误数据,不能直接下线会导致事故
  • 比特币等交易系统
  • 叛将必须 小于 1/3,系统才能达到共识
  • 数据中心内没有拜占庭故障,但有弱的谎言形式
    • 硬件错误
    • web层接收的恶意输入
    • NTP服务器时间差距多大(用多个服务器来实现鲁棒性)

计时方面的系统模型

  • 同步模型,任何进程、网络的延迟和暂停都有上限
  • 部分同步模型,大部分情况下都有有限的,但有时候无法确定上限
  • 异步模型

节点失效的系统模型

  • 崩溃-中止模型
  • 崩溃-恢复模型
  • 拜占庭(任意)失效模型

真实的系统,最普遍的组合方式:

  • 崩溃-恢复模型
  • 部分同步模型

正确的算法

  • 唯一性,两个令牌不能有相同的值
  • 单调递增
  • 可用性
  • 安全性 与 活性
  • 唯一性、单调递增 属于安全性
  • 可用性 属于活性

一致性与共识

设计原则

  • 通过事务,开发人员不用关心底层存储是否可靠(持久),有没有崩溃(原子),有没有多人同时访问(隔离)
  • 类似这个思路,分布式应用也可以忽略内部的各种问题,对外提供一种抽象表示
  • 这种方式就是:共识,多个节点对某一项提议达成一致

可线性化

定义

  • 对外看来,好像只有一个副本
  • 可线性化、原子一致性、强一致性 都是一个意思

实现线性化

  • 一旦某个读操悻返回了新值,之后所有的读(包括相同或不同的客户端)都必须返回新值
  • 原子比较设置
  • 每个读操作须返回最近写操作所设置的值

可线性化 vs 可串行化

  • 可串行化(Serializability)
    • 事务的隔离属性
    • 确保事务执行的结果与串行执行(即每次执行一个事务)的结采完全相同
  • 可线性化(Linearizability)
    • 读写寄存器(单个对象)的最新佳保证
    • 并不妥求将操作组合到事务中,因此无法避免写倾斜等问题
  • 数据库可以同时支持可串行化与线性化
  • 严格的可串行化或者强的单副本可串行化(strongone-copy serializability, strong-lSR)
  • 串行化的快照隔离,因为读到了旧值,所以不是线性化

线性化依赖条件

  • 主节点选举,ZK、ETCT(可线性化的写操作)都可以保证
  • 加锁、约束与唯一性保证
  • OracleReal Application Clusters RAC实现粒度更细
  • 跨通道的依赖,足球比赛时A告诉B结果、图片压缩采用了写数据库、读消息队列 两个通道
  • 不同的通道产生了条件竞争,引入读自己的写 可以解决,但会更复杂

实现线性化系统

  • 主从复制,部分支持可线性化
  • 共识算法,可线性化
  • 多主复制,不可线性化
  • 无主复制,不可能线性化
    • 即使r+w>n(3个节点3个写2个读),看起来好像满足,但仍然会出现非线性化
    • A读到了1新1旧副本,B读到了2旧副本,不满足
    • 同步执行读修复,写操作在发送结果之前,必须读取quorum节点以获取最新值
    • 通过牺牲性能,达到可线性化
    • 但安全做法是,认为Dynamo风格的无主复制系统无法保证线性化

线性化的代价

  • 如果发生分区,则没法保证线性化
  • 最初的存储系统依靠共享存储实现线性化
  • CAP鼓励通过无共享存储实现线性化
  • CAP的误导(因为一定会出现分区),网络分区情况下,选择一筑还是可用
  • CAP的局限
    • 只考虑了一种模型(可线性化)、一种故障(分区,节点活跃但相互断开)
    • 没有考虑网络延迟、节点失败或其他需要折中的情况
  • 现代多核CPU就是非线性化的
  • CAP理论不适用于当今的多核内存一致性模型
  • 不支持线性化的系统是为了提供:性能,而不是容错
  • 想实现线性化,那么读、写请求的响应时间至少要与网络中延迟成正比

顺序保证

排序、可线性化 与 共识算法存在深刻的联系
顺序与因果关系

  • 一致前缀读
  • 三个主节点之间的数据复制,写会覆盖其他写入,好像对不存在的行更新
  • 检查并发冲突,A和B存在 A->B、B->A、A|B
  • 读倾斜、写倾斜
  • 不同的通道的竞争
  • 因果关系对发生的事情做了某种排序,发送先于收到消息
  • 全序和偏序
  • 可线性化是 全序,任何两个元素都可以比较(线性化存储中不存在并发)
  • 因果关系是偏序,存在一些并行的情况
  • 可线性化一定满足因果关系,因此 强于 因果一致性
  • 使用其他方式来满足因果一致性,可以容忍网络故障和延迟,实现一致性
  • 新数据库正在探索因果一致性,类似最终一致性,但性能更好

序列号排序

  • 通过递增的方式实现序列号,保证A的序号一定在B之前,达到因果一致性
  • 非因果序列生成器
    • 两个节点,一个生成奇数、一个生成偶数
    • 把墙上时钟附加到每个操作上,保证足够分辨力,实现最后写入获胜
    • 预先分配一段序列,A处理1-1000,B处理1001-2000
    • 以上方式不会将请求压到一个节点上,有更好性能
    • 但以上方式可能无法保证因果一致
  • Lamport时间戳
    • 每个节点、每个客户端都跟踪迄今为止最大计数器的值
    • 可以保证全序和因果一致性
  • Lamport时间戳 vs 版本向量
    • 版本向量用以区分两个操作是并发还是因果依赖
    • Lamport时间戳则主要用于确保全序关系
    • 根据全序关系,Lamport时间戳无法区分两个操作是并发还是因果关系

全序关系广播

  • 处理用户名是否唯一这种情况,需要收集所有节点的请求,才能得到全序关系
  • Lamport只定义了因果一致的全序关系,但上述问题无法解决
  • 全序关系广播、原子广播
    • 让所有节点就全序关系达成一致
    • 可靠发送、严格有序
    • ZK和etcd实现了全序关系广播
    • 全序关系广播和共识有密切联系
    • 类似日志复制,日志是append方式追加的
  • 全序关系广播 vs 可线性化
    • 全序关系广播是基于异步模型的
    • 保证消息以固定的)II页序可靠地发送,但是不保证消息何时发送成功
    • 可线性化强调就近读,能看到最新的写入值
  • 全序关系广播,是线性化写入,但不保证线性化读取
    • 顺序一致性,也称为 时间线一致性,弱于线性化保证
    • 采用追加方式把读请求排序、广播,各个节点获取该日志,本节点收到消息才真正执行读请求,etcd的quorum模式
    • 以线性化方式读取当前最新日志消息,ZK的sync模式
  • 基于线性化的全序关系广播
    • 对每个消息原子递增读取计数器,附加到消息中并广播
    • 接受者也严格按照序列化来发送回复消息
    • 当发送了序号4,收到了序列化6消息,则要等待5才能回复6,不会有间隙
    • Lamport时间戳不是这样,这是区别全序关系广播与基于时间戳排序的关键。
  • 线性化的原子比较-设置(或自增)寄存器与全序关系广播二者都等价于共识问题[

分布式事务与共识

用到共识的场景

  • 主节点选举
  • 原子事务提交
  • FLP说的是异步模型下,不可能产生共识

两阶段提交

  • 常见的协调者
    • Narayana
    • JOTM
    • BTM
    • MSDTC
  • 两个确定,保证了原子性
    • 当参与者投票“是”时,它做出了肯定提交的承诺
    • 协调者做出了提交(或者放弃)的决定,这个决定也是不可撤销
  • 协调者发生故障
    • 超时机制无法解决
    • 参与者不能单方面提供/回滚,都会造成不一致

三阶段提交

  • 拆分的预提交可以解决本身就有问题的事务
  • 可以免去很多无用的写日志
  • 当写完日志后,有超时机制,参与者可以自己决定,但会造成不一致
  • 相当于是提高了可靠性

实践中的分布式事务

  • 数据库内部的分布式事务
  • 异构分布式事务
  • Exactly-once消息处理
  • XA事务(eXtended Architecture)
  • 停顿时仍持有锁,会导致这段时间数据一直被锁住不可用
  • 从协调者故障中恢复
    • 管理员手动操作
    • 紧急避险措施(有不一致的风险)
  • 分布式事务的限制
    • 协调者不支持复制,就相当于单点
    • 协调者如果是web服务,则此服务就变成有状态了
    • 由于XA需要与各种数据系统保持兼容,它最终其实是多系统可兼容的最低标准
    • 对于数据库内部的分布式事务(而不是XA),限制则少很多,如SSI

支持容错的共识

  • 协商一致性(Uniform agrement)
  • 诚实性(Integrity)
  • 合法性(Validity)
  • 可终止性(Termination)
  • 最后一个代表容错,满足了活性

共识算法与全序广播

  • 实现的系统
    • VSR
    • Paxos
    • Raft
    • Zab
  • 全序关系广播相当于持续的多轮共识

主从复制与共识

  • 需要共识算在去选出一位主节点

Epoch和Quorum

  • Paxos中的ballotnumb
  • VSP中viewnumber
  • Raft中的termnumber
  • 投票决定谁是主节点
  • 对主节点的提议进行投票
  • 参与两轮的quorum必须有重叠
  • 如果某个提议获得通过,那么其中参与投票的节点中必须至少有一个也参加了最近一次的主节点选举

共识的局限性

  • 复制过程是同步的
  • 需要严格的多数节点才能运行
  • 需要固定的节点,不能动态、添加或删除节点
  • 通常依靠超时机制来检测节点失效
    • 在在网络延迟高度不确定的环境中会有问题
    • raft曾出现过bug

成员与协调服务

  • ZooKeeper和etcd主要针对保存少量、可完全载入内存的数据
  • ZooKeeper
    • 线性化的原子操作
    • 操作全序
    • 故障检测
    • 更改通知
  • 共识的主要功能
    • 节点任务分配
    • 服务发现
    • 成员服务,查看哪些节点是否活跃

共识总结

  • 共识意味着就某一项提议,所有节点做出一致的决定,而且决定不可撤销
  • 多个广泛的问题最终都可以归结为共识,并且彼此等价
  • 等价问题
    • 可线性化的比较-设置寄存器
    • 原子事务提交
    • 全序广播
    • 锁与租约
    • 成员/协调服务
    • 唯一性约束
  • 主复制和多主复制复制系统通常并不支持全局共识

派生数据

批处理系统

三种不同类型的系统

  • 在线服务,同步交互,相应时间很重要
  • 批处理系统(离线系统),可以等很久,性能指标是吞吐量
  • 流处理系统(近实时系统),介于上面两者之间,在事件发生之后就处理

使用UNIX工具进行批处理

使用工具做简单的日志分析

1
2
3
4
5
6
cat /var/log/nginx/access .log | 
awk’{print $7}’                |
sort                           | 
uniq -c                        | 
sort -r -n                     | 
head -n 5 

命令行

  • awk、sed、grep、sort、uniq、xargs可以组合报表分析,效果非常好
  • sort可以自动的扩展到并行,数据量很大的时候,可以自动换出到磁盘

UNIX的设计哲学,像花园的管道一样把软件连接在一起

  • 每个程序做好一件事,新工作就另起一个程序
  • 每个程序的输出成为另一个尚未确定的程序的输入
  • 尽早尝试设计和构建软件,甚至是操作系统
  • 优先使用工具来减轻编程任务,即使你不得不额外花费时间去构建工具
  • 自动化、快速原型设计、增量式迭代、测试友好、可管理的模块等
  • 跟现在的DevOps非常类似

统一接口

  • UNIX中,接口就是文件(文件描述符)
  • 另一个统一的接口是HTTP

逻辑与布线分离

  • 标准输入、标准输出
  • 可以设置任何输入、输出
  • 将一个程序的输出、变成另一个程序的输入
  • 这是一种松耦合,后期绑定的方式
  • 输入/输出的布线连接与程序逻辑分开

透明与测试

  • UNIX命令的输入文件通常被视为是不可变的
  • 可以在任何时候结束流水线,观察其效果
  • 可以将流水线某个阶段的输出写入文件,并将该文件用作下一阶段的输入

MapReduce和分布式文件系统

相关项目

  • GlusterFS
  • QuantcastFile System
  • AmazonS3
  • Azure Blob
  • OpenStackSwift
  • 编码算法 Reed-Solomon

M-R的问题

  • 两个MapReduce之间相互调用,需要通过文件路径来确定
  • 有50-100个MR的任务非常常见(推荐系统),需要有专门的工作流系统来调用
  • 相关调度工具
    • Oozie
    • Azkaban
    • Luigi
    • Airflow
    • Pinbal
  • 一些高层级别的工具,支持自动将MapReduce任务串联起来
    • Pigl
    • Hive
    • Cascading
    • Crunch
    • FlumJava

MapReduce的用处

  • join
  • gourp

数据倾斜

  • 某个reducer可能会处理非常多的任务
  • Pig通过抽象确定哪些是热键,然后随机的发送给Reducer中的一个
  • 传统的方式使用hash分发到reducer中
  • Crunch 使用共享join的方式,需要指明具体哪个是热键
  • Hive需要再表格元数据中指明哪个是热键

优化

  • map端的join,这种方式没有reduce,
  • 每个mapper只需从分布式文件系统中读取输入文件块,然后将输出文件写入文件系统即可。
  • 广播hash
  • Hive的bucketedmap join,两端的分区一致,hash完之后都是相互匹配的
  • map端join(输入数据集相同方式分区,相同关键字排序)
  • 了解数据集的物理布局非常重要
  • 还要知道分区数量,分区和排序的关键字

批处理工作流的输出

  • 批处理即不是事务处理,也不是分析
  • 谷歌用M-R构建索引
  • 分类器(例如垃圾邮件过滤器,异常检测,图像识别)
  • 推荐系统(可能认识的人,可能感兴趣的商品)
  • Hadoop和UNIX有相同的哲学
    • 输入都是不可变
    • 如果出现错误,只要丢弃重新运行即可
    • 而OLTP数据库则不行,这种直接丢弃的方式,有利于敏捷开发

Hadoop与分布式数据

  • MPP数据库专注于在一个机器集群上井行执行SQL查询分析
  • MapReduce是可以运行任意程序的通用操作系统。
  • 存储多样,文本、图像、视频、传感器读数、稀疏矩阵、特征向量、基因组序列或任何其他类型的数据
  • Hadoop,数据湖,是读时模式,不同团队共享数据会比较容易
  • MPP数据库,是写时模式
  • Impala和HBase底层都是对接Hadoop,但是存储格式并不同,而且一个是OLTP,一个是OLAP
  • 硬件其实没那么容易坏,谷歌最初的论文假设MapReduce任务是抢占式的
  • 100个任务运行10分钟,那么至少一个被杀掉的风险是50%
  • 这么做是为了更好的利用资源,测试环境和生成环境公用一个集群,但低优先级的MR可能随时会被kill掉
  • 所以谷歌当初的设计并不只是硬件的容错,更是当时环境导致的

MapReduce的问题

  • 太底层,想要用MR实现一个功能其实很难,更多是用上层工具完成的
  • UNIX管道是同时启动多个进程,而M-R需要等前面任务完成才能启动下一个,需要等待前面很慢的任务
  • 不同的任务的reduce和mapper可能做了类似的事情,mapper有些冗余
  • 将中间状态存储在分布式文件系统,意味着文件会被复制到多个机器,有点多余

数据流引擎

  • Spark
  • Tez
  • Flink
  • Dryad和Nephele风格
    • 只在必要的时候排序
    • 将没有必要的map任务合并到reduce中
    • 优化join顺序
    • 减少写入文件,将中间结果写入到内存、本地磁盘
    • 预先启动一些任务,免去了M-R任务冷启动的耗时
  • 容错
    • Spark使用血缘关系+checkpoint
    • Flink使用checkpoint
  • 不需要自己将所有中间状态写入文件系统

图和迭代处理

  • PageRank算法、机器学习、排名系统
  • 通过一次遍历一个边、将一个顶点于相邻顶尖join起来以便传递某种信息,直到中止
  • M-R的效率低,因为跟上次相比,本次只有一小部分改变,但却要读取整个数据集并产生全新输出
  • 计算的批量同步井行(bulk synchronous parallel BSP)
  • 谷歌的Pregel论文,和相关系统
    • Apache Giraph
    • Spark的GraphX API
    • Flink的Gelly API
  • 每次迭代,将每个顶点函数发送到相关顶尖
  • 每次迭代结果保存在内存中
  • 通过定期的快照实现容错

高级API

  • 更通用的接口API
  • 声明方式有利于JOIN优化
  • 向量化执行,代码生成
  • k临近、分类、推荐等机器学习框架也用在了批处理系统上

总结分布式框架要解决的问题

  • 分区、容错
  • 分区算法:
    • 排序-合并join
    • 广播join
    • hash join

流处理系统

发送事件流

传统数据库都是pull模式,很少有push方式
发布订阅模式

  • 发送速度过快:丢弃,放入队列中,消息背压(UNIX管道和TCP)
  • 节点崩溃是否会丢数据

生产者-接受者直接发送消息

  • UDP组播
  • 无代理的消息库(ZeroMQl、nanomsg)
  • StatsD、Brubeck使用不可靠的UDP消息传递来收集网络中所有机器的指标井对其进行监控
  • HTTP、RPC

消息代理

  • 没有二级索引,不支持范围查询
  • 跟数据库相比,只是作为瞬间存储的
  • 获取消息后,就会被删除
  • JMS和AMQP标准
    • RabbitMQ
    • ActiveMQ
    • HornetQ
    • Qpid
    • TIBCO Enterpris Message Service
    • IBM MQ, Azure Service Bus
    • GoogleCloud Pub/Sub
  • 多个消费者
    • 负载均衡式
    • 扇出方式,一对多
  • 日志会重复

分区日志消息

  • 实现的系统
    • Apache Kafka
    • Amazon Kinesis Streams
    • Twittr DistributedLog
  • 对比传统消息代理
    • 消息处理代价高,不在乎顺序,希望并行处理,用JMS/AMQP
    • 吞吐量高、处理快、要求顺序 用日志消息
  • 消费者偏移量
  • 磁盘空间使用
  • 当消费者跟不上生产者时
  • 重新处理信息

数据库与流

同步的方式

  • ETL
  • 双写,会有一致性问题,也会丢数据
  • Change Data Capture, CDC,会有延迟问题
  • 相关系统
    • Linked的Databus
    • Facebook的Wormhole
    • Yahoo的Sherpa
    • Bottled Water 使用解码日志API实现PG的CDC
    • Maxwell
    • Debezium
    • Mongoriver读取MongoDB的oplog
    • Oracle Golden Gate

CDC

  • CDC的初始快照
  • 日志压缩,对删除做了merge
  • kafka这样的系统持久保存数据,可以从0的offset读取获得全量数据
  • API
    • RethinkDB支持订阅查询结果发生变化的通知
    • Firebase和CouchDB可以将同步变更提供给应用层
    • Meteor使用MongoDB oplog来订阅更改消息
    • VoltDB支持事务以流的形式连续地从数据库中导出数据

事件溯源

  • 应用程序以数据可变方式来操纵数据库
  • 应用程序逻辑是基于写入事件日志的不可变事件构建的
  • EventStore 是这种方式的数据库
  • 区分命令和事件

流和不可变

  • 应用状态是事件流对时间的积分得到的
  • 变化流是状态对时间的求导得到的
  • 会计中的每笔记录都是不可变的,写错了只能再触发一笔
  • 命令查询责任分离(CommandQuery Responsibility Segregation, CQRS)
  • 基于日志复制都是异步的,需要同步,或者全序关系广播
  • 永远保存所有历史变化对于append是可以的,但是大量更新不合适
  • 法律问题,当用户删除账户后,不能保留历史,必须全部删除

流处理

流的使用

  • 将数据写入DB、cache、es等,然后客户端查询
  • 通过某种形式推送给客户
  • 处理一个或多个输入流以产生一个或多个输出流

流的场景

  • 场景
    • 欺诈检查
    • 金融交易检测,再指导其做一些事情
    • 制造工厂的检查
    • 军方检测
  • 复杂事件处理(Complex Event Processing CEP)
  • 数据库存储是永久的,查询是暂时的
  • CEP查询是永久的,来自输入流事件匹配查询
  • 相关系统
    • Esper
    • IBM Info Sphere Streams
    • Apama
    • TIBCO StreamBase
    • SQLstream
  • 流分析,使用hyperloglog,基于概率的近似值
  • 源系统和查询系统之间的同步,有点类似于更新物化视图
  • actor模型中也使用了流技术,但跟流查询并不同
    • actor是并发和分布式执行,而流是管理数据
    • actor是短暂的,而流是持久的
    • actor可以任意方式执行,而流只能用于非循环流水线

流的时间问题

  • 星战的问题,先上映4,5,6;然后是前传1,2,3;之后是后传7,8.9
  • 如果发送方有重启,那么按请求时间处理,则看起来好像有波动,实际则是平稳的
  • 因为各种问题,可能导致某个时间点的事件有严重延迟,解决方式
    • 忽略,丢弃这些事件
    • 发布一个更正,针对滞后事件的一个更新值
  • 为了调整不正确的设备时钟,一种方告是记录三个时间戳:
    • 根据设备的时钟,记录事件发生的时间
    • 根据设备的时钟,记录将事件发送到服务器的时间
    • 根据服务器时钟,记录服务器收到事件的时间
    • 通过(3) - (2) 可以估算出设备时间和服务器时间的偏移量
  • 窗口类型
    • 轮转窗口,固定的
    • 跳跃窗口
    • 滑动窗口
    • 会话窗口

流的JOIN

  • 流和流join
  • 流和表join
  • 表和表join
  • 表的join,有点类似于物化视图
  • 数据仓库中的缓慢变化维度

容错

  • 批处理处理起来很容易,但是流不容易处理
  • Spark的微批处理方式,Flink定期做checkpoint
  • 流框架本身支持事务性
  • 上层的应用支持冥等性

数据系统的未来

数据集成

每个产品都有他的适应范围,厂商也不会告诉你的,了解每个产品的特点
然后在不同环境中,组合使用这些产品
流复制

  • 相比ETL,双写,流复制不会出现竞争问题
  • 事务是线性一致性的,而流复制时异步的
  • 全序的局限
    • 多个分区情况下,不同分区之间的顺序不明确
    • 每个数据中心都有独立节点,不同数据中心的事件顺序不确定
    • 微服务部署时,两个事件来自不同服务时,这些事件没有清晰的顺序
    • 客户端可以离线工作,这样客户端和服务器可能看到不同的事件顺序
    • 大多共识算法针对单节点吞吐量设计的,不支持多借点共享的事件排序机制
  • 排序事件以捕获因果关系
    • 逻辑时间戳可以在无协调者情况下提供的全序关系
    • 记录一条事件来标记用户在做决定以前所看到系统状态,井给i主事件一个唯一的标识符
    • 冲突解决算法可以处理异常顺序的事件

批处理和流处理集成

  • 数据整合的目标是确保数据在所有正确的地方以正确的形式结束
  • Spark 通过将流分解为微批处理来在批处理引擎之上执行流处理
  • ApacheFlinkli!IJ直接在流处理引擎上执行批处理
  • 流处理可以将输入的变化数据迅速反映在派生视图中
  • 处理则可以反复处理大量的累积数据,以便将新视图导出到现有数据集上
  • lambda架构
  • 统一批处理和流处理

分拆数据库

UNIX和数据库

  • UNIX为程序员提供一个逻辑的,但相当低层次的硬件抽象
  • 数据库为程序员提供一个高层次的抽象,来隐藏磁盘上数据结构的复杂性、并发性、崩溃恢复等

编排多种数据存储技术

  • 创建索引,跟配置新的从节点副本类似,改变数据后,索引也会跟着改变
  • 元数据库,整个组织的数据流开始变得像一个巨大的数据库
  • 批处理和流处理器就像触发器,存储过程和实体化视图维护相关实现
  • 两种途径
    • 联合数据库:统一读端
    • 分离式数据库:统一写端
  • 对于统一写端来说,具有幕等写入的异步事件日志是一种更加健壮和可行的方式
  • 基于日志的集成的一大优势是各个组件之间的松搞合
  • 分离的目的是广度,将多个数据库组合起来对应更广泛的需求
  • 缺少了类似UNIX的管道技术,如 mysql | elasticsearch ,直接将mysql的数据放到es去做索引

围绕数据流设计应用系

  • 电子表格的数据一变动,其公式中展现的结果就变了
  • 二级索引是一种派生的数据集
  • 各种自然语言处理是一种派生(语言检测、自动分词、词干或词形识别、拼写检查和同义词识别)
  • 各种特征提取和统计分析功能从训练数据中导出模型 是派生数据
  • 缓存中的聚合数据,也是派生数据
  • 系统的某部分专注于持久性数据存储
  • 另外一部分专门负责运行应用程序代码
  • 维护派生数据
    • 当维护报生数据时,状态更改的顺序通常很重要
    • 容错性是派生数据的关键
  • 数据流系统是异步的,而微服务是同步的

观察派生状

  • 读路径、 写路径
  • 类似索引那样, 写路径会增加,但对于后续的读路径会减少
  • 没有索引,写路径会减少,但是读路径会增加很多
  • 客户端可以缓存结果,进行本地浏览交互,这样完全没有网络通讯
  • 等网络连通后,再接入源端网络,获取最新信息
  • WebSocket也可以看做是一种流时间,由服务端主动推送的
  • 读取也可以当做一个事件来处理,这样方便跟踪其因果关系,但增加了I/O开销
  • 推特中某人看了哪些URL需要分区处理,反欺诈需要检查此人的所有信用也需要分区处理
  • MPP中的的查询也是要分区处理,将读作为事件可以提供一种新的选择
  • 数据库等存储系统都是读取/响应模式,很少支持订阅的
  • 响应性的用户界面、更好的离线模式也值得尝试,发布/订阅这种模式对于存储也值得尝试

端到端的正确性

数据库的端到端

  • TCP可以去重,但是两个TCP连接的数据是重复的,TCP协议本身就没法控制了
  • 两阶段提交可以保证原子性,但是重复提交相当于两次事务了,数据库没法保证
  • 加入UUID,可以保证端到端的正确性
  • A 转转给 B,在事务开头增加一个写入(UUID那个字段有唯一约束),再做更新就可以去重了
  • TCP复制消除,以太网校验和,WiFi加密 无法提供端到端的有效应
  • 事务是一个很好的抽象(并发写入,违反约束,崩愤,网络中断,磁盘故障等)当做提交、决绝处理
  • 但事务的代价太高了

强制约束

  • 唯一性约束需要达成共识
  • 共识算法的扩展性不强
  • 基于日志的消息传递唯一性
  • 将 A转账给B 做成异步的
    • 将这个事件,加上UUID,写入一个库中(可以保证原子性)
    • 通过日志复制写入到流系统中
    • 第一个系统处理扣款,第二个系统处理收款
  • 避免了原子提交,但有更好的性能和容错性

时效性与完整性

  • 时效性,意味着看到的都是最新的,线性一致性
  • 完整性,意味着数据是完整的,没有丢失
  • 完整性一旦破坏就是永久性的,时效性是暂时的
  • 流系统的:只执行一次 保证了完整性,但需要冥等、去重
  • 可以放低约束性要求,之后通过补充来弥补,比如超卖后订单出错,给客户补偿

无需协调的数据系统

  • 数据流系统可以保证派生数据的完整性,无需原子提交,线性化或跨分区的同步协调
  • 只要整体上保证完整性,即使发生暂时约束破坏,可以事后进行修复
  • 只在某些必要的情况下做事务,事务也可以减少超卖的发生,但降低可用性
  • 在事务和流系统的设计中做好权衡

信任和确认

  • 任何硬件都可能出错,内存也可能出现 但比特翻转
  • 即使mysql和PG也会有bug
  • 不能盲目的信任承诺,ACID就给了我们一种信任承诺的假象
  • 定期做端到端验证(中间的任何磁盘、网络、算法故障都自然的被验证了)
  • 事件溯源的方式,非常适合审计
  • 完整性检查和审计算法也许会出现在更多的通用数据库中

做正确的事情

不应该只关注技术,技术产生的风险、法律、道德问题也要考虑

预测性分析

  • 数据分析会给人贴标签,尽管这个人没有认证犯罪前科,也没有犯罪证据,却被各种系统拒绝了(且无法申诉)
  • 预测分析系统只是基于过去而推断,如果过去是有偏见的,它们就会把这种偏见编码下来
  • 算法预测出现问题时,怎么负责,怎么向法官解释器原理
  • 正态分布使得某些情况下会出现极个别的异常情况,但算法如果只考虑平均,就会忽视那些异常原因
  • 算法错误的给人评级,造成这个人信用下降,丢失工作,会继续恶化,未来会导致信用进一步降低

数据隐私与追踪

  • 数据追踪就等于监控
  • 对于社交软件来说,可以拒绝其隐私策略,这等于放弃使用权,代价也非常高
  • 工业革命带来了社会巨大进步,但也伴随着污染问题、压迫工人,虽然之后解决了,但成本也上升了
  • 现在的数据收集与滥用 就和当时的工业时代一样,是信息时代初期的表象
  • 收集隐私可以更高的处理广告,这时候对于公司来说,广告主是首要,用户是其次
  • 收集隐私可能对于医疗方面帮助很大,过度监管可能会破坏这种潜在机会
  • 很难在监管和潜在机会之间做出平衡