CSP

CSP

Communicating Sequential Processes,簡稱 CSP,和 Content Security Policy 不一樣,是用來處理非同步執行序之間溝通的一個數學模型,我最早是在 Addy Osmani 的JavaScript Application Architecture On The Road To 2015這篇文章裡面看到的,花了蠻多時間試著去瞭解,最近終於覺得懂一點皮毛可以紀錄一下了。

CSP 其實不是新東西,是C. A. R. Hoare在 1978 年就發表的論文(PDF),1985 還出了整本書來介紹,而且全文 PDF都有在網路上,可是這本書實在太理論了,看了一點點就看不下去,只好找其它資源,發現還真的蠻少的,但是確有找到一些近幾年的實做,像是 Go 的 routine 間用 channel 溝通,或是 Clojure 的 core.async,當然 Addy Osmani 那篇也有提到 JavaScript 的部分。

根據我目前淺薄的理解,CSP 就是用 channel 的非同步溝通機制,channel 怎麼用呢,顧名思義,就是一個傳遞訊息用的頻道,不過我覺得用管線可以更精確的描述它,而且這是一個單向的管線,一邊只能傳訊息進去,一邊只能拿訊息出來,可以達成非同步的溝通最主要在於拿訊息這邊,當你在其中一個 process 中說你要跟某個 channel 拿一個訊息出來時,如果那個 channel 裡面沒有東西,則這邊的 process 就會停下來等到那個 channel 有訊息出現,這個等待的機制不同語言有各自的方法實做。

先來看看 Go 的範例吧,因為實在是比 JavaScript 的直覺多了:

package main
import "fmt"

func main() {
    messages := make(chan string, 1)

    messages <- "ping"

    msg := <-messages
    fmt.Println(msg)
}

這段程式碼是基於 Go by Example 說明 channel 的範例,程式碼很好理解,messages := make(chan string, 1)這行用 make 產生一個 channel 指派給 messages 這個變數,messages <- "ping"表示把 "ping" 這個字串丟進去 message 這個 channel 裡面,然後msg := <-messages表示從 message channel 裡面抓訊息出來,丟到 msg 這個變數,:=是指派同時宣告變數的運算子,<-則是用來描述操作中訊息傳遞方向用的運算子,當它是箭頭就很好理解,在 Go 裡面稱為receive operator

在第一個例子當中,因為是先送資料進去 channel 才拿出來,所以還不太有感覺,接下來看第二個例子,一樣是 Go by Example 的,這段是Channel Synchronization的範例:

package main

import "fmt"
import "time"

func worker(done chan bool) {
    fmt.Print("working...")
    time.Sleep(time.Second)
    fmt.Println("done")

    done <- true
}

func main() {

    done := make(chan bool, 1)
    go worker(done)

    <-done
}

這個範例稍微複雜一點,done := make(chan bool, 1)先產生一個 done channel,然後用go worker(done)產生一個 concurrent routine,跑的是 worker 這個 function,內容在 main 的上面,基本上就是 sleep 一下然後傳訊息回 done channel,然後 main 最後的<-done就是從 done channel 拿訊息出來,先不管平行出去的 routine,通常的程式跑到這行結束,整個程式就結束關閉了,不過,就是這個不過,正常情況下,有<-channel的話,該 routine 程式執行到這邊就會暫停下來,直到有從 channel 裡面拿到訊息才會繼續跑下去(或是裡面已經有訊息,直接拿到就繼續往下)。

Go 的 channel 還有一些細節可以參考Golang channels tutorial這篇文章,其實就是一個可以跨 routine 的傳遞資料的管道,資料可以一直傳,沒有限制數量,不過還有一些相關的細節,像是 sync channel,還有 channel 的 buffer 等等。

綜合以上的兩個範例,可以歸納出來,要支援 CSP 有兩個必要條件,第一個是可以做得出 channel 物件的機制,可以放資料進去,可以拿資料出來,是先進先出機制,這部分其實不是問題,問題是第二個條件,程式碼要能跑一跑停下來等訊息然後又繼續跑下去,這可不是用while (1)可以處理的狀況,用 recursive function call 效能也不太好,以前的 JavaScript 是無法良好的達成第二個條件的,直到 ES6 的 async function 出現。

ES6 async function 之前有文章介紹過,這邊就不再說明,不過總之就是執行到yield後,這個 function call 就會先停下來,把值傳出,直到下次再次執行該 function 才會繼續往下執行,這樣停下來的機制,正好可以利用來作為 CSP 等訊息的機制,不過利用yield的話有一個限制,就是一定要在 async function 裡面才可以利用 channel,不像 Go 由於是建在語言裡面的,main thread 也可以跟 channel 溝通。

