什么叫惊群现象

首先，我们看看维基百科对惊群的定义:

The thundering herd problem occurs when a large number of processes waiting for an event are awoken when that event occurs, but only one process is able to proceed at a time. After the processes wake up, they all demand the resource and a decision must be made as to which process can continue. After the decision is made, the remaining processes are put back to sleep, only to all wake up again to request access to the resource.

This occurs repeatedly, until there are no more processes to be woken up. Because all the processes use system resources upon waking, it is more efficient if only one process was woken up at a time.

This may render the computer unusable, but it can also be used as a technique if there is no other way to decide which process should continue (for example when programming with semaphores).

惊群简单来说就是多个进程或者线程在等待同一个事件，当事件发生时，所有线程和进程都会被内核唤醒。唤醒后通常只有一个进程获得了该事件并进行处理，其他进程发现获取事件失败后又继续进入了等待状态，在一定程度上降低了系统性能。

accept 惊群

具体来说惊群通常发生在服务器的监听等待调用上，服务器创建监听socket，后fork多个进程，在每个进程中调用accept或者epoll_wait等待终端的连接。

那么这个问题真的存在吗？

事实上，历史上，Linux 的 accpet 确实存在惊群问题，但现在的内核都解决该问题了。即，当多个进程/线程都阻塞在对同一个 socket 的 accept 调用上时，当有一个新的连接到来，内核只会唤醒一个进程，其他进程保持休眠，压根就不会被唤醒。

测试代码如下：

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>  
#include <sys/socket.h>  
#include <netinet/in.h>  
#include <arpa/inet.h>  
#include <assert.h>  
#include <sys/wait.h>
#include <string.h>
#include <errno.h>
#define IP   "127.0.0.1"
#define PORT  8888
#define WORKER 4
int worker(int listenfd, int i)
{
    while (1) {
        printf("I am worker %d, begin to accept connection.\n", i);
        struct sockaddr_in client_addr;  
        socklen_t client_addrlen = sizeof( client_addr );  
        int connfd = accept( listenfd, ( struct sockaddr* )&client_addr, &client_addrlen );  
        if (connfd != -1) {
            printf("worker %d accept a connection success.\t", i);
            printf("ip :%s\t",inet_ntoa(client_addr.sin_addr));
            printf("port: %d \n",client_addr.sin_port);
        } else {
            printf("worker %d accept a connection failed,error:%s", i, strerror(errno));
			close(connfd);
        }
    }
    return 0;
}
int main()
{
    int i = 0;
    struct sockaddr_in address;  
    bzero(&address, sizeof(address));  
    address.sin_family = AF_INET;  
    inet_pton( AF_INET, IP, &address.sin_addr);  
    address.sin_port = htons(PORT);  
    int listenfd = socket(PF_INET, SOCK_STREAM, 0);  
    assert(listenfd >= 0);  
    int ret = bind(listenfd, (struct sockaddr*)&address, sizeof(address));  
    assert(ret != -1);  
    ret = listen(listenfd, 5);  
    assert(ret != -1);  
    for (i = 0; i < WORKER; i++) {
        printf("Create worker %d\n", i+1);
        pid_t pid = fork();
        /*child  process */
        if (pid == 0) {
            worker(listenfd, i);
        }
        if (pid < 0) {
            printf("fork error");
        }
    }
    /*wait child process*/
    int status;
    wait(&status);
    return 0;
}

当我们对该服务器发起连接请求（用 telnet/curl 等模拟）时，会看到只有一个进程被唤醒。

epoll惊群

如上所述，accept 已经不存在惊群问题，但 epoll 上还是存在惊群问题。即，如果多个进程/线程阻塞在监听同一个 listening socket fd 的 epoll_wait 上，当有一个新的连接到来时，所有的进程都会被唤醒。

考虑如下场景：

主进程创建 socket, bind， listen 后，将该 socket 加入到 epoll 中，然后 fork 出多个子进程，每个进程都阻塞在 epoll_wait 上，如果有事件到来，则判断该事件是否是该 socket 上的事件，如果是，说明有新的连接到来了，则进行 accept 操作。为了简化处理，忽略后续的读写以及对 accept 返回的新的套接字的处理，直接断开连接。

那么，当新的连接到来时，是否每个阻塞在 epoll_wait 上的进程都会被唤醒呢？

很多博客中提到，测试表明虽然 epoll_wait 不会像 accept 那样只唤醒一个进程/线程，但也不会把所有的进程/线程都唤醒。

为了验证这个问题，我自己写了一个测试程序：

#include <sys/types.h>
#include <sys/socket.h>
#include <sys/epoll.h>
#include <netdb.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/wait.h>
#include <unistd.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#define IP   "127.0.0.1"
#define PORT  8888
#define PROCESS_NUM 4
#define MAXEVENTS 64
static int create_and_bind ()
{
    int fd = socket(PF_INET, SOCK_STREAM, 0);
    struct sockaddr_in serveraddr;
    serveraddr.sin_family = AF_INET;
    inet_pton( AF_INET, IP, &serveraddr.sin_addr);  
    serveraddr.sin_port = htons(PORT);
    bind(fd, (struct sockaddr*)&serveraddr, sizeof(serveraddr));
    return fd;
}
static int make_socket_non_blocking (int sfd)
{
    int flags, s;
    flags = fcntl (sfd, F_GETFL, 0);
    if (flags == -1) {
        perror ("fcntl");
        return -1;
    }
    flags |= O_NONBLOCK;
    s = fcntl (sfd, F_SETFL, flags);
    if (s == -1) {
        perror ("fcntl");
        return -1;
    }
    return 0;
}
void worker(int sfd, int efd, struct epoll_event *events, int k) {
    /* The event loop */
    while (1) {
        int n, i;
        n = epoll_wait(efd, events, MAXEVENTS, -1);
        //sleep(1);
        printf("worker  %d return from epoll_wait!\n", k);
        for (i = 0; i < n; i++) {
            if ((events[i].events & EPOLLERR) || (events[i].events & EPOLLHUP) || (!(events[i].events &EPOLLIN))) {
                /* An error has occured on this fd, or the socket is not ready for reading (why were we notified then?) */
                fprintf (stderr, "epoll error\n");
                close (events[i].data.fd);
                continue;
            } else if (sfd == events[i].data.fd) {
                /* We have a notification on the listening socket, which means one or more incoming connections. */
                struct sockaddr in_addr;
                socklen_t in_len;
                int infd;
                char hbuf[NI_MAXHOST], sbuf[NI_MAXSERV];
                in_len = sizeof in_addr;
                infd = accept(sfd, &in_addr, &in_len);
                if (infd == -1) {
                    printf("worker %d accept failed!\n", k);
                    break;
                }
                printf("worker %d accept successed!\n", k);
                /* Make the incoming socket non-blocking and add it to the list of fds to monitor. */
                close(infd); 
            }
        }
    }
}
int main (int argc, char *argv[])
{
    int sfd, s;
    int efd;
    struct epoll_event event;
    struct epoll_event *events;
    sfd = create_and_bind();
    if (sfd == -1) {
        abort ();
    }
    s = make_socket_non_blocking (sfd);
    if (s == -1) {
        abort ();
    }
    s = listen(sfd, SOMAXCONN);
    if (s == -1) {
        perror ("listen");
        abort ();
    }
    efd = epoll_create(MAXEVENTS);
    if (efd == -1) {
        perror("epoll_create");
        abort();
    }
    event.data.fd = sfd;
    event.events = EPOLLIN | EPOLLEXCLUSIVE;
    s = epoll_ctl(efd, EPOLL_CTL_ADD, sfd, &event);
    if (s == -1) {
        perror("epoll_ctl");
        abort();
    }
    /* Buffer where events are returned */
    events = (struct epoll_event*)calloc(MAXEVENTS, sizeof event);
    int k;
    for(k = 0; k < PROCESS_NUM; k++) {
        printf("Create worker %d\n", k+1);
        int pid = fork();
        if(pid == 0) {
            worker(sfd, efd, events, k);
        }
    }
    int status;
    wait(&status);
    free (events);
    close (sfd);
    return EXIT_SUCCESS;
}

