Jepsen 回過頭來測試 MySQL 8.0

Hacker News 上看到作者自己貼的:「Jepsen: MySQL 8.0.34 (jepsen.io)」,原文在「MySQL 8.0.34」。

這次的測試不是 Oracle 付費讓 Jepsen 測,而是 Jepsen 這邊自己回頭測試 MySQL 8.0:

This work was performed independently without compensation, and conducted in accordance with the Jepsen ethics policy.

然後意外的流彈 (或是榴彈?) 打下了 AWSRDS,測出 RDS 在 cluster 模式下無法達到 SERIALIZABILITY

As a lagniappe, we show that AWS RDS MySQL clusters routinely violate Serializability.

然後 MySQL 本體則是找到 REPEATABLE-READ (預設 isolation level) 的問題:

Using our transaction consistency checker Elle, we show that MySQL Repeatable Read also violates internal consistency. Furthermore, it violates Monotonic Atomic View: transactions can observe some of another transaction’s effects, then later fail to observe other effects of that same transaction. We demonstrate violations of ANSI SQL’s requirements for Repeatable Read.

文章的前面一大段在寫歷史,解釋 ANSI 當初的 SQL 標準在定義 isolation level 時寫的很差,導致有很多不同的解讀,而且即使到了 SQL:2023 也還是沒有改善。

接著則是提到各家資料庫宣稱的 isolation level 跟 ANSI 定義的又不一樣的問題... (包括了無論怎麼解讀 ANSI 定義的情況)

不過中間有提到 1999 年 Atul Adya 試著正式定義 isolation level,把本來的四個 isolation level 用更嚴謹的方法重新給出相容的定義,這看起來是作者推薦在一般狀況下的替代方案:

In 1999, Atul Adya built on Berenson et al.’s critique and developed formal and implementation-independent definitions of various transaction isolation levels, including those in ANSI SQL. As he notes[.]

這四個會是 PL-1 對應到 READ UNCOMMITTEDPL-2 對應到 READ COMMITTEDPL-2.99 對應到 REPEATABLE-READ,以及 PL-3 對應到 SERIALIZABILITY;而其中 PL-2.99REPEATABLE-READ 在後面也會重複出現多次。

這次比較意外是在單機上找出問題來,至於 RDS 的部分反倒不是太意外,因為知道 AWS 在底層做了不少 hack,總是會有些 trade off 的?

SQLite 的 HC-tree 計畫

Hacker News 首頁上看到的新計畫:「HC-tree is an experimental high-concurrency database back end for SQLite (sqlite.org)」,SQLite 弄了一個實驗性質的 backend,叫做 HC-tree

The HC-tree (hctree) project is an attempt to develop a new database backend that improves upon regular SQLite as follows:

他列了幾個重點,其中「Improved concurrency」這點題到了可以讓多個 writer 同時寫入運作,這點算是 SQLite 很大的改變,目前希望可以做到在 single-threaded 情況下不輸現有的 SQLite:

An implicit goal is that hctree must be as fast or faster than stock SQLite for all single-threaded cases. There is no point in running dozens of concurrent writers if each of them is an order of magnitude slower than a single writer writing to a legacy database.

另外一方面,這算是 SQLite 真正要面對資料庫的 isolation 的問題了,比起現在的版本,同時間從只有一個 writer 的架構要變成支援多個 writer 的架構,所以在「Concurrency Model」這邊也帶了一下他預期可以做到的事情。

然後這邊可以看到在解釋裡面有提到 table 與 index 還是 b-tree,這樣應該可以猜測 hctree 的實做方式應該還是在市場上已經很成熟的 MVCC 那套方法:

If no other client has modified any b-tree (table or index) entry or range that the transaction being committed accessed by a range or stabbing query, then the transaction is valid.

另外一個蠻大的改變是「Support for replication」,現有的 SQLite 可以透過 extension 的方式加掛支援 replication 功能,現在則是讓底層的 backend 直接支援。

底層支援新的 backend 以後看起來會有不少變化可以玩,第一個想到的當然是變成 server 類型的服務,也就是像 MySQL 或是 PostgreSQL 這樣的方式,另外一種方向是包裝成 distributed database,讓應用程式可以簡單跨機器使用。

目前還不知道會往什麼方向走就是了,也有可能 SQLite 這邊只實做 backend,上面讓大家發揮...

又一份講基本 RDBMS 的文件

