#28 資料庫基礎 - 存取 Page (Hashed File)

前面兩篇文章提到了存取 page 的兩種方式，在這一篇文章裡要介紹的是另一種方式，我們稱它為 hashed file．聽到這個名字，你可能已經猜到這是和 hash function 有關係的儲存方式．沒錯，它就是利用 hash function 來決定儲存位置，也是就說透過 hash function 的計算來決定要儲存到那一個 page 上．

前面的文章曾提到過基本的 hash function，也介紹了它最簡單的運算方式．所以，假設一開始有十個 page，然後有五筆資料，我們可以將每筆資料傳給 hash function，計算出來的結果是 0 - 9 的數字，而這數字就用來代表要儲存到那一個 page 上．一旦資料變多時，資料的筆數一定會遠遠大於 page 的數量，所以同一個 page 上一定會有許多筆資料．因此，透過 hash function 的方式來計算儲存位置也是個蠻快速的方法．不過，資料庫引擎通常不會被設計成將整筆資料拿來 hash，因為我們在找資料時很少會用全部的欄位做為搜尋的條件，因此，我們通常會選擇幾個重要的欄位或是只選擇 primary key 的欄位來做為 hash function 的輸入值，而 hash function 輸出值就是 page 的號碼．因此，資料庫引擎在為我們找資料的時候，只要欄位條件符合的話，就可以透過 hash function 的計算而快速地得到 page 號碼．

接下來，你可能會問到，一旦資料量越來越大時，一定會有很多的資料經過 hash function 計算後會得到同樣的答案，而這些資料量會遠遠超過一個 page 得記錄的資料量．這種情況在我們談論 hash function 的時候也會發生，當時所採用的方法就是在 bucket 上做一個 list 來承接更多的資料．相同地，在這裡也是可以用相同的觀念．如下圖:

如上圖的上面那個 page，當它沒有足夠的空間承載更多資料時，此時資料庫引擎就必需要一個空白的 page ，然後在前面的 page 做一個連結到空白的 page，接著就可以把屬於同一個 bucket 的資料寫進去．因此，你可以看見的是，如果 hash function 的 bucket 準備不多的話，那麼資料就會長成像幾條很長的 page life，我們並不希望碰到這樣的情況．所以若要採用 hashed file 的儲存方式，則該 hash function 需要有能力產生足夠多的 bucket，甚至最好是能彈性處理，依照資料的多少來決定，但相對地要做多的配套措施．但若以好的角度來看，用 hashed file 的結構來儲存資料，對資料庫引擎而言可以大大提供資料搜尋的速度．

有關資料如何儲存在 page 上，從儲存的方式來看基本上有三種方式，而每一種方式都有其優點和缺點，所以針對不同的資料，根據他們的特性來決定用那一種儲存方式將是比較好的決定．要怎麼評估呢 ? 我會把評估的成本估算寫在未來的文章裡，讓大家知道資料庫引擎是根據什麼樣的數據來決定要用什麼方式儲存資料．

閱讀全文

#27 Coding 面試 Leetcode #98 Validate Binary Search Tree

我記得這一題我被問過兩次，是兩個不同的團隊，而且都是跟資料庫有關的工作．所以，若你也要尋找資料庫相關的開發工作，看來 Tree 的題目是很難避免的．

這題的題目很單純，就是要寫一個 function 用來驗證題目的 Tree 是不是 Binary Search Tree (BST).
根據 BST 的定義，左邊的節點值必需小於父節點值，而右邊的節點值必需大於父節點值.
但這題有一點要小心的是，別只是檢查父節點值而己，應該要檢查所有上層的父節點值都要小於或是大於．

如果題目只給你 tree root，那麼你可以寫出像下面的 function 來檢查這個 tree 是不是 BST.

        public bool IsValidBST(TreeNode root)
        {
            return BST(root, null, null);
        }

        bool BST(TreeNode node, int? min, int? max)
        {
            if (node == null) return true;
            if (min == null && max == null)
            {
                    return BST(node.left, min, node.val ) && BST(node.right, node.val , max);
            }
            else if (min != null && max == null)
            {
                if (node.val > min )
                    return BST(node.left, min, node.val) && BST(node.right, node.val, max);
            }
            else if (min == null && max !=null)
            {
                if ( node.val < max)
                    return BST(node.left, min, node.val) && BST(node.right, node.val, max);
            }
            else
            {
                if (node.val > min && node.val < max)
                    return BST(node.left, min, node.val) && BST(node.right, node.val, max);
            }
            return false;
        }

