Алексей Махоткин

домашняя страница

Алгоритмы и структуры данных

Масштабируемые и высокопроизводительные веб-приложения, гл. II

Алгоритмы и структуры данных

Вычислительная сложность

Вычислительная сложность — базовое понятие алгоритмической теории. Вычислительная сложность алгоритма — это попросту оценка количества операций, требуемых для достижения результата, в зависимости от количества обрабатываемых элементов. Чаще всего встречаются такие виды вычислительной сложности: константная, логарифмическая, линейная, квадратичная, экспоненциальная и факториальная. Каждая следующая — «хуже» предыдущей. Вычислительная сложность обозначается как O(…) (читается «O-большое»).

Возьмём, например, простой массив (как в C или Паскале, индексируемый целыми числами). Операция взятия значения по индексу — это примитивная операция, время её выполнения не зависит от значения индекса (и от количества элементов в массиве). Такой тривиальный «алгоритм» имеет константную вычислительную сложность (обозначается O(1)).

Поиск в том же массиве конкретного значения методом последовательного перебора в худшем случае потребует от нас проверить все N элементов этого массива. В среднем нам придётся проверить N/2 элементов. Алгоритм последовательного перебора имеет линейную вычислительную сложность (обозначается O(n)).

Если мы знаем, что значения в массиве упорядочены по возрастанию, то мы можем воспользоваться алгоритмом бинарного поиска. В нём на каждом шаге берётся элемент из середины массива. Если искомый элемент меньше взятого, то операция повторяется с левой частью массива, в противном случае — с правой частью. Таким образом, на каждом шаге пространство поиска делится пополам. Алгоритм гарантированно заканчивается за log₂(N) шагов. Его вычислительная сложность называется логарифмической (обозначается O(log n)).

Возьмём N точек на плоскости и попробуем найти пару самых близко расположенных точек. Для этого нам придётся вычислить расстояние между каждой парой, то есть совершить N*(N-1) операций. Вычислительная сложность этого алгоритма называется квадратичной (обозначается O(n²)). Заметим, что при указании вычислительной сложности члены младшего порядка обычно отбрасываются, а иначе мы писали бы O(n²-n).

Задачи, имеющие экспоненциальную: O(2ⁿ) и факториальную: O(n!) вычислительную сложность, практически не поддаются вычислению при достаточно больших значениях n. Например, классическая задача о путешествующем коммивояжере имеет факториальную вычислительную сложность (хотя в последнее время с помощью различных оптимизаций и эвристик эту характеристику удалось существенно сократить).

Заметим, что при теоретическом рассмотрении вычислительной сложности постоянные коэффициенты игнорируются. Так, если некоторый алгоритм выполняется ровно за секунду при любом размере входных данных, то он считается «лучше» алгоритма, который тратит на обработку каждого элемента микросекунду (и таким образом, второй выполняется быстрее первого при количестве элементов менее миллиона). При практическом рассмотрении проблемы, конечно же, время работы приходится учитывать. Однако, стараться уменьшить этот коэффициент имеет смысл только после того, как станет ясно, что уменьшить вычислительную сложность алгоритма невозможно.

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

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

Структуры данных

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

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

Базовые структуры данных

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

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

Самая простая структура данных — массив (без изменения размера на лету, как в языке C). Массив обеспечивает всего две операции: константный доступ к элементам по целочисленному индексу и линейный поиск нужного элемента. Размер его задаётся на стадии объявления массива и не может быть изменен во время выполнения. Если держать элементы в отсортированном виде и использовать алгоритм двоичного поиска, то время поиска элемента можно улучшить до логарифмического.

Непосредственный потомок массива — вектор (динамический массив с возможностью изменения размера). Он обеспечивает те же операции, что и массив, но позволяет изменять размер массива, добавляя и удаляя элементы (в зависимости от реализации, с одного или двух концов). Разновидности вектора — дек (deque), очередь и стек. Операция добавления элемента в вектор имеет амортизированную константную сложность (при достижении определенного размера массива требуется выделить совершенно новый кусок памяти и перенести туда все элементы вектора; таким образом, операция добавления вырождается до линейной).

То, что называется «массивом» в современных системах веб-разработки, обычно обеспечивает любые разумные операции работы с вектором, всеми силами стараясь не допустить вырожденного поведения. Однако, при некоторых задачах бывает необходимо понять, как устроена соответствующая реализация, чтобы исправить соответствующую проблему производительности (например, некоторые реализации вектора будут плохо работать в режиме высокоскоростной FIFO-очереди, неконтролируемо отъедая память).

