# 【NO.480】Nginx数据结构

就是nginx源码里面该怎么去看里面有哪些东西？

核心的第一点就是把基础组建这一块，就是把我们在nginx源码里面的一些数据结构，得需要捋一遍。

数据结构这里面包含哪些东西，，就现在凭你自己现在自己，你认为做一款开源的项目，这里面有哪些组件是我们有必要要了解的，

第一个大家可以想象，首先对于字符串的处理字符的处理，这个肯定是有的。
第二个对于内存的处理我们也是需要有的，
我们对于文件的操作也是需要有的，就是对于这索引hash它是需要有的，还有类似于红黑树也是需要有，还有呢比如共享内存也是要有的，链表也是要有的，消息队列也是要有的。
还有呢比如说进程间通信的组件也是要有

可以看到在我们任何1个项目里面，就是在任何1个项目里面，你会发现这些组件它是可以通通拿过来又可以去复用的，
应用到其他的项目里面也是可以的，因为其他项目里面这些组件也会有，你经历过几个项目之后，如果你自己的技术有点追求，这里面有很多标准，但是很多时候你换其他地方读也是ok，因为这做法不同做法就会有些差异，
就是这些小组件，然后对应到我们的项目中间，它就是整个一个一个的轮子

nginx所有的数据结构划分出来，有这么几个部分所组成，