若你仔細看的話，我是把每個分支出去時可能的節點值範圍也傳遞過去．這樣的寫法也許不是最好，但就如之前文章所說，要在五分鐘內想好然後在半小時內寫完再測試，所以就勉強用了.

這時候如果遇到要求更高的面試人員，他可能會說 recursive 的方法不適合用在 tree，所以要改成 iterative 的方式來寫．
其實要改成 iterative 的方式，說難不難，說簡單也不簡單，因為要在那短時間想出來也是件不容易的事．比較幸運的是之前我有練習過 BST 用 In-order traversal 的走法來驗證 BST，所以這題也就順利寫完了，以下就是改成 iterative 的方式，用 In-order 走訪 BST 之後，得到的答案一定是從小排到大的數值，所以只要多一個 for loop 來檢查數值是不是從小排到大即可.

  public bool IsValidBST(TreeNode root)
        {
            if (root == null) return true;
            List<int> re = InOrder(root);
             if (re.Count == 1) return true;
            for (int i = 0; i < re.Count - 1; i++)
            {
                if (re[i] >= re[i + 1])
                    return false;
            }
            return true;
        }

        List<int> InOrder(TreeNode node)
        {
            List<int> result = new List<int>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (stack.Count != 0 || node != null)
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }
                else
                {
                    TreeNode t = stack.Pop();
                    result.Add(t.val);
                    node = t.right;
                }
            }
            return result;
        }

雖然在初步面談中都把上述的題目做完了，但這也不代表就有機會可以繼續做後續的面試．所以，很可惜沒能做成資料庫開發的工作，找工作真的一切都是個緣份.

閱讀全文

#26 資料庫基礎 - 存取 Page (Sorted File)

上一篇文章談的內容是針對資料之間是沒有順序的情況，因此在尋找資料時就是採用依照資料的排列順序來尋找．因此整個尋找過程的時間複雜度是 O(n) ．通常來說，資料庫設計者不會讓這樣的事情發生，除非資料本身是一個相當小的參考資料而己，否則資料一旦多了，  O(n) 實在不是一個好現象．

在真實世界中的應用，我們常常可以為資料找到至少一種排列方法，例如，在學校的資料庫中，基本上可以用學生證的號碼來排序學生的資料，因為在同一個學校裡不會有相同的學生證號碼．我們在前面的文章中也提過，一旦資料排序過了之後，時間複雜度就會從 O(n) 下降成 O(log n)，基本上就是 Binary search．因此，如果資料可排序的話，則資料庫引擎就可以依序地將資料寫在檔案中．

資料庫引擎為這些可排序的資料寫入到檔案中有兩個方式．第一種方式是直接將資料依序排列好寫在檔案中，所以每個資料的前後順序就跟排列的順序是一模一樣的，如果中間要插入一筆新資料時，就很有可能會發生 page split 的動作．如圖是一個例子．紅色的框框代表 page，而藍底的框框帶表一筆資料，而藍框裡的數字代表資料的序號，序號不一定要連續，只要不重複即可．所以一開始把資料寫入時，它的排列長相如下:

這時候如果要新增一筆序號 7 的資料，那麼它要排在 5 和 10 之間，但是該 page 已經沒有位置了，因此發生 page split．

資料 7 會放在前面的 page 還是後面的 page，這將由資料庫引擎內定的邏輯來決定．

第二種將資料寫入檔案的方式是讓資料的實體位置不需要改變，另外在建立 "目錄"，然後在這目錄上做 binary search 的動作．

在這種方式下，新增一筆序號 7 的資料時，它就可以直接在 page n+1 的地方寫入，然後資料庫引擎只要更新目錄的內容即可．

當新增一筆序號 7 的資料在目錄 page 時，此時會發現  page split 還是在有足夠的空間下把後面的資料往後移，這將由資料庫引擎的內定邏輯而定．因此，第二種方式就變成直接在目錄 page 上做  binary search ，然後再依照其內容 (pointer) 就可以找到該筆資料．

