原來有專有名詞:TOCTOU (Time-of-check to time-of-use)

看「The trouble with symbolic links」這篇的時候看到的專有名詞:「TOCTOU (Time-of-check to time-of-use)」,直翻是「先檢查再使用」,算是一個常見的 security (hole) pattern,因為檢查完後有可能被其他人改變,接著使用的時候就有可能產生安全漏洞。

在資料庫這類環境下,有 isolation (ACID 裡的 I) 可以確保不會發生這類問題 (需要 REPEATABLE-READ 或是更高的 isolation level)。

但在檔案系統裡面看起來不太順利,2004 年的時候研究出來沒有 portable 的方式可以確保避免 TOCTOU 的問題發生:

In the context of file system TOCTOU race conditions, the fundamental challenge is ensuring that the file system cannot be changed between two system calls. In 2004, an impossibility result was published, showing that there was no portable, deterministic technique for avoiding TOCTOU race conditions.

其中一種 mitigation 是針對 fd 監控:

Since this impossibility result, libraries for tracking file descriptors and ensuring correctness have been proposed by researchers.

然後另外一種方式 (比較治本) 是檔案系統的 API 支援 transaction,但看起來不被主流接受?

An alternative solution proposed in the research community is for UNIX systems to adopt transactions in the file system or the OS kernel. Transactions provide a concurrency control abstraction for the OS, and can be used to prevent TOCTOU races. While no production UNIX kernel has yet adopted transactions, proof-of-concept research prototypes have been developed for Linux, including the Valor file system and the TxOS kernel. Microsoft Windows has added transactions to its NTFS file system, but Microsoft discourages their use, and has indicated that they may be removed in a future version of Windows.

目前看起來的問題是沒有一個讓 Linux community 能接受的 API 設計?

ClickHouse 自家做的 benchmark 比較

在「Show HN: A benchmark for analytical databases (Snowflake, Druid, Redshift) (clickhouse.com)」這邊看到 ClickHouse 自家做的 benchmark 比較,網站在「ClickBench — a Benchmark For Analytical DBMS」這邊。

這種 benchmark 基本上是拿來當作清單來看,另外 Hacker News 上的討論一定得看,尤其是沒被列上 benchmark 的...

講到 ClickHouse,先前是有朋友跑來說他有個需求是需要跑分析,但遇到用 PostgreSQL 時發現寫入速度不夠快的問題,看看有沒有什麼方法可以解。問了多一點以後發現他的需求是 OLAP 類而不是 OLTP 類,就先跟他講要去找 OLAP engine 來解決。

然後就聊到維基百科上「Comparison of OLAP servers」這個條目,裡面列出來的 open source 軟體是不少,但 Apache 家基本上大家都知道是回收場,裡面就剩下 ClickHouse 比較常在 Hacker News 以及其他地方被提到,但我有跟他講我連玩都沒玩過,我們家自己反而是用 CassandraTrino 搭出來的,當時沒有花太多時間研究市場上的方案,就挑了一個自己熟悉的方案趕快先解決。

但過了兩天後他就說用 ClickHouse 解決了,反而讓我對 ClickHouse 有興趣起來,反正記憶體當時裝了一堆沒用到。

拉了一下「Summary of the 1.1 Billion Taxi Rides Benchmarks」這邊的資料看,這個作者常常會測各種資料庫,算是一個可以參考的資料來源,可以看到 2019 年測的「1.1 Billion Taxi Rides: 108-core ClickHouse Cluster」其實就相當不錯了?

基本上先照「Usage Recommendations」這邊看一輪,基本的要求不低,但剛好機器是 32GB RAM:

If your system has less than 16 GB of RAM, you may experience various memory exceptions because default settings do not match this amount of memory. The recommended amount of RAM is 32 GB or more. You can use ClickHouse in a system with a small amount of RAM, even with 2 GB of RAM, but it requires additional tuning and can ingest at a low rate.

