Redis 的眾多 fork

從「Redis 改變授權,變成非開源軟體」差不多過去一個禮拜了,瞬間冒出一卡車 Redis fork:「The race to replace Redis」。

文章裡提到的第一個是 Valkey,在 Redis 宣佈改變授權後幾天 fork 出來的。

第二個則是 KeyDB,是很久前就 fork 出來實作 multi-threading 的公司,後來公司被 Snap 買走後 open source,但因為 fork 的很早,後續 Redis 增加的功能就沒有跟上了...

第三個則是 Redict,這是 SourceHut 這邊的 fork 版本。

第四個不算是 fork,是微軟前幾天公開的 Garnet,用 C# 寫的,也因為不是 fork,相容性當然比不上前面幾個。

另外一個文章帶出來的重要資訊,是目前 Redis 的 contributor 分佈,可以看到其實 Redis 本家不算多,這樣 Redis 決定硬幹 BSL + SSPL 的決定就頗值得玩味了:

可以看看 Redis 接下來會不會有什麼重量級的功能要推出?

Proxmox 的 VMware 轉移方案

Hacker News 上看到「Proxmox VE: Import Wizard for Migrating VMware ESXi VMs (proxmox.com)」這篇,原文在「New Import Wizard Available for Migrating VMware ESXi Based Virtual Machines」這邊。

算是有比較簡單的方式 (在這邊是提供 wizard) 可以把現有跑在 VMware 上面的 VM 轉出來,就不用自己在 command line 下 export (dump) & convert & import (restore),光是把 storage 轉過去就弄半天,這對於不熟悉 CLI & script 的人方便不少。

話說二月時傳出 Broadcom 打算把買來的 VMware 的 C 端產品拆開來賣:「VMware's end-user compute unit reportedly headed to private equity firm KKR」,後續好像沒有看到新消息?不過 C 端目前的領頭者應該還是 VirtualBox?這樣看起來賣掉也不算太意外就是了...

AWS Lambda 的 cache 架構

Lobsters 上看到的老文章:「[Cache Architecture for] Container Loading in AWS Lambda」,原文從 url 看起來是去年五月發表的資訊了:「Container Loading in AWS Lambda」。

主要是在講 container 怎麼 load 才會儘快執行,首先是提到了大家常用的 layer cache,在 AWS Lambda 上則是改用了 block level cache:

Most of the existing systems do this at the layer or file level, but we chose to do it at the block level.

然後每一塊 512KB:

We unpack a snapshot (deterministically, which turns out to be tricky) into a single flat filesystem, then break that filesystem up into 512KiB chunks.

接著是提到 lazy load 的方式:「Slacker: Fast Distribution with Lazy Docker Containers」:

Our analysis shows that pulling packages accounts for 76% of container start time, but only 6.4% of that data is read.

Slacker speeds up the median container development cycle by 20x and deployment cycle by 5x.

而這個技巧也被用在 AWS Lambda 上,而且是透過 FUSE 實作:

In Lambda, we did this by taking advantage of the layer of abstraction that Firecracker provides us. Linux has a useful feature called FUSE provides an interface that allows writing filesystems in userspace (instead of kernel space, which is harder to work in).

另外一個 AWS Lambda 有實作的是 tiered caching,分成三層,包括了 worker 的 local cache (L1)、同一個 AZ 上的 cache (L2) 以及 S3 上的資料 (L3):

Despite our local on-worker (L1) cache being several orders of magnitude smaller than the AZ-level cache (L2) and that being much smaller than the full data set in S3 (L3), we still get 67% of chunks from the local cache, 32% from the AZ level, and less than 0.1% from S3.

也因為 L3 cache 是 S3 的關係,他們在 L1 與 L2 上就不用擔心 durability 的問題 (反正不見了就往後面找):

The whole set of chunks are stored in S3, meaning the cache doesn’t need to provide durability, just low latency.

但還是用了 Erasure code,儘量維持每個 cache tier 在自己 tier 裡面就可以找到資料的機率,這樣可以盡量降低 peak latency (於是造成 99.9%/99.95%/99.99% 的 SLO 不好看?):

Think about what happens in a classic consistent hashed cache with 20 nodes when a node failure happens. Five percent of the data is lost. The hit rate drops to a maximum of 95%, which is a more than 5x increase in misses given that our normal hit rate is over 99%. At large scale machines fail all the time, and we don’t want big changes in behavior when that happens.

So we use a technique called erasure coding to completely avoid the impact. In erasure coding, we break each chunk up into M parts in a way that it can be recreated from any k. As long as M - k >= 1 we can survive the failure of any node with zero hit rate impact (because the other k nodes will pick up the slack).

