知识汇总

红黑树

规则如下：

• 每个节点不是黑色就是红色
• 根节点为黑色
• 如果节点红色，其子节点必为黑
• 任意路径到叶子节点的路径，所含黑色节点数必相同

以上规则规定了红黑树中一条路径至多是另一条路径的两倍长度。

deque

deque的实现为一系列连续的缓冲块连接在一起，通过中央map，其中每一个节点都指向一块缓冲，当要扩展时，就新开辟一个节点，申请一块缓存，指向这个缓存，当中央map满了，就会像vector一样，重新分配一块更大的空间，复制过去，释放旧空间。在向前后添加时，迭代器可能失效，但是指针不会失效，因为存放数据的缓存是不会改变的。

next_permutation

从尾端向前寻找两个相邻元素，前面的记为i，后面的记为ii，找到一组i < ii的，再从最后往前找到第一个大于i的，记为j，i和j对调，再把ii之后的所有元素倒排。

prev_permutation

从尾端向前寻找两个相邻元素，前面的记为i，后面的记为ii，找到一组i > ii的，再从最后往前找到第一个小于i的，记为j，i和j对调，再把ii之后的所有元素倒排。

partial_sort

将前n个数组成一个最大堆，遍历后面的数，和最大堆堆顶比较，如果小于堆顶就互换位置然后调整堆，如此遍历一遍，前n个数就是最小的n个数，再对前n个数进行堆排序。

sort

数据量大时采用快排，当递归到数据量小于某个阈值，改用插入排序，当递归层数过深，改用堆排序。

进程的内存结构

linux虚拟内存管理

进程布局存在于虚拟内存中，每个程序使用的内存切割成小型的、固定大小的页，任意时刻，每个进程只有部分页需要在物理内存中，当进程要访问的页不在物理内存中，发生页面错误，内核挂起进程，同时从磁盘将该页面载入内存。为了支持这个组织方式，内核为每个进程维护了一个页表，记录了每页在物理空间中的位置，若进程试图访问的位置没有页表与之对应，则会收到SIGSEGV信号。

栈帧

调用函数时，会在栈上分配一个栈帧。每个栈帧包括：函数实参和局部变量，参数是从右到左的顺序压栈，函数调用的链接信息，主要是一些寄存器，比如程序计数器，指向下一条要执行的机器指令，当函数调用另一个函数时，会在被调用函数的栈帧中保存这些寄存器的副本，以便函数返回时能将寄存器恢复原状。在函数调用的过程中，ebp和esp两个寄存器分别存放了维护这个栈的栈帧底和栈帧顶指针。

分配栈帧时，首先将ebp压栈，方便以后返回，然后将esp赋给ebp作为新的栈帧的栈底，然后esp向下扩展分配一个栈帧，返回时，将ebp赋给esp，然后ebp出栈，将出栈的ebp赋给ebp，回到上一个函数的栈帧。

内存分配

当前堆顶称为program break，brk和sbrk函数可以抬升program break，抬升后，程序可以访问新分配的地址，此时这些新内存的物理内存还没分配，第一次访问时会自动分配物理内存。

malloc和free用来在堆上分配和释放内存，一般情况下，free不降低program break，而是将这块内存添加到空闲内存列表中，供后续的malloc使用，这么做有3个原因，释放的内存位于中间而不是堆顶，因此不可能降低program break；减少了sbrk调用的次数；应用程序倾向于反复释放和分配内存。

malloc的实现：首先扫描free的空闲列表，找到尺寸大于等于要求的一块内存（first-fit或者best-fit），如果大小刚好，就返回给用户，如果较大，会对其切割，返回大小相等的，剩余的小块内存保留在空闲列表中。如果在空闲列表中找不到合适的内存，会调用sbrk分配更多的内存，为了减少sbrk的调用次数，会以比要求的大小更大的幅度来增加program break，并将超出的部分置于空闲列表。

free的实现：如何知道内存块的大小呢，在malloc分配内存时，额外分配几个字节来存放这块内存大小的整数值。当内存块置于空闲列表时，free会用内存块本身的空间来存放链表指针，一个内存块从开始的内容为：内存块长度、指向前一个内存块的指针、指向后一个内存块的指针、剩余的空闲空间。

calloc会将分配的内存初始化为0。realloc可以改变已经分配的内存块的大小，当增大时，首先尝试合并在空闲列表中紧随其后的大小合适的内存块，如果没有就分配一块新内存，将数据复制过去。

alloca在栈上分配内存，分配的内存会自动释放。

sizeof

编译时就确定下来，sizeof一个函数返回函数返回值类型大小，函数不会执行，sizeof一个表达式，表达式不会执行。

extern “C”

C++为了支持函数重载，要对函数的名称做处理，而C中不做处理，两者对函数名称的处理是不一样的，在链接阶段按照C++的命名规则去找C的函数就会出现链接错误。extern “C”告诉编译器用C的规则来链接函数。

排序

稳定排序：插入排序，冒泡排序，归并排序，基数排序

不稳定排序：堆排序，快速排序，选择排序，希尔排序

时间复杂度：

io缓冲

read或者write不会直接操作磁盘文件，仅仅在用户空间和内核缓冲区高速缓存之间复制数据，内核会在后续的某个时间缓冲区中的数据同步到文件中，也就是说系统调用和磁盘操作并不同步。这样的设计让read和write速度更快，因为不用等待磁盘操作，而且也可以减少磁盘传输数据的次数。fsync会强制把缓冲区中的数据刷新到磁盘中，open的时候指定O_SYNC标志也可以让后续的写入立即同步。

stdio库也有缓冲区，可以用setvbuf或者fflush强制刷新，这个缓冲区在用户空间，而io的缓冲区在内核。

open时指定O_DIRECT可以在用户空间和磁盘文件直接进行IO。

文件描述符和流可以互相转换，fileno将流转成描述符，fdopen将描述符转成流。

i-node

对于系统上的每个文件，文件系统的i-node表会包含一个i-node，ls -li现实的第一列就是i-node。

i-node维护了一些信息：

• 文件类型
• 文件属主
• 文件属组
• 3类用户的访问权限
• 3个时间戳，最后访问时间，最后修改时间，文件状态的最后改变时间
• 指向文件的硬链接数量
• 文件大小
• 分配给文件的块数，512字节块为单位，文件块中包含了文件内容

