大数据

大数据开发知识点-1

大数据开发知识点-1

数据倾斜

定义：

数据倾斜在MapReduce编程模型中十分常见,用最通俗易懂的话来说,数据倾斜无非就是大量的相同key被partition分配到一个分区里,造成了’一个人累死,其他人闲死’的情况,这种情况是我们不能接受的,这也违背了并行计算的初衷,首先一个节点要承受着巨大的压力,而其他节点计算完毕后要一直等待这个忙碌的节点,也拖累了整体的计算时间,可以说效率是十分低下的。

原理以及现象分析：

出现数据倾斜的原因，基本只可能是因为发生了shuffle操作，在shuffle的过程中，出现了数据倾斜的问题。因为某个，或者某些key对应的数据，远远的高于其他的key。你在自己的程序里面找找，哪些地方用了会产生shuffle的算子，groupByKey、countByKey、reduceByKey、join。看log一般会报是在你的哪一行代码，导致了OOM异常；或者呢，看log，看看是执行到了第几个stage！！！

###解决思路：

  1. 对包含少数几个数据量过大的key的那个RDD，通过sample算子采样出一份样本来，然后统计一下每个key的数量，计算出来数据量最大的是哪几个key。
  2. 然后将这几个key对应的数据从原来的RDD中拆分出来，形成一个单独的RDD，并给每个key都打上n以内的随机数作为前缀，而不会导致倾斜的大部分key形成另外一个RDD。

接着将需要join的另一个RDD，也过滤出来那几个倾斜key对应的数据并形成一个单独的RDD，将每条数据膨胀成n条数据，这n条数据都按顺序附加一个0~n的前缀，不会导致倾斜的大部分key也形成另外一个RDD。
再将附加了随机前缀的独立RDD与另一个膨胀n倍的独立RDD进行join，此时就可以将原先相同的key打散成n份，分散到多个task中去进行join了。
而另外两个普通的RDD就照常join即可。
最后将两次join的结果使用union算子合并起来即可，就是最终的join结果。

Hbase实现快速查询的原因

快速查询:

  1. 分区储存
    HBase将每个表划分为多个region，每个region用rowkey来划分，数据的查询也是通过rowkey来查询
    查询过程：client向HBase依赖的zookeeper获取metaregion的位置，然后通过metaregion中的记录获取到所要查询的rowkey
    对应的region，这样就确定到一个region范围
  2. HFile的索引
    HFile是HBase最底层数据文件的存储格式，一个region下包含着多个HFile，每个HFile的最后有末尾固定的长度来存储索引，这样可以快速确认你所查询的数据是否在这个HFile中
  3. BloomFilter
    BloomFilter是针对HFile的，每一条存储的数据，BloomFilter将记录hash进固定的数组中，这样在查询时对应Hash数组，如果对应位置被改变了，那么所要查的记录可能在这个文件里。如果没有被改变，那么肯定不在，这样可以大幅提高查询的效率

实时查询：

实时查询，可以认为是从内存中查询，一般响应时间在1秒内。HBase的机制是数据先写入到内存中，当数据量达到一定的量（如128M）， 再写入磁盘中， 在内存中，是不进行数据的更新或合并操作的，只增加数据，这使得用户的写操作只要进入内存中就可以立即返回，保证了HBase I/O的 高性能。

实时查询，即反应根据当前时间的数据，可以认为这些数据始终是在内存的，保证了数据的实时响应。

像RDBMS这让的关系型数据库，按行存储，通过严格的ACID事务来进行同步，这造成了系统的可用性和伸缩性方面的大大折扣
HBase，Casandra是NOSQL的数据库或者说no relation，按列存储，是最终一致性的系统，他们为了高的可用性牺牲了一部分的一致性，向HBase就不支持事务特性。

