| 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.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 [^] [^^] [^^^] [ответить] | +/– | Постраничная блокировка - это не атомарная операция и в больших БД страница може... текст свёрнут, показать | | |
| |
| |
| |
| |
| 12.35, parad (ok), 11:18, 15/04/2009 [^] [^^] [^^^] [ответить] | +/– | скорость доступа всегда O 1 , даже если при возникновении коллизии мы проведем п... текст свёрнут, показать | | |
|
|
| 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 может записи выдавать с сортировкой на основе ключа.
> Хэш насколько я понимаю так не может.
А ещё хеш не может искать по частичному совпадению.
| | |
|
| |
| 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
Напрмиер я нашел саму запись, такой же блок для обновления истории, больше для этой команды ничего нет.
Открытие файла недорогая операция, гораздо медленнее обновление кучи метаданных, связанное с созданием нового объекта в директории.
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
| | |
|
|
|
