乐趣区

关于腾讯:当内卷风波及代码领域看Alluxio将会采取怎样的块分配策略

jiezi

本期分享主题：《Alluxio 块调配策略详解》
全文次要围绕 3 个局部进行介绍：【策略详解概述】、【块调配策略介绍】、【代码层面解读】
话不多说，间接上干货↓

策略详解概述

Alluxio 的 Worker 负责存储用户的数据资源，并且数据会以 Block 模式存储在 Worker 的存储目录 (tiered storage) 中，而存储目录能够有 MEM/SSD/HDD 等多个不同的 level，同一 level 又能够由多个目录组成，那么当用户通过 Alluxio 读写数据的时候，Alluxio 又是如何决定要把一个 Block 放在哪一个目录中呢？本文就从代码角度来剖析一下 Block 存储目录的选取流程。

块调配策略介绍

Alluxio 应用块调配策略(Block Allocation Policies) 来定义如何在多个存储目录（同一层或不同层）中调配 Block。

目前 Alluxio 的块调配策略次要有 3 种：

alluxio.worker.block.allocator.GreedyAllocator
从顶层到底层，将 Block 调配到第一个可能包容 Block 的存储目录中。
alluxio.worker.block.allocator.MaxFreeAllocator
将 Block 调配到残余可用空间最大的存储目录中。
alluxio.worker.block.allocator.RoundRobinAllocator
从顶层到底层，循环将 Block 放入每一个存储目录中。
默认应用的策略是 MaxFreeAllocator，这能够通过 property alluxio.worker.allocator.class 来更改。

代码层面解读

allocateSpace
代码层面负责给 Block 调配存储目录的函数是 allocateSpace。
当读写数据时，如果须要在 Worker 中存储数据, 会依照 Block Allocation Policies 来为 Block 申请一个存储目录来保留数据，allocateSpace 首先会尝试在传入参数 options 中指定的地位 (默认是 level0) 中寻找，如果指定地位没有找到适合的空间，则会尝试在所有的存储目录中寻找。

private StorageDirView allocateSpace(long sessionId, AllocateOptions options)
      throws WorkerOutOfSpaceException, IOException {while (true) {if (options.isForceLocation()) {//...} else {
            //...
            dirView = mAllocator.allocateBlockWithView(sessionId, options.getSize(),
                options.getLocation(), allocatorView, false);
            if (dirView != null) {return dirView;}
            dirView = mAllocator.allocateBlockWithView(sessionId, options.getSize(),
                BlockStoreLocation.anyTier(), allocatorView, false);
            if (dirView != null) {return dirView;}
      }
        //...
}

能够看到，上文讲述的 allocateSpace 所选取的存储目录是通过动静计算所失去的，然而在某些时候, 也须要数据能够写入指定的存储目录或者 level，所以 allocateSpace 也反对通过 evict Block 来让某一个存储目录腾出足够的空间以包容新的数据(这里后文会具体介绍)。

private StorageDirView allocateSpace(long sessionId, AllocateOptions options) {
    StorageDirView dirView;
//...
    while (true) {if (options.isForceLocation()) {dirView = mAllocator.allocateBlockWithView(sessionId, options.getSize(),
            options.getLocation(), allocatorView, true);
        if (dirView != null) {return dirView;}
        freeSpace(sessionId, options.getSize(), options.getSize(), options.getLocation());
        dirView = mAllocator.allocateBlockWithView(sessionId, options.getSize(),
                      options.getLocation(), allocatorView.refreshView(), true);        
        //...
        }
      }
      //...
      } else {//...}
      return dirView;
    }
  }

从 allocateSpace 中具体寻找适合存储目录的类就是 Allocator 接口的几个实现类，也就是上一章节中提出的几个块调配策略：GreedyAllocator/MaxFreeAllocator/RoundRobinAllocator

Allocator

public interface Allocator {

  //...
  StorageDirView allocateBlockWithView(long sessionId, long blockSize, BlockStoreLocation location,
        BlockMetadataView view, boolean skipReview);
}

Allocator 接口中的 allocateBlockWithView 次要负责寻找适合的存储目录，须要关注的参数次要有 3 个：
✓ blockSize: 想要调配多大的空间
✓ location: 想要在哪调配空间
✓ skipReview: 是否跳过 Review
以默认的 alluxio.worker.block.allocator.MaxFreeAllocator#MaxFreeAllocator 为例，能够看到如果想要在所有的地位寻找存储目录，那么它就一一查看所有存储目录，并返回最大的那个：

private StorageDirView allocateBlock(long sessionId, long blockSize,
      BlockStoreLocation location, boolean skipReview) {if (location.equals(BlockStoreLocation.anyTier())) {for (StorageTierView tierView : mMetadataView.getTierViews()) {candidateDirView = getCandidateDirInTier(tierView, blockSize, BlockStoreLocation.ANY_MEDIUM);
        if (candidateDirView != null) { // Review
          if (skipReview || mReviewer.acceptAllocation(candidateDirView)) {break;}
        }
      }
    } 
    //...
    return candidateDirView;
  }

private StorageDirView getCandidateDirInTier(StorageTierView tierView,
      long blockSize, String mediumType) {
    StorageDirView candidateDirView = null;
    long maxFreeBytes = blockSize - 1;
    for (StorageDirView dirView : tierView.getDirViews()) {if ((mediumType.equals(BlockStoreLocation.ANY_MEDIUM)
          || dirView.getMediumType().equals(mediumType))
          && dirView.getAvailableBytes() > maxFreeBytes) {maxFreeBytes = dirView.getAvailableBytes();
        candidateDirView = dirView;
      }
    }
    return candidateDirView;
  }

