2015年8月26日 星期三

找出 node.js 中 block main loop 的程式

環境

問題描述

node.js 的 single thread event loop 架構容易處理 I/O bound, 也避開 multi-thread 的各式問題, 但弱點是 main loop 被卡住了, 整個程式就不會動了。幸好找出錯誤原因的方法滿多的, 若確定是 CPU bound 而不是自己呼叫到 sync API, 也有很多成熟的解法

在開發環境偵錯

node.js 有很多種 profiling 的方法, 試過幾種作法, 我偏好這兩個作法:

兩者都會產生一個 web server 讓你可以連到指定的 port 用網頁作的 UI 看資料。也都不用傳資料到別人機器上。配合 stress test 可以找出潛在的 CPU bound。look 的介面比較簡單, 啟動速度較快。

在上線環境除錯

但若 CPU bound 只有在上線後才會遇到, 就不容易找了。試了一些方法, 覺得用內建的 command line debugger 最管用。

node.js 已內建 debugger, 不需特殊設定就可以用 debugger attach 上線執行的程式。執行方法如下:

$ kill -USR1 PID  # PID 為 node.js pid
$ node debug -p PID

然後執行 pause 暫停程式,接著執行 bt (backtrace) 才會有效。這樣就有線索找出 main loop 卡住的時候在作什麼了。

下面是一個完整的小例子:

$ cat b.js
function fib(n) {
  if (n <= 1) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}

setTimeout(function() {
  console.log(fib(100));
}, 10000);
$ node b.js
Hit SIGUSR1 - starting debugger agent.
debugger listening on port 5858

在另一個 shell 用 debugger:

$ ps auxw | grep node
fcamel          44656   3.2  0.2  3075620  18524 s013  S+    9:23PM
$ kill -USR1 44656
$ node debug -p 44656
connecting... ok
debug> bt
Can't request backtrace now
debug> pause
break in b.js:6
  4   }
  5   return fib(n - 1) + fib(n - 2);
  6 }
  7
  8 setTimeout(function() {
debug> bt
#0 b.js:6:1
#1 b.js:5:10
#2 b.js:5:23
#3 b.js:5:23
#4 b.js:5:23
#5 b.js:5:10
#6 b.js:5:10
#7 b.js:5:23
#8 b.js:5:10
#9 b.js:5:10
debug> repl
Press Ctrl + C to leave debug repl
> n
6

不過 CPU 太忙的時候 kill -USR1 好像會失效 (node.js 沒有顯示收到 SIGUSR1 進入 debug mode), 然後 debugger attach 會失敗。或是 debugger attach 成功, 有時 pause 也會失敗, 像這樣卡住沒反應:

debug> pause
break in [unnamed]:1
  1

有閒再深入了解原因。

2015年8月17日 星期一

為什麼需要 async programming 以及相關技術的演進

幾種使用 async programming 的情境:

GUI: 像是Web、iOS、Android apps。在 event-driven 的架構下用 callback 滿直覺的, 但是為了避免卡住 UI thread 而需要連續多個 non-blocking I/O 才能完成一件事時,寫起來就不直覺了。這時新增 thread 用 blocking I/O 寫起來比較直覺,但是不容易處理 thread-safety。

server: 像是 Web server、API server、reverse proxy。要能同時承受上千筆連線,必須用 non-blocking I/O。遇到 CPU 吃重的工作時,可以轉交給其它專門的 server (如向資料庫讀資料或用 Lucene 處理 text search)。

其它像是一些會用到多筆 http request 取資料的小程式,例如用 Gmail API 取出所有信件的附件,或是 stress test 的工具,或是 Web crawler,這些也會用 non-blocking I/O 加速程式 (或用 multi-thread/multi-process + blocking I/O 也行,最近才寫了個小工具 prunner.py)。

共通需求

  • 用 non-blocking I/O 避免卡住服務或縮短完成時間。
  • 用 single thread 降低實作複雜度。

為了滿足上述需求,主流的解法是用 single-thread event loop。但遇到 CPU bound 時還是得開新 thread。

注意這個共通需求對 Web page 和 server 是必要需求,但對其它情境只是「優先希望的作法」,Android、iOS 或 crawler 還是可以選擇新增 thread/process 使用 blocking I/O,然後自行承擔 multi-thread/multi-process 衍生的問題。

non-blocking I/O 的問題

single-thread event loop 只有幫忙監聽所有 non-blocking I/O 的動靜,用 callback 的方式通知結果。用 callback 處理 GUI 反應很自然,但是需要依序發數個 http request 的時候,在 callback 裡跳來跳去就頭大了,很難看出程式的流程。

換句話說,我們需要以下功能:

  • 用 synchronous API 來使用 non-blocking I/O。方便看出控制流程。
  • 執行中可以得到 call stack,方便除錯。

提供底層使用 non-blocking I/O 的 synchronous API

如何在不增加新的語法下提供這樣的功能?換句話說,我們還是想新增 thread 用「看起來像 blocking I/O 但底層是 non-blocking I/O」的 API。Python 的 gevent 提供一個不錯的解法:

  • 以 event loop 為底,實作 coroutine (由 greenlet 完成)
  • 提供 synchronous API + non-blocking I/O 實作 (用 yield 主動讓出執行權)
  • task scheduler 會在 I/O 完成後再回到當初 yield 處,讓使用 API 的人用起來像 blocking I/O 一般
剩下的唯一的問題是:所有程式都要用 gevent 提供的 I/O API。實務上這很難作到,所以 gevent 另外提供 monkey patch 處理沒有用 gevent API 的 third-party library。去除 monkey patch 的不穩因素 (比方說 lxml.etree.parse(URL) 會用 native code 從網路讀資料而 block main thread),效果意外地不錯。除了 Python 以外,Go 也有 goroutine,不過我沒研究也沒相關使用經驗。

值得一提的是,coroutine 是 non-preemptive multitasking,比使用 native thread 的 multi-thread (preemptive multitasking) 容易避免 race condition,不過代價是要小心不要寫出 busy loop 卡住整個 process。

新語法:async/await

相對於 Python 陣營有龐大使用 blocking I/O third-party library 的問題,JavaScript 陣營 (Node.js / Browser) 天生就使用 non-blocking I/O (長年以來只有一個 thread 的自然結果),這點很有優勢。

JavaScript 不用 coroutine 而是發展出兩種方式提供 synchronous API:

  • Promise: 看起來像 synchronous API,只是囉嗦了點,還有可能會搞混執行順序。
  • async/await: 基於 Promise 定義新的語法,簡化使用並突顯使用 async 的程式。

詳情見The long road to Async/Await in JavaScript。另外 What Is Asynchronous Programming?Managing Asynchronous Code - Callbacks, Promises & Async/Await 也值得一看。

另外,Python 也會在 3.5 加入新語法 async/await,用它們明確地定義 coroutine,藉此區分 generator。async/await 去掉 thread 的概念,應該會比 coroutine 適合。但對習慣 multi-thread 的人來說,可能 coroutine 比較親切吧?

整體來說,未來繼續用 Node.js 或 Python 寫 server 程式還是不錯的選擇,語法簡單、用戶眾多又有廣大的 third-party library 可用 (目前各用 geventNode.js 寫過一次上線的服務)。

雜談

話說大家都用 synchronous API 提供 non-blocking I/O 後,還能稱這為 async programming 嗎?不過語法裡有 async/await啦。具體來說,async programming 的定義到底是什麼......

2015年8月14日 星期五

prunner.py: 連猴子都會用的加速框架

問題

寫 python script 時有時會遇到 I/O bound (例如需發出大量 HTTP request) 或 CPU bound, 這時可用 multiprocessing 加速。但是自己寫 multi-process 有點麻煩:

  • 要留意 API 使用細節
  • 容易發生 race condition 或 dead lock。
  • 程式較複雜時會切成多個階段作業, 有時會閒置部份 processes 而浪費了加速的機會。
  • 辛苦寫好的平行架構不易重覆使用 (我至少重寫三次以上...泣)。

解法

prunner.py 是我寫好的框架, 中心思想是透過 task queue 提供容易重覆使用的架構, 還有協助減少閒置的 process。

以計算 sum( (i+1) * 2 ) 為例, 下面的程式會用很蠢的方式透過 10 個 processes 平行計算出結果:

import prunner

def begin():
    prunner.get_dict()['sum'] = 0
    prunner.post_task(init, range(2000))

def init(numbers):
    for i in numbers:
        prunner.post_task(add_one, i)

def add_one(n):
    prunner.post_task(double, n + 1)

def double(n):
    prunner.post_task(sum_up, n)
    prunner.post_task(sum_up, n)

def sum_up(n):
    with prunner.global_lock():
        prunner.get_dict()['sum'] += n

def end():
    print prunner.get_dict()['sum']

prunner.init(10, False, begin, end)
prunner.start()

每個 function call 會在一個 process 上執行, 藉此增加使用到的 CPU。也可以盡情地用 blocking I/O, 反正有很多 processes 會平行執行程式。

若不習慣 message loop 的寫法, 也可以用較 low level 的 API, 直接繼承 ParallelTaskRunner 然後覆寫 begin(), run(), end():

import prunner

TASK_INIT = 'task_init'
TASK_ADD_ONE = 'task_add_one'
TASK_DOUBLE = 'task_double'
TASK_SUM = 'task_sum'

class MyRunner(prunner.ParallelTaskRunner):
    def begin(self, options):
        self.dict_['sum'] = 0
        self.queue.put(prunner.Task(TASK_INIT, range(2000)))

    def run(self, task):
        if task.label == TASK_INIT:
            for i in task.data:
                self.queue.put(prunner.Task(TASK_ADD_ONE, i))
            return

        if task.label == TASK_ADD_ONE:
            self.queue.put(prunner.Task(TASK_DOUBLE, task.data + 1))
            return

        if task.label == TASK_DOUBLE:
            self.queue.put(prunner.Task(TASK_SUM, task.data))
            self.queue.put(prunner.Task(TASK_SUM, task.data))
            return

        if task.label == TASK_SUM:
            with prunner.ScopeLock(self.lock):
                self.dict_['sum'] += task.data

    def end(self):
        print self.dict_['sum']


runner = MyRunner(10, False, None)
runner.start()

和前面一樣, 同時有多個 processes 執行 run(), 每次呼叫帶有不同的資料。

雜談

1. 因為底層是 multiprocessing, prunner.py 可以處理 CPU bound 和 I/O bound, 直接用 blocking I/O 也沒問題, 方便配合 third-party library。

不過 I/O 需求量極高時, 還是用 gevent 較適當, 但是要找合 gevent 的 third-party library 或用 gevent monkey patch

2. 這個架構中比較需要巧思的部份是判斷程式的中止條件並且提供有效率的實作。中止條件是「所有 process 閒置且 queue 是空的」。

各個 process 有一個獨立的 flag 表示閒置與否, 這樣比用一個共用的計數器有效率。在我的電腦上執行 prunner_example.py 的時候, 獨立 flag 和計數器的時間分別是 2.5s 和 3.6s。

3. 雖然可以用 post_task() 執行 instance method, 不過會隱含 serialize/deserialize instance 以及傳到其它 process 的成本。這是用框架的缺點, 用起來方便, 但不小心會造成不必要的 overhead。我寫了兩個例子比較: prunner_example3.py 用 instance method, pyrunner_example2.py 用 function。執行時間分別是 2.8s 和 2.6s。

4. 試過各種架構後, 覺得 task queue (或稱 message queue) 還是最直覺的運作方式。有想過 producer-consumer 或 MapReduce 的架構, 不過還是 task queue 最易使用。這種單機層級的運算, 用 task queue 應該綽綽有餘。若要跨機器執行, 太過彈性可能會增加實作的複雜度。那時應該用別人作好的成熟工具。

2015年8月10日 星期一

用 grequests 作 stress test

作了一個 C10K 的 server 後, 還要作 stress test 才能驗證 server 真的挺得住 C10K 的連線。試了幾套工具, 最後覺得 grequests 最好用 (用 gevent monkey patch 的 requests), 用法就這麼簡單:

import grequests

def exception_handler(request, exception):
    print "Request failed: %s" % exception

url = 'SERVER_URL'
rs = [grequests.post(url, data={...})
      for i in range(10000)]
rss = grequests.map(rs, size=1000, exception_handler=exception_handler)

這樣就寫好一個會同時產生 1k 個連線, 總共產生 10k 個連線的 client。因為是直接寫程式, 可以自訂各式各樣的內容, 測得出真正的效果, 不會被簡單的 cache 消掉絕大多數的 requeests。若要改用 get 就用 grequests.get(url) 產生 request, 詳細用法見 requests

幾個測試情境和作法:

  • Connection bound: 提升 size 數, 或多跑幾個 client
  • CPU bound: 同上, 故意使用耗 CPU 的 API
  • Memory bound: 依 API 的性質, 產生 1MB 或更大的資料, 由 data=... 傳過去

grequests.map() 不設 size 的話, 會盡可能產生最多連線, client 有可能自己先爆掉。依自己的網路環境和 server 狀況, 可試看看不同的值。

執行前記得先用 ulimit -n 提升 open file number, 不過要用 root 才能提升, 作法如下:

$ sudo bash
$ ulimit -n 50000
$ su YOUR_ID

這樣可以用一般帳號測試, 但保有 max open file number = 50k。

以下是我試過但不管用的方法, 憑印象寫下放棄使用的原因 (不見得是工具不好):

  • ab: 很久以前用過覺得不夠順手, 查到文章推薦用 httperf, 這回我就跳過 ab 了。
  • httperf: 雖然有 --wsesslog 可以讀文字檔產生不同內容, 還是不夠彈性。另外有遇到 open too many files 的問題, 似乎要編程式才能提升 limit, 就懶得再試了
  • loadtest: 看起來不錯, 可用 -R 指定 script自訂程式, 由 loadtest 幫忙處理其它事, 不過沒有試成功, 就試別套了
  • nodeload: 還不錯用, 可以自訂程式, 執行後還會自動產生報表, 附一個 local http server 跑在 port 8000 可以即時看報表變化。不過量大了以後會炸, 有些 bug, 作者又說沒在維護了, 就放棄它了。
  • Btw, 用這些工具的時候, 都要自己設好 http header 才可以使用 POST, 不如 requests 直覺。

2015年8月8日 星期六

http 1.1 pipeline 失敗的原因

網路連線的基本指標是 latency 和 throughput。用 pipeline 同時提升 latency 和 throughput 還滿直覺的, 但在 http 1.1 上卻意外地以失敗收場, 所以花了點時間查一下為什麼。

What are the disadvantage(s) of using HTTP pipelining? 提到幾個問題:

  • http 1.x 是 stateless 的 protocol, client 沒有能力知道 request 之間的 order (沒有流水號)。
  • 因此, server 必須依 request order 回傳 response, 但是有些 server 實作錯了。
  • 即使 server 作對了, 因為要照 order 回傳 response, server 可能需要暫存大量回應, 有被 DoS 的風險。
  • 因為 response 要依順序回傳, client 有 head-of-line blocking 的風險, 比方說剛好先要一個大圖檔再要一個 JS 檔, 結果 JS 檔因此比較慢收到, 讓網頁比較慢取得較重要的檔案。
  • client 端的實作比想像中複雜, client 要先偵測 server 是否支援 pipeline 接著才能開始用 pipeline, 因此有些延遲。再者, 因為 client 不會真的只開一個連線, client 還需考慮如何分配 request 到不同連線作 pipeline。
  • 因為 http 1.x 過往的限制, 網站早就依 domain 拆開回資料, client 也會同時發多個連線加速。結果是即使 pipeline 都作對了, 可能也沒賺到什麼。
  • 此外, server 和 client 中間的 proxy 也可能不支援 (如擔心 DoS) 或是作錯, 又降低了可行的機率。

如果 http 裡面有含流水號, 由 http client library 自己匯合好再依順序回傳資料給上層程式 (像 TCP 那樣), 問題會少一些。設計協定時決定由 server 或 client 處理還挺關鍵的, 一但作錯決定, 協定普及後就很難改了。

HTTP/2SPDY 直接支援 multiplexing, 在一開始就作對了 pipeline。剩下的問題只有使用 TCP 造成 head-of-line blocking (block 的層級不同, 不像 HTTP/1.1 pipeline 那樣嚴重), 但這個得繞過 TCP 才能解決, 也因此 Chrome 又作了 QUICQUIC 看來挺有趣的, 不過不像 HTTP2 看來快要普及了 (從 Chrome 6 開始用 SPDY, 這也花了四年以上的時間...)。

Btw, What are the disadvantage(s) of using HTTP pipelining? 附了許多有趣的連結, 有興趣讀讀可以了解更多細節。

gold 和 GNU ld 行為差異造成的問題

原因

ToolChain/DSOLinking - Debian Wiki 介紹得很清楚, 主要的差異是處理 DT_NEEDED section 的行為不同。

對 program A 和 shared lib B 和 C 來說, 假設相依性如下:

  • A 用到 B 和 C
  • B 用到 C

照理說 link 的設定要如實反應出相依性。若 link 的設定如下:

  • A: link B
  • B: link C

linker 是 GNU ld (BFD-based linker) 的時候會成功, 但用 gold 的時候會失敗。原因是 linker 會在目標的 DT_NEEDED section 記錄用到的 shared lib, 然後 GNU ld 預設會將 DT_NEEDED section 的值一併「往上傳」。所以 A link B 的時候不只會在 DT_NEEDED section 加上 B 的記錄, 還會取得 B 的 DT_NEEDED section 內的值, 所以沒寫 link C 也會有 C 的記錄。

這造成一個問題: 日後 B 沒有用到 C 的時候, 會因為升級 B 而造成 A 的 link error, 錯誤原因是沒有 link C。

解法是用 GNU ld link 時也要下 --no-add-needed 避免自動取用 shared lib 內的 DT_NEEDED section 的內容。這樣開發的時候才會注意到漏加 shared lib。

這種情況容易發生嗎? 就我個人的經驗來說, 比我預期的容易。比方說寫 GTK+ 也會用到 glib, 但 GTK+ 自己也有用 glib, 所以 GTK+ 的 DT_NEEDED section 有含 glib, 然後自己就忘了加。若用 GNU ld link, 沒加 glib 也會成功。或是很多 lib 用到 pthread, 自己也用到或加入的 static lib 間接用到, 然後忘了 link pthread。

改用 gold 為預設 linker

gold link 的行為不但比較正確,速度比較快也比較省記憶體。可以的話, 改用 gold 作為系統預設 linker 比較省事。Mac OS X 已經用 gold 了, Ubuntu 12.04 要另裝 binutils-gold:

$ sudo apt-get install binutils-gold

然後檢查看看:

$ ls -l /usr/bin/ld
lrwxrwxrwx 1 root root 7 Apr  2 00:05 /usr/bin/ld -> ld.gold*

安裝前會是連到 GNU ld, 像這樣:

$ ls -l /usr/bin/ld
lrwxrwxrwx 1 root root 7 Apr  2 00:02 /usr/bin/ld -> ld.bfd*

若沒有成功, 可能要用 update-alternatives 切換預設 linker (Ubuntu 14.04 好像需要), 詳見這裡

其它

1. GNU ld 預設會加入所有指定要 link 的 shared lib 到 DT_NEEDED section, 即使沒有用到那些 lib 也一樣。若希望只加入用到的 lib, 要加上參數 --as-needed

2. 可以用 ldd 列出 executable 或 shared lib 相依的 lib, 像這樣:

$ ldd /bin/ls
        linux-vdso.so.1 =>  (0x00007fffe2351000)
        libselinux.so.1 => /lib/x86_64-linux-gnu/libselinux.so.1 (0x00007ff642698000)
        librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x00007ff642490000)
        libacl.so.1 => /lib/x86_64-linux-gnu/libacl.so.1 (0x00007ff642287000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007ff641ec8000)
        libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007ff641cc4000)
        /lib64/ld-linux-x86-64.so.2 (0x00007ff6428ce000)
        libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007ff641aa6000)

