cctg

2017/5/22

監督式機器學習方法 Supervised Machine Learning: 生成模型 (Generative Model) 與判別模型 (Discriminative Model)

機器學習是人工智慧的一個分支，讓機器透過某種學習方法，實現並解決人工智慧中的一些問題。機器學習演算法是從資料中自動分析獲得規律，並利用規律對未知資料進行預測的演算法。學習演算法需要用到大量的統計學理論，也被稱為統計學習理論。

Machine Learning 的分類

監督學習：從給定的訓練資料集中學習出一個函式，當新的資料到來時，可以根據這個函式預測結果，訓練資料中的目標是人工標註的。
無監督學習：與監督學習相比，訓練資料沒有人為標註的結果。常見的無監督學習演算法有聚類分析 Cluster Analysis。
半監督學習：介於監督學習與無監督學習之間。
增強學習：通過觀察來學習做成如何的動作。每個動作都會對環境有所影響，學習物件根據觀察到的周圍環境的反饋來做出判斷。

監督式機器學習方法 Supervised Learning

監督式機器學習方法 Supervised Learning 是 Machine Learning 中的一個方法，可以由訓練資料中學到或建立一個模式（函數 / learning model），並依此模式推測新的實例，換句話說，任務就是在觀察完一些訓練範例（輸入和預期輸出）後，利用這個函數去對任何可能出現的輸入的值，預測輸出的結果。

訓練資料是由輸入物件（通常是向量）和期待的輸出所組成。函數的輸出可以是一個連續的值（稱為迴歸分析），或是預測一個分類標籤（稱作分類）。

監督式機器學習方法可以分為生成方法和判別方法兩類，常見的生成方法有混合高斯模型、樸素貝葉斯法和隱形馬爾科夫模型等，常見的判別方法有SVM、LR等，生成方法學習出的是生成模型，判別方法學習出的是判別模型。

生成模型就是能夠隨機生成觀測數據的模型，也就是對影像、聲音以及對現實世界的一切其他實物（representations）進行創造的系統。如果 AI 學會了建立現實世界中的種種細節，例如現實中的圖像和聲音，這將幫助 AI 更好地理解現實世界的結構。

生成模型與判別模型的比較

生成式模型和判別式模型的區別很像人和機器的區別：機器採取的是完美主義，因為它可以不斷優化，追求極致。而人是把事情做得夠好就滿足了。

因為人類的構造天生跟機器不同，所以人類不需要跟 Alpha Go 比賽圍棋分出高下，Alpha Go 只專注在做圍棋這件事，並把它做到極限。

生成模型是所有變量的全機率模型，而判別模型是在給定觀測變量值前提下，觀測目標變量條件機率模型。

生成模型能夠用於模擬（即生成）模型中任意變量的分布情況，而判別模型只能根據觀測變量得到目標變量的樣本。

判別模型不提供觀測變量的分布建模，因此它不能夠表達觀測變量與目標變量之間更複雜的關係。因此，生成模型適用於無監督的任務，如分類和聚類。

由生成模型可以得到判別模型，但由判別模型得不到生成模型。

生成模型收斂速度比較快，如果樣本數量較多時，生成模型能更快地收斂於真實模型。生成模型中的聯合分佈能提供更多的資訊，但也需要更多的樣本和更多計算。

例如我們有一個輸入數據x，然後我們想將它分類為標籤y。最自然的做法就是條件概率分佈p(y|x)，這就是為什麼我們對其直接求p(y|x)方法叫做判別模型演算法。生成模型學習聯合概率分佈p(x,y)，p(x,y)可以通過貝葉斯方法轉化為p(y|x)，然後再用其分類。但是p(x,y)還有其他作用，例如，你可以用它去生成(x,y)。

假設我們有以下(x,y)形式的數據：(1,0), (1,0), (2,0), (2, 1)

那麼p(x,y)是：y 共有四種結果，0,0,0,1，產生的機率分別是 1/4，其中前面兩個 0,0，它的 x 都是 1，所以當 x 為 1，產生出 y 為 0 的機率是 1/4+1/4 = 1/2，不可能產生 y=1 的狀況，所以機率為0。而當 x 為 2，產生出 y 為 0 的機率是 1/4，產生出 y 為 1 的機率也是 1/4。目標是要生成 y，所以生成 y 的所有機率總和為 1。

            y=0   y=1

           -----------

   x=1 | 1/2   0

   x=2 | 1/4   1/4

而p(y|x) 是：因為當 x =1，y 一定為 0，所以在 x 為 1 的基本條件下，y 為 0 的機率為 1，如果 x = 2 的條件下，y 有 0 或 1 兩種可能，發生的機率分別是 1/2。目標是先以 x 為基本條件，在給定 x 之後，得到 y 的機率分佈。

           y=0   y=1

           -----------

    x=1| 1     0

    x=2| 1/2   1/2

如果有某項工作是要識別一個語音屬於哪種語言，有兩種方法達到這個目的：

1、把所有語言先都學會，然後就能識別任何一段新的語音了。

2、不去學習每一種語言，只學習這些語言模型之間的特徵及差別，然後再分類。只要學會了漢語和英語等語言的發音的差別，直接用這樣的差異去分類就好了。

第一種方法就是生成方法，第二種方法是判別方法。

生成算法嘗試去找到底這個數據是怎麼產生的，然後再對一個信號進行分類。基於你的生成假設，那個類別的資料最有可能產生這個信號，這個信號就屬於那個類別。判別模型不關心數據是怎麼生成的，它只關心信號之間的差異，然後用差異來簡單對給定的一個信號進行分類。

生成模型：一般是學習一個代表目標的模型，然後通過它去搜索圖像區域，然後最小化重構誤差。類似於生成模型描述一個目標，然後就是模式匹配了，在圖像中找到和這個模型最匹配的區域，就是目標了。

判別模型：將跟蹤問題看成一個二分類問題，找到目標和背景的決策邊界。它不管目標是怎麼描述的，只知道目標和背景的差異，然後你給一個新的圖像，看它屬於那一邊，就歸為哪一類。

生成式對抗網絡 GenerativeAdverserial Network GAN

有兩個系統，在互相對抗，兩個系統都試圖優化自己的目標函數。第一個系統對應判別式模型D：判別式模型D在試圖識別到來的樣本是否是自然真實的；它在儘量增大對真實樣本的識別率，同時減少對模擬生成的樣本的誤判率。

另一個系統則對應著生成式模型G：G希望它生成的模擬樣本可以在D那裡魚目混珠。所以G試圖最大可能地產生真實的樣本。判別器D從判別角度來說，判別的越好，D的目標實現的就越強大。

但對於生成器G來說，它要最小化（minimize）對方的優化函數，這就相當於最大化（maximize）它自己的優化函數。這個過程就像G和D在下棋一樣。

用一個AI對現實世界的圖像進行創造，再用另一個AI去分析結果並對圖像的真偽進行識別。兩個系統在競爭中不斷成長，最後兩個都達到最佳化。

