io.druid.server.coordinator

Class CostBalancerStrategy

java.lang.Object

io.druid.server.coordinator.CostBalancerStrategy

All Implemented Interfaces:

BalancerStrategy

Direct Known Subclasses:

CachingCostBalancerStrategy, DiskNormalizedCostBalancerStrategy

public class CostBalancerStrategy
extends Object
implements BalancerStrategy

Constructor Summary

Constructors

Constructor and Description
CostBalancerStrategy(com.google.common.util.concurrent.ListeningExecutorService exec)

Method Summary

Modifier and Type	Method and Description
double	calculateInitialTotalCost(List<ServerHolder> serverHolders) Calculates the initial cost of the Druid segment configuration.
double	calculateNormalization(List<ServerHolder> serverHolders) Calculates the cost normalization.
protected Pair<Double,ServerHolder>	chooseBestServer(DataSegment proposalSegment, Iterable<ServerHolder> serverHolders, boolean includeCurrentServer) For assignment, we want to move to the lowest cost server that isn't already serving the segment.
protected double	computeCost(DataSegment proposalSegment, ServerHolder server, boolean includeCurrentServer)
static double	computeJointSegmentsCost(DataSegment segmentA, DataSegment segmentB) This defines the unnormalized cost function between two segments.
void	emitStats(String tier, CoordinatorStats stats, List<ServerHolder> serverHolderList)
ServerHolder	findNewSegmentHomeBalancer(DataSegment proposalSegment, List<ServerHolder> serverHolders)
ServerHolder	findNewSegmentHomeReplicator(DataSegment proposalSegment, List<ServerHolder> serverHolders)
static double	intervalCost(double x1, double y0, double y1) Computes the joint cost of two intervals X = [x_0 = 0, x_1) and Y = [y_0, y_1) cost(X, Y) = \int_{x_0}^{x_1} \int_{y_0}^{y_1} e^{-\lambda |x-y|}dxdy $$ lambda = 1 in this particular implementation Other values of lambda can be calculated by multiplying inputs by lambda and multiplying the result by 1 / lambda ^ 2 Interval start and end are all relative to x_0.
BalancerSegmentHolder	pickSegmentToMove(List<ServerHolder> serverHolders)

Methods inherited from class java.lang.Object

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

Constructor Detail

CostBalancerStrategy

public CostBalancerStrategy(com.google.common.util.concurrent.ListeningExecutorService exec)

Method Detail

computeJointSegmentsCost

public static double computeJointSegmentsCost(DataSegment segmentA,
                                              DataSegment segmentB)

This defines the unnormalized cost function between two segments. See https://github.com/druid-io/druid/pull/2972 for more details about the cost function. intervalCost: segments close together are more likely to be queried together multiplier: if two segments belong to the same data source, they are more likely to be involved in the same queries

Parameters:

segmentA - The first DataSegment.

segmentB - The second DataSegment.

Returns:

the joint cost of placing the two DataSegments together on one node.

intervalCost

public static double intervalCost(double x1,
                                  double y0,
                                  double y1)

Computes the joint cost of two intervals X = [x_0 = 0, x_1) and Y = [y_0, y_1) cost(X, Y) = \int_{x_0}^{x_1} \int_{y_0}^{y_1} e^{-\lambda |x-y|}dxdy $$ lambda = 1 in this particular implementation Other values of lambda can be calculated by multiplying inputs by lambda and multiplying the result by 1 / lambda ^ 2 Interval start and end are all relative to x_0. Therefore this function assumes x_0 = 0, x1 >= 0, and y1 > y0

Parameters:

x1 - end of interval X

y0 - start of interval Y

y1 - end o interval Y

Returns:

joint cost of X and Y

findNewSegmentHomeReplicator

public ServerHolder findNewSegmentHomeReplicator(DataSegment proposalSegment,
                                                 List<ServerHolder> serverHolders)

Specified by:

findNewSegmentHomeReplicator in interface BalancerStrategy

findNewSegmentHomeBalancer

public ServerHolder findNewSegmentHomeBalancer(DataSegment proposalSegment,
                                               List<ServerHolder> serverHolders)

Specified by:

findNewSegmentHomeBalancer in interface BalancerStrategy

pickSegmentToMove

public BalancerSegmentHolder pickSegmentToMove(List<ServerHolder> serverHolders)

Specified by:

pickSegmentToMove in interface BalancerStrategy

calculateInitialTotalCost

public double calculateInitialTotalCost(List<ServerHolder> serverHolders)

Calculates the initial cost of the Druid segment configuration.

Parameters:

serverHolders - A list of ServerHolders for a particular tier.

Returns:

The initial cost of the Druid tier.

calculateNormalization

public double calculateNormalization(List<ServerHolder> serverHolders)

Calculates the cost normalization. This is such that the normalized cost is lower bounded by 1 (e.g. when each segment gets its own historical node).

Parameters:

serverHolders - A list of ServerHolders for a particular tier.

Returns:

The normalization value (the sum of the diagonal entries in the pairwise cost matrix). This is the cost of a cluster if each segment were to get its own historical node.

emitStats

public void emitStats(String tier,
                      CoordinatorStats stats,
                      List<ServerHolder> serverHolderList)

Specified by:

emitStats in interface BalancerStrategy

computeCost

protected double computeCost(DataSegment proposalSegment,
                             ServerHolder server,
                             boolean includeCurrentServer)

chooseBestServer

protected Pair<Double,ServerHolder> chooseBestServer(DataSegment proposalSegment,
                                                     Iterable<ServerHolder> serverHolders,
                                                     boolean includeCurrentServer)

For assignment, we want to move to the lowest cost server that isn't already serving the segment.

Parameters:

proposalSegment - A DataSegment that we are proposing to move.

serverHolders - An iterable of ServerHolders for a particular tier.

Returns:

A ServerHolder with the new home for a segment.