如何用JDK8實作一個小型的關聯式資料庫系統

自我介紹

午安大家好,
很高興和大家見面,我叫 kishida naoki
我在日本的福岡做自由工作者。
這次是我第二次到台灣來。


我在twitter上的帳號叫做kis,
https://twitter.com/kis
我也有在寫部落格,除了 Java 8 以外也寫各種主題。
http://d.hatena.ne.jp/nowokay/
雖然內容都是日文,但通常也會放一些程式碼,所以有機會可以上來看看。


不知道大家有沒有聽過福岡?
在日本的西邊,九州的北邊,大概這附近。
九州大概跟台灣一樣大,福岡在那裡面的位置大概就像臺北一樣。
從福岡到東京跟從福岡到臺北,所需要的時間大概差不多。
大約兩個小時左右的飛機就可以到了。


今天我要介紹我如何使用 Java 8 來自製資料庫。
首先,我會先介紹自製資料庫的功能大概,
接下來會介紹如何實作,
這次我的內容不會介紹的太精細,重點會比較放在 Java 8 使用到的功能以及其他程式庫。

自製的資料庫

關於自製的資料庫,主要用途是為了學習。
為了想知道資料庫的運作方式,所以自己實作看看。
畢竟要理解原理的話,最快的方式還是自己動手做一遍。
我做的資料庫是關聯式資料庫,
但是因為太麻煩了所以沒有資料形態。
另外它是單執行緒的應用程式,
因為如果寫成多執行緒的話,實作上會在變得更複雜。
也沒有提供網路通訊存取。
在記憶體上運作,也不會存取到檔案系統。
原始碼我有放在 github,有興趣的人可以到上面下載來試試看。


關於資料庫的構造,
像這樣子,每個項目會在後面一個一個介紹,
首先使用 Parser 將 SQL 轉換成抽象語法樹,也就是 AST。
然後透過 Planner 將抽象語法樹變成邏輯執行計劃,
產生邏輯執行計劃會被最佳化,例如使用 index。
然後 executor 執行器依照計劃將資料讀取並執行。
另外 executor 也會管理 transaction 來達到 ACID 的特性。


一般資料庫除了上述的功能以外,會有排程管理多執行緒,
存取管理來做應碟上的資料讀寫,快取管理來作暫存,
日誌管理來做 log 的更新以防止系統出現錯誤時,資料消失的狀況。
Parser 會將字串表示的 SQL 剖析,製作 AST 抽象語法樹。
抽象語法樹就是用樹狀結構表示語法。
例如,將這個 SQL 變成像這個樹上面的物件。
這使用了 JParsec 來實作,稍後我會在針對 JParsec 做介紹。


Planner 取得 Parser 產生的抽象語法樹後產生邏輯執行計劃,
邏輯執行計劃就是將查詢的處理順序,用關聯式代數(Relational Algebra)表示的東西。
關聯式代數是構成關聯式資料庫基礎的數學。
將邏輯執行計劃透過最佳化,節省不必要的處理,決定要使用的 index,製作物理執行計劃。
在這邊使用了規則為基礎的演算法。
一般來說,資料庫會在此時決定儲存媒體的存取,以及快取的使用方式。
規則為基礎的演算法,用來設定好規則使用 index。
但是這種方式難支援複雜的查詢,而且依照資料的分佈狀況,有可能會造成效率不好的狀況。
所以一般來說,很多資料庫都會使用 cost based 的演算法。


最後會依照物理執行計劃執行。
這個時候也會顧及 transaction 來執行,
transaction 最主要是要滿足 ACID 特性,
Transaction 的實作使用了 MVCC(multi version concurrency control) 的方式。依照 Transaction 不同,對資料分別給予不同的版號。在做新筯,更新時給新的資料版號,變更及刪除時將舊的資料暫時保存到其他地方。
用這樣的方式來達到還沒 commit 的資料不會被其他 transaction 看到。


例如 A 開始了一個新的 transaction,假設這時的 transaction 序號是十,資料庫已經提交到了九號的 transaction。我們可以看到比自己早提交的 transaction。
這時如果 A 新筯了資料,我們會在新資料上設定尚未提交的標記,因為 transaction 尚未結束,所以其他 transaction 並不能看到剛剛新筯的資料。
當 A 結束 transaction 前,如果 B 開始了新的 transaction,那麼這個新的 transaction 會是十一號。transaction 只能看到之前完成的 transaction 的資料,因此他只能看到序號為十號的資料。
假設現在 A 完成,那麼剛剛新筯的資料便會被設定成交易序號十一號。因為 B 只能看到十號之前的資料,所以便會看不到剛剛 A 新筯的資料。

Java8

