用户态 内核态

用户态 内核态

Linux探秘之用户态与内核态

内核从本质上看是一种软件——控制计算机的硬件资源，并提供上层应用程序运行的环境。用户态即上层应用程序的活动空间，应用程序的执行必须依托于内核提供的资源，包括CPU资源、存储资源、I/O资源等。为了使上层应用能够访问到这些资源，内核必须为上层应用提供访问的接口：即系统调用。

因为操作系统的资源是有限的，如果访问资源的操作过多，必然会消耗过多的资源，而且如果不对这些操作加以区分，很可能造成资源访问的冲突。所以，为了减少有限资源的访问和使用冲突，Unix/Linux的设计哲学之一就是：对不同的操作赋予不同的执行等级，就是所谓特权的概念。简单说就是有多大能力做多大的事，与系统相关的一些特别关键的操作必须由最高特权的程序来完成。Intel的X86架构的CPU提供了0到3四个特权级，数字越小，特权越高，Linux操作系统中主要采用了0和3两个特权级，分别对应的就是内核态和用户态。运行于用户态的进程可以执行的操作和访问的资源都会受到极大的限制，而运行在内核态的进程则可以执行任何操作并且在资源的使用上没有限制。很多程序开始时运行于用户态，但在执行的过程中，一些操作需要在内核权限下才能执行，这就涉及到一个从用户态切换到内核态的过程。比如C函数库中的内存分配函数malloc()，它具体是使用sbrk()系统调用来分配内存，当malloc调用sbrk()的时候就涉及一次从用户态到内核态的切换，类似的函数还有printf()，调用的是wirte()系统调用来输出字符串，等等。

中断 异常 系统调用

中断 异常 系统调用

• 系统调用 (system call)(软中断)
  应用程序 主动 向操作系统发出的服务器请求
• 异常 (exception)
  非法指令或其他原因导致当前 指令执行失败
  如: 内存出错后的处理请求
• 中断(hardware interrupt)
  来自硬件设备的处理请求

从触发方式上看，可以认为存在前述3种不同的类型，但是从最终实际完成由用户态到内核态的切换操作上来说，涉及的关键步骤是完全一致的，没有任何区别，都相当于执行了一个中断响应的过程，因为系统调用实际上最终是中断机制实现的，而异常和中断的处理机制基本上也是一致的。涉及到由用户态切换到内核态的步骤主要包括：

1. 从当前进程的描述符中提取其内核栈的ss0及esp0信息。
2. 使用ss0和esp0指向的内核栈将当前进程的cs,eip,eflags,ss,esp信息保存起来，这个过程也完成了由用户栈到内核栈的切换过程，同时保存了被暂停执行的程序的下一条指令。
3. 将先前由中断向量检索得到的中断处理程序的cs,eip信息装入相应的寄存器，开始执行中断处理程序，这时就转到了内核态的程序执行了。

异步io

异步IO

线程状态流转

文件类型

普通文件

从Linux的角度来说，类似mp4、pdf、html这样应用层面上的文件类型都属于普通文件Linux用户可以根据访问权限对普通文件进行查看、更改和删除

目录文件（d，directory file）

目录文件对于用惯Windows的用户来说不太容易理解，目录也是文件的一种目录文件包含了各自目录下的文件名和指向这些文件的指针，打开目录事实上就是打开目录文件，只要有访问权限，你就可以随意访问这些目录下的文件（普通文件的执行权限就是目录文件的访问权限），但是只有内核的进程能够修改它们虽然不能修改，但是我们能够通过vim去查看目录文件的内容

符号链接（l，symbolic link）

这种类型的文件类似Windows中的快捷方式，是指向另一个文件的间接指针，也就是我们常说的软链接

块设备文件（b，block）和字符设备文件（c，char）

这些文件一般隐藏在/dev目录下，在进行设备读取和外设交互时会被使用到比如磁盘光驱就是块设备文件，串口设备则属于字符设备文件系统中的所有设备要么是块设备文件，要么是字符设备文件，无一例外

FIFO（p，pipe）

管道文件主要用于进程间通讯。比如使用mkfifo命令可以创建一个FIFO文件，启用一个进程A从FIFO文件里读数据，启动进程B往FIFO里写数据，先进先出，随写随读。

套接字（s，socket）

用于进程间的网络通信，也可以用于本机之间的非网络通信这些文件一般隐藏在/var/run目录下，证明着相关进程的存在

Linux 的文件是没有所谓的扩展名的，一个 Linux文件能不能被执行与它是否可执行的属性有关，只要你的权限中有 x ，比如[ -rwx-r-xr-x ] 就代表这个文件可以被执行，与文件名没有关系。跟在 Windows下能被执行的文件扩展名通常是 .com .exe .bat 等不同。不过，可以被执行跟可以执行成功不一样。比如在 root 主目彔下的 install.log 是一个文本文件，修改权限成为 -rwxrwxrwx 后这个文件能够真的执行成功吗？ 当然不行，因为它的内容根本就没有可以执行的数据。所以说，这个 x 代表这个文件具有可执行的能力， 但是能不能执行成功，当然就得要看该文件的内容了。虽然如此，不过我们仍然希望能从扩展名来了解该文件是什么东西，所以一般我们还是会以适当的扩展名来表示该文件是什么种类的。所以Linux 系统上的文件名真的只是让你了解该文件可能的用途而已， 真正的执行与否仍然需要权限的规范才行。比如常见的/bin/ls 这个显示文件属性的指令要是权限被修改为无法执行，那么ls 就变成不能执行了。这种问题最常发生在文件传送的过程中。例如你在网络上下载一个可执行文件，但是偏偏在你的 Linux 系统中就是无法执行，那就可能是档案的属性被改变了。而且从网络上传送到你 的 Linux 系统中，文件的属性权限确实是会被改变的

文件描述符

文件描述符、文件、进程间的关系

• 每个文件描述符会与一个打开的文件相对应
• 不同的文件描述符也可能指向同一个文件
• 相同的文件可以被不同的进程打开，也可以在同一个进程被多次打开

系统为维护文件描述符，建立了三个表

• 进程级的文件描述符表
• 系统级的文件描述符表
• 文件系统的i-node表

示例：

%!(EXTRA markdown.ResourceType=, string=, string=)

• 在进程A中，文件描述符1和30都指向了同一个打开的文件句柄（#23），这可能是该进程多次对执行打开操作
• 进程A中的文件描述符2和进程B的文件描述符2都指向了同一个打开的文件句柄（#73），这种情况有几种可能，
  1. 进程A和进程B可能是父子进程关系;
  2. 进程A和进程B打开了同一个文件，且文件描述符相同（低概率事件）；
  3. A、B中某个进程通过UNIX域套接字将一个打开的文件描述符传递给另一个进程。
• 进程A的描述符0和进程B的描述符3分别指向不同的打开文件句柄，但这些句柄均指向i-node表的相同条目（#1936），换言之，指向同一个文件。发生这种情况是因为每个进程各自对同一个文件发起了打开请求。同一个进程两次打开同一个文件，也会发生类似情况。

文件描述符限制

格式

Linux操作系统支持很多不同的文件系统，比如ext2、ext3、XFS、FAT等等，而Linux把对不同文件系统的访问交给了VFS（虚拟文件系统），VFS能访问和管理各种不同的文件系统。所以有了区之后就需要把它格式化成具体的文件系统以便VFS访问。

标准的Linux文件系统Ext2是使用「基于inode的文件系统」

