赛题官网： 阿里云第三届数据库大赛 - 性能挑战赛
今年的数据库比赛可谓异常激烈，原定 2021年07月02日 ~ 2021年08月06日 的复赛，因为主办方原因被延期至 2021-08-20，而前排的分数相差都在秒、半秒、甚至毫秒级，“卷”的程度可见一斑
一般这种限定Java语言的比赛，鄙人都是会义无反顾参与的，在享受比赛的期间，更可以提高自身技术，何乐而不为呢？国际惯例，先报下本次比赛成绩哈
| 赛段 | 排名 |
|---|---|
| 预热塞 | 3 |
| 第一赛季 | 2 |
| 第二赛季 | 6 |
| 决赛答辩 | 季军 |
季军的奖励是人民币1万块钱，决赛答辩环节也是激烈异常，文末附上决赛期间的一些图片
具体赛制规则大家可查看官网介绍
此处我简单描述下大规则
5月17日至8月20日，比赛历经3个月，可谓旷日持久
语言限定
赛题本身描述比较简洁，简言之就是给你一堆数，排序后返回第K大值
格式类似于：
复赛在初赛的基础上增加持久化和高并发要求
说明：因复赛是初赛的升级版，所以后续论述主要针对复赛展开，其中会掺杂一些初赛的历程
我们最终是需要将数据排序，并返回K大值的，但面对的源文件达74G，即便全部数据都用字节存储，也有30G之多，而评测机的内存只有8G，明显不可能将全部数据放入内存后再排序。那为了解决此问题，比较容易想到的一个点便是：多part快排，整体归并的思路
假定我们启动8个线程，每个线程一次读取4M的数据，那程序完全可以将4M的数据进行快排后落盘，等全部数据读取完毕后，我们便积累了多个但有序的数据块，然后再将这些数据块进行多线程归并排序
当数据全部有序后，莫说查询4000次，即便是查询4000万次，查询模块的性能也能达到最优；但此方案的劣势也相当明显，全量排序需要消耗大量的cpu，最终的瓶颈很有可能由IO转移到cpu排序上，经过小数据量的benchmark，该方案很快被摒弃
既然数据量巨大，我们为什么不采用分桶排序呢？将全量数据拆分成N个桶，每个桶内的数据都可以被直接加载至内存，一次性排序完毕（目标数据是30G，假定我们分1024桶的话，每个桶的数据量仅有30M左右）；当所有分桶数据都排序完成，那全量数据自然也是全量有序的了。但某个分桶内的数据只有将全量数据读取完毕后，才能确定，所以我们必须要经历：读->分桶（不排序）->落盘->读取分桶全量数据->排序->落盘排序后数据
选择分桶方案后，我们发现方案的实操性变得可控了，但上述方案同时也存在明显的不足：那就是频繁的IO。数据被读取、写入、再读取、再写入。
我们仔细分析一下便发现，虽然步骤繁琐，但是貌似每一步都必不可少：
反复思考几次后，便发现第二阶段仅仅会查询4000次，而4000次的查询有可能不会命中所有分桶，但我们却兴师动众的将全量数据进行了全排序。例如假定我们将每一列都分成2048个桶，这样全部4列的数据，就会被分割为2048*4=8192个分桶，而在第二阶段查询的时候，也仅仅会查询4000次，这就意味着即便4000次查询每一次都命中不同的分桶，那么也至少有一半儿多的分桶没有命中。
那最后可得出结论：排序不是必须的，那什么时候排序呢？我们可以在查询阶段再对具体命中的分桶排序，何乐而不为呢？这样便可大大提高程序性能
那分桶的方案便可简化为：
那如何确定目标数据落在哪个分桶呢？其实我们只要保证桶之间有序即可；假如我们分了4个桶，每个桶数据及范围如下：
bucket 0 存储1-100范围的数据，总共数量有20个bucket 1 存储101-200范围的数据，总共数量有50个bucket 2 存储201-300范围的数据，总共数量有35个bucket 3 存储301-400范围的数据，总共数量有38个当寻找排序为100大的数据时，其一定是落在bucket 2号分桶内，如下图所示：
总结：之所以最终锁定分桶且不排序的方案，是因为查询的次数太少了，为了仅仅4000次的查询，而进行全量数据的排序的方案性价比实在太低。不过我们可以思考一个问题，如果第二阶段不是查询4000次，而是查询4000万次呢？如果真是如此的话，那么我相信全量排序一定会定位成：“磨刀不误砍柴工”了
大思路定了以后，我们再来分析下赛题。复赛给出了2个接口：
loadquantile其实选手本质上就是实现这2个接口，把接口逻辑填充完整即可，接口的协议内容如下
public interface AnalyticDB {
void load(String tpchDataFileDir, String workspaceDir) throws Exception;
String quantile(String table, String column, double percentile) throws Exception;
}
进程会被评测程序启动2次：
load接口，接下来调用10次quantile接口load接口，接下来调用4000次quantile接口复赛给出了2张源表的数据，每张表均为2列，每列的数据行数是10亿行，因为所有数据均为long类型，这样总共存在40亿个long值，在Java中，使用8个字节存储长整型，所以我们简单做个算式便可得出，40亿个long大约会占用40亿*8/1024/1024/1024约 30G 的空间。但源文件是以字符存储的，即一个十进制的位占用一个字节，一个long如果是19位的话，就会占用19个字节，因long的值为随机生成，故源文件大小约 74G
在我们读取数据后，需要对数据进行排序等cpu操作，因内存只有8G，且进程会被kill，所以解析出来的30G数据一定需要落盘，至此我们可以描绘一下整个进程的运行轨迹
我们简单把所有行为分为4个步骤：
load_1 加载源文件74G的数据，解析处理query_1 10次查询load_2 加载关键部分数据query_2 4000次查询由于load_2只会加载一些关键数据，且query_1只会进行10次查询，基数较小；所以耗时操作分布在load_1及query_2
IO读取貌似没有什么可展开说的，注意一些关键点即可：
| 注意点 | 说明 |
|---|---|
| 1、基准测试 | 在评测机上做IO的benchmark test，探测到启动多少线程、单次写入量多大时能打满IO |
| 2、文件读取方式 | FileChannel vs MappedByteBuffer(mapp) 两者的性能做下对比，虽然通常情况下，mapp只在单次写入小数据量时才有优势，但有时不同的评测机表现得差异很大，所以针对性的比较一下还是很有必要 |
| 3、堆外内存 | 因为JVM对于IO操作的特殊处理，在对文件进行读、写时，无论采用的是DirectByteBuffer还是HeapByteBuffer，JVM均会将数据首先拷贝至堆外内存中，所以无形中，使用HeapByteBuffer会多一次数据拷贝（其实还是JAVA垃圾回收带来的问题，在垃圾回收时，堆内存的数据地址会发生移动并重排，而native方法接收的是address以及写入大小，address变动会带来致命的问题，但总不能设定在IO操作时，不能进行GC吧。又因为堆外内存不受GC约束，所以设计者将数据主动拷贝一份至堆外，来避免垃圾回收带来的尴尬；在java doc中也标注使用者尽量使用堆外内存以提高性能，此处不再赘述） |
| 4、串行读取 | 此处较好理解，即便是多线程读取IO，我们也要控制请求是串行访问的。因为不论是机械磁盘还是SSD，其本身的并发读写能力是非常低的，所以当我们多线程读取某个文件时，一定要控制读取姿势，保证串行读取的同时，充分利用好操作系统的 Page Cache |
对于第4点，简单展开说一下。我们看以下代码：
场景一：
@Test
public void test() throws Exception {
int threadNum = 8;
int readSize = 1024 * 1024;
FileChannel fileChannel = FileChannel.open(file.toPath(), StandardOpenOption.READ);
AtomicInteger readFlag = new AtomicInteger();
Thread[] threads = new Thread[threadNum];
for (int i = 0; i
try {
ByteBuffer byteBuffer = ByteBuffer.allocateDirect(readSize);
while (true) {
int blockIndex = readFlag.getAndIncrement();
int flag = fileChannel.read(byteBuffer, blockIndex * readSize);
if (flag == -1) {
break;
}
}
} catch (Exception e) {
e.printStackTrace();
}
});
}
for (Thread thread : threads) {
thread.start();
}
for (Thread thread : threads) {
thread.join();
}
}
场景二：
@Test
public void test2() throws Exception {
int threadNum = 8;
int readSize = 1024 * 1024;
FileChannel fileChannel = FileChannel.open(file.toPath(), StandardOpenOption.READ);
AtomicInteger readFlag = new AtomicInteger();
Thread[] threads = new Thread[threadNum];
for (int i = 0; i
try {
ByteBuffer byteBuffer = ByteBuffer.allocateDirect(readSize);
while (true) {
synchronized (Object.class) {
int blockIndex = readFlag.getAndIncrement();
int flag = fileChannel.read(byteBuffer, blockIndex * readSize);
if (flag == -1) {
break;
}
}
}
} catch (Exception e) {
e.printStackTrace();
}
});
}
for (Thread thread : threads) {
thread.start();
}
for (Thread thread : threads) {
thread.join();
}
}
场景二对比场景一，仅仅是在读取数据时，添加了synchronized锁，感觉性能没有场景一高。但由于操作系统的pageCache存在，场景二其实是顺序读的模式，所以真实测下来的话，场景二的性能肯定要高于场景一的
然而，正是在这个众所周知的点上，栽了一个大跟头。。。。
评测机采用的 intel 的持久内存存储介质PMEM，使得这块盘具备了并发能力，也就是说，在本次评测机上，场景一的性能是要高于场景二的。下面附上 PMEM 的官网，有兴趣的同学可以去了解下，本文不再展开
Intel傲腾持久化内存介绍
说明：此处的解析主要是指将字符存储的10进制数据，转换为字节存储
这个命题感觉很小，没什么值得聊得，但是不得不说，小细节中藏着大文章。
为什么要转换为字节存储？ 其实目的主要是为了存储压缩。假定现在有一个数据，内容是123，字符在存储的时候，不关心这个数据是什么类型，且只认为这是一组字符数组组成，因为目标值中，只存在0-9，10个数字，所以存储123的话，只需要3个字节
那这不是好事儿吗？如果123存储在一个long类型时，需要8个byte，而现在存储123仅需要3个字节。如果仅拿123举例的话，的确是这样，但比赛的数据都是随机生成，且数据散列，绝大多数的数据都是19位，这样的话，存储一个long就需要19个字节，远大于8个字节
源数据举例
2747223341331115405,4799778556018601156
3277655512998525145,5145305521134065229
5014057769282191800,1358990770775079655
6180255258051820430,9182333839965782307
比较容易想到的方式便是利用jdk进行字符串分割
String[] split = str.split(",");
long data1 = Long.parseLong(split[0]);
long data2 = Long.parseLong(split[1]);
当然这种看起来就慢的方式实在是太慢了split()、parseLong()内部都是大量的计算以及各类校验，如果你真的采用这种方式解析字符的话，那可能估计得有一半儿以上的时间浪费在了这里
其实经典的将十进制转换二进制的方式便是乘10法：
1 如果只有1位，那么直接将其返回12 可通过1*10+2得到123 层层计算 (1*10+2)*10+3得到1234 层层计算 ((1*10+2)*10+3)*10+4得到由此不难写出如下代码
for (int i = 0; i
if (element <45) {
storeData(data);
data = 0L;
} else {
data = data * 10 + (element - 48);
}
}
方式二已经很快了，难道有更快的策略吗？答案是肯定的。我们看一下方式二存在的弊端，那就是每个字节都要执行if (element <45)的判断，假定每个long为19位，40亿long的话需要进行判断的次数为40亿*19次，而在cpu优化中，if是比较耗时的。通常我们采用分支预判或者减少分支的方式，那上述逻辑如何减少分支判断呢？
我们发现一点，大多数的数字长度均为19位，比例几乎占到 90%，且最小的数字长度也 >= 11位，所以我们可以直接判断当前位置后的第20位是否为分隔符，如果是的话，那么就可以肯定这段range中的数据均为0-9，这样便可以不用分支判断
while (endAddress > addressTmp) {
byte element = unsafe.getByte(addressTmp + 19);
long tmp = 0;
if (element <45) {
for (int j = 0; j <19; j++) {
tmp = tmp * 10 + (unsafe.getByte(addressTmp++) & 15);
}
addressTmp++;
storeData(element, tmp);
} else {
for (int j = 0; j <19; j++) {
byte ele = unsafe.getByte(addressTmp++);
if (ele <45) {
storeData(ele, tmp);
break;
} else {
tmp = tmp * 10 + (ele & 15);
}
}
}
}
另外乘10法依旧还有优化的空间，例如123，如果采用data = data * 10 + (element - 48)来计算，自然无可厚非，但如果我们已经知晓123中1已处于百位的位置、2处于十位、3处于个位，那么可以直接执行1*100 + 2*10 + 3的运算，这样性能会有半秒的提升
方式四是比赛结束后才找到资料，特此说明哈
因为方式一至方式三，都是面向字节的，如果我们能面向long操作，直接将一个“十进制”的long转换为二进制的，那性能不可同日而语。其主要思想是将一个long拆成2个，long1保留奇数位的字节，long2保留偶数位的字节，然后执行 long2*10 + (long1>>8)
以下是本人根据论文实现的 long 值转换
@Test
public void test() {
String str = "1234567890123456789";
byte[] bytes = str.getBytes();
ByteBuffer byteBuffer = ByteBuffer.wrap(bytes).order(ByteOrder.nativeOrder());
long long1 = byteBuffer.getLong();
long1 = transLong(long1);
long long2 = byteBuffer.getLong();
long2 = transLong(long2);
long byte1 = byteBuffer.get();
byte1 &= 0x0f;
long byte2 = byteBuffer.get();
byte2 &= 0x0f;
long byte3 = byteBuffer.get();
byte3 &= 0x0f;
long tail = byte1 * 100 + byte2 * 10 + byte3;
long res_0 = long1 * 100000000000L + long2 * 1000L + tail;
System.out.println(res_0);
}
private long transLong(long half) {
long upper = (half & 0x000f000f000f000fL) * 10;
long lower = (half & 0x0f000f000f000f00L) >> 8;
half = lower + upper;
upper = (half & 0x000000ff000000ffL) * 100;
lower = (half & 0x00ff000000ff0000L) >> 16;
half = lower + upper;
upper = (half & 0x000000000000ffffL) * 10000;
lower = (half & 0x0000ffff00000000L) >> 32;
return lower + upper;
}
有兴趣的同学可以翻阅原文连接：Faster Integer Parsing 本文不再展开
分桶思想是整个赛题的大脉络，策略好坏直接影响最终成绩
如何进行分桶呢？我们可以利用数据散列的特点，假定现在所有的数据范围是[1,1000]，因为要保证桶自身是有序的，所以可以将数据分为10个桶：[1,100]、[101,200]、[201,300]、[301,400]......、[901,1000]，这样就可保证第一个分桶的数据都是小于第二个分桶的，第二个分桶的数据都是小于第三个分桶的。。。
不过我们分桶时除了满足桶有序外，还要对二进制友好，最好通过简单的位移操作便可获取分桶号，所以自然我们便想到通过截取高字节的bit来确定分桶个数
这样带来的好处是，直接执行data >> shift便可以获取到分桶下标
既然分桶的话，就存在一个重要命题：分多少个桶合适？我们知道最终耗时是load阶段跟query阶段的加和。
load阶段耗时变小，因为逻辑需要处理的分流变得简单。最极端的情况是整个程序只分一个桶，那分桶阶段的耗时将会变得忽略不计。但分桶数量变少必然导致每个分桶内的数据增多，那么查询阶段的耗时也会骤增load阶段的耗时增加、query阶段的耗时减少所以我们需要在分桶数量上寻找平衡点，此消彼长的模型一定存在一个中轴值，或者说是抛物线的最高点，来保证load阶段与query阶段的加和最小，也就是整体耗时最少。经过大量的benchmark，我的方案最终得出的结论是：2048个桶。在2048桶时，load阶段的耗时为28s左右，4000次的query阶段的耗时为3.3s左右
如果选手一上来就将总的分桶数量设置为2048，并开始进行分发、cpu计算等，那最终的成绩一定上不来：简单设想一下，40亿个long值，每一次分发都面对是一个长度是2048的数组或二维数组或数组引用，每进行一次数据分发，就加大了cpu各级缓存失效的几率，从而拖慢性能。那该如何解决此问题呢？
答案就是二次分发，或者多次分发。我们可以将一个2048长度的数组拆分为128个大分桶，每个大分桶内再拆分16个小分桶。128*16=2048，这样数据每次分流时，面对的是128或16长度的数组，大大增加cpu cache的命中率。本人亲测，这块能提升10s左右的性能
那多次分桶的数量是不是越多越好呢？例如我进行11次分发，这样每一次分发的数组长度可能只有2，岂不是更能提高cpu cache的命中率了吗？但多级分桶并不是比赛的银弹，它带来最直观的问题就是数据拷贝，如果真的进行了11次多级分桶，那30G的数据将会在内存中进行11次的拷贝，这个带来的后果是灾难性的，同4.5.1论述的场景类似，多级分桶跟耗时也是一个抛物线的模型，具体进行几次分桶就需要选手摸爬滚打的benchmark
load阶段结束后就要进行4000次的桶内查询了
最直观的方式当然是排序了，因为目标数据量比较大，分了2048个桶后，每个桶内的数据也有大约50万，所以直接进行快排，并返回第80位的数据arr[79]即可
此处额外提一下JDK自带的Arrays.sort()排序方法，此方法是直接进行快排的吗？答案是否定的，该方法真实的逻辑为：
但是如果想利用Arrays.sort()进行归并排序的话，需要注意的是，归并排序需要用到额外的数组来存放临时排序结果，而直接调用Arrays.sort()会每次都新建数组，拖慢性能，所以真有此类需求的话需留意，根据场景可将辅助数组绑定至线程上下文中
我们冷静下来再来梳理一遍此处的需求，我们真实的需求只是想找到某个数组中的K大值，而排序的方案则是兴师动众的将全量数据都进行了一遍排序。
而寻找K大值的过程其实与快排类似，例如我们寻找第80大值，然后找到了中轴值50，最终发现，中轴值左边有70个值，右边有30个，那第80大值一定在中轴值的右侧，所以我们再针对右边的30个数重复这个操作，而左边的70个值，可以直接放弃，不用再迭代排序，贴一下代码：
/**
* 寻找K大值
* @param nums 目标数组
* @param l 左index
* @param r 右index
* @param k K大
* @return 具体值
*/
public static long solve(long[] nums, int l, int r, int k) {
if (l == r) {
return nums[l];
}
int p = partition(nums, l, r);
if (k == p) {
return nums[p];
} else if (k
} else {
return solve(nums, p + 1, r, k);
}
}
private static int partition(long[] arr, int l, int r) {
long v = arr[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i]
swap(arr, j, i);
}
}
swap(arr, l, j);
return j;
}
private static void swap(long[] arr, int a, int b) {
long temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
寻找K大值的方案已经很快了，难道还有更快的方案？
是的，此处就要利用原题意描述的数据特征了：随机生成、离散。为了叙述方便，我们简化一下模型：随机给定100个数，这些数据的范围是[1-100]，然后需要返回第80大的数据。这样的话我们能否对目标数据进行预测？返回第80大的数据，且数据分布是[1-100]，那可以预测目标值就是80，可80大概率不是正确答案，但一定是在80左右浮动，此时我们可以设定一个浮动百分比，或者上下浮动的范围，例如：[75-85]，所以我们接下来的工作就是寻找目标数组落在这个区域以及小于这个区域的数量了，假定统计的结果如下：
所以我们可以非常确定目标数据一定落在[75-85]区间，这样只扫描一遍数据后，便将数据缩小到了很小的范围。有同学可能会问，如果扫描一遍后没有命中范围怎么办？那就重新执行寻找K大值的方法，保证程序不出错，而至于浮动范围设定为多少合适，就又是抛物线模型，寻找最高点了
写入操作没有太多值得分享的点，保证堆外内存写入、以及单次写入量不宜过小都是一些基本注意事项
值得一提的是，有小伙伴建议写入使用write(ByteBuffer[] srcs)的方式，其底层调用函数做了很多优化，我方案修改成此方式后，性能并没有有效提升，有兴趣的同学可以深入探索下
针对于进程内的“读-解析(cpu)-写”场景，此处提出两个线程模型
两个线程模型各有优劣，很难明确地说哪种模型更好，不同的场景表现差异较大，所以本人的结论还是那句亘古不变的话：Benchmark Everything
随机生成的离散数据如何压缩呢？其实倒也不难想到，因为我们已经将数据前N个bit提取出来作为分桶编号了，所以这N个bit都是重复数据，例如想压缩掉高位的8个bit（1个字节）的话，可以有2种方式：
writeBuffer.putLong(index, data);
index += 7;
或者
writeBuffer.put((byte) ((data1 <<8 >>> 56)));
writeBuffer.putInt((int) (data1 <<16 >>> 32));
writeBuffer.putShort((short) (data1));
有时候数组开辟空间的耗时也将会是一个很大的提升点，可以通过多线程并发开辟空间的方式，来提供性能。为什么数组开辟这么耗时？不就是申请一段连续的内存空间吗？其实本身申请内存空间不耗时，但内存申请完毕后，会对数组内全部数据有个赋0操作，而这个操作本身是相当耗时的
当我们想申请堆外内存DirectByteBuffer时，发现速度也相当慢，翻看其源码便能发觉其本身开辟空间时，同样存在赋0操作
long base = 0;
try {
base = unsafe.allocateMemory(size);
} catch (OutOfMemoryError x) {
Bits.unreserveMemory(size, cap);
throw x;
}
// 赋0操作
unsafe.setMemory(base, size, (byte) 0);
那如何绕过这个蹩脚操作呢？同样翻看源码便可发现，其控制写入、读取是通过两个关键变量address、capacity：一个是当前buffer的内存地址，一个是buffer的长度，我们是否可以通过反射瞒天过海呢？以下贴上源码
private static Field addr;
private static Field capacity;
static {
try {
addr = Buffer.class.getDeclaredField("address");
addr.setAccessible(true);
capacity = Buffer.class.getDeclaredField("capacity");
capacity.setAccessible(true);
} catch (NoSuchFieldException e) {
e.printStackTrace();
}
}
public static ByteBuffer newFastByteBuffer(int cap) {
long address = unsafe.allocateMemory(cap);
ByteBuffer bb = ByteBuffer.allocateDirect(0).order(ByteOrder.nativeOrder());
try {
addr.setLong(bb, address);
capacity.setInt(bb, cap);
} catch (IllegalAccessException e) {
return null;
}
bb.clear();
return bb;
}
多线程如何读取文件呢？我们获取到文件大小后，完全可以为每个线程指定读取区间，但这样可能会造成木桶效应，即程序的耗时取决于最慢线程的耗时，同时可能带来评测程序的不稳定
理想的情况是滚动读，多个线程一起来消费数据；但如果一次读取的数据量不够大，可能执行滚动的cas操作会消耗较多的cpu，简单直接的解决方式是一次标记一段数据，减少线程见的争抢
private int tmpBlockIndex = -1;
private int threadReadData() throws Exception {
if (tmpBlockIndex == -1) {
tmpBlockIndex = number.getAndAdd(cpuThreadNum);
} else {
if ((tmpBlockIndex + 1) % cpuThreadNum == 0) {
tmpBlockIndex = number.getAndAdd(cpuThreadNum);
} else {
tmpBlockIndex++;
}
}
int indexNum = tmpBlockIndex;
}
还有很多小的cpu优化不能穷举，有兴趣同学可以参看源码
首先给本次adb比赛点个大大的赞，不论是初赛还是复赛，本次比赛没有修改过题目描述、没有私自换过评测数据、排行榜没有清空、更没有给选手留下漏洞，是我近几年参赛中最干净、纯粹的赛题了；其他赛道或将来的比赛应该向人家学习
其次整个比赛期间，真心感谢身边小伙伴@振兴、@满仓、@新然、@笳鑫的鼎力协助 [抱拳]
源码地址： git@github.com:xijiu/tianchi-2021-db-contest.git
 |  |  |  |  |
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有