不同点：

  1. 存储模式：HBase是基于列存储的，每个列族都有几个HFile保存，不同列族的文件是分离的，关系型数据库则是基于表格结构和行模式保存的
  2. 数据操作：HBase只有最简单的CRUD操作，表与表之间是相互分离的，没有关系型数据库中的那些连接操作
  3. 数据类型：HBase只有简单的字符类型，所有的类型都是交由用户自己处理，他只保存字符串。而关系性数据库则有丰富的类型和存储方式
  4. 数据维护：HBase是基于HDFS的，所以真实的更新操作是通过新增新纪录外加时间戳来实现的
  5. 可伸缩性：HBase这类分布式数据库就是为了这个目的开发出来的，他可以轻松的增加或减少硬件的数量，对错误的兼容性比较高

Zookeeper的实现原理

ZooKeeper 是一个开源的分布式协调服务，分布式应用程序可以基于 ZooKeeper 实现诸如数据发布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master 选举、分布式锁和分布式队列等功能。

集群角色

  • Leader 负责进行投票的发起和决议，更新系统状态
  • Follower 追随者用于接受客户端请求并向客户端返回结果，在选主过程中参与投票
  • Observer 可以接受客户端连接，将写请求转发给leader，但observer不参加投票过程，只同步leader的状态，observer的目的是为了扩展系统，提高读取速度
  • client，请求发起

一个ZooKeeper集群同一时刻只会有一个Leader，其他都是Follower或Observer。Zookeeper的核心是原子广播，这个机制保证了各个Server之间的同步。实现这个机制的协议叫做Zab协议。Zab协议有两种模式，它们分别是恢复模式（选主）和广播模式（同步）。当服务启动或者在领导者崩溃后，Zab就进入了恢复模式，当领导者被选举出来，且大多数Server完成了和leader的状态同步以后，恢复模式就结束了。状态同步保证了leader和Server具有相同的系统状态。

为了保证事务的顺序一致性，zookeeper采用了递增的事务id号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了zxid。实现中zxid是一个64位的数字，它高32位是epoch用来标识leader关系是否改变，每次一个leader被选出来，它都会有一个的epoch，标识当前属于那个leader的统治时期。低32位用于递增计数。

每个Server在工作过程中有三种状态：

  • LOOKING：当前Server不知道leader是谁，正在搜寻
  • LEADING：当前Server即为选举出来的leader
  • FOLLOWING：leader已经选举出来，当前Server与之同步

重要概念

会话(Session)

Session 是指客户端会话，在讲解客户端会话之前，我们先来了解下客户端连接。在 ZooKeeper 中，一个客户端连接是指客户端和 ZooKeeper 服务器之间的TCP长连接。

数据节点(ZNode)

谈到分布式的时候，一般『节点』指的是组成集群的每一台机器。而ZooKeeper 中的数据节点是指数据模型中的数据单元，称为 ZNode。ZooKeeper 将所有数据存储在内存中，数据模型是一棵树（ZNode Tree），由斜杠（/）进行分割的路径，就是一个ZNode，如 /hbase/master，其中 hbase 和 master 都是 ZNode。每个 ZNode 上都会保存自己的数据内容，同时会保存一系列属性信息。

在 ZooKeeper 中，ZNode 可以分为持久节点和临时节点两类。

  • 持久节点

所谓持久节点是指一旦这个 ZNode 被创建了，除非主动进行 ZNode 的移除操作，否则这个 ZNode 将一直保存在 ZooKeeper 上。

  • 临时节点

临时节点的生命周期跟客户端会话绑定，一旦客户端会话失效，那么这个客户端创建的所有临时节点都会被移除。

另外，ZooKeeper 还允许用户为每个节点添加一个特殊的属性：SEQUENTIAL。一旦节点被标记上这个属性，那么在这个节点被创建的时候，ZooKeeper 就会自动在其节点后面追加上一个整型数字，这个整型数字是一个由父节点维护的自增数字。

Zookeeper 的读写机制

  • Zookeeper是一个由多个server组成的集群
  • 一个leader，多个follower
  • 每个server保存一份数据副本
  • 全局数据一致
  • 分布式读写
  • 更新请求转发，由leader实施

Zookeeper 的保证

  • 更新请求顺序进行，来自同一个client的更新请求按其发送顺序依次执行
  • 数据更新原子性，一次数据更新要么成功，要么失败
  • 全局唯一数据视图，client无论连接到哪个server，数据视图都是一致的
  • 实时性，在一定事件范围内，client能读到最新数据

