Eric's Blogs

Better Code, Better Life

0%

发表于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

Copy-On-Write 是什么？

首先我讲一下什么是Copy-On-Write，顾名思义，在计算机中就是当你想要对一块内存进行修改时，我们不在原有内存块中进行写操作，而是将内存拷贝一份，在新的内存中进行写操作，写完之后呢，就将指向原来内存指针指向新的内存，原来的内存就可以被回收掉嘛！

网上兄弟们说了，这是一种用于程序设计中的优化策略，是一种延时懒惰策略。都说优化优化，那么到底优化了哪些问题呢？

先给大家一份代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class IteratorTest {

	private static List<String> list = new ArrayList<>();

	public static void main(String[] args) {
		
		list.add("1");
		list.add("2");
		list.add("3");
		
		Iterator<String> iter = list.iterator();
		
		//我当前正在迭代集合（这里模拟并发中读取某一list的场景）
		while (iter.hasNext()) {
			
			System.err.println(iter.next());
		
		}
		
		System.err.println(Arrays.toString(list.toArray()));
	}
}

上面的程序片段在单线程下执行时没什么毛病的，但到了多线程的环境中，可能就GG了！为什么呢？因为多线程环境中，你在迭代的时候是不允许有其他线程对这个集合list进行添加元素的，看下面这段代码，你会发现抛出java.util.ConcurrentModificationException的异常。

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
public class IteratorTest {

	private static List<String> list = new ArrayList<>();

	public static void main(String[] args) {

		list.add("1");
		list.add("2");
		list.add("3");

		Iterator<String> iter = list.iterator();

		// 存放10个线程的线程池
		ExecutorService service = Executors.newFixedThreadPool(10);

		// 执行10个任务(我当前正在迭代集合（这里模拟并发中读取某一list的场景）)
		for (int i = 0; i < 10; i++) {
			service.execute(new Runnable() {
				@Override
				public void run() {
					while (iter.hasNext()) {
						System.err.println(iter.next());
					}
				}
			});
		}
		
		// 执行10个任务
		for (int i = 0; i < 10; i++) {
			service.execute(new Runnable() {
				@Override
				public void run() {
					list.add("121");// 添加数据
				}
			});
		}
		
		System.err.println(Arrays.toString(list.toArray()));
		
	}
}
  • 1、这里的迭代表示我当前正在读取某种集合中的数据,属于读操作；
  • 2、线程则模拟当前程序处于多线程环境中，有其他线程正在修改该数据

这里暴露的问题是什么呢？

  • 多线程会对迭代集合产生影响，影响读操作

解决：

  • CopyOnWriteArrayList 避免了多线程操作List线程不安全的问题

CopyOnWriteArrayList介绍

从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用，可以在非常多的并发场景中使用到。

CopyOnWriteArrayList原理：

1
上面已经讲了，就是在写的时候不对原集合进行修改，而是重新复制一份，修改完之后，再移动指针

那么你可能会问？就算是对原集合进行复制，在多线程环境中不也是一样会导致写入冲突吗？没错，但是你可能还不知道CopyOnWriteArrayList中增加删除元素的实现细节，下面我就说说网上老是提到的add()方法

CopyOnWriteArrayList简单源码解读

add()方法源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;//重入锁
        lock.lock();//加锁啦
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);//拷贝新数组
            newElements[len] = e;
            setArray(newElements);//将引用指向新数组  1
            return true;
        } finally {
            lock.unlock();//解锁啦
        }
    }

恍然大悟，小样，原来add()在添加集合的时候加上了锁，保证了同步，避免了多线程写的时候会Copy出N个副本出来。(想想，你在遍历一个10个元素的集合，每遍历一次有1人调用add方法，你说当你遍历10次，这add方法是不是得被调用10次呢？是不是得copy出10分新集合呢？万一这个集合非常大呢？)

那么？你还要问？CopyOnWriteArrayList是怎么解决线程安全问题的？答案就是—-写时复制，加锁 还要问？那么有没有这么一种情况，当一个线程刚好调用完add()方法，也就是刚好执行到上面1处的代码，也就是刚好将引用指向心数组，而此时有线程正在遍历呢？会不会报错呢？（答案是不会的，因为你正在遍历的集合是旧的，这就有点难受啦，哈哈~）

当你把上面的代码的ArrayList改为CopyOnWriteArrayList，执行就不会报错啦！

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
public class IteratorTest {

	private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

	public static void main(String[] args) {

		list.add("1");
		list.add("2");
		list.add("3");

		Iterator<String> iter = list.iterator();

		// 存放10个线程的线程池
		ExecutorService service = Executors.newFixedThreadPool(10);

		// 执行10个任务(我当前正在迭代集合（这里模拟并发中读取某一list的场景）)
		for (int i = 0; i < 10; i++) {
			service.execute(new Runnable() {
				@Override
				public void run() {
					while (iter.hasNext()) {
						System.err.println(iter.next());
					}
				}
			});
			service.execute(new Runnable() {
				@Override
				public void run() {
					list.add("121");// 添加数据
				}
			});
		}
		
		// 执行10个任务
		for (int i = 0; i < 10; i++) {
			service.execute(new Runnable() {
				@Override
				public void run() {
					list.add("121");// 添加数据
				}
			});
			service.execute(new Runnable() {
				@Override
				public void run() {
					while (iter.hasNext()) {
						System.err.println(iter.next());
					}
				}
			});
		}
		
		System.err.println(Arrays.toString(list.toArray()));
		
	}
}

CopyOnWriteArrayList 优缺点

缺点：

  • 1、耗内存（集合复制）
  • 2、实时性不高

优点：

  • 1、数据一致性完整，为什么？因为加锁了，并发数据不会乱
  • 2、解决了像ArrayList、Vector这种集合多线程遍历迭代问题，记住，Vector虽然线程安全，只不过是加了synchronized关键字，迭代问题完全没有解决！

CopyOnWriteArrayList 使用场景

  • 1、读多写少（白名单，黑名单，商品类目的访问和更新场景），为什么？因为写的时候会复制新集合
  • 2、集合不大，为什么？因为写的时候会复制新集合
  • 实时性要求不高，为什么，因为有可能会读取到旧的集合数据

本文整理自

CopyOnWriteArrayList
如何线程安全地遍历List：Vector、CopyOnWriteArrayList

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

发表于 分类于
本文字数： 15k 阅读时长 ≈ 14 分钟

同步IO和异步IO，阻塞IO和非阻塞IO分别是什么，到底有什么区别？不同的人在不同的上下文下给出的答案是不同的。所以先限定一下本文的上下文。

1
本文讨论的背景是Linux环境下的network IO。

一 概念说明

在进行解释之前，首先要说明几个概念：
- 用户空间和内核空间
- 进程切换
- 进程的阻塞
- 文件描述符
- 缓存 I/O

用户空间与内核空间

现在操作系统都是采用虚拟存储器，那么对32位操作系统而言，它的寻址空间（虚拟存储空间）为4G（2的32次方）。操作系统的核心是内核，独立于普通的应用程序，可以访问受保护的内存空间，也有访问底层硬件设备的所有权限。为了保证用户进程不能直接操作内核（kernel），保证内核的安全，操心系统将虚拟空间划分为两部分，一部分为内核空间，一部分为用户空间。针对linux操作系统而言，将最高的1G字节（从虚拟地址0xC0000000到0xFFFFFFFF），供内核使用，称为内核空间，而将较低的3G字节（从虚拟地址0x00000000到0xBFFFFFFF），供各个进程使用，称为用户空间。

进程切换

为了控制进程的执行，内核必须有能力挂起正在CPU上运行的进程，并恢复以前挂起的某个进程的执行。这种行为被称为进程切换。因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。

从一个进程的运行转到另一个进程上运行，这个过程中经过下面这些变化：
\1. 保存处理机上下文，包括程序计数器和其他寄存器。
\2. 更新PCB信息。
\3. 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
\4. 选择另一个进程执行，并更新其PCB。
\5. 更新内存管理的数据结构。
\6. 恢复处理机上下文。

注：总而言之就是很耗资源，具体的可以参考这篇文章：进程切换

进程的阻塞

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作做等，则由系统自动执行阻塞原语(Block)，使自己由运行状态变为阻塞状态。可见，进程的阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程（获得CPU），才可能将其转为阻塞状态。当进程进入阻塞状态，是不占用CPU资源的。

文件描述符fd

文件描述符（File descriptor）是计算机科学中的一个术语，是一个用于表述指向文件的引用的抽象化概念。

文件描述符在形式上是一个非负整数。实际上，它是一个索引值，指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。在程序设计中，一些涉及底层的程序编写往往会围绕着文件描述符展开。但是文件描述符这一概念往往只适用于UNIX、Linux这样的操作系统。

缓存 I/O

缓存 I/O 又被称作标准 I/O，大多数文件系统的默认 I/O 操作都是缓存 I/O。在 Linux 的缓存 I/O 机制中，操作系统会将 I/O 的数据缓存在文件系统的页缓存（ page cache ）中，也就是说，数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。

缓存 I/O 的缺点：
数据在传输过程中需要在应用程序地址空间和内核进行多次数据拷贝操作，这些数据拷贝操作所带来的 CPU 以及内存开销是非常大的。

二 IO模式

刚才说了，对于一次IO访问（以read举例），数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。所以说，当一个read操作发生时，它会经历两个阶段：
\1. 等待数据准备 (Waiting for the data to be ready)
\2. 将数据从内核拷贝到进程中 (Copying the data from the kernel to the process)

正式因为这两个阶段，linux系统产生了下面五种网络模式的方案。
- 阻塞 I/O（blocking IO）
- 非阻塞 I/O（nonblocking IO）
- I/O 多路复用（ IO multiplexing）
- 信号驱动 I/O（ signal driven IO）
- 异步 I/O（asynchronous IO）

注：由于signal driven IO在实际中并不常用，所以我这只提及剩下的四种IO Model。

阻塞 I/O（blocking IO）

在linux中，默认情况下所有的socket都是blocking，一个典型的读操作流程大概是这样：
clipboard.png

当用户进程调用了recvfrom这个系统调用，kernel就开始了IO的第一个阶段：准备数据（对于网络IO来说，很多时候数据在一开始还没有到达。比如，还没有收到一个完整的UDP包。这个时候kernel就要等待足够的数据到来）。这个过程需要等待，也就是说数据被拷贝到操作系统内核的缓冲区中是需要一个过程的。而在用户进程这边，整个进程会被阻塞（当然，是进程自己选择的阻塞）。当kernel一直等到数据准备好了，它就会将数据从kernel中拷贝到用户内存，然后kernel返回结果，用户进程才解除block的状态，重新运行起来。

所以，blocking IO的特点就是在IO执行的两个阶段都被block了。

非阻塞 I/O（nonblocking IO）

linux下，可以通过设置socket使其变为non-blocking。当对一个non-blocking socket执行读操作时，流程是这个样子：
clipboard.png

当用户进程发出read操作时，如果kernel中的数据还没有准备好，那么它并不会block用户进程，而是立刻返回一个error。从用户进程角度讲 ，它发起一个read操作后，并不需要等待，而是马上就得到了一个结果。用户进程判断结果是一个error时，它就知道数据还没有准备好，于是它可以再次发送read操作。一旦kernel中的数据准备好了，并且又再次收到了用户进程的system call，那么它马上就将数据拷贝到了用户内存，然后返回。

所以，nonblocking IO的特点是用户进程需要不断的主动询问kernel数据好了没有。

I/O 多路复用（ IO multiplexing）

IO multiplexing就是我们说的select，poll，epoll，有些地方也称这种IO方式为event driven IO。select/epoll的好处就在于单个process就可以同时处理多个网络连接的IO。它的基本原理就是select，poll，epoll这个function会不断的轮询所负责的所有socket，当某个socket有数据到达了，就通知用户进程。

clipboard.png

当用户进程调用了select，那么整个进程会被block，而同时，kernel会“监视”所有select负责的socket，当任何一个socket中的数据准备好了，select就会返回。这个时候用户进程再调用read操作，将数据从kernel拷贝到用户进程。

所以，I/O 多路复用的特点是通过一种机制一个进程能同时等待多个文件描述符，而这些文件描述符（套接字描述符）其中的任意一个进入读就绪状态，select()函数就可以返回。

这个图和blocking IO的图其实并没有太大的不同，事实上，还更差一些。因为这里需要使用两个system call (select 和 recvfrom)，而blocking IO只调用了一个system call (recvfrom)。但是，用select的优势在于它可以同时处理多个connection。

所以，如果处理的连接数不是很高的话，使用select/epoll的web server不一定比使用multi-threading + blocking IO的web server性能更好，可能延迟还更大。select/epoll的优势并不是对于单个连接能处理得更快，而是在于能处理更多的连接。）

在IO multiplexing Model中，实际中，对于每一个socket，一般都设置成为non-blocking，但是，如上图所示，整个用户的process其实是一直被block的。只不过process是被select这个函数block，而不是被socket IO给block。

异步 I/O（asynchronous IO）

inux下的asynchronous IO其实用得很少。先看一下它的流程：
clipboard.png

用户进程发起read操作之后，立刻就可以开始去做其它的事。而另一方面，从kernel的角度，当它受到一个asynchronous read之后，首先它会立刻返回，所以不会对用户进程产生任何block。然后，kernel会等待数据准备完成，然后将数据拷贝到用户内存，当这一切都完成之后，kernel会给用户进程发送一个signal，告诉它read操作完成了。

总结

blocking和non-blocking的区别

调用blocking IO会一直block住对应的进程直到操作完成，而non-blocking IO在kernel还准备数据的情况下会立刻返回。

synchronous IO和asynchronous IO的区别

在说明synchronous IO和asynchronous IO的区别之前，需要先给出两者的定义。POSIX的定义是这样子的：
- A synchronous I/O operation causes the requesting process to be blocked until that I/O operation completes;
- An asynchronous I/O operation does not cause the requesting process to be blocked;

两者的区别就在于synchronous IO做”IO operation”的时候会将process阻塞。按照这个定义，之前所述的blocking IO，non-blocking IO，IO multiplexing都属于synchronous IO。

有人会说，non-blocking IO并没有被block啊。这里有个非常“狡猾”的地方，定义中所指的”IO operation”是指真实的IO操作，就是例子中的recvfrom这个system call。non-blocking IO在执行recvfrom这个system call的时候，如果kernel的数据没有准备好，这时候不会block进程。但是，当kernel中数据准备好的时候，recvfrom会将数据从kernel拷贝到用户内存中，这个时候进程是被block了，在这段时间内，进程是被block的。

而asynchronous IO则不一样，当进程发起IO 操作之后，就直接返回再也不理睬了，直到kernel发送一个信号，告诉进程说IO完成。在这整个过程中，进程完全没有被block。

各个IO Model的比较如图所示：
clipboard.png