所以，你的 table schema 的設定理應當是都有 primary key 的存在，如此一來才能做為資料庫引擎排序的依據．其實，以上的內容基本上也就是 clustered index 和 non-clustered index 的精神．

閱讀全文

#25 資料庫基礎 - 存取 Page (Heap File)

        在前面的幾篇文章中提到了資料庫引擎讀取與寫入資料時在面對固定長度與非固定長度時所可以採用的儲存方式，其中提供了 Page 為一個儲存空間的管理單位，透過 Page 的機制，讓資料庫引擎能以 Page 為單位做資料讀取與寫入的動作．搭配上 Page 裡的 manifest 資料，資料庫引擎就可以很清楚地知道這個 Page 裡面有多少筆資料以及有多少剩餘空間可用．這時候我們把層次往上拉高一點來看，那 Page 跟 Page 之間的關係是如何定義呢 ? 舉例來說，當某一個表格裡的資料繼續變多時，這些資料很可能會需要很多的 Page 來能承載，那資料庫引擎又怎麼知道是那幾個 Page 是用來承載這表格的資料呢 ? 因此，我們也必須定義 Page 和 Page 之間的關係．

        要定義 Page 之間的關係最簡單的方法就是採用 Linked List 的概念，也就是說每一個 Page 都會記錄著上下一個 Page 的位置，這就像是 Double Linked List 一樣，所以資料庫引擎便很容易地在 Page 之間游走來尋找資料．參考下圖來看一個很簡單的例子:

上圖一共有七個 Page，其中 page 1, 3, 4, 6 前後之間有 pointer 指著上下一個 Page 的位置，這也代表這四個 Page 儲存著高度相關的資料，比如說是同一個表格的資料，或是同一份 index 的資料等．但什麼樣的資料會讓 Page 用這種方式儲存呢 ? 看來是隨意安排的資料，不需要排序，也不需要特殊的安排，資料先進來就先寫入．因此，當資料庫引擎在存取這類型的資料時所花費的成本就會很高，因為都必須從頭開始往後找．不論是找什麼樣的資料，尋找一律都是從最前面的 Page 開始找到最後的 Page．其實這也就是 Linked List 的特性之一．也就是說你要找的資料剛好落在最後一個 Page 的時候，資料庫引擎就必須要從最前面的 Page 一直找到最後一個 Page．因此，這樣所花費的成本是相當高的．

所以，這也告訴了你一件事情，如果你的資料用上述的方式來儲存，這將造成資料庫引擎花費許多時間成本來尋找與寫入資料，而這種像 Double Linked List 的 Page 關係方式，一般的課本稱它為 heap file. 後面的文章會再繼續介紹其他方法．

閱讀全文

#24 我的 IT 人生 - 簡短篇

這一篇內容我不談資料結構，也不談資料庫，更不談寫程式，我來簡單地談一談自己的 IT 人生．

在我還是高中生時，當時有接觸一些電腦課，學會了操作 MS-DOS 系統，也會寫一些簡單的 BASIC 程式，對電腦的確是有相當興趣，但還沒想過要把它當成一生的工作方向．後來，念了大學之後，我念的是機械工程，原本我的打算是想要念電機工程，因為自認為在物理課本中，電學念的比力學好很多，不過也奇怪，我當時還是把機械工程填入到志願卡裡，若我印象沒錯的話，我記得我的志願卡裡還有土木工程電子工程等等相關的工程科系．大學四年就這樣念到畢業了，說實在，到現在我還是覺得大學那 4 年似乎是浪費的，因為我現在沒需要用到任何機械工程的知識．不過，人生就是這樣，現在回過頭來看，就當做是用人生的時間換來了一些人生經驗．

