org.apache.druid.server.coordinator

Class CostBalancerStrategy

java.lang.Object

org.apache.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(org.apache.druid.timeline.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(org.apache.druid.timeline.DataSegment proposalSegment, ServerHolder server, boolean includeCurrentServer)
static double	computeJointSegmentsCost(org.apache.druid.timeline.DataSegment segmentA, org.apache.druid.timeline.DataSegment segmentB) This defines the unnormalized cost function between two segments.
void	emitStats(String tier, CoordinatorStats stats, List<ServerHolder> serverHolderList) Add balancing strategy stats during the 'balanceTier' operation of DruidCoordinatorBalancer to be included
ServerHolder	findNewSegmentHomeBalancer(org.apache.druid.timeline.DataSegment proposalSegment, List<ServerHolder> serverHolders) Find the best server to move a DataSegment to according the the balancing strategy.
ServerHolder	findNewSegmentHomeReplicator(org.apache.druid.timeline.DataSegment proposalSegment, List<ServerHolder> serverHolders) Find the best server on which to place a DataSegment replica according to the balancing strategy
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) Pick the best segment to move from one of the supplied set of servers according to the balancing strategy.
Iterator<ServerHolder>	pickServersToDrop(org.apache.druid.timeline.DataSegment toDrop, NavigableSet<ServerHolder> serverHolders) Returns an iterator for a set of servers to drop from, ordered by preference of which server to drop from first for a given drop strategy.

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(org.apache.druid.timeline.DataSegment segmentA,
                                              org.apache.druid.timeline.DataSegment segmentB)

This defines the unnormalized cost function between two segments. See https://github.com/apache/incubator-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(org.apache.druid.timeline.DataSegment proposalSegment,
                                                 List<ServerHolder> serverHolders)

Description copied from interface: BalancerStrategy

Find the best server on which to place a DataSegment replica according to the balancing strategy

Specified by:

findNewSegmentHomeReplicator in interface BalancerStrategy

Parameters:

proposalSegment - segment to replicate

serverHolders - servers to consider as replica holders

Returns:

The server to replicate to, or null if no suitable server is found

findNewSegmentHomeBalancer

public ServerHolder findNewSegmentHomeBalancer(org.apache.druid.timeline.DataSegment proposalSegment,
                                               List<ServerHolder> serverHolders)

Description copied from interface: BalancerStrategy

Find the best server to move a DataSegment to according the the balancing strategy.

Specified by:

findNewSegmentHomeBalancer in interface BalancerStrategy

Parameters:

proposalSegment - segment to move

serverHolders - servers to consider as move destinations

Returns:

The server to move to, or null if no move should be made or no server is suitable

pickSegmentToMove

public BalancerSegmentHolder pickSegmentToMove(List<ServerHolder> serverHolders)

Description copied from interface: BalancerStrategy

Pick the best segment to move from one of the supplied set of servers according to the balancing strategy.

Specified by:

pickSegmentToMove in interface BalancerStrategy

Parameters:

serverHolders - set of historicals to consider for moving segments

Returns:

BalancerSegmentHolder containing segment to move and server it current resides on

pickServersToDrop

public Iterator<ServerHolder> pickServersToDrop(org.apache.druid.timeline.DataSegment toDrop,
                                                NavigableSet<ServerHolder> serverHolders)

Description copied from interface: BalancerStrategy

Returns an iterator for a set of servers to drop from, ordered by preference of which server to drop from first for a given drop strategy. One or more segments may be dropped, depending on how much the segment is over-replicated.

Specified by:

pickServersToDrop in interface BalancerStrategy

Parameters:

toDrop - segment to drop from one or more servers

serverHolders - set of historicals to consider dropping from

Returns:

Iterator for set of historicals, ordered by drop preference

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)

Description copied from interface: BalancerStrategy

Add balancing strategy stats during the 'balanceTier' operation of DruidCoordinatorBalancer to be included

Specified by:

emitStats in interface BalancerStrategy

Parameters:

tier - historical tier being balanced

stats - stats object to add balancing strategy stats to

serverHolderList - servers in tier being balanced

computeCost

protected double computeCost(org.apache.druid.timeline.DataSegment proposalSegment,
                             ServerHolder server,
                             boolean includeCurrentServer)

chooseBestServer

protected Pair<Double,ServerHolder> chooseBestServer(org.apache.druid.timeline.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.