通过上面的图片，可以发现non-blocking IO和asynchronous IO的区别还是很明显的。在non-blocking IO中，虽然进程大部分时间都不会被block，但是它仍然要求进程去主动的check，并且当数据准备完成以后，也需要进程主动的再次调用recvfrom来将数据拷贝到用户内存。而asynchronous IO则完全不同。它就像是用户进程将整个IO操作交给了他人（kernel）完成，然后他人做完后发信号通知。在此期间，用户进程不需要去检查IO操作的状态，也不需要主动的去拷贝数据。

三 I/O 多路复用之select、poll、epoll详解

select，poll，epoll都是IO多路复用的机制。I/O多路复用就是通过一种机制，一个进程可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。（这里啰嗦下）

select

1
int select (int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

select 函数监视的文件描述符分3类，分别是writefds、readfds、和exceptfds。调用后select函数会阻塞，直到有描述副就绪（有数据 可读、可写、或者有except），或者超时（timeout指定等待时间，如果立即返回设为null即可），函数返回。当select函数返回后，可以 通过遍历fdset，来找到就绪的描述符。

select目前几乎在所有的平台上支持，其良好跨平台支持也是它的一个优点。select的一 个缺点在于单个进程能够监视的文件描述符的数量存在最大限制，在Linux上一般为1024，可以通过修改宏定义甚至重新编译内核的方式提升这一限制，但 是这样也会造成效率的降低。

在linux下网络通信中，经常用到select机制，这是一种异步通信的实现方式，select中提供一fd_set的数据结果，实际上是一个long类型的数组， 每一个数组元素都能与一打开的文件句柄建立联系，通常这个句柄并不局限于网络通信中的socket句柄，还包括其他文件、命名管道或设备句柄等。当程序中调用select()时，由内核根据IO状态修改fd_set的内容，由此来通知执select()的进程哪一Socket或文件可读或者可写。

　　select的本质上是通过设置或者检查存放fd标志位的数据结构来进行下一步处理。这样所带来的缺点是：

　　1、单个进程可监视的fd数量受到了限制，在32位机器上，他所能管理的fd数量最大为1024。

　　2、需要维护一个用来存放大量fd的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大。

　　3、对socket进行扫描时是线性扫描，当socket文件描述符数量变多时，大量的时间是被白白浪费掉的。

poll

1
int poll (struct pollfd *fds, unsigned int nfds, int timeout);

不同于select使用三个位图来表示三个fdset的方式，poll使用一个 pollfd的指针实现。

1
2
3
4
5
struct pollfd {
    int fd; /* file descriptor */
    short events; /* requested events to watch */
    short revents; /* returned events witnessed */
};

pollfd结构包含了要监视的event和发生的event，不再使用select“参数-值”传递的方式。同时，pollfd并没有最大数量限制（但是数量过大后性能也是会下降）。 和select函数一样，poll返回后，需要轮询pollfd来获取就绪的描述符。

从上面看，select和poll都需要在返回后，通过遍历文件描述符来获取已经就绪的socket。事实上，同时连接的大量客户端在一时刻可能只有很少的处于就绪状态，因此随着监视的描述符数量的增长，其效率也会线性下降。

　poll是Linux中的字符设备驱动中有一个函数，Linux 2.5.44版本后已经被epoll所取代。poll机制是用在某些Unix系统中，使用poll()函数用于执行与select()函数同等功能的函数。

　　poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，如果设备就绪则在设备等待队列中加入一项并继续遍历，如果遍历完所有fd后没有发现就绪设备，则挂起当前进程，直到设备就绪或者主动超时，被唤醒后它又要再次遍历fd。这个过程经历了多次无谓的遍历。

　　相比于select机制，poll机制采用链表来进行文件描述符的存储，因此它并没有最大连接数的限制，但同样存在一些缺点：

　　1、大量的fd的数组被整体复制于用户态和内核地址空间之间，而不管这样的复制是不是有意义。

　　2、poll还有一个特点是“水平触发”，如果报告了fd后，没有被处理，那么下次poll时会再次报告该fd。

epoll

epoll是在2.6内核中提出的，是之前的select和poll的增强版本。相对于select和poll来说，epoll更加灵活，没有描述符限制。epoll使用一个文件描述符管理多个描述符，将用户关系的文件描述符的事件存放到内核的一个事件表中，这样在用户空间和内核空间的copy只需一次。

　epoll是Linux内核为处理大批量的句柄而作了改进的poll，是Linux下多路复用IO接口select/poll的增强版本，它能显著提高程序在大量并发连接中只有少量活跃的情况下的系统CPU利用率。

　　epoll会复用文件描述符集合来传递结果而不用迫使开发者每次等待事件之前都必须重新准备要被侦听的文件描述符集合，另一点原因就是获取事件的时候，它无须遍历整个被侦听的描述符集，只要遍历那些被内核IO事件异步唤醒而加入Ready队列的描述符集合就行了。epoll除了提供select/poll那种IO事件的电平触发（Level Triggered）外，还提供了边沿触发（Edge Triggered），这就使得用户空间程序有可能缓存IO状态，减少epoll_wait/epoll_pwait的调用，提高应用程序效率。

　　相比于poll机制，epoll支持水平触发和边缘触发，最大的特点在于边缘触发，它只告诉进程哪些fd刚刚变为就需态，并且只会通知一次。在fd的数组在用户态和内核地址空间之间复制的问题上，epoll使用mmap减少复制开销。还有一个特点是，epoll使用“事件”的就绪通知方式，通过epoll_ctl注册fd，一旦该fd就绪，内核就会采用类似callback的回调机制来激活该fd，epoll_wait便可以收到通知。

一 epoll操作过程

epoll操作过程需要三个接口，分别如下：

1
2
3
int epoll_create(int size)；//创建一个epoll的句柄，size用来告诉内核这个监听的数目一共有多大
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)；
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

1. int epoll_create(int size);
创建一个epoll的句柄，size用来告诉内核这个监听的数目一共有多大，这个参数不同于select()中的第一个参数，给出最大监听的fd+1的值，参数size并不是限制了epoll所能监听的描述符最大个数，只是对内核初始分配内部数据结构的一个建议。
当创建好epoll句柄后，它就会占用一个fd值，在linux下如果查看/proc/进程id/fd/，是能够看到这个fd的，所以在使用完epoll后，必须调用close()关闭，否则可能导致fd被耗尽。

2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)；
函数是对指定描述符fd执行op操作。
- epfd：是epoll_create()的返回值。
- op：表示op操作，用三个宏来表示：添加EPOLL_CTL_ADD，删除EPOLL_CTL_DEL，修改EPOLL_CTL_MOD。分别添加、删除和修改对fd的监听事件。
- fd：是需要监听的fd（文件描述符）
- epoll_event：是告诉内核需要监听什么事，struct epoll_event结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct epoll_event {
  __uint32_t events;  /* Epoll events */
  epoll_data_t data;  /* User data variable */
};

//events可以是以下几个宏的集合：
EPOLLIN ：表示对应的文件描述符可以读（包括对端SOCKET正常关闭）；
EPOLLOUT：表示对应的文件描述符可以写；
EPOLLPRI：表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）；
EPOLLERR：表示对应的文件描述符发生错误；
EPOLLHUP：表示对应的文件描述符被挂断；
EPOLLET： 将EPOLL设为边缘触发(Edge Triggered)模式，这是相对于水平触发(Level Triggered)来说的。
EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket的话，需要再次把这个socket加入到EPOLL队列里

3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
等待epfd上的io事件，最多返回maxevents个事件。
参数events用来从内核得到事件的集合，maxevents告之内核这个events有多大，这个maxevents的值不能大于创建epoll_create()时的size，参数timeout是超时时间（毫秒，0会立即返回，-1将不确定，也有说法说是永久阻塞）。该函数返回需要处理的事件数目，如返回0表示已超时。

二 工作模式

　epoll对文件描述符的操作有两种模式：LT（level trigger）和ET（edge trigger）。LT模式是默认模式，LT模式与ET模式的区别如下：
　LT模式：当epoll_wait检测到描述符事件发生并将此事件通知应用程序，应用程序可以不立即处理该事件。下次调用epoll_wait时，会再次响应应用程序并通知此事件。
　ET模式：当epoll_wait检测到描述符事件发生并将此事件通知应用程序，应用程序必须立即处理该事件。如果不处理，下次调用epoll_wait时，不会再次响应应用程序并通知此事件。

1. LT模式

LT(level triggered)是缺省的工作方式，并且同时支持block和no-block socket.在这种做法中，内核告诉你一个文件描述符是否就绪了，然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作，内核还是会继续通知你的。

2. ET模式

ET(edge-triggered)是高速工作方式，只支持no-block socket。在这种模式下，当描述符从未就绪变为就绪时，内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪，并且不会再为那个文件描述符发送更多的就绪通知，直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如，你在发送，接收或者接收请求，或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误）。但是请注意，如果一直不对这个fd作IO操作(从而导致它再次变成未就绪)，内核不会发送更多的通知(only once)

ET模式在很大程度上减少了epoll事件被重复触发的次数，因此效率要比LT模式高。epoll工作在ET模式的时候，必须使用非阻塞套接口，以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。

3. 总结

假如有这样一个例子：
\1. 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符
\2. 这个时候从管道的另一端被写入了2KB的数据
\3. 调用epoll_wait(2)，并且它会返回RFD，说明它已经准备好读取操作
\4. 然后我们读取了1KB的数据
\5. 调用epoll_wait(2)……

LT模式：
如果是LT模式，那么在第5步调用epoll_wait(2)之后，仍然能受到通知。

ET模式：
如果我们在第1步将RFD添加到epoll描述符的时候使用了EPOLLET标志，那么在第5步调用epoll_wait(2)之后将有可能会挂起，因为剩余的数据还存在于文件的输入缓冲区内，而且数据发出端还在等待一个针对已经发出数据的反馈信息。只有在监视的文件句柄上发生了某个事件的时候 ET 工作模式才会汇报事件。因此在第5步的时候，调用者可能会放弃等待仍在存在于文件输入缓冲区内的剩余数据。

当使用epoll的ET模型来工作时，当产生了一个EPOLLIN事件后，
读数据的时候需要考虑的是当recv()返回的大小如果等于请求的大小，那么很有可能是缓冲区还有数据未读完，也意味着该次事件还没有处理完，所以还需要再次读取：

​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while(rs){
  buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);
  if(buflen < 0){
    // 由于是非阻塞的模式,所以当errno为EAGAIN时,表示当前缓冲区已无数据可读
    // 在这里就当作是该次事件已处理处.
    if(errno == EAGAIN){
        break;
    }
    else{
        return;
    }
  }
  else if(buflen == 0){
     // 这里表示对端的socket已正常关闭.
  }

 if(buflen == sizeof(buf){
      rs = 1;   // 需要再次读取
 }
 else{
      rs = 0;
 }
}

Linux中的EAGAIN含义

Linux环境下开发经常会碰到很多错误(设置errno)，其中EAGAIN是其中比较常见的一个错误(比如用在非阻塞操作中)。
从字面上来看，是提示再试一次。这个错误经常出现在当应用程序进行一些非阻塞(non-blocking)操作(对文件或socket)的时候。

例如，以 O_NONBLOCK的标志打开文件/socket/FIFO，如果你连续做read操作而没有数据可读。此时程序不会阻塞起来等待数据准备就绪返回，read函数会返回一个错误EAGAIN，提示你的应用程序现在没有数据可读请稍后再试。
又例如，当一个系统调用(比如fork)因为没有足够的资源(比如虚拟内存)而执行失败，返回EAGAIN提示其再调用一次(也许下次就能成功)。

三 代码演示

下面是一段不完整的代码且格式不对，意在表述上面的过程，去掉了一些模板代码。

​ 

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
#define IPADDRESS   "127.0.0.1"
#define PORT        8787
#define MAXSIZE     1024
#define LISTENQ     5
#define FDSIZE      1000
#define EPOLLEVENTS 100

listenfd = socket_bind(IPADDRESS,PORT);

struct epoll_event events[EPOLLEVENTS];

//创建一个描述符
epollfd = epoll_create(FDSIZE);

//添加监听描述符事件
add_event(epollfd,listenfd,EPOLLIN);

//循环等待
for ( ; ; ){
    //该函数返回已经准备好的描述符事件数目
    ret = epoll_wait(epollfd,events,EPOLLEVENTS,-1);
    //处理接收到的连接
    handle_events(epollfd,events,ret,listenfd,buf);
}

//事件处理函数
static void handle_events(int epollfd,struct epoll_event *events,int num,int listenfd,char *buf)
{
     int i;
     int fd;
     //进行遍历;这里只要遍历已经准备好的io事件。num并不是当初epoll_create时的FDSIZE。
     for (i = 0;i < num;i++)
     {
         fd = events[i].data.fd;
        //根据描述符的类型和事件类型进行处理
         if ((fd == listenfd) &&(events[i].events & EPOLLIN))
            handle_accpet(epollfd,listenfd);
         else if (events[i].events & EPOLLIN)
            do_read(epollfd,fd,buf);
         else if (events[i].events & EPOLLOUT)
            do_write(epollfd,fd,buf);
     }
}

//添加事件
static void add_event(int epollfd,int fd,int state){
    struct epoll_event ev;
    ev.events = state;
    ev.data.fd = fd;
    epoll_ctl(epollfd,EPOLL_CTL_ADD,fd,&ev);
}

//处理接收到的连接
static void handle_accpet(int epollfd,int listenfd){
     int clifd;     
     struct sockaddr_in cliaddr;     
     socklen_t  cliaddrlen;     
     clifd = accept(listenfd,(struct sockaddr*)&cliaddr,&cliaddrlen);     
     if (clifd == -1)         
     perror("accpet error:");     
     else {         
         printf("accept a new client: %s:%d\n",inet_ntoa(cliaddr.sin_addr),cliaddr.sin_port);                       //添加一个客户描述符和事件         
         add_event(epollfd,clifd,EPOLLIN);     
     } 
}

//读处理
static void do_read(int epollfd,int fd,char *buf){
    int nread;
    nread = read(fd,buf,MAXSIZE);
    if (nread == -1)     {         
        perror("read error:");         
        close(fd); //记住close fd        
        delete_event(epollfd,fd,EPOLLIN); //删除监听 
    }
    else if (nread == 0)     {         
        fprintf(stderr,"client close.\n");
        close(fd); //记住close fd       
        delete_event(epollfd,fd,EPOLLIN); //删除监听 
    }     
    else {         
        printf("read message is : %s",buf);        
        //修改描述符对应的事件，由读改为写         
        modify_event(epollfd,fd,EPOLLOUT);     
    } 
}

