課程鏈結: 這裡

學習鏈結:

• Week 1-2
• Week 3
• Week4
• Week5
• Mini Project (Gossip Protocol)

課程內容:

這裡先簡單的介紹整系列的課程內容，希望能讓大家了解這個課程想做什麼．

這整堂課主要是圍繞著 Cloud Computing 經常會使用到的技術與相關的概念． 整堂課其實只有一個程式語言作業:

	使用 C++ 寫 Gossip Protocol

雖然課程裡面程式語言的作業不多，但是整體上的內容還算不少． 除了有談到一些雲端技術的基本概念:

• Map Reduce
• Multicasting and Gossip Protocol
• P2P Protocol and System
• K/V DB, NOSQL, and Cassandra (畢竟都談了 Gossip)
• Consensus Algorithm - Paxos, FLP Proof

其實課程內容很有料，也可以學到很多的東西．

前提:

最近決定要把這堂課學完，於是付錢並且開始從 week3 繼續我的學習進度．

Week3 卡住相當久，由於裡面有許多東西需要好好的計算．往往就很難靜得下心來算．加上內容相當充實，介紹了許多種 P2P 軟體的運作方式，不僅僅有 Napster 還有 Bittorent 的運作方式，更有 Gnutella 與具有 Consistent Hashing 架構的 Chord

Week3 P2P (Peer-To-Peer) System

這一週主要講到 P2P (Peer To Peer) 不僅僅有提到基本的概論外，也有將各種 P2P 軟體的傳輸方式做一個簡單的整理．

Napster

伺服器不存檔案，但是存每個節點的資料與檔案清單．並且也存放節點網路狀況．

• Server maintain <file, ip_address> tuple
• How client search:
  • Send key word to server
  • Server search tuple list, return ip list
  • Client ping each node to find transfer rate.
  • Client fetch file from best host.
• Using TCP

Problem:

• Centralize server
• Server cannot fixed SPOF
• No security (plaintext)

Gnutella

下一代的 Napster ，主要針對 Napster 集中式伺服器的問題來解決．Client act as server call Servents

Gnutella 有五種訊息種類:

• Query (Search)
• QueryHit (Reponse for Search)
• Ping (Hearbit)
• Pong (Response for Heartbit)
• Push (Init for transfer)

Message Format:

• Descriptor ID
• Payload Descriptor (Messavge Type)
• TTL (Time To Life)
• Hops (Increase by each node (hop) )
• Payload Length

P.S.:

• TTL only use for QueryHit to provide distance of overlay network.
• 透過 HTTP 傳遞檔案
• 具有 Reverse-Routed 功能的只有 QueryHit ，因為他是回應 Query 的答案，需要具有回傳的的功能．

避免過多的 Query 流量

• 每個節點記住傳過的清單
• 每個節點只會轉達 “一次” 相同來源的 Query
• 重複的 Qeury 會被 drop

Problem:

• 太多的 Ping/Pong 網路流量．(約莫 50%)
  • 解法: 透過 cache 解決 heartbit 流量．

Fasttrack and Bittorent

Fasttrack 的特點

• 混合 Gnutella 與 Napster 的優點
• 某些節點( node )會變成 Supernode 也就是可以作為目錄的節點．

Bittorent

流程:

• 下載 .torrent 檔案
• 讀取裡面所有的 tracker (所謂的 tracker 就是管理所有 peer 的清單的伺服器）
• 分別到 tracker 去下載相關的 peer 清單
• 跟每一個 peer 去要求下載自己所需要的 block

選取檔案策略

• 採取 Local Rarest First 也就是會先找重複性最少的 block 來下載
• 如此一來可以增加檔案的健康度

Chord

效能比對

What is Chord

• A DHT (Destributed Hash Table)
• Using consistent hashing

Finger Table 計算方式

根據上圖

• 如果 m = 7
• 那麼如果要找出 N80 的 ft(finger table of N80 ) 就會是:
  • 80 + \(2^0\) = 80+ 1 = 81 > 80 –> 96
  • 80 + \(2^1\) = 80+ 2 = 82 > 80 –> 96
  • 80 + \(2^2\) = 80+ 4 = 84 > 80 –> 96
  • 80 + \(2^3\) = 80+ 8 = 88 > 80 –> 96
  • 80 + \(2^4\) = 80+ 16 = 96 = 96 –> 96
  • 80 + \(2^5\) = 80+ 32 = 112 > 96 –> 112
  • 80 + \(2^6\) = 80+ 64 = 144 mod 128 = 16 = 16 –> 16

How to handle Chord Failure?

尋找繼承者節點 (successor)

• N32
  • successor N45
  • presuccessor N16
• N112
  • successor N16
  • presuccessor N96

備份方式:

通常會有 r 份備份 \(r = 2 log(N)\)

新增節點

如果增加新節點 N40 在 N32 與 N45 之間，那麼有經過這兩個的上的 FT (並不是代表這兩個節點..) 就需要重新計算．

Pastry

特色

• 相當類似 Chord 使用consistent hashing table
• 每個葉節點 (Leaf Node) 會知道自己前一個( Predecessor ) 葉節點跟後一個( Successor )葉節點
• Routing Table 採取 Prefix Matching
  • 時間複雜度就是 \(log(N)\)
  • 由第一個位元開始比對，相同 prefix 最多的就是 “best next-hop”

ex:

10110110111

的 best next-hop 就是 101101101”0”1

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

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

網路文章心得:

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

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

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

本週摘要

真是一個瘋狂的禮拜，每天都是滿滿的會議．見識了很多特別的人，也了解了許多商場上的策略．很開心能有這樣的機會了解與參與公司在擴張與尋找合作夥伴的機會．

在學習上，也開始能夠參加公司內部 Macine Learning 的讀書會． 希望能花上更多時間來好好學習．

Go

uber/cherami-server: Distributed, scalable, durable, and highly available message queue system.

Uber 將他們的 Task Queue - Cherami 開源． 原本 Uber 是使用 Celery (Python) 作為他們的 task queue ． 由於業務的增加，對於 HA 的需求增加，於是用 #Golang 重寫成過，

並且與 Uber 許多好用的套件 TChannel (管 RPC) 與 RingPop (負責 Health Checking 與 Membership ) 結合在一起．

成為一個具有 Distributed, scalable, durable, 跟 highly available 的 task/message queue 系統

說明的部落格在這裡

Goroutine leak

Goroutine leak #golang 這篇文章敘述了再使用 goroutine 的時候經常呼叫了卻沒有跑完而造成 memory leak

Go 1.8 development stats

Golang 二月將要發行的 1.8 目前開發的狀況!!

Go 1.8 Performance improvements on ARM (RasPi)

有人在 reddit 上面丟出 #Golang 1.8 針對 RPI (Raspberry Pi) 跟 1.7.4 來比較，平均效能能高出一倍左右．

Dataman-Cloud/swan: A Distributed, Highly Available Mesos Scheduler, Inspired by the design of Google Borg

Swan 是一個用 Golang 寫出的 mesos 資源管理器套件． 參考了 Borg 裡面的精神．

作者並且在 Reddit 上面寫了兩篇來介紹了如何透過 Golang 來寫另外一套類似 Mesos 的資料管理器，文章不僅僅有介紹了身為”資源管理器”所需要的功能與面向，也介紹了該如何透過 Golang 來實作 Mesos 資料管理器．

主要推廣的 Golang Package Dataman-Cloud/swan: github.com/Dataman-Cloud/swan

教學文章整理:

• Reddit: How to write a mesos framework(1)

• Reddit: How to write a mesos framework(2)

Python

Android/JAVA/NODE.JS/Scala

Cassandra backup script on linux system

Use nodetool to backup cassandra DB.

Docker

Kubernetes

kubernetes-incubator/kompose: Tool to move from docker-compose to Kubernetes

幫你把 Docker-Compose 的機制放到 Kubernetes 上面，更容易來部署 Kubernetes 的 Pods ．

iOS/Swift

其他程式語言

論文收集

Apache Hadoop YARN: Yet another resource negotiator

Morning Paper 是一個會每天讀一篇論文，然後幫你寫導讀跟介紹的網站． 裡面論文的精彩程度是每個做軟體工程師不可不讀的．

之前一系列的 Deep Learning 之後，作者準備要來好好讀讀分散式系統了． 所選的第一篇論文就是這篇 Hadoop YARN 的論文．

YARN 是從 Hadoop 2.0 之後從 Hadoop 中抽出來的架構．本篇論文裡面的 YARN 還無法解決 SPOF ． (Hadoop 2.4 之後有支援 HA)

本篇論文也有討論到底 Mesos 跟 YARN 有什麼差異:

Mesos -> Offer-based approach YARN -> Request-based approach

同場加映:

有沒有辦法把 Mesos 跟 Hadoop YARN 一起用呢? 可以看看這篇文章

網站文章

资本寒冬，你真的懂怎么裁员吗？

對照 H 公司，這篇文章真的很有趣

各大互联网公司架构演进之路汇总

將中國大陸的比較大的互聯網架構演進文章都收集得好好的．

Machine Learning

有聲書/影片心得

前提

每週五是我們公司的資料科學家讀書會時間，常常這類時間我可能都會在外面跟客戶開會無法參加． 但是這個禮拜總算把時間空出來參加，還好聽得懂內容跟為何要這麼做，所以相當的開心．

本週分享的是 Clustering 中的 K-Means ， K-Means++ 與 \(K-MC^2\) 也就是有名的文章 K-MC2: Approximate K-Means++ in Sublinear Time

其中 K-MC2 : K-Means++ with Markov chain Monte Carlo.

簡單筆記

• Fast and Provably Good Seeding for means
  • K-mean
    • 計算 k-gram 之間距離
    • 如果以三角形來說 tri-gram
    • 透過”三角不等式”

      • 第三邊不小於

        1 - 2

      • 第三邊不能大於

        1+ 2

    • 透過這樣來限縮第三邊的範圍可以加速 k-means 運算
  • K-mean++
    • 解決 k-mean 容易因為初始值導致 clustering 效果不佳
    • 透過修正取點的方式（比較遠的比較容易被取到) 透過機率性的方式
    • 取點只做第一次，後面還是使用 k-mean 來計算
  • MCMC Samling (K-MC2)
    • 在做 clustering 中心點取樣的時候
    • 透過取樣後 clustering 中心點，然後來分群
    • 透過 Markov Chain
    • [優點]
      • 以往做 K-mean 挑點，需要 k * m
      • 透過這個方式可以不在需要把每個點都走過挑選