Ассоциативные массивы

Ещё интереснее — ассоциативные массивы. Именно они скрываются под названием «массива» в современных системах веб-разработки. Даже обычные массивы и вектора реализуются через ассоциативные массивы. Однако, обычные и ассоциативные массивы радикально отличаются, если рассматривать их абстрактную структуру.

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

Хэш-массивы

Самая распространенная реализация ассоциативного массива — хэш-массив. Данные в нём организуются путём разбиения на N «корзин» (buckets), в каждой из которых хранится отдельный ассоциативный массив. Нужная корзина выбирается с помощью хэш-функции. Хэш-функция принимает в качестве аргумента ключ и возвращает целое число от 0 до N-1, которое как раз и задаёт номер корзины. Внутри корзины данные могут храниться по-разному: либо опять используется хэш-массив, либо дерево, либо простой последовательный поиск. Таким образом, хэш-массив попросту механически уменьшает вычислительную сложность на большой константный коэффициент. Считается, что доступ к элементам хэш-массива имеет амортизированную константную сложность.

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

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

Деревья

Деревья (особенно сбалансированные) обычно облегчают поиск нужного элемента, на каждом шаге уменьшая область поиска вдвое. Таким образом, поиск элемента в дереве имеет логарифмическую сложность. Различных видов деревьев огромное количество; и каждое из них специализируется на отдельном классе задач.

Списки

Классические списки (односвязный и двусвязный) сложно уже встретить где-то за пределами систем, написанных непосредственно на языке C. Однако, их концептуальное значение чрезвычайно велико.

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

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

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

MapReduce

Функции map и reduce — две классические операции функционального программирования.

Фукция map принимает список значений и функцию-трансформатор, а возвращает список результатов применения трансформатора к каждому значению. Например, список (1, 2, 3) и функция «возвести в квадрат» даёт в результате список (1, 4, 9).

Функция reduce принимает список значений, стартовое значение аккумулятора и функцию свертки (которая принимает два значения, и возвращает одно). Reduce последовательно передаёт в функцию свертки значение аккумулятора и очередное значение из списка, а результат помещает в аккумулятор. Результатом выполнения функции reduce является финальное значение аккумулятора. Например, для списка (1, 4, 9), стартового значения 0 и функции «плюс» результатом будет 0 + 1 + 4 + 9, то есть 14.

Оказывается, что множество сложных задач можно свести к последовательному выполнению комбинаций функций map и reduce. Например, каждый раз, когда мы что-то ищем в Google, над непосредственным содержимым страниц результатов работают несколько функций map и reduce.

map и reduce накладывают некоторые разумные ограничения на функцию-трансформатор и функцию свертки. Так, например, функция свертки для reduce должна возвращать одно и то же значение независимо от порядка элементов в списке: то есть, результат применения reduce к списку (1, 2, 3) и списку (3, 2, 1), должен совпадать.

Функция-трансформатор для map должна для каждого значения аргумента всегда возвращать одно и то же значение: то есть, список (2, 2, 2, 2) должен вернуть (4, 4, 4, 4).

Энциклопедический бестиарий

Рассмотрим гипотетический, но чрезвычайно иллюстративный пример работы функций map/reduce и возможностей оптимизации, которые они предоставляют.

Представим, что нам поставили задачу: выяснить, какие животные и сколько раз встречаются в многотомной энциклопедии. Пусть в энциклопедии 20 томов по 1000 страниц. У нас есть мощный ксерокс, неограниченный запас бумаги и тонера, а также большой бюджет на привлечение квалифицированной рабочей силы (например, мы можем нанять тысячу человек).

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

Животные Кол-во
---------------
кошки      5 
собаки     7
утконосы   1
носороги   2

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

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

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

Теперь мы можем, например, опять раздать им по 100 табличек каждому, чтобы они вернули по одной консолидированной табличке. Через 100 минут у нас будет 2000 консолидированных табличек. Раздадим ещё раз по 100 табличек (теперь нам нужно всего 20 помощников, а остальных можно отпустить). Через 100 минут у нас есть двадцать табличек, которые можно самостоятельно за двадцать минут просуммировать, получив требуемый результат.