前幾天在 Hacker News Daily 看到「Things You Should Know About Databases」這篇文章,裡面講了很多基本的 RDBMS 的概念,另外 Hacker News 上對應的討論在「Things to know about databases (architecturenotes.co)」這邊。

裡面講了 B-treeB+tree 的差異:

不過這點在維基百科上也蠻清楚的文字說明:

A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.

另外裡面的 sorted 的那張圖:

這邊的說明不完全正確,在維基百科上的「Database index」這個條目裡面有提到 Non-clustered、Clustered 與 Cluster 三種架構,這邊圖片所表示的是 Non-clustered。在 InnoDB 裡面 data 是照 primary key 順序存放的 (沒有指定時會有一套邏輯選出哪個欄位當 PK,最後的情況是有 hidden key)。

再來就是提到 isolation,這邊也講的比較淺,只提到 ANSI 標準裡面的 SERIALIZABLEREPEATABLE READ (RR)、READ COMMITTED (RC) 與 READ UNCOMMITTED (RU) 四個,但沒提到像是 SNAPSHOT ISOLATION (SI) 這類的也很常見的標準。

說到 SI,在查 Snapshot isolation 的資料時整理了一下 PostgreSQL 的混亂情況。

在 PostgreSQL 9.0 以及更早前的版本,你指定 SERIALIZABLE 其實只有做到 Snapshot isolation 的等級,到了 9.1+ 後,SERIALIZABLE 才是真正做到 ANSI 定義的強度:

Snapshot isolation is called "serializable" mode in Oracle and PostgreSQL versions prior to 9.1, which may cause confusion with the "real serializability" mode.

另外 ANSI 定義的 isolation level 很難「用」 (但還是值得學起來,算是基本的東西),實際上的使用都是看各家資料庫對 isolation level 的保證程度來設計。

在 Docker 裡面跑 GUI 程式的點子

昨天的 Hacker News Daily 上看到「Running GUI apps within Docker containers」這篇文章,裡面想要把程式包到 Docker container 裡面,然後給了一些想法,另外在「Running GUI apps within Docker containers (trickster.dev)」這邊也有一些討論與想法可以看。

要注意的是,這邊主要是以 X11 類的環境為主 (所以應該還是 Linux 了),而文章是用 Firefox 當例子,不過主要應該還是會拿來跑其他的東西...

看起來 GUI 的部份主要就是先用 VNC + x11vnc 打通到 host 的 X11 環境,這邊會需要 xhost 開授權讓 container 內的程式可以控制 X11 的環境 (話說他範例裡面直接開 xhost + 也真讚)。

後面提到的 noVNC 則是把 VNC 轉到 HTML5 上面讓瀏覽器可以操作,就不是那麼感興趣。

另外在討論裡面也有人直接放大絕,把一堆權限放進去 container:

docker run -it --rm -e DISPLAY --net=host -v $XAUTHORITY:/root/.Xauthority -v /tmp/.X11-unix:/tmp/.X11-unix debian:11-slim

不過整體看起來算是提供了一些思路... 算是除了 Flatpak 外的一些方法。

PostgreSQL 的 SERIALIZABLE 的 bug

這是 Jespen 第一次測試 PostgreSQL,就順利找出可重製的 bug 了:「PostgreSQL 12.3」。

第一個 bug 是 REPEATABLE READ 下的問題,不過因為 SQL-92 定義不夠嚴謹的關係,其實算不算是 bug 有討論的空間,這點作者 Kyle Kingsbury 在文章裡也有提出來:

Whether PostgreSQL’s repeatable-read behavior is correct therefore depends on one’s interpretation of the standard. It is surprising that a database based on snapshot isolation would reject the strict interpretation chosen by the seminal paper on SI, but on reflection, the behavior is defensible.

另外一個就比較沒問題了,是 SERIALIZABLE 下的 bug,在 SQL-92 下對 SERIALIZABLE 的定義是這樣:

The execution of concurrent SQL-transactions at isolation level SERIALIZABLE is guaranteed to be serializable. A serializable execution is defined to be an execution of the operations of concurrently executing SQL-transactions that produces the same effect as some serial execution of those same SQL-transactions. A serial execution is one in which each SQL-transaction executes to completion before the next SQL-transaction begins.

也就是說,在 SERIALIZABLE 下一堆 transaction 的執行結果,你至少可以找到一組排序,使得這些 transaction 的結果是等價的。

而 Jespen 順利找出了一組 transaction (兩個 transaction),在 SERIALIZABLE 下都成功 (但不應該成功):

