[論文導讀]The Case for Learned Index Structures (一)

論文原文: The Case for Learned Index Structures

Morning Paper Reading: part1, par2

緣起:

剛好最近有幾次機會可以去工研院開會的路上,在高鐵的路途上可以好好的來欣賞這篇文章. 這篇文章是由 Google Brain 的大神 Jeff Dean 連署的論文之一.講的是透過 NN 的方式來讓大家熟知的 B-Tree, Hashing table 甚至是 Bloom Filter 更有效率…

2018 年第一篇好好閱讀的論文,當然要獻給有深度而且相當有趣的這篇文章.The Case for Learned Index Structures .主要的原因有以下:

Jeff Dean 是誰? 快來看他的 Quorahttps://www.quora.com/What-are-all-the-Jeff-Dean-facts

- 他看得懂, 也寫 Binary code - 他的 PIN code 是 Pi 末四碼

先講講 B-Tree

B-Tree (Binary Tree) 是大家相當熟知的資料結構,在此僅列出幾個需要知道的.

  • 時間複雜度 (Balanced B-Tree)
  • 需要空間(cache) 代表存多少資訊在 B-Tree .當資料不在 cache 中,代表需要重新跑一次 re-balanced
  • B-Tree traversal 無法分散式處理 (透過 GPU 來加速)

再來談 Learning Index Tree

回過來講 B-Tree Index 你可以把一個數值輸入 B-Tree ,透過搜尋過後可以傳回一個 Index (可能有 re-balanced).

換個角度,如過透過 NN (Neural Networking) model 的學習將一個數值輸入後,來預測 (predict) 它可能的索引位置 (index) .那麼我們就稱這個為 Learned Index

這邊有一些你需要知道關於 Learned Index 的部分:

  • 由於直接運算,所以時間複雜度相當的低:
  • 由於透過 NN 來運算,可以很輕易透過 GPU 來加速運算
  • 空間要求相當的少
    • 不像 B-Tree Index 需要一定的空間來儲存目前已知的數值來加速. (根據文章: cache size 128 是最快的)

關於 CDF (Cumulative Distribution Function)

B-Tree 就可以當成是一個透過 Key 值來轉換到 Index (Pos)的方式. 那麼也可以當成是透過 Key 的分佈來預測 (predict) 位置.

Tensorflow 來做 CDF 與傳統 B-Tree Index 的效能比對

  • 來源資料: 200M 筆的 Web Log
  • Activation fnction: ReLu
  • 32 個 Neural per layer

透過 Tensorflow 來實作為 Naive Learning Index 與 B-Tree 的效能比對. B-Tree 快上 2~3 倍,論文提出以下理由:

  • Tensorflow 設計是為了處理大量的數據,對於 200M (相對小) 他本身的處理效率有相對的消耗
  • B-Tree 的結果會 overfit 也就是說完全以輸入的資料來作為 B-Tree 的計算與樹狀的建置. 但是相反的 CDF 是透過 NN 來計算”可能性”的位置.
  • B-Tree 需要比較大的 Cache (比較表內使用 128 的 cache 效能最佳) ,而 CDF 透過 NN 來學習不需要儲存之前的資料.(不過兩者都需要 re-train (CDF) 與 re-balanced(B-Tree) )

參考文章:

[TIL] 超好用的 Kubernetes Console tool - c9s/Vikube.vim

Kubernetes 相當好用,但是要維運的時候最痛苦的事情,就是要打 kubectl

雖然我超愛 Golang ,而且其實我基本的 IDE 都是使用 VSCode ,但是我一定要跟各位好好推薦這個好工具. Vikube.vim

不論你透過 alias 設定成 kc 甚至是 k 還是得要記憶一堆指令 ex: kubectl get pod

其實就算你不是 vim 的愛用者 (畢竟學習曲線太高了) 我還是很推薦你使用這個工具.

  • :VikubeContextList 可以開啟你所有連接過的 K8S 集群,透過 s 來切換你的集群.
  • :VikubeNodeList 可以開啟所有的節點清單,l 可以看到 結點上面的 logs, 可以幫助你除錯(如果有問題)
  • :VikubePodList 可以開啟 pod 清單,當然也可以透過 l 來看 POD 是否有出現問題.
  • :VikubeTop 可以開啟 top 來看各個 POD 的使用量

真的很好用… 再也不用擔心打 kubectl 或是忘記相關指令了 :p

[TIL] Change fish shell theme with nerd font

起源

Fish Shell 強大的親和力,並且讓我很簡單就上手.讓我使用上相當方便. 但是隨著許多軟體的安裝都還是需要 bash 並且在 vim 的更新上變得相當困難. 我其實有開始想要把 fish 換到大家比較常使用的 zsh .

原本看了這篇文章 超簡單!十分鐘打造漂亮又好用的 zsh command line 環境 要打算把自己的 fish shell 換到 zsh.

不過考量許多原因,做了一些小修改:

Fish shell failure update Vundle in Vim:

Refer: I don’t use a POSIX Shell (i.e. Bash/Sh)](https://github.com/VundleVim/Vundle.vim/wiki#i-dont-use-a-posix-shell-ie-bashsh)

解法: add ~/.config/fish/functions/updatevim.fish

function updatevim
    set -lx SHELL (which sh)
    vim +BundleInstall! +BundleClean +qall
end

Zsh PowerLevel9k 看起來實在很威

PowerLevel9K 實在很方便,所以找了一個 Fish Shell 可以使用的 bobthefish

不過 bobthefish 資訊太多了,需要一些調整.

#OMF setting for bobthefish
#
set -g theme_display_date no
set -g theme_nerd_fonts yes
set -g theme_display_k8s_context no

換漂亮的字型 nerd-font

後來有換這個字型,看起來還挺順眼的.

還有..

VSCode Integrated terminal 還是會有亂碼,目前還在解決中. 可以參考這個VSCode integrated terminal versus nerdfont-complete #672

Reference

[TIL][Google Kubernetes Engine] Tensorflow/k8s and GPU on GKE

Easy way for :Distributed Tensorflow

tensorflow/k8s : Tools for ML/Tensorflow on Kubernetes.

Architecture:

  • Run a job operator by Helm
  • Post your job just like a simple yaml file
  • Job Operator will help you to distributed to each node for computing result
    • PS
    • Worker

Sample Job Kubernetes YAML file

apiVersion: "tensorflow.org/v1alpha1"
kind: "TfJob"
metadata:
  name: "example-job"
spec:
  replicaSpecs:
    - replicas: 1
      tfReplicaType: MASTER
      template:
        spec:
          containers:
            - image: gcr.io/tf-on-k8s-dogfood/tf_sample:dc944ff
              name: tensorflow
          restartPolicy: OnFailure
    - replicas: 1
      tfReplicaType: WORKER
      template:
        spec:
          containers:
            - image: gcr.io/tf-on-k8s-dogfood/tf_sample:dc944ff
              name: tensorflow
          restartPolicy: OnFailure
    - replicas: 2
      tfReplicaType: PS

Sample Distributed Tensorflow Code

Refer here.

Troubleshooting: Could not enable default namespace on Helm.

kubectl create serviceaccount --namespace kube-system tiller
kubectl create clusterrolebinding tiller-cluster-rule --clusterrole=cluster-admin --serviceaccount=kube-system:tiller
kubectl patch deploy --namespace kube-system tiller-deploy -p '{"spec":{"template":{"spec":{"serviceAccount":"tiller"}}}}'      
helm init --service-account tiller --upgrade

GKE: Enable GPU on GKE

gcloud alpha container clusters create gpu-test \
    --project $PROJECT_ID \
    --zone $ZONE \
    --enable-kubernetes-alpha \
    --enable-cloud-logging \
    --enable-cloud-monitoring \
    --accelerator type=nvidia-tesla-k80,count=1 \
    --machine-type n1-standard-1 \
    --cluster-version=1.8.4-gke.1 \
    --image-type $IMAGE_TYPE \
    --num-nodes 1 \
    --quiet

Trobleshooting:

  1. K8S alpha don’t support master version upgrade, so you need define k8s 1.8 when you create it. (default: 1.7.8)
  2. How to get GKE current support versions?
    1. gcloud container get-server-config

[TIL] Netflix: Heterogeneous Cluster Allocation

原文: Netflix: Distributing Content to Open Connect

最近都在忙著趕公司專案,這篇文章讀了好久.

Netflix 最近寫了這篇技術文章來解釋他們如何面對大量影片下載需求的 Load Balance 的方式 : Heterogeneous Cluster Allocation (HCA)

一般來說我們都會使用 Consistent Hashing 的方式來處理伺服器分配流量的方式. 這也是最為人熟知的 Load Balancing 的方式. 但是 Netflix 提出了有趣的想法是,作為 Load Balancing 的時候,我們都是把伺服器當作是同質的 (註: 同樣速度,同樣硬碟大小)

但是如果其實伺服器可能是異質的(Heterogeneous) ,舉例來說: 有的一般硬碟 100TB 但是 throughput 比較低 ,另外則有速度快的 SSD 50 TB ,但是 throughput 相對來說就比較高.這樣的分配法則下,原來的 Consistent Hashing 就無法滿足這樣的方式.

於是 Netflix 他們使用 HCA 的方式來達到更適量的分配.針對這兩種異質的方式,Netflix: Heterogeneous Cluster Allocation (HCA) 作法如下:

  • 在兩種異質的機器上,各自給予 content 相對的權重 (weight).權重的評比來自於 content 受歡迎程度

  • 兩種機器各自有不同的 cutoff (也就是 threashold) ,來決定該 content 是否受歡迎. (ex: 40Gbps, cutoff: 0.3, 100Gbps 0.28..)

透過這樣的調整,可以確定接下來 content 會被放在哪裡.也能夠更有效率的分配流量.並且也驗證了在負載高的時候,更能讓不同的需求讓不同的伺服器來服務.

[TIL][markdown] 好用的編輯器 - typora

https://typora.io/img/new/inline.png

Typora 網站

今日內部教育訓練的時候,首席(筆頭?) 唯一問的問題,竟然是請問展示使用的 markdown 編輯器是什麼? 一問之下,才知道原來有另外一個好用的 markdown 編輯器 typora

  • 動態檢視 (類似 dropbox paper 體驗) (特愛
  • 支援 Latex preview, 支援 Latex preview, 支援 Latex preview (媽呀,真棒
  • 有 Tab 的支援
  • outline 顯示模式
  • 聽說支援 Windows, Ubuntu, OSX

於是我馬上把 MacDown 換掉了 XDDD ~~大推…