//写处理
static void do_write(int epollfd,int fd,char *buf) {     
    int nwrite;     
    nwrite = write(fd,buf,strlen(buf));     
    if (nwrite == -1){         
        perror("write error:");        
        close(fd);   //记住close fd       
        delete_event(epollfd,fd,EPOLLOUT);  //删除监听    
    }else{
        modify_event(epollfd,fd,EPOLLIN); 
    }    
    memset(buf,0,MAXSIZE); 
}

//删除事件
static void delete_event(int epollfd,int fd,int state) {
    struct epoll_event ev;
    ev.events = state;
    ev.data.fd = fd;
    epoll_ctl(epollfd,EPOLL_CTL_DEL,fd,&ev);
}

//修改事件
static void modify_event(int epollfd,int fd,int state){     
    struct epoll_event ev;
    ev.events = state;
    ev.data.fd = fd;
    epoll_ctl(epollfd,EPOLL_CTL_MOD,fd,&ev);
}

//注：另外一端我就省了

四 epoll总结

在 select/poll中，进程只有在调用一定的方法后，内核才对所有监视的文件描述符进行扫描，而epoll事先通过epoll_ctl()来注册一 个文件描述符，一旦基于某个文件描述符就绪时，内核会采用类似callback的回调机制，迅速激活这个文件描述符，当进程调用epoll_wait() 时便得到通知。(此处去掉了遍历文件描述符，而是通过监听回调的的机制。这正是epoll的魅力所在。)

epoll的优点主要是一下几个方面：
\1. 监视的描述符数量不受限制，它所支持的FD上限是最大可以打开文件的数目，这个数字一般远大于2048,举个例子,在1GB内存的机器上大约是10万左 右，具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。select的最大缺点就是进程打开的fd是有数量限制的。这对 于连接数量比较大的服务器来说根本不能满足。虽然也可以选择多进程的解决方案( Apache就是这样实现的)，不过虽然linux上面创建进程的代价比较小，但仍旧是不可忽视的，加上进程间数据同步远比不上线程间同步的高效，所以也不是一种完美的方案。

  1. IO的效率不会随着监视fd的数量的增长而下降。epoll不同于select和poll轮询的方式，而是通过每个fd定义的回调函数来实现的。只有就绪的fd才会执行回调函数。

如果没有大量的idle -connection或者dead-connection，epoll的效率并不会比select/poll高很多，但是当遇到大量的idle- connection，就会发现epoll的效率大大高于select/poll。

select、poll与epoll的比较

　　1、支持一个进程所能管理的最大连接数

方法 描述
select 单个进程所能打开的最大连接数有FD_SETSIZE宏定义，其大小是32个整数的大小（在32位的机器上，大小就是3232，同理64位机器上FD_SETSIZE为3264），当然我们可以对进行修改，然后重新编译内核，但是性能可能会受到影响，这需要进一步的测试。
poll poll本质上和select没有区别，但是它没有最大连接数的限制，原因是它是基于链表来存储的
epoll 虽然连接数有上限，但是很大，1G内存的机器上可以打开10万左右的连接，2G内存的机器可以打开20万左右的连接

　　2、文件描述符剧增后带来的IO效率问题

方法 描述
select 因为每次调用时都会对连接进行线性遍历，所以随着FD的增加会造成遍历速度慢的“线性下降性能问题”。
poll 同上
epoll 因为epoll内核中实现是根据每个fd上的callback函数来实现的，只有活跃的socket才会主动调用callback，所以在活跃socket较少的情况下，使用epoll没有前面两者的线性下降的性能问题，但是所有socket都很活跃的情况下，可能会有性能问题。

　　3、消息传递的方式

方法 描述
select 内核需要将消息传递到用户空间，都需要内核拷贝动作
poll 同上
epoll epoll通过内核和用户空间共享一块内存来实现的。

本文整理自

Linux IO模式及 select、poll、epoll详解

进程切换
维基百科-文件描述符
Linux 中直接 I/O 机制的介绍
IO - 同步，异步，阻塞，非阻塞 （亡羊补牢篇）
Linux中select poll和epoll的区别
IO多路复用之select总结
IO多路复用之poll总结
IO多路复用之epoll总结

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

发表于 分类于
本文字数： 8.4k 阅读时长 ≈ 8 分钟

1、查看有多少个IP访问：

1
awk '{print $1}' log_file|sort|uniq|wc -l

2、查看某一个页面被访问的次数：

1
grep "/index.php" log_file | wc -l

3、查看每一个IP访问了多少个页面：

1
awk '{++S[$1]} END {for (a in S) print a,S[a]}' log_file > log.txt

sort -n -t ' ' -k 2 log.txt 配合sort进一步排序

4、将每个IP访问的页面数进行从小到大排序：

1
awk '{++S[$1]} END {for (a in S) print S[a],a}' log_file | sort -n

5、查看某一个IP访问了哪些页面：

1
grep ^111.111.111.111 log_file| awk '{print $1,$7}'

6、去掉搜索引擎统计的页面：

1
awk '{print $12,$1}' log_file | grep ^\"Mozilla | awk '{print $2}' |sort | uniq | wc -l

7、查看2015年8月16日14时这一个小时内有多少IP访问:

1
awk '{print $4,$1}' log_file | grep 16/Aug/2015:14 | awk '{print $2}'| sort | uniq | wc -l

8、查看访问前十个ip地址

1
awk '{print $1}' |sort|uniq -c|sort -nr |head -10 access_log

uniq -c 相当于分组统计并把统计数放在最前面
cat access.log|awk '{print $1}'|sort|uniq -c|sort -nr|head -10

1
cat access.log|awk '{counts[$(11)]+=1}; END {for(url in counts) print counts[url], url}

9、访问次数最多的10个文件或页面

1
2
cat log_file|awk '{print $11}'|sort|uniq -c|sort -nr | head -10
cat log_file|awk '{print $11}'|sort|uniq -c|sort -nr|head -20

awk '{print $1}' log_file |sort -n -r |uniq -c | sort -n -r | head -20
访问量最大的前20个ip

10、通过子域名访问次数，依据referer来计算，稍有不准

1
cat access.log | awk '{print $11}' | sed -e ' s/http:\/\///' -e ' s/\/.*//' | sort | uniq -c | sort -rn | head -20

11、列出传输大小最大的几个文件

1
cat www.access.log |awk '($7~/\.php/){print $10 " " $1 " " $4 " " $7}'|sort -nr|head -100

12、列出输出大于200000byte(约200kb)的页面以及对应页面发生次数

1
cat www.access.log |awk '($10 > 200000 && $7~/\.php/){print $7}'|sort -n|uniq -c|sort -nr|head -100

13、如果日志最后一列记录的是页面文件传输时间，则有列出到客户端最耗时的页面

1
cat www.access.log |awk '($7~/\.php/){print $NF " " $1 " " $4 " " $7}'|sort -nr|head -100

14、列出最最耗时的页面(超过60秒的)的以及对应页面发生次数

1
cat www.access.log |awk '($NF > 60 && $7~/\.php/){print $7}'|sort -n|uniq -c|sort -nr|head -100

15、列出传输时间超过 30 秒的文件

1
cat www.access.log |awk '($NF > 30){print $7}'|sort -n|uniq -c|sort -nr|head -20

16、列出当前服务器每一进程运行的数量，倒序排列

1
ps -ef | awk -F ' ' '{print $8 " " $9}' |sort | uniq -c |sort -nr |head -20

17、查看apache当前并发访问数

对比httpd.conf中MaxClients的数字差距多少
netstat -an | grep ESTABLISHED | wc -l

18、可以使用如下参数查看数据

1
2
3
ps -ef|grep httpd|wc -l

1388

统计httpd进程数，连个请求会启动一个进程，使用于Apache服务器。
表示Apache能够处理1388个并发请求，这个值Apache可根据负载情况自动调整

1
2
3
netstat -nat|grep -i "80"|wc -l

4341

netstat -an会打印系统当前网络链接状态，而grep -i “80”是用来提取与80端口有关的连接的，wc -l进行连接数统计。
最终返回的数字就是当前所有80端口的请求总数

1
2
netstat -na|grep ESTABLISHED|wc -l
376

netstat -an会打印系统当前网络链接状态，而grep ESTABLISHED 提取出已建立连接的信息。 然后wc -l统计
最终返回的数字就是当前所有80端口的已建立连接的总数。

1
netstat -nat||grep ESTABLISHED|wc

可查看所有建立连接的详细记录

19、输出每个ip的连接数，以及总的各个状态的连接数

1
netstat -n | awk '/^tcp/ {n=split($(NF-1),array,":");if(n<=2)++S[array[(1)]];else++S[array[(4)]];++s[$NF];++N} END {for(a in S){printf("%-20s %s\n", a, S[a]);++I}printf("%-20s %s\n","TOTAL_IP",I);for(a in s) printf("%-20s %s\n",a, s[a]);printf("%-20s %s\n","TOTAL_LINK",N);}

20、其他的收集

分析日志文件下 2012-05-04 访问页面最高 的前20个 URL 并排序 

1
cat access.log |grep '04/May/2012'| awk '{print $11}'|sort|uniq -c|sort -nr|head -20

查询受访问页面的URL地址中 含有 www.abc.com 网址的 IP 地址 

1
cat access_log | awk '($11~/\www.abc.com/){print $1}'|sort|uniq -c|sort -nr

获取访问最高的10个IP地址 同时也可以按时间来查询

1
cat linewow-access.log|awk '{print $1}'|sort|uniq -c|sort -nr|head -10

\时间段查询日志时间段的情况**

1
cat log_file | egrep '15/Aug/2015|16/Aug/2015' |awk '{print $1}'|sort|uniq -c|sort -nr|head -10

分析2015/8/15 到 2015/8/16 访问”/index.php?g=Member&m=Public&a=sendValidCode”的IP倒序排列

1
cat log_file | egrep '15/Aug/2015|16/Aug/2015' | awk '{if($7 == "/index.php?g=Member&m=Public&a=sendValidCode") print $1,$7}'|sort|uniq -c|sort -nr

(7里面包含.php的就输出,本句的意思是最耗时的一百个PHP页面

1
cat log_file |awk '($7~/\.php/){print $NF " " $1 " " $4 " " $7}'|sort -nr|head -100

列出最最耗时的页面(超过60秒的)的以及对应页面发生次数 

1
cat access.log |awk '($NF > 60 && $7~/\.php/){print $7}'|sort -n|uniq -c|sort -nr|head -100

统计网站流量（G) 

1
cat access.log |awk '{sum+=$10} END {print sum/1024/1024/1024}'

统计404的连接 

1
awk '($9 ~/404/)' access.log | awk '{print $9,$7}' | sort

统计http status 

1
2
cat access.log |awk '{counts[$(9)]+=1}; END {for(code in counts) print code, counts[code]}'` 
`cat access.log |awk '{print $9}'|sort|uniq -c|sort -rn

每秒并发 

1
watch "awk '{if($9~/200|30|404/)COUNT[$4]++}END{for( a in COUNT) print a,COUNT[a]}' log_file|sort -k 2 -nr|head -n10"

带宽统计 

1
2
cat apache.log |awk '{if($7~/GET/) count++}END{print "client_request="count}'` 
`cat apache.log |awk '{BYTE+=$11}END{print "client_kbyte_out="BYTE/1024"KB"}'

找出某天访问次数最多的10个IP 

1
cat /tmp/access.log | grep "20/Mar/2011" |awk '{print $3}'|sort |uniq -c|sort -nr|head

当天ip连接数最高的ip都在干些什么

1
cat access.log | grep "10.0.21.17" | awk '{print $8}' | sort | uniq -c | sort -nr | head -n 10

小时单位里ip连接数最多的10个时段

1
awk -vFS="[:]" '{gsub("-.*","",$1);num[$2" "$1]++}END{for(i in num)print i,num[i]}' log_file | sort -n -k 3 -r | head -10

找出访问次数最多的几个分钟

awk '{print $1}' access.log | grep "20/Mar/2011" |cut -c 14-18|sort|uniq -c|sort -nr|head
取5分钟日志
if [ $DATE_MINUTE != $DATE_END_MINUTE ] ;then #则判断开始时间戳与结束时间戳是否相等
START_LINE=sed -n "/$DATE_MINUTE/=" $APACHE_LOG|head -n1 #如果不相等，则取出开始时间戳的行号，与结束时间戳的行号

查看tcp的链接状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
netstat -nat |awk '{print $6}'|sort|uniq -c|sort -rn 
    
netstat -n | awk '/^tcp/ {++S[$NF]};END {for(a in S) print a, S[a]}' 

netstat -n | awk '/^tcp/ {++state[$NF]}; END {for(key in state) print key,"\t",state[key]}' 
    
netstat -n | awk '/^tcp/ {++arr[$NF]};END {for(k in arr) print k,"\t",arr[k]}' 
    
netstat -n |awk '/^tcp/ {print $NF}'|sort|uniq -c|sort -rn 
    
netstat -ant | awk '{print $NF}' | grep -v '[a-z]' | sort | uniq -c
netstat -ant|awk '/ip:80/{split($5,ip,":");++S[ip[1]]}END{for (a in S) print S[a],a}' |sort -n 
    
netstat -ant|awk '/:80/{split($5,ip,":");++S[ip[1]]}END{for (a in S) print S[a],a}' |sort -rn|head -n 10 
    
awk 'BEGIN{printf ("http_code\tcount_num\n")}{COUNT[$10]++}END{for (a in COUNT) printf a"\t\t"COUNT[a]"\n"}'

查找请求数前20个IP（常用于查找攻来源）：
netstat -anlp|grep 80|grep tcp|awk '{print $5}'|awk -F: '{print $1}'|sort|uniq -c|sort -nr|head -n20
netstat -ant |awk '/:80/{split($5,ip,":");++A[ip[1]]}END{for(i in A) print A[i],i}' |sort -rn|head -n20

用tcpdump嗅探80端口的访问看看谁最高 

1
tcpdump -i eth0 -tnn dst port 80 -c 1000 | awk -F"." '{print $1"."$2"."$3"."$4}' | sort | uniq -c | sort -nr |head -20

查找较多time_wait连接 

1
netstat -n|grep TIME_WAIT|awk '{print $5}'|sort|uniq -c|sort -rn|head -n20

找查较多的SYN连接 

1
netstat -an | grep SYN | awk '{print $5}' | awk -F: '{print $1}' | sort | uniq -c | sort -nr | more

根据端口列进程
netstat -ntlp | grep 80 | awk '{print $7}' | cut -d/ -f1

查看了连接数和当前的连接数 

1
2
netstat -ant | grep $ip:80 | wc -l` 
`netstat -ant | grep $ip:80 | grep EST | wc -l

查看IP访问次数
netstat -nat|grep ":80"|awk '{print $5}' |awk -F: '{print $1}' | sort| uniq -c|sort -n

Linux命令分析当前的链接状况
netstat -n | awk '/^tcp/ {++S[$NF]} END {for(a in S) print a, S[a]}'

