Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

HTTP对比

HTTP1.0

301: 永久重定向
302: 临时重定向

!默认关闭!
在HTTP 1.0中,服务器始终在发送响应后关闭连接, 除非客户端发送了Connection: keep-alive请求标头,并且服务器发送了一个Connection: keep-alive响应标头。 如果不存在这样的响应报头,则客户端在收到响应后必须关闭连接的结束。

!默认打开!
在HTTP 1.1中,服务器在发送响应之后不关闭连接, 除非客户端发送了Connection: close请求标头,或者服务器发送了Connection: close响应标头。 如果存在这样的响应头,则客户端在收到响应后必须关闭连接的结束。

HTTPS

可以参考:https://blog.csdn.net/xiaoming100001/article/details/81109617

对称加密与非对称加密相结合

通信内容,通过对称加密算法来加解密;其中有一个重要的东西叫:密钥

密钥是通过非对称加密算法来加密传输,客户端使用服务器的public key来加密,服务端通过自己的private key来解密。

服务器的public key,浏览器如何得知呢? 通过SSL证书

SSL证书组织是一个树形组织,最上面的几层是hardcode在系统中的。

当需要验证证书有效性时,浏览器会通过根认证组织逐层认证!

HTTP2.0

服务器推送、头信息压缩、等

二进制分帧

先来理解几个概念:

帧:HTTP/2 数据通信的最小单位消息:指 HTTP/2 中逻辑上的 HTTP 消息。例如请求和响应等,消息由一个或多个帧组成。

流:存在于连接中的一个虚拟通道。流可以承载双向消息,每个流都有一个唯一的整数ID。

HTTP/2 采用二进制格式传输数据,而非 HTTP 1.x 的文本格式,二进制协议解析起来更高效。 HTTP / 1 的请求和响应报文,都是由起始行,首部和实体正文(可选)组成,各部分之间以文本换行符分隔。HTTP/2 将请求和响应数据分割为更小的帧,并且它们采用二进制编码。

HTTP/2 中,同域名下所有通信都在单个连接上完成,该连接可以承载任意数量的双向数据流。每个数据流都以消息的形式发送,而消息又由一个或多个帧组成。多个帧之间可以乱序发送,根据帧首部的流标识可以重新组装。

多路复用

在 HTTP/2 中,有了二进制分帧之后,HTTP /2 不再依赖 TCP 链接去实现多流并行了,在 HTTP/2中:

同域名下所有通信都在单个连接上完成。
单个连接可以承载任意数量的双向数据流。
数据流以消息的形式发送,而消息又由一个或多个帧组成,多个帧之间可以乱序发送,因为根据帧首部的流标识可以重新组装。

服务器推送

服务端可以在发送页面HTML时主动推送其它资源,而不用等到浏览器解析到相应位置,发起请求再响应。例如服务端可以主动把JS和CSS文件推送给客户端,而不需要客户端解析HTML时再发送这些请求。

服务端可以主动推送,客户端也有权利选择是否接收。如果服务端推送的资源已经被浏览器缓存过,浏览器可以通过发送RST_STREAM帧来拒收。主动推送也遵守同源策略,服务器不会随便推送第三方资源给客户端。

头部压缩

HTTP 1.1请求的大小变得越来越大,有时甚至会大于TCP窗口的初始大小,因为它们需要等待带着ACK的响应回来以后才能继续被发送。HTTP/2对消息头采用HPACK(专为http/2头部设计的压缩格式)进行压缩传输,能够节省消息头占用的网络的流量。而HTTP/1.x每次请求,都会携带大量冗余头信息,浪费了很多带宽资源。

为了减少这块的资源消耗并提升性能, HTTP/2对这些首部采取了压缩策略:

HTTP/2在客户端和服务器端使用“首部表”来跟踪和存储之前发送的键-值对,对于相同的数据,不再通过每次请求和响应发送;

首部表在HTTP/2的连接存续期内始终存在,由客户端和服务器共同渐进地更新;

每个新的首部键-值对要么被追加到当前表的末尾,要么替换表中之前的值。

HTTP3.0

HTTP23对比

QUIC(Quick UDP Internet Connections)基于 UDP 实现,是 HTTP/3 中的底层支撑协议,该协议基于 UDP,又取了 TCP 中的精华,实现了即快又可靠的协议

参考:https://blog.51cto.com/u_6315133/3122045

负数

负数用补码来表示,补码等于数的反码 + 1

浮点数

两种表示小数的数据类型,分别是双精度浮点数和单精度浮点数

双精度浮点数类型用64位:符号位(1位) + 阶码(11位) + 尾数(52位)

单精度浮点数类型用32位:符号位(1位) + 阶码(8位) + 尾数(23位)

符号位:正数为0,负数为1;

指数位:阶数+偏移量,阶数是2^(e-1)-1,e为阶码的位数,也就是指数位的位数。偏移量是把小数点移动到整数位只有1时移动的位数,正数表示向左移,负数表示向右移;

小数位:即二进制小数点后面的数。

一个例子

把0.1(10)转成的二进制0.00011 0011 0011 …(2)转成浮点数形式的二进制:

(能够精确表示的小数为:0.5,0.25,0.125…等的自由组合)

转化过程见:https://cloud.tencent.com/developer/article/1856972

1、先要把小数点移动到整数位只有1,要向右移动4位,故偏移量为-4,通过指数位的计算公式2^(e-1)-1+偏移量 = 2^(11-1)-1-4 = 1019,把1019转成二进制为1111111011,不够11位要补零,最终得出指数位位01111111011;

2、移位后的小数位为.1 0011 0011 …,因为小数位只能保留52位,第50、51、52位、53位分别为0011,故对第52位进1使第51位为1,使第50、51、52位为010。

注意:此处的精度丢失问题,有很多小数(例如本例中的0.1)在转二进制时会出现无限循环的情况,所以在位数有限的境况下,肯定需要舍弃后面的精度。这一点,就与1/3这种小数是在十进制下无限循环类似。

定点数

只能表示纯小数,例如0.999991212

TLB(Translation Lookaside Buffer)是一块高速缓存。

TLB缓存虚拟地址和其映射的物理地址。

数据cache缓存地址(虚拟地址或者物理地址)和数据。

参考:https://zhuanlan.zhihu.com/p/108425561

存储的分布式化

高效存储的一些考虑:

  1. 很长时间没有人访问的老数据,怎么办?
  2. 是不是减少副本的同时,还能还原出数据?(例如,RAID)
  3. 数据压缩,平成好压缩效果与压缩/解压速度
  4. 数据的分层存储:根据数据的冷热来选择不同的存储介质(局部性原理),内存、硬盘(SSD、SATA)
  5. 存储与计算分离(底层基础:网络IO不再是瓶颈,而CPU性能、磁盘IO性能跟不上)

分布式存储引擎

