杂乱知识点

一些杂乱的知识点

杂乱知识点 01

目录

TODO

protobuf为啥快

• 数据压缩程度高
• 解析速度快

protobuf基本

使用tag|value方法存储数据。tag中包含数据序号与数据类型。从而避免了json的字符串解析。
tag生成办法：

static int makeTag(final int fieldNumber, final int wireType) {
  return (fieldNumber << 3) | wireType;
}

在上述代码中，fieldNumber为序号，wireType为数据类型。
有符号整型使用zigzag编码，减少了存储空间。
非varint类型数字采用小端序列存储。
字符串类型采用**tag|len|str|**方法存储。

有符号整型的压缩

ZigZag主要是将无符号数字0,1,2,3转换为有符号数字0,-1,1,-2等。
之后我们可以压缩数据。将32位数据每次取7位，如果非最低字节则补1,其余补0.然后将低字节与高字节反转。（小端）

断点调试原理

断点调试，即在断点处插入int 3指令，OS向进程发送SIGTRAP信号，使得当前进程暂停，交给父进程去处理。

按下ctrl-c后会发生什么

发送SIGINT信号给前台进程组所有进程，强行终止程序执行。

进程间通信IPC InterProcessCommunication

• 匿名管道PIPE
  • 半双工，只能一个方向流动，固定读写端
  • 只能有亲缘关系进程之间的通信
  • 类似于文件，可以read write，但仅存于内存
• 命名管道FIFO
  • 可以在无关进程之间交换数据
  • 属于特殊的文件形式存在于文件系统中，有路径名
• 消息队列
  • 包含消息类型，存在优先级，有特定格式
  • 读取时候可以按类型读取
• 信号量
  • 发送信号，主要用于同步进程
  • 原子操作
  • 可以计数
• 共享内存
  • 最快，直接读内存，效率高
  • 可以多进程同时操作，需要同步
  • 通常和信号量同时使用
  • 共享内存不需要涉及内核，所以最快

TOP-K问题

• quick select：快排思想，省去一半 平均On 最坏On2
• 建堆 nlogk 使用priority_queue来建，默认是大于号
• 建堆可以分布式
• 可以哈希去重

B树与B+树

B树

• 多叉树
• 关键词集合分布在整个树中
• 性能优异，等价于二分查找
• 关键词只出现在一个结点中
• 自动层次控制

B+树

• 用于数据库，文件系统等
• 数据稳定有序，自底向上插入，性能稳定
• 结点关键词只用于索引，不存储
• 叶子结点存储数据，并且添加链表指针

HTTP状态码

见restful api

布隆过滤器

使用k个哈希函数，将key映射成k个整数，然后将对应二进制位置为1。
有一定概率判断出错。
无法删除。

红黑树

红黑树，自平衡的类平衡树，非严谨平衡。有以下特点

• 结点或黑或红
• 根是黑的
• 红色无法相连，黑色可以
• 根到所有叶子结点经过的黑色结点个数相同
• 插入结点过程
  • 新插入的结点为红色
  • 如果为根结点，则标记成黑色
  • 如果parent不是黑色且不是root
    • uncle为红
      • 将parent and uncle标记为黑
      • 祖父标记为红
      • 与祖父相同颜色
    • uncle为黑 触发旋转
      • 新结点为左左，则提绳子
      • 左右，则将亲子换位，然后左左
      • 右右同理
      • 右做，则换位后右右
• 统计性能比avl更好

进程与线程

• 进程
  • 系统进行资源调度和分配的基本单位，实现操作系统的并发。
  • 进程内的线程共享堆，全局变量，静态变量，文件等。
  • 进程之间同步基于IPC。
  • 不同进程之间挂掉不影响
• 线程
  • CPU调度和分配的基本单位，实现进程内部的并发。
  • 有独立的寄存器组，指令计数器，自己的栈。
  • 线程之间同步基于内存。
  • 同一进程的线程会相互影响

虚拟地址

操作系统采用虚拟地址的方法，给予程序虚拟地址，由mmu翻译成物理地址，使得每个程序都认为自己独占了内存。
好处：