接下來則是一一介紹實作過程中使用到的 Java 8 的功能。
這次主要使用了 lambda,stream 和 Optional。
lambda 非常便利。
這次為了 parser 使用的 JParsec 雖然在 Java 7 就可以使用,但是有了 lambda 後就變得非常好用。
另外,為了 SQL 的處理,很常會使用物件的 instanceof 來判斷型別,這邊也自己寫了一個程式庫,可以利用 lambda 來很簡單的達到。
這個程式庫有點像是 Scala 的 pattern match 的簡化版。在 Java 8 也可以輕鬆的做出這種控制流程的程式庫。

Stream

Stream 也帶來非常多好處。
資料庫的處理時,很常會將List 中的資料處理後產生新的 List。
例如有個叫做 fields 的 List,要對所有值執行 eval 的方法後放入一個新的容器,這時候程式碼如下。

List<Value> result = new ArrayList<>();
for(Field f : fields){
  result.add(eval(f));
}

如果用 Stream 便會像以下的效果

List<Value> result = fields.stream()
  .map(f -> eval(f))
  .collect(toList());

不用一直準備 list 然後使用 for 迴圈一直 add。


如果只有少部分地方要這樣就算了,因為這種類似處理非常多,所以使用 Stream 可以減輕很多負擔。
另外,在做 List 的所有元素是否都符合條件的判斷也變得非常容易。
例如有一個叫做 conditions 的 List,如果所有元素在使用 hasOr 後回傳 true 的話就 return,會像上面這樣的程式碼。


初始化 result, 使用 for 迴圈走過 conditions 的元素,如果 hasOr 方法回傳 false 的話就將 result設定為 false,等到 for 迴圈結束後檢查 result 的值如果是 true 的話再 return 。

boolean result = true;
for(Condition c : conditions){
  if(!hasOr(c)) result = false;
}
if(result) return;

如果用 Stream 便會像以下的效果

if(conditions.stream().allMatch(c -> hasOr(c))) return;

一行就可以了。
可以在 if 直接使用 allMatch 方法的結果。
另外也減少不必要的 result 變數,像之前這種寫法邏輯就有點複雜,是容易出現臭蟲的地方。
透過使用 stream 便可以減少一些邏輯上出錯的問題。

Optional

接著最重要的就是 Optional 了。
Optional是一個可以用來表示有沒有值的型別。 Scala 叫 Option,Haskell 上叫做 Maybe。


到現在為止,通常大家都會使用 null 當作沒有值得表示方式。如果忘記做 null 檢查,就會出現 NullPointerException。而且從程式碼型別上根本就分辨不出來,變數有沒有可能被指定成 null 的狀況。


例如,、BufferedReader 類別的 readLine 方法,當沒有資料可以讀時會回傳 null。在看 method 的時候只看得到它會回傳 String,所以你根本不會知道他有可能回傳 null。這時你就必須認真看文件。只是平常再寫程式時,有時並不會將文件寫的非常完整,或是忘記寫。


可能大家都會記得寫,但像我自己就常常偷懶沒寫。這時候就容易發生忘記檢查 null,而出現 NullPointerException。使用 Optional 就可以減少這類 NullPointerException 的狀況。


那麼,簡單說明一下 Optional 的使用方法。


要建立 Optional 要使用 of 這個類別方法。只是這時候如果傳入的是 null 的話,會產生 NullPointerException,所以一定要確保傳入的參數不為 null 時才可以使用。
如果值不知道是不是 null,那麼要使用 ofNullable,我自己覺得照理上這才應該叫 of,有點可惜。
如果要表示沒有值,可以使用 Optional 的 empty 方法。


要從 Optional 取得值得最簡單的方法,就是使用 get。只是如果裡面沒有值的話,會丟出 NoSuchElementException,這樣的話使用 Optional 會變得沒有意義,請儘量不要這樣使用。
orElse 方法的話,如果沒有值時會回傳 defaultValue。
如果要對 List 做統計,而 defaultValue 的計算可能會花一些時間,可以使用 orElseGet。因為 orElseGet 要傳入一個型別為 Supplier 的參數,這邊直接使用 lambda 式。


如果這樣使用,會在 Optional 沒有值的時候才會執行 expression 後回傳值。像這樣只有在需要時才執行的動作叫做延遲執行。


有時候會想要 Optional 有值得時候才會想要執行某些動作。
這有兩種做法。
第一種是判斷有沒有值,
這時會使用 isPresent 方法。
isPresent 方法如果 Optional 有值時會回傳 true,沒有值的話會回傳 false。
所以可以利用 if 來判斷回傳值。在這邊有呼叫 length 方法,如果沒有用 isPresnet 保護值的話會發生 NoSuchElementException ,但是這樣並不是 Java 8 的風格。

Optional<String> ostr = Optional.ofNullable(str);
if(ostr.isPresent()){
  System.out.println(ostr.get().length());
}


ifPresent 方法就比較像 Java8 風格了。
ifPresent 只有在有值時會執行傳入的式。參數的型別是 Consumer,但是可以像這樣用 lambda 來寫。這樣的話當 ostr 有值時,println 才會執行。

Optional<String> ostr = Optional.ofNullable(str);
ostr.ifPresent(s -> {
  System.out.println(s.length());
});


