Визуализация 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.