数据一致性算法 – Paxos

节点角色

Paxos 协议中，有三类节点:

  • Proposer:提案者

Proposer 可以有多个，Proposer 提出议案(value)。所谓 value，在工程中可以是任何操作，例如“修改某个变量的值为某个值”、“设置当前 primary 为某个节点”等等。Paxos 协议中统一将这些操作抽象为 value。
不同的 Proposer 可以提出不同的甚至矛盾的 value，例如某个 Proposer 提议“将变量 X 设置为 1”，另一个 Proposer 提议“将变量 X 设置为 2”，但对同一轮 Paxos 过程，最多只有一个 value 被批准。

  • Acceptor:批准者

Acceptor 有 N 个，Proposer 提出的 value 必须获得超过半数(N/2+1)的
Acceptor 批准后才能通过。Acceptor 之间完全对等独立。

  • Learner:学习者

Learner 学习被批准的 value。所谓学习就是通过读取各个 Proposer 对 value 的选择结果，如果某个 value 被超过半数 Proposer 通过，则 Learner 学习到了这个 value。

这里类似 Quorum 议会机制，某个 value 需要获得 W=N/2 + 1 的 Acceptor 批准，Learner 需要至少读取 N/2+1 个 Accpetor，至多读取 N 个 Acceptor 的结果后，能学习到一个通过的 value。

约束条件

上述三类角色只是逻辑上的划分，实践中一个节点可以同时充当这三类角色。有些文章会添加一个Client角色，作为产生议题者，实际不参与选举过程。

Paxos中 proposer 和 acceptor 是算法的核心角色，paxos 描述的就是在一个由多个 proposer 和多个 acceptor 构成的系统中，如何让多个 acceptor 针对 proposer 提出的多种提案达成一致的过程，而 learner 只是“学习”最终被批准的提案。

Paxos协议流程还需要满足几个约束条件：

  • Acceptor必须接受它收到的第一个提案；
  • 如果一个提案的v值被大多数Acceptor接受过，那后续的所有被接受的提案中也必须包含v值（v值可以理解为提案的内容，提案由一个或多个v和提案编号组成）；
  • 如果某一轮 Paxos 协议批准了某个 value，则以后各轮 Paxos 只能批准这个value；

倒序排序

倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。

倒排索引有两种不同的反向索引形式：

  • 一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。
  • 一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。

后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。

通过上面的定义可以知道，一个倒排索引包含一个单词词典和一个倒排文件。其中单词词典包含了所有粒度的拆分词；倒排文件则保存了该词对应的所有相关信息。

倒序排序例子

Bitmap大数据去重

BitMap 基于位的映射。

bitmap算法思想

32位机器上，一个整形，比如int a; 在内存中占32bit位，可以用对应的32bit位对应十进制的0-31个数，bitmap算法利用这种思想处理大量数据的排序与查询。

优点：

  1. 运算效率高，不许进行比较和移位；
  2. 占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。

缺点：

所有的数据不能重复。即不可对重复的数据进行排序和查找。

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

public static void main(String[] args) {
        int [] array = new int [] {1,2,3,22,0,3};
        BitSet bitSet  = new BitSet(6);
        //将数组内容组bitmap
        for(int i=0;i<array.length;i++)
        {
            bitSet.set(array[i], true);
        }
       System.out.println(bitSet.size());
        System.out.println(bitSet.get(3));
    }

布隆过滤器

Bloom Filter是一种空间效率很高的随机数据结构，Bloom Filter可以看做是对bit-map的扩展。

原理如下：

当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个位阵列(Bit Array)中的K个点，把它们置为1，检索时我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了。

  1. 如果这些点有任何一个0，那么被检索元素一定不存在；

  2. 如果都是1，那么被检索元素可能存在；

布隆过滤器

使用场景

主要使用场景:用来检测某个元素是否是巨量数据集合中的成员，但识别结果存在误差；

识别场景：某个元素实际不存在，但是由于前面元素在进行多个Hash时，刚好对应位为1，那么会误认为其存在，但实际不存在。

如果某个成员确实属于集合，那么Bloom Filter一定能够给出正确的判断。