一般操作系统的文件数据除了文件实际内容外， 还带有很多属性，例如 Linux 操作系统的文件权限(rwx)与文件属性(拥有者、群组、 时间参数等)，文件系统通常会将属性和实际内容这两部分数据分别存放在不同的区块在基于inode的文件系统中，权限与属性放置到 inode 中，实际数据放到 data block 区块中，而且inode和data block都有编号Ext2 文件系统在此基础上

文件系统最前面有一个启动扇区(boot sector)这个启动扇区可以安装开机管理程序， 这个设计让我们能将不同的引导装载程序安装到个别的文件系统前端，而不用覆盖整个硬盘唯一的MBR， 也就是这样才能实现多重引导的功能把每个区进一步分为多个块组 (block group)，每个块组有独立的inode/block体系如果文件系统高达数百 GB 时，把所有的 inode 和block 通通放在一起会因为 inode 和 block的数量太庞大，不容易管理这其实很好理解，因为分区是用户的分区，实际计算机管理时还有个最适合的大小，于是计算机会进一步的在分区中分块（但这样岂不是可能出现大文件放不了的问题？有什么机制善后吗？）每个块组实际还会分为分为6个部分，除了inode table 和 data block外还有4个附属模块，起到优化和完善系统性能的作用所以整个分区大概会这样划分：

1. inode table
   主要记录文件的属性以及该文件实际数据是放置在哪些block中，它记录的信息至少有这些：大小、真正内容的block号码（一个或多个）访问模式(read/write/excute)拥有者与群组(owner/group)各种时间：建立或状态改变的时间、最近一次的读取时间、最近修改的时间没有文件名！文件名在目录的block中！一个文件占用一个 inode，每个inode有编号Linux 系统存在 inode 号被用完但磁盘空间还有剩余的情况注意，这里的文件不单单是普通文件，目录文件也就是文件夹其实也是一个文件，还有其他的也是inode 的数量与大小在格式化时就已经固定了，每个inode 大小均固定为128 bytes (新的ext4 与xfs 可设定到256 bytes)文件系统能够建立的文件数量与inode 的数量有关，存在空间还够但inode不够的情况系统读取文件时需要先找到inode，并分析inode 所记录的权限与使用者是否符合，若符合才能够开始实际读取 block 的内容inode 要记录的资料非常多，但偏偏又只有128bytes ， 而inode 记录一个block 号码要花掉4byte ，假设我一个文件有400MB 且每个block 为4K 时， 那么至少也要十万条block 号码的记录！inode 哪有这么多空间来存储？为此我们的系统很聪明的将inode 记录block 号码的区域定义为12个直接，一个间接, 一个双间接与一个三间接记录区（详细见附录）
2. data block
   放置文件内容数据的地方在格式化时block的大小就固定了，且每个block都有编号，以方便inode的记录原则上，block 的大小与数量在格式化完就不能够再改变了(除非重新格式化)在Ext2文件系统中所支持的block大小有1K, 2K及4K三种，由于block大小的区别，会导致该文件系统能够支持的最大磁盘容量与最大单一文件容量各不相同：Block 大小 1KB 2KB 4KB最大单一档案限制 16GB 256GB 2TB最大档案系统总容量 2TB 8TB 16TB每个block 内最多只能够放置一个文件的资料，但一个文件可以放在多个block中（大的话）若文件小于block ，则该block 的剩余容量就不能够再被使用了(磁盘空间会浪费)所以如果你的档案都非常小，但是你的block 在格式化时却选用最大的4K 时，可能会产生容量的浪费既然大的block 可能会产生较严重的磁碟容量浪费，那么我们是否就将block 大小定为1K ？这也不妥，因为如果block 较小的话，那么大型档案将会占用数量更多的block ，而inode 也要记录更多的block 号码，此时将可能导致档案系统不良的读写效能事实上现在的磁盘容量都太大了，所以一般都会选择4K 的block 大小
3. superblock
   记录整个文件系统相关信息的地方，一般大小为1024bytes，记录的信息主要有：block 与inode 的总量未使用与已使用的inode / block 数量一个valid bit 数值，若此文件系统已被挂载，则valid bit 为0 ，若未被挂载，则valid bit 为1block 与inode 的大小 (block 为1, 2, 4K，inode 为128bytes 或256bytes)；其他各种文件系统相关信息：filesystem 的挂载时间、最近一次写入资料的时间、最近一次检验磁碟(fsck) 的时间Superblock是非常重要的， 没有Superblock ，就没有这个文件系统了，因此如果superblock死掉了，你的文件系统可能就需要花费很多时间去挽救每个块都可能含有superblock，但是我们也说一个文件系统应该仅有一个superblock 而已，那是怎么回事？事实上除了第一个块内会含有superblock 之外，后续的块不一定含有superblock，而若含有superblock则该superblock主要是做为第一个块内superblock的备份，这样可以进行superblock的救援
4. Filesystem Description
   文件系统描述这个区段可以描述每个block group的开始与结束的block号码，以及说明每个区段(superblock, bitmap, inodemap, data block)分别介于哪一个block号码之间
5. block bitmap
   块对照表如果你想要新增文件时要使用哪个block 来记录呢？当然是选择「空的block」来记录。那你怎么知道哪个block 是空的？这就得要通过block bitmap了，它会记录哪些block是空的，因此我们的系统就能够很快速的找到可使用的空间来记录同样在你删除某些文件时，那些文件原本占用的block号码就得要释放出来， 此时在block bitmap 中对应该block号码的标志位就得要修改成为「未使用中」
6. inode bitmap
   与block bitmap 是类似的功能，只是block bitmap 记录的是使用与未使用的block 号码， 至于inode bitmap 则是记录使用与未使用的inode 号码

流程

创建文件过程

当在ext2下建立一个一般文件时， ext2 会分配一个inode 与相对于该文件大小的block 数量给该文件

1. 例如：假设我的一个block 为4 Kbytes ，而我要建立一个100 KBytes 的文件，那么linux 将分配一个inode 与25 个block 来储存该文件
2. 但同时请注意，由于inode 仅有12 个直接指向，因此还要多一个block 来作为区块号码的记录

创建目录过程

当在ext2文件系统建立一个目录时（就是新建了一个目录文件），文件系统会分配一个inode与至少一块block给该目录

1. inode记录该目录的相关权限与属性，并记录分配到的那块block号码
2. 而block则是记录在这个目录下的文件名与该文件对应的inode号
3. block中还会自动生成两条记录，一条是.文件夹记录，inode指向自身，另一条是..文件夹记录，inode指向父文件夹

从目录树中读取某个文件过程

因为文件名是记录在目录的block当中，因此当我们要读取某个文件时，就一定会经过目录的inode与block ，然后才能够找到那个待读取文件的inode号码，最终才会读到正确的文件的block内的资料。

由于目录树是由根目录开始，因此操作系统先通过挂载信息找到挂载点的inode号，由此得到根目录的inode内容，并依据该inode读取根目录的block信息，再一层一层的往下读到正确的文件。举例来说，如果我想要读取/etc/passwd 这个文件时，系统是如何读取的呢？先看一下这个文件以及有关路径文件夹的信息：

1$ ll -di / /etc /etc/passwd2     128 dr-xr-x r-x . 17 root root 4096 May 4 17:56 /333595521 drwxr-x r-x . 131 root root 8192 Jun 17 00:20 /etc436628004 -rw-r– r– . 1 root root 2092 Jun 17 00:20 /etc/passwd复制代码

于是该文件的读取流程为：

1. /的inode：通过挂载点的信息找到inode号码为128的根目录inode，且inode规定的权限让我们可以读取该block的内容(有r与x)
2. /的block：经过上个步骤取得block的号码，并找到该内容有etc/目录的inode号码(33595521)
3. etc/的inode：读取33595521号inode得知具有r与x的权限，因此可以读取etc/的block内容
4. etc/的block：经过上个步骤取得block号码，并找到该内容有passwd文件的inode号码(36628004)
5. passwd的inode：读取36628004号inode得知具有r的权限，因此可以读取passwd的block内容
6. passwd的block：最后将该block内容的资料读出来