运行server端后用telnet连，出现了2个进程被唤醒的情况，并不是每次都出现。

worker  3 return from epoll_wait!
worker 3 accept successed!
worker  2 return from epoll_wait!
worker 2 accept failed!

也就是说，到目前为止，还没有得到一个确定的答案。但后来，在下面这篇博客中看到这样一个评论：http://blog.csdn.net/spch2008/article/details/18301357

这个总结，需要进一步阐述，你的实验，看上去是只有4个进程唤醒了，而事实上，其余进程没有被唤醒的原因是你的某个进程已经处理完这个 accept，内核队列上已经没有这个事件，无需唤醒其他进程。你可以在 epoll 获知这个 accept 事件的时候，不要立即去处理，而是 sleep 下，这样所有的进程都会被唤起

看到这个评论后，我顿时如醍醐灌顶，重新修改了上面的测试程序，即在 epoll_wait 返回后，加了个 sleep 语句，这时再测试，果然发现所有的进程都被唤醒了。

worker  1 return from epoll_wait!
worker  3 return from epoll_wait!
worker 1 accept successed!
worker 3 accept failed!
worker  2 return from epoll_wait!
worker 2 accept failed!
worker  0 return from epoll_wait!
worker 0 accept failed!

所以，epoll_wait上的惊群确实是存在的。

为什么内核不处理 epoll 惊群

看到这里，我们可能有疑惑了，为什么内核对 accept 的惊群做了处理，而现在仍然存在 epoll 的惊群现象呢？

accept 确实应该只能被一个进程调用成功，内核很清楚这一点。但 epoll 不一样，他监听的文件描述符，除了可能后续被 accept 调用外，还有可能是其他网络 IO 事件的，而其他 IO 事件是否只能由一个进程处理，是不一定的，内核不能保证这一点，这是一个由用户决定的事情，例如可能一个文件会由多个进程来读写。所以，对 epoll 的惊群，内核则不予处理。

Nginx 是如何处理惊群问题的

使用EPOLLEXCLUSIVE

Linux 4.5解决了这一问题，使用EPOLLEXCLUSIVE标记，但我自己的系统还没这么新，留待之后验证。
http://www.man7.org/linux/man-pages/man2/epoll_ctl.2.html

小结

现在我们对惊群及 Nginx 的处理总结如下：

accept 不会有惊群(since linux2.6)，epoll_wait 才会。
Nginx 的 accept_mutex,并不是解决 accept 惊群问题，而是解决 epoll_wait 惊群问题。
说Nginx 解决了 epoll_wait 惊群问题，也是不对的，它只是控制是否将监听套接字加入到epoll 中。监听套接字只在一个子进程的 epoll 中，当新的连接来到时，其他子进程当然不会惊醒了。

自旋锁

自旋锁可以使线程在没有取得锁的时候，不被挂起，而转去执行一个空循环，（即所谓的自旋，就是自己执行空循环），若在若干个空循环后，线程如果可以获得锁，则继续执行。若线程依然不能获得锁，才会被挂起。

使用自旋锁后，线程被挂起的几率相对减少，线程执行的连贯性相对加强。因此，对于那些锁竞争不是很激烈，锁占用时间很短的并发线程，具有一定的积极意义，但对于锁竞争激烈，单线程锁占用很长时间的并发程序，自旋锁在自旋等待后，往往毅然无法获得对应的锁，不仅仅白白浪费了CPU时间，最终还是免不了被挂起的操作，反而浪费了系统的资源。

在JDK1.6中，Java虚拟机提供-XX:+UseSpinning参数来开启自旋锁，使用-XX:PreBlockSpin参数来设置自旋锁等待的次数。

在JDK1.7开始，自旋锁的参数被取消，虚拟机不再支持由用户配置自旋锁，自旋锁总是会执行，自旋锁次数也由虚拟机自动调整。

可能引起的问题：

过多占据CPU时间：如果锁的当前持有者长时间不释放该锁，那么等待者将长时间的占据cpu时间片，导致CPU资源的浪费，因此可以设定一个时间，当锁持有者超过这个时间不释放锁时，等待者会放弃CPU时间片阻塞；
死锁问题：试想一下，有一个线程连续两次试图获得自旋锁（比如在递归程序中），第一次这个线程获得了该锁，当第二次试图加锁的时候，检测到锁已被占用（其实是被自己占用），那么这时，线程会一直等待自己释放该锁，而不能继续执行，这样就引起了死锁。因此递归程序使用自旋锁应该遵循以下原则：递归程序决不能在持有自旋锁时调用它自己，也决不能在递归调用时试图获得相同的自旋锁。

阻塞锁

让线程进入阻塞状态进行等待，当获得相应的信号（唤醒，时间）时，才可以进入线程的准备就绪状态，准备就绪状态的所有线程，通过竞争，进入运行状态。。

JAVA中，能够进入\退出、阻塞状态或包含阻塞锁的方法有，synchronized 关键字（其中的重量锁），ReentrantLock，Object.wait()\notify()

可重入锁

可重入锁，也叫做递归锁，指的是同一线程外层函数获得锁之后，内层递归函数仍然有获取该锁的代码，但不受影响。
在JAVA环境下ReentrantLock和synchronized都是可重入锁

3、可重入锁

可重入锁，也叫做递归锁，指的是同一线程外层函数获得锁之后，内层递归函数仍然有获取该锁的代码，但不受影响。