將二者的關係想像成一個藝術家和一個文藝批評家。作為藝術家，生成模型希望愚弄藝術批評家，讓後者認為它畫出來的東西是真實的。因為藝術批評家努力地將這些畫辨認為假畫，藝術家慢慢學會了如何摹擬那些真的東西，而這原本只靠它自己是做不到的。

References

楊強教授漫談《西部世界》、生成式對抗網絡及遷移學習

機器學習中的貝氏定理：生成模型 (Generative Model) 與判別模型 (Discriminative Model)

生成模型與判別模型

機器學習“判定模型”和“生成模型‘有什麼區別？

GAN誕生記：最火的AI模型，來自一群博士的酒後爭吵

2017/5/15

以 docker 測試網站

docker container 本身並沒有 persistence 的機制，但可以透過共享 valume 的方式，將本地機器的某個實體的路徑，綁定到 container 中，由於 container 疊加式的文件檔案系統，我們還是會覺得只有一個檔案系統。

靜態網站

在 sample 目錄中，製作一個 Dockerfile 檔案

FROM ubuntu:latest
MAINTAINER yaocl
ENV REFRESHED_AT 2016-12-23

# 安裝 ngnix
RUN apt-get -yqq update && apt-get -yqq install nginx

# 建立 website 目錄
RUN mkdir -p /var/www/html/website

# 調整 nginx 設定
ADD nginx/global.conf /etc/nginx/conf.d/
ADD nginx/nginx.conf /etc/nginx/

# TCP Port 80
EXPOSE 80

另外準備兩個 nginx 設定檔：

nginx/global.conf

server {
        listen          0.0.0.0:80;
        server_name     _;

        root            /var/www/html/website;
        index           index.html index.htm;

        access_log      /var/log/nginx/default_access.log;
        error_log       /var/log/nginx/default_error.log;
}

nginx/nginx.conf

user www-data;
# process 數量
worker_processes 4;
# 紀錄 process id
pid /run/nginx.pid;

# 不讓 nginx 進入 daemon 狀態，以前景執行，否則會讓 container 啟動後直接停掉
daemon off;

events {  }

