Blog E

compile regexps only once (regexp.MustCompile) and use the compiled regexp for matching,
use buffered output (bufio.NewWriter, and don’t forget to Flush) when writing to output file,
don’t use fmt.Sprintf for simple string concatenation, if you want speed,
don’t use ioutil.ReadDir if you don’t need sorted filenames,

But the whole concept is strange for me: a one-process map-reduce should’nt use files for intermediate output, but channels.

最後，這邊有個 Golang 的 ETL 套件 (crunch)

行外人論 ePub 爲何很難普及

看一看各種電子書籍的格式之爭與為何 epub 很難普及的各種原因．

DeepText 介紹: Facebook 的文本理解引擎

Facebook 的語意理解引擎 DeepText 的介紹．

gØv summit 2016番外心得

透過參加 g0v summit 2016 來了解各國對於開放政府的概念．分別採訪了法國，印尼與尼泊爾來參訪的人，深入的了解各地開放政府的進度．

網站收集

喜歡看論文的不可以錯過 Golang 相關的論文．裡面有大量的有使用到 Golang 或是講解 Golang 相關的論文集錦．

有聲書/影片心得

本週專案 —–

這邊會寫一些我的Project 52的成果.

https://github.com/kkdai/maglev

主要就是將 Google 的論文做出實作．最重要的還是花了一個禮拜的時間好好的了解論文的精髓．

這裡有完整的導讀．

June 2nd, 2016

[論文中文導讀] Maglev : A Fast and Reliable Software Network Load Balancer (using Consistent Hashing)

前言（為何想讀這一篇論文)

這一篇論文吸引我注意的原因是， Consistent Hashing 本來的特性就是作為 Distributed Caching 之用．但是 Google 將他們的 Load Balancer (代號: Maglev ) 公布他的實作方式，裡面並且將 Consistent Hashing 做了一些小改版來符合他們的需求．

由於我之前就有學習過 Consistent Hashing ，所以相當好奇 Google 能夠如何地將它更進一步地做提升．就想要閱讀這一篇論文．

本篇導讀主要內容如下:

介紹 Maglev 的特性與其改善的部分
回顧 Consistent Hashing
介紹 Maglev Hashing

原始論文

Maglev: A Fast and Reliable Software Network Load Balancer

導讀

什麼是 Maglev?

Maglev 是 Google 的軟體 Load Balancer ，不像是一般硬體的 Load Balancer ，他可以運行在一般的 Linux 機器上面． Maglev 在 Google 內部已經運行了超過六年 ( since 2008 ) ．一台 Maglev 可以處理 10Gbps 的小封包連結．

Maglev 主要的功能與特色

Maglev 作為 Google 內部的高效能軟體 Load Balancer ，他有以下兩個主要功能：

新的 Consistent Hashing Algorithm 稱為 Maglev Hashing
Connection Tracking

回過來講，那什麼是 Consistent Hashing ?

講到 Consistent Hashing 就必須要提到原本 distributed caching 的運作是靠 Hash Table 的方式來達成，比如說:

來源 ip : 1.2.3.4 透過將來源 ip 做 Hashing 過後指向 server1
來源 ip : 1.2.3.5 透過將來源 ip 做 Hashing 過後指向 server2
來源 ip : 1.2.4.6 透過將來源 ip 做 Hashing 過後指向 server3

依照原先的設計如果 server1 發生了故障，那麼不論如何 1.2.3.4 就無法連接到任何一個伺服器．

於是 Consistent Hashing 就是在這裡發揮效果．根據定義 Consistent Hashing 為一個排序的環狀的表格，上面根據 Hashing 的數值來存放不同的節點資訊，並且需要滿足以下兩個條件:

Minimal Disruption : 這邊指的就是如果有節點被刪除，應該要達到只有該節點影響到的部分要修改而已．在 Consistent Hashing 裡面透過選取下一個的方式．透過將索引排序後，直接選取下一個節點作為 Hashing 後的結果節點．簡單的範例如下:
- 來源 IP 位置 1.2.3.4 ，經過 Hashing 後得到位置 1024 (假設)
- 到表格 1024 查詢資料，發現 1024 的節點伺服器 server1 已經出現故障．
- 尋找 1024 最接近的下一個節點（假設是 1028 ) 並且對應到 server2
- 分配 server2