public class Test implements Runnable{
	public synchronized void get(){
		System.out.println(Thread.currentThread().getId());
		set();
	}
	public synchronized void set(){
		System.out.println(Thread.currentThread().getId());
	}
	@Override
	public void run() {
		get();
	}
	public static void main(String[] args) {
		Test ss=new Test();
		new Thread(ss).start();
		new Thread(ss).start();
		new Thread(ss).start();
	}
}
public class Test implements Runnable {
	ReentrantLock lock = new ReentrantLock();
	public void get() {
		lock.lock();
		System.out.println(Thread.currentThread().getId());
		set();
		lock.unlock();
	}
	public void set() {
		lock.lock();
		System.out.println(Thread.currentThread().getId());
		lock.unlock();
	}
	@Override
	public void run() {
		get();
	}
	public static void main(String[] args) {
		Test ss = new Test();
		new Thread(ss).start();
		new Thread(ss).start();
		new Thread(ss).start();
	}
}

两个例子最后的结果都是正确的，即同一个线程id被连续输出两次。

结果如下：

Threadid: 8

Threadid: 10

Threadid: 9

可重入锁最大的作用是避免死锁

我们以自旋锁作为例子，

public class SpinLock {  
    private AtomicReference<Thread> owner =new AtomicReference<>();  
    public void lock(){  
        Thread current = Thread.currentThread();  
        while(!owner.compareAndSet(null, current)){  
        }  
    }  
    public void unlock (){  
        Thread current = Thread.currentThread();  
        owner.compareAndSet(current, null);  
    }  
}

对于自旋锁来说，

若有同一线程两调用lock() ，会导致第二次调用lock位置进行自旋，产生了死锁
说明这个锁并不是可重入的。（在lock函数内，应验证线程是否为已经获得锁的线程）
若1问题已经解决，当unlock（）第一次调用时，就已经将锁释放了。实际上不应释放锁。

（采用计数次进行统计）
修改之后，如下：

public class SpinLock1 {
	private AtomicReference<Thread> owner =new AtomicReference<>();
	private int count =0;
	public void lock(){
		Thread current = Thread.currentThread();
		if(current==owner.get()) {
			count++;
			return ;
		}
		while(!owner.compareAndSet(null, current)){
		}
	}
	public void unlock (){
		Thread current = Thread.currentThread();
		if(current==owner.get()){
			if(count!=0){
				count--;
			}else{
				owner.compareAndSet(current, null);
			}
		}
	}
}

该自旋锁即为可重入锁。

悲观锁和乐观锁

悲观锁(Pessimistic Lock), 顾名思义就是很悲观，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会block直到它拿到锁。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。独占锁是悲观锁的一种实现

乐观锁(Optimistic Lock), 顾名思义，就是很乐观，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号等机制。乐观锁适用于多读的应用类型，这样可以提高吞吐量，像数据库如果提供类似于write_condition机制的其实都是提供的乐观锁。使用CAS来保证,保证这个操作的原子性

两种锁各有优缺点，不可认为一种好于另一种，像乐观锁适用于写比较少的情况下，即冲突真的很少发生的时候，这样可以省去了锁的开销，加大了系统的整个吞吐量。但如果经常产生冲突，上层应用会不断的进行retry，这样反倒是降低了性能，所以这种情况下用悲观锁就比较合适。

读-写锁

Lock接口以及对象，使用它，很优雅的控制了竞争资源的安全访问，但是这种锁不区分读写，称这种锁为普通锁。为了提高性能，Java提供了读写锁，在读的地方使用读锁，在写的地方使用写锁，灵活控制，如果没有写锁的情况下，读是无阻塞的,在一定程度上提高了程序的执行效率。

Java中读写锁有个接口java.util.concurrent.locks.ReadWriteLock，也有具体的实现ReentrantReadWriteLock，详细的API可以查看JavaAPI文档。

ReentrantReadWriteLock 和 ReentrantLock 不是继承关系，但都是基于 AbstractQueuedSynchronizer 来实现。lock方法是基于CAS来实现的

ReadWriteLock中暴露了两个Lock对象：
在读写锁的加锁策略中，允许多个读操作同时进行，但每次只允许一个写操作。读写锁是一种性能优化的策略。
RentrantReadWriteLock在构造时也可以选择是一个非公平的锁（默认）还是公平的锁。

进程的内存空间布局

进程的内存布局在结构上是有规律的，具体来说对于 linux 系统上的进程，其内存空间一般可以粗略地分为以下几大段【1】，从高内存到低内存排列：

内核态内存空间，其大小一般比较固定（可以编译时调整），但 32 位系统和 64 位系统的值不一样。
用户态的堆栈，大小不固定，可以用 ulimit -s 进行调整，默认一般为 8M，从高地址向低地址增长。
mmap 区域，进程茫茫内存空间里的主要部分，既可以从高地址到低地址延伸(所谓 flexible layout)，也可以从低到高延伸(所谓 legacy layout)，看进程具体情况【2】【3】。
brk 区域，紧邻数据段(甚至贴着)，从低位向高位伸展，但它的大小主要取决于 mmap 如何增长，一般来说，即使是 32 位的进程以传统方式延伸，也有差不多 1 GB 的空间（准确地说是 TASK_SIZE/3 - 代码段数据段，参看 arch/x86/include/asm/processor.h 里的定义)【4】
数据段，主要是进程里初始化和未初始化的全局数据总和，当然还有编译器生成一些辅助数据结构等等)，大小取决于具体进程，其位置紧贴着代码段。
代码段，主要是进程的指令，包括用户代码和编译器生成的辅助代码，其大小取决于具体程序，但起始位置根据 32 位还是 64 位一般固定(-fPIC, -fPIE等除外【5】)。

参考文献

编译过程预览

预处理

预处理(Prepressing) : -E 表示只进行预处理, 即 : gcc –E hello.c –o hello.i
- 展开所有 #define 定义的宏
- 处理所有条件预编译指令,如 #if, #ifdef
- 递归的将 #include 的文件插入到该预编译文件中
- 删除各类注释
- 添加行和文件标识,如 #2 “hello.c” 2 ,用于调试或编译出错报警
- 保留所有的 #pragma 编译指令,编译器要使用
对于C++ 来说,预处理后的文件扩展名是 .ii

编译

编译(Compilation): gcc –S hello.i –o hello.s
编译过程就是把预处理完的文件进行一系列词法分析,语法分析,语义分析及优化后生成相应的汇编代码文件.
现在的gcc 把预处理和编译两个步骤合成一个步骤,C语言使用一个叫做 cc1 的程序来完成,C++则是 cc1plus ,位于 /usr/libexec/gcc/x86_64-redhat-linux/4.1.2/
gcc 实际上是这些后台程序的包装,它会根据参数要求去调用 cc1(cclplus), 汇编器 as 和链接器 ld

