關於 GitLab 的 SQL 設計

今天「My notes on Gitlab's Postgres schema design (2022) (shekhargulati.com)」這篇上 Hacker News 首頁 (看起來因為是在 pool 的關係,在第一頁卡很久...),文章「My Notes on GitLab Postgres Schema Design」是作者在 2022 年七月的時候分析了 GitLabstructure.sql 的資料庫設計整理出來的心得 & 感想,裡面有不少東西,不過這邊想補充個背景知識 (姿勢?):

RDBMS 在系統架構裡面,相較於其他的元件,是個很難 scale out 的東西 (i.e. 加更多機器得到更多效能),所以遇過 scalability 問題的架構師,會很習慣避開在 RDBMS 上面跑各種功能,有其他方式可以做的就拆出去用容易 scale out 的工具來做,非不得已才上 RDBMS。

而就算要塞進 RDBMS 裡的資料,能省的還是要省,畢竟宣稱自動幫你處理資料庫 scale out 的技術 (像是 CockroachDBTiDB) 其實沒想像中萬能,還是需要開發者改寫以前大惡搞的 SQL query (一個 terminal 列不完那種)。

而你心裡也有底,如果 scale out 不是條好的路,那麼只好 scale up (i.e. 加大機器的 CPU & RAM),而 scale up 總是有極限,真的遇到自己被迫要處理 sharding 的時候,DBOps/DBA 與 Dev 的臉都很臭... (一堆 JOIN 要改成拉回 application 端自己湊,或是有 ProxySQL 這種東西幫你處理,但是發現 ProxySQL 去後面資料庫拉太多資料幫你組反而很慢 !@#$%)

但另外一方面,現在已經不是 2005 年 64GB RAM 的伺服器是個天價的年代... 硬體的成長已經長到在 AWS 雲端上面可以租到給 SAP 用的 24TB RAM 的機器 (u-24tb1.112xlarge),而地端找個 server 也都有 15TB RAM (POWEREDGE R940),所以很容易把所有資料都塞到記憶體裡面搞,加上 NVMe 的讀寫速度比以前 HDD disk 快多了。

記得這兩件都是現實,然後再回來看文章內容與其他的討論,用不同的現實就會有不同的想法出現。

GitLab 的設計有他當時的限制以及想法,這些是外面的人看不到的,也就不好批評對錯。

Starlink 的雷射傳輸細節

在「Starlink's laser system is beaming 42 petabytes of data per day (pcmag.com)」這邊看到 Starlink 的雷射資訊,原文是「Starlink's Laser System Is Beaming 42 Million GB of Data Per Day」。

主要是這兩張圖的資訊:

文字與圖片有很多不一致的地方,所以先抓個概念就好... 目前看起來是個「可商用」的階段了,而上面提到的 5400km 光是真空單向傳輸就要 18ms latency,如果擺到地球上的話,台灣到澳洲中間差不多?到關島、北海道或是新加坡都差不多在 3000km 左右。

想像中,海洋上面的 client 應該會透過這個方式 relay 到附近的陸地...

Slack 自己幹的 Cron System

在 HN 上看到「Executing Cron Scripts Reliably at Scale (slack.engineering)」,發現是去年九月的文章:「Executing Cron Scripts Reliably At Scale」(話說 Slack 的 engineering blog 可讀性變差好多,不過這又是另外一回事了...)。

夠大的組織的 cron job system 都會自己幹一套出來用,因為檯面上的都不好用 XD

Slack 的搞法是組合三個內部系統:

  • 一個 container-based 管理實際執行資源的系統,基於 Bedrock,而 Bedrock 則是基於 k8s 上的系統。
  • 一個 job queue 子系統,後面是 Kafka + Redis 組成的。
  • 一組在 Vitess 上的表格,所以後面是 MySQL

這樣的系統也注定這是 Slack-only 的系統了,看一下知道用什麼就好了...

2014/2015 年的 Smart Home & IoT 裝置?

昨天的「What's that touchscreen in my room? (laplab.me)」這篇頗有趣的,原文「What's that touchscreen in my room?」是在租屋處看到牆上有一片平板,研究這到底是什麼的文章:

作者在一包文件裡找到手冊以後 (應該是屋主當初直接拿給他的一包文件?),知道這是 NetThings 的設備 (看起來已經是歷史了,這邊留個 LinkedIn 上的連結...):

然後連了半天發現連不上,到公共區域發現他還有一台主機要打開,但因為沒有保險絲,所以沒通電:

在裝了保險絲開機之後就是黑這台機器的過程...?

在各種嘗試中得知,port scan 過程發現有 tcf-agent 可以直接對檔案系統操作,首先是試著撈出 root 加密過的密碼來 john 但不順利,後來是發現可以修改 /etc/shadowroot 密碼清空,並且修改 /etc/ssh/sshd_config,就順利連上了這台機器...

這是一台 ARM9 的機器,有大約 118MB 的記憶體,而且 CPU 可以直接跑 Java bytecode (Jazelle)。

另外這台平板是 Android 5 的系統,透過 webview 從主機上拉狀態出來。

然後裡面有不少 (以現在來看) 古董:

Along with the Pulse app, there is the second part of the application. A Node.js app reads CSV files populated with energy usage data and displays them to the user in the web UI. It uses Node.js 0.10.26, Express.js 4.13.3 and Socket.io 1.3.6.

是個 2014/2015 年左右的產品...

用 inxi 列出系統資訊,在回報問題時提供環境

在「GPU Survival Toolkit for the AI age: The bare minimum every developer must know」這篇看到的工具,雖然裡面是講 GPU 相關的事情,但看到這段:

inxi -G

This command provides information about the graphics subsystem, including details about the GPU and the display.

inxi 這個工具是用 Perl 寫的,在 manpage 的說明是:

inxi - Command line system information script for console and IRC

提供一些資訊給使用者,方便使用者在問問題時順便複製貼上到 IRC 或是論壇。

看了一下系統的 dependency,我的桌機是因為 xubuntu-desktop 這個套件相依裝進去的,這是 XFCE 桌面環境的套件。

Ubuntu 的預設環境沒有包這個套件進去,會需要額外安裝。

NIST P-curve 的 Seed Bounty Program

Filippo Valsorda 發起了 seed bounty program,針對 NIST P-curve 裡 seed 的部分尋找 SHA-1 的 pre-image:「Announcing the $12k NIST Elliptic Curves Seeds Bounty」。

先講一下這次的 bounty program,希望找出下面這些 SHA-1 的 pre-image input (也就是找出 input,使得 SHA1(input) 會等於下面的東西):

3045AE6FC8422F64ED579528D38120EAE12196D5
BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
C49D360886E704936A6678E1139D26B7819F7E90
A335926AA319A27A1D00896A6773A4827ACDAC73
D09E8800291CB85396CC6717393284AAA0DA64BA

金額是 US$12288,但是要五個都找到。

話說在寫這篇時,查資料發現 P-384 有獨立條目,但 P-256P-521 都是重導指到 Elliptic-curve cryptography 這個條目,但 P-384 看起來也沒什麼特別的,不知道當初編輯的人是怎麼想的...

回來原來的問題,要從一些背景開始講,橢圓曲線的表示法有多種,像是:

y^2 = x^3 + ax + b (Weierstrass form) y^2 = x^3 + ax^2 + bx (Montgomery form)

而這些常數 ab 的選擇會影響到計算速度,所以通常會挑過,但畢竟是密碼學用的東西,挑的過程如果都不解釋的話,會讓人懷疑是不是挑一個有後門的數字,尤其 NIST (NSA) 後來被證實在 Dual_EC_DRBG 裡面埋後門的醜聞,大家對於 NIST 選擇或是設計的密碼系統都有很多疑慮。

舉個例子來說,2005 年時 djb 發明了 Curve25519 (論文「Curve25519: new Diffie-Hellman speed records」則是記錄 2006),選擇的橢圓曲線是:

y^2 = x^3 + 486662x^2 + x

他就有提到這邊的 486662 是怎麼來的:他先在前一個段落說明,這邊數字如果挑的不好的話,會有哪些攻擊可以用,接下來把最小的三個值列出來,然後說明原因:

To protect against various attacks discussed in Section 3, I rejected choices of A whose curve and twist orders were not {4 · prime, 8 · prime}; here 4, 8 are minimal since p ∈ 1+4Z. The smallest positive choices for A are 358990, 464586, and 486662. I rejected A = 358990 because one of its primes is slightly smaller than 2^252, raising the question of how standards and implementations should handle the theoretical possibility of a user’s secret key matching the prime; discussing this question is more difficult than switching to another A. I rejected 464586 for the same reason. So I ended up with A = 486662.

而 P-192、P-224、P-256、P-384 與 P-521 的值都很怪,這是十六進位的值,在正式的文件或是正式的說明上都沒有解釋,屬於「magic number」:

3045AE6FC8422F64ED579528D38120EAE12196D5 # NIST P-192, ANSI prime192v1
BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5 # NIST P-224
C49D360886E704936A6678E1139D26B7819F7E90 # NIST P-256, ANSI prime256v1
A335926AA319A27A1D00896A6773A4827ACDAC73 # NIST P-384
D09E8800291CB85396CC6717393284AAA0DA64BA # NIST P-521

依照 Steve Weis 說,這些值當初是 Jerry Solinas 是隨便抓個字串,再用 SHA-1 生出來的:

Apparently, they were provided by the NSA, and generated by Jerry Solinas in 1997. He allegedly generated them by hashing, presumably with SHA-1, some English sentences that he later forgot.

這是 Steve Weis 的敘述,出自「How were the NIST ECDSA curve parameters generated?」:

[Jerry] told me that he used a seed that was something like:
SEED = SHA1("Jerry deserves a raise.")
After he did the work, his machine was replaced or upgraded, and the actual phrase that he used was lost. When the controversy first came up, Jerry tried every phrase that he could think of that was similar to this, but none matched.

如果可以證實當初的字串,那麼 NIST 在裡面埋後門的疑慮會再降低一些,這就是這次發起 bounty program 的原因。

Amazon S3 的新數字

Werner Vogels 寫了一篇在回憶 Amazon S3 的文章:「Building and operating a pretty big storage system called S3」,裡面有個是他這個層級比較容易取得公開權限的資料:

有標注「S3 by the numbers (as of publishing this post).」,所以是 2023 年七月現在的數字。

雖然很明顯的還是避開談總大小,但有提供目前的 S3 object 數量是 280 兆,以及 request 量是每秒 1 億次。

搭配之前公開過的數字 (出自維基百科上的「Amazon S3」條目),上次公佈是在 2021 年三月的時候宣布超過 100 兆,所以過了兩年的時間已經到 280 兆了:

Amazon Web Services introduced Amazon S3 in 2006. Amazon reported it stored more than 100 trillion objects as of March 2021, up from 10 billion objects in October 2007, 14 billion objects in January 2008, 29 billion objects in October 2008, 52 billion objects in March 2009, 64 billion objects in August 2009, 102 billion objects in March 2010, and 2 trillion objects in April 2013.

分散式系統的 clock

前幾天在 Hacker News 上看到「Clocks and Causality – Ordering Events in Distributed Systems (2022) (exhypothesi.com)」這篇,講分散式系統上 clock 的設計,作者也有跑出來在 Hacker News 上面跟大家聊一下 (帳號是 thoughtlede),原文在「Clocks and Causality - Ordering Events in Distributed Systems」這邊。

文章裡面主要講空間是 O(1)Lamport timestamp 與空間是 O(n)Vector clock (這邊的 n 相對於節點數量),以及這兩個對應的擴充版本:

作者會整理這些資料的原因是因為在研究 CRDT 的時候看到演算法中常常會需要處理分散式系統裡面事件的順序,所以花了一些時間整理常見的方式:

Author here. Pleasantly surprised to see the article here.

Some context behind the article. I studied CRDTs for a few months, and noticed that different CRDT designs use logical clocks in different and clever ways. And I haven't seen anyone narrate all those ways of use in one article. My attempt with this article was to dredge up those flavors of logical clocks into one article and give them names for future reference.

(To respond to a couple of other comments, I ignored atomic (and gps-based) clocks in this discussion, as indicated in my footnote 3).

我記得還有一個 Interval Tree Clocks 可以參考 (在「Interval Tree Clocks」這邊講的比較清楚),是針對節點的動態增刪而改善的演算法,但不確定有什麼比較有名的系統有用。

大多數應該都是用 Vector clock,畢竟是在 2007 年的「Dynamo: Amazon’s Highly Available Key-value Store」被發揚光大,而且也算是還不錯的演算法?

在 CSS 裡面使用系統字型的選擇

一開始是看到「Show HN: Modern Font Stacks – New system font stack CSS for modern OSs (modernfontstacks.com)」這個,專案希望可以使用不用另外下載的字型 (系統內建字型),但這個網站本身不好用,留言區提到的一些其他網站好用多了...

首先是「CSS Font Stack: Web Safe and Web Font Family with HTML and CSS code.」這個,把 WindowsmacOS 上預設的字型都列出來,然後也列出對應的安裝比率。

而另外一個則是在 GitHub 上的專案「Modern Font Stacks」,把類似的字型放在一起。

看起來可以參考,比起只用 serif 或是 sans-serif 來說會多一些變化可以用。

GitHub 自己開發的搜尋引擎

前陣子 GitHub 發了一篇文章,說明自己開發搜尋引擎的心路歷程:「The technology behind GitHub’s new code search」。

看了一下其實就是自己幹了一套 search engine cluster,然後針對 code search 把一些功能放進去。

目前這套 search enginer 還是 beta 版本,全站兩億個 repository 只包括了 4500 萬 (大概 22% 左右),然後已經有 115TB 的程式碼了;另外也題到了先前導入 Elasticsearch 時的數字是 800 萬個 repository:

GitHub’s scale is truly a unique challenge. When we first deployed Elasticsearch, it took months to index all of the code on GitHub (about 8 million repositories at the time). Today, that number is north of 200 million, and that code isn’t static: it’s constantly changing and that’s quite challenging for search engines to handle. For the beta, you can currently search almost 45 million repositories, representing 115 TB of code and 15.5 billion documents.

目前是 32 台機器,沒有特別提到記憶體大小,也沒有提到 replication 之類的數字:

Code search runs on 64 core, 32 machine clusters.

然後各種 inverted index 與各種資料在壓縮後只有 25TB:

There are some big wins on the size of the index as well. Remember that we started with 115 TB of content that we want to search. Content deduplication and delta indexing brings that down to around 28 TB of unique content. And the index itself clocks in at just 25 TB, which includes not only all the indices (including the ngrams), but also a compressed copy of all unique content. This means our total index size including the content is roughly a quarter the size of the original data!

換算一下,就會發現現在已經是「暴力」可以解很多事情的年代了,而這已經是全世界最大的 code hosting。

以前隨便一個主題搞大一點就會撞到 Amdahl's law,現在輕鬆不少...