資料結構、RDBMS、ORM

欠了很久的雜記。既然是雜記,只是把一些事情記錄下來,許多句子的主題會跳來跳去,請多見諒。

先解釋標題的三個詞彙。這邊要講的是三種存取資料的方式:

  • 資料結構:直接操作最底層的資料結構。
  • RDBMS (Relational Database Management System,關聯式資料庫):透過 RDBMS 存取資料的方式,在 open source 領域比較常遇到 MySQLPostgreSQL。由於與下面的 ORM 比較,這一條指的是透過 SQL query 去存取資料。
  • ORM (Object-Relational Mapping):透過程式語言的 object 以及 object 之間的關聯性存取資料。

彈性最高、效能也最好的是直接的資料存取,但寫起來也最複雜;而 ORM 大致上就是反過來。

現代的 RDBMS 大多都有實做 ACID,在自己操作資料結構時考慮這塊會比較辛苦。兩個層級之間有一些 library 試著解決這個問題 (像是 BerkeleyDB 或是 LevelDB),不過這篇文章暫時跳過。

MySQL 與其他的 RDBMS 比較起來欠了許多東西,但 High Availability 的成熟度以及效能而成為 open source 的第一選項。而也因為許多人使用,大家都知道 MySQL 的先天限制,也有許多 workaround 出現,所以大多數的狀況下這不是問題。

MySQL 的 InnoDB 其實寫的相當不錯,但 MySQL 的 SQL parser 一直都是 MySQL 的痛處,所以許多人使用 MySQL 時會儘量使用 simple query,而 ORM 的特性剛好可以搭上風。

使用 ORM 時最常見要避免的是 N+1 的問題,其他常見到的問題大多都不是 ORM 專有的。

先整理到這邊。

ESR 解釋 C 的 Compiler 對 Structure Packing 的處理...

ESR (Eric S. Raymond) 寫了一篇 C Compiler 對 struct 實際如何佔用記憶體空間的說明:「The Lost Art of C Structure Packing」,全文在「The Lost Art of C Structure Packing」。

以前都學過也都還記得,但沒用就不容易想起來...

以文章裡的例子用這個 struct 說明:

struct {
    char *p;
    char c;
    int x;
};

(下面就不列出 struct 的部份了)

實際上在記憶體裡面會因為 alignment requirement 的關係,多了一個 padding (pad):

char *p;      /* 4 or 8 bytes */
char c;       /* 1 byte */
char pad[3];  /* 3 bytes */
int x;        /* 4 bytes */

而如果 x 是 8 bytes 的 long 時:

char *p;
char c;
long x;

padding 會變成:

char *p;     /* 8 bytes */
char c;      /* 1 byte
char pad[7]; /* 7 bytes */
long x;      /* 8 bytes */

這是因為硬體架構的關係。有些是因為硬體只支援切齊 alignment 的存取指令,有些是因為效率的差異而預設會增加 padding。

在處理 protocol 這類必須依照原始的 struct 設計時,需要指定

#pragma pack

強迫 compiler 關掉,不然 compiler 還是會補上 padding。

而在一般的情況下,調整 struct 裡元素的位置就能夠在不影像存取效能的前提下節省空間,如果是大量的 struct 時效果就會變得很明顯...

Linux kernel 內的資料結構與演算法...

Theoretical Computer Science Stack Exchange 上,有人問到有沒有哪些軟硬體的 source code 是可以跟學生說明某些經典演算法的重要性:「Core algorithms deployed」。

下面就有人列了 Linux kernel 內的演算法,以及對應的程式碼。相當長的一份列表...

除了 Linux kernel 外,也還有其他大型 open source 專案用到的資料結構與演算法...

不過看到 Bubble sort 是怎樣呢... XD

PHP 提供的資料結構...

從「How big are PHP arrays (and values) really? (Hint: BIG!)」這篇看到的。文章本身值得花些時間看過了解,不過對我來說重點在最後面的 SplFixedArray

PHPDatastructures 說明目前 PHP SPL 所支援的 data structure,在記憶體用量以及效率上面都會比自己實作來的小且快。

可以看到很多都支援 Countable、Iterator,以及 ArrayAccess,代表可以用 foreach() 或是對應的方式存取... 如果自己寫 library 的時候應該要善用這些 SPL。