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 吃到飽，但是我跟老婆還是因為照顧小孩子太辛苦而消瘦．

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

Go

dgryski: best practices for writing high-performance Go code.

大大 dgryski 教導如何寫出高效能的 Go App．

Replication of Etcd - Blog With ReeZhou

有介紹 etcd 裡面使用 raft 的 propose 的流程分析．

Suffix arrays in the Go standard library

介紹如何使用 Go 內建的 Suffix Array ，其實 Go 內建也有 container/ring 的套件可以用．這裡有篇介紹文章．

To create package alias for your #Go tool by using “go list”

Application data caching using SSDs

Netflix 最新的部落格提到有一個 ‎golang 寫的 application data cache proxy - Rend 決定資料要存放 memcached 或是 SSDs

Abstracting S3 for Fun and Profit in Go

試著做一出一個類似 AWS S3 的服務．

Practical Golang: Using Protobuffs | Jacob Martin

一些關於 Protobuf 的實際應用．

VoV is a high score game for Android

完全使用 Go 開發的 Android 射擊遊戲．

Four and a Half Years of Go in Production at goto Chicago 2016

講解 iron.io 在四年半前如何從 ruby 換到 Go 的故事．當時 Go 才一年多，算是相當新的程式語言．他們必須要說服相當多人如何從穩定的 Ruby 換到一個嶄新的嘗試，並且還不敢開始找 Go 工程師 (怕找不到?)

How to organise a Go HTTP service

教導你要如何組織你的 Http Go App ，這裡有更詳細的文章

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.

網站文章

淺析 serverless 架構與實作

算是最齊全資料的繁體中文 serverless 架構與實作解析．

Fizz Buzz in Tensorflow

關於 tensorflow 的笑話．（應該只有工程師才看得懂)

m157q: GCP 筆記: CP100A: Google Cloud Platform Fundamentals

阮一峰：要聊天，先付费

將群聊當作諮詢的一種要收費，這樣的商業模式到底能不能起來．

时序列数据库武斗大会之什么是TSDB

關於 TSDB 的一些基本介紹．

Amazon Debuts Flourish, a Runtime Application Model for Serverless Computing

AWS Serverless部門的GM @timallenwagner 宣布AWS即將來源一套Serverless開發工具叫Flourish, 感覺是一個能在本地開發測試的IDE或SDK，一起期待了

How I Satisfied My Passion for Software Development and Open-Source by Doing a Part-Time PhD

講解一個人如何邊上班邊做 Open Source 並且念完博士班．

來日本工作三個月的心得

講解在日本的 Line 工作有不少與在台灣工作不相同的地方．提到面試，專案時程與文化．很值得一看．

为什么你有10年经验，但成不了专家？

除了工作經驗之外，沒有不斷的努力學習與自我強化．沒辦法說自己是專家的．

網站收集

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．

Go

Essential knowledge for Go debugging | Stack Traces In Go

很有用的舊文章，透過了解 Golang 處理 stack 的方式可以讓你更了解如何 debugging golang app．

distatus/battery: cross-platform, normalized battery information library

跨平台的電池資訊顯示工具，挺有趣的 golang app．

Comparing Golang with Java

從 Java 轉到 Go 的工程師寫出他心得感想．

pierrre/imageserver: Image server toolkit in Go

將一些影像處理可能經常用到的工具 kits 寫成 web services 並且開源．

C++ Bindings For A Go Library

講解如何在 C++ 中去使用 Go library 的方式與該注意的地方．並且有提到 C++ GC 處理方式的 Golang-Nuts

The InfoQ Podcast: Uber’s Chief Systems Architect on their Architecture and Rapid Growth

Uber 的開發團隊決定從把開發語言從 node.js 搬到 Go 跟 Java

Dev Cheney 出的程式小測驗，你能做對嗎?

主要是講解使用 point 指向 slice 要注意到 slice 會因為 cap 變大而 reallocation 位置，造成你舊的指標指向一個已經過期的資料空間．更多資訊可以參考這篇 https://blog.golang.org/go-slices-usage-and-internals

