轉：猜想祖國的偉大的圍牆的原理

防民之口，甚於防川。
引用自百度百科的對於｢防民之口，甚於防川｣的啟示：

中國歷史上有很多統治者荒淫無道，但他們又怕人民議論，就採取了壓制社會言論的措施，以為可以高枕無憂、平安無事。實際上這是最愚蠢的作法，它 不僅使下情無法上達，錯誤的政策得不到糾正，加劇社會矛盾。更可怕的在於雖然民眾口上不說，但心裏卻充滿了仇恨，只要社會矛盾到達臨界點，大規模的暴亂必 然爆發，給社會生產力造成極大破壞。正可謂｢防民之口，甚於防川。｣中國人是世界上最能忍受暴政的民族，但也是爆發起義最多的國家。

無邏輯的輿論的控制，究竟會引發什麼後果呢？或許多年後答案便自己浮現。

暫且不談論我們偉大的圍牆的對於人民生活的影響，我們來看看它的技術方面的實現。
景德鎮的國域網
景德鎮的國域網對外的出口線路不多，只要在這些出口處架設好強大的過濾器，便可以保障國民思想安全性。這樣過濾不會太麻煩，因為出口就這麼幾個，派兵守住就好。

在網路課上，劉孜文老師給我們講了一個他的經歷，我大致複述一下（語文很差，希望不會扭曲原意）：

老師的一個同學在收到領導指示，要弄一個省級的防火牆，這樣可以方便警察叔叔將一些騙子網站、黃色網站過濾掉。於是他的同學開始鴨梨巨大了，因為一個省的對外的線路有很多很多條，很難在每一條出口安上防火牆，因為線路太多了。

這個例子說明，一個國家級的要比一個省級的圍牆容易得多，原因是關口少，不像省與省之間的線路四通八達。

那麼我們知道了在國域網對外的出口處有各種Cisco等強大的怪獸守住，我們來探討一下這些怪獸的機制。
工作機制
在普遍的看法，我們偉大的圍牆工作機制主要包括IP黑名單、內容過濾和DNS劫持。
IP黑名單
怪獸手裡肯定把握著一份黑名單，上面寫著Facebook、twitter、youtube等的ip地址，一旦發現鎮民發往黑名單中地址的請求數據包，就直接無情地丟棄，當鎮民等到花兒都謝了都沒有收到伺服器發回的包，他便生了一種叫超時的病而放棄了。

溫總理曾說過：中國財富再多，除以13億人，就少得可憐了；中國問題再小，乘以13億人，也就很大了。

一個秒鐘一個請求*13億，就是一個很大的請求了。請問怪獸如何可以高速地在IP黑名單中查詢這個ip在不在呢？

對於ipv4，每個ip地址32位，可以看作32位無符號整形。也就是2^32個ip地址。黑名單應該也不小，怎麼也有幾千幾萬幾十萬吧。那麼怪獸怎麼處理呢？

怪獸如果很2B的話，它會拿著收到數據包的ip一個一個地和黑名單中的ip比較，如果在黑名單裡面就將其丟棄，不在那就放過它。這樣怪獸花的時間是O(n)，n為黑名單的大小。
怪獸智商稍微高一點的話，它會將黑名單中的排好序，然後使用偉大的二分查找法術，就可以花O(log(n))的時間判斷那個ip在不在黑名單裡面。
怪事如果智商不錯的話，它會構建一個4G個單位的哈希表blacklist，然後直接將ip作為索引，初始化哈希表 blacklist，blacklist[ip] = 1, if ip in ip_blacklist，這樣，在一個請求過來的時候，怪獸只需要花費O(1)的時間就可以知道ip在不在黑名單裡面。

對於一個4G個單位的ip黑名單hash table，我們可以一個bit來表示一個ip是不是屬於特殊對待ip。於是我們的ip hash table大小為：

4G bit = 4 / 8 G Byte = 0.5 GB = 512 MB

