2-websocket协议算法


websocket协议中的一些算法

在分析 WebSocket 协议握手过程和数据帧格式过程中,我们讲到了一些算法,下面我们讲解下具体实现。

Sec-WebSocket-Accept的计算方法

从上面的分析中,我们知道字段的值是通过固定字符串258EAFA5-E914-47DA-95CA-C5AB0DC85B11加上请求中Sec-WebSocket-Key字段的值,然后再对其结果通过 SHA1 哈希算法求出的结果。可以通过以下 golang 代码实现:

var keyGUID = []byte("258EAFA5-E914-47DA-95CA-C5AB0DC85B11")
func computeAcceptKey(challengeKey string) string {
    h := sha1.New()
    h.Write([]byte(challengeKey))
    h.Write(keyGUID)
    return base64.StdEncoding.EncodeToString(h.Sum(nil))
}

掩码处理

浏览器发送给服务器的数据帧是经过掩码处理的,那怎么样对数据进行解码呢?以下是来自RFC6455文档的解释

具体的流程是:将传输的数据按字节 byte 处理,同时将 Masking-key 代表的值也按字节处理。假如 data-byte-i 代表的是数据的第 i 个字节,那么 j = i MOD 4,然后从Maksing-key中(一共有 4 个字节)取出第 j 个字节 mask-key-byte-j,然后将 data-byte-imask-key-byte-j 代表的字节进行异或操作,取得结果就是最终的结果。该操作可以用如下 golang 代码实现:

func maskBytes(key [4]byte,pos int,b[]byte)int{
    for i := range b{
        b[i] ^= key[pos & 3]
        pos++
    }
    return pos & 3
}

注意以上的操作,pos & 3这里代表的操作是pos%4,因为 a % (2 ^ n) 等价于 a & (2^n -1),在这里使用按位与操作更加高效


1-websocket协议分析


WebSocket协议详解

WebSocket 协议解决了浏览器和服务器之间的全双工通信问题。在 WebSocket 出现之前,浏览器如果需要从服务器及时获得更新,则需要不停的对服务器主动发起请求,也就是 Web 中常用的poll技术。这样的操作非常低效,这是因为每发起一次新的 HTTP 请求,就需要单独开启一个新的 TCP 链接,同时 HTTP 协议本身也是一种开销非常大的协议。为了解决这些问题,所以出现了 WebSocket 协议。WebSocket 使得浏览器和服务器之间能通过一个持久的 TCP 链接就能完成数据的双向通信。关于 WebSocket 的 RFC 提案,可以参看RFC6455。

WebSocket 和 HTTP 协议一般情况下都工作在浏览器中,但 WebSocket 是一种完全不同于 HTTP 的协议。尽管,浏览器需要通过 HTTP 协议的GET请求,将 HTTP 协议升级为 WebSocket 协议。升级的过程被称为握手(handshake)。当浏览器和服务器成功握手后,则可以开始根据 WebSocket 定义的通信帧格式开始通信了。像其他各种协议一样,WebSocket 协议的通信帧也分为控制数据帧和普通数据帧,前者用于控制 WebSocket 链接状态,后者用于承载数据。下面我们将一一分析 WebSocket 协议的握手过程以及通信帧格式。

一、websocket握手

握手的过程也就是将HTTP协议升级为WebSocket协议的过程,握手开始首先由浏览器端发送一个GET请求,该请求的HTTP头部信息如下:

        GET /chat HTTP/1.1
        Host: server.example.com
        Upgrade: websocket
        Connection: Upgrade
        Sec-WebSocket-Key: dGhlIHNhbXBsZSBub25jZQ==
        Origin: http://example.com
        Sec-WebSocket-Protcol: chat, superchat
        Sec-WebSocket-Version: 13

当服务器端,成功验证了以上信息后,则会返回一个形如以下的响应:

        HTTP/1.1 101 Switching Protocols
        Upgrade: websocket
        Connection: Upgrade
        Sec-WebSocket-Accept: s3pPLMBiTxaQ9kYGzzhZRbK+xOo=
        Sec-WebSocket-Protocol: chat

