[TIL][Python] Let's play darkflow and face_recognition

darkflow

https://github.com/thtrieu/darkflow

face_recognition

https://github.com/ageitgey/face_recognition

How to install in Mac OSX

  • Install opencv3 + python3 + dlib

  • Install cython on Python3: pip3 install cython
  • Install darkflow
    • git clone https://github.com/thtrieu/darkflow.git
    • cd darkflow
    • python3 setup.py build_ext --inplace
    • pip3 install -e .
  • Install face_recognition
    • pip3 install face_recognition

[TIL][Python] OpenCV with Python2/Python3, dlib for python3

Python2 (opencv2) with Homebrew

Python 2

  • brew install python
  • brew install opencv
  • python
>>> import cv2

Python3 (opencv3) with Homebrew and PIP

Python3

  • brew install python3
  • brew uninstall opencv3
  • brew install opencv3 --without-python --with-python3
  • echo /usr/local/opt/opencv3/lib/python3.6/site-packages >> /usr/local/lib/python3.6/site-packages/opencv3.pth
  • python3
>>> import cv2

Refer to this

Install dlib (only for Python3)

dlib is very useful for face detection machine learning, but it is hard to install on mac osx with python. compile issue and compile issue2

I got some script from this, but still not working for me.

Using PIP3 to install dlib for python3

  • Install boost for python3 but not for python2
    • brew install boost-python --with-python3 --without-python
  • pip3 install dlib
  • python3
>>> import dlib

Reference

[TIL] 為了自己的習慣,弄了一個簡單的服務 Github issue bookmark

本篇提到的開源專案:

https://github.com/kkdai/bookmark-makerserver

https://github.com/kkdai/bookmarks

起因

平時習慣拿 twitter 作為 bookmark 的概念,看到喜歡的鏈結或是網站就直接 tweet 出來. 但是都沒有記錄下來.

之前有想過透過程式設計週記的方式來記錄下來,但是又覺得太過流水帳而且沒有辦法有系統的分類.

想著想著就想到透過 Github Issue 來做這件事情,有以下的好處:

  • 可以透過 Label 來分類
  • 可以使用 Github 的搜尋功能來尋找想找的部分
  • 可以補充很多的 comment 在同一個 issue 上面做為閱讀後的心得記錄.更方便未來搜尋.

架構

一如往常,我依舊使用許多免錢的架構.並且將整個流程都開源給大家分享,大家應該可以在五分鐘內建立自己的整體流程.

你可能要自己做的事情如下:

  • 取得 Github Auth Token (去這裡)
  • 取得 IFTTT Maker 帳號與權限
  • 修改一下 IFTT Maker 資料.

詳細流程都在 https://github.com/kkdai/bookmark-makerserver

支援的語法範例

這裡提供一些 tweet 的範例,還有他會變成何種 github issue

gernest/mention: Twitter like mentions and #hashtags parser for Go(Golang) # easy way to get hashtag in #golang https://github.com/gernest/mention

  • Title: gernest/mention: Twitter like mentions and #hashtags parser for Go(Golang)
  • Content: easy way to get hashtag in
  • Labels: hashtags,golang
  • Link: https://github.com/gernest/mention

希望能提供給一些需要的人,有任何問題歡迎發 issue 討論 ..

未來發展

幾個階段…

  • 第一個階段應該會先支援 Facebook 貼文,並且根據我臉書文章格式來貼 Github issue
  • 等收集好大量的 Github issue 後,應該會寫另外一個工具來定期(每個禮拜) 根據 Github issue 來產出 Monthly_README.md
  • 甚至可以把這個機制弄成電子報… 恩… 應該說是部落格好一點.

[Coursera] Illinois: Cloud Computing Concept Part 1 : Week 5

課程鏈結: 這裡

學習鏈結:

課程內容:

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

這整堂課主要是圍繞著 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

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

前提:

Snapshots

Global Snapshot

Global Snapshot =

  • Global State =
  • Individual state + communication channel

