10 days ago

在這一篇文章中,我們將要理解兩個問題 :

  1. 在新增一個 document 時,會建立 json 實體與索引,那這兩個東東會存放到那兒去 ?
  2. 而在建立索引時,它又存放了什麼東東 ?

在開始前,我們先簡單的複習一下 Elasticsearch 的基本觀念。

Elasticsearch ( ES ) 的前提觀念概要

Elasticsearch 是一種分散的搜尋引擎,它也有和關聯式資料庫相似的結構,如下圖。

所以假設我們要新增一筆 document 應該是會長的像下面這樣。

POST /markcorp/employee (/(index)/(type))

上面這行的語意就是新增一筆 document 到 markcorp (index) 的 employee 類別
(type)

{
  id: 123
  name: ‘Mark’,
  age: 18
}

然後當我們要去 ES 尋找這筆資料時,就可以使用它提供的 Restful API 來直接尋找:

GET 127.0.0.1:9200/markcorp/employee/123

在有了簡單的基本概念後接下來就可以來尋找我們這篇文章的問題。

新增一個 document 時資料會存放到那 ??

像我們上面已經建立好了 document ,那實際上在 ES 中它是存放在那呢 ?? 雖然我們上面說它是對應到 RDBMS 的概念,但實際存放的地方不是存放在 markcorp 這個資料庫下的 employee 表下。

嚴格來說它是存放在 markcorp 這個 index 裡面,並且它的類型是 employee 。

那 index 裡的實體 document 又是放在那裡呢 ??

答案是在shards裡,咱們可以執行下面的指定看到 index 底下有那些 shards

curl 127.0.0.1:9200/markcorp/_search_shards

那 shards 是什麼,不如我們先來說說為什麼要有 shards ,一個 index 有可能會存放大量的 document ,這時所有的 document 都存放在同一個地方,一定會產生硬體貧頸,所以為了解決這個問題 ES 提供了方法可以將 index 分散成塊,而這個塊就被稱為『 shards 』。

所以簡單的說 index 是由多個 shard 所組成,然後 document 會實際存放在 shards 中。

然後不同的 shards 可能會存放在不同的節點上,而這裡指的節點就是指不同實體,你也可以先想簡單一點就是機器。

上面這張圖就是 ES 的 Cluster 基本架構,每當有文檔要建立時,它會依據 index 有那些分片,然後來將它丟到『某一個』分片中,當然它有辦法指定到分片中,不過這不是該篇文章要討論的主題。

我相信有人看到上面那張圖時會想說,如果其中一個節點上天堂了,那不就代表那個節點的 document 都會找不到嗎 ? 沒錯 ~ 不過你想想你都想得到了,那開發 ES 的人會想不到嗎 ??

ES 的解法就是每一個節點除了存放你上面看到的分片,它事實上還多存放了其它節點的備份分片,如下圖,假設我們有三個節點,然後每個節點上面有一個分片和另一個分片的備份,而當節點 2 上天堂時,我們在節點 1 還有分片 2 的備份,所以還是可以找的到分片 2 的 document 。

那它除了將 document 實體建立起來,還有建立什麼東西嗎 ??

有的,那就是建立一些索引(此索引不是上面說的 index ),來幫助我們更快速的搜尋到它。

而要理解它存了啥,那就要來理解理解 ES 的倒排索引,如下圖,它的方向就是 ES 要搜尋時跑的方向,它會先去 term index 中尋找某個東西,然後可以指到 term dictionary ,接下來在從 dictionary 可以找到指定的 posting list ,最後 posting list 裡面就列了,你要的 document 編號。

接下來我們將從 posting list 開始來說起,以下為範例 documents 。

{
  id: 1,
  name: ‘Mark',
  age: 18
},
{
  id: 2,
  name: ‘Ack',
  age: 28
},{
  id: 3,
  name: ‘Ad'
  age: 17
}
{
  id: 4,
  name: ‘Ban'
  age: 28
}

Posting List

上面的 documents 會被轉換下面的列表,所以如果 client 要搜尋 age 為 28 歲的,馬上就能找到對應的 2 與 3 號 document。

name
Term Posting List
Mark 1
Ack 2
Ad 3
Ban 4
age
Term Posting List
18 1
17 3
28 [2,4]

Term Dictionary

上面搜尋的方法看試可以,但假設有成千上萬個 term 呢 ? 例如你 name 的 term 有好幾千萬筆,所以為了解決這個問題
ES 會將所有的 term 進行排序,這樣就可以使用二分搜尋法來達到 O(logn) 的時間複雜度囉。( 二分搜尋可參考哥的這篇文章 傳送門)

所以 name 這個會變成下面像下面這張表一樣,有排序過的 term。

Term Dictionary Posting List
Ack 2
Ad 3
Ban 4
Mark 1

Term Index

上面這些東西如果數量小時,放在記憶體內還行,但問題是如果 term 很多,導致 term dictionary 非常大的話,放在記憶體內會出事情的,所以 ES 的解法就是Term Index

Term Index 本身就是像個樹,它會根據上面的 term dictionary 產生出樹如下圖:

Term Index 基本上是存放在記憶體中,每當進行搜尋時會先去這裡尋找到對應的 index ,然後再根據它去硬碟中尋找到對應的 term dictionary 最後就可以成功的找到指定的 document 囉。

結論

最後簡單的總結一下本篇文章所提的兩個問題的結論。

1 . 在新增一個 document 時,會建立 json 實體與索引,那這兩個東東會存放到那兒去 ?

Ans: 會存放到某一個 shard 中,而 shard 又存放在每個節點裡面。

2 . 而在建立索引時,它又存放了什麼東東 ?

Ans: 會建立三個東西分別為 Posting List 、Dictionary 與 Term Index ,其中前兩者是存放在硬碟中,而最後的 index 是存放在記憶體中。

參考資料

 
10 days ago

本篇文章中,我們將要很快速的學習以下幾個重點:

  1. elasticsearch 的基本觀念。
  2. 使用 docker 建立 elastisearch 服務。
  3. 新增 document。
  4. 取得 document。
  5. 修改 document。
  6. 搜尋 document。

elasticsearch 的基本觀念

Elasticserach 是一種分散式的搜尋引擎,它非常適合用來處理大量資料的搜尋與分析,像 github 就是拿他來搜尋它們所有的程式碼,而且它也提供了豐富的 restful api 來給我們進行操作。

Elasticserach 有這和關聯式資料庫相似的結構,如下圖。

所以假設我們要新增一筆在 markcorp 某一位員工的文檔會長的如下:

index: markcorp
type: employee

{
  id: 123
  name: ‘Mark’,
  age: 18
}

然後當我們要去 ES 尋找這筆資料時,就可以使用它提供的 Restful API 來直接尋找:

GET 127.0.0.1:9200/markcorp/employee/123

使用 docker 建立 elastisearch 服務

接下來的教學可以直接用這個專案來直接執行:

git clone https://github.com/h091237557/docker-composer-tools.git
cd elasticsearch/
docker-compose up

下面為官網所直接使用的docker compose的檔案。(官網傳送門)

version: '2.2'
services:
  elasticsearch:
    image: docker.elastic.co/elasticsearch/elasticsearch:6.2.3
    container_name: elasticsearch
    environment:
      - cluster.name=docker-cluster
      - bootstrap.memory_lock=true
      - "ES_JAVA_OPTS=-Xms512m -Xmx512m"
    ulimits:
      memlock:
        soft: -1
        hard: -1
    volumes:
      - esdata1:/usr/share/elasticsearch/data
    ports:
      - 9200:9200
    networks:
      - esnet
  elasticsearch2:
    image: docker.elastic.co/elasticsearch/elasticsearch:6.2.3
    container_name: elasticsearch2
    environment:
      - cluster.name=docker-cluster
      - bootstrap.memory_lock=true
      - "ES_JAVA_OPTS=-Xms512m -Xmx512m"
      - "discovery.zen.ping.unicast.hosts=elasticsearch"
    ulimits:
      memlock:
        soft: -1
        hard: -1
    volumes:
      - esdata2:/usr/share/elasticsearch/data
    networks:
      - esnet

volumes:
  esdata1:
    driver: local
  esdata2:
    driver: local

networks:
  esnet:

以下有幾個配置要注意一下。

environment

  • cluster.name : 這個就是設定這個 ES cluster 的名稱,所有在相同機器上且命名相同 cluster.name 的都將在相同的 cluster 裡。
  • bootstrap.memory_lock : 這個設定 true 是為了要防止 swapping 抓到 ES 的 memory 來用,導致節點不穩而脫離 cluster。官網
  • ES_JAVA_OPTS: -Xms512m -Xmx512m 代表設定 ES 的最大與最小的 heap 空間為 512 mb。
  • discovery.zen.ping.unicast.hosts: 這是為了讓此節點知道去連結 elasticsearch ( docker 節點 )。

ulimits

這個參數就是可以設定 docker 容器的 ulimits 參數,其中官網這裡會設定 memlock,事實上我還在研究它。不過主要事實和上面的 bootstrap.memory_lock 的原因有關,待調查。

ulimits:
      memlock:
        soft: -1
        hard: -1

確保 Elasticsearch 有成功執行

請指定執行下面的執令,然後該會看到如下的資訊。

curl 127.0.0.1:9200

---
{
  "name" : "OcaPXYM",
  "cluster_name" : "docker-cluster",
  "cluster_uuid" : "Cg2ogE6ETbOhSEh0E8m-3w",
  "version" : {
    "number" : "6.2.3",
    "build_hash" : "c59ff00",
    "build_date" : "2018-03-13T10:06:29.741383Z",
    "build_snapshot" : false,
    "lucene_version" : "7.2.1",
    "minimum_wire_compatibility_version" : "5.6.0",
    "minimum_index_compatibility_version" : "5.0.0"
  },
  "tagline" : "You Know, for Search"
}

新增與取得文檔

我們試這新增一筆 markcorp 的一筆員工資料看看,上面有提到 ES 提供了 restful api 給我們操作,所以我們只要準備好員工資料的 json 檔。

{
  name: 'Mark',
  age: 18,
  habit: 'Cut someone' 
}

然後使用 curl 執行下面的指令就可以新增一筆資料到裡面囉。

curl -X POST -H "Content-Type: application/json" -d @./post.json 127.0.0.1:9200/markcorp/employee

執行完的訊息
{"_index":"markcorp","_type":"employee","_id":"Mmbls2IBnSbSo4fQfVml","_version":1,"result":"created","_shards":{"total":2,"successful":1,"failed":0},"_seq_no":0,"_primary_term":1}%

上面的指令重點有兩個,第一個就是post在 restful api 中就代表這新增的意思,然後第二個重點就是下面這段 uri ,它說明了這筆資料要新增的地點,markcorp 就是 index 而 employee 就是 type 的意思。

127.0.0.1:9200/markcorp/employee

然後我們就可以使用下面的 restful api 來取得該筆資料,其中 employee 後面的那個英文就是文檔 id。