watch "netstat -n | awk '/^tcp/ {++S[\$NF]} END {for(a in S) print a, S[a]}'" # 通过watch可以一直监控

1
2
3
4
5
6
7
8
9
10
11
LAST_ACK 5 #关闭一个TCP连接需要从两个方向上分别进行关闭，双方都是通过发送FIN来表示单方向数据的关闭，当通信双方发送了最后一个FIN的时候，发送方此时处于LAST_ACK状态，当发送方收到对方的确认（Fin的Ack确认）后才真正关闭整个TCP连接；

SYN_RECV 30  # 表示正在等待处理的请求数；

ESTABLISHED 1597 # 表示正常数据传输状态； 

FIN_WAIT1 51 # 表示server端主动要求关闭tcp连接； 

FIN_WAIT2 504 # 表示客户端中断连接； 

TIME_WAIT 1057  # 表示处理完毕，等待超时结束的请求数；

本文整理自

shell在手分析服务器日志不用愁

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

Kafka可以将主题划分为多个分区（Partition），会根据分区规则选择把消息存储到哪个分区中，只要如果分区规则设置的合理，那么所有的消息将会被均匀的分布到不同的分区中，这样就实现了负载均衡和水平扩展。另外，多个订阅者可以从一个或者多个分区中同时消费数据，以支撑海量数据处理能力：

img)img

Kafka的设计也是源自生活，好比是为公路运输，不同的起始点和目的地需要修不同高速公路（主题），高速公路上可以提供多条车道（分区），流量大的公路多修几条车道保证畅通，流量小的公路少修几条车道避免浪费。收费站好比消费者，车多的时候多开几个一起收费避免堵在路上，车少的时候开几个让汽车并道就好了，嗯……

顺便说一句，由于消息是以追加到分区中的，多个分区顺序写磁盘的总效率要比随机写内存还要高（引用Apache Kafka – A High Throughput Distributed Messaging System的观点），是Kafka高吞吐率的重要保证之一。

为了保证数据的可靠性，Kafka会给每个分区找一个节点当带头大哥（Leader），以及若干个节点当随从（Follower）。消息写入分区时，带头大哥除了自己复制一份外还会复制到多个随从。如果随从挂了，Kafka会再找一个随从从带头大哥那里同步历史消息；如果带头大哥挂了，随从中会选举出新一任的带头大哥，继续笑傲江湖。

img)img

1.kafka为什么要在topic里加入分区的概念？

topic是逻辑的概念，partition是物理的概念，对用户来说是透明的。producer只需要关心消息发往哪个topic，而consumer只关心自己订阅哪个topic，并不关心每条消息存于整个集群的哪个broker。

为了性能考虑，如果topic内的消息只存于一个broker，那这个broker会成为瓶颈，无法做到水平扩展。所以把topic内的数据分布到整个集群就是一个自然而然的设计方式。Partition的引入就是解决水平扩展问题的一个方案。

每个partition可以被认为是一个无限长度的数组，新数据顺序追加进这个数组。物理上，每个partition对应于一个文件夹。一个broker上可以存放多个partition。这样，producer可以将数据发送给多个broker上的多个partition，consumer也可以并行从多个broker上的不同paritition上读数据，实现了水平扩展.

2.如果没有分区,topic中的segment消息写满后,直接给订阅者不是也可以吗?

“segment消息写满后”，consume消费数据并不需要等到segment写满，只要有一条数据被commit，就可以立马被消费.

segment对应一个文件（实现上对应2个文件，一个数据文件，一个索引文件），一个partition对应一个文件夹，一个partition里理论上可以包含任意多个segment。所以partition可以认为是在segment上做了一层包装。

这个问题换个角度问可能更好，“为什么有了partition还需要segment”。

如果不引入segment，一个partition直接对应一个文件（应该说两个文件，一个数据文件，一个索引文件），那这个文件会一直增大。同时，在做data purge时，需要把文件的前面部分给删除，不符合kafka对文件的顺序写优化设计方案。引入segment后，每次做data purge，只需要把旧的segment整个文件删除即可，保证了每个segment的顺序写，

本文整理自

kafka中的topic为什么要进行分区

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

一、简介

ApacheKafka 是一个分布式的流处理平台。它具有以下特点：

  • 支持消息的发布和订阅，类似于 RabbtMQ、ActiveMQ 等消息队列；
  • 支持数据实时处理；
  • 能保证消息的可靠性投递；
  • 支持消息的持久化存储，并通过多副本分布式的存储方案来保证消息的容错；
  • 高吞吐率，单 Broker 可以轻松处理数千个分区以及每秒百万级的消息量。

二、基本概念

2.1 Messages And Batches

Kafka 的基本数据单元被称为 message(消息)，为减少网络开销，提高效率，多个消息会被放入同一批次 (Batch) 中后再写入(批量发送)。

2.2 Topics And Partitions

Kafka 的消息通过 Topics(主题) 进行分类,一个Topics相当于一个逻辑上的消息队列，一个主题可以被分为若干个 Partitions(分区)，一个分区就是一个提交日志 (commit log)。消息以追加的方式写入分区，然后以先入先出的顺序读取。Kafka 通过分区来实现数据的冗余和伸缩性(删除旧数据和扩展broker)，分区可以分布在不同的服务器上，这意味着一个 Topic 可以横跨多个服务器，以提供比单个服务器更强大的性能。

由于一个 Topic 包含多个分区，因此无法在整个 Topic 范围内保证消息的顺序性，但可以保证消息在单个分区内的顺序性。

https://github.com/heibaiying

2.3 Producers And Consumers

1. 生产者

生产者负责创建消息。一般情况下，生产者在把消息均衡地分布到在主题Topics的所有分区Partition上，而并不关心消息会被写到哪个分区。如果我们想要把消息写到指定的分区，可以通过自定义分区器(基于哈希等)来实现。

2. 消费者

消费者是消费者群组的一部分，消费者负责消费消息。消费者可以订阅一个或者多个主题，并按照消息生成的顺序来读取它们。消费者通过检查消息的偏移量 (offset) 来区分读取过的消息。偏移量是一个不断递增的数值，在创建消息时，Kafka 会把它添加到其中，在给定的分区里，每个消息的偏移量都是唯一的。消费者把每个分区最后读取的偏移量保存在 Zookeeper 或 Kafka 上，如果消费者关闭或者重启，它还可以重新获取该偏移量，以保证读取状态不会丢失。

https://github.com/heibaiying

一个分区只能被同一个消费者群组里面的一个消费者读取，但可以被不同消费者群组中所组成的多个消费者共同读取。多个消费者群组中消费者共同读取同一个主题时，彼此之间互不影响。

https://github.com/heibaiying

2.4 Brokers And Clusters

一个独立的 Kafka 服务器被称为 Broker。Broker 接收来自生产者的消息，为消息设置偏移量，并提交消息到磁盘保存。Broker 为消费者提供服务，对读取分区的请求做出响应，返回已经提交到磁盘的消息。

Broker 是集群 (Cluster) 的组成部分。每一个集群都会选举出一个 Broker 作为集群控制器 (Controller)，集群控制器负责管理工作，包括将分区分配给 Broker 和监控 Broker。

在集群中，一个分区 (Partition) 从属一个 Broker，该 Broker 被称为分区的首领 (Leader)。一个分区可以分配给多个 Brokers，这个时候会发生分区复制。这种复制机制为分区提供了消息冗余，如果有一个 Broker 失效，其他 Broker 可以接管领导权。

https://github.com/heibaiying

本文整理自

Kafka 简介

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

发表于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

Kafka的消息是保存或缓存在磁盘上的，一般认为在磁盘上读写数据是会降低性能的，因为寻址会比较消耗时间，但是实际上，Kafka的特性之一就是高吞吐率。

即使是普通的服务器，Kafka也可以轻松支持每秒百万级的写入请求，超过了大部分的消息中间件，这种特性也使得Kafka在日志处理等海量数据场景广泛应用。

针对Kafka的基准测试可以参考，Apache Kafka基准测试：每秒写入2百万（在三台廉价机器上）

下面从数据写入和读取两方面分析，为什么Kafka速度这么快。

写入数据

Kafka会把收到的消息都写入到硬盘中，它绝对不会丢失数据。为了优化写入速度Kafka采用了两个技术，顺序写入和MMFile 。

顺序写入

磁盘读写的快慢取决于你怎么使用它，也就是顺序读写或者随机读写。在顺序读写的情况下，磁盘的顺序读写速度和内存持平。

因为硬盘是机械结构，每次读写都会寻址->写入，其中寻址是一个“机械动作”，它是最耗时的。所以硬盘最讨厌随机I/O，最喜欢顺序I/O。为了提高读写硬盘的速度，Kafka就是使用顺序I/O。

而且Linux对于磁盘的读写优化也比较多，包括read-ahead和write-behind，磁盘缓存等。如果在内存做这些操作的时候，一个是JAVA对象的内存开销很大，另一个是随着堆内存数据的增多，JAVA的GC时间会变得很长，使用磁盘操作有以下几个好处：

  • 磁盘顺序读写速度超过内存随机读写(比如在虚拟内存经常缺页的情况下,会增加很多磁盘IO操作)
  • JVM的GC效率低，内存占用大。使用磁盘可以避免这一问题
  • 系统冷启动后，磁盘缓存依然可用

下图就展示了Kafka是如何写入数据的， 每一个Partition其实都是一个文件 ，收到消息后Kafka会把数据插入到文件末尾（虚框部分）：

img

这种方法有一个缺陷——没有办法删除数据 ，所以Kafka是不会删除数据的，它会把所有的数据都保留下来，每个消费者（Consumer）对每个Topic都有一个offset用来表示读取到了第几条数据 。

img

两个消费者：

  • Consumer1有两个offset分别对应Partition0、Partition1（假设每一个Topic一个Partition）；
  • Consumer2有一个offset对应Partition2。

这个offset是由客户端SDK负责保存的，Kafka的Broker完全无视这个东西的存在；一般情况下SDK会把它保存到Zookeeper里面，所以需要给Consumer提供zookeeper的地址。

如果不删除硬盘肯定会被撑满，所以Kakfa提供了两种策略来删除数据：

  • 一是基于时间；
  • 二是基于partition文件大小。

具体配置可以参看它的配置文档。

Memory Mapped Files 内存映射文件

即便是顺序写入硬盘，硬盘的访问速度还是不可能追上内存。所以Kafka的数据并不是实时的写入硬盘 ，它充分利用了现代操作系统分页存储来利用内存提高I/O效率。

Memory Mapped Files(后面简称mmap)也被翻译成内存映射文件 ，在64位操作系统中一般可以表示20G的数据文件，它的工作原理是直接利用操作系统的Page来实现文件到物理内存的直接映射。

完成映射之后你对物理内存的操作会被同步到硬盘上（操作系统在适当的时候）。

通过mmap，进程像读写硬盘一样读写内存（当然是虚拟机内存），也不必关心内存的大小有虚拟内存为我们兜底。

使用这种方式可以获取很大的I/O提升，省去了用户空间到内核空间复制的开销（调用文件的read会把数据先放到内核空间的内存中，然后再复制到用户空间的内存中。）

但也有一个很明显的缺陷——不可靠，写到mmap中的数据并没有被真正的写到硬盘，操作系统会在程序主动调用flush的时候才把数据真正的写到硬盘。

Kafka提供了一个参数——producer.type来控制是不是主动flush，如果Kafka写入到mmap之后就立即flush然后再返回Producer叫 同步 (sync)；写入mmap之后立即返回Producer不调用flush叫异步 (async)。

读取数据

Kafka在读取磁盘时做了哪些优化？

基于sendfile()实现Zero Copy

传统模式下，当需要对一个文件进行网络传输的时候，其具体流程细节如下：

  • 调用read函数，文件数据被copy到内核缓冲区
  • read函数返回，文件数据从内核缓冲区copy到用户缓冲区
  • write函数调用，将文件数据从用户缓冲区copy到内核与socket相关的缓冲区。
  • 数据从socket缓冲区copy到相关协议引擎(网卡发送缓冲区)。

以上细节是传统read/write方式进行网络文件传输的方式，我们可以看到，在这个过程当中，文件数据实际上是经过了四次copy操作：

硬盘—>内核buf—>用户buf—>socket相关缓冲区—>协议引擎(网卡缓冲区)

而sendfile()系统调用则提供了一种减少以上多次copy，提升文件传输性能的方法。

在内核版本2.1中，引入了sendfile系统调用，以简化网络上和两个本地文件之间的数据传输。sendfile的引入不仅减少了数据复制，还减少了上下文切换。

1
sendfile(socket, file, len);

运行流程如下：

  • sendfile系统调用，文件数据被copy至内核缓冲区
  • 再从内核缓冲区copy至内核中socket相关的缓冲区
  • 最后再socket相关的缓冲区copy到协议引擎

相较传统read/write方式，2.1版本内核引进的sendfile已经减少了内核缓冲区到user缓冲区，再由user缓冲区到socket相关缓冲区的文件copy，而在内核版本2.4之后，文件描述符结果被改变，sendfile实现了更简单的方式，再次减少了一次copy操作。

在Apache、Nginx、lighttpd等web服务器当中，都有一项sendfile()相关的配置，使用sendfile()可以大幅提升文件传输性能。

Kafka把所有的消息都存放在一个一个的文件(Partition)中，当消费者需要数据的时候Kafka直接把文件发送给消费者，配合mmap作为文件读写方式，直接把它传给sendfile()。

批量压缩

在很多情况下，系统的瓶颈不是CPU或磁盘，而是网络IO，对于需要在广域网上的数据中心之间发送消息的数据流水线尤其如此。进行数据压缩会消耗一定的CPU资源,不过对于kafka而言,网络IO更应该需要考虑。

  • 如果每个消息都压缩，但是压缩率相对很低，所以Kafka使用了批量压缩，即将多个消息一起压缩而不是单个消息压缩
  • Kafka允许使用递归的消息集合，批量的消息可以通过压缩的形式传输并且在日志中也可以保持压缩格式，直到被消费者解压
  • Kafka支持多种压缩协议，包括Gzip和Snappy压缩协议

总结

Kafka速度的秘诀在于，它把所有的消息都变成一个批量的文件(Partition)，并且进行合理的批量压缩，减少网络IO消耗，通过mmap提高I/O速度，写入数据的时候由于单个Partion是末尾添加所以速度最优；读取数据的时候配合sendfile()直接零拷贝输出。

本文整理自

Kafka为什么速度那么快？

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

发表于 分类于
本文字数： 9k 阅读时长 ≈ 8 分钟

停止一个线程意味着在任务处理完任务之前停掉正在做的操作，也就是放弃当前的操作。停止一个线程可以用Thread.stop()方法，但最好不要用它。虽然它确实可以停止一个正在运行的线程，但是这个方法是不安全的，而且是已被废弃的方法。

