elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Пишем самый быстрый хеш для кэширования данных: Часть 1
elizarov

12 мая 2012 года я выступаю с докладом на конференции Application Developer Days. Мой доклад будет посвящен написанию высокопроизводительных структур данных и будет служить продолжением моей серии статей про производительность. Я покажу весь путь дизайна на примере конкретной задачи. Это задача кэширования данных загруженных из БД, которая очень часто возникает в бизнес приложениях. Безусловно, есть множество готовых каркасов, которые решают эту задачу совершенно прозрачно для программиста. Но что делать, если вы создаете высоконагруженное приложение, оперирующее миллионами объектов и вынужденное постоянно к мим обращаться для выполнения тех или иных стоящих перед вами задач? Например, высокопроизводительные приложения для торговли на финансовых рынках, по типу тех, которые мы создаем в Devexperts.

Заметьте, что при работе с миллионом объектов, даже лишние 10 наносекунд потраченные на поиск объекта в кэше, превратятся в лишние 10 миллисекунд времени выполнения всей операции. Конечно, можно распараллелить работу. Однако, если система выполняет большое количество операций и манипулирует большим объемом данных, то даже поиск данных в кэше в памяти может стать узким местом. Нужно оптимизировать сам кэш.

При решение любой оптимизационной задачи (да и вообще при решении любой задачи) надо первым делу четко сформулировать саму задачу. Пусть есть некий класс для сущностей, которые приложение часто читает из БД, например заявки, представленные в виде класса Order. У заявки есть уникальный идентификатор long id, контрольное число int check (будет использоваться для проверки корректности всех алгоритмов) и еще 5 несущественных атрибутов типа int. В 32-битной JVM каждая такая заявка будет занимать 40 байт. Обычно бизнес приложения оперируют с сущностями большего размера, но для целей демонстрации общих принципов такой класс вполне подойдет.

public class Order { 
    private final long id; 
    private final int check; 
    // и еще 5 несущественных атрибутов типа int не показаны
    public Order(long id, int check) { 
        this.id = id; 
        this.check = check; 
    } 
 
    public long getId() { 
        return id; 
    } 
 
    public int getCheck() { 
        return check; 
    } 
}

В процессе работы системы заявкам присваиваются уникальные последовательные идентификаторы, а при чтении чаще всего используются последние из них. Вероятность запросить заявку с тем или иным идентификатором будет подчинена геометрическому распределению. Класс AccessSequence создает соответствующую последовательность идентификаторов для тестирования: 10 миллионов запросов, примерно 1М уникальных запрашиваемых идентификаторов в диапазоне идентификаторов от 6M до 10М. Заявки с большими номерами запрашиваются чаще. Например, заявка с id=9994952 запрашивается 69 раз (чаще не бывает). Этот же класс выделяет в случайном порядке экземпляры класса Order только с теми идентификаторами, к которым будет доступ, для инициализации разных кэшей максимально похожим образом.

Меня интересует скорость чтения из кэша. Я замеряю среднее время доступа к одному элементу в заранее подготовленном порядке. Сравниваемые кэши должны реализовать простейший интерфейс Cache в котором есть два главных метода:

public interface Cache { 
    public void addObject(Order order); 
    public Order getById(long id); 
} 

Внутренний цикл тестирования в главном классе BenchmarkAccessSpeed выглядит так:

    private int accessOnce() { 
        int checkSum = 0; 
        for (long id : seq.access) 
            checkSum += impl.getById(id).getCheck(); 
        return checkSum; 
    } 

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

Реализация Описание Скорость (нс на операцию)
HashMapCache на основе java.util.HashMap из JDK 7 216 ± 30
GuavaCache на основе com.google.common.cache.CacheBuilder из Google Guava версии 12 459 ± 37
HighScaleCache на основе org.cliffc.high_scale_lib.NonBlockingHashMapLong из high-scale-lib Клифа Клика 143 ± 1
TroveCache на основе gnu.trove.map.hash.TLongObjectHashMap из Trove версии 3.0.2 101 ± 1
JavolutionCache на основе javolution.util.FastMap из Javolution версии 5.4.2 508 ± 26
HppcCache на основе com.carrotsearch.hppc.LongObjectOpenHashMap из HPPC версии 0.4.1 156 ± 1