接著，學校畢業後就直接去當兵了．我想這是我整個 IT 人生的起點．我很幸運地被分配到資訊單位，我還記得一進去時學長丟給我一本書，網路概論．我就從網路開始學習，從區域網路到廣域網域，也包含通訊協定如 TCP/IP 等等的都學了，後來還得學習寫網頁程式，一開始用 CGI 後來用 ASP 寫．在那近兩年的時間裡就像是一個職業訓練所一樣，我把基本的網路和網頁程式學了起來，退伍後就直接在資訊業找了工作．當時是差不多 2000 年的時候，Internet 和電子商務正在蓬勃發展，所以許多公司也不會在乎學歷或科系，只要真的能拿出工具寫出一些真實的東西，很多公司都是歡迎的．我的印象中，當時我快退伍找工作時，每個星期總是可以收到公司邀請面試的信件．

在工作了幾年後，我腦中漸漸地有越來越多的問號，比如要怎麼才能寫出好的程式，要如何才能是好的設計，甚至細節到為什麼資料庫的搜尋可以這麼快，在工作上有太多太多的問題實在讓我很好奇．因為我覺得我如果要在工作上更進一步的話，我最好還是去了解這些問題的原因，因此我決定回學校去念書，但我選擇不是回去念資訊科系的大學部，我選擇是去考資工研究所．我還記得當時大部份的學校都會考資料結構，演算法，作業系統，計算機組織以及離散數學．我當時買了一堆書，一堆補習班的講義就開始念了．在念書的過程中也得到不少的收獲，比如作業系統裡提到了 CPU Scheduling 才知道電腦要做多工環境的概念，念了資料結構也才知道原來程式的效能是透過 Big O 來評估的．在那過程獲得不少心得，但可惜準備的時間太少還無法完全熟悉以及融會貫通，最後我用三個月的念書時間考到一家國立大學後段班的資工所．

在念研究所時，我已經 30 歲了，對自己來說算是項蠻挑戰的投資，在那段時間我到大學部去上課，作業系統，離散，資料結構，演算法等等，把這些基礎課目透過學校課程補起來，然後也念了物件導向，分散式系統與資料庫等課程，自己也蠻開心可以走到這一步．在畢業前，我收到了一間美國大學的入學許可，我申請到了電腦科學博士班，畢業一年後，我就前往美國念書．到了美國後，學校規定演算法和計算理論是必修，成績不達標準不能畢業，光是這兩個科目就讓我很辛苦，重修一次後才過關，也是因為這樣的辛苦，所以對電腦科學才有更進一步的認識．雖然最後沒能把博士學位完成，但還是覺得自己能走到這一步也是不賴了．在我大學剛畢業時，我可從沒想過自己能走到這樣的地步．

寫這篇文章時，我 40 歲了，在美國一家軟體公司上班，每天就寫著一些程式來改進公司的工具與產品．從現在回過看，在我 28 歲之前，連 Big O 是什麼都不知道，也不知道什麼是 Binary search，這十年來的變化就好像變魔術一樣讓自己的 IT 人生起了很多的改變．把自己的 IT 人生寫的很簡短，現在我有新的人生方向，但短期內還不會離開資訊業，就如同前面說的，這一切都是自己的選擇而造就自己的人生經驗，也希望這些經驗能提供其他年輕人做為參考．如果你認為我有值得讓你參考之處，歡迎你留言給我. ^_^

閱讀全文

#23 Coding 面試 Leetcode #73 Set Matrix Zeroes

我打算把以前遇到的一些在面試時遇到的一些特別經驗或感想記錄在這電腦科學筆記裡，一方面，在面試時會遇到的問題大部份都是基礎的電腦科學題目，二方面也把這些過程記錄下來，當做是一種紀念吧!

在美國的軟體行業裡，要做 coding 面試算是很正常的事情，而這些 coding 面試大部份都是資料結構和演算法的內容，所以都是大學的必修課．但其實有許多題目還真的不是光念過課本就能想的到，那些題目還真的需要多練習．在市面上有許多網站會列出一些常見的面試考題，而我之前最常去的網站就是 Leetcode. 這網站不僅記載了許多考題，而且還有 online judge 可以直接測驗你的程式碼是否正確.

今天來聊聊這一題，在 Leetcode 網站上的第 73 題．我被問過一模一樣的題目，面試者連改都沒有改，而這一題也讓我體會到另一種空間複雜度的境界．

