HBase的MSLAB (memstore-local allocation buffer)

前言

本文简要介绍了HBase的写缓存MemStore和数据结构，以及作为写缓存主要组件的MSLAB的作用和源码分析。MSLAB是memstore-local allocation buffer的简写，对MemStore的内存进行合理的规划管理，有效优化了Java程序的GC问题。

Memstore简介

Memstore是HBase中重要的数据存储组件之一，HBase数据写入首先记录WAL在HLog上，之后不会将数据直接写入磁盘，而是写入到Memstore后就快速返回，从而有效的提高了HBase的写入吞吐。

Memstore数据结构

Memstore使用跳表的数据结构来存储有序的KeyValue，MemStore中KeyValueSkipListSet对ConcurrentSkipListMap进行了一层包装。

跳表结构简单示意(ConcurrentSkipListMap注释示例图)：

	/*
     * Head nodes          Index nodes
     * +-+    right        +-+                      +-+
     * |2|---------------->| |--------------------->| |->null
     * +-+                 +-+                      +-+
     *  | down              |                        |
     *  v                   v                        v
     * +-+            +-+  +-+       +-+            +-+       +-+
     * |1|----------->| |->| |------>| |----------->| |------>| |->null
     * +-+            +-+  +-+       +-+            +-+       +-+
     *  v              |    |         |              |         |
     * Nodes  next     v    v         v              v         v
     * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
     * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
     * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
     */

所有数据均在最下层的链表结构中，上层的节点简单理解为索引节点。数据搜索从最上层的Head nodes开始，先在同层向右侧遍历，如果右侧节点大于要搜寻的节点，则向下一层移动，直到获取到数据。

这样存储的KeyValue保证了有序性，可以很好地在数据需要获取的时候快速定位到所需的数据内容，在flush的时候也可以直接将内存中的数据按顺序直接写入HFile中。

MSLAB的意义

? MemStore作为内存存储，数据可能在较长的时间内都一直存在于内存之中，这在Java程序中不可避免会引发GC问题。MemStore中存储的KeyValue引用可能会较长时间被持有，当执行flush后，MemStore数据被刷写到HFile中，这部分KeyValue引用也就自然可以释放了。如果对这些KeyValue内存分配不加以管理的话，在数次回收之后会产生大量的内存碎片导致Java进程没有连续的内存分配从而引发FullGC。
内存回收示意
一个RegionServer进程中存在多个region，但是多个Region的MemStore却是共享同一块JVM内存来使用。上图简单示意了这种情况下如果不对内存进行管理会造成碎片的后果。

为了解决内存碎片的问题，MSLAB诞生了。
MSLAB使用一段固定的内存段Chunk来存储KeyValue数据，而不是任由KeyValue被长期持有。这样当Region执行flush之后释放的就是一段Chunk所占有的连续内存，而不是KeyValue占有的零散内存，很好地解决了内存碎片的问题。

MSLAB源码解析

下面直接进入源码，英文注释为HBase项目原有注释，中文注释为了方便理解方法的执行过程和逻辑。

MemStoreLAB#allocateBytes

首先来看分配Chunk的主要流程，MemStore为新进入的KeyValue分配内存空间时，使用MSLAB来获取Allocation实例将KeyValue数据写入到Chunk中。

	/**
   * Allocate a slice of the given length.
   *
   * If the size is larger than the maximum size specified for this
   * allocator, returns null.
   */
   // MemStore调用该方法目的是为KeyValue的数据写入到MSLAB的Chunk中，size即为KeyValue的byte长度，即所需的空间
   // 返回的Allocation持有Chunk的字节数组，和offset用于记录从何处开始写入size大小的数据
  public Allocation allocateBytes(int size) {
    Preconditions.checkArgument(size >= 0, "negative size");

    // Callers should satisfy large allocations directly from JVM since they
    // don't cause fragmentation as badly.
    // 当KeyValue的大小超过maxAlloc时，不会将KeyValue存入到Chunk中
    if (size > maxAlloc) {
      return null;
    }

    while (true) {
      // 获取当前还没被写满的Chunk或者创建一个新的Chunk
      Chunk c = getOrMakeChunk();

      // Try to allocate from this chunk
      // 使用该Chunk分配size大小的空间
      int allocOffset = c.alloc(size);
      if (allocOffset != -1) {
        // We succeeded - this is the common case - small alloc
        // from a big buffer
        // allocOffset != -1代表Chunk仍然能分配出size大小的空间，直接返回Allocation实例
        return new Allocation(c.data, allocOffset);
      }

      // not enough space!
      // try to retire this chunk
      // 当前Chunk没有足够的空间分配，将当前的Chunk从MSLAB的引用中移出
      tryRetireChunk(c);
    }
  }

MemStoreLAB#getOrMakeChunk

上一步代码中获取当前Chunk或者创建新的Chunk

/**
   * Get the current chunk, or, if there is no current chunk,
   * allocate a new one from the JVM.
   */
  private Chunk getOrMakeChunk() {
    while (true) {
      // Try to get the chunk
      // curChunk持有当前正在使用的Chunk，curChunk为AtomicReference类型便于cas操作
      Chunk c = curChunk.get();
      if (c != null) {
        return c;
      }

      // No current chunk, so we want to allocate one. We race
      // against other allocators to CAS in an uninitialized chunk
      // (which is cheap to allocate)
      // 这里如果有开启Chunk的池化功能会从chunkPool里分配复用的Chunk，如果没有启用池化的话则会分配一个chunkSize大小(默认2MB)的Chunk实例
      c = (chunkPool != null) ? chunkPool.getChunk() : new Chunk(chunkSize);
      if (curChunk.compareAndSet(null, c)) {
        // we won race - now we need to actually do the expensive
        // allocation step
        c.init();
        this.chunkQueue.add(c);
        return c;
      } else if (chunkPool != null) {
        chunkPool.putbackChunk(c);
      }
      // someone else won race - that's fine, we'll try to grab theirs
      // in the next iteration of the loop.
    }
  }