• 抽象化，便于管理，分配，调度，便于利用碎片
• 扩大地址空间
• 便于共享
• 可以保护内存空间，难以访问到其他进程的内存
  坏处：
• 增加了开销，如翻译地址，额外的数据结构，磁盘io
• 可能浪费内存

缺页中断

在malloc和mmap调用时候，只构建了虚拟地址，没有分配物理内存，当访问到的时候引起缺页异常，保护现场，分析原因，调用对应的处理函数，恢复。

系统锁

• mutex互斥锁

  • 读写都锁，统一时刻只能有一个访问

• rwlock读写锁

  • 写锁，可以有很多读，但写的时候不能读

• spin自旋锁

  • 同一时刻只有一个访问，但不会睡眠，而是自旋，一直保持活跃

• RCU锁

  • 写时候拷贝，对副本进行修改，在没有操作临界区时候去回调。

• 可重入锁

• 同一线程可以再次锁，不会死锁

• 乐观锁

  • 认为拿数据的时候别人不会修改，读取的时候不会上锁。
  • 在提交更新的时候使用版本号或者CAS算法来确定
    • CAS：当期望与实际符合的时候，才会更新替换，否则不会

• 悲观锁

  • 在每次读取或修改都会上锁
  • 不正确的代码容易导致死锁

进程状态

创建-就绪-执行-等待-终止

死锁

• 互斥：资源只能被一个进程使用
• 请求与保持：在请求资源时候，不会放开自己已经持有的资源
• 不剥夺：不能强行剥夺
• 循环等待：各个进程循环等待
• 银行家算法：三个矩阵claimd allocated need，只要剩余不为负数则贷款给过去

几种io

缓存IO：先拷贝到page cache，再拷贝到目标空间 效率较慢
select poll epoll本质都是同步io，用于io复用
select在socket被唤醒之后，进程从阻塞状态被加入工作队列，在工作队列中正运行的时候，会遍历一遍fd set来找到被唤醒的sock，从而处理。
select调用后会阻塞，知道fd就绪或者超时，并且通过遍历fd数组找到目标fd。描述符数量一半为1024。

poll使用pollfd指针来实现，返回后采用轮询来返回就绪的fd
epoll作用：先调用epoll create，然后用epoll ctl加入需要处理的sock，最后用epoll wait等待。在创建对象时候，会创建一个epollfd，用ctl来处理。当中断执行的时候，会加入到epollfd里面的readylist中。 epoll存在LT模式和ET模式，LT：应用程序不立即处理，ET则是立即处理。

• BIO 同步阻塞
  • 读取写入必须阻塞再一个线程里面完成，过程阻塞
• NIO 同步非阻塞
  • 不阻塞，而是反复查询
• AIO 异步io
  • 读取写入异步，内核读取了则发送信号

下一个排列算法

基本原则：把右边的稍微大一点的元素挪到前面来，并且使它不会到过于前面的位置。
从右向左，找到第一个ai小于ai+1的i，我们可以得知从i+1到末尾是完全降序的。再从右往左找到第一个大于ai的j。交换ai与aj，这时候ai+1到n是完全降序，因此然后将ai+1到末尾变成reverse，使其变成升序，也就是后半字典序最小，即为下一个排列。

丑数二分

如何找到比x小的，可以被abc整除的数的个数：使用集合，x/a+x/b+x/c-x/lcm(ab)-x/lcm(ac)-x/lac(bc)+x/lcm(abc)即可。
根据此原则，可以二分答案，找到模糊的界。
再根据该数，求出精确的边界。由n-min(n%a,n%b,n%c)可以得到。

为什么要等2MSL的时间，time_await状态才会结束

• 为了可靠地终止TCP连接。最后一次ACK可能会传输失败，因此需要等待。
• TCP分节可能会因为路由器异常而迷路，此时可能会有迟来的TCP分节到达，需要在到达的时候保证不返回，及时丢弃。

如何处理time_await过多的状态

MSL时间常用是30s，1min和2min。因此对于高并发短连接业务来说，会消耗大量端口，而且2MSL时间相对于业务逻辑过长。因此需要处理。
在系统设置中开启重用和快速回收。

如何查看进程

ps指令，或者进proc查pid，netstat显示网络链接