curl 127.0.0.1:9200/markcorp/employee/Mmbls2IBnSbSo4fQfVml?pretty

執行完結果
{
  "_index" : "markcorp",
  "_type" : "employee",
  "_id" : "Mmbls2IBnSbSo4fQfVml",
  "_version" : 1,
  "found" : true,
  "_source" : {
    "name" : "Mark",
    "age" : 18,
    "habit" : "cut someone"
  }
}

更新文檔

更新文檔的方法也是相同的,使用 put 方法,然後在指定要更新誰就可以囉。

127.0.0.1:9200/markcorp/employee/Mmbls2IBnSbSo4fQfVml
curl -X PUT -H "Content-Type: application/json" -d @./update.json 127.0.0.1:9200/markcorp/employee/Mmbls2IBnSbSo4fQfVml?pretty

{
  "_index" : "markcorp",
  "_type" : "employee",
  "_id" : "Mmbls2IBnSbSo4fQfVml",
  "_version" : 3,
  "result" : "updated",
  "_shards" : {
    "total" : 2,
    "successful" : 2,
    "failed" : 0
  },
  "_seq_no" : 2,
  "_primary_term" : 1
}

搜尋文檔

假設我們現在有兩筆資料。

{
  name: "Mark",
  age: 18,
  habit: "cut someone"
},
{
  name: "Ian",
  age: 18,
  habit: "hack someone"

}

然後我們現在要搜尋興趣為cut的員工,就執行下面的指令。

curl 127.0.0.1:9200/markcorp/employee/_search?q=habit:'cut'

---
執行結果

{
    "took": 146,
    "timed_out": false,
    "_shards": {
        "total": 5,
        "successful": 5,
        "skipped": 0,
        "failed": 0
    },
    "hits": {
        "total": 1,
        "max_score": 0.2876821,
        "hits": [
            {
                "_index": "markcorp",
                "_type": "employee",
                "_id": "YGYhtGIBnSbSo4fQe2Lh",
                "_score": 0.2876821,
                "_source": {
                    "name": "Mark",
                    "age": 18,
                    "habit": "cut someone"
                }
            }
        ]
    }
}

上面的搜尋是最最基本的搜尋,elasticserach 他提供了非常強大的分析與搜尋工具,將留到下一篇文章中來說明。

 
about 1 month ago

本篇文章中我們將會學習到以下幾個重點

  1. 什麼是 Prometheus 呢 ?
  2. 要如何監控 node http server 呢 ?
  3. 我想從 Prometheus 監控自訂的資訊,要如何做呢 ?

什麼是 Prometheus 呢 ?

在我們平常開發完系統時,我們常常會有個需求,那就是要如何監控我們的系統呢 ?
以確保它 cpu 往上衝時,我們會知道呢。

當然我們可以很簡單的寫個小程式,定期的去呼叫系統取他的 cpu,這是很淺的東東 ~ 那如果是還要一個 api 的請求次數呢 ? 或是平均的某個 api 的請求次數或圖表呢 ? 這時如果還要自幹一個,那就太麻煩囉,所以這時我們就可以使用Prometheus ~

Prometheus 官網上面寫了下面這段話 :

Power your metrics and alerting with a leading open-source monitoring solution.

這句話就是 Prometheus 存在的目的。

Prometheus 的架構

太細節的不說囉 ~ 這裡大概列出這個架構的三個重點:

  1. Prometheus 是用 pull 去取得目標資訊,下面的 pull metrics 就是這個意思,而這裡你只先去記一點,如果你有個 http server ,然後你要用 Prometheus 去監控 server ,那 Prometheus 就會去 xxxx_host/metrics 取得資訊。
  2. PromQL 是 Prometheus 所提供的查詢語言,利用它可以快速的找到我們想要的資訊 (大概)。
  3. AlertManager 是一個警告系統,你只要配置好 Prometheus 在某個東東到了報警線時,就自動發送警告到 AlertManager 然後它會使用某些方法通知你,例如 email or slack。

安裝 Prometheus

請直接到官網直接下載下來。

https://prometheus.io/download/

接下來在解壓縮

tar xvfz prometheus-*.tar.gz
cd prometheus-*

然後進到解壓縮後的資料夾後,執行以下指令,就可以開啟 Prometheus 。

./prometheus

要如何監控 node http server 呢 ?

再開始前我們先去 prometheus server 的資料夾下修改一下 prometheus.yml 這檔案,基本上我們只要先調整 scrape_configs 裡的 scrape_configs,設定 prometheus server 要去監控的目標,如下我們去監控localhost:3000

# my global config
global:
  scrape_interval:     5s # Set the scrape interval to every 15 seconds. Default is every 1 minute.
  evaluation_interval: 5s # Evaluate rules every 15 seconds. The default is every 1 minute.
  # scrape_timeout is set to the global default (10s).

# Alertmanager configuration
alerting:
  alertmanagers:
  - static_configs:
    - targets:
      # - alertmanager:9093

# Load rules once and periodically evaluate them according to the global 'evaluation_interval'.
rule_files:
  # - "first_rules.yml"
  # - "second_rules.yml"

# A scrape configuration containing exactly one endpoint to scrape:
# Here it's Prometheus itself.
scrape_configs:
  # The job name is added as a label `job=<job_name>` to any timeseries scraped from this config.
  - job_name: 'test'

    static_configs:
      - targets: ['localhost:3000']

然後我們就可以簡單的寫一個 nodejs 的 http server 。

const http = require('http')
const port = 3000

const requestHandler = (request, response) => {
    response.end('Hello Node.js Server!')
}

const server = http.createServer(requestHandler)

server.listen(port, (err) => {
    if (err) {
        return console.log('something bad happened', err)
    }

    console.log(`server is listening on ${port}`)
})

接下來,我們需要建立一個 api endpoint 的/metrics

const http = require('http');
const port = 3000;

const requestHandler = (request, response) => {
  if (request.url === '/metrics') {

  }
  response.end('Hello Node.js Server!');
};

const server = http.createServer(requestHandler);

server.listen(port, (err) => {
  if (err) {
    return console.log('something bad happened', err);
  }

  console.log(`server is listening on ${port}`);
});

然後上面有說過 Prometheus 會去監控的目標抓取資訊,而他抓的地方就是/metrics,然後這時我們裡面就要回傳資訊回去。

這裡我們會使用prom-client套件,這個套件是一個 Prometheus client ,它會幫我們抓取他自訂的資料,並且將資料已 Prometheus 可以接受的格式回傳回去。

npm install prom-client

然後再將 endpoint 修改成如下。

const http = require('http');
const port = 3000;
const client = require('prom-client');
const collectDefaultMetrics = client.collectDefaultMetrics;
collectDefaultMetrics();

const requestHandler = (request, response) => {
  if (request.url === '/metrics') {
    response.end(client.register.metrics());
  }
  response.end('Hello Node.js Server!');
};

const server = http.createServer(requestHandler);

server.listen(port, (err) => {
  if (err) {
    return console.log('something bad happened', err);
  }

  console.log(`server is listening on ${port}`);
});

那要如何驗證有沒有資料呢 ? 你只要去 chrome 然後打http://localhost:3000/metrics然後你看到下面的資訊,就代表你有在產生資料囉,下面這些是prom-client自已會去抓 process 的一些相關資訊,如果要自訂的資訊請看下一章結 ~

# HELP process_cpu_user_seconds_total Total user CPU time spent in seconds.
# TYPE process_cpu_user_seconds_total counter
process_cpu_user_seconds_total 0.015771 1520243222641

# HELP process_cpu_system_seconds_total Total system CPU time spent in seconds.
# TYPE process_cpu_system_seconds_total counter
process_cpu_system_seconds_total 0.000973 1520243222641

# HELP process_cpu_seconds_total Total user and system CPU time spent in seconds.
# TYPE process_cpu_seconds_total counter
process_cpu_seconds_total 0.016744000000000002 1520243222641

# HELP process_start_time_seconds Start time of the process since unix epoch in seconds.
# TYPE process_start_time_seconds gauge
process_start_time_seconds 1520243212

# HELP process_resident_memory_bytes Resident memory size in bytes.
# TYPE process_resident_memory_bytes gauge
process_resident_memory_bytes 26382336 1520243222641

# HELP nodejs_eventloop_lag_seconds Lag of event loop in seconds.
# TYPE nodejs_eventloop_lag_seconds gauge
nodejs_eventloop_lag_seconds 0.00048715 1520243222642

# HELP nodejs_active_handles_total Number of active handles.
# TYPE nodejs_active_handles_total gauge
nodejs_active_handles_total 3 1520243222641

# HELP nodejs_active_requests_total Number of active requests.
# TYPE nodejs_active_requests_total gauge
nodejs_active_requests_total 0 1520243222641

最後我們先開啟 Prometheus ,然後連線到http://localhost:9090/,最後到 status 裡面的 target 裡面,你如果看到你的 endpoint 的 state 是up就代表 Prometheus 有成功的去那抓資料囉。

我想從 Prometheus 監控自訂的資訊,要如何做呢 ?

定義好符合 Prometheus 的時序資料格式 metric

假設我們想要自訂個內容,然後給 Prometheus server 抓取,第一步我們要先定義好『資料模式』,你把他想成 server 與 client 的協定就好囉,然後他長的如下:

<metric name>{<label name>=<label value>, ...}

注意 ! metric name 只能用 _ 來分割名詞 Ex. chat_room_count

假設我們要定義一個『ID 1 的聊天室用戶人數』那他的定義應該會長下面這樣:

chatRoomCount{ chat_id=“1”} 100(人數)

決定時序資料的類型

在 Prometheus 中有提供四種時序資料的類型

Counter

這種類型用於『累積值』,例如 Prometheus 內建提供的 http 請求數或錯誤量,它的類型就是 Counter 。

http_response_total{method="GET",endpoint="/api/peoples"} 10
http_response_total{method="GET",endpoint="/api/peoples"} 20
http_response_total{method="GET",endpoint="/api/peoples"} 30
Gauge

這種類型用於『常規值』,例如 cpu 使用率或記憶體使用率就是此類型。

