幹壞事是進步最大的原動力
在 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，很多經典遊戲都可以玩，像是俄羅斯方塊：
貪食蛇：
打磚塊：
在「Varnish Software Achieves 500Gbps Throughput Per Server for UHD Video Content」這邊看到 PR 稿，由 Intel 與 Varnish 合作，宣稱達到單機 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 vs Redis - More Different Than You Would Expect」這邊看到對 Memcached 與 Redis 的分析。
這兩套軟體都很常被拿來用作 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 就是了...
前幾個禮拜 Imgur 決定擋掉 Ptt 的網頁版，所以 Ptt 網頁版上會發現 Imgur 的圖都不見了：「[問題] 突然imgur的貼圖無法顯示」。
這是因為 Imgur 用 Referer 擋了 Ptt 的關係，後來 Ptt 官方在 8/15 後有針對 https://i.gslin.com/imgur/ 的圖片改用 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) 的支援，可以顯示第一張圖。https://cache.ptt.cc/ 的版本換回直接走 https://i.gslin.com/imgur/，就不用透過 TANet 或是台大的出國頻寬了。程式碼不長 (參考「imgur-links-rewriting-on-ptt.user.js」這邊)，主要是練手... 沒事就寫一下 userscript 可以維持對於 JavaScript 的基本熟悉度。
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」。
另外作者提到了他的硬體是 Intel 的 Skylake，他又再跑一次 pre-patch 與 post-patch 的速度，可以看到在 pre-patch 前，mitigation 會讓系統慢超多 (從 2m5.776s 到 3m19.648s)，而 post-patch 後大幅降低 syscall 的使用，就不會影響那麼多 (從 0m33.422s 到 0m36.160s)。
就目前知道的 mitigation 方式來說，這個猜測應該是對的...
看到 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。
在 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.1 與 168.95.192.1 沒有太直接受到影響 (相較於其他的 DNS resolver)，是因為這兩個 DNS resolver 後面有 server cluster 會打散流量，所以未必能猜對去查詢時用的 DNS server 所使用的 IP address，有點類似下面提到的緩解方案 (只是沒那麼有效)。
而記得後來的緩解方式是透過亂數化 source port (讓 DNS resolver 查詢時不要從 port 53 出去問)，這個方式讓攻擊機率大幅下降 (大約降到 
後來 DNS 加上 nonce 機制再繼續壓低攻擊成功的機率 (再降一次 
資安領域的重大損失，尤其在 DNS 這塊...
在大約三年前 (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 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：「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。
在 AWS 的 CloudFront 也有類似的架構，叫做 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. 操作起來要很流暢)...