本期分享主题：《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 智库]：
相关文章