链接

链接(Linking):解决一个程序被分割成多个模块后,模块间最后如何组合成一个单一程序的问题.
链接的主要任务是把各个模块之间相互引用的部分处理好,使各个模块之间能正确的衔接.

查看某个进程的线程数量

根据进程号进行查询：
- pstree -p 进程号

example:

chris@ubuntu:~/myspace/test/network$ pstree -p 5629
test05(5629)─┬─{test05}(5630)
             ├─{test05}(5631)
             ├─{test05}(5632)
             └─{test05}(5633)

top -Hp 进程号

 PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND 
  5629 chris     20   0 47680 1420 1188 S    0  0.1   0:00.02 test05                                          
 5630 chris     20   0 47680 1420 1188 S    0  0.1   0:00.00 test05                                          
 5631 chris     20   0 47680 1420 1188 S    0  0.1   0:00.03 test05                                          
 5632 chris     20   0 47680 1420 1188 S    0  0.1   0:00.00 test05                                          
 5633 chris     20   0 47680 1420 1188 S    0  0.1   0:00.00 test05
 ``` 
2. 根据进程名字进行查询：

pstree -p `ps -e | grep test05 | awk '{print $1}'`

pstree -p `ps -e | grep test05 | awk '{print $1}'` | wc -l

```
执行效果和上面的命令是一样的

概述

一些场景希望同样的请求尽量落到一台机器上，比如访问缓存集群时，我们往往希望同一种请求能落到同一个后端上，以充分利用其上已有的缓存，不同的机器承载不同的稳定working set。而不是随机地散落到所有机器上，那样的话会迫使所有机器缓存所有的内容，最终由于存不下形成颠簸而表现糟糕。我们都知道hash能满足这个要求，比如当有n台服务器时，输入x总是会发送到第hash(x) % n台服务器上。但当服务器变为m台时，hash(x) % n和hash(x) % m很可能都不相等，这会使得几乎所有请求的发送目的地都发生变化，如果目的地是缓存服务，所有缓存将失效，继而对原本被缓存遮挡的数据库或计算服务造成请求风暴，触发雪崩。一致性哈希是一种特殊的哈希算法，在增加服务器时，发向每个老节点的请求中只会有一部分转向新节点，从而实现平滑的迁移。这篇论文中提出了一致性hash的概念。

一致性hash满足以下四个性质：

平衡性 (Balance) : 每个节点被选到的概率是O(1/n)。
单调性 (Monotonicity) : 当新节点加入时，不会有请求在老节点间移动，只会从老节点移动到新节点。当有节点被删除时，也不会影响落在别的节点上的请求。
分散性 (Spread) : 当上游的机器看到不同的下游列表时(在上线时及不稳定的网络中比较常见), 同一个请求尽量映射到少量的节点中。
负载 (Load) : 当上游的机器看到不同的下游列表的时候，保证每台下游分到的请求数量尽量一致。

算法实现

所有server的32位hash值在32位整数值域上构成一个环(Hash Ring)，环上的每个区间和一个server唯一对应，如果一个key落在某个区间内，它就被分流到对应的server上。

当删除一个server的，它对应的区间会归属于相邻的server，所有的请求都会跑过去。当增加一个server时，它会分割某个server的区间并承载落在这个区间上的所有请求。单纯使用Hash Ring很难满足我们上节提到的属性，主要两个问题：

在机器数量较少的时候，区间大小会不平衡。
当一台机器故障的时候，它的压力会完全转移到另外一台机器，可能无法承载。
为了解决这个问题，我们为每个server计算m个hash值，从而把32位整数值域划分为n*m个区间，当key落到某个区间时，分流到对应的server上。那些额外的hash值使得区间划分更加均匀，被称为Virtual Node。当删除一个server时，它对应的m个区间会分别合入相邻的区间中，那个server上的请求会较为平均地转移到其他server上。当增加server时，它会分割m个现有区间，从对应server上分别转移一些请求过来。

Raft一致性算法

发表于 2018-03-07 | 分类于分布式系统

一致性问题

在分布式系统中,一致性问题(consensus problem)是指对于一组服务器，给定一组操作，我们需要一个协议使得最后它们的结果达成一致。

在理论计算机科学中，计算机科学家Eric Brewer之后命名为布鲁尔定理的CAP定理指出，分布式数据存储不可能同时提供以下三种保证中的两种以上：

一致性	可用性	分区容忍
在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本）	在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。（对数据更新具备高可用性）	以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择。

换句话说，CAP定理指出，在存在网络分区的情况下，必须在一致性和可用性之间进行选择。请注意，CAP定理中定义的一致性与ACID 数据库事务中保证的一致性完全不同。

由于CAP理论告诉我们对于分布式系统，如果不想牺牲一致性，我们就只能放弃可用性，所以，数据一致性模型主要有以下几种：强一致性、弱一致性和最终一致性等，在本篇章中，我们主要讨论的算法Raft，是一种分布式系统中的强一致性的实现算法。

强一致性的一般实现的原理：当其中某个服务器收到客户端的一组指令时,它必须与其它服务器交流以保证所有的服务器都是以同样的顺序收到同样的指令,这样的话所有的服务器会产生一致的结果,看起来就像是一台机器一样.

Raft算法描述

在Raft被提出来之前，Paxos协议是第一个被证明的一致性算法，但是Paxos的论文非常难懂，导致基于Paxos的工程实践和教学都十分头疼，于是Raft在设计的过程中，就从可理解性出发，使用算法分解和减少状态等手段，目前已经应用非常广泛。

在Raft中，问题分解为：领导选取、日志复制、安全和成员变化。

复制状态机（Replicated State Machine）

复制状态机通过复制日志来实现：
- 日志：每台机器保存一份日志，日志来自于客户端的请求，包含一系列的命令
- 状态机：状态机会按顺序执行这些命令
- 一致性模型：分布式环境下，保证多机的日志是一致的，这样回放到状态机中的状态是一致的
一致性算法作用于一致性模型，一般有以下特性：
- safety：在非拜占庭问题下（网络延时，网络分区，丢包，重复发包以及包乱序等），结果是正确的
- availability：在半数以上机器能正常工作时，则系统可用
- timing-unindependent：不依赖于时钟来保证日志一致性，错误的时钟以及极端的消息时延最多会造成可用性问题

服务器状态

每台服务器一定会处于三种状态：

领导者
候选人
追随者

追随者只响应其他服务器的请求。如果追随者没有收到任何消息，它会成为一个候选人并且开始一次选举。收到大多数服务器投票的候选人会成为新的领导人。领导人在它们宕机之前会一直保持领导人的状态。

