Как расширить задачу топ звонящих абонентов на большие данные

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

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

Как отвечать

Начните с уточнений: топ по числу звонков или по длительности, за какой период, нужен ли точный ответ, сколько уникальных абонентов и сколько записей.

Дальше по ступеням масштаба:

• одна машина, счётчики влезают: читать потоком через File.ReadLines или StreamReader, считать в Dictionary<long, int> (номер как long, не строка), топ-K держать в PriorityQueue<TElement, TPriority> размера K. Итог O(n log K) по времени и O(число абонентов) по памяти. Для быстрого инкремента есть CollectionsMarshal.GetValueRefOrAddDefault;
• не влезает в память: разбить вход по hash(номер) % N на N файлов. Один абонент всегда попадает в один файл, поэтому каждый файл считается отдельно, а локальные топы честно сливаются в общий;
• кластер: та же схема в Spark или ClickHouse. Сначала агрегация по ключу с предварительным комбинированием на месте, чтобы не гонять по сети каждую запись, потом топ-K на партицию и слияние;
• поток и приближённость: если данные идут непрерывно, а памяти мало, берут алгоритмы тяжёлых элементов: Space-Saving, Misra-Gries или Count-Min Sketch с кучей. Ошибка у них ограничена и известна заранее. В ClickHouse есть готовая приближённая функция topK.

Сервис на C# в такой архитектуре обычно читает поток из Kafka и пишет агрегаты, а тяжёлый пересчёт живёт в хранилище.

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

Сразу предлагают Hadoop, не спросив объёмы. Сотни миллионов строк часто считаются на одной машине за минуты.

Берут локальный топ-K на каждом узле, не разбив данные по абоненту. Если один номер размазан по узлам, он может не попасть ни в один локальный топ и выпасть из общего.

Не думают о перекосе: колл-центр делает на порядки больше звонков, чем обычный абонент, и одна партиция считается дольше всех. Помогает двухфазная агрегация с солью в ключе.