Python

用Python開發Facebook Bot

流程算清楚，先存檔起來

Android/JAVA/NODE.JS

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

前端透過 JS 的 pocast player．

Docker

Using Caddy with Docker

透過 docker 架設具有 Caddy ( Go web app) 的 image ．

走近Docker安全扫描器

解釋 Docker 安全掃描器 Project Nautilus 如何使用與原理．

[Slide] DOCKER, KUBERNETES, AND MESOS: COMPARED.

講解如何選擇 Kubernetes 跟 Mesos 或是只使用 Docker 就好，其中說 cluster < 200 要使用 Kebernetes 這點很特別！！

iOS/Swift

其他程式語言

A fundamental introduction to x86 assembly programming

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

Mastering Git subtrees

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

網站文章

Notes on Distributed Systems for Young Bloods

給初學分散式系統的建議，寫得真好。

The Scala Effect

講解到 Scala 的一些特色與它造成的影響．

Enabling HTTP/2 for Dropbox web services: experiences and observations

Dropbox 導入 http2 的經驗與觀察．

如果有人问你数据库的原理，叫他看这篇文章

講解各種 B-Tree 在資料庫中是如何應用．

Google’s 9 lines

讓 Google 跟 Oracle 打官司的九行程式碼．

網站收集

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 看到這個東西，覺得應該單獨成一個好用的小套件．

May 18th, 2016

[中文導讀] Facebook 的時間序列資料庫 - Gorilla (Gorilla: A Fast, Scalable, In-Memory Time Series Database)

(come from Paper)

前言:

本文會介紹最近被討論的 Facebook 時間序列資料庫的論文，並且會介紹資料庫壓縮演算法．其中不少解讀都是參考 Morning Paper 裡面的論文導讀．

最後會導入 Damian Gryski 根據論文推導出的演算法 dgryski/go-tsz ．

原始論文:

Gorilla: A Fast, Scalable, In-Memory Time Series Database

導讀:

什麼是 Gorilla ?

Gorilla 是 Facebook 開發的時間序列資料庫．其實市場上已經有很多的時間序列資料庫 (HBase on TSDB(time-series database)) ，為什麼還需要自己開發一個呢?

資料的儲存過於龐大
查詢的延遲過長

所以 Gorilla 針對這些有了以下的優化:

針對 timestamp 的壓縮
分析並且針對資料的壓縮
放在記憶體 (in-memory databse)

那麼 Gorilla 比起一般的時間序列資料庫究竟有多強大呢?

透過將時間與數值的壓縮，並且透過儲放在記憶體的操作． Gorilla 可以達到:

73 倍的 Query Latency 減少
14 倍的 Query Throughput 增加

為了要儲存到 26 小時以上的時間序列資料，並切壓縮到 1.3 TB 的記憶體之中(分散在 20 部伺服器中)．所以 Gorilla 針對儲存資料有相當程度的壓縮．

透過資料的壓縮最佳狀態可以達到:

(come from Paper)

高達 12 倍的壓縮比: 原先 16 bytes 的數值資料(包括 timestamp 與 value )透過壓縮，一般而言平均可以達到 1.37 bytes (通常在經過 240 分鐘後)

12倍的壓縮比？那麼大的壓縮比是如何做到?

簡單的來說 Gorilla 透過將時間資料( timestamp )與數值資料( value ) 的壓縮．其壓縮的方式是參考前一次的資料，透過時間序列資料庫的特性:

連續性資料
在比較小的取樣時間中，每筆資料間的變化不大

透過這樣的方式，可以拿目前的資料 $t_n$ 去與前一筆資料 $t_(n-1)$ 比對的方式，來拿到差異值 (delta) ．並且將差異值做一定程度的壓縮．達到整個資料庫數值的壓縮．

壓縮的演算法: 關於時間資料的壓縮

首先針對時間資料的壓縮部分，讓我們先看看以前的時間可能如何紀錄: (舉例)

$t_0$ => 02: 00 : 00
$t_1$ => 02: 01 : 02
$t_2$ => 02: 02 : 02
$t_3$ => 02: 03 : 02

