第一部分 数据的存储

存储——性能（存储介质，数据格式，数据组织，索引，cache)
   ——扩展性（对于scale up共享内存和磁盘部分忽略）
   ——功能（索引，事务）
   ——一致性
   ——可靠性
   ——成本（物理，维护）

性能

数据组织

• 模型
  1.SQL 对象和关系不批配，ORM不能隐藏，支持XML/JSON转为行或者列
  2.文档型，多对1关系，文档对连接支弱，多对多=》文档引用（并非所有文档性都支持mongodb不支持连接）。二者对于复杂关系都抛弃了旧的网络模型（网络模型必须搜索所有路径）
  文档读取只能读取一整条，无法直接获取第二项；无模式alter table
  3.图模型：当多对多特别频繁，社交图谱，网络图谱等。三元组存储。SPARQL
  与网络差别：无模式，任意记录类型的嵌套，通过唯一ID直接饮用任何节点，也可以建立索引查询定点，网络中只能通过范耐高温你路径，订点和边无序，查询支持SPARQL
• 索引及数据存储方式
  1.文件追加加入+hash索引：
  hash索引key和偏移量：散列表必须要内存中放得下，否则需要大量随机访问，不支持范围查询
  分段，开启新段，压缩合并旧段。逐个向后找。旧段的索引、旧数据的删除可以通过偏移量最小点删除或者保持冗余
  考虑点：删除标记，崩溃hash索引的恢复，数据库中途崩溃，并发控制

  2.内存放不下，hash索引=》稀疏索引+有序
  SSTables：sorting string table 要求每个键只在每个段中出现一次且排序可以超出内存（随加载随merge），不需要保存所有键的索引（排序），范围查找
  如何让数据有序：磁盘上B树，内存中更容易：红黑树/AVL树
  LSM，日志合并，保存一系列在后台合并的SSTable，写入时，添加到内存的红黑树中。作为SSTable写入磁盘。关键在于会如何压缩和合并
  LevelDB 水平，HBase 大小分层
  3.从日志追加到就地更新=》B树
  写操作用新数据覆盖磁盘页面，并发控制复杂。需要用哪个额外的磁盘（redo log）放着覆盖失败。LSM只是追加
  一些优化：修改页面写入不同位置，父页面创建新版本（mongodb）。B+树等
  比较B树与LSM
  B 读取速度快。写面redolog和本身，页面维度覆盖
  LSM 写入速度快，压缩分段检查不同SSTables。SSTbales的复写在合并（有时应为磁盘写入带宽等有限，有影响，压缩和写入速率控制）。LSM更小由于压缩
  4.其他索引：多列索引（B树和LSM都不能很好的支持）；空间，二维填充曲线转为单个数字再用B树索引，或者用特殊化的空间索引R树；全文索引/模糊索引，lucene
  5.内存中存储一切：性能+实现特殊的磁盘和索引难以实现的数据模型比如队列。=》反缓存

• 分析=》大量扫描索引不重要了，解决IO问题。压缩
  上面的模型和结构在事务中很常见，在分析系统中，有些常用过简单的模型和索引等
  星型和雪花型
  列存储：行巨多但每次只查询少数列。=》列压缩，避免修改的LSM
• 数据格式
  内存中:针对cpu和操作优化，树、列表
  文件/网络传输：编码，json/xml/csv/二进制(thrift,protocal buffer)
  需要考虑：数据表更改兼容（数据库中的数据，REST/RPC/Mq中的数据）
  这部分详见：https://segmentfault.com/a/11...

事务

• 单对象，日志崩溃恢复+锁实现隔离性+CAS实现复杂的自增原子操作，但是事务更多指多对象
• 事务的关键：中止。ACID数据库违反原则放弃事务。无主复制的数据存储尽力而为遇到错误不撤销
• 重试问题：
  如果服务器已经成功但返回超时，可能成功两次
  错误由于负载过大造成，重试会造成更大的
  仅在临时性错误后才值得重试，永久性错误重试没没有意义
  事务后还副作用，比如发送邮件，几个系统一起，二阶段提交
