Content Defined Chunking (CDC)

前幾個禮拜在 Hacker News Daily 上看到「CDC File Transfer (github.com/google)」這則,連結是指到 GoogleGitHub 專案上,裡面實做了 FastCDC 演算法,另外說明他們為什麼要解這個問題以及對應的成果:「google/cdc-file-transfer」。

Google 的人看起來像是是在 CI/CD 階段遇到頻寬上的問題 (從「The builds are 40-45 GB large.」這邊猜),用 scprsync 看起來都不能解,所以他們自己刻了 FastCDC 演算法來解。

但我對 Content Defined Chunking (CDC) 不熟,所以先查一下 CDC 是什麼東西,就查到 restic 這篇講得很清楚:「Foundation - Introducing Content Defined Chunking (CDC)」。

要計算 delta 很直覺的作法就是要切 chunk,而接著的直覺就是固定大小的 chunk 切開,像是這樣每 16 bytes 切一個 chunk:

0123456789abcdef 0123456789abcdef 0123456789abcdef 0123456789abcdef

如果其中一個地方有變化,但其他沒變化的話就可以透過 cryptographic hash function (像是 SHA-256) 確認 chunk 內容一樣,進而省下很多傳輸的頻寬:

0123456789abcdef 0123456789ABCDEF 0123456789abcdef 0123456789abcdef

但可以馬上看出來這個方法的大缺點是只能處理 replacement,很難處理 insert & delete 的部份,舉例來說,如果變更是在開頭的地方加上 ABC,就會造成 chunk 會完全不一樣,而導致全部都要再傳一次:

ABC0123456789abc def0123456789abc def0123456789abc def0123456789abc def

這邊其實是個經典的演算法問題:想要找出兩個 string 的差異 (把舊的內容當作一個 string,新的內容也當作一個 string)。

這個問題算是 Edit distance 類型的題目,但你會發現解 Edit distance 的演算法會需要先傳輸完整個 string 才能開始跑演算法,這就本末倒置了。

而另外一個想法是,放棄固定的 chunk 大小,改用其他方式決定 chunk 的邊界要切在哪裡。而 CDC 就是利用一段 sliding window + hash 來找出切割的點。

文章裡面提到的 sliding window 是 64 bytes,這邊就可以算出對應的 HASH(b0, b1, ..., b63),然後往右滑動變成 HASH(b1, b2, ..., b64),再來是 HASH(b2, b3, ..., b65),一直往右滑動計算。

接下來 restic 會看 hash 值,如果最低的 21 bits 都是 0 就切開,所以 chunk 大小的期望值應該是 2MB?(這邊不確定,好像不能直接用 2^21 算,應該用積分之類的方法...)

For each fingerprint, restic then tests if the lowest 21 bits are zero. If this is the case, restic found a new chunk boundary.

而這個演算法可以適應新增與刪除的操作,不會造成從新增或刪除後的資料都要重傳,只有自己這個 chunk 需要重傳 (可能前或後的 chunk 也會要)。

然後挑一下 hash function 的特性,就可以讓計算的速度也很快。這邊提到了 hash function 可以用 Rolling hash,可以很快的從 HASH(b0, b1, ..., b63) 算出 HASH(b1, b2, ..., b64),而不需要全部重算。

有了 chunk 後,再用 cryptographic hash function 比較 chunk 的內容是否一樣,這樣就可以大幅降低傳輸所需要的頻寬了。

Vultr 更新流量計算方式

一時間沒找到在哪邊看到的,但的確是漏掉這個消息,早上看到去翻才注意到的... Vultr 在去年 11 月底宣佈更新流量的計算方式:「Vultr Announces Reduced Bandwidth Pricing, 2 TB of Free Monthly Egress, Free Ingress, and Global Pooling」。

這波費用的更新算是跟上另外兩家 (LinodeDigitalOcean) 的算法了,先前 Vultr 的算法就很古老 XD

第一個是 inbound traffic 不算錢了 (總算):

Data ingress will now be free.

再來是 traffic pool 的概念,現在每個帳號的流量會統一計算,而非每台機器自己計算:

All customers will receive global account-level pooling of transfer across all instances and locations.

然後是每個帳號都提供 2TB 的 free outbound traffic,這點有點放送的感覺:

Every Vultr customer will now receive two terabytes (2 TB) of free outbound data transfer every month, in addition to the transfer included with each subscription.

最後是超量的部份收費也簡化了,不管什麼地區都是 $0.01/GB:

Vultr will now offer a reduced, single worldwide egress overage rate of only $0.01 per GB.

最後這點有個值得操作的點:依照他的收費標準,超量 1TB 的流量需要付 $10 的費用,但你可以多租一台 $5/mo 的機器,這個方式提供了 1TB 的流量到 traffic pool 裡面。

KataGo 1.12.0 與 UEC 杯用的 model:b18c384nbt-uec.bin.gz