主要解决数据如何拆分、数据如何冗余、数据如何定位的问题。

(1)parititioning 方式,即数据在逻辑上怎么切分

(2)localization 方式,即数据在物理上怎么分布

一个系统要想拥有高可用性,有且只有一个办法 — 副本(replication),因为物理故障是无法避免的,只能花钱做备份。

主从和时效性是 replication 要考虑的两个重要问题。

主从主要有单主、多主和无主三种方式。

时效性主要有同步、异步、半同步三种方式。

(3)rebalance 方式,即在节点数变化后,数据在物理上怎么重新分布.

分布式文件系统

按照Block拆分文件,然后通过一个管理员来管理Block到对应及其的映射关系。

新的问题:
如果存储block的机器挂了怎么办? 如果管理员挂了怎么办?

参考:https://zhuanlan.zhihu.com/p/141775358

CAP VS BASE

一致性

强一致性

保证手段:单机落磁盘、数据库事务、分布式事务等

弱一致性

可能丢失一定的数据:异步复制、PageCache的write back

最终一致性

带TTL的缓存

为什么会有分布式

两点:算得慢(算力不足),存不下(数据分散)。

无论是线程、进程,还是协程,本质上,目的都是为了计算的并行化,解决的是算的慢的问题。

因为一个CPU算不过来,而单机扩容CPU数量成本极高(有空间这个刚性限制),所以需要水平扩容,多搞几台机器。

计算的分布式化:基于分治思想,出现了分布式框架。

MapReduce: 分布式计算的总体思想。

分布式计算框架更多尝试对资源的调度做优化。ResourceManager, yarn, k8s;
(多租户,隔离,软隔离,租借,抢占等)

高并发系统的三个目标与挑战

高并发是一个系统的挑战

如何衡量一个系统的并发有多高呢? 同时在线人数

高性能、高可用、可扩展是一个牛B系统目标

三者的关系

为了保证高可用,需要冗余更多的相同功能机器(replication),要求系统可扩展;

为了保证高性能,必须需要更多的相同功能的机器(存储的replication、应用的无状态)或者服务于不同对象的机器(shard),也要求可扩展;

一份完整的数据,分为多个shard的过程需要可扩展;

一份数据冗余了多份,前端对下游访问时用到的负载均衡策略需要可扩展。

如何衡量一个吞吐量有多大呢?

系统的QPS,吞吐量 = 并发进程数 / 响应时间

如何衡量一个系统的性能有多高呢?

一旦系统的负载被描述好,就可以研究当负载增加会发生什么。我们可以从两种角度来看:

  • 增加负载参数并保持系统资源(CPU、内存、网络带宽等)不变时,系统性能将受到什么影响?(接口响应时间,分位耗时)
  • 增加负载参数并希望保持性能不变时,需要增加多少系统资源?

如何衡量一个系统的可用性有多高呢?

平均故障间隔,平均故障恢复时间

不同可用性标准下允许的故障时间

如何衡量一个系统的可扩展能力?

考察一个问题:能够通过增加进程来应对更高的并发? 如果一直加机器,我一直能线性的提高系统的处理能力吗?

如何应对系统的挑战

架构通用原则:“4 要 1 不要”

(1) 数据要尽量少

  • 用户请求的数据能少就少
  • 系统依赖的数据能少就少

(2) 请求数要尽量少

例如,静态文件合并

(3)路径要尽量短

将强依赖的服务进行单机部署

(4)依赖要尽量少

系统服务分级,高等级服务尽量少依赖低等级服务

(5)不要有单点

服务无状态,可扩展;存储层做副本备份

主流系统架构

软件设计模式的几种分类

创建型

创建对象时,不再由我们直接实例化对象;而是根据特定场景,由程序来确定创建对象的方式,从而保证更大的性能、更好的架构优势。

创建型模式主要有:

简单工厂模式
工厂方法

意图:定义一个创建对象的接口,让其子类自己决定实例化哪一个工厂类,工厂模式使其创建过程延迟到子类进行。

主要解决:主要解决接口选择的问题。

何时使用:我们明确地计划不同条件下创建不同实例时。

如何解决:让其子类实现工厂接口,返回的也是一个抽象的产品。

关键代码:创建过程在其子类执行。

应用实例:
1、您需要一辆汽车,可以直接从工厂里面提货,而不用去管这辆汽车是怎么做出来的,以及这个汽车里面的具体实现。
2、Hibernate 换数据库只需换方言和驱动就可以。

优点:
1、一个调用者想创建一个对象,只要知道其名称就可以了。
2、扩展性高,如果想增加一个产品,只要扩展一个工厂类就可以。
3、屏蔽产品的具体实现,调用者只关心产品的接口。

缺点:每次增加一个产品时,都需要增加一个具体类和对象实现工厂,使得系统中类的个数成倍增加,在一定程度上增加了系统的复杂度,同时也增加了系统具体类的依赖。这并不是什么好事。

使用场景:
1、日志记录器:记录可能记录到本地硬盘、系统事件、远程服务器等,用户可以选择记录日志到什么地方。
2、数据库访问,当用户不知道最后系统采用哪一类数据库,以及数据库可能有变化时。
3、设计一个连接服务器的框架,需要三个协议,”POP3”、”IMAP”、”HTTP”,可以把这三个作为产品类,共同实现一个接口。

注意事项:作为一种创建类模式,在任何需要生成复杂对象的地方,都可以使用工厂方法模式。有一点需要注意的地方就是复杂对象适合使用工厂模式,而简单对象,特别是只需要通过 new 就可以完成创建的对象,无需使用工厂模式。如果使用工厂模式,就需要引入一个工厂类,会增加系统的复杂度。

抽象工厂模式

就是建立一个工厂类,对实现了同一接口的一些类进行实例的创建。简单工厂模式的实质是由一个工厂类根据传入的参数,动态决定应该创建哪一个产品类(这些产品类继承自一个父类或接口)的实例。

意图:提供一个创建一系列相关或相互依赖对象的接口,而无需指定它们具体的类。

主要解决:主要解决接口选择的问题。

何时使用:系统的产品有多于一个的产品族,而系统只消费其中某一族的产品。

如何解决:在一个产品族里面,定义多个产品。

关键代码:在一个工厂里聚合多个同类产品。

应用实例:

优点:当一个产品族中的多个对象被设计成一起工作时,它能保证客户端始终只使用同一个产品族中的对象。

缺点:产品族扩展非常困难,要增加一个系列的某一产品,既要在抽象的 Creator 里加代码,又要在具体的里面加代码。

使用场景: 1、QQ 换皮肤,一整套一起换。 2、生成不同操作系统的程序。

注意事项:产品族难扩展,产品等级易扩展。

单例模式

全局资源管理,简化访问。

意图:保证一个类仅有一个实例,并提供一个访问它的全局访问点。