链接

硬链接是指多个文件指向同一个i-node，软链接是指一个文件的内容是另一个文件的名称。i-node会维护一个计数，每有一个硬链接计数就增加，当计数为0时，系统会释放i-node中的数据块。

i-node中不包含文件名，目录会列出文件名和对应i-node的一个表格。

SIGSEGV

当应用程序对内存的引用无效时，会产生该信号。可能是因为要引用的页不存在，或者试图修改只读内存，或者用户试图访问内核部分内存，C语言中往往是指针包含的地址错误。

fork

子进程返回0，父进程返回子进程的进程id，错误返回-1。子进程拥有父进程数据段、堆、栈的拷贝，但是采用写时复制的手法，修改时才拷贝，和父进程共享代码段，共享文件描述符。

vfork是为fork之后立刻调用exec专门设计的，他不会拷贝父进程的内存，而且在子进程执行exec之前，父进程会暂停执行。vfork保证子进程优先于父进程得到调度。

通常只有一个进程调用exit，其他子进程调用_exit，exit会刷新stdio缓冲区。

父进程使用waitpid回收退出的子进程，常常安装SIGCHLD的信号处理器，在处理器函数中循环调用waitpid，使用WNOHANG标志非阻塞地回收子进程。

clone也可以创建进程，不同的是，clone可以指定子进程的起始函数，而且对父子之间的共享属性有更精确的控制，主要用于线程库的实现。fork、vfork、clone都是由kernel/fork.c中的do_fork实现的。

pthread

每个线程都有属于自己的errno。线程的一些函数：

• pthread_create:创建线程
• pthread_exit:退出线程，相当于在线程函数里面return
• pthread_join:连接线程，相当于线程版的waitpid，回收线程资源
• pthread_detach:线程分离，不需要手动进行join，但是当主线程退出时，该线程也会退出

线程的优点：

• 线程间共享数据很简单，相比之下，进程间共享数据需要ipc
• 线程创建速度比进程快，上下文切换的开销比进程小

线程的缺点：

• 确保线程安全
• 某个线程中的bug可能会危及进程内的所有线程，而进程之间空间不共享，隔离更彻底
• 每个线程都适用宿主进程的虚拟空间，空间是有限的，当分配大量线程时就会受到限制，而每个进程可以使用全部有效的虚拟内存

除此之外，多线程程序应该避免使用信号，所有线程运行同一个程序，而多进程可以运行不同的程序。

信号量与互斥量

只有锁住互斥量的线程能对它解锁，而一个线程可以递增一个被另一个线程锁住的信号量。

shutdown

可以实现半关闭，关闭写端用得最多。shutdown可以立即关闭套接字通道，而close只是将引用计数减1。shutdown不会关闭描述符，只能用close来关闭。

sendfile

又称零拷贝传输，把文件直接在内核中发送到socket的发送缓冲区中，省去了内核空间和用户空间之间的拷贝，只能用于将文件传输给socket。

time_wait

有两个作用，一是实现可靠的连接终止，二是让老的重复报文段在网络中过期消失。

如果关闭阶段最后的ack服务端没有收到，服务端会重发fin，这时若客户端关闭则无法重新发送ack，连接就得不到关闭，反而会发送一个rst作为响应，这个rst会解释为一个错误。通常维持2MSL时间，一个MSL是ack发送的时间，另一个MSL是fin重新发送的时间。

考虑连接关闭后有个新连接用同样的端口建立起来，tcp协议采用的重传算法可能产生重复的报文，这些老的重复的报文可能在连接关闭后才到达服务端，这时候服务端可能把这个报文误认为是新的连接发送的，为了避免这种情况，time_wait状态是必须的。

在这期间，端口被占用，服务器不能立刻绑定该端口，可以设置tcp的选项SO_REUSEADDR，即可关闭服务器后立刻绑定同一个端口，同时仍然允许time_wait状态生效。

udp的优势

udp不需要建立连接，因此传送单条信息开销较小，且速度更快。DNS就是应用udp的例子。udp可以进行广播和组播。有些应用不需要tcp的可靠性也能在接受范围内，相反，tcp的超市重传造成的延时是不能接受的，比如视频流，这样的应用udp更合适。

select和poll的问题

• 每次调用后必须检查所有的文件描述符
• 每次调用都要将相应的数据结构从用户空间拷贝到内核，内核修改后再拷贝到用户空间，非常耗费cpu

epoll的优势

• 不需要每次传递要监视的描述符到内核，内核会维护所有的要监视的描述符
• 返回的是已经就绪的描述符集合，不需要再对所有描述符遍历一遍

epoll的使用场景是需要同时监视大量描述符，但是大部分处于空闲状态，只有少数处于就绪状态。

边缘触发

EPOLLET通常和非阻塞套接字配合使用。使用et触发，一个事件只会得到一次通知，所以必须在这次通知将其处理完毕，不断执行io直到返回eagain。

当一个描述符上有大量io时，如果这时尝试将所有输入都读取，其他描述符可能会处于饥饿状态得不到处理，可以维护一个列表，列表中存放已经就绪的文件描述符，不立刻进行io，epoll调用完之后，再对列表中的描述符进行一定限度的io，直到有返回EAGAIN就可以将这个描述符从列表中删除了。

http1.0、1.1、2.0

• http1.0和1.1：1.1默认支持长连接，1.0需要设置keep-alive字段才行；1.1支持host域，1.0不支持；1.1可以只发送头部字段，等到收到100再继续发送消息体，若收到401就不必发送消息体，节约了带宽，1.0不支持，此外1.1还支持发送部分内容。
• http1.1和2.0：2.0支持多路复用，一个连接并发处理多个请求，1.1不支持；2.0支持对头部进行HPACK压缩，体积小了传输速度更快，1.1不支持；2.0支持服务器推送，当客户端请求时，服务器会把客户端需要的资源缓存到客户端本地，下次客户端就可以直接从本地加载，不需要通过网络。

https

由于http是明文传输，故数据可能被抓包篡改，https=http+认证+加密。

https建立过程：

脏读、不可重复读、丢失更新