剛剛看到 KataGo 出了 1.12.0,同時也放出了在 2022 年十一月 UEC 比賽時用的 model:「New Neural Net Architecture!」。

1.12.0 比較特別的新的類神經網路架構:

This version of KataGo adds support for a new and improved neural net architecture!

這個新的架構以及其他的改善讓訓練的速度改善:

The new neural nets use a new nested residual bottleneck structure, along with other major improvements in training. They train faster than KataGo's old nets and learn more effectively.

另外一個是他把 UEC 比賽時用的 model 放出來了,很特別的是採用 b18c384,而 KataGo Distributed Training 這邊目前主要是 b40c256 與 b60c320,看起來是為了比賽而一次性訓練出來的。

依照他的說法這個 b18c384 版本跟目前訓練網站上的 b60c320 有差不多強度,但計算速度會比 b60c320 快不少,甚至在一些機器上會跟 b40c256 差不多快:

Attached to this release is a one-off net b18c384nbt-uec.bin.gz that was trained for a tournament in 2022, which should be of similar strength to the 60-block nets on http://katagotraining.org/, but on many machines will run much faster, on some machines between 40-block and 60-block speed, but on some machines even as fast as or faster than 40-block.

另外一個大改變是他把訓練工具從 TensowFlow 跳槽到 PyTorch

The training code has been all rewritten to use pytorch instead of tensorflow.

在 release note 裡沒有提到原因,但這個頗讓人好奇的...

Twitter 新政策禁止推廣其他社交平台的連結

看到 Paul Graham 這個宣告:

裡面提到的新政策在「Promotion of alternative social platforms policy」這邊,直接禁止其他社交平台:

At both the Tweet level and the account level, we will remove any free promotion of prohibited 3rd-party social media platforms, such as linking out (i.e. using URLs) to any of the below platforms on Twitter, or providing your handle without a URL:

  • Prohibited platforms:
    • Facebook, Instagram, Mastodon, Truth Social, Tribel, Post and Nostr
    • 3rd-party social media link aggregators such as linktr.ee, lnk.bio

Hacker News 的討論上面,Paul Graham 有回應 (帳號是 pg),他又提出了一些猜測與見解,包含了他覺得這個新政策會被收回:「Paul Graham is leaving Twitter for now (twitter.com/paulg)」。

I'm not leaving Twitter. It seems more likely than not that Elon will reverse the ban on links to other social media sites. I just don't want to hang out there in the meantime. Plus given the way things are going, it seemed like a good time to learn about alternatives.

I still think Elon is a smart guy. His work on cars and rockets speaks for itself. Nor do I think he's the villain a lot of people try to make him out to be. He's eccentric, definitely, but that should be news to no one. Plus I don't think he realizes that the techniques that work for cars and rockets don't work in social media. Those two facts are sufficient to explain most of his behavior.

He could still salvage the situation. He's the sort of person it would be a big mistake to write off. And I hope he does. I would be delighted to go back to using Twitter regularly.

不過的確如他說的,這是個好機會嘗試其他的 social network...

Tailscale 也推出類似 Cloudflare Tunnel 的產品,Tailscale Funnel

Tailscale 也推出了類似 Cloudflare Tunnel 的產品,叫做 Tailscale Funnel:「Introducing Tailscale Funnel」。

都是透過 server 本身主動連到 Cloudflare 或是 Tailscale 的伺服器上,接著外部的 request 就可以繞進來了。

不過 Tailscale Funnel 的定位跟 Cloudflare Tunnel 有些差異,看起來 Tailscale Funnel 比較偏向給 dev/stage 環境的用法,Cloudflare Tunnel 像是要跑在 production 的設計?

目前是 alpha 階段,有些限制,像是目前能開的 port:

The ports you can specify to expose your servers on are currently to 443, 8443 and 10000.

另外從技術面上看起來一定得用 TLS 連線,因為他得透過 TLS 的 SNI 資訊來決定是誰:

We can only see the source IP and port, the SNI name, and the number of bytes passing through.

對於已經有用 Tailscale 的使用者來說好像可以玩看看,但另外一點是 Cloudflare 的機房密度很高,這點可能是 Tailscale 也要想一下的問題?

英國政府開始定時掃描英國內的網路服務

Hacker News Daily 上看到的,英國政府也建立了自己的掃描資料庫:「NCSC Scanning information」。

看起來是類似於 Shodan 這樣的服務,但是範圍限制在英國內的網路服務:

These activities cover any internet-accessible system that is hosted within the UK and vulnerabilities that are common or particularly important due to their high impact.

不過這個東西各國應該都有做,只是有沒有公開講?

Netflix 單機 800Gbps 伺服器所使用的最佳化技巧

