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

Как мы видим, роль IBM в части внедрения систем кеширования в 60-е годы была одной из основных. Неудивительно, что IBM стала первой проводить фундаментальные исследования алгоритмов кеширования. И, пожалуй, пальму первенства среди них нужно отдать алгоритму Ласло Белади. Белади родился в 1928 году в Венгрии, учился на инженера-механика, а во время Венгерской революции 1956 года бежал в Германию с одним рюкзаком, «в котором лежали только белье и диплом». Из Германии он переехал во Францию, затем в 1961 году эмигрировал в США вместе с женой, «маленьким сыном и тысячей долларов в кармане». Казалось, что он обладал отличным чувством меры и понимал, что нужно хранить, а с чем можно легко распрощаться, еще до начала своей работы над замещением кеша в IBM.

Работа Белади по алгоритмам кеширования, которую он написал в 1966 году, оставалась наиболее цитируемым исследованием в компьютерной науке в течение 15 лет. Согласно ей, цель использования кеша состоит в минимизации обращений к более медленной основной памяти в тех случаях, когда пользователь не может найти нужную информацию в кеше. Такие случаи называют «ошибка отсутствия страницы» или «число непопаданий в кеш». Оптимальная политика замещения кеша, как становится очевидно из определения, писал Белади, заключается в том, чтобы, когда кеш полностью заполнен, вытеснить любой его элемент, который максимально нескоро нам понадобится.

Разумеется, определить, когда нам понадобится та или иная информация, – задача трудновыполнимая.

Гипотетически всезнающий и предвидящий алгоритм, способный выбрать оптимальную политику, сегодня известен как алгоритм Белади. Это пример так называемого ясновидящего алгоритма, который использует информацию из будущего. На самом деле не все так безумно, как кажется, ведь существуют случаи, когда система может знать, чего ждать. Но в целом с ясновидением работать сложно, и специалисты по программному обеспечению часто шутят о «трудностях внедрения», которые возникают при попытках применить алгоритм Белади на практике. Таким образом, задача состоит в том, чтобы найти такой алгоритм, решение которого будет максимально дальновидным и точным в тех случаях, когда мы крепко завязли в настоящем и можем лишь гадать, что ждет нас впереди.

Мы могли бы просто прибегнуть к произвольному замещению, добавляя новые данные в кеш и записывая их поверх старых вне какого-либо определенного порядка. Одним из удивительных результатов ранней теории кеширования стал тот факт, что этот подход, хоть и далекий от идеала, отчасти все же работает. Получается, что просто наличие кеша в системе уже делает ее более эффективной, вне зависимости от того, как вы ее используете. Единицы информации, которые вы часто используете, все равно вернутся в кеш. Другое простое решение – метод «первым вошел, первым вышел», когда вы замещаете или перезаписываете те данные, которые находятся в кеше дольше всего (помните вопрос Марты Стюарт «Как давно у меня эта вещь?»).

В рамках третьего подхода – вытеснения по давности использования – замещается тот фрагмент информации, к которому дольше всего не было обращений (вопрос Марты Стюарт «Когда в последний раз я это надевала или использовала?»).

Получается, что эти две мантры Марты Стюарт предлагают две разные стратегии. Более того, одна из них явно превосходит другую. Белади сравнил произвольное замещение, метод «первым вошел, первым вышел» и различные вариации вытеснения по давности использования на нескольких примерах и пришел к выводу, что метод вытеснения по давности использования неизменно показывал результаты, максимально близкие к ясновидению. Этот метод эффективен из-за так называемой временной локальности: если программа обращалась к некоему фрагменту информации единожды, то вполне вероятно, что это повторится в ближайшем будущем. Временная локальность отчасти обусловлена тем, как компьютер справляется с задачами (например, выполнением цикла быстрых операций, связанных со считыванием данных и их записью), но она также заметно проявляется и в том, как люди решают свои проблемы. Работая на компьютере, вы можете переключаться между электронной почтой, интернет-браузером и текстовым редактором. Тот факт, что вы недавно использовали одну из этих программ, указывает на то, что вы, вполне вероятно, откроете ее снова, и при прочих равных условиях программа, которой вы не пользовались дольше всего, с наибольшей вероятностью не будет открыта в ближайшее время.

По сути, этот принцип косвенным образом лежит в основе интерфейса, который компьютер демонстрирует своим пользователям. Окна на экране вашего компьютера располагаются в Z-образном порядке, который симулирует глубину, показывая, какая программа открыта поверх остальных. Программа, которая использовалась максимально давно, как будто оказывается на дне. Как утверждает Аза Раскин, бывший креативный директор Firefox, «бóльшая часть времени, которую вы проводите за современным компьютером, – это цифровой эквивалент сортировки бумаг». Эта «сортировка» с точностью отражается в интерфейсах переключения задач в Windows и Mac OS: когда вы нажимаете на клавиши Alt + Tab или Command + Tab, вы видите, что ваши приложения отражаются упорядоченным списком, от наиболее используемого к наименее используемому.

В литературе, посвященной политикам замещения, подробно анализируются различные схемы, включая алгоритмы, которые подсчитывают частотность и давность использования, алгоритмы, которые отслеживают время предпоследнего обращения к определенной информации, и т. д. Однако, несмотря на изобилие инновационных схем кеширования (некоторые из них могли бы при благоприятных условиях побить метод вытеснения по давности использования), сам по себе этот метод – и небольшие его вариации – безоговорочный фаворит специалистов по информатике и используется в широком спектре развертываемых приложений на различных уровнях. Этот подход учит нас: следующее, что нам может понадобиться, – это то, что нам было нужно в последний раз. А после, вероятно, нам будет нужно то, что мы использовали до этого. А то, без чего мы обходились дольше всего, вряд ли скоро станет для нас необходимостью.

Если у нас нет разумных причин думать иначе, мы можем решить, что нашим лучшим проводником в будущее является зеркальное отображение прошлого. Чтобы максимально приблизиться к ясновидению, нужно просто признать, что история повторяет себя – в обратном порядке.