进程

进程控制块

进程控制块（Processing Control Block），是操作系统核心中一种数据结构，主要表示进程状态。其作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位或与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。 PCB通常是系统内存占用区中的一个连续存区，它存放着操作系统用于描述进程情况及控制进程运行所需的全部信息，它使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位或一个能与其他进程并发执行的进程。

进程控制块(PCB)是系统为了管理进程设置的一个专门的数据结构。系统用它来记录进程的外部特征，描述进程的运动变化过程。同时，系统可以利用PCB来控制和管理进程，所以说，PCB（进程控制块）是系统感知进程存在的唯一标志。

PCB内容

PCB通常记载进程之相关信息，包括

• 程序计数器：接着要运行的指令地址。
• 进程状态：可以是new、ready、running、waiting或 blocked等。
• CPU暂存器：如累加器、索引暂存器（Index register）、堆栈指针以及一般用途暂存器、状况代码等，主要用途在于中断时暂时存储数据，以便稍后继续利用；其数量及类因电脑架构有所差异。
• CPU排班法：优先级、排班队列等指针以及其他参数。
• 存储器管理：如标签页表等。
• 会计信息：如CPU与实际时间之使用数量、时限、账号、工作或进程号码。
• 输入输出状态：配置进程使用I/O设备，如磁带机。

或按照信息类型划分：

1. 进程标识信息
   进程标识信息用于唯一地标识一个进程，一个进程通常有两种标识符：内部标志符&外部标识符。
   为了描述进程间的家族关系，通常还设有父进程标识和子进程标识，以表示进程间的家族关系。
   此外，还设有用户名或用户标识号表示该进程属于哪个用户。
   • 内部标志符： 由操作系统赋予每个进程的一个唯一的数字标识符，它通常为一个进程的序号，方便了系统使用。
   • 外部标识符： 由创建者产生，是由字母和数字组成的字符串，为用户进程访问该进程提供方便。
2. 处理机状态
   处理机状态信息主要由处理机的各个寄存器内的信息组成。 进程运行时的许多信息均存放在处理机的各种寄存器中。其中程序状态字（PSW）是相当重要的，处理机根据程序状态寄存器中的PSW来控制程序的运行。
3. 进程调度信息
   PCB中还存放着一些与进程调度有关的信息。
   • 进程状态。 标识进程的当前状态（就绪、运行、阻塞），作为进程调度的依据。
   • 进程优先级。 表示进程获得处理机的优先程度。
   • 为进程调度算法提供依据的其他信息。例如，进程等待时间、进程已经获得处理器的总时间和进程占用内存的时间等。
   • 事件。 是指进程由某一状态转变为另一状态所等待发生的事件。（比如等待I/O释放）
4. 进程控制信息
   • 程序和数据地址。 是指组成进程的程序和数据所在内存或外存中的首地址，以便在调度该进程时能从其PCB中找到相应的程序和数据。
   • 进程同步和通信机制。 指实现进程同步和通信时所采取的机制，如消息队列指针和信号量等，他们可以全部或部分存在PCB中。
   • 资源清单。 列出了进程所需的全部资源 及 已经分配给该进程的资源，但不包括CPU.
   • 链接指针。它给出了处于同一队列中的下一个PCB的首地址。

进程控制块PCB的组织方式

1. 线性表方式：不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。
2. 索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。
3. 链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列等。

进程上下文

进程是在操作系统支持下执行的，进程执行时需要操作系统为其设置相应的执行环境，如系统堆栈、地址映像寄存器、程序计数器、程序状态字、打开文件表以及相关通用寄存器等。 所以，把进程的物理实体与支持进程执行的物理环境合称为进程上下文。

• 上文： 把已执行的进程指令和数据在相关寄存器与堆栈中的内容称为上文。
• 正文： 把正在执行的进程指令和数据在相关寄存器与堆栈中的内容称为正文。
• 下文： 把待执行的进程指令和数据在相关寄存器与堆栈中的内容称为下文。

Unix System Ⅴ 的进程上下文组成：由用户级上下文、寄存器上下文、系统级上下文组成。 

• 用户级上下文：由进程的用户程序段部分编译而成的用户正文段、用户数据和用户栈等组成。
• 寄存器上下文：由程序计数器（PC）、处理机状态字（PS）、栈指针和通用寄存器组成。 PC给出CPU将要执行的下一条指令的虚地址；PS给出机器与该进程相关联时的硬件状态；栈指针指向下一项的当前地址；通用寄存器则用于不同执行模式之间的参数传递。
• 系统级上下文又分为静态部分和动态部分。 这里的动态部分是指进入和退出不同的上下文层次时，系统为各层上下文中相关联的寄存器值所保存和恢复的记录。 系统级上下文静态部分包括PCB结构、将进程虚地址空间映射到物理空间的有关表格、核心栈等。 这里，核心栈主要用来装载进程中所使用的系统调用的调用序列。

系统级上下文的动态部分是与寄存器上下文相关联的。

进程上下文的层次概念主要体现在动态部分中，即系统级上下文的动态部分可看成是由一些数量变化的层次组成，其变化规则符合许先进后出的堆栈方式。

进程状态

三状态进程模型：

挂起：处在挂起状态的进程映像在磁盘上，目的是减少内存占用

具有挂起状态的进程模型：

进程切换

进程上下文切换发生在不同的进程之间而不是同一个进程内。

进城上下文切换分成三个步骤：

1. 把被切换进程的相关信息保存到有关存储区，例如该进程的PCB中。
2. 操作系统中的调度和资源分配程序执行，选取新的进程。
3. 将被选中进程的原来保存的正文部分从有关存储区中取出，并送至寄存器与堆栈中,激活被选中进程执行。

总结： 进程上下文切换的切换过程涉及由谁来保护和获取进程的正文的问题，也就是如何使寄存器和堆栈等中的数据流入流出 PCB 的存储区。 另外，进程上下文切换还涉及系统调度和分配程序，这些都比较耗费CPU时间。

fork

由fork创建的新进程被称为子进程（child process）。该函数被调用一次，但返回两次。两次返回的区别是子进程的返回值是0，而父进程的返回值则是新进程（子进程）的进程 id。将子进程id返回给父进程的理由是：因为一个进程的子进程可以多于一个，没有一个函数使一个进程可以获得其所有子进程的进程id。对子进程来说，之所以fork返回0给它，是因为它随时可以调用getpid()来获取自己的pid；也可以调用getppid()来获取父进程的id。(进程id 0总是由交换进程使用，所以一个子进程的进程id不可能为0 )。

fork之后，操作系统会复制一个与父进程完全相同的子进程，虽说是父子关系，但是在操作系统看来，他们更像兄弟关系，这2个进程共享代码空间，但是数据空间是互相独立的，子进程数据空间中的内容是父进程的完整拷贝，指令指针也完全相同，子进程拥有父进程当前运行到的位置（两进程的程序计数器pc值相同，也就是说，子进程是从fork返回处开始执行的），但有一点不同，如果fork成功，子进程中fork的返回值是0，父进程中fork的返回值是子进程的进程号，如果fork不成功，父进程会返回错误。

可以这样想象，2个进程一直同时运行，而且步调一致，在fork之后，他们分别作不同的工作，也就是分岔了。这也是fork为什么叫fork的原因

