日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。

      一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。

三、 Bloom-Filter的应用。
        Bloom-Filter一般用于在大数据量的集合中判定某元素是否存在。例如邮件服务器中的垃圾邮件过滤器。在搜索引擎领域，Bloom-Filter最常用于网络蜘蛛(Spider)的URL过滤，网络蜘蛛通常有一个 URL列表，保存着将要下载和已经下载的网页的URL，网络蜘蛛下载了一个网页，从网页中提取到新的URL后，需要判断该URL是否已经存在于列表中。此时，Bloom-Filter算法是最好的选择。
      比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。  

     布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。

     假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制位全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制位全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。（见下图）   现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。
      布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万分之一以下。
      布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

       Reactor模式处理网络事件一般按照以下方式进行：

      * 声明对于感兴趣的网络事件的处理接口(event_handler)。

      * 事件多路分发器等待事件发生(select/epoll)。

      * 当有事件触发时，程序调用注册好event_handler去处理对应事件。

      * event_handler调用实际的I/O操作，当有连接到达，则将其加入到I/O events中。

     以下用C++代码简单的描述一下Reactor模式。
    

 1class event_handler 
 2{
 3    public:
 4       virtual void handle_read_event(int fd) = 0;
 5       virtual void handle_write_event(int fd) = 0;
 6};
 7   
 8/*事件多路分发和回调事件处理接口*/
 9class dispatcher
10{
11    public:
12      void event_poll()
13   {
14            while(1)
15         {
16                    select(max_fd,&read_set,&write_set,NULL,NULL);

17                    if event in read_set
18                 {
19                           handler->handle_read_event(event.fd);
20                     }
21                    if event in write_set
22                 {
23                          handler->handle_write_event(event.fd);
24                     }
25              }
26        }
27
28       void set_handler(event_handler *handler)
29    {
30              m_handler = handler;
31       }
32       
33    private:
34       event_handler *m_handler;
35};
36 

       当然我们必须派生event_handler，实现具体的事件处理逻辑，上述的代码才能起作用。

     select系统调用是用来让我们的程序监视多个文件描述符(file descriptor)的状态变化的。程序会停在select这里等待，直到遇到以下情况之一select会退出：

     (1)     监控的句柄至少有一个发生变化，返回值大于1。

     (2)     等待时间已到，返回值等于0。

     (3)     收到信号退出，返回值小于0。

     select操作的内部会在指定的时间内，不断的检测受控集合中的套接字是否可读，可写或有错误，在select返回时只保留发生状态变化的套接字。通过判断select的返回值，就可以了解该调用是否有文件描述符可读或是select调用退出等信息。

     要想让程序运行，光有一个select的调用不是不够的，我们还需要一系列的配套数据结构和算法来帮助将套接字归类，判断是否有指定的套接字等等，结构体fd_set和宏FD_ZERO,FD_CLR,FD_SET,FD_ISSET等就是我们所需要的。通过定义一个fd_set的对象，例如可读集合，有相同需求的套接字都可以放置到这个对象中，可以通过FD_SET这个宏来完成，当然在这之间需要利用FD_ZERO将这个对象初始化。等完成了以上操作后，便会调用select查询是否有套接字可读。等待select完成后，如果有套接字可读，就可以利用FD_ISSET判断是否为监听套接字，转而执行accept操作。如果一个套接字已经关闭，就可以利用FD_CLR将其从fd_set对象中剔除。

    服务器端源代码：
 

  1#include <iostream>
  2#include <sys/socket.h>
  3#include <sys/types.h>
  4#include <arpa/inet.h>
  5#include <sys/select.h>
  6#include <sys/ioctl.h>
  7using namespace std;
  8
  9int main()
 10{
 11
 12   int server_sock = socket(AF_INET,SOCK_STREAM,0);
 13   if(server_sock < 0)
 14   {
 15      cout << "create socket error" << endl;
 16      return -1;
 17   }
 18
 19   struct sockaddr_in server_addr;
 20   memset(&server_addr,0,sizeof(server_addr));
 21   server_addr.sin_family = AF_INET;
 22   server_addr.sin_port = htons(5555);
 23   server_addr.sin_addr.s_addr = htonl(INADDR_ANY);
 24
 25   if(bind(server_sock,(struct sockaddr*)&server_addr,sizeof(server_addr)) < 0)
 26   {
 27      cout << "bind socket error" << endl;
 28      close(server_sock);
 29      return -1;
 30   }
 31
 32   listen(server_sock,10);
 33
 34   fd_set read_set;
 35   fd_set test_set;
 36   FD_ZERO(&read_set);
 37   FD_SET(server_sock,&read_set);
 38
 39   struct timeval tm;
 40   tm.tv_sec = 5;
 41   tm.tv_usec = 500;
 42
 43
 44   while(true)
 45   {
 46       int nread = 0;
 47       test_set = read_set;
 48       int ret = select(FD_SETSIZE,&test_set,NULL,NULL,&tm);
 49
 50       if(ret < 0)
 51       {
 52           cout << "select error" << endl;
 53           close(server_sock);
 54           return -1;
 55       }
 56       else if(ret == 0)
 57       {
 58           //cout << "waitout" << endl;
 59           continue;
 60       }
 61       else
 62       {
 63           for(int fd=0; fd<FD_SETSIZE; ++fd)
 64           {
 65               if(FD_ISSET(fd,&test_set))
 66               {
 67                   //如果有新的连接到达
 68                   if(fd == server_sock)
 69                   {
 70                       int sock = accept(server_sock,NULL,NULL);
 71                       FD_SET(sock,&read_set);
 72                   }
 73                   else
 74                   {
 75                       ioctl(fd,FIONREAD,&nread);
 76
 77                       if(nread == 0) //客户端已经关闭
 78                       {
 79                          close(fd);
 80                          FD_CLR(fd,&read_set);
 81                          cout << "client has removed " << fd << endl;
 82                       }
 83                       else
 84                       {
 85                          char buf[128];
 86                          recv(fd,buf,128,0);
 87                          cout << buf << endl;
 88                          send(fd,buf,strlen(buf)+1,0);
 89                       }
 90                   }
 91
 92               }
 93
 94           }
 95
 96       }
 97
 98   }
 99}