• 脏读：事务对缓冲池中数据的修改，并且没有提交。一个事务可以读取到另一个事务尚未提交的数据。
• 不可重复读：在一个事务中，多次读取一个集合，另一个事务也访问该集合并作了一些修改，那么第一个事务两次读取的数据可能是不一样的。脏读是读到了未提交的数据，不可重复读是读到了已经提交的数据。
• 丢失更新：一个事务的更新会被另一个事务的更新所覆盖，导致数据不一致。

乐观锁、悲观锁

• 乐观锁：总是认为不会产生并发问题，每次去取数据的时候总认为不会有其他线程对数据进行修改，因此不会上锁，但是在更新时会判断其他线程在这之前有没有对数据进行修改，一般会使用版本号机制或CAS操作实现。

• 悲观锁：总是假设最坏的情况，每次取数据时都认为其他线程会修改，所以都会加锁（读锁、写锁、行锁等），当其他线程想要访问数据时，都需要阻塞挂起。可以依靠数据库实现，如行锁、读锁和写锁等，都是在操作之前加锁。

并查集

1
2
3
4
5
6
7
8
9
10
11
12

int parent[N];
    
void init(){
    for(int i=0; i<N; i++)
        parent[i] = i;
}
    
int find(int x){
    if(parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

gc算法

• 引用计数法：
  给对象添加一个引用计数器，每过一个引用计数器值就+1，少一个引用就-1。当它的引用变为0时，该对象就不能再被使用。它的实现简单，但是不能解决互相循环引用的问题。
• 根搜索算法：
  以一系列叫“GC Roots”的对象为起点开始向下搜索，走过的路径称为引用链（Reference Chain），当一个对象没有和任何引用链相连时，证明此对象是不可用的，用图论的说法是不可达的。那么它就会被判定为是可回收的对象。
• 标记-清除算法
  这是一个非常基本的GC算法，它是现代GC算法的思想基础，分为标记和清除两个阶段：先把所有活动的对象标记出来，然后把没有被标记的对象统一清除掉。但是它有两个问题，一是效率问题，两个过程的效率都不高。二是空间问题，清除之后会产生大量不连续的内存。
• 标记整理算法
  标记整理算法适用于存活对象较多的场合，它的标记阶段和标记-清除算法中的一样。整理阶段是将所有存活的对象压缩到内存的一端，之后清理边界外所有的空间。它的效率也不高。

蓄水池抽样

从n个对象中随机取一个对象，每个对象被取到的概率为1/n，假设不知道n的值，或者n非常大，无法直接rand()%n。解决方法是总是选择第一个对象，以1/2的概率选择第二个，以1/3的概率选择第三个，以此类推，以1/m的概率选择第m个对象。当该过程结束时，每一个对象具有相同的选中概率，即1/n，证明如下。

第m个对象最终被选中的概率P=选择m的概率*其后面所有对象不被选择的概率，即

代码：

1
2
3
4
5
6
7
8
9
10
11

int cnt = 1;
object choose;
for(object o:objs){
	if(cnt == 0)
		choose = o;
	else{
		if(rand()%cnt == 0)
			choose = o;
	}
	++cnt;
}

gdb原理

通过ptrace系统调用实现，ptrace可以让父进程观察子进程的运行，gdb run一个程序时，首先fork一个子进程，在子进程调用ptrace，然后exec加载指定的程序运行。

gdb调试建立在信号的基础上，设置断点时，找到该行代码的具体地址，向该地址写入断点指令，INT3，程序运行到这里会触发SIGTRAP信号，然后根据目标程序当前停止的位置在gdb维护的断点链表中查询，若存在，则可判定为命中断点。gdb暂停目标程序运行的方法是想起发送SIGSTOP信号。

如果一个进程CPU占用太大，如何定位和调试这个进程？

用top命令找到最占CPU的进程，使用pstack跟踪进程栈，此命令允许使用的唯一选项是要检查的进程的PID，使用top命令查看指定进程最耗CPU的线程，top -H -p pid，如果想查看具体的原因，如现场的函数中变量等的数值等，就要使用的GDB的实时调试功能，gdb attach pid。

new和malloc

new和malloc的10点区别

linux中，对于一个已经动态编译后的文件，怎么查找出它用了哪些动态库？

ldd。

Linux共享库的搜索路径先后顺序

1、编译目标代码时指定的动态库搜索路径：在编译的时候指定-Wl,-rpath=路径
2、环境变量LD_LIBRARY_PATH指定的动态库搜索路径
3、配置文件/etc/ld.so.conf中指定的动态库搜索路径
4、默认的动态库搜索路径/lib
5、默认的动态库搜索路径 /usr/lib

kmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

vector<int> getNext(const string& pattern){
	const int n = pattern.size();
	vecor<int> res(n, -1);
	int i = 0, j = -1;
	while(i < n - 1){
		if(j == -1 || pattern[i] == pattern[j]){
			++i; ++j;
			if(pattern[i] == pattern[j]) next[i] = next[j];
			else next[i] = j;
		}
		else
			j = next[j];
	}
}

int kmp(const string& s, const string& pattern){
	vector<int> next = getNext(pattern);
	const int m = s.size(), n = pattern.size();
	int i = 0, j = 0;
	while(i < m && j < n){
		if(j == -1 || s[i] == pattern[j]){
			++i; ++j;
		}
		else{
			j = next[j];
		}
		if(j == n) return i - j;
	}
	return -1;
}

洗牌算法

1
2
3
4
5
6
7

void shuffle(vector<int>& num){
	const int n = num.size();
	for(int i = n-1; i >= 0; --i){
		int tmp = rand() % (i+1);
		swap(num[i], num[tmp]);
	}
}

跳跃表

B+树

syn flood

Nginx简介

Nginx是高性能web服务器，使用量排世界第二。一些优点：单次请求更快的响应，高并发情况下更快响应，扩展性好，高可靠性，低内存消耗，单机支持10w以上并发连接，可提供热部署，开源等等。

架构设计

• 模块化设计，高度模块化，有着抽象简单的接口，非常灵活。
• 事件驱动架构，分为事件收集、分发者和各种事件的消费者
• 请求的多阶段异步处理，把一个请求分为多个阶段，每次处理只能处理一部分，等下一次epoll循环再继续处理剩余的部分，取决于内核调度，配合事件驱动架构，使得每个进程都全力运转，尽量少出现休眠状况，具体是将阻塞方法分解为多个阶段，用定时器来代替循环检查标志位，若阻塞方法无法划分，用一个单独的进程来执行方法
• 管理进程、多工作进程的设计，采用一个master管理进程，多个worker进程的工作方式，master进程监控worker进程，当worker进程出现问题，会启动新的进程避免性能下降，其次，master进程还支持运行时程序升级，配置项的修改等，worker进程间通过进程间通信来进行负载均衡，master进程和worker进程通过unix套接字进行通信
• 可移植性
• 使用内存池，减少内存碎片，减少内存申请次数，减少cpu消耗。

worker进程的工作方式

每个worker进程运行一个epoll事件循环，监听相同的端口，这会带来惊群问题，惊群指的是当新连接到来的时候，会唤醒所有监听端口的子进程，但是最后进行连接的只有最开始accept那个进程，其他进程accept失败继续休眠，这引起了不必要的上下文切换，增加了系统开销。解决方法是一个时刻只让一个进程监听端口，使用accept_mutex锁，监听时首先尝试持有锁，如果失败则不监听，若成功才监听端口，可能这个进程上有很多活跃的连接，可能占用锁很长时间，这样其他进程就不能监听了，nginx提供了2个post队列，一个用来放连接事件，另一个用来放普通读写事件，收到新连接时将连接事件放入连接post队列，接下来先处理连接post队列里面的请求，然后释放锁，再处理正常事件post队列的事件，这样就大大减少了锁的持有时间。

多个子进程之间还要实现负载均衡。和解决惊群的问题一样，需要accept_mutex锁，同时有一个变量ngx_accept_disabled，它是负载均衡的一个阈值。在启动时，这个阈值是一个负数，值为连接总数的7/8，负数时不会触发负载均衡，正数的时候才会触发负载均衡，当其为正数时，就不再接受新的连接，即是说当前连接使用达到总连接数的7/8时就不再接受新连接，每次循环将这个值减1，直到负数，才会尝试去持有accept_mutex锁处理新连接。伪代码如下：

1
2
3
4
5
6
7

if(ngx_accept_disabled)
	ngx_accept_disabled--;
else{
	if(ngx_trylock_accept_mutex() == NGX_ERROR)
		return;
	...
}

在一个事件循环中，主要调用ngx_processs_events_and_timers函数，处理网络事件和定时器事件，核心操作有3个：处理网络事件、处理两个post队列中的事件（上文提到）、处理定时器事件。

epoll的实现结构

简单提一下epoll的实现，epoll内部有一个红黑树用来保存所有监听的描述符及其对应的事件，和一个链表用来保存所有已经就绪的描述符，epoll_create时创建并初始化这个数据结构，epoll_ctl向红黑树中插入删除查找，效率很高，epoll_wait查看链表，若链表不为空就将链表中的内容从内核空间复制到用户空间。每个事件就绪后会用类似于回调方法的机制将自己添加到队列中，所有整个过程很高效。

TCP和Nginx

内核中的TCP和Nginx之间的关系。
连接时：

发送数据：

接受数据：

配置项

Nginx的配置文件大致格式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

http{
	server{
		server_name A;
		listen 80;
		listen 127.0.0.1:8080;

		location /L1{
			root html;
			...
		}

		location /L2{
			...
		}
	}

	server{
		server_name B;
		listen 80;
		listen 127.0.0.1:8000;

		location /L3{
			...
		}

		location /L4{
			...
		}
	}
}

可以看出一个配置文件可能有多个server块，server块下有多个location块，代表感兴趣的匹配url地址，每个server块代表了一个服务器，包括监听的端口号，感兴趣的url地址，根目录等。

upstream

Nginx通过upstream机制来提供反向代理服务。反向代理时，Nginx作为一个媒介，连接客户端与上游服务器，接受客户端的请求，将请求转发给上游服务器，再将上游服务器的结果转发给客户端。为什么要有这种设计呢？通常客户端与Nginx之前是外网连接，而Nginx和上游是内网连接，内网速度非常快，而外网较慢，利用Nginx的高性能可以尽可能的多处理客户端的请求从而减轻上游服务器的压力，上游服务器可以是Apache、Tomcat、memcached、mysql等。通常下游是HTTP协议，而下游是TCP协议。

当上下游网速差距不大，或者下游更快时，会开辟一块固定大小的内存，用来接受上游响应，并将其转发给下游，当下游接受速度慢，响应就会堆积在内存中，无法接受上游的响应。

当上游快于下游时，就要开辟足够的内存缓存来保存上游响应，内存满时还会将响应缓存到磁盘文件中。

Redis简介

Redis是一个高效的键值对内存数据库。

基本数据结构

简单动态字符串（SDS）、链表、字典、跳跃表、整数集合、压缩列表。基于这些数据结构实现了Redis的5种存储类型，分别是字符串、哈希、列表、有序集合、集合，每种类型底层有多种数据结构实现方法，根据应用场景不同而变化。

SDS

长度可变，当进行扩展时，除了分配所需的空间外，还分配额外的未使用空间，有效减少内存重分配次数，释放时不真正释放，采用惰性释放，用free字段记录这些字节。

字典

用哈希表实现：用链式地址法解决键冲突，具有相同哈希值的键用一个链表存储起来，将新节点添加到链表的头节点位置。

当哈希表的键值对太多或太少时，会进行相应的扩展或收缩，内部有两个哈希结构，记为ht[0]和ht[1]，平常只用到ht[0]用来存储键值对，当要扩展时，首先将ht[1]的大小设为第一个大于等于ht[0].used*2的2的n次方，收缩时，将ht[1]的大小设为第一个大于等于ht[0].used的2的n次方，然后将ht[0]里的键值对rehash到ht[1]中，释放ht[0]，将ht[0]设为ht[1]，ht[1]设为ht[0]，并在ht[1]创建一个空哈希表为下一次rehash准备。决定是否要扩展或者收缩根据负载因子（used/size）确定。当键值对非常多，一次rehash会占用相当长的时间，导致服务器停止服务，因此实际上rehash时分多次、渐进式的完成的。具体来说，在字典中维护一个rehashidx变量，从0开始计数，在每次对字典进行查找删除添加的时候，将rehashidx这一索引上的键值对全部rehash到ht[1]中，相当于在每次操作之后rehash一行键值对，然后rehashidx加1，下次操作rehash下一行，如此rehash完所有行后将rehashidx设为-1表示rehash操作已完成。这么做的好处是将所有工作均摊到每一次操作上，避免了一次性rehash的庞大计算。此外，在rehash期间进行的删除查找操作会在两个表上查找，而添加操作一律添加到ht[1]中。

跳跃表

平均O（logn），最坏O（n）的查找。是有序集合的基本数据结构。

整数集合

底层实现是数组，保存整数。数组有个类型，当新加入的数比这个类型长时，数组会进行升级。只有在必要时才进行升级，尽可能节约了内存。

压缩列表

压缩列表节约内存。可以包含多个节点，每个节点保存一个字节数组或者用一个整数值。添加或者删除节点，可能引发连锁更新操作，出现几率并不高。

字符串

底层编码可以是int、raw(SDS)、embstr。embstr是专门保存短字符串的优化编码方式，当字符串长度小于等于39会采用。

命令：set、get、append、incrby、decrby、……

列表

编码可以是压缩列表和双向链表，内部会嵌套字符串对象。当所有字符串长度小于64且元素数量小于512用跳跃表，否则用链表。

命令：lpush、rpush、lrange、lpop、rpop、……

哈希

编码可以是压缩列表和哈希表。转化条件和列表一样。

命令：hset、hget、hexists、hmset、hmget、hgatall……

集合

编码可以是整数集合或者哈希表。当元素都为整数且数目不超过512个用整数集合，否则哈希表。

命令：sadd、smembers、spop……

有序集合

编码可以是压缩列表和跳跃表。字典提供O(1)的查找复杂度，而跳跃表提供快速的范围操作。当元素数量小于128个，且长度都小于64字节时用压缩列表。

命令：zadd、zrange、zrank、zscore……

内存回收

基于引用计数的内存回收。当计数为0释放内存。此外当一个对象同时被两个键引用时，还会进行共享，即对象只有一份，引用计数为2，节约内存。目前Redis会在初始化服务器时创建0到9999的所有整数作为共享对象。

空转时长

对象里还有一个lru属性，记录了对象最后一次被命令访问的时间，当前时间减去lru即时空转时长，空转时长较高的键会被释放，回收内存。

单机数据库

数据库基本数据结构

数据库的结构为redisServer：

1
2
3
4
5

struct redisServer{
	...
	redisDb * db; //保存所有的数据库
	int dbnum;    //数据库的数量
}

默认情况下，数据库有16个，启动时默认选择0号数据库，可以用select命令选择数据库：

1

select 2

变化的是客户端数据库，服务器的数据库总是从0开始。
dict字典保存了所有键值对：

1
2
3
4
5

struct redisServer{
	...
	dict* dict;    //保存所有键值对
	dict* expires; //保存所有键的过期时间
}

可以用expire为键设置过期时间，时间到自动删除。expires字典保存了所有键的过期时间，值为longlong，是一个毫秒精度的unix时间戳。persist可以移除一个键的过期时间。对于过期键的删除策略，有以下三种方式：

• 定时删除：设置键过期时间时设置一个定时器，时间到了进行删除。
• 惰性删除：不主动删除，获取键的时候判断是否过期，如果过期再删除。
• 定期删除：每隔一段时间，对数据库进行检查，删除其中的过期键。

定时删除对内存最友好，因为可以第一时间删除过期的键，但是对cpu不友好，每次都需要占用cpu时间，删除时需要处理与当前无关的键。惰性删除是对cpu最友好的，每次只对查询的键做处理，如果过期才删除，同时对内存最不友好，因为存在大量过期的无用的键没有及时删除占用内存。定期删除是一种折中方案，难点是确定删除的时长和频率。Redis使用的是惰性删除和定期删除两种策略。定期删除是在服务器的周期性操作serverCron执行时进行的，每次运行时，从一定数量的数据库中随机取出一定数量的随机键进行检查，删除其中的过期键，每轮检查有一个时间，时间到了则停止检查，记录下此时检查到第几个数据库，下次继续从这个数据库开始检查过期键。

持久化

Redis是内存数据库，数据都存储在内存中，如果服务器退出，内存中的数据就都丢失了，因此需要将数据保存在本地磁盘上，称为持久化。分为RDB持久化和AOF持久化。

RDB持久化

RDB文件是一个经过压缩的二进制文件。save和bgsave命令会生成RDB文件，save会阻塞服务器直到文件写入完成，而bgsave会创建子进程来写文件，服务器能够继续正常运行，子进程完成后向父进程发送信号。服务器启动时自动读取RDB文件恢复数据库内容，读取是阻塞的。通过配置文件的save选项，若一段时间内执行了一定次数的写操作，则服务器可以自动进行bgsave命令来保存RDB文件。RDB文件由5部分组成：
|REDIS|db_version|databases|EOF||check_sum|

对于不同的键值对，会用不同的方式保存。

AOF持久化

RDB文件保存数据库的数据，而AOF文件保存的是服务器执行的写命令。每执行一条写命令，都会添加到AOF文件中，AOF实现可以分为命令追加、文件写入、文件同步三个步骤。服务器结构中有一个AOF缓冲区，命令追加到缓冲区中，Redis默认是每秒将缓冲区中的内容写入文件并进行同步，因为write调用是将内容写入到内核的io缓冲区中并不是马上写入磁盘文件，所以需要同步操作（fsync）来讲io缓冲中的内容写入文件。

AOF载入时，会先创建一个伪客户端，让这个客户端执行AOF文件中的写命令，从而恢复数据库数据。

随着写命令的增加，AOF文件可能变得非常庞大，不利于服务器的运行。Redis提供了AOF重写功能，创建一个新的AOF文件，这个文件的数据库状态和旧文件相同，但是没有冗余的写命令，体积小得多。AOF重写不需要分析现有的AOF文件，它是通过读取服务器状态来实现的。原理是读取数据库所有键目前的值，然后只用一条写命令记录键值对，代替多条命令，因此新AOF文件只包含必要的命令，不会浪费任何空间。

AOF提供了后台重写的功能，创建子进程来重写AOF文件，但是存在一个问题，创建子进程后可能会有新的写命令改变了数据库的状态，导致AOF文件和当前数据库状态不一致，为解决该问题，设置了一个AOF重写缓冲区，创建子进程之后，所有执行的写命令都写到这个缓冲区中，等到子进程完成重写操作向父进程发送信号，父进程将AOF重写缓冲区中的写命令全部写到AOF文件中并同步，如此数据库的状态就一致了。

事件

Redis服务器是一个事件驱动型程序，处理两种事件：文件事件和时间事件。文件事件就是和客户端产生的一些网络事件，时间事件是定时的操作。

Redis基于reactor模式开发了网络事件处理器，处理器采用io复用的方式同时监听多个套接字，根据套接字目前执行的任务来为套接字关联不同的事件处理器，整体是单线程的，保持了Redis内部单线程的简单性。结构如下：

网络事件类型分为可读（客户端发起连接或者write）和可写（客户端read），如果又可读又可写，优先处理可读。最常见的事件处理器是连接应答处理器、命令请求处理器、命令回复处理器。

时间事件分为定时事件、周期性事件。目前Redis只使用周期性事件。服务器将所有的时间事件都放在一个无序链表中，每次时间事件执行器运行时，遍历这个链表查找已经到达的时间事件调用相应的处理器，正常模式下只有serverCron这一个时间事件。
serverCron的主要工作包括：

• 更新服务器的各类统计信息，如时间、内存占用、数据库占用等
• 清理数据库中的过期键值对
• 关闭清理连接失效的客户端
• 尝试进行持久化
• 若服务器是主服务器，对从服务器进行定期同步
• 若处于集群模式，对集群进行定期同步和连接测试
  默认每隔100毫秒运行一次serverCron。

服务器事件的调度与执行过程：首先获取距离当前时间最近的时间事件，以这个时间作为io复用的超时时间，然后执行io复用，处理文件事件，然后处理时间事件，伪代码如下：

1
2
3
4
5
6

def processEvent():
	time_event = searchNearestTimer()
	time = time_event.when - unix_ts_now()
	poll(time)
	processFileEvents()
	processTimeEvents()

服务器的主函数的伪代码为：

1
2
3
4
5
6
7
8
9

def main():
	# 初始化服务器
	init_server()

	while server_is_not_shutdown()
		processEvent()

	# 清理服务器
	clean_server()

客户端

客户端包含一些属性，包括：

• 套接字描述符
• 名字
• 标志（记录了客户端的角色和状态）
• 输入缓冲区（保存命令）
• 命令与命令参数
• 命令的实现函数（在命令表中查找对应命令的函数）
• 输出缓冲区（保存回复，2个缓冲区，一个大小固定，保存长度较小的回复，一个大小可变，保存长度长的回复）
• 身份验证
• 创建客户端的时间、客户端与服务器最后一次互动时间、空转时间

服务器用clients链表连接多个客户端，新客户端放到末尾。缓冲区限制分为硬限制和软限制，一旦缓冲区中的数据长度超过硬限制立即关闭该客户端，若超过软限制且在一段时间内一直超过软限制也将其关闭，若一段时间内没有超过软限制了就不关闭该客户端。

服务器

命令请求的执行过程：

• 发送命令请求
• 读取命令请求
• 查找命令实现、执行预备操作、调用命令的实现函数、执行后续工作
• 将命令回复发送给客户端
• 客户端接受并打印回复

serverCron函数默认每隔100毫秒执行一次，负责管理服务器的资源，所做的工作如下：

• 更新服务器的时间缓存，即当前时间
• 更新lru时钟
• 更新服务器每秒执行次数
• 更新服务器内存峰值记录
• 处理sigterm信号
• 管理客户端资源，调用客户端的clientsCron函数，如果客户端已经超时（空转时间太长）就释放它，若输入缓冲区超过一定长度，释放该缓冲区，重新建立一个默认大小的缓冲区，避免占用太多内存
• 管理数据库资源，删除过期键
• 执行被延迟的bgrewriteaof
• 检查持久化操作的运行状态
• 将AOF缓冲区的内容写入文件
• 关闭异步客户端
• 增加cronloops，代表serverCron运行的次数

服务器初始化的过程：

• 初始化服务器状态结构
• 载入配置选项
• 初始化服务器数据结构
• 还原数据库状态
• 执行事件循环

多机数据库

主从复制

通过slaveof命令让一个服务器（从）复制另一个服务器（主），首先从服务器向主服务器发送sync命令，主服务器向从服务器发送RDB文件，并且在缓冲区中记录下之后执行的命令，从服务器读取RDB文件进行数据库恢复，然后主服务器将缓冲区中的命令发送给从服务器使得状态一致。之后每次写命令改变主服务器时，主服务器都会将命令传播给从服务器。但是当从服务器断线，然后重新上线时，为了恢复主服务器的状态，要重新发送sync命令重新生成RDB文件，这非常耗费时间和资源。为解决这个问题，psync命令可以实现部分同步，只需要将从服务器缺少的命令发送给从服务器。部分同步由三个部分组成：

• 复制偏移量，主服务器发送N字节就将自己的复制偏移量加N，从服务器接受N字节就将自己的复制偏移量加N，因此只要主从服务器的复制偏移量不同就说明从服务器掉线了。
• 复制积压缓冲区，时一个固定长度的队列，默认大小1m，缓冲区中记录着最近向从服务器传播的写命令，同时记录了每条命令的偏移量，当从服务器故障恢复时把自己的偏移量offset发送给主服务器，如果offset之后的命令都在缓冲区中，就可以将这部分命令发给从服务器完成部分同步，若不存在则进行完全同步。
• 服务器运行id，运行id在服务器启动时自动生成，由40个随机的十六进制字符组成，从服务器保存主服务器的运行id，当故障重启时，判断当前连接的主服务器的id和保存的id，如果id一致，说明之前就是连接的这个主服务器，则可以尝试进行部分同步，若id不相同，说明现在已经连接到一个新的主服务器，则进行完全同步。

复制的实现步骤：

• 设置主服务器的地址和端口
• 建立套接字连接
• 发送ping命令
• 身份验证
• 发送端口信息
• 同步
• 命令传播

此外还有心跳检测用域检测主从服务器的网络连接状态，检测命令丢失，辅助实现min-slave选项。

sentinel

sentinel（哨兵）系统可以监视多个主服务器以及所有从服务器，当监视的主服务器下线时，会从它的从服务器中选一个成为新的主服务器接管下线的主服务器，当下线的服务器再次上线时，它会成为新的主服务器的从服务器。

snetinel会以每秒一次的频率向所有与他建立连接的实例发送ping命令，当主服务器连续50000毫秒都返回无效回复时，sentinel将其标记为主观下线，为了确认这个服务器是否真的下线，它会向其他监视这个服务器的sentinel进行询问，当它收集到足够多的下线判断后，就将服务器判定为客观下线，并进行故障转移。首先挑选出一个状态良好、数据完整的从服务器升级为主服务器（优先级高，复制偏移量最大），让其他从服务器成为新的主服务器的从服务器，让下线的主服务器成为新的主服务器的从服务器。

集群

集群由多个节点组成，节点通过cluster meet和其他节点连接起来，一个节点就是一个服务器。

集群通过分片的方式保存数据库中的键值对，数据库被分为16384个槽，每个键都属于这些槽中的一个，每个节点可以处理0个到16384个槽。

节点收到一个命令请求时，会先检查这个命令请求的键所在的槽是否指派给自己，如果是就处理，如果不是则返回一个moved错误指引客户端转向负责该槽的节点。

集群里的从节点用于复制主节点，并在主节点下线时，代替主节点继续处理命令请求。（与sentinel类似）。

集群中的节点通过发送消息来通信，包括meet、ping、pong、publish、fail。

发布与订阅

通过subscribe订阅频道，当客户端向该频道发送消息时（publish），所有订阅该频道的客户端都能接收到消息。

在服务器中有一个字典记录了对应频道的所有订阅用户：

1
2
3
4

struct redisServer{
	//...
	dict* pubsub_channels;//保存所有频道的订阅关系
}

该字典的键是频道，值是一个链表，链表记录了所有订阅这个频道的客户端。

此外还可以订阅一个模式，相当于订阅了所有与该模式匹配的频道。在服务器中也有一个链表保存所有订阅模式的信息：

1
2
3
4

struct redisServer{
	//...
	list* pubsub_patterns;//保存所有模式的订阅关系
}

链表每一个节点都是一个pubsubPattern结构：

1
2
3
4

struct pubsubPattern{
	redisClient* client;//订阅的客户端
	robj* pattern;//订阅的模式
}

发布消息时首先找到在字典中找到频道对应的客户端链表，遍历链表将消息发送给所有客户端，然后遍历模式链表，找到一个匹配的模式就将消息发送给订阅该模式的客户端（模式O(n)复杂度，非模式O(1)复杂度）。

事务

通过multi、exec、watch来实现事务。multi标志一个事务的开始，接下来的命令会进入一个队列不立即执行，等到exec命令，将队列中的命令全部按顺序执行。

watch是一个乐观锁，可以在exec执行之前，监视任意数量的数据库键，在exec执行时，当至少有一个键已经被修改过了，服务器将拒绝执行事务。数据库中有一个字典用来记录watch的信息，键是watch监视的键，值是一个链表，保存了监视这个键的客户端，当键改变之后，会查找监视这个键的客户端，打开它的REDIS_DIRTY_CAS标志，表明事务安全性已经被破坏，exec执行时首先看客户端有没有REDIS_DIRTY_CAS标志，如果有就拒绝执行事务。

事务的ACID性质，即原子性，一致性，隔离性，持久性。Redis具有原子、一致、隔离，运行在持久化模式下时具有持久性。

原子性指的是事务中的操作要么全部执行，要么全部不执行。Redis不支持回滚。

一致性指的是如果事务在执行事务前是一致的，那么在事务执行后无论事务执行成功与否数据库仍然是一致的。一致指的是数据符合数据库本身的定义和要求，没有包含非法或者无效的错误数据。

隔离性指的是多个事务并发执行，各个事务之间也不会相互影响。因为Redis总是以串行方式来执行事务，所以有隔离性。

持久性指的是执行完事务过后，结果已经被保存到硬盘里了。只有运行在AOF的always模式下才具有持久性。

复合模式

定义

结合两个或以上的模式，组成一个解决方案，解决一再发生的一般性问题。

类图

MVC：

理解

MVC：同一个模型可以适用于多个视图，三层解耦，各自不需要知道具体实现，针对接口编程，分工明确。

设计原则

• 封装变化
• 多用组合，少用继承
• 针对接口编程，不针对实现编程
• 为交互对象之间的松耦合设计而努力
• 类应该对扩展开放，对修改关闭，开放关闭原则
• 依赖抽象，不要依赖具体类
• 只和朋友交谈，最少知识原则
• 别找我，我会找你，依赖倒置原则
• 类应该只有一个改变的理由，单一责任原则

代理模式

定义

为另一个对象提供一个替身或占位符以控制对这个对象的访问。

类图

理解

和客户直接打交道的不是服务本身，而是一个替身，但是客户不知道，以为他在和真正的服务打交道，这样做增加一层间接性，替身可以做很多事，比如控制访问，缓存，显示，而服务只需要关注服务本身，体现了单一责任原则。

一些例子，远程代理，虚拟代理，保护代理，缓存代理。

状态模式

定义

允许对象在内部状态改变时改变它的行为，对象看起来好像修改了它的类。

类图

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

class State {
public:
	virtual void insertQuarter() = 0;
	virtual void ejectQuarter() = 0;
	virtual void turnCrank() = 0;
	virtual void dispense() = 0;
};

class NoQuarterState :public State {
private:
	GumballMachine* machine;
public:
	NoQuarterState(GumballMachine* m) :machine(m) {

	}

	void insertQuarter() {
		cout << "you insert a coin" << endl;
		machine->setState(machine->getHasQuarterState());
	}

	void ejectQuarter() {
		cout << "Error" << endl;
	}

	void turnCrank() {
		cout << "Error" << endl;
	}

	void dispense() {
		cout << "Error" << endl;
	}
};

class HasQuarterState :public State {
private:
	GumballMachine* machine;
public:
	HasQuarterState(GumballMachine* m) :machine(m) {

	}

	void insertQuarter() {
		cout << "Error" << endl;
	}

	void ejectQuarter() {
		cout << "coin return" << endl;
		machine->setState(machine->getNoQuarterState());
	}

	void turnCrank() {
		cout << "turn crank" << endl;
		machine->setState(machine->getSoldState());
	}

	void dispense() {
		cout << "Error" << endl;
	}
};

class SoldState :public State {
private:
	GumballMachine* machine;
public:
	SoldState(GumballMachine* m) :machine(m) {

	}

	void insertQuarter() {
		cout << "Error" << endl;
	}

	void ejectQuarter() {
		cout << "Error" << endl;
	}

	void turnCrank() {
		cout << "Error" << endl;
	}

	void dispense() {
		machine->releaseBall();
		if (machine->getCount() > 0){
			machine->setState(machine->getNoQuarterState());
		}
		else {
			machine->setState(machine->getSoldOutState());
		}
	}
};

class SoldOutState :public State {
private:
	GumballMachine* machine;
public:
	SoldOutState(GumballMachine* m) :machine(m) {

	}

	void insertQuarter() {
		cout << "Sold out" << endl;
	}

	void ejectQuarter() {
		cout << "Sold out" << endl;
	}

	void turnCrank() {
		cout << "Sold out" << endl;
	}

	void dispense() {
		cout << "Sold out" << endl;
	}
};

class GumballMachine {
private:
	State* noQuarterState;
	State* hasQuarterState;
	State* soldState;
	State* soldoutState;
	State* state;
	int count = 0;

public:
	GumballMachine(int num) :
		noQuarterState(new NoQuarterState(this)),
		hasQuarterState(new HasQuarterState(this)),
		soldState(new SoldState(this)),
		soldoutState(new SoldOutState(this)),
		state(noQuarterState),
		count(num)
	{

	}

	void insertQuarter() {
		state->insertQuarter();
	}

	void ejectQuarter() {
		state->ejectQuarter();
	}

	void turnCrank() {
		state->turnCrank();
		state->dispense();
	}

	void setState(State* s) {
		state = s;
	}

	void releaseBall() {
		cout << "a ball comes out!" << endl;
		if (count != 0) {
			--count;
		}
	}

	State* getNoQuarterState() { return noQuarterState; }
	State* getHasQuarterState() { return hasQuarterState; }
	State* getSoldState() { return soldState; }
	State* getSoldOutState() { return soldoutState; }
	int getCount() { return count; }
};

理解

将一堆if的状态判断语句换成一堆状态类，每一个类代表一个状态，一个类只处理自己的状态，将代码分开，不容易出错，且容易扩展。

组合模式

定义

允许你将对象组合成树形结构来表现“整体/部分”层次结构，组合能让客户以一致的方式处理个别对象以及对象组合。

类图

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

class MenuComponent {
public:
	virtual void add(MenuComponent*) {};
	virtual void remove(MenuComponent*) {};
	virtual MenuComponent* getChild(int) { return nullptr; };

	virtual string getName() { return string(); };
	virtual void print() {};
};

class MenuItem :public MenuComponent {
private:
	string name;
	double price;
public:
	MenuItem(string n, double p) :name(n), price(p) {

	}

	string getName() {
		return name;
	}

	void print() {
		cout << getName() << "----" << to_string(price) << endl;
	}
};

class Menu :public MenuComponent {
private:
	vector<MenuComponent*> components;
	string name;
public:
	Menu(string n) :name(n) {

	}

	void add(MenuComponent* component) {
		components.push_back(component);
	}

	void remove(MenuComponent* component) {
		auto it = find(components.begin(), components.end(), component);
		if (it != components.end()) {
			components.erase(it);
		}
	}

	MenuComponent* getChild(int index) {
		if (index < components.size()) {
			return components[index];
		}
		return nullptr;
	}

	string getName() {
		return name;
	}

	void print() {
		cout << getName() << endl;
		cout << "----------------------" << endl;
		for (auto it = components.begin(); it != components.end(); ++it) {
			(*it)->print();
		}
	}
};

class Waitress {
public:
	Waitress(MenuComponent* m) :menu(m) {

	}

	void printMenu() {
		menu->print();
	}

private:
	MenuComponent* menu;
};

理解

将集合和个体组合成树形结构，叶子节点是个体，非叶子节点是集合，集合包含多个个体，也就是包含多个叶子节点，这样对集合和个体提供一致的访问方式。

迭代器模式

定义

提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露其内部的表示。

类图

代码示例

略

理解

用一个统一的接口访问不同的聚合对象（容器），不用知道对象其内部怎么实现，只需要用迭代器一个一个取出元素即可。迭代器由这个对象构造出来，因为只有这个对象知道该如何访问自己。

模板方法模式

定义

在一个方法中定义一个算法的骨架，将一些步骤延迟到子类中，模板方法使得子类可以在不改变算法结构的情况下，重新定义算法中的某些步骤。

类图

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class CaffeineBeverage {
public:
	void prepareRecipe() {
		cout << "**********************" << endl;
		cout << "prepare...." << endl;
		boilWater();
		pourInCup();
		brew();
		addCondiments();
	}

	void boilWater() {
		cout << "boil water" << endl;
	}

	void pourInCup() {
		cout << "pour in cup" << endl;
	}

	virtual void brew() {};
	virtual void addCondiments() {};
};

class Coffee :public CaffeineBeverage {
public:
	void brew() {
		cout << "dripping coffee" << endl;
	}

	void addCondiments() {
		cout << "adding sugar and milk" << endl;
	}
};

class Tea :public CaffeineBeverage {
public:
	void brew() {
		cout << "steeping the coffee" << endl;
	}

	void addCondiments() {
		cout << "adding lemon" << endl;
	}
};

理解

在接口中定义一个算法的框架，分为多个步骤，子类可以改变其中的某些步骤。STL中的很多算法都可以传入自定义的比较函数，此即为模板方法模式。

外观模式

定义

提供了一个统一的接口，用来访问子系统中的一群接口，外观定义了一个高层接口，让子系统更容易使用。

类图

代码示例

略

理解

将很长的复杂方法用一个方法封装起来，简化接口。