从代码中能够看到，当找到 candidateDirView 后，还须要通过一个 Review 的流程, 能力最终决定返回哪个存储目录，那么 Review 的流程又有什么用呢？

Block Allocation Review Policies
Review 是对块调配策略的一种补充，它给块调配策略带来了一些额定的限度 (例如 SoftLimit/HardLimit) 以及肯定随机性。目前 Alluxio 有两 Review 策略：

alluxio.worker.block.reviewer.AcceptingReviewer
间接通过所有 Review，相当于没有进行 Review
alluxio.worker.block.reviewer.ProbabilisticBufferReviewer
会依据以后的可用空间残余大小来 Reviewer 之前的调配后果
以默认的 ProbabilisticBufferReviewer 来看：

public class ProbabilisticBufferReviewer implements Reviewer {
    //...
    double getProbability(StorageDirView dirView) {
        //...
        if (availableBytes > mSoftLimitBytes) {return 1.0;}
        if (availableBytes <= mHardLimitBytes) {return 0.0;}
    
        double x = capacityBytes - availableBytes;
        double k = 1.0 / (mHardLimitBytes - mSoftLimitBytes); // If HardLimit = SoftLimit, then we would have returned in the previous if-else
        double b = (capacityBytes - mHardLimitBytes + 0.0) / (mSoftLimitBytes - mHardLimitBytes);
        double y = k * x + b;
        return y;
      }
}

ProbabilisticBufferReviewer

如果以后的存储目录残余空间小于 mHardLimitBytes，那么就会间接返回 0，示意未通过 review ;
如果以后的存储目录残余空间大于 mSoftLimitBytes，那么就会间接返回 1，示意通过 review ;
如果残余空间大小介于 mHardLimitBytes 与 mSoftLimitBytes 之间，那么就会返回 (0, 1) 之间的一个值。
freeSpace
上文中提到 allocateSpace 反对通过 evict Block 来让某一个存储目录腾出足够的空间以包容新的数据。那么当进行 evict 的时候，又是如何决定该 evict 哪一个 Block 呢？

evict Block 是通过 freeSpace 实现的，如果空间有余，在 freeSpace 中会一一淘汰 Block，直到腾出了足够的空间。

public synchronized void freeSpace(long sessionId, long minContiguousBytes,
      long minAvailableBytes, BlockStoreLocation location) {Iterator<Long> evictionCandidates = mBlockIterator.getIterator(location, BlockOrder.NATURAL);
    while (true) {
      //...
      if (contiguousSpaceFound && availableBytesFound) {break;}

      if (!evictionCandidates.hasNext()) {break;}
      long blockToDelete = evictionCandidates.next();
      if (evictorView.isBlockEvictable(blockToDelete)) { // 有一些 block 是不会被 evict 的
        try {BlockMeta blockMeta = mMetaManager.getBlockMeta(blockToDelete);
          removeBlockFileAndMeta(blockMeta);
          //...
      }
    //...
  }

当然, 有一些 block 不会被 evict：

public boolean isBlockEvictable(long blockId) {boolean pinned = isBlockPinned(blockId);
    boolean locked = isBlockLocked(blockId);
    boolean marked = isBlockMarked(blockId);
    boolean isEvictable = !pinned && !locked && !marked;
    if (!isEvictable) {LOG.debug("Block not evictable: {}. Pinned: {}, Locked: {}, Marked: {}", blockId, pinned,
          locked, marked);
    }

    return isEvictable;
  }

evict 的规定目前有 2 种：

alluxio.worker.block.annotator.LRUAnnotator
LRU 规定, 即首先会被淘汰的是最久未被拜访的
alluxio.worker.block.annotator.LRFUAnnotator
可能以 LRFU 与 LRU 的规定联合, 也能够通过参数让该规定靠近 LRFU 或者 LRU
默认应用的策略是 LRUAnnotator，这能够通过 property alluxio.worker.block.annotator.class 来更改。
以默认的 LRUAnnotator 来看：

public class LRUAnnotator implements BlockAnnotator<LRUAnnotator.LRUSortedField> {private static final Logger LOG = LoggerFactory.getLogger(LRUAnnotator.class);

  private AtomicLong mLRUClock;

  @Override
  public BlockSortedField updateSortedField(long blockId, LRUSortedField oldValue) {long clockValue = mLRUClock.incrementAndGet();
    return new LRUSortedField(clockValue);
  }

  /**
   * Sorted-field for LRU.
   */
  protected class LRUSortedField implements BlockSortedField {
    private Long mClockValue;

    private LRUSortedField(long clockValue) {mClockValue = clockValue;}

    @Override
    public int compareTo(BlockSortedField o) {Preconditions.checkState(o instanceof LRUSortedField);
      return mClockValue.compareTo(((LRUSortedField) o).mClockValue);
    }
    //...
}

能够看到 LRUAnnotator 外部通过一个枯燥递增的 AtomicLong 来标识每个 Block 的拜访程序，AtomicLong 越大，代表越先被拜访。

想要获取更多乏味有料的【流动信息】【技术文章】【大咖观点】，请关注[Alluxio 智库]：

退出移动版