如果要跑 cluster 模式的話會需要 ZooKeeper 或是替代品 ClickHouse Keeper

然後除了使用官方的 clickhouse-client 連線以外,也可以用 MySQL 或是 PostgreSQL 的 client 連,裡面操作其實蠻簡單的,好像值得投資看看?

PostgreSQL 的 scale 建議

Hacker News Daily 上看到「Postgres scaling advice for 2021」這篇,講 PostgreSQL 要怎麼 scale,在 Hacker News 上也有對應的討論可以看:「Postgres scaling advice (cybertec-postgresql.com)」。

文章前面先提到分散式系統的複雜度會導致 RDBMS 上的一些假設失效,所以如果可以用單台機器暴力解,就儘量用單台機器來解 (scale up 的情境),裡面就提到了一些「暴力可以解決很多問題」的說明,差不多就是前幾天提到的「Let's Encrypt 升級資料庫伺服器 (AMD YES?)」。

後面提到如果真的要放進分散式的 RDBMS (scale out 的情境),怎麼設計資料結構會比較好。

這邊剛好也可以提一下,量夠大的時候要把 OLTPOLAP 的應用分開,現在有很多 OLAP 資料庫可以選擇,同步的工具也很成熟了,通常效能會比在 OLTP 上面硬跑來的好。

最後提一下,文章裡面對於 transaction per second 可以拉很高,有些假設沒有明寫出來。這需要盡可能把 transaction 拆小,避免常常有 giant transaction 卡住整個資料庫,這點對於一般的系統會需要做不少改寫...

不過最後比較疑惑的是,這種文章怎麼會上 Hacker News 的啊...

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,應該會是後續的目標?

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 避免這類問題),開發者需要了解的資料庫限制...

EnterpriseDB 打算推出的 zheap,想要解 VACUUM 問題...

前天被問到「DO or UNDO - there is no VACUUM」這篇,回家後仔細看一看再翻了一些資料,看起來是要往 InnoDB 的解法靠...

PostgreSQL 與 InnoDB 都是透過 MVCC 的概念實做 transaction 之間的互動,但兩者實際的作法不太一樣。其中帶來一個明顯的差異就是 PostgreSQL 需要 VACUUM。這點在同一篇作者八年前 (2011) 的文章就有提過兩者的差異以及優缺點:「MySQL vs. PostgreSQL, Part 2: VACUUM vs. Purge」。

UPDATE 時,InnoDB 會把新資料寫到表格內,然後把可能會被 rollback 的舊資料放到表格外:

In InnoDB, only the most recent version of an updated row is retained in the table itself. Old versions of updated rows are moved to the rollback segment, while deleted row versions are left in place and marked for future cleanup. Thus, purge must get rid of any deleted rows from the table itself, and clear out any old versions of updated rows from the rollback segment.

而被 DELETE 清除的資料則是由 purge thread 處理:

All the information necessary to find the deleted records that might need to be purged is also written to the rollback segment, so it's quite easy to find the rows that need to be cleaned out; and the old versions of the updated records are all in the rollback segment itself, so those are easy to find, too.

所以可以在 InnoDB 看到 purge thread 相關的設定:「MySQL :: MySQL 5.7 Reference Manual :: 14.6.11 Configuring InnoDB Purge Scheduling」,負責處理這些東西。

而在 PostgreSQL 的作法則是反過來,舊的資料放在原來地方,新資料另外存:

PostgreSQL takes a completely different approach. There is no rollback tablespace, or anything similar. When a row is updated, the old version is left in place; the new version is simply written into the table along with it.

新舊資料的位置其實還好,主要是因為沒有類似的地方可以記錄哪些要清:

Lacking a centralized record of what must be purged, PostgreSQL's VACUUM has historically needed to scan the entire table to look for records that might require cleanup.

這也使得 PostgreSQL 裡需要 autovacuum 之類的程序去掃,或是手動跑 vacuum。而在去年 (2017) 的文章裡也有提到目前還是類似的情況:「MVCC and VACUUM」。

