# CoSky Load Balancing Algorithms: ArrayWeightRandom vs BinaryWeightRandom vs TreeWeightRandom > Explore CoSky load balancing algorithms: ArrayWeightRandom, BinaryWeightRandom, and TreeWeightRandom. Understand their O(1) or O(log n) selection speeds and memory trade-offs to optimize your system. - Repository: [Ahoo Wang/cosky](https://github.com/ahoo-wang/cosky) - Tags: deep-dive - Published: 2026-02-23 --- **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`](https://github.com/ahoo-wang/cosky/blob/main/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`](https://github.com/ahoo-wang/cosky/blob/main/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`](https://github.com/ahoo-wang/cosky/blob/main/TreeWeightRandomLoadBalancer.kt), uses Java's `TreeMap` for weighted selection. ### Balanced Tree Structure This algorithm populates a `TreeMap` 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` | O(1) | O(totalWeight) | Low total weights, maximum speed | | **BinaryWeightRandom** | `IntArray` (cumulative) | O(log n) | O(n) | Large weights, memory-constrained environments | | **TreeWeightRandom** | `TreeMap` | 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`](https://github.com/ahoo-wang/cosky/blob/main/application.yml): ```yaml 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: ```kotlin 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`](https://github.com/ahoo-wang/cosky/blob/main/ArrayWeightRandomLoadBalancer.kt). - **BinaryWeightRandom** uses cumulative weights and binary search to achieve O(log n) complexity with O(n) memory, implemented in [`BinaryWeightRandomLoadBalancer.kt`](https://github.com/ahoo-wang/cosky/blob/main/BinaryWeightRandomLoadBalancer.kt). - **TreeWeightRandom** leverages `TreeMap` navigation for O(log n) selection, suitable for ordered access scenarios, found in [`TreeWeightRandomLoadBalancer.kt`](https://github.com/ahoo-wang/cosky/blob/main/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`](https://github.com/ahoo-wang/cosky/blob/main/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`](https://github.com/ahoo-wang/cosky/blob/main/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.