要將Optional的值轉換成其他值,可以使用 map 或 flatMap 方法。
map方法會傳入回傳普通值的 lambda 式,然後就會回傳包著那個值得 optional。如果回傳的值是 null,那就會變成 empty。所以就不用擔心 NullPointerException, 可以一直串下去。
flatMap則是傳入回傳Option的 lambda式,然後他就會回傳剛剛的 Optional。
在這邊的 map 方法使用 method reference 的方式,傳入處理動作。

Optional<String> ostr = Optional.ofNullable(str);
ostr
  .map(String::length)
  .ifPresent(System.out::println);


當值符合條件,才要處理時,可以搭配 filter 方法。
如果條件不符合會回傳 empty 。

Optional<String> ostr = Optional.ofNullable(str);
ostr
  .map(String::length)
  .filter(len -> len < 5)
  .ifPresent(System.out::println);

Optional 像這樣,跟 map 還有 filter 之類的方法搭配處理時,非常有效果。
這時候 Optional 會保證map, filter 和 ifPresent 裡面的值不會是 null,所以可以不用擔心NullPointerException 來寫程式。


也就是說 Optional 可以隔離有 null 的世界和沒有null 的世界。在 Optinal 中可以寫出和 null 無緣的程式。
像我這次的實作過程中,常常會有值不存在的狀況,但透過使用 Optional 的方式,達到幾乎可以不用在意 NullPointerException 的情況下寫程式。
Optional 雖然還要多打一些字,但是可以讓人寫的比較安心。
在 Java8 中請記得會出現 null 時就要利用 Optional。

Lombok

最後介紹一下我使用到的程式庫。
第一個是 lombok
lombok 可以把一些 Java 很繁雜的程式碼減少。
http://projectlombok.org/


例如比較常見的 setter/getter。
Java 的類別中常常會有很多 setter/getter。
雖然可以用 IDE 幫我們產生,
但是看起來一長串很煩,改也很麻煩。

class Foo{
  String message;
  publilc void setMessage(String message){
    this.message = message;
  }
  public String getMessage(){
    return message;
  }
}


使用 lombok 可以寫成這樣
清爽許多。

class Foo{
  @Setter @Getter
  String message;
}


其他也有幫忙產生預設建構子的@NoArgsConstructor,產生所有成員變數都要設定的建構子的@AllArgsConstructor。產生 toString 的 @ToString,產生 equals 和 hashcode 的@EqualsAndHashCode 等等,透過這些可以讓程式碼簡潔很多。
這種自動生成程式碼內容的程式庫,直覺上會覺得跟IDE不相容。
例如自動產生的方法如果不能IDE偵測到而出錯,就會讓人不太舒服。
但是 lombok 會幫我們對應 IDE 所以不用擔心。

JParsec

另一個是在處理 SQL 時很重要的 JParsec。
http://jparsec.codehaus.org/
JParsec 是用來製作 parser 用的程式庫,也就是 parser 產生器。
原本是 Haskell 的 Parsec 移植到 Java
Java做 parser 可以使用 javaCCAntlr 這類程式庫,但是這些東西需要 Java 程式碼以外的語法定義檔,也必須特別編譯。
JParsec使用 Java 來定義語法,不需要額外的檔案和編譯。


例如 delete 的語法定義像這樣。
這邊不會講的太細,首先有 delete, 星號,但是這個可以省略,接著是 from,然後是 identifier,接著 Where,這也是可以省略,像這樣的定義。然後 parse 過後的結果產生 ASTDelete 物件。

public static Parser<ASTDelete> delete(){
  return Parsers.sequence(
    terms.token("delete").next(terms.token("*").optional())
            .next(terms.token("from")).next(identifier()),
    where().optional(),
    (id, w) -> new ASTDelete(id, Optional.ofNullable(w)));
}


在這裡看到 identifier和 where ,是我在程式中定義的語法。
像這樣組合語法定義,產生更大的語法就是 JParsec。
可以一小部分一小部分測試 parse,跟JavaCCAntlr 比起來可以一邊嘗試一邊寫,非常方便。


JParsec 雖然在 Java SE 7 就可以使用,那時用匿名類別所以非常不好寫,寫起來人看了會很吃力。但是到了 Java 8可以使用 lambda後就變得非常好用,看起來也不再吃力。
如果需要小型的語法定義的話,非常推薦此程式庫。

總結

最後總結一下,
手動製作資料庫非常有幫助,尤其接著再接觸 MySQLPostgreSQLOracle 的資料庫時,就能大概知道他們到底在做什麼。也比較能了解 SQL 的處理過程,讓自己可以寫出效率更好的 SQL


Java8 很方便,回不去 Java7 了。
Optional應該多加利用,在 Java8中如果出現 NullPointerException 就太失敗了。
使用 lombok 可以從又臭又長麻煩的程式碼中解脫。
JParsec 的話會讓你不知不覺的完成結構很大的語法定義,很有趣。