任期(Term)

Raft 算法将时间划分成为任意不同长度的任期（term）。任期用连续的数字进行表示。每一个任期的开始都是一次选举（election），一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举，它就会在该任期的剩余时间担任领导人。在某些情况下，选票会被瓜分，有可能没有选出领导人，那么，将会开始另一个任期，并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最多只有一个领导人。

RPC

Raft 算法中服务器节点之间通信使用远程过程调用（RPCs），并且基本的一致性算法只需要两种类型的 RPCs。请求投票（RequestVote） RPCs 由候选人在选举期间发起，然后附加条目（AppendEntries）RPCs 由领导人发起，用来复制日志和提供一种心跳机制。为了在服务器之间传输快照增加了第三种 RPC。当服务器没有及时的收到 RPC 的响应时，会进行重试，并且他们能够并行的发起 RPCs 来获得最佳的性能。
RPC有三种：

RequestVote RPC：候选人在选举期间发起
AppendEntries RPC：领导人发起的一种心跳机制，复制日志也在该命令中完成
InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者。

超时设置：

BroadcastTime: 领导者的心跳超时时间
Election Timeout: 追随者设置的候选超时时间
MTBT: 指的是单个服务器发生故障的间隔时间的平均数
BroadcastTime << ElectionTimeout << MTBF

两个原则：

BroadcastTime应该比ElectionTimeout小一个数量级，为的是使领导人能够持续发送心跳信息（heartbeat）来阻止追随者们开始选举；
ElectionTimeout也要比MTBF小几个数量级，为的是使得系统稳定运行。
一般BroadcastTime大约为0.5毫秒到20毫秒，ElectionTimeout一般在10ms到500ms之间。大多数服务器的MTBF都在几个月甚至更长。

领导人选取

触发条件：

一般情况下，追随者接到领导者的心跳时，把ElectionTimeout清零，不会触发；
领导者故障，追随者的ElectionTimeout超时发生时，会变成候选者，触发领导人选取；

候选操作过程：

追随者自增当前任期，转换为Candidate，对自己投票，并发起RequestVote RPC，等待下面三种情形发生；

获得超过半数服务器的投票，赢得选举，成为领导者；
另一台服务器赢得选举，并接收到对应的心跳，成为追随者；
选举超时，没有任何一台服务器赢得选举，自增当前任期，重新发起选举；

注意事项：

服务器在一个任期内，最多能给一个候选人投票，采用先到先服务原则；
候选者等待投票时，可能会接收到来自其它声明为领导人的的AppendEntries RPC。如果该领导人的任期（RPC中有）比当前候选人的当前任期要大，则候选人认为该领导人合法，并转换成追随者；如果RPC中的任期小于候选人的当前任期，则候选人拒绝此次RPC，继续保持候选人状态；
候选人既没有赢得选举也没有输掉选举：如果许多追随者在同一时刻都成为了候选人，选票会被分散，可能没有候选人能获得大多数的选票。当这种情形发生时，每一个候选人都会超时，并且通过自增任期号和发起另一轮 RequestVote RPC 来开始新的选举。然而，如果没有其它手段来分配选票的话，这种情形可能会无限的重复下去。所以Raft使用的随机的选举超时时间（150~300ms之间），来避免这种情况发生。

日志复制

接受命令的过程：

领导者接受客户端请求；
领导者把指令追加到日志；
发送AppendEntries RPC到追随者；
领导者收到大多数追随者的确认后，领导者Commit该日志，把日志在状态机中回放，并返回结果给客户端；

提交过程：

在下一个心跳阶段，领导者再次发送AppendEntries RPC给追随者，日志已经commited；
追随者收到Commited日志后，将日志在状态机中回放。

安全性

到目前为止描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令，例如：一个跟随者可能会进入不可用状态同时领导人已经提交了若干的日志条目，然后这个跟随者可能会被选举为领导人并且覆盖这些日志条目；因此，不同的状态机可能会执行不同的指令序列。

领导者追加日志（Append-Only)
领导者永远不会覆盖已经存在的日志条目；
日志永远只有一个流向：从领导者到追随者；
选举限制：投票阻止没有全部日志条目的服务器赢得选举
如果投票者的日志比候选人的新，拒绝投票请求；
这意味着要赢得选举，候选者的日志至少和大多数服务器的日志一样新，那么它一定包含全部的已经提交的日志条目。
永远不提交任期之前的日志条目（只提交任期内的日志条目）
在Raft算法中，当一个日志被安全的复制到绝大多数的机器上面，即AppendEntries RPC在绝大多数服务器正确返回了，那么这个日志就是被提交了，然后领导者会更新commit index。

如果允许提交任期之前的日志条目，那么在步骤c中，我们就会把之前任期为2的日志提交到其他服务器中去，并造成了大多数机器存在了日志为2的情况。所以造成了d中S5中任期为3的日志条目会覆盖掉已经提交的日志的情况。

Raft 从来不会通过计算复制的数目来提交之前人气的日志条目。只有领导人当前任期的日志条目才能通过计算数目来进行提交。一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配原则（Log Matching Property），之前的日志条目也都会被间接的提交。

论文中的这段话比较难理解，更加直观的说：由于Raft不会提交任期之前的日志条目，那么就不会从b过渡到c的情况，只能从b发生S5down机的情况下直接过渡到e，这样就产生的更新的任期，这样S5就没有机会被选为领导者了。

候选者和追随者崩溃
候选者和追随者崩溃的情况处理要简单的多。如果这类角色崩溃了，那么后续发送给他们的 RequestVote和AppendEntries的所有RCP都会失败，Raft算法中处理这类失败就是简单的无限重试的方式。
　　如果这些服务器重新可用，那么这些RPC就会成功返回。如果一个服务器完成了一个RPC，但是在响应Leader前崩溃了，那么当他再次可用的时候还会收到相同的RPC请求，此时接收服务器负责检查，比如如果收到了已经包含该条日志的RPC请求，可以直接忽略这个请求，确保对系统是无害的。

集群成员变更

集群成员的变更和成员的宕机与重启不同，因为前者会修改成员个数进而影响到领导者的选取和决议过程，因为在分布式系统这对于majority这个集群中成员大多数的概念是极为重要的。

简单的做法是，运维人员将系统临时下线，修改配置，重新上线。但是这种做法存在两个缺点：

更改时集群不可用
人为操作失误风险
直接从一种配置转到新的配置是十分不安全的
如下图所示：

因为各个机器可能在任何的时候进行转换。在这个例子中，集群配额从 3 台机器变成了 5 台。不幸的是，存在这样的一个时间点，两个不同的领导人在同一个任期里都可以被选举成功。一个是通过旧的配置，一个通过新的配置。