memory_usage_bytes{host=“server-01"} 50
memory_usage_bytes{host=“server-01"} 100
memory_usage_bytes{host=“server-01"} 80
Histogram

主要用於一段時間範圍內對資料的採集,並且可針對內容進行分組。

{小於100毫秒=5次,小於500毫秒=1次,小於100毫秒=2次}
Summary

與 Histogram 相同且支持百分比與跟蹤的結果。

比較詳細的類型說明請參考下篇文章,寫的很詳細的。
傳送門

實作『用戶使用』人數的自訂內容

假設我們希望 Prometheus 可以去指定的聊天室 Server,抓取使用人數的資訊,那我們要如何實作呢 ?

根據上面的教學我們要先定義好資料格式與資料類型。

//資料格式 => 代表聊天室`1`的使用人數當下有多少人.
chatRoomCount{ chat_id=“1”} 100(人數)
//資料類型 => 會選擇 Gauge 而不選 Counter 是因為聊天室的人數是會上下變動,而不是只增加或減少。
Gauge

接下來我們就來實作一下,首先做出自訂資料的格式定義與類型。

// 定義自訂 metric 的格式與類型
// 格式: chatRoomCount{ chat_id=“1”} 100(人數)
// 類型: Guage
const guage = new client.Gauge({
  name: 'chatRoomCount',
  help: 'The metric provide the count of chatroom`s people',
  labelNames: ['chat_id']
});

然後下面就是所有的程式碼,主要的重點就是定義格式,然後讓 Prometheus 從/metrics這個 api 取得資料前,先將 count 資訊更新到 metric 裡面。

const http = require('http');
const port = 3000;
const client = require('prom-client');
let count = 0;
const guage = new client.Gauge({
  name: 'chatRoomCount',
  help: 'The metric provide the count of chatroom`s people',
  labelNames: ['chat_id']
});

const requestHandler = (request, response) => {
  if (request.url === '/metrics') {
    // 更新 metric
    guage.set({
      chat_id: '1'
    }, count);
    response.end(client.register.metrics());
  }
  if (request.url === '/add') {
    count++;
    response.end(`now ~ count:${count}`);
  }
  if (request.url === '/leave') {
    count--;
    response.end(`now ~ count:${count}`);
  }

  response.end('Hello Node.js Server!');
};

const server = http.createServer(requestHandler);

server.listen(port, (err) => {
  if (err) {
    return console.log('something bad happened', err);
  }
  console.log(`server is listening on ${port}`);
});

那我們要如何確認有產生資料呢 ? 你先加幾個用戶幾去,然後再去打/metrics就可以看到結果囉。

http://localhost:3000/add // 加一人
http://localhost:3000/add // 加一人

http://localhost:3000/metrics

結果如下。

# HELP chatRoomCount The metric provide the count of chatroom`s people
# TYPE chatRoomCount gauge
chatRoomCount{chat_id="1"} 2

最後你在去http://localhost:9090你就可以看到那個 tab 中會多增加了chatRoomCount的標籤,然後點進去選 graph 你就可以看到你的圖表了。

參考資料

 
about 2 months ago

本文中我們將會知道兩件事件

為什麼要使用命令模式呢 ? 
什麼是命令模式呢?

為什麼要使用命令模式呢 ?

我們先來想想,假設我們要做一個簡單的計算機的功能,然後他有提供以下方法:

然後實際上執行大概會長這樣 :

add(5) => current = 5
sub(3) => current = 2
mul(3) => current = 6
div(3) => current = 2

這樣我們大概會寫個最簡單的程式碼,大概會長成下面這樣:

class Calculator {
    constructor(){
        this.current = 0;
    }
    add(value){
        this.current += value;
    }
    sub(value){
        this.current -= value;
    }
    mul(value){
        this.current *= value;
    }
    div(value){
        this.current /= value;
    }
    getCurrent(){
        return this.current;
    }
}

const client = new Calculator();
client.add(5);
client.sub(3);
client.mul(3);
client.div(3);

console.log(client.getCurrent());

這有啥問題呢 ?

如果我們這時要增加一個undo的功能呢 ? 上面的程式碼的結構就無法做這種功能了,因為它的緊偶合了。

緊耦合白話文就是你們(模組和類別)關係太好囉 ~ 要修理 A 的話 B 也要先打一頓才行。

而我們上面範例關係太好的兩位可以定義為『行為請求者』與『行為實現者』,行為請求就是指我們外面指接client.add(5),而行為實現者則為add方法裡面的實作。

也因為上面這種狀況,所以我們無法做undo功能,如果我們想要奇耙一點在這案例做排程或是記錄請求日誌的話,也都很難實現。

所以解法就是 :

將『行為請求者』與『行為實現者』的解耦合,也就是所謂的『命令模式』。

什麼是命令模式呢?

就是將『行為請求者』與『行為實現者』分開模式。

下圖中,我們會在請求者與實現者的中間增加一個東西,叫作呼叫者,你也可以稱為Invoker

這張圖的概念你可以簡單的想成,你去一間餐館食飯,然後你就是『請求者』,負責接受點菜的服務生就是『呼叫者』,而最後實際做飯的就是『實現者』。

那為什麼這叫命令模式呢 ? 因為我們會將所有的請求,都封成一個『命令 command 』物件,接下來的服務生,會將這此命令寫在紙上,然後再由他來決定什麼時後要丟給廚師,而客戶如果要取消命令時,也都會由服務生這裡來經手。

程式碼實作

接下來我們要將上面的程式碼來進行修改,首先我們會多增加上面那張圖中的Invoker類別,記好他就是服務生,用來叫廚師做飯的。

這段程式碼中,execute就是用來實際叫廚師做飯的方法,而undo就是用來執行取消這命令的方法。

class Invoker {
    constructor() {
        this.commands = [];
        this.current = 0;
    }

    execute(command) {
        this.commands.push(command);
        this.current = command.execute(this.current);

        console.log(`Execute command : ${command.name} , and result : ${this.current}`);
    }
    undo() {
        const command = this.commands.pop();
        this.current = command.undo(this.current);

        console.log(`Execute undo and result : ${this.current}`);
    }
    getCurrent() {
        return this.current;
    }
}

然後下面是我們每一個命令,這裡每一個都是廚師,然後裡面都有定義好這個命令實際要做的事情與取消時要做的事情,由於我是用 JS 這種語言來撰寫範例,所以沒有個抽象類別或 介面,不然每一個命令應該都會繼承一個叫 Command 的類別或介面。

class AddCommand {
    constructor(value) {
        this.value = value;
        this.name = "Add";
    }

    execute(current) {
        return current + this.value;
    }

    undo(current) {
        return current - this.value;
    }
}

class SubCommand {
    constructor(value) {
        this.value = value;
        this.name = "Sub";
    }

    execute(current) {
        return current - this.value;
    }

    undo(current) {
        return current + this.value;
    }
}

class MulCommand {
    constructor(value) {
        this.value = value;
        this.name = "Mul";
    }

    execute(current) {
        return current * this.value;
    }

    undo(current) {
        return current / this.value;
    }
}
class DivCommand {
    constructor(value) {
        this.value = value;
        this.name = "Div";
    }

    execute(current) {
        return current / this.value;
    }

    undo(current) {
        return current * this.value;
    }
}

最後執行時,我們會麻煩 invoker (服務生),叫實際執行者 (廚師) 進行工作,並且服務生那裡都有記住我們要點的菜,如果臨時想取消,就很簡單囉。

const invoker = new Invoker();
invoker.execute(new AddCommand(5)); // current => 5
invoker.execute(new SubCommand(3)); // current => 2
invoker.execute(new MulCommand(3)); // current => 6
invoker.execute(new DivCommand(3)); // current => 2

invoker.undo(); // current => 6

console.log(invoker.getCurrent());

結論

今天我們學習了『命令模式』,它主要的功能與目的如下 :

就是將『行為請求者』與『行為實現者』分開的模式,為了更彈性操作命令。

你只要記得餐廳的概念就可以理解命令模式的實作了。

再來我們談談它的優缺點。

它最主要的優點是,可讓我們將『行為要求者』與『行為執行者』分開,使得我們可以做更多的運用,例如取消、寫日誌、交易事務 (就是要麻所有命令都執行要麻不要執行)。

但缺點呢 ?
不能否認程式碼的複雜度增加與變長,這也代表,不是所有類似這種命令的功能都需要用到這種模式,在設計一個系統時最怕『過度設計』,所以如果你們確定你的系統是需要『對命令進行特殊的動作時(ex: undo)』時,才需要使用到這種模式。

像我剛剛的計算機範例,如果不需要undo,那用最一開始的範例就夠了 ~~

參考資料

 
4 months ago

在現今伊斯蘭的世界中,我們常常會聽到遜尼派什葉派這兩個派別,那這兩個派別有什麼不同嗎 ? 而且為什麼會又分這兩個派別呢 ? 這兩個派別又對現在的世界有什麼影響呢 ? 在這篇文章中,我們會來慢慢的理解這些事情。

伊斯蘭的起源

首先呢我們要將時間拉回到先知穆罕默德創立伊斯蘭教前的時代,在當時,先知還只是默默無名的路人甲,在西元 610 年時,它在麥加的某個山洞沉思,突然間他聽到大天使加百列的聲音,並且叫先知Iqra (誦讀),而這時它讀出來的東西就是影響了人類世界的古蘭經

然後先知聽到這聲音後,就把發生的這段事情告訴它的第一任妻子哈蒂嘉,她相信這個聲音是神的使者而非邪靈,也因為哈蒂嘉的這段話,穆罕默德就決定成立伊斯蘭教,並把古蘭經的教義宣楊到全世界。

在這裡我們要介紹另外兩位人士,這兩位都是改變伊斯蘭的人,或許也可以這樣說,因為這兩人,才使得伊斯蘭分裂成遜尼派什葉派

真主之獅 - 阿里

阿里最初的先知男追隨者,又被人稱為真主之獅,並且是真主的女婿,可以說是什葉派起源之人。

上面有提到先知決定成立伊斯蘭教時,先知首先做的事情就是先去將親朋好友聚集在一起,其中當然包含先知的堂弟阿里,它這時才 13 歲喔,然後先知說了以下這段話 :

你們之中誰願意輔助我成就此業 ?

想當然而,你和親朋好友說,你聽到神的聲音,要將這理念宣楊出去,你看看有誰會輔助你 ? 當然沒有人會支持,但唯獨阿里說了這段話 :

他們所有人都退縮,而我雖然是這裡最年輕的,我眼晴看不清、肚子最肥大、雙腿最瘦弱,但我會說我,真主的先知,讓我成為您的助手。

在這時後,伊斯蘭的最初三個信士就誕生了 : 穆罕默德哈蒂嘉阿里

任何人都沒有想到,這個動作改變了全世界。

題外話,阿里他有一把劍,它比亞瑟王的『 Excalibur 』還有名,要不是亞瑟王的傳說太有名並且有很多小說或影集來宣傳,不然在基督教世界中,最有名的劍是阿里的配劍『 Dhu'l Fikar 』中文為『分割者』,而也因為阿里手持這把神兵,奮勇殺敵無數的戰役,而贏得先智賜予『真主之獅』(Assad Allah)之名。

信士之母 - 阿伊夏

阿伊夏先知最年輕的一位妻子,這個人年輕、漂亮、又有才智,更是先知最寵愛的一位,但也是最有爭議的,她幾乎可以說是讓遜尼派產生的導火者。

在咱們現今的社會裡,對伊斯蘭女性的第一印象應該是壓迫,在伊斯國家裡,女性不能一個人
出門,並且出門時必須帶頭巾,伊斯蘭女性在婚姻、離婚以及繼承權等各個層面權利都低於男性。

但阿伊夏不同,她是公認的女權主義先行者,她是頂尖的伊斯蘭學者 又是負責發布伊斯蘭教令的法官,又是能在駱駝背上指揮戰場的指揮官,現今有很多為了伊斯蘭女性發聲的人,很多都會以阿伊夏來當做反駁的論點。

阿伊夏生平最有名的軼事就是項鍊事件,簡單的說阿伊夏和部隊走失了,結果有一名年輕男子恰巧路過,將她帶回麥地那,但回到城裏流言四起,那名年輕男子非常的俊美,阿伊夏則是活潑亮麗,不知道在那段時間,沒有沒發生啥迷不可告人之事 ?

先知那時也有懷疑,而且阿里也有桶一刀,但是最後結果就是先知或得啟示,就是古蘭經的下面這篇經文 :

當你們聽見謠言時候,信士和信女對自已的教胞,為何不作善意的猜想,並且說
『這是明顯的謠言呢?』

他們為何不找四個見證者來證明這件事呢 ? 他們沒有找來四個見證者,所以在真主看來他們是說謊的


二十四章: 十二至十三節

因為找不到四個人看到阿伊夏與那位年輕男子做些不好的事情,所以阿伊夏就降無罪 !

不過說來諷刺,阿伊夏為女權先行者,但也因為這段經文,導致不少穆斯林女性被強爆,而找不到四位見證者,因此施暴者被無罪釋放。

阿里與阿伊夏

阿里是先知的堂弟,也就代表這他和先知有相同的血源,而且他也將先知第一任妻子當成母親,那個時對阿里來說,阿伊夏就是另一位繼母的感覺,這或許也是阿里與阿伊夏相處不好的關係。

那阿伊夏呢 ? 他是先知最愛的最愛的妻子,但可惜的事,她沒有和先知生下孩子,在後宮的電視劇中也很常看出,沒兒子沒權力,這也是母憑子貴的成語由來。阿伊夏沒有孩子,所以他對擁有血源與兒子的阿里,自然而然的也就沒什麼好感。

事實上假設阿伊夏有生孩子了,那或許,什葉派就不會誕生了,而接下來下面要說的繼承權的戰爭,也就不會發生了。

分裂使源 - 繼承

會造成伊斯蘭教分裂的最主要源因就是繼承,如果先知在上天堂時一切指名好誰是繼承者,那一切天下太平,但好死不死的就是,先知還沒指令誰是繼承者時,就上天堂了。

在這裡我們可以簡單用一句話說明兩派的官點,但記好這兩派在當時還沒完全成型。

什葉派支持阿里,而遜尼派支持阿布巴克爾

第一任哈理發 - 阿布巴克爾 (阿伊夏她爹)

它在遜尼派中被稱為『受正確指引者 (rashidun)』

在先知要上天堂時,在當時最有可能被認為是繼承者的就是上天說到的,真主之獅阿里,但有個程咬金卻出現了,那就是阿布巴克爾,他那位 ? 阿伊夏他爸,也就是先知的岳父。

為什麼會是他出線了,就先知死後招開了一個民主大會,來選誰是繼承者,然後他就當上了第一任哈里發,那阿里呢 ? 沒參加,他在幫先知淨身。

事實上很多什葉派的學者指出,先知在活者時,早就心中指定阿里為繼承者,但是因為阿伊夏,這位最長時間待在先知的妻子影響,所以導致先知上天堂時,一直沒有指定繼承者。

有一則故事是這樣的,在先知快要掰掰前,事實上他一直招人進來說後事,但是別忘了誰最常待在先知旁,那就是阿伊夏,然後每當先知想叫阿里進來時,阿伊夏就說 : 『難道你不是更想見阿布巴克爾 ~ baba』,先知不勘承受她們的堅持,只能加召,唯獨阿里沒有,QQ。

第二任哈理發 - 歐瑪爾 (先知的岳父 + 孫女婿)

當時在第一任哈里發成為先知的繼承者後,伊斯蘭教眾正準備南征北討,當他們準備攻打拜占庭的大馬士革時,阿布巴克爾卻身染重病。

但是別擔心,有鑒於先知未指定繼承人的風波,這位仁兄早已自已選擇了繼承者,而他選擇了歐瑪爾

歐瑪爾他和阿布巴克爾一樣,都是很早起就追隨先知左右,而且他又是軍事將領,這也是遜尼派認定為什麼選他當第二任哈理發,而不是阿里,而什葉派的看法就是,他們本來就不打算讓阿里遠離權力中心,不管選誰,就是不給阿里當。

題外話,最後第二任哈理發娶了先知最年長的孫女 (就是阿里的女兒)。

還有他在先知還活這時,把女兒嫁給他。

所以他和先知有兩層關係,岳父和孫女婿,假設先知還活這,我真好奇他要叫啥。

第三任哈理發 - 伍斯曼 (伍麥亞貴族 + 女婿)

第二任哈理發,在一次禮拜時,被波斯來的基督徒用匕首刺了六刀,當然歐瑪爾可是個軍事將領,還不至於直接上天堂,但也是差一點兒,他在死於刀傷的幾小時前,他採取一個方式來選擇繼承者。

他提名了六個人,這六個人同時是候選者,也同時是選民,就由這六個人來決定誰是下一任哈理發,六名分別為阿里、阿伊夏的姐夫、阿伊夏的堂兄,伍斯曼、另外兩名不重要,想當然兒最後他們縮小了選擇範圍,只剩先知的兩女婿,阿里與伍斯曼。

阿里這位候選人,四十歲,皈信伊斯蘭的第一人,真主之獅,並且擔任先知和伍瑪發的代理人,又和先知有血源關係,並且又是先知的女婿。

而伍斯曼,也算是很早皈信伊斯蘭的伍麥亞貴族,七十歲,沒打過啥戰,但也是先知的女婿。

但最後結果還是伍斯曼當選,阿里第三次落敗。

第四任哈理發 - 阿里 (真主之獅)

在第三任哈理發伍斯曼統治時期,伊斯蘭擴張得更遠,同時間他也將高級官員都給伍麥亞家族的成員,並且奢侈的炫耀自已的官殿,而且還自稱為『真主的代理人』,這個稱號只有先知擁有,第一、二任哈里發都只敢稱『穆罕默德的代理人』。

當然這些都引起不少人的不滿,最後發生叛變,而掀起這場叛變的是阿伊夏,所對伍斯曼包哮了一段話 :

看看這是什麼 ? 先知的涼鞋 ! 是不是就快要腐朽了 ?
鞋子腐朽的速度,就和你們忘卻聖訓的速度一樣快 !

也因為這段話,而掀起了幾隻叛軍。

其它最有名的是首任哈里發的兒子,阿伊夏的弟弟,穆罕默德。阿布巴克爾,同時間他的母親也再嫁給阿里,因此也是阿里的繼子,這批叛軍本來沒打算殺死伍斯曼,只是希望他下台,但不知道為什麼,極少數人呼籲要發起『聖戰 (jihad)』,在這狀況下,阿伊夏的弟弟同時也是阿里的繼子就殺了第三任哈理發。

然後阿里就上台了。

分裂時刻 - 內戰

在第三任哈理發伍斯曼上天堂後,阿里他被推舉為第四任哈理發。

但這時有兩隊人馬,不滿阿里上台,這兩隊分別為阿伊夏伍麥亞家族

先來說說阿伊夏,雖然她鼓吹人民反對上一任哈理發,但她可不想要阿里上台啊。

阿伊夏雖然反對第三任哈理發,但不想殺掉他,而只是希望他下台,再由其它人上台(她心想的是姐夫或妹夫之一),但是不管如何,他都不希望阿里上台,因此她站在『卡巴』就是所謂的聖壇上哭喊 :

以神之名,伍斯曼的一個小指尖,都比世上這種人全部加起來要強。為伍斯曼流淌的血報仇雪恨,
你將讓伊斯蘭世界更為強大。

在當時的世界裡,雖然知道阿里並不是殺害伍斯曼的人,但當時的詩人總是會大做文章 :

就算阿里你沒公開殺害他,你肯定暗中捅了他一刀。

而另一個反對人馬為伍麥亞家族,第三任哈理發就是從這家族出來,並且穆阿維亞這個後面會提到的大名人,也是從這個家族的人。

也因為有這兩個潮流匯集,伊斯蘭教的第一場內戰發生了。

第一次內戰 - 駱駝之戰

這時伊斯蘭的什葉派遜尼派的雛形就出來了。

支持阿里的在這段時間被稱為阿里黨,這時人後來也是被稱為什葉派的穆斯林,而另一派就是反對阿里的,在這時被稱為伍斯曼黨,也就是後來遜尼派的雛形。

在大約公元 656 年時,雙方在巴斯拉碰頭,在一開始的時後,雙方事實上很不想開戰,雙方的指揮官在帳篷中交談了三天,雙方事實上有達成共識,並解除大軍武裝,但在這晚上,發生了一件伊斯蘭教歷史的神秘事件。

在眾人都在沈睡時,有一批人動手了,到目前為止,沒有人知道是誰發動了攻擊,接下來就像潑出去的水一樣,在也收不會來了。雙方開始大戰,最後就是由阿伊夏的陣營敗北。

阿里在最後終於掌握了權力,但是代價就是同胞的鮮血,但這時一個幕後黑影正慢慢的靠近他,那個人就是穆阿維亞,也就是後來的阿拉伯帝國創立者。

第二次內戰 - 隋芬之戰

在阿里擔任阿里發之後,他要求和各地總督向他宣誓效忠,但這時在敘利亞當總督的穆阿維亞拒絕效忠,並且在現今敘利亞的首都大馬士革,公開的拿出伍斯曼的血衣出來,要求阿里交出殺死第三任阿里發伍斯曼的兇手。

穆阿維亞他真的是個政治天才,他精心籌劃每一步棋,並且懂的將人民的風向轉向自已身邊,讓人民催促他去攻打阿里,而不是自已想去打阿里,最後的結果就是隨芬之戰,伊斯蘭的第二次內戰發生。

在戰爭後期,阿里軍本來有可能會勝利的,但最後穆阿維亞命令軍隊將可蘭經挑在槍尖上,要求阿里接受真主的裁決,阿里本人當然不願意,但問題是士兵們動搖了,因此阿里只能接受裁決,最後結果就是雙方均放棄哈里發職位

瓦哈比派 (Khawāridj) 的誕生

瓦哈比派近乎可以說是最早的伊斯蘭派別,上面有提到阿里接受裁決結果,而其中主戰極端派的人不接受這個結果,因此在當時至少有一萬人左右出走,而這些人就是瓦哈比派,這個單字也就是出走者的意思。

他們的基本教義和其它派別幾乎相同,但是更為極端,他們禁止一切的娛樂,禁止與外人通婚,並認為除了他們以外一切的伊斯蘭教派都是叛教者。

最後他們刺殺了阿里。

題外話,在現今的伊斯蘭世界裡,瓦哈比代表這極端遜尼派主義,其中最有名的塔利班政權、蓋達組織都有這個教派的影子存在,在 1981 年時埃及總統只因為要於敵人談判就被幹掉了。

阿里之死與伍麥亞王朝的建立

阿里被瓦哈比派幹掉了,隨然沒有直接的證劇可以說穆阿維亞策劃的,但是他的確是最後的受益者,他成為了哈里發,而當他在 679 年宣布其子亞齊德一世為哈里發繼承人時,就也代表這哈里發制度就此終結,也就代表這世襲王朝統治的阿拉伯帝國就此產生,咱們這裡常聽到的大食就是指它。

分裂結果

什葉派

當穆阿維亞宣布他的兒子繼承哈里發後,引起了不少人的噴怒,這群人大部份是支持阿里的二兒子胡笙 (Ḥusayn),他帶領者家人與七十二名戰士起程前往伊拉克群求協助,但是不久後就紛紛的收到警告,亞齊德,穆阿維亞的兒子已在等後他。

每一個人都在勸他不要前往,當胡笙仍然還是決定前往,或許他就知道自已必死無疑,但他知道他的死必定會衝擊這個伊斯蘭世界,所以他決定前往。

胡笙與其家人在卡爾巴拉全數陣亡,從此以後這個地方也成為什葉派的聖地,而他也被稱為永遠的殉教者,同時這也是伊斯蘭的阿舒拉節的由來。

而最後分散在各地支持先知血派阿里的人,就是我們現在所說的什葉派

他們的想法是 :

只有先知的血派才是正統,因此不承認除了阿里以外的哈里發

遜尼派

而這此反對只有先知血統才能當哈里發的人,就被稱為遜尼派,也被稱為正統派,伍麥亞王朝就是個代表,他們認為的教義與什葉派基本上是相同的,但與什葉派不同點在於 :

遜尼派認為哈里發應從有資格的人推選出來,不論他是否有先知的血派

這如果以現今的社會來看,決對是正確的思想,但矛盾的是,穆阿維亞將哈里發制變成繼承制,那就與原本來的中心思想矛盾了,這也是後來為什麼什葉派與遜尼派千年的恩怨如同死結一樣,如何解都解不開。

 
5 months ago

在筆者的『基礎資料結構 3 --- 樹狀結構與二元樹』的這篇文章中,我們介紹了樹的基本概念,也學習了如何遍歷樹的方法,在之前的文章中,我們有說到,如果要遍歷樹大至上有以下三種方法 :

  • 中序追蹤 (in-order) : 先走訪左子樹,然後在根,最後在右子樹。(DBEAFCG)
  • 前序追蹤 (pre-order) : 先走訪根,然後在左子樹,最後在右子樹。(ABDECFG)
  • 後序追蹤 (post-order) : 先走訪左子樹,然後在右子樹,最後是根。(DEBFGCA)
  • level-order : 先走訪第一層節點,再走訪第二層,最後會走到最後一層。(ABCDEFG)

補充: 這裡我們在補充第四種追蹤level-order,事實上它就是BFS,也就是一層一層的掃

那為什麼我們這裡要在拿來說一次呢 ?

因為我們之前實作的方法是用『 Recursion 』來實作。

有寫過程式的人大概會知道,在使用recursion實作程式碼,常常有可能會發生memory leak事件,所以我們這篇將要來說明,如何不使用它,來實作以上三種 traversal。

中序追蹤 (in-order)

左 => 根 => 右

iteration

  1. 直接先深入最深的左子樹,並將行經的節點,存放到 stack 中。
  2. 然後深入到最後時,發現是 null ,開始從 stack 中 pop 東西出來。
  3. 接下來在從 pop 出的節點的右子樹開始重複第一個步驟。
/**
 * Tree inordrTraversal (no recursive)
 * Tip: 左根右
 */
BinarySearchTree.prototype.inorderTraversal = function(){
    let stack = [];
    let current = this.root;

    while (current !== null || stack.length !== 0) {
        while(current != null){
          stack.push(current);
          current = current.left;
        }
        current = stack.pop();
        console.log(current.val);
        current = current.right;
    }
}

recursion

BinaryTree.prototype.inOrderTraverse = function(callback) {

    inOrderTraverseNode(this.root,callback);

    function inOrderTraverseNode(node,callback) {
        if(node !== null){
            inOrderTraverseNode(node.left,callback);
            callback(node.data);
            inOrderTraverseNode(node.right,callback);
        }
    }   
};

前序追蹤 (pre-order)

根 => 左 => 右

iteration

  1. 先將 root 存放到 stack 中。
  2. 然後因為pre-order 是先根在子樹,所以直接從 stack pop 出節點輸出。
  3. 接下來在將左右子樹放入 stack。
  4. 重複第二個步驟。
/**
 * Tree preorderTraversal (no recursive)
 * Tip: 根左右
 */
BinarySearchTree.prototype.preorderTraversal = function(){
    let stack = [];
    stack.push(this.root);
    let current;
    while (stack.length > 0) {
        current = stack.pop();
        console.log(current.data);

        if(current.right){
            stack.push(current.right);
        }

        if(current.left){
            stack.push(current.left);
        }
    }
}

recursion

BinaryTree.prototype.preOrderTraverse = function(callback) {

    preOrderTraverseNode(this.root,callback);

    function preOrderTraverseNode(node,callback) {
        if(node !== null){
            callback(node.data);
            preOrderTraverseNode(node.left,callback);
            preOrderTraverseNode(node.right,callback);
        }
    }   
};

後序追蹤 (post-order)

左 => 右 => 根

iteration

  1. 將第一個節點丟到 stack 中。
  2. 然後在進行 while
  3. pop 出節點,然後丟到 temp 陣列中。
  4. 在將該節點的左右子樹丟到 stack 中。
  5. 重複 while
  6. 最後在將 temp 陣列中的節點取出。
/**
 * Tree postOrder Traversal (no recursive)
 * Tip: 左右根
 */
BinarySearchTree.prototype.postOrderTraversal = function() {
    let stack = [];
    let temp = [];
    let current = this.root;
    let isEnd = false;

    stack.push(current);
    while(stack.length > 0){
        current = stack.pop();
        temp.push(current);

        if(current.left != null){
            stack.push(current.left);
        }
        if(current.right != null){
            stack.push(current.right);
        }
    }

    while(temp.length > 0){
        current = temp.pop();
        console.log(current.data);
    }

}

recursion

BinaryTree.prototype.postOrderTraverse = function(callback) {

    postOrderTraverseNode(this.root,callback);

    function postOrderTraverseNode(node,callback) {
        if(node !== null){
            postOrderTraverseNode(node.left,callback);
            postOrderTraverseNode(node.right,callback);
            callback(node.data);
        }
    }   
};

層級追蹤 (level-order BFS)

就是所謂的 BFS 廣度優先搜尋,也就是一層一層找。

  1. 將第一個 root 丟入 queue 中 ( queue 是先進先出 )。
  2. 從 queue 中取出節點。
  3. 然後再將左右子樹丟進去 queue 中。
  4. 然後就重複 2 的動作。

下面的程式碼中多了一些記 level 的東西,那是因為我希望的輸出結果會像下面這樣,所以才有下面的其它步驟。

  1
 2  3
 
[[1],[2,3]]

iteration

BinarySearchTree.prototype.bfsTraversal = function() {
    let current;
    let queue = [];
    let result = [];
    if(!this.root){
        return [];
    }
    
    queue.push({
        node: this.root,
        level: 0
    });
    
    while (queue.length > 0){
        current = queue.shift();

        if(result[current.level]){
            result[current.level].push(current.node.data);
        }else{
            result[current.level] = [];
            result[current.level].push(current.node.data);
        }
        
        if(current.node.left != null){
            queue.push({
                node: current.node.left,
                level: current.level + 1
            });
        }
        
        if(current.node.right != null){
            queue.push({
                node: current.node.right,
                level: current.level + 1
            })
        }
    }
    return result;
}

let tree = new BinarySearchTree();
tree.add(new Node(1));
tree.add(new Node(2));
tree.add(new Node(3));
tree.add(new Node(4));
tree.add(new Node(5));
tree.add(new Node(6));
tree.add(new Node(7));

//輸出: [ [ 1 ], [ 2, 3 ], [ 4, 5, 6, 7 ] ]

參考資料

 
6 months ago

首先我們先來看看最一開始時,要建立連線會那些事情,假設我們的 server 已經開啟 :

var io = require('socket.io').listen(8080);

io.sockets.on('connection', function (socket) {
    console.log("Hello xxxx client");
});

接下來我們要從前端開始追蹤它做了那些事情。

Client 端它做了什麼呢 ??

在最開始時,一定時前端會去進行連線,那我們來看看他在socket.io-client中什麼地方處理。

我們前端與 server 端連結的程式碼如下,從下面程式碼可知,我們執行io('xxxx')時,他就會去後端建立連線。

<script src="/socket.io/socket.io.js"></script>
<script>
  var socket = io('http://localhost');
  socket.on('connect', function(){});
</script>

然後我們來看看 socket.io-client 的這段程式碼長啥樣子,如下,但下面程式碼我們只要先注意newConnection裡面做的事情,因為我們是要建立新的連線。

lookup 原始碼

function lookup (uri, opts) {
  ....

  if (newConnection) {
    debug('ignoring socket cache for %s', source);
    io = Manager(source, opts);
  } else {
    if (!cache[id]) {
      debug('new io instance for %s', source);
      cache[id] = Manager(source, opts);
    }
    io = cache[id];
  }
  if (parsed.query && !opts.query) {
    opts.query = parsed.query;
  }
  return io.socket(parsed.path, opts);
}

下面這段程式碼為manager裡面的程式碼,大部份都是在進行屬性初使化,並且還有一些重連機制的設定,這邊我們直接來看最下面的this.open部份。

Manger 原始碼

function Manager (uri, opts) {
  if (!(this instanceof Manager)) return new Manager(uri, opts);
  if (uri && ('object' === typeof uri)) {
    opts = uri;
    uri = undefined;
  }
  opts = opts || {};

  ...
  
  if (this.autoConnect) this.open();
}

this.open 裡面的程式碼如下,這段就是socket.io-client建立連線的地方,但這邊要注意,我們實際建立連線的地方為eio(this.uri, this.opts)這段程式碼,所以我們接下來要去看engion.io-client的程式碼。

Manger.prototype.open 原始碼傳送門

Manager.prototype.open =
Manager.prototype.connect = function (fn, opts) {
  debug('readyState %s', this.readyState);
  if (~this.readyState.indexOf('open')) return this;

  debug('opening %s', this.uri);
  this.engine = eio(this.uri, this.opts);
  var socket = this.engine;
  var self = this;
  this.readyState = 'opening';
  this.skipReconnect = false;


 ....

  return this;
};

engine.io-client 實際建立連線的地方

這段程式碼是我們實際建立連線的地方,首先他會判斷我們的transport是什麼,是要用websocket還是polling,然後確定好後,就使用this.createTransport來建立實際上要用的transport,最後在將要使用的 transport 開啟,然後他裡面將會建立連線了。

Socket.prototype.open 原始碼傳送門

Socket.prototype.open = function () {
  var transport;
  if (this.rememberUpgrade && Socket.priorWebsocketSuccess && this.transports.indexOf('websocket') !== -1) {
    transport = 'websocket';
  } else if (0 === this.transports.length) {
    // Emit error on next tick so it can be listened to
    var self = this;
    setTimeout(function () {
      self.emit('error', 'No transports available');
    }, 0);
    return;
  } else {
    transport = this.transports[0];
  }
  this.readyState = 'opening';

  // Retry with the next transport if the transport is disabled (jsonp: false)
  try {
    transport = this.createTransport(transport);
  } catch (e) {
    this.transports.shift();
    this.open();
    return;
  }

  transport.open();
  this.setTransport(transport);
};

前端流程圖

前端這邊,我們最後補上一張流程圖,好讓各位官爺更好的追 code 。

後端接受到請求後,它做了啥 ??

每當我們 socket io server 啟動時,會將 engine io server attach 到 http server (srv) 上監聽request事件,下面程式碼的 srv 就是我們 attach 的 server。

attachServe 傳送門

Server.prototype.initEngine = function(srv, opts){
  // initialize engine
  debug('creating engine.io instance with opts %j', opts);
  this.eio = engine.attach(srv, opts);

  // attach static file serving
  if (this._serveClient) this.attachServe(srv);

  // Export http server
  this.httpServer = srv;

  // bind to engine events
  this.bind(this.eio);
};

當收到一個 http 請求時,會轉到 engine.io 下面這段程式碼中,然後會在handleRequest進行主要處理,它這裡只會簡單的檢查一下 req 這個參數,而這參數就是我們 http request 請求內容。

server.on 原始碼

server.on('request', function (req, res) {
    if (check(req)) {
      debug('intercepting request for path "%s"', path);
      if ('OPTIONS' === req.method && 'function' === typeof options.handlePreflightRequest) {
        options.handlePreflightRequest.call(server, req, res);
      } else {
        self.handleRequest(req, res);
      }
    } else {
      for (var i = 0, l = listeners.length; i < l; i++) {
        listeners[i].call(server, req, res);
      }
    }
  });

接下來,下面這段程式碼為handleRequest程式碼,主要用來處理這個請求。首先他會先使用verify進行檢查,看看這一次的請求是不是合法的,而它主要檢查兩個點,首先是transport的檢查,我們要先確定req._query.transport這個參數是否合法,因為我們是要用這參數來決定我們要用那種傳輸方式,而第二個檢查為sid checksid就是每個 client 的編號,在這邊會檢查該條 sid 是否存在以及如果存在是否合法。

檢查完這個 request 請求後,接下來就看看這個請求的 client 有沒有建立請起,如果沒有則執行handshake,有的話則執行onRequest

handleRequest 原始碼

Server.prototype.handleRequest = function (req, res) {
  debug('handling "%s" http request "%s"', req.method, req.url);
  this.prepare(req);
  req.res = res;

  var self = this;
  this.verify(req, false, function (err, success) {
    if (!success) {
      sendErrorMessage(req, res, err);
      return;
    }

    if (req._query.sid) {
      debug('setting new request for existing client');
      self.clients[req._query.sid].transport.onRequest(req);
    } else {
      self.handshake(req._query.transport, req);
    }
  });
};

接下來我們來看看,如果這個 client 還沒建立的流程,也就是要進行handshake
這個方法最主要的功能就是用來建立一條新的連線,然後最後會發送一個connection事件到socket.io

Server.prototype.handshake 原始碼

Server.prototype.handshake = function (transportName, req) {
  var self = this;
  this.generateId(req, function (err, id) {
    if (err) {
      sendErrorMessage(req, req.res, Server.errors.BAD_REQUEST);
      return;
    }
    debug('handshaking client "%s"', id);

    try {
      var transport = new transports[transportName](req);
      ……
    
    var socket = new Socket(id, self, transport, req);
     ……
   

    transport.onRequest(req);

    self.clients[id] = socket;
    self.clientsCount++;

    socket.once('close', function () {
      delete self.clients[id];
      self.clientsCount--;
    });

    self.emit('connection', socket);
  });
};

當我們engion.io已經建立好連線後,它會發送connection訊息到socket.io,然後它在下面這段程式碼,會收到這個事件,然後他這邊會建立一個 client,並且處理一些連線的事務。

bind 與 onconnection 原始碼

Server.prototype.bind = function(engine){
  this.engine = engine;
  this.engine.on('connection', this.onconnection.bind(this));
  return this;
};

Server.prototype.onconnection = function(conn){
  debug('incoming connection with id %s', conn.id);
  var client = new Client(this, conn);
  client.connect('/');
  return this;
};

然後我們來看看client.connection這段程式碼做的事情,這裡它主要會將這名client加入到nsp中也就是 io 的 namespace 裡,但這邊 socket 還沒有產生喔。

Client.prototype.connect 原始碼

Client.prototype.connect = function(name, query){
  debug('connecting to namespace %s', name);
  var nsp = this.server.nsps[name];
  if (!nsp) {
    this.packet({ type: parser.ERROR, nsp: name, data : 'Invalid namespace'});
    return;
  }

  if ('/' != name && !this.nsps['/']) {
    this.connectBuffer.push(name);
    return;
  }

  var self = this;
  var socket = nsp.add(this, query, function(){
    self.sockets[socket.id] = socket;
    self.nsps[nsp.name] = socket;

    if ('/' == nsp.name && self.connectBuffer.length > 0) {
      self.connectBuffer.forEach(self.connect, self);
      self.connectBuffer = [];
    }
  });
};

然後在add中,會將這個 client 產生一個 socket,然後將這條 socket 進行onconnect,並且在最後,會執行self.emit('connection', socket)這裡也就是我們在最上面,實際上觸發connection事件的地方。

Namespace.prototype.add 原始碼

Namespace.prototype.add = function(client, query, fn){
  debug('adding socket to nsp %s', this.name);
  var socket = new Socket(this, client, query);
  var self = this;
  this.run(socket, function(err){
    process.nextTick(function(){
      if ('open' == client.conn.readyState) {
        if (err) return socket.error(err.data || err.message);

        // track socket
        self.sockets[socket.id] = socket;

        // it's paramount that the internal `onconnect` logic
        // fires before user-set events to prevent state order
        // violations (such as a disconnection before the connection
        // logic is complete)
        socket.onconnect();
        if (fn) fn();

        // fire user-set events
        self.emit('connect', socket);
        self.emit('connection', socket);
      } else {
        debug('next called after client was closed - ignoring socket');
      }
    });
  });
  return socket;
};

我們最後來看一下onconnect實際上做了那些事情,這個方法是當我們 connect 確定建立起來後,會進行的動作,它會將這條 socket 連線加入到 nsp 裡的 connected 這個地方,這個屬性也可以讓我們知道,一個 nsp 中有那些 socket 在進行連線。

然後並且會將這條 socket ,加入到一個已自已 id 為名的房間,所以假設我們要追蹤某個 client ,也可以選擇加入到該名使用者為名的房間,這樣該名使用者收到的事件,我們也都可以收到,不過這只是變化用法,到不是這邊的重點。

最後他會執行this.packet就是會將這個訊息,傳送到 client 端。

onconnect 原始碼

Socket.prototype.onconnect = function(){
  debug('socket connected - writing packet');
  this.nsp.connected[this.id] = this;
  this.join(this.id);
  var skip = this.nsp.name === '/' && this.nsp.fns.length === 0;
  if (skip) {
    debug('packet already sent in initial handshake');
  } else {
    this.packet({ type: parser.CONNECT });
  }
};

後端的流程圖

最後,這邊將提供後端的流程圖,讓我們更容易的理解它的流程。

 
6 months ago

socket io 是 nodejs 所提供的套件,它主要可以做的事情就是推播功能

你想想,假設你要做個股票報價網站,然後當你後端收到新的股價時,你要如何的送到前端 ?
在傳統的 server 與 client 架構下,因為只能由 client 向 server 發出請求,而不能由 server 發送新的訊息到 client,所以當時的人們的解決方案就是輪詢,固名思意就是指定時的去 server 找資料。

但這種方案有缺點,你想想,你有可能去 server 抓 10 次資料,它有可能 10 次都有新的資料嗎 ? 不一定對吧 ? 所以最理想的方案一定是從 server 端有新資料就自動推送到 client 端。

websocket就是一個由 html 5 所發布的新協議,它就可以做到上面所需要的功能。

socket.io是啥 ? 它是會根據你的 client 所支援的功能(websocket、comet、長輪詢…)來決定你後端要如何的發送資料,更白話文的說,你不用管你的 client 有沒有支援 websocket,socket.io 一切都自動會處理好,你只要和我說啥時要送資訊到前端就對了。

Socket.io 的組成

請參考筆者的這篇文章。

Socketio 的架構

簡單 client 與 server 的溝通範例

server 端程式碼如下,這段程式碼當與 client 端建立一條 websocket 連線後,會直接對該條連線傳送個{hello: "world"}訊息。

var io = require('socket.io').listen(8080);

io.sockets.on('connection', function (socket) {
    socket.emit('news', { hello: 'world' });
    socket.on('my other event', function (data) {
        console.log(data);
    });
});

前端 :

<script src="/socket.io/socket.io.js"></script>
<script>
    var socket = io.connect('http://localhost:8080');
    socket.on('news', function (data) {
        console.log(data);
        socket.emit('my other event', { my: 'data' });
    });
</script>

這樣就可以完成簡單的推播功能囉。

Socket.io 的 Rooms 與 Namespaces

在 socket.io 有兩個很重要的概念roomsnamespaces,這邊你只需要記好一件事,那就是它們兩個存在的原因都是為了分組,把要傳送的訊息,送到你想要的群組中。

Namespaces

我們先看看namespaces,上面的範例中有沒有注意到,我們都是用io來進行所有的操作,假設我們要放送訊息到所有連線的 socket,那我們只要下達該指令 :

io.emit('news', 'Hi I am Mark')

接下來然後我們也可以使用 rooms 來將 io 裡面的 socket 分類到不同的房間中,所以當我們要傳送指定的訊息到某個房間中只要下達下面的指令 :

io.to('全家就是我家').emit('news', 'Hi I am Mark')

那這邊我想問問,有沒有辦法建立另一個 io 呢 ? 例如我想建立一個是專門處理股票的 io ,而另一個是專門處理期貨的 io ,這時我們就可以使用namespaces裡的of這方法來處理。

例如我們先來建立一個股價的 namespaces :

var stock_io = io.of('/stock');

然後我們就可以使用這個stock_io來進行我們上面提到的所有動作。

namespaces 你可以想成, 子 io ,它可以做所有 io 可以做的事情 (基本上)

Room

接下來我們來說說rooms,這東東的概念和namespace事實上很像,但記好,rooms 是在 namespaces 底下的

假設你有一個需求,有3個用戶在用你的股價報價系統,其中兩個是在看 1101 台泥的股價,而其中一個是在看 2330 台積電 的股價,這時你應該要注意,不能將 2330 的股價推到在看 1101 股價的使用者那。

socket.io 的 rooms 的功能就可以解決上面的需求,rooms的功能白話文就是你可以發送訊息到指定的房間,像 1101 就是一個房間,而 2330 就是另一個房間,所以假設有 1101 的訊息要推送,只要針對該 room 的用戶進行推送就夠了。

那要如何加入到房間呢 ?

如下 :

io.on('connection', function(socket){
  socket.join('1101');
});
那要如何傳送訊息到指定的房間呢 ?

如下園式碼,你就可以發送訊息到這個房間裡。注意這邊是用io來發送訊息,上面簡單的範例是用socket.emit來送是因為上面範例只需要發送訊息給那條 socket 連線就好,而這邊我們是要發送給1101 這個 room中的 socket,所以要用io來發送。

 io.to('1101').emit('xxxx股價')

這兩個的差別

最後終結一下這兩個的差別

你可以把 namespace 的功能想成可以建立多個子 io ,不同的子 io 可以處理自已的事情,也代表有自已的 rooms ,io1 與 io2 兩個如果都有 room 為 movie 的,也不會影響到什麼,因為它們是分屬不同的 io 了。

在 Socket.io 中使用 middleware

在平常我們 web 開發時,有時後會有下面這種需求 :

每一個 http 請求進來前,需要先檢查登入狀態

通常這種時後我們就會建立一個 middleware 來處理登入狀態,這邊要注意 middleware 不是用來專門處理登入的東東,它只是一個概念,它真正的定義如下 :

middleware 又稱中介層,用來處理所有進入或離開主體前的事務。

像我們每個 http 請求進到主體前,我們需要先確認它的狀態,又或者是進到主題前就先將 log 寫好,這些都是可以放置到middleware來處理,你只要記好,主體就只做主體要做的事情就好。

當然在 socket.io 中我們也是有這個需求,例如每當要建立 websocket 連線時,要預先處理的事情,我們都可以建立 middleware 來處理。

socket.io 提供use方法來讓我們建立 middleware ,範例程式碼如下 :

var srv = require('http').createServer();
var io = require('socket.io')(srv);
var run = 0;
io.use(function(socket, next){
  run++; // 0 -> 1
  next();
});

var socket = require('socket.io-client')();
socket.on('connect', function(){
  // run == 2 at this time
});

像上面的官方程式碼中,下面這段就是 midddleware 的使用方法,裡面的 use 就是一個 middleware 方法,在建立 websocket 前會先處理的事情。

io.use(function(socket, next){
  run++; // 0 -> 1
  next();
});

所以假設我們需要先處理log 事務快取事務時,我們程式碼就大概會長如下 :

io.use(logMiddleWare);
io.use(cacheMiddleWare);

function logMiddleWare(socket, next){
    寫 log ~~~
    next();
}

function cacheMiddleWare(socket, next){
    取得暫存資料.....
    next();
}

參考資料

 
6 months ago

socket.io 是 node js 的一個 framework,它可以幫助我們建立聊天室這種推播功能的系統,這篇文章我們不會說明它如何使用,而是要理解 socket.io 這個套件的架構組成。

socket.io 主要由以下幾個東東構成的 :

  • engine.io、engino.io-client
  • socket.io-parser
  • socket.io-adapter
  • socket.io-client
  • socket.io-protocol

接下來我們將一個一個說明它們是做啥用的,並且最後會在進行一個總結。

engine.io

engine.io是一個實際執行 socket.io 通訊層級的 libary,嚴格說起來,socket.io 的核心就是engine.io,所有的建立連線、傳輸資訊實際上都是由它來做,並且根據前端傳送回來的資訊,來決定使用什麼傳輸方式。

目前 engine.io 所提供的溝通方式有以下幾種 :

  • polling-jsonp
  • polling-xhr
  • pollin
  • websocket

上面有提到,socket.io 本身不提供連線功能,而是在 engine.io 才提供,所以事實上,如果你沒有一定要使用到 socket.io 的功能,而只是要連線到 http server 或是監聽 port 的話,只要用 engine.io 就夠了,這邊有個重點要記得 socket.io 是個 framework 而 engine.io 只是個 libary,只要分的出這兩個差別,你就可以自由的選你要的使用。

var engine = require('engine.io');
var server = engine.listen(80);

server.on('connection', function(socket){
  socket.send('utf 8 string');
  socket.send(new Buffer([0, 1, 2, 3, 4, 5])); // binary data
});

engino.io-client

engine.io-clientsocket.io-client的核心,所有關鍵的連線、選擇傳輸方式,都是在這裡面執行。

我們這裡來看看,它是從那決定要用那種的傳輸方式(websocket、polling)。

engine.io-client下面這段程式碼(程式碼傳送門)中 ,這段onOpen是在 socket 要與 server 進行連線時,會先執行的事件,其中,就是由this.probe(this.upgrades[i])這個方法來決定要用什麼方式(websocket、polling)來進行傳輸。

Socket.prototype.onOpen = function () {
  debug('socket open');
  this.readyState = 'open';
  Socket.priorWebsocketSuccess = 'websocket' === this.transport.name;
  this.emit('open');
  this.flush();

  // we check for `readyState` in case an `open`
  // listener already closed the socket
  if ('open' === this.readyState && this.upgrade && this.transport.pause) {
    debug('starting upgrade probes');
    for (var i = 0, l = this.upgrades.length; i < l; i++) {
      this.probe(this.upgrades[i]);
    }
  }
};

然後在後端 server ,也就是engine.io裡根據前端傳送回來的url參數的Transport來決定要用什麼來進行傳輸 :

url 範例 : 

/engine.io/default/?transport=polling

engine.io的下面這段程式碼裡,check用來驗證傳進來的參數是否合法,來決定這個transport參數是否合法,然後再來將 http 升級為 websocket 協義。

server.on('upgrade', function (req, socket, head) {
      if (check(req)) {
        self.handleUpgrade(req, socket, head);
      } else if (false !== options.destroyUpgrade) {
        // default node behavior is to disconnect when no handlers
        // but by adding a handler, we prevent that
        // and if no eio thing handles the upgrade
        // then the socket needs to die!
        setTimeout(function () {
          if (socket.writable && socket.bytesWritten <= 0) {
            return socket.end();
          }
        }, destroyUpgradeTimeout);
      }
    });

socket.io-parser

在 socket.io 的世界中,有一個東西叫做 packet,它是所有溝通的基礎包,事實上它也就是 socket.io 的協議,有一個東西叫socket.io-protocol(傳送門),它裡面有定議好,你這個 packet 要長什麼樣子。

下面為最簡單的 packet 包 :

{
    type: 2,
    data: [{
        word: "hello mark"
    },{
        word: "hello gg"
    }]
}

其中2所代表的為這個 packet 是要用來處理event事件,像要傳送到前端的事件也是用這個代號,這個數字會由 socket.io-protocol 裡定義好。

然後每當我們要傳送 packet 到前端時,都會先使用socket.io-parser`將 packet 給 encode ,而致於為什麼要 encode 後在傳呢 ? 主要原因,可能是希望儘可能的將要傳送出去的 packet 縮小已節省傳輸成本。

像官方所提供的socket.io-parser會將上面的 packet 包 encode 成如下數據 :

"2[{"word":"hello mark"},{"word":"hello gg"}]"

它的確比原本要傳輸的資料還少點兒東西,然後前端在再用相同的socket.io-parser來進行decode,變成原來的 packet 包。

這就是socket.io-parser所做的事情,當然我們也可以自訂一個 parser ,如果你有需要的話,例如你想使用 xml 來當傳輸格式,這時你就要自訂一個 parser 了,雖然覺得應該不會想用xml來傳。

socket.io-adapter

在理解這套件之前,我們先看看adapter這代表什麼意思呢 ? 我們直接用這個單字去 google 圖片一下,然後可以看到下圖的結果 :

嗯哼,就是電源轉接器,在插頭和我們的機器之間所需要的東西,在程式開發中,你有沒有遇過下面這種問題呢 ?

我和 A 要 api 來使用,但發覺它的 api 我需要調整過後才能使用。

所以通常你這時,應該中間會有一個東西,來呼叫這隻 api ,然後再裡面先整理一下,然後才傳出去給主要的方法來使用,對吧 ? 這時那中間的東東就是所謂的adapter它本身就是一種設計模式。

好回來到socket.io-adapter,那我們的插頭和機器各代表什麼呢 ? 先來說說機器,機器就是我們的 socket.io 那插頭呢 ? 嚴格來說是儲存空間,儲啥呢 ? 就是namespace、rooms、sids這些東東。

socket.io-adapter預設是存放在記憶體之內,所以如果你要用 redis 或 mq 之類的來做儲放,你就只要調整你的 adapter 就好,目前官方有提供socket.io-redis可使用,它也是一個 adapter。

基本上你要進行任何 socket.io 提供的 emit、broadcast、join room 這些功能,都一定會到這一層來做處理。

socket.io-client

這個東東就是讓我們在前端使用的東西,假設我們在後端 server 建立好喔,我們就可以如下面這樣,連建立連線 :

<script src="/socket.io/socket.io.js"></script>
<script>
  var socket = io('http://localhost');
  socket.on('connect', function(){});
  socket.on('event', function(data){});
  socket.on('disconnect', function(){});
</script>

然後如果你在後端要寫整合測試時,想要模擬前端,也可以如下使用 :

var socket = require('socket.io-client')('http://localhost');
socket.on('connect', function(){});
socket.on('event', function(data){});
socket.on('disconnect', function(){});

這邊還有一個重點,它與 socket.io 一樣核心都是engine.io-client並且也是由它來決定我們要用什麼傳輸方式(polling、websocket)。

socket.io-protocol

最後是socket.io-protocol,這個事實上上面有說明過了,我們在來複習一次。

它是個協定,它不是程式碼、套件或其它可以執行的東西,它是一個規定,它定議好socket.io 要如何的傳輸資料,它主要定義了以下二個主題 :

Parser API

Parser API上面有提到,它是用來將 packet 包進行 encode 與 decode 的東東,在 protocol 中,它實際定義一個 parser api 需要有那些東西。

下面為它的主要定義

  • Encoder.encode(Object: packet, Function: callback)
  • Decoder.add(Object:encoding)

Encoder就是用來進行 encode 的類別,然後它需要提供encode方法,並且有兩個參數分別為packet 和 callback

Decoder就是要將 packet 進行 decod 會類別,並且需要有個add方法,來進行處理。

像我們上面提到的socket.io-parser就是根據socket.io-protocol所定義的parser api實作出的程式碼。

var parser = require('socket.io-parser');
var encoder = new parser.Encoder();
var packet = {
  type: parser.EVENT,
  data: 'test-packet',
  id: 13
};
encoder.encode(packet, function(encodedPackets) {
  var decoder = new parser.Decoder();
  decoder.on('decoded', function(decodedPacket) {
    // decodedPacket.type == parser.EVENT
    // decodedPacket.data == 'test-packet'
    // decodedPacket.id == 13
  });

  for (var i = 0; i < encodedPackets.length; i++) {
    decoder.add(encodedPackets[i]);
  }
});

Packet

Packetsocket.io世界裡的溝通包包,像你如果要放送訊息或是進行 connect 時,它們都是傳送的都是packet

在 protocol 中,它定義好了,一個 packet 要長什麼樣子 :

{
    type: Number,
    data: [],
    id: Number,
}
type

就是用來決定,這個包是要做什麼事情,protocol 它定義了以下幾種類型 :

  • CONNECT(0)
  • DISCONNECT(1)
  • EVENT(2)
  • ACK(3)
  • ERROR(4)
  • BINARY_EVENT(5)
  • INARRY_ACK(6)
data

就是你這個包傳送的資訊,它常都是我們自已的,不過記好,它是要放成一個陣列。

id

用來識別這個包是誰的,需要時在設定。

總結

最後我們來使用下面這張圖,來總結一下 socket.io 這個 framework 的架構 :

上圖為 socket.io 的整體架構,我們最後來複習一次。

首先最主要的主體為engino.io,所有的連線、傳輸方式的核心都是他,然後當你想要與其它東西進行溝通時,它們統一的溝通元件packet都需要使用socket.io-parser來進行 encode 與 decode ,因為某些傳輸方式 websocket 只能用文字與二進位數據,還有這些定義都會寫在 socket.io-protocol裡面,最後如果想你要與儲存元件溝通,請建立一個 adapter 來處理。

參考資料

 
7 months ago

在上一篇文章中,我們說明了如何的設計像 line 的聊天群的架構設計,而這一篇我們要來說明聊天室的架構設計,這東西和上一篇有什麼差別 ?

通常聊天群是會由用戶提出申請,然後管理者來加入到該群裡,而聊天室則不相同,它是用戶可以自由自在的加入或退出,這也代表這,通常聊天群會限制人數,像 line 好像就限制 500 人,而聊天室則否,他通常不會限制人數。

那這也代表我們要面對什麼問題呢 ? 我目前想想主要有兩個 :

  1. 由於沒有限制人數,所以通常我們的架構要考慮擴展性。
  2. 訊息的即時性非常的要求,如果一個訊息傳輸慢了,會導致其它人無法理解上下文。

最簡單的聊天室架構 V-1

基本上和聊天群的架構相同,都是一個Business Server和一個Message Server,其中前者做的事情是為所有需要使用 http 協議的工作,更正確的說是 http 短連接的工作,如新增聊天室、登入、登出、註冊這類事情的,都屬於 Business Server ,而所有使用 websocket 協議的都是屬於 Message Server 的工作。

聊天室 V-2

上面的架構有沒有啥問題呢 ? 有的 ! 請想像一個情境 :

用戶 A 從 business server 登入後,然後再去 message server 建立連線,但問題是 message server 怎麼知道這條連線是用戶 A 呢 ?

在一般的 web 應用中,每當 client 連結 server 時,server 會產生唯一個 sessionId ,並用它來連結 server 內的存放空間,然後會將 sessionId 存放到 cookie 中,這樣每一次 client 進行請求時,server 都會去 cookie 中取得 sessionId 然後再去 session 取得資料。

從上面的說明可知 session 是存放在 server 中,所以上面的情境變成 business server 產生 session 但問題是 message server 沒有 session。

所以我們將架構修改成如下 :

我們會新增一個 redis 用來專門存放 session 當使用者登入後產生 session 資訊存放入 redis 中,接下來 client 要與 message server 建立連結時,由於它是使用 http 進行連線,所以它會有包含 cookie ,內含已加密過的 sessionId 進來,最後到 message server 時他會用這個 sessionId 再去 redis 取得使用者資訊。而每當登出時,business server 相同的也會更新 redis 裡面的資料。

V-2 版本大致上就是如此 ~

聊天室 V-3

上面的架構理論上基本應該可以運行,但根據我們的要求,用戶數有可能會激增,所以我們這邊的Message Server需要考慮擴展,會優先考慮擴展他主要原因在於,每一個 websocket 都代表這一條 tcp 連線,而由於他是持久連接,白話文就是它會一直佔著一定的資源,它並不像 http 用完一定時間就收,所以如果一個 message server 有 1 萬人在聊天室,就也代表這需要同時維持 1萬條 tcp 連線,會上西天的,所以說我們需要一個代理器來做 Load balance 可以幫助我們將流量分散,架構變成如下 :

其中 Proxy 可以做很多的事情,其中最重要的就是要幫助我們分散流量,它會將我們 http 的請求 (登入、登出) 導到 business server。 websocket 的連接,則導到其中一個message server

這時我們來模擬一下,用戶在聊天室時發送訊息的流程 :

  1. client 發送訊息 。
  2. proxy 收到請求,並將它導至 message server A 。
  3. 然後 message server A 將該訊息 broadcast 到聊天室的用戶 。

目前是建議 proxy 使用 nginx 來處理,他本身就提供了 load balance 的功能,而且它也可以幫助我們來防禦一些 ddos 攻擊。

這邊有一個重點要記得:

它建立websocket 通道是長成:

client ==== proxy ==== message server
而不是
client ==== message server

聊天室 V-4

嗯嗯 ~ 看上去都沒問題。

但這是有前提假設的,那個假設就是 :

那個聊天室的所有用戶,都在同一個 message server 裡 。

你想想如果有個用戶不在 message server A 裡,那 broadcast 時不就代表那個用戶不會收到訊息 ?

那這邊要如何解決呢 ? 我目前想到的二個方法就是 :

  1. 在 load balance 時,將同一聊天室的用戶都導到同一個 message server 裡 (QQ)。
  2. 建立一個 pub/sub 的redis 來處理。

我先說說第一個的方法,我們使用 load balance 根據聊天室來將 websocket 連線導至某台 message server ,也就是說同一個聊天室的用戶都放在相同的 message server 裡,所以當有用戶發訊息到聊天室時,那個特定的 message server 就會自動的 bordcast 出去。

而當用戶要加入某個聊天室,而想發出xxxx加入聊天室時,因為那個聊天室在那個 message server 所以只要往那個 message server 發送訊息。但這種方法的缺點就在於你要如何分配聊天室在那個 message server , 分配不好,大部份流量都往那個 message server 去,反而失去我們擴展 message server 的用因。

這方法我覺得還有一個問題,那就是假設我們其中一台 message server 上西天了,那不就代表該聊天室的用戶都無法進行連線了 ? 除非我們的 load balance 演算法有設計好,不然問題很大。

目前比較推第二個方法,就是架構個 pub/sub 功能的 redis ,如下圖 :

然後我們來說一下它的運作流程,我們先看看下圖,當用戶 A、B、C 加入某個叫 kkbox 的聊天室時,當在建立連線時 message server 會去 redis 進行 kkbox這個 channel 的訂閱 (subscribe)。

接下來當用戶 A 發送訊息時,會前往 redis 對應的 kkbox channel 進行訊息 pub ,然後存在用戶 B、C 的 message server 收到訂閱的敲門,就會將消息推送到用戶 B、C了。

聊天室 V-5

上圖為我們到目前的架構,基本上可以動,理論上應該運行的不錯,但實際上呢 ?
不知道 !,現在環境難以預測,所以可能現實環境會發生下面的事情 :

啊 ! proxy gg 了,所有的請求都不能進來了 !

由於我們 proxy 那裡是使用 nginx 來做 load balance ,所以如果我們那裡掛掉,那我們的還有服務事實上就說掰掰了,所以為了避免這種狀況,我們需要用到keepalive的功能。

keepalive是啥 ? 它主要的功用就是如下 :

在一個集群中,會隨時的檢查每一台機器的健康狀態,保證該集群可以服務。

所以說,我們可以在 proxy 建立一個集群,也代表這可能有多個 nginx,然後我們在搭配 使用 keepalive,這樣每當有一台 nginx 上西天後,keepalive 就會檢查到,然後會立即的轉換成另一台可以用的 nginx,這樣也確保了我們的整體服務不會因為一台 nginx 上西天就全死了。

聊天室 V-6 (在想想)

基本上,上面的架構的確可以運行,但是呢 ~ 我們有沒有辦法確定訊息的即時性是正確的,例如下面的情況 :

聊天室中有 A 然後他發了三句話 :

A(最早) : 肚子餓了吃啥 ?

B(第二) : 吃拉麵如何 ?

C(最後) : 還是吃飯 !

但有沒有可能在實際的聊天室看到的是變成這樣 ?

C(最後) : 還是吃飯 !

B(第二) : 吃拉麵如何 ?

A(最早) : 肚子餓了吃啥 ?

會出現這種狀況,最有可能的場景就是分散式的問題,因為每一個服務都是不同的機器上,而不同的機器上會有自已的本地時鐘。

像假設我們 message server A 在台灣、message server B 在日本,這時他們的本地時鐘就是不相同的,所以我們在判斷訊息的先後順序不能使用 server 端時鐘,同理 client 端的時鐘也不行。

我這邊簡單的整理一下,很難保證時間順序性的原因 :

時鐘不一致 :

就像我們上面說的範例,你放在不同的機器,會有不同的本地時鐘。

多用戶端 :

假設我們有兩個用戶 A、 B ,一個 server,然後 A 先發送訊息,接下來是 B 再發送訊息,但因為網路傳輸的問題,我們不能保證 server 先收到 A 。

多伺服器端 :

假設我們有一個用戶 A ,然後兩個 server A 與 B ,然後先發送訊息到 server A、在發送訊息到 server B ,但因為兩台機器時鐘不一定相同,所以可能會導致時間不正確。這邊你可以想成,假設有 load balance 時,第一次訊息它導至 A,而第二次訊息導至 B。

不好意思,請參考這篇文章 如何保证IM实时消息的“时序性”与“一致性”? ,不過這篇文章中有幾個解法我是有點疑問的,像它裡面有個在單點 server 上,生成有順序的 id ,但問題在於如果你進來的順序就已經亂掉了(網路問題),那你生成的這 id 事實上也沒什麼意思,除非你可以確保,你進到 server 時的順序是正確的,這 id 才能使用。

所以這方面的問題,改天在另生一篇文章出來寫寫,這邊就先降 ~

參考資料

由於本篇參考不少資料,所以以下只列出所參考資料出處。