Квадрат
Меня на фоне гнева так попёрло, что мне в голову пришло аж две идеи.

Первая идея алгоритмическая. Допустим, у нас есть тупой алгоритм O(N), работающий по очень большой (не влезающей в память) базе документов, под очень большой нагрузкой (много запросов за единицу времени). Например, поиск текста по нетривиальному (но не очень вычислительно сложному) условию.

Мы сейчас в таком случае изобретаем сложносинхронизированные иерархические модели разноуровневых кешей, которые потом годами подкручиваем, а они у нас разъезжаются. Чтобы получить заветные O(logN)

Я понял, что надо делать вообще по-другому. А именно, сделать цикл, проходящий по всем N документам последовательно. И по кругу. И в каждом шаге этого цикла проверять соответствие n-ного документа сразу многим - всем заданным на данный момент - запросам.

Таким образом, если у нас за время обхода всех N документов приходит M запросов, то вычислительная сложность алгоритма будет O(N)/M. Если M сравнимо с ln(N) - начинается хороший добрый профит.

Казалось бы, предельная латентность такого алгоритма будет два полных прохода по документам - но нет. Когда приходит новый запрос, а мы в это время обходим n-ный документ, мы сразу начинаем проверять все следующие документы на соответствие этому запросу - продолжаем, когда пошли на следующий виток - и отвечаем на запрос, как только дошли до n-1-го документа на следующем круге.

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

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

А ещё такой алгоритм можно распиливать хоть поперёк (поставить две машины на M запросов каждая), хоть вдоль (на одной машине прогонять запросы по первой половине документов, на второй - те же запросы по другой половине), хоть по вертикали (сделать две подбазы документов по выделяемому признаку, классифицировать запросы, отправлять разные категории в разные машины с разными базами документов).

И главное - очень предсказуемая производительность и очень равномерное замедление при повышении нагрузки. А не как сейчас, "летим и вдруг стена".

Хотя наверняка это баян и все давно так делают. Если нет - можете звать эту конь струкцию "квадратом Казначеева".

Это была, кстати, стрёмная идея, а вторая вообще гениальная. "Они рассказали нам главную сказку - мне не страшно теперь."