至于那一个最先运行，可能与操作系统（调度算法）有关，而且这个问题在实际应用中并不重要，如果需要父子进程协同，可以通过原语的办法解决。

进程通讯方式

管道/匿名管道(pipe)

• 管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道。
• 只能用于父子进程或者兄弟进程之间(具有亲缘关系的进程);
• 单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在与内存中。
• 数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。

管道的实质：

管道的实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据，管道一端的进程顺序的将数据写入缓冲区，另一端的进程则顺序的读出数据。

该缓冲区可以看做是一个循环队列，读和写的位置都是自动增长的，不能随意改变，一个数据只能被读一次，读出来以后在缓冲区就不复存在了。

当缓冲区读空或者写满时，有一定的规则控制相应的读进程或者写进程进入等待队列，当空的缓冲区有新数据写入或者满的缓冲区有数据读出来时，就唤醒等待队列中的进程继续读写。

管道的局限：

管道的主要局限性正体现在它的特点上：

• 只支持单向数据流；
• 只能用于具有亲缘关系的进程之间；
• 没有名字；
• 管道的缓冲区是有限的（管道制存在于内存中，在管道创建时，为缓冲区分配一个页面大小）；
• 管道所传送的是无格式字节流，这就要求管道的读出方和写入方必须事先约定好数据的格式，比如多少字节算作一个消息（或命令、或记录）等等；

有名管道(FIFO)

匿名管道，由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道(FIFO)。

有名管道不同于匿名管道之处在于它提供了一个路径名与之关联，以有名管道的文件形式存在于文件系统中，这样，即使与有名管道的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过有名管道相互通信，因此，通过有名管道不相关的进程也能交换数据。值的注意的是，有名管道严格遵循先进先出(first in first out),对匿名管道及有名管道的读总是从开始处返回数据，对它们的写则把数据添加到末尾。它们不支持诸如lseek()等文件定位操作。有名管道的名字存在于文件系统中，内容存放在内存中。

匿名管道和有名管道总结：

1. 管道是特殊类型的文件，在满足先入先出的原则条件下可以进行读写，但不能进行定位读写。
2. 匿名管道是单向的，只能在有亲缘关系的进程间通信；有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。
3. 无名管道阻塞问题：无名管道无需显示打开，创建时直接返回文件描述符，在读写时需要确定对方的存在，否则将退出。如果当前进程向无名管道的一端写数据，必须确定另一端有某一进程。如果写入无名管道的数据超过其最大值，写操作将阻塞，如果管道中没有数据，读操作将阻塞，如果管道发现另一端断开，将自动退出。
4. 有名管道阻塞问题：有名管道在打开时需要确实对方的存在，否则将阻塞。即以读方式打开某管道，在此之前必须一个进程以写方式打开管道，否则阻塞。此外，可以以读写（O_RDWR）模式打开有名管道，即当前进程读，当前进程写，不会阻塞。

信号(Signal)

• 信号是Linux系统中用于进程间互相通信或者操作的一种机制，信号可以在任何时候发给某一进程，而无需知道该进程的状态。
• 如果该进程当前并未处于执行状态，则该信号就有内核保存起来，知道该进程回复执行并传递给它为止。
• 如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消是才被传递给进程。

Linux系统中常用信号：

• SIGHUP：用户从终端注销，所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。
• SIGINT：程序终止信号。程序运行过程中，按Ctrl+C键将产生该信号。
• SIGQUIT：程序退出信号。程序运行过程中，按Ctrl+\键将产生该信号。
• SIGBUS和SIGSEGV：进程访问非法地址。
• SIGFPE：运算中出现致命错误，如除零操作、数据溢出等。
• SIGKILL：用户终止进程执行信号。shell下执行kill -9发送该信号。
• SIGTERM：结束进程信号。shell下执行kill 进程pid发送该信号。
• SIGALRM：定时器信号。
• SIGCLD：子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号，则子进程退出后将形成僵尸进程。

信号来源

信号是软件层次上对中断机制的一种模拟，是一种异步通信方式，，信号可以在用户空间进程和内核之间直接交互，内核可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件主要有两个来源：

• 硬件来源：用户按键输入Ctrl+C退出、硬件异常如无效的存储访问等。
• 软件终止：终止进程信号、其他进程调用kill函数、软件异常产生信号。

信号生命周期和处理流程

1. 信号被某个进程产生，并设置此信号传递的对象（一般为对应进程的pid），然后传递给操作系统；
2. 操作系统根据接收进程的设置（是否阻塞）而选择性的发送给接收者，如果接收者阻塞该信号（且该信号是可以阻塞的），操作系统将暂时保留该信号，而不传递，直到该进程解除了对此信号的阻塞（如果对应进程已经退出，则丢弃此信号），如果对应进程没有阻塞，操作系统将传递此信号。
3. 目的进程接收到此信号后，将根据当前进程对此信号设置的预处理方式，暂时终止当前代码的执行，保护上下文（主要包括临时寄存器数据，当前程序位置以及当前CPU的状态）、转而执行中断服务程序，执行完成后在回复到中断的位置。当然，对于抢占式内核，在中断返回时还将引发新的调度。
   

消息(Message)队列

• 消息队列是存放在内核中的消息链表，每个消息队列由消息队列标识符表示。
• 与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。
• 另外与管道不同的是，消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达。

消息队列特点总结：

1. 消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识.
2. 消息队列允许一个或多个进程向它写入与读取消息.
3. 管道和消息队列的通信数据都是先进先出的原则。
4. 消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比FIFO更有优势。
5. 消息队列克服了信号承载信息量少，管道只能承载无格式字 节流以及缓冲区大小受限等缺。
6. 目前主要有两种类型的消息队列：POSIX消息队列以及System V消息队列，系统V消息队列目前被大量使用。系统V消息队列是随内核持续的，只有在内核重起或者人工删除时，该消息队列才会被删除。

共享内存(share memory)

• 使得多个进程可以可以直接读写同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。
• 为了在多个进程间交换信息，内核专门留出了一块内存区，可以由需要访问的进程将其映射到自己的私有地址空间。进程就可以直接读写这一块内存而不需要进行数据的拷贝，从而大大提高效率。
• 由于多个进程共享一段内存，因此需要依靠某种同步机制（如信号量）来达到进程间的同步及互斥。
  %!(EXTRA markdown.ResourceType=, string=, string=)

信号量(semaphore)

信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。

为了获得共享资源，进程需要执行下列操作：

1. 创建一个信号量：这要求调用者指定初始值，对于二值信号量来说，它通常是1，也可是0。
2. 等待一个信号量：该操作会测试这个信号量的值，如果小于0，就阻塞。也称为P操作。
3. 挂出一个信号量：该操作将信号量的值加1，也称为V操作。

为了正确地实现信号量，信号量值的测试及减1操作应当是原子操作。为此，信号量通常是在内核中实现的。Linux环境中，有三种类型：Posix（可移植性操作系统接口）有名信号量（使用Posix IPC名字标识）、Posix基于内存的信号量（存放在共享内存区中）、System V信号量（在内核中维护）。这三种信号量都可用于进程间或线程间的同步。

信号量与普通整型变量的区别：

1. 信号量是非负整型变量，除了初始化之外，它只能通过两个标准原子操作：wait(semap) , signal(semap) ; 来进行访问；
2. 操作也被成为PV原语（P来源于荷兰语proberen”测试”，V来源于荷兰语verhogen”增加”，P表示通过的意思，V表示释放的意思），而普通整型变量则可以在任何语句块中被访问；

信号量与互斥量之间的区别：

1. 互斥量用于线程的互斥，信号量用于线程的同步。这是互斥量和信号量的根本区别，也就是互斥和同步之间的区别。
   互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。
   同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。
   在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源