Load Balancing : 也就是盡可能地讓每個節點都能運用到，不會有某些節點有過分運用的疑慮．在 Consistent Hashing 裡面是使用 Virtual Node ．
- 簡單的說，也就是在加入節點的時候，會一併複製數個虛擬節點 (通常使用 節點#1, 節點#2 ... 命名方式．
- 透過多個虛擬節點散佈在各地，讓尋找的時候更容易平均的分配到不同的節點．

對於 Maglev 而言，原本的 Consistent Hashing 有哪些缺點（限制)？

雖然 Consisten Hashing 本身已經解決了許多的問題，但是對於 Google 而言，他們有以下兩個額外的部份需要考量：

需要更均勻地分配每隔節點位置：由於 Google 的每個節點可能都是數百台的機器，由於來源資料龐大，根據舊的演算法可能需要相當大的 lookup table 才能負荷．
需要更減少 Disruption : 對於 Google 的需求，演算法需要容忍小量的 disruption ．

關於 Maglev Hashing Algorithm 的介紹

根據以上兩個需要額外考量（應該說是要更加強化）的部分， Google 提出了新的 Consistent Hashing 的演算法，稱為 Maglev Hashing Algorithm

主要概念: 新增 Preference List 概念

Preference List (偏好清單) 會分配給每一個節點，讓每一個節點去填上自己偏好的位址( Permutation )．直到整個表格是填滿的狀態．

效能:

這裡需要注意，如果 \(M\) 相當接近 \(N\) 的話，整體效能很容易落入最差狀況．

但是如果 \(M >> N\) ，比較容易將效能落入平均的狀況．

平均狀況: \(O(M log M)\)
最差狀況: \(O(M^2)\)

其中：

\(M\) 是表示 lookup table 的大小．
\(N\) 是表示節點的個數．

流程:

首先 Maglev Hashing 會先把所有的 Preference List 產生出來．
透過產生好的 Preference List 開始將節點一個個地加入並且產生出Lookup table

程式碼分析:

計算 “排列表格” Permutation Table

以下先簡單列出 generatePopulation()，主要目的就是建立 permutation table 也就一個排列組合的表格．

//name is the list of backend.
func generatePopulation() {
	//如果 []name 是空的就離開
	if len(name) == 0 {
		return
	}

	for i := 0; i < len(name); i++ {
		bData := []byte(name[i])

		//計算 offset 透過 Hash K1
		offset := siphash.Hash(0xdeadbabe, 0, bData) % M
		//計算 skip 透過 Hash K2
		skip := (siphash.Hash(0xdeadbeef, 0, bData) % (M - 1)) + 1

		iRow := make([]uint64, M)
		var j uint64
		for j = 0; j < m.m; j++ {
			//排列組合的表格
			iRow[j] = (offset + uint64(j)*skip) % M
		}

		permutation = append(permutation, iRow)
	}
}

由於 M 必須是一個 prime number （如果不給 prime number ，找出的 permutation 就會有重複值) ，舉例 M=7 這個函式就會產生可能是 [3, 2, 5, 6, 0, 4, 1] 或是 [0, 5, 6, 4, 2, 3, 1] ．這樣的排列表格是為之後使用的．

產生查表表格(Lookup Table)

論文中的 Populate Maglev Hashing lookup table 的 Golang 程式碼．

這邊有兩個表格:

entry: 代表表格中有沒有走過．架設 lookup table 大小為 7，就得 0 ~ 6 都走過一次．（不然為 -1)．而最後裡面的數值就是節點的索引．
next: 代表排列表格的下一個位置．如果節點有三個，那麼排列表格就有三組．於是 next 大小也有三個，分別記錄每一個排列表格走到第幾個位置．

範例資料

unc (m *Maglev) populate() {
	if len(m.nodeList) == 0 {
		return
	}

	var i, j uint64
	next := make([]uint64, m.n)
	entry := make([]int64, m.m)
	for j = 0; j < m.m; j++ {
		entry[j] = -1
	}

	var n uint64

	for { //true
		for i = 0; i < m.n; i++ {
			c := m.permutation[i][next[i]]
			for entry[c] >= 0 {
				next[i] = next[i] + 1
				c = m.permutation[i][next[i]]
			}

			entry[c] = int64(i)
			next[i] = next[i] + 1
			n++

			if n == m.m {
				m.lookup = entry
				return
			}
		}

	}

}

以下用簡單的範例資料，希望能夠讓大家更容易了解．

N = 3
M = 5

m.permutation [0] = [4, 3, 2, 1, 0]
m.permutation [1] = [3, 2, 1, 0, 4]
m.permutation [2] = [0, 1, 2, 3, 4]

透過這個範例，建立出 Lookup table 的方式如下：

