# mycache
**Repository Path**: zzl_60/mycache
## Basic Information
- **Project Name**: mycache
- **Description**: my cache server
- **Primary Language**: Unknown
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 0
- **Forks**: 1
- **Created**: 2023-07-17
- **Last Updated**: 2023-07-17
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
# mycache设计原理
## 申明
该项目借鉴和参考了apache trafficserver、nginx和openresty相关源代码, 并在此基础上进行改进完善。固默认继承了nginx和openresty相关开源许可协议, 如有疑问请与我进行联系。
> Author: 张强
> Mail: 13260255349@163.com
> Referce:
> - https://github.com/nginx/nginx
> - https://github.com/apache/trafficserver
> - https://github.com/openresty/lua-nginx-module
## 背景
在往期工作中，大量使用了nginx和apache trafficserver相关开源软件，随着时间推移这些软件越来越难以支撑公司业务的发展，而且像nginx和trafficserver, 它们本身的设计会对我们的研发产生一定的局限性，只能使用一些奇怪的方式实现所需的功能，固在此基础上编写了mycache。
mycache集反向代理和代理缓存功能于一身，它的设计目的如下:
- 支持域名级别的配置能力, 并支持动态配置。该能力trafficserver本身并不具备, 需要额外定制。nginx则缺乏动态配置能力(nginx reload不适合配置频繁变更的场景)。
- 大规模缓存能力。nginx对缓存相关控制协议支持不足, 需要额外定制，同时nginx自身的缓存引擎是基于文件系统设计, 性能、淘汰机制、磁盘利用率等都不能达到最大化。并且nginx和trafficserver都不具备三级缓存能力。mycache直接对接裸盘、使用异步IO并支持三级缓存功能，同时提供完善的磁盘故障处理逻辑。
- 易于扩展的回源管控能力。nginx的upstream功能虽然强大，但是本身限制也比较多，比如我们想在重试阶段修改请求头、http回源失败后走https回源等，以及多源站分流、follow302等等。特别是nginx对域名方式回源本身的管控能力较弱, 如重试、故障IP屏蔽等。
## 整体概览:
- common: 存放一些基础库函数, 主要包括各类数据结构、内存池、hash算法、原子锁、读写锁、时间库函数等。
- config: 用于存放mycache系统配置和域名配置等。
- event: 用于实现事件系统和网络系统, 以及tcp listen和 tcp connect等操作。
- cache: 缓存功能实现, 包括内存缓存、ssd cache、hdd cache，以及对应的IO操作接口。
- dns: 用于实现DNS解析和DNS Cache等功能。
- http: http server和http client相关实现。
- service: 反向代理 + 代理缓存相关功能实现。
## common:
**my_queue**
> my_queue是一个双向链表, 该结构是mycache最基础的数据结构之一, 它拷贝自nginx, 并在此基础上进行一个一些扩充。
**my_rbtree**
> my_rbtree是一颗红黑树, 同样也是mycache最基础的数据结构之一, 它拷贝自nginx, 并在此基础上进行了更高层次的抽象, 通过侵入式结构实现了类似泛型集合的特性。原理及使用方式如下:
> 在mycache中大量使用了该编程技巧, 理解该编程技巧有助于编写易用复用的数据结构。
**my_str**
> my_str是mycache中对字符串的抽象, 它参考自nginx, 在一些buff解析过程中大量使用该结构(此场景下字符串没有\0字符)，同时它也被用于优化字符串的各类操作, 使用该结构可以很好的避免**strlen**开销。
> 同时参考ngx_snprintf, 实现了my_snprintf, 可以通过fmt的方式打印my_str, 支持大部分的格式化操作语义。
**my_mem**
> my_mem是mycache中的内存池, 它本质上是由多个freelist组成, 基于该结构实现了全局内存池和线程本地内存池。
> 在mycache代码编写中, 通常使用my_thread_malloc/calloc/free, 而不使用此处提供的各类操作接口。
> 另外该函数支持aligned_malloc等相关操作。
> 在my_thread_malloc中实现了各类场景的检测, 固用户通常情况下无需关心这一层， 详细内容见my_thread_base结构。
**my_spinlock & my_rwlock**
> my_spinlock和my_rwlock是mycache中普遍使用的一种多线程同步手段, 在一些简单的并发场景中, 我们通常使用spinlock和rwlock来实现并发安全, 比如在某些容器中添加、查找或删除元素这类在几条或十几条cpu指令即可完成的场景中, 这可以保证高性能的同时降低异步编程的复杂度。
> my_rwlock被设计为写操作为第一优先级, 具体实现可参考源代码, 该方式使得my_rwlock更具有普适性。
**my_crc & my_fnv_hash**
> my_crc和my_fnv_hash是mycache提供的hash函数, 可以将一个字符串转换为各种类型的整形值。
**my_inet**
> my_inet实现了ipv4/ipv6/unix socket addr + port字符串的解析。
> 使用该接口可降低程序对各类sockaddr操作的复杂度, 并且使用该库可将sockaddr转换为对应的sockaddr txt。
**my_pool**
> my_pool同样参考ngx_pool实现, 该结构包含了小块内存申请、大块内存申请、注册cleanup函数等操作。
> 小块内存申请: 在开始创建一个4K大小的buff, 小内存申请只是简单的移动它的pos的指针完成划分, 释放时什么也不做。
> 大块内存申请: 大块内存申请使用rbtree对地址进行管理, 对每个大块内存进行追踪。
> 在pool销毁时, 先执行所有的cleanup函数, 根据大块内存分配表释放大块内存, 最后释放申请的各类page_buf。
> 合理使用该结构可降低复杂场景下内存管理的复杂度。
**my_syscall**
> my_syscall用于同一系统调用的返回值和错误码的获取, 简化系统调用api的复杂性, 杜绝错误使用的风险。
**my_buf**
> my_buf包含了**my_buf_data**、**my_buf**和**my_buf_chain**。
> my_buf_data负责管理最底层的数据缓存区。
> my_buf管理对应buf_data中的可读数据区和可写数据区，同时my_buf可能指向同一个my_buf_data, 不同my_buf可以维护自己的数据消费情况。
> my_buf_chain本质上是一个简单的queue, 管理多个my_buf, 用于实现数据的流式管理, 它本身是一个写者一个读者的结构, 一写多读场景可以基于该结构进行实现。
> 其中my_buf_data和my_buf均维护着各自的引用计数, 当引用计数为0时对应的结构将被释放。
> my_buf相关结构设概览:
> my_buf_chain使用指南:
> - my_buf_chain此处是一个单向queue, 使用enqueue将buf追加到chain尾部, 使用dequeue返回chain头部的第一个buf。enqueue会导致该buf的refer+1, 而dequeue并不会修改buf的refer值, 用户在使用完毕后必须显示调用buf_free释放该buf。(如果dequeue对refer-1可能导致buf被直接释放)。
> - my_buf_chain_first: 返回buf chain中第一个buf, 这通常是第一个可读buf。配合my_buf_chain_next可顺序遍历该chain中所有的可读buf。用户可以通过遍历的方式消费数据并记录消费的数据量，使用my_buf_consume将消费情况同步到my_buf_chain上，这可避免buf_chain结构被破坏。(dequeue会将buf从chain中摘下, 如果数据没有消费完毕，也无法重新挂载到buf_chain上)。
> - my_buf_chain_last: 返回最后一个buf, 这通常是最后一个可写的buf。将数据写入该buf后只需简单的移动该buf的end指针即可。
> - my_buf_chain_copy/copy_n: 对buf chain中的数据进行拷贝, 新buf chain除了复用底层的my_buf外，其他的所有结构都是新创建的。配和consume接口可实现一写多读缓冲区。
**my_thread_base**
> my_thread_base是mycache中最重要的结构之一, 很多操作都依赖该结构实现, 它包含了各种缓存数据和 thread local stroage table。
> 在创建线程后, 我们就立即为当前线程绑定该对象, 相关api对该结构进行了隐藏, 配置mycache的事件模型, 绝大多数情况下, 用户感觉是在编写单线程程序, 极大的降低了多线程程序的复杂度。
> 如my_thread_malloc/free, 它内部会先通过thread_getspecific获取thread_base, 根据不同场景来进行进行内存申请释放, 用户无需关注各类内存池结构。
> 如cache_time, cache_http_time, cache_error_time等, 在生成access log、error log时, 可以直接使用缓存的时间, 无需每次都将一个cache_time转换为对应的数据格式。
> my_thread_base提供了线程本地存储的能力, 后续的http client session pool, http server session pool都是在此基础上进行构建。
**others**
> my_chash
> my_hrtime
> my_cleanup
> my_random
> my_log
> my_slru
## event
mycache中有三种类型的任务, 分别为 my_event、my_conn 和 my_dispatch_event。
***my_event***用于描述定时任务和就绪任务，同时它也是my_conn_t的子结构。
***my_conn***用于描述一个IO任务, 它包含两个event, 分别为read和write, 读写事件回调和触发都基于event来实现。
***my_dispatch_event***用于描述一个跨线程的任务, 它记录了任务的发起方和任务的执行方, 所有的跨线程任务处理都是请求-响应模式。
### my_event_loop & my_worker
my_event_loop实现了跨线程任务、定时任务、就绪任务、网络任务的处理。而my_worker只是简单的使用round robin的方式将任务投放到不同的event loop中。它的处理流程如下:
- 其中external_queue是一个受spinlock保护的队列, 每个event loop维护自己的external_queue并在每一次循环都一次性将所有事件转移到自己的local queue中 (仅指针的修改), 可以极大的降低该splinlock的竞争。
- local_queue: 任务从external_queue转移到local_queue后, 无需上锁即可进行处理。 该队列可复用ready_queue, 目前local_queue和ready_queue是分离的。
- timer_task: 使用红黑树实现的定时任务队列, 基于exec_time进行排序。
- ready_queue: 处理就绪任务, 应为在定时任务中可能使某些任务恢复执行, 或添加立即被执行的任务。
- epoll_wait: 监听notify conn和net conn的读写事件, 并将对应的read event和write event投放到ready queue。
- ready_queue: 再次处理read_queue, 这里为epoll事件触发后添加的读写任务。
**my_event_loop事件处理接口**
my_event_loop_add/del_timer: 添加/删除定时任务。
my_event_loop_remove_conn: 该接口用于一次性移除当前连接上的所有任务(读写任务和定时任务)。 举个例子, 比如一个连接读写任务同时就绪, 他们全部放入了ready queue中。如果在读事件回调中该链接对应的上层状态机被销毁, 此时写事件回调程序将出现段错误。而该接口方便用户一次性对所有注册事件完成清理。
my_event_loop_start/stop/enabled/disabled_io: 开启/关闭/启用(读|写)/禁用(读|写)网络IO。
- mycache通过上述结构在更高层次抽象了ET模式和LT模式, 业务层无需关注底层poller使用的是ET还是LT模式。
- start_io在连接建立后调用, stop_io在连接释放前调用。在ET模式中, 此时会立即监听连接的读写事件, 在LT模式中什么也不做(stop_io阶段会移除未取消的任务)。使用ET模式可以避免频繁的进行系统调用(epoll_ctl modify)，提高系统性能。
- enabled/disabled_io (read/write), 并且仅在start_io操作后才可调用。它们会将对应事件设置为active, 如果一个事件处于deactive, 即使它处于ready状态(读写事件触发), 仍然不会回调上层状态机。
- enabled/disabled_io (read/write) 接口是幂等性的, 当上层状态机想要读取数据时必须显示调用enabled接口（即使任务可能处于就绪状态，这是为了简化事件通知机制而设计的，用户只需要关心是否要读写数据，要则调用enabled_io, 否则调用disabled_io）, 不想要读取数据时调用disabled接口。如果任务已经处于就绪状态, 调用enabled接口可能会导致任务被同步回调, 也可能将任务投放到就绪任务队列进行异步回调。而调用disabled接口后, 即使任务处理ready状态, 它也绝对不会回调。
- enabled/disabled_io在更高层次抽象了数据驱动模型, mycache的所有数据流相关的处理中都是用了该语义，它由底层事件系统进行驱动(事件是否就绪), 由上层状态机负责调控(继续还是取消)。它方便用户更好的控制状态机的运行和挂起。
**mycache中的跨线程设计**
mycache为了简化多线程编程模型的复杂度, 通常情况是不会跨线程的。 如http请求的处理、响应、回源的，他的处理都在所属线程中完成, 包括相关的数据结构如http server session pool和http client session pool都是线程本地对象。但是在某些全局数据共享的场景下, 必须进行跨线程操作，此时跨线程操作有两种方式。
- 请求-响应模式: 将一个跨线程任务封装成一个请求, 投放到对应的线程中, 处理完毕后再通过dispatch_event记录的setup_thread投递回来。
- 类似于合并回源场景, 由第一个发起者进行处理（该任务被称之为master task）, 其他任务只是将自己的dispatch_event注册到全局的pending列表 (这些任务被称之为slave task)。当master task拿到结果后, 遍历pending列表, 将这些disaptch_event再投放到所属外部任务队列中, 等待事件系统重新驱动。
- 其余一些简单的多线程并发场景使用spinlock和rwlock即可。
### my_tcp
my_tcp包含my_tcp_accepter和my_tcp_connect。其中my_tcp_acceper由单独的线程池进行非阻塞的accept, 并将结果投递到不同的worker event loop中。而my_tcp_connect只能在worker event loop中发起。
my_tcp_acceper线程池并发的进行非阻塞accept操作, 不同epoll_wait监听相同的sockfd默认情况下存在惊群问题, mycache本身不解决惊群问题, 而是对该问题进行隔离。比如mycache创建2个非阻塞的event loop处理accpet任务, 惊群现象只存在于这两个线程中, 不会对其他线程产生影响, 自然也不会带来更大的性能损耗。设计如下:
my_tcp_connect用于在worker event loop中异步的发起tcp连接, 本身实现了connect超时控制。设计如下:
## my_http
不论是http server request, 还是http client request，它本身都包含一个http request和http response结构，区别是http server request接收客户端请求并做出响应，而http client request是向服务端发起请求并接收响应。
### my_http与upperSM交互流程:
以下使用http server request举例, http client request流程大同小异。一个http请求的处理阶段分为: 读取请求头、读取请求体、发送响应头、发送响应体。其中读取请求和发送响应可能是异步的。
- case1: http server读取到一个请求的请求头后立即做出403响应，此时request body可能并未读取。
- case2: web scoket协议中, 当连接建立后, 请求侧和响应侧将以tcp全双工的方式进行交互。
固my_http将http request和http response设计为独立的执行流程，在对应的独立执行流程中执行my_http_abort_request和my_http_finalize_request都会导致该http request和response上的异步任务被取消。其中abort会导致该请求被terminal, 之后应该立即销毁my_http_request, 而finalize_request会等待http请求和响应处理完毕, 根据情况分离my_conn之后再回调上层状态机finalize_done, 此时才可销毁my_http_request。
http_server_request与upperSM交互流程:
http_client_request与upperSM交互流程:
### my_http请求响应头解析和处理:
http请求响应头在不同的http协议版本中有一定的区别, 我们这里仅描述HTTP/1.1的请求头和响应头的解析流程。
http请求头由一个请求行(request line) 及 一系列的 request header line以及最终的空行 (\r\n)组成。http响应头由一个响应行(request line)以及一系列的response header line以及最终的空行(\r\n)组成。可见对于请求头和响应头的解析流程是对于行数据的解析。
my_http中实现了my_http_readline_sm结构用来异步事件回调中读取一整行数据，readline_sm限定一行数据不超过4K, 否则将解析失败。my_http_readline不支持跨buf数据解析, 如果当前buf中没有足够空间存放整行数据时，需要切换新的buf, 并将readline_sm中解析了部分的数据拷贝到新的buf中，并重置readline_sm，重新开始行数据解析。
其余内容只是简单的对字符串进行解析，这里就不再过多涉及。
### my_http请求响应头封包发送流程:
在发送http请求或响应时, 需事先将相关的内容设置到request或resonse结构上。 在开始调用start_send_request/response_header时，开始构建请求或响应头, 并将它保存到header_chain中，后续发送完毕后，即回调上层状态机SUCCESS事件。
### my_http中的数据流转流程:
my_http_request_t和my_http_response_t结构中均包含了如下结构, 这些结构相互配置即可实现body数据的读取。
- body_chain: 保存待upperSM读取的数据。
- body_buf: 保存从底层连接中读取到的数据。
- last_buf: last_buf只是对body_buf的一个引用, 它是body_buf的shandow。
- output_chain: 保存待发送的数据。
请求体读取和响应体读取流程:
- 在初始化阶段先将last_buf->pos指向body_buf->pos请求体开始的位置(body_buf可能携带了非body数据的内容, 后续对数据进行加工时会重新调整last_buf->pos指针)。
- 当读事件触发后, 数据会先读取到body_buf, 在body_buf中的数据是未加工的，如果body_buf中的数据已经读取完毕、EAGAIN或者遇到异常, 都立即对body_buf中的数据进行处理。
- body_buf中的数据可能夹杂了一些非body数据，此时我们需要跳过该部分数据, 将last_buf->pos指向实际数据开始的部分, 接下来移动body_buf->pos指针直到当前buf中有效的body数据被消费完毕，此时last_buf->pos到body_buf->pos中的数据即为当前buf中有效的body数据，接下来为其创建一个新的my_buf_t结构, 并将它append到body_chain中。
- 如果body_buf中已无可写的空间, 则创建新的buf结构 (释放老的), 并将last_buf->pos指向body_buf->pos, 然后继续上述数据的读取。
- 需要注意的是: 如果body_chain中的数据量达到限定的大小, my_http将停止数据读取, 上层状态机在消费完数据后必须调用enabled_read_request/response_body重新数据读取任务。因此我们统一约定，如果上层状态机想要继续读取数据，不论my_http中的数据读取任务是否暂停，都必须主动调用调用enabled_read_request/response_body接口。如果当前不再想读取数据，则调用disabled_read_request/response_body接口即可暂停数据读取任务。
- 通常情况下my_http将通知上层状态机 MY_AGAIN/MY_BUSY/MY_SUCCESS/MY_EOS/MY_TIMEOUT/Othet Errors。如果请求体或响应体全部被读取完毕，则回调上层状态机MY_SUCCESS。上层状态机可能收到MY_AGAIN和MY_BUSY事件，这两种事件都代表当前body_chain中有数据可读。
- 当read系统调用遇到EAGAIN时，如果body_chain中有数据, 则通知上层状态机MY_AGAIN (此时有数据可读)。 否则等待读事件触发。
- 当body_buf没有空间可写 (body_chain中未读取的数据达到上限), 则取消读事件回调，不通知上层状态机MY_BUSY，此时上层状态机应尽快消费数据。
请求体和响应体发送流程:
- 当上层状态机需要发送数据时, 只需要简单的将携带了body数据的buf追加到body_chain中。
- 接下来my_http将开始数据发送流程， 首先将body_chain中的数据进行加工，并搬移到output_chain中。
- 接下来将output_chain中的数据发送到网络中。
- 发送流程中没有disabled接口, 这是因为数据写入body_chain就是需要发送的，如果body_chain已经空了，那么数据发送任务将处于暂停状态，等待填充数据重新恢复执行。
- 同样上层状态机可能收到MY_AGAIN事件, 表示有数据已经发送完毕(至少是部分数据)。通常情况下上层状态机不会收到MY_BUSY事件，这是因为底层的write操作遇到了EAGAIN并且未发送任何数据(在本次驱动中), 此时my_http不会通知上层状态机，而是等待写事件就绪后继续发送数据。
请求体读取流程:
响应体发送流程:
请求体发送流程:
响应体读取流程:
补充:
- 在chunked传输场景中，上层状态机将最后的body数据添加到对应的body_chain后，必须调用与之对应的set_last_body_flag，这是因为在chunked传输场景中，body数据发送完毕后，需要主动发送一个empty chunk。my_http本身不知道body何时结束，固需要上层状态机主动告知。此时my_http将body_chain中的数据搬移到output后，会append一个empty chunk, 代表当前的body体已经结束。 否则my_http将认为body数据被截断。
- http pipeline: 某些客户端可能在一根TCP连接通道中连续发起多个http请求，等待服务端顺序处理。 而服务端在读取request header时，可能读取了下个request的相关数据。针对该情况，在当前请求处理完毕后应该分离多读取的数据到下个http request, 以保证http pipline request中的数据完整性。
- lingering close: 在http server request处理中，可能出现请求体未读取完毕就立即做出异常响应，并断开连接的情况。此时如果内核读缓冲区中有数据，在调用close操作时，server端将直接发送RST报文, 并丢弃内核写缓冲区中待发送的数据，客户端很可能出现收取不到body的情况。 而lingering close会等待一段时间，保证客户端收取到异常响应后再执行close操作，合理的配置lingering close可以提供http server的友好性。
## cache:
关于cache设计的一些想法:
- :white_check_mark: cache支持三级缓存, 分别为MemCache, FastCache和SlowCache, 并且保证多级缓存数据的一致性。
- :white_check_mark: cache层支持大文件流式写入, 底层使用块的方式存储, 并且保证大文件的完整性。
- :white_check_mark: 支持大文件流式读写, 支持chunked响应写入。
- :white_check_mark: http cache多副本支持。
- :white_check_mark: 读盘请求合并。
- :white_check_mark: SlowCache支持二级索引, 大幅度降低索引表的内存开销。
- :white_check_mark: 缓存降级, 在FastCache层快速淘汰冷资源, 降低SlowCache写压力。
- :white_check_mark: 支持SlowCache中的资源在 一段时间内访问频次达到n次才提升到FastCache, 减少不必要的热点提升。
- :white_check_mark: 支持小文件只写FastCache, 不写SlowCache, 提升小文件访问质量, 降低小文件占用的索引容量。
- :white_check_mark: 支持对某些资源做pinner, 比如视频的头片, 提升服务质量 (降低首包延迟)。
### 设计和接口概览:
- 修改put接口, 支持pinner操作, 用于实现针对某些资源做pinner。
- 被pinner的资源是总量有上限阈值, 使用SLRU的方式管理pinner记录 (注意: 这里并不删除缓存)。避免缓存引擎中全是pinner资源而最终只能被迫崩溃。
- 修改put接口, 支持downgrade flag等。
### 多级缓存及缓存一致性
多级缓存支持热点提升、热点降级和Only-FastCache三种策略，这三种策略可彼此协作运行，共同为不同类型的资源提供更优的访问体验。
**关于热点提升**
热点提升是将缓存资源从低速存储介质提升到高速存储介质以加速高频数据的查找效率，同时降低低速存储介质的IO压力。
- 分别是从SlowCache提升到FastCache 和 Slow/FastCache提升到MemCache。
- 从SlowCache和FastCache提升到MemCache只是简单的对slru做一次put操作。而SlowCache到FastCache涉及到磁盘IO, 因此需要使用异步模型。
- 支持SlowCache中的资源达到一定热度后才提升到FastCache, 减少不必要的热点提升, 减少FastCache压力。
- 理想中的命中率模型为: MemCache: > 50%, FastCache: > 20%, SlowCache: < 10%。
- 多级缓存的一致性: 在缓存读写过程中，基于CacheKey进行读写合并, 多个写者处于排队状态。缓存删除和修改之前先清理MemCache和FastCache，并$\color{#F44336}{取消}$热点提升和降级流程中对应的异步任务。
- 在某些极端场景仍然存在缓存不一致性的现象，比如删除FastCache中的资源但未落盘, 此时服务终止。 该问题在缓存场景中可以通过回源补片的方式保证数据的一致性，如果需要实现严格一致，可能需要引入日志重放机制进行保证。
**关于热点降级**
热点降级一般应用在如下的场景中:
- 冷资源占比较多，比如像腾讯视频，热播剧在总的资源体系中占比是非常少的，99%的资源为冷资源。又比如App中的个人头像, App中自带缓存。
- 短时间内热点集中，比如像很多电商活动期间推广的商品图片，过了这段时间后基本无人问津。
据我工作中统计，一个缓存对象落在一个8T的盘写满一圈的周期内(可看做是一周), 访问次数 < 2次的资源占总资源数的40% ~ 60%), 将此类资源直接写入FastCache, 可实现快速的淘汰, 避免冷资源挤占SlowCache的存储空间, 同时也可降低SlowCache本身的读写压力(据估算, 实际SlowCache写压力可减少40%+）。而针对域名级别的统计分析则可取得更优的结果。
何种资源需要降级? 如果保存待降级的记录？
- FastCache中的数据有两种, 一种是直接写入FastCache中的数据, 另一种是从SlowCache中提升到FastCache的数据，我们需要对第一种资源进行降级。
- 在索引中使用一个bit位来标识该资源是需要降级的数据。 (该bit位占用另一个字段的第一个bit, 无需额外的内存开销)
关于命中率的题外话:
很对同学会问, 热点降级会将冷资源给快速淘汰掉，那么在商业CDN中如何保证冷资源的命中率？
- 缓存的命中率需要多重手段保证，上述热点降级只是从单机成本、性能出发考虑的，合理使用该策略可以提高单机的整体命中率，并降低SlowCache的负载，比如SlowCache采用了HDD, 使用这些手段可以让存储引擎整体的吞吐量提升近一倍。但是该方案会使得冷资源的命中率变的更低。
- 传统的商业CDN一般设计为两层或三层，同时又存在覆盖域(使用多少个缓存节点覆盖该区域)的概念。资源命中率包含了各Level的总命中率, 冷资源需要的是大存储容量，同时减少冷资源的副本数目(减少全网冷资源的重复数)。
- 对于L1来说，可以让冷资源仅访问该覆盖域内的部分缓存节点 (比如山西有5个缓存节点, 默认情况同一资源会缓存5份, 基于round-robin。 设定冷资源域名仅在其中的2个缓存节点上调度, 那么在该地区同一资源只缓存了2份, 提升了该部分节点的缓存命中率)。
- 对于L1来说，可以将该覆盖域内的所有Cache节点组建成一个哈希环，使用内容302的方式将冷资源调度到对应的缓存节点。
- 对于L1来说, 还可以将极冷资源直接302到L2节点，让请求直接访问L2, 从而降低冷资源对L1的压力，避免大量的冷资源冲掉L1上的热资源。
- 对于L2来说, 通常会基于不同区域组件哈希环，并配备大量的HDD硬盘来构建大容量节点, 从而保证足够的存储容量。
- 写在最后: 不管是热点缓存还是缓存准入机制, 都是基于使用场景来区分的。比如在L1上开启热点降级在提升存储引擎性能、命中率和服务质量的基础上，通过引入廉价的存储介质(HDD)来减少各类成本。而在L2上则无需开启热点降级功能。
热点降级设计方案:
### 关键资源pinner操作
外部客户通常使用 首包延迟、首屏耗时、百毫秒卡顿率等各种指标来衡量CDN的服务质量。PK资源测试场景中，使用pinner钉住某些关键, 可避免它被淘汰，从而提升命中率并降低首包延迟。在视频场景中，我们可以对首片进行pinner, 降低首屏延迟。
pinner操作采用的是磁盘空间回收时的recycle-reinsert操作，如果pinner资源过多，那么回收压力将会暴增。如果缓存引擎中的所有资源都是pinner资源, 那么回收程序将变成死循环。为避免该问题出现, pinner采用一张额外的表进行记录, 使用slru的方式管理，并且pinner的容量不得超过当前volume容量的1/20（这是一个内置到系统中的最大限制）。
pinner设计方案:
### 硬盘异常检测及剔除机制
硬盘的可靠稳定在缓存系统中是至关重要的，硬盘出故障轻者影响服务质量，重则导致程序内部任务堆积最终服务崩溃。常见的硬盘异常如下:
- 坏盘/坏块
- 慢盘, 比如相同介质的硬盘，大部分吞吐量在80MB/s, 而某些盘只能跑到20MB/s，导致访问该盘的请求都出现阻塞。
- 硬盘Hang死，或者周期性Hang死。比如在在不停止服务的情况下，动态升级SSD固件程序，或者SSD固件程序Bug等，导致请求Hang住很长时间。
针对坏盘一般在初始化阶段即可发现, 而坏块一般在读写对应着读写出错, 我们可以配置读写出错阈值, 在n秒内达到m次即可剔除该盘，同时也可按情况对坏块进行屏蔽，坏块数达到一定程度后再剔除该盘。 这两种剔除机制可彼此结合共同保障服务质量。
慢盘情况需要通过对任务进行排队，设置合理的队列，当发生请求溢出时说明当前的盘的消费能力不足，此时按情况来判断是否对盘进行剔除。如果是服务压力超出盘的性能, 则不可以剔除，否则将加重其他盘的压力，最终导致服务崩溃。 因此此处需要结合当前盘的读写速率进行区分。针对慢速盘的问题，当请求发生溢出后，检测是否需要踢盘，如果需要剔除，则在剔除后访问其他的磁盘。否则将直接走合并回源途径。
针对硬盘Hang问题，我们会记录每个正在处理的请求添加一个定时器，如果在一定时间内发生超时，则上报超时事件。
### SlowCache索引压缩
SlowCache二级索引功能只是作为一个可选功能开放，通常用于特大容量且内容容量与之不匹配的场景中。
SlowCache一般会采用较多数量且大容量，廉价且低速的HDD。比如16 * 16T或者更大容量的磁盘阵列。如果将索引全部存放到内存中, 内存开销将非常的。假设平均文件大小为512K, 每个缓存索引为16个字节, Hash表填充率为50%, 那么总内存开销为20G。
当我们对CacheKey取Hash, 之后对该Hash值除以1024(压缩1024倍), 作为第一级索引。而第二级索引则为一个固定的大小的Block, 首先根据一级索引找到对应的二级索引表, 在二级索引表中以FIFO的方式进行缓存淘汰 (二级索引表由一个跳表和一个FIFO组成)。二级索引会导致索引写放大n倍, 针对该问题，我们创建了一组mem table, 采用类似于leveldb的方式在内存中先做聚合, 再与原表进行合并写入。
因二级索引可能存在额外的IO开销 (针对热点条目做Cache)，固用户需在两种方案中进行衡量和取舍。我们以一种冷资源大容量存储的服务规划，假设有24块16T的HDD，单机的带宽峰值为23Gbps, 命中率为70%, 此时单盘的写IO为36MB/s, 假设平均文件对象大小为512K, 此时新增索引数为72/s, 此场景中采用二级索引保证存储引擎吞吐量的同时, 可大幅度降低索引表对存储空间的需求。 假设索引合并完毕需要3小时, 单盘二级索引表有30GB, 此时索引带来的写IO为7MB/s, 属于可控范围。而存放3小时索引的增量需要的内存空间为253KB。
二级索引设计示意图:
### HttpCache如何保证大文件的完整性
对于Cache系统来说，我们允许缓存丢失, 但是不期望缓存出现部分丢失(读取了部分缓存数据, 然后因某些片段丢失, 导致数据被截断)。因为此场景一般服务于类似图片、js、以及chunk响应的资源，通常很难通过补片的方式完成资源完整性的修复。固一旦出现部分片段丢失，那么该请求应该立即回源, 从源站直接获取完整的资源。
如何检测到大文件的是完整的，需要注意在本系统中索引的存储是不保证可靠的？
- 对于大文件的写入, 我们是先写body, 再写header，在header中保存了所有body fragmet的 indexitem (hash值 + offset), 在读取时，先根据头片来获取所有body fragment的 indexitem, 先检查一遍是否一致，如果一致则认为cache hit，否则cache miss。
-如果缓存回收导致不一致该怎么办
- recycle程序将不对资源进行热点回收。但是recycle流程需要保证正处于读取过程中的大文件不会被覆盖。因此recycle流程需要在要覆盖时，该区域是否存在被hold住的frament。 如果存在被hold住的fragment, 则将它读取出来, 构建一个新的索引, 更新到内存中的header frament上 (body frament被hold, header fragment必然在内存中), 但是此处并不更新到索引表, 因为该资源属于紧急疏散, 读取完毕后就会被丢弃。
设计示意图:
### 不允许分片的资源读写合并问题
不允许分片的资源可能存在整个响应体很大的情况。我们假设该资源有1G, 请求A发起回源读取操作, 当它消费了部分数据后，此时请求B到来, 它是没办法从请求A上拿到想要的数据的 (如果A要持有1GB的数据, 无疑内存会爆掉)。固此情况请求A需要将数据写入缓存, 请求B从缓存中读取即可。 这需要我们实现一种cache read wait write的能力。 同时我们需要主要各种特殊场景的处理，比如B要从A上读取数据，但是A当前尚未拿到缓存数据, 固未写缓存，比如B从A上读取数据，但是A已经将绝大多数响应内容落盘的情况。
设计示意图如下:
## TODO:
- 当前跨线程组内存申请释放较差, 待优化。
- 基础库整体添加一个初始化函数和结束函数, 方便外部程序使用。
- 字符串长度类型均修改为size_t。
- http支持多种连接处理。
- http trailer处理。
- http 连接复用, 将IP:Port从str比较改为sockaddr比较。
- my_conn结构中包含local_sockaddr和peer_sockaddr?
- http 库支持websocket和connect相关协议。
- http 的pool由外部程序传入, 拆分create_request和request_init接口, request本身不创建pool, 而是由外部传入。
- 没必要严格准守在进程结束时释放所有已分配的内存, 要添加asan检测文件方便检测内存泄露
- mem pool支持debug方式编译。
- multiple RANGE支持。
- websocket和connect请求支持。