BigTable没有Schema用户需要自定义
数据的下标是行和列的名字
BigTable是一个稀疏的分布式的持久化存储的多维序列Map，Map(row:string, column:string,time:int64)
行：同一行关键字的读或者写都是原子的
列族：列关键字组成的集合叫做“列族”，列族在使用之前必须先创建，然后才能在列族中任何的列关键字下存放数据，一张表的列族不能太多（最多几百个）
时间戳：在BigTable中每一个数据项都可以包含同一份数据的不同版本，BigTable时间戳类型为64位整形精确到毫秒，有参数可以设置，只保存最后n个版本的数据
BigTable支持单行事物处理，目前不支持通用的跨行事物处理
BigTable内部存储的数据文件是Google SSTable格式的，SSTable是一个持久化排序的，不可更改的Map结构，Map是由K，V组成并且都是任意的Byte串，通常每个块大小是64KB，大小可配置
SSTable定位数据块：

打开SSTable的时候，索引被加载到内存
每次查找都可以通过一次磁盘搜多完成(首先使用二分查找方法在内存中的索引里找到数据块的位置，然后再从硬盘读取的相应的数据块)


BigTable依赖一个高可用的序列化的分布式锁服务组件叫做Chubby，Chubby由5个活跃副本，其中一个为Master，当有副本失效时使用Paxos算法来保证副本的一致性
BigTable使用Chubby完成以下几个任务

确保在任何给定的时间内最多只有一个活动的Master副本
存储BigTable数据的有引导指令的位置
查找Tablet服务器，以及在Tablet服务器失效时进行善后
存储BigTable模式信息（每张表的列族信息）
以及存储访问控制列表

1.一个行可以分成多个tablet（应该是一个tablet包含了相关的多个行记录），Tablet是数据分布和负载均衡调整的最小单位。这样做的结果是，当操作只读取行中很少几
列的数据时效率很高，通常只需要很少几次机器间的通信即可完成。
2.列关键字组成的集合叫做“列族“，列族是访问控制的基本单位。一张表中的列族不能太多（最多几百个），并且列族在运行期间很少改变。与之相对应的，一
张表可以有无限多个列。
3.BigTable内部存储数据的文件是Google SSTable格式的。SSTable是一个持久化的、排序的、不可更改的
Map结构，而Map是一个key-value映射的数据结构，key和value的值都是任意的Byte串。可以对
SSTable进行如下的操作：查询与一个key值相关的value，或者遍历某个key值范围内的所有的keyvalue对。也就是sstable可以进行range 操作？
4.相较于mysql，bigtable可以让用户定制一些数据存储和分布方式，从而提高性能。

问题场景
有两个RDD的数据集A和B（暂且分别称为新、老RDD）以及一组关于这两个RDD数据的映射关系，如下图所示：


以及A和B的各元素映射关系的RDD，如下图所示：



上述映射关系，代表元素a和c同义，若为url，则表示指向同一个页面，元素b和d同理。
以第一列所组成的元素作为关键字，第二列作为值的集合。现要求映射对，使得在该映射关系下，B的值集合可以覆盖A的值几何的元素。如上结果应该为：（b, d）。因为A中以b为键的集合为B中以d为键的值集合的子集。

受到单机编程的思维定势，使用HashMap实现，虽然可以运行，但是太慢啦啦，所以改用另一种思路，可以充分利用分布式的优点。
解决方案
val data = sc.textFile("/user/wuzhongqiang/clean_data/baidubaike_source.20180801/").cache()
//1.以左边的为key，进行分组，统计每一个key所对应的值集合
val groupData = data.map(item => {
    val key = item._1 
    val value = item._1
    (key, value)
}).groupByKey

//2. 读取链接映射文件至map
//(AKey, BKey) 
val projectionMap = sc.textFile("hdfs://projection").cache()
// (AKey, BKey) 
val aData = projectionMap.map(item => (item._1, item._2))
// (BKey, AKey) 
val bData = projectionMap.map(item => (item._2, item._1))
// (AKey, (BKey, AValueSet)) 
val aKeyJoinData = aData.join(groupData)
// (BKey, (AKey, BValueSet)) 
var bKeyJoinData = bData.join(groupData)
// 交换新老键的位置，为后面的join做准备 (AKey, (BKey, BValueSet) )
bKeyJoinData = nbKeyJoinData.map(item => {(item._2._1, (item._1, item._2._2))})
//结果形式为(AKey, ((BKey, AValueSet), (BKey, BValueSet)))
val aBData = aKeyJoinData.join(bKeyJoinData)
aKeyJoinData.take(1).foreach(println)
// oldUrl -> newUrl
val resultMap = aBData.map(item => {
    val aValueSet = item._2._1._2.to[Set]
    val bValueAttrSet = item._2._2._2.to[Set]
    val subtractSet = aValueSet -- bValueAttrSet
    //若新的URL属性可以完全覆盖旧的url属性， 即 oldAttrSet与newAttrSet的差集为空
    if(subtractSet.isEmpty)
    	(item._1, item._2._1._1)
    else ("", "")
}).filter(_._1 != "")
resultMap.take(1).foreach(println)

《桶排序 》中我们能够看到，数据值的范围越大，可能需要桶的个数也就越多，空间代价也就越高。对于上亿单位的关键字，桶排序是很不实用的。基数排序是对桶排序的一种改进，这种改进是让“桶排序”适合于更大的元素值集合的情况，而不是提高性能。

 

多关键字排序问题(类似于字典序)：

 

我们先看看扑克牌的例子。一张牌有两个关键字组成：花色(桃<心<梅<方)+面值(2<3<4<...<A)。假如一张牌的大小首先被花色决定，同花色的牌有数字决定的话。我们就有两种算法来解决这个问题。

 

(1) 首先按照花色对所有牌进行稳定排序，这样就可以将所有牌分成4组。然后同组的牌(同花色)再按照面值进行排序。

(2) 首先按照面值对所有牌进行稳定排序，然后按照花色再次对所有牌进行稳定排序。

 

显然，第一种方法需要将序列分割成几个子序列。而第二种方法则完全不需要。因此我们采用从次关键字排序开始的方法。




基数排序

 

上面的问题是多关键字的排序，但单关键字也仍然可以使用这种方式。

比如字符串“abcd” “aesc” "dwsc" "rews"就可以把每个字符看成一个关键字。另外还有整数 425、321、235、432也可以每个位上的数字为一个关键字。

 

基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列：

                 278、109、063、930、589、184、505、269、008、083

我们将每个数值的个位，十位，百位分成三个关键字： 278 -> k1(个位)=8  ，k2(十位)=7 ，k3=(百位)=2。

然后从最低位个位开始(从最次关键字开始)，对所有数据的k1关键字进行桶分配(因为，每个数字都是 0-9的，因此桶大小为10)，再依次输出桶中的数据得到下面的序列。

                       930、063、083、184、505、278、008、109、589、269

再对上面的序列接着进行针对k2的桶分配，输出序列为：

                       505、008、109、930、063、269、278、083、184、589

最后针对k3的桶分配，输出序列为：

                       008、063、083、109、184、269、278、505、589、930

 

性能分析

 

很明显，基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度，而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2N) ，当然d要远远小于N，因此基本上还是线性级别的。基数排序的空间复杂度为O(N+M)，其中M为桶的数量。一般来说N>>M，因此额外空间需要大概N个左右。

 

但是，对比桶排序，基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作，而桶排序在桶相对较少的情况下，桶内多个数据必须进行基于比较操作的排序。因此，在实际应用中，基数排序的应用范围更加广泛。