Neo's Blog

熔断简单说明

在分布式系统中，一次完整的请求可能需要经过多个服务模块的调用，请求在多个服务中传递，服务对服务的调用会产生新的请求，这些请求共同组成了这次请求的调用链。当调用链中的某个环节，特别是下游服务不可用时，将会导致上游服务调用方不可用，最终将这种不可用的影响扩大到整个系统，导致整个分布式的不可用，引起服务雪崩现象。

为了避免这种情况，在下游服务不可用时，保护上游服务的可用性显得极其重要。对此我们可以通过熔断的方式，通过及时熔断服务调用方和服务提供方的调用链，保护服务调用方资源，防止服务雪崩现象的出现。

使用服务熔断，能够有效地保护服务调用方的稳定性，它能够避免服务调用者频繁调用可能失败的服务提供者，防止服务调用者浪费cpu、线程和IO资源等，提高服务整体的可用性。

所以，熔断设计的目的是在服务提供方不可用时保护服务调用方的资源，减少服务调用中无用的远程调用。

常见熔断策略

google SRE 自适应熔断

基于失败率

drop_ratio = $max(0, （requests - K * accepts） / (requests + 1))$

算法参数：

• requests：窗口时间内的请求总数
• accepts：正常请求数量
• K：敏感度，K 越小越容易丢请求，一般推荐 1.5-2 之间

算法解释：

• 正常情况下 requests=accepts，所以概率是 0。
• 随着正常请求数量减少，当达到 requests == K* accepts 继续请求时，概率 P 会逐渐比 0 大开始按照概率逐渐丢弃一些请求，如果故障严重则丢包会越来越多，假如窗口时间内 accepts==0 则完全熔断。
• 当应用逐渐恢复正常时，accepts、requests 同时都在增加，但是 K*accepts 会比 requests 增加的更快，所以概率很快就会归 0，关闭熔断。

brpc熔断策略

在开启了熔断之后，CircuitBreaker会记录每一个请求的处理结果，并维护一个累计出错时长，记为acc_error_cost，当acc_error_cost > max_error_cost时，熔断该节点。

两个小技巧：

1. 利用EMA（移动平均值）策略计算接口的平均响应时间
2. 利用双时间窗口统计来平衡短期抖动与长期错误率过高；

具体见：
CircuitBreaker

netflix 断路器

三种断路器状态：关闭、打开、半开

最近一段时间内的错误率 = 错误数 / 总数

最近一段时间内的错误数与总数，通过滑动窗口来实现，而滑动窗口又通过环形队列来实现。

错误率超过多少，则进入打开状态，持续一段时间。

持续一段时间后，进入半开状态，允许定量的请求通过，如果成功的比例足够大，则进入关闭状态，否则重新加入打开状态。

并行排序（并行归并排序、并行快速排序）

并行查找（并行的散列表，随机分为K份）

并行字符串匹配（任何算法都可以，只是分割后，需要补上2m个char）

并行搜索（对于BFS，使用两个队列，循环使用）

多线程问题的本质：有序性，可见性，原子性

我们处理线程安全可以有几个层次：

1. 能否做成无状态的不变对象。无状态是最安全的。
2. 能否线程封闭
   （1）栈封闭，多采用局部变量
   （2）线程局部存储（用空间换性能）
   （3）程序控制线程封闭（Hash，将同一hash val的的请求丢给同一个线程去处理）
3. 采用何种同步技术

多线程同步的方式

线程同步

多个线程间的一种协作机制。谈到线程我们经常想到的是线程间的竞争，比如去争夺锁，但这并不是故事的全部，线程间也会有协作机制。就是在一个线程进行了规定操作后，就进入等待状态， 等待其他线程执行完他们的指定代码过后 再将其唤醒;
（在有多个线程进行等待时， 如果需要，可以使用 notifyAll()来唤醒所有的等待线程。）

(1) 信号量 semphore

(2) 共享内存 shared_memory

(3) 读写锁 rw_lock

(4) 条件变量 condition

线程间存在依赖

(5) 互斥量 mutex

互斥锁

对于互斥锁，如果资源已经被占用，资源申请者只能进入睡眠状态。

1. 临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
2. 互斥量：为协调共同对一个共享资源的单独访问而设计的。
3. 信号量：为控制一个具有有限数量用户资源而设计。
4. 读写锁

自旋锁

但是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁。如果等待的时间比较短，适合使用自旋锁，占用大量的CPU资源

锁的实现机制

在硬件层面，CPU提供了原子操作、关中断、锁内存总线的机制。

