Better Prevent Read Outliers during short-term Bookie Slow-Down

[nicmichael]

BUG REPORT

Issue #709 introduced a feature to put bookies which didn't respond to a read request for speculativeReadTimeout ms (default: 2000 ms) on a "slowBookie" list, on which they remain for bookieFailureHistoryExpirationMSec ms (default: 60000). During this period, bookies on the slowBookie list will be put behind any non-slow bookie in "writeSet" that determines the read order. As a consequence, if a bookie has been slow just once, it will not be considered for further reads for 60 seconds. This pushes more load (potentially unnecessarily) onto other bookies in the ensemble. In some cases, this may overload the other bookies, which might then as a result hit the speculativeReadTimeout as well. In some cases, I've seen all bookies end up on the slowBookie list though none of them had any longer lasting performance issues. At that point, the read order is decided based on the number of outstanding requests of those bookies.

This might work well if bookies are slow for an extended period of time, but not if they only face a brief hickup. For example, we're setting speculativeReadTimeout = 30 to improve read latency and prevent outliers in case of slow bookies, for example due to Java GC in bookies (on the order of tens of ms) or any other short hickups bookies they may face. The current implementation does not address these needs adequately since it only detects slow bookies after speculativeReadTimeout ms (but not while a queue is building up on a bookie), and also puts bookies that have once been slow on the slowBookie list needlessly long without detecting whether or not the problem (e.g. Java GC) has been resolved.

We should have a feature that quicker reacts to short latency spikes or blocking of individual bookies, and quickly resumes directing load to them once the situation is resolved.

[nicmichael]

The plot below shows the behaviour of the current implementation with RackawareEnsemblePlacementPolicy for a scenario with 3 bookies and a speculativeReadTimeout of 30 ms. Ticks on the x axis are minutes.

Plot #1:

Shortly before minute 01, a read request on bookie 3 reached the speculativeReadTimeout, and bookie 3 is added to the slowBookie list. As a consequence, it received no further reads for the next minute (cyan curve drops to 0). Bookie 1 (green curve) sees its read rate double as a consequence. Before minute 02, the same happens to bookie 2 (magenta curve). Around minute 2:30 (until 4:00), overall read load increases on the bookies (not shown in graph). Shortly before minute 03, both bookie 2 and 3 are on the slowBookie list, and bookie 1 (green) is handling all the requests, which coincides with a steep increase in client-side response times (red curve). After minute 03, it is bookie 2 that's handling all requeest. This behaviour toggles between bookies several times.

Plot #2:

Shortly before minute 12, both bookies 1 (green) and 3 (cyan) hit the speculativeReadTimeout and are put on the slowBookie list, and all reads are redirected to bookie 2 (magenta). Neither bookie 1 or 3 had any longer-lasting performance problems, but both don't receive any reads for ~ 20 seconds, until bookie 2 - overloaded as it has to handle 3x the regular number of reads - also hits the speculativeReadTimeout. With all bookies on the slowBookies list, it is now bookie 3 that gets selected based on number of pending requests, then also bookie 1, while bookie 2 remains on the slowBookie list for a whole minute.

I have implemented a slightly different strategy to better deal with short latency spikes. When enabled, it deactivates the current slowBookie list implementation and instead reorders the read set based on the number of pending requests to each bookie based on a configurable threshold. The idea is that on average, all bookies should receive a similar rate of requests, and should (if they operate equally fast) have a similar number of outstanding requests. An increase in outstanding requests one one bookie relative to others indicates that it might have an issue - e.g. responding slower or for a brief time (e.g. during a Java GC) not responding at all. Once the primary bookie's number of outstanding requests is too large compared to other bookies in the ensemble, we direct the read request to the bookie with the shortest queue length.

Setting the threshold very low will more frequently reorder the read set and potentially result in better latency, but will also reduce data affinity of reads. Reads send to other than the preferred bookie have a low chance to be served from file system cache on that bookie, and will likely result in a physical read. Small thresholds therefore shuffle read requests more among bookies and may lead to reduced file system cache reach and increased physical reads on disks.

A larger timeout will maintain data affinity and avoid above problems, but only kick in once a bookie has built-up a considerable queue of requests. It therefore masks only slightly larger outliers, and leads to overall better efficiency.

Using the number of pending requests to a bookie is a good proxy for each bookies current performance, as it reacts quickly to any change in behavior. For example, if a bookie is blocked for ~ 25 ms for a Java GC, the number of outstanding requests will (depending on requests rate) quickly increase - typically within few ms - and after exceeding the threshold prevent further requests being sent to that bookie. Once the bookie resumes work (e.g. Java GC completed), its queue will drain quickly below the threshold, and it can receive further requests. Note that alternative approaches such as a moving average of response times would not achieve this (during Java GC, a bookie doesn't respond, so we only get slow responses once the problem - Java GC - has been resolved).

Below are two plots illustrating how a threshold of 100 (with slowBookie list disabled) behaves in comparison, and avoids redirection of all traffic to single bookies for any extended period of time. In my experiements, this implementation improves client-side response times by 4% (avg) and 14% (99th percentile), and reduces proxy READ_ENTRY times by 5% avg. A threshold of 10 reorders slightly more frequent, but does not lead to overall (measurably)

[sijie]

/cc @philipsu522 @yzang for awareness :)

[sijie]

Using the number of pending requests to a bookie is a good proxy for each bookies current performance, as it reacts quickly to any change in behavior.

@nicmichael +1 on using the number of pending requests. that is a good approach. the results look promising.

[philipsu522]

Results look good!