CI/CD (Continuous Integration/Continuous Deployment 或是 Continuous Delivery) 這個概念近年來在業界也是越來越火紅，一部分也是因為敏捷式開發的風潮帶動 CI/CD，其實講白了就是為了兩個字：方便，CI/CD 就是減輕人工的負擔，使得一切都能自動化實現。實現甚麼事情呢？我們來一個一個來看名詞解釋：

現今大部分常見的應用，例如 Web、APP，首先第一步可能都會需要使用者去註冊，最常見的話是信箱作為帳號，然後使用者設定他記得起來的密碼。而近年來其實常常會在 Web、APP 看到雙因子認證的選項，或是會主動詢問你需不需要開啟雙因子認證，所以到底什麼是雙因子認證？

開場先來個感嘆，這年頭要把精力全部花在寫程式好像是一件不太可能的事情了，做後端現在都要多種能力，要會好多種不同語言的 Web Framework，還需要可能會多種不同的資料庫，又分 RDBMS 跟 NoSQL、還有快取型的資料庫，此外，可能還要學會如何寫基本 script 檔，例如 Windows 的 bat 檔案、Linux 的 bash 檔，再來佈署應用程式又是一大學問，從一台主機架設，到 Docker 容器化佈署，再到現在很夯的 Kubernetes 的容器管理平台的佈署。技術債學都學不完的～

minikube 是一個輕量級的工具，可以讓開發者在本機上輕易架設一個 Kubernetes Cluster，透過單一 Cluster 讓我們可以在本機上學習各種指令操作。minikube 運作原理就是會在本機上建立一個 virtual machine，並且在這 VM 建立一個 signle-node Kubernetes Cluster，但通常不會把 minikube 用在實際生產環境上，不過如果是開發環境測試就很方便了！

kubectl 是用來操作 Kuberbetes 的 command-line tool，可以透過此工具來下指令，例如：deploy applications、管理 cluster 上面的 resources，還可以查詢 logs 等等功能。

今天試著使用 PostgreSQL 搭配各種 Transaction Isolation Level 加上 JMeter 模擬同時多個 Request 造成 Race Condition 的情況，只有自己親手試過才知道 Race Condition 的可怕！！

之前有介紹到 RDBMS 的 Isolation Level 總共有四種以及每個隔離層級可以預防的 Race Condition 的程度在哪。而根據不同的資料庫的底層設計，分成 SX LOCK 跟 MVCC，它們各自實作這四種 Isolation Level 又是如何設計的？今天就來介紹這些～