可以看到,浏览器发送端HTTP请求中,增加了一些新端字段,其作用如下所示:

  • Upgrade: 规定必需的字段,其值必需为 websocket, 如果不是则握手失败;
  • Connection: 规定必需的字段,值必需为 Upgrade, 如果不是则握手失败;
    Sec-WebSocket-Key: 必需字段,一个随机的字符串;

Sec-WebSocket-Protocol: 可选字段,可以用于标识应用层的协议;
Sec-WebSocket-Version: 必需字段,代表了 WebSocket 协议版本,值必需是 13, 否则握手失败;

返回端响应中,如果握手成功会返回状态码101的HTTP响应,同时其他字段说明如下:

  • Upgrade: 规定必需的字段,其值必需为 websocket, 如果不是则握手失败;
  • Connection: 规定必需的字段,值必需为 Upgrade, 如果不是则握手失败;
  • Sec-WebSocket-Accept: 规定必需的字段,该字段的值是通过固定字符串258EAFA5-E914-47DA-95CA-C5AB0DC85B11加上请求中Sec-WebSocket-Key字段的值,然后再对其结果通过 SHA1 哈希算法求出的结果。
  • Sec-WebSocket-Protocol: 对应于请求中的 Sec-WebSocket-Protocol 字段;

当浏览器和服务端成功握手后,就可以传递数据了,传送数据是按照WebSocket的数据格式生成的

二、WebSocket协议数据帧

数据帧的定义类似与TCP/IP的格式定义,具体看下图:

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-------+-+-------------+-------------------------------+
     |F|R|R|R| opcode|M| Payload len |    Extended payload length    |
     |I|S|S|S|  (4)  |A|     (7)     |             (16/64)           |
     |N|V|V|V|       |S|             |   (if payload len==126/127)   |
     | |1|2|3|       |K|             |                               |
     +-+-+-+-+-------+-+-------------+ - - - - - - - - - - - - - - - +
     |     Extended payload length continued, if payload len == 127  |
     + - - - - - - - - - - - - - - - +-------------------------------+
     |                               |Masking-key, if MASK set to 1  |
     +-------------------------------+-------------------------------+
     | Masking-key (continued)       |          Payload Data         |
     +-------------------------------- - - - - - - - - - - - - - - - +
     :                     Payload Data continued ...                :
     + - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
     |                     Payload Data continued ...                |
     +---------------------------------------------------------------+

以上这张图,一行代表32bit(位),也就是4bytes(字节),总体上包含两份,帧头部和数据内容。每个从WebSocket链接中接受到的数据帧,都要按照以上格式进行解析,这样才能知道该数据帧是用于控制的还是用于传送数据的,关于以上数据帧的各个比特位的解释如下:

  • FIN:1bit,当该比特位值为%x0时,表示后面还有更多的数据帧,%x1时表示这是最后一个数据帧;
  • RSV1,RSV2,RSV3:各占1个比特位。一般情况下全为0,当客户端、服务端协商采用WebSocket扩展时,这三个标识位可以非0,且值当含义由扩展进行定义,如果出现非0当值,且没有采用WebSocket扩展,则链接出错
  • opcode:4 bit,用于表明数据帧当类型,一共可以表示16种帧类型,如下所示:

    • %x0:表示这是一个分片当帧,它属于前面帧当后续帧;
    • %x1:表示该数据帧携带的数据类型是文本类型,且编码utf-8
    • %x2 : 表示携带的是二进制数据;
    • %x3-7 : 保留未使用;
    • %x8 : 表示该帧用于关闭 WebSocket 链接;
    • %x9 : 表示该帧代表了 ping 操作;
    • %xA : 表示该帧代表了 pong 回应;
    • %xB-F : 保留未使用;
  • MASK:1 bit,%x0表示数据帧没有经过掩码计算,而%x1则表示数据帧已经经过掩码计算,得到真正当数据需要解码,一般情况下,只有浏览器发送给服务端当数据帧才需要进行掩码计算;
  • Payload len:7 bit,表示了数据帧携带当数据长度,7 bit 的值根据三种情况,帧的解析有所不同:

    • %x0 - 7D : 也就是从 0 到 125,表示数据长度, 数据总长度也就是 7 bit 代表的长度;
    • %x7E : 7 bit 的值是 126 时,则后续的 2 个字节(16 bit)表示的一个 16 位无符号数,这个数用来表示数据的长度;
    • %x7F : 7 bit 的值是 127 时,则后续的 8 个字节(64 bit)表示的一个 64 位无符号数,这个数用来表示数据的长度;
    • Masking-key: 32 bit, 表示了用于解码的 key,只有当 MASK 比特位的值为 %x1 是,才有该数据;
  • Payload Data: 余下的比特位用于存储具体的数据;