2. 互斥量值只能为0/1，信号量值可以为非负整数。
   也就是说，一个互斥量只能用于一个资源的互斥访问，它不能实现多个资源的多线程互斥问题。信号量可以实现多个同类资源的多线程互斥和同步。当信号量为单值信号量是，也可以完成一个资源的互斥访问。
3. 互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程释放，另一个线程得到。

套接字(socket)

套接字是一种通信机制，凭借这种机制，客户/服务器（即要进行通信的进程）系统的开发工作既可以在本地单机上进行，也可以跨网络进行。也就是说它可以让不在同一台计算机但通过网络连接计算机上的进程进行通信。

%!(EXTRA markdown.ResourceType=, string=, string=)

线程

用户线程

用户线程是完全建立在用户空间的线程库，用户线程的创建、调度、同步和销毁全又库函数在用户空间完成，不需要内核的帮助。因此这种线程是极其低消耗和高效的。

• 处理器竞争：单纯的用户线程是建立在用户空间，其对内核是透明的，因此其所属进程单独参与处理器的竞争，而进程的所有线程参与竞争该进程的资源。
• 使用资源：与所属进程共享进程地址空间和系统资源。
• 调度：由在用户空间实现的线程库，在所属进程内进行调度

LWP虽然本质上属于用户线程，但LWP线程库是建立在内核之上的，LWP的许多操作都要进行系统调用，因此效率不高。而这里的用户线程指的是完全建立在用户空间的线程库，用户线程的建立，同步，销毁，调度完全在用户空间完成，不需要内核的帮助。因此这种线程的操作是极其快速的且低消耗的。

上图是最初的一个用户线程模型，从中可以看出，进程中包含线程，用户线程在用户空间中实现，内核并没有直接对用户线程进程调度，内核的调度对象和传统进程一样，还是进程本身，内核并不知道用户线程的存在。

用户线程之间的调度由在用户空间实现的线程库实现。

这种模型对应着多对一线程模型，其缺点是一个用户线程如果阻塞在系统调用中，则整个进程都将会阻塞。

内核线程

内核线程就是内核的分身，一个分身可以处理一件特定事情。这在处理异步事件如异步IO时特别有用。内核线程的使用是廉价的，唯一使用的资源就是内核栈和上下文切换时保存寄存器的空间。支持多线程的内核叫做多线程内核(Multi-Threads kernel )。

内核线程只运行在内核态，不受用户态上下文的拖累。

• 处理器竞争：可以在全系统范围内竞争处理器资源；
• 使用资源：唯一使用的资源是内核栈和上下文切换时保持寄存器的空间
• 调度：调度的开销可能和进程自身差不多昂贵
• 同步效率：资源的同步和数据共享比整个进程的数据同步和共享要低一些。

轻量级进程LWP

轻量级进程(LWP)是建立在内核之上并由内核支持的用户线程，它是内核线程的高度抽象，每一个轻量级进程都与一个特定的内核线程关联。内核线程只能由内核管理并像普通进程一样被调度。

轻量级进程由clone()系统调用创建，参数是CLONE_VM，即与父进程是共享进程地址空间和系统资源。

与普通进程区别：LWP只有一个最小的执行上下文和调度程序所需的统计信息。

• 处理器竞争：因与特定内核线程关联，因此可以在全系统范围内竞争处理器资源
• 使用资源：与父进程共享进程地址空间
• 调度：像普通进程一样调度

轻量级线程(LWP)是一种由内核支持的用户线程。它是基于内核线程的高级抽象，因此只有先支持内核线程，才能有LWP。每一个进程有一个或多个LWPs，每个LWP由一个内核线程支持。这种模型实际上就是一对一线程模型。在这种实现的操作系统中，LWP就是用户线程。

由于每个LWP都与一个特定的内核线程关联，因此每个LWP都是一个独立的线程调度单元。即使有一个LWP在系统调用中阻塞，也不会影响整个进程的执行。

轻量级进程具有局限性。

• 首先，大多数LWP的操作，如建立、析构以及同步，都需要进行系统调用。系统调用的代价相对较高：需要在user mode和kernel mode中切换。
• 其次，每个LWP都需要有一个内核线程支持，因此LWP要消耗内核资源（内核线程的栈空间）。因此一个系统不能支持大量的LWP。

线程和进程区别

我的理解是进程是指在系统中正在运行的一个应用程序；程序一旦运行就是进程，或者更专业化来说：进程是指程序执行时的一个实例。

线程是进程的一个实体。

进程——资源分配的最小单位，线程——程序执行的最小单位。

1. 因为进程拥有独立的堆栈空间和数据段，所以每当启动一个新的进程必须分配给它独立的地址空间，建立众多的数据表来维护它的代码段、堆栈段和数据段，这对于多进程来说十分“奢侈”，系统开销比较大，而线程不一样，线程拥有独立的堆栈空间，但是共享数据段，它们彼此之间使用相同的地址空间，共享大部分数据，比进程更节俭，开销比较小，切换速度也比进程快，效率高，但是正由于进程之间独立的特点，使得进程安全性比较高，也因为进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。一个线程死掉就等于整个进程死掉。
2. 体现在通信机制上面，正因为进程之间互不干扰，相互独立，进程的通信机制相对很复杂，譬如管道，信号，消息队列，共享内存，套接字等通信机制，而线程由于共享数据段所以通信机制很方便。
3. 属于同一个进程的所有线程共享该进程的所有资源，包括文件描述符。而不同过的进程相互独立。
4. 线程又称为轻量级进程，进程有进程控制块，线程有线程控制块；
5. 线程必定也只能属于一个进程，而进程可以拥有多个线程而且至少拥有一个线程；
6. 体现在程序结构上，举一个简明易懂的列子：当我们使用进程的时候，我们不自主的使用if else嵌套来判断pid，使得程序结构繁琐，但是当我们使用线程的时候，基本上可以甩掉它，当然程序内部执行功能单元需要使用的时候还是要使用，所以线程对程序结构的改善有很大帮助。

Hadoop

架构

HDFS

Blocks

物理磁盘中有块的概念，磁盘的物理Block是磁盘操作最小的单元，读写操作均以Block为最小单元，一般为512 Byte。文件系统在物理Block之上抽象了另一层概念，文件系统Block物理磁盘Block的整数倍。通常为几KB。Hadoop提供的df、fsck这类运维工具都是在文件系统的Block级别上进行操作。

HDFS的Block块比一般单机文件系统大得多，默认为128M。HDFS的文件被拆分成block-sized的chunk，chunk作为独立单元存储。比Block小的文件不会占用整个Block，只会占据实际大小。例如， 如果一个文件大小为1M，则在HDFS中只会占用1M的空间，而不是128M。

HDFS的Block为什么这么大？

是为了最小化查找（seek）时间，控制定位文件与传输文件所用的时间比例。假设定位到Block所需的时间为10ms，磁盘传输速度为100M/s。如果要将定位到Block所用时间占传输时间的比例控制1%，则Block大小需要约100M。

但是如果Block设置过大，在MapReduce任务中，Map或者Reduce任务的个数 如果小于集群机器数量，会使得作业运行效率很低。

Block抽象的好处

block的拆分使得单个文件大小可以大于整个磁盘的容量，构成文件的Block可以分布在整个集群， 理论上，单个文件可以占据集群中所有机器的磁盘。

Block的抽象也简化了存储系统，对于Block，无需关注其权限，所有者等内容（这些内容都在文件级别上进行控制）。

Block作为容错和高可用机制中的副本单元，即以Block为单位进行复制。

NameNode