![在这里插入图片描述](https://img-blog.csdnimg.cn/860557320f104605ad5173c370db9d7c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oiR5Lmf6KaB5b2T5piP5ZCb,size_20,color_FFFFFF,t_70,g_se,x_16)



第一个部分是说的基础的数据结构，这里面呢大家可以看到什么叫基础，就对于数据类型这种叫基础，比如int的定义，

然后还有高级点的，比如队列数组红黑树哈希
一些进程间通信的组件，包括共享内存，原子操作，自旋锁然后包括通道，信号，
但是在面试的时候它不仅仅局限于要你会用，而很多的时候会问到里面它是怎么实现的，其他的方法是怎么实现的，
这叫分为4类，还有最后一类就是基础组件式的，内存池，线程池，slab

sizeof(int)这个地方它就会有点小差异，这个差异在哪？

就很容易比如说我们在都是以32位这种心态去写的，这时候他数据不会丢失，请注意这时候这个long型占了8个字节，这8个字节中间它就会有一些空档的区域，有一些空隙的空间，从而造成一些数据我们是没有意义的，造成一些占的空间会浪费，这个时候出于这么一个问题，
所以在这种情况里面有了这么一个定义intptr，这个东西是为了去兼容这个32位和64位这个int

![在这里插入图片描述](https://img-blog.csdnimg.cn/dc8de6d261b94eacb322a7b2fc783e8c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oiR5Lmf6KaB5b2T5piP5ZCb,size_20,color_FFFFFF,t_70,g_se,x_16)



第二个概念就是个string，
这个东西啊我想问一下大家有没有对字符号进行处理过，有没有对字符号进行操作过没有？在做字符串操作的时候，你认为做这个最不爽的一点是？

比如说第一个问题是越界，越界的问题就是因为它不带长度，所以越界，结尾标识符的它也是由于我们不带长度所引起的，还有内存分配，就这两点是非常不爽的问题，
一个就是对内存分配，比如说我们在数据中间进行一些操作的时候，各位你要发现我们在操作之前，我们可能对它先得需要分配一块内存。

第一个对于越界的问题我们可以加长度，这是第一个。
第二个对于内存分配的时候，我们可以这样做，但是这是有一个前提的，你有这个客观条件才可以操作，你每次拿数据的时候，对于字符串操作的时候，
首先我们引入一个内存池，也是我们分配这种数据直接在内存池里面，

就是在满足这两个条件的基础上面，第一个内存先分配，就是这个内存我们已经分配好了，我们不用担心内存越界问题。
第二个至于它使用多长，我们是有一个长度的一个计算的，满足这两点我们可以使用柔性数组，也叫做零长数组，什么意思？我们就可以这么定义，

![在这里插入图片描述](https://img-blog.csdnimg.cn/cc27fb587bd44be49cccefba92cbf499.png)



加了一个零长数组，每一次分配的时候这个 a,我们只是打个标签
这个结构体是4个字节，
4个字节就是我们定义的这个结构体，然后再紧接着这个 a我们这个标识指向的是这个地方，那紧接着它下面开始就可以存储我们字符。

![在这里插入图片描述](https://img-blog.csdnimg.cn/60793923812f40cdb987eb58d9d03aaa.png)



那这个字符有多长呢我们通过len来控制，那是不是发现这个做法是挺好的？
但是它中间它有一个缺陷，我们这个计算是可以的，但是请注意不利于我们的printf（），
适合我们的数据把它存储起来，不能把它打印出来，这个东西在使用的时候它有一个局限性，这是一个版本。
第二个版本，

![在这里插入图片描述](https://img-blog.csdnimg.cn/1de7d920ee824acb8ac1d3ef1d207a08.png)



这个我们用的是一个字符，用的是一个指针指向的位置，
多占了一个指针的长度，这个指针不利于我们去修改这个数据，但我们可以指向另外的空间，
就什么意思？
我们是可以不连续我们也是ok的，我们是可以把这个data任意的指向任意一个地方，就是说我们在使用的时候，我们可以指向下一块内存不连到一起，这个也是ok的，我们可以指向任意的地方，这两者之间的差异

所以这时候，**这个问题为什么nginx这地方不用柔性数组？**

![在这里插入图片描述](https://img-blog.csdnimg.cn/a91b9d9f4b9a45b4b109c6ee1effc5c0.png)



可以看到，比如说看到这个宏，

![在这里插入图片描述](https://img-blog.csdnimg.cn/13984f9ef45141ddb1afe3e7a439144d.png)



这个东西这个做法上面可能在一开始看的时候，不是那么能理解，就举个例子，比如说我们一个函数

![在这里插入图片描述](https://img-blog.csdnimg.cn/9dfd7f22ec104fd0950f843961fcf047.png)



这个操作上面可不可以？
这个当他一返回的时候他是没有用的，在这里跟大家讲了一个前提，首先这里面要么直接传一个常量进去，要么就是直接在内存池中间去分配的一个string，在内存池中间去分配的，也就在堆上分配，然后一起去释放，那两种情况才是ok的，**所以对于一些常用的数据结构，是有自己的一些场景。**

首先第一个点就是这个地方为什么既然它是在内存中间的，**为什么这东西它不能用柔性数组，**之前说过柔性数组用在它的内存是先于分配的，第二的话呢长度是我们可以通过另外的渠道拿到的，它使用时候，它的常量改变就不那么方便。

那接着再给大家讲一个比较复杂的东西叫list。

![在这里插入图片描述](https://img-blog.csdnimg.cn/51c92a11c1064d58bf8df0bd8cf41781.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oiR5Lmf6KaB5b2T5piP5ZCb,size_11,color_FFFFFF,t_70,g_se,x_16)



有这么一个场景，GPS上传，有一针一传，一针一传，一针一次，就会发现这时候很容易耗电，所以就出现一个现象，在终端的时候在设备上的时候就把数据给存起来，可能到5分钟的时候再发一次，或者10分钟的时候再发一次，这个数据先在本地先存n帧，然后存完之后5分钟再全部发一次，中间多一些少一些无所谓，

那我们再来分析一下，就是把n个GPS的数据我们要传到服务端，
这边比如说我们这个 n等于20，一次传20帧，那在这传的时候相当于是一个数组，相当于有20个数据，**问一下在服务端我们去接收这20个数据的时候，我们用什么数据结构比较好？**

就是一个经度一个维度，再加上一个再加上一个n乘以它，这个接收完了之后只要解析这个n我们就知道它有多少帧
那现在这个数组我们用什么数组？
这 N它是一个变化的值，首先这个数组我们是不能够直接去定一个固定的值

我大方我直接定一个1024的数字，然后要他一直存是不是？可以，这个当然没问题，如果他有一次超过1024，我就问一下你这个数字怎么搞？

第一个数组长度固定，因为这个n它是不固定的，
这个数组不合适，

还有一个前提，我们如果有了内存池的前提，对于这个问题我们该怎么做？
这里面它前提是有一个内存池的情况下面，vector这个东西可能我们就不太利于在我们已有的这个内存池的情况再去往里面去分配，也就是这个 vector里面定义是我们很难把它分配到内存池里面。

我们每一帧每一帧数据，这个要给大家引入一个东西，我们可以这样子在一开始的时候我们定一个链表，这个链表有点特殊

跟大家讲的这个场景，我们就比较的适合ngx_list_t。



![在这里插入图片描述](https://img-blog.csdnimg.cn/a14d4777a23240cda012e70488c68822.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oiR5Lmf6KaB5b2T5piP5ZCb,size_20,color_FFFFFF,t_70,g_se,x_16)

![在这里插入图片描述](https://img-blog.csdnimg.cn/2a79e2b0d1a6447799bd2f27f1a0ee5e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oiR5Lmf6KaB5b2T5piP5ZCb,size_16,color_FFFFFF,t_70,g_se,x_16)



第一个就说的这个链表本身
就是它，在紧接着是每个链表里面的节点，请注意这个链表和链表的节点不是一个东西，

它总归一起有两个东西组成，一个就是链表本身，第二个就是每个链表的节点是什么。
还有一个可选的东西，就是中间的内存这节点*elts，指向的内存块是什么地方，

nelts这个值是用来做什么的？
这项就是用来描述这个分配的这个 n里面，这中间比如说这个123456块里面中间有多少个已经被使用。
比如说这里面已经使用了4个，那这个n那就等于4，这就是关于这个结构体的组成。
这个传输的过程这是网络做的，也就是当我们去读出来的这个数据，我们存到哪里，我们如何去把更好的存储

接下再问到一个问题，既然这个里面使用了一个池使用了一个内存池，作用就是防止这些数据会有碎片的出现，那想问他这个问题，那这里面碎片多少，这里还是个碎片。这个池它的作用在哪里？既然它这么多的碎片。

在这里只是图，这个图是这么画的，核心来说还是一个整块，这么多小块其实就是一整块的内存。

![在这里插入图片描述](https://img-blog.csdnimg.cn/8a286d96e7274411b8048f5cde79e099.png)



这还只是一个轮廓，他要提供多少个方法，我们如何去把它用起来，
提供方法，首先第一个就是刚刚的那个结构体的定义，然后还有一些我们需要实现一些函数来操作这些
我们到底要不要改，以及我们到底要不要删，或者我们到底要不要查，或者说我们该怎么去
增加

核心来说就提供了一个方法
我们先来看一下这里面到底需不需要增删改查

首先第一个
我们增加一个节点，或者我们有没有删除一个节点，或者说我们有没有去修改的情况，删除比较麻烦好
第一个增加肯定是要有的，不然怎么添这个节点。
第二个对于这个数据结构，我们有没有必要去删除？

这个删除我们有没有意义，我们可以用整个内存池一起去回收。
它的使用场景就是，每一个连接在连接的时候，我们建立一个内存池，在连接释放的时候，整个内存是销毁，那这个删除有没有必要？
第三个有没有可能修改，有没有可能修改？
以及修改我们该怎么去修改，那还有一个就是查找有没有要查找的可能性

它是不带索引的功能，也就是在这个茫茫的这种n多的这种数据存储进去之后，我们的查找方法只能通过遍历，而且这种查找方法效率极低，它的查找是没有意义的
**只要一个增加就可以了**

对于这个链表操作的方法只有一个就是ngx_list_push,

![在这里插入图片描述](https://img-blog.csdnimg.cn/c5ca5754f3c84e3197b843f1bc558dd3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oiR5Lmf6KaB5b2T5piP5ZCb,size_20,color_FFFFFF,t_70,g_se,x_16)



关于这个push才真的能够领略它设计的整个优势，

```cpp
//gcc -o ngx_list_main ngx_list_main.c -I ./nginx-1.14.2/src/core/ -I ./nginx-1.14.2/objs/  -I ./nginx-1.14.2/src/os/unix/ -I ./pcre-8.41/ -I ./nginx-1.14.2/src/event/ ./nginx-1.14.2/objs/src/core/ngx_list.o ./nginx-1.14.2/objs/src/core/ngx_string.o ./nginx-1.14.2/objs/src/core/ngx_palloc.o ./nginx-1.14.2/objs/src/os/unix/ngx_alloc.o



 



 



#include <stdio.h>



#include <string.h>



#include "ngx_config.h"



#include "ngx_core.h"



#include "ngx_list.h"



#include "ngx_palloc.h"



#include "ngx_string.h"



 



#define N    10



 



volatile ngx_cycle_t *ngx_cycle;



 



void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log,



            ngx_err_t err, const char *fmt, ...)



{



}



 



void print_list(ngx_list_t *l) {



    ngx_list_part_t *p = &(l->part);



    while (p) {



        int i = 0;



        for (i = 0;i < p->nelts;i ++) {



            printf("%s\n", (char*)(((ngx_str_t*)p->elts + i)->data));



        }



        p = p->next;



        printf(" -------------------------- \n");



    }



}



 



int main() {



 



    ngx_pool_t *pool = ngx_create_pool(1024, NULL);



 



    ngx_list_t *l = ngx_list_create(pool, N, sizeof(ngx_str_t));



 



    int i = 0;



    for (i = 0;i < 24;i ++) {



        ngx_str_t *ptr = ngx_list_push(l);//返回是精髓，返回待写的



        



        char *buf = ngx_palloc(pool, 32);



        sprintf(buf, "King %d", i+1);



        ptr->len = strlen(buf);



        ptr->data = buf;



    }



    print_list(l);



}
```

这个 table的东西呢它就4项，它是一个非常非常简单的东西

![在这里插入图片描述](https://img-blog.csdnimg.cn/7c608de5bd274d9b94ba51c5454a1a8d.png)



可以看到第一项哈希,第二项key,第三项value，第四项lowcase_key就是小写的key，这个什么意思？

这个数据结构呢就是单纯的就是为了这个而生的,就是为了去避免这种发小写的这种，比如说我们这小写的也认了，要注意这个哈希是什么意思,把我们这个 key那我们只对它做一个计算，方便我们去找到
哈希是对这个 k做了一个简单的这个哈希值，然后方便我们对于这个数组的位置，方便我们查找就这个意思。

纯内存操作，
那关于文件操作，我们如果对这个文件操作要实现一个组件的话，或者实现一个数据结构的话，我们该怎么做，
第一个我们不需要担心数据的存储，我们不需要去考虑布局在内存中的存储，因为它有内存池，不需要考虑具体数据的程度在内存中的存储，**那我们对这如果已经知道了一块内存的数据，我们如何去把它同步到磁盘中间？**

所以现在考虑一下现在大家考虑一下，我们假设已经有了这一块内存所有的数据我们需要同步到这个磁盘中间去，同步的方法就是write和read，那么现在对于这一块内存的数据，我们怎么把它同步进去，这个要考虑几个原因，考虑几个问题，
第一个一次性能不能写完?第二个就是我们一次性没有写完，下一次在哪个地方开始写这几个问题，
那我们怎么去定义对这个内对这块内存我们做一个结构体来标识，让我们更好的把这个数据同步到磁盘里面，就用一个结构体来表述把它同步进去，
就是头在哪个地方，尾在哪个地方，读到哪个地方

首先第一个它开始的位置，
首先它是有个开始的位置，还有一个结束的位置。文件在不停的增加哪个目录？。
他就是做这个事情，他就是记录我们对数据文件同步的时候用了这个ngx_buf_t，
这里只是对一个文件进行同步，如果我们要对多个文件进行同步，那对多个文件进行统一的操作那怎么做？这个链ngx_chain_t



![在这里插入图片描述](https://img-blog.csdnimg.cn/23291a3927fc4a92b05e7d9be4686f59.png)

![在这里插入图片描述](https://img-blog.csdnimg.cn/f04b21fec4e0415195b5db9d4f201e9e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oiR5Lmf6KaB5b2T5piP5ZCb,size_20,color_FFFFFF,t_70,g_se,x_16)



为什么这里有开始的位置，这里有个结束位置，这里为什么还要那个文件的结束位置，这个是怎么理解？
这些东西关于对于文件操作的几个东西，就是我们对于文件定位的时候，就是我们从哪个地方，这首先前面6项，
就是我们在同步的文件里面就记录了这个所有的位置，
后面它不是核心，只是为了去辅助我们数据更好做。

我们在读的时候或者我们再往里面写的时候，在里面写的时候，首先这个buff从哪个地方开始到哪个地方结束，写到文件的哪个位置，再到文件的哪个位置，
u_char这里面的数据我们可以拿出来的，

不像是我们刚刚讲的那个例子，
历史里面它是指向的是有具体的某个类型值的，但是请注意这个buff它分配完了之后，它也是在那些池里面，我们没办法知道从buff里面是哪个内存池，但是我们可以从内存池里面
去分配
list可以知道这是分配在哪一个内存池的

这一项start是从buff里面哪个地方开始到哪个地方结束，然后写到这个文件在哪个定位开始到哪个地方结束，然后写进去的时候之前这个内容是什么，到了结尾这个内容是什么？
这个返回能够返回回来，就是这么6个字**对于这个 buff操作时候我们需要引几个函数？**其实核心的是这两个读和写

所有的业务需求是基于这个基础组建做的，它也是基于这些技术组建做的，全部都是基于这些技术组件在上面做的，

进程间通信最好的一个方法可以采用共享内存。
那共享内存的做法，关于函数接口上面有这么两种做法，
一个是采用的mmap
第二个就采用shmat，这两个都是可取的，而这两个的思路在实现的时候又是很相近的，各位朋友你去打开那个进程，虚拟内存它的共享图的时候，那个内存的Top图的时候，你要发现现在中间它多一项叫做mmap项，这个当我们使用共享内存的时候，这个内存多个进程之间共享的内存地址就是说的mmap这个段



![在这里插入图片描述](https://img-blog.csdnimg.cn/55a88a9c3d414205a5d19ded9aa526ba.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oiR5Lmf6KaB5b2T5piP5ZCb,size_9,color_FFFFFF,t_70,g_se,x_16)



总共一起提供出来三个方法，这三个方法大家可以看到可以看到
这三个这三个中间到底是采用宏地分隔出来的，他到底是选择哪个？



![在这里插入图片描述](https://img-blog.csdnimg.cn/e2f4501e00bb49368124ca1c4ed3dd9a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oiR5Lmf6KaB5b2T5piP5ZCb,size_20,color_FFFFFF,t_70,g_se,x_16)



关于共享内存本身来说，第一个就是分配，第二个就是释放

 原文作者：[[我也要当昏君](https://blog.csdn.net/qq_46118239)

原文链接：https://bbs.csdn.net/topics/605194135