怪獸只需要有512MB的空閑記憶體就可以構建這麼一個hash表，然後無論是多線程模式的還是多進程模式的設計都可以共享這塊放hash表的記憶體， 中途如果有新增或者取消話都可以直接更新hash表，當然可能會因為有緩存而導致不一致，但是在這個大環境下也不一那麼較真，讓正確率100%，所以連鎖 都可以不用加，這樣怪獸的負擔會輕很多。不過bitmap在IPv6下是不那麼實際的，因為使用記憶體會非常巨大，2^128bit，會消耗 39614081257132168796771975168GB的記憶體來放bitmap。可能這也是怪獸沒有對ipv6下手的原因。

我們來看一段代碼，描述了高效判斷是否在黑名單的方法。


#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <arpa/inet.h>
#define BITSPERWORD 32
#define SHIFT 5 // 2 ^ 5 = 32
#define MASK 0x1F // 0x1F = (11111)b
#define SET(a, i) ((a)[(i)>>SHIFT] |= (1<<((i) & MASK)))
#define CLR(a, i) ((a)[(i)>>SHIFT] &= ~(1<<((i) & MASK)))
#define TEST(a, i) ((a)[(i)>>SHIFT] & (1<<((i) & MASK)))
inline void test_block(int* blacklist, char* ip)
{
if (TEST(blacklist, inet_addr(ip)))
printf("%s is blocked.\n", ip);
else
printf("%s is pass.\n", ip);
}
int main(int argc, char *argv[])
{
const unsigned long long N = 4294967295;
const unsigned int SIZE = N / BITSPERWORD + 1;
int* blacklist = (int*)malloc(SIZE * sizeof(int));
memset(blacklist, SIZE, 0xff);
SET(blacklist, inet_addr("243.185.187.39"));
SET(blacklist, inet_addr("8.8.4.4"));
SET(blacklist, inet_addr("202.84.125.66"));
SET(blacklist, inet_addr("222.221.31.55"));
SET(blacklist, inet_addr("183.182.44.111"));
SET(blacklist, inet_addr("255.255.255.156"));
test_block(blacklist, "8.8.4.4");
test_block(blacklist, "222.222.222.222");
test_block(blacklist, "202.84.125.66");
test_block(blacklist, "88.54.32.156");
test_block(blacklist, "255.255.255.156");
free(blacklist);
return 0;
}

當然可能還有更好的方法，請賜教～
內容過濾
曾經在一個人部落格看到程序員的工作環境怎樣為好，裡面有一句讓我影響無比深刻｢訪問Google的服務沒有障礙｣。這個真滴非常重要呀，雖然現在Google的https可以用了，不過好慢好慢，受不了啊。

像我們如果在Google搜尋某些關鍵詞後，我們從Google打開了某些網址後，不僅那些網站訪問不了，而且Google就會被怪獸吃了。

Google不作惡啊，為什麼要對Google那麼狠……

例如我們在Google中搜尋

翻牆

然後就會發現Google被吃了。

怪獸做了什麼？

怪獸首先偽造Google的ip發了許多RST包給鎮民的瀏覽器，然後怪獸也可能偽造鎮民的ip發了很多RST給Google，挑撥離間，最後鎮民和Google在經過一段努力後發現還是無法溝通就不再繼續通信了。

怪獸應該對http包進行了掃描，看看有沒有什麼敏感詞，有的話就偽裝成對方開始卑鄙地發送RST，來挑撥離間最終實現斷開連接。
DNS劫持
有一部分怪獸應該會專門負責污染國內DNS伺服器的緩存，導致我們解析到了錯誤的ip。有一部分怪獸會篡改國外DNS發回的響應，導致鎮民獲得了錯誤的ip。
結言
防民之口，甚於防川。過度地壓制景德鎮的鎮民似乎並不太好，希望未來的祖國會更加開放、更加發達。

天朝威武～