Слияние больших массивов данных

На нашем кассетнике кончилась плёнка — мотай!

Оглавление

Итак, изучив кучи в первом приближении, можно вернуться к сортировке слиянием и рассмотреть те случаи, где другая сортировка работать не будет в принципе. Речь на этот раз пойдёт о таких объёмах данных, которые не влезают в оперативную (внутреннюю) память.

Об уровнях памяти

Часто, говоря о памяти компьютера, предлагают рассматривать лишь оперативную (RAM) и дисковую (HDD / SSD). На самом деле уровней памяти в современном компьютере значительно больше. Если упростить некоторые вещи, то можно рассматривать следующую иерархию:

  1. регистры процессора: сотни байт, единицы тактов;
  2. кеши процессора: от десятков килобайт до нескольких мегабайт, от нескольких до сотен тактов;
  3. оперативная память: десятки и сотни гигабайт, сотни и тысячи тактов;
  4. дисковое хранилище: терабайты, миллионы тактов;
  5. ленточные библиотеки: неограниченно, секунды или даже минуты.

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

Эволюция и скорость

Что же означает: пропускная спопобность шины выросла более чем в 500 раз, а время отклика — всего в 3. Это означает, что мы увеличили «диаметр трубы», но длинная её осталась практически прежней. Из этого соотношения вырастает правило, действующее на всех уровнях иерархии памяти: читай с запасом.

Читай с запасом

Современные диски не дают возможность прочитать один байт. На уровне встроенных микроконтроллеров они возвращают сектор размером 512 байт или 4 Кб. Если же довериться операционной системе, то мы получим размер кластера от 4 Кб до 64 Кб. На самом деле эффективное чтение (то есть когда время отклика становится меньше времени чтения) начинается от нескольких мегабайт.

А таблица выше говорит о том, что подобная ситуация в современных компьютерах стала актуальна не только для чтения с диска, но и для работы с оперативной памятью. Так, например, процессор не взаимодействует с памятью напрямую. Если необходимо прочитать значение переменной, целый кусок памяти считывается в кеш процессора. Затем, после выполнения операций, весь кусок записывается обратно в память.

Это накладывает определённые требования на эффективные алгоритмы, например локальность данных или кеш-независимость (cache-oblivious)1. В случае с сортировками слияния оба требования выполняются за счёт последовательных чтения и записи.

Применение

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

Ниже мы будем рассматривать задачу сортировки \(n\) ключей на машине, где в оперативную память помещается лишь \(m\) ключей. Причём будем считать, что \(m \ll n\). В целом аналогичную задачу можно рассматривать и для пары оперативная память / кеш процессора.

План решения задачи целиком

Итак, у нас есть файл, содержащий \(n\) ключей, при этом в оперативную память помешается только \(m\). Поступим следующим образом:

  • разделим файл на части размером \(m\);
  • отсортируем каждую часть в оперативной памяти;
  • будем сливать части до тех пор, пока не получим отсортированным весь объём ключей.

Первые два пункта понятны, поэтому займёмся последним.

Итак, пусть \(k = n / m \gg 100\). Каким образом будем сливать получившиеся части? Первое, о чём надо помнить: надо как можно меньше читать и писать. Именно чтение и запись являются бутылочным горлышком всей задачи. Таким образом сливать попарно кусочки будет не лучшей затеей, потому как каждый ключ мы прочитаем с диска и запишем обратно \(\log(n/m)\) раз. Чтобы уменьшить высоту дерева слияния надо увеличить основание логарифма. Для этого надо будет сливать не по паре частей, а сразу по 10, 20 или… Сколько кусочков надо сливать?

