[論文導讀]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 .主要的原因有以下: 這篇是講解一個新的機器學習的新領域(至少是相當有趣的觀點) 雖然有些限制跟品質的降低,但是讓我們對於 AI/Deep Learning 有了一個新領域的想法… 這篇是被稱為世界上最聰明的人 Google Brain 的主持人 - Jeff Dean 的論文( 編按: 這篇 Quora 有許多關於 Jeff Dean 的敘述文,相當的有趣 XD) Jeff Dean 是誰? 快來看他的 Quorahttps://www.quora.com/What-are-all-the-Jeff-Dean-facts - 他看得懂, 也寫 Binary code - 他的 PIN code 是 Pi 末四碼 先講講 B-Tree B-Tree 是大家相當熟知的資料結構,在此僅列出幾個需要知道的. 時間複雜度 \(O(log n)\) (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 的部分: 由於直接運算,所以時間複雜度相當的低: \(O(1)\) 由於透過 NN 來運算,可以很輕易透過 GPU 來加速運算 空間要求相當的少 不像 B-Tree Index 需要一定的空間來儲存目前已知的數值來加速. (根據文章: cache size 128 是最快的) 關於 CDF (Cumulative Distribution Function) 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 https://github.com/oh-my-fish/oh-my-fish/blob/master/docs/Themes.md#bobthefish 超簡單!十分鐘打造漂亮又好用的 zsh command line 環境 VSCode integrated terminal versus nerdfont-complete #672 Powerline fonts in terminal incorrect #7116​
繼續閱讀

[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...
繼續閱讀

[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

Typora 網站 今日內部教育訓練的時候,首席(筆頭?) 唯一問的問題,竟然是請問展示使用的 markdown 編輯器是什麼? 一問之下,才知道原來有另外一個好用的 markdown 編輯器 typora 動態檢視 (類似 dropbox paper 體驗) (特愛 支援 Latex preview, 支援 Latex preview, 支援 Latex preview (媽呀,真棒 有 Tab 的支援 outline 顯示模式 聽說支援 Windows, Ubuntu, OSX 於是我馬上把 MacDown 換掉了 XDDD ~~大推…
繼續閱讀