通过以上分析可以看出,WebSocket 协议数据帧的最大头部为 2 + 8 + 4 = 14 bytes 也就是 14 个字节。同时我们要实现 WebSocket 协议,最主要的工作就是实现对数据帧的解析。


c & 多线程归并 & 单线程归并


多线程归并排序 与 单线程归并排序的对比

@测试环境

  • CPU 1核
  • MEM 298M

@测试用例

用python脚本向文件中写入100万整数用于测试

import random
f = open("./data","w")
for i in range(1000000):
    f.write(str(random.randint(1,1000)))
    f.write("\n")
f.close()

@头文件

#include<stdio.h>
#include<pthread.h>
#include<stdlib.h>
#include<string.h>
#include<ctime>
int array_length,file_length;
int *array_master;
FILE *freader;

int read_length(char *fname){
    freader = fopen(fname,"rt");
    char line[80];
    int file_length = 0;

    while(fgets(line,80,freader ) != NULL)
        file_length += 1;
    return file_length;
}

int *read_file(char *fname){
    freader = fopen(fname,"rt");
    int bufsize = file_length;
    char line[80];
    int integer;
    int index = 0;
    int *input = (int *)malloc(bufsize*sizeof(int));
    while(fgets(line,80,freader) != NULL){
        sscanf(line,"%d",&integer);
        input[index] = integer;
        ++index;
        ++array_length;
    }
    fclose(freader);
    return input;
}

@多线程读写文件归并排序源码

#include "file.h"
void merge(int arr[],int left,int middle,int right){
    int i,j,k;
    int half1 = middle - left + 1;
    int half2 = right - middle;
    int first[half1],second[half2];
    for(i = 0; i< half1; i++)
        first[i] = arr[left + i];
    for(j = 0;j< half2;j++)
        second[j] = arr[middle + 1 + j];
    i = 0;
    j = 0;
    k = left;
    while(i < half1 && j < half2)
    {
        if(first[i] <= second[j]){
            arr[k] = first[i];
            ++i;
        }else
        {
            arr[k] = second[j];
            j++;
        }
        k++;
    }
    while(i < half1){
        arr[k] = first[i];
        i++;
        k++;
    }
    while(j < half2){
        arr[k] = second[j];
        j++;
        k++;
    }
}
void* merge_sort(void* arg){
    int *arr = array_master;
    int *argu = (int*)arg;
    int l = argu[0];
    int r = argu[1];
    if(l < r){
        pthread_t tid1;
        pthread_t tid2;

        int arg1[2];
        int arg2[2];

        int middle;
        middle = (l +(r-1))/2;
        arg1[0] = l;
        arg1[1] = middle;
        arg2[0] = middle +1;
        arg2[1] = r;

        pthread_create(&tid1,NULL,merge_sort,arg1);
        pthread_create(&tid2,NULL,merge_sort,arg2);

        pthread_join(tid1,NULL);
        pthread_join(tid2,NULL);

        merge(arr,1,middle,r);
        pthread_exit(0);

    }
    return NULL;
}

int main(int argc,char *argv[]){
    char *fname = argv[1];
    
    clock_t startTime = clock();
    file_length = read_length(fname);

    array_master = read_file(fname);

    int arg[2];
    arg[0] = 0;
    arg[1] = file_length - 1;

    pthread_t tid;
    pthread_create(&tid, NULL ,merge_sort,arg);

    pthread_join(tid,NULL);
    clock_t endTime = clock();
    printf("%f",double(endTime - startTime)/CLOCKS_PER_SEC);
    return 0;
}

编译命令 gcc main.c -lpthread
运行命令 ./a.out ./datadata 为数据文件

@单线程读写文件归并排序源码

