Одной из самых сильных сторон языка программирования Go является встроенная поддержка concurrency, основанная на труде Тони Хоара «Communicating Sequential Processes». Go создан для удобной работы с многопоточным программированием и позволяет очень легко строить довольно сложные concurrent-программы. Но задумывались ли вы когда-нибудь, как выглядят различные паттерны concurrency визуально?
Конечно, задумывались. Все мы, так или иначе, мыслим визуальными образами. Если я попрошу вас о чём-то, что включает числа «от 1 до 100», вы мгновенно их «увидите» в своей голове в той или иной форме, вероятно даже не отдавая себе в этом отчёт. Я, к примеру, ряд от 1 до 100 вижу как линия с числами уходящая от меня, поворачивающая на 90 градусов вправо на числе 20 и продолжающая до 1000+. И, покопавшись в памяти, я вспоминаю, что в самом первом детском саду в раздевалке вдоль стены были написаны номерки, и число 20 было как-раз в углу. У вас же, вероятно, какое-то свое представление. Или вот, другой частый пример — представьте круглый год и 4 сезона года — кто-то их видит как квадрат, каждая грань которого принадлежит сезону, кто-то — как круг, кто-то ещё как-то.
Так или иначе, позвольте мне показать мою попытку визуализировать основные паттерны concurrency с помощью Go и WebGL. Эти интерактивные визуализации более-менее отражают то, как я вижу это в своей голове. Интересно будет услышать, насколько это отличается от визуализаций читателей.
Итак, давайте начнем с простейшего примера — «Hello, concurrent world», чтобы познакомиться с концепцией моего подхода.
Привет, concurrent мир
package main func main() { // создаем новый канал типа int ch := make(chan int) // запускаем новую анонимную горутину go func() { // отправляем 42 в канал ch <- 42 }() // ждем, читаем из канала <-ch } 
Ссылка на интерактивное WebGL демо
Здесь синие линии представляют горутины, время «бежит» вниз по оси Y. Тонкие синие линии соединяющие ‘main’ и ‘go #19’ — это отметки начала и завершения жизни горутины, показывающие предков и детей. Красные стрелочки демонстрируют событие отправки сообщения в канал, и отправленное значение подписано. На самом деле, «отправка в канал» и «чтение из канала» это два отдельных события, и поведение будет сильно отличаться между буферизированными и небуферизированными каналами, но я два этих события анимирую как одно — «передача значения по каналу». Строка "#19" в названии анонимной горутины — это реальный ID запущенной горутины. Хотя официально узнать ID горутин и нельзя (чтобы люди не городили другие модели concurrency, в которых идентификаторы играют важную роль), но для вот таких хакерских случаев таки можно — об этом хорошо написано в статье Скота Мэнсфилда «Goroutine IDs».
Таймеры
Фактически, наш простейший Hello, world выше может использоваться для создания простейшего таймера. В стандартной библиотеке Go есть такие удобные функции, как time.After или time.Tick, но давайте реализуем наш собственный — напишем функцию, которая создает канал, запускает горутину, которая спит необходимое время и пишет в канал, и возвратим этот канал вызывающему.
package main import "time" func timer(d time.Duration) <-chan int { c := make(chan int) go func() { time.Sleep(d) c <- 1 }() return c } func main() { for i := 0; i < 24; i++ { c := timer(1 * time.Second) <-c } } 
Ссылка на интерактивное WebGL демо
Здорово, правда? Но идём дальше.
Пинг-понг
Этот интересный пример concurrency был взят из известного доклада гуглера Sameer Ajmani "Advanced Concurrency Patterns". Конечно, этот пример не слишком advanced, но для тех, кто только знакомится с concurrency в Go он должен быть интересным и демонстративным.
Итак, у нас есть канал table, выполняющий роль стола, есть мяч Ball, который является переменной типа int и хранит в себе количество ударов по нему, и есть горутины-игроки, которые «забирают мяч со стола» (читают из канала), «бьют по нему» (увеличивают переменную) и «бросают обратно на стол» (пишут в канал).
package main import "time" func main() { var Ball int table := make(chan int) go player(table) go player(table) table <- Ball time.Sleep(1 * time.Second) <-table } func player(table chan int) { for { ball := <-table ball++ time.Sleep(100 * time.Millisecond) table <- ball } } 
Ссылка на интерактивное WebGL демо
На этом моменте я хочу ещё раз обратить ваше внимание на ссылку с интерактивным WebGL демо, доступную под каждой анимацией — открыв в новом табе, вы можете двигать, вращать, увеличивать/уменьшать и рассматривать эти 3D анимации, как вам угодно, а так же замедлять/ускорять и перезапускать их.
Теперь, давайте запустим три игрока-горутины, вместо двух:
go player(table) go player(table) go player(table) 
Ссылка на интерактивное WebGL демо
В данном примере мы видим, что каждый игрок забирает мяч со стола по-очереди, и вы можете задаться вопросом — почему именно так, кто гарантирует этот порядок?
Ответ тут прост — рантайм Go содержит FIFO очередь для горутин, готовых читать из канала, поэтому мы и наблюдаем этот порядок. В нашем случае каждая горутина становится в очередь сразу же после отправки мяча на стол. Впрочем, это поведение может измениться в будущем и расчитывать на порядок не стоит. Но пока это так, и давайте запустим не три, а сто горутин.
for i := 0; i < 100; i++ { go player(table) } 
Ссылка на интерактивное WebGL демо
Порядок FIFO теперь более очевиден, не так-ли? Мы можем запросто запустить и миллион горутин (они дешевые, и это ок в больших Go программах иметь сотни тысяч горутин), но для наших целей это будет слишком много. Давайте перейдем к другим паттернам.
Fan-in
Один из самых известных паттернов это так называемый fan-in паттерн. Он является противоположностью паттерну fan-out, который мы рассмотрим далее. Если вкратце, то fan-in — это функция, читающая из нескольких источников и мультиплексирующая всё в один канал.
К примеру:
package main import ( "fmt" "time" ) func producer(ch chan int, d time.Duration) { var i int for { ch <- i i++ time.Sleep(d) } } func reader(out chan int) { for x := range out { fmt.Println(x) } } func main() { ch := make(chan int) out := make(chan int) go producer(ch, 100*time.Millisecond) go producer(ch, 250*time.Millisecond) go reader(out) for i := range ch { out <- i } } 
Ссылка на интерактивное WebGL демо
Как мы видим, первый producer генерирует числа каждые 100мс, второй — каждые 250мс, а reader получает числа от обоих продюсеров сразу же. Мультиплексирование, по-сути, происходит в функции main.
Fan-out
Противоположностью fan-in является fan-out или workers паттерн. Множество горутин читают из одного канала, забирая на обработку какие-то данные и эффективно распределяя работу между ядрами CPU. Отсюда и название "workers". В Go реализовывать этот паттерн очень просто — запустите пачку горутин, передав канал через параметр и пишите в этот канал ваши данные, а мультиплексирование и распределение будет происходит автоматически благодаря рантайму Go.
package main import ( "fmt" "sync" "time" ) func worker(tasksCh <-chan int, wg *sync.WaitGroup) { defer wg.Done() for { task, ok := <-tasksCh if !ok { return } d := time.Duration(task) * time.Millisecond time.Sleep(d) fmt.Println("processing task", task) } } func pool(wg *sync.WaitGroup, workers, tasks int) { tasksCh := make(chan int) for i := 0; i < workers; i++ { go worker(tasksCh, wg) } for i := 0; i < tasks; i++ { tasksCh <- i } close(tasksCh) } func main() { var wg sync.WaitGroup wg.Add(36) go pool(&wg, 36, 50) wg.Wait() } 
Ссылка на интерактивное WebGL демо
Одна вещь, на которую тут хотелось бы обратить внимание — параллелизм. Лего заметить, что горутины-воркеры бегут параллельно, забирая себе «работу» по каналам, одна за другой. По данной анимации можно также увидеть, что горутины делают это почти одновременно. К сожалению, пока что в анимации не видно, где горутина реально работает, а где блокируется, и также тут временной масштаб уже близок к порогу погрешности ошибки, но конкретно эта анимация была записана на программе, бегущей на 4 ядрах, тоесть с GOMAXPROCS=4. Чуть дальше мы рассмотрим этот вопрос подробнее.
А пока что, давайте попробуем что-то посложнее — воркеры, у которых есть свои, саб-воркеры.
package main import ( "fmt" "sync" "time" ) const ( WORKERS = 5 SUBWORKERS = 3 TASKS = 20 SUBTASKS = 10 ) func subworker(subtasks chan int) { for { task, ok := <-subtasks if !ok { return } time.Sleep(time.Duration(task) * time.Millisecond) fmt.Println(task) } } func worker(tasks <-chan int, wg *sync.WaitGroup) { defer wg.Done() for { task, ok := <-tasks if !ok { return } subtasks := make(chan int) for i := 0; i < SUBWORKERS; i++ { go subworker(subtasks) } for i := 0; i < SUBTASKS; i++ { task1 := task * i subtasks <- task1 } close(subtasks) } } func main() { var wg sync.WaitGroup wg.Add(WORKERS) tasks := make(chan int) for i := 0; i < WORKERS; i++ { go worker(tasks, &wg) } for i := 0; i < TASKS; i++ { tasks <- i } close(tasks) wg.Wait() } 
Ссылка на интерактивное WebGL демо
Здорово. Конечно, можно было сделать больше и воркеров, и саб-воркеров, но я стремился сделать анимацию максимально наглядной.
Есть гораздо более сложные паттерны, воркеров с сабворкерами со своими сабворкерами, и каналы, которые сами передаются по каналам, но идея fan-out должна быть понятна.
Серверы
Следующий популярный паттерн, похожий на fan-out, это серверы. Он отличается тем, что горутины стартуют динамически, выполняют необходимую работу и завершаются. И довольно часто этот паттерн применяется для реализации серверов — слушаем порт, принимаем соединение, стартуем горутину, которая дальше займется входящим запросом, передав ей соединение, а в это время слушаем дальше, ожидая следующее соединение. Это достаточно удобно и позволяет реализовать эффективный сервер, выдерживающий 10K соединений, очень просто. Вгляните на следующий пример:
package main import "net" func handler(c net.Conn) { c.Write([]byte("ok")) c.Close() } func main() { l, err := net.Listen("tcp", ":5000") if err != nil { panic(err) } for { c, err := l.Accept() if err != nil { continue } go handler(c) } } 
Ссылка на интерактивное WebGL демо
Этот пример не слишком интересен — по-сути, тут ничего особо не происходит. Хотя, конечно, под капотом там заботливо спрятана громадная сложность и алгоритмы. «Простота сложна».
Но давайте добавим немного активности в наш сервер, и, скажем, добавим логгер, в который каждая горутина будет писать адрес клиента.
package main import ( "fmt" "net" "time" ) func handler(c net.Conn, ch chan string) { ch <- c.RemoteAddr().String() c.Write([]byte("ok")) c.Close() } func logger(ch chan string) { for { fmt.Println(<-ch) } } func server(l net.Listener, ch chan string) { for { c, err := l.Accept() if err != nil { continue } go handler(c, ch) } } func main() { l, err := net.Listen("tcp", ":5000") if err != nil { panic(err) } ch := make(chan string) go logger(ch) go server(l, ch) time.Sleep(10 * time.Second) } 
Ссылка на интерактивное WebGL демо
Достаточно демонстративно, не так ли? На этой анимации видно, что наш логгер может быстро стать узким местом, если количество соединений будет расти, а логгер будет не слишком быстрым (скажем, он будет сереализовать данные и куда-то еще отправлять). Но мы можем решить это, использовав уже знакомый нам паттерн fan-out. Давайте напишем это.
Сервер+Воркер
Пример сервера с воркером будет чуть более продвинутым вариантом только что озвученного решения. Он не только стартует логгер в нескольких горутинах, но и собирает с них данные с результатами (скажем, результат записи на удаленный сервис).
Посмотрим на код и анимацию:
package main import ( "net" "time" ) func handler(c net.Conn, ch chan string) { addr := c.RemoteAddr().String() ch <- addr time.Sleep(100 * time.Millisecond) c.Write([]byte("ok")) c.Close() } func logger(wch chan int, results chan int) { for { data := <-wch data++ results <- data } } func parse(results chan int) { for { <-results } } func pool(ch chan string, n int) { wch := make(chan int) results := make(chan int) for i := 0; i < n; i++ { go logger(wch, results) } go parse(results) for { addr := <-ch l := len(addr) wch <- l } } func server(l net.Listener, ch chan string) { for { c, err := l.Accept() if err != nil { continue } go handler(c, ch) } } func main() { l, err := net.Listen("tcp", ":5000") if err != nil { panic(err) } ch := make(chan string) go pool(ch, 4) go server(l, ch) time.Sleep(10 * time.Second) } 
Ссылка на интерактивное WebGL демо
Мы улучшили наш сервер, эффективно распределив задачу для логгера между 4-мя горутинами, но всё равно видим, что логгер таки может стать узким местом. Тысячи соединений сходятся в одном канале. перед тем как мультиплексироваться между горутинами. Но, конечно, это случится уже при гораздо больших нагрузках, чем в предыдущем варианте.
Решето Эратосфена
Но довольно fan-in/fan-out экспериментов. Давайте посмотрим на более интересные пример. Один из моих любимых — это «Решето Эратосфена» на горутинах и каналах, найденное в докладе "Go Concurrency Patterns". Решето Эратосфена это древний алгоритм нахождения простых чисел до заданного лимита. Его суть заключается в последовательном вычеркивании всех чисел, делящихся на каждое последующее найденное простое число. Алгоритм «в лоб» не слишком эффективен, особенно на мультиядерных машинах.
Вариант реализации этого алгоритма с горутинами и каналами запускает по одной горутине на каждое найденное простое число, и эта горутина фильтрует числа, которые на него делятся. Когда же найдено первое простое число в горутине — оно отправляется в главную горутину(main) и выводится на экран. Этот алгоритм тоже далеко не самый эффективный, но я нахожу его потрясающе элегантным. Вот сам код:
// A concurrent prime sieve package main import "fmt" // Send the sequence 2, 3, 4, ... to channel 'ch'. func Generate(ch chan<- int) { for i := 2; ; i++ { ch <- i // Send 'i' to channel 'ch'. } } // Copy the values from channel 'in' to channel 'out', // removing those divisible by 'prime'. func Filter(in <-chan int, out chan<- int, prime int) { for { i := <-in // Receive value from 'in'. if i%prime != 0 { out <- i // Send 'i' to 'out'. } } } // The prime sieve: Daisy-chain Filter processes. func main() { ch := make(chan int) // Create a new channel. go Generate(ch) // Launch Generate goroutine. for i := 0; i < 10; i++ { prime := <-ch fmt.Println(prime) ch1 := make(chan int) go Filter(ch, ch1, prime) ch = ch1 } } А теперь взгляните на анимацию.
Ссылка на интерактивное WebGL демо
Не забудьте покрутить его интерактивно в 3D пространстве по ссылке выше. Мне очень нравится, как иллюстративен этот пример и изучение его в 3D может помочь понять сам алгоритм лучше. Мы видим, что первая горутина(generate) посылает первое простое число (2) в main, затем стартует первая горутина-фильтр, отсеивающая двойки, затем тройки, пятерки, семерки… и каждый раз новое найденное простое число отправляется в main — это особенно хорошо видно при виде сверху. Красивый алгоритм, в том числе и в 3D.
GOMAXPROCS
Теперь давайте вернёмся к нашему примеру с воркерами. Помните, я написал, что этот пример был запущен с GOMAXPROCS=4? Это потому что все эти анимации не нарисованы, это реальные трейсы реальных программ.
Для начала, давайте освежим память и вспомним, что такое GOMAXPROCS:
GOMAXPROCS устанавливает максимальное количество ядер CPU, которые могут исполнять код одновременно
Я изменил код воркеров слегка, чтобы они делали реальную работу. нагружая процессор, а не просто спали. Затем запустил код без каких либо изменений на Linux-машине с двумя процессорами по 12 ядер каждый — сначала с GOMAXPROCS=1, затем с GOMAXPROCS=24.
Итак. первая анимация показывает одну и ту же программу, бегущую на 1-м ядре, вторая — на 24-х ядрах.
WebGL анимация 1 WebGL анимация 24
Скорость анимации времени разная в этих примерах (я хотел, чтобы все анимации занимали фиксированное время по высоте), но разница должна быть очевидна. При GOMAXPROCS=1 следующий воркер забирает работу (читает из канала) только когда освободилось ядро процессора и предыдущая горутина отработала свою порцию. С 24-мя ядрами, горутины почти сразу же разбирают задачи и ускорение огромно.
Впрочем, важно понимать, что увеличение GOMAXPROCS не всегда приводит к увеличению производительности, и могут быть случаи, когда она даже падает от увеличения количества ядер.
Утечки горутин
Что ещё мы можем продемонстрировать из мира concurrency? Одна из вещей, которая мне приходит в голову, это утечки горутин. Они могут случаться по неосторожности, или, скажем, если вы запустили горутину, но она вышла из области видимости.
Первый (и единственный) раз, когда я столкнулся с утечкой горутин, в моей голове возникла ужасающая картинка, и буквально на следующих выходных я написал expvarmon для быстрого мониторинга. И сейчас я могу визуализировать эту ужасающую картинку с помощью WebGL.
Посмотрите:
Ссылка на интерактивное WebGL демо
Мне больно даже смотреть на это 🙂 Каждая линия — это потраченные ресурсы компьютера и бомба с часовым механизмом для вашей программы.
Concurrency is not Parallelism
Слово concurrency часто переводят как «параллелизм», но это не совсем верно. По правде, хорошего перевода я не знаю, поэтому везде тут и пишу без перевода. Но сама тема, объясняющая отличия между concurrency и параллелизмом раскрыта многократно, в том числе и Робом Пайком в замечательном одноимённом докладе. Посмотрите, если ещё не.
Если вкратце, то:
Параллелизм — это просто много штук, запущенных параллельно.
Concurrency — это способ структурировать программу.
Важно понимать, что эти концепции несколько ортогональны — concurrent-программа может быть параллельной, а может и не быть. Мы чуть выше видели пример этого с разными GOMAXPROCS — один и тот же код бежал как на 1-м ядре (последовательно), так и на 24-х ядрах (параллельно).
Я мог бы повторять многие постулаты из вышеприведенных ссылок и докладов, но это уже сделано до меня. Лучше попробую показать это визуально.
Итак, вот это параллелизм. Просто много штук, бегущих параллельно.
Ссылка на интерактивное WebGL демо
И вот это параллелизм. Ещё больше параллельных штук, что, впрочем, ничего не меняет.
Ссылка на интерактивное WebGL демо
Но вот это — concurrency:
И вот это:
И вот это тоже concurrency:
Как это было сделано?
Чтобы создать эти анимации, я написал две программы — gotracer и gothree.js. Первая делает следующие вещи:
- парсит AST-дерево исходного кода примеров на Go (ещё один плюс простой грамматики Go) и вставляет специальный вывод на событиях, относящихся к concurrency — старт/стоп горутины, запись/чтения в канал, создание канала
- запускает модифицированную программу
- анализирует вывод, и генерирует специальный JSON с ивентами и таймштампами
Пример результирующего JSON-а:
Далее, gothree.js использует мощь шикарной библиотеки Three.js, чтобы рисовать и анимировать эти данные в 3D с помощью WebGL. Небольшой враппер, чтобы втиснуть это в одну демо-страничку и готово.
Впрочем, этот подход очень ограничен. Мне приходилось очень аккуратно подбирать примеры, переименовывать каналы, чтобы получать корректный трейс. С этим подходом нет легкого способа связать каналы между горутинами, если они называются внутри функции иначе. Также есть проблемы с таймингом — вывод в консоль занимает порой больше времени, чем запуск горутины, запись в канал и выход, поэтому в некоторых примерах мне приходилось чуть подтюнивать, вставляя time.Sleep (в примере с таймерами анимация чуть некорректна поэтому).
Вобщем-то. это основная причина, по которой я пока-что не открываю код. Сейчас я играюсь ещё с execution tracer-ом Дмитрия Вьюкова — он, похоже, даёт нужный уровень детализации, хотя не содержит информации о том, что именно было отправлено в канал. Возможно есть ещё какие-то способы достичь максимально детального трейса, буду исследовать дальше. Пишите мне в твиттер или тут в комментариях, если есть идеи. Было бы круто, чтобы этот инструмент в итоге перерос в 3D concurrency-дебаггер, применимый к абсолютно любой программе на Go, без исключений.
Эта статья изначально была в виде доклада на Go Meetup-е во Львове (23 января 2016), затем опубликована на английском языке в моём блоге. Также на HackerNews и на Reddit.
ссылка на оригинал статьи https://habrahabr.ru/post/276255/
Добавить комментарий