對於這兩個 transaction,不論是上面這條先執行,還是下面這條先執行,都不存在等價的結果,所以不符合 SERIALIZABLE 的要求。

另外也找到一個包括三個 transaction 的情況:

把 transaction 依照執行的結果把 dependency 拉出來,就可以看出來裡面產生了 loop,代表不可能在 SERIALIZABLE 下三個都成功。

在 Jespen 找到這些 bug 後,PostgreSQL 方面也找到軟體內產生 bug 的部份,並且修正了:「Avoid update conflict out serialization anomalies.」,看起來是在 PostgreSQL 引入 Serializable Snapshot Isolation (SSI) 的時候就有這個 bug,所以 9.1 以後的版本都有這個問題...

這次順利打下來,測得很漂亮啊... 翻了一下 Jespen 上的記錄,發現好像還沒測過 MySQL,應該會是後續的目標?

SQL-92 裡定義 Isolation Level 的背景

Twitter 上看到這則推,講到在 SQL-92 裡面 Isolation Level 定義的背景:

先是講了為什麼有 SERIALIZABLEREPEATABLE READREAD COMMITTED,然後講為什麼是用 anomalies 定義 (除了 SERIALIZABLE),也因此造成了定義不清楚而導致問題。

SQL-92 的 isolation 問題後來在其他文件裡面有被討論,像是 1995 年的「A Critique of ANSI SQL Isolation Levels」,以及 2000 年的論文「Generalized Isolation Level Definitions」,過了二十年後的現在,大家也都大概知道有哪些雷區了。

另外講到 Isolation Level,實務上會希望知道 database 與標準之間的差異,在「Hermitage: Testing transaction isolation levels」這篇可以看到各家 RDBMS 在不同設定下實際的 isolation level,包括了 open source 的 MySQLPostgreSQL 與商用常遇到的 OracleMicrosoft SQL Server

MySQL 的 REPEATABLE READ 因為 SQL-92 的定義不清楚,所以大概知道這邊本來就有爭議,比較意外的反倒是 Oracle 裡面的 SERIALIZABLE 實際上是 Snapshot Isolation,沒有辦法達到 SQL-92 裡面最高等級的 Isolation Level。

然後發現有些知識還是有漏,趁這個機會補...

MongoDB 的欺騙性廣告

Jepsen 最近丟出了一篇新的測試報告在測新版的 MongoDB 4.2.6,而且語氣看起來比以前兇很多,翻了一下前因後果,看起來起因是出自 Twitter 上的這則推,提到了 MongoDB 拿 Jepsen 宣傳的頁面:

然後 Jepsen 的官方帳號這邊也回應,覺得不可置信:

過兩個禮拜後 Jepsen 就丟出由老大 Kyle Kingsbury 發表的「Jepsen: MongoDB 4.2.6」,這篇測試 MongoDB 4.2.6 最新版的測試報告了。

在這篇報告裡面提到了很多不道德的行為,首先是在之前的測試發現有很多會掉資料的問題,但在 MongoDB 官方的宣傳文件「MongoDB and Jepsen」裡面則是完全沒提到,而且還宣稱有業界最強的資料一致性與正確性 (與 Jepsen 報告所提供的資料不符),所以 Jepsen 建議把這些問題列到這個頁面上,以避免使用者受到「誤解」:

Curiously, MongoDB omitted any mention of these findings in their MongoDB and Jepsen page. Instead, that page discusses only passing results, makes no mention of read or write concern, buries the actual report in a footnote, and goes on to claim:

MongoDB offers among the strongest data consistency, correctness, and safety guarantees of any database available today.

We encourage MongoDB to report Jepsen findings in context: while MongoDB did appear to offer per-document linearizability and causal consistency with the strongest settings, it also failed to offer those properties in most configurations. We think users might want to be aware that their database could lose data by default, but MongoDB’s summary of our work omits any mention of this behavior.

另外當然就是重測 MongoDB 4.2.6 版,沒時間看內容的人可以先瞄一下標題,裡面就已經點出不少東西了:

3 Results
3.1 Sometimes, Programs That Use Transactions… Are Worse
3.2 How ACID is Snapshot Isolation, Anyway
3.3 Indeterminate Errors
3.4 Duplicate Effects
3.5 Read Skew
3.6 Cyclic Information Flow
3.7 Read Your (Future) Writes

不過在最後面的 Discussion 比較清楚。