#include<iostream>
#include "file.h"

template<typename T>
void __merge(T arr[],int l , int mid , int r)
{
    T aux[r-l +1];
    for(int i = l;i <= r; i++)
        aux[i-l] = arr[i];
    int i = l,j = mid+1;
    for (int k = l ;k <= r;k++)
    {
        if(i > mid){
            arr[k] = aux[j-l];
            j ++;
        }else if(j > r){
            arr[k] = aux[i-l];
            i ++;
        }else if(aux[i-l] < aux[j-l]){
            arr[k] = aux[i-l];
            i++;
        }else{
            arr[k] = aux[j-l];
            j++;
        }
    }
}

template<typename T>
void __mergeSort(T arr[],int l , int r)
{
    if( l >= r )
        return;
    int mid = (l + r)/2;
    __mergeSort(arr,l,mid);
    __mergeSort(arr,mid+1 , r);
    if(arr[mid] > arr[mid+1])
        __merge(arr , l,mid,r);
}
template<typename T>
void mergeSort(T arr[],int n)
{
    __mergeSort(arr , 0 , n-1);
}

int main(int argc,char *argv[])
{
    char *fname = argv[1];
    clock_t startTime = clock();
    file_length = read_length(fname);
    array_master = read_file(fname);
    mergeSort(array_master,file_length);
    clock_t endTime = clock();
    std::cout<<double(endTime -startTime)/CLOCKS_PER_SEC);
    return 0;
}

测试

构造数据 python number.py 数据如下

-rw-rw-r-- 1 xiaodo xiaodo 3.8M Mar 22 16:42 data
-rw-rw-r-- 1 xiaodo xiaodo 762 Mar 22 16:30 file.h
-rw-rw-r-- 1 xiaodo xiaodo 1.8K Mar 22 16:33 merge_sort.c
-rw-rw-r-- 1 xiaodo xiaodo 1.3K Mar 22 16:35 merge_sort.cpp
-rw-rw-r-- 1 xiaodo xiaodo 132 Mar 22 16:41 number.py
可以看到data存入1000万数据后 大小为38M

编译多线程和单线程程序
g++ -o cmerge merge_sort.c -lpthread
g++ -o cppmerge merge_sort.cpp -lpthread

执行与结果对比

./cmerge ./data
Segmentation fault (core dumped)
./cppmerge ./data
0.510115

  • 多线程开销实在太大了 我从100万调到10万还是内存不足
  • 单线程完胜,只有0.5s

epoll_详解


@epoll 详解和记录

创建epoll流程

#define EPOLL_SIZE 5000//这个为告诉内核需要监听的数量是多少,这个只需要大于0 就可以了因为内核会更加实际数量自动扩充,为了兼容linux平台 大于等于0 就可以了
int epfd = epoll_create(EPOLL_SIZE);

struct epoll_event ev;//创建事件
ev.data.fd = fd;//fd 一般为socketfd资源
ev.events = EPOLLIN;//将socketfd绑定为read()操作

epoll_ctl(epfd,EPOLL_CTL_ADD,fd,&ev);//EPOLL_CTL_ADD 为 在epfd中注册指定的fd文件描述符并能把event和fd关联起来