Для ответа на этот вопрос надо вспомнить правило читай с запасом. Итак, ни чтение, ни запись не происходит по одному элементу, для обоих операций используется некоторый буфер. Размер этого буфера выбирается по правилу соотношения с времени позиционирования и пропускной способности шины. Пусть размер буфера будет составлять \(b\) ключей. Тогда сливать мы сможем не более чем \[ p = \frac{m}{b} - 1 \] частей (один буфер будет использоваться для записи результата). Например, пусть минимально эффективный размер буфера для диска составляет 1 Мб, а объём выделенной для процесса памяти равен 1 Гб, тогда надо будет сливать 1023 части. Как же выбирать следующий минимум из такого количества буферов?

Добавим немного куч

Для решения этой задачи отлично подходит известная нам структура кучи. В итоге получаем следующий алгоритм слияния:

  • вычитываем в память буферы \(p\) частей;
  • образуем из вычитанных ключей кучу;
  • выбираем минимум из кучи и пишем его в буфер записи;
  • как только буфер записи заполнен, пишем его на диск и очищаем.

Но тут возникает следующий вопрос: когда читать следующие блоки из файлов источников? Вычитывать их надо ровно тогда, когда иссякает их буфер чтения. Однако элементы уже переставлены из буферов чтения так, что концов не сыщешь. Для этого необходимо помечать последние элементы вычитанных блоков. Для этого требуется поддерживать \(p\) итераторов. Так как итераторы нужны не для всех элементов, а только для \(p\) штук, лучше всего здесь подойдёт хеш-таблица, сопоставляющая последним в блоках ключам номера блоков. И каждый раз, когда выбирается минимум, делать проверку — не является ли этот ключ последним в каком-либо из блоков. Есть нюансы с одинаковыми ключами, но их можно обойти, хешируя не ключи, а значения или меняя размер блоков.

Немного больше

Но можно улучшить схему ещё больше. Если вдруг так оказалось, что одна из сливаемых частей сильно меньше остальных (поэлементно) и закончилась (была полностью вычитана) раньше остальных, то можно начать читать следующую часть. При этом возможно 2 варианта:

  1. минимальный элемент новой части больше текущего минимума кучи;
  2. минимальный элемент новой части меньше или равен текущего минимума.

В первом случае нам повезло и мы можем продолжать читать блоки новой части так, как если бы она с самого начала участвовала в слиянии. Во втором случае необходимо отделить этот блок в новую кучу. В следующий раз можно вычитать блок из другой части и вновь сравнить его с головой текущей кучи. В итоге, когда текущая куча будет полностью вычитана, новая куча будет уже содержать вычитанные \(p\) блоков из \(p\) ещё не слитых частей, необходимо будет только писать в новый файл. Таким образом результирующий файл получается в среднем размером не \(pm\), а в \(2\) раза больше3.

Задания

  1. Реализуйте слияние \(k\) массивов с использованием двоичной кучи.

Дополнительное чтение

  1. Максим Александрович Бабенко. Видеолекции курса «Алгоритмы и структуры данных». Школа Анализа Данных. https://yandexdataschool.ru/edu-process/courses/algorithms#item-3
  2. Георгий Кириченко. Видеолекции курса «Базы данных». Техносфера Mail.ru Group. https://www.youtube.com/playlist?list=PLrCZzMib1e9o-2km1HniylB-ZZteznvLb

  1. Hiroshi Inoue, Kenjiro Taura. “SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures.” Proceedings of the VLDB Endowment. vol. 8, iss. 11, 2015, pp. 1274-1285. http://www.vldb.org/pvldb/vol8/p1274-inoue.pdf ↩︎

  2. Patrick O’Neil1 and al. “The Log-Structured Merge-Tree (LSM-Tree).” Acta Informatica. vol. 33, no. 4, 1996, pp. 351–385. https://www.cs.umb.edu/~poneil/lsmtree.pdf ↩︎

  3. Xavier Martinez-Palau, David Dominguez-Sal, Josep Lluis Larriba-Pey. “Two-way Replacement Selection.” Proceedings of the VLDB Endowment VLDB Endowment. vol. 3, iss. 1-2, 2010, pp. 871-881. http://www.vldb.org/pvldb/vldb2010/papers/R78.pdf ↩︎