Если данные не помещаются в память. Простейшие методы

Самка трубкозуба с детёнышем. Фото: Scotto Bear, CC BY-SA 2.0

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

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

Что делать?

Ну, можете развернуть кластер Big Data, всего-то:

• Найти кластер компьютеров.
  
• За неделю его настроить.
  
• Изучить новый API и переписать свой код.

Это дорого и неприятно. К счастью, зачастую и не нужно.

Нам требуется простое и лёгкое решение: обрабатывать данные на одном компьютере, с минимальной настройкой и максимальным использованием уже подключенных библиотек. Почти всегда это возможно с помощью простейших методов, которые иногда называют «вычислениями вне памяти» (out-of-core computation).

В этой статье обсудим:

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

В будущих статьях на практике покажем, как применять эти методы с конкретными библиотеками, таким как NumPy и Pandas. Но сначала теория.

Зачем вообще нужна оперативная память?

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

Теоретически это может сработать. Но даже современные быстрые SSD работают намного, намного медленнее, чем RAM:

• Чтение с SSD: ~16 000 наносекунд
  
• Чтение из RAM: ~100 наносекунд

Для быстрых вычислений у нас не остаётся выбора: данные приходится записывать в ОЗУ, иначе код замедлится в 150 раз.

Самое простое решение: больше оперативной памяти

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

• Купить Thinkpad M720 Tower с 6 ядрами и 64 ГБ оперативной памяти за $1074
  
• Арендовать в облаке виртуальную машину с 64 ядрами и 432 ГБ оперативной памяти за $3,62/час

Это просто цифры после быстрого поиска. Проведя хорошее исследование, вы наверняка найдёте более выгодные предложения.

Потратить немного денег на аппаратное обеспечение, чтобы данные поместились в ОЗУ, — зачастую самое дешёвое решение. В конце концов, наше время дорого. Но иногда этого недостаточно.

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

Если покупка/аренда большого объёма RAM не решает проблему или невозможна, следующий шаг — оптимизировать само приложение, чтобы оно расходовало меньше памяти.

Техника № 1. Сжатие

Сжатие позволяет поместить те же данные в меньший объём памяти. Есть две формы сжатия:

• Без потерь: после сжатия сохраняется в точности та же информация, что и в исходных данных.
  
• С потерями: сохраняемые данные теряют некоторые детали, но в идеале это не сильно влияет на результаты расчёта.

Просто для ясности, речь не о файлах ZIP или gzip, когда происходит сжатие данных на диске. Для обработки данных из ZIP-файла обычно нужно распаковать его, а потом загрузить файлы в память. Так что это не поможет.

Что нам нужно, так это сжатие представления данных в памяти.

Предположим, в ваших данных хранится только два возможных значения, и больше ничего: "AVAILABLE" и "UNAVAILABLE". Вместо сохранения строк с 10 байтами или более на запись, вы можете сохранить их как логические значения True или False, которые кодируются просто одни байтом. Можете сжать информацию даже до одного бита, уменьшив расход памяти ещё в восемь раз.

Техника № 2. Разбиение на блоки, загрузка данных по одному блоку за раз

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

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

largest_word = ""
for word in book.get_text().split():
    if len(word) > len(largest_word):
        largest_word = word

Но если книга не помещается в память, можно загрузить её постранично:

largest_word = ""
for page in book.iterpages():
    for word in page.get_text().split():
        if len(word) > len(largest_word):
            largest_word = word

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

Техника № 3. Индексация, когда требуется только подмножество данных

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

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

Если вам нужна только часть данных, вместо фрагментации лучше использовать индекс — выжимку данных, которая указывает на их реальное местоположение.

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

Или можете сразу открыть алфавитный индекс в конце книги — и найти слово «трубкозуб». Там указано, что упоминания слова есть на страницах 7, 19 и 120-123. Теперь можно прочитать эти страницы, и только их, что намного быстрее.

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

Самый простой метод индексирования

Самый простой и распространённый способ индексирования — именование файлов в каталоге:

mydata/
    2019-Jan.csv
    2019-Feb.csv
    2019-Mar.csv
    2019-Apr.csv
    ...

Если вам нужны данные за март 2019 года, вы просто загружаете файл 2019-Mar.csv — нет необходимости загружать данные за февраль, июль или любой другой месяц.

Дальше: применение этих методов

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

Те же методы используются в различных программных пакетах и инструментах. На них построены даже высокопроизводительные системы Big Data: например, параллельная обработка отдельных фрагментов данных.

В следующих статьях рассмотрим, как применять эти методы в конкретных библиотеках и инструментах, в том числе NumPy и Pandas.