//将文件描述符设置为非阻塞方式(利用fcntl函数)
 fcntl(sockfd, F_SETFL, fcntl(sockfd, F_GETFD, 0)| O_NONBLOCK);
 
 //主循环
 while(1){
     //events   => epoll_event 结构体
    int count = epoll_wait(epfd,events,EPOLL_SIZE,-1);//计算epoll就绪的事件 返回int  总数
    //处理就绪事件
    for(int i = 0 ; i < count ; ++i){
        int fd = events[i].data.fd;
        //fd 如果 等于 socket 返回的  sockfd  则表明是新用户加入 需要recv()其他情况就是已存在用户发发送的消息 调用send就可以了
        if(fd == sockfd){
        //新用户加入 
        recv(sockfd,clientfd
        }
    }
 }

@epoll_event 结构体

typedef union epoll_data {
    void *ptr;
    int fd;
    __uint32_t u32;
    __uint64_t u64;
} epoll_data_t;

struct epoll_event {
    __uint32_t events;      /* Epoll events */
    epoll_data_t data;      /* User data variable */
};

events 宏定义

  • EPOLLIN - 当关联的文件可以执行 read ()操作时。
  • EPOLLOUT - 当关联的文件可以执行 write ()操作时。
  • EPOLLRDHUP - (从 linux 2.6.17 开始)当socket关闭的时候,或者半关闭写段的(当使用边缘触发的时候,这个标识在写一些测试代码去检测关闭的时候特别好用)
  • EPOLLPRI - 当 read ()能够读取紧急数据的时候。
  • EPOLLERR - 当关联的文件发生错误的时候,epoll_wait() 总是会等待这个事件,并不是需要必须设置的标识。
  • EPOLLHUP - 当指定的文件描述符被挂起的时候。epoll_wait() 总是会等待这个事件,并不是需要必须设置的标识。当socket从某一个地方读取数据的时候(管道或者socket),这个事件只是标识出这个已经读取到最后了(EOF)。所有的有效数据已经被读取完毕了,之后任何的读取都会返回0(EOF)。
  • EPOLLET - 设置指定的文件描述符模式为边缘触发,默认的模式是水平触发。
  • EPOLLONESHOT - (从 linux 2.6.17 开始)设置指定文件描述符为单次模式。这意味着,在设置后只会有一次从epoll_wait() 中捕获到事件,之后你必须要重新调用 epoll_ctl() 重新设置。

@epoll_ctl 设置epoll事件

include <sys/epoll.h>

int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

epfd  为 epoll_create 创建的
fd 为 scoketfd
有效的op值有以下几种:
EPOLL_CTL_ADD 在epfd中注册指定的fd文件描述符并能把event和fd关联起来。
EPOLL_CTL_MOD 改变*** fd和evetn***之间的联系。
EPOLL_CTL_DEL 从指定的epfd中删除fd文件描述符。在这种模式中event是被忽略的,并且为可以等于NULL。

@epoll_wait 唤起事件

函数返回唤起的事件数量

epoll_wait(epfd,events,EPOLL_SIZE,-1)
return count;


位运算


位运算

字节

1.一个int 占4个字节
2.一个char 占1个字节内存
3.一个字节由8个二进制位组成

1字节最大 对应二进制 8个111 => 最大255

运算公式

1.% 取模与 & 转换

  • 取模 和 按位与在 条件为2的平方根的时候可以互相转换
  • 因为使用按位与的效率要高很多

a % (2^n) == a & (2^n -1)

运算符

& 按位与

有0 则 0
0 & 0 = 0;

0 & 1 = 0;
1 & 1 = 1;

unsigned int temp = 38 & 22;
//进行二进制进行按位与
100110 //38
010110 // 22
------------------
000110 => 6
38 & 22 = 6;

| 按位或

有1 则 1

0 | 0 = 0;
0 | 1 = 1;
1 | 1 = 1;

unsigned int temp = 38 | 22;
//进行二进制进行按位或
100110 //38
010110 // 22
---------------
110110 => 54
38 & 22 = 6;

^ 按位异或

相同则0 不同则 1

0 ^ 0 = 0;
0 ^ 1 = 1;
1 ^ 1 = 0;

unsigned int temp = 38 ^ 22;
100110 //38
010110 // 22
---------------
110000 => 48
38 ^ 22 = 48;

~ 取反

对单个数字进行按位取反

unsigned int temp = ~38;
00000000,00000000,00000000,00100110//38
-------------------------------------------------------
1111111,11111111,11111111,11011001;//4294657357 42亿。。。。

<< 左移

将一个数的二进制位左移若干个位
每移动一个 都是乘以2

unsigned int temp = 15 << 1;//30
unsigned int temp = 15 << 2;//60

>> 右移

将一个数的二进制右移若干个位
每右移一位都相当于除以2
unsigned int temp = 15 >> 1;//7
unsigned int temp = 15 >> 2;//3
1111 15

||
v

/0111 7

位运算符结合使用

&= |= >>= <<= ^=

a &= b ===> a = a&b

案列

#define BIT(x)  (1<<(x))
int main(){
    unsigned int task;//有32个位    
    BIT(2) => 1 << 2;    
    
    
    return 0;
}