首先是批評 snapshot isolation 不是 ACID:

MongoDB 4.2.6 claims to offer “full ACID transactions” via snapshot isolation. However, the use of these transactions is complicated by weak defaults, confusing APIs, and undocumented error codes. Snapshot isolation is questionably compatible with the marketing phrase “full ACID”. Even at the highest levels of read and write concern, MongoDB’s transaction mechanism exhibited various anomalies which violate snapshot isolation.

Snapshot isolation is a reasonably strong consistency model, but claiming that snapshot isolation is “full ACID” is questionable.

而且即使把所有的資料安全性相關的設定都調到最高,也根本就做不到宣稱的 snapshot isolation:

Finally, even with the strongest levels of read and write concern for both single-document and transactional operations, we observed cases of G-single (read skew), G1c (cyclic information flow), duplicated writes, and a sort of retrocausal internal consistency anomaly: within a single transaction, reads could observe that transaction’s own writes from the future. MongoDB appears to allow transactions to both observe and not observe prior transactions, and to observe one another’s writes. A single write could be applied multiple times, suggesting an error in MongoDB’s automatic retry mechanism. All of these behaviors are incompatible with MongoDB’s claims of snapshot isolation.

過程中也發現就算設定了 snapshot 層級,MongoDB 在讀取時也不會遵守 snapshot isolation:

MongoDB’s default read and write concern for single-document operations remains local, which can observe uncommitted data, and w: 1, which can lose committed writes. Even when users select safer settings in their clients at the database or collection level, transactions ignore these settings and default again to local and w: 1. The snapshot read concern does not actually guarantee snapshot isolation, and must always be used in conjunction with write concern majority. This holds even for transactions which perform no writes.

然後所有的官方文件都沒有教 snapshot isolation 要怎麼設定,你必須在第三方的文件上才有機會找到:

Nor can users rely on examples to demonstrate snapshot isolated behavior. MongoDB’s transaction documentation and tutorial blog posts show only write-only transactions, using read concern local rather than snapshot. Other examples from MongoDB don’t specify a read concern or run entirely with defaults. Learn MongoDB The Hard Way uses read concern snapshot but write concern local, despite performing writes. Tutorials from DZone, Several Nines, Percona, The Code Barbarian, and Spring.io all claim that transactions are either ACID or offer snapshot isolation, but none set either read or write concern. There are some examples of MongoDB transactions which are snapshot isolated—for instance, from BMC, +N Consulting, and Maciej Zgadzaj, but most uses of MongoDB transactions we found ran—either intentionally or inadvertently—with settings that would (in general) allow write loss and aborted reads.

基本上就是一個老大被惹怒了,丟出來炸,而且看他的語氣還有很多東西沒測,打算要再炸一篇?

RDBMS 裡的各種 Lock 與 Isolation Level

來推薦其他人寫的文章 (雖然是在 Medium 上...):「複習資料庫的 Isolation Level 與圖解五個常見的 Race Conditions」、「對於 MySQL Repeatable Read Isolation 常見的三個誤解」,另外再推薦英文維基百科上的「Snapshot isolation」條目。

兩篇文章都是中文 (另外一個是英文維基百科條目),就不重複講了,這邊主要是拉條目的內容記錄起來,然後寫一些感想...

SQL-92 定義 Isolation 的時候,技術還沒有這麼成熟,所以當時在訂的時候其實是以當時的技術背景設計 Isolation,所以當技術發展起來後,發生了一些 SQL-92 的定義沒那麼好用的情況:

Unfortunately, the ANSI SQL-92 standard was written with a lock-based database in mind, and hence is rather vague when applied to MVCC systems. Berenson et al. wrote a paper in 1995 critiquing the SQL standard, and cited snapshot isolation as an example of an isolation level that did not exhibit the standard anomalies described in the ANSI SQL-92 standard, yet still had anomalous behaviour when compared with serializable transactions.

其中一個就是 Snapshot Isolation,近代的資料庫系統都用這個概念實做,但實際上又有不少差別...

另外「Jepsen: MariaDB Galera Cluster」這篇裡出現的這張也很有用,裡面描述了不同層級之間會發生的問題:

這算是當系統有一點規模時 (i.e. 不太可能使用 SERIALIZABLE 避免這類問題),開發者需要了解的資料庫限制...

Fortnite 看起來沒上 Auto Scaling?(或是沒正確設好?)