禁中断

既然只有中断才能把上锁过程打断，造成多线程操作失败。我先关中断不就得了，在加锁操作完成后再开中断。

普通的原子指令

上面这个手段太笨重了，能不能硬件做一种加锁的原子操作呢？能，大名鼎鼎的“test and set”指令就是做这个事情的。

锁内存总线 + 原子指令

通过上面的手段，单核环境下，锁的实现问题得到了圆满的解决。

那么多核环境呢？简单嘛，还是“test and set”不就得了，这是一条指令，原子的，不会有问题的。

真的吗，单独一条指令能够保证该指令在单个核上执行过程中不会被中断打断，但是两个核同时执行这个指令呢？。。。

我再想想，硬件执行时还是得从内存中读取lock，判断并设置状态到内存，貌似这个过程也不是那么原子嘛。对，多个核执行确实会存在这个问题。怎么办呢？首先我们得明白这个地方的关键点，关键点是两个核会并行操作内存而且从操作内存这个调度来看“test and set”不是原子的，需要先读内存然后再写内存，如果我们保证这个内存操作是原子的，就能保证锁的正确性了。

确实，硬件提供了锁内存总线的机制，我们在锁内存总线的状态下执行test and set操作，就能保证同时只有一个核来test and set，从而避免了多核下发生的问题。

无锁

1. 无锁算法的底层实现 — CAS
2. 借助内存访问WORD的原子性

参考：

https://xie.infoq.cn/article/c7045d48ccb28872277445ff8

http://jm.taobao.org/2011/12/07/1347/

https://blog.csdn.net/heiyeshuwu/article/details/9722443

https://www.cnblogs.com/jing99/p/11984966.html

https://www.qbitai.com/2019/12/9895.html
https://www.jianshu.com/p/d585b3938dea

https://blog.csdn.net/ITer_ZC/article/details/40392787

高速缓存

思想：索引思想、折中思想

• 直接映射ByHash

主存中的一个块只能映射到Cache的某一特定块中去。例如，主存的第0块、第16块、……、第2032块，只能映射到Cache的第0块；而主存的第1块、第17块、……、第2033块，只能映射到Cache的第1块……

直接映射是最简单的地址映射方式，它的硬件简单，成本低，地址变换速度快，而且不涉及替换算法问题。

但是这种方式不够灵活，Cache的存储空间得不到充分利用，每个主存块只有一个固定位置可存放，容易产生冲突，使Cache效率下降，

因此只适合大容量Cache采用。

例如，如果一个程序需要重复引用主存中第0块与第16块，最好将主存第0块与第16块同时复制到Cache中，但由于它们都只能复制到Cache的第0块中去，即使Cache中别的存储空间空着也不能占用，因此这两个块会不断地交替装入Cache中，导致命中率降低

• 全相连映射ByAll

图3-15 是全相联映射的Cache组织，主存中任何一块都可以映射到Cache中的任何一块位置上

全相联映射方式比较灵活，主存的各块可以映射到Cache的任一块中，Cache的利用率高，块冲突概率低，只要淘汰Cache中的某一块，即可调入主存的任一块。

但是，由于Cache比较电路的设计和实现比较困难，这种方式只适合于小容量Cache采用。

• 组相连映射ByGroup

组间直接相连，组内全相连

组相联映射实际上是直接映射和全相联映射的折中方案，其组织结构如图3-16所示。主存和Cache都分组，主存中一个组内的块数与Cache中的分组数相同，组间采用直接映射，组内采用全相联映射。也就是说，将Cache分成u组，每组v块，主存块存放到哪个组是固定的，至于存到该组哪一块则是灵活的。例如，主存分为256组，每组8块，Cache分为8组，每组2块。

主存中的各块与Cache的组号之间有固定的映射关系，但可自由映射到对应Cache组中的任何一块。例如，主存中的第0块、第8块……均映射于Cache的第0组，但可映射到Cache第0组中的第0块或第1块；主存的第1块、第9块……均映射于Cache的第1组，但可映射到Cache第1组中的第2块或第3块。

常采用的组相联结构Cache，每组内有2、4、8、16块，称为2路、4路、8路、16路组相联Cache。

组相联结构Cache是前两种方法的折中方案，适度兼顾二者的优点，尽量避免二者的缺点，因而得到普遍采用。

具体参考：https://blog.csdn.net/weixin_34319111/article/details/92562285

一致性协议

MESI 缓存一致性协议

Modified、Exclusive、Shared、Invalid

