ИНКРЕМЕНТАЛЬНЫЕ ВЫЧИСЛЕНИЯ

Первая статья из цикла статей «Сравнение алгоритмов повторных и инкрементных вычислений». Цикл разделен на 2 части: в первой мы рассмотрим основные идеи алгоритмов повторных и инкрементных вычислений, а также сравним алгоритмы на примере задачи повышения производительности системы; во второй статье будет проведен анализ устойчивости к отказам и универсальности алгоритмов.

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

В качестве элементарного примера рассмотрим пакетное представление, содержащее общее количество записей в главном массиве данных. Алгоритм повторных вычислений обновит подсчет, присоединив сначала новые данные к главному массиву данных, а затем подсчитав заново все записи. Подобная стратегия представлена на рис. 1

Рисунок 1. Алгоритм повторных вычислений, обновляющий количество записей в главном массиве данных. Сначала к главному массиву присоединяются новые данные, а затем все записи подсчитываются заново.

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

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

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

Производительность

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

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

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

В других случаях увеличение размера пакетного представления для алгоритма инкрементных вычислений оказывается еще более значительным [1]. Рассмотрим в качестве еще одного примера запрос на подсчет количества индивидуальных посетителей страниц по каждому URL. В таблицах снизу показаны отличия в пакетных представлениях при использовании алгоритмов повторных и инкрементных вычислений.

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

Таблица 1

Пакетное представление при повторном вычислении

Таблица 2

Пакетное представление при инкрементном вычислении

Список литературы:

1. Марц, Натан, Уорен, Джеймс. Большие данные: принципы и практика построения масштабируемых систем обработки данных в реальном времени.: Пер. с англ. — М.: ООО “И.Д.Вильямс”, 2016 – 368 с.: ил. — Парал. Тит. Англ.