Core-Knowledge
2020-04-12 10:00:00 +0800
核心知识库
2020核心知识体系，基础知识+上层应用+实践能力，2020年2、3、4月学习复习总结
2020 核心知识体系
2020 全年学习计划和路径
目录
I. 计算机基础知识
- 高级编程语言
- C/C++
- Golang
- Python
- Shell编程
- 计算机网络
- 应用层 OSI中7层
- 运输层 OSI中4层
- 网络层 OSI中3层
- 链路层 OSI中2层
- 物理层 OSI中1层
- TCP/IP网络模型/五层网络
- 网络建设：三层网络，二层网络，核心，接入，汇聚
- 数据结构和算法
- 基本数据结构的实现
- 基础排序算法&稳定性
- 算法思想&解题思想
- 数据结构的应用
- 操作系统
- Linux
- 内核
- 系统调用
- 进程&线程
- 调度
- 体系结构
- 程序结构
- 信息表示
- 编译器驱动程序
- ECF 异常控制流
- 虚拟内存
- 多线程编程，并发、并行
- 网络编程
- IO并发
II. 上层应用
- 数据库
- 关系型数据库
- 缓存数据库、对象存储
- 时序数据库
- 分布式
- 分布式系统的横向伸缩
- 分布式基础
- 分布式锁，事务单一处理
- 分布式横向扩展
- 负载均衡、转发代理
- 高可用
- 数据库读写分离
- 消息队列
- rabbitmq
- Kafka
- Redis的消息订阅
- 容器
- Docker基础
- Kubernetes
- 主流云环境监控系统
- open falcon
- prometheus
- 云网络
- 云数据中心网络与SDN
- 云计算
- Cloud Native
- 虚拟化
- Serverlesss
III. 实践能力
IaaS 基础设施研发实践 Python Golang
Linux运维实践
IV. 题目总结
- 算法
- 常见题目
VI. 开源项目代码研究
- CPython
- Redis
- malloc/jemalloc/tcmalloc
VII. 云计算的未来和趋势
- 虚拟化
- 容器再
- serverless
核心内容
I. 计算机基础知识
1. 高级编程语言
C/C++
- C和C++中的指针和引用
- 编译阶段的符号表 * & 取地址符 间接访问符
- C++中的引用和指针的区别
- 指针和引用变成了什么？
- 编译阶段生成符号表，用于链接阶段的重定向
- 引用是C++中的新增特性，其作用是为目标变量起一个别名，通过访问别名可以实现对变量和访问其变量名完全一致的效果；
- 指针 * type 指针类型 * var 间接访问指针指向变量的值 & var 取地址符，对一个变量取地址；
- 指针和引用变成了什么？
- C++中 map 库的红黑树实现
- C标准库malloc函数的实现
- google tcmalloc
- facebook jemalloc
- C中static静态存储类修饰符的作用
- static修饰的全局遍历所分配的内存段
- static修复的局部过程变量所分配的内存段
- 内存管理
- 从低地址到高地址
- 只读内存段 .init .text .rodata格式串和开关语句跳转表
- 读/写内存段 .data .bss (已初始化全局变量、静态变量，未初始化全局变量和静态变量)
- 堆 内存段 由malloc函数调用创建分配
- 共享库的内存映射区域
- 用户栈 运行时创建
- 从低地址到高地址
Golang
- Golang 中的协程
- 协程的上下文切换及管理调度
- 协程堆栈内存段的使用
- Golang垃圾回收机制
Python
- Python协程&协程C底层实现
- python协程 yeild
- 第三方模块 greenlet，gevent的协程实现及原理
Python 基本数据结构的底层实现
CPython CPython源代码分析&虚拟机原理
CPython执行过程的高度概括：
读取和检查py文件，并进行解释器和线程状态的初始化；
解释器
- 解释器状态是一个简单的结构体，结构体中的字段
- *next 引用进程中的另一个解释器状态结构体；
- *tstate_head 引用正在执行的线程状态，多线程下引用全局解释器锁；
- 其余字段有解释器状态所有合作线程共享；
线程
线程结构体包括 next 和 previous 指针，指向该线程之前和之后创建的线程状态；
interp字段指向线程状态所属于的解释器状态
frame字段为当前执行的栈帧
本质：
线程状态只是一个数据结构，封装了正在执行的线程的某些状态；
每个线程都与正在执行的python进程内的操作系统线程关联；
关系
Python进程 单进程 解释器状态 单进程包含一个或者多个解释器状态 线程状态 每个解释器状态包含一个或多个线程状态 操作系统管理的线程（控制流） 每个线程状态的数据结构映射到操作系统的执行线程上 线程状态和OS线程如何映射：OS线程和线程状态在python的threading模块被实例化时创建
所有线程中，同一时间内持有全局解释器锁的线程才能执行虚拟机中的代码对象；
线程由操作系统的线程控制块进行调度和资源分派，但是即使系统调度当前没有持有GIL的线程运行，该线程也必须等待获取GIL；
全局解释器锁GIL：
为了不在虚拟机内实现细颗粒度的各种锁，更明确精细的互斥锁会一定程序降低线程执行效率，简化了虚拟机的实现而存在；
由于引用计数，GIL提供了堆中对象的线程安全，并且CPython链接的部分共享库并非线程安全；
CPython中GIL的实际工作过程：
GIL 只是一个布尔变量（
gil_locked），其访问受到互斥锁（gil_mutex）的保护，并且其更改由条件变量（gil_cond）发出信号。gil_mutex的使用时间很短，因此几乎没有竞争。在 GIL 保持线程中，主循环（PyEval_EvalFrameEx）必须能够根据另一个线程的需要释放 GIL。为此使用了一个临时的布尔变量（gil_drop_request），该变量在每次 eval 循环时都会检查。在gil_cond上等待间隔微秒后，将设置该变量。 【 实际上，使用了另一个临时的布尔变量（eval_breaker），该变量将多个条件进行或运算。由于 Python 仅在高速缓存相关的体系结构上运行，因此，可变布尔值就足以作为线程间信号传递的手段。】这鼓励了定义的周期性切换，但由于操作码可能需要花费任意时间来执行，因此不强制执行。用户可以使用Python APIsys.{get,set}switchinterval()读取和修改时间间隔值。当一个线程释放 GIL 并设置了gil_drop_request时，该线程将确保安排另一个等待 GIL 的线程。它通过等待条件变量（switch_cond）直到gil_last_holder的值更改为其自己的线程状态指针以外的值来进行操作，这表明另一个线程能够使用 GIL。这是为了禁止多核计算机上的延迟潜伏行为，在多核计算机上，一个线程会推测性地释放 GIL，但仍然运行并最终成为第一个重新获取 GIL 的对象，这使得“时间片”比预期的长得多。
将一系列python文件中的代码块进行”编译“，生成虚拟机字节码文件（pyc）
其中CPython有一套自己的指令集，这些指令不同于x86指令集这样的直接面向x86架构的CPU的指令集合，这些指令面对CPython内部实现的指令处理过程，这个过程的集合就可以看作为一个虚拟的”机器（机器是泛指其实就是机器处理单元）“
这些指令和参数共同组成了字节码文件，可以将这个字节码文件称为Python虚拟机上的”经过汇编器汇编后的可重定向目标文件“
- 从python源文件到字节码文件的过程包括
- 生成parse tree
- parse tree转化为AST抽象语法树
- 生成符号表
- AST转化为control flow graph
- 从control flow graph生成code object
- 从python源文件到字节码文件的过程包括
Python每个文件中的程序代码由代码块构成，如模块、函数、类定义，CPython的整个编译过程就是从代码块生成“代码对象的过程”；
代码对象PyCodeObject在CPython中也是一个和PyObject类似也是一个复杂的结构体，结构体中包含co_stacksize，co_flags，co_zombieframe等字段，被初始化的代码对象的结构体被存储在堆中（在PyMem_NEW(type, n)函数中调用PyMem_MALLOC函数在堆中分配内存空间）；
此时，完成了PyCodeObject的创建之后，解释器启动，创建单个执行主线程(在python虚拟机的过程调用中如果创建新的线程和线程状态，就会堆GIL产生竞争)；
堆中的代码对象的引用被传入解释器循环模块，在执行代码之前，解释器获取到当前代码对象后，会创建一个frame对象
- frame 对象包含执行代码对象（局部，全局和内置）所需的所有名称空间，对当前执行线程的引用，用于求值字节码的堆栈以及其他对于执行字节码的内部信息；
- frame对象的概念类似与C中的过程调用无法全部装载到寄存器中的时候，会在运行时栈中修改rsp指针分配栈帧；
- frame对象在运行时栈中创建并保留部分成员的值，保留其他成员的栈空间，局部变量为空；
类似与C的栈中的rip指针执行栈中的指令，Python虚拟机也在栈中进行过程的执行和返回，相应的指令有相应的过程进行处理（如指令：
BUILD_LIST，BUILD_MAP，BUILD_CLASS），每个过程执行完成后，会从栈中弹出；C中的过程：程序开始阶段，运行时栈的rip（程序计数器指针）指针指向入口函数，然后开始执行，例如执行主函数Q的指令，该指令指向主函数内的过程调用的函数P，这是新的函数P在栈中分配了新的栈帧，该栈帧中的过程返回后，rip指针又指向Q中调用P的那条指令，此时这条指令指向P函数的返回值；
在指令执行过程中创建的全局变量等PyObject也会在堆中初始化，每个数据结构的底层实现都有与之对应的C代码，如dict底层是一个使用开放寻址法解决冲突的散列表，并且有特殊的因子进行扩容；
至此，CPython底层虚拟机的运行已经完成了非常简洁的概括式讨论，实际上每个部分的实现都有细节和复杂的思想在其中；
程序的静态和动态存储空间分配：
- 静态：编译器在编译阶段基于源代码就可以确定的数据大小
- 动态：只有在运行时才能确定的数据对象的大小
C语言的编译过程中，对于全局或者静态变量这些在编译阶段确定大小的数据结构或为0值的数据结构，会被放入在编译和汇编完成后生成的可重定向目标文件中的.data节和.bss节，链接器会基于符号表中的重定位条目来将这两个节定位到可执行文件的相应的段中；最总装载程序会将这部分数据装载到该程序虚拟内存的读写段（静态区）；
对于一个被调用的过程，在寄存器无法满足参数存储的情况下，会在运行时栈中分配栈帧；
而对于调用malloc进行内存分配的变量会在运行时在堆中创建；
对于CPython程序而言，无法预知将要读取的python文件中的代码段的数量和大小，怎么才能将这些数据读入栈中；
编译器对栈空间分配的要求是：一个数据对象局限于某个过程，且当过程结束后这个对象不可访问；
C++利用”变长数组“，大小依赖与被调用过程的一个或者多个参数值的数组来将未知大小的对象；
程序的执行过程在生命周期中讨论
dict
list
string
CPython对python对象的内存管理与CPython本身的用户栈
Python的内回收机制，和底层内存管理
Python的动态类型底层实现
Python的GIL与线程安全及IO操作
Python语法基础
- 装饰器
- 单例子实现
__new__, __call__方法
Python主流Web框架的实现
- Tornado
Python调优
Python&CPython核心
- I. 虚拟机工作原理&CPython源代码&工作方式
- II. 内存管理和底层数据结构的实现及数据结构的内存分配、回收、扩容 “heap”
- 优化
- 最小开销的python代码中变量创建和管理
- 优化
- III. 生成器和协程 generator & coroutine
- 生成器对象 generator
Shell编程
- shell内置命令
- shell与内核的系统调用，syscall n指令，Linux中上报中系统调用指令，每个指令有唯一正整数标识，对应一个内核中跳转表的偏移量，跳转表对应一系列系统级函数；
2. 计算机网络 「计算机网络 自顶向下」
- 应用层 OSI中7层
- 运输层 OSI中4层
- 网络层 OSI中3层
- 链路层 OSI中2层
- 链路帧
- 链路层协议
- 物理层 OSI中1层
- TCP/IP网络模型/五层网络
- 协议栈
- TCP
- TCP报文结构
- TCP连接建立
- TCP连接拆除
- TCP segment 数据报交付方式Socket
- 多路分解
- 多路复用
- Linux网路编程Socket多路复用算法
- TCP可靠传输的实现
- 快速重传
- 选择重传
- TCP流量控制
- TCP拥塞控制
- 三个冗余
- 拥塞避免
- 慢启动
- 快速恢复
- 吞吐量/速率
- UDP
- 报文结构
- 无连接
- 无拥塞控制、无流量控制
- 多路复用、多路分解
- 因特网网际协议 IP
- 数据报结构
- IPv6
- IPv4
- IP数据报分片
- v4和v6分片方式
- DHCP
- NAT
- UPnP
- 分组交换机/路由器
- 路由器的基本结构
- 路由选择算法
- 层次路由选择
- 自治系统AS
- BGP
- 广播和多播路由选择
- ICMP 网络控制报文协议
- TCP
- 协议栈
- 网络建设：三层网络，二层网络，核心，接入，汇聚
3. 数据结构和算法 「算法导论&Leetcode训练」
- 基本数据结构的实现
- 数组（C中的数组）
- C++ Java Python 中map/dict 散列表数据结构的实现
- 散列函数
- 除法函数
- 乘法函数
- 哈稀重叠处理
- 链表法
- 开放寻址法
- 散列函数
- 堆
- 堆排序 nlogn
- bitmap数据结构
- 链表
- 树/二叉树
- 二叉树的深度遍历 前 中 后
- 二叉树的广度遍历
- 二叉搜索树
- 图
- 图的深度遍历
- 图的广度遍历
- 矩阵
- 多维数组
基础查找算法&数据结构
- 跳表
- 红黑树
- 二分查找
基础排序算法&稳定性
算法的稳定性：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
对于序列中相同的元素，在排序之后次序与排序之前保持不变；
Sorting algorithm stability
非比较排序
- 桶排序
比较排序
- 简单选择排序
- 基本思想：每一趟从待排序列中选择最小/最大的元素做为首元素，不稳定排序；
- 直接插入
- 选择排序
- 冒泡排序
- 快速排序
- 基本思想
- 基准数元素和其余所有元素做比较，比较完成后，找到自己在有序序列中的位置，这时候比基准小的在左边，比基准元素大的在右边；对基准元素的左右两边分别做相同操作，以此类推，最终得到有序序列；
- 排序的时间复杂度完全取决于基准数的选取，使用“三数取中“的方法，可以一定程度降低基准数对时间复杂的影响；
- 实现方式
- i，j双指针进行比较和交换，指针相遇交换结束，基准元素找到自己的位置；
- 递归对left到i-1，i+1到right做相同操作
- 见Tag: Algorithm
- 分析
- 快速排序为不稳定排序，因为在每次比较和交换过程中，对于大小相同的元素，无法保证其顺序在比较和交换之后还能保持一直，例如有可能会将第一个小的元素交换到中间点；
- 时间复杂度，需要带入”主定理“求解，基准数选取好的情况下，平均时间复杂为O(nlogn)
- 空间复杂度，空间复杂度为O(1)；
- 基本思想
- 堆排序
- 基本思想
- 堆排序是利用堆这种数据结构而设计的一种排序算法，属于一种比较排序，最坏，最好，平均时间复杂度均为O(nlogn)，属于不稳定排序；
- 将待排序序列构造成一个大顶堆，整个序列的最大值就在堆顶的根节点
- 将根节点元素和序列末尾元素交换，末尾就是待排序序列的最大值
- 将剩余的n-1个元素构造成新的堆
- 重复以上步骤，知道无元素在进行堆的构造
- 实现方式
- 大顶堆 arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
- 小顶堆 arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
- 构造堆的过程
- 从最后一个非叶子结点开始，与其左右孩子进行调整，先左右，再上下，此处三个节点中权值最大的结点被升到第一个非叶子结点的位置；
- 按顺序找到第二个非叶子结点，重复第一步
- 按顺序找完所有的非叶子结点，则第一次构造完成；
- 构造完成后，将根节点和最后一个叶子结点交换，再对剩下的元素进行构造；
- 见algorithm-heap
- 分析
- 时间复杂度
- 初始化建堆的过程需要消耗的时间
- O(n)
- 每次交换首位元素后，对堆的重新整理的时间复杂度为 logn，共整理了n-1次，所以整理和交换的时间复杂度为
- O(nlogn)
- 所以最终该算法的最差和平均时间复杂度都为O(nlogn)
- 初始化建堆的过程需要消耗的时间
- 空间复杂度
- 原地算法
- 基于堆的数据结果的排序算法是时间复杂度为 O(nlogn) 的 原址排序算法
- 时间复杂度
- 基本思想
- 归并排序
- 分、治思想
- 简单选择排序
定理
主定理
主定理时间复杂度分析：
T(n)=aT(n/b)+f(n)其中a≥1和b>1是常数，f(n)是渐近正函数。这个递推式将规模为n的问题分解为a个子问题，每个子问题的规模为n/b，a个子问题递归地求解，每个花费时间T(n/b)。函数f(n)包含了问题分解和子问题解合并的代价。
条件 计算式 情况1, 若𝑓(𝑛) < 𝑛𝑙𝑜𝑔𝑏𝑎 则复杂度为 T(n)=O(n ^ {log_b a}); 情况2, 若f(n) = n ^ {log_b a} 则复杂度为T(n)= O(n ^ {log_b a} * lgn); 情况3, 若f(n) > n ^ {log_b a} 则复杂度为T(n)=O(f(n)); 例子，对于快速排序，每次递归都将n的问题分解为了2个子问题，所有a=2，每次合并的问题规模是n/2，函数f(n)包含了问题分解的代价，每次对n个问题的递归分解，都需要n次比较，所以问题分解和合并的代价为n，f(n) = n；将a=2，b=2，f(n)=n，带入公式后得到，T(n) = 2T(n/2) + n，符号情况2，所有由情况2可知，时间复杂度T(n) = O(nlogn);
常见排序算法的稳定性分析
堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。 首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。 其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就 是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。 回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。 (1)冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改 变，所以冒泡排序是一种稳定排序算法。 (2)选择排序 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个 元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么 交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。 (3)插入排序 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳 定的。 (4)快速排序 快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。 (5)归并排序 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个元素(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定 性。那么，在短的有序序列合并的过程中，稳定是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。 (6)基数排序 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优 先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。 (7)希尔排序(shell) 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。 (8)堆排序 我们知道堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。 综上，得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
- 算法思想&解题思想
- 分而治之 分治 divide-conquer
- 线性数组双指针
- 滑动窗口法
- 位运算 异或
- 贪心算法 局部最优解
- 动态规划
- 状态定义
- 状态转移方程
- 边缘条件处理base case
- 递归/迭代
- 二分查找/二分思想
- 数据结构的应用
- 红黑树
- B/B+树 B树就是B-树
4. 操作系统 「现代操作系统&Linux」
Linux
- 进程数据结构的实现
- 文件描述符的管理表
内核
- 内核组件
- 内核维护的数据结构
系统调用
进程&线程
进程
- 核心概念，对当前运行的程序的一个抽象；
- 一个 进程 process 表示当前在执行的一个程序的实例；
- 程序和进程，程序是存放在磁盘上的可执行目标文件，进程是调用fork，和execve函数后装载虚拟内存空间和init执行入口指令开始后的过程的实例；
- 守护进程，后台进程；
- 进程由POSIX标准的system call的接口函数fork创建；
- execve系统调用函数在fork函数之后调用，目的是允许子进程处理其文件描述符，完成对标准输入，标准输出和标准错误的重定向；
- 进程的主动终止，调用 exit system call；
- 进程内部错误导致的异常退出，例如sefamentation fault（栈溢出用户栈的大小ulimit查看默认10mb、指针越界），操作系统向进程发送中断信号；
- kill命令，直接杀死进程；Linux中由父进程创建的子进程和其更多的子进程组成一个进程组，当系统向进程发送信号，进程组中的每个进程都会捕获信号，并执行动作；Unix中所用进程都是以init为根的一棵树；
- 三种状态：
- 运行态
- 就绪态
- 阻塞态
- 运行到就绪，调度算法引起（时间片用完），阻塞到就绪I/O完成进入就绪队列，运行到阻塞I/O等待或者临界区访问等待，就绪到运行调度算法引起；
- 进程的实现
- 内核维护了一个结构数组，叫做进程表process table，每个进程占用一个表项，这就是所谓的进程控制块；
- 表中字段包括，进程管理，程序计数器，寄存器，程序状态字，堆栈指针，优先级，父进程，进程ID,信号，进程开始时间，使用CPU的时间，子进程使用CPU的时间…
- 中断发生的底层操作
- 硬件压入堆栈程序计数器
- 硬件从中断向量装入新的程序计数器
- 汇编语言过程保存寄存器值
- 汇编语言过程设置新的堆栈
- C中断服务例程运行
- 调度程序决定下一个将要运行的进程
- C过程返回至汇编代码
- 汇编语言过程开始运行新的当前进程
线程
- 进程就是一个地址空间和一个控制线程的组合；
- 线程的意义：
- 并行的实体共享同一个地址空间和所有可能的数据；
- 相比进程线程更加的轻量级，线程的创建和上下文切换都要更快；
- 对于I/O密集型的应用，多个线程允许多个活动重叠进行，从而加快了应用程序的执行速度；
- 并发和并行
- 并发是指进程或线程执行的过程或控制流在同一时间段内发生了重叠；
- 并行是指进程或线程在多CPU系统中的同时执行，有完全不同的物理寄存器和程序计数器；
线程 thread 是操作系统内核资源分派和调度的最小单位，是调度算法执行的实体；
每个线程都有自己的 “寄存器”，”用户栈帧“，栈帧保存着当前程序执行的过程的局部变量及返回地址及机器指令；
- 线程没有层次关系，所有线程都是平等的；
- 基本过程调用
- 调用库函数 thread_create 创建线程，创建成功后返回线程标示符；
- 调用库过程 thread_exit 退出线程；
- 调用库过程 thread_join 一个线程会等待另一个线程，知道所等待的线程退出，阻塞才会结束退出；
- 调用过程 thread_yield 自动放弃CPU从而让另一个线程运行；
POSIX
- POSIX，Protable System Interface 是IEEE为各种Unix操作系统上运行的软件定义的API和其关联的标准的总称；
- POSIX定义的线程相关的函数的package是Pthread；定义了60个函数调用；
- Pthread_create 创建新线程
- Pthread_exit 结束一个线程
- Pthread_join 等待一个特定的线程退出
- Pthread_yield 主动释放当前分配的CPU时间片，内核会调度新的线程运行
- Pthread_attr_init 创建并初始化一个线程的属性结构
- Pthread_attr_destory 删除一个线程的属性结构
- Pthread特性
- 一个标示符 调用Pthread_create函数返回 起到PID的作用
- 一组寄存器和程序计数器
- 一组存储在结构中的属性，堆栈大小，调度参数，使用线程需要的其他项目
用户空间实现线程，操作系统内核对线程的存在没有任何感知，内核对进程的调度，可以理解为，内核只调度单线程进程；用户空间的内的运行时系统来对线程进程管理，且运行时系统中会管理线程表（thread table），线程的调度实现在运行时系统中，运行时系统的过程进行线程的上下文切换，比内核级别的线程上下文切换要快一个数量级；这个过程不需要陷阱（如系统调用），不需要内核控制的上下文切换，不需要对高速缓存进行刷新；并且允许每个进程中有自己实现的调度算法；
- 内核级线程，所有的调度都发生在内核的调度中；
竞争 （互斥 mutual exclusion）mutex
- 临界区
- 共享内存进行访问的程序片段为临界区域（critical region），或临界区（critical section）
- 用于解决多个进程竞争访问共享资源：共享内存、共享文件
- 并发进程共享数据且高效运行，对临界区访问的必须条件
- 任何两个进程不能同时处于临界区
- 不对CPU的速度和数量做任何限制
- 临界区外运行的进程不得阻塞其他进程（由于其他进程导致进程阻塞，只能是因为阻塞等待访问临界区）
- 进程不能无限期的进入临界区
- 共享内存进行访问的程序片段为临界区域（critical region），或临界区（critical section）
- 临界区
调度
操作系统的 调度程序 scheduler 进行对当前多个处就绪状态的线程或者进程选择谁去运行当前的时间分片；
调度程序 scheduler 使用的算法是 调度算法 scheduling algorithm
进程的切换会消耗大量的CPU时间
- 用户态切换到内核态，将当前进程的状态及程序计数器保存到当前进程的数据结构中（表）
- 运行调度算法选择一个新的进程
- 将新进程的内存映像装入MMU （Memory management Unit）
- 进程的切换会使得高速缓存失效，缓存需要重装两次，进入内核一次，离开内核一次
I/O活动
- 当一个进程等待外部设备完成工作而被“阻塞”
- 当前进程发出一个系统调用进行I/O的读写
- CPU的突发使用和等待I/O的时期交替出现
compute-bound
- CPU密集型进程，长的CPU突发，较少的等待I/O
I/O-bound
- I/O密集型，短的CPU突发，较多发生的I/O等待
- CPU性能的增长，大多数应用倾向于I/O密集型，CPU密集型例如特效渲染等，建模大量浮点运算等；
调度的简单归纳
- 对于创建的新进程，策略为合法选择先运行父进程或者先运行子进程
- 进程退出，从就绪进程集中选择某个进程，没有就绪进程则运行一个系统提供的空闲进程
- 当一个进程阻塞在I/O和信号量上或者其他原因阻塞，必须选择另一个进程；
- 进程发生I/O中断时，系统必须作出调度决策，对于完成了I/O工作的进程，又会进入就绪状态，对于这个进程的调度，取决与调度算法；
调度算法的分类
- 时钟中断，调度策略发生在每个时钟中断或者每k个时钟中断（硬件提供50HZ或者60HZ的周期性中断）
- 非抢占式调度算法
- 挑选一个进程，让该进程运行直至被阻塞（I/O或临界区等待），或者直到该进程自动释放CPU；在这种算法下，进程运行了数个小时没有发生I/O或者阻塞，都不会被强制挂起；
- 抢占式调度算法
- 挑选一个进程，让该进程运行某个固定时段最大值（最大运行时间片），时段结束，关起进程，在调度下一个就绪进程运行；
- 抢占式的调度算法，需要在时间间隔的末端发生时钟中断，用来将CPU控制返回给调度程序（程序计数器）；
- 在没有可用的时钟的条件下，非抢占式的调度式唯一的选择；
不同的领域和环境需要不同的调度算法
- 批处理：非抢占式调度算法，或者每个进程都有长时间周期的抢占式；
- 交互式环境&服务器：抢占式调度算法，避免程序无限期的霸占CPU；
- 实时系统：非抢占式，程序很快完成工作并进入阻塞；
调度算法的目标
- 所有系统
- 公平 - 每个进程公平的CPU时间片
- 策略强制执行
- 平衡 - 保持系统所有部分都忙碌
- 批处理系统
- 吞吐量 - 每小时最大作业数
- 周转时间 - 从提交到终止间的最小时间
- CPU利用率 - 保持CPU忙碌
- 交互式系统
- 响应时间 - 快速响应请求
- 均衡性 - 满足用户的期望
- 实时系统
- 满足截至时间 - 避免丢失数据
- 可预测性 - 在多媒体系统中避免品质降低
- 必须保障
- 强制执行公平相关的体系策略
- 保持系统的所有部分尽可能忙碌
- 所有系统
调度算法
非抢占式的 先到先服务 first-come first-serverd
- 进程按照请求CPU的顺序使用CPU
- 就绪进程的单一队列，新的进程和发生阻塞的进程再次处于就绪状态都将更新到队列尾部；
非抢占式的 最短作业优先 shortest job first
- 对于同时进入就绪队列的进程，从 运行时间 最短的进程依次执行，总体上所有进程的周转时间（执行时间+阻塞时间）的平均值最小；
非抢占式的 最短剩余时间优先 shortest remaining time next
- 总是选择运行时间最短的进程运行；
抢占式 轮转调度 round robin
古老、最简单、最公平、使用最广的算法
- 每个进程被分配一个时间片（quantum），允许该进程在该时间段中运行；
- 时间片结束后，程序依然没有发生阻塞而在继续运行，算法将剥夺CPU并分配给其他进程；
- 如果在时间片之内，程序发生了I/O阻塞或者访问临界区阻塞，则直接发生CPU切换；
- 保持一个就绪队列，当一个进程的时间片用完就将其移动到队列尾部；
- 进程的控制切换（context switch）开销非常大，保存当前寄存器、内存映像、重载内核映像、清除和重新子啊如高速缓存，载入新进程的内核映像…
- 时间片取值，太短降低CPU效率，太长引起响应时间变长，折中为20ms~50ms
优先级调度
- 操作系统动态的确定进程的优先级；操作系统将进程的优先级分为4类，并使用轮转调度；
- 调度算法实现
- 轮转算法将给第4类优先级进程分配时间片，并云子能够；
- 第4类为空的情况下，轮转第3类；
- 依次类推；
- 并且系统会定期对进程的优先级进行调整；
多级队列
最短进程优先
保证调度
彩票调度
公平分享调度
调度策略与调度机制分离（scheduling policy & scheduling mechanism)
- 算法参数化，由用户进程填写；
线程调度
- 进程和线程并存的系统中的调度
- 用户级线程
- 没有内核级别的线程，内核不知道线程的存在，内核还是对进程进行基于时间片的轮转调度，而线程的调度由进程内部自己实现，进程内一个或多个线程运行完当前的时间片之后，内核会将控制转移给队列首部的进程；
- 缺少时钟周期对线程进行中断；
- 内核级线程
- 操作系统内核以线程为最小调度单位，用轮转调度和优先级调度算法对线程分配时间片，并在时间片完成后，挂起该线程，在运行其他线程；
- 对于线程的I/O阻塞，同样可以将线程挂起，调度运行其他线程；
- 线程调度的比较
- 用户级线程调度发生在用户程序内部，开销更小，速度更快；
- 用户级线程，可以让应用程序定制自己的线程调度算法；
- 内核级线程调度，需要用户态和内核态的切换，开销更大，上下文切换时间更长；
- 操作系统在线程调度时候，更加倾向与调度运行上下文切换开销较小的线程，例如同一个进程中的多个线程，在运行线程阻塞的情况下，内核更加倾向于调度执行该进程中的其他线程而不是其他进程中的线程；
软中断&硬中断
5. 体系结构 「CSAPP-深入理解计算机系统」
程序结构
- CPU寄存器和系统字长
- 信息表示
- 补码表示
- 浮点数的表示
- Intel指令集架构
- y86指令集
- 复杂指令集、精简指令集
- 编译器驱动程序
- 预处理
- 编译
- 汇编
- 链接
ECF 异常控制流
控制流
- 程序计数器中指令地址的过度称为控制转移 control transfer
- 程序计数器指令地址的过度的序列为处理器的控制流（control flow）
- 平滑的控制流序列，其中每个指令的地址都是相邻的；
- 平滑流的突变，通常由跳转， 调用、返回等指令造成
- 控制流突变
- 异常控制流 Exceptional Control Flow ECF
- 发生在计算机系统的各个层次
- 硬件事件触发控制突然转移到异常处理程序
- 内核通过上下文切换将控制从一个用户进程转移到另一个用户进程
- 应用层，进程之间使用信号通信，接受者会将控制转移到信号处理程序；
- 程序通过回避通常的栈规则，执行到其他函数任意位置的非本地跳转来对错误作出反应；
- ECF
- ECF是OS用来实现I/O，进程、虚拟内存的基本机制；
- 应用程序使用系统调用 （system call）的ECF形式，向系统请求服务；
- 磁盘写入数据
- 网络读取数据
- 创建新进程
- 终止当前进程
- 通过系统调用实现
- ECF是计算机系统实现并发的基本机制；
- 中断应用程序执行的异常处理程序
- 时间上重叠执行的进程和线程
- 中断应用程序执行的信号处理程序；
- ECF软件异常
- C++ try catch throw
- 软件异常允许程序进行非本地跳转，来响应错误；
- 非本地跳转是一种应用层ECF，C中通过setjmp和longjmp函数提供
- 各种形式的ECF
过程
用户栈 - 参数 返回地址 被保存的寄存器 局部变量 参数构造区 <-%rsp 过程是一种软件中的抽象，提供一种封装代码的方式，用一组指定的参数和一个可选的返回值来实现某种功能
过程的属性包括
- 传递控制
- 程序开始阶段，运行时栈的rip（程序计数器指针）指针指向入口函数，然后开始执行，例如执行主函数Q的指令，该指令指向主函数内的过程调用的函数P，这是新的函数P在栈中分配了新的栈帧，该栈帧中的过程返回后，rip指针又指向Q中调用P的那条指令，此时这条指令指向P函数的返回值；
- 传递数据
- 分配和释放内存
- 传递控制
使用栈数据结构的提供的先进后出的内存管理原则
过程在被调用时候，才会在栈中为局部变量分配空间，而过程结束后分配的局部存储空间都会被释放掉；
栈和程序寄存器存放着传递控制和数据、分配内存所需要的信息；
X86_64 栈向底地址增长，栈指针%rsp指向栈顶元素，pushq指令入栈，popq指令出栈，将指针减小一个适当的量可以为没有指定初始值的数据在栈上分配空间 （指针偏移量，变长数组），增加栈指针来释放空间
栈帧 （stack frame）
X86_64 过程所需要的存储空间超出寄存器能够存放的大小，就会在栈上分配空间
栈通过增加和减小%rsp的大小来释放空间和分配栈帧；
当前正在执行的过程的栈总是在栈顶
定长栈帧
变长栈帧
栈帧的实质就是过程因为所需要的寄存器空间不足而在栈顶分配的新的内存空间；内存中一个过程所包含的过程调用和数据及返回；
- 6个或者更少的参数可以直接通过寄存器传递 （6个参数：可以通过寄存器最多传递6个参数，例如整数和指针参数，寄存器只用有特殊的顺序，名字取决于传递的参数的大小）
- 叶子过程：所有局部变量都保存在寄存器中，而且不会调用其他函数的过程
- X86_64 只分配自己所需要的栈帧部分
异常
- 事件发生 – 处理器通过异常表 exception table 跳转表，进行一个间接的过程调用 – 异常处理程序 exception handler – 处理完成后
- 处理程序将控制返回给当前指令，事件发生时正在执行的指令
- 处理程序将控制返回给当前指令的下一条指令，没有发生异常就会执行下一条指令
- 处理程序终止被中断的程序
- 事件发生 – 处理器通过异常表 exception table 跳转表，进行一个间接的过程调用 – 异常处理程序 exception handler – 处理完成后
陷阱
- 有意的异常，执行一条指令的结果，像中断处理程序一样；
- 用途
- 用户程序和内核之间提供一个像过程一样的接口，系统调用
- 用户程序向系统内核请求服务：
- read
- fork （创建新进程）
- execve
- exit
- 为了允许对内核服务的受控的访问，处理器提供一条特殊的“syscall n”指令；
- 用户程序想要请求服务n时，执行指令 syscall n，就会导致一个异常处理程序的陷阱；
- 这个处理程序解析参数，并调用适当的内核程序；
- 用途
- 有意的异常，执行一条指令的结果，像中断处理程序一样；
虚拟内存
多线程编程
网络编程
磁盘读写
I/O
Linux I/O模式
在 select/poll中，进程只有在调用一定的方法后，内核才对所有监视的文件描述符进行扫描，而epoll事先通过epoll_ctl()来注册一 个文件描述符，一旦基于某个文件描述符就绪时，内核会采用类似callback的回调机制，迅速激活这个文件描述符，当进程调用epoll_wait() 时便得到通知。(
此处去掉了遍历文件描述符，而是通过监听回调的的机制。这正是epoll的魅力所在。)epoll的优点主要是一下几个方面：
- 监视的描述符数量不受限制，它所支持的FD上限是最大可以打开文件的数目，这个数字一般远大于2048,举个例子,在1GB内存的机器上大约是10万左 右，具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。select的最大缺点就是进程打开的fd是有数量限制的。这对 于连接数量比较大的服务器来说根本不能满足。虽然也可以选择多进程的解决方案( Apache就是这样实现的)，不过虽然linux上面创建进程的代价比较小，但仍旧是不可忽视的，加上进程间数据同步远比不上线程间同步的高效，所以也不是一种完美的方案。
- IO的效率不会随着监视fd的数量的增长而下降。epoll不同于select和poll轮询的方式，而是通过每个fd定义的回调函数来实现的。只有就绪的fd才会执行回调函数。
- 如果没有大量的idle -connection或者dead-connection，epoll的效率并不会比select/poll高很多，但是当遇到大量的idle- connection，就会发现epoll的效率大大高于select/poll。
II. 上层应用
数据库
- 关系型数据库
- 索引实现
- B+tree Mysql的两种可选索引引擎的异同
- 数据库并发和锁
- 索引实现
- 缓存数据库
- redis
- 时序数据库
- M3DB/InfluxDB
- etcd
分布式系统
- 什么是分布式
- 分布式基础
- zookeeper
- redis
- 分布式锁，事务单一处理
- 分布式横向扩展
- 负载均衡、转发代理
- 高可用
数据库读写分离
- 容器
- Docker基础
- Docker隔离的基本原理和机制
- Docker swarm
- Docker compose 配置管理标准
- Kubernetes
- serverless架构中Kubernetes的角色
- 基本组件和使用
- Docker基础
主流云环境监控系统
- open falcon
- prometheus
云网络
- LVS
- Nginx
- iptable
- NFV
- SDN
云计算
- Cloud Native
- 虚拟化
- hypervisor
- KVM
- Openstack
- Quem
- Serverlesss
III. 实践能力
IaaS 基础设施研发实践 Python Golang
Linux运维实践
IV. 题目总结
算法
八皇后问题，火车接龙， 高考分数线，5人抢答题概率，丢手绢问题
常见题目
- 基本排序算法的实现思路和时间空间复杂度
- 快速排序，经典的比较排序，基准数与其他逐个比较，找到自己在序列中的位置，二分对两边做同样地操作，基准数选择至关重要，可以用三数取中法；
- 时间复杂度，带入“主定理”求解，为nlogn
- 快速排序，经典的比较排序，基准数与其他逐个比较，找到自己在序列中的位置，二分对两边做同样地操作，基准数选择至关重要，可以用三数取中法；
个人题目总结
1. 算法与数据结构
树形结构的同步
A和B两台计算机，分别跑着同一个程序m，A和B用一根网线相连接，现在A中有一个树形数据结构，有根节点也子节点，且这些子节点都保存着一个二进制数小于256位的二进制数，但是每个节点的子节点最大数量为2^10 256个，且树的深度可能很大，要求描述一个算法将A上的树备份到B上，不能使用json等序列化方式，设计一个算法，实现这个数据传输；
Merkle Tree（默克尔树）算法解析
不能离开数据结构谈算法，实际的生产应用中，数据结构和算法应该是怎么样去实践的
分析
- 网线连接，首先说明AB的链路时直接相连中间没有任何分组交换，直接使用socket接口，先在单线程内解决该问题，再思考用socket线程池进行同步，数据的一致性要求，选择TCP
- 树形结构，树的深度为n，对于此数据的同步需要进行实时同步，不能一次性同步
方案
哈希表的原理及实现方式，扩容、冲突解决
将n个有序数组进行合并
- 堆排序 nklogk
- 归并排序，分治 nklogk
链表，在算法训练中有讨论，下面两题属于非常简单的题型
- 链表反转，递归反转
- 检测链表成环，快慢指针
2. 并发编程
多线程编程
A线程 ————C1————-C2————– B线程 ——————–C3———————
分析
- 对于这样的两个线程，要求实现 C1 C3 C2 的执行顺序 重点：线程的执行顺序和代码顺序无关，线程也不是同时执行的，线程是由操作系统内核的调度算法进行调度执行的；
Solution
单CPU的并发
维护两个堆中的全局变量的布尔值为 did_e_c1, did_e_c3
创建一个互斥锁
实现
- 对于两个布尔值的修改，使用一个互斥锁，保证线程安全；
- 此处可以不使用yeild函数，但是会浪费调度算法分配的时间片；
- A线程中实现三个过程（两个控制流）
- 第一个控制流判断两个布尔值是否都为 False，如果符合条件则执行C1，并将did_e_c1置为True，不符合条件则当前帧出栈也就是继续执行
- 控制流继续执行，判断是否当前两个布尔值都为 True，如果符合条件就继续执行，如果不符号条件，则调用 Pthread_yeild 过程主动让出当前线程的时间片，此处的判断条件可以使用while循环；
- 第三个控制流直接执行代码块C2，执行完成后将did_e_c1, did_e_c3都置为False
- B线程中实现两个过程
- 第一个过程判断当前是否符合 did_e_c1 == True, did_e_c3 == False；如果符合则直接运行过程C3，如果不符合则Pthread_yeild 过程主动让出当前线程的时间片，此处的判断条件可以使用while循环；
- 执行完成后将did_e_c3置为True
数据库更新A记录和B记录的加锁和死锁问题
数据库，数据库更新A记录和B记录的加锁和死锁问题，表中管理账户信息，A账户给B账户转账，更新A和B，考虑行锁和死锁出现的解决
KMP算法，搜索单词数量；
磁盘存取原理
3. 网络
- 链路层
- TCP连接拆除的过程，三次握手，四次分手，为什么是三次，和TCP配置相关的linux参数；
- TCP 连接拆除 大量TIME_WAIT问题，TIME_WAIT分析和解决方案；
- 网络工程
4. 操作系统
基础问题
cpu 占用率到底代表什么，linuxload代表什么，linux中各种内存又代表了什么，linux的网络是如何工作的
5. 其他问题
2019年4月16日 记录
时序数据库底层的实现 时序数据库和关系型数据库的区别
协程到底是什么，协程如何“并发”，io密集型，GIL如何避免
并发&并行 python的并发 并行的概念是 multiprocessing 如何实现并行
KVM QUEM Openstack
自动化的横向扩展
rabbitmq和Kafka
长短链接
跳表
tcp tw socket recycle reuse 底层实现 / tcp 为什么三次 为什么四次
malloc tcmalloc jemalloc
长短连接的保持，应用层协议探查连接状态
内核 及 内核组件 模块 操作系统
socket在内核中保持的table
微服务 容错 容灾 远程调用方案 追踪
异常 控制流 中断 陷阱 系统调用
socket 底层原理 linux 内核部分
时序 数据库和关系型 数据库 对象存储 redis
4月19日
线程 进程 切换/控制转移/时间片 操作系统
数据结构 跳表
查找算法，查找算法的时间复杂度，查找算法的稳定性如何衡量
小白鼠问题
调试 循环引用
redis 中间件
问什么回答什么，加快节奏，总是打断？
集中式/分布式
epoll poll select 区别是什么
V. 2020年2、3、4月学习复习总结
VI. 开源项目代码研究
- CPython
- Redis
- malloc/jemalloc/tcmalloc
VII. 云计算的未来和趋势
- 云计算从虚拟化到容器再到现在的serverless的发展趋势， 我个人理解云计算的未来在客户的层面来讲是要看到产品的使用更加简单、开发成本更低，用户编写测试完核心业务代码或者函数，剩下的自动化部署、高可用、快速伸缩、负载均衡这些都扔给服务的provider去做，这也是现在FaaS的概念，这样的serverless架构就要求云服务的提供者有一套完善的容器编排和调度策略，及准确的流量和数据监控系统，保证快速的横向伸缩和计费的准确，例如像AWS的lambda，我看到的统计资料全球有30%的企业都有使用AWS的lamdba服务；所以serverless是一个大的发展趋势；
- 从宏观上来讲，云计算的未来是网络和数据的未来，我们需要更加安全和可靠的网络去承载新的业务，像IOT和车联网，也需要准确的，也需要更可靠的分布式的数据存储系统去承载更多业务类型的数据；
VII. 其他
Intro
项目背景和挑战
亮点及成果
个人规划
自我提问
简历问题：
- 数据库优化具体是指什么
- Linux的基本操作
- Docker原理
- LXC RabbitMQ 原理
- 基本的网络知识，协议在哪一层
TCP的状态都有哪些
数据库优化： 数据库优化的问题，我来举两个例子吧：
- redis替代率全表查询到服务缓存问题 例如redis这样的非关系数据库和关系库的区别
- 数据持久化方式：redis是一个内存数据库，对于我们实时访问的数据都是直接存储在内存中以k-v方式存储，很大程度上提高了读写效率，redis会将更新的数据周期性的同步到磁盘中，并且进行master slave的同步；而关系型数据数据还是索引都存放在硬盘中。到要使用的时候才交换到内存中。能够处理远超过内存总量的数据。
- 存储方式：关系型数据库可以存储多种不同的表关系，而且每个表都有自己的行和列，主键外键、索引等； Redis的外围由一个键、值映射的字典构成。与其他非关系型数据库主要不同在于：Redis中值的类型 [1] 不仅限于字符串，还支持如下抽象数据类型： 字符串列表 无序不重复的字符串集合 有序不重复的字符串集合 键、值都为字符串的哈希表 [1]
- 查询方式：redis以k-v形式查询和存储，而且传统的关系型数据库提供了一整套的SQL语句进行各种查询和读写；
- 增加了索引，对数据量基本确定的表增加了btree的索引，对数据量较大的数据库增加了Brin索引，为什么，分别是什么
RIN索引和BTREE索引相比，在存储空间占用上具备巨大优势。本例中达到6848倍！对于数据仓库或者VLDB应用可以节省大量的存储成本。 本文给出并分析了7中不同的数据分布，在等值查询情况下，所有的场景BTREE的性能都优于BRIN索引。但在不同数据分布情况下，BTREE在性能上的领先优势差别非常大，从不到1倍到265倍。在选择创建BRIN还是BTREE索引时，需要权衡性能和空间使用两方面的影响。根据数据量、数据分布和SQL选择最适合的索引类型。在性能相差不大的情况下，选择BRIN可能是更加经济的选择。总体来说，当实际匹配数据量较少时，BTREE索引更加适合；反之，BRIN更加适合。
- BRIN 索引（块范围索引，Block Range Indexes）
该索引维护每一定范围内数据块的最大最小值和其他一些统计数据，当数据库查询时可根据索引的统计信息筛选出不符合查询条件的数据块，以避免全表扫描，提高性能和减少 IO。和 BTree 索引比较所占用的空间足够小[1]，因此 BRIN 索引一般用于线性相关较强字段的精确和范围查询，如在一张很大的日志表中通过 id 或时间查询。 BRIN 索引页的存储顺序依次是 meta page、revmap pages 和 regular pages
- B-TREE btree是一个多路的树形结构，内存节点不存储data，只存储key；叶子节点不存储指针,叶子节点存储数据，在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree，这个优化的目的是为了提高区间访问的性能。
检索原理：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或未找到节点返回null指针。 缺点：1.插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。造成IO操作频繁。2.区间查找可能需要返回上层节点重复遍历，IO操作繁琐。
B-tree和二叉树的一个显著的区别就是，B-tree是从下往上生长，而二叉树是从上往下生长的。
增加了查询函数和view视图，view视图的主要作用是减小前后端工作量，将较为复杂的SQL查询直接放在可视化的视图上，前端通过中间件直接获取数据；例如
查询函数的优化，主要是以rpc的方式更新数据库中比较固定的字段； 使用了pg函数的方式，将统一的数据访问方式全都放在了中间件上；
agent心跳逻辑的更新 旧逻辑：
每个agent自己通过中间件连接数据库，调用rpc函数，更新它当前所要监控的设备上的update_timestamp和region上的update_time字段为最新时间； 一共440个agent每分钟都在调用rpc函数，导致了严重的对锁的竞争，因为pg会为操作自动加上行锁也就是rowexclusivelock，又因为大量进程的同时修改，导致了两个进程会互相等待对方释放锁，从而导致了死锁；
完成重构了agent的更新的逻辑，每个agent在表agent_heartbeat中有一条单独的记录，agent还是每分钟更新update_time, 新的agent distribution的服务会将每分钟检查是否有agent down掉，如果有则将设备表中agent的分配update为null，并且将这些无人认领的设备平均分配给其他活着的agent
这里将多个服务的大量写入更新操作放在了一个服务统一进行； 将rpc函数更新为了简单的agent心跳更新；将原来数据库端的rpc压力降低了；
主键 外键 主键是一张表里的一个unique的字段，该字段的记录在表中只有一个 外键，是用来约束两张表之间数据关系的，外键的参考键必须是库中其他表的主键或者说必须是uniqe的，外键关联的字段可以是本表的任意字段 表1设置了表2的id和自己的id为外键，表1如果新增数据时，表2中必须已经包含了该数据，表2删除数据时，所删除的ID不能存在于表1中；
- 给数据量较大的表，比如3000条数据的表，加入了btree的索引
- metric_event表的并发BRIN 索引
- 配置一个表的外键，需要选取参考模式参考表和参考值，
Linux Load Average: 1min 5min 15min 一个逻辑核心的Load为1.0，表示当前n分钟的时间内，CPU核心一直处于工作状态, 当小于1.0的情况下例如0.7，表示CPU在n分钟内有0.3n分钟的时间内是idle的状态；如果为1.3的情况下，表示CPU在n分钟内一直处于工作状态，且有进程处于阻塞等待调度和执行的时间为0.3n分钟； n个逻辑核心的load average为n.0 将CPU的逻辑核心数*0.7 到0.8 就是最好的运行状态
Linux的堆和栈 内存从高地址到底地址分为 栈区 剩余内存区 bss段 data段 text段 text段存放代码，data段和bss段存放全局变量和静态变量 data存已经初始化的 bss存未初始化的 栈的作用就是在寄存器紧张的情况下，临时存放一些数据，push和pop的方式进行访问，当寄存器空闲的情况下，栈中的数据会被pop出来以供使用，比如存放局部变量，函数参数和上下文环境这些临时数据，栈的顶部是向底内存方向增加的，栈顶由ESP堆栈指针寄存器来标记；
Linux中的内存
所谓的malloc和free进行分配和释放的内存区域为中间的剩余内存段，也就是常说的堆；
首先，栈是一个后进先出(LIFO)结构。当把数据放入栈时，我们把数据push进入；当从栈取出数据时，我们把数据pop出来。 在x86体系中，栈顶由堆栈指针寄存器ESP来标记，它是一个32位寄存器，里面存放着最后一个压入栈顶的项的内存地址，栈顶是朝着底内存方向增长的。 栈经常可以用来在寄存器紧张的情况下，临时存储一些数据，并且十分安全。当寄存器空闲后，我们可以从栈中弹出该数据，供寄存器使用。这种临时存放数据的特性，使得它经常用来存储局部变量，函数参数，上下文环境等。
堆相对于栈，更加强调需要进行控制。常见的就是我们手动申请，手动释放。因此可以分配更大的空间，但开销也会更多。
数据格式： { “endpoint”: “metric”: “timestamp”: “step”: “value”: “counterType”: “tags”: }
TCP/IP协议 OSI 应用层 表示层 会话层 传输层 TCP协议族 网络层 IP协议 + Internet协议 IP包：[] 数据链路层 物理层
Linux中TCP状态：
SYN:(同步序列编号,Synchronize Sequence Numbers)该标志仅在三次握手建立TCP连接时有效。表示一个新的TCP连接请求。
ACK:(确认编号,Acknowledgement Number)是对TCP请求的确认标志,同时提示对端系统已经成功接收所有数据。
FIN:(结束标志,FINish)用来结束一个TCP回话.但对应端口仍处于开放状态,准备接收后续数据。
1)、LISTEN:首先服务端需要打开一个socket进行监听，状态为LISTEN. The socket is listening for incoming connections. 侦听来自远方TCP端口的连接请求
2)、SYN_SENT:客户端通过应用程序调用connect进行active open.于是客户端tcp发送一个SYN以请求建立一个连接.之后状态置为SYN_SENT. The socket is actively attempting to establish a connection. 在发送连接请求后等待匹配的连接请求
3)、SYN_RECV:服务端应发出ACK确认客户端的SYN,同时自己向客户端发送一个SYN. 之后状态置为SYN_RECV A connection request has been received from the network. 在收到和发送一个连接请求后等待对连接请求的确认
4)、ESTABLISHED: 代表一个打开的连接，双方可以进行或已经在数据交互了。 The socket has an established connection. 代表一个打开的连接，数据可以传送给用户
5)、FIN_WAIT1:主动关闭(active close)端应用程序调用close，于是其TCP发出FIN请求主动关闭连接，之后进入FIN_WAIT1状态. The socket is closed, and the connection is shutting down. 等待远程TCP的连接中断请求，或先前的连接中断请求的确认
6)、CLOSE_WAIT:被动关闭(passive close)端TCP接到FIN后，就发出ACK以回应FIN请求(它的接收也作为文件结束符传递给上层应用程序),并进入CLOSE_WAIT. The remote end has shut down, waiting for the socket to close. 等待从本地用户发来的连接中断请求
7)、FIN_WAIT2:主动关闭端接到ACK后，就进入了FIN-WAIT-2 . Connection is closed, and the socket is waiting for a shutdown from the remote end. 从远程TCP等待连接中断请求
8) 、LAST_ACK:被动关闭端一段时间后，接收到文件结束符的应用程序将调用CLOSE关闭连接。这导致它的TCP也发送一个 FIN,等待对方的ACK.就进入了LAST-ACK . The remote end has shut down, and the socket is closed. Waiting for acknowledgement. 等待原来发向远程TCP的连接中断请求的确认
9)、TIME_WAIT:在主动关闭端接收到FIN后，TCP就发送ACK包，并进入TIME-WAIT状态。 The socket is waiting after close to handle packets still in the network.等待足够的时间以确保远程TCP接收到连接中断请求的确认
10)、CLOSING: 比较少见. Both sockets are shut down but we still don’t have all our data sent. 等待远程TCP对连接中断的确认
11)、CLOSED: 被动关闭端在接受到ACK包后，就进入了closed的状态。连接结束. The socket is not being used. 没有任何连接状态
TIME_WAIT状态的形成只发生在主动关闭连接的一方。
主动关闭方在接收到被动关闭方的FIN请求后，发送成功给对方一个ACK后,将自己的状态由FIN_WAIT2修改为TIME_WAIT，而必须再等2倍的MSL(Maximum Segment Lifetime,MSL是一个数据报在internetwork中能存在的时间)时间之后双方才能把状态 都改为CLOSED以关闭连接。目前RHEL里保持TIME_WAIT状态的时间为60秒。
当然上述很多TCP状态在系统里都有对应的解释或设置,可见man tcp
二、关于长连接和短连接:
通俗点讲:短连接就是一次TCP请求得到结果后,连接马上结束.而长连接并不马上断开,而一直保持着,直到长连接TIMEOUT(具体程序都有相关参数说明).长连接可以避免不断的进行TCP三次握手和四次挥手.
长连接(keepalive)是需要靠双方不断的发送探测包来维持的,keepalive期间服务端和客户端的TCP连接状态是ESTABLISHED.目前http 1.1版本里默认都是keepalive(1.0版本默认是不keepalive的)，ie6/7/8和firefox都默认用的是http 1.1版本了(如何查看当前浏览器用的是哪个版本，这里不再赘述)。Apache,java
一个应用至于到底是该使用短连接还是长连接，应该视具体情况而定。一般的应用应该使用长连接。
TCP 主动端-被动端
主机1发送完自己要发送的所有数据，决定断开连接 主机1使用close发送fin|ack（附带对主机2前面数据的ack），断开连接的过程开始，此时主机1的发送窗口关闭，接受窗口还在工作； 主机2接受到主机1的fin后，发送ack告知主机1对方的fin已收到； 主机2继续发送数据，直到主机2发送完所有数据 主机2使用close发送fin，表示自己的数据也发送完毕 主机1接受fin，发送ack，告知主机2对方的fin已收到
time-wait开始的时间为tcp四次挥手中主动关闭连接方发送完最后一次挥手，也就是ACK=1的信号结束后，主动关闭连接方所处的状态。
然后time-wait的的持续时间为2MSL. MSL是Maximum Segment Lifetime,译为“报文最大生存时间”，可为30s，1min或2min。2msl就是2倍的这个时间。工程上为2min，2msl就是4min。但一般根据实际的网络情况进行确定。
然后，为什么要持续这么长的时间呢？
原因1：为了保证客户端发送的最后一个ack报文段能够到达服务器。因为这最后一个ack确认包可能会丢失，然后服务器就会超时重传第三次挥手的fin信息报，然后客户端再重传一次第四次挥手的ack报文。如果没有这2msl，客户端发送完最后一个ack数据报后直接关闭连接，那么就接收不到服务器超时重传的fin信息报(此处应该是客户端收到一个非法的报文段，而返回一个RST的数据报，表明拒绝此次通信，然后双方就产生异常，而不是收不到。)，那么服务器就不能按正常步骤进入close状态。那么就会耗费服务器的资源。当网络中存在大量的timewait状态，那么服务器的压力可想而知。
原因2：在第四次挥手后，经过2msl的时间足以让本次连接产生的所有报文段都从网络中消失，这样下一次新的连接中就肯定不会出现旧连接的报文段了。也就是防止我们上一篇文章 为什么tcp是三次握手而不是两次握手？ 中说的：已经失效的连接请求报文段出现在本次连接中。如果没有的话就可能这样：这次连接一挥手完马上就结束了，没有timewait。这次连接中有个迷失在网络中的syn包，然后下次连接又马上开始，下个连接发送syn包，迷失的syn包忽然又到达了对面，所以对面可能同时收到或者不同时间收到请求连接的syn包，然后就出现问题了。
产生原因 通过图上，我们来分析，什么情况下，连接处于CLOSE_WAIT状态呢？ 在被动关闭连接情况下，在已经接收到FIN，但是还没有发送自己的FIN的时刻，连接处于CLOSE_WAIT状态。 通常来讲，CLOSE_WAIT状态的持续时间应该很短，正如SYN_RCVD状态。但是在一些特殊情况下，就会出现连接长时间处于CLOSE_WAIT状态的情况。
出现大量close_wait的现象，主要原因是某种情况下对方关闭了socket链接，但是我方忙与读或者写，没有关闭连接。代码需要判断socket，一旦读到0，断开连接，read返回负，检查一下errno，如果不是AGAIN，就断开连接。
参考资料4中描述，通过发送SYN-FIN报文来达到产生CLOSE_WAIT状态连接，没有进行具体实验。不过个人认为协议栈会丢弃这种非法报文，感兴趣的同学可以测试一下，然后把结果告诉我;-)
为了更加清楚的说明这个问题，我们写一个测试程序，注意这个测试程序是有缺陷的。 只要我们构造一种情况，使得对方关闭了socket，我们还在read，或者是直接不关闭socket就会构造这样的情况。
交换机和路由器的区别
交换机拥有一条很高带宽的背部总线和内部交换矩阵。交换机的所有的端口都挂接在这条总线上，控制电路收到数据包以后，处理端口会查找内存中的地址对照表以确定目的MAC（网卡的硬件地址）的NIC（网卡）挂接在哪个端口上，通过内部交换矩阵迅速将数据包传送到目的端口，目的MAC若不存在则广播到所有的端口，接收端口回应后交换机会“学习”新的地址，并把它添加入内部MAC地址表中。 使用交换机也可以把网络“分段”，通过对照MAC地址表，交换机只允许必要的网络流量通过交换机。通过交换机的过滤和转发，可以有效的隔离广播风暴，减少误包和错包的出现，避免共享冲突。 交换机在同一时刻可进行多个端口对之间的数据传输。每一端口都可视为独立的网段，连接在其上的网络设备独自享有全部的带宽，无须同其他设备竞争使用。当节点A向节点D发送数据时，节点B可同时向节点C发送数据，而且这两个传输都享有网络的全部带宽，都有着自己的虚拟连接。假使这里使用的是10Mbps的以太网交换机，那么该交换机这时的总流通量就等于2×10Mbps＝20Mbps，而使用10Mbps的共享式HUB时，一个HUB的总流通量也不会超出10Mbps。 总之，交换机是一种基于MAC地址识别，能完成封装转发数据包功能的网络设备。交换机可以“学习”MAC地址，并把其存放在内部地址表中，通过在数据帧的始发者和目标接收者之间建立临时的交换路径，使数据帧直接由源地址到达目的地址。
从过滤网络流量的角度来看，路由器的作用与交换机和网桥非常相似。但是与工作在网络物理层，从物理上划分网段的交换机不同，路由器使用专门的软件协议从逻辑上对整个网络进行划分。例如，一台支持IP协议的路由器可以把网络划分成多个子网段，只有指向特殊IP地址的网络流量才可以通过路由器。对于每一个接收到的数据包，路由器都会重新计算其校验值，并写入新的物理地址。因此，使用路由器转发和过滤数据的速度往往要比只查看数据包物理地址的交换机慢。但是，对于那些结构复杂的网络，使用路由器可以提高网络的整体效率。路由器的另外一个明显优势就是可以自动过滤网络广播。
SNAT 指的就是在数据包从网卡发送出去时，将数据包里面的源地址这一个部分替换成为一个指定的IP（也就是网络之间互连的协议）。这样子的话，那么接收方就会认为数据包的来源就是被替换的那个IP的主机了。
例如：路由器lan口接的电脑访问百度，数据包从路由器出去的时候源地址会被替换成路由器wan口的ip地址，这种行为就是SNAT。
DNAT 网卡收到数据包的是否，将数据包里面的目的地址这一个部分替换成为一个指定的IP。这样子的话，那么接收方就会认为数据包的目的就是被替换的那个IP的主机了。
例如：路由器wan口收到百度返回的数据包的时候，目地址会被替换成路由器lan口下面接的pc的ip地址，这种行为就是DNAT。
POSTROUTING和REROUTING 在POSTROUTING链后，就传出数据包，该链是整个NAT结构的最末端。执行的是修改数据包的源IP地址，即SNAT。POSTROUTING只能进行SNAT
在数据包传入时，就进到PREROUTIING链。该链执行的是修改数据包内的目的IP地址，即DNAT（变更目的IP地址）。PREROUTING只能进行DNAT。因为进行了DNAT，才能在路由表中做判断，决定送到本地或其它网口
比如一台内网的机器想上internet，这时要用SNAT，将内网地址换成公网的正式IP地址；又比如内网有一台服务器想发布到公网上，让公网上的其它人来访问你，这时要用的就是DNAT。