两阶段方法保证安全性：
为了保证安全性，配置更改必须使用两阶段方法。在 Raft 中，集群先切换到一个过渡的配置，我们称之为共同一致；一旦共同一致已经被提交了，那么系统就切换到新的配置上。共同一致是老配置和新配置的结合。

共同一致允许独立的服务器在不影响安全性的前提下，在不同的时间进行配置转换过程。此外，共同一致可以让集群在配置转换的过程人依然响应服务器请求。

一个领导人接收到一个改变配置从 C-old 到 C-new 的请求，他会为了共同一致存储配置（图中的 C-old,new），以前面描述的日志条目和副本的形式。一旦一个服务器将新的配置日志条目增加到它的日志中，他就会用这个配置来做出未来所有的决定。领导人完全特性保证了只有拥有 C-old,new 日志条目的服务器才有可能被选举为领导人。当C-old,new日志条目被提交以后，领导人在使用相同的策略提交C-new，如下图所示，C-old 和 C-new 没有任何机会同时做出单方面的决定，这就保证了安全性。

一个配置切换的时间线。虚线表示已经被创建但是还没有被提交的条目，实线表示最后被提交的日志条目。领导人首先创建了 C-old,new 的配置条目在自己的日志中，并提交到 C-old,new 中（C-old,new 的大多数和 C-new 的大多数）。然后他创建 C-new 条目并提交到 C-new 中的大多数。这样就不存在 C-new 和 C-old 可以同时做出决定的时间点。

日志压缩

日志会随着系统的不断运行会无限制的增长，这会给存储带来压力，几乎所有的分布式系统(Chubby、ZooKeeper)都采用快照的方式进行日志压缩，做完快照之后快照会在稳定持久存储中保存，而快照之前的日志和快照就可以丢弃掉。

Raft的具体做法如下图所示：

与Raft其它操作Leader-Based不同，snapshot是由各个节点独立生成的。除了日志压缩这一个作用之外，snapshot还可以用于同步状态：slow-follower以及new-server，Raft使用InstallSnapshot RPC完成该过程，不再赘述。

Client交互
Client只向领导者发送请求；
Client开始会向追随者发送请求，追随者拒绝Client的请求，并重定向到领导者；
Client请求失败，会超时重新发送请求；
Raft算法要求Client的请求线性化，防止请求被多次执行。有两个解决方案：

Raft算法提出要求每个请求有个唯一标识；
Raft的请求保持幂等性；

内存管理比较:ptmalloc & tcmalloc & jemalloc

发表于 2018-02-28 | 分类于 OS

介绍

系统的物理内存是有限的，而对内存的需求是变化的, 程序的动态性越强，内存管理就越重要，选择合适的内存管理算法会带来明显的性能提升。
比如nginx，它在每个连接accept后会malloc一块内存，作为整个连接生命周期内的内存池。当HTTP请求到达的时候，又会malloc一块当前请求阶段的内存池, 因此对malloc的分配速度有一定的依赖关系。(而apache的内存池是有父子关系的，请求阶段的内存池会和连接阶段的使用相同的分配器，如果连接内存池释放则请求阶段的子内存池也会自动释放)。

内存管理可以分为三个层次，自底向上分别是：

操作系统内核的内存管理
glibc层使用系统调用维护的内存管理算法
应用程序从glibc动态分配内存后，根据应用程序本身的程序特性进行优化，比如使用引用计数std::shared_ptr，apache的内存池方式等等。
当然应用程序也可以直接使用系统调用从内核分配内存，自己根据程序特性来维护内存，但是会大大增加开发成本。

一个优秀的通用内存分配器应具有以下特性:

额外的空间损耗尽量少
分配速度尽可能快
尽量避免内存碎片
缓存本地化友好
通用性，兼容性，可移植性，易调试

目前大部分服务端程序使用glibc提供的malloc/free系列函数，而glibc使用的ptmalloc2在性能上远远弱后于google的tcmalloc和facebook的jemalloc。而且后两者只需要使用LD_PRELOAD环境变量启动程序即可，甚至并不需要重新编译。

glibc ptmalloc2

ptmalloc原理

系统调用接口

上图是 x86_64 下 Linux 进程的默认地址空间, 对 heap 的操作, 操作系统提供了brk()系统调用，设置了Heap的上边界；对 mmap 映射区域的操作,操作系统供了 mmap()和 munmap()函数。
因为系统调用的代价很高，不可能每次申请内存都从内核分配空间，尤其是对于小内存分配。而且因为mmap的区域容易被munmap释放，所以一般大内存采用mmap()，小内存使用brk()。

多线程支持

Ptmalloc2有一个主分配区(main arena)，有多个非主分配区。非主分配区只能使用mmap向操作系统批发申请HEAP_MAX_SIZE（64位系统为64MB）大小的虚拟内存。当某个线程调用malloc的时候，会先查看线程私有变量中是否已经存在一个分配区，如果存在则尝试加锁，如果加锁失败则遍历arena链表试图获取一个没加锁的arena，如果依然获取不到则创建一个新的非主分配区。
free()的时候也要获取锁。分配小块内存容易产生碎片，ptmalloc在整理合并的时候也要对arena做加锁操作。在线程多的时候，锁的开销就会增大。

ptmalloc内存管理

用户请求分配的内存在ptmalloc中使用chunk表示，每个chunk至少需要8个字节额外的开销。用户free掉的内存不会马上归还操作系统，ptmalloc会统一管理heap和mmap区域的空闲chunk，避免了频繁的系统调用。
ptmalloc 将相似大小的 chunk 用双向链表链接起来, 这样的一个链表被称为一个 bin。Ptmalloc 一共维护了 128 个 bin,并使用一个数组来存储这些 bin(如下图所示)。

数组中的第一个为 unsorted bin, 数组中从 2 开始编号的前 64 个 bin 称为 small bins, 同一个small bin中的chunk具有相同的大小。small bins后面的bin被称作large bins。

当free一个chunk并放入bin的时候， ptmalloc 还会检查它前后的 chunk 是否也是空闲的, 如果是的话,ptmalloc会首先把它们合并为一个大的 chunk, 然后将合并后的 chunk 放到 unstored bin 中。另外ptmalloc 为了提高分配的速度,会把一些小的(不大于64B) chunk先放到一个叫做 fast bins 的容器内。
在fast bins和bins都不能满足需求后，ptmalloc会设法在一个叫做top chunk的空间分配内存。对于非主分配区会预先通过mmap分配一大块内存作为top chunk，当bins和fast bins都不能满足分配需要的时候, ptmalloc会设法在top chunk中分出一块内存给用户, 如果top chunk本身不够大, 分配程序会重新mmap分配一块内存chunk, 并将 top chunk 迁移到新的chunk上，并用单链表链接起来。如果free()的chunk恰好与 top chunk 相邻,那么这两个 chunk 就会合并成新的 top chunk，如果top chunk大小大于某个阈值才还给操作系统。主分配区类似，不过通过sbrk()分配和调整top chunk的大小，只有heap顶部连续内存空闲超过阈值的时候才能回收内存。
需要分配的 chunk 足够大,而且 fast bins 和 bins 都不能满足要求,甚至 top chunk 本身也不能满足分配需求时,ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。