這次內容依舊參考，[TritonHo 大神的簡報](https://github.com/TritonHo/slides/tree/master/Taipei 2019-04 course)，好教材！

今天介紹如何安裝 Redis 資料庫，準確來說它是一種 NoSQL，專門存放 key-value 的資料庫，在實務上最常拿來作快取的用途的資料庫，因為它讀取的速度非常快，之所以那麼快是因為它是在先把資料存在 memory 裡面，才能存取如此得快。

因此其實在 Redis 的預設設定，它會自動將記憶體資料，保存到硬碟的 dump.rdb 檔案。當 redis 重開時，它會將硬碟 dump.rdb 資料拷貝到記憶體中。

Hashing 定義

是一種資料儲存與擷取之技術，當要存取 Data X 之前，必須先經過 Hashing Function 計算求出 Hashing Address (or Home Address)，再到 Hash Table 中對應的 Bucket 中存取 Data X，而 Hash Table 結構是由 B 個 buckets 組成，每個 bucket 有 S 個 Slots，每個 Slot 可存一筆 Data

=> Hash Table 大小 = B * S 筆

Hashing 優點

1. 搜尋 Data 之前，無需事先排序過

2. 再沒有 Collision 情況下，Search X 之 time 為: O (1)，與資料量 n 無關

3. 保密 / 安全性高，在不知道 Hashing Function 下，很難取得 Data

4. 可作為 Data 壓縮之用途

   例如：Unix 之 password 採用一對一，不可逆之 Hashing

何謂 Collision (碰撞)？

不同的 Data，例如 (x,y)，經過 Hashing function 計算後得出相同的 Hashing Address 稱之，也就是 H (x) = H (y)。

何謂 Overflow (溢位)？

當 Collision 發生後，且對應的 Bucket 已滿，則稱為 Overflow

Collision 與 Overflow 比較

1. 有 collision 不一定會 overflow
2. 若每個 bucket 只有 1 個 slot，或是只能放一筆 Data，則 Collision = Overflow

identifier density 與 loading density

令 t 為 identifier 是 Hash table 裡面的總數，n 為使用 identifier 個數，B * S 為 Hash Table size

則：

1. $$
   identifier, density, = \frac{n}{t}
   $$

2. $$
   loading, density,(負載密度) = \frac {n}{B * S}
   $$

Note：若 load density 越大， 代表 Hash Table 利用度高，但相對 Collision 機會也大

Hashing Function Design 雜湊函數設計

好的 Hashing Function 設計，要滿足下列三個 criteria：

1. 計算宜簡單，不要過度複雜
2. Collision 要少
3. 不要造成 Hash Table 局部儲存之情況，要夠均勻才好

Perfect Hashing Function

此函數保證不會發生 Collision

Uniform Hashing Function

n 個 Data 存入 Hash Table 之 B 個 Bucket 時，每個 Bucket 內之 Data 個數大約相等，即 n / B，則此函數為 Uniform (均勻的)

常見的 Hashing Function 設計

Middle Square

將鍵值平方後，取中間適當位數作為 Hashing Address

例如：鍵值 = 8125，平方後， = 66015625

取中間三個位數，156 作為 Hashing Address

Mod (or Divide) 取餘數

H(X) = X % M

M 最好滿足：

• 質數 (除盡 1 和除盡自已)
• M 不宜為 2 (求得的位址僅有 0 或 1，collision 的機會很大)

Folding Addition

將鍵值切成幾個相同長度之片段 (P1~Pn)，再將這些片段加總，即得 Hash Address

而相加的方法有兩種：

• shift (位移)
• bounding (邊界)

例如：x = 12320324111220

切成這樣：

P1 = 123

P2 = 203

P3 = 241

P4 = 112

P5 = 020

1. shift 作法

   將 P1~Pn 相加 = 699

2. bounding 作法

   偶數的片段反向，所以：

   P2 = 302

   P4 = 211

   再加總 P1~Pn = 897

Digits Analysis (位數值分析)

適用於資料事先知道之情況，分析每個資料再不同位數之值域分布情況，若分布很集中，則捨棄該位數，若散亂，則挑選，挑出之位數組成 Hashing Address

拿電話號碼為例：

02-7415089 => 158

02-7434079 => 347

02-7424139 => 243

02-7458069 => 586

02-7473029 => 732

根據以上的位數挑出三個數字的 Hashing Addrss

Overflow 處理方法 (重要)

Linear Probing (線性探測)

當 H (x) 發生 overflow 的時候，則探測 (H (x)+i)% B，B 為 Bucket 數，i = 1,2,3,…,B-1，直到有 Bucket 可存 or Table 全滿為止

優點：

1. 簡單、易於實施
2. 保證 Table 空間可以充分利用

缺點：

容易發生 Primary Clustering 現象，造成 Search/Insert/Delete X 等時間大幅增加之問題

Primary Clustering 意思：具有相同 Hashing Address 之 Data 容易占用相鄰的 Buckets 存放，形成群聚現象

Quadratic Probing (二次方探測)

當 H (x) 發生 overflow 時，則探測
$$
(H(x)\pm i^2)\text{ % B}
$$
或是
$$
(H(x)+ i^2)\text{ % B}
$$
B 為 Bucket 數目，i=1,2,3…,[B/2]，直到有 Bucket 可存，或探測位置都滿，無法存入為止

優點：

解決 Primary Clustering Problem

缺點：

1. 有 Secondary Clustering Problem，因為具有相同的 Hashing Address 之 Data，它們的探測軌跡均相同，後來進來的 Data 仍需花大量時間去探測先前 Data 已經探測的位置，才能找到可用的 Bucket。
2. Table Space 不保證可以充分利用

Double Hashing

令 H1 為 Hashing Function，當 H1 (x) 發生 Overflow 時，則探測
$$
(H1(x)+i\times H2(x))\text{ % B}
$$
B 為 Bucket 數目，i 從 1,2,3,…,B-1，H2 (x) 為探測間隔 (Span)，通常形式為
$$
R-(x\text %R)
$$
R 為質數，直到找到空的 Bucket 或是探測位置皆滿為止

優點：

解決 Primary Clustering and Secondary Clustering Problem

缺點：

Table Space 不保證充分利用

Chaining or Link List (鏈結串列)

具有相同的 Hashing Address 的 Data 均置入同一個 Bucket 去，而 Bucket 內之 Data 彼此透過 Link List 結構串連在一起，而這種情況就作 Closed Address Mode。

其他的 Overflow 處理方法是 Open Address Mode。

分析：

最差之 Search Time in chain 是 O (n)，但如果串列裡面結構改用 AVL Tree、R-B Tree 之結構去作，則改善時間為 O (logn)

Rehashing (再雜湊)

提供一系列的 Hashing Function H1~Hm，當 H1 發生 Overflow，則改用 H2，以此類推，直到找到 Bucket 可存，或 Hashing Function 用完為止。

最後最後！請聽我一言！

如果你還沒有註冊 Like Coin，你可以在文章最下方看到 Like 的按鈕，點下去後即可申請帳號，透過申請帳號後可以幫我的文章按下 Like，而 Like 最多可以點五次，而你不用付出任何一塊錢，就能給我寫這篇文章的最大的回饋！

今天要介紹的這個算是很知名的中文斷詞工具，這個是大陸人發明的工具，並且將其開源在 GitHub 上，而且有積極維護中，非常不錯。但是可想而知它的這個工具對簡體中文分詞會比較準確，繁體中文雖然用這工具也還可以，但是有一些像是台灣用語就比較難斷得很好。