將剛剛建立出的排列表格拿出來
i=0 ，從第一個排列表格的第一個挑出數值 c1=4 ，那麼 entry[4] = 0 (代表 lookup table 中的 entry[4] 是指向節點 0．
i=1 ，從第二個排列表格的第一個挑出數值 c2=3 ，那麼 entry[3] = 1
i=2 ，從第三個排列表個的第一個挑出數值 c3=0 ，那麼 entry[0] = 2
重跑 i 迴圈， i=0 ．從第一個排列表格的第二個( index=1 )挑出數值 c4=3 ，由於 entry[3] 走過了，往後走一個（next[0] +1) 走到 m.permutation[0][2]=2，於是 entry[2]=0
依此類推，直到所有的 n == M ．此時，也會發現 entry[] 不再存在任何 -1

詳細走法如下圖:

Maglev Hashing 跟 Consistent Hashing 的比較

這部分比較屬於我的心得，建議各位看完論文後再看這段．

Consistent Hashing
- 準備工作:
  - 將每個節點數值根據 Hashing key 加入 lookup table
  - 製作出 Virtual Node 來達到平衡．
- 如何查詢:
  - 將數值透過 Hash Key 對應到一個 lookup table 的索引 index
  - 如果該 index 沒有節點，往下尋找最接近的節點
Maglev Hashing
- 準備工作:
  - 需要先建立一個排列表格
  - 並請需要先透過排列表格做出偏好清單．注意這時候所有 lookup table 每一個索引都有一個節點分配．
- 如何查詢:
  - 數值透過 Hash Key 對應到一個 lookup table 的索引 index
  - 由於準備工作，該 index 必定存在數值
  - 傳回節點資料

完整程式碼

這邊有我的完整程式碼，大家可以參考一下：

https://github.com/kkdai/maglev

參考

May 27th, 2016

程式設計週記[2016/05/27]: 史詩級任務：帶著你第一個未滿周歲的小孩一起出國旅遊

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

主要會貼一些github，但是會盡量寫上一些有用的評語（或是我容易想到的關鍵詞）幫助以後查詢

網路文章心得:

會寫些心得，強迫自己閱讀．

“程式週記”並且定期週期性更新．

大部分內容在我的twitter都會有，這邊只是將一些簡單的心得與感想註解一下．

本週摘要

這個禮拜有三天請假，因為帶我的小孩去石垣島的 ClubMed 遊玩．雖然當地每天都是 Buffet 吃到飽，但是我跟老婆還是因為照顧小孩子太辛苦而消瘦．

由於只有兩天，本週專案想了很久不知道要寫什麼．於是先把上週的專案加以應用．但是也重寫了好幾次，並且想不到一個很好的處理方式．

Python

Android/JAVA/NODE.JS

Docker

iOS/Swift

其他程式語言

PHP GitHub - howtomakeaturn/pay2go-invoice: 一個用來呼叫智付寶電子發票API的library。

先備份起來，這種東西需要的時候總是會想看看．

論文收集

API Design Reviews at Scale

[論文][Paper] Jump Consistent Hash algorithm

Some implement code here.

網站收集

StackOverkill: Programming language and framework ranking based on StackOverflow’s activity

一個專門搜集 Stackoverflow 一些趨勢的網站，可以看看最近受歡迎的問題來自於哪個平台．哪些問題比較多．

有聲書/影片心得

podcast: Dropbox’s Magic Pocket with James Cowling

幾個月前 Dropbox 離開 Amazon S3 離開到自己建立的 Magic Pocket 硬體架構，被稱為是史詩般的故事．

Dropbox storage lead James Cowling 來談談當初的轉換過程．不少有趣的架構討論與經驗談(包含測試)．

會放在這裡是因為在 (32:55) 開始會討論到使用 Go 與 Rust 在的選擇上．

大家都知道 Dropbox 本身是使用 Python 起家的，但是他們喜歡 Go 的 Concurrency 跟 Strong type system ，架構語言選擇上:

整體架構使用 Golang ，整個流程．
商業部份的邏輯仍舊使用原來的 Python
硬體相關與記憶體相關操作使用 Rust ，因為 Rust 在記憶體部分比較有彈性．

有考慮使用 Go 與 Rust 的人可以聽聽那一段．

Steve Klabnik 介紹 Rust

透過淺顯易懂的方式來介紹 Rust ，並且介紹三大 Goal：

Safety
Speed
Concurrency

如果你還在觀看 Rust ，針對以下三個角色講者也提出一些 Rust 會吸引你的地方:

如果你是 C/C++ 的使用者
如果你是 FP 的使用者
如果你是 Web App 的使用者 ( Python/Ruby)

並且有介紹為何 Rust 沒有 GC 與使用 LLVM 的優點，也有介紹到 LLVM 與其優點．蠻適合新手聽聽看

Youtube: SREcon16

原來 Site Reliability Engineeering 也是有 conference．

本週專案 —–

這邊會寫一些我的Project 52的成果.

本週專案: https://github.com/kkdai/trr

透過 Gorilla time-series algorithm 做一個簡單的 KV value DB with Raft consensus algorithm RPC client/server

特色:

Gorilla 演算法來壓縮時間資料
透過 Raft 可以做到分散式 Consensus
Key Value 架構，可以快速搭配多個資料
RPC Entry point 使用簡單

怎麼有種撒尿牛丸的感覺… orz

May 20th, 2016

程式設計週記[2016/05/20]: 最簡單的地震探知系統

(pic from twitter: https://twitter.com/toddmotto/status/731435248588890113)

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

主要會貼一些github，但是會盡量寫上一些有用的評語（或是我容易想到的關鍵詞）幫助以後查詢

網路文章心得:

會寫些心得，強迫自己閱讀．

“程式週記”並且定期週期性更新．

大部分內容在我的twitter都會有，這邊只是將一些簡單的心得與感想註解一下．

本週摘要

本週都在讀臉書的時間序列資料庫 Gorilla 論文，覺得應該有不少地方可以運用這樣的技術．本週專題是一個幫助你處理 bit/byte 的 bit stream helper．

Python

用Python開發Facebook Bot

流程算清楚，先存檔起來

Android/JAVA/NODE.JS

devstdio/podq: The Open-source Online Podcast Player for Developers

前端透過 JS 的 pocast player．

iOS/Swift

其他程式語言

A fundamental introduction to x86 assembly programming

x86 組合語言基礎，其實可以幫助你認清不少記憶體處理方式．在 debugging 的時候會更容易找到你需要的資訊．

Mastering Git subtrees

一篇 Git 基礎好文，我認為充分了解 git subtree 與 git submodule 的差異，可以幫助以更有效率地去規劃你的軟體架構．

網站收集

https://go.zeef.com/zeefcom

這個網站分門別類地收集了 Golang 專案，有想找特別某類專案的人可以去看看

Gopher China 2016 presentation video already out

有聲書/影片心得

關於 12 factor app 的投影片

相關的影片介紹．

投影片 Go-unikernels

講解什麼是 unikernels 與 Go-unikernels 的介紹．

本週專案

這邊會寫一些我的Project 52的成果.

本週專案: https://github.com/kkdai/bstream

一個簡單的 Bit Stream 的工具，可以幫助你快速寫入數個 bit/byte 與讀取．主要是看 go-tsz 看到這個東西，覺得應該單獨成一個好用的小套件．

起源:

流程:

透過 “系統移轉輔助程式” 來轉移資料:

透過 “Time Machine” 來轉移資料

參考:

這是什麼?

Gihub project 介紹:

網路文章心得:

本週摘要

Go

Python

Android/JAVA/NODE.JS/Scala

Docker

iOS/Swift

其他程式語言

論文收集

[Static Deadlock Detection for Concurrent Go

網站文章

網站收集

有聲書/影片心得

這是什麼?

Gihub project 介紹:

網路文章心得:

本週摘要

Go

Python

Android/JAVA/NODE.JS/Scala

Docker

iOS/Swift

其他程式語言

論文收集

網站文章

網站收集

有聲書/影片心得

前言 （為何想讀這一篇論文)

原始論文

導讀

什麼是 Maglev?

Maglev 主要的功能與特色

回過來講，那什麼是 Consistent Hashing ?

對於 Maglev 而言，原本的 Consistent Hashing 有哪些缺點（限制)？

關於 Maglev Hashing Algorithm 的介紹

主要概念: 新增 Preference List 概念

效能:

流程:

程式碼分析:

計算 “排列表格” Permutation Table

產生查表表格(Lookup Table)

範例資料

Maglev Hashing 跟 Consistent Hashing 的比較

完整程式碼

參考

這是什麼?

Gihub project 介紹:

網路文章心得:

本週摘要

Go

Python

Android/JAVA/NODE.JS

Docker

iOS/Swift

其他程式語言

論文收集

網站文章

網站收集

有聲書/影片心得

本週專案: https://github.com/kkdai/trr

前言（為何想讀這一篇論文)