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 攻擊中很重要的一環。

Amazon EKS 與 AWS Fargate

在今年的 AWS re:Invent 2017 上宣佈 Amazon ECS 也支援 Kubernetes,也就是 Amazon EKS:「Amazon Elastic Container Service for Kubernetes」,一個用的人夠多就支援的概念...

目前這個服務還在 Preview,所以要申請才能用:

Amazon EKS is available in Preview. We look forward to hearing your feedback.

另外一個在 AWS re:Invent 2017 上宣佈的是 AWS Fargate,讓你連 Amazon ECS 或是 Amazon EKS 都不用管的服務,直接按照 container 的大小收費:「Introducing AWS Fargate – Run Containers without Managing Infrastructure」、「AWS Fargate: A Product Overview」。

第一個有疑慮的點是,是否會跟其他人共用相同的 host,也就是 isolation 的程度。這點在 AWS 的人在 Hacker News 上的這邊有回覆,在不同的 cluster 上不會使用同樣的底層:

NathanKP 4 days ago [-]
Fargate isolation is at the cluster level. Apps running in the same cluster may share the underlying infrastructure, apps running in different clusters won't.

另外也提到每個 cluster 都是使用者自己產生的:

NathanKP 3 days ago [-]
A customer creates a cluster on their account. You as a customer can create one or more Fargate clusters on your account to launch your containers in.

不是很正面的回覆,而且不是在官方的 forum 回的,安全性就要大家自己判斷了...

另外也有有提到與 Amazon EC2 相比,價錢當然會比較貴,但可以預期會降低 engineer 的時間成本:

NathanKP 4 days ago [-]
AWS employee here. Just want to say that we actually had a typo in the per second pricing on launch. The actual pricing is:
$0.0506 per CPU per hour
$0.0127 per GB of memory per hour
Fargate is definitely more expensive than running and operating an EC2 instance yourself, but for many companies the amount that is saved by needing to spend less engineer time on devops will make it worth it right now, and as we iterate I expect this balance to continue to tip. AWS has dropped prices more than 60 times since we started out.

目前只能接 Amazon ECS,預定 2018 可以接 Amazon EKS:

I will tell you that we plan to support launching containers on Fargate using Amazon EKS in 2018.

而目前這個版本 (可以接 Amazon ECS 的版本) 在 us-east-1 已經開放了:

Fargate is available today in the US East (Northern Virginia) region.

MySQL 上不同 Isolation Level 對效能的影響

目前看到的結論都是:MySQL (InnoDB) 上因為高度對 RR (REPEATABLE-READ) 最佳化,使得 RR 的效能反而比 RC (READ-COMMITTED) 以及 RU (READ-UNCOMMITTED) 都好。

不清楚 RR/RC/RU 差異的可以參考維基百科上「Isolation (database systems)」的解釋...

從 2010 年在測 5.0 的「Repeatable read versus read committed for InnoDB」到 2015 年測 5.7 的「MySQL Performance : Impact of InnoDB Transaction Isolation Modes in MySQL 5.7」都測出 RR 的效能比 RC/RU 好... 三段分別是 RR/RC/RU:

所以在 MySQL 上沒有使用 RC/RU 的必要... (抱頭)

InnoDB 的 Isolation Level 以及 Performance Schema 對效能的影響

雖然 Mark Callaghan 現在的主力都在 MyRocks 上,但他還是對 InnoDB 上的效能頗關注 (畢竟是個成熟而且競爭的產品)。而這篇「Sysbench, InnoDB, transaction isolation and the performance schema」講到 MySQL 5.6.26 裡的 InnoDB,了解 isolation level 與 performance schema 對效能的差異。結果可以在這邊翻到。

關掉 performance schema 會讓效能變好是預期的,不過看起來比預期小很多。另外某些情況下 RR (REPEATABLE-READ) 的效能會比 RC (READ-COMMITTED) 好倒是頗意外,這邊也有給出原因:

Using repeatable-read boosts performance because it reduces the mutex contention from getting a consistent read snapshot as that is done once per transaction rather than once per statement.

不過看了看數據,純粹讀取的部份 RC 會在某些地方快一些,不過整體來說在 MySQL 5.6.26 上的 RR 與 RC 差異真的不算太明顯了...