而在今年 (2018) 的文章裡,EnterpriseDB 就提出了 zheap 的想法,在 UPDATE 時寫到 table 裡,把可能被 rollback 的資料放到 undo log 裡。其實就是把 InnoDB 那套方法拿過來用,只是整篇都沒提到而已 XD:

That brings me to the design which EnterpriseDB is proposing. We are working to build a new table storage format for PostgreSQL, which we’re calling zheap. In a zheap, whenever possible, we handle an UPDATE by moving the old row version to an undo log, and putting the new row version in the place previously occupied by the old one. If the transaction aborts, we retrieve the old row version from undo and put it back in the original location; if a concurrent transaction needs to see the old row version, it can find it in undo. Of course, this doesn’t work when the block is full and the row is getting wider, and there are some other problem cases as well, but it covers many useful cases. In the typical case, therefore, even bulk updates do not force a zheap to grow. Instead, the undo grows. When a transaction commits, all row versions that will become dead are in the undo, not the zheap.

不過馬上就會想到問題,如果要改善問題,不是個找地方記錄哪些位置要回收就好了嗎?順便改變方法是為了避免 fragment 嗎?

等著看之後變成什麼樣子吧...

Stripe 也宣佈要停止支援 Bitcoin 了

Stripe 發了公告出來,要停止支援 Bitcoin:「Ending Bitcoin Support」。預定保留三個月的緩衝期,在 2018 年 4 月 23 日停掉:

Over the next three months we will work with affected Stripe users to ensure a smooth transition before we stop processing Bitcoin transactions on April 23, 2018.

跟其他單位停用的原因都差不多,愈來愈慢的交易速度與愈來愈高的手續費:

Transaction confirmation times have risen substantially; this, in turn, has led to an increase in the failure rate of transactions denominated in fiat currencies. (By the time the transaction is confirmed, fluctuations in Bitcoin price mean that it’s for the “wrong” amount.) Furthermore, fees have risen a great deal. For a regular Bitcoin transaction, a fee of tens of U.S. dollars is common, making Bitcoin transactions about as expensive as bank wires.

Steam 當時的理由很類似... (參考「Steam 停止使用 Bitcoin 購買遊戲」)

Steam 停止使用 Bitcoin 購買遊戲

Steam 宣佈停止使用 Bitcoin 購買遊戲:「Steam is no longer supporting Bitcoin」。

官方提到的原因是因為交易費用太高 (雖然是讓使用者付):

In the past few months we've seen an increase in the volatility in the value of Bitcoin and a significant increase in the fees to process transactions on the Bitcoin network. For example, transaction fees that are charged to the customer by the Bitcoin network have skyrocketed this year, topping out at close to $20 a transaction last week (compared to roughly $0.20 when we initially enabled Bitcoin).

另外一個原因是波動問題:

Historically, the value of Bitcoin has been volatile, but the degree of volatility has become extreme in the last few months, losing as much as 25% in value over a period of days.

所以這樣推測,Steam 不是直接換成法幣?我記得他們合作的交易所 (BitPay) 可以馬上換成法幣...

InnoDB 的 MVCC 繁忙時的效能問題

Facebook 上看到 Percona 的人修正了 InnoDB 的 MVCC 在繁忙時會有 O(n^2) 的效能問題:

MySQL 官方的 bug tracking system 是「InnoDB's MVCC has O(N^2) behaviors」這個,可以看到給的重製範例是在 transaction 內大量塞 INSERT 進去後,另外一個 transaction 使用 secondary index 就會受到影響。

裡面也有提到「Secondary index updates make consistent reads do O(N^2) undo page lookups」,雖然修正了,但看起來跟當時實做的規劃有關?所以導致許多地方都是 O(n^2)...

這個 bug 感覺是批次作業的行為?因為批次作業可能會用 transaction 包起來,一次寫入萬筆資料後再 COMMIT 進去。而這個行為很有機會觸發這個 bug,導致影響到線上的服務...