The OpenNET Project / Index page

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

форумы  помощь  поиск  регистрация  майллист  вход/выход  слежка  RSS
"Оптимизация алгоритма btree позволила увеличить производител..."
Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Изначальное сообщение [ Отслеживать ]

"Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от opennews on 15-Июн-10, 14:54 
Poul-Henning Kamp, принимающий участие в разработке FreeBSD, опубликовал статью (http://queue.acm.org/detail.cfm?id=1814327) в которой рассмотрел проблемы в работе классического алгоритма btree. При разработке высокопроизводительного http-акселератора  Varnish (http://varnish-cache.org/) было замечено, что при работе btree не учитывается состояние виртуальной памяти, что при высокой нагрузке на VM приводит к провалам в производительности (возникновение паразитных задержек из-за VM page fault). Предложенная в проекте Varnish реализация бинарных деревьев продемонстрировала увеличение пиковой производительности до 10 раз.

Http-акселератор Varnish используется в таких проектах, как Facebook, Wikia и Slashdot. Работа Varnish базируется на задействовании современных методов мультиплексирования соединений, таких как epoll и kqueue, а также системных вызовов sendfile и madvise. Для формирования конфигурации используется специальный язык VCL (http://varnish-cache.org/wiki/VCL), который за...

URL: http://queue.acm.org/detail.cfm?id=1814327
Новость: http://www.opennet.ru/opennews/art.shtml?num=26969

Высказать мнение | Ответить | Правка | Cообщить модератору

Оглавление

Сообщения по теме [Сортировка по времени | RSS]


1. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от anonimus on 15-Июн-10, 14:54 
> увеличение пиковой производительности до 10 раз.

лихо!

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

2. "Оптимизация алгоритма btree позволила увеличить производител..."  –4 +/
Сообщение от User294 (ok) on 15-Июн-10, 15:08 
ИМХО, если волнует производительность, попросту нефиг на виртуальную память рассчитывать вообще. При современных объемах оперативки - чувак явно опоздал с исследованиями лет на 10. Вот лет 10 назад ему бы за такое исследование памятник при жизни воздвигли :)
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

3. "Оптимизация алгоритма btree"  +4 +/
Сообщение от Andrey Mitrofanov on 15-Июн-10, 15:21 
>ИМХО, если волнует производительность, попросту нефиг на виртуальную память рассчитывать вообще.

Нынче вся память - виртуальная, это раз. Не факт, что там речь про "своп", это два. Вполне возможно, про "промахи TLB" или что-то подобное -- более "тонкое". См.например, http://lwn.net/Articles/374424/?format=printable

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

16. "Оптимизация алгоритма btree"  +/
Сообщение от User294 (ok) on 15-Июн-10, 17:48 
> Нынче вся память - виртуальная, это раз.

Но проседание скорости ее работы начинается только когда объем запрошенной памяти начинает превышать объем физической. Грубо говоря - если нет page faults, нет и проблем от них.

> Вполне возможно, про "промахи TLB" или что-то подобное -- более "тонкое".

В данном случае насколько я понял упор сугубо на page faults и как с ними жить. Ну да, сперва создадим себе проблем а потом с помпой их разрюхаем...

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

20. "Оптимизация алгоритма btree"  +/
Сообщение от аноним on 15-Июн-10, 18:59 
Для альтернативно одарённых - кроме размеров рамы выросли и объёмы траффика. Прикинь на бумажке сколько рамы нужно чтобы закешить да хоть грёбанный Ю-туб и иди уже в трактористы-мелиораторы, Ыксперт :(
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

23. "Оптимизация алгоритма btree"  +/
Сообщение от User294 (ok) on 15-Июн-10, 20:08 
>на бумажке сколько рамы нужно чтобы закешить да хоть грёбанный Ю-туб

Закешить что именно? Контент? Каталог оного? Или wtf?

>и иди уже в трактористы-мелиораторы, Ыксперт :(

А вы, очевидно, в уютную пещерку. И не забудьте свою дубинку :).

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

24. "Оптимизация алгоритма btree"  –3 +/
Сообщение от аноним on 15-Июн-10, 20:30 
> В данном случае насколько я понял упор сугубо на page faults и как с ними жить. Ну да, сперва создадим себе проблем а потом с помпой их разрюхаем...

Господи, какое феерическое ламерство. Иди почитай что такое page fault, а то так договоришься до "придумали себе kernel panic'ов, а теперь мужественно их чиним".

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

28. "Оптимизация алгоритма btree"  +2 +/
Сообщение от User294 (ok) on 15-Июн-10, 21:08 
Я в курсе что такое page fault-ы, спасибо. Когда потребовалась страница памяти которой нет в физической оперативке, процессор генерит исключение. И по этому поводу обработчиком оного в операционке страница памяти подгружается откуда-то сбоку (из свопа, как правило на диске, хотя науке известны и более извратные варианты). И что такое memory pressure - представляю себе.

Но не очень вдупляю зачем все это сделано вот так. Да, возможно я тупой, но если вы не можете в 2 словах объяснить этого не только мне но и даже кухарке - вы ничем таким не лучше, если что. Такое ощущение что человек сделал эквивалент каких-то иных существующих схем но несколько более странными методами, после чего с помпой доказал что в выбранных им парадигмах и условиях обычный b-tree хуже его изобретения, дескать.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

36. "Оптимизация алгоритма btree"  +/
Сообщение от аноним on 16-Июн-10, 20:04 
>Но не очень вдупляю зачем все это сделано вот так.

То есть memory mapped file - одно из немногих _реальных_ технологических улучшений за последние 15 лет ... как то прошли мимо тебя да? :) Ну так я и говорю - Ыксперт!

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

4. "Оптимизация алгоритма btree позволила увеличить производител..."  –1 +/
Сообщение от sluge (ok) on 15-Июн-10, 15:26 
ну дак ты знаешь сколько чел одновременно ломятся на фэйсбук? тут и терабайта оперативки не напасешься! так что оптимизаторам респект!
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

9. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от hostmaster (??) on 15-Июн-10, 16:10 
так там и стоит далеко не один сервер, а собрать кластер из кешей на терабайт не сложно были бы деньги

информация о том что facebook использует varnish есть только на сайте varnish-а ... к чему бы это

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

11. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от Фкук on 15-Июн-10, 16:19 
При современных объемах оперативки ?

Вам свободно в 64 ГБ?
Мне - нет. А больше на мать не воткнуть.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

26. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от Дмитрий (??) on 15-Июн-10, 20:34 
Покупайте нормальную материнку...Вон STSS продаёт машинки 2U не c 64, а с 512Гб....вам этого мало ??
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

19. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от аноним on 15-Июн-10, 18:55 
VM != Swap, dude! Ты не заговаривайся, сейчас 99.9% осей c VM.

И перец пишет: "A 300-GB backing store, memory mapped on a machine with no more than 16 GB of RAM, is quite typical."   Лет 10-15 назад были бы те же цифры но MB, лет через 5-10 опять то же но TB ... суть того что он предлагает это не изменит ни на йоту.

А ты статью то читал?! А то меня мучают смутные сомнения(С)

PS: Ну а то что "640 Кб хватит всем" - мы уже слышали, да  :)

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

27. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от User294 (ok) on 15-Июн-10, 20:58 
>VM != Swap, dude!

А еще 2 * 2 == 4.

>Ты не заговаривайся, сейчас 99.9% осей c VM.

Для капитанов намекаю: имелась в виду физическая оператива. Почему-то на небольшой ляп в терминологии сразу вылезло куча КО, ехидно констатировавших "акелла промахнулся, акелла промахнулся!" :)

>И перец пишет: "A 300-GB backing store, memory mapped on a machine
>with no more than 16 GB of RAM, is quite typical."

Ну вообще да, только опять же - в конечном итоге - на традиционных дисках I/O медленное. И если уж оно есть - оно есть. Его количество разумеется можно уменьшить, загнав часто юзаемые сущности в память а

>А ты статью то читал?! А то меня мучают смутные сомнения(С)

Да, но не совсем понял нафиг чувак сперва придумал себе проблемы ("а давайте начнем свопиться?!") а потом их с помпой решил ("а давайте-ка уменьшим число page fault-ов"). Какое-то весьма хацкерское решение, сильно закладывающееся на специфику VM и кроме того, если уж товарисч говорит о устаревших компьютерах - вообще, существует мнение что в будущем компьютеры будут как раз содержать 1-2 типа памяти, возможно даже энергонезависимой. И быстрой. И никаких медленных дисков. Вообще. Глядя на рост размеров оперативы и флеша - думаю что этот весьма немолодой прогноз не так уж и неправилен. Тот же флеш по скорости чтения в общем то не особо проигрывает оперативке (а чего б ему?). По скорости записи - проигрывает ессно(но, собссно, как сам товарисч и написал, это как правило сравнительно редкая операция).

>PS: Ну а то что "640 Кб хватит всем" - мы уже слышали, да  :)

Чудес не бывает - или данные лезут в оперативку(и скорость их извлечения растет в тысячи раз), или не лезут и будут просадки на медленное IO с носителем на ажно миллисекунды (по масштабам оперативы это гигантские времена). Такое ощущение что товарисч толи изобретает велик, толи ставит костыли манагеру виртуальной памяти, толи еще что-то в этом же духе. Выглядит забавно. А, гм, решения существовавшие до чувака были чем-то принципиально хуже? Ну да, они не оперировали в парадигме "все - виртуальная память", явно деля на память (буфера/кеши) и диски(медленный стораж). Вот собссно сравнения этого я не вижу. А так то да, в парадигме "а давайте все загоним в виртуальную память и начнем ее безбашенно использовать как будто ее и правда 2^64 есть" - наверное алгоритм чувака и правда хорош. А вот сама парадигма - какая-то довольно странная, имхо. Лезет глубоко в недра особенности работы VM но зато абстрагируется от "дисков" и "памяти". А смысл? Тем более такой сенсационный заголовок и упоминание Кнута и т.п.. oO

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

37. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от аноним on 16-Июн-10, 20:23 
>>А ты статью то читал?! А то меня мучают смутные сомнения(С)

Всё - сомнения меня больше не мучают!
Ыксперт статью __НЕ__ читал, либо ангельских букв не осилил :)


>Да, но не совсем понял нафиг чувак сперва придумал себе проблемы ("а
>давайте начнем свопиться?!") а потом их с помпой решил ("а давайте-ка

Ну конечно, не всем же везёт жить в Ыдеальном мире Ыкспертов у которых данные _всегда_ влазят в 640KB :)


>кроме того, если уж товарисч говорит о устаревших компьютерах - вообще,

Наоборот - он говорит о новых - modern компьютерах. Которые начались с VAX'а :)

>существует мнение что в будущем компьютеры будут как
>раз содержать 1-2 типа памяти, возможно даже энергонезависимой. И быстрой. И
>никаких медленных дисков. Вообще. Глядя на рост размеров оперативы и флеша

Просто ___шикарнейшее___ подтверждение моих подозрений ! :)

В статье автор проводил сравнительные испытания на нотике с SSD-диском, и указал что на традиционных выигрыш будет даже больше ....  :)

Кроме того имею напокобелимую уверенность - если бы статью написал не один из разработчиков FreeBSD, а кто нить из линуксовых - Ыксперт с таким же неиствовством и пренебрежением здравым смыслом доказывал бы РеволюЧионность и "неимение мировых аналогов" :)

За сим торжественно присваиваю User294 пожизненный тиул ЫкспертЪ с занесением в грудную клетку :)))) Амба.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

6. "Оптимизация алгоритма btree позволила увеличить производител..."  –1 +/
Сообщение от avatar (ok) on 15-Июн-10, 15:53 
Надо выключать swap тогда такие проблемы возникать не будут.
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

10. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от Tav (ok) on 15-Июн-10, 16:14 
Ага, и пусть OOM Killer убивает всех несогласных с таким решением.

Серьезно: если вы хотите, чтобы своп использовался только в крайнем случае, установите соответствующие параметры VM (как минимум, swapinness), но имейте в виду, что в Линуксе оперативная память не простаивает зря, даже когда она не занята пользовательскими процессами, поэтому все время держать данные неактивных процессов в оперативной памяти нерационально.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

13. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от avatar (ok) on 15-Июн-10, 16:44 
>Ага, и пусть OOM Killer убивает всех несогласных с таким решением.
>
>Серьезно: если вы хотите, чтобы своп использовался только в крайнем случае, установите
>соответствующие параметры VM (как минимум, swapinness), но имейте в виду, что
>в Линуксе оперативная память не простаивает зря, даже когда она не
>занята пользовательскими процессами, поэтому все время держать данные неактивных процессов в
>оперативной памяти нерационально.

Это где это у акселератора неиспользуемые данные для выгрузки в своп?

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

22. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от User294 (ok) on 15-Июн-10, 20:05 
>поэтому все время держать данные неактивных процессов в
>оперативной памяти нерационально.

Ну извините, или времена реакции, или экономия оперативки. Диски штука медленная, да.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

7. "Оптимизация алгоритма btree позволила увеличить производител..."  –1 +/
Сообщение от zomg on 15-Июн-10, 16:02 
Wikia?
Может Wikipedia? Wikimapia?
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

15. "Оптимизация алгоритма btree позволила увеличить производител..."  +1 +/
Сообщение от Аноним (??) on 15-Июн-10, 16:53 
>Wikia?
>Может Wikipedia? Wikimapia?

нет, wikia.com

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

8. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от hostmaster (??) on 15-Июн-10, 16:05 
Для тех кто в танке замечу что описанные изменения есть пока только в trunk/
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

12. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от Аноним (??) on 15-Июн-10, 16:21 
Наглая ложь.
В статье ни слова о btree.

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

// pppp

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

17. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от Аноним (??) on 15-Июн-10, 18:13 
"локальные по памяти программы работают существенно эффективнее наиболее оптимальных с теоретической точки зрения" = "огурцы ложкой банка майонеза"
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

18. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от tn on 15-Июн-10, 18:29 
> Наглая ложь.
> В статье ни слова о btree.

8-ой абзац:

> A quick browse of the mental catalog flipped up the binary-heap card, which....

http://en.wikipedia.org/wiki/Binary_heap :

> A binary heap is a heap data structure created using a binary tree.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

34. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от Аноним (??) on 16-Июн-10, 11:16 
>> Наглая ложь.
>> В статье ни слова о btree.
>
>8-ой абзац:
>
>> A quick browse of the mental catalog flipped up the binary-heap card, which....
>
>http://en.wikipedia.org/wiki/Binary_heap :
>
>> A binary heap is a heap data structure created using a binary tree.

binary tree != b-tree

Ваш КО

// pppp

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

21. "Оптимизация алгоритма btree позволила увеличить производител..."  +/
Сообщение от аноним on 15-Июн-10, 19:02 
Кстати - Varnish сам по себе целиком и полностью на парадигме "Нет дисков и RAM'ы - есть VM!" И надо сказать продугд удался ...
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

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