Скетчи: сосчитать, не запоминая

Данные, которые не помещаются

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

Записи о звонках телефонной сети, пакеты на магистральном маршрутизаторе, обращения к большому сайту — они идут потоком, поток бесконечен, и сохранить его целиком нельзя. Между тем вопросы к нему самые обыкновенные: сколько было различных абонентов? какие адреса встречались чаще всего? насколько сегодняшнее распределение похоже на вчерашнее?

Прежние методы предполагают, что данные лежат и к ним можно обратиться. Здесь их нет — есть только проходящая мимо струя.

Модель потока

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

В 1996 году Нога Алон, Йосси Матиас и Марио Сегеди публикуют работу, за которую получат премию ГёделяКурт Гёдельавстрийский и американский логик · 1906–1978Доказал, что в любой достаточно богатой формальной системе есть истинные утверждения, которые она не может доказать, — и тем закрыл программу Гильберта в двадцать пять лет.: они показывают, что в этой модели можно и чего нельзя.

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

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

Как считают, не запоминая

Идея настолько наглядна, что её стоит рассказать на пальцах — на примере подсчёта числа различных элементов (Флажоле и Мартен, 1985; в нынешнем виде — HyperLogLog, 2007).

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

Строка начинается с одного нуля примерно у половины элементов, с двух нулей — у четверти, с $k$ нулей — у одного из $2^{k}$. Значит, если за всё время мы видели строку с десятью ведущими нулями, различных элементов, скорее всего, было около тысячи. Рекорд — одно маленькое число, и в нём содержится оценка количества.

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

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

Замыкание

Здесь линию уместно остановить — не потому, что история кончилась, а потому, что видна её форма.

Двенадцать веков подряд менялся один и тот же ответ на один и тот же вопрос: что в вычислении дорого?

• Пиза — дорого само действие: жетоны на доске не умеют умножать.
• Лейден — дорога дробь: общий знаменатель требует думать на каждом шаге.
• Мерчистон — дорого умножение; его меняют на сложение.
• Лондон — дорога таблица; её сжимают до мантисс.
• Лондон — дорого обращение к таблице; сложение переносят на дерево.
• Руан и Лондон — дорог человек; действие отдают металлу.
• Париж — дорого понимание; его изымают из процедуры.
• Лондон — дорога надёжность; уставший человек ошибается, машина нет.
• Гёттинген — дорога формула, которой попросту не существует; ответом становится таблица с оценкой погрешности.
• Принстон и Теддингтон — дорога точность; ошибка сама становится предметом теории.
• Мюррей-Хилл, Москва, Цюрих — дорого время; показатель степени сбивают рекурсией.
• Нью-Хейвен — дорога размерность; её обменивают на точность по известному курсу.
• Мюррей-Хилл, снова — дорога память и самый взгляд на данные; отказываются от точного ответа в обмен на один проход.

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

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

А следующий дефицит уже виден. Когда счёт стал стоить электричества и воды для охлаждения, вопрос «сколько стоит вычисление» снова сделался буквальным — впервые со времён парижской мастерской, где его задавали в жалованье восьмидесяти счётчикам.