Текст книги "Алгоритмы для жизни: Простые способы принимать верные решения"

Вытеснение и предсказания

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

Шерлок Холмс

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

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

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

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

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

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

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

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

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

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

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

Вывернуть библиотеку наизнанку

Глубоко в дебрях библиотеки Гарднер Стакс в Калифорнийском университете в Беркли, за закрытыми дверями с большой табличкой «Вход только для персонала», располагается одна из жемчужин библиотечной системы университета. Кормак Маккарти, Томас Пинчон, Элизабет Бишоп, Дж. Д. Сэлинджер; Анаис Нин, Сьюзан Зонтаг, Хунот Диас и Майкл Шейбон; Энни Пру, Марк Стрэнд и Филип К. Дик; Уильям Карлос Уильямс, Чак Паланик и Тони Моррисон; Дэнис Джонсон, Джулиана Спар, Джори Грэм и Дэвид Седарис; Сильвия Плат, Дэвид Мэмет, Дэвид Фостер Воллас и Нил Гейман… Это не коллекция редких книг библиотеки. Это ее кеш.

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

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

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

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

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

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

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

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

Облако в конце улицы

Мы создали такую карту нашей страны, масштаб которой равняется миле на милю!

– И часто вы ею пользуетесь? – спросил я.

– Ее еще ни разу не расстилали, – сказал Майн Герр. – Крестьяне были недовольны. Они сказали, что если такую карту расстелить на всю страну, она скроет солнечный свет! Так что пока мы используем саму страну как ее карту, и смело могу вас заверить, действует она преотлично.

Льюис Кэрролл

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

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

Инженеры думают о географии в скромных масштабах, когда занимаются разработкой технического обеспечения компьютера: в частности, более быстрая память обычно устанавливается ближе к процессору, чтобы сократить время путешествия информации по проводам. Цикл современного процессора измеряется в гигагерцах, что означает, что процессоры осуществляют операции за доли наносекунд. Для сравнения, за такое время свет преодолевает расстояние всего в несколько дюймов. Таким образом, подготовка карты внутренней организации компьютера – вопрос затруднительный. Если применить тот же принцип, но в гораздо большем масштабе, мы увидим, что для функционирования сети, в которой протяженность проводов измеряется не дюймами, а тысячами миль, реальная география становится крайне важна.

Если вы можете создать кеш для контента интернет-страницы, которая располагается географически ближе к людям, которые ее посещают, то открываться такая страница будет гораздо быстрее. Бóльшая часть интернет-трафика сейчас регулируется с помощью сетей доставки контента (CDN), которые хранят копии популярных веб-сайтов на компьютерах по всему миру. Это позволяет пользователям, запрашивающим определенные страницы, получить необходимые данные от ближайшего компьютера без необходимости тянуться через континенты к основному серверу. Компания Akamai управляет крупнейшей сетью CDN. Провайдеры контента платят за то, чтобы их веб-сайты были «акамаизированы» и работали максимально быстро. Например, житель Австралии, который просматривает видео с сайта BBC, наверняка получает информацию с местного сервера Akamai в Сиднее; в любом случае запрос никогда не доходит до Лондона. «Ему и не надо, – комментирует главный разработчик архитектуры Akamai Стефан Лудин. – Мы считаем, что расстояние имеет значение, и наша компания создана на базе этого принципа».

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

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

Это фундаментальное наблюдение – что востребованные файлы должны храниться в непосредственной близости от того места, где они используются, – также можно перенести в чисто физическую реальность. Например, в огромных центрах обработки и исполнения заказов интернет-магазина Amazon обычно избегают применения понятных человеку способов организации работы вроде тех, которые вы можете наблюдать в библиотеке или магазине. Здесь, напротив, сотрудники должны размещать поступающую продукцию в любом свободном месте на складе: батарейки соседствуют с точилками для карандашей, памперсы с переносным грилем и обучающими игре на гитаре DVD-дисками. Для того чтобы отметить и сохранить месторасположение того или иного товара в центральной базе данных, используются штрихкоды. Однако эта на первый взгляд намеренно дезорганизованная система хранения все же имеет одно заметное исключение: все наиболее востребованные товары располагаются в отдельной зоне – более доступной, чем остальные. Эта зона и есть кеш Amazon.

Недавно Amazon получил патент на инновацию, которая развивает этот принцип. В патенте говорится об «опережающей отправке посылок». В прессе это нововведение объяснили так: Amazon сможет отправить вам то, что вы еще не купили. В Amazon, как в технологической компании, конечно, были бы рады иметь дар ясновидения, как у Белади, но в целом все снова сводится к кешированию. Действие их патента распространяется на отправку тех товаров, которые в последнее время приобрели большую популярность у жителей определенного региона. Товары заранее отправляются на склад в этом регионе, который становится своего рода аналогом сети CDN для материальных благ. Затем кто-нибудь делает заказ, и – вуаля – товар уже почти доставлен! Предугадать покупки нескольких клиентов трудно, но, если пытаешься предугадать покупки нескольких сотен человек, начинает работать закон больших чисел. Предположим, что кто-нибудь в Беркли собирается в определенный день заказать, скажем, туалетную бумагу. В тот момент, когда заказ сделан, товар уже находится на полпути к Беркли.