100

      OCOT是one client one thread的简写，从字面上就可以理解，每当有一个客户连接过来，都会有一个线程为其服务，不管这个线程是预先创建的还是临时创建的。当每个客户都有专门的线程为其服务时，就可以解决上述问题。

      利用OCOT为多客户服务时，适应于连接数量有限，而且连接希望是长连接的情况，如果海量的短连接时则不适宜利用OCOT，究其原因无非是频繁的CPU执行权的切换会导致效率底下。

至于如果解决海量短连接的情况，以后再说。下面还是给一个简单的例子，其实应该给一个简单的ftp雏形的，不过为了简单，还是给一个简单点吧！
      服务端源代码：
     

 1 #include <iostream>
 2   #include <sys/socket.h>
 3   #include <sys/types.h>
 4   #include <arpa/inet.h>
 5   #include <pthread.h>
 6   using namespace std;
 7   
 8   void* thread_func(void* arg);
 9   
10  int main()
11  {
12     //create socket
13     int listen_sock = socket(AF_INET,SOCK_STREAM,0);
14     if(listen_sock < 0)
15     {
16        cout << "create socket error" << endl;
17        return -1;
18     }
19  
20     struct sockaddr_in address;
21     address.sin_family = AF_INET;
22     address.sin_port = htons(5656);
23     address.sin_addr.s_addr = htonl(INADDR_ANY);
24  
25     if(bind(listen_sock,(struct sockaddr*)&address,sizeof(address)) < 0)
26     {
27        cout << "bind socket error" << endl;
28        close(listen_sock);
29        return -1;
30     }
31  
32     listen(listen_sock,10);
33  
34     while(true)
35     {
36        void *ret;
37        int sock = accept(listen_sock,NULL,NULL);
38        pthread_t tid;
39        pthread_create(&tid,NULL,thread_func,&sock);
40       // pthread_join(tid,&ret);
41        sleep(1);
42  
43     }
44  
45     close(listen_sock);
46     return 0;
47  }
48  
49  // thread function
50  void* thread_func(void *arg)
51  {
52     int sock = *((int*)arg);
53     cout << pthread_self() <<" send data" << endl;
54     send(sock,"hello world",strlen("hello world")+1,0);
55     close(sock);
56  
57     return (void*)0;
58  }
59