"BerkeleyDB btree vs hash table benchmark (http://www.ioremap.net/node/213)" - результаты измерения производительности реализаци btree структур и хэшей в BerkeleyDB, в сравнении с организацией хранения данных в файлах в ФС ext3 (ключ к хэшу = имя файла). Интересно, что хэш в BerkeleyDB оказался быстрее btree, который в свою очередь обогнал метод хранения в файлах.
Результаты тестов заставляют задуматься о целесообразности замены файлового хранилища, системой подобной memcacheDB (http://memcachedb.org/) (хранение данных в BerkeleyDB базе с использование совместимого с memcached протокола).
URL: http://www.ioremap.net/node/213
Новость: http://www.opennet.me/opennews/art.shtml?num=21234
> Интересно, что хэш в BerkeleyDB оказался быстрее btree, который в свою очередь обогнал метод хранения в файлах.Метод поиска по хешу априори быстрей метода поиска, основанного на бинарных деревьях. А метод хранения в файлах тут вообще непричем - это все равно что палец с мужбулочным пространством сравнивать.
>Метод поиска по хешу априори быстрей метода поиска, основанного на бинарных деревьях.
>А метод хранения в файлах тут вообще непричем - это все
>равно что палец с мужбулочным пространством сравнивать.Например, индексы на основе хешей в PostgreSQL работали пару лет назад ощутимо медленее btree.
>
>Например, индексы на основе хешей в PostgreSQL работали пару лет назад ощутимо
>медленее btree.Это всего лишь означает, что постгресовцы неправильно выбрали размер ключа или алгоритм хэширования. В любом учебнике написано, что у нормального хэша время поиска не зависит от числа элементов, т.е. растет как O(1). У бинарных деревьев в лучшем случае O(ln n).
>Это всего лишь означает, что постгресовцы неправильно выбрали размер ключа или алгоритм хэширования.
>В любом учебнике написано, что у нормального хэша время поиска не зависит от числа элементов, т.е. растет как O(1). У бинарных деревьев в лучшем случае O(ln n).Кроме поиска есть ещё и редактирование. И в случае с хешем, надо блокировать весь хеш. И пусть весь мир подождёт :)
Кто же редактирует хеш??? В хешу пишуть и из него читають.
Ложь, никто не мешает блокировать как отдельный bucket, так и вообще отдельный элемент. А вообще, мне рассказывали про реализацию thread-safe хэша вообще без блокировок, чисто на атомарных операциях. Да, с изменением размера, как положено.
атомарными операциями не прокатит - на смп за атомарностью следит ядро, а доступ к этим блокировкам только через тред-мьютексы или ипц-семафоры.заполнение хеша происходит в 3этапа - вычесление хеша, проверка на коллизии вычеленного значения, вставка в массив. после второго этапа может возникнуть черти-что без блокировки ячейки. а мьютекс на каждую ячейку - это слишком дорого, поэтому и остается блокировать все, хоть даже и рв-локами.
>атомарными операциями не прокатит - на смп за атомарностью следит ядро, а
>доступ к этим блокировкам только через тред-мьютексы или ипц-семафоры.
>
>заполнение хеша происходит в 3этапа - вычесление хеша, проверка на коллизии вычеленного
>значения, вставка в массив. после второго этапа может возникнуть черти-что без
>блокировки ячейки. а мьютекс на каждую ячейку - это слишком дорого,
>поэтому и остается блокировать все, хоть даже и рв-локами.Что мешает прочитать мануал по BerkeleyDB и перестать фантазировать?
Для btree и hash там используется постраничная блокировка. Ни о каком блокировании всей базы речи нет.
Кстати, там же речь идет о сравнении производительности hash и btree. Резюме такое, что в зависимости от размера базы это немонотонная функция. Вначале (пока база влезает в оперативную память) - без разницы, потом узким местом становится IO и hash сливает, а потом начинает сказываться размер метаданных, который больше у btree, и в итоге на самых больших базах выигрывает hash. Разумеется, если locality не важна, а нужен только точный поиск по ключу и важна производительность.
>Кстати, там же речь идет о сравнении производительности hash и btree. Резюме
>такое, что в зависимости от размера базы это немонотонная функция. Вначале
>(пока база влезает в оперативную память) - без разницы, потом узким
>местом становится IO и hash сливает, а потом начинает сказываться размер
>метаданных, который больше у btree, и в итоге на самых больших
>базах выигрывает hash. Разумеется, если locality не важна, а нужен только
>точный поиск по ключу и важна производительность.В памяти хранится только кэш - все транзакции обязаны быть на диске в базе или логе во время коммита (хотя это можно несколько ослабить).
Дисковый ввод.вывод всегда является узким местом базы данных.
>Что мешает прочитать мануал по BerkeleyDB и перестать фантазировать?
>
>Для btree и hash там используется постраничная блокировка. Ни о каком блокировании
>всей базы речи нет.Постраничная блокировка - это не атомарная операция и в больших БД страница может стать о(sizeof(DB)) - 'о'-малое от размера бд, те фактические своим количеством сэмитировать блокировку ячейки. Если даже поставить лимит кол-ва страниц, то на тех-же больших бд возникнет эффект схожий с блокировкой все БД. Предлагаю не выпендриваться и перестать перефразировать мои слова. + мозг подключять при чтении документации.
>Кстати, там же речь идет о сравнении производительности hash и btree. Резюме
>такое, что в зависимости от размера базы это немонотонная функция. Вначале
>(пока база влезает в оперативную память) - без разницы, потом узким
>местом становится IO и hash сливает, а потом начинает сказываться размер
>метаданных, который больше у btree, и в итоге на самых больших
>базах выигрывает hash. Разумеется, если locality не важна, а нужен только
>точный поиск по ключу и важна производительность.Твою ###########! Хеш будет сливать только при малом размере БД (очень малом). При всех остальных, даже если он целиком будет храниться на диске - он будет впереди. Другое дело реализация - можно обосраться и сделать даже самый быстрый алгоритм медленее банального перебора. Если берклидб в документации пишет, то, что ты выше рассказал - то это явно у них проблемы с реализацией.
> перестать перефразировать мои слова. + мозг подключять
>при чтении документации."в случае с хешем, надо блокировать весь хеш"(svn)
"В случае с деревом - таже история. Нужно заблокировать все."(parad)
Таки теперь выясняется, что блокировать всё уже не надо?>Хеш будет сливать только при малом размере БД (очень малом).
>При всех остальных, даже если он целиком будет храниться на диске
>- он будет впереди.Забавная уверенность, учитывая, что хэш не дает гарантий по времени, и можно только надеятся, что для случайного ключа в среднем скорость будет вести себя как в идеальном случае, когда хэширующая функция подобрана под заранее известный набор ключей.
>только надеятся, что для случайного ключа в среднем скорость будет вести
>себя как в идеальном случае,Все это конечно замечательно, но для дерева то время поиска (включая и среднее) будет логарифмически расти с ростом числа записей в бд.А у хеша это время в среднем не растет.На бд с большим числом записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то что на конкретном ключе может быть и несколько медленнее чем в среднем обычно мало кого волнует.
>>только надеятся, что для случайного ключа в среднем скорость будет вести
>>себя как в идеальном случае,
>
>Все это конечно замечательно, но для дерева то время поиска (включая и
>среднее) будет логарифмически расти с ростом числа записей в бд.А у
>хеша это время в среднем не растет.На бд с большим числом
>записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то
>что на конкретном ключе может быть и несколько медленнее чем в
>среднем обычно мало кого волнует.Если хеш автоматически не меняет свой размер, то с ростом количества записей скорость доступа будет уменьшаться как O(количества ключей / количество ячеек в хеш-таблице), что по сути есть O(n).
Хеш-таблица подходит для случаев, когда количество ключей сравнимо с размером таблицы, т.е. максимум в несколько раз больше.
Как устроена таблица (в частности, есть ли в ней автоматическое изменение размера) в BDB, не известно.
> Если хеш автоматически не меняет свой размер, то с ростом количества записей скорость доступа будет уменьшаться как O(количества ключей / количество ячеек в хеш-таблице), что по сути есть O(n).скорость доступа всегда O(1), даже если при возникновении коллизии мы проведем повторную операцию хеширования получим O(2) = O(1). есть методы заполнения позволяющие иметь кпд хеша 95% при максимум 3х вычеслениях хеша на операцию записи/чтения, что O(3) = O(1).
тот метод, который возможно, вы имеете в виду (перебор в цикле всех последующих ячеек до нахождения свободной) описывается для облегчения понимания в начале каждого учебника, но никак не может быть использован в качестве рабочего варианта, т.к. сводит быстрый доступ по индексу к банальнобу перебору всех значений.
> Хеш-таблица подходит для случаев, когда количество ключей сравнимо с размером таблицы, т.е. максимум в несколько раз больше.
Читайте выше и дальше - это тоже самое начало любого учебника, есть методы быстрого заполнения хеша на 95%.
>>только надеятся, что для случайного ключа в среднем скорость будет вести
>>себя как в идеальном случае,
>
>Все это конечно замечательно, но для дерева то время поиска (включая и
>среднее) будет логарифмически расти с ростом числа записей в бд.А у
>хеша это время в среднем не растет.На бд с большим числом
>записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то
>что на конкретном ключе может быть и несколько медленнее чем в
>среднем обычно мало кого волнует.Ну, дык я и не спорю. Хэш рано или поздно на больших объемах победит деревья, но пока до этого дойдет - замотаешься пыль глотать.
Хотя практика сравнения среднего времени в смысле статистики с гарантированным worst case - кажется мне несколько порочной ...
>Таки теперь выясняется, что блокировать всё уже не надо?опять непонятно из какого пальца ты такое умозаключение высосал: выше я описал что постраничная блокировка - это бессмысленное действие на очень больших бд и так или иначе глобальная блокировка будет присутствовать всегда - от этого не уйдешь.
>Забавная уверенность, учитывая, что хэш не дает гарантий по времени, и можно
>только надеятся, что для случайного ключа в среднем скорость будет вести
>себя как в идеальном случае, когда хэширующая функция подобрана под заранее
>известный набор ключей.тут вообще тяжело догодаться что ты хочешь сказать. функция хеширования не занимается подгонкой под определенный набор, она вычесляет число(хеш), на основе которого высчитывается индекс. например, если в пямяти умещяется массив из 1млн экземпляров, а хеш-число - 64битное, то расчет индекса будет: i = 1млн * ( hashfunc( data ) / max( uint_64 )), где max( uint_64 ) = 0xffffffffffff, а i - индекс массива mas[i] куда/откуда мы должны положить/извлеч данные. + конечно обработка коллизий.
> на смп за атомарностью следит ядроугу, а мьютекс реализовываается сам на себе, надо думать? я про железные атомарные операции.
> после второго этапа может возникнуть черти-что без блокировки ячейки
для не-unique значений второй этап не нужен. я той реализации не видел, возможно это и был multimap.
> а мьютекс на каждую ячейку - это слишком дорого
совсем нет. теоретический потолок - в 2 раза больше памяти (пустой хэш, смещение=слово, мьютекс=слово). На практике (> 50% заполнение) - <1.5 раза. Не уверен, но можно под мьютексы и байты использовать.
>угу, а мьютекс реализовываается сам на себе, надо думать? я про железные
>атомарные операции.не хочется даже ничего спрашивать, боюсь услышать ответ.
>совсем нет. теоретический потолок - в 2 раза больше памяти (пустой хэш, смещение=слово, мьютекс=слово). На практике (> 50% заполнение) - <1.5 раза. Не уверен, но можно под мьютексы и байты использовать.
ты взял sizeof(phtrad_mutex_t)? флаг в руки. этот тип дефайнет указатель на структуру - эт раз. слово - это 2байта, указатель - минимум 4байта - это какбы два. три - не придумывай херню про байт, потомучто как минимум у тебя будет 256 мьютексов + это нужно сильно обидется чтобы так начать фантазировать. (извини если где-то, возможно, резко высказался, - давай будем объективными). четыре - хеш не хранит смещение, хеш может не хранить и само вычесленное хеш-число - это массив данных, занесенных в ячейку на основе вычесленного хеш-числа, указавшего номер ячейки для размещения + несколько методов борьбы с коллизиями, поэтому размер ячейки хеша может быть скольугоднобольшим.
можешь просто спросить если есть вопрос - придумывать незачем. для этого форум и создан. а бред, извини, в таких количествах раздражает.
>не хочется даже ничего спрашивать, боюсь услышать ответНе сомневаюсь. А я имел в виду всего навсего lock cmpxchg (для x86). Не думал что это настолько неочевидно.
>ты взял sizeof(phtrad_mutex_t)? флаг в руки. этот тип дефайнет указатель на структуру
Нет, я взял размер регистра. От реализации тредов тут вообще ничего не зависит, спинлоки всегда будут эффективней ядерных мьютексов (разумеется речь идет про SMP).
>- эт раз. слово - это 2байта, указатель - минимум 4байта
Слово это размер регистра общего назначния. Когда пишешь под что-то кроме x86, от ереси типа слово=2байта быстро отвыкаешь.
>- это какбы два. три - не придумывай херню про байт,
>потомучто как минимум у тебя будет 256 мьютексов + это нужно
>сильно обидется чтобы так начать фантазировать.Я имел в виду cmpxchg XXX, _byte ptr_ [YYY]
Просто не уверен насчет ее производителньости и сайдэффектов, к тому же такие мьютексы придется хранить сбоку из-за выравнивания.>четыре - хеш не хранит смещение, хеш может не хранить и само
>вычесленное хеш-число - это массив данных, занесенных в ячейку
>на основе вычесленного хеш-числа, указавшего номер ячейки
>для размещения + несколько методов борьбы с коллизиями,
>поэтому размер ячейки хеша может быть скольугоднобольшим.Боже мой. Вы бы для начала все-таки читали, что читаете, а не изображали преподавателя инфорамтики. Хэш никогда не хранит вычисленное хэш число, потому что это и есть индекс бакета. А по этому индексу надо хранить ни что иное как адрес(=смещение) массива/первого элемента списка элементов данных, имеющих этот хэш.
В любом случае, если вы предлагаете напихать в бакет скольугодномного всякого мусора, я думаю не то что int, но и pthread_mutex_t со всеми его прелестями вас там не смутит.
>а бред, извини, в таких количествах раздражает.
Полностью согласен
В случае с деревом - таже история. Нужно заблокировать все.
Что-то слабо верится во все эти бенчмарки, да и результат зависит от слишком многих условий.А MemcacheDB -- судя по всему прикольная штука, надо попробовать.
> Интересно, что хэш в BerkeleyDB оказался быстрее btree,О! Капитан Очевидность! А если просто ПОЧИТАТЬ ОПИСАНИЕ технологий hash и btree - это и без бенчмарков будет понятно.Просто не помню как в BDB с его API а в токийском кабинете - btree может записи выдавать с сортировкой на основе ключа.Хэш насколько я понимаю так не может.Посему право на жизнь имеют оба.
> btree может записи выдавать с сортировкой на основе ключа.
> Хэш насколько я понимаю так не может.А ещё хеш не может искать по частичному совпадению.
http://www.ioremap.net/gallery/elliptics_bdb_hash_btree_file...График несколько неоднозначен.
Линии 1025 байтных записей обрываются в разных местах.
И ближе к концу "файловая реализация" показывает чуть больше быстродействия.
Может кто-нибудь пояснить, в каких попугаях проводятся измерения?
Может просто тесты останавливались в разное время?
По графику файловая реализация для маленьких записей нигде не быстрее, а для больших так и должно быть. В блоге описано, что bdb сливает файловому хранилищу при больших записях и особенно для записей с большм смещением.
Если в тексте блога сходить по ссылочке "yesterday", то там можно наткнуться на такую чудненькую фразу:>>While I expect there may be some bugs, getting I started to read bdb documentation the first time yesterday, it works at least for the purpose of performance testing.
Что, теперь про каждый студенческий hello world будем новости на опеннете постить? Называя их при этом "измерениями производительности"?
Этот хояин блога zbr - автор POHMELFS оказывается, а elliptics - сервер для хранения метаданных для неё. Тогда беру свои слова про студенческие hello world назад :)Это уже чем-то напоминает PVFS2 - там тоже bdb используют для хранения метаданных. У них правда сервер - это userspace процесс, а только клиент выполнен как ядерный модуль.
Можете не брать. Евгений порою несколько импульсивен в своих высказаваниях и выводах. Хотя конечно за последниие лет шесть ситуация меняется в лучшую сторону.
По любому в данном случае измерялась не производительность BDB backend а результаты его применения в сыром виде в даже не конкректном случае. Не удивлюсь если прогоны были на разных выборках.BTW Поскольку на графике отсутствуют оценки погрешности и load time,а число прогонов недостаточно для применения правила трех сигм, можно смело зачислять в поделку студента.
PS. Например при идеальных условиях со стороны USERSPACE прогоны чисто вычислительных алгоритмов на абсолютно идентичных выборках на P4 и выше запросто вам дадут отклонения производительности от 1 до 3%, а при неправильном выравнивании данных до двух раз. И все из-за другого состояния кэша данных,кода,TLB и модуля предсказания переходов.
Сложно сказать, в чем там косяк, не видя кода, но настораживает такой момент.Насколько я понял, тестируется скорость _записи_ в файл (file IO) и в BerkeleyDB. При этом, чтобы в файл что-то можно было записать - его надо открыть. Для BDB - это не столь важно, можно открыть файл с базой в начале, а потом иметь в наличии готовый дескриптор. Это, кстати, рекомендуемый способ работы с BDB, поскольку открытие файла - дорогая операция. Я не знаю, как это сделано у zbr, но есть нехорошие подозрения, что тестирует он как раз скорость открытия/закрытия файлов.
>Насколько я понял, тестируется скорость _записи_ в файл (file IO) и в
>BerkeleyDB. При этом, чтобы в файл что-то можно было записать -
>его надо открыть. Для BDB - это не столь важно, можно
>открыть файл с базой в начале, а потом иметь в наличии
>готовый дескриптор. Это, кстати, рекомендуемый способ работы с BDB, поскольку открытие
>файла - дорогая операция. Я не знаю, как это сделано у
> zbr, но есть нехорошие подозрения, что тестирует он как раз
>скорость открытия/закрытия файлов.Код можно посмотреть в git: http://www.ioremap.net/cgi-bin/gitweb.cgi?p=elliptics.git;a=...
Напрмиер я нашел саму запись, такой же блок для обновления истории, больше для этой команды ничего нет.Открытие файла недорогая операция, гораздо медленнее обновление кучи метаданных, связанное с созданием нового объекта в директории.
276 memset(&key, 0, sizeof(DBT));
277 memset(&data, 0, sizeof(DBT));
278
279 key.data = cmd->id;
280 key.size = DNET_ID_SIZE;
281
282 data.data = buf;
283 data.size = io->size;
284 data.ulen = io->size;
285 data.flags = DB_DBT_PARTIAL | DB_DBT_USERMEM;
286 data.doff = io->offset;
287 data.dlen = io->size;
288
289 err = e->cursor->c_put(e->cursor, &key, &data, DB_KEYFIRST);
290 if (err) {
291 e->db->err(e->db, err, "%s: object put failed: offset: %llu, size: %llu, err: %d",
292 dnet_dump_id(cmd->id), (unsigned long long)io->offset,
293 (unsigned long long)io->size, err);
294 goto err_out_exit;
295 }
296