Как считается медиана с помощью MapReduce

Что проверяют

Понимаете ли вы, что медиана не раскладывается на частичные результаты, как сумма или среднее, и поэтому в MapReduce не считается в один честный проход. Наивное решение с одним ключом интервьюер принимает как отправную точку, а дальше спрашивает, что будет на миллиарде строк и устроит ли приближённый ответ.

Как отвечать

Сначала покажите наивный вариант и назовите его проблему: все числа уходят под один ключ, значит в один редьюсер, который должен удержать и отсортировать всё в памяти. Параллелизма нет, на больших данных это падение по памяти.

Потом рабочие подходы:

• гистограмма в два прохода: map выдаёт номер корзины (диапазона значений) и единицу, combiner и reduce суммируют счётчики. По накопленным суммам находите корзину, куда попадает позиция N/2, и вторым проходом берёте только её значения. Если корзина всё ещё велика, повторяете шаг внутри неё;
• глобальная сортировка: сэмплируете данные, строите границы диапазонов и распределяете по ним ключи, в Hadoop для этого есть TotalOrderPartitioner. Каждый редьюсер получает свой отсортированный отрезок, и по размерам отрезков вы находите нужный элемент;
• приближённые скетчи: t-digest, KLL, алгоритм Гринвальда-Ханны. Каждый маппер строит маленький скетч, скетчи сливаются, ошибка контролируется параметром. В Spark это approxQuantile с аргументом relativeError и функция percentile_approx в SQL.

Для чётного N медиана это среднее двух центральных элементов, проговорите это. И уточните у интервьюера, нужна ли точность: для аналитики приближение с ошибкой в доли процента почти всегда устраивает и стоит одного прохода.

Где спотыкаются

Считают медиану каждого блока, а потом медиану медиан. Это неверный ответ: блоки разного размера и распределения, и результат может заметно уехать.

Оставляют один ключ и не видят в этом проблемы. Интервьюеру важно, чтобы вы сами назвали узкое место: один редьюсер и сортировку всего массива в памяти.

Забывают про перекос. Если значения сильно сгруппированы, одна корзина или один диапазон получает почти все данные, поэтому границы берут по сэмплу, а не равными интервалами.