Fortnite 遊戲的伺服器放在 AWS 上,看起來這波 Meltdown 的安全更新 (KPTI) 造成非常大的 overhead:

不過看起來出了問題:

We wanted to provide a bit more context for the most recent login issues and service instability. All of our cloud services are affected by updates required to mitigate the Meltdown vulnerability. We heavily rely on cloud services to run our back-end and we may experience further service issues due to ongoing updates.

最有可能的是把 AWS 當作一般的 VPS 在用,另外一種可能是有部份內部服務沒有 scale,造成上了 KPTI 後 overhead 增加,就卡住了...

讀書時間:Meltdown 的攻擊方式

Meltdown 的論文可以在「Meltdown (PDF)」這邊看到。這個漏洞在 Intel 的 CPU 上影響最大,而在 AMD 是不受影響的。其他平台有零星的消息,不過不像 Intel 是這十五年來所有的 CPU 都中獎... (從 Pentium 4 以及之後的所有 CPU)

Meltdown 是基於這些前提,而達到記憶體任意位置的 memory dump:

  • 支援 µOP 方式的 out-of-order execution 以及當失敗時的 rollback 機制。
  • 因為 cache 機制造成的 side channel information leak。
  • 在 out-of-order execution 時對記憶體存取的 permission check 失效。

out-of-order execution 在大學時的計算機組織應該都會提到,不過我印象中當時只講「在確認不相干的指令才會有 out-of-order」。而現代 CPU 做的更深入,包括了兩個部份:

  • 第一個是 µOP 方式,將每個 assembly 拆成更細的 micro-operation,後面的 out-of-order execution 是對 µOP 做。
  • 第二個是可以先執行下去,如果發現搞錯了再 rollback。

像是下面的 access() 理論上不應該被執行到,但現代的 out-of-order execution 會讓 CPU 有機會先跑後面的指令,最後發現不該被執行到後,再將 register 與 memory 的資料 rollback 回來:

而 Meltdown 把後面不應該執行到 code 放上這段程式碼 (這是 Intel syntax assembly):

其中 mov al, byte [rcx] 應該要做記憶體檢查,確認使用者是否有權限存取那個位置。但這邊因為連記憶體檢查也拆成 µOP 平行跑,而產生 race condition:

Meltdown is some form of race condition between the fetch of a memory address and the corresponding permission check for this address.

而這導致後面這段不該被執行到的程式碼會先讀到資料放進 al register 裡。然後再去存取某個記憶體位置造成某塊記憶體位置被讀到 cache 裡。

造成 cache 內的資料改變後,就可以透過 FLUSH+RELOAD 技巧 (side channel) 而得知這段程式碼讀了哪一塊資料 (參考之前寫的「Meltdown 與 Spectre 都有用到的 FLUSH+RELOAD」),於是就能夠推出 al 的值...

而 Meltdown 在 mov al, byte [rcx] 這邊之所以可以成立,另外一個需要突破的地方是 [rcx]。這邊 [rcx] 存取時就算沒有權限檢查,在 virtual address 轉成 physical address 時應該會遇到問題?

原因是 LinuxOS X 上有 direct-physical map 的機制,會把整塊 physical memory 對應到 virtual memory 的固定位置上,這些位置不會再發給 user space 使用,所以是通的:

On Linux and OS X, this is done via a direct-physical map, i.e., the entire physical memory is directly mapped to a pre-defined virtual address (cf. Figure 2).

而在 Windows 上則是比較複雜,但大部分的 physical memory 都有對應到 kernel address space,而每個 process 裡面也都還是有完整的 kernel address space (只是受到權限控制),所以 Meltdown 的攻擊仍然有效:

Instead of a direct-physical map, Windows maintains a multiple so-called paged pools, non-paged pools, and the system cache. These pools are virtual memory regions in the kernel address space mapping physical pages to virtual addresses which are either required to remain in the memory (non-paged pool) or can be removed from the memory because a copy is already stored on the disk (paged pool). The system cache further contains mappings of all file-backed pages. Combined, these memory pools will typically map a large fraction of the physical memory into the kernel address space of every process.

這也是 workaround patch「Kernel page-table isolation」的原理 (看名字大概就知道方向了),藉由將 kernel 與 user 的區塊拆開來打掉 Meltdown 的攻擊途徑。

而 AMD 的硬體則是因為 mov al, byte [rcx] 這邊權限的檢查並沒有放進 out-of-order execution,所以就避開了 Meltdown 攻擊中很重要的一環。