CoSky Load Balancing Algorithms: ArrayWeightRandom vs BinaryWeightRandom vs TreeWeightRandom

ArrayWeightRandom provides O(1) selection speed by expanding instances into a weighted array, while BinaryWeightRandom and TreeWeightRandom offer O(log n) selection with O(n) memory using cumulative weights and binary search or TreeMap navigation.

CoSky is a high-performance service discovery and configuration platform designed for distributed systems. When routing requests across multiple service instances, selecting the appropriate CoSky load balancing algorithm directly impacts both memory consumption and request latency. This article examines the three weighted random implementations—ArrayWeightRandom, BinaryWeightRandom, and TreeWeightRandom—available in the cosky-discovery module to help you choose the right strategy for your workload.

Overview of CoSky Load Balancing

All three algorithms extend AbstractLoadBalancer and implement the LoadBalancer.Chooser interface defined in cosky-discovery. They share common validation logic: if the instance collection is empty, if the total weight is zero, or if only one instance exists, the chooser handles these edge cases immediately before applying the weighted selection logic.

Each implementation uses ThreadLocalRandom for thread-safe random number generation and relies on the ServiceInstance weight property to determine selection probability.

ArrayWeightRandom: O(1) Selection with Expanded Arrays

The ArrayWeightRandom algorithm, implemented in ArrayWeightRandomLoadBalancer.kt, prioritizes selection speed over memory efficiency.

How ArrayWeightRandom Works

This algorithm expands the instance list into a flat array called instanceLine where each instance appears proportionally to its weight. If instance A has weight 3 and instance B has weight 1, the array contains [A, A, A, B]. Selection requires only a single random index generation and direct array access.

Performance Characteristics

• Time Complexity: O(1) — one ThreadLocalRandom.nextInt(0, totalWeight) call and array lookup.
• Memory Overhead: O(totalWeight) — the array size equals the sum of all instance weights, which can consume significant memory if weights are large.
• Best For: Scenarios with modest total weights where raw selection speed is critical.

BinaryWeightRandom: Memory-Efficient Binary Search

The BinaryWeightRandom algorithm, found in BinaryWeightRandomLoadBalancer.kt, offers a balanced approach using cumulative weights and binary search.

Cumulative Weight Strategy

Instead of expanding instances into an array, this algorithm maintains an IntArray called weightLine containing cumulative weights. For instances with weights [3, 1, 2], the cumulative array stores [3, 4, 6]. A random number between 0 and totalWeight-1 is generated, and Arrays.binarySearch locates the corresponding instance index.

Complexity Trade-offs

• Time Complexity: O(log n) — binary search on the cumulative array where n is the instance count.
• Memory Overhead: O(n) — stores one integer per instance regardless of weight magnitude.
• Best For: Environments with many instances or large weight values where memory efficiency matters more than microsecond-level selection latency.

TreeWeightRandom: TreeMap-Based Navigation

The TreeWeightRandom implementation, located in TreeWeightRandomLoadBalancer.kt, uses Java's TreeMap for weighted selection.

Balanced Tree Structure

This algorithm populates a TreeMap<Int, ServiceInstance> where each key represents a cumulative weight and the value is the corresponding instance. To select an instance, it generates a random weight value and calls TreeMap.tailMap(random).firstEntry() to find the smallest cumulative weight greater than the random value.

When to Use TreeMap

• Time Complexity: O(log n) — tailMap operations on the balanced red-black tree.
• Memory Overhead: O(n) — one map entry per instance with tree node overhead.
• Best For: Applications already utilizing sorted map structures or requiring ordered navigation of weighted entries for debugging or monitoring purposes.

Comparing CoSky Load Balancing Algorithms

Algorithm	Data Structure	Selection Complexity	Memory Usage	Ideal Scenario
ArrayWeightRandom	Array<ServiceInstance>	O(1)	O(totalWeight)	Low total weights, maximum speed
BinaryWeightRandom	IntArray (cumulative)	O(log n)	O(n)	Large weights, memory-constrained environments
TreeWeightRandom	TreeMap<Int, ServiceInstance>	O(log n)	O(n)	Existing TreeMap usage, ordered access needs