主要解决:一个全局使用的类频繁地创建与销毁。

何时使用:当您想控制实例数目,节省系统资源的时候。

如何解决:判断系统是否已经有这个单例,如果有则返回,如果没有则创建。

关键代码:构造函数是私有的。

应用实例:

1、一个班级只有一个班主任。
2、Windows 是多进程多线程的,在操作一个文件的时候,就不可避免地出现多个进程或线程同时操作一个文件的现象,所以所有文件的处理必须通过唯一的实例来进行。
3、一些设备管理器常常设计为单例模式,比如一个电脑有两台打印机,在输出的时候就要处理不能两台打印机打印同一个文件。

优点:
1、在内存里只有一个实例,减少了内存的开销,尤其是频繁的创建和销毁实例(比如管理学院首页页面缓存)。
2、避免对资源的多重占用(比如写文件操作)。

缺点:没有接口,不能继承,与单一职责原则冲突,一个类应该只关心内部逻辑,而不关心外面怎么样来实例化。

使用场景:

1、要求生产唯一序列号。
2、WEB 中的计数器,不用每次刷新都在数据库里加一次,用单例先缓存起来。
3、创建的一个对象需要消耗的资源过多,比如 I/O 与数据库的连接等。

注意事项:getInstance() 方法中需要使用同步锁 synchronized (Singleton.class) 防止多线程同时进入造成 instance 被多次实例化。

建造者模式

意图:将一个复杂的构建与其表示相分离,使得同样的构建过程可以创建不同的表示。

主要解决:主要解决在软件系统中,有时候面临着”一个复杂对象”的创建工作,其通常由各个部分的子对象用一定的算法构成;由于需求的变化,这个复杂对象的各个部分经常面临着剧烈的变化,但是将它们组合在一起的算法却相对稳定。

何时使用:一些基本部件不会变,而其组合经常变化的时候。

如何解决:将变与不变分离开。

关键代码:建造者:创建和提供实例,导演:管理建造出来的实例的依赖关系。

应用实例:
1、去肯德基,汉堡、可乐、薯条、炸鸡翅等是不变的,而其组合是经常变化的,生成出所谓的”套餐”。
2、JAVA 中的 StringBuilder。

优点: 1、建造者独立,易扩展。 2、便于控制细节风险。

缺点: 1、产品必须有共同点,范围有限制。 2、如内部变化复杂,会有很多的建造类。

使用场景: 1、需要生成的对象具有复杂的内部结构。 2、需要生成的对象内部属性本身相互依赖。

一个类的各个组成部分的具体实现类或者算法经常面临着变化,但是将他们组合在一起的算法却相对稳定。提供一种封装机制 将稳定的组合算法于易变的各个组成部分隔离开来。

注意事项:与工厂模式的区别是:建造者模式更加关注与零件装配的顺序

原型模式

意图:用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象。

主要解决:在运行期建立和删除原型。

何时使用:
1、当一个系统应该独立于它的产品创建,构成和表示时。
2、当要实例化的类是在运行时刻指定时,例如,通过动态装载。
3、为了避免创建一个与产品类层次平行的工厂类层次时。
4、当一个类的实例只能有几个不同状态组合中的一种时。建立相应数目的原型并克隆它们可能比每次用合适的状态手工实例化该类更方便一些。

如何解决:利用已有的一个原型对象,快速地生成和原型对象一样的实例。

关键代码:
1、实现克隆操作,在 JAVA 实现 Cloneable 接口,重写 clone(),在 .NET 中可以使用 Object 类的 MemberwiseClone() 方法来实现对象的浅拷贝或通过序列化的方式来实现深拷贝。
2、原型模式同样用于隔离类对象的使用者和具体类型(易变类)之间的耦合关系,它同样要求这些”易变类”拥有稳定的接口。

应用实例: 1、细胞分裂。 2、JAVA 中的 Object clone() 方法。

优点: 1、性能提高。 2、逃避构造函数的约束。

缺点: 1、配备克隆方法需要对类的功能进行通盘考虑,这对于全新的类不是很难,但对于已有的类不一定很容易,特别当一个类引用不支持串行化的间接对象,或者引用含有循环结构的时候。 2、必须实现 Cloneable 接口。

使用场景: 1、资源优化场景。 2、类初始化需要消化非常多的资源,这个资源包括数据、硬件资源等。 3、性能和安全要求的场景。 4、通过 new 产生一个对象需要非常繁琐的数据准备或访问权限,则可以使用原型模式。 5、一个对象多个修改者的场景。 6、一个对象需要提供给其他对象访问,而且各个调用者可能都需要修改其值时,可以考虑使用原型模式拷贝多个对象供调用者使用。 7、在实际项目中,原型模式很少单独出现,一般是和工厂方法模式一起出现,通过 clone 的方法创建一个对象,然后由工厂方法提供给调用者。原型模式已经与 Java 融为浑然一体,大家可以随手拿来使用。

注意事项:与通过对一个类进行实例化来构造新对象不同的是,原型模式是通过拷贝一个现有对象生成新对象的。浅拷贝实现 Cloneable,重写,深拷贝是通过实现 Serializable 读取二进制流。

结构型

用于帮助将多个对象组织成更大的结构。

结构型模式主要有:

适配器模式adapter

适配器模式(Adapter Pattern)是作为两个不兼容的接口之间的桥梁。这种类型的设计模式属于结构型模式,它结合了两个独立接口的功能。

意图:将一个类的接口转换成客户希望的另外一个接口。适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。

主要解决:主要解决在软件系统中,常常要将一些”现存的对象”放到新的环境中,而新环境要求的接口是现对象不能满足的。

何时使用:
1、系统需要使用现有的类,而此类的接口不符合系统的需要。
2、想要建立一个可以重复使用的类,用于与一些彼此之间没有太大关联的一些类,包括一些可能在将来引进的类一起工作,这些源类不一定有一致的接口。
3、通过接口转换,将一个类插入另一个类系中。(比如老虎和飞禽,现在多了一个飞虎,在不增加实体的需求下,增加一个适配器,在里面包容一个虎对象,实现飞的接口。)

如何解决:继承或依赖(推荐)。

关键代码:适配器继承或依赖已有的对象,实现想要的目标接口。

应用实例:
1、美国电器 110V,中国 220V,就要有一个适配器将 110V 转化为 220V。
2、JAVA JDK 1.1 提供了 Enumeration 接口,而在 1.2 中提供了 Iterator 接口,想要使用 1.2 的 JDK,则要将以前系统的 Enumeration 接口转化为 Iterator 接口,这时就需要适配器模式。
3、在 LINUX 上运行 WINDOWS 程序。 4、JAVA 中的 jdbc。

优点: 1、可以让任何两个没有关联的类一起运行。 2、提高了类的复用。 3、增加了类的透明度。 4、灵活性好。