http {
  sendfile on;
  tcp_nopush on;
  tcp_nodelay on;
  keepalive_timeout 65;
  types_hash_max_size 2048;
  include /etc/nginx/mime.types;
  default_type application/octet-stream;
  access_log /var/log/nginx/access.log;
  error_log /var/log/nginx/error.log;
  gzip on;
  gzip_disable "msie6";
  include /etc/nginx/conf.d/*.conf;
}

在 website 目錄，放一個 index.html 網頁。

所有檔案的目錄結構為

sample\
    Dockerfile
    nginx\
        global.conf
        nginx.conf
    website\
        index.html

以 build 指令產生 docker image

docker build -t yaocl/nginx .

可透過 history 查看 image 的過程

docker history yaocl/nginx

啟動 container，以 -v 將 website 目錄綁定為 container 的 /var/www/html/website 目錄，覆蓋掉原本在 image 中的那個目錄，我們就可以修改 website 的網頁，並即時由 browser 看到網頁的結果。

$ docker run -d -p 80:80 --name website \
    -v $PWD/website:/var/www/html/website \
    yaocl/nginx nginx
b64855fbfc6bb313c9190eeead2f1d433d28b9d759dba85d06399841e0ef9f78

如果加上 :ro ，就變成 readonly，rw 則是可讀寫

docker run -d -p 80:80 --name website \
    -v $PWD/website:/var/www/html/website:ro \
    yaocl/nginx nginx

連結兩個 container

如果我們需要用到兩個 containers，其中一個用來執行 application server，另一個執行 redis或 db，這時候有兩種方式，可以讓兩個 containers 可以互相連結使用服務。

我們建立一個 redis image 跟 container，另外產生一個只有 os 的 container，讓測試讓後面那個 container 可以用 redis-cli 連結到 redis server。

產生 redis db server 的 Dockerfile

FROM ubuntu:latest
MAINTAINER yaocl
ENV REFRESHED_AT 2016-12-23

RUN apt-get -yqq update && apt-get -yqq install redis-server redis-tools

EXPOSE 6379

ENTRYPOINT ["/usr/bin/redis-server"]
CMD []

產生 redis image，並啟動 container

docker build -t yaocl/redis .

docker run -d -p 6379:6379 --name redis yaocl/redis

如果剛剛沒有指定主機的 port 可以用 port 指令查詢 port

$ docker port redis 6379
0.0.0.0:6379

以本機的 redis-cli 測試 redis:6379

$ redis-cli -h 127.0.0.1 -p 6379
127.0.0.1:6379>

要從 container: redis-cli 連接到 redis，有兩種方式，一種是使用 docker 的內部網路 network stack，安裝 docker 時就會建立一個 docker0 的網路介面，每一個 docker container 都會在這個網路上分配到獨立的 172.16~172.30 這個範圍的 ip。

預設這些網路之間不能互相連接，如果搭配修改 iptables（DNAT），就可以讓 container 互相溝通，但 docker for mac 找不到 docker0 這個 network，如果要測試，可以參考 Docker container networking 的說明。

我們用另一個比較常見的方式，直接讓 container 互相連接。

在 mac 先將 lo0 綁定一個新的 ip

sudo ifconfig lo0 alias 10.200.10.1/24

首先刪除掉剛剛的 redis container

docker stop redis

docker rm redis

重新執行一個 redis container，但不指定 -p 6379

docker run -d --name redis yaocl/redis

redis-cli 的 Dockerfile

FROM ubuntu:latest
MAINTAINER yaocl
ENV REFRESHED_AT 2016-12-23

RUN apt-get update
RUN apt-get -y install inetutils-ping redis-tools

ENTRYPOINT ["/bin/bash"]
CMD []

產生 redis-cli image

docker build -t yaocl/redis-cli .

docker run --name webapp -t -i yaocl/redis-cli

如果不是用 docker for mac，可以用 link 的方式直接將 container 連接起來。

docker run --name webapp --link redis:db -t -i yaocl/redis-cli

啟動 redis-cli container webapp 後，就能直接用 db 這個 hostname 連接到 redis server

root@79bb961c2b78:/# redis-cli -h db
db:6379>

root@79bb961c2b78:/# env
HOSTNAME=79bb961c2b78
DB_NAME=/webapp/db
DB_PORT_6379_TCP_PORT=6379
TERM=xterm
DB_PORT=tcp://172.17.0.2:6379
DB_PORT_6379_TCP=tcp://172.17.0.2:6379
LS_COLORS=rs=0:di=01;34:ln=01;36:mh=00:pi=40;33:so=01;35:do=01;35:bd=40;33;01:cd=40;33;01:or=40;31;01:mi=00:su=37;41:sg=30;43:ca=30;41:tw=30;42:ow=34;42:st=37;44:ex=01;32:*.tar=01;31:*.tgz=01;31:*.arc=01;31:*.arj=01;31:*.taz=01;31:*.lha=01;31:*.lz4=01;31:*.lzh=01;31:*.lzma=01;31:*.tlz=01;31:*.txz=01;31:*.tzo=01;31:*.t7z=01;31:*.zip=01;31:*.z=01;31:*.Z=01;31:*.dz=01;31:*.gz=01;31:*.lrz=01;31:*.lz=01;31:*.lzo=01;31:*.xz=01;31:*.bz2=01;31:*.bz=01;31:*.tbz=01;31:*.tbz2=01;31:*.tz=01;31:*.deb=01;31:*.rpm=01;31:*.jar=01;31:*.war=01;31:*.ear=01;31:*.sar=01;31:*.rar=01;31:*.alz=01;31:*.ace=01;31:*.zoo=01;31:*.cpio=01;31:*.7z=01;31:*.rz=01;31:*.cab=01;31:*.jpg=01;35:*.jpeg=01;35:*.gif=01;35:*.bmp=01;35:*.pbm=01;35:*.pgm=01;35:*.ppm=01;35:*.tga=01;35:*.xbm=01;35:*.xpm=01;35:*.tif=01;35:*.tiff=01;35:*.png=01;35:*.svg=01;35:*.svgz=01;35:*.mng=01;35:*.pcx=01;35:*.mov=01;35:*.mpg=01;35:*.mpeg=01;35:*.m2v=01;35:*.mkv=01;35:*.webm=01;35:*.ogm=01;35:*.mp4=01;35:*.m4v=01;35:*.mp4v=01;35:*.vob=01;35:*.qt=01;35:*.nuv=01;35:*.wmv=01;35:*.asf=01;35:*.rm=01;35:*.rmvb=01;35:*.flc=01;35:*.avi=01;35:*.fli=01;35:*.flv=01;35:*.gl=01;35:*.dl=01;35:*.xcf=01;35:*.xwd=01;35:*.yuv=01;35:*.cgm=01;35:*.emf=01;35:*.ogv=01;35:*.ogx=01;35:*.aac=00;36:*.au=00;36:*.flac=00;36:*.m4a=00;36:*.mid=00;36:*.midi=00;36:*.mka=00;36:*.mp3=00;36:*.mpc=00;36:*.ogg=00;36:*.ra=00;36:*.wav=00;36:*.oga=00;36:*.opus=00;36:*.spx=00;36:*.xspf=00;36:
DB_ENV_REFRESHED_AT=2016-12-23
PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin
REFRESHED_AT=2016-12-23
PWD=/
DB_PORT_6379_TCP_ADDR=172.17.0.2
DB_PORT_6379_TCP_PROTO=tcp
SHLVL=1
HOME=/root
no_proxy=*.local, 169.254/16
DB_ENV_no_proxy=*.local, 169.254/16
_=/usr/bin/env

root@79bb961c2b78:/# ping db
PING db (172.17.0.2): 56 data bytes
64 bytes from 172.17.0.2: icmp_seq=0 ttl=64 time=0.223 ms
64 bytes from 172.17.0.2: icmp_seq=1 ttl=64 time=0.139 ms

References

The Docker Book

Networking your docker containers using docker0 bridge

How to create a bidirectional link between containers?

2017/5/8

docker for mac

docker 在 mac 上原本是用 boot2docker，但現在已經有了原生的 Docker for mac，Docker for mac 不再是使用 VirtualBox，而是改用比較輕量化的 macOS 虛擬機 HyperKit。

Docker for mac 需要 OS X El Capitan 10.11 以上的作業系統，以及 2010 或更新 Mac 硬體，以支援 MMU virtualization。

在 Get started with Docker for Mac 這個網頁可以下載 docker，目前分為 Stable 及 Beta 兩個版本，我們是安裝 Stable 版本，但還是隨時可以切換到 Beta 版。

安裝完成並執行後，可以在狀態列看到 docker 那隻鯨魚。

docker 的元件

客戶端及伺服器: client 發送 request 給 docker daemon，由 damone 代理工作並回傳結果

image: 由指令一步一步建構出來的 image，類似 container 的 source code
registry: docker 以 registry 保存 image，分為 public 及 private 兩種，公用的 registry 稱為 docker hub，可以自己架設 private registry。
container: image 是 docker 的建構及打包對象，而 container 是啟動跟執行的目標。

docker 的技術元件

libcontainer: 就是原生的 Linux 容器
獨立的 kernel namespace 用來隔離文件、process、網路
每個 container 都有自己的 /root，獨立的文件系統
獨立的 process
獨立的網路
資源隔離及分組: 使用 cgroups 將 CPU 及記憶體獨立分配給每個 container
copy-on-write: 分層的文件系統，但 user 還是只能看到所有文件疊加後的結果，會覺得只有一個文件系統
log: container 的 STDIN, STDOUT, STDERR 都會記錄到 log中
互動式 shell: 可建立虛擬的 tty terminal，連接到 STDIN

測試 docker

我們可以利用 ubuntu 的 image，執行一個 echo 指令進行 docker 的測試，在安裝了 docker for mac 之後，就可以直接在 terminal 使用 docker 的 command line tool。

$ docker run -it ubuntu echo "Hello World"
Unable to find image 'ubuntu:latest' locally
latest: Pulling from library/ubuntu
b3e1c725a85f: Pull complete
4daad8bdde31: Pull complete
63fe8c0068a8: Pull complete
4a70713c436f: Pull complete
bd842a2105a8: Pull complete
Digest: sha256:7a64bc9c8843b0a8c8b8a7e4715b7615e4e1b0d8ca3c7e7a76ec8250899c397a
Status: Downloaded newer image for ubuntu:latest
Hello World

我們也可以直接執行一個 nginx web server

$ docker run -d -p 80:80 --name webserver nginx
nable to find image 'nginx:latest' locally
latest: Pulling from library/nginx
75a822cd7888: Already exists
64f0219ba3ea: Pull complete
325b624bee1c: Pull complete
Digest: sha256:2a07a07e5bbf62e7b583cbb5257357c7e0ba1a8e9650e8fa76d999a60968530f
Status: Downloaded newer image for nginx:latest
50f78171d0e26922a0b01025125a231b33615086119ebf3e8a0846b2b297760b

啟動了 web server，就可以用 browser 連結到 http://localhost/ 瀏覽網頁。

使用 Kitematic 管理 docker container

docker for mac 並沒有將 kitematic 放進去，而是讓去下載 Kitematic ，下載後會取得 Kitematic-Mac.zip，直接用以下的指令將 kitematic 解壓縮到 Applications 目錄中。

sudo unzip ~/Downloads/Kitematic-Mac.zip -d /Applications

我們可以看到剛剛執行的那個 ubuntu 的 container。

一些 docker 的基本指令

docker 容器有兩種，一種是 interactive container，
可以用互動的方式進行操作，一種是 daemonized container，可以執行應用服務 server。

執行一個名稱為 u1 的容器，-i 是保證容器有打開 STDIN，-t 是產生一個虛擬的 tty 終端，此容器使用 ubuntu 這個 image，然後執行 bash，在 bash shell 中以 exit 離開時，這個容器就會停止。可以在 bash 中執行 ls, ps -aux 等等指令。

docker run --name u1 -i -t ubuntu /bin/bash

啟動剛剛建立的 u1 container

docker start u1

重新附著到 u1，也就是進入 u1 的 bash

docker attach u1

利用 while，產生一個一直列印 hello world 的 daemon server

docker run --name d1 -d ubuntu /bin/sh -c "while true; do echo hello world; sleep 1; done"

查看正在執行的 container

$ docker ps
CONTAINER ID        IMAGE               COMMAND                  CREATED              STATUS              PORTS               NAMES
a0d673b448a8        ubuntu              "/bin/sh -c 'while tr"   About a minute ago   Up About a minute                       d1

列出所有的 containers，包含執行跟停止中的

docker ps -a

查看 d1 的 log

docker logs d1
# 類似 tail -f
docker logs -f d1

停止 d1

docker stop d1

產生一個新的 d2 container（新的容器名稱不能跟舊的一樣），不管遇到容器的(bash)退出碼是多少，都會自動重新啟動，也可以用 --restart=on-failure:5 來限制退出碼非0時，重新啟動，且只會重啟動 5 次。

docker run --restart=always --name d2 -d ubuntu /bin/sh -c "while true; do echo hello world; sleep 1; done"

可用 inspect 查看 d2 的資訊

$ docker inspect d2
[
    {
        "Id": "8dba5cf2a6ef94143f460bb6be37342d0e14bdae3d3d02645736ab1c9f343621",
        "Created": "2016-12-22T01:57:38.837925059Z",
        "Path": "/bin/sh",
        "Args": [
            "-c",
            "while true; do echo hello world; sleep 1; done"
        ],
        "State": {
            "Status": "running",
            "Running": true,
            "Paused": false,
            "Restarting": false,
            "OOMKilled": false,
            "Dead": false,
            "Pid": 2799,
            "ExitCode": 0,
            "Error": "",
            "StartedAt": "2016-12-22T01:57:39.765031056Z",
            "FinishedAt": "0001-01-01T00:00:00Z"
        },
        "Image": "sha256:104bec311bcdfc882ea08fdd4f5417ecfb1976adea5a0c237e129c728cb7eada",
        "ResolvConfPath": "/var/lib/docker/containers/8dba5cf2a6ef94143f460bb6be37342d0e14bdae3d3d02645736ab1c9f343621/resolv.conf",
        "HostnamePath": "/var/lib/docker/containers/8dba5cf2a6ef94143f460bb6be37342d0e14bdae3d3d02645736ab1c9f343621/hostname",
        "HostsPath": "/var/lib/docker/containers/8dba5cf2a6ef94143f460bb6be37342d0e14bdae3d3d02645736ab1c9f343621/hosts",
        "LogPath": "/var/lib/docker/containers/8dba5cf2a6ef94143f460bb6be37342d0e14bdae3d3d02645736ab1c9f343621/8dba5cf2a6ef94143f460bb6be37342d0e14bdae3d3d02645736ab1c9f343621-json.log",
        "Name": "/d2",
        "RestartCount": 0,
        "Driver": "aufs",
        "MountLabel": "",
        "ProcessLabel": "",
        "AppArmorProfile": "",
        "ExecIDs": null,
        "HostConfig": {
            "Binds": null,
            "ContainerIDFile": "",
            "LogConfig": {
                "Type": "json-file",
                "Config": {}
            },
            "NetworkMode": "default",
            "PortBindings": {},
            "RestartPolicy": {
                "Name": "always",
                "MaximumRetryCount": 0
            },
            "AutoRemove": false,
            "VolumeDriver": "",
            "VolumesFrom": null,
            "CapAdd": null,
            "CapDrop": null,
            "Dns": [],
            "DnsOptions": [],
            "DnsSearch": [],
            "ExtraHosts": null,
            "GroupAdd": null,
            "IpcMode": "",
            "Cgroup": "",
            "Links": null,
            "OomScoreAdj": 0,
            "PidMode": "",
            "Privileged": false,
            "PublishAllPorts": false,
            "ReadonlyRootfs": false,
            "SecurityOpt": null,
            "UTSMode": "",
            "UsernsMode": "",
            "ShmSize": 67108864,
            "Runtime": "runc",
            "ConsoleSize": [
                0,
                0
            ],
            "Isolation": "",
            "CpuShares": 0,
            "Memory": 0,
            "CgroupParent": "",
            "BlkioWeight": 0,
            "BlkioWeightDevice": null,
            "BlkioDeviceReadBps": null,
            "BlkioDeviceWriteBps": null,
            "BlkioDeviceReadIOps": null,
            "BlkioDeviceWriteIOps": null,
            "CpuPeriod": 0,
            "CpuQuota": 0,
            "CpusetCpus": "",
            "CpusetMems": "",
            "Devices": [],
            "DiskQuota": 0,
            "KernelMemory": 0,
            "MemoryReservation": 0,
            "MemorySwap": 0,
            "MemorySwappiness": -1,
            "OomKillDisable": false,
            "PidsLimit": 0,
            "Ulimits": null,
            "CpuCount": 0,
            "CpuPercent": 0,
            "IOMaximumIOps": 0,
            "IOMaximumBandwidth": 0
        },
        "GraphDriver": {
            "Name": "aufs",
            "Data": null
        },
        "Mounts": [],
        "Config": {
            "Hostname": "8dba5cf2a6ef",
            "Domainname": "",
            "User": "",
            "AttachStdin": false,
            "AttachStdout": false,
            "AttachStderr": false,
            "Tty": false,
            "OpenStdin": false,
            "StdinOnce": false,
            "Env": [
                "no_proxy=*.local, 169.254/16",
                "PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"
            ],
            "Cmd": [
                "/bin/sh",
                "-c",
                "while true; do echo hello world; sleep 1; done"
            ],
            "Image": "ubuntu",
            "Volumes": null,
            "WorkingDir": "",
            "Entrypoint": null,
            "OnBuild": null,
            "Labels": {}
        },
        "NetworkSettings": {
            "Bridge": "",
            "SandboxID": "ea7a45d1dcfb681283e18aad9feaaedd98da8cc8cd4155ca2284e4aeb6db640f",
            "HairpinMode": false,
            "LinkLocalIPv6Address": "",
            "LinkLocalIPv6PrefixLen": 0,
            "Ports": {},
            "SandboxKey": "/var/run/docker/netns/ea7a45d1dcfb",
            "SecondaryIPAddresses": null,
            "SecondaryIPv6Addresses": null,
            "EndpointID": "48480731d5cb9ab9e268e341c65fd924671222660ffa58a6adc61734811bae83",
            "Gateway": "172.17.0.1",
            "GlobalIPv6Address": "",
            "GlobalIPv6PrefixLen": 0,
            "IPAddress": "172.17.0.2",
            "IPPrefixLen": 16,
            "IPv6Gateway": "",
            "MacAddress": "02:42:ac:11:00:02",
            "Networks": {
                "bridge": {
                    "IPAMConfig": null,
                    "Links": null,
                    "Aliases": null,
                    "NetworkID": "b7f0ca41f518b121beb774aac41e709b5032e7cff96939e43e3ddac1ed16cf98",
                    "EndpointID": "48480731d5cb9ab9e268e341c65fd924671222660ffa58a6adc61734811bae83",
                    "Gateway": "172.17.0.1",
                    "IPAddress": "172.17.0.2",
                    "IPPrefixLen": 16,
                    "IPv6Gateway": "",
                    "GlobalIPv6Address": "",
                    "GlobalIPv6PrefixLen": 0,
                    "MacAddress": "02:42:ac:11:00:02"
                }
            }
        }
    }
]

配合 format 查看特定的資訊

$ docker inspect --format='{{ .State.Running }}' d2
true
$ docker inspect --format='{{ .NetworkSettings.IPAddress }}' d2
172.17.0.2

$ docker inspect --format='{{.Name}} {{ .State.Running }}' d1 d2
/d1 false
/d2 true

先停止 d2 後，才能用 rm 刪除 d2

docker stop d2
docker rm d2

列出所有 images

docker images

取得 ubuntu 的 image

docker pull ubuntu

以 TAG 指定 ubuntu 的版本

docker run --name t1 -t -i ubuntu:12.04 /bin/bash

列出 ubuntu 的 images

$ docker images ubuntu
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
ubuntu              latest              104bec311bcd        6 days ago          129 MB
ubuntu              12.04               f0d07a756afd        6 days ago          103.6 MB

要先移除跟 image 相關的 containers，才能移除 image

docker rm t1

docker rmi ubuntu:12.04

搜尋所有 docker hub 的公用可用 image

docker search puppet

建立 docker image

有兩種方式:

使用 docker commit: 不建議用這種方式

登入 docker hub

$docker login
Login with your Docker ID to push and pull images from Docker Hub. If you don't have a Docker ID, head over to https://hub.docker.com to create one.
Username: yaocl
Password:
Login Succeeded

執行一個 ubuntu 的 container

docker run -i -t ubuntu /bin/bash

在容器中安裝 apache

apt-get -yqq update
apt-get -y install apache
exit

將 container 以 commit 存成另一個 image

$ docker commit fd915f899feb yaocl/apache2
sha256:32421625c13d3076c90a18d3146dab180a9ed5c33e8439b5572acdcf7a328e02

$ docker images yaocl/apache2
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
yaocl/apache2       latest              32421625c13d        31 seconds ago      267.6 MB

自訂一些資訊欄位，產生新的 image tag

$ docker commit -m="custom image" --author="yaocl" fd915f899feb yaocl/apache2:webserver
sha256:b2e0f5faed623a8f62bdad08223773ae85274c9fc40e12753ac1df1258152f2f

$ docker images yaocl/apache2
REPOSITORY          TAG                 IMAGE ID            CREATED              SIZE
yaocl/apache2       webserver           b2e0f5faed62        About a minute ago   267.6 MB
yaocl/apache2       latest              32421625c13d        2 minutes ago        267.6 MB

使用新的 yaocl/apache2:webserver image

docker run -t -i yaocl/apache2:webserver /bin/bash

使用 dokcer build 及 Dockerfile 文件

static_web 目錄就是 dokcer 的 build environment，此環境就稱為 context 或 build context，先在這個 context 中建立一個 Dockerfile

mkdir static_web
cd static_web/
touch Dockerfile

編輯 Dockerfile 內容

# Version 0.0.1
FROM ubuntu:latest
MAINTAINER yaocl
ENV REFRESHED_AT 2016/12/22
RUN apt-get update
RUN apt-get install -y nginx
RUN echo "hi from container" > /usr/share/ngnix/html/index.html
EXPOSE 80

以 build 指令建立 image，如果沒有寫 :v1，就是預設的 latest 這個 tag

cd static_web/
#docker build -t="yaocl/static_web" .

docker build -t="yaocl/static_web:v1" .

建立 images 時發生錯誤

Setting up nginx (1.4.6-1ubuntu3.7) ...
Processing triggers for libc-bin (2.19-0ubuntu6.9) ...
Processing triggers for sgml-base (1.26+nmu4ubuntu1) ...
 ---> 83f7d5f1ad20
Removing intermediate container 2681f1e39e14
Step 5 : RUN echo "hi from container"   > /usr/shre/ngnix/html/index.html
 ---> Running in f1bd373dc64e
/bin/sh: 1: cannot create /usr/shre/ngnix/html/index.html: Directory nonexistent
The command '/bin/sh -c echo "hi from container"    > /usr/shre/ngnix/html/index.html' returned a non-zero code: 2

以 docker images 可以看到錯誤步驟前那一個 image id: 83f7d5f1ad20

$ docker images
REPOSITORY                      TAG                 IMAGE ID            CREATED             SIZE
<none>                          <none>              83f7d5f1ad20        39 seconds ago      231.1 MB

以該 image id 執行一個 container

$ docker run --name test -i -t 83f7d5f1ad20 /bin/bash

發現是路徑寫錯了 /usr/share/nginx/html

修改 Dockerfile 內容

# Version 0.0.1
FROM ubuntu:latest
MAINTAINER yaocl
ENV REFRESHED_AT 2016/12/22
RUN apt-get update
RUN apt-get install -y nginx
RUN echo "hi from container" > /usr/share/nginx/html/index.html
EXPOSE 80

再 build 一次，就成功了

$ docker build -t="yaocl/static_web:v1" .
Sending build context to Docker daemon 2.048 kB
Step 1 : FROM ubuntu:latest
 ---> 3f755ca42730
Step 2 : MAINTAINER yaocl
 ---> Using cache
 ---> 062ac75f50aa
Step 3 : RUN apt-get update
 ---> Using cache
 ---> 43e1cecf45be
Step 4 : RUN apt-get install -y nginx
 ---> Using cache
 ---> 83f7d5f1ad20
Step 5 : RUN echo "hi from container" > /usr/share/nginx/html/index.html
 ---> Running in 9a1dcbadd174
 ---> 11fa4a76019d
Removing intermediate container 9a1dcbadd174
Step 6 : EXPOSE 80
 ---> Running in 2d0db9f90d57
 ---> 683486e4c00a
Removing intermediate container 2d0db9f90d57
Successfully built 683486e4c00a
[14:10]charley@cmbp ~/Downloads/static_web$ docker images
REPOSITORY                      TAG                 IMAGE ID            CREATED             SIZE
yaocl/static_web                v1                  683486e4c00a        4 seconds ago       231.1 MB

由於 docker 會在每一個步驟都產生 image，可以加上 --no-cache 避免產生這個問題

docker build --no-cache -t="yaocl/static_web:v1" .

產生 yaocl/static_web:v1 的 container

$ docker run --name t1 -d -p 80 yaocl/static_web:v1 nginx -g "daemon off;"
4dbe731715cb046c6c12bb23264e9b4add0631948b3dfa15cb4e740a586eed68

以 ps 指令查看主機隨機以 49153 ~ 65535 任意一個 port 對應到 80 的資訊

$ docker ps
CONTAINER ID        IMAGE                 COMMAND                  CREATED             STATUS              PORTS                   NAMES
4dbe731715cb        yaocl/static_web:v1   "nginx -g 'daemon off"   29 seconds ago      Up 28 seconds       0.0.0.0:32768->80/tcp   t1

瀏覽器可以連結到 http://localhost:32768 查看網頁

如果是 -p 80:80 就是使用主機的 80

$ docker run --name t1 -d -p 80:80 yaocl/static_web:v1 nginx -g "daemon off;"

綁定主機的 127.0.0.1:80

$ docker run --name t1 -d -p 127.0.0.1:80:80 yaocl/static_web:v1 nginx -g "daemon off;"

Dockerfile 指令

Dockerfile reference

CMD

指定 container 最後要執行的命令，也可以用 docker run 覆蓋 CMD 的指令
```
CMD ["nginx", "-g", "daemon off;"]
```
可以省略最後用 /bin/sh -c 執行的指令
```
$ docker run --name t2 -d -p 127.0.0.1:80:80 yaocl/static_web:v2
```
ENTRYPOINT

跟 CMD 類似但不一樣，使用 ENTRYPOINT 可以接受 run 後面增加的參數
```
ENTRYPOINT ["/usr/sbin/nginx"]
```
執行時會增加後面 -g "daemon off;" 的參數給 nginx
```
$ docker run --name t2 -d -p 127.0.0.1:80:80 yaocl/static_web:v2 -g "daemon off;"
```
所以實際上使用會是
```
ENTRYPOINT ["/usr/sbin/nginx"]
CMD ["-g", "daemon off;"]
```
或是在沒有參數時，列印 help 資訊
```
ENTRYPOINT ["/usr/sbin/nginx"]
CMD ["-h"]
```
WORKDIR

在 container 內設定工作目錄，執行 ENTRYPOINT 或 CMD

使用時可以在過程中隨時切換目錄
```
WORKDIR /opt/webapp/db
RUN bundle install
WORKDIR /opt/webapp
ENTRYPOINT ["rackup"]
```

ENV

設定環境變數，可以在 docker run 以 -e 參數指定環境變數

ENV RVM_PATH /home/rvm/

ENV TARGET_DIR /opt/app
WORKDIR $TARGET_DIR

docker run -i -t -e "WEB_PORT=8080" ubuntu env

USER

指定用什麼帳號身份執行指令，可以用 docker run 的 -u 參數覆蓋這個設定，如果沒有指定，預設為 root
```
USER user
USER user:group
USER uid
USER uid:gid
USER uid:group
```
VOLUME

對 container 增加 volume，一個 volume 可同時存在於一個或多個 container 的特定目錄，該目錄可繞過聯合文件系統，進行資料共享或持久化的工作
- volume 可在 container 之間共享, 重用
- container 不一定要跟其他 container 共享 volume
- 對 volume 修改資料會立即生效
- 修改 volume 裡面的資料，不會對 image 產生影響
- volume 會一直存在，直到沒有任何 container 使用它
```
VOLUME ["/opt/project", "/data"]
```
ADD

將建構環境中的檔案複製到 image 中，後面的目的地檔名不能省略，新目錄或檔案權限都是 0755，UID及 GID 都是 0
```
ADD sw.lic /opt/application/sw.lic
ADD http://wordpress.org/latest.zip /root/wordpress.zip
```
這會自動將 latest.tar.gz 解壓縮到目的地的目錄中
```
ADD latest.tar.gz /var/www/wordpress/
```
COPY

類似 ADD，但沒有解壓縮的功能
```
COPY conf.d/ /etc/apache2/
```
ONBUILD

為 image 增加 trigger 的功能，當 image 被使用時，就會觸發 trigger
```
ONBUILD ADD . /app/src
ONBUILD RUN cd /app/src && make
```

Docket hub 與私有的 Docker Registry

push image to Docker hub

docker push static_web

也可以在 docket hub 增加 github/BitBucket 帳號連結，然後製作 Automated Build 自動產生 image

用這個指令可以產生一個 private docker registry

docker run -p 5000:5000 registry

$ docker images yaocl/static_web
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
yaocl/static_web    v2                  1d48b7f306d8        2 hours ago         231.1 MB
yaocl/static_web    v1                  ce19993fc181        3 hours ago         231.1 MB

將 image push 到 docker.example.com:5000 這個 private registry

docker tag 1d48b7f306d8 docker.example.com:5000/yaocl/static_web

docker run -t -i docket.example.com:5000/yaocl/static_web /bin/bash

scripts

移除所有 stopped containers

docker rm $(docker ps -a -q)

移除所有 UNTAG images

docker rmi $(docker images | grep "<none>" | awk '{print $3}')

References

[Docker] 在 Mac 上使用原生的 Docker for Mac 操作 container

撰寫一份符合需求的 Dockerfile

2017/4/24

Actor Model

Actor Model 是一個 concurrent computing 的計算模型，Actor 是這個模型的基本計算單元，當 actor 透過一個自己的獨立 mailbox 接收到一個訊息，他能夠根據這個訊息，做出決策、進行運算、產生其他訊息、決定如何回應。

Ａctor model 是 1973 年由Carl Hewitt、Peter Bishop及Richard Steiger的論文: A Universal Modular Actor Formalism for Artificial Intelligence 提出。

在當時由於機器多屬於單核心且網路速度較慢，不同的 actor 甚至是遠端的 actor 之間發送訊息，存在著明顯的資料延遲時間。但由於 Moore's Law 的趨勢，目前的 CPU 已經是多核心的時代，網路速度也已經不可同日而語，以往的資料鎖定 (lock) 方法已經無法滿足於現今處理並行運算的硬體設備。Actor Model 簡化了 data lock 的實作的複雜性，去掉了 deadlock 的問題，在一個運算環境中以大量的actor 小單元完成並行運算的工作。 

Everything's an Actor

相對於物件導向的 Everything is an Object，Actor Model 認為 Everything is an Actor。actors 是一個並行的運算系統，能夠處理下列的工作，這是 actor 的基本原則。

傳送有限數量的訊息給其他 actors
建立有限數量的 new actors
指定接受到下一個訊息時的行為

所有訊息的收送都是非同步的，透過 mail address 傳送資料。每一個 actor 都有一個 mailbox ，以 FIFO 方式暫存接收到的訊息。

Actor Model 的爸爸 Carl Hewitt 在 Lang.NEXT 2012 針對 acotr model 有一段討論會形式的說明 Hewitt, Meijer and Szyperski: The Actor Model (everything you wanted to know...)，整個影片的過程就像是聊天一樣，3 個 actors 在互相溝通與討論 actor model。

實作 actor 有三個原則，必須要包含下面三種基本要素

processing: 要能進行運算
storage: 必須要能儲存資料
communication: 要能跟其他 actors 溝通

actor 就像是一個獨立的個體，他能持續的接收訊息，進行工作，但同一時間內，只能處理一個訊息，所有訊息都是依照收到的順序依次進行處理。

當 actor 互相傳送訊息，可能透過某種方式發送訊息給自己，這有可能會造成 deadlock 嗎？

Carl Hewitt 給了使用 Futures and promises 的概念，因為 future 就像是在現在預約一個在未來會產生結果的訊息，因此 actor 可以產生一個 future，並發送給自己的 address，然後在收到自己發送的訊息時，進行下一步的運算，並將結果放到 future 裡面，這完全不可能會造成 deadlock。

address 跟 actor 本身並不是一對一的，而是多對多的，一個 actor 可以有多個 addresses，一個 address 也可能因為原本的 actor 失效，而指向到另一個重新產生的 actor，address 並不代表是 actor 的 identity。

actor 因為一次處理一個訊息的特性，因此不會造成資料同步上的問題，基本上資料只存在於這個 actor 裡面，一次又只能因為一個訊息的輸入及運算，而異動了這個資料，因此不會造成資料同步上的問題。

AKKA NOTES - INTRODUCING ACTORS 這篇文章用了幾張圖片，說明 actor 之間如何互相傳送資料，Actor 就像是一群人，他們互相之間不會面對面地交流，而只是通過郵件的方式進行溝通。

傳遞消息是Actor模型的基礎，他以一名學生和一位教師舉例，描述了以下基礎流程：

一名學生給一位教師發送了一封郵件，郵件一旦發送之後，就不能夠修改了
教師會在她認為適合的時機去檢查她的郵箱，收到這封郵件
該教師稍後會寄一封回信給該學生，這封回信也是一旦發送就不可修改的
學生在一段時間後決定去檢查一下他的郵箱，收到了回信

信件是單向的，那麼它一旦送出之後並不會期待或等待任何響應，但 actor 都能夠在一個 request-response 週期內，為發送者發送回應消息。

Scratch 也使用了 Actor Model

Actor Model 中列出了現在支援了 Actor Model 的程式語言，其中有一個特別的是 Scratch，Scratch 是 MIT 為了小朋友開發的一套圖形介面的程式設計軟體，適合從來沒有學過程式設計的小朋友，通過拖曳預先設定好的積木式程式模件，堆疊出指令，設定或控制角色及背景的行動和變化，從而完成程式設計。

參考這個範例 Scratch 教學的第 1 堂課（1/5）適合親子共學的兒童程式設計入門，如果有用過 Scratch，也會知道在開發時，一開始就是要產生人物的主角，然後再程式區塊，產生數個 blocks，為每個 block 設定 trigger 該 block 的事件條件，當滿足該條件時，就持續下去進行下面程式區塊的運算，也可以在運算後，廣播一個訊息，驅動其他的程式區塊。

這跟 Actor Model 的概念是很接近的，執行時也可以發現，這些程式區塊是可以同時進行運算的，程式區塊之間，也可以透過訊息的發送傳遞消息，不過 scratch 還是支援了全域變數，這跟 actor model 本身就有些不同，但這畢竟是給小朋友使用的工具，因為變數的概念對學程式來說是一個門檻，如果變數沒有辦法共享，coding 就沒辦法那麼直覺地使用變數。

References

Akka in action: actor model

以Akka為示例，介紹Actor模型
I

2017/4/17

分散式系統一致性演算法

分散式系統透過網路互相連接，但由於網路的時間延遲，再加上各節點可能的失效或異常，需要一個適當的演算法達到資料一致性，如果其中有些節點，可能會刻意造假以混淆資料的一致性結果，那麼需要更有效的演算法來解決這樣的問題。

一致性問題

資料一致性通常指關聯數據之間的邏輯關係是否正確和完整。而資料存儲的一致性模型則可以認為是存儲系統和資料使用者之間的一種約定。如果使用者遵循這種約定，則可以得到系統所承諾的訪問結果，常用的一致性模型有：

嚴格一致性（linearizability, strict/atomic Consistency）

讀出的數據始終為最近寫入的數據。這種一致性只有當全域時鐘存在時才有可能達成，在分散式網路環境不可能實現。
順序一致性（sequential consistency）

對同一資料的操作，所有使用者都看到同樣的操作順序，但是該順序不一定是即時的。
因果一致性（causal consistency）

只有存在因果關係的寫入操作才要求所有使用者看到相同的操作順序，對於無因果關係的寫入則並行進行，不保證操作順序。因果一致性可以看做對順序一致性性能的一種優化，但在實現時必須建立與維護因果依賴圖，這是相當困難的。
管道一致性（PRAM/FIFO consistency）

在因果一致性模型上的進一步弱化，要求由某一個使用者完成的寫入操作可以被其他所有的使用者按照順序的感知到，而從不同使用者中來的寫操作則無需保證順序，就像一個一個的管道一樣。相對來說比較容易實現。
弱一致性（weak consistency）

只要求對共享的資料結構的訪問保證順序一致性。對於同步變數的操作具有順序一致性，是全局可見的，且只有當沒有寫操作等待處理時才可進行，以保證對於臨界區域的訪問順序進行。在同一時間，所有使用者可以看到相同的資料。
釋放一致性（release consistency）

弱一致性無法區分使用者是要進入臨界區還是要出臨界區，釋放一致性使用兩個不同的操作語句進行了區分。需要寫入時，使用者先acquire該對象，寫完後release，acquire-release之間形成了一個臨界區，提供釋放一致性也就意味著當release操作發生後，所有使用者應該可以看到該操作。
最終一致性（eventual consistency）

在沒有新的更新的情況下，更新最終會通過網路傳播到所有副本點，所有副本點最終會一致，也就是說使用者在最終某個時間點前的中間過程中無法保證看到的是新寫入的數據。可以採用最終一致性模型有一個關鍵要求：可以接受讀取到舊的資料狀態。
delta consistency

系統會在delta時間內達到一致。這段時間內會存在一個不一致的窗口，該窗口可能是因為log shipping的過程導致。資料庫完整性（Database Integrity）是指資料庫中數據的正確性和相容性。資料庫完整性由各種各樣的完整性約束來保證，因此可以說資料庫完整性設計就是資料庫完整性約束的設計。

共識演算法 consensus problem

要保障系統滿足不同程度的一致性，往往需要通過共識演算法來達成。共識算法解決的是對某個提案（Proposal），大家達成一致意見的過程。

提案的含義在分佈式系統中十分寬泛，例如多個事件發生的順序、某個鍵對應的值、誰是領導...，可以認為任何需要達成一致的信息都是一個提案。通過訪問足夠多個服務節點來驗證確保獲取共識後結果。

如果分佈式系統中各個節點都能保證以十分強大的性能（即時響應）無故障的運行，則實現共識過程並不複雜，簡單通過投票即可。但實際上每個資料 request 會有網路的傳輸時間延遲，節點可能會故障，甚至存在了惡意的節點要故意破壞系統。

如果只有故障（不響應）的情況，沒有惡意節點，稱為「非拜占庭錯誤」，針對非拜占庭錯誤的情況，一般使用 Paxos、Raft 這一類的演算法。
如果有惡意響應的情況，稱為「拜占庭錯誤」，對於要能容忍拜占庭錯誤的情況，一般使用 PBFT 系列、PoW 系列演算法。

拜占庭將軍問題是一個協議問題，拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。但這些將軍在地理上是分隔開來的，並且將軍中存在叛徒。叛徒可以任意行動以達到以下目標：欺騙某些將軍採取進攻行動，促成一個不是所有將軍都同意的決定，如當將軍們不希望進攻時促成進攻行動；或者迷惑某些將軍，使他們無法做出決定。如果叛徒達到了這些目的之一，則任何攻擊行動的結果都是註定要失敗的，只有完全達成一致的努力才能獲得勝利。

由於硬體錯誤、網路擁塞或斷開以及遭到惡意攻擊，計算機和網路可能出現不可預料的行為。拜占庭容錯協議必須處理這些失效，並且這些協議還要滿足所要解決的問題要求的規範。

FLP 不可能性原理

在網絡可靠情況下，如果存在節點失效（即便只有一個）的最小化異步模型系統中，不存在一個可以解決一致性問題的確定性算法。

有個實例可以解釋這個原理，三個人在不同房間，進行投票（投票結果是 0 或者 1）。三個人彼此可以通過電話進行溝通，但經常會有人突然睡著。比如某個時候，A 投票 0，B 投票 1，C 收到了兩人的投票，然後 C 睡著了。A 和 B 永遠無法在有限時間內獲知最終的結果。逾時的時候，可以重新投票，如果類似情形每次在取得結果前發生，就永遠無法取得共識。

但加上一些條件限制，就可以達到共識。

CAP 原理

分佈式計算系統不可能同時達到一致性（Consistency）、可用性（Availablity）和分區容忍性（Partition），設計中往往需要弱化對某個特性的保證。

一致性（Consistency）

任何操作應該都是原子的(不能被中斷)，發生在後面的事件能看到前面事件發生導致的結果，注意這裡指的是強一致性
可用性（Availablity）

在有限時間內，任何非失敗節點都能能夠回應請求的結果
分區容忍性（Partition）

網路可能發生分區，不保障節點之間的通信。

CAP 三個可以弱化某一個條件，用以設計系統。

弱化一致性 AP

對結果一致性不敏感的應用，可以允許在新版本的資料上線後過一段時間才更新成功，在更新過程中，不保證一致性。
例如網站靜態頁面內容、實時性較弱的查詢類數據庫等，CouchDB、Cassandra 等為此設計。
弱化可用性 CP

對結果一致性很敏感的應用，例如銀行取款機，當系統故障時候會拒絕服務。MongoDB、Redis 等為此設計。Paxos、Raft 等算法，主要處理這種情況。
弱化分區容忍性 CA

網絡分區出現概率減小，但較難避免。某些關聯式資料庫、ZooKeeper 即為此設計。網絡可透過雙路由等機制增強可靠性，達到高穩定的網路通信。

ACID 原則強調一致性 C，失去了可用性

資料庫管理系統（DBMS）在寫入/更新資料的過程中，為保證事務（transaction）是正確可靠的，所必須具備的四個特性：原子性（atomicity，或稱不可分割性）、一致性（consistency）、隔離性（isolation，又稱獨立性）、持久性（durability）。

原子性：一個事務（transaction）中的所有操作，要麼全部完成，要麼全部失敗，不會結束在中間某個環節。事務在執行過程中發生錯誤，會被 Rollback 到事務開始前的狀態，就像這個事務從來沒有執行過一樣。
一致性：在事務開始之前和事務結束以後，資料庫的完整性沒有被破壞。這表示寫入的資料必須完全符合所有的預設規則，這包含資料的精確度、串聯性以及後續資料庫可以自發性地完成預定的工作。
隔離性：資料庫允許多個並發事務同時對齊數據進行讀寫和修改的能力，隔離性可以防止多個事務並發執行時由於交叉執行而導致數據的不一致。事務隔離分為不同級別，包括讀未提交（Read uncommitted）、讀提交（read committed）、可重複讀（repeatable read）和串行化（Serializable）。
持久性：transaction 處理結束後，對數據的修改就是永久的，即便系統故障也不會遺失資料。

BASE 原則強調可用性，但失去了一致性

Base: 一種 Acid 的替代方案

BASE（Basic Availiability，Soft state，Eventually Consistency）

BA Basic Availiability

基本可用性
S Soft state

server 在有限度的資源（一般是時間）內維持上下文 context，逾時則拋棄狀態回復到默認狀態。
E Eventually Consistency

允許因延時等出現臨時的數據不一致現象，只要數據最終是一致的就可以。

Paxos 與 Raft

Paxos 是 1990 年由 Leslie Lamport 提出的演算法，針對分散式系統，其中存在著故障的節點，但不存在惡意節點的狀況下，如何達成共識的處理方法。

古希臘 Paxon 島上的多個法官在一個大廳內對一個議案進行表決，但要達成一致的結果。法官之間通過服務人員來傳遞紙條，但法官可能離開或進入大廳，服務人員可能偷懶去睡覺。

Paxos 是以 two-phase commit 的方式來解決問題。

演算法中將節點分為

Proposer: 負責提案，等待大家同意並結案，通常是客戶端 client 擔任這個角色
Acceptor: 對提案進行投票，通常是 server 擔任這個角色
Learner: 被告知投票的結果，並與結果同步，但不參與投票的過程，client 或是 server 都有可能擔任這個角色

phase1（準備階段）

Proposer向超過半數（n/2+1）Acceptor發起prepare消息(發送編號)
如果prepare符合協議規則，Acceptor回覆promise消息，否則拒絕

phase2（決議階段或投票階段）

如果超過半數Acceptor回覆promise，Proposer向Acceptor發送accept消息
Acceptor檢查accept消息是否符合規則，消息符合則批准accept請求

以實際上三個 server 推舉 leader 的議案為例

細節可參閱一致性算法Paxos詳解

Raft 是 Paxos 的簡化實現，是由Stanford提出的一種更易理解的一致性演算法，意在取代目前廣為使用的Paxos演算法。

包含了三種角色：leader、candiate 和 follower，其基本過程為

Leader 選舉：每個 candidate 隨機經過一定時間都會提出選舉方案，最近階段中得票最多者被選為 leader；
同步 log：leader 會找到系統中 log 最新的記錄，並強制所有的 follower 來刷新到這個記錄 (log 是各種事件的發生記錄)

PBFT

PBFT Practical Byzantine Fault Tolerance 實用拜占庭容錯算法，是 Miguel Castro 和 Barbara Liskov 在1999年提出來的，解決了原始拜占庭容錯算法效率不高的問題，將算法複雜度由指數級降低到多項式級。

PBFT的一致性協議如下圖所示，每一個客戶端的請求需要5個階段才能完成。PBFT通過採用兩次兩兩交互的方式在服務器達成一致之後再執行客戶端的請求，由於客戶端不能從服務器端獲得任何服務器運行狀態的信息，因此PBFT 協議中主節點是否發生錯誤只能由服務器監測。如果服務器在一段時間內都不能完成客戶端的請求，則會觸發視圖更換協議。

PBFT的熱門應用是在IBM主導的區塊鏈超級賬本項目中，除了PBFT之外，超級賬本項目還引入了基於PBFT的自用共識協議Sieve，它的目的是希望在PBFT基礎之上能夠對節點的輸出也做好共識，這是因為超級賬本項目的一個重要功能是提供區塊鏈之上的智能合約——就是在區塊鏈上執行的一段代碼，因此它會帶來區塊鏈賬本上最終狀態的不確定，為此Sieve會在PBFT實現的基礎之上引入代碼執行結果簽名進行驗證。