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

讓使用者可以自己選擇 Push notification service 的 UnifiedPush

前幾天 Hacker News Daily 上看到的,F-Droid 寫了一篇文章介紹可以讓使用者自己選擇 Push notification service 的 UnifiedPush:「UnifiedPush: A decentralized, open-source push notification protocol (f-droid.org)」。

一般在 Android 平台上是透過 Google 自家提供的 FCM 傳遞 push notification 訊息:

A modern Android smartphone relies on a lot of services, from app stores and calendars to messaging and push notifications. Most of them have open alternatives, but until now, the only option for push notifications was Google’s proprietary service, Firebase Cloud Messaging (FCM).

但這樣很明顯會遇到隱私問題 (i.e. Google 可以知道所有的 push notification),所以一直都有要怎麼解決的討論。

而看起來 UnifiedPush 給了一個方案:使用者在 Android 手機上安裝一隻程式 (ntfy),這隻程式可以連到使用者指定的伺服器接收 push notification (可以是自架或是用現有的服務),另外一方面,當然也會跟 app 說要把 push notification 送到哪邊。

另外也考慮到使用者如果極度在意電池的問題,還是可以 fallback 回去使用 Google 的 FCM,也就是不影響現有使用者的體驗。

這樣就可以做到還是單一連線 (降低電力使用),但是是分散式的架構,而且使用者有一定的控制權。

目前支援的 app 看起來不多,但可以以預期後續 F-Droid 上面的 app 應該會有不少 app 會支援:「Apps using UnifiedPush」。

因應 Manifest V3 而推出的 uBlock Minus (MV3)

前幾天在 Hacker News 上看到「“UBO Minus (MV3)” – An Experimental uBlock Origin Build for Manifest V3 (github.com/gorhill)」這個,裡面是 uBlock Origin 的作者 Raymond Hill 針對 Manifest V3 的半殘版,取名為 uBO Minus (MV3):「Add experimental mv3 version」。

在這個版本裡會有不少的功能失效,尤其是用的很多的 cosmetic filtering:

- No cosmetic filtering (##)
- No scriptlet injection (##+js)
- No redirect= filters
- No csp= filters
- No removeparam= filters

這個版本應該是打算要提供給 Manifest V2 被 Google 廢掉後還在用 Google 控制的瀏覽器的人,依照「Manifest V2 support timeline」這邊看起來是明年一月:

Google Cloud 宣佈明年關閉 IoT Core Services

Hacker News 上的「Google IoT Core will be discontinued on Aug. 16, 2023」這篇,大家在討論 Google Cloud 宣佈明年關閉 IoT Core Services 的事情,基本上討論的內容大概都想的到...

AWS 這邊的話,最近比較有印象的就是要淘汰 EC2 Classic (EC2-Classic 的狀態),但到現在還是在跑。

另外一個是把 Xen 架構 porting 到 Nitro 上 (AWS 將新的 Nitro 架構回過投來支援以前 Xen 的機種),讓原有的 Xen 應用可以繼續用。

久一點以前的 SimpleDB 到現在也還是活著,官方現在應該是主力在推 DynamoDB

兩種完全不同的作法...

從 Android (AOSP) fork 出來的 /e/

上個禮拜在 Hacker News 看到的「Review of /e/ – An Android Alternative For Mobile Phones」,在講 /e/ 這個從 AOSP 改出來的作業系統,主力在於「unGoogled」這件事情,避免任何資料傳回給 Google。Hacker News 上對應的討論在「Review of /e/ – Android-based alternative for mobile phones (thenewleafjournal.com)」這邊。

先看了一下運作方式,/e/ 的後面是 e Foundation,以非營利組織的方式經營。

LineageOS 的經驗來看,看起來有蠻多東西預先包好了,像是預掛了 microG 來模擬 Google Play Services 的服務與 API,這樣可以讓一些需要 Google Play Services 的服務可以跑 (但可以預期不會是完全相容)。

另外也有一些商業合作,所以市場上可以買到出廠就已經安裝 /e/ 的手機,讓一般使用者更容易上手。另外一條可以預期的路是自己刷 /e/,從「Smartphone Selector」這邊可以看到 /e/ 支援很多型號。

文章裡另外題到了其他的 AOSP fork,走不同的路線:

In addition to LineageOS, there are two forks focused primarily on security – GrapheneOS and CalyxOS. There is also Replicant, which appears to mostly support older devices at this time.

看起來弄個 Pixel 5a 或是舊一點的 Pixel 4a 應該是個還可以的方向,Google 自家牌的手機通常都是這些 distribution 優先支援的機種...

Google 說要把 double quote 強制搜尋的功能加回來...

Hacker News Daily 上看到「We're improving search results when you use quotes (blog.google)」這則,才知道原來被拔掉了?(不過已經很久不是拿 Google Search 當主力了...)

原文在「How we're improving search results when you use quotes」這邊,裡面提到:

For example, if you did a search such as [“google search”], the snippet will show where that exact phrase appears:

[...]

In the past, we didn’t always do this because sometimes the quoted material appears in areas of a document that don’t lend themselves to creating helpful snippets.

在「Google for the exact phrase (and no, quotation marks don't help)」這邊可以看到 2020 的時候 double quote 就已經不是傳回精確的結果了。

不過應該不會回去用 Google Search 了,一方面是 Kagi 的表現還不錯,另外一方面是避免讓 Google 拿到更多資訊...

歐盟通過 Digital Markets Act 與 Digital Services Act

Hacker News Daily 上翻的時候看到的大消息,歐盟通過了 Digital Markets Act (DMA) 與 Digital Services Act (DSA):「EU Approves Landmark Legislation to Regulate Apple and Other Big Tech Firms」,這兩個法案會直接衝擊大企業壟斷的情況。

找了一下中文的資料,iThome 有報導:「歐洲議會通過《數位服務法》與《數位市場法》!傳訊服務必須互通,不得禁止使用者採用第三方App Store」。

其中 MacRumors 上的文章整理的蠻清楚的,DMA 包括了:

  • Allow users to install apps from third-party app stores and sideload directly from the internet.
  • Allow developers to offer third-party payment systems in apps and promote offers outside the gatekeeper's platforms.
  • Allow developers to integrate their apps and digital services directly with those belonging to a gatekeeper. This includes making messaging, voice-calling, and video-calling services interoperable with third-party services upon request.
  • Give developers access to any hardware feature, such as "near-field communication technology, secure elements and processors, authentication mechanisms, and the software used to control those technologies."
  • Ensure that all apps are uninstallable and give users the ability to unsubscribe from core platform services under similar conditions to subscription.
  • Give users the option to change the default voice assistant to a third-party option.
  • Share data and metrics with developers and competitors, including marketing and advertising performance data.
  • Set up an independent "compliance function" group to monitor its compliance with EU legislation with an independent senior manager and sufficient authority, resources, and access to management.
  • Inform the European Commission of their mergers and acquisitions.

可以看出來除了最後兩項是針對 EU 的監管機制外,其他的包括了安裝來自第三方的軟體、可以使用第三方的付款系統、可以整合系統服務、可以整合硬體功能、可以使用第三方的語音工具、可以反安裝所有的 app 以及提供平台蒐集到的資料給開發者,都是針對現在 AppleApp StoreGoogle Play 所限制的條件。

另外 DMA 也禁止了這些行為:

  • Pre-install certain software applications and require users to use any important default software services such as web browsers.
  • Require app developers to use certain services or frameworks, including browser engines, payment systems, and identity providers, to be listed in app stores.
  • Give their own products, apps, or services preferential treatment or rank them higher than those of others.
  • Reuse private data collected during a service for the purposes of another service.
  • Establish unfair conditions for business users.

而 DSA 的部份則是針對網路上的非法內容處理:

The Digital Services Act (DSA), which requires platforms to do more to police the internet for illegal content, has also been approved by the European Parliament.

其中 DMA 的生效日看起來會在 2023 年年中生效?應該是 六個月加上六個月...

Once formally adopted, the Act, which takes the legal form of a Regulation, will enter into force 20 days after publication in the EU Official Journal and will apply six months later. The designated gatekeepers will have a maximum of six months after the designation decision by the Commission to ensure compliance with the obligations laid down in the Digital Markets Act.

而 DSA 至少要到 2024 年才有機會會實施:

Once adopted, the DSA will be directly applicable across the EU and will apply fifteen months or from 1 January 2024, whichever later, after entry into force.

歐盟的市場夠大,這個應該會帶來足夠大的衝擊...

搜尋引擎的替代方案清單

看到「A look at search engines with their own indexes」這篇在介紹各個搜尋引擎,作者設計了一套方法測試,另外在文章裡面也給了很多主觀的意見,算是很有參考價值的,可以試看看裡面提出來的建議。

另外在 Hacker News 上也有討論可以參考:「A look at search engines with their own indexes (2021) (seirdy.one)」。

在文章開頭的「General indexing search-engines」這個章節,先列出三大搜尋引擎 GBY (GoogleBingYandex),以及使用這三家當作後端資料庫的搜尋引擎,可以看到到處都是 Bing 的影子。

接著作者推薦 Mojeek 這個作為 GBY 的替代方案:

Mojeek: Seems privacy-oriented with a large index containing billions of pages. Quality isn’t at GBY’s level, but it’s not bad either. If I had to use Mojeek as my default general search engine, I’d live. Partially powers eTools.ch. At this moment, I think that Mojeek is the best alternative to GBY for general search.

在「Smaller indexes or less relevant results」這邊也有一些方案,像是這個章節第一個提到的 Right Dao,作者就給他了不錯的評價:

Right Dao: very fast, good results. Passes the tests fairly well. It plans on including query-based ads if/when its user base grows.

接下來的「Smaller indexes, hit-and-miss」與「Unusable engines, irrelevant results」也可以翻一下,看看作者怎麼批評 XD

然後是後面的「Semi-independent indexes」就出現了最近幾個比較有名的,像是 Brave Search 與目前我在用的 Kagi

整理的相當不錯...

AWS DataSync 支援 GCP 與 Azure 上的 Storage 上的資料了

AWS DataSync 宣佈支援 GCP 與 Azure 上的 Storage 了:「New for AWS DataSync – Move Data Between AWS and Other Public Locations」,比較特別的是,文章的 URL 有提到這兩家的產品,但在標題上反而就沒提到...

這測的重點就是支援 Google CloudMicrosoft Azure 的 object storage 產品:

Today, we added to DataSync the capability to migrate data between AWS Storage services and either Google Cloud Storage or Microsoft Azure Files.

之前大家都是自己開機器手動搬,現在可以直接付錢 (依照 GB 計費) 用服務搬了,不過要注意網路頻寬的流出部份還是有費用...

GCP 推出 AlloyDB,一套相容 PostgreSQL 協定的資料庫服務

也是在清 RSS reader 的時候翻到的,看起來是在今年的 Google I/O 上發表的服務,AlloyDB:「AlloyDB for PostgreSQL under the hood: Intelligent, database-aware storage」,值得提的是這篇有中文版可以看:「適用於 PostgreSQL 的 AlloyDB 隆重登場:從此擺脫成本高昂的老舊資料庫」。

另外還有一篇比較偏 PR 的文章也可以看看:「Introducing AlloyDB for PostgreSQL: Free yourself from expensive, legacy databases」,這篇就比較針對的提到了與 AWS 的服務相比,但畢竟是 PR 稿沒有明講 (出事會比較好打模糊戰),但我猜測是與 Aurora 對比:

AlloyDB was also two times faster for transactional workloads than Amazon’s comparable service.

宣稱在 OLTP 上快了兩倍 (原來的三倍?),但應該都是以 PostgreSQL 下去改,猜測可能是底層的 storage 與 replication 比較好?

AlloyDB 設計上是考慮了 HTAP (Hybrid transactional/analytical processing) 的使用,所以同時可以提供 OLAP 與 OLTP 的應用:

[...] This makes AlloyDB a great fit for business intelligence, reporting, and hybrid transactional and analytical workloads (HTAP).

直接在一個資料庫內處理 OLAP 與 OLTP 這點的確會讓 AlloyDB 比 AWS 目前能提供的方案方便不少 (然後想一下 BigQuery 團隊...)。

目前在 AWS 對應的方案應該是透過 Redshift 來解決,另外一個方案是透過 Athena 來跑。

最後來看價錢,如果效能變成兩倍但價錢也是兩倍的話,就代表在價格上沒優勢。

先看機器的部份,如果是拿 Aurora 這邊 Intel-based 的 db.r5.24xlarge (96 vCPU + 768 GB RAM) 來算的話是 US$13.92/hr,而如果換算到 AlloyDB 的話是 US$14.94528/hr,相除是 0.9314,大約 7% 的差距,可以算是同一個級距。

如果 Aurora 這邊是拿 ARM-based 的 db.r6g.16xlarge (64 vCPU + 512 GB RAM) 來算的話是 US$8.306/hr,換算到 AlloyDB 的話是 US$9.96352/hr,相除是 0.8336,這邊就差超過 16% 了...

(這邊剛好回顧一下 "Amazon’s comparable service" 這段,不確定他是跟 Intel-based 比還是跟 ARM-based 比,畢竟 ARM 除了比較便宜外,還有效能的提昇)

但最大的差異應該是在 storage 相關的部份。其中 Aurora 這邊的空間與 I/O 是分開收費的,以 us-east-1 來說,storage 是 US$0.10/GB/mo,而 I/O 是 US$0.20/million-requests,在 AlloyDB 這邊來說,Regional cluster storage 是 US$0.0004109/GB/hr (us-east4),變成是 US$0.295848/GB/mo,兩邊相比後可以算出來對等的計價會是 AWS 的 storage 加上 AWS 給你 1.47M 的 I/O (per GB)。

這樣算起來把資料丟 S3 跑 Athena 可能不會比較貴... (當然效能是另外的主題了)

光就檯面上的資料來看,看起來是個不錯的東西,等後續有人跳進去用看看感想...