NameNode也叫名称节点，它管理文件系统的命名空间，维护着文件系统树及整棵树内所有的文件和目录。这些信息以两个文件形式永久保存在本地磁盘上：

• 命名空间镜像文件(namespcae image)
• 编辑日志文件(edit log)

对整个分布式文件系统进行总控制，会纪录所有的元数据分布存储的状态信息。比如文件是如何分割成数据块的，以及这些数据块被存储到哪些节点上，还有对内存和I/O进行集中管理。但是持久化数据中不包括Block所在的节点列表，及文件的Block分布在集群中的哪些节点上，这些信息是在系统重启的时候重新构建（通过Datanode汇报的Block信息）。用户首先会访问Namenode，获取文件分布的状态信息，然后访问相应的节点，把文件拿到。

整个HDFS可存储的文件数受限于NameNode的内存大小。

不过这是个单点，如果NameNode宕机，那么整个集群就瘫痪了。

Secondary Namenode

Secondary NameNode，该部分主要是定时对NameNode数据进行备份，这样尽量降低NameNode崩溃之后，导致数据的丢失，其实所作的工作就是从NameNode获得fsimage（命名空间镜像文件）和edits（编辑日志文件）把二者重新合并然后发给NameNode，这样，既能减轻NameNode的负担又能保险地备份。

DataNode

数据节点，提供真实文件数据的存储服务。每台从服务器节点都运行一个，负责把HDFS数据块读、写到本地文件系统。

文件写入

1. Client向NameNode发起文件写入的请求
2. NameNode根据文件大小和文件块配置情况，返回给Client它所管理部分DataNode的信息。
3. Client将文件划分为多个文件块，根据DataNode的地址信息，按顺序写入到每一个DataNode块中。

文件读取

1. Client向NameNode发起文件读取的请求
2. NameNode返回文件存储的DataNode的信息。
3. Client读取文件信息。

MapReduce

MapReduce是一种编程模型，用于大规模数据集的并行运算。Map（映射）和Reduce（化简），采用分而治之思想，先把任务分发到集群多个节点上，并行计算，然后再把计算结果合并，从而得到最终计算结果。多节点计算，所涉及的任务调度、负载均衡、容错处理等，都由MapReduce框架完成，不需要编程人员关心这些内容。

1.0

MapReduce采用Master/Slave结构。

• Master：是整个集群的唯一的全局管理者，功能包括：作业管理、状态监控和任务调度等，即MapReduce中的JobTracker。
• Slave：负责任务的执行和任务状态的回报，即MapReduce中的TaskTracker。

JobTracker

作业跟踪器，运行在主节点（Namenode）上的一个很重要的进程，是MapReduce体系的调度器。用于处理作业（用户提交的代码）的后台程序，决定有哪些文件参与作业的处理，然后把作业切割成为一个个的小task，并把它们分配到所需要的数据所在的子节点。（程序跟着数据跑，这样子就可以避免对数据进行重新分配）

TaskTracker

任务跟踪器，运行在每个slave节点上，与datanode结合（代码与数据一起的原则），管理各自节点上的task（由jobtracker分配），每个节点只有一个tasktracker，但一个tasktracker可以启动多个JVM，用于并行执行map或reduce任务，它与jobtracker交互通信，可以告知jobtracker子任务完成情况。

两者联系：JobTracker会给TaskTracker下达各种命令，主要包括：启动任务(LaunchTaskAction)、提交任务(CommitTaskAction)、杀死任务(KillTaskAction)、杀死作业(KillJobAction)和重新初始化(TaskTrackerReinitAction)。

2.0

Yarn

HA

MapReduce流程

Map阶段

1. 读取输入文件的内容，并解析成键值对（<key, value>）的形式，输入文件中的每一行被解析成一个<key, value>对，每个<key, value>对调用一次map()函数。
2. 用户写map()函数，对输入的<key,value>对进行处理，并输出新的<key,value>对。
   3。 对Step 2中得到的<key,value>进行分区操作。
3. 不同分区的数据，按照key值进行排序和分组，具有相同key值的value则放到同一个集合中。
4. 分组后的数据进行规约。

Shuffle

Map Shuffle

1. 环形内存缓存区：每个split数据交由一个map任务处理，map的处理结果不会直接写到硬盘上，会先输送到环形内存缓存区中，默认的大小是100M（可通过配置修改），当缓冲区的内容达到80%后会开始溢出，此时缓存区的溢出内容会被写到磁盘上，形成一个个spill file，注意这个文件没有固定大小。
2. 在内存中经过分区、排序后溢出到磁盘：分区主要功能是用来指定 map 的输出结果交给哪个 reduce 任务处理，默认是通过 map 输出结果的 key 值取hashcode 对代码中配置的 redue task数量取模运算，值一样的分到一个区，也就是一个 reduce 任务对应一个分区的数据。这样做的好处就是可以避免有的 reduce 任务分配到大量的数据，而有的 reduce 任务只分配到少量甚至没有数据，平均 reduce 的处理能力。并且在每一个分区（partition）中，都会有一个 sort by key 排序，如果此时设置了 Combiner，将排序后的结果进行 Combine 操作，相当于 map 阶段的本地 reduce，这样做的目的是让尽可能少的数据写入到磁盘。
3. 合并溢出文件：随着 map 任务的执行，不断溢出文件，直到输出最后一个记录，可能会产生大量的溢出文件，这时需要对这些大量的溢出文件进行合并，在合并文件的过程中会不断的进行排序跟 Combine 操作，这样做有两个好处：减少每次写入磁盘的数据量&减少下一步 reduce 阶段网络传输的数据量。最后合并成了一个分区且排序的大文件，此时可以再进行配置压缩处理，可以减少不同节点间的网络传输量。合并完成后着手将数据拷贝给相对应的reduce 处理，那么要怎么找到分区数据对应的那个 reduce 任务呢？简单来说就是 JobTracker 中保存了整个集群中的宏观信息，只要 reduce 任务向 JobTracker 获取对应的 map 输出位置就可以了。具体请参考上方的MapReduce工作原理。

Reduce Shuffle

reduce 会接收到不同 map 任务传来的有序数据，如果 reduce 接收到的数据较小，则会存在内存缓冲区中，直到数据量达到该缓存区的一定比例时对数据进行合并后溢写到磁盘上。随着溢写的文件越来越多，后台的线程会将他们合并成一个更大的有序的文件，可以为后面合并节省时间。这其实跟 map端的操作一样，都是反复的进行排序、合并，这也是 Hadoop 的灵魂所在，但是如果在 map 已经压缩过，在合并排序之前要先进行解压缩。合并的过程会产生很多中间文件，但是最后一个合并的结果是不需要写到磁盘上，而是可以直接输入到 reduce 函数中计算，每个 reduce 对应一个输出结果文件。

Reduce阶段

1. 对于多个map任务的输出，按照不同的分区，通过网络传输到不同的Reduce节点。
2. 对多个map任务的输出结果进行合并、排序，用户书写reduce函数，对输入的key、value进行处理，得到新的key、value输出结果。
3. 将reduce的输出结果保存在文件中。

例子

MySQL

参考资料：

万字总结：学习MySQL优化原理，这一篇就够了！

架构

逻辑架构

MySQL逻辑架构整体分为三层，最上层为客户端层，并非MySQL所独有，诸如：连接处理、授权认证、安全等功能均在这一层处理。

MySQL大多数核心服务均在中间这一层，包括查询解析、分析、优化、缓存、内置函数(比如：时间、数学、加密等函数)。所有的跨存储引擎的功能也在这一层实现：存储过程、触发器、视图等。