思考脈絡與筆記

• K-Means
  • 優點:
    • 分群效能快，取樣隨便取．
  • 缺點：
    • 精準度不足，當一開始的取樣點不好的時候．需要不斷重新取樣來重新計算．
• K-Means++
  • 優點(解決 K-Means 問題):
    • 分群精准度好
  • 缺點:
    • 取樣的時間複雜度變高．試著每次取樣比較遠的點．
• K-MC2
  • 優點(解決 K-Means++ 問題):
    • 分群精準度好之外，也減少了取樣的複雜度．
  • 缺點:
    • 需要Markov Chain length 超過一定比例的 m
    • 你的精準度，就會達到 K-Means++

圖表

代碼 github.com/obachem/kmc2 :

安裝

pip install numpy
pip install kmc2

不過… macOS 會報錯

kmc2.c:232:10: fatal error: 'numpy/arrayobject.h' file not found
    #include "numpy/arrayobject.h"
             ^
    1 error generated.
    error: command 'clang' failed with exit status 1
    

解決方式

解法

export CFLAGS="-I /usr/local/lib/python2.7/site-packages/numpy/core/include $CFLAGS"

範例

import kmc2
import numpy
X = numpy.random.random((3, 3))
seeding = kmc2.kmc2(X, 5)  # Run k-MC2 with k=5

參考資料:

• An Introduction to MCMC for Machine Learning
• Fast and Provably Good Seedings for k-Means
• Introduction to Markov Chain Monte Carlo
• K-MC2：Approximate k-means++ in sublinear time
• Markov Chains
• obachem/kmc2: Cython implementation of k-MC2 and AFK-MC2 seeding

前提

2016/12 底由 CoreOS 主辦的 TECTONIC 2016 Summit 裡面有將 Kubernetes 1.5 做了一整個清楚的說明． Kubernetes 1.5 （與未來) 針對了大家一直以來的痛點做了很多的改進，並且用很生動的範例來解釋如何使用．相當推薦的好影片，以下快速整理一下:

簡化安裝流程: (KubeAdm, KubeFed)

KubeAdm: 一直以來安裝 Kubernetes 一直都不是簡單的事情 (與 Docker Swarm 與 DCOS 比較起來) ．當然 Google 找出了解決方式，就是 KubeAdm ( 跟 Docker Swarm 一樣的使用方式)

個人有使用過 KubeAdm ，真的使用起來就像 Docker Swarm Mode 一樣簡單．就是 init 之後，其他就透過 join 來加入就好．

KubeFed: 就是 Kubernets 解決多個集群的問題．

支援更複雜的排程: (Taint, Toleration, Forgiveness 目前都還沒完成)

• Taint/Toleration (issue 25320) : 透過 Taint 標記每個節點的特性 （比如說機器具有 GPU)，然後 Toleration 可以挑選具有 GPU 的機器 （反之，沒有透過 Toleration 的 Pod 無法分配到 Taint 上面． 相同的也可以設定使用者特定的 Pod 在特定幾台專屬用該使用者機器上． 細節在這裡

• Forgiveness(issue 1574): 可以透過對於 pod 的 health check 判別是否 pod 已經出問題，如果出問題會移到另外的節點重啟．

• Disruption Budget: 可以透過他來做 stateful server 的關閉與升級． 細節在這裡

• Network Policy Object: 可以設定哪些 pod 可以跟哪些 pod 溝通，甚至可以規定到單向． 細節在這裡

如何更輕鬆地不少複雜的軟體服務?: (比如說成套的服務套件，或是有優先順序？)

HELM: The Kubernetes Package Manager : 就把它當成 Kubernetes apt-get，可以快速幫你安裝軟體．

投影片

在這裡

Preface

Our cassandra instance sometime got crash mess amount of data. To backup those data to another storage is task need to do.

CQLSH

First backup canssandra schema

Export entire schema of your cassandra.

cqlsh -e "DESC SCHEMA" > user_schema.cql

Or you can specific your keyspace here.

cqlsh -e "DESC SCHEMA" > user_schema.cql

Export and Import cassandra data

Export

COPY <tablename> [ ( column [, ...] ) ]
     FROM ( '<filename>' | STDIN )
     [ WITH <option>='value' [AND ...] ];

For example

cqlsh> COPY log.parts FROM STDIN;

Another example to transform output format

cqlsh> COPY log.chatlogs (ts, content, other) TO './chatlog.dat'
   ... WITH DELIMITER = '|' AND QUOTE = '''' AND ESCAPE = '''' AND NULL = '<null>';

Import

cqlsh> COPY emp (empid,deptid,last_name,first_name) FROM 'temp.csv';

Troubleshooting

1. Cannot dump all DB because partition.

Error for (-5813055698912042437, -5769658640073958582): Failed to connect to all replicas ['10.123.456.789'] for (-5813055698912042437, -5769658640073958582), errors: ['NoHostAvailable - (\'Unable to connect to any servers\', {\'10.123.456.789\': error(None, "Tried connecting to [(\'10.123.456.789\', 9042)]. Last error: timed out")})'] (will try again later attempt 1 of 5)

Ans:

Because your cassandra has three partition, and it is in GCE. We only export one port for cqlsh remote connect. So, you could not get any data from your other two partition.

Try install cqlsh in GCE machine with pip install cqlsh.

1. pip install cqlsh has some problem with copy.

'module' object has no attribute 'parse_options'

**Ans: **

We could not use cqlsh from pip, suggestion use cassanra’s cqlsh. Refer jira

sudo docker run -it cassandra /usr/bin/cqlsh

Refer:

• stackoverflow: Import and export schema in cassandra
• Simple data importing and exporting with Cassandra
• Export/Import Data in Cassandra Table
• AttributeError: ‘module’ object has no attribute ‘compress’

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

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

網路文章心得:

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

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

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

本週摘要

本週工作上有個里程碑，很開心夥伴們能夠準時的交付出產品．雖然我們也踩了不少雷，不過我們完成了!!

目前一邊在看 udacity 的 Introduction Machine Learning 一邊也跟著公司同事們學習相關論文．相當充實!!

Go

Contributing to the Go project