大概是本來比較簡單的三層架構在 benchmark 後發現無法達成對應的 SLO,所以就「補上」erasure code 拉高 SLO,從這邊就可以感覺到老闆的要求對於架構設計上的影響...

話說難得看到一些細節被丟出來...

當年 Facebook 透過 VPN 記錄使用者活動細節的目的

2019 年年初的時候 TechCrunch 爆出 Facebook 透過付錢給使用者,透過 VPN (以及安裝 Root CA) 記錄使用者的行為:「Facebook 花錢向使用者購買他們的行為記錄」,最近揭露的文件透漏了當年的目的:「Facebook snooped on users’ Snapchat traffic in secret project, documents reveal」。

TC 這邊的文章裡面沒看到信件,另外找了其他報導:「Project Ghostbusters: Facebook Accused of Using Your Phone to Wiretap Snapchat」,裡面有兩份資料是信件往來的部分:「Document 735」、「Document 736」。

裡面可以看到想要取得 SnapchatYouTubeAmazon 這些使用行為:

The goal of Facebook’s SSL bump technology was the company’s acquisition, decryption, transfer, and use in competitive decisionmaking of private, encrypted in-app analytics from the Snapchat, YouTube, and Amazon apps, which were supposed to be transmitted over a secure connection between those respective apps and secure servers (sc-analytics.appspot.com for Snapchat, s.youtube.com and youtubei.googleapis.com for YouTube, and *.amazon.com for Amazon). Id.

然後信裡還有提到是用 Squid 實作的:

Today we are using the Onavo vpn-proxy stack to deploy squid with ssl bump the stack runs in edge on our own hosts (onavopp and onavolb) with a really old version of squid (3.1).

這次的訴訟裡提到了 18 U.S. Code § 2511 - Interception and disclosure of wire, oral, or electronic communications prohibited,看起來會是聯邦層級的刑事案件...

那是個還不流行 certificate pinning 的年代...?

Brendan Gregg 推薦平常在 Linux 上先裝好的工具

Brendan Gregg 推薦了一整包內建的工具 (透過系統的 apt repository 就能裝),平常先準備好,出問題的時候可以直接拿出來用:「Linux Crisis Tools」。

作者有提到表上列出來的工具算是基本盤,有特殊硬體的情況 (像是 GPU) 需要再加裝其他的套件:

This list is a minimum. Some servers have accelerators and you'll want their analysis tools installed as well: e.g., on Intel GPU servers, the intel-gpu-tools package; on NVIDIA, nvidia-smi. Debugging tools, like gdb(1), can also be pre-installed for immediate use in a crisis.

這邊是把表格有提到的都放進去,另外包括了上面提到的 GDB

sudo apt install -y bpfcc-tools bpftrace cpuid ethtool gdb iproute2 linux-tools-common msr-tools nicstat numactl procps sysstat tcpdump tiptop trace-cmd util-linux; sudo apt clean

裝了以後可以順便拿這張表格練練手,把不熟悉的工具開 backlog 找機會練手,熟悉一下這些工具的常用用法,這樣遇到狀況的時候可以直接用...

Threads 開放更多使用者進入 Fediverse

Meta 宣佈了讓更多 Threads 使用者進入 Fediverse:「Threads has entered the fediverse」。

目前是 beta 功能,然後有些限制條件:

Threads has entered the fediverse! As part of our beta experience, now available in a few countries, Threads users aged 18+ with public profiles can now choose to share their Threads posts to other ActivityPub-compliant servers.

