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 的內容是否一樣,這樣就可以大幅降低傳輸所需要的頻寬了。

RFC 定義的 application/problem+json (或是 xml)

剛剛在 Clubhouse 上聽到保哥提到了 RFC 7807 這個東西 (Problem Details for HTTP APIs),剛剛翻瀏覽器累積的 tab,發現原來先前有看到,而且有打算要出新版的消息:

RFC 7807 裡面這樣定義的方式可以讓 client 端直接判斷 Content-Type 知道這個回傳資料是不是錯誤訊息,不然以前都是 JSON 就得再另外包裝。用 Content-Type 的作法可以讓判斷條件變得清晰不少。

除了 application/problem+jsonapplication/problem+xml 以外,在「3.1. Members of a Problem Details Object」裡面則是說明 JSON (或是 XML) 裡面有哪些必要以及可選的資訊要填,然後「3.2. Extension Members」這邊則大概描述一下怎麼擴充。

先有個印象,之後新規劃的東西可以考慮進去...

CloudFront 新增泰國節點

看到 Amazon CloudFront 新增了泰國曼谷節點的消息:「Amazon CloudFront launches in Thailand」,原來泰國之前沒開啊...

Amazon CloudFront announces its first two edge locations in Thailand.

另外依照網路架構,先前泰國的流量應該是往新加坡或是香港跑 (我覺得新加坡可能比較像?),不過也不是那麼確定... 畢竟地理位置比較近的馬來西亞可以透過陸地就拉過去,不需要走海纜,只是不確定馬來西亞的點有沒有買 transit:

These new edge locations in Bangkok will provide viewers as much as a 30% reduction in p90 latency measures.

然後最近都至少是兩個點在開了,對服務穩定性比較好,維修的影響也比較小...

Safari 上 uBlock Origin 的情況

uBlock Origin 在 2016 的時候 porting 到 Safari 上,但在 2018 後就沒有再更新了,維護者在「Explanation of the state of uBlock Origin (and other blockers) for Safari #158」這邊說明了目前的情況。

主要就是蘋果要廢掉本來的 Extension API,而替代的框架裡沒有對應的 content filtering 能力,所以在新的框架內無法實做 uBlock Origin 的功能...

維護者的建議是換瀏覽器,但其實可以選擇的瀏覽器愈來愈少了 (因為 Google Chrome 這邊也在搞),所以維護者的建議就是換成 Firefox

另外我自己會建議用看看 Brave,因為 Brave 已經決定,如果 Google Chrome 修改 webRequest 的阻擋能力 (也就是這次的 Manifest V3),他們會繼續維持本來的相容性,所以可以預期 uBlock Origin 應該還是會動 (參考之前寫的「Brave 試用」這篇)。

Automattic (WordPress.com 的公司) 買下 Tumblr

Verizon 一直在把 Yahoo! 手上比較有價值的資產賣掉,總算是輪到 Tumblr 了,這次是賣給了 Automattic,也就是 WordPress.com 營運的公司。

Verizon 已經發新聞稿了:「Verizon Media announces sale of Tumblr to Automattic」,Tumblr 的 staff blog 上也發表了:「Hello Tumblr ? Today, Tumblr’s owner, Verizon...」,但 Automattic 這邊還沒看到:「Features, news, and more: See what’s been going on in Automattic’s world.」。

金額不確定多少,但感覺應該算是好事?不知道之前的 porn content 會不會回流...

Mercury Web Parser 開源

看到「Mercury Goes Open Source!」這篇,Postlight 的團隊開源了 Mercury Web Parser,程式碼在 GitHub 上的 postlight/mercury-parser 可以取得。

這個版本是用 Node.js 寫的,可以從範例看出用法以及結果:

import Mercury from '@postlight/mercury-parser';
Mercury.parse(url).then(result => console.log(result););
{
  "title": "Thunder (mascot)",
  "content": "<div><div><p>This is the content of the page!</div></div>",
  "author": "Wikipedia Contributors",
  "date_published": "2016-09-16T20:56:00.000Z",
  "lead_image_url": null,
  "dek": null,
  "next_page_url": null,
  "url": "https://en.wikipedia.org/wiki/Thunder_(mascot)",
  "domain": "en.wikipedia.org",
  "excerpt": "Thunder Thunder is the stage name for the horse who is the official live animal mascot for the Denver Broncos",
  "word_count": 4677,
  "direction": "ltr",
  "total_pages": 1,
  "rendered_pages": 1
}

先前其他的軟體與服務可以參考「Evaluating Text Extraction Algorithms」這篇的整理與比較,不過這篇連原網站都不見了... 只能從 Internet Archive 上翻出來。

這個主題有不少團隊都做過 (給一個 html 網頁,抓出實際的內容塊落),但也死了不少團隊... 比較有印象的是 Readability,在 2016 年收掉了:「The Readability bookmarking service will shut down on September 30, 2016.」。

要撈資料可以拿來用...

CloudFront 在東京開到第八個點了...

看到 Amazon CloudFront 宣佈在東京開到第八個點了:「Amazon CloudFront launches eighth Edge location in Tokyo, Japan」。

Amazon CloudFront announces the addition of an eighth Edge location in Tokyo, Japan. The addition of another Edge location continues to expand CloudFront's capacity in the region, allowing us to serve increased volumes of web traffic.

這個成長速度有點驚人,一月才加了兩個,現在又要再加一個... 不過大阪還是維持一個。

Microsoft 啟用自己的 CDN 了...

在朋友的 tweet 裡看到微軟啟用自己的 Azure CDN 了,先前應該是提供 AkamaiEdgeCast 的服務:「Announcing Microsoft's own Content Delivery Network」。

看圖似乎是有台灣的點,不過我找不到可以測試 traceroute 的 endpoint,頁面上用的圖還是 EdgeCast 的啊 XDDD

;; ANSWER SECTION:
azurecomcdn.azureedge.net. 1604 IN      CNAME   azurecomcdn.ec.azureedge.net.
azurecomcdn.ec.azureedge.net. 3404 IN   CNAME   cs9.wpc.v0cdn.net.
cs9.wpc.v0cdn.net.      3404    IN      A       117.18.232.200

然後公測期間優惠價 50%:

Azure Content Delivery Network Standard from Verizon (S1) and Akamai (S2) and Microsoft (S3)*
*S3 is currently in public preview. CDN rates will be 50% of the stated price during this period.

Seam Carving (接縫裁剪)

看到有人實做 Seam Carving (接縫裁剪) 了,用 Golang 寫的,放在 GitHubesimov/caire 這邊,副標題「Content aware image resize library」。實做了「Seam Carving for Content-Aware Image Resizing」這篇論文。

Seam Carving 指的是知道內容的 resize,像是把上面這張變成下面這張:

或是變大:

馬上可以想到的應用是需要保留資訊內容,但又想要大量提供資訊的地方,像是 Nuzzle 的縮圖 (或是以前的 Zite),或是網路新聞媒體的首頁所用的縮圖。不知道還有沒有其他地方可以用...