時間不同步的時候所造成 Global Snapshot 會失敗的原因

  • 時間不正確
  • 無法抓到溝通的狀態

任何造成 Global Snapshot 變動的原因:

  • Process send/receive message
  • Process move one step

以一個範例來解釋演算法

基本定義:

  • There are no failures and all messages arrive intact and only once
  • The communication channels are unidirectional and FIFO ordered
  • There is a communication path between any two processes in the system
  • Any process may initiate the snapshot algorithm
  • The snapshot algorithm does not interfere with the normal execution of the processes
  • Each process in the system records its local state and the state of its incoming channels

Chandy-Lamport Global Snapshot Algorithm

Wiki

  • 隨便挑一個 Process () 來對所有其他的 Process 傳送一個 Marker 訊息 )
    • 並且開始記錄所有進來的 Message (InComing Msg)
  • 如果收到的 Process 並沒有收過
    • 先將該訊息 的 State 標示為 “empty” 一樣開始傳送 Marker 給其他 Process
  • 如果已經收過了
    • 代表所有 Process 已經開始在傳遞 Marker 而其他訊息已經完整的到了.
  • 停止條件:
    • 當所有節點都收到 Marker 代表儲存的資料已經完成.
    • 當所有 Process 收到其他訊息都是 Marker (需要有 N - 1 個)

最後還要把各個分開的 Snapshot 組合成 Global Snapshot

停止條件,所有節點都收到 Marker 外,所有等待外部回來的資料 (marker) 也都收到.

將 Snapshot 統一回收整理成一個大的 snapshot

P.S. 這個演算法並不記錄對外的資料,因為由收到資料的人統一來記錄結果.

Consistent Cut

講解到 Snapshot ,不免俗就要講到擷取 snapshot 的時間點 (cut).

Consistent Cut

  • A cut C is a consistent cut if and only if: for (each pair of events e, f in the system)

也就是說每一個 pair f->e (f happen before e) 如果有 e in the cut 那麼必須 f 也必須要 in the cut. 反之不需要滿足.

透過 Chandy-Lamport Global Algorithm 截取的 Snapshot 都滿足 Consistent Cut

證明: in the cut (透過 記錄到) 那麼 (透過 記錄到) 必定也在 snapshot 之中.

  • We already know
  • We also know in the cut but not in the cut
  • Because and already record state for
  • Since happen before , if not in the cut so must not in the cut too.
  • Contracdition.

Safety and Liveness

Conrectness => Liveness or Safety

Definition:

  • Liveness: something good eventually happen
  • Safety: Guarantee something bad never happen

Chandy-Lamport Algorithm 與 Safety, liveness 的關係:

  • 一旦 Stable 就會一直保持 Stable
  • 只能滿足 Liveness but non-safety

Multicast

Communication 的種類:

  • Unicast: 訊息從一個傳送者送到一個接收者
  • Multicast: 訊息寄送給一群的人
  • Broadcast: 訊息寄送給全部的人

Multicast Ordering

探討順序的時候,有以下三個方式的 multicast :

  • FIFO Ordering
  • Causal Ordering
  • Total Ordering

FIFO Ordering:

這邊的 FIFO 代表的是,先發送的人就會被收到.(同一個 Process 上):

  • 先發送的人,會先被人收到. (同一個發送的人,先後順序在某個節點上應該會保持一樣的順序.)
  • Ex:
    • ,
    • 根據 FIFO 原理
    • 收到順序也會是

Causal Ordering:

Causal Ordering 代表的是因果的關係,也又是接受到的人絕對比傳送的人還晚. (因為傳送過程的 latency) 這邊指的是跨 Processes ,的因果關係.

Causal Ordering -->(imply) FIFO Ordering

由於 Causal Ordering 可以跨 processes 跟同個 process . 如果是在同個 Process 的話,就是指的是先入先出 (FIFO) 因為同一個的先後順序必定影響該 multicast 的順序.

Total Ordering:

所有 process 收到訊息的順序都相同.

Hybrid ordering

  • FIFO-Total:
  • Causal-Total:

Implement of multicasting

Implement FIFO Ordering

拿這張圖來解釋如何讓 FIFO Ordering 能夠滿足:

  • P1 有兩個 multicasting [1,0,0,0] 與 [2,0,0,0]
  • 會看到在 P3 那邊 [2,0,0,0] 比起 [1,0,0,0] 先到
  • 所以後面的需要先等一下 (buffered) 改成 [0,0,0,0] 等到後面到了才能改.
  • 但是 P1, seq: 2 與 P3 seq: 1 不會有這樣的問題.因為 FIFO Ordering 並不局限於跨線程

About total ordering

就是計算每個人收到的順序必須要跟開始發送的順序一樣(可跨程序) 就算是.計算的方式就是去累進收到的順序.

Implement Causal Ordering

滿足條件:

	所有的接收者都必須有著相同的接受順序(跨程序).
	
	If multicast(g,m) -> multicast(g,m’)
	then any correct process that
	delivers m’ would already have
	delivered m.

做法:

  • P1 與 P2 原本就滿足 Causal Ordering ,故不提.
  • P3 先收到 P2 msg ,這時候就知道要等待 P1 msg 因此就 buffer
  • P3 後來又收到 P4 msg ,又必須要等待 P1 msg 所以就 buffer
  • P3 要一直收到 P1 msg 之後,才會把 P2 與 P4 msg 收起來
  • 如此一來就滿足 Causal Ordering

Reliability of multicast

	Reliability = Correctness = Ordering 

在此討論的 Reliability 都是基於 non-Faulty (沒有錯誤發生的) process 上面來討論.

現實中的實現方式

在現實中如何透過實現類似 multicast 的確保方式?

	每個 process 收到之後,在發送 multicast 給其他 process 作為標記

透過這樣的方式,才能確保每個 process 收到的 msg 順序是正確的,因為順序需要有外部的資訊來紀錄.

Virtual Synchrony

View

每個 Process 都維護一套自己的 member list ,那樣的 member list 就稱為 “View”

View Change

當 Process 發生了 “新增”, “離開”, “故障” .. 等等影響 member list 的事情就稱為 View Change

Virtual synchrony

Virtual Synchrony 保證所有的 View Change 都會發生於相同的順序上.

ex:

  • P1 join
  • {P1, P2}, {P1, P2, P4} , {P1, P2, P3} are all view change
  • 所以 P2 會收到 一樣順序 {P1, P2}, {P1, P2, P4} , {P1, P2, P3}

Paxos

Consensus Problem

問題釐清:

為何 SLA 永遠都是 five-9' 獲釋 seven-9' 永遠不能夠 100%?

解答:
所謂的錯誤,不光是任何人員控管與公司流程上的錯誤.當然也不在於機器本身的錯誤. 而是在於是否能夠達到一致性( Consensus ).

Consensus Statement:

Consensus Constraints:

  • Validity: 需要全部人提議相同數值才能決定.
  • Integrity: 最後決定的數值必定是某個 process 提議出來(不是無中生有)
  • Non-triviality: 至少有一個初始狀態,而不是常見的 all-0, all-1

Consensus In Synchronous Systems

Synchronous Systems 的特性:

  • 訊息有時間限制
  • Process 間交換訊息有時間限制 (round: f, upper bound)

如果能夠解決 Synchronous Systems 的一致性 (Consensus) 問題 ,那麼是否能夠解決 Asynchronous System

–> 將訊息交換的時間限制延長到 N

Paxos

關於 Paxos

並沒有完全解決 Consensus 的問題,

但是可以提供兩種主要特性:

  • Safety:
    • 不違背一制性
  • Evantual liveness:
    • 如果有問題發生,還是可以達成一制性. (但是不保證,原因後續)

並且在以下系統都有使用:

  • zookeeper
  • Chubby

Paxos 三個階段:

Election

  • 每個節點 (node) 會送出 election request
  • 需要達到大多數 (majority) (或是稱為 Quorum)
  • Paxos 允許 multiple leader (這裡先不討論那麼複雜)