我们知道linux采用了分页机制，通常采用四级页表，页全局目录(PGD)，页上级目录(PUD)，页中间目录(PMD)，页表(PTE)。如下：

1. 从CR3寄存器中读取页目录所在物理页面的基址(即所谓的页目录基址)，从线性地址的第一部分获取页目录项的索引，两者相加得到页目录项的物理地址。
2. 第一次读取内存得到pgd_t结构的目录项，从中取出物理页基址取出，即页上级页目录的物理基地址。
3. 从线性地址的第二部分中取出页上级目录项的索引，与页上级目录基地址相加得到页上级目录项的物理地址。
4. 第二次读取内存得到pud_t结构的目录项，从中取出页中间目录的物理基地址。
5. 从线性地址的第三部分中取出页中间目录项的索引，与页中间目录基址相加得到页中间目录项的物理地址。
6. 第三次读取内存得到pmd_t结构的目录项，从中取出页表的物理基地址。
7. 从线性地址的第四部分中取出页表项的索引，与页表基址相加得到页表项的物理地址。
8. 第四次读取内存得到pte_t结构的目录项，从中取出物理页的基地址。
9. 从线性地址的第五部分中取出物理页内偏移量，与物理页基址相加得到最终的物理地址。
10. 第五次读取内存得到最终要访问的数据。

整个过程是比较机械的，每次转换先获取物理页基地址，再从线性地址中获取索引，合成物理地址后再访问内存。不管是页表还是要访问的数据都是以页为单位存放在主存中的，因此每次访问内存时都要先获得基址，再通过索引(或偏移)在页内访问数据，因此可以将线性地址看作是若干个索引的集合。

虚拟内存管理

Linux通过红黑树管理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

struct task_struct {

    struct mm_struct *mm;

}

struct vm_area_struct {
    struct mm_struct * vm_mm;    /* 所属的内存描述符 */
    unsigned long vm_start;    /* vma的起始地址 */
    unsigned long vm_end;        /* vma的结束地址 */
 
    /* 该vma的在一个进程的vma链表中的前驱vma和后驱vma指针，链表中的vma都是按地址来排序的*/
    struct vm_area_struct *vm_next, *vm_prev;
 
    pgprot_t vm_page_prot;        /* vma的访问权限 */
    unsigned long vm_flags;    /* 标识集 */
 
    struct rb_node vm_rb;      /* 红黑树中对应的节点 */
}

该结构体是一段虚拟内存，从vm_start到vm_end，他们拥有相同的权限；
vm_prev 、vm_next 是双向链表的next与pre；
vm_rb 是红黑树节点

1
2
3
4
5

struct mm_struct {
        struct vm_area_struct * mmap;       /* list of VMAs */
        struct rb_root mm_rb;/*又是红黑树的根节点*/
        struct vm_area_struct * mmap_cache;      /* last find_vma result */
}

mmap是双向链表；按照地址大小来顺序管理所有的area

mm_rb是红黑树的根节点

红黑树的Key-Value: 虚拟地址 => 对应的area.

Page Cache 用于缓存文件的页数据，

buffer cache 用于缓存块设备（如磁盘）的块数据。

页是逻辑上的概念，因此 Page Cache 是与文件系统同级的；

块是物理上的概念，因此 buffer cache 是与块设备驱动程序同级的。

Page Cache 与 buffer cache 的共同目的都是加速数据 I/O

写数据时首先写到缓存，将写入的页标记为 dirty，然后向外部存储 flush，也就是缓存写机制中的 write-back（另一种是 write-through，Linux 默认情况下不采用）；

读数据时首先读取缓存，如果未命中，再去外部存储读取，并且将读取来的数据也加入缓存。

操作系统总是积极地将所有空闲内存都用作 Page Cache 和 buffer cache，当内存不够用时也会用 LRU 等算法淘汰缓存页。

在 Linux 2.4 版本的内核之前，Page Cache 与 buffer cache 是完全分离的。但是，块设备大多是磁盘，磁盘上的数据又大多通过文件系统来组织，这种设计导致很多数据被缓存了两次，浪费内存。

所以在 2.4 版本内核之后，两块缓存近似融合在了一起：如果一个文件的页加载到了 Page Cache，那么同时 buffer cache 只需要维护块指向页的指针就可以了。

只有那些没有文件表示的块，或者绕过了文件系统直接操作（如dd命令）的块，才会真正放到 buffer cache 里。

因此，我们现在提起 Page Cache，基本上都同时指 Page Cache 和 buffer cache 两者，本文之后也不再区分，直接统称为 Page Cache。

