| Erlang avalanche | Оценить ![]() ![]() ![]() ![]() ![]() ![]() |
| От: | Lazy Cjow Rhrr | lj://_lcr_ |
| Дата: | 12.12.06 15:03 | |
| Оценка: | 528 (40) | |
| ... или почему имплементация Erlang style concurrency под обычные VM очень проблематична (“очень проблематична” – это потому что я ненавижу слово “невозможно”). Я собираюсь довольно сильно углубиться в детали (в конце концов, внимание к деталям – это то что отличает профи от любителя 1. Хотя даже сами эрланговцы шутят, что soft real time – это “basically nothing”, тем не менее разница между soft real-time и отсутствием вообще каких-либо гарантий существенна. (Для сложных систем обеспечить SRT довольно трудно, и существуют ли вообще сложные системы с HRT я не знаю). Кроме того, для задач телекома важно, чтобы и время отклика было очень мало (речь идёт о милисекундах). Здесь “soft” означает, “мы не можем _абсолютно_ гарантировать всё, но мы проектировали платформу с самого начала так, чтобы можно было _практически_ гарантировать достаточно быстрый отклик”. Это гораздо больше того, что может сказать здесь, скажем, Ява (и это неудивительно, поскольку Ява проектировалась так, чтобы сказать кое-что в другом месте). То есть этим абзацем я хочу сказать, что SRT отнюдь не пустой звук и фатально влияет на весь дизайн системы как в малом масштабе (например, отсутствие деструктивного изменения туплов), так и в большом (например, отсутствие встроенных ленивых вычислений). И это требование может (и будет) конфликтовать с существующими платформами (куда требование SRT не закладывалось). 2. Первый отпечаток – это решение о том, как распределяется время среди процессов. Наприме, в есть аналогичные легковесные процессы в Питоне (stackless microthreads, Candygram), в Яве (Scala actors) и в Лиспе (Distel). В сущности, что такое параллельная программа на лёгких процессах? Грубо говоря, это большой однопоточный while (или хвостово-рекурсивный эквивалент):
Функции, которые пишет программер, при компиляции будут порезаны на мелкие кусочки переходами на внешний уровень, так что поток управления неявно размазывается по функциям work_in_process(n). Очевидно, что пока work_in_process(n) не отработает, передать управление в work_in_process(n+1) мы не можем. Теперь предположим, что программер пишет
Внимание вопрос: как выдрать управление из функции parse и передать в work_in_process(n+1)? Если эта функция из фреймворка? Если эта функция из third-party библиотеки? Скала и Питон разводят руками. Distel – потенциально опасные функции помечаются специальным соглашением о наименовании. То же самое придётся делать с функциями, вызывающими эти, функциями второго, третьего и т.п. уровня. Такая операция замыкания на множестве функций вырежет добрую половину (если не больше) всех доступных библиотек и функций. Файберы не решают этой проблемы, потому что внедрить переход к другому файберу в функцию parse технически трудноосуществимо. Либо похожий (скорее фантастический) вариант – послайсить тяжёлые функции по результатам предварительного прогона – то есть внедрить в их код команды возврата к шедулеру. Однако, во-первых, технически я не представляю как это сделать. Во-вторых, нужно где-то хранить контекст, чтобы потом можно было продолжить выполнение. В-третьих, у этого подхода есть жёсткие ограничения по масштабируемости. В-четвёртых, этот подход плохо подстраивается под меняющиеся условия – если какой-то участок Остаётся одно – выдрать управление с помощью потоков ОС. Получается, от чего ушли к тому пришли. По мне так не очень весело, а больше способов я лично не вижу. Ситуация с Concurrent Haskell и E лучше, но там, насколько мне известно, тоже нельзя дать никаких гарантий даже в предположении идеальной операционки. Единственный конкурент – Oz (как утверждают его авторы). Однако строго говоря там другая модель параллельности ну и опять же – свой рантайм. Эрланг – это функциональный язык реализованный на основе редукций. В то время как скажем в питоновских микропотоках или скалистых акторах квант времени определяется на основе количества выполненых инструкций байт-кода, в Эрланге квант определяется на основе количества редукций. Разница принципиальная: выполнение одной инструкции байткода может длиться от времени выполнения нескольких машинных инструкций до времени перехода Солнца из стадии жёлтого карлика в стадию красного гиганта. В то же время одна редукция выполняется _всегда_ быстро (верхняя граница существует и весьма мала; кстати поэтому в гвардах можно делать только жёстко ограниченный набор операций). Это означает что эрланговский процесс (в противовес вышеперечисленным) не может оккупировать процессор на долгое время. Вдобавок, шедулер имеет и обеспечивает необходимую точность: _практически гарантируется_, что процесс получит управление во временном окне X (где X зависит от многих факторов, но для целевых приложений его хватает с запасом). Любой математик/программист может вывести все необходимые вероятностные оценки на время отклика и испытать их практически. Естественно, нужно учитывать вносимые флуктуации железом и операционкой. Если с практической точки зрения, нас волнует доступность сервиса, то следует учесть, что доступность и ограничения на время сильно коррелируют. Возьмите правильное железо, и правильную операционку, и при должном подходе к делу вы тоже получите девять девяток доступности, как в случае мегасвитча AXD-301. 3. “Selective receive” это три маленьких пункта: 1. Если очередь пуста, процесс блокируется. 2. Все сообщения в мэйлбоксе “паттерн-матчатся”, соответствующее сообщение удаляется из мэйлбокса и запускается обработка сообщения, которая может длиться сколь угодно долго. 3. Все сообщения в мэйлбоксе сортируются по категориям так, что наиболее приоритетные сообщения берутся первыми. “Selective receive” имеет преимущества по сравнению с FIFO: Однако требуются значительные усилия, чтобы реализовать его эффективно. А именно, (1) как только в мэйлбокс некоторого приоритетного процесса приходит сообщения, он (процесс) должен мгновенно получить управление (прямой доступ к шедулеру), (2) чтобы разбить сообщения на категории, нужно в худшем случае сканировать весь мэйлбокс, следовательно сканирование может занять большое время, (3) в силу специфики приложений receive запросто может стать узким местом, (4) реализация receive требует некоторой возни с массивами, в частности in-place resize, а для этого нужно взаимодействие с gc. Считаю, что этих четырёх пунктов должно быть достаточно для того, чтобы реализовать receive на уровне виртуальной машины, а не на уровне байткода. (Подробнее про семантику selective receive читаем мегасообщение от Richard’а O’Keefe) 4. GC в Эрланге – это произведение искусства. Ну ладно, просто классный: То есть мало того, что он быстрый (один проход по списку – вот и вся сборка мусора), так ещё имеет предсказуемое время работы. По этой теме можно также взглянуть сюда (ссыла от Cyberax Это ещё не всё. Чтобы увеличить независимость процессов, каждый процесс обслуживается сборщиком отдельно, то есть имеет собственную кучу. Преимущество – можно просто выбросить все данные для процесса, когда этот процесс мрёт. Расшаривание одной большой кучи может привести к более частым сборкам мусора, что нежелательно. GC должен одинаково хорошо работать как в случае частых перезапусков процессов, так и в случае множества долгоживущих многососущих и многовыплёвывающих процессов. В то же время, можно сделать так, что если какому-то критическому процессу не будет хватать памяти, то ему будет выделена память за счёт бездействующих процессов. Наконец, в последнее время появилась “гибридная” модель с расшаренной кучей, где локальная посылка сообщений проходит вообще без какого-либо копирования (см. erl -hybrid) и с сохранением SRT. Это вообще принципиально э... очень проблематично без взаимодействия с gc. 5. Я конечно ляпнул про “интеллектуальность” шедулера. Обратите внимание на первый и третий пункты. Чтобы обеспечить эти пункты, нужно иметь возможность шедулеру в любой момент получить управление (вот он SRT). И для совсем тяжёлых случаев у нас есть То есть здесь конечно рулит не сам шедулер как таковой, а то что он тесно склеен с рантаймом и поэтому обеспечивает такие возможности. Ну я надеюсь, я достаточно подробно пояснил, почему я считаю, что Эрланг невозможен под jvm/.net? Хочу правильно поставить акцент: я не отрицаю возможность lightweight библиотеки, я всего лишь навсего очень-очень сильно сомневаюсь, что она может составить конкуренцию Эрлангу на _его_ поле боя и на смежных площадях:
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#) |