• 隔离
  1.脏写：行写锁
  2.脏读：锁代价大=》持有写入锁可以设置新值，读旧数据。读已提交的隔离级别，只需要保留一个版本
  3.可重复读：A事务过程中读取数据是一致的，即使该数据在期间被B修改，实现：MVCC。读已提交为每个查询使用单独的快照，可重复读对整个事务使用相同的快照。记录创建和删除的事务号，对大事务号的写入操作都忽略。索引可以指向所有版本，再过滤，可以所有版本存储在一个节点。还有仅追加，不更新，创建新的树分支，不需要再写另外存储。
  4.关于幻读：网上的资料都是错的，MVCC可以保证读的正确性，会找旧版本。但是对写不保证，因为写会取最新的，只能用锁保证，比如虽然事务中select 取不到另一个事务的，但是Insert可能会冲突报错，select for update也会读到B事务的，因为读取是最新的。若要保证更新没问题用select for update加锁。这种先select检查再update的行为导致会议室预定等问题。幻读其实是写偏差。当可以间隙所时加锁，不能比如!=1
  5.丢失更新：A select value=2后update value=value+1。但是期间B事务insert value=3。此时value=4都是因为写都是最新的。这种问题mysql可重复读不保证，要么数据库加排它锁保证整个事务原子，要么显示锁定比如for update，代价较大。或者CAS，update value=value+1 where value=3；
  分布式丢失更新？允许多节点并发，不能用锁和CAS=>冲突解决
  6.串行化：单线程（扩展性不好，分布式要一个一个等，为了提高性能可以一个分区一个CPU一个事务线程，对于夸多分区的需要分区锁，尤其二级索引，吞吐量差）
  7.锁
  两阶段锁定：读共享锁写升级为排他锁，写要等所有的读释放，读必须等写释放，经常发生死锁。锁粒度控制：谓词锁（性能不好，符合搜索条件的再加锁）=》间隙锁（范围或全表）
  SSI 序列化快照隔离：悲观锁=》乐观锁（先执行到提交时再检查是否与隔离违背，违背则中止重试）。快照隔离+检测写入序列化冲突。（读之前存在未提交的写入）MVCC的读在提交时检查是否有被忽略的写入已经被提交。写入数据时通知所有最近读取的其他事务（读之后发生写入）

扩展性

• 分片
  hash(事先分多)
  hash+键值组合
  一致性hash(不推荐，写不好)
  range(hbase 热点问题，分配不均，扫描和范围查询)

• 二级索引:
  1.按主键ID范围分区，写入本地分区二级索引，合并读取。比如a的color放a机，按color查需要合并a和b
  2.全局按关键词索引，索引本身分布式。color自身分布式，每次写入a要写更新a和b机器的color索引，写慢读快。因为跨分区事务问题和一般异步更新二级索引，二级索引有不同步问题(不一致或部分更新失败，我认为分别是一致性问题和事务原子性问题)
• 分区再平衡：
  1.固定分区数：如果用hash%n的形式（需要移动全部数据），需要提前分配更多，按照子集扩展，比如。虽然只有4个节点，开始就设置N为20
  2.动态分区数，按数据范围，类似B树节点的合并和拆分。mongodb的范围和hash都是动态分球
  3.固定节点数。每个节点有n个分区。新加入节点随机获取几个旧节点中几个的分区的一半组成新的分区，剩余的留在原来分区中，增加节点会增加分区数量，为了均衡随机选择分区拆分，要求分区边界基于散列的分区。（最符合一致性hash的语义）
• 元数据部署
  路由决策组件：节点，单独路由，客户端
• 分区并行查询问题后续再说

可靠性

• 目的：考虑高可用的备份，高性能的负载，地理就近进行数据复制，一般三个副本可以保证11个9，两副本大规模下3个9必丢数据
• 运行：同步，异步（绝大多数领导者形式都是这个），半同步：一个追随者同步，其他异步，至少有两个节点拥有最新的数据副本
• 扩容：设置新从库，从主库拉取历史快照，从主库读取落后新数据直到commentid一致(本来就用log同步的)
• 故障发现，主动上报/心跳/lease
• 故障恢复：
  1.从库，日志点
  2.主库：确认主库失效（超时设置多少合理？）
  选择新主库 （脑裂）
  更新客户端和其他从库配置
  旧主库恢复数据冲突处理
• 复制方案：
  基于语句的。不确定性处理rand().now(),自增(mysql5.1以前)，紧凑
  WAL。用于主存储或崩溃恢复。记录数据底层磁盘块字节更改，与存储引擎紧密耦合，存储格式更改版本，若复制协议不支持匹配版本，需要停机处理
  逻辑日志，行复制。更新：唯一标识+所有列新值
  触发器（只复制部分）