2016 的舊文章，不過很實用．

由於 Go 專案都是放在 Gerrit 想要貢獻給 #golang 專案，卻又不知道該如何開始？ 這篇文章提供一整個流程的介紹，幫助你可以提交你的第一個 PR 給 Golang， 來看看這篇文章吧

The 9 most popular Golang links from 2016

有人幫忙精選了在 2016 的九篇最受歡迎的 Golang 相關文章，其中前五篇是:

• 1: What Should We Be Excited About in Go 1.8?
• 2: Go’s Alias Proposal and All My Concerns of Google Controlling Go
• 3: Go Best Practices, Six Years In
• 4: Introducing Go 2.0 (A Thought Experiment Only)
• 5: Ten Million Concurrent Websockets

Grumpy: Go running Python!

Google open source 為了解決很多 legacy 的 python code ，開發了一個工具可以讓你將 Python 轉換成 Go ，或是在 python 裡面跑 go 的套件．

一些重點整理:

1. Grumpy (脾氣暴躁 XD) 把 令人討厭的 GIL (Global interpreter lock) 拿掉了．換成 Go 的 GC 來管理．可以讓跑 python 的時候 multiple thread 更快． Grumpy 也不是第一個把 GIL 拿掉的 Python runtime, IronPython/Jython 都這樣幹過

2. 目前 Grumpy 支援度不夠，所以大家使用前看一下 issue list (光是 import “/”, “.” 就有些問題 refer issue 11)

3. Grumpy 不知道 CPython 的部分，所以 numPy 跟 opencv 都不能用． (其實還不少不能用的，畢竟還 alpha)

4. 也是可以跑 Interactive shell “make run” 就可以了…

5. 目前僅支援 python 2.7 (畢竟還有四年可以活 XD)

最後，為了呼應拿掉 GIL ， Russ Cox 也發了篇十年前的 C 與顏文章．來解釋 lock 有多痛苦 XDDD

想清楚了解 Python GIL 是什麼，可以看看這篇 slide

Python

Android/JAVA/NODE.JS/Scala

Migration From Spark 1.x to Spark 2.x

如何將你手邊 Spark 1.x 的代碼移植到 Spark 2.x 裡面．有些 package 位置有換得的部分要注意一下．

Docker

Kubernetes

Setting up OpenAI’s Kubernetes EC2 autoscaler in the cluster installed by kops

同事寫的相關安裝文件，整理的不錯．

iOS/Swift

其他程式語言

Rust: Reword ‘stupid’ and ‘crazy’ in docs.

如何在文件中把一些比較激進的文字修改成比較溫和的文字 XDD

論文收集

網站文章

【长城】原来是一部细思极恐的IT大片

雲端架構師如何來看”長城”這部賀歲大片． HA 的怪是哪招？ XDD

Machine Learning

berkeley 2017 春季的 Deep Reinforcement Learning 課程

Breaking things is easy

Nicolas Papernot 和 Ian Goodfellow 探討機器學習模型的資安問題，本文列出了三招，摘要如下：

1. 對資料集下毒：在已上線的模型中，餵幾個最能增加模型預測錯誤的資料點。例如莫里雅提教授送福爾摩斯穿一雙新鞋子，讓警方認為那雙鞋子就是福爾摩斯穿的，接著莫再穿著另一雙一樣的鞋子去犯案，來入罪福爾摩斯。
2. 惡意輸入讓模型預測錯誤：例如一隻熊貓加上一些人眼無法察覺的雜訊，可讓機器預測為長臂猿。要使用這種攻擊需要知道模型參數
3. 隱私問題：壞人的目標是想辦法取得一部分帶有使用者隱私的訓練資料，或是觀察模型的預測來擷取隱私。例如觀察智慧型手機鍵盤輸入的預測，可以約略知道使用者常打什麼關鍵字。

(以上文字轉錄自 智程梁)

Learning from Simulated and Unsupervised Images through Adversarial Training

Apple 發表的第一篇跟 Machine Learning 相關的論文，內容圍繞著 GAN 與影像處理．

Matching networks for one shot learning

Morning Paper 是每天會幫你讀一篇論文，然後寫下導讀跟心得． 今天談如何透過極少的object 來做分類

有聲書/影片心得