2015年8月7日 星期五

PHP + JavaScript 提供 L10N 的文字

我希望的用法如下:

  • PHP 和 JavaScript 共用同一套文字格式。
  • PHP 和 JavaScript 用同一套 API。
  • 各國語系用字串 key 取出翻譯的內容。優點是可以隨意更改預設語系的內容; 缺點是網頁原始檔有一點難閱讀,無法像 L10N 前那樣直接看到內文。
  • 選用的目標語言缺內容時,改用預設語言。
  • L10N 的文字存成 JSON, 方便用各種工具編輯。
  • 函式庫相依性愈小愈好。

多數人使用的 gettext 不合我的需求, 查了一下沒找到順手的工具, 最後自己寫了一個。只有一個檔案 l10n.php, 程式不到 100 行。我不太熟 PHP 和 JavaScript, 可能寫得不怎麼道地。

用法是在網頁內 <?php require('l10n.php') ?>, 之後 PHP 和 JavaScript 都可以用 _m(KEY) 取得對到目前語言的字。可用 ?lang=LANG 切換語言,不然會以 Accept-Language 內 weight 最大的為目標語言。預設語言為 en。

API 還有一些可以改進的地方,像是支援替換文字內的變數,不用自己取出來後再替換;或是在 JSON 格式內加些輔助翻譯的描述。不過比較細微就是了,有這打算時再來參考 Chrome extension API 的作法, 還滿直覺的。