• 复制延迟：几种保证：读写一致性（自己更新自己立刻可看），单调读（同一用户多次读取一致），一致性前缀读（保证读取顺序按写入顺序），最终一致性。
  前三个一致性解决方法举例：
  1）读主库，刚更新数据读主库，记录时间戳；自己请求读主库，注意不同网络和设备，分布打到多个数据中心的需要路由到主库的数据中心
  2）同一用户读固定从库，防止更旧
  3）依赖事务有因果关系的写入 同一个分片。不同分片不保证顺序一致
• 部署：
  1.单主
  2.多主，只有多活多数据中心用到。或者需要每个本地离线写入。

  
  多活多数据中心与单活对比：单活每个写入都要进入主库数据中心，增加写入时间；通过网络中心的写是同步的，对网络容忍度比多中心异步复制低很多；故障一个主从切换，一个换主。
  处理写入冲突：写入检测两个主违背多主目的，写入都成功后同步时检测冲突用户无法补救。
  并发写入：哪些需要覆盖（比如依赖关系的B知道A先发生，只需要覆盖即可），哪些是并发（B不知道A的发生，并发需要按版本解决或者允许丢失用时间或序号。）
  =》
  预防冲突：同一写入只入一个，在故障等时特殊处理（需要切换，保证不了同一个请求不丢失或不重复）。
  冲突合并：每个写入或副本一个唯一ID，覆盖丢弃，维护多版本，自动处理的数据类型：集合等，带多版本等。
  版本向量：返回时将读取自的版本返回，再次写入时该版本的就是依赖，可覆；否则是并发保留保本。

  

  3.无主：全部多读多写，返回数量足够成功。（读写法定人数的确认）
  单个落后如何恢复：读取时选择版本高的反更新（读修复）或 异步不断同步差异（反熵，不保证顺序）
  写入冲突和多主一样

一致性

困难：丢包/延迟，时钟不同步。会导致设计上再延时（同步，半同步，异步）和一致性（线性一致性，原子事务提交）上有一定取舍，现实中模型：同步模型，假设网络延迟，进程暂停，时钟误差都有界限；部分同步：大多数同步，偶尔变得相当大；异步模型：不能用超时，没有时钟。崩溃-停止故障：停止后永远不回来；崩溃恢复故障：未知时间后再次开始响应，节点具有稳定的存储且会保留内存会丢失。拜占庭故障：包括试图戏弄和欺骗其他节点。可以实现不同等级的一致性：如ACID，最终一致性，sessioin一致性，单调一致性

CAP是针对一条数据的。一致性的定义应该是广泛的（不只是副本之间数据相同），可以理解为对一条数据获取的一致性，多个人多同一条数据读结果一致，一个事务对同一数据读结果一致，唯一性读取一致（唯一被获取其他读应该失败）
写入顺序与实际一致 不属于一致性范畴但应尽量保证才使得读有意义，也归到这里讨论。叫因果一致性
最强的一致性是线性一致性（一旦写入成功读取的就是该值，直到再次覆盖）
因此涉及到问题大概有：因果一致性保证，线性一致性保证，事务一致性保证，唯一性约束

• 因果一致性
  lamport时间戳，一个客户端在多个写节点中的顺序保证，保证同步时因果覆盖正确。解决同一客户端发出对同一操作两个有序请求，最终到两个主库上，序号（到达是有序的，但时钟不可靠）不一定哪个在后，所以同步时有错的问题。办法就是每次请求带节点最大序号，更新落后的节点。（不需去取全局递增序号）
  在纸上画了一下，与其他方案对比。不方便画，后续补吧
  只是提供同步序号问题，只有同步解决才会得到全局数据，读数据调的应用需阻塞在全局回复上

• 全序广播
  顺序在消息传递时被固化，不允许将消息插入到顺序中较早位置。全序广播保证以固定顺序可靠的发送，不保证消息何时被送达.
  全序广播实现线性一致性存储

  向全序日志中追加一个唯一抢的用户名
  读日志，等待消息被送回
  写一致性：若该用户所有权第一条消息是自己的，确认提交。若有并发写入，所有节点会对最先到达者达成一致
  读取一致性：当有读取时追加一条消息，消息回送时读取日志，执行实际的读取。其他等待直到该位置前的所有消息都传达到你，再执行读取。或者可以从哪个同步更新的副本中读取

