从数据谈起存储/计算/分布式

第一部分 数据的存储

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

性能

存储介质特点数据组织
磁带
内存 map,set,list,skip-list,memory-table,stm(支持内存事务)
磁盘顺序读写强,随机读写差,block-Tress =>B+ 层数一样,性能稳定,中间节点只有索引,容易缓存,数据只在子节点,数据可以扫描
SSD随机性能高,并行度高,擦除影响寿命SST(sst为何适合SSD)
PCM

数据组织

  • 模型
    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。

相关推荐