八股汇总
说明
采用折叠语法，方便复习，涉及图片时，采用正常语法，使用
<br>在标签内换行1
2
3
4
5
6
7
8<details>
<summary>题目描述</summary>
<pre>
<code>
答案
</code>
</pre>
</details>尽可能的延伸题目，发散思维
关键词之间通过
&连接整理到418
C/C++
关键字
new & malloc
1. new/delete是C++关键字，需要编译器支持。malloc/free是库函数，需要头文件支持
2. new申请内存不需要指定大小，malloc需要（以字节为单位）
3. new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进行类型转换，故new是符合类型安全性的操作符。而malloc内存分配成功则是返回void * ，需要通过强制类型转换将void*指针转换成我们需要的类型。
4. new内存分配失败时，会抛出bad_alloc异常。malloc分配内存失败时返回NULL。（在operator new抛出异常以反映一个未获得满足的需求之前，它会先调用一个用户指定的错误处理函数，这就是new-handler）
5. new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对象构造和析构工作
6. placement new：使用已有的内存空间并进行对象的初始化工作
7. 已分配内存的扩充：new没有办法，malloc可以使用remalloc
const（部分完成）
修饰全局变量
修饰局部变量
修饰普通函数
修饰类成员函数（this指针）
1. 成员函数后加const后我们称为这个函数为常函数
2. 用`const`修饰成员函数时，`const`修饰this指针指向的内存区域，成员函数体内不可以修改本类中的任何普通成员变量
3. 成员属性声明时加关键字mutable后，在常函数中才可以修改
4. 原理：this指针（this的本质：是指针常量，指针常量的指向是不可以修改的。即谁调用，指向谁，生成对象时，就已经决定了，即this相当于：Person* const this;），因此加了const后变成const Person* const this，值也无法改变
修饰类对象（this指针）：常量对象只能调用常成员函数 原因分析
1. 使用const修饰类的实例化对象
2. 常对象只能调用`const`的成员函数（防止成员函数中修改成员变量）
3. 常对象可访问`const`或`非const`数据成员，不能修改任何变量，除非成员用`mutable`修饰
4. 原理：
1. 常量对象传入函数的是const指针，普通对象传入的为普通指针，普通指针能向常量指针转换而常量指针无法向普通指针转换，即*p能够向const *p转换，但const *p(常量指针)类型无法转换到*p类型(普通指针)
2. 类中函数都隐式传入了this指针，而常函数的作用就是修饰*this不能被修改，也就是 type fun(class *this) const就相当于type fun(const class *this)
atomic
1. atomic对int、char、bool等数据结构进行了原子性封装，在多线程环境中，对std::atomic对象的访问不会造成竞争-冒险。利用std::atomic可实现数据结构的无锁设计
static
static的最主要功能是隐藏，其次因为static变量存放在静态存储区，所以它具备持久性和默认值0
全局变量
1. 全局变量本身就是静态存储方式， 静态全局变量当然也是静态存储方式。 这两者在存储方式上并无不同
2. 区别在于非静态全局变量的作用域是整个源程序，静态全局变量则限制了其作用域， 即只在定义该变量的源文件内有效， 在同一源程序的其它源文件中不能使用它（这一现象发生在多个文件同时编译时，如gcc 1.c 2.c -o 2）
3. 普通全局变量，加extern能够被其他使用，static全局变量不能
局部变量
1. 把局部变量改变为静态变量后是改变了它的存储方式即改变了它的生存期
普通函数
1. static函数与普通函数作用域不同,仅在本文件
2. static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝
类成员变量
1. 静态数据成员可以实现多个对象之间的数据共享，它是类的所有对象的共享成员，它在内存中只占一份空间，如果改变它的值，则各对象中这个数据成员的值都被改变
2. 静态数据成员是在程序开始运行时被分配空间，到程序结束之后才释放，只要类中指定了静态数据成员，即使不定义对象，也会为静态数据成员分配空间
3. 静态数据成员可以被初始化，但是只能在类体外进行初始化，若未对静态数据成员赋初值，则编译器会自动为其初始化为0
4. 静态数据成员既可以通过对象名引用，也可以通过类名引用
类成员函数
1. 静态成员函数和静态数据成员一样，他们都属于类的静态成员，而不是对象成员
2. 非静态成员函数有this指针，而静态成员函数没有this指针
3. 静态成员函数主要用来访问静态数据成员而不能访问非静态成员
final
1. 禁止继承：C++11中允许将类标记为final，方法时直接在类名称后面使用关键字final，如此，意味着继承该类会导致编译错误
2. 禁用重写：C++中还允许将方法标记为fianal，这意味着无法再子类中重写该方法。这时final关键字至于方法参数列表后面
thread_local
1. 线程间隔离，线程内共享
2. C++ 11 关键字：thread_local
指针相关
数组 & 指针
问题
1. 作为函数入参的区别，用sizeof求的话大小是多少？
2. 在作为函数入参，两者有区别嘛？
3. 数组能够直接传入而不变成指针形式嘛？
4. 会改变之前数组的内容嘛？
答案
1. 作为函数入参，数组会退化成指针，所以大小都为4（32位）
2. 没有区别，因为数组会退化成指针，退化为指针是为了高效，因为指针在固定操作系统下长度固定，更加高效
3. 不行，一维数组会退化成一级指针，多维数组退化成数组指针
4. 可以，因为是地址传递
值传递和引用传递
1. 当实参的值被拷贝给形参时，实参和形参是两个独立的变量，我们说实参被值传递或者函数被传值调用
2. 将形参绑定到实参，对引用的操作实际上是作用在引用所引的对象上
三大智能指针（概述）
unique_ptr：持有对对象的独有权——两个unique_ptr不能指向一个对象，即 unique_ptr 不共享它所管理的对象。它无法复制到其他 unique_ptr，无法通过值传递到函数，也无法用于需要副本的任何标准模板库 （STL）算法。只能移动 unique_ptr，即对资源管理权限可以实现转移
shared_ptr：是一个标准的共享所有权的智能指针，允许多个指针指向同一个对象，在使用引用计数的机制上提供了可以共享所有权的智能指针
weak_ptr：它不具有普通指针的行为，没有重载 operator* 和 operator->，表明其是功能较弱的智能指针。它协助 shared_ptr 工作，可获得资源的观测权，像旁观者那样观测资源的使用情况。观察者意味着 weak_ptr 只对 shared_ptr 进行引用，而不改变其引用计数，当被观察的 shared_ptr 失效后，相应的 weak_ptr 也相应失效。 weak_ptr 可用于打破循环引用。引用计数是一种便利的内存管理机制，但它有一个很大的缺点，那就是不能管理循环引用的对象
防止循环引用手段
1. 当只剩下最后一个引用的时候需要手动打破循环引用释放对象
2. 当parent的生存期超过children的生存期的时候，children改为使用一个普通指针指向parent
3. 使用弱引用的智能指针（weak_ptr）打破这种循环引用。,虽然通过弱引用指针可以有效的解除循环引用，但这种方式必须在程序员能预见会出现循环引用的情况下才能使用，也可以是说这个仅仅是一种编译期的解决方案，如果程序在运行过程中出现了循环引用，还是会造成内存泄漏的。因此，不要认为只要使用了智能指针便能杜绝内存泄漏
虚函数
虚函数 & 纯虚函数
1. 虚函数是为了实现动态编联产生的，目的是通过基类类型的指针/引用指向不同对象时，自动调用相应的、和基类同名的函数（使用同一种调用形式，既能调用派生类又能调用基类的同名函数）
2. 纯虚函数只是相当于一个接口名，带纯虚函数的类叫抽象类，含有纯虚函数的类不能够实例化，“=”
3. 都有关键字virtual，虚函数表
4. 子类继承抽象类也必须实现其中的纯虚函数才能实例化对象
虚函数是怎么实现的？
1. 主要通过虚函数指针（vfptr）和虚函数表（vftable）实现
2. 当父类中有了虚函数后，内部结构就发生了改变，多了一个vfptr，vfptr指向vftable，表中存放虚函数的地址
3. 子类会继承父类的虚函数指针vfptr和虚函数表(vftable)，构造函数中会将虚函数指针指向自己的虚函数表
4. 出于效率的考虑，该指针通常放在对象实例最前面的位置（第一个slot处）。每一个class所关联的type_info信息也由virtual table指出（通常放在表格的最前面）
构造函数 & 虚函数表
B继承A，调用B b
1. 调用B的构造函数，先调用A的构造函数
2. 调用A的构造函数，先按照A对象的内存布局进行初始化
3. 因为虚表指针是放在顶部的，先初始化虚表指针，指向虚表（虚表在编译期就生成），之后按照声明顺序初始化成员变量。最后调用构造函数{ }中的代码
3. 由此可见调用this->fun( )时已经设定好虚表指针，所以调用不会有任何问题。之后B将虚表指针指向自己的虚表，初始化自己的成员变量，最后调用B(){ }中的代码this->fun( )，这个时候对象顶部的虚表指针指向B的虚表，调到的自然是B::fun( )。
4. 析构函数完全相反，先调用析构函数{ }中的代码。
STL
vector底层实现
1. 底层有三个指针(start, finish, capacity)，分别指向申请空间的起始位置，目前数组容量位置（即下一个元素放的位置）以及最大空间位置
2. 如果空间不够(finish=capacity)，就会触发扩容机制，申请一块新的空间，并将之前的内容进行拷贝，销毁旧的空间
3. 扩容机制在GCC下是两倍增长，在VS下是1.5倍增长
vector扩容机制
通过求移动元素次数/元素总数求得平均时间复杂度（详见博客）
1. 以等长个数进行扩容：平均时间复杂度O(n)，假设每次扩容k个，那第i次扩容就需要移动ki个元素
2. 以倍数方式进行扩容：平均时间复杂度O(1)，假设每次倍增m倍，那么n个元素，只需要log以m为底n的对数扩容次数即可达到要求
3. 最好的扩容方式：后面申请的空间能够利用上之前已经释放的空间
4. 两者的差别，1.5倍在空间上更友好（有几率复用之前的空间），2倍时间上更友好
5 其实2倍都有点不满足，所以超过更加不满足了，过大会导致空间浪费可能会比较高，无法使用到前面已释放的内存
6. 最好的方式X(n-2)+X(n-1)>=X(n)，又因为要在时间上满足X(n-2)+X(n-1)=X(n)，即斐波拉契数列，所以最佳为1.618倍增长
hashtable
1. hashtable是STL中的一种底层容器，源码中是使用vector进行实现，每个位置是一个链表节点
2. 基本原理是把关键字Key通过一个固定的算法函数即所谓的哈希函数（散列函数）转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的list空间里
说说hashtable的增删查时间复杂度
都是O(1)，因为都是通过哈希函数算出来结果
解决hashtable地址冲突的方法
1. 线性探测：找X+1，X+2，X+i位置是否可行
2. 二次探测：找X+1²，X+2²，X+i²位置是否可行
3. 开链法
hashtable线性探测法和开链法的性能差异*
感觉用开链法的原因是确保查找达到O(1)，如果是线性探测之类的，可能找起来比较麻烦
STL是否线程安全
一般说来，STL对于多线程的支持仅限于下列两点：(貌似Effective STL中有描述)
1.多个读取者是安全的。即多个线程可以同时读取一个容器中的内容。 即此时多个线程调用容器的不涉及到写的接口都可以 eg find, begin, end 等.
2.对不同容器的多个写入者是安全的。即多个线程对不同容器的同时写入合法。 但是对于同一容器当有线程写，有线程读时，如何保证正确? 需要程序员自己来控制，比如：线程A读容器某一项时，线程B正在移除该项。这会导致一下无法预知的错误。 通常的解决方式是用开销较小的临界区（CRITICAL_SECTION）来做同步。
以下列方式同步基本上可以做到线程安全的容器(就是在有写操作的情况下仍能保证安全)。
1.每次调用容器的成员函数的期间需要锁定
2.每个容器容器返回迭代器的生存期需要锁定
3.每个容器在调用算法的执行期需要锁定
1. All container functions are safe to be called concurrently on different objects of the same container type (i.e. it is safe to use two different std::vector instances on two different threads
2. All const member functions can be called concurrently by different threads
3. Containers can be safely read from multiple threads if no thread is making asynchronous writes
4. Different elements in the same container can be modified concurrently, except for the elements of std::vector.
5. If an object is written to by one thread and read by other threads, the object must be protected
6. In general, iterator operations read from a container, but do not modify it, so they are thread-safe. Container operations that invalidate iterators are NOT thread-safe, as they modify the container
vector<bool>的线程安全性：stackoverflow
1. 对容器中不同元素同时写，不是线程安全的
2. 因为底层实现上，读取一个byte但是只会修改一个bit，多线程同时写，会出现覆盖的行为，不安全
面向对象
定义空类时，会创建哪些函数
1. 默认构造函数(无参，函数体为空)
2. 默认析构函数(无参，函数体为空)
3. 默认拷贝构造函数，对类中非静态成员属性简单值拷贝
4. 默认operator=重载函数(赋值运算符重载)，实现简单的值传递
什么是构造函数
1.构造函数是类的成员函数，其名称与类相同
2.构造函数是类的一种特殊类型的成员函数，它初始化类的对象。在 C++ 中，创建对象（类的实例）时会自动调用构造函数
3.在创建对象时调用构造函数。它构造值，即为对象提供数据，这就是它被称为构造函数的原因
4.构造函数没有返回值，因此它们没有返回类型。
5.构造函数可以重载
6.构造函数不能被声明为虚拟的
什么是析构函数
1. 与类同名的一个函数，前面需要加~号
2. 销毁对象时，将自动调用析构函数，完成一些清理工作，比如：释放内存等
3. 不能将其声明为static或const=>static修饰的是类共享（即没有this指针），const修饰无法修改非静态成员（即限制this指针值不能改变）
4. 析构函数没有参数，它没有返回类型，甚至没有void修饰
5. 具有析构函数的类的对象不能成为联合的成员=>联合体共有空间，而构造和析构将会导致空间增加或减小（堆），规定不可用，当c++中的联合体遇到类的构造函数
8. 析构函数应在该类的公共部分中声明
9. 程序员无法访问析构函数的地址
构造函数 & 虚函数
1. 构造函数不可以是虚函数
2. 当类中声明虚函数时，编译器会在类中生成一个虚函数表，虚函数表是一个存储成员函数指针的数据结构
3. 虚函数表是由编译器自动生成与维护的，virtual成员函数会被编译器放入虚函数表中，当存在虚函数时，每个对象都有一个指向虚函数的指针（vptr指针）。在实现多态的过程中，父类和派生类都有vptr指针
4. vptr的初始化：当对象在创建时，由编译器对vptr指针进行初始化。在定义子类对象时，vptr先指向父类的虚函数表，在父类构造完成之后，子类的vptr才指向自己的虚函数表
5. 如果构造函数时虚函数，那么调用构造函数就需要去找vptr，而此时vptr还没有初始化
6. 因此，构造函数不可以是虚函数
构造函数 & 异常
1. 理论上可以，因为C++并没有禁止这一行为的发生，但是一般不抛出异常
2. 构造函数中抛出异常，会导致析构函数不能被调用，所以可能会造成内存泄露或系统资源未被释放
析构函数 & 异常
1. 理论上可以，因为C++并没有禁止这一行为的发生，但是一般不抛出异常
2. 这样会导致程序过早结束或出现不明确的行为
C++异常
1. C++中使用try_catch进行捕获异常
2. 将可能抛出异常的程序段放到try块之中
3. catch语句会根据出现的先后顺序被检查，匹配的catch语句捕获并处理异常(或继续通过throw操作创建一个异常对象并抛出异常)
4. 如果在try段执行期间没有引起异常，那么跟在try后面的catch语句就不会执行
5. 如果匹配的处理未找到，则运行函数terminate将自动被调用，其缺省功能调用abort终止程序
6. 处理不了的异常，可以在catch的最后一个分支，使用throw，向上抛
7. 异常被抛出后，从进入try块起，到异常被抛出前，这期间在栈上构造的所有对象，都会被自动析构。析构的顺序与构造的顺序相反，这一过程称为栈的解旋(unwinding)
重载和重写
1. 重载是指不同的函数使用相同的函数名，但是函数的参数个数或类型不同。调用的时候根据函数的参数来区别不同的函数
2. c++实现多态时会用到。函数重写，也被称为覆盖，是指子类重新定义父类中有相同名称和参数的虚函数，主要在继承关系中出现
模板
1. 编译器并不是把函数模板处理成能够处理任何类型的函数(比如结构体)
2. 函数模板通过具体类型产生不同的函数，由此产生的函数称为模板函数，模板不能直接调用，生成后的模板函数才可以调用
3. 编译器会对函数模板进行两次编译，在声明的地方对模板代码本身进行编译，在调用的地方对参数替换后的代码进行编译
操作系统
进程 & 线程 & 协程
1. 进程是资源调度的基本单位，运行一个可执行程序会创建一个或多个进程，进程就是运行起来的可执行程序
2. 线程是程序执行的基本单位，是轻量级的进程。每个进程中都有唯一的主线程，且只能有一个，主线程和进程是相互依存的关系，主线程结束进程也会结束
3. 协程是用户态的轻量级线程，线程内部调度的基本单位
进程切换 & 线程切换
1. 进程切换涉及到虚拟地址空间的切换而线程切换则不会
2. 因为每个进程都有自己的虚拟地址空间，而线程是共享所在进程的虚拟地址空间的，因此同一个进程中的线程进行线程切换时不涉及虚拟地址空间的转换
判断死锁
1. 用资源分配图判断系统是否死锁，即排除已经分配的资源剩余的资源是否满足进程所需要的需求
2. GDB调试分析死锁
线程调度策略
1. 先来先服务
2. 短作业优先算法
3. 高优先权优先调度算法
4. 高响应比优先调度算法
5. 时间片轮转法
6. 多级反馈队列调度算法
虚拟内存
1. 为了在多进程环境下，使得进程之间的内存地址不受影响，相互隔离，于是操作系统就为每个进程独⽴分配⼀套虚拟地址空间，虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存
2. 操作系统引⼊了虚拟内存，进程持有的虚拟地址会通过 CPU 芯⽚中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存（MMU的主要功能有两项，一个是用来将虚拟地址转换成物理地址，一个是转换的同时检查对应的页是否有执行权限）
3. 分段、分页和段页式
4. 分段：将虚拟地址分成四段（栈、堆、数据和代码），并使用段表（段选择因子和段内偏移量）与物理地址进行映射
5. 分段->外部碎片（产生了多个不连续的小物理内存）->内存交换（将某个程序占用的内存先写到硬盘，然后紧挨其他分配的位置再写回内存）
6. 分页->为了解决内存分段带来的外部碎⽚和内存交换效率低的问题
7. 分页：分⻚是把整个虚拟和物理内存空间切成⼀段段固定尺⼨的⼤⼩（Linux下一页为4KB），并使用页表（页号与页内偏移）与物理地址进行映射，页表存在于进程的内存之中，MMU收到虚拟地址之后查询Page Table来获取物理地址
8. 单级页表：32位下，共4G虚拟内存(2^32)，每个页为4KB(2^12)，故一共100万个页(2^20)，每个页表项需要四字节，故一个进程需要4MB(2^22)来存储，那么100个应用程序就需要400MB=>比较占空间
9. 多级页表：简单分页比较占用空间，多级页表只有在需要的时候才会创建下面的页表（即如果一级页面没用到，就不需要创建后面的页表了）
10. 多级页表转换速度读（要按次序查页表）->TLB（页表缓存）
解引用空指针
1. 现代操作系统提供了虚拟内存的概念，所以在访问空指针时，编译器把空指针当做虚拟内存中的虚拟地址 0 对待，并让你去访问空指针
2. 然后通过页表去查找相应的地址是否在物理内存中出现，发现没有，触发缺页异常
3. 缺页异常处理程序发现你没有访问的权限（Linux 中，每个进程空间的 0x0 虚拟地址开始的线性区(memory region)都会被映射到一个用户态没有访问权限的页上。通过这样的映射，内核可以保证没有别的页会映射到这个区域）
4. 内核发送 SIGSEGV 信号给进程，该信号默认是让进程自杀
mmap
1. 进程启动映射过程，并在虚拟地址空间中为映射创建虚拟映射区域
2. 调用内核空间的系统调用函数mmap（不同于用户空间函数），实现文件物理地址和进程虚拟地址的一一映射关系
注：前两个阶段仅在于创建虚拟区间并完成地址映射，但是并没有将任何文件数据的拷贝至主存。真正的文件读取是当进程发起读或写操作时
3.进程发起对这片映射空间的访问，引发缺页异常，实现文件内容到物理内存（主存）的拷贝
缺页异常
Page fault（硬错误、硬中断、分页错误、寻页缺失、缺页中断、页故障等)指的是当软件试图访问已映射在虚拟地址空间中，但是目前并未被加载在物理内存中的一个分页时，由中央处理器的内存管理单元所发出的中断
行为
1. 假如目标内存页在物理内存中没有对应的页帧或者存在但无对应权限，CPU 就无法获取数据，这种情况下CPU就会报告一个缺页错误
2. 由于CPU没有数据就无法进行计算，CPU罢工了用户进程也就出现了缺页中断，进程会从用户态切换到内核态，并将缺页中断交给内核的 Page Fault Handler 处理
缺页异常的几种情况（口述版）：
1. 分为有效缺页异常（硬缺页错误和软缺页错误）和无效缺页异常（无效缺页错误）
2. Hard Page Fault 也被称为Major Page Fault，翻译为硬缺页错误/主要缺页错误，这时物理内存中没有对应的页帧，需要CPU打开磁盘设备读取到物理内存中，再让MMU建立VA和PA的映射
3. Soft Page Fault 也被称为Minor Page Fault，翻译为软缺页错误/次要缺页错误，这时物理内存中是存在对应页帧的，只不过可能是其他进程调入的，发出缺页异常的进程不知道而已，此时MMU只需要建立映射即可，无需从磁盘读取写入内存，一般出现在多进程共享内存区域
4. Invalid Page Fault 翻译为无效缺页错误，比如进程访问的内存地址越界访问，又比如对空指针解引用内核就会报segment fault，并会升级触发SIGSEGV信号结束进程
缺页异常的几种情况（源码版）：
1. 当 MMU 中没有创建虚拟页物理页映射关系，并且在该虚拟地址之后没有当前进程的线性区 vma 的时候，肯定这编码错误，将杀掉进程；
2. 当 MMU 中没有创建虚拟页物理页映射关系，并且在该虚拟地址之后存在当前进程的线性区 vma 的时候，可能是栈溢出导致的缺页异常；
3. 使用 malloc/mmap 等希望访问物理空间的库函数 / 系统调用后，linux 并未真正给新创建的 vma 映射物理页
1. 若先进行写操作，如上面的 2 的情况产生缺页异常
2. 若先进行读操作，虽也会产生缺页异常，将被映射给默认的零页 (zero_pfn)，等再进行写操作时，仍会产生缺页异常，进入写时复制的流程；
4. 使用 fork 等系统调用创建子进程，子进程不论有无自己的 vma，“它的”vma 都有对于物理页的映射，但它们共同映射的这些物理页属性为只读，即 linux 并未给子进程真正分配物理页，当父子进程任何一方要写相应物理页时，导致缺页异常的写时复制；
遍历数组和链表性能为什么差那么多
1. cpu读取数据是按照缓存行读取到缓存的，简单来说就是cpu会把需要的数据加载到缓存中，查找数据时，会先从缓存找，找不到再到内存找
2. 而数组作为连续内存，cpu缓存会把一片连续的内存空间读入，这样连续内存的数组会更易于整块读取到缓存中，当进行遍历时，直接命中缓存
3. 链表是跳跃式的地址，很轻易就会跳出缓存，跑到内存中去查找数据。所以会慢很多
使用fprintf时操作系统做了什么？*
个人理解（暂时没找到）：
1. 用户应用进程调用fprintf函数，是一个输出的操作，所以应该会调用C库中的write函数，然后向操作系统发起IO调用，上下文从用户态转为内核态
2. CPU将用户缓冲区中的数据，拷贝到需要输出的文件缓冲区中
3. 执行完一系列操作以后，再由内核态切换成用户态
IO多路复用（select，poll，epoll）
概念
I/O多路复用（multiplexing）的本质是通过一种机制（系统内核缓冲I/O数据），让单个进程可以监视多个文件描述符，一旦某个描述符就绪（一般是读就绪或写就绪），能够通知程序进行相应的读写操作。（包括select、poll、epoll）
select
1. select实现了IO多路复用的基本要求，但是只会通知有几个任务可用，但不知道具体哪几个任务，还需遍历
2. 每次调用select，都需要把fd集合（文件描述符集合）从用户态拷贝到内核态，这个开销在fd很多时会很大
3. 同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大
4. select支持的文件描述符数量太小了，默认是1024
5. 文件描述符集合不能重用，每次都需要重置
poll
1. 在select的基础上进行改进，用一个结构体记录文件描述符集合，并记录用户态状态和内核态状态
2. 解决了：(1)select支持的文件描述符数量太小了，默认是1024;(2)fds集合不能重用，每次都需要重置
3. 问题依旧：（1）每次调用poll，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大；（2）同时每次调用poll都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大
epoll
1. 直接在内核态创建 eventpoll实例(结构体)，通过epoll提供的API操作该实例，比如使用epoll_ctl维护等待队列，再调用epoll_wait阻塞进程
2. 结构体中有红黑树和双链表，分别用来存储需要检测的文件描述符和存储已经发生改变的文件描述符
3. 因为像select和poll这种都是只能返回有几个文件描述符发生了改变，所以还需要遍历整个数组，而epoll维护的就绪队列就可以很快的进行操作
epoll中LT与ET区别
水平触发(level triggered, LT)
1. epoll的缺省的工作方式，并且同时支持 block 和 non-block socket
2. 在LT下，内核告诉你一个文件描述符是否就绪了，然后你可以对这个就绪的 fd 进行 IO 操作。如果你不作任何操作，内核还是会继续通知你的
边沿触发(edge triggered, ET)
1. 是高速工作方式，只支持 non-block socket，需要对监听文件描述符设置才能实现
2. 只会通知一次
两者的区别
1. ET 模式在很大程度上减少了 epoll 事件被重复触发的次数，因此效率要比 LT 模式高
2. epoll工作在 ET 模式的时候，必须使用非阻塞套接口，以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死（因为需要循环读取，如果缓冲区没数据了，那么就会卡在那，配合EAGAIN退出循环）
3. 所以如果使用ET且缓冲区内容不能一次性读完，需要写一个循环将内容全部读取，且需要将套接字设置为非阻塞
epoll中红黑树和链表怎么协作？
1. 首先通过epoll_ctl将要监听的文件描述符放到红黑树上面
2. 当socket收到数据后，中断程序会给eventpoll的“就绪列表”添加socket引用
3. 节点会同时存在红黑树和链表里面嘛？：其实是会的，当某个socket读取到数据，那么就会给一个引用放到双向链表里面，也就是就绪队列
函数调用行为（普通函数，普通成员函数，虚函数）
1. 栈帧，也就是stack frame，其本质就是一种栈，只是这种栈专门用于保存函数调用过程中的各种信息（参数，返回地址，本地变量等）=>（栈帧也叫过程活动记录，是编译器用来实现过程/函数调用的一种数据结构。简言之，栈帧就是利用EBP（栈帧指针，请注意不是ESP）寄存器访问局部变量、参数、函数返回地址等的手段）
2. 普通函数调用流程：假设main函数（A）中调用func函数（B）
1. 当A调用B时，会把返回地址压入栈中，指明B返回时，要从A的哪个位置继续执行，这一步属于A的栈帧
2. 扩展当前栈的空间，为B开辟栈帧空间
3. 函数参数从右至左进行压栈（可能通过寄存器传递，如果参数小于6个）
4. 函数局部变量进行压栈，注意静态变量是不入栈的
3. 普通成员函数调用流程（大体）：1. 由于函数地址在编译期间已确定，所以直接找到该函数地址，2. this指针，作为隐含参数传入该函数，3. 之后的调用和普通函数调用方式一致，4. 注意：如果该函数中，使用了实例的成员变量，由于this指针为null，程序会报错=》感觉说的是没有实例化对象的时候？
4. 虚函数调用流程（大体）：1. 查找this指针（也就是实例）的地址，2. 根据this指针，查找虚函数表（函数指针数组）的地址，3. 从虚函数表中，取出相应的函数地址
为什么函数参数从右往左压栈？（https://blog.csdn.net/xxxxxx91116/article/details/40478173）
1. 从右向左压栈的顺序是与C/C++支持可变参数有关的
可以举例printf("%d %d %d", 1, 2, 3)
2. 从右到左的好处是，第一个参数就在栈顶，我们很方便就定位到了第一个参数的位置
3. C方式参数入栈顺序(从右至左)的好处就是可以动态变化参数个数。通过栈堆分析可知，自左向右的入栈方式，最前面的参数被压在栈底。这样的话，除非知道参数个数，否则是无法通过栈指针的相对位移求得最左边的参数。这样就变成了左边参数的个数不确定，正好和动态参数个数的方向相反
什么是线程安全？
1. 线程安全就是多线程访问时，采用了加锁机制，当一个线程访问该类的某个数据时，进行保护，其他线程不能进行访问直到该线程读取完，其他线程才可使用。不会出现数据不一致或者数据污染
2. 线程不安全就是不提供数据访问保护，有可能出现多个线程先后更改数据造成所得到的数据是脏数据
什么情况会导致线程不安全
同一个程序运行在多个线程中本身不会有线程安全问题，问题在于多个线程访问共享资源时存在，如：类成员变量（普通或静态变量），系统共享资源（文件，数据库）等。
想在栈上动态分配内存
alloca函数：能够在栈上申请空间，但是可能引起爆栈，不推荐使用
可执行文件加载到内存中，描述地址分配情况（可执行程序的空间分布）
程序运行开始，由系统为进程地址空间中的text/data/bss段进行映射，由系统的缺页异常处理程序按需将磁盘上程序文件中的真正代码、数据写入进程。此外，bss区域中的所有变量都会被清零
代码段（.text）：指用来存放程序执行代码（汇编代码）的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读，某些架构也允许代码段为可写，即允许修改程序。在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等
数据段（.data）：数据段(datasegment)通常是指用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配
数据段（.bss）：BSS段(bsssegment)通常是指用来存放程序中未初始化的全局变量的一块内存区域。BSS是英文BlockStarted by Symbol的简称。BSS段属于静态内存分配
堆（heap）：堆是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上(堆被扩张)；当利用free等函数释放内存时，被释放的内存从堆中被剔除(堆被缩减)
栈（stack）：是用户存放程序临时创建的局部变量，也就是说我们函数括弧“{}”中定义的变量(但不包括static声明的变量，static意味着在数据段中存放变量)。除此以外，在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。由于栈的先进先出特点，所以栈特别方便用来保存/恢复调用现场。从这个意义上讲，我们可以把堆栈看成一个寄存、交换临时数据的内存区
常量段：常量段一般包含编译器产生的数据(与只读段包含用户定义的只读数据不同)。比如说由一个语句a=2+3编译器把2+3编译期就算出5，存成常量5在常量段中
.rodata：存放C中的字符串和#define定义的常量
注意事项
1. text和data段都在可执行文件中(在嵌入式系统里一般是固化在镜像文件中)，由系统从可执行文件中加载
2. bss段不在可执行文件中，由系统初始化
3. bss段(未手动初始化的数据)并不给该段的数据分配空间，只是记录数据所需空间的大小，具体体现为一个占位符
4. bss是不占用.exe文件空间的，其内容由操作系统初始化(清零)；而.data却需要占用，其内容由程序初始化
动态库 & 静态库
概念
1. 库文件是计算机上的一类文件，可以简单的把库文件看成一种代码仓库，它提供给使用者一些可以直接拿来用的变量、函数或类，库是特殊的一种程序，编写库的程序和编写一般的程序区别不大，只是库不能单独运行
2. 静态库在程序的链接阶段被复制到了程序中
3. 动态库在链接阶段没有被复制到程序中，而是程序在运行时由系统动态加载到内存中供程序调用
静态库优缺点
优点
1. 静态库被打包到应用程序中，所以加载速度更快
2. 发布程序无需提供静态库，移植方便
缺点
1. 消耗系统资源，浪费内存
2. 更新、部署、发布麻烦
动态库优缺点
优点
1. 可以实现进程间资源共享（共享库）
2. 更新、部署、发布简单
3. 可以控制何时加载动态库
缺点
1. 加载速度比静态库慢
2. 发布程序时需要提供依赖的动态库
malloc底层实现（Linux）
1. 在用户态层面，进程使用库函数malloc分配的是虚拟内存，并且系统是延迟分配物理内存的，由缺页中断来完成分配
在内核态层面，内核也需要物理内存，并且使用了另外一套不同于用户态的分配机制和系统调用函数
Linux下用户态的进程通过库函数malloc来申请内存，malloc调用了brk/mmap（小于128KB和大于128KB）这两个系统调用，最终触达到伙伴系统实现内存分配
2. malloc将内存分成了大小不同的chunk，malloc将相似大小的chunk用双向链表链接起来，这样一个链表被称为一个bin，malloc一共维护了128个bin，并使用一个数组来存储这些bin
1. bins[0]目前没有使用
2. bins[1]的链表称为unsorted_list，用于维护free释放的chunk。
3. bins[2,63]总计长度为62的区间称为small_bins，用于维护＜512B的内存块，其中每个bin中对应的链表中的chunk大小相同，相邻bin的大小相差8字节，范围为16字节到504字节
4. bins[64,126]总计长度为63的区间称为large_bins，用于维护大于等于512字节的内存块，每个元素对应的链表中的chunk大小不同，数组下标越大链表中chunk的内存越大，large bins中的每一个bin分别包含了一个给定范围内的chunk，其中的chunk按大小递减排序，最后一组的largebin链中的chunk大小无限制，该bins的使用频率低于small bins
计网
TCP三次握手-简
1. 客户端发送SYN和客户端随机序列号
2. 服务端回SYN和ACK，确认序号和服务端随机序列号
3. 客户端回ACK和确认序号
TCP三次握手（详细）
1. 一开始，客户端和服务端都处于 CLOSED 状态。先是服务端主动监听某个端口，处于 LISTEN 状态
2. 客户端会产生随机初始化序号（client_isn），将此序号置于 TCP 首部的「序号」字段中，同时把 SYN 标志位置为 1 ，表示 SYN 报文。接着把第一个 SYN 报文发送给服务端，表示向服务端发起连接，该报文不包含应用层数据，之后客户端处于 SYN-SENT 状态
3. 服务端收到客户端的 SYN 报文后，首先服务端也随机初始化自己的序号（server_isn），将此序号填入 TCP 首部的「序号」字段中，其次把 TCP 首部的「确认应答号」字段填入 client_isn + 1, 接着把 SYN 和 ACK 标志位置为 1。最后把该报文发给客户端，该报文也不包含应用层数据，之后服务端处于 SYN-RCVD 状态
4. 客户端收到服务端报文后，还要向服务端回应最后一个应答报文，首先该应答报文 TCP 首部 ACK 标志位置为 1 ，其次「确认应答号」字段填入 server_isn + 1 ，最后把报文发送给服务端，这次报文可以携带客户到服务器的数据，之后客户端处于 ESTABLISHED 状态
5. 服务器收到客户端的应答报文后，也进入 ESTABLISHED 状态
TCP四次挥手
客户端和服务端都可以主动断开连接，我就说一下以客户端主动断开连接的过程
1. 客户端主动发起断开连接请求，会发送一个 TCP 首部 FIN 标志位被置为 1 的报文，也即 FIN 报文，客户端进入FIN_WAIT_1 状态
2. 服务端收到该报文后，就向客户端发送 ACK 应答报文，接着服务端进入 CLOSED_WAIT 状态
3. 客户端收到服务端的 ACK 应答报文后，之后进入 FIN_WAIT_2 状态
4. 等待服务端处理完数据后，也向客户端发送 FIN 报文，之后服务端进入 LAST_ACK 状态
5. 客户端收到服务端的 FIN 报文后，回一个 ACK 应答报文，之后进入 TIME_WAIT 状态
6. 服务器收到了 ACK 应答报文后，就进入了 CLOSED 状态，至此服务端已经完成连接的关闭
7. 客户端在经过 2MSL 一段时间后，自动进入 CLOSED 状态，至此客户端也完成连接的关闭
TCP协议如何保证可靠传输
TCP 是通过序列号、确认应答、重发控制、连接管理以及窗口控制等机制实现可靠性传输的
TCP网络拥塞算法
1. 慢启动
2. 拥塞避免算法
3. 当发生了「超时重传」，则就会使用拥塞发生算法
4. 快速重传和快速恢复
get & post
1. Get ⽅法的含义是请求从服务器获取资源，这个资源可以是静态的⽂本、⻚⾯、图⽚视频等，GET把参数包含在URL中
2. POST ⽅法向 URI 指定的资源提交数据，数据就放在报⽂的 body ⾥，POST通过request body传递参数
3. GET安全且幂等，POST两者都不是
4. GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留。
5. GET请求在URL中传送的参数是有长度限制。（大多数）浏览器通常都会限制url长度在2K个字节，而（大多数）服务器最多处理64K大小的url。
6. GET产生一个TCP数据包；POST产生两个TCP数据包。对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；而对于POST，浏览器先发送header，服务器响应100（指示信息—表示请求已接收，继续处理）continue，浏览器再发送data，服务器响应200 ok（返回数据）
TCP & UDP (概念对比)
1. TCP面向连接，UDP面向无连接
2. TCP提供可靠的服务，UDP不保证可靠交互
3. TCP面向字节流，UDP面向数据包
4. TCP只能一对一，UDP可以一对一，一对多和多对多
5. TCP首部开销20字节，UDP的首部开销小，只有8个字节
6. TCP的逻辑通信信道是全双工的可靠信道，UDP则是不可靠信道
TCP & UDP (头部对比)
TCP头部
- 源端口号：发送方端口号
- 目的端口号：接收方端口号
- 序号：本报文段的数据的第一个字节的序号
- 确认号：期望收到对方下一个报文段的第一个数据字节的序号
- 头部长度（数据偏移）：TCP 报文段的数据起始处距离 TCP 报文段的起始处有多远，即首部长度。==单位：32位，即以 4 字节为计算单位==？？？
- 保留：占 6 位，保留为今后使用，目前应置为 0
- 紧急 `URG` ：此位置 1 ，表明紧急指针字段有效，它告诉系统此报文段中有紧急数据，应尽快传送
- 确认 `ACK`：仅当 ACK=1 时确认号字段才有效，TCP 规定，在连接建立后所有传达的报文段都必须把 ACK 置1
- 推送 `PSH`：当两个应用进程进行交互式的通信时，有时在一端的应用进程希望在键入一个命令后立即就能够收到对方的响应。在这种情况下，TCP 就可以使用推送（push）操作，这时，发送方TCP 把 PSH 置 1，并立即创建一个报文段发送出去，接收方收到 PSH = 1 的报文段，就尽快地（即“推送”向前）交付给接收应用进程，而不再等到整个缓存都填满后再向上交付
- 复位 `RST`：用于复位相应的 TCP 连接
- 同步 `SYN`：仅在三次握手建立 TCP 连接时有效。当 SYN = 1 而 ACK = 0 时，表明这是一个连接请求报文段，对方若同意建立连接，则应在相应的报文段中使用 SYN = 1 和 ACK = 1。因此，SYN 置1 就表示这是一个连接请求或连接接受报文
- 终止 `FIN`：用来释放一个连接。当 FIN = 1 时，表明此报文段的发送方的数据已经发送完毕，并要求释放运输连接
- 窗口：指发送本报文段的一方的接收窗口（而不是自己的发送窗口）
- 校验和：校验和字段检验的范围包括首部和数据两部分，在计算校验和时需要加上 12 字节的伪头部
- 紧急指针：仅在 URG = 1 时才有意义，它指出本报文段中的紧急数据的字节数（紧急数据结束后就是普通数据），即指出了紧急数据的末尾在报文中的位置，注意：即使窗口为零时也可发送紧急数据
- 选项：长度可变，最长可达 40 字节，当没有使用选项时，TCP 首部长度是 20 字节
UDP头部
- 源端口号：发送方端口号
- 目的端口号：接收方端口号
- 长度：UDP用户数据报的长度，最小值是8（仅有首部）
- 校验和：检测UDP用户数据报在传输中是否有错，有错就丢弃
浏览器输入baidu.com发生了什么
发送请求
1. 首先浏览器做的第一步工作就是要对 URL 进行解析，从而生成发送给 Web 服务器的请求信息
2. 通过DNS查询域名对应的IP地址（先找浏览器缓存、然后操作系统缓存，然后是hosts 文件看，如果缓存都没有，就询问本地DNS服务器，如果还是没有：根->顶级->权威）
3. 往下传到达传输层，添加TCP头部，填写源端口（操作系统分配）和目的端口（特殊）
4. 往下传到达网络层，添加IP头部，填写源IP和目的IP
源地址IP，即是客户端输出的 IP 地址，多个网卡的话，靠路由表进行查询，如果匹配得到就填写相应网段，如果匹配不到，就填写默认网关的网段
目标地址，即通过 DNS 域名解析得到的 Web 服务器 IP
5. 然后达到网际接口层，填写源MAC和目的MAC，用于两点间传输，通过ARP广播获得（ARP缓存）
6. 经过一系列封装，需要将数字信息转换为电信号，才能在网线上传输，网卡执行操作：网卡驱动从 IP 模块获取到包之后，会将其复制到网卡内的缓存区中，接着会在其开头加上报头和起始帧分界符，在末尾加上用于检测错误的帧校验序列
接收请求
交换机
1. 电信号到达网线接口，交换机模块将电信号转换为数字信号，然后通过包末尾的 FCS 校验错误，如果没问题则放到缓冲区
2. 然后交换机根据 MAC 地址表查找 MAC 地址，然后将信号发送到相应的端口（如果表里面没有，那就广播，并缓存），交换机原样转发
路由器
3. 经过交换机之后，现在到达了路由器，并在此被转发到下一个路由器或目标设备。电信号到达网线接口部分，路由器中的模块会将电信号转成数字信号，然后通过包末尾的 FCS 进行错误校验，如果没问题则检查 MAC 头部中的接收方 MAC 地址，看看是不是发给自己的包，如果是就放到接收缓冲区中，否则就丢弃这个包
4. 完成包接收操作之后，路由器就会去掉包开头的 MAC 头部，查询路由表确定输出端口。如果路由表中的网关列为空，到达目的地址，如果不为空，继续转发
面试官：主机决定用哪个MAC的时候靠路由表进行查询
1. 如果目的IP和源IP在一个子网中，直接请求目的的ARP，并拿到MAC地址
2. 如果目的IP和源IP不在一个子网中，请求的是本网段网关（交换机）的MAC地址
cookie & session
区别：
1. Cookie通过在客户端记录信息确定用户身份，Session通过在服务器端记录信息确定用户身份
2. cookie不是很安全，别人可以分析存放在本地的COOKIE并进行COOKIE欺骗，考虑到安全应当使用session
3. 设置cookie时间可以使cookie过期
4. session会在一定时间内保存在服务器上。当访问增多，会比较占用你服务器的性能考虑到减轻服务器性能方面，应当使用cookie
5. 单个cookie保存的数据不能超过4K，很多浏览器都限制一个站点最多保存20个cookie。(Session对象没有对存储的数据量的限制，其中可以保存更为复杂的数据类型)
6. 一个是IE启动到IE关闭.(浏览器页面一关 ,session就消失了)，一个是预先设置的生存周期，或永久的保存于本地的文件。(cookie)
使用场景
1. 客户端和服务器连接
OSI七层模型与五层模型
OSI七层：应用、表示、会话、传输、网络、数据链路、物理
五层：应用、传输、网络、数据链路、物理
OSI七层模型各层的作用
应用层：网络服务与最终用户的一个接口
表示层：数据的表示、安全、压缩
会话层：建立、管理、中止会话
传输层：定义传输数据的协议号端口，以及流控和差错校验
网络层：进行逻辑地址寻址，实现不同网络间的路径选择
数据链路层：建立逻辑连接，进行硬件地址寻址，差错校验功能
物理层：建立、维护、断开物理连接
应该是上三层（应用、表示、会话）在实际场景中不能或者不需要分得特别细吧？（没找到）
大报文传输
在IP 协议中的分片算法主要解决异种网最大传输单元(MTU) 的不同（http://blog.chinaunix.net/uid-26993600-id-3359402.html）
既然 IP 层会分片，为什么 TCP 层还需要 MSS 呢？=>IP层效率低
1. 当如果一个 IP 分片丢失，整个 IP 报文的所有分片都得重传
2. IP 层本身没有超时重传机制，它由传输层的 TCP 来负责超时和重传
3. 当接收方发现 TCP 报文（头部 + 数据）的某一片丢失后，则不会响应 ACK 给对方，那么发送方的 TCP 在超时后，就会重发「整个 TCP 报文（头部 + 数据）」
假设发送方发送一个 4000 字节的大数据报，若要传输在以太网链路，则需要把数据报分片成 3 个小数据报进行传输，再交由接收方重组成大数据报（经过分片之后的 IP 数据报在被重组的时候，只能由目标主机进行，路由器是不会进行重组的）
IP分片要修改IP数据报中的标志、分片偏移和总长度的值，其他的不变
标志（flag）：目前只有两位有意义
- 标志字段中的最低位记为 MF。MF = 1 即表示后面“还有分片”的数据报。MF = 0 表示这已是若干数据报片中的最后一个
- 标志字段中间的一位记为 DF，意思是“不能分片”，只有当 DF = 0 时才允许分片
片偏移：指出较长的分组在分片后，某片在源分组中的相对位置，也就是说，相对于用户数据段的起点，该片从何处开始。片偏移以 8 字节为偏移单位
IP分片 & 报文合并
IP分片
标志（flag）：目前只有两位有意义
- 标志字段中的最低位记为 MF。MF = 1 即表示后面“还有分片”的数据报。MF = 0 表示这已是若干数据报片中的最后一个
- 标志字段中间的一位记为 DF，意思是“不能分片”，只有当 DF = 0 时才允许分片
报文合并
- 本地流量，即已经到达目的端，需要进行重组，然后交给上层协议
- 过路流量：根据是否允许分片分为两种情况（传输过程的MTU发生改变，所以可能还需要分片，IP分片就是为了这个设计的，如果不需要分片直接转发不用重组）
- 允许分片（DF=0）：中间路由器负责IP分片，分片到达目的地进行重组
- 不允许分片（DF=1）：中间路由器丢弃IP包，并发ICMP 消息给上一条，要求发送更小的IP数据包
IP层路由
1. 默认路由是一种特殊的静态路由，指的是当路由表中和包的目的地址之间没有匹配的表项时路由器能够做出的选择
2. 如果没有默认路由器，那么目的地址在路由表中没有匹配表项的包将被丢弃
3. 同一个子网下，但是没有MAC地址：ARP广播获得MAC地址
数据库
B+树介绍
1. B树和B+数都是多叉搜索树
2. B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树，但它们在降低磁盘I/O操作数方面要更好一些
3. B+树是B树的一种变形，它把所有的数据都存储在叶节点中，内部节点只存放关键字和孩子指针
B+树只在叶子结点存数据有什么好处？
1. 索引结点中不存数据，只存键和指针，所以一个索引结点就可以存储大量的分支，而一个索引结点只需要一次IO即可读取到内存中
2. 最大化了内部节点的分支因子，所以B+树的遍历也更加高效(B树需要以中序的方式遍历节点，而B+树只需把所有叶子节点串成链表就可以从头到尾遍历)
MySQL事务(ACID)
ACID
A：原子性（Atomicity），一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节，而且事务在执行过程中发生错误，会被回滚到事务开始前的状态，就像这个事务从来没有执行过一样
C：一致性（Consistency）：数据库的完整性不会因为事务的执行而受到破坏，比如表中有一个字段为姓名，它有唯一约束，也就是表中姓名不能重复，如果一个事务对姓名字段进行了修改，但是在事务提交后，表中的姓名变得非唯一性了，这就破坏了事务的一致性要求，这时数据库就要撤销该事务，返回初始化的状态
I：隔离性（Isolation）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致
D：持久性（Durability）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失
InnoDB 引擎通过什么技术来保证事务的这四个特性的呢？
持久性是通过 redo log （重做日志）来保证的；
原子性是通过 undo log（回滚日志） 来保证的；
隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；
一致性则是通过持久性+原子性+隔离性来保证；
脏读、不可重复读、幻读（严重性依次减弱）
简略
脏读：读到其他事务未提交的数据；
不可重复读：前后读取的数据不一致；
幻读：前后读取的记录数量不一致
详细
脏读：如果一个事务「读到」了另一个「未提交事务修改过的数据」，就意味着发生了「脏读」现象
不可重复读：在一个事务内多次读取同一个数据，如果出现前后两次读到的数据不一样的情况，就意味着发生了「不可重复读」现象
幻读：在一个事务内多次查询某个符合查询条件的「记录数量」，如果出现前后两次查询到的记录数量不一样的情况，就意味着发生了「幻读」现象
MySQL隔离级别
四种隔离级别
读未提交（read uncommitted），指一个事务还没提交时，它做的变更就能被其他事务看到；
读提交（read committed），指一个事务提交之后，它做的变更才能被其他事务看到；
可重复读（repeatable read），指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别；
串行化（serializable ）；会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行
InnoDB默认隔离级别如何解决幻读？
InnoDB 引擎的默认隔离级别虽然是「可重复读」，但是它通过next-key lock 锁（行锁和间隙锁的组合）来锁住记录之间的“间隙”和记录本身，防止其他事务在这个记录之间插入新的记录，这样就避免了幻读现象
四种隔离级别的实现原理
对于「读未提交」隔离级别的事务来说，因为可以读到未提交事务修改的数据，所以直接读取最新的数据就好了；
对于「串行化」隔离级别的事务来说，通过加读写锁的方式来避免并行访问；
对于「读提交」和「可重复读」隔离级别的事务来说，它们是通过 Read View 来实现的，它们的区别在于创建 Read View 的时机不同，大家可以把 Read View 理解成一个数据快照，就像相机拍照那样，定格某一时刻的风景。「读提交」隔离级别是在「每个语句执行前」都会重新生成一个 Read View，而「可重复读」隔离级别是「启动事务时」生成一个 Read View，然后整个事务期间都在用这个 Read View
MySQL的MVCC
当前读与快照读
1. 当前读：它读取的数据库记录，都是当前最新的版本，会对当前读取的数据进行加锁，防止其他事务修改数据。是悲观锁的一种操作
2. 快照读：快照读的实现是基于多版本并发控制，即MVCC，既然是多版本，那么快照读读到的数据不一定是当前最新的数据，有可能是之前历史版本的数据
MVCC=>快照读
1. Multi-Version Concurrency Control，即多版本并发控制，主要是为了提高数据库的并发性能
2. 同一行数据平时发生读写请求时，会上锁阻塞住。但MVCC用更好的方式去处理读-写请求，做到在发生读-写请求冲突时不用加锁（这个读是指的快照读，而不是当前读，当前读是一种加锁操作，是悲观锁）
3. MVCC指的就是在使用READ COMMITTD（读提交）、REPEATABLE READ（可重复读）这两种隔离级别的事务在执行普通的SEELCT操作时访问记录的版本链的过程，这样子可以使不同事务的读-写、写-读操作并发执行，从而提升系统性能
数据库的设计中有哪些模块？——存储引擎、优化器
1. 连接层：最上层是一些客户端和链接服务，包含本地sock 通信和大多数基于客户端/服务端工具实现的类似于 TCP/IP的通信，主要完成一些类似于连接处理、授权认证、及相关的安全方案
2. 服务层：第二层架构主要完成大多数的核心服务功能，如SQL接口，并完成缓存的查询，SQL的分析和优化，部分内置函数的执行。所有跨存储引擎的功能也在这一层实现，如过程、函数等
3. 引擎层：存储引擎真正的负责了MySQL中数据的存储和提取，服务器通过API和存储引擎进行通信。不同的存储引擎具有不同的功能，这样我们可以根据自己的需要，来选取合适的存储引擎
4. 数据存储层，主要是将数据存储在文件系统之上，并完成与存储引擎的交互
MySQL索引
1. Primary Key（聚集索引）：InnoDB存储引擎的表会存在主键（唯一非null），如果建表的时候没有指定主键，则会使用第一非空的唯一索引作为聚集索引，否则InnoDB会自动帮你创建一个不可见的、长度为6字节的row_id用来作为聚集索引。
2. 单列索引：单列索引即一个索引只包含单个列
3. 组合索引：组合索引指在表的多个字段组合上创建的索引，只有在查询条件中使用了这些字段的左边字段时，索引才会被使用。使用组合索引时遵循最左前缀集合
4. Unique（唯一索引）：索引列的值必须唯一，但允许有空值。若是组合索引，则列值的组合必须唯一。主键索引是一种特殊的唯一索引，不允许有空值
5. Key（普通索引）：是MySQL中的基本索引类型，允许在定义索引的列中插入重复值和空值
6. FULLTEXT（全文索引）：全文索引类型为FULLTEXT，在定义索引的列上支持值的全文查找，允许在这些索引列中插入重复值和空值。全文索引可以在CHAR、VARCHAR或者TEXT类型的列上创建
7. SPATIAL（空间索引）：空间索引是对空间数据类型的字段建立的索引，MySQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING和POLYGON。MySQL使用SPATIAL关键字进行扩展，使得能够用于创建正规索引类似的语法创建空间索引。创建空间索引的列必须声明为NOT NULL
MySQL优化技巧
1. 查看SQL执行频率：show [session|global] status 命令可以提供服务器状态信息
2. 定位低效率执行SQL：慢查询日志、show processlist（慢查询日志在查询结束以后才纪录，所以在应用反映执行效率出现问题的时候查询慢查询日志并不能定位问题，可以使用show processlist命令查看当前MySQL在进行的线程，包括线程的状态、是否锁表等，可以实时地查看 SQL 的执行情况，同时对一些锁表操作进行优化）
3. explain分析执行计划
4. show profile分析SQL
MySQL的回表机制
1. 先检查二级索引的 B+Tree 的索引值，找到对应的叶子节点，然后获取主键值
2. 然后再通过主键索引中的 B+Tree 树查询到对应的叶子节点，然后获取整行数据
3. 即要查两个 B+Tree 才能查到数据
4. 在查询时使用了二级索引，如果查询的数据能在二级索引里查询的到，那么就不需要回表，这个过程就是覆盖索引
5. 如果查询的数据不在二级索引里，就会先检索二级索引，找到对应的叶子节点，获取到主键值后，然后再检索主键索引，就能查询到数据了，这个过程就是回表
红黑树
红黑树概念：红黑二叉树(简称：红黑树)，它首先是一棵二叉树，同时也是一棵自平衡的排序二叉树
1. 每个节点要么是红色，要么是黑色
2. 根节点永远是黑色的。
3. 所有的叶节点都是空节点(即 null)，并且是黑色的。
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点
系列问题
1. 保证平衡性的好处：便于查找，红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)
2. 是二叉树嘛？：是的
3. 和B+树的区别：二叉树和多叉树，红黑树结构的数据常常存在于主存中，主要用于快速查找。树的每个节点存储的数据量比较小，cpu通过与主存少量的交互就能获取树的全部数据，并快速的查找到所需数据。而B+树形式的数据常常存在于SSD或磁盘中，由于树的深度比较小(一般3~4)，能够减少cpu于磁盘间的交互时间
4. 缺点：二叉树导致树太高
5. 并发调整会不会有影响：不是线程安全的
算法
设计模式
情景设计
设计一个数据结构：线程间数据隔离、线程内数据共享
1. 有一个Person对象，通过入参的传递进行实现
2. 使用map绑定线程ID和数据值
3. C++11 thread_local
博客
记录内容丰富，但暂未自己归纳的博客
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 cv-programmer！