直接丟 Threads 的 url 找 (像是 https://www.threads.net/@zuck 這樣) 在 Mastodon 上沒辦法找到,需要丟 @zuck@threads.net 這樣的 identifier 加。

另外文章裡面有提到支援了一些延伸的標準,像是 FEP-e232: Object Links 以及 _misskey_quote,這些「表態」應該也會對社群有重大影響,畢竟 Threads 就算是新加入 Federvise 的成員,但還是太大...

查詢 GitHub 上面 repository 的公開記錄

起因應該是「Claim: Private GitHub repos included in AI dataset (lurk.org)」這邊的討論,原文是 @emenel@post.lurk.orghttps://post.lurk.org/@emenel/112111014479288871 這邊宣稱他在 GitHub 的 private repository 被當作 training data 蒐集走使用。

而 GitHub 有公開全站的 public event data,所以 Simon Willison 就拿這份資料直接組了一個工具出來用:「GitHub Public repo history」。

這樣可以直接 auditing 對應的說法,不過看了一下 GitHub 上的帳號 emenel (上面連結是到同一個站,應該是同一個人),目前看起來已經把所有 repository 都刪掉了...

Redis 改變授權,變成非開源軟體

Redis 宣佈拿掉開源授權:「Redis Adopts Dual Source-Available Licensing」,對應的 git commit 在「Change license from BSD-3 to dual RSALv2+SSPLv1 (#13157)」這邊可以看到。

Starting with Redis 7.4, Redis will be dual-licensed under the Redis Source Available License (RSALv2) and Server Side Public License (SSPLv1).

算是今天蠻熱的新聞之一,不過算是在預期之內的變化,因為 Redis 在 2018 年就把很多他們自己開發的 proprietary component 變成 SSPL,現在主體也變其實不算太意外,後續就是看社群的 fork 凝聚的力量會比較大,還是 Redis 公司方的力量比較大... 尤其在 Redis 已經實作了許多 data structure 後,Redis 公司想要套現這件事情是否還有機會?

不過比較特別的反倒是微軟... 微軟早了一兩天發佈了 Redis 相容的實作 Garnet

Garnet is a remote cache-store from Microsoft Research that offers strong performance (throughput and latency), scalability, storage, recovery, cluster sharding, key migration, and replication features. Garnet can work with existing Redis clients.

會是巧合嗎?這時間點其實真的很微妙...

Google 的 HyperLogLog++

算是接續昨天寫的「Redis 對 HyperLogLog 省空間的實作」,在 RedisHyperLogLog 實作有提到 Google 在 2013 年的論文「HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm」,裡面提出了 HyperLogLog++ (HLL++)。

論文中 Google 提出來的改進主要有三個,第一個是用了 64-bit hash function:

5.1 Using a 64 Bit Hash Function

原因也有提到,當需要處理超過十億筆資料時,32-bit hash 的 4B 上限就有點不太夠用:

To fulfill the requirement of being able to estimate multisets of cardinalities beyond 1 billion, we use a 64 bit hash function.

這點也簡化了原始論文中當 cardinality 接近 232 時的 count 估算修正,因為實務上不太可能遇到 264 上限?

It would be possible to introduce a similar correction if the cardinality
approaches 264, but it seems unlikely that such cardinalities are encountered in practice.

第二個是改善 cardinality 比較低時的 count 估算公式:

5.2 Estimating Small Cardinalities

第三個則是提出了 sparse representation 的概念,在 cardinality 比較低的時候不需要直接用完整的 HLL 資料結構儲存:

5.3 Sparse Representation

另外也是一路往回讀的關係,查資料才了解 (ε, δ)-model 的用法,在「A Quick Introduction to Data Stream Algorithmics」這邊投影片的 Page 17 可以看到指的是,有多少正確性 (randomized) 是給出 ε 內的誤差 (approximation),像是 Page 18 的範例:

Example: Actual answer is within 5 ± 1 with prob ≥ 0.9

Redis 對 HyperLogLog 省空間的實作

HyperLogLog (HLL) 是用統計方式解決 Count-distinct problem 的資料結構以及演算法,不要求完全正確,而是大概的數量。

演算法其實沒有很難懂,在 2007 年的原始論文「HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm」裡面可以讀到演算法是長這樣:

可以看到一開始要決定好 b 的值 (於是就會有 2b 個 register),以及單個 register M[j] 的大小,所以是一開始就會決定好固定大小,無論有多少元素都會先吃掉這麼多空間。

但在 Redis 的文件「HyperLogLog」裡面則是提到很少元素的時候會低於 12KB:

The magic of this algorithm is that you no longer need to use an amount of memory proportional to the number of items counted, and instead can use a constant amount of memory; 12k bytes in the worst case, or a lot less if your HyperLogLog (We'll just call them HLL from now) has seen very few elements.

網路上搜了一下沒看到怎麼做到的,不過直接翻 Redis 的程式碼 hyperloglog.c 可以看到答案。

在檔案開頭的註解可以看到有 16384 個 register (對應到論文裡面的 b = 14,因為 214 = 16384),單個 register 的大小則是 6 bit (對應到論文裡面的 M[j]),相乘後是 12K bytes,剛好符合文件上的說明:

The use of 16384 6-bit registers for a great level of accuracy, using a total of 12k per key.

在「Dense representation」這邊也說明了每個 register 都是 6 bit 的存放方式,到這邊都與 HLL 論文提到的實作一樣。

省空間的方式是在「Sparse representation」這邊做到的,在大多數的 register 都沒有被設定的情況下,用這種方式可以省下大量的空間,而缺點是當元素「有點多」的時候會有比較高的 CPU time:

In the example the sparse representation used just 7 bytes instead of 12k in order to represent the HLL registers. In general for low cardinality there is a big win in terms of space efficiency, traded with CPU time since the sparse representation is slower to access.

依照註解上面的數字,看起來在 10000 個元素以下有機會低於 12KB,然後夠大的時候從 sparse 轉到 dense 上。

本來以為是什麼其他論文可以調整 b 參數 (enlarge),結果是個比較像是 hack 的方式搞定,但的確是蠻有效的...