• 线性一致性：包含因果性(从概念上是读取最新的写入，但是写入有延迟是可接受的，读取不变即可)
  线性一致性是新鲜性的保证，读取一定能看见最新的写入值
  线性一致性存储实现全序广播
  每次全序广播发送首先从哪个线性一致寄存器执行自增并返回操作，作为序号附加到消息中，将消息发送到所有节点，收件人按照序号连续处理消息。与lamport时间戳不一样，一致性存储数字没有间隙，如果节点发送了4并且收到6，在传递6之前必须等5再发送6。
  全序广播和线性一致都等价于共识
• 分布式事务原子提交
  1.二阶段提交

  
  如果协调者在准备好后失败，不得不等待他重新恢复。协调者上的常规单点提交。
  协调者有问题，锁无法释放棘手问题

  2.三阶段分布式原子提交

  
  所有消息处理要保证可重试
  缺陷：协调者单点，引入协调者可能使得服务器不再是无状态的不能随意扩容，当夸各种数据系统时，需要时所有系统的最小集不能检测系统间死锁无法SSI等，数据库内部的分布式事务(其实非XA)没有3问题但是系统任何部分失败都会失败扩大失效=》改用共识

• 共识
  详细见单独：https://segmentfault.com/a/11...
  全序广播相当于重复多伦共识。

常见数据存储开源方案

1.redis=>codis

性能

redis单机基础
内存
跳表-list

功能

无索引，基本不支持事务

redis的分布式

1，代码中写；
2，redis Cluster。请求不在的key要两次，先返回ip再请求一次
3，代理分片，比如tuemproxy,codis

redis cluster

1.主从模式。一主多从
可靠性：无法自动故障转移
无扩展性
复制：
主服务器BGSAVE命令生成一个RDB文件，并使用缓冲区开始记录写命令
BGSAVE结束后后发送RDB文件给从服务器载入后+缓冲区命令
主服务器将所有写命令传播给从服务器
每秒一次频率向主服务器发送REPLCONF ACK <replication_offset>进行心跳检测。检测网络和命令丢失。（主服务器配置min-slaves-to-write n, min-slaves-max-lag m当从服务器数量少于3个，或者延迟大于等于10将拒绝执行写命令根据replication_offset检测是否丢失命令，补发命令）
断点续传：replication_offset，复制积压缓冲区，服务运行ID

2.哨兵模式。哨兵系统也是一个或多个特殊的redis服务器，监视普通服务器，负责下线主服务器和故障转移
可靠性：自动故障转移（哨兵通过raft协议选主，主哨兵选择主服务器）。
1.创建，根据给定的配置文件，初始化sentinel的监视主服务器列表，创建连向主服务器的网络连接命令连接，订阅连接（在建立后发送SUBSCRIBE __sentinel__:hello，sentinel需求通过接收其他服务器发来的频道信息发现未知的sentinel)
2.sentinel默认10s一次向主/从服务器发INFO命令
3.sentinel默认2s/次用命令连接向所有服务器（发现其他哨兵）发送 PUBLISH __sentinel__:hello
4.sentinel默认1s/次的频率向所有主/从/sentinel服务器发送PING命令，有效回复为+PONG,-LOADING,-MASTERDOWN。当一个实例在down-after-milliseconds内，连续向sentinel返回无效回复，sentinel修改实例中flags加入|SRI_S_DOWN标识主观下线
5.当接收到认为下线的sentinel数量超过quorum(sentinel moniter 127.0.0.1 6379 2中2设置)则flags加|SRI_O_DOWN
6.通过SENTINEL is-master-down-by-addr 看来是要分开进行，带runid。
每个发现主服务器进入客观下线的sentinel向其他sentinal发送命令
在一个配置epoch中将先到的设为局部领头，不能再更改。
接收回复检查epoch的值和自己的相同就取出leader_runid，如果发现自己被半数以上选择，则成为领头，epoch+1
如果在规定时间内未选举成功，epoch+1重新选举
7.故障转移
领头进行故障转移
1） 选出新的主服务器
在线的，5s内回复过INFO的，与主服务器断开连接时间足够短，优先级高，复制偏移量大，runid最小的，发送SLAVEOF no one，以1s/次（其他是10s/次）的频率向该服务器发送INFO。当role变为master时继续2
2） 向下线的主服务的其他从服务器发送SLAVEOF命令
3） 向旧的主服务器发送SLAVEOF命令
无扩展性

