Визуализация concurrency в Go с WebGL
Одной из самых сильных сторон языка программирования 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.