最下层为存储引擎，其负责MySQL中的数据存储和提取。和Linux下的文件系统类似，每种存储引擎都有其优势和劣势。中间的服务层通过API与存储引擎通信，这些API接口屏蔽了不同存储引擎间的差异。

查询过程：

客户端/服务端通信协议

MySQL客户端/服务端通信协议是“半双工”的：在任一时刻，要么是服务器向客户端发送数据，要么是客户端向服务器发送数据，这两个动作不能同时发生。一旦一端开始发送消息，另一端要接收完整个消息才能响应它，所以我们无法也无须将一个消息切成小块独立发送，也没有办法进行流量控制。

客户端用一个单独的数据包将查询请求发送给服务器，所以当查询语句很长的时候，需要设置max_allowed_packet参数。但是需要注意的是，如果查询实在是太大，服务端会拒绝接收更多数据并抛出异常。

与之相反的是，服务器响应给用户的数据通常会很多，由多个数据包组成。但是当服务器响应客户端请求时，客户端必须完整的接收整个返回结果，而不能简单的只取前面几条结果，然后让服务器停止发送。因而在实际开发中，尽量保持查询简单且只返回必需的数据，减小通信间数据包的大小和数量是一个非常好的习惯，这也是查询中尽量避免使用SELECT *以及加上LIMIT限制的原因之一。

查询优化器

MySQL的查询优化器是一个非常复杂的部件，它使用了非常多的优化策略来生成一个最优的执行计划：

• 重新定义表的关联顺序（多张表关联查询时，并不一定按照SQL中指定的顺序进行，但有一些技巧可以指定关联顺序）
• 优化MIN()和MAX()函数（找某列的最小值，如果该列有索引，只需要查找B+Tree索引最左端，反之则可以找到最大值）
• 提前终止查询（比如：使用Limit时，查找到满足数量的结果集后会立即终止查询）
• 优化排序（在老版本MySQL会使用两次传输排序，即先读取行指针和需要排序的字段在内存中对其排序，然后再根据排序结果去读取数据行，而新版本采用的是单次传输排序，也就是一次读取所有的数据行，然后根据给定的列排序。对于I/O密集型应用，效率会高很多）

索引

b+ tree

介绍

浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。

如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

性质

间距越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。

当b+树的数据项是复合的数据结构，比如(name,age,sex)的时候，b+数是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据；但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了， 这个是非常重要的性质，即索引的最左匹配特性。

意义

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

简单点说说内存读取，内存是由一系列的存储单元组成的，每个存储单元存储固定大小的数据，且有一个唯一地址。当需要读内存时，将地址信号放到地址总线上传给内存，内存解析信号并定位到存储单元，然后把该存储单元上的数据放到数据总线上，回传。

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

内存存取效率，跟次数有关，先读取A数据还是后读取A数据不会影响存取效率。而磁盘存取就不一样了，磁盘I/O涉及机械操作。磁盘是由大小相同且同轴的圆形盘片组成，磁盘可以转动(各个磁盘须同时转动)。磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不动，磁盘转动，但磁臂可以前后动，用于读取不同磁道上的数据。磁道就是以盘片为中心划分出来的一系列同心环(如图标红那圈)。磁道又划分为一个个小段，叫扇区，是磁盘的最小存储单元。

磁盘读取时，系统将数据逻辑地址传给磁盘，磁盘的控制电路会解析出物理地址，即哪个磁道哪个扇区。于是磁头需要前后移动到对应的磁道，消耗的时间叫寻道时间，然后磁盘旋转将对应的扇区转到磁头下，消耗的时间叫旋转时间。所以，适当的操作顺序和数据存放可以减少寻道时间和旋转时间。为了尽量减少I/O操作，磁盘读取每次都会预读，大小通常为页的整数倍。即使只需要读取一个字节，磁盘也会读取一页的数据(通常为4K)放入内存，内存与磁盘以页为单位交换数据。因为局部性原理认为，通常一个数据被用到，其附近的数据也会立马被用到。

B-Tree：如果一次检索需要访问4个节点，数据库系统设计者利用磁盘预读原理，把节点的大小设计为一个页，那读取一个节点只需要一次I/O操作，完成这次检索操作，最多需要3次I/O(根节点常驻内存)。数据记录越小，每个节点存放的数据就越多，树的高度也就越小，I/O操作就少了，检索效率也就上去了。

B+Tree：非叶子节点只存key，大大滴减少了非叶子节点的大小，那么每个节点就可以存放更多的记录，树更矮了，I/O操作更少了。所以B+Tree拥有更好的性能。

索引实现

MyISAM：MyISAM引擎使用B+Tree作为索引结构。MyISAM索引文件和数据文件是分离的，叶节点的data域存放的是数据记录的地址。MyISAM主键索引和辅助索引结构是一样的。

InnoDB：InnoDB的数据文件本身就是索引文件。在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

• 为什么不建议使用过长的字段作为主键：
  因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
• 用非单调的字段作为主键在InnoDB中不是个好主意：
  因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
• 为何自增主键好：
  InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。
  
  这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。
  如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，如下：
  
  此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

最左前缀原则

https://www.jianshu.com/p/b7911e0394b0

https://www.cnblogs.com/wmbg/p/6800354.html

联合索引会按照b+tree排序，例如(a,b,c)，索引的结果是order by a,b,c ,所以当查询(a),(a,b),(a,b,c)时都可以使用索引。而查询(b,c),(c)

1. 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。

2. =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式

索引规则

• 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。
• =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式
• 尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录
• 索引列不能参与计算，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);
• 尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可，当然要考虑原有数据和线上使用情况

隔离级别

1. 原子性
   事务必须是原子工作单元；对于其数据修改，要么全都执行，要么全都不执行。
2. 一致性
   事务的一致性指的是在一个事务执行之前和执行之后数据库都必须处于一致性状态。事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。
3. 隔离性（关于事务的隔离性数据库提供了多种隔离级别）
   一个事务的执行不能干扰其它事务。即一个事务内部的操作及使用的数据对其它并发事务是隔离的，并发执行的各个事务之间不能互相干扰。
4. 持久性
   事务完成之后，它对于数据库中的数据改变是永久性的。该修改即使出现系统故障也将一
   直保持。
   在介绍数据库提供的各种隔离级别之前，我们先看看如果不考虑事务的隔离性，会发生的几种问题：

• 脏读
  脏读是指在一个事务处理过程里读取了另一个未提交的事务中的数据。
• 不可重复读
• 幻读
  幻读和不可重复读都是读取了另一条已经提交的事务,不可重复读重点在于update和delete，而幻读的重点在于insert。

在可重复读中，该sql第一次读取到数据后，就将这些数据加锁，其它事务无法修改这些数据，就可以实现可重复 读了。但这种方法却无法锁住insert的数据，所以当事务A先前读取了数据，或者修改了全部数据，事务B还是可以insert数据提交，这时事务A就会 发现莫名其妙多了一条之前没有的数据，这就是幻读，不能通过行锁来避免。需要Serializable隔离级别 ，读用读锁，写用写锁，读锁和写锁互斥，这么做可以有效的避免幻读、不可重复读、脏读等问题，但会极大的降低数据库的并发能力。

现在来看看MySQL数据库为我们提供的四种隔离级别：