雖然說可以利用 async function 可以做出 CSP 的架構出來,不過要只用 async function 來寫出像 Go 那樣簡短的程式碼實在是很困難,中間還有很多機制需要補起來,所以就開始有 library 實做,目前最有名的是js-csp,Facebook 最近的 React.js Conf 其中一場議程介紹 CSP 時也是用 js-csp 做範例,錄影在這,作為入門 CSP 我覺得是蠻不錯的一場演講:

js-csp 裡面其實做了很多事情,目前看起來像是參考 Go 來設計,例如這樣的 Go程式碼

package main
import "fmt"
import "time"

type Ball struct{ hits int }

func player(name string, table chan *Ball) {
    for {
        ball := <-table
        ball.hits++
        fmt.Println(name, ball.hits)
        time.Sleep(100 * time.Millisecond)
        table <- ball
    }
}

func main() {
    table := make(chan *Ball)
    go player("ping", table)
    go player("pong", table)

    table <- new(Ball) // game on; toss the ball
    time.Sleep(1 * time.Second)
    <-table // game over; grab the ball
}

改成用 js-csp 寫的話就變成:

function* player(name, table) {
  while (true) {
    var ball = yield csp.take(table);
    if (ball === csp.CLOSED) {
      console.log(name + ": table's gone");
      return;
    }
    ball.hits += 1;
    console.log(name + " " + ball.hits);
    yield csp.timeout(100);
    yield csp.put(table, ball);
  }
}

csp.go(function* () {
  var table = csp.chan();

  csp.go(player, ["ping", table]);
  csp.go(player, ["pong", table]);

  yield csp.put(table, {hits: 0});
  yield csp.timeout(1000);
  table.close();
});

csp.chan產生 channel,用yield csp.take代替從 channel 取訊息,用yield csp.put代替送訊息到 channel,然後最重要的是用csp.go來代替從 Go 裡面用go產生 routine 的操作,然後不說可能沒人注意到,js-csp 把 routine(process)、ticker等比較底層的基礎建設都做起來了,也就是如此才能讓程式碼和 Go 的看起來這麼接近。

js-csp 基本上就是仿照 Go 的的語法來設計,只是常常需要 yield,語法還是不如 Go 來的簡潔,至於何種情境比較適合使用 CSP 呢,以 channel 的特性來說,目前看起來是常常會發生的 event 比較適合,像是常常被拿出來講的 mousemove 事件,另外就是有要分 thread 做平行運算的話也不錯,不過目前看起來是無法接上 WebWorker,主要是因為postMessage無法傳遞物件 instance 過去,而是會複製一份;另外因為 channel 可以關起來,所以要用來實做 Promise 也不是不行,不過就沒什麼必要如此搞就是。

講到做事件的處理,應該會有人注意到實做上的細節問題,就是要怎麼讓多個 process 去讀取同一個 channel 呢,一般而言,channel 的訊息是只能讀取一次的,就是說雖然你可以多個 process 等同一個 channel 的訊息,但是只會有一個 process 會真的拿到新的訊息,而實務上,一個事件綁了多個 handler 的情形非常常見,照 channel 的機制,應該是不能用下去的,不然就要自己管裡 handler,又多繞了一圈,事實上,CSP 模型是有一些運算可以用的,像要處理多個 handler 的問題,就可以用mult,可以把一個 channel 轉成一對多,其它還有多對一的 share resource、Clojure 的 onto等等,應該是想的到的情形都已經有數學模型或是不同語言的實做可以處理了,不過 js-csp 在這部分還在開發中,像是 mult 就還在 beta 階段,其實還不太能真的用,作者有說現在的介面可能會改,也因此還沒寫到文件裡面。

最後想要記錄一下 Clojure 所提出的 transducer,transducer 的目的是讓 reduce 的操作可以用 compose 來組合,什麼是 reduce 操作呢,其實包括像 map、filter 都可以算是,但是這些操作以前是無法用 function composition 來做組合的,直到有了 transducer,又加上 transducer 把處理資料的型別也 decouple 出去了,所以 channel message 也可以利用。有兩篇文章可以參考,第一篇文章是CSP and transducers in JavaScript,這篇講得非常清楚,他是從無到有把 transducer 建構起來,我是第二次認真看這篇文章才理解的,另外一篇文章是Transducers.js: A JavaScript Library for Transformation of Data,是 Transducer.js 的作者寫的,從不太一樣的角度來看 Transducer 這個設計,有機會再來分享詳細一點。

這篇文章其實也不算是介紹或教學 CSP on JavaScript,比較是記錄一些我花時間想辦法理解的問題,包括為什麼現在才有人用 JavaScript 實做 CSP,實際上怎麼實做,目前適用的地方,還有整理了對 transducer 的理解,如果單純是想理解 CSP,除了前面提到的文章之外,還有幾篇文章可以參考ES6 Generators Deliver Go Style ConcurrencyTaming the Asynchronous Beast with CSP Channels in JavaScript

comments powered by Disqus