又一份講基本 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 的保證程度來設計。

PostgreSQL 裡的 B-tree 結構

在「Indexes in PostgreSQL — 4 (Btree)」這邊看到講 PostgreSQLB-tree 結構以及常見的查詢會怎麼使用 B-tree。

裡面講了三種查詢,第一種是等號的查詢 (Search by equality),第二種是不等號的查詢 (Search by inequality),第三種是範圍的查詢 (Search by range)。再後面講到排序與 index 的用法。

雖然是分析 PostgreSQL,但裡面是一般性的概念,其他使用 B-tree 結構的資料庫也是類似作法...

openrsync

在「openrsync imported into the tree」這邊看到 openrsync 專案進入到 OpenBSD 的 source tree 內。

rsync 是使用 GPLv3 授權,這個授權剛出來的時候,幾個比較大的 BSD 的團隊都有找律師研究過,最後都是做出不要把 GPLv3 的軟體放進 source tree 的建議,但 rsync 算是很好用的工具 (尤其是在效率上)。

看起來 openrsync 這個專案主要的目的就是重新實做出 ISC license 版本的 rsync:

This is an implementation of rsync with a BSD (ISC) license. It's compatible with a modern rsync (3.1.3 is used for testing, but any supporting protocol 27 will do), but accepts only a subset of rsync's command-line arguments.

然後目前只有設計在 OpenBSD 上跑,其他平台可能需要花些時間 porting 修正相容性:

At this time, openrsync runs only on OpenBSD. If you want to port to your system (e.g. Linux, FreeBSD), read the Portability section first.

GitHub 上的 Git repository 只是個 mirror,真正在管理程式碼的部份還是使用 CVS

This repository is a read-only mirror of a private CVS repository. I use it for issues and pull requests. Please do not make feature requests: I will simply close out the issue.

Mark Callaghan 花五分鐘介紹 LSM trees

實做 MyRocksMark Callaghan 花五分鐘在 CIDR 2019 上介紹 LSM tree:「Geek code for LSM trees」。翻了一下發現 CIDR 是兩年辦一次,跟之前遇過的 conference 不太一樣...

投影片在「Diversity of LSM tree shapes」這邊可以看到,在五分鐘內講完的前提下規劃出的重點...

Amazon Aurora (MySQL) 推出相容於 MySQL 5.7 的版本

Amazon Aurora (MySQL) 推出相容於 MySQL 5.7 的版本了:「Amazon Aurora is Compatible with MySQL 5.7」。

不過網站上的介紹還沒更新:

Amazon Aurora is a relational database service that combines the speed and availability of high-end commercial databases with the simplicity and cost-effectiveness of open source databases. The MySQL-compatible edition of Aurora delivers up to 5X the throughput of standard MySQL running on the same hardware, and is designed to be compatible with MySQL 5.6, enabling existing MySQL applications and tools to run without requiring modification.

5.7 其中一個賣點在於支援 Spatial index (透過 R-tree),不過 AWS 的版本看起來是自己用 B-tree 加上 Z-order curve 實做:「Amazon Aurora under the hood: indexing geospatial data using Z-order curves」。

我覺得看看就好啦,拿 244GB RAM 的 r3.8xlarge 跑 1GB 的 data set,當大家是傻逼嗎...

Percona 宣佈支援 MyRocks (MySQL 上的 RocksDB engine)

RocksDBFacebookGoogle 放出的 LevelDB 改出來,然後被更多人接受並且投注資源的 library... (看兩邊的 GitHub 應該就會有感覺了)

而 Facebook 的人在改進後又花了不少力氣 porting 到 MySQL 上...

之前 Twitter 上就有看到不少消息,這次算是在 Percona 官方的 blog 上正式公佈要支援 MyRocks 的消息:「Announcing MyRocks in Percona Server for MySQL」。

依照目前的計畫次在明年 2017 的 Q1 放出 experimental build,依照 Percona 的品質慣例,應該是可以拿來在測試環境下跑的順順的 (在還沒有 heavy loading 的前提下):

We will provide the experimental builds of MyRocks in Percona Server in Q1 2017, and we encourage you to start testing and experimenting so we can quickly release a solid GA version.

文章下面的 comment 剛好有人提到 Percona 另外一個產品線 TokuDB,這兩個產品線重複的問題:

MyRocks seems pretty similar to TokuDB. They are both write-optimized. MyRocks uses LSM tree while TokuDB uses fractal tree.

How do the 2 compare? Which one would you recommend using?

之前被 Percona 買下的 TokuDB 跟 Facebook 所發展出來的 MyRocks 的產品重複性頗高 (都是為了寫入的部分最佳化)。應該還是因為 fractal treeLSM tree 成熟度造成的效能差異還是太明顯吧 (當然另外也跟後面公司投入的資源有關),讓 Percona 決定還是要支援 MyRocks,而不是全力推動自家買下的 TokuDB... (唔,變成阿斗了?)

不知道成熟後有沒有機會變成 InnoDB replacement...

Go 上面的白箱安全性檢查

HP 的 open source 專案「Go AST Scanner」,分析 Go 的原始程式碼拉出 AST 進行分析 (Static program analysis),再找出可能的安全性問題。

雖然是 alpha 階段,但看起來是個好東西啊... 至少寫的太誇張的 SQL injection 可以掃出來。

Percona 正式推出相容於 MongoDB 的產品「Percona Server for MongoDB」

Percona 正式推出與 MongoDB 相容的產品 Percona Server for MongoDB:「Percona Delivers Free, Open Source Percona Server for MongoDB」。

挑重點講,其實最重要的是 data engine 多了 Percona 自家的 PerconaFT 以及 FacebookRocksDB

Percona Server for MongoDB offers all the features of MongoDB 3.0 Community Edition, along with two additional storage engine options – PerconaFT and Facebook’s RocksDB

PerconaFT 是基於被併購的 Tokutek 所研發的 TokuDB (Fractal tree index) 而誕生的產品,在效能上有相當的優勢...

如果有機會的話來研究看看吧 :o

MySQL 的 Index 設計技巧

Percona 的「Indexing 101: Optimizing MySQL queries on a single table」這篇講了最基本的 index 設計技巧,雖然文章裡沒提到,但最好是需要 B-treeB+ tree 的背景知識。

MySQL 的 query 大致分成幾個階段。先決定要使用哪些 index (或是完全不用),然後透過 index 抓出符合條件資料 (或是 table scan),最後再細部過濾。

以文章裡提到的「Multiple inequalities」範例裡這樣的 SQL query 來討論:

SELECT * FROM t WHERE c > 100 and b < 10 and d = 'xyz'

如果 index 是 (d, c),需要在透過這組 index 抓出資料後再過濾 b < 10 的條件。而如果 index 是 (d, b),需要在取出資料後再過濾 c > 100 的條件。也就是 B+ tree 做不到的事情,就要另外 post-processing。

另外也有提到 covering index 對效能提昇的原理,不過這就有點屬於怪招了...