1. Serializable (串行化)：可避免脏读、不可重复读、幻读的发生。在可串行化级别上，MySQL执行S2PL并发控制协议, 一阶段申请，一阶段释放。读写都要加锁。
2. Repeatable read (可重复读)：可避免脏读、不可重复读的发生。读不加锁，只有写才加锁，读写互不阻塞，并发度相对于可串行化级别要高，但会有Write Skew异常。事务在开始时创建一个ReadView，当读一条记录时，会遍历版本链表，通过当前事务的ReadView判断可见性，找到第一个对当前事务可见的版本，读这个版本。对于写操作，包括Locking Read(SELECT … FOR UPDATE), UPDATE, DELETE，需要加写锁。根据谓词条件上索引使用情形，锁定有不同的方式：
   1. 有索引：对于索引上有唯一约束且为等值条件的情形，不用GAP LOCK，只锁定索引记录。对于其它情形，使用GAP LOCK，相当于谓词锁。
   2. 没有索引：由于MySQL没有实现通用的谓词锁，这时就相当于锁全表。
3. Read committed (读已提交)：可避免脏读的发生。MySQL的读已提交实际是语句级别快照。与可重复读级别主要有两点不同：
   1. 获得ReadView的时机。每个语句开始执行时，获得ReadView，可见性判断是基于语句级别的ReadView。读的策略与可重复读类似。
   2. 写锁的使用方式。这里不需要GAP LOCK，只使用记录锁。并且事务只持有被UPDATE/DELETE记录的写锁（可重复读需要保留全部写锁直到事务结束，而读已提交只保留真正更改的）。
4. Read uncommitted (读未提交)：最低级别，任何情况都无法保证。读最新的数据，不管这条记录是不是已提交。不会遍历版本链，少了查找可见的版本的步骤。这样可能会导致脏读。

在MySQL数据库中默认的隔离级别为Repeatable read (可重复读)。

innodb可重复读级别可以避免读数据时产生的幻读问题（mvcc缘故，读不到版本号大于当前版本号的行），但不能避免写数据时产生的幻读问题。

因为读是快照度，写是当前读。要解决幻读需要用间隙锁或者串行化。

锁

共享锁，排它锁

间隙锁

调优

explain

返回结果

• id : 表示SQL执行的顺序的标识,SQL从大到小的执行
• select_type：表示查询中每个select子句的类型
• table：显示这一行的数据是关于哪张表的，有时不是真实的表名字
• type：表示MySQL在表中找到所需行的方式，又称“访问类型”。常用的类型有： ALL, index, range, ref, eq_ref, const, system, NULL（从左到右，性能从差到好）
• possible_keys：指出MySQL能使用哪个索引在表中找到记录，查询涉及到的字段上若存在索引，则该索引将被列出，但不一定被查询使用
• Key：key列显示MySQL实际决定使用的键（索引），如果没有选择索引，键是NULL。
• key_len：表示索引中使用的字节数，可通过该列计算查询中使用的索引的长度（key_len显示的值为索引字段的最大可能长度，并非实际使用长度，即key_len是根据表定义计算而得，不是通过表内检索出的）
• ref：表示上述表的连接匹配条件，即哪些列或常量被用于查找索引列上的值
• rows： 表示MySQL根据表统计信息及索引选用情况，估算的找到所需的记录所需要读取的行数，理论上行数越少，查询性能越好
• Extra：该列包含MySQL解决查询的详细信息

EXPLAIN的特性

• EXPLAIN不会告诉你关于触发器、存储过程的信息或用户自定义函数对查询的影响情况
• EXPLAIN不考虑各种Cache
• EXPLAIN不能显示MySQL在执行查询时所作的优化工作
• 部分统计信息是估算的，并非精确值
• EXPALIN只能解释SELECT操作，其他操作要重写为SELECT后查看执行计划。

log

Bin Log:是mysql服务层产生的日志，常用来进行数据恢复、数据库复制，常见的mysql主从架构，就是采用slave同步master的binlog实现的

Redo Log:记录了数据操作在物理层面的修改，mysql中使用了大量缓存，修改操作时会直接修改内存，而不是立刻修改磁盘，事务进行中时会不断的产生redo log，在事务提交时进行一次flush操作，保存到磁盘中。当数据库或主机失效重启时，会根据redo log进行数据的恢复，如果redo log中有事务提交，则进行事务提交修改数据。

Undo Log: 除了记录redo log外，当进行数据修改时还会记录undo log，undo log用于数据的撤回操作，它记录了修改的反向操作，比如，插入对应删除，修改对应修改为原来的数据，通过undo log可以实现事务回滚，并且可以根据undo log回溯到某个特定的版本的数据，实现MVCC

MVCC

MySQL InnoDB实现了多版本并发控制（MVCC），在多版本存储上，MySQL采用从新到旧（Newest To Oldest）的版本链。B+Tree叶结点上，始终存储的是最新的数据（可能是还未提交的数据）。而旧版本数据，通过UNDO记录（做DELTA）存储在回滚段（Rollback Segment）里。每一条记录都会维护一个ROW HEADER元信息，存储有创建这条记录的事务ID，一个指向UNDO记录的指针。通过最新记录和UNDO信息，可以还原出旧版本的记录。

MVCC是通过在每行记录后面保存三个隐藏的列来实现的。一个保存了行的创建版本号，一个保存行的过期版本号，一个指向最近的undo log。每开始一个新的事务，系统版本号都会自动递增。事务开始时刻的系统版本号会作为事务的版本号，用来和查询到的每行记录的版本号进行比较。

下面看一下在REPEATABLE READ隔离级别下，MVCC具体是如何操作的。

• SELECT
  InnoDB会根据以下两个条件检查每行记录：
  InnoDB只查找版本早于当前事务版本的数据行（也就是，行的系统版本号小于或等于事务的系统版本号），这样可以确保事务读取的行，要么是在事务开始前已经存在的，要么是事务自身插入或者修改过的。
  行的删除版本要么未定义，要么大于当前事务版本号。这可以确保事务读取到的行，在事务开始之前未被删除。
  只有符合上述两个条件的记录，才能返回作为查询结果
• INSERT
  InnoDB为新插入的每一行保存当前系统版本号作为行版本号。
• DELETE
  InnoDB为删除的每一行保存当前系统版本号作为行删除标识。
• UPDATE
  InnoDB为插入一行新记录，保存当前系统版本号作为行版本号，同时保存当前系统版本号到原来的行作为行删除标识。
  保存这两个额外系统版本号，使大多数读操作都可以不用加锁。这样设计使得读数据操作很简单，性能很好，并且也能保证只会读取到符合标准的行，不足之处是每行记录都需要额外的存储空间，需要做更多的行检查工作，以及一些额外的维护工作

Innodb vs Myisam

1. InnoDB 支持事务，MyISAM 不支持事务。这是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；
2. InnoDB 支持外键，而 MyISAM 不支持。对一个包含外键的 InnoDB 表转为 MYISAM 会失败；
3. InnoDB 是聚集索引，MyISAM 是非聚集索引。聚簇索引的文件存放在主键索引的叶子节点上，因此 InnoDB 必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。而 MyISAM 是非聚集索引，数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的。
4. InnoDB 不保存表的具体行数，执行 select count(*) from table 时需要全表扫描。而MyISAM 用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快；
5. InnoDB 最小的锁粒度是行锁，MyISAM 最小的锁粒度是表锁。一个更新语句会锁住整张表，导致其他查询和更新都会被阻塞，因此并发访问受限。这也是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一；

如何选择：

1. 是否要支持事务，如果要请选择 InnoDB，如果不需要可以考虑 MyISAM；
2. 如果表中绝大多数都只是读查询，可以考虑 MyISAM，如果既有读写也挺频繁，请使用InnoDB。
3. 系统奔溃后，MyISAM恢复起来更困难，能否接受，不能接受就选 InnoDB；
4. MySQL5.5版本开始Innodb已经成为Mysql的默认引擎(之前是MyISAM)，说明其优势是有目共睹的。如果你不知道用什么存储引擎，那就用InnoDB，至少不会差。