如果要直接紀錄的話，其實資料長度會變得相當大．讓我們換個角度來看:

$t_0$ => 02: 00 : 00 (跟之前差距 0)
$t_1$ => 02: 01 : 02 (跟之前差距 62 秒)
$t_2$ => 02: 02 : 02 (跟之前差距 60 秒)
$t_3$ => 02: 03 : 02 (跟之前差距 60 秒)

這樣紀錄 delta 只要紀錄差異就好，那有可能更簡短嗎？

$t_0$ => 02: 00 : 00 (跟之前差距 0)
$t_1$ => 02: 01 : 02 (跟之前差距 62 秒)
$t_2$ => 02: 02 : 02 (跟之前差距 60 秒，跟上一個差距的差異 -2 秒 )
$t_3$ => 02: 03 : 02 (跟之前差距 60 秒,跟上一個差距的差異 0)

這個概念就是紀錄 delta of delta，也就是差距中的差異．

將 差距中的差異 以字母 $D$ 來代替，透過 Tag Bit 與 Value Bits 來表示．

(Pic: from Morning Paper )

轉換之前的範例為:

$t_0$ => 02: 00 : 00 => D = 0, tag bit 0.
$t_1$ => 02: 01 : 02 => D = 62, tag bit 10, value 62 (011 1110) 總共 9 bits
$t_2$ => 02: 02 : 02 => D = -2, tag bit 10, value -2 (111 1101) 總共 9 bits
$t_3$ => 02: 03 : 02 => D = 0, tag bit 0 總共 1 bit

這樣就可以節省不少空間來儲存時間資料．

(come from Paper)

這張圖，顯示了大部分的時間資料的分佈．可以透過這張圖看到，不少的時間差異的差距 (delta of delta) 其實都是屬於 0 (具有 96%)．

也就是說經常兩兩儲存的時間差距是相同的，這樣的話其實可以不需要儲存那麼繁瑣的時間資料．而透過一個方式來儲存．

壓縮的演算法: 關於時間資料的壓縮 (程式碼)

