大数据日知录

 

第一章 数据的分片与路由

分片包括二个映射:

1.key-partition映射，将数据记录映射到数据分片空间中，一般是多对一的映射即一个数据分片包含多条记录

2.partition-macheine映射，将数据分片映射到物理机器中，也是多对一映射，即一台物理机器容纳多个数据分片

 

哈希分片(hash partition)

1.Round Robin

    H(key) = hash(key) mod (K+1)     K为当前机器数量，新增一台物理机器就是K+1

    RoundRobin算法在增加一台机器后整个结果都变了

2.虚拟桶(Virtual Buckets)

    Membase(现更名为Couchbase)使用的算法

3.一致性hash(Consistent Hashing)

    如memcached使用的一致性hash算法

范围分片(Range Partition)

    将所有记录的主键先排序，然后在排好序的主键记录空间里将记录划分成数据分片，每个数据分片存储有序的主键空间片段内的所有记录。现实实现中使用一个数据分片映射表，记录表每一项记载数据分片的最小主键及其对应的物理主机地址

    也就是需要一个元记录表，记录最终记录所在机器的位置，比如HBase的meta表

memcache一致性hash算法介绍

 

 

 

 

 

第二章 数据复制与一致性

CAP

一致性(Consistency)在分布式系统中的同一数据多副本情形下，对于数据的更新操作提现处的效果与只有

                                 单份数据是一样的

可用性(Availability) 客户端在任何时刻对大规模数据系统的读/写操作都应该保证在限定的时间内完成

分区容忍性(Partition Tolerance)  在大规模分布式数据系统中，网络分区现象，即分区间的机器无法进行

                              网络通讯的情况是必然会发生的，所以系统应该能够在这种情况下继续工作

对于分布式系统来说P 是一定要满足的，所以在CAP三者不能兼顾的情况下，要不选择AP，要不选择CP

 

ACID原则

原子性(Atomicity) 一个事务要么全部执行，要么全部不执行

一致性(Consistency) 事务在开始和结束时，应该始终满足一致性约束条件，比如系统要求A+B=100，那么

                                 事务如果改变了A的数值，则B的数值也要相应的修改来满足这种一致性要求

事务独立(Isolationi) 如果有多个事务同时执行，彼此之间不需要知晓对方的存在，而且执行时相互不影响，

                               不允许出现两个事务交错，间隔执行部分任务的情况，也即事务之间需要序列化执行

持久性(Durability) 事务运行成功以后，对系统状态的更新是永久的，不会无缘无故的回滚撤销

 

BASE原则

基本可用(Basically Available)在绝大多数时间内系统处于可用状态，允许偶尔的失败，所以称基本可用

软状态或者柔性状态(Soft State)是指数据状态不要求在任意时刻都完全保持同步，到目前为止软状态并

                                                  无一个统一明晰的定义，即处于有状态和无状态之间

最终一致性(Eventual Consistency)在给定时间窗口内数据会达到一致状态

 

一致性模型

1.强一致性

2.最终一致性

3.因果一致性

4.读你所读一致性

5.会话一致性

6.单调读一致性

7.单调写一致性

 

副本更新策略

1.同时更新(通过一致性协议来更新)

2.主从更新(同步，异步更新，混合更新)

3.任意节点更新(同步，异步)

 

一致性协议

两阶段提交(Two-Phrase Commit 2PC)

 

向量时钟

RWN协议

N表示在分布式系统中有多少个备份数据

W表示一次成功的更新操作至少要有W份数据写入成功

R表示一次成功的读取数据要求至少有R份数据成功读取

如果满足    R + W > N       则可称为满足 数据一致性协议

 

Paxos一致协议

Raft协议

 

详细解析Dynamo存储引擎

向量时钟

事务和两阶段提交

关于分布式事务、两阶段提交、一阶段提交、Best Efforts 1PC模式和事务补偿机制的研究

Paxos百科

Paxos算法细节详解(一)--通过现实世界描述算法

分布式一致性Paxos算法学习笔记（一）：paxos大杂烩