集群模式。去中心化，每个可以读写，
可靠性：gossip协议，主从自动故障转移，gossip通信，从节点发现故障，raft重新选主
扩展性：16384个槽。以槽为单位，重新分片
指派槽与节点
key与槽：CRC16(KEY) & 16383
读写到任意节点， 二次转移
重新分片：redis-trib

codis

架构
图片描述

扩展性

分片：hash
元数据：codis-proxy中，用codis-dashboard控制，zk保持同步
扩展:固定1024个slot。迁移是按照slot的维度
迁移有两个阶段，第一阶段状态改为pre_m。若proxy都确认，将状态改m。向所在的redis-server发送迁移命

可靠性

codis-proxy的用zookeeper保证。client获取zk节点做负载均衡
codis-group的主从用redis的哨兵模式

一致性

分片信息和元数据由zk保证一致性，group中主从由redis自身负责最终一致性

详细redis与codis见：
https://segmentfault.com/a/11...

2.mysql=>proxy

性能

磁盘，B+树（搜索性能高稳定，节点不包含数据可以包含更多地址，层高少，叶节点链表扫面呢），内存buffer（二级索引change buffer）
索引：聚簇索引
buffer到磁盘过程中问题：
刷脏 flush
二次写 脏页落盘需要二次写，redolog块对其不需要
清理过期 purge

功能

事务
A undo log，逻辑日志，受redo log保护 。涉及回滚
C (一个事务中间状态可见性)MVCC 每个视图有readviewid。不可见通过undo恢复
I (多个事物之间可见性/操作不干扰)MVCC
D redolog 物理位置+逻辑日志。每个事务自己buffer=>公共buffer=>磁盘 涉及checkpoint
server和innodb的binlog和redolog的一致性保证：内部二阶段提交
分布式事务

分布式

没有自己的集群管理.需要自行实现
主从 用binlog复制（基于行，语句，混合）；采取同步/半同步/异步；全局GTID代替文件名和物理偏移量使得slave在换主复制时不会重复执行相同事务操作。

扩展性

当主库支撑不了。水平扩展。拆表。

可靠性

无法自身保证

一致性

同步策略影响。
XA分为外部和内部。对于外部。要应用程序或proxy作为协调者。（二阶段提交协调者判断所有prepare后commit）。对于内部，binlog控制。
同步和事务失败回滚会有问题，先提交发送网络异常导致主库有从库无。等发送返回后提交失败回滚导致从库有主库无。

详细：
https://segmentfault.com/a/11...

3.fusion

没有开源。基于cache+rocksdb。

性能

介于redis和rocksdb之前。对rocksdb的热key多了一层cache。

功能

想结合redis的性能，mysql的持久化。redis和mysql的集成。支持分布式。

分布式

master读写都在master.slave备份作用。同一个slave和master不在一台机器上
把所有结构都转为纯粹K-V。rocksdb只负责存储kv
分片和redis一样，1024个固定，每个集群管理部分

扩展性

迁移：rocksdb文件快照，内存快照。slot迁移，增量记录。当迁移结束直接返回false换路由（最后一个增量时间在一个qps旧可以），增量后merge.

可靠性

复制：用rocksdb扫描key+多线程发送，同步成功点记录
同步：WAL。采取同步成功删除的方式。同步后用redis命令放入slot中
主备切换：codis的proxy感知切换

一致性

proxy用zk保证一致性
主备一致性WAL同步保证

4.leveldb/rocksdb

性能

SSD+SST。在正常的读写性能写入14M/S（32核），写比读稍好

功能

ACID。常规的读只会读sequenceid之前的，内存中内容用sid控制，文件中version来组织，每次sid引用的version。写会抢锁再写入成功后才更新seq+1，其他写隔离，并且本次写入内seqid也不会读到之前的。并发写入会批量分配sid段。每个事务一个writebatch的sid,只能读到最原始sid前的

分布式

leveldb没有任何分布式。bigtable是chubby(分布式锁)+单机lebeldb。
rocksdb提供了基本的备份，增量备份，恢复，同步，两阶段提交的接口支持。可以自己搭建proxy

