How to estimate the median response time of a service with a large volume of logs that do not fit into memory?

To estimate the median response time of a service with large logs that do not fit into memory, streaming algorithms can be used. One approach is the 'Selection Algorithm' with limited memory or approximate methods, such as T-Digest or P² (P-square) for quantile estimation.

An approximate approach:

1. Read logs in parts (chunks), processing each record sequentially.
2. For each response time, update a data structure that stores an approximate distribution.
3. After processing, obtain an approximate median value without storing all data.

This allows efficient handling of large data and obtaining the median with acceptable accuracy.

If using Python, the tdigest library can be applied:

from tdigest import TDigest
tdigest = TDigest()

with open('logs.txt') as f:
    for line in f:
        response_time = float(line.strip())  # assuming each line contains response time
        tdigest.update(response_time)

median = tdigest.percentile(50)
print(f"Median response time: {median}")

This approach scales and is suitable for streaming large volumes of data.