分布式系统的Raft算法

Raft一致性算法

 

 

 

 

 

第三章 大数据常用的算法与数据结构

布隆过滤器(Bloom Filter)

使用一个N个函数，对指定要查找的key执行函数 fun1(key)如果落到了数组的某一位上就将这位设置为1

所以指定了三个函数之后会有三个bit被设置为1

bloom filter会误判但不会漏判，而且存在一定的误判率，和数组大小，函数个数都有关系

bloom filter只能用于数据添加操作，数据删除就不行了，因为一个bit只能表示有和无不能再有其他状态了。解决办法是用多个bit来表示一个状态

这个就是计数BF(Counting Bloom Filter)

布隆过滤器在Chrome的URL判断，比特币历史交易，hbase，cassandra中都有使用

布隆过滤器百科

 

SkipList

在插入，删除，查找数据时都能保证O(long(N))时间复杂度，hbase和levelDB都使用了跳表

本质上是一个链表结构，但是每个每个节点可能都有N个指向后面的节点，即一个节点有多个后续，而节点包含多少个后续是随机产生的。

最下面那层包含所有的数据，倒数第二层的数据节点个数就少一些，层数越往上节点数就越少

查找的时候首先从第一层开始，再依次往下

SkipList跳表的基本原理

 

LSM树

首先将数据写到预写日志中，然后将写的数据先放到内存中这样就可以保证以后的随机读了，如果内存中的数据到一定大小后，就将数据flush到磁盘上。从整个结构上来说就像一颗树，整体是字典排序有序的。

一个节点下可能会被flush了一个或多个文件，如果定位到某个节点(就类似HBase中的region)那么就需要遍历下面的所有文件(也就是HFile)才能读取到对应的值了，这个读取的可以使用布隆过滤器优化提高速度。

本质上来说就像region一样，一开始可能很少，后来越来越多，region按照key顺序排序，其实只有三层的树，root表-->meta表-->业务表

然后region不断变多，但是region下面的HFile数量还是1个到7个(默认最多7个)，当达到HFile达到一定数量后就会合并，这样就减少region下面的HFile提高读性能。

LSM树由来、设计思想以及应用到HBase的索引

LSM树 VS B+树

 

Merkle Hash Tree

每个节点和其所有子节点都会计算一次hash，这样如果比较根节点的hash有变化了，则会依次找寻到变化的子节点，最后找到最终的变化数据

被广泛运用于分布式领域，主要用来在海量数据下快速定位少量变化的数据内容(变化原因可能是损毁，篡改或者正常变化等)

如P2P下载系统BitTorrent，Git等工具，比特币以及Dynamo，Riak，Cassandra等

Dynamo中结合Merkle树和Gossip协议，假设A和B存储了相同的数据副本。此时两个节点都对两者所存储数据的共同键值范围(Key Range)部分建立Merkle树。之后可以比较两个节点的Merkle树节点hash值来查找不同部分，首先比较根节点再比较所有叶子节点。Gossip协议在上述过程中起的作用是：两个节点在交换Merkle树节点内容以及同步数据内容时可通过这个协议来进行

比特币通过Merkle树来验证交易的历史数据。

Merkle Hash Tree

Merkle Tree算法详解

 

Snappy与LZSS算法

LZSS是LZ77的一种，LZ77是一种动态词典编码(dictionary coding)

词典编码的意思是：文本中的词用它在词典中表示位置的号码代替无损数据压缩方法，一般分为静态词典和动态词典。

静态词典需要事先构造，采用动态词典时编码器将被压缩的文本中自动导出词典，解码器解码时边解码边构造词典。 

 

LZ77采用滑动窗口和前向缓冲区

新读入的字节放到滑动窗口中(也是处理过的字节)，如果前向缓冲区(也就是未处理的部分)和滑动窗口中数据有匹配，则记录一个标号，类似三元数组<指针，长度，后续字符>，如(3,2)表示从开头第三个字节开始匹配两个

一个常用的技巧是：将滑动窗口内字符串的各种长度片段存入哈希表，哈希表的值记载在滑动窗口的出现位置