可靠性

WAL

一致性

事务日志。

5.mongodb

详细：https://segmentfault.com/a/11...
使用文档的好处是：
文档（即对象）对应于许多编程语言中的本机数据类型。
嵌入式文档和数组减少了对昂贵连接的需求。//减少join的IO
动态模式支持流畅的多态性。
运行模型：每个连接一个线程，限制栈1M。虽然线程多切换代价大，但后台都是IO操作，代价还好。请求调用引擎层的方法
引擎
wiredTiger（简称WT）支持行存储、列存储以及LSM等3种存储形式，Mongodb使用时，只是将其作为普通的KV存储引擎来使用，mongodb的每个集合对应一个WT的table，table里包含多个Key-value pairs

性能

B树，buffer,文档（磁盘）
修改操作在持久化时在新页中，不会对旧页有影响，成块写入不需要二次写
比较占内存（一个连接一个线程，tcp连接500个就1G，引擎数据cache,新写数据，备节点差异buffer,长事务快照，夸多集合时的排序）

功能

K-V
单机AD WAL(journal)+checkpoint
CI 未提交事务快照，只有读用，写还是要最新的页

分布式

全量同步+oplog增量同步
主从同步：oplog 幂等（incr会转为set），循环覆盖，
顺序保证：写入 oplog前，会先加锁给 oplog 分配时间戳，并注册到未提交列表里，正式写入 oplog，在写完后，将对应的 oplog 从未提交列表里移除，在拉取 oplog 时若未提交列表为空，所有 oplog 都可读，否则只能到未提交列表最小值以前的 oplog
Secondary 拉取到一批 oplog 后，在重放这批 oplog 时，会加一个特殊的 Lock::ParallelBatchWriterMode 的锁，这个锁会阻塞所有的读请求，直到这批 oplog 重放完成

扩展性

存储/读写qps
集合分片：分片范围，hash，tag(机房)
hash可以预先分配多个。同一时刻抢锁之后又一个mongos会迁移。迁移期间原请求阻塞排队，返回给mongos重新请求

可靠性

复制集模式：故障检测恢复。成员间心跳，选举primary(Bully算法)。driver与复制集合心跳

一致性

路由（客户端，或mongos或单独的connfig server）
数据：oplog保证

第二部分 衍生数据的处理

原数据的存储介绍了工具，介质，结构等。实际上系统中还包括对源数据处理，比如缓存，计算。计算涉及到分布式要并行处理，流数据计算等。这一章节说下分布式下数据的处理

批处理

1.MPP

并行执行SQL。缺点:仅支持sql，倾向于内存中保存尽量多数据，最多分钟级别。分布式文件系统的map-reduce或其他优化计算方式，数据多样性，不仅关系或文档；查询不限于SQL（HIVE在此之上封装了SQL）；文件系统可以包含MPP风格的或OLTP如HBase

2.map/reduce

unix管道处理的思想，sort内存溢出放入磁盘,输入输出与逻辑分离/统一接口/可复用 =》map/reduce
输入输出为分布式上的文件HDFS

好处：数据网络传输和计算分离。永远数据完备后才执行mapper或reducer；重试，失败回滚都中间态存储。
针对数据倾斜，每次都要map数据+reduce逻辑处理有一些优化。比如
正常都在reduce连接。某些可以在mapper连接优化，比如大数据与小数据的链接，将小数据广播打到mapper内存，mapper和reduce分区相同时，mapper只需要单独单个分区。若分区本来有序，可以直接在可以在此完成reduce的工作
举例：mapper根据需要对文档集合分区，reducer创建该分区的索引，并将索引你文件写入分布式文件系统。增量索引写入新的段，并在后台压缩与合并。就不详细说了。

基于这种处理思想，整个批处理的构建系统hadoop:

hdfs是存储系统（见https://segmentfault.com/a/11...）
yarn是资源管理（见https://segmentfault.com/a/11...）
hadoop的高级该工具hive（见https://segmentfault.com/a/11...），可以自动组装多个mapreduce阶段
构建推荐系统等，在线使用，mapreduce入单独数据库。比如HBase（见：https://segmentfault.com/a/11...）

3.spark/flink

