throws IOException {
PriorityQueue<Pair<FileReader, Integer>> heap =
new PriorityQueue<>((p1, p2) -> p1.getValue() - p2.getValue());
for (FileReader fr : readers) {
if (fr.hasNext()) {
heap.add(new Pair<>(fr, fr.next()));
while (!heap.isEmpty()) {
Pair<FileReader, Integer> current = heap.poll();
writer.append(current.getValue());
FileReader currentReader = current.getKey();
if (currentReader.hasNext()) {
heap.add(new Pair<>(currentReader, currentReader.next()));
}
}
3. LSM树的索引结构
一个LSM树的索引主要由两部分构成：内存部分和磁盘部分。内存部分是一个ConcurrentSkipListMap，Key就是前面所说的Key部分，Value是一个字节数组。数据写入时，直接写入MemStore中。随着不断写入，一旦内存占用超过一定的阈值时，就把内存部分的数据导出，形成一个有序的数据文件，存储在磁盘上。
图2-8 LSM树索引结构
LSM树索引结构如图2-8所示。内存部分导出形成一个有序数据文件的过程称为f lush。为了避免flush影响写入性能，会先把当前写入的MemStore设为Snapshot，不再容许新的写入操作写入这个Snapshot的MemStore。另开一个内存空间作为MemStore，让后面的数据写入。一旦Snapshot的MemStore写入完毕，对应内存空间就可以释放。这样，就可以通过两个MemStore来实现稳定的写入性能。
在整个数据写入过程中，LSM树全部都是使用append操作（磁盘顺序写）来实现数据写入的，没有使用任何seek+write（磁盘随机写）的方式来写入。无论HDD还是SSD，磁盘的顺序写操作性能和延迟都远好于磁盘随机写。因此LSM树是一种对写入极为友好的索引结构，它能将磁盘的写入带宽利用到极致。
随着写入的增加，内存数据会不断地刷新到磁盘上。最终磁盘上的数据文件会越来越多。如果数据没有任何的读取操作，磁盘上产生很多的数据文件对写入并无影响，而且这时写入速度是最快的，因为所有IO都是顺序IO。但是，一旦用户有读取请求，则需要将大量的磁盘文件进行多路归并，之后才能读取到所需的数据。因为需要将那些Key相同的数据全局综合起来，最终选择出合适的版本返回给用户，所以磁盘文件数量越多，在读取的时候随机读取的次数也会越多，从而影响读取操作的性能。
为了优化读取操作的性能，我们可以设置一定策略将选中的多个hfile进行多路归并，合并成一个文件。文件个数越少，则读取数据时需要seek操作的次数越少，读取性能则越好。
一般来说，按照选中的文件个数，我们将compact操作分成两种类型。一种是major compact，是将所有的hf ile一次性多路归并成一个文件。这种方式的好处是，合并之后只有一个文件，这样读取的性能肯定是最高的；但它的问题是，合并所有的文件可能需要很长的时间并消耗大量的IO带宽，所以major compact不宜使用太频繁，适合周期性地跑。
另外一种是minor compact，即选中少数几个hf ile，将它们多路归并成一个文件。这种方式的优点是，可以进行局部的compact，通过少量的IO减少文件个数，提升读取操作的性能，适合较高频率地跑；但它的缺点是，只合并了局部的数据，对于那些全局删除操作，无法在合并过程中完全删除。因此，minor compact虽然能减少文件，但却无法彻底清除那些delete操作。而major compact能完全清理那些delete操作，保证数据的最小化。
总结：LSM树的索引结构本质是将写入操作全部转化成磁盘的顺序写入，极大地提高了写入操作的性能。但是，这种设计对读取操作是非常不利的，因为需要在读取的过程中，通过归并所有文件来读取所对应的KV，这是非常消耗IO资源的。因此，在HBase中设计了异步的compaction来降低文件个数，达到提高读取性能的目的。由于HDFS只支持文件的顺序写，不支持文件的随机写，而且HDFS擅长的场景是大文件存储而非小文件，所以上层HBase选择LSM树这种索引结构是最合适的。
2.3 布隆过滤器
1.案例
如何高效判断元素w是否存在于集合A之中？首先想到的答案是，把集合A中的元素一个个放到哈希表中，然后在哈希表中查一下w即可。这样确实可以解决小数据量场景下元素存在性判定，但如果A中元素数量巨大，甚至数据量远远超过机器内存空间，该如何解决问题呢？
实现一个基于磁盘和内存的哈希索引当然可以解决这个问题。而另一种低成本的方式就是借助布隆过滤器（Bloom Filter）来实现。
布隆过滤器由一个长度为N的01数组array组成。首先将数组array每个元素初始设为0。
对集合A中的每个元素w，做K次哈希，第i次哈希值对N取模得到一个index(i)，即index(i)=HASH_i(w) % N，将array数组中的array[index(i)]置为1。最终array变成一个某些元素为1的01数组。
下面举个例子，如图2-9所示，A = {x, y, z}，N = 18，K = 3。
图2-9 布隆过滤器算法示例
初始化array = 000000000000000000。
对元素x，HASH_0(x)%N = 1，HASH_1(x)%N = 5，HASH_2(x)%N = 13。因此array = 010001000000010000。
对元素y，HASH_0(y)%N = 4，HASH_1(y)%N = 11，HASH_2(y)%N = 16。因此array = 010011000001010010。
对元素z，HASH_0(z)%N = 3，HASH_1(y)%N = 5，HASH_2(y)%N = 11。因此array = 010111000001010010。
最终得到的布隆过滤器串为：010111000001010010。
此时，对于元素w，K次哈希值分别为：
HASH_0(w)%N = 4
HASH_1(w)%N = 13
HASH_2(w)%N = 15
可以发现，布隆过滤器串中的第15位为0，因此可以确认w肯定不在集合A中。因为若w在A中，则第15位必定为1。
如果有另外一个元素t，K次哈希值分别为：
HASH_0(t)%N = 5
HASH_1(t)%N = 11
HASH_2(t)%N = 13
我们发现布隆过滤器串中的第5、11、13位都为1，但是却没法肯定t一定在集合A中。
因此，布隆过滤器串对任意给定元素w，给出的存在性结果为两种：
w可能存在于集合A中。
w肯定不在集合A中。
在论文中证明，当N取K*|A|/ln2时（其中|A|表示集合A元素个数），能保证最佳的误判率，所谓误判率也就是过滤器判定元素可能在集合中但实际不在集合中的占比。
举例来说，若集合有20个元素，K取3时，则设计一个N = 3×20/ln2 = 87二进制串来保存布隆过滤器比较合适。
2.算法实现
布隆过滤器的代码实现很短，如下所示：
public class BloomFilter {
private int k;
private int bitsPerKey;
private int bitLen;
private byte[] result;
public BloomFilter(int k, int bitsPerKey) {
this.k = k;
this.bitsPerKey = bitsPerKey;
public byte[] generate(byte[][] keys) {
assert keys != null;
bitLen = keys.length * bitsPerKey;
bitLen = ((bitLen + 7) / 8) << 3; // align the bitLen.
bitLen = bitLen < 64 64 : bitLen;
result = new byte[bitLen >> 3]; // each byte have 8 bit.
for (int i = 0; i < keys.length; i++) {
assert keys[i] != null;
int h = Bytes.hash(keys[i]);
for (int t = 0; t < k; t++) {
int idx = (h % bitLen + bitLen) % bitLen;
result[idx / 8] |= (1 << (idx % 8));
int delta = (h >> 17) | (h << 15);
h += delta;
return result;
public boolean contains(byte[] key) {
assert result != null;
int h = Bytes.hash(key);
for (int t = 0; t < k; t++) { // Hash k times
int idx = (h % bitLen + bitLen) % bitLen;
if ((result[idx / 8] & (1 << (idx % 8))) == 0) {
return false;
int delta = (h >> 17) | (h << 15);
h += delta;
return true;
}
}
有两个地方说明一下：
在构造方法BloomFilter(int k, int bitsPerKey)中，k表示每个Key哈希的次数，bitsPerkey表示每个Key占用的二进制bit数，若有x个Key，则N=x*bitsPerKey。
在实现中，对Key做k次哈希时，算出第一次哈希值h之后，可借助h位运算来实现二次哈希，甚至三次哈希。这样性能会比较好。
3.案例解答
有了布隆过滤器这样一个存在性判断之后，我们回到最开始提到的案例。把集合A的元素按照顺序分成若干个块，每块不超过64KB，每块内的多个元素都算出一个布隆过滤器串，多个块的布隆过滤器组成索引数据。为了判断元素w是否存在于集合A中，先对w计算每一个块的布隆过滤器串的存在性结果，若结果为肯定不存在，则继续判断w是否可能存在于下一个数据块中。若结果为可能存在，则读取对应的数据块，判断w是否在数据块中，若存在则表示w存在于集合A中；若不存在则继续判断w是否在下一个数据块中。
这样就解决了这个问题。读者可以思考一下：在64KB的数据块中，平均每个Key占用1000字节，且在做3次哈希的情况下，需要占用多少字节的空间来存储布隆过滤器的二进制？
4. HBase与布隆过滤器
正是由于布隆过滤器只需占用极小的空间，便可给出“可能存在”和“肯定不存在”的存在性判断，因此可以提前过滤掉很多不必要的数据块，从而节省了大量的磁盘IO。HBase的Get操作就是通过运用低成本高效率的布隆过滤器来过滤大量无效数据块的，从而节省大量磁盘IO。
在HBase 1.x版本中，用户可以对某些列设置不同类型的布隆过滤器，共有3种类型。
NONE：关闭布隆过滤器功能。
ROW：按照rowkey来计算布隆过滤器的二进制串并存储。Get查询的时候，必须带- rowkey，所以用户可以在建表时默认把布隆过滤器设置为ROW类型。
ROWCOL：按照rowkey+family+qualif ier这３个字段拼出byte[]来计算布隆过滤器值并存储。如果在查询的时候，Get能指定rowkey、family、qualif ier这３个字段，则肯定可以通过布隆过滤器提升性能。但是如果在查询的时候，Get中缺少rowkey、family、qualifier中任何一个字段，则无法通过布隆过滤器提升性能，因为计算布隆过滤器的Key不确定。
注意，一般意义上的Scan操作，HBase都没法使用布隆过滤器来提升扫描数据性能。原因很好理解，同样是因为布隆过滤器的Key值不确定，所以没法计算出哈希值对比。但是，在某些特定场景下，Scan操作同样可以借助布隆过滤器提升性能。
对于ROWCOL类型的布隆过滤器来说，如果在Scan操作中明确指定需要扫某些列，如下所示：
Scan scan = new Scan()
.addColumn(FAMILY0, QUALIFIER0)
.addColumn(FAMILY1, QUALIFIER1)
那么在Scan过程中，碰到KV数据从一行换到新的一行时，是没法走ROWCOL类型布隆过滤器的，因为新一行的key值不确定；但是，如果在同一行数据内切换列时，则能通过ROWCOL类型布隆过滤器进行优化，因为rowkey确定，同时column也已知，也就是说，布隆过滤器中的Key确定，所以可以通过ROWCOL优化性能，详见HBASE-4465。
另外，在HBASE-20636中，腾讯团队介绍了一种很神奇的设计。他们的游戏业务rowkey是这样设计的：
rowkey=#
也就是用userid和其他字段拼接生成rowkey。而且业务大部分的请求都按照某个指定用户的userid来扫描这个用户下的所有数据，即按照userid来做前缀扫描。基于这个请求特点，可以把rowkey中固定长度的前缀计算布隆过滤器，这样按照userid来前缀扫描时（前缀固定，所以计算布隆过滤器的Key值也就固定），同样可以借助布隆过滤器优化性能，HBASE-20636中提到有一倍以上的性能提升。另外，对于Get请求，同样可以借助这种前缀布隆过滤器提升性能。因此，这种设计对Get和基于前缀扫描的Scan都非常友好。
这个功能已经在HBase 2.x版本上实现，感兴趣的读者可以尝试。
2.4 设计KV存储引擎MiniBase
前面我们已经介绍了LSM树索引结构中最核心的数据结构和算法。在理解了这些基本知识后，我们可以自己动手设计一个嵌入式KV存储引擎。
本节实践性很强，我们将动手实现一个高吞吐低延迟的KV存储引擎。这个KV存储引擎非常轻量级，可以说是HBase的一个极简版本，所以，我们暂且称它为MiniBase，即HBase的迷你版本。
MiniBase作为嵌入式存储引擎，提供了一些非常简洁的接口，如下所示：
public interface MiniBase extends Closeable {
void put(byte[] key, byte[] value) throws IOException;
byte[] get(byte[] key) throws IOException;
void delete(byte[] key) throws IOException;
Fetch all the key values whose key located in the range [startKey, stopKey)
@param startKey start key to scan (inclusive), if byte[0], means -oo
@param stopKey to stop the scan. (exclusive), if byte[0], means +oo
@return Iterator for fetching the key value one by one.
*/
Iter scan(byte[] startKey, byte[] stopKey) throws IOException;
interface Iter {
boolean hasNext() throws IOException;
KeyValue next() throws IOException;
}
}
MiniBase只容许使用byte[]作为Key和Value，事实上，其他类型的基本数据类型可以非常容易地转化成byte[]：例如，String s = "abc"，那么通过Bytes.toBytes(s)可以转化成byte[]，其他数据类型类似。下面对接口部分做简要介绍：
put/get/delete这3个接口非常容易理解，即增加、读取、删除一个key。如碰到异常，则直接抛出IOException。
scan接口需要传入扫描的数据范围[startKey, stopkey)。注意，如果startKey=byte[0]，则表示扫描（- ∞, stopKey）的所有数据，stopkey=byte[0]也是类似的含义。由于Scan操作可能返回内存无法存放的大量数据，因此，我们设计了一个迭代器用来读取数据。用户只需不断地执行next()，直到hasNext()返回false，即可从小到大依次读取存储引擎中的所有数据。
1.MiniBase核心设计
MiniBase的总体结构如图2-10所示。MiniBase是一个标准的LSM树索引结构，分内存部分和磁盘部分。
图2-10 MiniBase总体结构
内存部分为MemStore。客户端不断地写入数据，当MemStore的内存超过一定阈值时，MemStore会flush成一个磁盘文件。可以看到图2-10中的MemStore分成MutableMemstore和ImmutableMemstore两部分，MutableMemstore由一个ConcurrentSkipListMap组成，容许写入；ImmutableMemstore也是一个ConcurrentSkipListMap，但是不容许写入。这里设计两个小的MemStore，是为了防止在f lush的时候，MiniBase无法接收新的写入。假设只有一个MutableMemstore，那么一旦进入f lush过程，MutableMemstore就无法写入，而此时新的写入就无法进行。
磁盘部分为DiskStore，由多个DiskFile组成，每一个DiskFile就是一个磁盘文件。ImmutableMemstore执行完flush操作后，就会生成一个新的DiskFile，存放到DiskStore中。当然，为了有效控制DiskStore中的DiskFile个数，我们为MiniBase设计了Compaction策略。目前的Compaction策略非常简单—当DiskStore的DiskFile数量超过一个阈值时，就把所有的DiskFile进行Compact，最终合并成一个DiskFile。
下面考虑DiskFile的文件格式设计。在设计之前，需要注意几个比较核心的问题：
DiskFile必须支持高效的写入和读取。由于MemStore的写入是顺序写入，如果flush速度太慢，则可能会阻塞后续的写入，影响写入吞吐，因此flush操作最好也设计成顺序写。LSM树结构的劣势就是读取性能会有所牺牲，如果在DiskFile上能实现高效的数据索引，则可以大幅提升读取性能，例如考虑布隆过滤器设计。
由于磁盘空间很大，而内存空间相对很小，所以DiskFile的数据必须分成众多小块，一次IO操作只读取一小部分的数据。通过读取多个数据块来完成一次区间的扫描。
基于这些考虑，我们为MiniBase的DiskFile做了简单的设计，如图2-11所示。
图2-11 DiskFile存储格式
一个DiskFile由３种类型的数据块组成，分别是DataBlock、IndexBlock、MetaBlock。
DataBlock ：主要用来存储有序的KeyValue集合—KeyValue-1，KeyValue-2，…，KeyValue-N，这些KeyValue的大小顺序与其存储顺序严格一致。另外，在MiniBase中，默认每一个Block约为64kB，当然用户也可以自己设置Block的大小。注意，一个DiskFile内可能有多个Block，具体的Block数量取决于文件内存储的总KV数据量。
IndexBlock ：一个DiskFile内有且仅有一个IndexBlock。它主要存储多个DataBlock的索引数据，每个DataBlock的索引数据包含以下４个字段：
lastKV ：该DataBlock的最后一个KV，查找时，先查IndexBlock，根据lastKV定位到对应的DataBlock，然后直接读取这个DataBlock到内存即可。
offset ：该DataBlock在DiskFile中的偏移位置，查找时，用offset值去文件中Seek，并读取DataBlock的数据。
size：该DataBlock占用的字节长度。
bloomFilter：该DataBlock内所有KeyValue计算出的布隆过滤器字节数组。
MetaBlock ：和IndexBlock一样，一个DiskFile中有且仅有一个MetaBlock；同时MetaBlock是定长的，因此可以直接通过定位diskf ile.f ilesize - len(MetaBlock)来读取MetaBlock，而无需任何索引。主要用来保存DiskFile级别的元数据信息：
fileSize ：该DiskFile的文件总长度，可以通过对比这个值和当前文件真实长度，判断文件是否损坏。
blockCount：该DiskFile拥有的Block数量。
blockIndexOffset：该DiskFile内的IndexBlock的偏移位置，方便定位到IndexBlock。
- blockIndexSize：IndexBlock的字节长度。
假设用户需要读取指定DiskFile中key='abc'对应的value数据，那么可以按照如下流程进行IO读取：首先，由于DiskFile中MetaBlock的长度是定长的，所以很容易定位到MetaBlock的位置，并读取MetaBlock的二进制内容。MetaBlock中存储着blockIndexOffset字段，这个字段指向着IndexBlock存储的位置，因此可以定位到这个位置并读取blockIndexSize字节的二进制内容，这样就完成了IndexBlock的读取。由于IndexBlock中存储着每一个DataBlock对应的数据区间，通过二分查找可以很方便定位到key='abc'在哪个DataBlock中，再根据对应的DataBlock的offset和size，就能顺利完成DataBlock的IO读取。
在MemStore的数据导出成DiskFile时，按照DiskFile设计的存储格式，我们应该是可以保证顺序写入的。请读者自行思考DiskFile的生成流程，这里不再赘述。
2. KeyValue组成
在MiniBase中，只容许两种更新操作：Put操作，Delete操作。由于LSM树索引中存放的是操作记录，并不是真实数据，所以我们需要把KeyValue结构设计成操作记录的格式。
我们设计的KeyValue结构如下所示：
public enum Op {
Put((byte) 0),
Delete((byte) 1);
private byte code;
Op(byte code) {
this.code = code;
public class KeyValue{
private byte[] key;
private byte[] value;
private Op op;
private long sequenceId;
// ...other methods
}
这里，主要有（key, value, Op, sequenceId）这4个字段，Op有Put和Delete两种操作类型。重点需要理解SequenceId字段，我们会为每一次Put/Delete操作分配一个自增的唯一sequenceId，这样每一个操作都对应一个sequenceId。读取的时候，只能得到小于等于当前sequenceId的Put/Delete操作，这样保证了本次读取不会得到未来某个时间点的数据，实现了最简单的Read Committed的事务隔离级别。
由于KeyValue在MemStore和DiskFile中都是有序存放的，所以需要为KeyValue实现Comparable接口，如下所示：
public class KeyValue implements Comparable{
// ...
@Override
public int compareTo(KeyValue kv) {
if (kv == null) {
throw new IllegalArgumentException("kv to compare shouldn't be null");
int ret = Bytes.compare(this.key, kv.key);
if (ret != 0) {
return ret;
if (this.sequenceId != kv.sequenceId) {
return this.sequenceId > kv.sequenceId -1 : 1;
if (this.op != kv.op) {
return this.op.getCode() > kv.op.getCode() -1 : 1;
return 0;
}
}
其中，compareTo方法定义了KeyValue的比较顺序。Key小的KeyValue排在更前面，这是因为用户期望按照从小到大的顺序读取数据。注意在Key相同的情况下，sequenceId更大的KeyValue排在更前面，这是因为sequenceId越大，说明这个Put/Delete操作版本越新，它更可能是用户需要读取的数据。
（1）写入流程
无论是Put操作还是Delete操作，我们都需要一个自增的sequenceId，用于构建KeyValue结构。例如，Put操作的写入代码如下：
@Override
public void put(byte[] key, byte[] value) throws IOException {
this.memStore.add(KeyValue.createPut(key, value, sequenceId.incrementAndGet()));
}
写入到MemStore之后，需要考虑的是，数据量达到一个阈值之后，需要开始f lush。在f lush的时候，先将MutableMemstore切换成ImmutableMemstore，切换过程中必须保证没有写入操作。所以，我们用一个读写锁updateLock来控制写入操作和Flush操作的互斥。写入时，先拿到updateLock的读锁，写完之后释放，而在切换MemStore时拿到updateLock的写锁，切换完之后释放。
因此，MemStore写入代码大致如下：
public void add(KeyValue kv) throws IOException {
f lushIfNeeded(true);
updateLock.readLock().lock();
try {
KeyValue prevKeyValue;
if ((prevKeyValue = kvMap.put(kv, kv)) == null) {
dataSize.addAndGet(kv.getSerializeSize());
} else {
dataSize.addAndGet(kv.getSerializeSize() - prevKeyValue.getSerializeSize());
} f inally {
updateLock.readLock().unlock();
}
f lushIfNeeded(false);
}
注意，第一个f lushIfNeeded方法在发现MemStore满的时候，将抛出IOException，告诉用户MemStore已经满了，此刻重试即可。第二个f lushIfNeeded将提交MemStore的Flush任务，Flush线程收到请求后开始跑Flush任务。另外，在成功地把KV放入到ConcurrentSkipListMap之后，需要更新MemStore的dataSize。这里有两种情况：之前KV不存在，则直接累计kv.getSerializeSize即可；之前KV存在，则将二者差值累积到dataSize上。
dataSize为当前MemStore内存占用字节数，用于判断是否达到Flush阈值。它是一个AtomicLong变量，所以在写入高并发的情景下，该变量可能成为一个性能瓶颈，因为所有的并发写入都需要串行执行这个CAS操作。但就目前来说，对性能并不会产生太大的影响。
（2）读取流程
读取流程相对要复杂很多，从MiniBase结构图（图2-10）可以看出，有MutableMemstore
和ImmutableMemstore两个内存有序KV集合、多个DiskFile有序集合。在Scan的时候，需要把多个有序集合通过多路归并算法合并成一个有序集合，然后过滤掉不符合条件的版本，将正确的KV返回给用户。
对于多路归并算法，我们已经在2.2节中介绍，这里不再赘述。重点阐述如何过滤不符合条件的数据版本。
假设用户按照图2-12左侧所示，依次执行了7个操作（注意，每个操作的sequenceId都是自增的），那么多路归并之后的数据如图2-12右侧所示。
图2-12 多路归并后读取的KeyValue列表
对于同一个Key的不同版本，我们只关心最新的版本。假设用户读取时能看到的sequenceld≤101的数据，那么读取流程逻辑如下：
对于Key=A的版本，我们只关注（A,Delete,100）这个版本，该版本是删除操作，说明后面所有key=A的版本都不会被用户看到。
对于Key=B的版本，我们只关心（B,Put,101）这个版本，该版本是Put操作，说明该Key没有被删除，可以被用户看到。
对于Key=C的版本，我们只关心（C,Put,95）这个版本，该版本是Put操作，说明该Key没有被删除，可以被用户看到。
于是，对于全表扫描的scan操作，MiniBase将返回（B,Put,101）和（C,Put,95）这两个KeyValue给用户。
对应的代码实现，可以在MiniBase源码的MStore#ScanIter中看到，这里不再赘述。
3.思考与练习
设计存储引擎是本章最核心的部分，完整的项目代码，我们已经开源在GitHub(https://github.com/openinx/minibase)上。为了让读者更深入地理解MiniBase的实现原理，我们特意设计了一些练习，这样读者可以亲自参与MiniBase的设计和实现，学以致用。
问题1.
向MiniBase写入数据时，是直接写到MemStore中的。在MemStore刷新到磁盘之前，若进程由于异常原因退出，则用户成功写入MemStore的数据将丢失，无法恢复。一种常见的解决方案就是，在将数据写入MemStore之前，先写一份操作日志，这样即使进程退出，仍然可以通过操作日志来恢复MemStore的数据。请为MiniBase实现写WAL日志功能，保证其在进程崩溃之后依然可以从WAL日志中恢复MemStore的数据。
这里给出几个小提示：
随着用户的不断写入，WAL日志可能无限增长。这样进程重启后，恢复数据时可能需花费很长时间。因此，需要控制WAL日志的数据量，事实上一旦MemStore执行了f lush操作，那么之前的WAL日志都可以清理。
在高并发写入的情况下，会有多线程同时写入WAL日志。但由于必须保证WAL日志的完整性，需通过排他锁来控制每次写入WAL日志的操作，即多个并发写入将在写WAL日志这个步骤中严格串行，这样会极大地限制吞吐量。请思考该如何设计写WAL日志流程，以达到提升写入吞吐的目的。
问题2.
MiniBase在Get/Scan实现中，涉及读取Block的地方，并没有使用LRU Cache，而是在每次读Block的时候直接去磁盘文件中读Block。请你为MiniBase设计一种LRU Cache，把经常访问的Block缓存在内存中，这样下次读取Block时，可以省去读取磁盘的开销，降低访问延迟。
实现一个LRU Cache并不难，网上也有很多资料和库。我们容许读者使用成熟的类库来完成练习。但有如下一些注意事项：
需要用参数控制LRU缓存的总大小，这样用户可以为不同的机器配置不同大小的LRU Cache。
请将Block的Cache命中率百分比在日志中打印出来，便于用户做进一步性能调优。
对比使用LRU Cache前后，MiniBase的Get/Scan吞吐分别提升多少。
问题3.
DiskFile中的DataBlock存放着有序的多个KeyValue集合。但目前Get/Scan的实现非常简单，当需要做Block内Seek时，现在是直接依次检查各个KeyValue，这种实现相对低效。但由于KeyValue的有序性，我们也可以借助二分搜索来提升DataBlock的读取性能。请为DataBlock的Seek操作实现二分查找。
其实，当存放的KeyValue字节数很小时，Block内将存放众多KeyValue。这时二分查找比顺序查找高效很多。在实现该功能后，请对比测试KeyValue长度分别为10和1000时的性能。理论上，采用二分后，KeyValue长度为10的性能将远优于顺序读取。
问题4.
当前，在实现MiniBase的Get接口时，我们采用了一个很简单粗暴的实现方式，即通过Scan接口得到迭代器，然后将迭代器执行一次Next，就获取了Get的数据。代码如下所示：
@Override
public KeyValue get(byte[] key) throws IOException {
KeyValue result = null;
Iter it = scan(key, Bytes.EMPTY_BYTES);
if (it.hasNext()) {
KeyValue kv = it.next();
if (Bytes.compare(kv.getKey(), key) == 0) {
result = kv;
}
return result;
}
事实上，由于Get操作的特殊性，我们可以通过布隆过滤器过滤掉大量无效的Block数据块。请重新设计Get操作的实现，通过布隆过滤器来优化Get操作的性能，并对比当前版本的Get性能，看看相差多少。
拓展阅读
［1］ Choose Concurrency-Friendly Data Structures: http://www.drdobbs.com/parallel/choose-concurrency-friendly-data-structu/208801371?pgno=1
［2］ Skip Lists: A Probabilistic Alternative to Balanced Trees: http://www.epaperpress.com/sortsearch/download/skiplist.pdf
［3］ Skip List源代码Java版本：https://github.com/openinx/algorithm-solution/blob/master/template/sort/SkipList.java
［4］ The Log-Structured Merge-Tree (LSM-Tree): https://www.cs.umb.edu/~poneil/lsmtree.pdf
［5］ Bloom Filter: https://en.wikipedia.org/wiki/Bloom_filter
Client是操作HBase集群的入口，对于管理类的操作，如表的增、删、改操纵，Client通过RPC与HMaster通信完成，对于表数据的读写操作，Client通过RPC与RegionServer交互，读写数据。