缺点: 1、过多地使用适配器,会让系统非常零乱,不易整体进行把握。比如,明明看到调用的是 A 接口,其实内部被适配成了 B 接口的实现,一个系统如果太多出现这种情况,无异于一场灾难。因此如果不是很有必要,可以不使用适配器,而是直接对系统进行重构。 2.由于 JAVA 至多继承一个类,所以至多只能适配一个适配者类,而且目标类必须是抽象类。

使用场景:有动机地修改一个正常运行的系统的接口,这时应该考虑使用适配器模式。

注意事项:适配器不是在详细设计时添加的,而是解决正在服役的项目的问题。

桥接模式bridge

意图:将抽象部分与实现部分分离,使它们都可以独立的变化。

主要解决:在有多种可能会变化的情况下,用继承会造成类爆炸问题,扩展起来不灵活。

何时使用:实现系统可能有多个角度分类,每一种角度都可能变化。

如何解决:把这种多角度分类分离出来,让它们独立变化,减少它们之间耦合。

关键代码:抽象类依赖实现类。

应用实例:

1、猪八戒从天蓬元帅转世投胎到猪,转世投胎的机制将尘世划分为两个等级,即:灵魂和肉体,前者相当于抽象化,后者相当于实现化。生灵通过功能的委派,调用肉体对象的功能,使得生灵可以动态地选择。

2、墙上的开关,可以看到的开关是抽象的,不用管里面具体怎么实现的。

优点:

1、抽象和实现的分离。
2、优秀的扩展能力。
3、实现细节对客户透明。

缺点:桥接模式的引入会增加系统的理解与设计难度,由于聚合关联关系建立在抽象层,要求开发者针对抽象进行设计与编程。

使用场景: 1、如果一个系统需要在构件的抽象化角色和具体化角色之间增加更多的灵活性,避免在两个层次之间建立静态的继承联系,通过桥接模式可以使它们在抽象层建立一个关联关系。 2、对于那些不希望使用继承或因为多层次继承导致系统类的个数急剧增加的系统,桥接模式尤为适用。 3、一个类存在两个独立变化的维度,且这两个维度都需要进行扩展。

注意事项:对于两个独立变化的维度,使用桥接模式再适合不过了。

组合器模式component

意图:将对象组合成树形结构以表示”部分-整体”的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。

主要解决:它在我们树型结构的问题中,模糊了简单元素和复杂元素的概念,客户程序可以像处理简单元素一样来处理复杂元素,从而使得客户程序与复杂元素的内部结构解耦。

何时使用:

1、您想表示对象的部分-整体层次结构(树形结构)。
2、您希望用户忽略组合对象与单个对象的不同,用户将统一地使用组合结构中的所有对象。

如何解决:树枝和叶子实现统一接口,树枝内部组合该接口。

关键代码:树枝内部组合该接口,并且含有内部属性 List,里面放 Component。

应用实例:
1、算术表达式包括操作数、操作符和另一个操作数,其中,另一个操作数也可以是操作数、操作符和另一个操作数。
2、在 JAVA AWT 和 SWING 中,对于 Button 和 Checkbox 是树叶,Container 是树枝。

优点:

1、高层模块调用简单。 2、节点自由增加。

缺点:在使用组合模式时,其叶子和树枝的声明都是实现类,而不是接口,违反了依赖倒置原则。

使用场景:部分、整体场景,如树形菜单,文件、文件夹的管理。

注意事项:定义时为具体类。

外观门面模式Facade

意图:为子系统中的一组接口提供一个一致的界面,外观模式定义了一个高层接口,这个接口使得这一子系统更加容易使用。

主要解决:降低访问复杂系统的内部子系统时的复杂度,简化客户端之间的接口。

何时使用: 1、客户端不需要知道系统内部的复杂联系,整个系统只需提供一个”接待员”即可。 2、定义系统的入口。

如何解决:客户端不与系统耦合,外观类与系统耦合。

关键代码:在客户端和复杂系统之间再加一层,这一层将调用顺序、依赖关系等处理好。

应用实例:

1、去医院看病,可能要去挂号、门诊、划价、取药,让患者或患者家属觉得很复杂,如果有提供接待人员,只让接待人员来处理,就很方便。
2、JAVA 的三层开发模式。

优点: 1、减少系统相互依赖。 2、提高灵活性。 3、提高了安全性。

缺点:不符合开闭原则,如果要改东西很麻烦,继承重写都不合适。

使用场景:
1、为复杂的模块或子系统提供外界访问的模块。
2、子系统相对独立。 3、预防低水平人员带来的风险。

注意事项:在层次化结构中,可以使用外观模式定义系统中每一层的入口。

亨元模式flyweight

意图:运用共享技术有效地支持大量细粒度的对象。

主要解决:在有大量对象时,有可能会造成内存溢出,我们把其中共同的部分抽象出来,如果有相同的业务请求,直接返回在内存中已有的对象,避免重新创建。

何时使用:

1、系统中有大量对象。
2、这些对象消耗大量内存。
3、这些对象的状态大部分可以外部化。
4、这些对象可以按照内蕴状态分为很多组,当把外蕴对象从对象中剔除出来时,每一组对象都可以用一个对象来代替。
5、系统不依赖于这些对象身份,这些对象是不可分辨的。

如何解决:用唯一标识码判断,如果在内存中有,则返回这个唯一标识码所标识的对象。

关键代码:用 HashMap 存储这些对象。

应用实例:
1、JAVA 中的 String,如果有则返回,如果没有则创建一个字符串保存在字符串缓存池里面。
2、数据库的数据池。

优点:大大减少对象的创建,降低系统的内存,使效率提高。

缺点:提高了系统的复杂度,需要分离出外部状态和内部状态,而且外部状态具有固有化的性质,不应该随着内部状态的变化而变化,否则会造成系统的混乱。

使用场景: 1、系统有大量相似对象。 2、需要缓冲池的场景。

注意事项: 1、注意划分外部状态和内部状态,否则可能会引起线程安全问题。 2、这些类必须有一个工厂对象加以控制。

装饰器模式decorator

对已有的业务逻辑进一步的封装,使其增加额外的功能,如java中的IO流就使用了装饰者模式,用户在使用的时候,可以任意组装,达到自己想要的效果。

代理模式proxy

代理模式是给某一个对象提供一个代理,并由代理对象控制对原对象的引用。

优点:代理模式能够协调调用者和被调用者,在一定程度上降低了系统的耦合度;可以灵活地隐藏被代理对象的部分功能和服务,也增加额外的功能和服务。

缺点:

由于使用了代理模式,因此程序的性能没有直接调用性能高;使用代理模式提高了代码的复杂度。

举一个生活中的例子:比如买飞机票,由于离飞机场太远,直接去飞机场买票不太现实,这个时候我们就可以上携程 App 上购买飞机票,这个时候携程 App 就相当于是飞机票的代理商。

行为型

用于帮助系统间各对象的通信,以及如何控制复杂系统中流程。

行为型模式主要有:

解释器模式

用的比较少,可能出现的地方:语法解析

中介者模式

作用:
通过使用一个中间对象来进行消息分发以及减少类之间的直接依赖。

本质:

ComponentA,ComponentB,ComponentC 都拥有一个Mediator(拥有一个方法notify)

当某一个Component执行某一个操作的时候, 除了做完自己的事情,还需要Mediator::Notify

Mediator有一个具体的子类叫:ConcreteMediator,他拥有所有的Component,并overwrite了Notify接口

命令模式command

命令模式:将一个请求封装为一个对象,从而使你可以用不同的请求对客户进行参数化,对请求排队和记录请求日志,以及支持可撤销的操作。

应用场景:将命令者与执行者完全解耦。

Java中的Runnable就是命令模式

迭代器模式

STL::iterator

备忘录模式

Originator 发起者;
CareTaker 备忘录管理者,管理所有的备忘录快照
Memoto 备忘录,有getState, setState两个方法

一个游戏,玩一会儿,自动存档,再玩一会,自动存档。就可以考虑用备忘录模式

观察者模式

发布订阅模式

对象间一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新。Android中的各种Listener就使用到了这一设计模式,只要用户对手机进行操作,对应的listener就会被通知,并作出响应的处理。

状态模式state

状态模式:允许对象在其内部状态改变时改变他的行为。对象看起来似乎改变了他的类。

应用场景:一个对象的内部状态改变时,他的行为剧烈的变化。

context 使用 State

concreteStateA,B,C继承自State

concreteStateA 可以在实现时切换状态到B

模板模式

模板方法模式是指定义一个模板结构,将具体内容延迟到子类去实现。

让子类可以重写方法的一部分,而不是整个重写,你可以控制子类需要重写那些操作。

做一件事情需要1,2,3三步,父类提供了基本实现,子类也可以选择overwrite。

策略模式

答:策略模式是指定义一系列算法,将每个算法都封装起来,并且使他们之间可以相互替换。

优点:遵循了开闭原则,扩展性良好。

缺点:随着策略的增加,对外暴露越来越多。

策略模式则是以接口形式提供抽象接口。由具体实现类提供不同算法。

策略模式一般由3部分组成

  • 一个Context持有所有策略实现类引用,提供给客户端运行
  • 一个策略接口提供
  • 具体的策略实现类

通过上面可以看到,策略模式和模板模式有一个最重要的区别,即模板模式一般只针对一套算法,注重对同一个算法的不同细节进行抽象提供不同的实现。而策略模式注重多套算法多套实现,在算法中间不应该有交集,因此算法和算法只间一般不会有冗余代码!因为不同算法之间的实现一般不同很相近。

因此我们可以看到,策略模式的关注点更广,模板模式的关注点更深。而且两种模式可以一起使用,即具体某个策略下可以通过模板减少不同步骤的冗余代码。

例如:限流是服务器要实现的功能,但是实现策略有基于滑动窗口的限流策略、基于令牌桶的限流策略等。

访问者模式

用途:文件遍历
java.nio.file.FileVisitor接口
类功能:一个用于访问文件的接口。这一接口的实现类通过Files.walkFileTree方法实现对文件树中每一个文件的访问。
public static Path walkFileTree(Path start,Set options,
int maxDepth,FileVisitor< super Path> visitor) ,这一方法中回调了visitor的方法。
方法实现上:访问者对每一个被访问者都有一个实现方法。每一个被访问者都有一个通用方法,输入参数为访问者,此方法用于调用访问者的方法。

责任链

webserver的filter

通过把请求从一个对象传递到链条中下一个对象的方式来解除对象之间的耦合,直到请求被处理完毕。链中的对象是同一接口或抽象类的不同实现。

参考:

https://blog.csdn.net/sinat_34166518/article/details/89206059

系统在困境(adversity)(硬件故障、软件故障、人为错误)中仍可正常工作(正确完成功能,并能达到期望的性能水准)。

plan挂了之后,系统能不能活下来? 有没有负责兜底的PlanB。

造成错误的原因叫做故障(fault),能预料并应对故障的系统特性可称为容错(fault-tolerant)或韧性(resilient)。

注意故障(fault)不同于失效(failure)【2】。故障通常定义为系统的一部分状态偏离其标准,而失效则是系统作为一个整体停止向用户提供服务。故障的概率不可能降到零,因此最好设计容错机制以防因故障而导致失效。

影响可用性的因素

首先我们先梳理一下影响系统稳定性的一些常见的问题场景,大致可分为三类:

人为因素

不合理的变更、外部攻击等等

软件因素

代码bug、设计漏洞、GC问题、线程池异常、上下游异常

硬件因素

网络故障、机器故障等

可用性速降到最低的表现-雪崩

两个导火索:

  • 下游或者本身机器故障导致latency增加
  • 上游请求qps变高

实际的并发超过了最大能支持的并发(当下游变慢后,该值迅速会下降),过载就发生了。过载不可怕,如果上游不重试,系统终将恢复。

如何提高可用性

系统拆分

拆分不是以减少不可用时间为目的,而是以减少故障影响面为目的。

因为一个大的系统拆分成了几个小的独立模块,一个模块(大概率是变更导致,例如升级代码)出了问题不会影响到其他的模块,从而降低故障的影响面。

系统拆分又包括接入层拆分、服务拆分、数据库拆分。

接入层&服务层

【轻重分离】
一般是按照业务模块、重要程度、变更频次等维度拆分。

数据层

【轻重分离】、【冷热分离】、【读写分离】
一般先按照业务拆分后,如果有需要还可以做垂直拆分也就是数据分片、读写分离、数据冷热分离等。

把核心库与非核心库分机器部署,避免相互影响。

解耦

系统进行拆分之后,会分成多个模块。模块之间的依赖有强弱之分。

如果是强依赖的,那么如果依赖方出问题了,也会受到牵连出问题,强依赖需要基于被依赖放的SLA做好超时熔断配置以及本服务自身的容量预估。

这时可以梳理整个流程的调用关系,做成弱依赖调用。

弱依赖调用可以用MQ的方式来实现解耦。即使下游出现问题,也不会影响当前模块。

技术选型

可以在适用性、优缺点、产品口碑、社区活跃度、实战案例、扩展性等多个方面进行全量评估,挑选出适合当前业务场景的中间件&数据库

前期的调研一定要充分,先对比、测试、研究,再决定,磨刀不误砍柴工。

冗余部署&故障自动转移

服务层的冗余部署很好理解,一个服务部署多个节点,有了冗余之后还不够,每次出现故障需要人工介入恢复势必会增加系统的不可服务时间。

所以,又往往是通过“自动故障转移”来实现系统的高可用。即某个节点宕机后需要能自动摘除上游流量,这些能力基本上都可以通过负载均衡的探活机制来实现。

涉及到数据层就比较复杂了,但是一般都有成熟的方案可以做参考。

一般分为一主一从、一主多从、多主多从。不过大致的原理都是数据同步实现多从,数据分片实现多主,故障转移时都是通过选举算法选出新的主节点后在对外提供服务(这里如果写入的时候不做强一致同步,故障转移时会丢失一部分数据)。具体可以参考Redis Cluster、ZK、Kafka等集群架构。

容量评估

  1. 每个系统,自己的最大处理能力是多少要做到清清楚楚。

在系统上线前需要对整个服务用到的机器、DB、cache都要做容量评估,机器容量的容量可以采用以下方式评估:

  1. 明确预期流量指标-QPS;
  2. 明确可接受的时延和安全水位指标(比如CPU%≤40%,核心链路RT≤50ms);

通过压测评估单机在安全水位以下能支持的最高QPS(建议通过混合场景来验证,比如按照预估流量配比同时压测多个核心接口);

最后就可以估算出具体的机器数量了。

DB和cache评估除了QPS之外还需要评估数据量,方法大致相同,等到系统上线后就可以根据监控指标做扩缩容了。

服务快速扩容能力&泄洪能力

现阶段不论是容器还是ECS,单纯的节点复制扩容是很容易的,扩容的重点需要评估的是服务本身是不是无状态的,比如:

  1. 下游DB的连接数最多支持当前服务扩容几台?

  2. 扩容后缓存是否需要预热?

  3. 放量策略

这些因素都是需要提前做好准备,整理出完备的SOP文档,当然最好的方式是进行演练,实际上手操作,有备无患。

泄洪能力一般是指冗余部署的情况下,选择几个节点作为备用节点,平时承担很小一部分流量,当流量洪峰来临时,通过调整流量路由策略把热节点的一部分流量转移到备用节点上。

对比扩容方案这种成本相对较高,但是好处就是响应快,风险小。

限流&熔断降级

限流

对于用户的重试行为,要适当的延缓。例如登录发现后端响应失败,再重新展现登录页面前,可以适当延时几秒钟,并展现进度条等友好界面。当多次重试还失败的情况下,要安抚用户。

过载保护很重要的一点,不是说要加强系统性能、容量,成功应答所有请求,而是保证在高压下,系统的服务能力不要陡降到0,而是顽强的对外展现最大有效处理能力。

前端系统有保护后端系统的义务,sla中承诺多大的能力,就只给到后端多大的压力。这就要求每一个前后端接口的地方,都有明确的负载约定,一环扣一环。

每个系统要有能力发现哪些是有效的请求,哪些是无效的请求。当过载发生时,该拒绝的请求(1、超出整个系统处理能力范围的;2、已经超时的无效请求)越早拒绝越好

中间层server对后端发送请求,重试机制要慎用,一定要用的话要有严格频率控制。

当雪球发生了,直接清空雪球队列(例如重启进程可以清空socket缓冲区)可能是快速恢复的有效方法。

流量整形也就是常说的限流,主要是防止超过预期外的流量把服务打垮,熔断则是为了自身组件或者依赖下游故障时,可以快速失败防止长期阻塞导致雪崩。

关于限流熔断的能力,开源组件Sentinel基本上都具备了,用起来也很简单方便,但是有一些点需要注意。

【自适应限流】限流阈值一般是配置为服务的某个资源能支撑的最高水位,这个需要通过压测摸底来评估。随着系统的迭代,这个值可能是需要持续调整的。如果配置的过高,会导致系统崩溃时还没触发保护,配置的过低会导致误伤。

熔断降级-某个接口或者某个资源熔断后,要根据业务场景跟熔断资源的重要程度来评估应该抛出异常还是返回一个兜底结果。

比如下单场景如果扣减库存接口发生熔断,由于扣减库存在下单接口是必要条件,所以熔断后只能抛出异常让整个链路失败回滚,如果是获取商品评论相关的接口发生熔断,那么可以选择返回一个空,不影响整个链路。

过载保护

异常有内外两种,一种是外部流量特别高,一种是某一个依赖故障导致系统响应变慢。

这里的课题应该包括:熔断、限流、超时控制、全局超时控制、服务降级(区分核心流程与非核心流程)

过载保护方案

这里推荐一种方案:在该系统每个机器上新增一个进程:interface进程。

Interface进程能够快速的从socket缓冲区中取得请求,打上当前时间戳,压入channel。

业务处理进程从channel中获取请求和该请求的时间戳,如果发现时间戳早于当前时间减去超时时间(即已经超时,处理也没有意义),就直接丢弃该请求,或者应答一个失败报文。

Channel是一个先进先出的通信方式,可以是socket,也可以是共享内存、消息队列、或者管道,不限。

Socket缓冲区要设置合理,如果过大,导致及时interface进程都需要处理长时间才能清空该队列,就不合适了。

建议的大小上限是:缓存住超时时间内interface进程能够处理掉的请求个数(注意考虑网络通讯中的元数据)。

参考:https://www.sohu.com/a/211248633_472869

资源隔离

如果一个服务的多个下游同时出现阻塞,单个下游接口一直达不到熔断标准(比如异常比例跟慢请求比例没达到阈值),那么将会导致整个服务的吞吐量下降和更多的线程数占用,极端情况下甚至导致线程池耗尽。引入资源隔离后,可以限制单个下游接口可使用的最大线程资源,确保在未熔断前尽可能小的影响整个服务的吞吐量。

说到隔离机制,这里可以扩展说一下,由于每个接口的流量跟ResponseTime都不一样,很难去设置一个比较合理的可用最大线程数,并且随着业务迭代,这个阈值也难以维护。

这里可以采用共享加独占来解决这个问题,每个接口有自己的独占线程资源,当独占资源占满后,使用共享资源,共享池在达到一定水位后,强制使用独占资源,排队等待。

这种机制优点比较明显就是可以在资源利用最大化的同时保证隔离性。

这里的线程数只是资源的一种,资源也可以是连接数、内存等等。

系统性保护

系统性保护是一种无差别限流,一句话概念就是在系统快要崩溃之前对所有流量入口进行无差别限流,当系统恢复到健康水位后停止限流。具体一点就是结合应用的 Load、总体平均 RT、入口 QPS 和线程数等几个维度的监控指标,让系统的入口流量和系统的负载达到一个平衡,让系统尽可能跑在最大吞吐量的同时保证系统整体的稳定性。

4.10 可观测性&告警

当系统出现故障时,我们首先需找到故障的原因,然后才是解决问题,最后让系统恢复。排障的速度很大程度上决定了整个故障恢复的时长,而可观测性的最大价值在于快速排障。其次基于Metrics、Traces、Logs三大支柱配置告警规则,可以提前发现系统可能存在的风险&问题,避免故障的发生。

4.11 变更流程三板斧

变更是可用性最大的敌人,99%的故障都是来自于变更,可能是配置变更,代码变更,机器变更等等。那么如何减少变更带来的故障呢?

可灰度

用小比例的一部分流量来验证变更后的内容,减小影响用户群。

产品特性设计和发布上,要尽量避免某个时刻导致大量用户集体触发某些请求的设计。发布的时候注意灰度。

可回滚

出现问题后,能有有效的回滚机制。涉及到数据修改的,发布后会引起脏数据的写入,需要有可靠的回滚流程,保证脏数据的清除。

可观测

通过观察变更前后的指标变化,很大程度上可以提前发现问题。 除了以上三板斧外,还应该在其他开发流程上做规范,比如代码控制,集成编译、自动化测试、静态代码扫描等。

五、总结

对于一个动态演进的系统而言,我们没有办法将故障发生的概率降为0,能做的只有尽可能的预防和缩短故障时的恢复时间。当然我们也不用一味的追求可用性,毕竟提升稳定性的同时,维护成本、机器成本等也会跟着上涨,所以需要结合系统的业务SLO要求,适合的才是最好的。

冗余

从根本上讲,解决高可用,只有一个方法,就是冗余。通过冗余更多的机器,来应对机器的硬件故障或者彼此之间的网络故障。

多机房部署

通过多机房部署来增加冗余。

多活的好处

  1. 响应时间短、提升用户体验
  2. 服务高可用
  3. 降低成本
  • 廉价的机器(非洲用户访问非洲的机器)
  • 流量的分摊(西方节日时,流量通过亚洲来分摊)

如何做到异地多活(必须要解决的一些问题)

  1. 接入层流量控制:用户默认访问哪个DC?什么时候做切换? 如何控制这个切换过程?

  2. 各DC业务逻辑一致:对于用户来说, 他的流量被调度前后,业务逻辑是一致的。 比如facebook上有一些内容对于亚洲用户是不可见的,不能因为亚洲用户的流量被迁移到了美洲机房,这个限制就失效了。

  3. 跨DC的实时数据同步与冲突处理:还是以fb为例, 如果访问非洲机房的用户A给访问南美洲机房的用户B的一个帖子点了赞, 那么B应该能及时收到相关的通知。这背后就依赖数据的实时同步。
    在多活情况下, 多DC的数据写入势必会引入数据的冲突, 比如facebook位于美东的的审核系统和位于东南亚的用户同时操作了一条帖子, 就会产生数据的冲突。

  4. 提供全球级别的强一致性
    对于大多数业务而言, 我们只需要最终一致性即可(比如点赞之类的计数)。 但是某些业务,需要全球的强一致保障(比如下
    单、支付之类的操作)。

同城多机房:延迟1~3ms

主要看接口的实现(如果有几十次的跨机房交互,这种是不可接受的)

实现相对比较简单

单机房写入;每一个机房近读取本机房的缓存与数据

如果数据发生变更,需要做两边机房缓存的清理,一般通过canal订阅数据库变更

同城多活示意图

国内异地多机房:延迟50ms以内

尽量减少跨机房的调用;而应该避免跨机房的数据库与缓存操作

多机房写入,按照用户或者其他业务维度来进行流量分割,使得一部分流量总是请求A机房,而另外的总是请求B机房。

根据业务需要,选择满足:
(1)一致性(如果选择了一致性,那么可用性便得不到100%保障)
(2)可用性(如果选择了可用性,那么一致性需要事后做补偿)

数据同步方式有两种:
(1)基于存储系统主从复制:同步redis、Mysql等
(2)基于消息队列:同步缓存、HBase的数据

异步多活示意图

跨国多机房:延迟在100~200ms

避免跨机房的调用,而只能做异步同步

每个SLA级别需要做的事情

感觉一下提高1个9,难度有多大。

三个9: 非核心业务可以容忍

四个9: 核心业务

运维值班体系、业务变更流程、故障处理流程、更加完善的系统故障排查工具、灰度发布(确保服务可回滚)

五个9: 必须让机器来自动处理恢复!

尽量思考故障发生后应该怎么办

考虑点:如何自动的发现故障、如何自动化的应对故障、系统运维-尽量避免故障发生

具体方法:failover(故障转移)、超时控制、服务降级、熔断限流

failover:

  • 完全对等
  • 非完全对等(例如存在主备节点,心跳,选择paxos, raft等)

什么是内存池

1.1 池化是在计算技术中经常使用的一种设计模式,其内涵在于:将程序中需要经常使用的核心资源先申请出来,放到一个池内,由程序自管理,这样可以提高资源的利用率,也可以保证本程序占有的资源数量,经常使用的池化技术包括内存池,线程池,和连接池等,其中尤以内存池和线程池使用最多。

1.2 内存池(Memory Pool)是一种动态内存分配与管理技术,通常情况下,程序员习惯直接使用new,delete,malloc,free等API申请和释放内存,这样导致的后果就是:当程序运行的时间很长的时候,由于所申请的内存块的大小不定,频繁使用时会造成大量的内存碎片从而降低程序和操作系统的性能。

内存池则是在真正使用内存之前,先申请分配一大块内存(内存池)留作备用。当程序员申请内存时,从池中取出一块动态分配,当程序员释放时,将释放的内存放回到池内,再次申请,就可以从池里取出来使用,并尽量与周边的空闲内存块合并。若内存池不够时,则自动扩大内存池,从操作系统中申请更大的内存池。

内存池解决什么问题?

  1. 内存碎片问题(解决glib、操作系统层面的内存碎片问题,提供内存利用率)
  2. 加速了内存的分配与回收,增加了系统性能。

先说第一个,

造成堆利用率很低的一个主要原因就是内存碎片化。如果有未使用的存储器,但是这块存储器不能用来满足分配的请求,这时候就会产生内存碎片化问题。内存碎片化分为内部碎片和外部碎片。

内碎片内部碎片是指一个已分配的块比有效载荷大时发生的。(假设以前分配了10个大小的字节,现在只用了5个字节,则剩下的5个字节就会内碎片)。内部碎片的大小就是已经分配的块的大小和他们的有效载荷之差的和。因此内部碎片取决于以前请求内存的模式和分配器实现(对齐的规则)的模式。

内部碎片问题

外碎片假设系统依次分配了16byte、8byte、16byte、4byte,还剩余8byte未分配。这时要分配一个24byte的空间,操作系统回收了一个上面的两个16byte,总的剩余空间有40byte,但是却不能分配出一个连续24byte的空间,这就是外碎片问题。

外部碎片问题

每一个场景都通用的解决方案 VS 为某一个场景的定制方案

底层逻辑

内存池设计

总体思路:

一次性向底层内存系统(依次为glibc、操作系统)申请一块大的内存慢慢使用,避免了频繁的向内存请求内存操作,提高内存分配的效率;由于向底层内存系统申请的内存块都是比较大的,所以能够降低(下一级别内存系统的)外碎片问题。

值得一提是的:内碎片问题无法避免,只能尽可能的降低。甚至,本层内存池需要通过额外的内存来管理内存,从宏观上讲(对于底层内存分配系统来讲),这是对内存的一种浪费,也可以称之为一种内部碎片。

例如,我每次只需要存储8个字节的数据,一共存储了1000次;显然这种的有效数据是8k; 但是实际上我管理着8k的数据,却使用了底层16k的内存,内存使用率只有50%。

所以,衡量一个内存池系统很重要的一方面就是:他的内存使用效率,他多大程度上降低了内存内碎片的产生。

  1. 内存池只能分配特定对象(数据结构)
  2. 充分考虑释考虑内存对象的生命周期(例如apache webserver)
  3. 考虑内存地址的对齐
  4. 考虑线程局部存储来避免不必要的锁冲突
  5. 除了考虑从大块内存上高效地将小内存划分出去,还要注意内存碎片问题。
  6. 当回收内存时要注意是否需要将相邻的空闲内存块进行合并管理。
    当内存池的空闲内存到达一定的阈值时,要合理地返还系统。
  7. 在多核处理器能够 scale

内存池的演变

最简单的内存分配器

做一个链表指向空闲内存,分配就是取出一块来,改写链表,返回,释放就是放回到链表里面,并做好归并。

注意做好标记和保护,避免二次释放,还可以花点力气在如何查找最适合大小的内存快的搜索上,减少内存碎片,有空你还可以把链表换成伙伴算法。

优点: 实现简单

缺点: 分配时搜索合适的内存块效率低,释放回归内存后归并消耗大,实际中不实用。

定长内存分配器

定长内存分配器即实现一个 FreeList,每个 FreeList 用于分配固定大小的内存块,比如用于分配 32字节对象的固定内存分配器,之类的。每个固定内存分配器里面有两个链表,OpenList 用于存储未分配的空闲对象,CloseList用于存储已分配的内存对象,那么所谓的分配就是从 OpenList 中取出一个对象放到 CloseList 里并且返回给用户,释放又是从 CloseList 移回到 OpenList。分配时如果不够,那么就需要增长 OpenList:申请一个大一点的内存块,切割成比如 64 个相同大小的对象添加到 OpenList中。这个固定内存分配器回收的时候,统一把先前向系统申请的内存块全部还给系统。

优点: 简单粗暴,分配和释放的效率高,解决实际中特定场景下的问题有效。

缺点: 功能单一,只能解决定长的内存需求,另外占着内存没有释放。

定长内存分配器

哈希映射的FreeList

池在定长分配器的基础上,按照不同对象大小(8,16,32,64,128,256,512,1k…64K),构造十多个固定内存分配器,分配内存时根据要申请内存大小进行对齐然后查H表,决定到底由哪个分配器负责,分配后要在内存头部的 header 处写上 cookie,表示由该块内存哪一个分配器分配的,这样释放时候你才能正确归还。如果大于64K,则直接用系统的 malloc作为分配,如此以浪费内存为代价你得到了一个分配时间近似O(1)的内存分配器。这种内存池的缺点是假设某个 FreeList 如果高峰期占用了大量内存即使后面不用,也无法支援到其他内存不够的 FreeList,达不到分配均衡的效果。

优点:这个本质是定长内存池的改进,分配和释放的效率高。可以解决一定长度内的问题。

缺点:存在内碎片的问题,且将一块大内存切小以后,申请大内存无法使用。多线程并发场景下,锁竞争激烈,效率降低。

范例:sgi stl 六大组件中的空间配置器就是这种设计实现的。

哈希映射的FreeList

并发内存池

第一层是Thread Cache,线程缓存是每个线程独有的,在这里设计的是用于小于64k的内存分配,线程在这里申请不需要加锁,每一个线程都有自己独立的cache,这也就是这个项目并发高效的地方。

第二层是Central Cache,在这里是所有线程共享的,它起着承上启下的作用,Thread Cache是按需要从Central Cache中获取对象,它就要起着平衡多个线程按需调度的作用,既可以将内存对象分配给Thread Cache来的每个线程,又可以将线程归还回来的内存进行管理。Central Cache是存在竞争的,所以在这里取内存对象的时候是需要加锁的,但是锁的力度可以控制得很小。

第三层是Page Cache,存储的是以页为单位存储及分配的,Central Cache没有内存对象(Span)时,从Page cache分配出一定数量的Page,并切割成定长大小的小块内存,分配给Central Cache。Page Cache会回收Central Cache满足条件的Span(使用计数为0)对象,并且合并相邻的页,组成更大的页,缓解内存碎片的问题。

并发内存池

一些常见的内存分配策略

如何分配定长记录

最大化内存使用率,最小化分配时间

  • bitmap来管理定长记录

内存使用率:bitmap需要额外内存,有一定浪费

时间分配效率:$O(1)$

  • FreeList来管理定长记录

内存使用率:100%
时间分配效率:$O(1)$

如何分配变长记录

变长记录进行“取整”操作,带来了内存碎片问题,我们只能减少,而无可避免。

为了减少内部碎片,分配规则按照 8, 16, 32, 48, 64, 80,并非2的幂次级

FreeList来管理“取整”之后的定长记录

内存使用率:有一定的内存碎片

时间分配效率:$O(1)$

以上分配方式都是基于page,当分配小于page的对象时会使用。

大的对象如何分配

首先,每一个线程有一块ThreadCache来管理从CentralCache分配的内存

由于ThreadLocal,所以从ThreadCache分配内存不需要加锁。

CentralCache通过page以及span来管理内存,当需要分配内存时,会通过spinlock来加锁保护。

span关键属性:是否空闲、startPageId, pageNum

page关键属性:是否空闲

通过Buddy系统来管理所有空闲的page, 而分配出去的Page通过RadixTree来管理起来。

通过RadixTree管理有两个好处:

  1. 节省内存,按需分配
  2. 查询性能也还不错,等价于树高度

参考:
https://www.cnblogs.com/wangshaowei/p/14287125.html

实现要点

  1. 分层(ThreadCache, CentralCache, PageCache)
  2. 线程局部存储来管理ThreadCache
  3. 通过基于hash的freelist来管理小对象
  4. 通过radix tree来管理分配出来的obj到span的映射,如此来方便做回收【对象地址到span的映射】
  5. 通过buddy算法来管理span, 保证用来分配内存的span尽可能的大(大的总是可以通过分裂成为小的,小的只有在合适的时机-内存连续才能合并成为大的)