ptmalloc分配流程

ptmalloc的缺陷

后分配的内存先释放,因为 ptmalloc 收缩内存是从 top chunk 开始,如果与 top chunk 相邻的 chunk 不能释放, top chunk 以下的 chunk 都无法释放。
多线程锁开销大，需要避免多线程频繁分配释放。
内存从thread的areana中分配，内存不能从一个arena移动到另一个arena，就是说如果多线程使用内存不均衡，容易导致内存的浪费。比如说线程1使用了300M内存，完成任务后glibc没有释放给操作系统，线程2开始创建了一个新的arena，但是线程1的300M却不能用了。
每个chunk至少8字节的开销很大
不定期分配长生命周期的内存容易造成内存碎片，不利于回收。 64位系统最好分配32M以上内存，这是使用mmap的阈值。

tcmalloc

tcmalloc是Google开源的一个内存管理库，作为glibc malloc的替代品。目前已经在chrome、safari等知名软件中运用。
根据官方测试报告，ptmalloc在一台2.8GHz的P4机器上（对于小对象）执行一次malloc及free大约需要300纳秒。而TCMalloc的版本同样的操作大约只需要50纳秒。

小对象分配

tcmalloc为每个线程分配了一个线程本地ThreadCache，小内存从ThreadCache分配，此外还有个中央堆（CentralCache），ThreadCache不够用的时候，会从CentralCache中获取空间放到ThreadCache中。
小对象（<=32K）从ThreadCache分配，大对象从CentralCache分配。大对象分配的空间都是4k页面对齐的，多个pages也能切割成多个小对象划分到ThreadCache中。

小对象有将近170个不同的大小分类(class)，每个class有个该大小内存块的FreeList单链表，分配的时候先找到best fit的class，然后无锁的获取该链表首元素返回。如果链表中无空间了，则到CentralCache中划分几个页面并切割成该class的大小，放入链表中。

CentralCache分配管理

大对象(>32K)先4k对齐后，从CentralCache中分配。 CentralCache维护的PageHeap如下图所示，数组中第256个元素是所有大于255个页面都挂到该链表中。
当best fit的页面链表中没有空闲空间时，则一直往更大的页面空间则，如果所有256个链表遍历后依然没有成功分配。则使用sbrk, mmap, /dev/mem从系统中分配。
tcmalloc PageHeap管理的连续的页面被称为span.
如果span未分配，则span是PageHeap中的一个链表元素
如果span已经分配，它可能是返回给应用程序的大对象，或者已经被切割成多小对象，该小对象的size-class会被记录在span中
在32位系统中，使用一个中央数组(central array)映射了页面和span对应关系，数组索引号是页面号，数组元素是页面所在的span。在64位系统中，使用一个3-level radix tree记录了该映射关系。

回收

当一个object free的时候，会根据地址对齐计算所在的页面号，然后通过central array找到对应的span。
如果是小对象，span会告诉我们他的size class，然后把该对象插入当前线程的ThreadCache中。如果此时ThreadCache超过一个预算的值（默认2MB），则会使用垃圾回收机制把未使用的object从ThreadCache移动到CentralCache的central free lists中。
如果是大对象，span会告诉我们对象锁在的页面号范围。假设这个范围是[p,q]，先查找页面p-1和q+1所在的span，如果这些临近的span也是free的，则合并到[p,q]所在的span，然后把这个span回收到PageHeap中。
CentralCache的central free lists类似ThreadCache的FreeList，不过它增加了一级结构，先根据size-class关联到spans的集合，然后是对应span的object链表。如果span的链表中所有object已经free，则span回收到PageHeap中。

tcmalloc的改进

ThreadCache会阶段性的回收内存到CentralCache里。解决了ptmalloc2中arena之间不能迁移的问题。
Tcmalloc占用更少的额外空间。例如，分配N个8字节对象可能要使用大约8N * 1.01字节的空间。即，多用百分之一的空间。Ptmalloc2使用最少8字节描述一个chunk。
更快。小对象几乎无锁， >32KB的对象从CentralCache中分配使用自旋锁。并且>32KB对象都是页面对齐分配，多线程的时候应尽量避免频繁分配，否则也会造成自旋锁的竞争和页面对齐造成的浪费。

Jemalloc

jemalloc是facebook推出的，最早的时候是freebsd的libc malloc实现。目前在firefox、facebook服务器各种组件中大量使用。

jemalloc原理

与tcmalloc类似，每个线程同样在<32KB的时候无锁使用线程本地cache。
Jemalloc在64bits系统上使用下面的size-class分类：
- Small: [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840]
- Large: [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]
- Huge: [4 MiB, 8 MiB, 12 MiB, …]
small/large对象查找metadata需要常量时间， huge对象通过全局红黑树在对数时间内查找。
虚拟内存被逻辑上分割成chunks（默认是4MB，1024个4k页），应用线程通过round-robin算法在第一次malloc的时候分配arena，每个arena都是相互独立的，维护自己的chunks， chunk切割pages到small/large对象。free()的内存总是返回到所属的arena中，而不管是哪个线程调用free()。

上图可以看到每个arena管理的arena chunk结构，开始的header主要是维护了一个page map（1024个页面关联的对象状态）， header下方就是它的页面空间。 Small对象被分到一起， metadata信息存放在起始位置。 large chunk相互独立，它的metadata信息存放在chunk header map中。
- 通过arena分配的时候需要对arena bin（每个small size-class一个，细粒度）加锁，或arena本身加锁。
  并且线程cache对象也会通过垃圾回收指数退让算法返回到arena中。

jemalloc的优化

Jmalloc小对象也根据size-class，但是它使用了低地址优先的策略，来降低内存碎片化。
Jemalloc大概需要2%的额外开销。（tcmalloc 1%， ptmalloc最少8B）
Jemalloc和tcmalloc类似的线程本地缓存，避免锁的竞争
相对未使用的页面，优先使用dirty page，提升缓存命中。

参考文献

MySQL索引原理剖析

发表于 2018-02-27 | 分类于 MySQL

本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。

文章主要内容分为三个部分。

第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。
第二部分结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。
第三部分根据上面的理论基础，讨论MySQL中高性能使用索引的策略。

数据结构及算法基础

索引的本质

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是一种数据结构。