第 73 題的題目是指，給你一個 m x n 的矩陣，如果在第 (i,j) 的位置上出現 0 時，就要把 row i 和 column j 的元素全部變成 0．剛看到這個題目，覺得不會很難．最直覺的方法是你可以宣告兩個 Array 或 List 來記錄那些 row 和 column 裡面有 0 ，最後再依據 Array 或 List 的內容把相關 row 和 column 的內容變成 0．如果你是這樣想的，其實這方法也沒什麼不好，只是要多浪費一點空間，因為另外宣告了額外的 Array/List 來記錄那些 row, column 有 0 的元素存在，而且 Array/List 的大小會根據矩陣的大小而改變，因此在空間複雜度上就不是 constant 了，而是 O(m+n)．如果這時候面試官沒繼續要求的話，那基本上就過關了．但生活中有時很難會如此順利，面試官很可能會要求你在空間複雜度上做到 constant space．也就是說你可以用其他的空間，但是這些額外的空間不能隨著矩陣大小變化而改變．

既然是這樣規定的話，這題目就真的變得有相當的難度了．我自己在做這題目時也無法在五分鐘之內想到好的解答．為什麼是五分鐘呢 ? 因為一個面試通常是一小時，其中做 coding 考試的時候大約有三十分鐘，所以在五分鐘之內沒有想出正確答案的話，那就很難可以在剩下的時間把程度寫完在白板或電腦上．
後來，我參考了網路上其他人的解法，我找到一個蠻好的解法．基本上，這個解法要宣告兩個基本的變數，這是  constant space，而它把每個 row, column 有 0 的資訊直接記錄在輸入矩陣之中，因此，根本就不需要用到非 constant space 的空間了．

如果你用心把這個解法看完的話，你一定也會覺得這方法實在太妙了，而且保證你對空間複雜度的應用會有更高一層的體會．原來把 input parameter 的空間拿來做為暫存空間，也是一種省空間的好方法．

閱讀全文

#22 資料庫的資料實體儲存單位 Page - 3