下图近似地示出 32-bit Linux 系统中可能的一种 Page Cache 结构，其中 block size 大小为 1KB，page size 大小为 4KB。

Page Cache 中的每个文件都是一棵基数树（radix tree，本质上是Trie、多叉搜索树），树的每个节点都是一个页。根据文件内的偏移量就可以快速定位到所在的页，如下图所示。关于基数树的原理可以参见英文维基，这里就不细说了。

TLB：MMU工作的过程就是查询页表的过程。如果把页表放在内存中查询的时候开销太大，因此为了提高查找效率，专门用一小片访问更快的区域存放地址转换条目。（当页表内容有变化的时候，需要清除TLB，以防止地址映射出错。）

Caches：cpu和内存之间的缓存机制，用于提高访问速率，armv8架构的话上图的caches其实是L2 Cache

内存命中率

假设在 n 次内存访问中，出现命中的次数是 m，那么 m / n * 100% 就表示命中率，这是衡量内存管理程序好坏的一个很重要的指标。

如果物理内存不足了，数据会在主存和磁盘之间频繁交换，命中率很低，性能出现急剧下降，我们称这种现象叫内存颠簸。这时你会发现系统的 swap 空间利用率开始增高， CPU 利用率中 iowait 占比开始增高。

大多数情况下，只要物理内存够用，页命中率不会非常低，不会出现内存颠簸的情况。因为大多数程序都有一个特点，就是局部性。

局部性就是说被引用过一次的存储器位置，很可能在后续再被引用多次；而且在该位置附近的其他位置，也很可能会在后续一段时间内被引用。

物理内存管理

对于Page级别的内存分配，通过Buddy系统来管理；TCMalloc 也是通过这种方式来管理span。

对于小对象（例如task_struct、mm_struct等）通过SlabAllcator来进行管理分配。这种思路，Memcache会借鉴。

进程与线程

• 进程线程的区别

线程独享：线程局部存储TLS、errno、寄存器、栈空间

• 进程间通信方式

• 线程的状态

• 介绍死锁和如何避免

线程安全

（1）synchronized 方法 + 代码块

（2）互斥锁lock

（3） 线程局部存储

（4）乐观锁

进程调度算法

多级反馈队列调度算法

分离thread

非分离线程在终止后，必须要有一个线程用 join 来等待它。否则，不会释放该线程的资源以供新线程使用，而这通常会导致内存泄漏。因此，如果不希望线程被等待，请将该线程作为分离线程来创建。

hash

hlist_head hlist_node 散列表拉链

根据PID定位task：PID哈希表

双向链表

list_head 双向链表

提高调度程序运行速度：建立多个可运行程序链表

等待队列（双向链表）：用自旋锁加保护的等待队列头、等待队列链表的元素

等待队列中睡眠进程的唤醒：互斥进程，非互斥进程

链表维护节点；节点包括管理区【硬件限制，ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM】+ page数组

动态定时器的链表组（将同一时间段内即将到时的定时器归入一组）

bitmap

pid分配管理：bitmap pidmap_array

inode、磁盘文件数据块

并发与同步

每CPU变量

不需要同步的内核数组，为每个cpu分配数组一元素

自旋锁

RCU机制

RCU(读取-拷贝-更新)：只保护被动态分配并通过指针引用的数据结构

何时释放旧副本？ CPU经过静止状态后，定期检测！！

原子变量

其他

thread 与 thread_info 紧密挨着；根据esp 屏蔽 低13位 可以最快的获取thread_info;
同时进程描述符指针在thread_info中的偏移为0!

也就是将： OS将task_struct指针存放到了栈上（可以通过esp做简单的AND操作即可）

jiffies:子系统启动的节拍总数

操作系统智慧

懒人哲学：越简单、越傻瓜、用户使用的学习成本越低越好

让困于人：当我们遇到困难时，搞不定的或者我们自己搞成本很大的，交给别人来搞(一般让操作系统来搞，其实操作系统也是别人完成的软件系统)

留有余地: 可扩展性，让系统有可扩展性

足够智能：一个系统最好能解决所有的问题，跟人的感觉是一个万能的解决方案，也就是操作系统的魔术师的角色

时空转换：在一个纬度遇到的瓶颈，那就改变方案把瓶颈移到另外一个纬度 【内存页表太大，占用内存资源；那就页表分级，不活跃的放到磁盘】

策机分离和权利分离：一个系统或者平台在主要指定规则、提供通用化的插件即可

简单与美：苛求于简，归于永恒