func (s *Series) Push(t uint32, v float64) {
	s.Lock()
	defer s.Unlock()

	if s.t == 0 {
		// first point
		s.t = t
		s.val = v
		//s.T0 是第一筆時間資料
		//s.tDelta 就是前兩筆的差異
		s.tDelta = t - s.T0
		s.bw.writeBits(uint64(s.tDelta), 14)
		s.bw.writeBits(math.Float64bits(v), 64)
		return
	}

	//tDelta 就是現在的目前的時間跟上一次時間的差異
	tDelta := t - s.t
	//dod (Delta of Delta): 就是 (tn - t(n-1) ) - (t(n-1) - t(n-2) )
	dod := int32(tDelta - s.tDelta)

	//透過 dod 來放置 tag but 䢎 vakye
	switch {
	case dod == 0:
		s.bw.writeBit(zero)
	case -63 <= dod && dod <= 64:
		// 放置 tag bit
		s.bw.writeBits(0x02, 2) // '10'
		// 放置 value bit
		s.bw.writeBits(uint64(dod), 7)
	case -255 <= dod && dod <= 256:
		s.bw.writeBits(0x06, 3) // '110'
		s.bw.writeBits(uint64(dod), 9)
	case -2047 <= dod && dod <= 2048:
		s.bw.writeBits(0x0e, 4) // '1110'
		s.bw.writeBits(uint64(dod), 12)
	default:
		s.bw.writeBits(0x0f, 4) // '1111'
		s.bw.writeBits(uint64(dod), 32)
	}
	
	...

(code from https://github.com/dgryski/go-tsz/blob/master/tsz.go )

壓縮的演算法: 關於數值資料的壓縮

到數值的部分，一樣使用之前的概念．也就是 delta of delta 的概念來處理數值壓縮．而差異的部分不再使用 minus 而是透過 XOR 的方式．

(come from Paper)

將以上的資料做個簡單的 XOR 運算，來計算數值資料中的差距:

$v_1$ 12 -> 0x40280 -> XOR: N/A
$v_2$ 24 -> 0x40380 -> XOR: 0x00100
$v_3$ 15 -> 0x402e0 -> XOR: 0x00160
$v_4$ 12 -> 0x40280 -> XOR: 0x00060
$v_5$ 12 -> 0x40280 -> XOR: 0x0

計算好各個數值資料間的 XOR 之後，我們要來針對這樣的資料壓縮:

(Pic: from Morning Paper )

針對以上的圖片，主要壓縮方式如下:

假設計算數值，如下

$v_2$ -> XOR: 0x001000000000000
$v_3$ -> XOR: 0x001600000000000

計算各個數值 XOR 的 leading/meaning/trailing bits

$v_2$ -> XOR: 0x001000000000000,
- leading bit: 2
- meaningful bit: 1
$v_3$ -> XOR: 0x001600000000000
- leading bit: 2
- meaningful bit: 2

其中:

Leading Bit: 就是 XOR 遇到第一個非零數值”前”的零的個數
Meaningful Bit: 中間所有非零的個數

計算 control bit ，其規則如下:

如果 XOR 是 0, control bit = 0
如果 XOR 不是 0, control bit = 1，並且透過以下方式來計算下一個 control bit
- Leading bit, Meaningful bit 個數相同，但是其中 Meaningful 數值不同． Control Bit 0 ，接下來是 Meaningful value.
- 如果 Leading bit 跟 Meaningful 個數與數值不同， Control bit 1 ．並且接下來存放資料:
  - 5 bits: 放 Leading bit 個數
  - 6 bits: 放 Meaningful bit 個數
  - 放置所有的 Meaningful bit 數值．

拿個範例拿來做壓縮範例:

會拿以下的數值來做壓縮運算，真實數值比較大這邊只做範例：

$v_1$ 12 -> 0x40280 -> XOR: N/A
$v_2$ 24 -> 0x40380 -> XOR: 0x00100
$v_3$ 15 -> 0x402e0 -> XOR: 0x00160
$v_4$ 12 -> 0x40280 -> XOR: 0x00060
$v_5$ 12 -> 0x40280 -> XOR: 0x0

經過計算後:

$v_1$ : treat XOR : 0x40280
- Control bit: 11 (bit)
- Leading bit: 00000 (bit)
- Meaningful bit: 00101 (5 bit)
- Meaningful value: 0x40280
$v_2$ : XOR : 0x00100 上一個 XOR: 0x40280
- Control bit: 11 (bit)
- Leading bit: 00000 (bit)
- Meaningful bit: 00101 -> 5 (bit)
- Meaningful value: 0x40280
$v_2$ : XOR : 0x00160 上一個 XOR: 0x00100
- Control bit: 10 (bit)
- Leading bit: 00010 -> 2 (bit)
- Meaningful value: 0x160
$v_4$ : XOR : 0x00060 上一個 XOR: 0x00160
- Control bit: 11 (bit)
- Leading bit: 00011 -> 3 (bit)
- Meaningful bit: 00010 -> 2 (bit)
- Meaningful value: 0x60

壓縮的演算法: 關於數值資料壓縮的程式碼:

func (s *Series) Push(t uint32, v float64) {
	...
	
	//計算 XOR 數值
	vDelta := math.Float64bits(v) ^ math.Float64bits(s.val)

	// 如果 XOR ==0
	if vDelta == 0 {
		//只寫一個 Bit `0`
		s.bw.writeBit(zero)
	} else {
		//如果是零，先寫入第一個 control bit `1`
		s.bw.writeBit(one)

		//計算 leading 跟 trailing 個數
		leading := uint8(bits.Clz(vDelta))
		trailing := uint8(bits.Ctz(vDelta))

		// clamp number of leading zeros to avoid overflow when encoding
		if leading >= 32 {
			leading = 31
		}

		// TODO(dgryski): check if it's 'cheaper' to reset the leading/trailing bits instead
		
		// leading 跟 trail 相同，但是 meaningful 數值不同
		if s.leading != ^uint8(0) && leading >= s.leading && trailing >= s.trailing {
			//寫入第二個 control bit `0`
			s.bw.writeBit(zero)
			//寫入meaningful value
			s.bw.writeBits(vDelta>>s.trailing, 64-int(s.leading)-int(s.trailing))
		} else {
			s.leading, s.trailing = leading, trailing

			//連 leading 都不相同，落入其他 case
			//寫第二個 control bit `1`
			s.bw.writeBit(one)
			//寫入 leading 個數
			s.bw.writeBits(uint64(leading), 5)

			// Note that if leading == trailing == 0, then sigbits == 64.  But that value doesn't actually fit into the 6 bits we have.
			// Luckily, we never need to encode 0 significant bits, since that would put us in the other case (vdelta == 0).
			// So instead we write out a 0 and adjust it back to 64 on unpacking.
			sigbits := 64 - leading - trailing
			//寫入 meaningful bit 個數
			s.bw.writeBits(uint64(sigbits), 6)
			//寫入 meaningful value
			s.bw.writeBits(vDelta>>trailing, int(sigbits))
		}
	}
	
	...

(code from https://github.com/dgryski/go-tsz/blob/master/tsz.go )

數值資料壓縮的成果計算:

(come from Paper)

經過論文中計算，一般而言透過 XOR 計算過後．有 59%的數值資料都會落入 0 也就是說跟前一個數值相同．另外 control bit 10 的 case 會達到 28.3 % ．最後比較長 (可能) 的 control bit 11 的 case 只有 12 % ．

這個表格也表示，透過這樣的壓縮有效的將數值資料可以做一定程度的壓縮．

心得:

這篇論文其實很棒，也是我第一篇透過 “Morning Paper” 來看懂的第一篇論文．我相信 Gorilla 對於資料壓縮的方式，對於之後如果有機會處理 Streamming Data 或是針對時間序列資料庫的處理都會有更有效率的方式．

參考

May 16th, 2016

[TIL][Mac] About GOPATH and GOBIN system environment

Major problem:

System environment variable GOBIN cause problem “vim-go error: vim-go: goimports does not support srcdir”

Situation:

Recently I use vs code to write golang more than vim-go，But when you upgrade the Golang version then use vim-go to save file, it will always popup following error message.

vim-go: goimports does not support srcdir

Problem Environment:

Mac Only.
Homebrew installed only.

Root Cause:

normally there are two importnt variable in go env which was $GOPATH and $GOBIN. But most user only set $GOPATH but $GOBIN.

It will cause your all golang binary install via go install to the directory $GOPATH/bin.

Recently Homebrew formula, it will help us to set $GOBIN but the path will be/usr/local/Cellar/go/GO_VERSION/libexec/bin rather than $GOPATH/bin.

What’s the problem with that？

If you have any package which force to install in $GOPATH/bin, it might has problem with duplicate or not install latest one with Golang update. dlv has the same issue before，I file a PR for this．
If you already install some useful tool in $GOPATH/bin before, it will not update and some problem will occur. As my problem in goimports which is identical with issue 775, I use the old version of goimports so it will occur error in vim-go.)

Solution:

Remove all binary file $GOPATH/bin. (If you always use Homebrew for Golang update)
Reinstall all binaries, it will install to correct path in $GOBIN, not $GOPATH/bin.

這是什麼?

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

這是什麼?

Gihub project 介紹:

網路文章心得:

本週摘要

Go

Python

Android/JAVA/NODE.JS

Docker

iOS/Swift

其他程式語言

網站文章

網站收集

有聲書/影片心得

本週專案

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

前言:

原始論文:

導讀:

什麼是 Gorilla ?

那麼 Gorilla 比起一般的時間序列資料庫究竟有多強大呢?

高達 12 倍的壓縮比: 原先 16 bytes 的數值資料(包括 timestamp 與 value )透過壓縮，一般而言平均可以達到 1.37 bytes (通常在經過 240 分鐘後)

12倍的壓縮比？ 那麼大的壓縮比是如何做到?

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

12倍的壓縮比？那麼大的壓縮比是如何做到?