3 миллиарда записей в Java Map на 16 GB RAM

Одним дождливым вечером я размышлял о памяти менеджмент в Java и как эффективно использовать Java коллекции. Я сделал простой эксперимент, сколько записей я могу вставить map с 16 Гб оперативной памяти?

Целью этого эксперимента является исследование внутренних расходов памяти на управление коллекциями. Поэтому я решил использовать маленькие ключи и малые значения. Все тесты проводились на 64-битных Linux Kubuntu 12.04. JVM 64bit Oracle Java 1.7.0_09-b05 с HotSpot 23.5-b02. Включены сжатые указатели (-XX: + UseCompressedOops) по умолчанию на этой JVM.

Первый тест с java.util.TreeMap. Вставляет число в map, работает пока память не заканчивается. JVM параметры для этого теста-Xmx15G

import java.util.*;
Map m = new TreeMap();
for(long counter=0;;counter++){
m.put(counter,"");
if(counter%1000000==0) System.out.println(""+counter);
}

Этот пример закончился 172 миллионами. Ближе к концу процесс замедлился благодаря агрессивной деятельности сборщика мусора. На втором заезде я заменил TreeMap на HashMap, он закончился 182 миллионами.

По умолчанию Java коллекции не являются супер эффективными. Так давайте попробуем более оптимизированы по памяти: Я выбрал LongHashMap из MapDB, который использует примитивные длинные ключи и оптимизирован чтоб иметь небольшой объем памяти. JVM настройки снова -Xmx15G

import org.mapdb.*
LongMap m = new LongHashMap();
for(long counter=0;;counter++){
m.put(counter,"");
if(counter%1000000==0) System.out.println(""+counter);
}

На этот раз счетчик остановился на 276 миллионов записей. Опять же ближе к концу процесс замедлился благодаря агрессивной деятельности сборщика мусора.

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

Настало время, чтобы выкатить настоящее оружие:-). Мы всегда можем уйти от динамической памяти, где сборщик мусора не увидит наши данные. Позвольте мне представить вам MapDB, он предоставляет TreeMap и HashMap при поддержке базы данных. Поддерживает различные режимы хранения, включая вариант который не в динамической памяти.

Так что давайте запустим предыдущий пример, но теперь Map без динамической памяти. Во-первых, это несколько строк, чтобы настроить и открыть базу данных, прямой доступ в память с выключенными транзакциями. Следующая строка создает новый Map в БД.

import org.mapdb.*

DB db = DBMaker
.newDirectMemoryDB()
.transactionDisable()
.make();

Map m = db.getTreeMap(«test»);
for(long counter=0;;counter++){
m.put(counter,"");
if(counter%1000000==0) System.out.println(""+counter);
}

Это Мap не находящийся в динамической памяти, так что мы нужны разные настройки JVM:-XX:MaxDirectMemorySize=15G -Xmx128M. Память закончилась на 980 миллионах.

Но MapDB можно сделать лучше. Проблема в предыдущем примере это фрагментация, узел дерева (b-tree) изменяет свой размер на каждой вставке. Решение заключается в кашировании узлов дерева, прежде чем они вставлены. Это уменьшает фрагментацию при записи до минимума. поменяем конфигурацию DB:

DB db = DBMaker
.newDirectMemoryDB()
.transactionDisable()
.asyncFlushDelay(100)
.make();

Map m = db.getTreeMap(«test»);

Память закончилась на 1,738 миллионов записей, через 31 минуту.

MapDB можно сделать еще лучше — увеличив размер узла в дереве от 32 до 120 записей и включить прозрачное сжатие:

DB db = DBMaker
.newDirectMemoryDB()
.transactionDisable()
.asyncFlushDelay(100)
.compressionEnable()
.make();

Map m = db.createTreeMap(«test»,120, false, null, null, null);

Этот пример заканчивает память на 3,315 миллионах записей. Это медленнее, благодаря сжатию, но он по-прежнему завершается в течение нескольких часов. Я мог бы, вероятно, сделать некоторые оптимизации (специальные сериализаторы) и увеличить количество записей, где-то около к 4 миллиардам.

Может быть, бы спросите, как все эти записи могут поместиться там. Ответ delta-key компрессия. Также вставлением упорядоченных ключей в B-Tree является лучшим сценарием и MapDB немного оптимизирована для него. Наихудший сценарий вставляет ключи в случайном порядке.