Таким образом, мы организовали труд так, что решили задачу за 20+100+100+20=240 минут, то есть чуть меньше 6 часов. Производительность выросла почти в 170 раз.

Оказывается, что мы воспользовались функциями map/reduce. Первая операция — взять страницу энциклопедии и вернуть табличку со списком животных на ней — это не что иное, как функция-трансформатор для map. Мы превратили список страниц энциклопедии в список табличек.

Вторая операция — взять список табличек и превратить его в консолидированную табличку — это не что иное, как функция свертки для reduce. Мы превратили список табличек в единую мастер-таблицу того же формата. За счет того, что от перестановки слагаемых сумма не изменяется, мы могли прибавлять цифры в любом порядке, а также суммировать промежуточные полученные цифры — результат от этого не менялся.

У нас также есть простор для переорганизации задач «на лету». Например, если кто-то забрал свои 20 страниц, но ему быстро наскучило работать и он отказался от задания, то мы можем повторно раздать те же 20 страниц другому человеку, и так до тех пор, пока все они не будут обработаны. Это несильно увеличивает время выполнения первой фазы (например, в 2-3 раза).

Практическое использование в Google Оказывается, что львиная доля вычислений, производимых в мега-системе, скрывающейся под сервисами Google, выполняется в рамках архитектуры MapReduce. Это набор библиотек и инфраструктурных решений, позволяющих быстро програмировать вычислительные задачи в стиле map/reduce и выполнять их на огромном кластере. Всего внутри компании за несколько лет были написаны многие тысячи задач в стиле map/reduce.

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

Существует также открытая реализация аналога MapReduce, которая называется Hadoop. Она была разработана в рамках Apache Software Foundation, совместно с Yahoo.

Memcached

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

Львиная доля объектов, используемых в типичном веб-приложении, изменяется относительно редко, и значительно чаще читается из базы данных для показа пользователю. Целесообразно один раз прочитать объект (например, запись о документе) из базы данных, затем поместить его в Memcached. Таким образом, при последующих обращениях забирать этот документ непосредственно из Memcached, экономя на запросах к базе данных.

Memcached постепенно выделяет себе кусок оперативной памяти, вплоть до установленного администратором предела. На высоконагруженных проектах ставится несколько серверов Memcached на разных машинах, что позволяет создавать кэши огромных размеров, вплоть до нескольких десятков терабайт оперативой памяти, размещенных на сотне и более физических машин. Внутри используется сложная система управления памятью, основанная на принципе slab-allocator (классификация хранимых объектов по размеру), а также высокопроизводительная машина для эффективного обслуживания огромного количества одновременных запросов.

Memcached используется практически во всех высоконагруженных популярных проектах, использующих технологию Unix. Интересно осознать, что он представляет собой «всего лишь» толстую обёртку поверх простой классической структуры данных, широко известной десятки лет.

Другие примеры структур данных на практике

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

Реляционные базы данных

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

Индексы обычно используют либо деревья (а именно, B-trees), либо хэш-массивы. Индексы эффективны лишь для определенных классов запросов, для определенных диапазонов значений в полях таблицы. Надо очень хорошо понимать, как устроены индексы (то есть, какова их нижележащая структура данных). В противном случае, велик риск не только не улучшить скорость запросов, но и получить ряд отрицательных эффектов. Среди них — снижение производительности при добавлении и изменении записей, а также расточительное использование дискового пространства (индексы могут занимать порой в несколько раз больше места, чем данные самой таблицы).

Файловые системы

Основное применение структур данных в файловых системах — это обработка очень большого количества файлов в одном каталоге. Без специальных (простых) мер обращение к таким файлам будет очень неэффективным и приведет к задержкам, которые видны невооруженным взглядом. Для исправления обычно используется раскладка файлов по набору подкаталогов, с тем или иным алгоритмом выбора подкаталога. Понятно, что такая методика — это всего лишь очередная манифестация универсальной структуры данных — хэш-таблицы.

Программы общего назначения обычно используют вышеизложенную схему хранения файлов, справедливо полагая нижележащую файловую систему неспособной самостоятельно справиться с задачей. Однако, намечаются и попытки разработчиков файловых систем самостоятельно справляться с «нагрузкой»: например, имена файлов в каталоге автоматически хэшируются как в ext3+DIRSHASH, так и в Reiserfs.

Comments