Когда вещи, ставшие популярными в определенном регионе, производятся в этом же регионе, возникает еще более интересная география облака. В 2011 году кинокритик Мика Мертес создал карту Соединенных Штатов на основе «любимых» фильмов по данным компании Netflix. На карте были показаны киноленты, необыкновенно популярные в каждом из штатов. В подавляющем большинстве случаев оказалось, что людям нравятся фильмы, снятые в их родных местах. Жителям штата Вашингтон нравится фильм «Одиночки», снятый в Сиэтле; в Луизиане смотрят «Большой кайф», снятый в Новом Орлеане; жители Лос-Анджелеса, что неудивительно, предпочитают «Лос-Анджелесскую историю»; на Аляске – «Бесстрашную Аляску», а в штате Монтана – «Небо Монтаны»[11]11
  Однако по неизвестным причинам фильм «Мой личный штат Айдахо» является фаворитом в штате Мэн.


[Закрыть]. И поскольку, пожалуй, локальное кеширование не может принести большей пользы, чем в случае с хранением огромных файлов с полнометражными видеофайлами в формате HD, то неудивительно, что Netflix «поселили» «Лос-Анджелесскую историю» в Лос-Анджелесе, то есть там, где живут ее герои и, что еще важнее, ее фанаты.

Кеширование в тылу

И хотя кеширование начинало свой путь как схема организации цифровой информации внутри компьютеров, очевидно, что оно также применимо для организации материальных объектов в человеческом обществе. Джон Хеннесси, президент Стэнфордского университета, пионер в разработке компьютерной архитектуры и один из разработчиков современных систем кеширования, сразу же заметил связь:

Кеширование – это очевидная вещь, поскольку мы занимаемся этим все время. Я имею в виду то количество информации, которое я получаю… За определенными вопросами мне приходится следить постоянно, некоторые я решаю в рабочем порядке, другие я сдал в архив. И, по моим наблюдениям, если какой-то материал был сдан в архив университета, потребуется целый день, чтобы его оттуда заполучить. Ту же технику мы используем ежедневно, пытаясь организовать свою жизнь.

Параллель между этими задачами означает, что существует потенциальная возможность сознательно применять решения из информатики в повседневной жизни.

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

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

Более яркий пример появляется в книге Уильяма Джонса «Не терять из виду найденные вещи»:

Доктор рассказала мне, как она хранит вещи. «Мои дети считают, что я эксцентрична, но я кладу вещи туда, где, мне кажется, они пригодятся мне в следующий раз, даже если это кажется бессмысленным». В качестве примера она поведала, что хранит дополнительные мешки для пылесоса за диваном в гостиной. За диваном в гостиной? Какая в этом логика?.. Оказывается, что пылесос обычно используется для чистки ковра в гостиной… Когда мешок в нем переполняется, это обычно происходит в гостиной. Тут как раз и находятся новые мешки.

Последнее наблюдение, которое нашло применение в руководствах по организации пространства платяного шкафа, – это теория многоуровневой иерархии памяти. Иметь кеш эффективно, но иметь несколько уровней кеша – от самого маленького и быстрого до самого объемного и медленного – в разы эффективнее. Если речь идет о ваших личных вещах, то ваш шкаф – это один уровень кеша, подвал – другой уровень, а арендованная ячейка на складе – третий. (Уровни расположены в порядке уменьшения скорости доступа к вещам. Таким образом, вам следует использовать принцип замещения по давности использования для определения тех вещей, которые должны переместиться с одного уровня на другой.) Но вы также можете ускорить процесс, добавив еще один уровень кеширования – еще меньшего объема и большей скорости доступа, расположенный ближе, чем шкаф.

Жена Тома, крайне терпимая в других вопросах, протестует против горы одежды рядом с кроватью, несмотря на утверждение мужа, что по сути это высокоэффективная схема кеширования. К счастью, в результате наших разговоров с программистами появилось решение и для этой проблемы. Рик Билью из Калифорнийского университета в Сан-Диего, изучающий поисковые системы с когнитивной точки зрения, рекомендует использовать вешалку для костюмов и брюк. Хотя в последнее время они не слишком популярны, в сущности, такая вешалка – это шкаф для одного комплекта одежды. Единая вешалка для пиджака, галстука и брюк – идеальное техническое обеспечение для кеширования в домашних условиях. Как видите, программисты могут не только сэкономить ваше время, но и спасти ваш брак.