Kenny's Blog

這是Kenny's technology blog,歡迎交流_(:3」∠)_

0%

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 用在實際生產環境上,不過如果是開發環境測試就很方便了!

閱讀全文 »

今天試著使用 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 不保證充分利用

具有相同的 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 上,而且有積極維護中,非常不錯。但是可想而知它的這個工具對簡體中文分詞會比較準確,繁體中文雖然用這工具也還可以,但是有一些像是台灣用語就比較難斷得很好。

閱讀全文 »