在來延續上一篇文章 (#21  資料庫的資料實體儲存單位 Page - 2) 的內容．在上一篇的文章中看到了如果沒有 page 的概念時，資料庫引擎有那些可行的方法來在硬碟上管理資料，從上一篇文章中，你看感受到空白空間的處理與以及資料的定位並不是很方便．於是在階層管理的方便性上多加了一層 Page．

在一般市面上常見的資料庫產品中，Page 的大小都大約在幾Kb之間，類似於作業系統的儲存單位大小．所以，一個資料庫可能會包含一個或多個資料庫檔案，而每一個資料庫檔案都會包含多個 Page．

我們再看看如何用 Page 來管理資料．如上一篇文章的情況，資料有可變長度與固定長度兩種．固定長度的情況是比較單純好處理，可以參考下圖:

上圖是某一個 Page 的示意圖，由於每筆資料都是固定長度，所以每一個 Page 都可以儲存相同數量的資料筆數 (除了最後一個 page 可能因為資料筆數無法除盡，所以不一定有相同筆數)．在每個 Page 的最後面會留下一些小空間用來做為目錄式的記錄，所以可以從這小空間中可以知道這一個 Page 一共儲存了多少筆數的資料，同時也可以知道每一個位置是不是都有資料．以上圖為例，我們透過 delete 語法刪除了一筆資料，而這筆資料剛好是位在這個 Page 的第二個位置，所以可以看到在目錄式記錄上第二個位置是 False (boolean)，用一個 bit 就可以表達完成．所以，當有新資料要寫入時，資料庫引擎就可以讀取每個 Page 上的這目錄就可以知道那一個 Page 有多少的空間是可以寫入新資料的．因此，這種實作方式對 storage manager 的開發者來說相當簡單，而且空白空間也易於維護．

另一個情況是可變長度的資料．因為每筆資料的長度不見得會一樣，所以每個 Page 能放多少筆的 record 完全得視實際上每個 record 的長度來決定．在 Page 上安排位置時，在 manifest 那段小空間裡所放的內容就會有點差異了，如下圖:

由於資料非固定長度，所以在 manifest 上每一個位置都會有一個 pointer 指定到那個資料的位置，同時也會指出來空白空間是從什麼位置開始．上圖的狀態等於是資料經過了一些 update/delete 指令後才會出現的情況，因為每筆資料之間還是有空白空間的存在，但那些空白空間不會被資料庫引擎所使用，因為管理上實在太麻煩了，所以當有一筆新資料要寫入到這個 Page 時，資料庫引擎只會找這個 Page 上的空白空間 (灰色區塊)，只要有足夠的空白空間，那麼新資料就會被寫進來，同時更新 manifest 的相關 pointer 內容．

以上的內容是資料庫引擎對在一個 Page 內針對固定長度與可變長度資料的存取安排，所以你就可以想像的到當一個資料庫運行了一段時間之後，零零碎碎的空白空間一定是散落在資料庫檔案的各角落，而那些零零碎碎的空白空間是不會被資料庫引擎所使用．所以，資料庫的產品通常都會一個功能把這些零零碎碎的空白空間給消除，也就是讓資料靠的更緊密些，讓儲存空間可以在容量上得到發揮更好的效果．

閱讀全文

#21 資料庫的資料實體儲存單位 Page - 2

延續上一篇文章 (#19 資料庫的資料實體儲存單位 Page) 的內容，在這篇文章裡，我們來談談有關資料庫的實體儲存結構．所謂的實體儲存結構是指資料放在硬碟中的情況．

首先，我們先來看看一個很簡單的結構，資料長度是固定的．這種情況在前面的文章有提過．因為長度都是固定的，所以每筆資料的長度便可以固定，這樣好處是在於方便計算也方便存取．

另一種情況是資料長度不是固定的，這種情況在前面文章也有提過．因為長度不是固定的，因此必須要想一個方法把不同欄位的資料做一個區隔，這樣在讀取資料時才知道什麼情況下是資料欄位的終點．在實體資料儲存時，有兩個方式可以來達成這種目的．第一，在每個資料欄位之間都用一個特殊符號隔開來，長相如下:

上圖是用一個 # 來當特殊符號，這是很笨的例子，但只是方便說明用．在資料寫入到硬碟時，資料欄位之間會透過特殊符號做為間隔，而在讀取資料時，資料庫引擎也知道該如何處理資料了，而這樣的好處就是非常直覺且簡單，並不會浪費多餘的硬碟空間，缺點就是會浪費較多的資料讀取時間，例如我只要讀取表格裡欄位五的資料，那麼資料庫引擎就必須從欄位一讀取過四個特殊符號才能取得欄位五的資料．從前面文章中，你應該有學到一個精神就是當你對時間不滿意時，那就犧牲點空間去換取時間．所以可以把上述的儲存方式最一點小改良如下圖:

在整筆資料的最前面加上一個導覽式的目錄，裡面存放著每個資料欄位開始的位址起點，所以每筆資料有五個欄位，因此目錄裡就有五個 pointer，而每個 pointer 的內容就是一個硬碟位址用來記得資料的起點．所以當資料庫引擎要讀取欄位五的資料時就不用從欄位一開始讀取了，可以透過目錄裡的第五個 pointer 就可以直接找到欄位五的位址．

以上所說的方法都是很直覺且自然的，但我們來想像一下如果進行資料更新或刪除時會發生什麼事情?

先針對資料更新來討論，如果把欄位三的內容更新成較小的內容時，此時影響不大，只是欄位三後面會有空白空間，而我們該討論的是該不該保留這個空白空間．因為這裡討論的是每個資料欄位都有一個 pointer 會對應到資料，所以若我們保留空白空間的話，可以讓資料少了些移動，但也可能會浪費許多細小的空白空間．如果此時的情況是欄位三的內容被更新成比較大的內容時，例如更長的字串，接著就面臨到沒有足夠的空間問題了，解決方法會有很多種，也許比較簡單的是把整筆資料搬移到足夠大的空間，好讓欄位三可以容納下新的內容，同時前面的五個 pointer 的內容也需要一起改變．如果是刪除呢? 那就更單純了，只要把整筆資料在刪除或是做一個已刪除的 flag 即可．所以，從這裡我們可以看到，其實在更新時所面到的挑戰是比刪除的挑戰還要大很多．而且不論是那一種更新 (內容變多或變小)，都會遇到空白空間管理的問題．

所以我們可以發現，當資料庫的資料筆數越來越多時，讓資料庫引擎直接去對每一筆資料做管理時，其實是有點不方便的．因此，我們需要在這中間多一層實體儲存的管理單位，而這管理單位就是我們前面文章中所介紹的 Page．這種感覺就有點像一個國家不可能直接管理到每一個家庭，中間一定會有省，市之類的層級來做為分類，以便於管理上的應用．而 Page 也就是這樣的感覺．

閱讀全文

#20 The Power of Ten - 撰寫可靠軟體的思維

標題為 The Power of Ten - Rules for Developing Safety Critical Code 的文章刊登在 IEEE Computer 2006 年 6 月的月刊中，作者是位在 NASA JPL 實驗室的研究科學家，同時也是位學者和工程師．這篇文章可以在 http://spinroot.com/gerard/pdf/P10.pdf 看到．

若以武功修練來比喻的話，這篇文章就像是一個得道高人所寫下來的內功心法，他把自己在 JPL 實驗室工作的多年 C 語言工作心得濃縮成十項重點，作者也為每一個重點留下說明．雖然這一篇文章是將近十年前的文章了，但它的參考價值極高，而且我相信許多資深的軟體工程師幾乎都會同意作者所寫的內容．

其中有幾點並非在所有的程式語言中都會碰的到，尤其是跟記憶體管理有關的工作．以現在一般商業應用裡最常見的 C# 和 Java 語言都應該有其 runtime 環境的設計，所以記憶體管理的工作並不在程式設計者上，而是在開發其語言的公司上，所以這樣等於你把記憶體管理的工作交給其他人來處理了．我想這對 NASA 來說應該是不太能接受的事情，畢竟能打上太空的物體都是極為龐大的資金，因此 NASA 應該是不可能用類似像 C#, JAVA 這般的語言來打造火箭或衛星要用的軟體．回歸最基本的本質，用 C 應該是相當原始且基礎了．所以，在那篇文章裡，作者談了一些與 C 語言有關的準則．在這裡我不談特定語言，我們來看看其他的通用的準則．

1. Restrict all code to very simple control flow constructs – do not use goto statements, setjmp or longjmp constructs, and direct or indirect recursion.

這一點應用也沒什麼好再做說明的了，就是這樣，沒有 GOTO，沒有 recursion．所以在前面的文章裡，有些程式的寫法我提供了 recursive 和 iterative 的寫法，那時也提過 iterative 的寫法是比較好的．

2. All loops must have a fixed upper-bound. It must be trivially possible for a checking tool to prove statically that a preset upper-bound on the number of iterations of a loop cannot be exceeded. If the loop-bound cannot be proven statically, the rule is considered violated.

你想想看你寫程式時做到了這一點嗎? 你有沒有做過 while (true) 之類的語法呢 ?

4. No function should be longer than what can be printed on a single sheet of paper in a standard reference format with one line per statement and one line per declaration. Typically, this means no more than about 60 lines of code per function.

這是一定要的．若以 OO 的角度來看，有一個 function 能寫的很長，我都會懷疑程式碼一定在某些地方會有重覆功能的現象．

5. The assertion density of the code should average to a minimum of two assertions per function.

每個 function 平均來說至少有兩個檢查．這邊的檢查就是要防止一些不尋常的參數發生．比如你今天要寫一個加法，接收兩個 int ，如果傳入的參數是負數，那你的程式能處理嗎? 或是加起來的數字 overflow 了，你的程式能處理嗎?

6.  Data objects must be declared at the smallest possible level of scope

這應該是很直覺的想法，因為你不需要把不相干的資料物件提供給不需要該資料物件的程式碼．

7.  The return value of non-void functions must be checked by each calling function, and the validity of parameters must be checked inside each function.

這應該是每一個程式工程師要做的，只要呼叫的參數皆符合要求，那麼回傳值也需要檢查，同時還要注意是否有可能會產生其他的 exception ，都要記得做好 try catch 的反應動作．

10. All code must be compiled, from the first day of development, with all compiler warnings enabled at the compiler’s most pedantic setting.

最後這一點就是在考驗你們的專案裡有沒有良好的軟體工程流程以及 build system．工程師們一旦把程式碼 check-in 之後，所有的程式就應該要重新編譯，然後所有的測試案例都要執行．這樣才能即早發現問題，即早解決．

閱讀全文

#19 資料庫的資料實體儲存單位 Page

在上一篇文章中提到了有關資料庫 Storage manager 一點點的資訊．因此，這一篇文章就來談談更基礎的東西，叫 Page．它是什麼呢 ? 它就是 Storage manager 在處理儲存資料上的一種邏輯格式，也就是每個邏輯儲存空間的大小．這樣說可能還不好了解，讓我來直接舉個例子．資料庫引擎中有一個管理員叫 storage manager，它是負責資料儲存和讀取用，也就是說，今天使用者發出一個請求如 select * from table123，那麼這個命令就會經由資料庫引擎裡各式各樣的管理員來做語法確認解析，來做語法最佳化，然後可能還會經由其他管理員的檢查，最後才會到 storage manager，而 storage manager 負責的工作就是到磁碟機上正確的位置點，把資料讀取出來然後再回傳給呼叫它的管理員，最後資料就一直這樣被回傳到使用者端．因此，storage manager 就是負責找到資料在硬碟上的那個地方，然後進行資料讀寫．所以，你現在可以知道 storage manager 的工作是非常底層的．

那 Page 和 storage manager 又是什麼關係呢 ? Page 是資料儲存空間的一種單位．依不同的產品設計，Page 的大小可能不同，如 Microsoft SQL Server 的 Page 設計成 8KB. 所以，如果你的資料庫檔案設定為 8000KB，那就表示你這個資料庫檔案就有 1000 個 Page．然後這一千個 page 並不是全部都可以做為使用者資料儲存的用途，因為需要有一些空間用來儲存資料庫的設定與變數等，但我們在此先不討論這些系統所需的空間，我們把 1000 個 page 視為都是可供使用者儲存資料用．而 Page 設計的概念就是我們以前說過的 Linked List 概念，所以 Page 裡會有一個 pointer 指向下一個 Page 在那裡，因此，相鄰的 Page 在實體位址上不一定要在隔壁，他們可以分別位在硬碟裡前後不同的位置上．

所以，假設你現在要寫入一筆資料到一個新的表格，也假設這個表格只有一個欄位，其 data type 是 char(1000)，而且這個欄位是 primary key．當你寫入第一筆資料 "1111" 時，這筆資料就會被記錄在 page 1 的最前面，如果你寫入第二筆資料 "2222" 時，這筆資料也會被記錄在 Page 1 且在 "1111" 的後面，如下圖所示:

在上圖中，假設寬度剛好是 1000 字元，所以你會到 "1111" 在第一行，由於 data type 是 char，所以後面有 996 個空白，而第二行是 "222"，後面接著是 996 個空白字元．如果你繼續寫入更多的資料時，第一個 Page 看起來就會如下:

如果你再繼續寫入資料的話，後面的資料就會從第二個 Page 開始寫．所以 storage manager 在讀取這表格的資料時就會從這個表格的第一個 page 開始讀資料．

假設，此時你要寫入 "4567" 到這個表格中，因為這個欄位是 primary key，所以預設上來看，字元的順序就是實體資料要擺放的順序，因為 "4567" 必須放在 "4444" 和 "5555" 之間．但由於這一個 Page 的空間已被佔滿了，因此 storage manager 只好做一個 page split 的動作，也就是把一個 Page 拆成兩個 Page ，然後再寫入資料．

如果用 List 的動作來看，這就是在一個 List 中插入一個元素的動作．用 storage manager  的角度來看，它要先尋找一個完全沒用過的 Page ，然後將需要分開的資料搬到新的 Page 上，最後再更改 page pointer 位置來讓新 Page 的順序能安排在其中．這個動作並不是一個單純的動作，花費的成本還不小，從這裡就可以了解到，當我們做 insert 或 update 資料時，如果沒有安排好的話很可能就會造成大量的 page split 導致硬碟會很忙碌而形成效能上的瓶頸．

當我們討論到資料庫的讀寫效能時，Page 是一個很好的對象讓我們知道一份資料被讀取時一共讀了多少個 Page，這也就是代表了資料庫引擎的效能．由此可見，對資料庫引擎而言，這是多麼重要的基礎考量．

閱讀全文