在java中有以下3种方法可以终止正在运行的线程：

  • 使用退出标志，使线程正常退出，也就是当run方法完成后线程终止。
  • 使用interrupt方法中断线程。
  • 使用stop方法强行终止，但是不推荐这个方法，因为stop和suspend及resume一样都是过期作废的方法。

1. 停止不了的线程

interrupt()方法的使用效果并不像for+break语句那样，马上就停止循环。调用interrupt方法是在当前线程中打了一个停止标志，并不是真的停止线程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class MyThread extends Thread {
    public void run(){
        super.run();
        for(int i=0; i<500000; i++){
            System.out.println("i="+(i+1));
        }
    }
}

public class Run {
    public static void main(String args[]){
        Thread thread = new MyThread();
        thread.start();
        try {
            Thread.sleep(2000);
            thread.interrupt();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

输出结果：

1
2
3
4
5
6
7
8
...
i=499994
i=499995
i=499996
i=499997
i=499998
i=499999
i=500000

2. 判断线程是否停止状态

Thread.java类中提供了两种方法：

  • this.interrupted(): 测试当前线程是否已经中断,若返回true会清除本次中断标志；
  • this.isInterrupted(): 测试线程是否已经中断；

那么这两个方法有什么图区别呢？

interrupted()方法

我们先来看看this.interrupted()方法的解释：测试当前线程是否已经中断，当前线程是指运行this.interrupted()方法的线程。

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
public class MyThread extends Thread {
    public void run(){
        super.run();
        for(int i=0; i<500000; i++){
            i++;
//            System.out.println("i="+(i+1));
        }
    }
}

public class Run {
    public static void main(String args[]){
        Thread thread = new MyThread();
        thread.start();
        try {
            Thread.sleep(2000);
            thread.interrupt();

            System.out.println("stop 1??" + thread.interrupted());
            System.out.println("stop 2??" + thread.interrupted());
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

运行结果：

1
2
stop 1??false
stop 2??false

类Run.java中虽然是在thread对象上调用以下代码：thread.interrupt(), 后面又使用

1
2
System.out.println("stop 1??" + thread.interrupted());
System.out.println("stop 2??" + thread.interrupted());

来判断thread对象所代表的线程是否停止，但从控制台打印的结果来看，线程并未停止，这也证明了interrupted()方法的解释，测试当前线程是否已经中断。这个当前线程是main，它从未中断过，所以打印的结果是两个false.

如何使main线程产生中断效果呢？

1
2
3
4
5
6
7
8
9
public class Run2 {
    public static void main(String args[]){
        Thread.currentThread().interrupt();
        System.out.println("stop 1??" + Thread.interrupted());
        System.out.println("stop 2??" + Thread.interrupted());

        System.out.println("End");
    }
}

运行效果为：

1
2
3
stop 1??true
stop 2??false
End

方法interrupted()的确判断出当前线程是否是停止状态。但为什么第2个布尔值是false呢？官方帮助文档中对interrupted方法的解释：

测试当前线程是否已经中断。线程的中断状态由该方法清除。换句话说，如果连续两次调用该方法，则第二次调用返回false。

isInterrupted()方法

下面来看一下isInterrupted()方法。

1
2
3
4
5
6
7
8
9
public class Run3 {
    public static void main(String args[]){
        Thread thread = new MyThread();
        thread.start();
        thread.interrupt();
        System.out.println("stop 1??" + thread.isInterrupted());
        System.out.println("stop 2??" + thread.isInterrupted());
    }
}

运行结果：

1
2
stop 1??true
stop 2??true

isInterrupted()并未清除状态，所以打印了两个true。

3. 能停止的线程–异常法

有了前面学习过的知识点，就可以在线程中用for语句来判断一下线程是否是停止状态，如果是停止状态，则后面的代码不再运行即可：

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
public class MyThread extends Thread {
    public void run(){
        super.run();
        for(int i=0; i<500000; i++){
            if(this.interrupted()) {
                System.out.println("线程已经终止， for循环不再执行");
                break;
            }
            System.out.println("i="+(i+1));
        }
    }
}

public class Run {
    public static void main(String args[]){
        Thread thread = new MyThread();
        thread.start();
        try {
            Thread.sleep(2000);
            thread.interrupt();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

运行结果：

1
2
3
4
5
6
...
i=202053
i=202054
i=202055
i=202056
线程已经终止， for循环不再执行

上面的示例虽然停止了线程，但如果for语句下面还有语句，还是会继续运行的。看下面的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class MyThread extends Thread {
    public void run(){
        super.run();
        for(int i=0; i<500000; i++){
            if(this.interrupted()) {
                System.out.println("线程已经终止， for循环不再执行");
                break;
            }
            System.out.println("i="+(i+1));
        }

        System.out.println("这是for循环外面的语句，也会被执行");
    }
}

使用Run.java执行的结果是：

1
2
3
4
5
6
...
i=180136
i=180137
i=180138
i=180139
线程已经终止， for循环不再执行

这是for循环外面的语句，也会被执行

如何解决语句继续运行的问题呢？看一下更新后的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class MyThread extends Thread {
    public void run(){
        super.run();
        try {
            for(int i=0; i<500000; i++){
                if(this.interrupted()) {
                    System.out.println("线程已经终止， for循环不再执行");
                        throw new InterruptedException();
                }
                System.out.println("i="+(i+1));
            }

            System.out.println("这是for循环外面的语句，也会被执行");
        } catch (InterruptedException e) {
            System.out.println("进入MyThread.java类中的catch了。。。");
            e.printStackTrace();
        }
    }
}

使用Run.java运行的结果如下：

1
2
3
4
5
6
7
8
...
i=203798
i=203799
i=203800
线程已经终止， for循环不再执行
进入MyThread.java类中的catch了。。。
java.lang.InterruptedException
    at thread.MyThread.run(MyThread.java:13)

4. 在沉睡中停止

如果线程在sleep()状态下停止线程，会是什么效果呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class MyThread extends Thread {
    public void run(){
        super.run();

        try {
            System.out.println("线程开始。。。");
            Thread.sleep(200000);
            System.out.println("线程结束。");
        } catch (InterruptedException e) {
            System.out.println("在沉睡中被停止, 进入catch， 调用isInterrupted()方法的结果是：" + this.isInterrupted());
            e.printStackTrace();
        }

    }
}

使用Run.java运行的结果是：

1
2
3
4
5
线程开始。。。
在沉睡中被停止, 进入catch， 调用isInterrupted()方法的结果是：false
java.lang.InterruptedException: sleep interrupted
    at java.lang.Thread.sleep(Native Method)
    at thread.MyThread.run(MyThread.java:12)

从打印的结果来看， 如果在sleep状态下停止某一线程，会进入catch语句，并且清除停止状态值，使之变为false。

前一个实验是先sleep然后再用interrupt()停止，与之相反的操作在学习过程中也要注意：

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
public class MyThread extends Thread {
    public void run(){
        super.run();
        try {
            System.out.println("线程开始。。。");
            for(int i=0; i<10000; i++){
                System.out.println("i=" + i);
            }
            Thread.sleep(200000);
            System.out.println("线程结束。");
        } catch (InterruptedException e) {
             System.out.println("先停止，再遇到sleep，进入catch异常");
            e.printStackTrace();
        }

    }
}

public class Run {
    public static void main(String args[]){
        Thread thread = new MyThread();
        thread.start();
        thread.interrupt();
    }
}

运行结果：

1
2
3
4
5
6
i=9998
i=9999
先停止，再遇到sleep，进入catch异常
java.lang.InterruptedException: sleep interrupted
    at java.lang.Thread.sleep(Native Method)
    at thread.MyThread.run(MyThread.java:15)

5. 能停止的线程—暴力停止

使用stop()方法停止线程则是非常暴力的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class MyThread extends Thread {
    private int i = 0;
    public void run(){
        super.run();
        try {
            while (true){
                System.out.println("i=" + i);
                i++;
                Thread.sleep(200);
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

public class Run {
    public static void main(String args[]) throws InterruptedException {
        Thread thread = new MyThread();
        thread.start();
        Thread.sleep(2000);
        thread.stop();
    }
}

运行结果：

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

Process finished with exit code 0

6.方法stop()与java.lang.ThreadDeath异常

调用stop()方法时会抛出java.lang.ThreadDeath异常，但是通常情况下，此异常不需要显示地捕捉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class MyThread extends Thread {
    private int i = 0;
    public void run(){
        super.run();
        try {
            this.stop();
        } catch (ThreadDeath e) {
            System.out.println("进入异常catch");
            e.printStackTrace();
        }
    }
}

public class Run {
    public static void main(String args[]) throws InterruptedException {
        Thread thread = new MyThread();
        thread.start();
    }
}

stop()方法以及作废，因为如果强制让线程停止有可能使一些清理性的工作得不到完成。另外一个情况就是对锁定的对象进行了解锁，导致数据得不到同步的处理，出现数据不一致的问题。

7. 释放锁的不良后果

使用stop()释放锁将会给数据造成不一致性的结果。如果出现这样的情况，程序处理的数据就有可能遭到破坏，最终导致程序执行的流程错误，一定要特别注意：

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
public class SynchronizedObject {
    private String name = "a";
    private String password = "aa";

    public synchronized void printString(String name, String password){
        try {
            this.name = name;
            Thread.sleep(100000);
            this.password = password;
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getPassword() {
        return password;
    }

    public void setPassword(String password) {
        this.password = password;
    }
}

public class MyThread extends Thread {
    private SynchronizedObject synchronizedObject;
    public MyThread(SynchronizedObject synchronizedObject){
        this.synchronizedObject = synchronizedObject;
    }

    public void run(){
        synchronizedObject.printString("b", "bb");
    }
}

public class Run {
    public static void main(String args[]) throws InterruptedException {
        SynchronizedObject synchronizedObject = new SynchronizedObject();
        Thread thread = new MyThread(synchronizedObject);
        thread.start();
        Thread.sleep(500);
        thread.stop();
        System.out.println(synchronizedObject.getName() + "  " + synchronizedObject.getPassword());
    }
}

输出结果：

1
b  aa

由于stop()方法以及在JDK中被标明为“过期/作废”的方法，显然它在功能上具有缺陷，所以不建议在程序张使用stop()方法。

8. 使用return停止线程

将方法interrupt()与return结合使用也能实现停止线程的效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class MyThread extends Thread {
    public void run(){
        while (true){
            if(this.isInterrupted()){
                System.out.println("线程被停止了！");
                return;
            }
            System.out.println("Time: " + System.currentTimeMillis());
        }
    }
}

public class Run {
    public static void main(String args[]) throws InterruptedException {
        Thread thread = new MyThread();
        thread.start();
        Thread.sleep(2000);
        thread.interrupt();
    }
}

输出结果：

1
2
3
4
5
...
Time: 1467072288503
Time: 1467072288503
Time: 1467072288503
线程被停止了！

不过还是建议使用“抛异常”的方法来实现线程的停止，因为在catch块中还可以将异常向上抛，使线程停止事件得以传播。

本文整理自

如何停止一个正在运行的线程

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

发表于 分类于
本文字数： 9.7k 阅读时长 ≈ 9 分钟

无处不在的C/S架构

在这个充斥着云的时代,我们使用的软件可以说99%都是C/S架构的！

  • 你发邮件用的Outlook,Foxmail等
  • 你看视频用的优酷，土豆等
  • 你写文档用的Office365,googleDoc，Evernote等
  • 你浏览网页用的IE,Chrome等(B/S是特殊的C/S)
  • ……

C/S架构的软件带来的一个明显的好处就是：只要有网络，你可以在任何地方干同一件事。

例如：你在家里使用Office365编写了文档。到了公司，只要打开编辑地址就可以看到在家里编写的文档，进行展示或者继续编辑。甚至在手机上进行阅读与编辑。不再需要U盘拷来拷去了。

C/S架构可以抽象为如下模型：

img

  • C就是Client(客户端),上面的B是Browser(浏览器)
  • S就是Server(服务器)：服务器管理某种资源，并且通过操作这种资源来为它的客户端提供某种服务

C/S架构之所以能够流行的一个主要原因就是网速的提高以及费用的降低，特别是无线网络速度的提高。试想在2G时代，大家最多就是看看文字网页，小说什么的。看图片，那简直就是奢侈！更别说看视频了！

网速的提高，使得越来越多的人使用网络，例如：优酷，微信都是上亿用户量，更别说天猫双11的瞬间访问量了！这就对服务器有很高的要求！能够快速处理海量的用户请求！那服务器如何能快速的处理用户的请求呢？

高性能服务器

高性能服务器至少要满足如下几个需求：

  • 效率高：既然是高性能，那处理客户端请求的效率当然要很高了
  • 高可用：不能随便就挂掉了
  • 编程简单：基于此服务器进行业务开发需要足够简单
  • 可扩展：可方便的扩展功能
  • 可伸缩：可简单的通过部署的方式进行容量的伸缩，也就是服务需要无状态

而满足如上需求的一个基础就是高性能的IO!

Socket

无论你是发邮件，浏览网页，还是看视频～实际底层都是使用的TCP/IP，而TCP/IP的编程抽象就是Socket!

我一直对Socket的中文翻译很困惑，个人觉得是我所接触的技术名词翻译里最莫名其妙的，没有之一！

Socket中文翻译为”套接字”！什么鬼？在很长的时间里我都无法将其和网络编程关联上！后来专门找了一些资料，最后在知乎上找到了一个还算满意的答案(具体链接，请见文末的参考资料链接)！

Socket的原意是插口，想表达的意思是插口与插槽的关系！”send socket”插到”receive socket”里，建立了链接，然后就可以通信了！

套接字的翻译，应该是参考了套接管(如下图)！从这个层面上来看，是有那么点意思！

img

套接字这个翻译已经是标准了，不纠结这个了！

我们看一下Socket之间建立链接及通信的过程！实际上就是对TCP/IP连接与通信过程的抽象:

img

  • 服务端Socket会bind到指定的端口上，Listen客户端的”插入”
  • 客户端Socket会Connect到服务端
  • 当服务端Accept到客户端连接后
  • 就可以进行发送与接收消息了
  • 通信完成后即可Close

对于IO来说，我们听得比较多的是:

  • BIO:阻塞IO
  • NIO:非阻塞IO
  • 同步IO
  • 异步IO

以及其组合:

  • 同步阻塞IO
  • 同步非阻塞IO
  • 异步阻塞IO
  • 异步非阻塞IO

那么什么是阻塞IO、非阻塞IO、同步IO、异步IO呢？

  • 一个IO操作其实分成了两个步骤：发起IO请求和实际的IO操作
  • 阻塞IO和非阻塞IO的区别在于第一步：发起IO请求是否会被阻塞，如果阻塞直到完成那么就是传统的阻塞IO;如果不阻塞，那么就是非阻塞IO
  • 同步IO和异步IO的区别就在于第二个步骤是否阻塞，如果实际的IO读写阻塞请求进程，那么就是同步IO，因此阻塞IO、非阻塞IO、IO复用、信号驱动IO都是同步IO;如果不阻塞，而是操作系统帮你做完IO操作再将结果返回给你，那么就是异步IO

举个不太恰当的例子 ：比如你家网络断了，你打电话去中国电信报修！

  • 你拨号—客户端连接服务器
  • 电话通了—连接建立
  • 你说：“我家网断了,帮我修下”—发送消息
  • 说完你就在那里等，那么就是阻塞IO
  • 如果正好你有事，你放下带电话，然后处理其他事情了，过一会你来问下，修好了没—那就是非阻塞IO
  • 如果客服说：“马上帮你处理，你稍等”—同步IO
  • 如果客服说：“马上帮你处理，好了通知你”，然后挂了电话—异步IO

本文只讨论BIO和NIO,AIO使用度没有前两者普及，暂不讨论！

下面从代码层面看看BIO与NIO的流程!

BIO

  • 客户端代码
1
2
3
4
5
6
7
8
9
10
//Bind,Connect
Socket client = new Socket("127.0.0.1",7777);    
//读写
PrintWriter pw = new PrintWriter(client.getOutputStream());
BufferedReader br=
        new BufferedReader(new InputStreamReader(System.in));  
pw.write(br.readLine());  
//Close
pw.close();  
br.close();
  • 服务端代码
1
2
3
4
5
6
7
8
9
10
11
Socket socket;  
//Bind,Listen
ServerSocket ss = new ServerSocket(7777);  
while (true) {  
    //Accept
    socket = ss.accept();  
    //一般新建一个线程执行读写
    BufferedReader br = new BufferedReader(
            new InputStreamReader(socket  .getInputStream()));  
    System.out.println("you input is : " + br.readLine());  
}
  • 上面的代码可以说是学习Java的Socket的入门级代码了
  • 代码流程和前面的图可以一一对上

模型图如下所示：

img

BIO优缺点

  • 优点
    • 模型简单
    • 编码简单
  • 缺点
    • 性能瓶颈低

优缺点很明显。这里主要说下缺点：主要瓶颈在线程上。每个连接都会建立一个线程。虽然线程消耗比进程小，但是一台机器实际上能建立的有效线程有限，以Java来说，1.5以后，一个线程大致消耗1M内存！且随着线程数量的增加，CPU切换线程上下文的消耗也随之增加，在高过某个阀值后，继续增加线程，性能不增反降！而同样因为一个连接就新建一个线程，所以编码模型很简单！

就性能瓶颈这一点，就确定了BIO并不适合进行高性能服务器的开发！像Tomcat这样的Web服务器，从7开始就从BIO改成了NIO，来提高服务器性能！

NIO

  • NIO客户端代码(连接)
1
2
3
4
5
6
7
8
//获取socket通道
SocketChannel channel = SocketChannel.open();        
channel.configureBlocking(false);
//获得通道管理器
selector=Selector.open();        
channel.connect(new InetSocketAddress(serverIp, port));
//为该通道注册SelectionKey.OP_CONNECT事件
channel.register(selector, SelectionKey.OP_CONNECT);
  • NIO客户端代码(监听)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
while(true){
    //选择注册过的io操作的事件(第一次为SelectionKey.OP_CONNECT)
   selector.select();
   while(SelectionKey key : selector.selectedKeys()){
       if(key.isConnectable()){
           SocketChannel channel=(SocketChannel)key.channel();
           if(channel.isConnectionPending()){
               channel.finishConnect();//如果正在连接，则完成连接
           }
           channel.register(selector, SelectionKey.OP_READ);
       }else if(key.isReadable()){ //有可读数据事件。
           SocketChannel channel = (SocketChannel)key.channel();
           ByteBuffer buffer = ByteBuffer.allocate(10);
           channel.read(buffer);
           byte[] data = buffer.array();
           String message = new String(data);
           System.out.println("recevie message from server:, size:"
               + buffer.position() + " msg: " + message);
       }
   }
}
  • NIO服务端代码(连接)
1
2
3
4
5
6
7
8
//获取一个ServerSocket通道
ServerSocketChannel serverChannel = ServerSocketChannel.open();
serverChannel.configureBlocking(false);
serverChannel.socket().bind(new InetSocketAddress(port));
//获取通道管理器
selector = Selector.open();
//将通道管理器与通道绑定，并为该通道注册SelectionKey.OP_ACCEPT事件，
serverChannel.register(selector, SelectionKey.OP_ACCEPT);
  • NIO服务端代码(监听)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while(true){
    //当有注册的事件到达时，方法返回，否则阻塞。
   selector.select();
   for(SelectionKey key : selector.selectedKeys()){
       if(key.isAcceptable()){
           ServerSocketChannel server =
                (ServerSocketChannel)key.channel();
           SocketChannel channel = server.accept();
           channel.write(ByteBuffer.wrap(
            new String("send message to client").getBytes()));
           //在与客户端连接成功后，为客户端通道注册SelectionKey.OP_READ事件。
           channel.register(selector, SelectionKey.OP_READ);
       }else if(key.isReadable()){//有可读数据事件
           SocketChannel channel = (SocketChannel)key.channel();
           ByteBuffer buffer = ByteBuffer.allocate(10);
           int read = channel.read(buffer);
           byte[] data = buffer.array();
           String message = new String(data);
           System.out.println("receive message from client, size:"
               + buffer.position() + " msg: " + message);
       }
   }
}

NIO模型示例如下：

img

  • Acceptor注册Selector，监听accept事件
  • 当客户端连接后，触发accept事件
  • 服务器构建对应的Channel，并在其上注册Selector，监听读写事件
  • 当发生读写事件后，进行相应的读写处理

NIO优缺点

  • 优点
    • 性能瓶颈高
  • 缺点
    • 模型复杂
    • 编码复杂
    • 需处理半包问题

NIO的优缺点和BIO就完全相反了!性能高，不用一个连接就建一个线程，可以一个线程处理所有的连接！相应的，编码就复杂很多，从上面的代码就可以明显体会到了。还有一个问题，由于是非阻塞的，应用无法知道什么时候消息读完了，就存在了半包问题！

半包问题

简单看一下下面的图就能理解半包问题了！

img

img

我们知道TCP/IP在发送消息的时候，可能会拆包(如上图1)！这就导致接收端无法知道什么时候收到的数据是一个完整的数据。例如:发送端分别发送了ABC,DEF,GHI三条信息，发送时被拆成了AB,CDRFG,H,I这四个包进行发送，接受端如何将其进行还原呢？在BIO模型中，当读不到数据后会阻塞，而NIO中不会!所以需要自行进行处理!例如，以换行符作为判断依据，或者定长消息发生，或者自定义协议！

NIO虽然性能高，但是编码复杂，且需要处理半包问题！为了方便的进行NIO开发，就有了Reactor模型!

Reactor模型

  • AWT Events

img

Reactor模型和AWT事件模型很像，就是将消息放到了一个队列中，通过异步线程池对其进行消费！

Reactor中的组件

  • Reactor:Reactor是IO事件的派发者。
  • Acceptor:Acceptor接受client连接，建立对应client的Handler，并向Reactor注册此Handler。
  • Handler:和一个client通讯的实体，按这样的过程实现业务的处理。一般在基本的Handler基础上还会有更进一步的层次划分， 用来抽象诸如decode，process和encoder这些过程。比如对Web Server而言，decode通常是HTTP请求的解析， process的过程会进一步涉及到Listener和Servlet的调用。业务逻辑的处理在Reactor模式里被分散的IO事件所打破， 所以Handler需要有适当的机制在所需的信息还不全（读到一半）的时候保存上下文，并在下一次IO事件到来的时候（另一半可读了）能继续中断的处理。为了简化设计，Handler通常被设计成状态机，按GoF的state pattern来实现。

对应上面的NIO代码来看:

  • Reactor：相当于有分发功能的Selector
  • Acceptor：NIO中建立连接的那个判断分支
  • Handler：消息读写处理等操作类

Reactor从线程池和Reactor的选择上可以细分为如下几种：

Reactor单线程模型

img

这个模型和上面的NIO流程很类似，只是将消息相关处理独立到了Handler中去了！同时我们可以看到IO操作和非IO操作混在Handler处理当中,如果非IO操作很慢,会影响接受IO请求的速度.

我们看一个客户端的情况，如果这个客户端多次进行请求，如果在Handler中的处理速度较慢，那么后续的客户端请求都会被积压，导致响应变慢！所以引入了Reactor多线程模型!

Reactor多线程模型

img

Reactor多线程模型就是将Handler中的IO操作和非IO操作分开，操作IO的线程称为IO线程，非IO操作的线程称为工作线程!这样的话，客户端的请求会直接被丢到线程池中，客户端发送请求就不会堵塞！

但是当用户进一步增加的时候，Reactor会出现瓶颈！因为Reactor既要处理IO操作请求，又要响应连接请求！为了分担Reactor的负担，所以引入了主从Reactor模型!

主从Reactor模型

img

主Reactor用于响应连接请求，从Reactor用于处理IO操作请求！

Netty

Netty是一个高性能NIO框架，其是对Reactor模型的一个实现！

  • Netty客户端代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
EventLoopGroup workerGroup = new NioEventLoopGroup();
try {
    Bootstrap b = new Bootstrap();
    b.group(workerGroup);
    b.channel(NioSocketChannel.class);
    b.option(ChannelOption.SO_KEEPALIVE, true);
    b.handler(new ChannelInitializer<SocketChannel>() {
        @Override
        public void initChannel(SocketChannel ch) throws Exception {
            ch.pipeline().addLast(new TimeClientHandler());
        }
    });

    ChannelFuture f = b.connect(host, port).sync();

    f.channel().closeFuture().sync();
} finally {
    workerGroup.shutdownGracefully();
}
  • Netty Client Handler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class TimeClientHandler extends ChannelInboundHandlerAdapter {
    @Override
    public void channelRead(ChannelHandlerContext ctx, Object msg) {
        ByteBuf m = (ByteBuf) msg;
        try {
            long currentTimeMillis =
                (m.readUnsignedInt() - 2208988800L) * 1000L;
            System.out.println(new Date(currentTimeMillis));
            ctx.close();
        } finally {
            m.release();
        }
    }

    @Override
    public void exceptionCaught(ChannelHandlerContext ctx,
                Throwable cause) {
        cause.printStackTrace();
        ctx.close();
    }
}
  • Netty服务端代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
EventLoopGroup bossGroup = new NioEventLoopGroup();
EventLoopGroup workerGroup = new NioEventLoopGroup();
try {
    ServerBootstrap b = new ServerBootstrap();
    b.group(bossGroup, workerGroup)
     .channel(NioServerSocketChannel.class)
     .childHandler(new ChannelInitializer<SocketChannel>() {
         @Override
         public void initChannel(SocketChannel ch) throws Exception {
             ch.pipeline().addLast(new TimeServerHandler());
         }
     })
     .option(ChannelOption.SO_BACKLOG, 128)  
     .childOption(ChannelOption.SO_KEEPALIVE, true);
    // Bind and start to accept incoming connections.
    ChannelFuture f = b.bind(port).sync();
    f.channel().closeFuture().sync();
} finally {
    workerGroup.shutdownGracefully();
    bossGroup.shutdownGracefully();
}
  • Netty Server Handler
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
public class TimeServerHandler extends ChannelInboundHandlerAdapter {

    @Override
    public void channelActive(final ChannelHandlerContext ctx) {
        final ByteBuf time = ctx.alloc().buffer(4);
        time.writeInt((int)
            (System.currentTimeMillis() / 1000L + 2208988800L));

        final ChannelFuture f = ctx.writeAndFlush(time);
        f.addListener(new ChannelFutureListener() {
            @Override
            public void operationComplete(ChannelFuture future) {
                assert f == future;
                ctx.close();
            }
        });
    }

    @Override
    public void exceptionCaught(ChannelHandlerContext ctx,
        Throwable cause) {
        cause.printStackTrace();
        ctx.close();
    }
}

我们从Netty服务器代码来看，与Reactor模型进行对应！

  • EventLoopGroup就相当于是Reactor，bossGroup对应主Reactor,workerGroup对应从Reactor
  • TimeServerHandler就是Handler
  • child开头的方法配置的是客户端channel，非child开头的方法配置的是服务端channel

具体Netty内容，请访问Netty官网！

Netty的问题

Netty开发中一个很明显的问题就是回调，一是打破了线性编码习惯，
二就是Callback Hell！

看下面这个例子：

1
2
3
a.doing1();  //1
a.doing2();  //2
a.doing3();  //3

1,2,3处代码如果是同步的，那么将按顺序执行！但是如果不是同步的呢？我还是希望2在1之后执行，3在2之后执行！怎么办呢？想想AJAX!我们需要写类似如下这样的代码！

1
2
3
4
5
6
7
8
9
a.doing1(new Callback(){
    public void callback(){
        a.doing2(new Callback(){
            public void callback(){
                a.doing3();
            }
        })
    }
});

那有没有办法解决这个问题呢？其实不难，实现一个类似Future的功能！当Client获取结果时，进行阻塞，当得到结果后再继续往下走！实现方案，一个就是使用锁了，还有一个就是使用RingBuffer。经测试，使用RingBuffer比使用锁TPS有2000左右的提高！

img

本文整理自

高性能Server—Reactor模型

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

发表于 分类于
本文字数： 12k 阅读时长 ≈ 11 分钟

在数据结构与算法–索引 https://url.wx-coder.cn/O07eI 一节中，我们讨论了 B+Tree, LSM-Tree 这样的文件索引以及全文索引的基础算法，本文则会针对文件索引在关系型数据库中的实际应用进行探讨。

索引（Index）是帮助数据库系统高效获取数据的数据结构，而数据库索引本质上是以增加额外的写操作，与用于维护索引数据结构的存储空间为代价的，用于提升数据库中数据检索效率的数据结构。索引可以帮助我们快速地定位到数据而不需要每次搜索的时候都遍历数据库中的每一行。当然，索引不是建立的越多、越长越好，因为索引除了占用空间之外，对后续数据库的增加、删除、修改都有额外的操作来更新索引。

一般来说，小表使用全表扫描更快，中大表才使用索引，而超级大表索引基本无效，我们可能需要借助独立的全文索引系统；MySQL 自带的全文索引只能用于 InnoDB、MyISAM ，并且只能对英文进行全文检索，所以一般会使用 Elasticsearch，Solr 这样的全文索引(搜索)引擎。

索引类型

从索引的实现上，我们可以将其分为聚集索引与非聚集索引(或称辅助索引或二级索引Secondary key)，这两大类；从索引的实际应用中，又可以细分为普通索引、唯一索引、主键索引、联合索引、外键索引、全文索引这几种。

InnoDB 使用的是聚集索引，因为它的 B+ 树的叶结点包含了完整的数据记录。InnoDB 的数据文件本身就是索引文件，表数据文件本身就是按 B+Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说，InnoDB 的所有辅助索引都引用主键作为 data 域。

img

而 MyISAM 方式 B+ 树的叶结点只是存储了数据的地址，故称为非聚集索引。MyISAM 引擎使用 B+Tree 作为索引结构，叶节点的 data 域存放的是数据记录的地址；在 MyISAM 中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。

在 InnoDB 中，又有聚簇索引和普通索引之分，聚簇索引根据主键来构建，叶子节点存放的是该主键对应的这一行记录，根据主键查询可以直接利用聚簇索引定位到所在记录。而普通索引根据申明这个索引时候的列来构建，叶子节点存放的是这一行记录对应的主键的值，根据普通索引查询需要先在普通索引上找到对应的主键的值，然后根据主键值去聚簇索引上查找记录，俗称回表。如果我们查询一整行记录的话，一定要去聚簇索引上查找，而如果我们只需要根据普通索引查询主键的值，由于这些值在普通索引上已经存在，所以并不需要回表，这个称为索引覆盖，在一定程度上可以提高查询效率。

img

普通索引中还有唯一索引和联合索引两个特例，唯一索引在插入和修改的时候会校验该索引对应的列的值是否已经存在，联合索引将两个列的值按照申明时候的顺序进行拼接后在构建索引。

数据行并不是存储引擎管理的最小存储单位，索引只能够帮助我们定位到某个数据页，每一次磁盘读写的最小单位为也是数据页，而一个数据页内存储了多个数据行，我们需要了解数据页的内部结构才能知道存储引擎怎么定位到某一个数据行，可以参考 MySQL 存储管理 https://url.wx-coder.cn/IF5HH 系列。

索引选择性

对索引列和字符串前缀长度，都参考选择性（Selectivity）这个指标来确定：选择性定义为不重复的索引值和数据总记录条数的比值，其选择性越高，那么索引的查询效率也越高，譬如对于性别这种参数，建立索引根本没有意义。

1
2
Index Selectivity = Cardinality / #T
复制代码

显然选择性的取值范围为 (0, 1]，选择性越高的索引价值越大，这是由 B+Tree 的性质决定的。在实际的数据库中，我们可以通过以下语句来计算某列的选择性：

1
2
SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM titles;
复制代码

主键

在 InnoDB 内部，表数据是优化主键快速查询而排列分布的，其查找速度是最快的，该索引中键值的逻辑顺序决定了表中相应行的物理顺序。即使表中没有适合做主键的列，也推荐采用一个自动增长的整数主键(代理键)，那么这个表在增加数据的时候是顺序存放的，而且后续在别的表参考该外键查询的时候也会得到优化。

如果在创建表时没有显式地定义主键（Primary Key），则 InnoDB 存储引擎会按如下方式选择或创建主键：

  • 首先表中是否有非空的唯一索引（Unique NOT NULL），如果有，则该列即为主键。
  • 不符合上述条件，InnoDB 存储引擎自动创建一个 6 个字节大小的指针，用户不能查看或访问。

主键的选择

在分布式 ID https://url.wx-coder.cn/tQ5eH 一文中我们讨论过分布式场景下的分布式 ID 的选择策略，而在数据库中，我们同样会有这样的考量。首先，MySQL 官方有明确的建议主键要尽量越短越好，36 个字符长度的 UUID 不符合要求；如果主键是一个很长的字符串并且建了很多普通索引，将造成普通索引占有很大的物理空间。并且主键最好是顺序递增的，否则在 InnoDB 引擎下，UUID 的无序性可能会引起数据位置频繁变动，严重影响性能。

img

自增 ID 在插入的时候可以保证相邻的两条记录可能在同一个数据块，而订单号这样的业务相关的连续性设计上可能没有自增 ID 好，导致连续插入可能在多个数据块，增加了磁盘读写次数。

  • 唯一性：自增 ID 很容易会被暴力破解，数据迁移的时候，特别是发生表格合并这种操作的时候，会不可避免地存在冲突。UUID 则能够保证唯一性，彻底避免冲突。
  • 键长度：自增字段的长度较 UUID 小很多，这会对检索的性能有较大影响。Innodb 引擎进行数据检索时，也是先根据索引找到主键，然后根据主键找到记录；这样在主键长度短的情况下，会有较好的读性能。
  • 并发性：自增 ID 并且高并发的情况下，竞争自增锁会降低数据库的吞吐能力。UUID 则能够在应用层生成 UUID，提高数据库的吞吐能力。
  • 数据库索引：InnoDB 中表数据是按照主键顺序存放的，在写入数据时候如果发生了随机 IO，那么就会频繁地移动磁盘块。当数据量大的时候，写的短板将非常明显。自增 ID 中新增的数据可以默认按序排列，对于性能有很大的提升；UUID 则主键之间没有顺序规律。

主键与唯一索引

主键就是唯一索引，但是唯一索引不一定是主键，唯一索引可以为空，但是空值只能有一个，主键不能为空。对于单列索引，要求该列所有数据都不相同，但允许有 NULL 值；对于多列的联合索引，要求这些列的组合是唯一的。唯一索引其本身既可以作为索引，实际中也可以用以产生数据约束，防止增加或者修改后产生相同数据，从而保证数据的完整性。

对于字符串类型，可以指定索引前缀长度(且对于 BLOB/TEXT 前缀长度参数是必须的)，在 InnoDB 表中其前缀长度最长是 767 bytes，且参数 M 是用 bytes 计量的。所以太长的字符串，建立 B+Tree 索引浪费比较大，这时候用手动模拟 HASH 索引是个方法，不过这种方式对字符串无法灵活的使用前缀方式查询(例如 LIKE 这类的操作)。

联合索引

单列索引指的是在表上为某一个字段建立的索引，一般索引的创建选择整型或者较小的定长字符串将更有利于效率的提升。联合索引指的是多个字段按照一定顺序组织的索引。以索引 (name, city, gender) 为例，其首先是按照 name 字段顺序组织的，当 name 字段的值相同时（如 Bush），其按照 city 字段顺序组织，当 city 字段值相同时，其按照 gender 字段组织。由于联合索引上通过多个列构建索引，有时候我们可以将需要频繁查询的字段加到联合索引里面，譬如经常需要根据 name 查找 age 我们可以建一个 name 和 age 的联合索引。

常见的条件联合包括了 WHERE 条件联合与 ORDER BY 条件联合；所谓 WHERE 条件联合指的是，对于 WHERE 条件中的等值条件，其字段使用与联合索引的字段一致（顺序可以不一致）。

ORDER BY 联合指的是如果 ORDER BY 后面的字段是联合索引覆盖 where 条件之后的一个字段，由于索引已经处于有序状态，MySQL 就会直接从索引上读取有序的数据，然后在磁盘上读取数据之后按照该顺序组织数据，从而减少了对磁盘数据进行排序的操作。即对于未覆盖 ORDER BY 的查询，其有一项 Creating sort index，即为磁盘数据进行排序的耗时最高；对于覆盖 ORDER BY 的查询，其就不需要进行排序，而其耗时主要体现在从磁盘上拉取数据的过程。

前缀索引

MySQL 的前缀索引可以分为三类：联合索引前缀，like 前缀和字符串前缀。

联合索引前缀与最左匹配（Leftmost Prefix）

联合索引前缀指的是在建立多列索引的时候，必须按照从左到右的顺序使用全部或部分的索引列，才能充分的使用联合索引，比如：(col1, col2, col3) 使用 (col1)、(col1, col2)、(col1, col2, col3) 有效。在查询语句中会一直向右匹配直到遇到范围查询 (>,<,BETWEEN,LIKE) 就停止匹配，其后的索引列将不会使用索引来优化查找了。

以 (name, city, interest) 三个字段联合的索引为例，如果查询条件为 where name='Bush'; 那么就只需要根据 B+树定位到 name 字段第一个 Bush 所在的值，然后顺序扫描后续数据，直到找到第一个不为 Bush 的数据即可，扫描过程中将该索引片的数据 id 记录下来，最后根据 id 查询聚簇索引获取结果集。同理对于查询条件为 where name='Bush' and city='Chicago'; 的查询，MySQL 可以根据联合索引直接定位到中间灰色部分的索引片，然后获取该索引片的数据 id，最后根据 id 查询聚簇索引获取结果集。

由此我们可以得出联合索引前缀的注意点：

  • 无法跨越字段使用联合索引，如 where name='Bush' and interest='baseball';，对于该查询，name 字段是可以使用联合索引的第一个字段过滤大部分数据的，但是对于 interest 字段，其无法通过 B+ 树的特性直接定位第三个字段的索引片数据，比如这里的 baseball 可能分散在了第二条和第七条数据之中。最终，interest 字段其实进行的是覆盖索引扫描。
  • 对于非等值条件，如 >、<、!= 等，联合索引前缀对于索引片的过滤只能到第一个使用非等值条件的字段为止，后续字段虽然在联合索引上也无法参与索引片的过滤。这里比如 where name='Bush' and city>'Chicago' and interest='baseball';，对于该查询条件，首先可以根据 name 字段过滤索引片中第一个字段的非 Bush 的数据，然后根据联合索引的第二个字段定位到索引片的 Chicago 位置，由于其是非等值条件，这里 MySQL 就会从定位的 Chicago 往下顺序扫描，由于 interest 字段是可能分散在索引第三个字段的任何位置的，因而第三个字段无法参与索引片的过滤。

因此 B-Tree 的列顺序非常重要，上述使用规则都和列顺序有关。对于实际的应用，一般要根据具体的需求，创建不同列和不同列顺序的索引。假设有索引 Index(A,B,C):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 使用索引
A>5 AND A<10 - 最左前缀匹配
A=5 AND B>6 - 最左前缀匹配
A=5 AND B=6 AND C=7 - 全列匹配
A=5 AND B IN (2,3) AND C>5 - 最左前缀匹配，填坑

# 不能使用索引
B>5 - 没有包含最左前缀
B=6 AND C=7 - 没有包含最左前缀

# 使用部分索引
A>5 AND B=2 - 使用索引 A 列
A=5 AND B>6 AND C=2 - 使用索引的 A 和 B 列
复制代码

使用索引对结果进行排序，需要索引的顺序和 ORDER BY 子句中的顺序一致，并且所有列的升降序一致(ASC/DESC)。如果查询连接了多个表，只有在 ORDER BY 的列引用的是第一个表才可以(需要按序 JOIN)。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 使用索引排序
ORDER BY A - 最左前缀匹配
WHERE A=5 ORDER BY B,C - 最左前缀匹配
WHERE A=5 ORDER BY B DESC - 最左前缀匹配
WHERE A>5 ORDER BY A,B - 最左前缀匹配

# 不能使用索引排序
WHERE A=5 ORDER BY B DESC,C ASC - 升降序不一致
WHERE A=5 ORDER BY B,D - D 不在索引中
WHERE A=5 ORDER BY C - 没有包含最左前缀
WHERE A>5 ORDER BY B,C - 第一列是范围条件，无法使用 BC 排序
WHERE A=5 AND B IN(1, 2) ORDER BY C - B 也是范围条件，无法用 C 排序
复制代码

like 前缀

对于 like 前缀，其是指在使用 like 查询时，如果使用的表达式为 first_name like 'rMq%';那么其是可以用到 first_name 字段的索引的。但是对于 first_name like '%Chu%';，其就无法使用 first_name 的索引。对于 like 前缀，MySQL 底层实际上是使用了一个补全策略来使用索引的，比如这里 first_name like 'rMq%';，MySQL 会将其补全为两条数据：rMqAAAAA 和 rMqzzzzz，后面补全部分的长度为当前字段的最大长度。在使用索引查询时，MySQL 就使用这两条数据进行索引定位，最后需要的结果集就是这两个定位点的中间部分的数据。如下是使用 like 前缀的一个示意图：

img

字符串前缀

字符串前缀索引指的是只取字符串前几个字符建立的索引。在进行查询时，如果一个字段值较长，那么为其建立索引的成本将非常高，并且查询效率也比较低，字符串前缀索引就是为了解决这一问题而存在的。字符串前缀索引主要应用在两个方面：

  • 字段前缀部分的选择性比较高；
  • 字段整体的选择性不太大（如果字段整体选择性比较大则可以使用哈希索引）。

譬如为 first_name 字段建立了长度为 4 的前缀索引，可以看到，如果查询使用的是 where first_name='qWhNIZqxcbD';，那么 MySQL 首先会截取等值条件的前四个字符，然后将其与字符串前缀索引进行比较，从而定位到前缀为”qWhN”的索引片，然后获取该索引片对应的磁盘数据，最后将获取的磁盘数据的 first_name 字段与查询的等值条件的值进行比较，从而得到结果集。

字符串前缀索引最需要注意的一个问题是如何选择前缀的长度，长度选择合适时，前缀索引的过滤性将和对整个字段建立索引的选择性几乎相等。这里我们就需要用到前面讲解的关于字段选择性的概念，即字段选择性为对该字段分组之后，数据量最大的组的数据量占总数据量的比例。这里选择前缀长度时，可以理解为，前缀的选择性为按照前缀分组之后，数据量最大的组占总数据量的比例。如下表所示为计算前缀长度的 SQL 公式：

1
2
3
4
5
select count(*) as cnt, first_name as perf from actor group by perf ORDER BY cnt desc limit 10;	-- 0
select count(*) as cnt, left(first_name, 2) as perf from actor group by perf ORDER BY cnt desc limit 10;	-- 2
select count(*) as cnt, left(first_name, 3) as perf from actor group by perf ORDER BY cnt desc limit 10;	-- 3
select count(*) as cnt, left(first_name, 4) as perf from actor group by perf ORDER BY cnt desc limit 10;	-- 4
复制代码

其他索引

覆盖索引

覆盖索引指的是对于查询中使用的除去参与索引过滤扫描的所有字段将其加入到该查询所使用的索引尾部的索引。覆盖索引扫描的优点在于由于查询中所使用的所有字段都在同一索引的字段，因而在进行查询时只需要在索引中获取相关数据即可，而不需要回磁盘扫描相应的数据，从而避免了查询中最耗时的磁盘 I/O 读取。对于如下查询：

1
2
select a, b, c from t where a='a' and b='b';
复制代码

该查询中如果建立联合索引(a, b, c)，那么这就是使用了覆盖扫描的索引，因为对于该查询，可以使用索引的前两个字段 a 和 b 根据 where 条件进行索引片的过滤，对过滤后的索引片直接在索引中读取 a, b, c 三个字段的值即可，而无需回表扫描。

三星索引

三星索引指的是对于一个查询，设立了三个通用的索引条件满足的条件，建立的索引对于特定的查询每满足一个条件就表示该索引得到一颗星，当该索引得到三颗星时就表示该索引对于该查询是一个三星索引。三星索引是对于特定查询的最优索引，建立三星索引的条件如下：

  • 取出所有的等值谓词的列 （WHERE COL=…） 作为索引开头的列；
  • 将 ORDER BY 中的列加入到索引中；
  • 将查询语句中剩余的列加入到索引中，将易变得列放到最后以降低更新成本。

譬如对于如下的查询，索引 (first_name, last_name, email) 就是一个三星索引：

1
2
SELECT first_name, last_name, email FROM user WHERE first_name = 'aa' ORDER BY last_name;
复制代码

三星索引的创建过程可以发现如下规律：

  • 覆盖等值谓词条件，如 first_name，可以过滤大部分的索引片数据；
  • 覆盖 order by 字段可以避免对结果集的排序，如 last_name;
  • 覆盖其余字段可以避免回磁盘读取数据，即使用了覆盖索引扫描，如 email。

索引存储结构

MySQL 查询的时候会先通过索引定位到对应的数据页，然后检测数据页是否在缓冲池内，如果在就直接返回，如果不在就去聚簇索引中通过磁盘 IO 读取对应的数据页并放入缓冲池。一个数据页会包含多个数据行。缓存池通过 LRU 算法对数据页进行管理，也就是最频繁使用的数据页排在列表前面，不经常使用的排在队尾，当缓冲池满了的时候会淘汰掉队尾的数据页。从磁盘新读取到的数据页并不会放在队列头部而是放在中间位置，这个中间位置可以通过参数进行修。缓冲池也可以设置多个实例，数据页根据哈希算法决定放在哪个缓冲池。

在 MySQL 存储结构一文中，我们讨论过 MySQL 数据页的存储结构。

Memory Architecture | 内存架构

InnoDB 的内存主要有以下几个部分组成：缓冲池 (buffer pool)、重做日志缓冲池(redo log buffer）以及额外的内存池（additional memory pool），如下图所示：

img

其中缓冲池占最大块内存，用来缓存各自数据，数据文件按页（每页 16K）读取到缓冲池，按最近最少使用算法（LRU）保留缓存数据。缓冲池缓冲的数据类型有：数据页、索引页、插入缓冲、自适应哈希索引、锁信息、数据字典信息等，其中数据页和索引页占了绝大部分内存。日志缓冲将重做日志信息先放入这个缓冲区，然后按一定频率（默认为 1s）将其刷新至重做日志文件。

InnoDB 通过一些列后台线程将相关操作进行异步处理，同时借助缓冲池来减小 CPU 和磁盘速度上的差异。当查询的时候会先通过索引定位到对应的数据页，然后检测数据页是否在缓冲池内，如果在就直接返回，如果不在就去聚簇索引中通过磁盘 IO 读取对应的数据页并放入缓冲池。一个数据页会包含多个数据行。缓存池通过 LRU 算法对数据页进行管理，也就是最频繁使用的数据页排在列表前面，不经常使用的排在队尾，当缓冲池满了的时候会淘汰掉队尾的数据页。从磁盘新读取到的数据页并不会放在队列头部而是放在中间位置，这个中间位置可以通过参数进行修。缓冲池也可以设置多个实例，数据页根据哈希算法决定放在哪个缓冲池。

Storage Architecture | 存储结构

InnoDB 存储引擎的逻辑存储结构和 Oracle 大致相同，所有数据都被逻辑地存放在一个空间中，我们称之为表空间（tablespace）。表空间又由段（segment）、区（extent）、页（page）组成。页在一些文档中有时也称为块（block），1 extent = 64 pages，InnoDB 存储引擎的逻辑存储结构大致如图所示：

img

表空间作为存储结构的最高层，所有数据都存放在表空间中，默认情况下用一个共享表空间 ibdata1 ，如果开启了 innodb_file_per_table 则每张表的数据将存储在单独的表空间中，也就是每张表都会有一个文件，

表空间由各个段构成，InnoDB 存储引擎由索引组织的，而索引中的叶子节点用来记录数据，存储在数据段，而非叶子节点用来构建索引，存储在索引段。区是由连续的页组成，任何情况下一个区都是 1MB，一个区中可以有多个页，每个页默认为 16KB ，所以默认情况下一个区中可以包含 64 个连续的页，页的大小是可以通过 innodb_page_size 设置，页中存储的是具体的行记录。一行记录最终以二进制的方式存储在文件里。

从物理意义上来看，InnoDB 表由共享表空间、日志文件组（更准确地说，应该是 Redo 文件组）、表结构定义文件组成。若将 innodb_file_per_table 设置为 on，则每个表将独立地产生一个表空间文件，以 ibd 结尾，数据、索引、表的内部数据字典信息都将保存在这个单独的表空间文件中。表结构定义文件以 frm 结尾，这个是与存储引擎无关的，任何存储引擎的表结构定义文件都一样，为 .frm 文件。

Process Architecture | 进程架构

默认情况下，InnoDB 的后台线程有 7 个，其中 4 个 IO thread, 1 个 Master thread, 1 个 Lock monitor thread, 一个 Error monitor thread。InnoDB 的主要工作都是在一个单独的 Master 线程里完成的。Master 线程的优先级最高，它主要分为以下几个循环：主循环（loop）、后台循环（background loop）、刷新循环（flush loop）、暂停循环（suspend loop）。

img

其中主循环的伪代码如下：

1
2
3
4
5
6
7
8
9
10
void master_thread() (
    loop:
    for (int i =0; i <10; i++){
        do thing once per second
        sleep 1 second if necessary
    }
    do things once per ten seconds
    goto loop;
}
复制代码
  • 其中每秒一次的操作包括：刷新日志缓冲区（总是），合并插入缓冲（可能），至多刷新 100 个脏数据页（可能），如果没有当前用户活动，切换至 background loop （可能）。
  • 其中每 10 秒一次的操作包括：合并至多 5 个插入缓冲（总是），刷新日志缓冲（总是），刷新 100 个或 10 个脏页到磁盘（总是），产生一个检查点（总是），删除无用 Undo 页 （总是）。
  • 后台循环，若当前没有用户活动或数据库关闭时，会切换至该循环执行以下操作：删除无用的 undo 页（总是），合并 20 个插入缓冲（总是），跳回到主循环（总是），不断刷新 100 个页，直到符合条件跳转到 flush loop（可能）。
  • 如果 flush loop 中也没有什么事情可做，边切换到 suspend loop，将 master 线程挂起。

索引与锁

MySQL 为我们提供了行锁、表锁、页锁三种级别的锁，其中表锁开销小，加锁快；不会出现死锁；锁定力度大，发生锁冲突概率高，并发度最低。行锁开销大，加锁慢；会出现死锁；锁定粒度小，发生锁冲突的概率低，并发度高；页锁开销和加锁速度介于表锁和行锁之间；会出现死锁；锁定粒度介于表锁和行锁之间，并发度一般。每个存储引擎都可以有自己的锁策略，例如 MyISAM 引擎仅支持表级锁，而 InnoDB 引擎除了支持表级锁外，也支持行级锁（默认）。

行锁 表锁 页锁
MyISAM √
BDB √ √
InnoDB √ √

InnoDB 行锁是通过给索引上的索引项加锁来实现的，这一点 MySQL 与 Oracle 不同，后者是通过在数据块中对相应数据行加锁来实现的。InnoDB 这种行锁实现特点意味着：只有通过索引条件检索数据，InnoDB 才使用行级锁，否则，InnoDB 将使用表锁，同样地，当 for update 的记录不存在会导致锁住全表。当表有多个索引的时候，不同的事务可以使用不同的索引锁定不同的行，另外，不论是使用主键索引、唯一索引或普通索引，InnoDB 都会使用行锁来对数据加锁。

InnoDB 的加锁过程比较复杂，将所有扫描到的记录都加锁，范围查询会加间隙锁，然后加锁过程按照两阶段锁 2PL 来实现，也就是先加锁，然后所有的锁在事物提交的时候释放。加锁的策略会和数据库的隔离级别有关，在默认的可重复读的隔离级别的情况下，加锁的流程还会和查询条件中是否包含索引，是主键索引还是普通索引，是否是唯一索引等有关。

譬如对于 select * from o_order where order_sn = '201912102322' for update; 这条 SQL 语句，在不同的索引情况下其加锁策略也不一致：

img

  • order_sn 是主键索引，这种情况将在主键索引上的 order_sn = 201912102322 这条记录上加排他锁。
  • order_sn 是普通索引，并且是唯一索引，将会对普通索引上对应的一条记录加排他锁，对主键索引上对应的记录加排他锁。
  • order_sn 是普通索引，并且不是唯一索引，将会对普通索引上 order_sn = 201912102322 一条或者多条记录加锁，并且对这些记录对应的主键索引上的记录加锁。这里除了加上行锁外，还会加上间隙锁，防止其他事务插入 order_sn = 201912102322 的记录，然而如果是唯一索引就不需要间隙锁，行锁就可以。
  • order_sn 上没有索引，innoDB 将会在主键索引上全表扫描，这里并没有加表锁，而是将所有的记录都会加上行级排他锁，而实际上 innoDB 内部做了优化，当扫描到一行记录后发现不匹配就会把锁给释放，当然这个违背了 2PL 原则在事务提交的时候释放。这里除了对记录进行加锁，还会对每两个记录之间的间隙加锁，所以最终将会保存所有的间隙锁和 order_sn = 201912102322 的行锁。
  • order_sn = 201912102322 这条记录不存在的情况下，如果 order_sn 是主键索引，则会加一个间隙锁，而这个间隙是主键索引中 order_sn 小于 201912102322 的第一条记录到大于 201912102322 的第一条记录。试想一下如果不加间隙锁，如果其他事物插入了一条 order_sn = 201912102322 的记录，由于 select for update 是当前读，即使上面那个事物没有提交，如果在该事物中重新查询一次就会发生幻读。
  • 如果没有索引，则对扫描到的所有记录和间隙都加锁，如果不匹配行锁将会释放只剩下间隙锁。回忆一下上面讲的数据页的结果中又一个最大记录和最小记录，Infimum 和 Supremum Record，这两个记录在加间隙锁的时候就会用到。

延伸阅读

此文尚未涉及 MySQL 中索引优化的相关内容，可以参考 MySQL 引擎架构与性能优化 https://url.wx-coder.cn/IF5HH 系列中性能优化的相关章节。

作者：王下邀月熊
链接：https://juejin.im/post/5cf3d550f265da1b76388a34
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本文整理自

MySQL 索引的原理与应用：索引类型，存储结构与锁

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。

牛客网OJ：二进制中1的个数

普通法

位运算无外乎 与、或、异或、左移和右移 5 种类型的运算。

使用位运算符进行运算时，整数会自动转为二进制形式，再进行位运算。所有位运算的题型基本都是各种类型位运算的组合。

注意点：整数包含正、负数。

负数右移需要在真空位补上1，如-1，二进制原码为 1000 0001，第一个位为符号位，负数为1，非负数为0开头。在计算机中，负数采用补码来表示，-1的最终二进制表现形式为： 绝对值取反加1，附带上符号位。即 111 1111 加上符号位为 1111 1111。

-1 >> 1 的结果是 1111 1111。

解题思路

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
判断二进制数中1的位数，可以通过和整数 1 进行 与 运算，1&1 = 1，1&0 = 0。

1 的二进制形式为：0000 0001

9 的二进制形式为：0000 1001

9&1 = 0000 0001 != 0，可以确定最后一位是 1。
那么此时要如何继续往前判断另一个1呢？

解决方案：

将 1 左移一位，即 0000 0001 变为 0000 0010，再判断 9（0000 1001）的第 2 位
0000 0010 & 0000 1001 = 0000 0000 == 0，可以确定第 2 位为 0。

这个过程中，使用一个中间计数器变量 count 每次确定与运算结果为非 0， 则加 1 即可统计 1 的个数。

再将 1 左移一位，即 0000 0010 变为 0000 0100，再判断 9（0000 1001）的第 3 位
0000 0100 & 0000 1001 = 0000 0100 != 0，可以确定第 3 位为 1。

后面同上，1 挨个左移，直到移动到最左边，变成 0000 0000，宣告位遍历结束：

0000 0001
0000 0010
0000 0100
0000 1000
0001 0000
0010 0000
0100 0000
1000 0000

0000 0000 结束

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        int flag = 1;
        while(flag != 0){
            if((n&flag) != 0){
                count++;
            }
            flag = flag << 1;
        }
        return count;
    }
}

img

快速法

解题思路

把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于是把整数的二进制表示中的最右边一个1变成0。

1
2
3
4
5
6
7
8
9
10
11
5 - 1 = 0101 - 0001 = 0100

0101 & 0100 = 0100 (最右边的 1 变成0：0101 --> 0100)

4 - 1 = 0100 - 0001 = 0011

0100 & 0011 = 0000 (最右边的 1 变成0：0100 --> 0000)

10 - 1 = 1010 - 0001 = 1001

1010 & 1001 = 1000 (最右边的 1 变成0：1010 --> 1000)

很多二进制的问题都可以用这个思路解决。

代码实现

这种方法速度比较快，其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0，代码如下

1
2
3
4
5
6
7
8
9
int BitCount2(unsigned int n)
{
    unsigned int c =0 ;
    for (c =0; n; ++c)
    {
        n &= (n -1) ; // 清除最低位的1
    }
    return c ;
}

总结

位运算的题首先要想到位移运算和 与或 运算的结合。

扩展

用一条语句判断一个整数是不是2的整数次方。

Basic

一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0。

思路分析

1
2
3
4
5
方案：把这个整数减去1之后再和它自己做与运算，这个整数中唯一的1就会变成0。

比如 8 的二进制位 0000 1000，0000 1000 - 1 = 0000 1000 - 0000 0001 = 0000 0111

然后再将计算结果和 8 自身进行与运算：0000 1000 & 0000 0111 = 0000 0000 结果刚好是 0 。

代码实现

1
2
3
if((n - 1) & n == 0){
    //是2的整数次方
}

输入两个整数 m 和 n，计算需要改变 m 的二进制表示中的多少位才能得到 n。

比如 10 的二进制表示为 1010，13 的二进制表示为 1101，需要改变 1010 中的 3 位才能得到 1101。

思路分析

我们可以分为两步解决这个问题：第一步求这两个数的异或，第二步统计异或结果中1的位数。

1
2
3
1010 ^ 1101 = 0111

再运用移位运算 + 与运算判断 1 的个数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
public int numOfBitToChange(int m, int n) {
    int result = m ^ n;
    int count = 0;
    int flag = 1;
    while(flag != 0) {
        if((result & flag) != 0) {
            count ++;
        }
        flag << 1;
    }
    return count;
}

img

本文整理自

二进制中1的个数

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!