Snappy则做了一些优化，设置了最少长度为4，也就是说必须至少匹配4个字符串才进行压缩处理。同时设定hash表内的字符串片段固定长度为4。此外Snappy将数据切割成32K大小，数据块之间无关联。

LZ77压缩算法

LZ77 算法的基本流程

snappy百科

 

Cuckoo Hashing

传统hash只使用一个hash函数，cuckoo同时使用两个不同的hash函数H1(x)和H2(x)

如果计算出H1(x)和H2(x)任意一个不为空就可以插入，如果两者都不为空则选择一个桶将已有的值y踢出去，由x来插入相应的位置。y的值重复上述步骤计算一个新的值如果再由冲突，则踢掉z插入y继续执行。这样可能导致无限循环所以需要设定一个最大替换次数，如果到了最大替换次数需要更换hash函数或者增加hash空间中桶的数量

Cuckoo hashing算法分析

 

 

 

 

 

第四章 集群资源管理与调度

采用独立的资源管理与调度系统而非静态划分资源有如下好处

1.集群整体资源利用率高，所有的资源统一管理与调度，可以根据不同计算任务的即时需要动态分配资源

2.可增加数据共享能力，对于有些共享的数据资源，需要分别在分配给不同计算任务的子集群中重复存储

3.支持多类型计算框架和多版本计算框架

 

调度系统设计的基本问题

1.资源异质性与工作负载异质性

2.数据局部性(从性能角度尽量选择A，再是B)

    A节点局部性

    B机架局部性

    C全局局部性

3.抢占式调度和非抢占式调度

4.资源分配粒度

5.饿死与死锁(如果不断出现高优先级任务，低优先级的可能出现饿死)

6.资源隔离

 

三种资源管理与调度系统范型

1.集中式调度器(Monolithic Scheduler)

2.两级调度器(Two-Level Scheduler)

3.状态共享调度器(Shared-State Scheduler)

 

资源调度策略

1.FIFO调度侧路了

2.公平调度策略

3.能力调度器

4.延迟调度器(提交任务延迟执行，等到数据尽可能局部化后再执行)

5.主资源公平调度策略

Mesos

YARN(Yet Another Resource Negotiator)另一个资源调度器

统一资源管理与调度平台（系统）介绍

YARN百科

Apache Mesos总体架构 

 

 

 

 

 

第五章 分布式协调系统

跟分布式协调系统相关的问题

1.当主控服务器发生故障时，为了使系统不至瘫痪，如何能够快速从备份机中选出新的主控服务器

2.当分布式系统负载过高时，可以动态加入新机器通过水平扩展来进行负载均衡，此时分布式系统如何自动

   探测到有一台新机器加入进来？如何自动向其分配任务？

3.如何在分布式环境下实现锁服务？

4.如何在多个进程或者机器之间实现任务同步，比如所有进程同时在某个时间点开始或者结束？

5.如何判断集群中某台机器是否依然存活？

6.如何快速构建生产者-消费者消息队列？

 

Chubby锁服务

google发开的分布式协调系统，基于Paxos协议，做了一些改进

 

Zookeeper

Yahoo开发的分布式协调系统

和Chubby不同，Zookeeper的从节点可以接收读请求，主节点负责更新请求。这样整体吞吐量会很高

使用了改进的Paxos协议ZAB协议

如果主节点来没来得及更新，读取从节点就可以读到旧数据，Zookeeper提供了sync命令，强制从主节点获取状态同步信息，这样就不会读到旧数据了

采用类似UNIX的目录结构

Zookeeper的典型应用场景

1.领导者选举(leader election)

2.配置管理(Configuration Management)

3.组成员管理(Group Membership)

4.任务分配

5.锁管理(Locks)

6.双向路障同步(Double Barrier)

 

使用Zookeeper的开源系统

1.HBase

2.Storm

3.Mesos

4.Pub-Sub(Yahoo)

5.SolrCloud

6.Kafka

 

 

 

 

 

第六章 分布式通讯

序列化与RPC框架