把整个工作流作为单个作业处理。替代map/reduce用算子，算子之间的连接可以有：记录重新分区排序/分区/广播连接。若中间态丢失，从先前中间态或原始数据重新计算。spark用弹性分布式数据集抽象跟踪数据的谱系，而flink对算子状态存档，允许在执行过程中你那个遇到错误的算子。许多不用排序的可以流水线方式执行。比如组合分区的map+reduce(groupby,sort等)作为一个subtask,另一个分区map+reduce(groupby,sort等)+reduce2（sink组合）为subtask2。1与2并行，2的reduce2等1。在map-reduce模式下是map1,map2并行，reduce分为很groupby1，groupby2,然后再map1,map2。再sort1,sort2。
Spark的技术理念是基于批来模拟流的计算。而Flink则完全相反，它采用的是基于流计算来模拟批计算。
详细见：由于批处理和流处理的整体划分思路（对分布式数据任务的拆分方式）是一样的。因此批处理和流处理的spark,flink写在一起了，详细见：spark(https://segmentfault.com/a/11...、flink(https://segmentfault.com/a/11...

流处理

对分布式数据的处理方法和上面一样，只说下流里边特别的

1.流处理的存储和传递

上述基于数据有界=》数据无界，增量处理。批处理输入是数据文件，需要考虑流处理的存储和传递？上述的分布式文件系统不再行：增量要轮询，轮询的越频繁，能返回新事件的请求比例就越低，而额外开销也就越高。 相比之下，最好能在新事件出现时直接通知消费者（数据库的触发器功能有限）=》

传递事件流——消息系统

设计点：费速度跟不上？丢弃，缓冲，背压。节点故障？
1.1 直接发送：UDP组播，ZeroMQ（https://segmentfault.com/a/11...）,HTTP或者RPC(webhooks,一种服务器的url被注册到另一个服务中)。容错能力有限
1.2 消息代理：负载均衡、扇出，并发确认重传
1）RabbitMQ,代理将单调消息分配给消费者，确认后删除(https://segmentfault.com/a/11...
2）基于日志的消息代理：使用日志消息存储。kafaka。每个分区有序，每个消息单调递增偏移量，要记录消费取的偏移量（https://segmentfault.com/a/11...）
适用于消息吞吐量高，处理迅速，顺序很重要（可以单分区全分能给某个负载均衡的线程）

数据与衍生数据的同步

数据库/缓存/索引/数据仓库
双写：
1.两个客户端两个系统相互覆盖=》版本向量检测并发写入；一个成功一个失败（原子）
2.选择一个为领导者，比如数据库，让其他系统作为追随者。

变更数据捕获，将其提取并替换为可以复制到其他系统中的形式的过程
事件溯源，事件仅追加。日志压缩仅保存最新版本。一般的删除都是使数据不能取回.可以连接数据库和衍生数据，使其作为主。
但是解决了覆盖但因为异步，还会有原子问题，使用分布式事务

时间与窗口

1.事件事件还是处理时间？
处理时间：处理有问题，重启后处理大量堆积的
事件时间：不知道1分钟内的最后到达会在几分钟后=》丢弃或发布更正
若要准确的事件时间（即事件在设备上发起时间，记录该时间，发往服务器时间，服务器收到时间），通过从第三个时间戳中减去第二个时间戳，可以估算设备时钟和服务器时钟之间的偏移(假
设网络延迟与所需的时间戳精度相比可忽略不计)。然后可以将该偏移应用于事件时间戳，
从而估计事件实际发生的真实时间(假设设备时钟偏移在事件发生时与送往服务器之间没有
变化)
2.窗口
滚动窗口，按分钟，每个事件仅属于一个窗口。跳动窗口，有重叠固定。滑动窗口，5分钟内任意时间开始。会话窗口，无会话关闭
容错
无法等待任务完成后根据输出错误处理=》微批量spark，存档点flink
详细见spark(https://segmentfault.com/a/11...、flink(https://segmentfault.com/a/11...

应用

天级别离线统计。kafaka=>hive 自行查询出报表
分钟级别。kafaka=>hive/mapreduce或直接入HBASE
实时简单搜索

kafka=>ES（ES算是数据或衍生数据的主要提供索引外加一些聚合，单独篇章详见：https://segmentfault.com/a/11...）
woator: kafaka=>spark/flink=>实时监控+预测模型
odin监控采集：采集，tsdb,druid。