2015年8月1日 星期六

近期閱讀有物報告的心得

整理一下最近閱讀的心得,只是雜亂的片段想法。也許有天能串出更深的想法。

一個預測未來的簡單方法

原文: 有物報告 | 一個預測未來的簡單方法

用正面的方式描述是: 任何沒考慮 smartphone 的產業都會被衝擊。反過來說則是: 基於「不是人人都有 smartphone」的假設而發展出來的產業, 勢必會因 smartphone 普及而被衝擊。我比較喜歡後者的說法,前者聽起來比較空泛,後者有比較強的因果關係 (或著說比較強的推測)。

現行的例子是叫計程車。以前沒有 smartphone 要透過中間的服務人員對上雙方的位置, 幫忙湊合人和車。現在大家都有 smartphone, 定位和上網都很容易。建立平台的成本大幅下降,也不用透過服務人員配對。

去中介化的犧牲者

原文:

能用數位傳遞的東西, 終將被網路取代。書店的定位必須轉型提供不同的服務,比方說營造店內的氣氛讓人想來逛, 像是誠品。或是經由個人品味挑選書本、寫評論分享自己挑選的書。

全程創業,販售服務

原文:

販售長期的服務,金流比賣一次性的產品來得穩定。也因為更了解用戶,有機會撥掘和提供新服務取得更多獲利。理論上從上至下都自己來,使用者用起來會更順。像選用 iPhone,和 Apple TV 結合的很流暢 (其它 iCloud 之類的我沒有用, 不知效果如何)。Android phone 和 Miracast 則不容易作到流暢。

