GTA 的啟動讀取效能問題

這件事情也已經過了一個禮拜,來整理一下發生什麼事情...

起因是 GTA Online 的遊戲開啟速度很慢,而有人一路 reverse engineering 找出問題並且解決:「How I cut GTA Online loading times by 70%」,對應的 Hacker News 討論有提到其他有趣的事情也可以看看:「How I cut GTA Online loading times by 70% (nee.lv)」。

作者的電腦不算太差,但光開啟 GTA Online 就需要六分鐘,網路上甚至有辦投票蒐集大家的等待時間,發現也有很多人反應類似的問題:

接下來就開始 reverse engineering 了,先觀察各種狀態後發現是卡在 CPU,而不是網路或 Disk I/O,然後就拿出 Luke Stackwalker 這個工具 profiling,不過因為沒有 debug symbol 幫忙 group,所以只能人工判斷後,可以看到兩個問題:

第一個問題發現效能是卡在 strlen(),而 call stack 可以看出來是從 sscanf() 一路打進去的:

反追發現是在處理 10MB 的 JSON 檔造成的,裡面 sscanf() 因為拉出 strlen(),於是就造成把整個 10MB 的 JSON 掃過很多次 (一開始是 10MB,掃到後面會愈來愈少,平均下來應該是 5MB):

第二個問題產生的時間會在第一個問題跑完後,另外看問題的性質,應該跟第一個 JSON 處理有關,他會把 JSON 處理過的資料丟進 array,每個 entry 長這樣:

struct {
    uint64_t *hash;
    item_t   *item;
} entry;

丟進 array 是 OK 的,但問題在於他需要判斷 entry 是否重複,卻沒有用 hash 或是 tree 的結構,而這邊大約有 63k 筆資料,用 array 實做就產生了 O(n^2) 的演算法:

But before it’s stored? It checks the entire array, one by one, comparing the hash of the item to see if it’s in the list or not. With ~63k entries that’s (n^2+n)/2 = (63000^2+63000)/2 = 1984531500 checks if my math is right. Most of them useless. You have unique hashes why not use a hash map.

作者在 PoC 的章節裡面描述他怎麼解這兩個問題。

第一個問題比較好的解法是修正 JSON Parser,但這太複雜,所以他用 workaround 解:把 strlen() 包起來,針對長字串加上一層 cache:

  • hook strlen
  • wait for a long string
  • “cache” the start and length of it
  • if it’s called again within the string’s range, return cached value

而第二個問題他直接把檢查是否有重複的跳過,因為資料本身不重複:

And as for the hash-array problem, it’s more straightforward - just skip the duplicate checks entirely and insert the items directly since we know the values are unique.

整個開啟的速度從六分鐘降到一分五十秒,還是偏慢,但算是大幅緩解的 GTA Online 啟動速度的問題了。

不過故事到這邊還沒結束,有人一路去挖,發現其實 sscanf() 的效能地雷已經不是第一次了:YAML 的 Parser 也中過一樣的問題:「Parsing can become accidentally quadratic because of sscanf」,這篇也一樣上了 Hacker News:「Parsing can become accidentally quadratic because of sscanf (github.com/biojppm)」。

然後這又帶出了六年前在 StackOverflow 上就有人問過這個問題:「Why is glibc's sscanf vastly slower than fscanf on Linux?」。

另外也有人整理出來,應該是大家把同樣的演算法拿來實做:

JdeBP 3 days ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300.

There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not.

The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far.

後續的更新動作可以再追一下進度 (包括 GTA Online 與各家的 libc)。

一人團隊的技術架構

Hacker News Daily 上看到的文章,在講一人團隊時所設計的技術架構:「The Tech Stack of a One-Man SaaS」。這種資訊通常帶有個人偏好,維護成本算是蠻重要的重點,在多人團隊就未必會這樣選,但就拿著爆米花看戲的心態來說應該還 OK。

像是作者很明顯熟悉 Python,就可以看到他裡面會列出許多 Python 相關的 toolchain 與維護工具。

裡面比較有趣的是他對 DigitalOcean 的 K8S 問題很多抱怨了一番,然後換去 Linode 後又因為不想要自己管 PostgreSQL 而決定搬到 AWS 上面,可以用 RDS 省事... 花錢解決 XD

算是當短文小說在看...

AWS 對 Elastic Stack 實作免費的開源版本 Open Distro for Elasticsearch

Elasticsearch 的主體是 Apache License 2.0,但 Elastic Stack (以前叫做 X-Pack) 則是需要付費使用的功能,其中包括了不少跟安全有關的項目在裡面,所以其實有不少人抱怨過產品凌駕安全性的問題,像是「ES 6.3: X-Pack Licence is "Expired" on New Install」這篇官方回應的:

A basic license is not entitled to security features. To try out security you need to use a trial license or obtain a subscription.

AWS 這次則是出手實作了他們自己的版本,叫做 Open Distro for Elasticsearch:「New – Open Distro for Elasticsearch」。

如果你看文章說明,他列出來的 feature 全部都是在 Elastic Stack 這頁上列出來的項目,針對性的意思其實很清楚了:

In addition to Elasticsearch and Kibana, the first release includes a set of advanced security, event monitoring & alerting, performance analysis, and SQL query features (more on those in a bit).

而前面提到的安全性功能也包括在內:

Security – This plugin that supports node-to-node encryption, five types of authentication (basic, Active Directory, LDAP, Kerberos, and SAML), role-based access controls at multiple levels (clusters, indices, documents, and fields), audit logging, and cross-cluster search so that any node in a cluster can run search requests across other nodes in the cluster.

目前支援 Docker Image 與 RPM,之後看看有沒有機會出 deb 版本:

In addition to the source code repo, Open Distro for Elasticsearch and Kibana are available as RPM and Docker containers, with separate downloads for the SQL JDBC and the PerfTop CLI.

這樣應該會讓 Elasticsearch 的服務模式受到很大的影響,來看 Elastic N.V. Ordinary Shares Real Time Stock Quotes 這邊會掉多少...

讓 Laravel 的 PHPUnit 在發生錯誤時把 Stack 丟出來

這兩天又遇到一次,這應該是 Laravel 裡設計比較奇怪的地方,既然是跑 PHPUnit 的環境,為什麼不預設在錯誤發生時把完整的 stack 拋到 console...

這邊的解法是參考「Laravel: How to enable stacktrace error on PhpUnit」這篇的解答。

舊版需要自己丟 handler 進去 (5.4 以及之前的版本),在 5.5+ (寫這篇時最新的穩定版本已經是 5.6) 有內建 withoutExceptionHandling() 可以用,所以在 tests/TestCase.php 內搞定 setUp()

    protected function setUp()
    {
        parent::setUp();
        $this->withoutExceptionHandling();
    }

不知道有沒有機會直接進 Laravel 的 package 設定裡面...

PChome 24h 連線會慢的原因... (續篇)

上一篇「PChome 24h 連線會慢的原因...」寫到 DNS resolver 會倒在路邊,但沒寫會怎麼倒... 因為規格書上沒有寫當問不到要問的東西時要怎麼處理,所以每一家處理的方式都不太一樣。

我把對各 DNS resolver 查詢 100 次的結果放在 GitHub Gist 上:「Query 24h.pchome.com.tw」,大家都是回 SERVFAIL,只是時間不一樣 (最後一個 x.xxxx total 的部份表示實際秒數,wall clock)。

先看這次的主角好了,HiNet168.95.1.1168.95.192.1,同時也應該是 PChome 24h 服務使用人數最多的 DNS resolver。

這兩個 DNS resolver 在遇到問題時不會馬上回 SERVFAIL,加上業界有小道消息說中華自己改了不少 code,所以跟一般的 open source software 行為不太一樣。由於看不到 PChome 端的 DNS packet,所以只能就行為來猜... 應該是在第一輪都查不到後,會先 random sleep 一段時間,然後再去問一次,如果第二次還是失敗的話才回應 SERVFAIL

這個 random sleep 看起來可能是 10 秒,因為數據上看起來最長的時間就是這個了。

SEEDNet 的 139.175.1.1 以及 Google8.8.8.8 都沒這個問題,都會馬上回應 SERVFAIL

前陣子新出的 9.9.9.9 (參考「新的 DNS Resolver:9.9.9.9」) 則是有些特別的狀況,可以看到前面有三個 query 很慢 (第 2、3、5 三行),但後面的速度就正常了。可能是新加坡那邊有三台伺服器在服務 (目前我這邊測試的機器到 9.9.9.9 會到新加坡),在第一次遇到都沒有答案時會有特殊的演算法先確認,之後就會 cache 住?

所以各家 DNS resolver 反應都不太一樣,然後最大那家有問題 XD

24h.pchome.com.tw 慢一次,ecvip.pchome.com.tw 再慢一次,圖片的 a.ecimg.tw 再慢一次,一個頁面上多來幾個 domain 就會讓人受不了了 XD

其實我只要改成 8.8.8.8 或是改走 proxy.hinet.net 就可以解決啦,但還是寫下來吧 (抓頭)。

Happy Eyeballs (RFC 6555)

在「PChome 24h 連線會慢的原因...」這篇的 comment 有讀者提到了 Happy Eyeballs 應該可以解決這個問題:

除了可以在維基百科上面看到外,比較正式的說明可以參考 RFC 6555:「Happy Eyeballs: Success with Dual-Stack Hosts」,其中在「6. Example Algorithm」就有提到 Google ChromeMozilla Firefox 怎麼實做 Happy Eyeballs:

What follows is the algorithm implemented in Google Chrome and Mozilla Firefox.

  1. Call getaddinfo(), which returns a list of IP addresses sorted by the host's address preference policy.
  2. Initiate a connection attempt with the first address in that list (e.g., IPv6).
  3. If that connection does not complete within a short period of time (Firefox and Chrome use 300 ms), initiate a connection attempt with the first address belonging to the other address family (e.g., IPv4).
  4. The first connection that is established is used. The other connection is discarded.

If an algorithm were to cache connection success/failure, the caching would occur after step 4 determined which connection was successful.

Other example algorithms include [Perreault] and [Andrews].

可以看到 Happy Eyeballs 的演算法是要避免 IPv6 network 不通的情況卡住很慢 (如果在 300ms 內連線沒有建起來,就會儘快往另外一個 address family 嘗試),而不是在 DNS 層避免問題 (也就是 getaddinfo() 觸發的 DNS query)。

這次的情況是 DNS query 很慢,就會導致還是一開始就很慢,Happy Eyeballs 沒辦法解決這個問題。

不過話說回來,我是有印象知道有這個演算法,但不知道有「Happy Eyeballs」這個這麼逗趣的名字... (掩面)

Python 在高收入國家的成長

Stack Overflow 的內文其實有點奇怪的誤導... 主要是分析在 Stack Overflow 上 Python 成長的趨勢:「The Incredible Growth of Python」。

但一開始的分析是做高收入國家的部份:

但如果你捲到最下面,即使是非高收入的國家也是一樣急遽成長,只是沒那麼明顯:

Anyway,回到高收入國家的部份,如果用模型預測的話:

另外列出 YoY 成長:

這篇用高收入這個分法有種在炒話題的感覺...

「把工作自動化」的討論

最近在 The Workplace Stack Exchange 上還蠻火紅的一篇文章:「Is it unethical for me to not tell my employer I’ve automated my job?」。

作者的全職工作是從系統上抓資料出來,貼到 spreadsheet 上 (也許是 Excel?),這份工作的薪資還不錯,然後作者寫程式自動化掉後發現他每禮拜只需要做一兩個小時了:

There might be amendments to the spec and corresponding though email etc, but overall, I spend probably 1-2 hours per week on my job for which I am getting a full time wage.

然後在糾結要不要跟雇主講,跑上來發文 XDDD 有興趣的人可以去圍觀看一看下面的回應...

最近 OpenVPN 的安全性漏洞...

看到「The OpenVPN post-audit bug bonanza」這個只有苦笑啊...

作者在 OpenVPN 經過一連串的安全加強後 (包括 harden 計畫與兩個外部單位的程式碼稽核找到不少問題),決定出手挖看看:

After a hardening of the OpenVPN code (as commissioned by the Dutch intelligence service AIVD) and two recent audits 1 2, I thought it was now time for some real action ;).

然後就挖出不少問題了...

可以看到作者透過 fuzzing 打出一卡車,包含了不少 crash XDDD:(然後有一個是 stack buffer corruption,不知道有沒有機會變成 RCE)

  • Remote server crashes/double-free/memory leaks in certificate processing (CVE-2017-7521)
  • Remote (including MITM) client crash, data leak (CVE-2017-7520)
  • Remote (including MITM) client stack buffer corruption
  • Remote server crash (forced assertion failure) (CVE-2017-7508)
  • Crash mbed TLS/PolarSSL-based server (CVE-2017-7522)
  • Stack buffer overflow if long –tls-cipher is given

StackOverflow 預設全上 HTTPS 了...

HTTPS Everywhere 沒什麼感覺,但對於一般人應該不簡單,所以 Nick Craver (根本就是他們家非正式的 PR Engineer XDD 他這幾年寫了不少內部的資訊...) 寫了一篇關於上 HTTPS 的故事:「HTTPS on Stack Overflow: The End of a Long Road」。

其中他們為了支援舊設備 (沒有支援 SNI 的),決定直接把所有 wildcard 類的 SSL certificate 都包進去 (另外找 DigiCert 處理):

然後中間提到這個真的頗無奈的,抱怨 SVG 的 XML... XDDD:

Finding and killing these was a little fun because you can’t just search for "http://". Thank you so much W3C for gems like this:

<svg xmlns="http://www.w3.org/2000/svg"...

一條辛苦路 XD