產出會有一個(或多個) Leader

Bill

  • Leader propose value (v)
  • 如果節點同意會回覆

Law

  • 如果 Leader 獲得大多數的同意
  • 會發出 Law (or Learn) request 給每個節點,確認數值的紀錄

[TIL] Advanced Scheduling in Kubernetes

前提

在 Kubernetes 或是 DCOS 這種集群管理系統上要分配工作相當的方便,但是有些時候我們需要指定某些特定的任務在指定的機器上面才能夠執行.

在 DCOS 上面可以使用 Constraints

Kubernetes 裡面要達到指定 POD 到特定的機器上面,一般來說而言有以下幾種方式:

  • nodeSelector (1.0)
    • Kubernetes 1.6 之前官方推薦的方式,不過 1.6 之後請使用 Affinity
  • Affinity (After Kubernetes 1.6)
  • Taints and Tolerations (After Kubernetes 1.6)

nodeSelector

簡單的方式就是透過對於 node 設定不同的 label 來讓 nodeSelector 可以找到適當的機器.

比如說你有一台機器有特殊的硬體,比如說 GPU

kubectl label nodes windows-node1 hardware=gpu 

以本次的範例來說,我們部署了不少的機器.其中有一台專門負責部署 Web App

kubectl label nodes windows-node1 usage=app 

設定好之後,也可以去查詢你目前節點所有的 labels

kubectl get nodes --show-labels 

提供一個官方的簡單範例,讓我們了解如何使用 nodeSelector

apiVersion: v1
kind: Pod
metadata:
  name: nginx
  labels:
    env: test
spec:
  containers:
  - name: nginx
    image: nginx
    imagePullPolicy: IfNotPresent
  nodeSelector:
    usage: app

試著跑起來看看…. (架設檔案名稱為 testpod.yaml)

kubectl create -f testpod.yaml

查看結果….

kubectl get pods -o wide

以下的部分只允許在 Kubernetes 1.6 以後才能正確執行.

Affinity (After Kubernetes 1.6)

Affinity 透過類似的方式可以指定 POD 所執行的位置,但是語法不是很類似. 以下先展示一個跟上面範例相同語法的範例

(testpod_affinity.yaml)

apiVersion: v1
kind: Pod
metadata:
  name: nginx
  labels:
    env: test
spec:
  affinity:
    nodeAffinity:
      requiredDuringSchedulingIgnoredDuringExecution:
        nodeSelectorTerms:
        - matchExpressions:
          - key: usage
            operator: In
            values:
            - app
  containers:
  - name: nginx
    image: nginx
    imagePullPolicy: IfNotPresent

那大家會問說, Affinity 究竟功能有哪些比起 nodeSelector 還強大.讓之後官方會建議使用這個?

這邊稍微解釋一下:

優先權語法的加強:

這邊有兩種 Scheduling 的方式,

  • requiredDuringSchedulingIgnoredDuringExecution
  • preferredDuringSchedulingIgnoredDuringExecution

這兩種有些許的不同,由字面上可以看到一個是”必要” (required) 另一個則是 “偏好” (preferred) .

用法上的建議是,如果要部署的 POD 比較少,而且必須要部署在特定的機器上.可以使用 required .

而如果要部署的 POD 可能超過目標,已如說部署 10 個 POD 在五個區域中. 可以使用 Preferred 這時候有資源會以偏好的優先.

判斷語法的加強:

對於判斷上,也再也不是相等而已.還有以下的判斷語法可以使用.

  • In
  • NotIn
  • Exists
  • DoesNotExist
  • Gt (greater than)
  • Lt (lower than)

這邊的用法比較直覺,也就不再去補充了.

Taints and tolerations

前面介紹的 Affinity 是透過一種偏好的方式來選擇你的執行節點.也就是設定好策略之後讓 POD 透過 “吸引” 的方式來挑選他應該去的節點.

