把 Blog 丟到 CloudFront 上

先前在「AWS 流量相關的 Free Tier 增加不少...」這邊有提到一般性的流量從 1GB/month per region 升到 100GB/month,另外 CloudFront 則是大幅增加,從 50GB/month (只有註冊完的前 12 個月) 提升到 1TB/month (不限制 12 個月),另外 CloudFront 到 EC2 中間的流量是不計費的。

剛剛花了點功夫把 blog 從 Cloudflare 搬到 CloudFront 上,另外先對預設的 /* 調整成 no cache,然後針對 /wp-content/* 另外加上 cache 處理,跑一陣子看看有沒有問題再說...

目前比較明顯的改善就是 latency,從 HiNet 連到免費版的 Cloudflare 會導去美國,用 CloudFront 的話就會是台灣了:

另外一方面,這樣國際頻寬的部份就會走進 AWS 的骨幹,比起透過 HiNet 自己連到美國的 PoP 上,理論上應該是會快一些...

在 Minecraft 裡面幹出一台完整的電腦

Lobsters Daily 上看到有強者在 Minecraft 實做邏輯電路,幹出一台完整的電腦出來 (CPU 的部份應該是 turing-complete 了):

PCWorld 有報導:「This 8-bit processor built in Minecraft can run its own games」。

把影片裡的描述截圖出來:

連分支預測器都出現了:

記憶體就 Minecraft 來說也是超大的 256 bytes:

然後還做了 cache 層,這邊提到的是 data cache:

然後這邊是 instruction cache:

也因為已經相當的 powerful,很多經典遊戲都可以玩,像是俄羅斯方塊:

貪食蛇:

打磚塊:

Connect Four

來看 Intel + Varnish 的單機 500Gbps 的 PR 新聞稿

在「Varnish Software Achieves 500Gbps Throughput Per Server for UHD Video Content」這邊看到 PR 稿,由 IntelVarnish 合作,宣稱達到單機 500Gbps 的 throughput 了:

According to Varnish Software, the following were the outcomes of the test:

  • 509.7 Gbps live-linear throughput, using a dual-processor configuration
  • 487.2 Gbps video-on-demand throughput, using a dual-processor configuration

白皮書在「Delivering up to 500 Gbps Throughput for Next-Gen CDNs」這頁可以用個資交換下載,不過用搜尋引擎找一下可以發現 Intel 那邊有放出 PDF (但不確定兩邊給的是不是同一份):「Delivering up to 500 Gbps Throughput for Next-Gen CDNs」。

單 CPU 的伺服器是四個 100Gbps 界面接出來,雙 CPU 的伺服器是八個 (這邊 SUT 是 system under test 的縮寫):

These client systems were connected to the CDN servers using 100 GbE links through a switch; 4x100 GbE connections for the single-processor SUT, and 8x100 GbE for the dualprocessor SUT. Testing was done using Wrk, a widely recognized open-source HTTP(S) benchmarking tool.

不過如果實際看圖會發現伺服器是兩個 100Gbps (單 CPU) 與四個 100Gbps (雙 CPU),然後 wrk 也吃了兩個或是四個 100Gbps:

在白皮書最後面也有提到測試的配置,都是在 Ubuntu 20.04 上面跑,單 CPU 用的是兩張 Intel 的 100Gbps 網卡,雙 CPU 的用的是四張 Mellanox 的 100Gbps 網卡:

3rd generation Intel Xeon Scalable testing done by Intel in September 2021. Single processor SUT configuration was based on the Supermicro SMC 110P-WTR-TNR single socket server based on Intel® Xeon® Platinum 8380 processor (microcode: 0xd000280) with 40 cores operating at 2.3 GHz. The server featured 256 GB of RAM. Intel® Hyper-Threading Technology was enabled, as was Intel® Turbo Boost Technology 2.0. Platform controller hub was the Intel C620. NUMA balancing was enabled. BIOS version was 1.1. Network connectivity was provided by two 100 GbE Intel® Ethernet Network Adapters E810. 1.2 TB of boot storage was available via an Intel SSD. Application storage totaled 3.84TB per drive and was provided by 8 Intel P5510 SSDs. The operating system was Ubuntu Linux release 20.04 LTS with kernel 5.4.0-80 generic. Compiler GCC was version 9.3.0. The workload was wrk/master (April 17, 2019), and the version of Varnish was varnishplus-6.0.8r3. Openssl v1.1.1h was also used. All traffic from clients to SUT was encrypted via TLS.

3rd generation Intel Xeon Scalable testing done by Intel in September 2021. Dual processor SUT configuration was based on the Supermicro SMC 22OU-TNR dual socket server based on Intel® Xeon® Platinum 8380 processor (microcode: 0xd000280) with 40 cores operating at 2.3 GHz. The server featured 256 GB of RAM. Intel® Hyper-Threading Technology was enabled, as was Intel® Turbo Boost Technology 2.0. Platform controller hub was the Intel C620. NUMA balancing was enabled. BIOS version was 1.1. Network connectivity was provided by four 100 GbE Mellanox MCX516A-CDAT adapters. 1.2 TB of boot storage was available via an Intel SSD. Application storage totaled 3.84TB per drive and was provided by 12 Intel P5510 SSDs. The operating system was Ubuntu Linux release 20.04 LTS with kernel 5.4.0-80- generic. Compiler GCC was version 9.3.0. The workload was wrk/master (April 17, 2019), and the version of Varnish was varnish-plus6.0.8r3. Openssl v1.1.1h was also used. All traffic from clients to SUT was encrypted via TLS.

不過馬上就會滿頭問號,四張 100Gbps 是怎麼跑到 500Gbps 的頻寬...

這份 PR 馬上就讓人想到 Netflix 先前放出來的投影片 (先前有在「Netflix 在單機服務 400Gbps 的影音流量」這篇提到),在 Netflix 的投影片裡面有提到他們在 Intel 平台上面受限於記憶體的頻寬,整台機器只能跑到 230Gbps。

另外一種猜測是,如果 Intel 與 Varnish 宣稱的 500Gbps 是算 switch 上的總流量 (有這樣算的嗎,你是 Juniper 嗎...),那這邊的 500Gbps 換算回去差不多就是減半 (還很客氣的沒把 cache 沒中需要去 origin server 拉資料的流量扣掉),跟 Netflix 在 FreeBSD 上跑出來的結果差不多啊...

坐等反駁 XDDD

Memcached 與 Redis 的比較

在「Memcached vs Redis - More Different Than You Would Expect」這邊看到對 MemcachedRedis 的分析。

這兩套軟體都很常被拿來用作 cache 機制,所以一般來說比較時就是比兩邊都有的東西 (如果你要 pub-sub 之類的東西,在這兩套裡面只有 Redis 有)。

最前面還是先講了對使用者 (開發者) 的差異,很明顯的是 Redis 對各種不同的資聊結構都有支援,這點可以從 Redis 被官方被稱作 Data Structures Server 就可以知道 (在「An introduction to Redis data types and abstractions」這篇可以看到),而 Memcached 只支援了 key-value 架構。

不過如果是以 cache 來說,的確 key-value 架構就還蠻好用的。

後面就開始比較硬的主題了,提到了 Memcached 與 Redis 內部是怎麼使用記憶體的。

Memcached 的部份先提了 page/slab/chunk 的架構以及產生的效能限制與浪費,接著有提到 2020 年 refactor 的部份 (太久沒有看 Memcached 的消息,去年沒跟到這個部份),讓多 CPU 的支援度更好。

Redis 則是靠 jemalloc 來處理這個部份,另外加上 background thread 的機制降低 fragment。

然後是比較 cache expiration 的部份,可以看到兩者用的演算法在現實世界中都夠用 (尤其是當作 cache 來用),這部份跟印象中的架構差不多,應該是沒有太大變化。

最後是比較 cluster 的部份,Memcached 是 share nothing,所以沒什麼好說的,主要是靠 client library 實做 consistent hash 之類的架構打散;而 Redis 的話看起來有實做新的機制出來 (也沒跟到),之後有機會再看看可以做到什麼程度。

不過好像沒提到 proxy 之類的架構,基本上各大公司都有自己幹:

少了這塊對於 cluster 架構的完整性差蠻多的。

文章最後沒有下定論一定要用哪個比較好,兩者都有強項與弱項,還是得看情況來處理。不過我自己還是很喜歡用 Memcached 就是了...

重寫 Ptt 上的 Imgur Userscript 解決圖片出不來的問題

前幾個禮拜 Imgur 決定擋掉 Ptt 的網頁版,所以 Ptt 網頁版上會發現 Imgur 的圖都不見了:「[問題] 突然imgur的貼圖無法顯示」。

這是因為 Imgur 用 Referer 擋了 Ptt 的關係,後來 Ptt 官方在 8/15 後有針對 https://i.imgur.com/ 的圖片改用 https://cache.ptt.cc/ 過一層,不過 https://imgur.com/ 的就沒圖了。

這邊可以參考 Certificate Transparency 的「crt.sh | cache.ptt.cc」記錄,以及台大對於 Ptt 的流量的記錄 (出自「PTT 流量分析」這邊):

除了 Ptt 官方的解法外,另外可以自己寫 userscript,用 Referrer-Policy 繞過 (需要比較新版的瀏覽器,不過目前的瀏覽氣應該都夠新),看了一下本來的 ptt-imgur-cleaner-gm,發現要整個打掉改寫,索性就開一個新的專案變成 imgur-links-rewriting-on-ptt

這個版本的特色:

  • 加上對 https://imgur.com/a/ (album) 的支援,可以顯示第一張圖。
  • WebP 的版本,下載速度應該會快一些。
  • 偏好都是用大圖 (原始大小的圖片)。
  • 把本來走 https://cache.ptt.cc/ 的版本換回直接走 https://i.imgur.com/,就不用透過 TANet 或是台大的出國頻寬了。

程式碼不長 (參考「imgur-links-rewriting-on-ptt.user.js」這邊),主要是練手... 沒事就寫一下 userscript 可以維持對於 JavaScript 的基本熟悉度。

又再次看到了 Spectre Mitigation 的效能損失...

Hacker News 首頁上看到的文章,講 Spectre Mitigation 的效能損失:「Spectre Mitigations Murder *Userspace* Performance In The Presence Of Frequent Syscalls」,對應的討論串在「Spectre Mitigations Murder Userspace Performance (ocallahan.org)」。

看起來作者是在調校 rr 時遇到的問題,幾年前有提到過 rr:「Microsoft 的 TTD 與 Mozilla 的 RR」。

對此作者對 rr 上了一個 patch,減少了 mitigation code 會在 syscall 時清掉 cache 與 TLB,這個 patch 讓執行的速度大幅提昇:「Cache access() calls to avoid syscalls」。

另外作者提到了他的硬體是 IntelSkylake,他又再跑一次 pre-patch 與 post-patch 的速度,可以看到在 pre-patch 前,mitigation 會讓系統慢超多 (從 2m5.776s 到 3m19.648s),而 post-patch 後大幅降低 syscall 的使用,就不會影響那麼多 (從 0m33.422s 到 0m36.160s)。

就目前知道的 mitigation 方式來說,這個猜測應該是對的...

Amazon S3 變成 Strong Consistency 背後的改善方式

看到 Hacker News 上的討論「Diving Deep on S3 Consistency (allthingsdistributed.com)」才想到該整理一下,原文的「Diving Deep on S3 Consistency」是 Amazon 的 CTO Werner Vogels 花了一些篇幅描述 Amazon S3 怎麼把 Eventually Consistent 變成 Strongly Consistent,當初 Amazon S3 公告時我也有寫一篇文章提到:「Amazon S3 現在變成 Strong Read-After-Write Consistency 啦...」。

Amazon S3 之所以會是 Eventually Consisient 是因為 Metadata Subsystem 的 cache 設計:

Per-object metadata is stored within a discrete S3 subsystem. This system is on the data path for GET, PUT, and DELETE requests, and is responsible for handling LIST and HEAD requests. At the core of this system is a persistence tier that stores metadata. Our persistence tier uses a caching technology that is designed to be highly resilient. S3 requests should still succeed even if infrastructure supporting the cache becomes impaired. This meant that, on rare occasions, writes might flow through one part of cache infrastructure while reads end up querying another. This was the primary source of S3’s eventual consistency.

如果要解決 Eventually Consistent,最直接的想法是拔掉 cache,但這樣對效能的影響太大,所以得在要保留 cache 的情況下設計,所以就想到用其他管道確保 cache 裡的資料狀態是正確的:

One early consideration for delivering strong consistency was to bypass our caching infrastructure and send requests directly to the persistence layer. But this wouldn’t meet our bar for no tradeoffs on performance. We needed to keep the cache. To keep values properly synchronized across cores, CPUs implement cache coherence protocols. And that’s what we needed here: a cache coherence protocol for our metadata caches that allowed strong consistency for all requests.

而接下來是設計一連串的邏輯確保每個 S3 object 的操作都有 serializability:

We had introduced new replication logic into our persistence tier that acts as a building block for our at-least-once event notification delivery system and our Replication Time Control feature. This new replication logic allows us to reason about the “order of operations” per-object in S3. This is the core piece of our cache coherency protocol.

後面又要確保這個 cache coherence 的 HA,最後要能夠驗證實做上的正確性,花的力氣比實做協定本身還多:

These verification techniques were a lot of work. They were more work, in fact, than the actual implementation itself. But we put this rigor into the design and implementation of S3’s strong consistency because that is what our customers need.

Amazon S3 算是 AWS 當初推出來的招牌,當時的 Amazon S3 底層的論文「Amazon's Dynamo」劇烈影響了後來整個產業 (雖然論文裡面是拿 Amazon 的購物車說明),這次的補充算是更新了原來論文的技術,告訴大家本來的 Eventually Consistent 是可以再拉到 Strongly Consistent。

Dan Kaminsky 過世

Hacker News 首頁上看到震驚的消息,Dan Kaminsky 過世:「Dan Kaminsky has died (twitter.com/marcwrogers)」,目前還沒看到過世的原因...

Dan Kaminsky 最有名的「成果」應該是在 2008 年發現當時大多數的 DNS resolver 軟體實做有問題,可以被 DNS cache poisoning 攻擊,當年我有寫下來提到,但寫的很短:「DNS 伺服器安全性更新」。

攻擊手法是先發一個 DNS query 到 DNS resolver,然後馬上再送出一個偽造的 DNS response packet 給 DNS resolver 收,運氣好的話這個偽造的結果就會被 cache 起來。

記得當年的 168.95.1.1168.95.192.1 沒有太直接受到影響 (相較於其他的 DNS resolver),是因為這兩個 DNS resolver 後面有 server cluster 會打散流量,所以未必能猜對去查詢時用的 DNS server 所使用的 IP address,有點類似下面提到的緩解方案 (只是沒那麼有效)。

而記得後來的緩解方式是透過亂數化 source port (讓 DNS resolver 查詢時不要從 port 53 出去問),這個方式讓攻擊機率大幅下降 (大約降到 1/2^{16} 的機率)。

後來 DNS 加上 nonce 機制再繼續壓低攻擊成功的機率 (再降一次 1/2^{16},變成大約 1/2^{32}),最後則是 DNSSEC 的支援度逐漸普及,才解決掉這個問題。

資安領域的重大損失,尤其在 DNS 這塊...

Google 釋出網頁版的 Spectre 攻擊 PoC,包括 Apple M1 在內

在大約三年前 (2018 年年初) 的時候,在讀完 Spectre 之後寫下了一些記錄:「讀書時間:Spectre 的攻擊方式」,結果在 Bruce Schneier 這邊看到消息,Google 前幾天把把 PoC 放出來了:「Exploiting Spectre Over the Internet」,在 Hacker News 上也有討論:「A Spectre proof-of-concept for a Spectre-proof web (googleblog.com)」。

首先是這個攻擊方法在目前的瀏覽器都還有用,而且包括 Apple M1 上都可以跑:

The demonstration website can leak data at a speed of 1kB/s when running on Chrome 88 on an Intel Skylake CPU. Note that the code will likely require minor modifications to apply to other CPUs or browser versions; however, in our tests the attack was successful on several other processors, including the Apple M1 ARM CPU, without any major changes.

即使目前的瀏覽器都已經把 performance.now() 改為 1ms 的精度,也還是可以達到 60 bytes/sec 的速度:

While experimenting, we also developed other PoCs with different properties. Some examples include:

  • A PoC which can leak 8kB/s of data at a cost of reduced stability using performance.now() as a timer with 5μs precision.
  • A PoC which leaks data at 60B/s using timers with a precision of 1ms or worse.

比較苦的消息是 Google 已經確認在軟體層沒辦法解乾淨,目前在瀏覽器上只能靠各種 isolation 降低風險,像是將不同站台跑在不同的 process 裡面:

In 2019, the team responsible for V8, Chrome’s JavaScript engine, published a blog post and whitepaper concluding that such attacks can’t be reliably mitigated at the software level. Instead, robust solutions to these issues require security boundaries in applications such as web browsers to be aligned with low-level primitives, for example process-based isolation.

Apple M1 也中這件事情讓人比較意外一點,看起來是當初開發的時候沒評估?目前傳言的 M1x 與 M2 不知道會怎樣...

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)。