All three implementations handle edge cases identically: empty instance lists return null with a warning log, zero total weight returns null, and single-instance scenarios return that instance directly without random selection.

Configuration and Usage Examples

Spring Boot Configuration

When using cosky-spring-cloud-starter-discovery, configure the algorithm via application.yml:

cosky:
  discovery:
    load-balancer: binary  # Options: array, binary, tree

The CoSkyDiscoveryAutoConfiguration class automatically wires the selected LoadBalancer implementation based on this property.

Programmatic Usage

Instantiate load balancers directly when not using Spring Cloud:

import me.ahoo.cosky.discovery.loadbalancer.*

// Prerequisites
val serviceDiscovery: ServiceDiscovery = // your discovery client
val eventContainer: InstanceEventListenerContainer = // your event container

// ArrayWeightRandom - fastest selection
val arrayLb = ArrayWeightRandomLoadBalancer(serviceDiscovery, eventContainer)
val instance1 = arrayLb.choose()

// BinaryWeightRandom - memory efficient
val binaryLb = BinaryWeightRandomLoadBalancer(serviceDiscovery, eventContainer)
val instance2 = binaryLb.choose()

// TreeWeightRandom - TreeMap based
val treeLb = TreeWeightRandomLoadBalancer(serviceDiscovery, eventContainer)
val instance3 = treeLb.choose()

All choosers return ServiceInstance? (nullable) and handle weight calculations internally based on instance metadata.

Summary

• ArrayWeightRandom expands weighted instances into a flat array for O(1) selection speed, trading memory for performance in ArrayWeightRandomLoadBalancer.kt.
• BinaryWeightRandom uses cumulative weights and binary search to achieve O(log n) complexity with O(n) memory, implemented in BinaryWeightRandomLoadBalancer.kt.
• TreeWeightRandom leverages TreeMap navigation for O(log n) selection, suitable for ordered access scenarios, found in TreeWeightRandomLoadBalancer.kt.
• All three extend AbstractLoadBalancer and share common edge-case handling for empty lists, zero weights, and single instances.
• Configure your preferred algorithm via cosky.discovery.load-balancer in Spring Boot, or instantiate the specific LoadBalancer implementation directly in Kotlin code.

Frequently Asked Questions

Which CoSky load balancing algorithm should I use for high-throughput services?

ArrayWeightRandom is the optimal choice for high-throughput scenarios because it provides O(1) selection complexity through direct array indexing. According to the implementation in ArrayWeightRandomLoadBalancer.kt, this algorithm performs only a single ThreadLocalRandom.nextInt() call and array access per request, minimizing CPU overhead at the expense of higher memory usage proportional to the total weight sum.

How does CoSky handle instances with zero weight in these algorithms?

All three algorithms validate the total weight before selection. As implemented in the shared logic of AbstractLoadBalancer, if the cumulative weight of all instances equals zero, the chooser returns null and logs a warning. Individual instances with zero weight contribute nothing to the selection probability and are effectively excluded from the routing pool.

Can I switch between load balancing algorithms without restarting my application?

When using Spring Cloud CoSky, you can change the cosky.discovery.load-balancer property value (array, binary, or tree) and the CoSkyDiscoveryAutoConfiguration will reconfigure the LoadBalancer bean accordingly. For programmatic usage, you must instantiate a new load balancer instance, though you can implement a factory pattern to enable runtime switching between ArrayWeightRandomLoadBalancer, BinaryWeightRandomLoadBalancer, and TreeWeightRandomLoadBalancer.

What is the memory overhead difference between ArrayWeightRandom and BinaryWeightRandom?

ArrayWeightRandom consumes memory proportional to O(totalWeight) because it expands each instance into an array slot repeated according to its weight, as seen in ArrayWeightRandomLoadBalancer.kt. In contrast, BinaryWeightRandom stores only one integer per instance in its cumulative weight array, resulting in O(n) memory usage regardless of weight magnitude. For scenarios with large weight values (e.g., weights of 1000+), BinaryWeightRandom typically consumes significantly less memory than ArrayWeightRandom.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}