delta-key компрессия по умолчанию на всех примерах. В этом примере я активировал Zlib компрессию.

DB db = DBMaker
.newDirectMemoryDB()
.transactionDisable()
.asyncFlushDelay(100)
.make();

Map m = db.getTreeMap(«test»);

Random r = new Random();
for(long counter=0;;counter++){
m.put(r.nextLong(),"");
if(counter%1000000==0) System.out.println(""+counter);
}

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

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

github.com/jankotek/jdbm3
Поделиться публикацией

Комментарии 16

    +4
    Хотя бы пару слов про скорость чтения…
    Мне сложно представить задачу, в которой вставка в дерево является единственной задачей (или основной).
      +1
      Речь идет не о оптимизации вставки в дерево, а о том, сколько записей в нем вообще может храниться.
      –3
      Ерунда. Если надо хранить в базе, будут хранить в базе. Туда влезет сколько угодно данных.
      По производительность базы читать тоже смешно. В высоконагружённых приложениях все затыкается в скорость ввода-вывода с диска, т.е в БД. Поэтому сравнение с in memory Map бессмысленно.
        0
        > Если надо хранить в базе, будут хранить в базе.
        А где в статье было сказано про необходимость долгосрочного хранение данных?

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

        >Поэтому сравнение с in memory Map бессмысленно.
        А где в статье делается сравнение с БД?
          –3
          Вы вообще не поняли, о чем речь. Бессмысленно сравнивать объем данных, которые можно сохранить в памяти и на диске.
          Аффтар статьи почему-то решил сравнить хранение в памяти с дисковым хранением, причем именно по параметру вмещаемых данных.
            0
            Где вы в статье вообще нашли дисковое хранение?
              –3
              Еще один.
              «Java MapDB provides concurrent TreeMap and HashMap backed by disk storage. It is a fast, scalable and easy to use embedded Java database.»
              github.com/jankotek/MapDB

              Вас в Гугла забанили или с соображалкой также плохо, как у автора статьи?
                +2
                А глубже глянуть не судьба? Или хотя бы посмотреть на название метода, которой вполне даже самодокументируем?
                     /** Creates new in-memory database. Changes are lost after JVM exits.
                     * <p/>
                     * This will use DirectByteBuffer outside of HEAP, so Garbage Collector is not affected
                     *
                     */
                    public static DBMaker newDirectMemoryDB(){
                        DBMaker m = new DBMaker();
                        m._file = null;
                        m._ifInMemoryUseDirectBuffer = true;
                        return  m;
                    }
                


                Или вы как-то по-другому переводите in-memory?
              0
              Кстати, не каждая БД (даже NoSQL) сможет показать такую скорость: «It also has outstanding performance with 1 million inserts per second and 10 million fetches per second (disk based!!).»
                0
                Я бы проверил эти числа. Может быть в тесте так же льются пустые данные, и на диск фактически ничего не льётся кроме мета-информации.
          +12
          Что за ужасный перевод? И где ссылка на оригинал?
          Я за минуту нагуглил вот это:
          kotek.net/blog/3G_map

          Скорее всего, есть более ранние версии того же текста.
            +1
            Кстати, я понимаю, что вы новичок на хабре, но здесь есть тег source, который рекомендуется использовать для вставок кода — он подсвечивает код, использует моноширинный шрифт и вообще весьма хорош и красив.
            +3
            m.put(counter,"");
            


            Все ключи будут указывать на один и тот же объект в памяти? С первого взгляда кажется, что для произвольного Map это тест проверяет только расход пямяти на ключи, но не на значения.
              +5
              Одним дождливым вечером я размышлял о памяти менеджмент в Java и как эффективно использовать Java коллекции. Я сделал простой эксперимент, сколько записей я могу вставить map с 16 Гб оперативной памяти?

              Бот гуглотранслейта получил инвайт на хабр?
                0
                Не иначе, потому как первый абзац абсолютно идентичен выдаче гуглопереводчика.
                0
                Перевод ужасный, но статья интересная, как раз хотел сам писать нечто подобное, а тут готовое решение :) Эх, надо над рабочем местом повесить «Поищи вначале на github!»

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое