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

Cloudflare 在 Argo 架構上推出 Tiered Cache Smart Topology

Cloudflare 在 Argo 架構上 (付費功能) 推出了 Tiered Cache Smart Topology:「Tiered Cache Smart Topology」、「Introducing: Smarter Tiered Cache Topology Generation」。

這邊提到的 Argo 是 Cloudflare 在 2017 年時提出來想要降低 Internet 的 routing (像是 BGP) 未必會走到最佳路徑上的問題,透過 Cloudflare 自家的骨幹網路,最佳化 latency & bandwidth & packet loss 產生的問題:「Introducing Argo — A faster, more reliable, more secure Internet for everyone」。

而 Tiered Cache 算是 CDN 行業裡面很常見的技術了,主要是要解決不同 data center 的 edge server 都去跟 origin server 要資料,而造成 origin server 的流量太大。

緩解的方式是在 edge server 與 origin server 中間疊一層 cache server,就可以大幅緩解 origin server 的流量。

origin server 流量問題在一般的應用來說還好:就算是 Windows Update 或是 iOS 更新這種基數超大的量,一開始也許會慢一點,但當 edge server 有 cache 後就不會再吃到 origin server 的頻寬。

另外也可以在公開上線前先 pre-warm,讓 edge server 都有 cache 後再上線,這樣 origin server 就不需要準備太多頻寬。

但在大型影音直播的時候就不一樣了,因為會一直產出新的內容 (之前玩的是走 HLS,所以會一直有新的 .ts 檔生出來),沒辦法先 pre-warm,這時候 origin server 就會需要大量的頻寬才有辦法支撐整個服務,所以需要 CDN 系統在中間疊一層 cache server,這個功能在各家 CDN 業者都有,只是名稱不太一樣。

記得當時用 Akamai 預設的 CDN 走直播時只有 95% 左右的 hit rate,這代表對外服務 20Gbps 就會對 origin server 產生 1Gbps 的量 (20:1),而打開 Tiered Distribution 後可以拉到 98% 甚至 99%+,相對於後端的壓力可以降到 50:1 到 100+:1。

AWSCloudFront 也有類似的架構,叫做 Regional Edge Caches:

不過這兩種架構都有一些缺點,像 Akamai 需要自己指定 cache server 的節點,這樣就不容易動態調整,或是使用者沒有設好導致 latency 偏高。

而像 AWS 這種已經已經先分好群的,就會遇到像是 origin server 與 edge server 都在台灣,但在 Regional Edge Caches 架構下必須先繞到日本 (或是新加坡),產生 latency 與 packet loss 偏高的問題。

這次 Cloudflare 在 Argo 架構推出的 Tiered Cache Smart Topology 的賣點 (Argo 本來就有提供 Tiered Cache),看起來是希望由系統自動選擇最佳的一個 data center 來當作 cache tier,不需要使用者額外設定。

不過一般網站應該還好,主力應該在電商網站與互動性很高的娛樂產業 (i.e. 操作起來要很流暢)...

Firefox 的 Cache Partition 也生效了

Google Chrome 實做了 Cache Partition (「Google Chrome 的 Cache Partition 生效」),Firefox 也實做的版本也進 standard 版本了:「Firefox 85 Cracks Down on Supercookies」。

In Firefox 85, we’re introducing a fundamental change in the browser’s network architecture to make all of our users safer: we now partition network connections and caches by the website being visited.

這要防禦的手法可以參考先前在「Google Chrome 要藉由拆開 HTTP Cache 提昇隱私」這邊提到的方法,主要就是共用 cache 時可以利用抓檔案的時間來判斷 (side channel information)。

這樣主流的瀏覽器都支援 Cache Partition 了...

Google Chrome 的 Cache Partition 生效

去年提到的「Google Chrome 要藉由拆開 HTTP Cache 提昇隱私」在最近推出的 Chrome 86 預設生效了:「Chrome changes how its cache system works to improve privacy」。

Google 的文章「Gaining security and privacy by partitioning the cache」這邊有提到不同瀏覽器都有打算要支援類似的架構,對應的差異:

Is this standardized? Do other browsers behave differently?

"HTTP cache partitions" is standardized in the fetch spec though browsers behave differently:

  • Chrome: Uses top-level scheme://eTLD+1 and frame scheme://eTLD+1
  • Safari: Uses top-level eTLD+1
  • Firefox: Planning to implement with top-level scheme://eTLD+1 and considering including a second key like Chrome

文章裡面看到了有趣的東西,是他提到了 Fetch 這個標準,然後是在「2.7. HTTP cache partitions」這邊出現了對應的說明:

To determine the HTTP cache partition, given request, run these steps:

Let key be the result of determining the network partition key given request.

If key is null, then return null.

Return the unique HTTP cache associated with key. [HTTP-CACHING]

所以看起來是訂 Fetch 時寫下一套方法,然後拿來擴大套用到整個瀏覽器...

Cloudflare 的另外一個策略:不熱門的資料只放到記憶體內

前陣子的文章,Cloudflare 將不熱門的資料放到記憶體內,不寫到磁碟裡面:「Why We Started Putting Unpopular Assets in Memory」。

主要的原因是這些不熱門的資料常常是一次性的,寫到 SSD 裡面反而浪費 SSD 的生命。而且這樣做因為減少了寫入,反而可以讓 SSD 的讀取變快:

The result: disk writes per second were reduced by roughly half and corresponding disk hit tail latency was reduced by approximately five percent.

這個想法還蠻特別的,但好像印象中之前有人有提過類似的方法...

Anyway,這個想法不只在 CDN 這邊可以用到,對於有 memory + storage 架構的 cache system 也可以套用類似的道理,而要怎麼決定哪些 object 要寫到磁碟裡面的演算法就是重點了...

題外話,剛剛因為突然想到,瞄了一下 Squid,發現連 HTTPS 都還沒上...

AWS 上的 Redis 服務支援 Global Replication

AWS 上的 Redis 服務 (Amazon ElastiCache) 推出了 Global Datastore,也就是跨區同步的功能:「Now Available: Amazon ElastiCache Global Datastore for Redis」。

技術上會分成 read endpoint 與 write endpoint (在最後面的操作可以看到 $US_WEST_1_CLUSTER_READWRITE$US_WEST_2_CLUSTER_READONLY),所以算是蠻常見的 primary-secondary 架構。

不過我基本上不太愛 Redis,能用 Memcached 解決的偏好用 Memcached 解。不過如果把 Redis 當作是一種雲端服務的話,倒是還可以接受...

蘋果的導流方案:Apple Edge Cache

Hacker News Daily 上看到蘋果的「Apple Edge Cache」這個服務,看起來就是個自家的 CDN 方案。

網路要求最低要能夠 peak 到 25Gbps 不算低,不過以蘋果的用量來說應該不算是高估:

Minimum 25 Gb/s peak traffic across all Apple traffic.

各家 ISP 應該都會考慮,畢竟 iPhoneiPad 的數量可不是假的,所以目前在台灣測到的點都是台灣的機房 (看 ping latency)...

另外一個有趣的事情是 SSL 的部份,從 SSL Labs 的資料可以看到一些有趣的東西:「SSL Report: cache.edge.apple (17.253.119.201)」。

一個是蘋果跟 GeoTrust 買了 Intermediate CA 再簽自己的 AEC 服務,另外一個是同時有 RSA 2048 bits 與 EC 256 bits 的 key,然後是支援 TLS 1.3 了。

跟其他內容業者的玩法類似,像是 NetflixOpen Connect