Hacker News 上看到 Netflix 的人丟出來的投影片,試著了解 Netflix 的 Open Connect Appliances 裡與 FreeBSD 相關的最佳化技巧對於效能的影響:「The “other” FreeBSD optimizations used by Netflix to serve video at 800Gb/s from a single server」。

看起來這邊的分析是先基於 400Gbps 的版本,可以跑到 375Gbps (53% CPU),接著在上面拔掉各種最佳化的設定,看看會掉多少流量。這邊可以參考先前在「Netflix 在單機服務 400Gbps 的影音流量」提到的資料。

投影片上的第一章是 sendfile 與 kTLS 相關的最佳化,這邊可以看出來都是重要的項目,隨便關掉一個就會掉很多 capacity:

  • Disable kTLS (and async sendfile) + nginx aio:40Gbps (100% CPU)
  • Disable kTLS (and async sendfile) + nginx thread pools:90Gbps (90% CPU)
  • Disable sendfile (but use kTLS):75Gbps (80% CPU)
  • Disable sendfile (but use NIC kTLS):95Gbps (80% CPU)
  • Enable Sendfile & kTLS, but disable ISA-L crypto:180Gbps (80% CPU)
  • Enable Sendfile & kTLS:240Gbps (80% CPU)

第二章是 virtual memory,UMA VM Page Cache 這邊看起來最明顯,SF_NOCACHE 也是個重要的項目:

  • Disable UMA VM Page Cache:60Gbps (95% CPU)
  • Disable VM Batch Queues:280Gbps (95% CPU)
  • Disable SF_NOCACHE:120Gbps (55% CPU)

另外第二章特別提到了一個之前沒有用到的 optimization,是把 arm64 上面的 4KB Pages 變成 16KB Pages,這帶動了些許的效能提昇,並且降低了 CPU 使用率:

345Gb/s @ 80% CPU -> 368Gb/s @ 66% CPU

第三章是 network stack,看起來 TSO 帶來的效益也是很高:

  • Disable TCP Large Receive Offload:330Gbps (65% CPU)
  • Disable RSS accelerated LRO:365Gbps (70% CPU)
  • TSO Disabled:180Gbps (85% CPU)
  • Disable TSO and LRO:170Gbps (85% CPU)

最後面則是有提到從 400Gbps 到 800Gbps 還多做了那些事情,最後是達到 731Gbps。

用的機器是 Dell PowerEdge R7525,這是一台 2U 的機器啊...

ISC DHCPD 要 EoL

看到「ISC DHCP Server has reached EOL」這個,月初的時候 ISC 宣佈了 EoL,除非有嚴重的安全性問題冒出來,不然官方打算停止維護了:

The 4.4.3-P1 and 4.1-ESV-R16-P2 versions of ISC DHCP, released on October 5, 2022, are the last maintenance versions of this software that ISC plans to publish. If we become aware of a significant security vulnerability, we might make an exception to this, but it is our intention to cease actively maintaining this codebase.

ISC 則是在推 Kea

Network and system administrators deploying DHCP in new environments should look beyond ISC DHCP for a solution, as it would be irresponsible to invest in new deployments of this software which is now end-of-life. Naturally, ISC suggests new users consider our Kea DHCP server, but there are alternatives.

從維基百科上的「Comparison of DHCP server software」這頁可以看到目前 DHCP server 的選擇。最直接的差異是,其他非 ISC 的全部都是 GPL,只有 ISC 的是 non-GPL。

不過一般不太會自己架 DHCP server,大多是用設備內建裝的跑,以後如果有機會要裝的話,也許得去熟悉 Kea 了...

Starlink 再開一條產品線 Aviation

Starlink 推出新的產品線 Starlink Aviation,預定在 2023 年推出:

High-speed, low-latency, in-flight internet with connectivity across the globe. Reserve now with deliveries starting in 2023.

客群看起來是航空公司 (或是私人飛機的機主),而非一般人。每一台飛機可以提供 350Mbps 的頻寬:

Starlink can deliver up to 350 Mbps to each plane, enabling all passengers to access streaming-capable internet at the same time.

所以看起來是要跟現在在飛機上的 internet 服務競爭,如果要用玩的話大概是看看哪家航空公司採用,不然就是得自己買飛機了 (?)...

Starlink 在亞洲的第一個點開台了:日本

Twitter 上看到有日本人在測 Starlink

搜新聞看到開台了:「Elon Musk's Starlink launches satellite internet service in Japan」,然後費用大概是因為還沒有調整匯率的關係,稍微比美國的 US$110/mo 低一些:

SpaceX made the announcement on its official Twitter page. According to its official website, the monthly service fee is 12,300 yen ($84) on top of hardware costs of 73,000 yen.

不過官網上看起來不是全區,只有本州的東半部,包括東京:

從回報的 routing 看起來 latency 還行?東京 30ms,新加坡 130ms... 這樣對於偏遠山區沒有佈建高速網路的,也許可以考慮用用看?