@Test
  public void partitionLevelAdaptiveTrackerTest() throws Exception {
    MockPartitionId mockPartition1 = new MockPartitionId(0L, MockClusterMap.DEFAULT_PARTITION_CLASS);
    MockPartitionId mockPartition2 = new MockPartitionId(1L, MockClusterMap.DEFAULT_PARTITION_CLASS);
    for (int i = 0; i < REPLICA_COUNT; i++) {
      mockPartition1.replicaIds.add(new MockReplicaId(PORT, mockPartition1, datanodes.get(i % datanodes.size()), 1));
      mockPartition2.replicaIds.add(new MockReplicaId(PORT, mockPartition2, datanodes.get(i % datanodes.size()), 2));
    }
    MockClusterMap clusterMap =
        new MockClusterMap(false, datanodes, 3, Arrays.asList(mockPartition1, mockPartition2), localDcName);
    trackerScope = OperationTrackerScope.Partition;
    RouterConfig routerConfig = createRouterConfig(true, 2, 1, 6, null, true);
    NonBlockingRouterMetrics originalMetrics = routerMetrics;
    routerMetrics = new NonBlockingRouterMetrics(clusterMap, routerConfig);
    Counter pastDueCount = routerMetrics.getBlobPastDueCount;
    Map<Resource, CachedHistogram> localColoMap = routerMetrics.getBlobLocalDcResourceToLatency;
    Map<Resource, CachedHistogram> crossColoMap = routerMetrics.getBlobCrossDcResourceToLatency;
    // mock different distribution of Histogram for two partitions
    Histogram localHistogram1 = localColoMap.get(mockPartition1);
    Histogram localHistogram2 = localColoMap.get(mockPartition2);
    Histogram remoteHistogram1 = crossColoMap.get(mockPartition1);
    primeTracker(localHistogram1, routerConfig.routerOperationTrackerMinDataPointsRequired, new Pair<>(0L, 50L));
    primeTracker(localHistogram2, routerConfig.routerOperationTrackerMinDataPointsRequired, new Pair<>(100L, 120L));
    primeTracker(remoteHistogram1, routerConfig.routerOperationTrackerMinDataPointsRequired, new Pair<>(150L, 180L));
    OperationTracker tracker1 = getOperationTracker(routerConfig, mockPartition1);
    OperationTracker tracker2 = getOperationTracker(routerConfig, mockPartition2);
    double localColoCutoff1 = localHistogram1.getSnapshot().getValue(QUANTILE);
    double localColoCutoff2 = localHistogram2.getSnapshot().getValue(QUANTILE);
    double crossColoCutoff1 = remoteHistogram1.getSnapshot().getValue(QUANTILE);
    sendRequests(tracker2, 1);
    sendRequests(tracker1, 1);
    // partition1: 2-1-0-0, partition2: 2-1-0-0

    time.sleep((long) localColoCutoff1 + 1);
    // partition1 should send 2nd request, partition2 won't because its 1st request isn't past due.
    sendRequests(tracker1, 1);
    sendRequests(tracker2, 0);
    // partition1: 1-2-0-0, partition2: 2-1-0-0

    time.sleep((long) (localColoCutoff2 - localColoCutoff1) + 2);
    // note that localColoCutoff2 > 2 * localColoCutoff1, then 2nd request of partition1 and 1st request of partition are both past due
    sendRequests(tracker1, 1);
    sendRequests(tracker2, 1);
    // partition1: 0-3-0-0, partition2: 1-2-0-0

    time.sleep((long) localColoCutoff1 + 1);
    // 3rd local request of partition1 is past due and starts sending 1st cross-colo request
    sendRequests(tracker1, 1);
    sendRequests(tracker2, 0);
    // partition1: 0-3-0-0(local), 2-1-0-0(remote);  partition2: 1-2-0-0(local)

    time.sleep((long) crossColoCutoff1 + 1);
    // 1st cross-colo request of partition1 is past due and 2nd local request of partition2 is past due.
    sendRequests(tracker1, 1);
    sendRequests(tracker2, 1);
    // partition1: 0-3-0-0(local), 1-2-0-0(remote);  partition2: 0-3-0-0(local)

    // generate response for each request to make them successful
    for (int i = 0; i < 2; ++i) {
      assertFalse("Operation should not be done", tracker1.isDone() || tracker2.isDone());
      tracker1.onResponse(partitionAndInflightReplicas.get(mockPartition1).poll(), TrackedRequestFinalState.SUCCESS);
      tracker2.onResponse(partitionAndInflightReplicas.get(mockPartition2).poll(), TrackedRequestFinalState.SUCCESS);
    }
    assertTrue("Operation should have succeeded", tracker1.hasSucceeded() && tracker2.hasSucceeded());
    assertEquals("Past due counter is not expected", 4 + 2, pastDueCount.getCount());
    // complete remaining inflight requests and test different final state of request
    LinkedList<ReplicaId> inflightRequests1 = partitionAndInflightReplicas.get(mockPartition1);
    LinkedList<ReplicaId> inflightRequests2 = partitionAndInflightReplicas.get(mockPartition2);
    while (!inflightRequests1.isEmpty()) {
      tracker1.onResponse(inflightRequests1.poll(), TrackedRequestFinalState.FAILURE);
    }
    while (!inflightRequests2.isEmpty()) {
      tracker2.onResponse(inflightRequests2.poll(), TrackedRequestFinalState.TIMED_OUT);
    }
    // The number of data points in local colo histogram should be 5 (3 from partition1, 2 from partition2). Note that,
    // 3rd request of partition2 timed out which shouldn't be added to histogram.
    assertEquals("Mismatch in number of data points in local colo histogram", 5,
        routerMetrics.getBlobLocalDcLatencyMs.getCount());
    // The number of data points in cross colo histogram should be 2 (both of them come from partition1)
    assertEquals("Mismatch in number of data points in cross colo histogram", 2,
        routerMetrics.getBlobCrossDcLatencyMs.getCount());

    // additional test: mock new partition is dynamically added and adaptive operation track should be able to create
    // histogram on demand.
    MockPartitionId mockPartition3 = (MockPartitionId) clusterMap.createNewPartition(datanodes);
    OperationTracker tracker3 = getOperationTracker(routerConfig, mockPartition3);
    // send 1st request
    sendRequests(tracker3, 1);
    // attempt to send 2nd request to make tracker check histogram and create a new one associated with this partition
    // the oldest one hasn't passed due (because there are not enough data points in histogram), so 2nd is not sent
    sendRequests(tracker3, 0);
    tracker3.onResponse(partitionAndInflightReplicas.get(mockPartition3).poll(), TrackedRequestFinalState.SUCCESS);
    // now it should be able to send 2nd request
    sendRequests(tracker3, 1);
    tracker3.onResponse(partitionAndInflightReplicas.get(mockPartition3).poll(), TrackedRequestFinalState.SUCCESS);
    assertTrue("Operation should have succeeded", tracker3.hasSucceeded());

    // restore the tracer scope and routerMetrics
    trackerScope = OperationTrackerScope.Datacenter;
    routerMetrics = originalMetrics;
  }
Tests that adaptive tracker uses separate partition-level histogram to determine if inflight requests are past due.
@throws Exception
ambry-router/src/test/java/com/github/ambry/router/AdaptiveOperationTrackerTest.java