alluxio.client.block.policy

Class CapacityBasedDeterministicHashPolicy

java.lang.Object

alluxio.client.block.policy.CapacityBasedDeterministicHashPolicy

All Implemented Interfaces:

BlockLocationPolicy

public class CapacityBasedDeterministicHashPolicy
extends Object
implements BlockLocationPolicy

A policy that pseudo-randomly distributes blocks between workers according to their capacity, so that the probability a worker is chosen is equal to the ratio of its capacity over total capacity of all workers, provided that the blocks requested follow a uniform distribution. If sharding is disabled, the same block is always assigned to the same worker. If sharding is enabled, the block is assigned to a fixed set of workers. The target worker is determined by the following algorithm: 1. build a cumulative distribution function by adding up all workers and their capacities. workers are sorted by their host name alphabetically. if worker A has 90 GB, B has 10 GB and C has 900 GB, the CDF looks like | 0 ... 90 | 90 ... 100 | 100 ... 1000 | | worker A | worker B | worker C | 2. find a fixed starting point in [0, totalCapacity) determined by the hashed block id. | 0 ... 90 | 90 ... 100 | 100 ... 1000 | | worker A | worker B | worker C | ^ start = 95 3. find the corresponding worker in the CDF. which is worker B in this example 4. if #shards = 1, this worker is selected. otherwise, find a set of candidates: 4.1 hashed_block_id(0) = block id 4.2 for i in [1, #shards], hashed_block_id(i) = hash(hashed_block_id(i-1)) 4.3 find the worker whose position corresponds to hashed_block_id(i) in the CDF, and add it to the candidates set 4.4 repeat 4.2 - 4.4 5. select a random worker in the candidate set The difference between this policy and CapacityBaseRandomPolicy is that this policy uses the hashed block ID as the index to choose the target worker, so that the same block is always routed to the same set of workers. Both this policy and DeterministicHashPolicy choose workers based the hashed block ID. The difference is that DeterministicHashPolicy uniformly distributes the blocks among the configured number of shards, while this policy chooses workers based on a distribution of their normalized capacity.

See Also:

CapacityBaseRandomPolicy, DeterministicHashPolicy

Nested Class Summary

Nested classes/interfaces inherited from interface alluxio.client.block.policy.BlockLocationPolicy

BlockLocationPolicy.Factory

Constructor Summary

Constructors

Constructor and Description
CapacityBasedDeterministicHashPolicy(AlluxioConfiguration conf) Constructor required by BlockLocationPolicy.Factory.create(Class, AlluxioConfiguration).

Method Summary

Modifier and Type	Method and Description
protected BlockWorkerInfo	getRandomCandidate(List<BlockWorkerInfo> candidates)
Optional<WorkerNetAddress>	getWorker(GetWorkerOptions options) Gets the worker's network address for serving operations requested for the block.
protected long	hashBlockId(long blockId)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CapacityBasedDeterministicHashPolicy

public CapacityBasedDeterministicHashPolicy(AlluxioConfiguration conf)

Constructor required by BlockLocationPolicy.Factory.create(Class, AlluxioConfiguration).

Parameters:

conf - Alluxio configuration

Method Detail

getWorker

public Optional<WorkerNetAddress> getWorker(GetWorkerOptions options)

Description copied from interface: BlockLocationPolicy

Gets the worker's network address for serving operations requested for the block.

Specified by:

getWorker in interface BlockLocationPolicy

Parameters:

options - the options to get a block worker network address for a block

Returns:

the address of the worker to write to, or empty if no worker can be selected

hashBlockId

protected long hashBlockId(long blockId)

getRandomCandidate

protected BlockWorkerInfo getRandomCandidate(List<BlockWorkerInfo> candidates)