Замеры проводились на процессоре Intel Core i5 520M (2.66GHz, 3MB L3 cache, DDR3 533MHz) работающим под управлением Windows 7 на Java(TM) SE Runtime Environment (build 1.7.0_02-b13) с Java HotSpot(TM) Server VM (build 22.0-b10, mixed mode), который запускался с параметрами "-server -ea -Xms1g -Xmx1g"

На самом деле, эти результаты легко объяснить без проведения замеров. HashMap и Guava CacheBuilder работают с long id через экземпляры объектов java.lang.Long, а high-scale-lib и Trove позволяют работать с примитивным типом long напрямую, как и требуется в моем интерфейсе Cache, благодаря чему выигрывают в производительности. Guava CacheBuilder проигрывает HashMap потому, что Guava CacheBuilder предоставляет более богатые функциональные возможности, хорошо иллюстрируя общий принцип: ради дополнительной функциональности всегда приходится приносить в жертву производительность. В тоже время high-scale-lib решает задачу масштабируемости на сотни ядер, принося в жертву однопоточную производительность и проигрывая Trove.

UPDATE: По просьбе читателей я добавил Javolution и HPPC. Javolution работает медленно из-за использования объектов Long и из-за того, что во главу дизайна Javolution, в отличии от всех других сравниваемых классов, поставлено требование реального времени, то есть гарантированного времени выполнения операции. Для этого всегда приходится приносить в жертву среднюю скорость работы, которую я замеряю в данном тесте. HPPC показывает хорошую скорость, так как оперирует примитивным типом long, но не раскрывает всего потенциала из-за особенностей используемых алгоритмов, существенно проигрывая Trove в этом тесте.

UPDATE2: Прогнал по 48 итераций каждого теста (16 разных наборов данных и порядков доступа, каждый со своим random seed, по 3 прогона на каждый набор). Теперь указанное в таблице среднеквадратическое отклонение вполне реалистично (наибольшая вариация в тех реализациях, которые выделяют объекты Long).

Можно ли сделать еще лучше? Конечно! Для этого надо совместить знания алгоритмов со знаниями особенностей устройства современных вычислительных систем. Я покажу как разработать быструю реализацию "by design", то есть так, что её преимущество будет очевидно еще до проведения каких-либо тестов. Читатели моего блога наверняка догадаются что часть секрета состоит в том, что память это новый диск. Но есть и немного чистой магии. Следите за обновлениями в блоге и приходите послушать мой доклад на конференции.

UPDATE: А вот и продолжение.


  • 1
а зачем "-ea" при измерении производительности?

Это просто привычка всегда указывать "-ea" при запуске любого тестового кода, ибо я на автомате расставляю "assert" в интересных местах кода для проверки корректности. Например, в классе BenchmarkAccessSpeed у меня написано assert impl.size() == seq.orders.size(), чтобы спать спокойно. А если без "-ea" его запускать, то как я буду спать спокойно?

Однако, так как я не пишу "assert" в критичных к производительности местах, то на результатах замера производительности это никак не сказывается.



ну а если кто-нибудь из авторов тех библиотек использует assert'ы в критичных для производительности местах?

Все эти библиотеки написаны грамотными людьми и все они доступны с исходным кодом. Не смотря на то, что при выключеных assertions в Java они не оказывают какого-либо влияния на производительность, писать assert внутри критических для производительности методов и циклов это, как мне кажется, все-равно плохой тон. Такого рода библиотеки хорошо тестируются с помощью unit tests, а не путем контроля их инвариантов assert-ами.

  • 1
?

Log in

No account? Create an account