1.Protocol Buffer    如果追求序列化的高效但不适用RPC可选择

2.Thrift                    如果需要内奸的便捷RPC支持可以选择

3.Avro                     如果需要和动态语言方便的继承可选择

消息队列Kafka

应用层多播通讯(Application-Level Multi-Broadcast)  Gossip协议

也被称为感染协议(Epidemic Protocol)

Dynamo和它的模仿者Cassandra，Riak等系统使用Gossip来进行估值检测，集群成员管理或副本修复

P2P下载系统BitTorrent使用Gossip在节点之间交换信息

Gossip包含三种

1.全部通知模型(Best Effort或Direct Mail)

    当某个节点有更新消息，则立即通知所有其他节点，这种传播方式简单但是容错性不好

2.反熵模型(Anti-Entropy)

    节点P随机选择另外一个节点Q然后与Q交换更新信息

    A)Push模式，P将更新信息退给Q，Q判断是否比本地信息要新，如果是则更新本地消息

    B)Pull模式，P从Q获取信息，如果比P本地信息要新，则P更新本地信息

    C)Push-Pull模式，P和Q同时进行push和pull操作，即两者同时互相通知对方更新

    Push推送给的节点可能已经更新过了，所以越往后效率越差，pull是主动拉的所以越往后效果越好

    效果来说 Push-Pull > Pull > Push

3.散布谣言模型(Rumor Mongering)

    增加了传播停止判断，如果节点Q已被其他节点通知更新了，那么节点P增加其不再主动通知其他节点的概率

 

 

 

 

 

第七章 数据通道

一般Log数据收集系统的设计关注如下点

1.低延迟

2.可扩展性

3.容错性

Chukwa (包括数据收集和数据分析，但是过于依赖MR，而且设计定位不够清晰未来发展堪忧)

Scribe

 

数据总线的作用是能够形成数据变化通知通道，当集中存储的数据源(往往是关系型数据库)的数据发生变化时，能尽快通知对数据变化敏感的相关应用或者系统构件。

设计数据总线系统要关注以下三点

1.近实时性

2.数据回溯能力

3.主题订阅能力

Databus

Wormhole

 

数据导入/导出，将HDFS中的数据导入导出到关系数据库中

sqoop专门用于在hadoop和其他关系数据库或nosql之间进行相互数据导入导出的工具

 

 

 

 

 

第八章 分布式文件系统

google文件系统GFS

colossus 谷歌下一代文件系统

HDFS

HayStack

 

文件存储布局

1.行式存储

2.列式存储(Dremel)

3.混合式存储(RCFile，ORCFile，Parquet)

 

纠删码(Erasure Code)

对于冷备的数据没有必须再存三份，通过纠删码只需保留一份

纠删码通过对原始数据进行校验并保留，以增加冗余的方式来保证数据的可恢复性。

极大距离可分码(Maximum Distance Separable codes MDS)是一种非常常用的纠删码，其将数据文件切割为等长的n个数据块，并根据这n个数据块生成m个冗余的校验信息，这样使得n+m块数据中即使任意m块数据丢失，也可以通过剩下的n块数据对m块损失的数据进行重构，以此来完成容错功能

Reed-Solomon纠删码

LRC编码，RS编码虽然是最优的，但是如果10个块中损坏了一个就需要从其他9个块中拷贝数据恢复。在分布式环境中恢复需要大量的网络数据拷贝，LRC编码就是为了解决这种数据恢复时导致的大量网络传输造成的网络阻塞问题

 

 

 

 

 

第九章 内存KV数据库

对于内存级数据库来说，有两种选择

1.忽略成本提高可用性，与外存一样在内存中对数据进行备份如常用的3备份策略，提高可用性，同时提高

    并发读性能

2.降低成本，内存只保留一份，数据备份放在磁盘或者SSD中，但是可用性会有问题

RAMCloud使用第二种策略

Redis和Membase(现更名为CouchBase)使用第一种策略

 

 

 

 

 

第十章 列式数据库

BigTable

PNUTS存储系统

MegaStore

Spanner