什麼都自己來, 代價是要作更多事,分散火力。如今透過 smartphone 上搭配的「商城」 (App Store、Google Play), 傳遞產品和收取費用比以前簡單許多。至少降低了一個門檻。

Btw, 這段話讓我特別有感觸,注重在賣服務,而不是工具:

哈佛商學院教授 Theodore Levitt 說:「人們要的不是鑽孔機,而是牆上的洞。」他認為購買鑽孔機是種不完美的妥協。訂閱制往往能創造企業與客戶的雙贏,因為雙方的目標是一致的。

雜談

總體來說,產品本身是數位內容, 全程都可數位化; 本身不是數位內容 (如餐廳、搭車), 背後的媒合平台也可以作些改善 (O2O, Online-to-offline)。smartphone 和行動網路的普及, 讓人們可以重新思考如何將習以為常的事作得更好。習慣的包裹愈輕, 愈容易想到新方法, 也更有機會找到更好的方法 。

看這些評論很有意思,不過對於實際作的事到是沒有直接的幫助。主要是了解目前的趨勢,偶而檢查一下自己的思維是否被舊習慣所綁住,放寬思考的方向。產品的本質還是為使用者解決他們願意付錢解決的問題。

C++ 能否用 memcpy 複製 class / struct 的資料?

答案是: POD (plain old data) type 可以。POD type 可和 C 互通, CPP Reference POD Type 的介紹: Specifies that the type is POD (Plain Old Data) type. Thi...