但是反過來,如果你有以下的情況該怎麼辦?

  • 如果有些機器絕對不能執行到某些的 POD 不然就會有效能的不完整或是極大的錯誤發生
  • 有台機器是要給某個 task 獨佔,分配之後就不希望他再去接任何其他的 task

類似這些的狀況,你就可以使用 taints .指令也相當的簡單….

kubectl taint nodes node1 key1=2:NoSchedule

這樣一來 node1 再也不會分配到任何的工作. (除非.. 等等再提)

恢復的方式也很簡單

kubectl uncordon node1

現在來討論剛剛的限制條件裡面的:

kubectl taint nodes node1 key1=2:NoSchedule

就是必須要 key 與 value 都要相同,並且要 effect (NoSchedule) 也相同. 才會被排到這個節點.

寫法可以參考以下: (某個 pod.yaml 中)

...
tolerations: 
- key: "key1"
  operator: "Equal"
  value: "2"
  effect: "NoSchedule"

其實 taints 還有更多應用可以探討… 先到這吧…

參考

[TIL][文章推薦] 設計高效能的 Hash Table

原文

Felix Chern: 設計高效能的Hash Table(一)

心得

還記得當初在寫 Consistent Hashing 的時候,一直不願意拿人家寫好的 Hash Function 來改,硬要自己寫一個.

結果發現寫出來的 Hashing 一直出問題.才知道原來 Hash Function 是實作 Consistent Hashing 的一個重點.

這一篇文章有了一些基本對於 Hash Function 的介紹,也把幾個好用的 Hash Function 一一的列出來.

其中包括了最近被移到了 Google 的 “highwayhash”

或是之前有介紹過在 Uber/ringpop 下作為 Consistent Hashing 的 farmhash

這篇文章相當推薦,原因如下:

  1. 作者 (Felix Chern) 目前似乎在 Google 工作,部落格文章都相當有深度.
  2. 有 Hash Function 列出的清單並且有簡單的介紹.

參考:

  • ringpop 是 Uber 的去中心化 App :
  • 這篇文章有下集,在這裡

關於實作與相關測試:

其實 Damian Gryski 實作了不少 Hash Function 的 Go 套件

HighWay Hash

其 Benchmark 如下:

 ~/s/g/s/g/d/go-highway   master  go test -bench=.             六  4/29 01:31:56 2017
BenchmarkHighway8-8    	50000000	        26.3 ns/op	 304.36 MB/s
BenchmarkHighway16-8   	50000000	        26.7 ns/op	 599.24 MB/s
BenchmarkHighway40-8   	50000000	        29.7 ns/op	1345.35 MB/s
BenchmarkHighway64-8   	50000000	        33.3 ns/op	1924.53 MB/s
BenchmarkHighway1K-8   	10000000	       137 ns/op	7452.07 MB/s
BenchmarkHighway8K-8   	 2000000	       873 ns/op	9378.40 MB/s

Farm Hash

其 Benchmark 如下:

 !  ~/s/g/s/g/d/go-farm   master  go test -bench=.    257ms  六  4/29 01:30:43 2017
BenchmarkHash32-8    	20000000	       100 ns/op
BenchmarkHash64-8    	20000000	        58.2 ns/op
BenchmarkHash128-8   	20000000	       123 ns/op

xxHash

這不是 Damian Gryski 實作的,是由 LiftOff Caleb Spare 但是做得很好而且也有被 InfluxDB 使用喔.

xxHash 是選定 64bit 輸出的通用 Hash Function ,使用範圍廣泛而且速度快.

結語:

本來想只是寫個簡單的推薦文,後來決定來跑跑看每個 Hash Function 的效能評比.跑完之後,又想去偷看是不是裡面都沒有使用除法.

發現其實 Hash Function 主要還是針對不同 CPU 的優化,讓他們的速度能夠更快.處理的資料類型能夠更多.

P.S.:

  • 其實 Damian Gryski 把幾乎所有 Google 出品的 Hash Function 都重寫成 Golang 版本.

  • Google 出了好幾個的 Hash Function 讓我覺得大公司對於 Hash Function 的注意.