The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

Результаты измерения производительности BerkeleyDB

13.04.2009 12:05

"BerkeleyDB btree vs hash table benchmark" - результаты измерения производительности реализаци btree структур и хэшей в BerkeleyDB, в сравнении с организацией хранения данных в файлах в ФС ext3 (ключ к хэшу = имя файла). Интересно, что хэш в BerkeleyDB оказался быстрее btree, который в свою очередь обогнал метод хранения в файлах.

Результаты тестов заставляют задуматься о целесообразности замены файлового хранилища, системой подобной memcacheDB (хранение данных в BerkeleyDB базе с использованием совместимого с memcached протокола).

  1. Главная ссылка к новости (http://www.ioremap.net/node/21...)
Лицензия: CC-BY
Тип: Обобщение
Ключевые слова: BerkeleyDB, benchmark, database, speed
При перепечатке указание ссылки на opennet.ru обязательно
Обсуждение (30) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.1, parad (ok), 13:17, 13/04/2009 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    > Интересно, что хэш в BerkeleyDB оказался быстрее btree, который в свою очередь обогнал метод хранения в файлах.

    Метод поиска по хешу априори быстрей метода поиска, основанного на бинарных деревьях. А метод хранения в файлах тут вообще непричем - это все равно что палец с мужбулочным пространством сравнивать.

     
     
  • 2.2, Аноним (-), 13:56, 13/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    >Метод поиска по хешу априори быстрей метода поиска, основанного на бинарных деревьях.
    >А метод хранения в файлах тут вообще непричем - это все
    >равно что палец с мужбулочным пространством сравнивать.

    Например, индексы на основе хешей в PostgreSQL работали пару лет назад ощутимо медленее btree.

     
     
  • 3.3, sky (??), 14:51, 13/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    >
    >Например, индексы на основе хешей в PostgreSQL работали пару лет назад ощутимо
    >медленее btree.

    Это всего лишь означает, что постгресовцы неправильно выбрали размер ключа или алгоритм хэширования. В любом учебнике написано, что у нормального хэша время поиска не зависит от числа элементов, т.е. растет как O(1). У бинарных деревьев в лучшем случае O(ln n).

     
     
  • 4.13, svn (??), 19:35, 13/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    >Это всего лишь означает, что постгресовцы неправильно выбрали размер ключа или алгоритм хэширования.
    >В любом учебнике написано, что у нормального хэша время поиска не зависит от числа элементов, т.е. растет как O(1). У бинарных деревьев в лучшем случае O(ln n).

    Кроме поиска есть ещё и редактирование. И в случае с хешем, надо блокировать весь хеш. И пусть весь мир подождёт :)

     
     
  • 5.16, pavlinux (ok), 22:34, 13/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Кто же редактирует хеш??? В хешу пишуть и из него читають.
     
  • 5.18, Guest (??), 00:36, 14/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Ложь, никто не мешает блокировать как отдельный bucket, так и вообще отдельный элемент. А вообще, мне рассказывали про реализацию thread-safe хэша вообще без блокировок, чисто на атомарных операциях. Да, с изменением размера, как положено.
     
     
  • 6.21, parad (ok), 10:47, 14/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    атомарными операциями не прокатит - на смп за атомарностью следит ядро, а доступ к этим блокировкам только через тред-мьютексы или ипц-семафоры.

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

     
     
  • 7.23, geekkoo (ok), 11:05, 14/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    >атомарными операциями не прокатит - на смп за атомарностью следит ядро, а
    >доступ к этим блокировкам только через тред-мьютексы или ипц-семафоры.
    >
    >заполнение хеша происходит в 3этапа - вычесление хеша, проверка на коллизии вычеленного
    >значения, вставка в массив. после второго этапа может возникнуть черти-что без
    >блокировки ячейки. а мьютекс на каждую ячейку - это слишком дорого,
    >поэтому и остается блокировать все, хоть даже и рв-локами.

    Что мешает прочитать мануал по BerkeleyDB и перестать фантазировать?

    Для btree и hash там используется постраничная блокировка. Ни о каком блокировании всей базы речи нет.

    Кстати, там же речь идет о сравнении производительности hash и btree. Резюме такое, что в зависимости от размера базы это немонотонная функция. Вначале (пока база влезает в оперативную память) - без разницы, потом узким местом становится IO и hash сливает, а потом начинает сказываться размер метаданных, который больше у btree, и в итоге на самых больших базах выигрывает hash. Разумеется, если locality не важна, а нужен только точный поиск по ключу и важна производительность.

     
     
  • 8.24, Аноним (-), 12:41, 14/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    В памяти хранится только кэш - все транзакции обязаны быть на диске в базе или л... текст свёрнут, показать
     
  • 8.25, parad (ok), 17:25, 14/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Постраничная блокировка - это не атомарная операция и в больших БД страница може... текст свёрнут, показать
     
     
  • 9.31, geekkoo (ok), 09:06, 15/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    в случае с хешем, надо блокировать весь хеш svn В случае с деревом - таже ис... текст свёрнут, показать
     
     
  • 10.32, User294 (??), 10:40, 15/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Все это конечно замечательно, но для дерева то время поиска включая и среднее ... текст свёрнут, показать
     
     
  • 11.33, Аноним (-), 10:59, 15/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Если хеш автоматически не меняет свой размер, то с ростом количества записей ско... текст свёрнут, показать
     
     
  • 12.35, parad (ok), 11:18, 15/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    скорость доступа всегда O 1 , даже если при возникновении коллизии мы проведем п... текст свёрнут, показать
     
  • 11.37, geekkoo (ok), 14:52, 15/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Ну, дык я и не спорю Хэш рано или поздно на больших объемах победит деревья, но... текст свёрнут, показать
     
  • 10.34, parad (ok), 11:02, 15/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    опять непонятно из какого пальца ты такое умозаключение высосал выше я описал ч... текст свёрнут, показать
     
  • 7.27, Guest (??), 23:07, 14/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    > на смп за атомарностью следит ядро

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

    > после второго этапа может возникнуть черти-что без блокировки ячейки

    для не-unique значений второй этап не нужен. я той реализации не видел, возможно это и был multimap.

    > а мьютекс на каждую ячейку - это слишком дорого

    совсем нет. теоретический потолок - в 2 раза больше памяти (пустой хэш, смещение=слово, мьютекс=слово). На практике (> 50% заполнение) - <1.5 раза. Не уверен, но можно под мьютексы и байты использовать.

     
     
  • 8.28, parad (??), 00:51, 15/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    не хочется даже ничего спрашивать, боюсь услышать ответ ты взял sizeof phtrad_m... текст свёрнут, показать
     
     
  • 9.29, Guest (??), 04:35, 15/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Не сомневаюсь А я имел в виду всего навсего lock cmpxchg для x86 Не думал чт... текст свёрнут, показать
     
  • 5.19, parad (??), 01:09, 14/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    В случае с деревом - таже история. Нужно заблокировать все.
     

  • 1.4, Аноним (-), 15:17, 13/04/2009 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Что-то слабо верится во все эти бенчмарки, да и результат зависит от слишком многих условий.

    А MemcacheDB -- судя по всему прикольная штука, надо попробовать.

     
  • 1.6, User294 (??), 16:05, 13/04/2009 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    > Интересно, что хэш в BerkeleyDB оказался  быстрее btree,

    О! Капитан Очевидность! А если просто ПОЧИТАТЬ ОПИСАНИЕ технологий hash и btree - это и без бенчмарков будет понятно.Просто не помню как в BDB с его API а в токийском кабинете - btree может записи выдавать с сортировкой на основе ключа.Хэш насколько я понимаю так не может.Посему право на жизнь имеют оба.

     
     
  • 2.15, svn (??), 19:38, 13/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    > btree может записи выдавать с сортировкой на основе ключа.
    > Хэш насколько я понимаю так не может.

    А ещё хеш не может искать по частичному совпадению.

     

  • 1.7, XoRe (ok), 16:10, 13/04/2009 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    http://www.ioremap.net/gallery/elliptics_bdb_hash_btree_file.png

    График несколько неоднозначен.
    Линии 1025 байтных записей обрываются в разных местах.
    И ближе к концу "файловая реализация" показывает чуть больше быстродействия.
    Может кто-нибудь пояснить, в каких попугаях проводятся измерения?

     
     
  • 2.8, Аноним (-), 17:06, 13/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Может просто тесты останавливались в разное время?
    По графику файловая реализация для маленьких записей нигде не быстрее, а для больших так и должно быть. В блоге описано, что bdb сливает файловому хранилищу при больших записях и особенно для записей с большм смещением.
     

  • 1.10, geekkoo (ok), 17:13, 13/04/2009 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Если в тексте блога сходить по ссылочке "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 будем новости на опеннете постить? Называя их при этом "измерениями производительности"?

     
     
  • 2.11, geekkoo (ok), 17:38, 13/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Этот хояин блога zbr - автор POHMELFS оказывается, а elliptics - сервер для хранения метаданных для неё. Тогда беру свои слова про студенческие hello world назад :)

    Это уже чем-то напоминает PVFS2 - там тоже bdb используют для хранения метаданных. У них правда сервер - это userspace процесс, а только клиент выполнен как ядерный модуль.

     

  • 1.14, alexr (??), 19:37, 13/04/2009 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    Можете не брать. Евгений порою несколько импульсивен в своих высказаваниях и выводах. Хотя конечно за последниие лет шесть ситуация меняется в лучшую сторону.

    По любому в данном случае измерялась не производительность BDB backend а результаты его применения в сыром виде в даже не конкректном случае. Не удивлюсь если прогоны были на разных выборках.

    BTW Поскольку на графике отсутствуют оценки погрешности и load time,а число прогонов недостаточно для применения правила трех сигм, можно смело зачислять в поделку студента.

    PS. Например при идеальных условиях со стороны USERSPACE прогоны чисто вычислительных алгоритмов на абсолютно идентичных выборках на P4 и выше запросто вам дадут отклонения производительности от 1 до 3%, а при неправильном выравнивании данных до двух раз. И все из-за другого состояния кэша данных,кода,TLB и модуля предсказания переходов.

     
     
  • 2.20, geekkoo (ok), 10:33, 14/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    Сложно сказать, в чем там косяк, не видя кода, но настораживает такой момент.

    Насколько я понял, тестируется скорость _записи_ в файл (file IO) и в BerkeleyDB. При этом, чтобы в файл что-то можно было записать - его надо открыть. Для BDB - это не столь важно, можно открыть файл с базой в начале, а потом иметь в наличии готовый дескриптор. Это, кстати, рекомендуемый способ работы с BDB, поскольку открытие файла - дорогая операция. Я не знаю, как это сделано у  zbr, но есть нехорошие подозрения, что тестирует он как раз скорость открытия/закрытия файлов.

     
     
  • 3.22, Аноним (-), 10:59, 14/04/2009 [^] [^^] [^^^] [ответить]  
  • +/
    >Насколько я понял, тестируется скорость _записи_ в файл (file IO) и в
    >BerkeleyDB. При этом, чтобы в файл что-то можно было записать -
    >его надо открыть. Для BDB - это не столь важно, можно
    >открыть файл с базой в начале, а потом иметь в наличии
    >готовый дескриптор. Это, кстати, рекомендуемый способ работы с BDB, поскольку открытие
    >файла - дорогая операция. Я не знаю, как это сделано у
    > zbr, но есть нехорошие подозрения, что тестирует он как раз
    >скорость открытия/закрытия файлов.

    Код можно посмотреть в git: http://www.ioremap.net/cgi-bin/gitweb.cgi?p=elliptics.git;a=blob;f=example/bd
    Напрмиер я нашел саму запись, такой же блок для обновления истории, больше для этой команды ничего нет.

    Открытие файла недорогая операция, гораздо медленнее обновление кучи метаданных, связанное с созданием нового объекта в директории.

    [code]
    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 [/code]

     

     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Спонсоры:
    Слёрм
    Inferno Solutions
    Hosting by Ihor
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2019 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру