1 如何调优

　　1.抽样检测分组字段，看看是否有倾斜

　　2.如果没有倾斜，就正常增加reduce数量，设置中间ORC+SNAPPY压缩

　　3.如果有倾斜，把倾斜的部分过滤出来加前缀打散处理，不倾斜的部分正常处理。

　　4.如果是大表join小表，大表倾斜，可以使用map端join方法，小表倾斜直接无视。

　　5.如果是大表join大表，某表倾斜，可以使用膨胀法处理。

　　2 实时排序

　　跳表法快速排序

　　将值域划分区间建有序链表，原本海量的遍历会被压缩N倍。每个值域对应一个有序链表，因此是双重链表。

　　前提：除了跳表外还有一张作品表，以作品id为key，value含分数

　　值变更时，先查询作品表更新原值，通过原值到对应区间的链表中删除该值，新值插入对应区间的链表中。

　　求排名：1.每个区间链表除了保存作品和分数外，还额外维护一个区间总长

　　2.每次新值插入时，都将原区间总长-1，新区间总长+1

　　3.求排名时遍历第一层链表将区间总长累加，然后遍历该值所在的区间求出区间内排名，两者相加。

　　求TopN:第二层链表一路往下走N个。

　　缺点：事实上所有针对数据直接排序的方式都存在锁问题，每次更新只能有一个线程做，否则必然会乱。

　　平衡二叉树排序

　　假设总分为5 [0,5]

　　1.将总分一分为二 [0,2],[3,5]

　　2.将划分的部分继续二分 [0,1],[1,2],[3,4],[4,5]

　　3.重复2直到划分到底 [0,0],[1,1],[2,2],[3,3]...

　　采用链表的方式从顶点往下一路关联起来，每个区间key对应一个人数value。

　　假设有某个值从2变成3。

　　先从顶点开始往下遍历查找[2,2]，遍历过程中经过的节点人数全部-1，终点[2,2]的人数也-1;

　　然后从顶点开始往下遍历查找[3,3]，经过的节点人数全部+1。终点也+1。

　　求排名：假设要求分数为3的排名，从起点开始往下查找[3,3]，如果是往左走，就把右值累加上，如果往右走则不加。

　　优点：毫秒级响应排名，更新不需要锁表，因为是单纯的加减日志。

　　缺点：消耗大量内存存储，每次更新都要改变N个值，每次更新值时还需要把排名添加到TopN表里。

　　3 求交集

　　理论：

　　如果是k-v形式的数据，或者是可以提取key的数据，可以使用分组法比较。

　　假设我有x G内存，要求A,B的交集。

　　先把A,B分别分组拆分成多个小文件，每个小文件的大小为(x-300)/2，超过的部分再水平拆分成多个文件。

　　然后按分组读入A,B的数据，在内存中比较，求出交集部分。

　　如果分组太细，就按分组key的哈希进行分区，一次比较多个分组。

　　为了方便小文件的合并，可以在输出时将数据排序输出，创建索引文件，后续可以采用归并排序的方式快速合并。

　　如果不能提取key，则按照hash分组。

　　实战：假设已经把两张表要求交集的部分字段拼接成"key"

　　select * from A join B on A.key = B.key

　　4 求差集

　　select * from A full outer join B on A.key = B.key where A.key is null or B.key is null;

上一篇

重定向和文件描述符

下一篇

算法题---有效的数独