joeangel · May 10, 2015 03:36
diff --git a/gistfile1.txt b/gistfile1.txt
 轉自: https://www.facebook.com/groups/616369245163622/permalink/672292292904650/
 作者: https://www.facebook.com/ho.s.fung?fref=nf

 （淺談系列）
 因為人們說我是PostgreSQL的熱血傳教士嘛
 好吧我來熱血傳教一下好了：
 今天我想談的，是RDBMS中的free space management(FSM)機制
 首先一點：
 MySQL(innoDB)和MSSQL是沒有這個機制的，因為其table是index-organized table，所有row的是基於其Primary Key有了指定位置的。
 相反，Oracle / postgreSQL的default table是heap-based，Primary Key index內只存放指向row data的pointer。所以，row record具體能放到那裡，是有很大的自由度的。為了最佳化效能，postgreSQL和oracle需要FSM讓快速找到能存放row data的空間。
 一個好的FSM應該有的特點：
 １　能快速知道table內有沒有空間剩下。如果沒有了便要告訴RDBMS去format新的空間出來
 ２　能快速找到足夠大的空間
 ３　能讓多個worker同一時間找到各自所需空間，而又不互相干擾
 ４　優先返回近期被使用過的空間，提升IO效率（cache hit rate）
 （註：第３點跟第４點的需求互相矛相的，下文會說）
 先再介紹一下PostgreSQL的FSM結構吧。
 PostgreSQL是一棵complete binary tree，其leaf node存放某一database所剩餘容量，而non leaf node則是存放了非其children的較大者的數值
 （註：這頁面有圖象化後的FSM http://blog.itpub.net/30088583/viewspace-1387176/）
 所以：
 １　要知道是否有空間剩下，只需要看root node的數值知可以了，這是O(1)
 ２　因為這是complete binary tree，所以只需要O (log n)時間便能找到所需空間所在的datablock
 ３　postgreSQL在searching時不是從root node開始的，而是從底層某一leaf node開始找。如果現在的node沒有足夠空間，便再移上一層，直到遇上了一個有足夠空間的non-leaf node為止，然後便再向有空間的subtree移動。
 整個過程是 (上移階段)O(log n) + (下移階段)O(log n) ＝ O(log n)
 而search starting position是由一個叫fp_next_slot的hint pointer控制，下一個request所得到的search starting position會是之前的+1。所以他們可能會落到不同的位置上，也不會互相干涉。
 ４　如果每個request都使用不同的datablock，在C100K的環境下便會每秒有100K * 8K = 800MB的random IO。（呃，好像今天企業級能忍受這種IO了，我要失業了）
 所以fp_next_slot是以~4000個datablock為單位作rotation的。如果一個Request在這一組的4000個datablock都沒法找到空間，fp_next_slot才會指向下一組的datablock。
 所以即使是在C100K的insert，所產生的Random IO也只會是8K * 8K / 3 = 21.3MB的Random IO（假設其每秒用光２個fsm group吧）
 總結：以我手提電腦能力，我的postgreSQL的concurrent insert是~8K pre sec。以今天企業級SSD能力，PostgreSQL其bottleneck很可能不會是IO也不是CPU，而是log management那邊。所以，PostgreSQL架構是寧可犠牲IO / CPU來換取更少量的blocking，到了今天終於發熱發亮。
	轉自: https://www.facebook.com/groups/616369245163622/permalink/672292292904650/
	作者: https://www.facebook.com/ho.s.fung?fref=nf

	（淺談系列）
	因為人們說我是PostgreSQL的熱血傳教士嘛
	好吧我來熱血傳教一下好了：
	今天我想談的，是RDBMS中的free space management(FSM)機制
	首先一點：
	MySQL(innoDB)和MSSQL是沒有這個機制的，因為其table是index-organized table，所有row的是基於其Primary Key有了指定位置的。
	相反，Oracle / postgreSQL的default table是heap-based，Primary Key index內只存放指向row data的pointer。所以，row record具體能放到那裡，是有很大的自由度的。為了最佳化效能，postgreSQL和oracle需要FSM讓快速找到能存放row data的空間。
	一個好的FSM應該有的特點：
	１　能快速知道table內有沒有空間剩下。如果沒有了便要告訴RDBMS去format新的空間出來
	２　能快速找到足夠大的空間
	３　能讓多個worker同一時間找到各自所需空間，而又不互相干擾
	４　優先返回近期被使用過的空間，提升IO效率（cache hit rate）
	（註：第３點跟第４點的需求互相矛相的，下文會說）
	先再介紹一下PostgreSQL的FSM結構吧。
	PostgreSQL是一棵complete binary tree，其leaf node存放某一database所剩餘容量，而non leaf node則是存放了非其children的較大者的數值
	（註：這頁面有圖象化後的FSM http://blog.itpub.net/30088583/viewspace-1387176/）
	所以：
	１　要知道是否有空間剩下，只需要看root node的數值知可以了，這是O(1)
	２　因為這是complete binary tree，所以只需要O (log n)時間便能找到所需空間所在的datablock
	３　postgreSQL在searching時不是從root node開始的，而是從底層某一leaf node開始找。如果現在的node沒有足夠空間，便再移上一層，直到遇上了一個有足夠空間的non-leaf node為止，然後便再向有空間的subtree移動。
	整個過程是 (上移階段)O(log n) + (下移階段)O(log n) ＝ O(log n)
	而search starting position是由一個叫fp_next_slot的hint pointer控制，下一個request所得到的search starting position會是之前的+1。所以他們可能會落到不同的位置上，也不會互相干涉。
	４　如果每個request都使用不同的datablock，在C100K的環境下便會每秒有100K * 8K = 800MB的random IO。（呃，好像今天企業級能忍受這種IO了，我要失業了）
	所以fp_next_slot是以~4000個datablock為單位作rotation的。如果一個Request在這一組的4000個datablock都沒法找到空間，fp_next_slot才會指向下一組的datablock。
	所以即使是在C100K的insert，所產生的Random IO也只會是8K * 8K / 3 = 21.3MB的Random IO（假設其每秒用光２個fsm group吧）
	總結：以我手提電腦能力，我的postgreSQL的concurrent insert是~8K pre sec。以今天企業級SSD能力，PostgreSQL其bottleneck很可能不會是IO也不是CPU，而是log management那邊。所以，PostgreSQL架構是寧可犠牲IO / CPU來換取更少量的blocking，到了今天終於發熱發亮。