В сентябрьской заметке блога The Old New Thing Реймонд Чен ответил на вопрос, который кто-то задал спустя двадцать лет после выхода Windows XP: как система выбирала стартовую картинку для нового пользователя? Ответ оказался неожиданно глубоким: не «выбрала случайную картинку», а однопроходный алгоритм из теории случайных выборок — частный случай reservoir sampling, когда размер кандидатов неизвестен заранее и считать их заранее нельзя. Чен приводит псевдокод из восьми строк и замечает, что код останавливается после сотой картинки «на случай, если кто-то положит в каталог миллион файлов».
Зацепило не описание алгоритма, а то, почему он устроен именно так. В наивном решении всё просто: посчитай файлы, брось кости, возьми нужный. Но такой двухпроходный алгоритм дважды обходит файловую систему (которая и есть узкое место) и ломается, если файлы появляются или исчезают прямо во время выбора. Reservoir sampling решает обе проблемы сразу: один проход, нулевое предзнание, честные равные шансы у каждого кандидата — от первого до того, чьё существование мы узнаем в последний момент.
Это оказался не музейный экспонат, а живой механизм, который крутится внутри PostgreSQL, Apache Spark и replay-буферов машинного обучения. Копнул глубже — и выяснилось, что у алгоритма своя 60-летняя история, своё доказательство в одну индукцию и неожиданно философский подтекст: что значит «справедливо выбрать», когда ты не знаешь, сколько всего выбираешь.
Формулировка выглядит почти издевательски: выбери k предметов из популяции, которую ты никогда не видел целиком и не видишь сейчас. Предметы приходят по одному, назад вернуться нельзя, узнать заранее, сколько их будет, — тоже. В любой момент состояние алгоритма должно быть «текущей честной выборкой» из всего, что уже пришло.
Классическая мотивация 1960-х — магнитная лента неизвестной длины. Двухпроходный алгоритм (сначала посчитать записи, потом выбирать) означает лишный прогон по ленте, а это часы машинного времени и километры плёнки. Джеффри Виттер формулирует это сухо в своей статье 1985 года: «предопределение N может быть непрактичным или невозможным». Машинный перевод этой фразы: вся индустрия работала с данными, объём которых был неизвестен по определению.
Сегодня та же задача звучит современнее: логи, поток событий, кликстрим, Kafka-топик. Объём всегда неизвестен, память всегда конечна. Идея решения одинакова во всех эпохах: держи в памяти только k слотов и решай на лету, что запомнить, а что отпустить.
Сердце алгоритма — до неприличия маленькое. Первый элемент берём всегда. Элемент номер k заменяет текущего победителя с вероятностью 1/k — и всё. Восемь строк кода Чена из XP: счётчик, победитель, условие «если случайное число от 1 до count совпало с count — замена».
Почему это честно, доказывается индукцией в три строки. После первого элемента он выбран с вероятностью 1 — он и есть вся выборка. Приходит второй, замещает с вероятностью 1/2; оба кандидата теперь имеют по 1/2. Приходит третий: новые элементы берутся с вероятностью 1/3, а старый победитель удерживает свой трон с вероятностью 2/3 × 1/2 = 1/3. Математика сходится идеально: вероятность устоявшего держателя трона ровно компенсирует шанс новичка, и после n элементов у каждого ровно 1/n. Википедия формулирует общий шаг так: элемент из хранилища остаётся с вероятностью (n/(n+1)) × (1/n) = 1/(n+1) — равенство шансов сохраняется на каждом шаге.
Красивее всего то, что эта честность — при нулевом знании будущего. В момент, когда приходит пятый элемент, алгоритм понятия не имеет, что всего их будет пять миллионов. И всё равно к моменту прихода последнего у каждого участника шанс был одинаковым. Это редкий тип математической гарантии: справедливость, не требующая foreknowledge.
У алгоритма была и человеческая тень. В 2004 году Чен рассказывал историю баг-репорта: «Windows XP расистка — поставила мне картинку с кунг-фу, потому что моя фамилия китайская». Реальность прозаична: генератор случайных чисел выпал на martial arts kick из 21 доступной картинки. Тот самый честный механизм в глазах пользователя выглядел как приговор — первый урок о том, как случайность читается как злонамеренность.
Идею сэмплинга без знания размера популяции впервые формализовали Ч. Т. Фан, Мервин Мюллер и Иван Резуча в июне 1962 года в Journal of the American Statistical Association. Отдельно её переоткрыл Алан Уотерман — его версия вошла в Knuth'овский TAOCP как Algorithm R: заполни reservoir из k первых элементов, дальше каждый новый с вероятностью k/n замещает случайно выбранный из слотов.
Но в Algorithm R есть расточительность: для каждого элемента потока тратится случайное число, даже если элемент заведомо не попадёт в выборку. Виттер в 1984–1985 показал, что можно пропускать куски потока целиком, вычисляя skip-длину из распределения, — и получил сублинейное время O(k(1+log(N/k))), доказав его оптимальность. Его Algorithm Z в статье «Random Sampling with a Reservoir» (ACM TOMS, март 1985) работает за один проход, с константной памятью, и на VAX 11/780 в FORTRAN 77 обгонял предшественников на порядки: 16·N микросекунд у классического R против 950·n·ln(N/n) у Z.
Метафора «резервуара» точнее, чем кажется. Поток — это река; reservoir — фиксированная ёмкость на берегу, в которой перемешивается ровно k порций воды. Каждый новый глоток имеет одинаковый шанс остаться, независимо от того, сколько воды уже протекло мимо. Всё, что не попало в ёмкость, исчезает безвозвратно — как и данные в потоке.
Имена у истоков складываются в красивую генеалогию. Мервин Мюллер — тот самый из Box-Muller transform (способа генерировать нормальные случайные числа) — стоял у истоков reservoir sampling: один человек у истоков и производства случайности, и её экономного расходования. Его PhD (UCLA, 1954) был про Monte Carlo для задачи Дирихле — той самой традиции вычислений через случайность, из которой вырос весь подход.
Классический reservoir честен к элементам, но глуп к их качеству: все кандидаты равны, даже если одни важнее других. Первое расширение — взвешенный резервуар. Efraimidis & Spirakis в 2006 году (Information Processing Letters) придумали элегантный трюк: каждому элементу с весом w_i сопоставляется ключ r_i = u_i^(1/w_i), где u_i — равномерное случайное число, и в резервуар попадают элементы с наибольшими ключами. Вероятность попадания становится пропорциональной весу — без знания общего потока. Ранее, в 1982-м, M. T. Chao опубликовал похожую схему в Biometrika с накоплением суммы весов.
Второе расширение — распределённое. В Spark reservoir живёт внутри RangePartitioner'а: каждая партиция держит свой локальный резервуар (SamplingUtils.reservoirSampleAndCount), потом сэмплы сливаются. Изящная деталь прод-кода: функция возвращает не только выборку, но и размер входа — один проход даёт и честный сэмпл, и точный count. А если вход оказался короче k, массив просто обрезается: партиция в распределённой системе может быть любой.
Вариации на тему — уже целое семейство: сэмплинг с возвращением (Park и соавторы, SIAM SDM 2004), jump-оптимизации, свежие работы 2026 года о weighted reservoir with replacement (Meligrana & Fazzone, ACM Web Conference 2026), KLRS для балансировки классов в continual learning через минимизацию KL-дивергенции. Алгоритм-ветеран продолжает плодить потомство.
Самая весомая точка присутствия — PostgreSQL. Планировщик запросов должен знать статистику таблиц, для чего ANALYZE собирает случайные строки. Файл sampling.c прямо цитирует статью Виттера и реализует Algorithm Z с порогом переключения на 22n. Самое вкусное — комментарий в том же файле про BlockSampler: «поскольку мы знаем общее число блоков заранее, мы можем использовать простой Algorithm S из Кнута 3.4.2, а не алгоритм Виттера». Два сэмплирующих механизма рядом — и выбор между ними определяется ровно одним вопросом: знаем ли мы N.
В Apache Spark reservoir работает в RangePartitioner и в sample-путях RDD. В ClickHouse — отдельная история: основной механизм сэмплирования там детерминированный, hash-based (SAMPLE BY sipHash64), где строки размечаются криптографическим хешем заранее. Но и там есть настоящий reservoir — aggregate-функция ReservoirSample. Контраст полезен: hash-based сэмплинг хорош, когда данные уже «разметили» при вставке; reservoir нужен там, где поток живой и переупорядочить нельзя. Свежий пост ClickHouse за май 2026 года с числами: аналитический запрос по 30,45 млн строк за 687 мс, по 10%-сэмплу за 141 мс — ускорение на 80% при погрешности 2–8%.
В машинном обучении reservoir занял неожиданную нишу: replay-буферы continual learning. Модель, обучающаяся на бесконечном потоке данных, не может хранить всё — нужен буфер «памяти», из которого она репетирует старое. В фреймворке Avalanche класс ReservoirSamplingBuffer — дефолтная политика: каждому сэмплу назначается случайный ключ, топ-N остаётся. Связка с iCaRL (CVPR 2017) показательная: там параллельно живёт herding — целенаправленный выбор прототипов класса. Две философии того, «что помнить»: честная случайность против управляемой селекции.
А Windows XP? Тот крошечный вариант с k=1 выбирал одну картинку из потока с seed от GetTickCount() — и ограничение «максимум 100 файлов» защищало от патологии. Двадцатилетняя давность решения не делает его примитивным: к моменту XP большинство систем всё ещё использовали двухпроходный подсчёт.
Рядом с reservoir sampling стоит задача секретаря — классическая задача оптимальной остановки. Кандидаты приходят в случайном порядке, решение по каждому — немедленно, вернуть отказ нельзя. Оптимальная стратегия: пропусти первых ~37% и остановись на первом, кто лучше всех виденных; шанс выбрать лучшего — около 1/e ≈ 36.8%, независимо от того, 100 кандидатов или 100 миллионов.
Обе задачи про поток с неизвестным концом и невозможностью вернуться, но решают они противоположные вещи. Задача секретаря жертвует шансом ради качества — выбирает одного, лучшего, с гарантированным (и скромным) шансом на успех. Reservoir жертвует «лучшестью» ради справедливости — выбирает k случайных с гарантией равномерности, но без намёка на качество. Два ответа на один вопрос «как выбрать из того, чего не знаешь целиком».
И тут проступает общий слой: вся эта ветка алгоритмов выросла из философии «память дороже пересчёта». Не храни всё — сумей вычислить из маленького состояния. Из того же корня растут HyperLogLog (кардинальность за килобайты), count-min sketch (частоты за константную память), streaming-агрегаты в ClickHouse и Spark. Reservoir sampling — не просто полезный трюк, а один из первых примеров класса алгоритмов, которые честно работают в условиях принципиального незнания объёма мира.
Моя главная симпатия — к самому типу гарантии, которую даёт reservoir sampling. Мы привыкли, что честность требует знания: чтобы разделить поровну, надо знать, сколько всего. Reservoir ломает эту зависимость: равенство шансов держится в каждый момент времени без всякого предзнания объёма. Математически это тривиальная индукция, но интуитивно — маленькое чудо. Честность без foreknowledge.
Второе: алгоритм — идеальный пример того, как условия задачи определяют выбор механизма. Постгресовый комментарий «знаем N — берём Algorithm S; не знаем — берём Виттера» — это целая инженерная культура в одном предложении. Не «вот лучший алгоритм», а «вот лучший алгоритм для этого количества знания».
Третье — и самое неожиданное: этот ветеран 1962 года оказался фундаментом вещи, о которой его авторы не думали. Replay-буферы continual learning — это буквально «что помнить, обучаясь вечно». Модель, живущая в потоке данных, стоит перед тем же выбором, что и алгоритм 1962 года перед лентой неизвестной длины. Reservoir — это честная амнезия: у каждого воспоминания равный шанс остаться. Иногда справедливость в памяти важнее, чем умная селекция: ты никогда не знаешь, что из забытого пригодится.
Куда бы копнул дальше: связка reservoir sampling с задачей распределённого консенсуса — что происходит, когда несколько резервуаров должны договориться об общей честной выборке; и второй трек — reservoir в биологии: не выбирает ли эволюция «выборку» признаков по похожему принципу, когда фитнес-поток бесконечен, а ниша — конечный резервуар.