kv: Lead Support Calculator (LSC)

# Lead Support Calculator (LSC)

Currently, each leader replica on every tick calculates the LeadSupportUntil (LSU). The calculation itself is not very expensive. However, given that each leader ticks twice a second. Dense nodes (with tens of thousands of leaders) by definition will end up calculating the LSU tens of thousands of times a second.

## Observations

* **The same work is done many times:**If we have a small number of stores, and a large number of replicas, a lot of those replicas will be in the same store. For example, if we only have 3 stores (and the replication factor is 3), all leaders on store 1 will have followers on stores 2 and 3. All the leaders on store 1 will have to do more or less the same calculation to get the LeadSupportUntil.
* **LSU calculation is coupled with raft ticks:** Right now, we tick each replica twice a second. We also calculate the LSU twice a second since we calculate it once per tick. However, this isn’t really necessary. Maybe doing this calculation once a second is enough.
* **LSU doesn’t regress:** If leader X knows that it’s LSU is set for time Y, it won’t happen that suddenly, the LSU for leader X will become something lower than Y.

## Proposal

This document proposes adding a small component called LeadSupportCalculator (LSC) that sits between the replicas and store liveness. Fortified raft leaders could offload calculating the LSU to this new component. This achieves 3 main benefits:

**1. Limit redundant work:**The LSC knows what are the stores all the leaders need in order to calculate the LSU. Therefore, the LSC will only calculate the necessary LSU to satisfy all leaders on that store.
**2. Decouples ticks from LSU calculations:** In the future, we might need to double the number of raft ticks per second. We probably don’t need to double the LSU calculations as well. Adding this extra component can help decouple the two concepts.
**3. Opens the door to leader-lease leader quiescence:** One of the things we need to resolve before implementing leader-lease leader quiescence is who will calculate the LSU when the leader is quiesced? The LSC could take that responsibility.

Figure 1 compares the current way replicas interact with store liveness to calculate the LSU with the proposed way of how that interaction goes.

Figure 1.a The current interaction with store liveness to calculate LSU.

Figure 1.b The proposed interaction with store liveness to calculate LSU.

## Proposed API

* **Register(store set):** The fortified leader calls this function to offload calculating the LSU to the LSC. The leader specifies the set of stores that fortify the leader.
* **Unregister(store set):** The leader calls this function when no longer needing to calculate the LSU. For example, if there is a config change, or if the leader is no longer fortified. Note that the LSC might still calculate the LSU for that store set if there are other leaders who want it. You can imagine the LSC having a reference counter for each store set requested.
* **GetLSU(store set, fresh):** The leader calls this function if it needs the LSU for a given store set. The LSC will respond with the latest calculated LSU value for that store set, calculating it if it wasn’t calculated yet. Also, the leader could specify a boolean called fresh, which forces the LSC to redo the calculation. This might be useful in some cases where the leader can’t tolerate a slightly stale LSU.

## General Design Points

* The LSC will contain a hash map called *RegisteredStores* that maps a StoreSet into a struct that contains {LSU, timestamp when it was computed last}.
* Every 500ms (configurable), the LSC would visit all registered store sets, updating its LSU.

## Theoretical Improvements

Figures 2.a and b show the theoretical improvements with the proposed approach. Figure 2.a Shows that as the number of leaders increase, the number of LSU calculations remains constant, since more leaders mean that they will have followers on the same stores as other leaders.

Figure 2.b shows that fixing the number of leaders per store, adding more stores reduces the chance of the proposed approach of reusing a previous LSU calculation, since it’s unlikely that the multiple leaders have followers on the same stores. 

Note that in the graphs, we fixed the replication factor to 3. Also, the graph assumes uniform distribution of followers, which is not true in reality as zone configs might restrict replicas from being distributed uniformly, making the optimization even better.

Figure 2.a. Comparing the current number of LSU calculations against the proposed approach. The number of stores is set to 100, and varying the number of leaders per store.

Figure 2.b. Comparing the current number of LSU calculations against the proposed approach. The number of leaders per store is set to 50,000, and we are varying the number of stores in the cluster.

**CPU utilization improvements**

Taking an example of having a very dense number of replicas per vCPU (imagine tiered storage) of 120K replicas per vCPU. One third of them are leaders. So the **number of leaders per vCPUs = 40K.**

If each calculation takes about **150ns**, we perform the calculation twice every second. Currently, doing the calculation would consume **1.2% vCPU utilization**.

Note that the CPU improvement is not the biggest gain from the LSC. Opening the door the leader-leases leader quiescence, and decoupling ticks with LSU calculation are stronger benefits than just CPU improvements from caching the LSU.

Jira issue: CRDB-49160