数据库查询是数据库的主要功能之一，最基本的查询算法是顺序查找（linear search）时间复杂度为O(n)，显然在数据量很大时效率很低。优化的查找算法如二分查找（binary search）、二叉树查找（binary tree search）等，虽然查找效率提高了。但是各自对检索的数据都有要求：二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织）。所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。

看一个例子：

图1展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，原因会在下文介绍。

B-Tree和B+Tree

关于B树和B+树请参考关于B树的一些总结，这篇文章介绍的比较详细，同时容易理解。

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，在本文的下一节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此广泛用于索引，这一节先单纯从数据结构角度描述它们。

B-Tree

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：

d>=2，即B-Tree的度；
h为B-Tree的高；
每个非叶子结点由n-1个key和n个指针组成，其中d<=n<=2d；
每个叶子结点至少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶结点的指针均为NULL；
所有叶结点都在同一层，深度等于树高h；
key和指针相互间隔，结点两端是指针；
一个结点中的key从左至右非递减排列；
如果某个指针在结点node最左边且不为null，则其指向结点的所有key小于v(key1)，其中v(key1)为node的第一个key的值。
如果某个指针在结点node最右边且不为null，则其指向结点的所有key大于v(keym)，其中v(keym)为node的最后一个key的值。
如果某个指针在结点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向结点的所有key小于v(keyi+1)且大于v(keyi)。
图2是一个d=2的B-Tree示意图。

由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。B-Tree上查找算法的伪代码如下：

BTree_Search(node, key) {
    if(node == null) return null;
    foreach(node.key)
    {
        if(node.key[i] == key) return node.data[i];
            if(node.key[i] > key) return BTree_Search(point[i]->node);
    }
    return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找结点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。

B+Tree

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比，B+Tree有以下不同点：

每个结点的指针上限为2d而不是2d+1。
内结点不存储data，只存储key；叶子结点不存储指针。
图3是一个简单的B+Tree示意。

由于并不是所有节点都具有相同的域，因此B+Tree中叶结点和内结点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个结点的域和上限是一致的，所以在实现中B-Tree往往对每个结点申请同等大小的空间。

一般来说，B+Tree比B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下面讨论。

带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

如图4所示，在B+Tree的每个叶子结点增加一个指向相邻叶子结点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着结点和指针顺序遍历就可以一次性访问到所有数据结点，极大提到了区间查询效率。

这一节对B-Tree和B+Tree进行了一个简单的介绍，下一节结合存储器存取原理介绍为什么目前B+Tree是数据库系统实现索引的首选数据结构。

为什么使用B-Tree（B+Tree）

上文说过，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理。

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

主存的存取过程如下：

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。

磁盘存取原理

上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。

图6是磁盘的整体结构示意图。

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

图7是磁盘结构的示意图。

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

B-/+Tree索引的性能分析

从使用磁盘I/O次数评价索引结构的优劣性：根据B-Tree的定义，可知检索一次最多需要访问h个结点。数据库系统的设计者巧妙的利用了磁盘预读原理，将一个结点的大小设为等于一个页面，这样每个结点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建结点时，直接申请一个页面的空间，这样可以保证一个结点的大小等于一个页面，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O（根结点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出读d是非常大的数字，通常超过100，因此h非常小。

综上所述，用B-Tree作为索引结构效率是非常高的。

而红黑树结构，h明显要深得多。由于逻辑上很近的结点（父子结点）物理上可能离得很远，无法利用局部性原理。所以即使红黑树的I/O渐进复杂度也为O(h)，但是查找效率明显比B-Tree差得多。

B+Tree更适合外存索引，是和内结点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于结点内key和data的大小：dmax=floor(pagesize/(keysize+datasize+pointsize))。

floor表示向下取整。由于B+Tree内结点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。

这一章从理论角度讨论了与索引相关的数据结构与算法问题，下一章将讨论B+Tree是如何具体实现为MySQL中索引，同时将结合MyISAM和InnDB存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。

MySQL索引实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本文主要讨论MyISAM和InnoDB两个存储引擎(MySQL数据库MyISAM和InnoDB存储引擎的比较)的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶结点的data域存放的是数据记录的地址。下面是MyISAM索引的原理图：

这里设表一共有三列，假设我们以Col1为主键，则图8是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶结点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

图10是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶结点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

聚簇索引 & 非聚簇索引

定义

聚簇索引的数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。
非聚簇索引，叶级页指向表中的记录，记录的物理顺序与逻辑顺序没有必然的联系

在mysql数据库中，myisam引擎和innodb引擎使用的索引类型不同，myisam对应的是非聚簇索引，而innodb对应的是聚簇索引。聚簇索引也叫复合索引、聚集索引等等。

适用场景

在聚簇索引中，数据会被按照顺序整理排列，当使用where进行顺序、范围、大小检索时，会大大加速检索效率。非聚簇索引在存储时不会对数据进行排序，相对产生的数据文件体积也比较大。

redis-analysis-sentinel01

发表于 2018-02-26

He Lei

c/c++/python | redis | recommend algorithm | search engine

GitHub Weibo

什么叫惊群现象

accept 惊群

epoll惊群

为什么内核不处理 epoll 惊群

Nginx 是如何处理惊群问题的

使用EPOLLEXCLUSIVE

小结

自旋锁

阻塞锁

可重入锁

悲观锁和乐观锁

读-写锁

进程的内存空间布局

参考文献

编译过程预览

预处理

编译

链接

查看某个进程的线程数量

pstree -p 进程号

top -Hp 进程号

pstree -p ps -e | grep test05 | awk '{print $1}'

pstree -p ps -e | grep test05 | awk '{print $1}' | wc -l

概述

算法实现

一致性问题

Raft算法描述

复制状态机（Replicated State Machine）

服务器状态

任期(Term)

RPC

领导人选取

日志复制

安全性

集群成员变更

日志压缩

介绍

glibc ptmalloc2

ptmalloc原理

系统调用接口

多线程支持

ptmalloc内存管理

ptmalloc分配流程

ptmalloc的缺陷

tcmalloc

小对象分配

CentralCache分配管理

回收

tcmalloc的改进

Jemalloc

jemalloc原理

jemalloc的优化

参考文献

数据结构及算法基础

索引的本质

B-Tree和B+Tree

B-Tree

B+Tree

带有顺序访问指针的B+Tree

为什么使用B-Tree（B+Tree）

主存存取原理

磁盘存取原理

局部性原理与磁盘预读

B-/+Tree索引的性能分析

MySQL索引实现

MyISAM索引实现

InnoDB索引实现

聚簇索引 & 非聚簇索引

定义

适用场景

pstree -p `ps -e | grep test05 | awk '{print $1}'`

pstree -p `ps -e | grep test05 | awk '{print $1}'` | wc -l