消息队列

消息队列

为什么需要消息队列?

异步处理

  • 例子: 秒杀系统
1
如何利用有限的服务器资源,尽可能多地处理短时间内的海量请求   
  • 处理方案: 多步骤异步处理
1
2
3
4
一个秒杀请求的步骤: 风险控制;库存锁定;生成订单;短信通知;更新统计数据 (5步) 

决定秒杀成功的步骤:实际上只有风险控制和库存锁定这 2 个步骤
所以服务端可以在处理完前两步后就返回给用户结果。后面三步异步去处理

秒杀请求异步处理

  • 好处
    • 更快返回结果
    • 减少等待,自然实现了步骤之间的并发,提升系统总体的性能

流量控制

  • 例子: 秒杀系统
1
短时间海量的请求不会压垮秒杀服务
  • 处理方案: 消息队列堆积; 消息队列令牌桶
1
2
3
4
5
6
7
8
9
10
消息队列堆积: 
逻辑: 消息队列直接隔离 网关和秒杀服务, 网关将请求放入消息队列,秒杀服务按照自己的能力处理请求并返回结果,超时按秒杀失败算。
优点: 根据下游的处理能力自动调节流量,达到“削峰填谷”的作用
问题: 增加了系统调用链环节,导致总体的响应时延变长。上下游系统都要将同步调用改为异步消息,增加了系统的复杂度。

消息队列令牌桶: 预估出秒杀服务的处理能力, 以固定大小的消息队列实现一个令牌桶。
令牌桶逻辑: 单位时间放置固定数量的令牌,服务在请求之前必须先获取令牌。 保证单位时间处理的请求不会超过令牌数量,流量控制
逻辑:网关增加一个获取令牌的步骤,没有令牌就拒绝请求
有点:不破坏原有调用链

消息队列堆积流控

消息队列令牌桶流控

服务解耦

  • 例子: 电商
1
2
3
4
5
6
7
8
订单系统创建订单后: 
支付系统需要发起支付流程;
风控系统需要审核订单的合法性;
客服系统需要给用户发短信告知用户;
经营分析系统需要更新统计数据;
......

消息队列:每当订单创建,发送一份数据到消息队列。 下游业务不管怎么需求,订单系统不需要改变。

其他场景

  • 作为发布 / 订阅系统实现一个微服务级系统间的观察者模式;
  • 连接流计算任务和数据;
  • 用于将消息广播给大量接收者。

引入消息队列带来的问题

  • 引入消息队列带来的延迟问题;
  • 增加了系统的复杂度;
  • 可能产生数据不一致的问题。

如何选择消息队列?

选择标准

  • 开源:
    • 遇到问题可以自己改源码紧急避险。 而不是等待开发者不知道什么时候的下一版
  • 流行并有一定社区活跃度:
    • 只要不是很偏的使用场景,使用过程遇到的问题都能在网上找到解决方案
    • 流行的产品与周边生态系统会有一个比较好的集成和兼容,比如,Kafka 和 Flink,Flink 内置了 Kafka 的 Data Source,使用 Kafka 就很容易作为 Flink 的数据源开发流计算应用

及格的消息队列

  • 消息的可靠传递:确保不丢消息;
  • Cluster:支持集群,确保不会因为某个节点宕机导致服务不可用,当然也不能丢消息;
  • 性能:具备足够好的性能,能满足绝大多数场景的性能要求。

产品

  • RabbitMQ : 老牌消息队列
1
2
3
4
5
6
Erlang 语言编写的,最早是为电信行业系统之间的可靠通信设计的,也是少数几个支持 AMQP 协议的消息队列之一
优点: 轻量级、迅捷
问题:
对消息堆积的支持并不好。 当大量消息积压的时候,会导致 RabbitMQ 的性能急剧下降。
性能比较其他的较差: 支持每秒几万到十几万的数据。应用对性能要求高的不好用
是小众语言Erlang开发
  • RocketMQ
1
2
3
4
5
6
7
8
9
是阿里在 2012 年开源的消息队列产品,后来捐赠给 Apache 软件基金会,2017 正式毕业,成为 Apache 的顶级项目


优点:
性能,稳定性,可靠性 都不错, JAVA开发,有活跃的中文社区
时延低,对在线业务的响应时延做了很多的优化,大多数情况下可以做到毫秒级的响应
每秒钟大概能处理几十万条消息
缺点:
国产的消息队列,相比国外的比较流行的同类产品,在国际上还没有那么流行,与周边生态系统的集成和兼容程度要略逊一筹。
  • kafka
1
2
3
4
5
6
7
Kafka 最早是由 LinkedIn 开发,目前也是 Apache 的顶级项目。Kafka 最初的设计目的是用于处理海量的日志。

优点:
Kafka 与周边生态系统的兼容性是最好的没有之一,尤其在大数据和流计算领域,几乎所有的相关开源软件系统都会优先支持 Kafka。
每秒处理几十万消息
缺点:
异步批量思想带来的问题,同步收发消息的时延相较其他的较高。 因为当客户端发送一条消息的时候,Kafka 并不会立即发送出去,而是要等一会儿攒一批再发送,在它的 Broker 中,很多地方都会使用这种“先攒一波再一起处理”的设计
  • 其他消息队列
1
2
ActiveMQ: 老气的开源队列,已过期,社区不活跃
Pulsar: 新兴的开源消息队列产品,最早是由 Yahoo 开发,目前处于成长期,流行度和成熟度相对没有那么高。 可持续关注
  • 总结建议
1
2
3
对消息队列功能和性能都没有很高的要求,只需要一个开箱即用易于维护的产品, 选择 RabbitMQ
主要场景是处理在线业务,比如在交易系统中用消息队列传递订单,需要低延迟和金融级的稳定性, 选择 RocketMQ
需要处理海量的消息,像收集日志、监控信息或是前端的埋点这类数据,或是你的应用场景大量使用了大数据、流计算相关的开源产品,选择 Kafka

消息模型: 主题 和 队列

1
2
3
队列是 一种数据结构
队列是先进先出(FIFO, First-In-First-Out)的线性表(Linear List)。
在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为 rear)进行插入操作,在前端(称为 front)进行删除操作。

早期的消息队列

队列模型

1
2
3
4
5
按照 '队列' 数据结构进行设计的 。 消息是严格有序的

问题:
多个消费者, 竞争消费, 每个消费者只会收到其中一部分消息。 不能实现每个消费者消费全量数据
可行办法是: 为每个消费者创建一个单独的队列,让生产者发送多份。浪费资源,并且需要知道多少给消费者不能实现解耦

发布-订阅 模型

发布订阅模型

1
2
3
服务端存放消息的容器称为主题(Topic)

与 队列模型的区别: 一条消息能不能被消费多次

RabbitMQ 的消息模型

1
2
3
4
比较例外,依然坚持着 队列模型。
其解决多个消费者的问题方案: Exchange 模块
exchange位于 生产者和队列之间, 生产者不关心消息发给哪个队列,而是将消息发送给 Exchange,由 Exchange 上配置的策略来决定将消息投递到哪些队列中。
同一份消息如果需要被多个消费者来消费,需要配置 Exchange 将消息发送到多个队列,每个队列中都存放一份完整的消息数据,

RocketMQ 的消息模型

是标准的 发布 - 订阅 模型
rocketMQ消息模型

  • rocketMQ的 队列概念
1
2
3
4
5
6
7
8
9
10
11
12
如何确保不丢失?  请求 - 确认 机制
发布者 ( 发送消息等待服务端确认 ,没有确认就重发)
消费者 ( 收到消息后给服务端发送确认, 服务端没有收到确认就重发 )

请求-确认机制的 问题:
为了确保消息的有序性,在某一条消息被成功消费之前,下一条消息是不能被消费的。
即同一时刻只能有一个消费者消费消息。那么就没法通过水平扩展消费者的数量来提升消费端总体的消费性能

问题解决方案: 主题下增加 队列概念
每个主题包含多个队列,通过多个队列来实现多实例并行生产和消费
(即同一时刻,如果消费者1在处理队列1的数据,消费者2就可以拿队列2的数据进行消费)
注意: RocketMQ 只在队列上保证消息的有序性,主题层面是无法保证消息的严格顺序的。
  • 消费组
1
2
3
4
5
6
7
8
9
是通过消费组来体现 订阅者概念的

每个消费组都消费主题中一份完整的消息,不同消费组之间消费进度彼此不受影响
同一个消费组中的消费者,是竞争消费的关系,每个消费者负责消费组内的一部分消息

在topic中消息被消费的过程中, 由于消息需要被不同的组进行多次消费,
所以消费完的消息不会立即被删除,而是为每个消费组在每个队列上维护一个消费位置(Consumer Offset), 每次消费一条消息,位置往后移

注: 丢消息的原因大多是由于消费位置处理不当导致的。

kafka的消息模型

1
2
业务层面概念上与RocketMQ的消息模型基本一致。 
只是其队列的概念是 分区(Partition)

如何利用事务消息实现分布式事务?

解决 消息队列 生产者和消费者的 数据一致性问题

事务

1
2
3
4
A: 原子性,一个事务操作不可分割,要么成功,要么失败,
C: 一致性,在事务执行完成之前,读到的一定是更新前的数据,之后读到的一定是更新后的数据
I: 隔离性, 事务的执行不能被其他事务干扰
D: 持久性, 事务一旦完成提交,后续的其他操作和故障都不会对事务的结果产生任何影响。

分布式事务

1
2
3
4
5
6
7
8
9
对于分布式系统来说,严格的实现 ACID 这四个特性几乎是不可能的,或者说实现的代价太大,大到我们无法接受

所以在更多情况下,分布式事务指的是 在分布式系统中事务的不完整实现
如一致性的残血版本: 顺序一致性、最终一致性等

常见的分布式事务实现:
2PC(Two-phase Commit,也叫二阶段提交)、
TCC(Try-Confirm-Cancel)
事务消息

例子

事务消息适用的场景主要是那些需要异步更新数据,并且对数据实时性要求不太高的场景。

电商用户将购物车中的商品一起下单支付 (订单成功后清理购物车中这几个商品)
电商购物车商品下单清空

1
2
3
4
5
6
清理购物车 不是下单支付的主流程, 所以用消息队列异步删除
同时即使下单成功后几秒内商品没清理掉问题也不大(即可接收一定的时延)

1. 消费方(购物车系统): 接收到消息后清理购物车,如果失败,只要不确认消息等待消息队列重传即可。

2. 生产方(订单系统)(事务问题): 创建订单 和 发送消息 需要同时成功或失败

消息队列如何实现分布式事务?

Kafka 和 RocketMQ 都提供了事务相关功能。

消息队列实现事务

半消息: 在事务提交之前,对消费者不可见

  • 问题: 第4步,事务提交失败怎么办
1
2
3
4
5
6
7
kafka: 
粗暴解决,抛出异常,让用户自行处理,可以在业务代码中反复重试提交,直到提交成功,或者删除之前创建的订单进行补偿

RocketMQ:
增加了事务反查的机制来解决事务消息提交失败的问题
消息队列broker在收到半消息,然后没有收到提交或回滚请求,会定期去进行事务反查,然后根据事务反查结果进行下一步操作
(该机制,业务代码提供反查接口,如以上例子中,反查接口为:查询该订单在本地事务是否创建成功)

RocketMQ事务实现流程

如何确保消息不会丢失?

检测消息丢失的方法

用消息队列最尴尬的情况不是丢消息,而是消息丢了还不知道

1
2
3
1. IT 基础设施比较完善的公司,一般都有分布式链路追踪系统,使用类似的追踪系统可以很方便地追踪每一条消息

2. 如果没有, 一个比较简单的方法,利用消息队列的有序性来验证是否有消息丢失
  • 利用消息队列的有序性来验证是否有消息丢失
1
2
3
4
5
6
7
8
9
10
11
12
原理: 
在 Producer 端,给每个发出的消息附加一个连续递增的序号,然后在 Consumer 端来检查这个序号的连续性

用法:
拦截器机制(大多数消息队列的客户端都支持): 在生产者发消息之前的拦截器中将序号注入到消息中,在消费者收到消息的拦截器中检测序号的连续性 (不侵入业务,系统稳定后就可关闭)

问题:
1. 像 Kafka 和 RocketMQ 这样的消息队列,它是不保证在 Topic 上的严格顺序的,只能保证分区上的消息是有序的,所以我们在发消息的时候必须要指定分区,并且,在每个分区单独检测消息序号的连续性。
2. 如果 生产者是多实例的, 并不好协调多实例之间的消息发送顺序,需要每个 Producer 分别生成各自的消息序号,并且需要附加上 Producer 的标识,在 Consumer 端按照每个 Producer 分别来检测序号的连续性。

建议:
Consumer 实例的数量最好和分区数量一致,做到 Consumer 和分区一一对应,这样会比较方便地在 Consumer 内检测消息序号的连续性。

确保消息可靠传递

消息 生成,存储,消费 三阶段

  • 生产阶段:从消息在 Producer 创建出来,经过网络传输发送到 Broker 端。
1
通过最常用的请求确认机制,来保证消息的可靠传递  
  • 存储阶段: 消息在 Broker 端存储,如果是集群,消息会在这个阶段被复制到其他的副本上。
1
2
3
4
5
6
7
8
9
10
正常情况下,只要 Broker 在正常运行,就不会出现丢失消息的问题
对可靠性要求高的,一般可以对broker的配置:
1. 消息存储进磁盘再进行确认
2. 如果是集群模式,至少将消息发送到 2 个以上的节点,再给客户端回复发送确认响应。
```

- 消费阶段: Consumer 从 Broker 上拉取消息,经过网络传输发送到 Consumer 上。

```text
同生成阶段一样使用确认机制, 客户端从 Broker 拉取消息后,执行用户的消费业务逻辑,成功后,才会给 Broker 发送消费确认响应

如何处理 消费过程的重复消息?

消息服务质量

  • At most once : 至多一次,没有消息可靠性
  • At least once: 至少一次, 不允许丢消息,但是允许有少量重复消息出现。
  • Exactly once:恰好一次, 不允许丢失也不允许重复
1
大多数消息队列的消息质量是达到 至少一次

重复消息 解决方案: 用幂等性解决重复消息问题

1
2
3
4
在消费端,让我们消费消息的操作具备幂等性
幂等性: 任意多次执行所产生的影响均与一次执行的影响相同

从对系统的影响来看: At least once + 幂等消费 = Exactly once
  • 幂等方案一 : 数据库的唯一约束
1
2
例子: 将账户 X 的余额加 100 元 
设计: 在数据库中建一张转账流水表,先建账单再更新余额。 根据账单ID实现幂等
  • 幂等方案二: 为更新的数据设置前置条件
1
2
例子: 将账户 X 的余额加 100 元  
设计: 加前置条件, 如果账户 X 当前的余额为 500 元,将余额加 100 元
  • 幂等方案三: 记录并检查操作 (通用,但难)
1
2
3
4
5
6
给每条消息指定全局唯一的ID,消费时,先根据这个 ID 检查这条消息是否有被消费过,如果没有消费过,才更新数据,然后将消费状态置为已消费。

难点:
全局唯一ID (高可用,高性能)
检查消费状态,更新数据,设置消费状态 三个操作必须保持原子性
分布式, 多个消费者收到重复消息, 同时执行,操作两次。 ( 需要 分布式事务或锁 )

消息积压 如何处理?

1
消息积压原因: 一定是系统中的某个部分出现了性能问题,来不及处理上游发送的消息

优化性能来避免消息积压

1
2
3
4
5
对于性能的优化,主要体现在生产者和消费者这一收一发两部分的业务逻辑中
原因: 消息队列本身的处理能力要远大于业务系统的处理能力
一般业务系统需要处理的业务逻辑远比消息队列要复杂:
消息队列单个节点每秒可以处理几万至几十万的消息,而业务系统单个节点单个节点每秒钟可以处理几百到几千次请求,已经可以算是性能非常好的了
所以性能优化,一般是在消息的收发两端,让业务代码和消息队列配合,达到一个最佳的性能
  • 发送端性能优化
1
2
3
4
代码发送消息的性能上不去,需要优先检查一下,是不是发消息之前的业务逻辑耗时太多导致的

1. 并发: 如果是处理在线业务,将业务做成并发就可以了。RPC框架都是多线程支持多并发的,所以只需要提高业务并发就可以了
2. 批量: 如果是离线分析系统,不关心时延。适合批量从数据库读取,然后批量发送
  • 消费端性能优化
1
2
3
4
5
大部分的性能问题都出现在消费端,消费速度 < 生产速度(即性能倒挂),就会造成消息积压

暂时倒挂:只要后续消费端性能恢复,积压的消息就可以被消化
一直倒挂:要么消息队列的存储被填满无法提供服务,要么消息丢失,对于整个系统来说都是严重故障

系统设计: 一定要保证消费端的消费性能要高于生产端的发送性能,这样的系统才能健康的持续运行。

1
2
水平扩容消费者实例数量,必须同步扩容主题中的分区(也叫队列)数量,确保 Consumer 的实例数和分区数量是相等的  
因为队列消息有序性, 如果 Consumer 的实例数量超过分区数量,这样的扩容实际上是没有效果的。 对于消费者来说,在每个分区上实际上只能支持单线程消费。

elasticsearch学习

概述

功能

  • 分布式搜索引擎
  • 大数据近实时分析引擎

学习

  • 开发: 产品基本功能,底层原理,数据建模
  • 运维: 容量规划; 性能优化; 问题诊断; 滚动升级
  • 方案: 搜索与如何解决搜索; 大数据分析实践,理论知识实际场景

考试: elastic 官网

简介

1
2
3
restful 接口, 供各种语言使用
功能: 搜索,聚合

elastic 生态

  • logstash 开源服务端数据处理管道, 从不同源采集数据,转换数据,发送到不同存储库
1
2
3
4
5
6
7
8
9
实时解析和转换数据
从IP地址破译地理位置
将PII(个人身份信息)数据匿名,排除敏感字段
可扩展
200多个插件 (日志、数据库。。。)
可靠安全性
持久化队列保证至少送达一次
数据传输加密
监控
  • kibana : 可视化分析利器
1
2
数据可视化公司
基于 logstash 的工具, 2013被es收购
  • BEATS : 轻量数据采集器
1
2
3
4
有多种不同的beat
filebeat: 日志,文件
packetbeat: 网络数据抓包
。。。

场景

安装上手

安装

文件目录结构

  • bin : 脚本执行文件 包括: 启动,安装插件,运行统计数据等
  • config : 集群配置文件
  • JDK : java运行环境
  • data : 数据文件
  • lib : java类库
  • logs : 日志文件
  • modules : 包含所有ES模块
  • plugins : 所有已安装插件

启动

  • 物理机
1
2
3
4
5
6
7
/bin/elasticsearch 启动
/bin/elasticsearch-plugin 插件管理 install 安装

分布式
./elasticsearch -E node.name=node1 -E cluster.name=geektime -E path.data=node1_data -d
./elasticsearch -E node.name=node2 -E cluster.name=geektime -E path.data=node2_data -d
./elasticsearch -E node.name=node3 -E cluster.name=geektime -E path.data=node3_data -d
  • docker
1

入门

索引,文档,RESTAPI

文档

1
2
3
4
5
6
ES是面向文档的, 文档是可搜索数据的最小单位
文档会被 序列化为JSON格式,保存在ES中 (JSON对象由字段组成,每个字段有类型)
每个文档都有一个 唯一ID, 可以自己指定/或ES自动生成

类似数据的一条记录
JSON文档格式灵活,不需要预先定义格 (字段类型可以指定,也可以ES自动推算)(支持 数组/嵌套)

文档的元数据

1
2
3
4
5
6
7
8
ES用于标注文档的相关信息

_index 文档所属索引名称
_type 文档所属类型名称
_id 文档唯一ID
_source 文档原始JSON数据
_version 文档版本信息
_score 相关性打分

索引

1
2
3
4
5
文档的容器, 一类文档的集合
体现逻辑空间的概念: 索引有自己的Mapping定义,定义包含文档的字段名和字段类型

索引的Mapping : 定义文档字段的类型
索引的Settings : 定义不同的数据分布

Shard 则是体现 物理空间的概念: 索引中的数据分散在 shard 上

1
2
3
索引的不同语意: 
名称: 文档的集合, 可创建多个索引
动词: 保存一个文档到ES的过程 (在ES中是创建一个 倒排索引) (有B树索引 , 倒排索引)
  • 类型 type

    1
    2
    7.0 版本之前, 每个索引可以建立多个type, 每个type下就是同类文档
    7.0开始废弃不用,每个索引只能建立一个type (_doc)

REST API

1
集成各种语言

节点,集群,分片,副本

1
2
3
4
5
6
7
8
分布式系统的可用性和扩展性

高可用
服务可用: 允许有节点停止服务
数据可用: 部分节点丢失,不会丢失数据

可扩展:
请求量提升 / 数据不断增长 (将数据分布到所有节点上)

ES的分布式架构

1
2
3
4
5
6
7
不同的集群 通过不同名字区分  (默认名字 elasticsearch)
通过配置文件修改,或命令行 -E cluster.name=geektime 设定
一个集群可以有一个或多个节点

好处:
存储的水平扩容
提高系统的可用性,部分节点停止服务,整个集群服务不受影响

节点

1
2
3
4
5
节点: 一个 ES 的实例
本质就是一个JAVA进程
一台机器可运行多个ES进程,但生产环境一般建议一台机器一个实例
每个节点设置名字: 通过配置文件,或启动命令行 -E node.name=node1 指定
每个节点启动后,会分配一个UID,保存在 data 目录下
  • master-eligible nodes

    1
    2
    3
    4
    可以参加 选主流程,成为master 节点

    每个节点启动后: 默认就是一个 master eligible 节点
    可设置 node.master: false 禁止
  • master node

    1
    2
    当第一个节点启动时, 会将自己选举成 master 节点
    每个节点都保存了集群的状态, 只有 master 节点才能修改集群的状态信息 (任何节点都能修改会导致数据不一致)

    集群状态: 维护集群中的必要信息

    所有节点的信息

    所有索引 和 其相关的 Mapping 与 Setting 信息

    分片的路由信息

  • Data Node

    • 保存数据的节点,叫做Data Node, 负责保存分片数据 (在数据扩展 起重要作用)
  • Coordinating Node

    • 负责接受client的请求,将请求分发到合适节点,最终把结果汇聚到一起。
    • 每个节点默认起到 coordinating node 职责
  • Hot & Warm Node

    • 冷热节点, Hot节点配置高, warm配置低(可存储比较旧的数据)
    • 不同硬件配置的 Data Node, 用来实现 Hot & Warm 架构,降低集群部署的成本
  • Machine Learning Node

    • 负责跑 机器学习的 Job, 用来做异常检测
  • Tribe Node

    • 连接到不同的 ES集群,支持将这些集群当成一个单独的集群处理
    • 淘汰, 5.3开始使用 cross cluster search(跨集群搜索)

节点类型的配置: 生成环境中,应该设置单一角色的节点

节点类型 配置参数 默认值
master eligible node.master true
data Node.data true
ingest node.ingest True
coordinating only 每个节点默认都是coordinating节点。设置其他类型则为false
machine learning node.ml true (需 enable x-pack )

分片

  • 主分片 ( primary shard )

    1
    2
    3
    解决数据水平扩展的问题。  主分片可以将数据分布到集群内的所有节点之上
    一个分片 是一个运行的 lucene 的实例
    主分片数 在索引创建时指定, 后续不允许修改, 除非 Reindex
  • 副本 ( replica shard )

    1
    2
    3
    用以解决数据高可用的问题。 副本分片是主分片的拷贝
    副本分片数 可以动态调整
    增加副本数,还可在一定程度上提高服务的可用性 ( 读取的吞吐 )

分片的设置: 生成环境分片的设定,提前做好容量规划

1
2
3
4
5
6
分片数设置过小: 
后续无法增加及节点实现水平扩展
单个分片数据量太大,导致数据重新分配耗时
分片数设置过大, 7.0 开始, 默认主分片设置成1, 解决了 over-sharding 的问题
影响搜索结果的 相关性打分,影响 统计结果的准确性
单个节点上过多的分片,会导致资源浪费, 同时也会影响性能
1
2
3
4
5
6
查看 集群健康状况
GET _cluster/health

green - 主分片 和 副本 都正常
yellow - 主分片正常, 有副本分片未正常分配
red - 有主分片未能分配 (例: 当服务器磁盘容量超过 85% 时, 去创建了一个新的索引

文档的基本 CRUD

操作 命令 (type约定用_dec) 说明
Index PUT my_index/_doc/1 如果ID不存在,创建信息的。 已经存在则删除旧的创建新的,版本号增加
Create PUT my_index/_create/1 如果id已经存在,会失败
Read GET my_index/_doc/1
Update POST my_index/_update/1 文档必须已经存在, 更新只会对相应字段做增量修改
Delete DELETE my_index/_doc/1

创建说明

1
2
3
4
支持 自动生成文档ID 和 指定文档ID 两种方式

通过调用 POST /my_index/_doc (系统自动创建ID)
通过 PUT /my_index/_create/1 创建, 指定 _create , 如果ID文档已存在,操作失败

注意: create是创建新的, index 是 删除旧的创建新的, update是在旧的上面做增量修改

批量操作

1
批量操作, 减少 网络连接产生的开销,提高性能
  • Bulk API

    1
    2
    3
    4
    5
    6
    7
    8
    9
    POST _bulk
    支持一次API调用中, 对不同索引进行不同操作

    支持四种操作:
    Index, Creat, Update, Delete

    可以在 URI 中指定Index, 也可以再请求 payload 中进行
    操作中 单条操作失败, 并不会影响其他操作
    返回结果包括 每一条操作执行的结果
  • mget 批量读取

    1
    GET /_mget
  • msearch 批量查询

    1
    POST /_msearch

常见错误返回

1
2
3
4
5
无法连接:   网络故障或集群挂了
连接无法关闭: 网络故障或节点出错
429 : 集群过于繁忙
4xx : 请求体格式错误
500 : 集群内部错误

注意: 批量操作一次请求不宜过多

倒排索引

1
数据引擎中的 重要数据结构

书本对比理解

1
2
3
4
书本开始: 有目录,书本内容的索引    - 正排索引
根据目录中的 章节名称对应页码 查询具体内容

有一些书本最后: 有一些重要内容对应页码的索引页 - 倒排索引

搜索引擎中

1
2
正排索引: 文档ID 到 文档内容和单词 的关联
倒排索引: 单词 到 文档ID 的关系

一个例子:

image-20220330115421025

1
2
左边正排索引, 三篇 es书 的文档
右边倒排索引, 所有词条的索引,出现次数, 在哪个文档中哪个位置

倒排索引的核心组成

  • 单词词典( term dictionary ), 记录所有文档的单词, 记录单词 到 倒排列表 的关联关系
    • 单词词典很大, 通过 B+树 或 哈希拉链法实现, 满足高性能的插入和查询
  • 倒排列表 ( posting list ) , 记录了 单词对应的文档 的结合, 由倒排索引项组成
    • 倒排索引项(posting)
      • 文档ID
      • 词频 TF - 该单词在文档中出现的次数, 用于相关性评分
      • 位置(position) - 单词在文档中分词的位置。 用于 语句搜索
      • 偏移(offset)-记录单词的开始结束位置, 实现高亮显示

上面例子在 ES中的实现

image-20220330121209363

  • ES中 JSON文档每个字段都有自己的 倒排索引
  • 可以指定 对某些字段不做索引
    • 优点: 节省存储空间
    • 缺点: 字段无法被搜索

通过 analyzer 进行分词

1
2
3
4
5
6
analysis 文本分析: 把全文本转换为 一系列单词 (term / token)的过程, 也叫 分词

analysis 通过 analyzer 实现
可使用ES内置的分析器 / 或按需定制化分析器

除了 数据写入时 转换词条, 匹配Query语句时也需要用相同的分析器对查询语句进行分享
  • 分词器是专门 处理分词的组件, analyzer 由三部分组成 (按顺序执行)
    • character filters ( 针对原始文本处理, 例如去除html )
    • Tokenizer ( 按照规则切分为 单词 )
    • Token Filter ( 将切分的单词进行加工, 小写,删除 stopwords,增加同义词 )

ES内置分词器

  • standard analyzer - 默认分词器,按词切分,小写处理
  • simple - 按 非字母切分 (符号被过滤), 小写处理
  • stop - 小写处理, 停止词过滤(the,a,is)
  • whitespace - 按空格切分,不转小写
  • keyword - 不分词,直接将输入当做输出
  • patter - 正则表达式, 默认 \W+ (非字符分割)
  • language - 提供 30多种常见语言的分词器
  • customer - 自定义分词器

使用 _analyzer API

1
2
GET /_analyze        // 直接指定 analyzer 进行测试 对文本如何分词
{"analyzer":"standard", "text":""}
1
2
POST my_index/_analyze  // 指定索引字段, 查看 该字段如何进行分词
{"field":"", "text":""}
1
2
POST /_analyze	 // 自定义分词测试, 定义一个tokenizer,定义fileter, 组合后 是如何进行分词的
{"tokenizer":"standard","filter":[""], text:""}

中文分词 的难点

1
2
3
中文句子,切分成一个个词 (而不是字)
英文,单词有自然的空格作为分割
中文,在不同上下文有不同理解
  • ICU Analyzer

    1
    2
    安装plugin:  elasticsearch-plugin install analysis-icu
    提供unicode支持,更好支持亚洲语言
  • IK

    1
    支持自定义词库, 支持热更新分词字典
  • THULAC

1
清华大学自然语言处理 和 社会人文计算实验室的一套中文分词器

Search API

  • URI search
    • 在URL中使用查询参数
  • Request Body search
    • 使用 ES 提供的, 基于JSON格式的更加完备的 Query Domain Specific Language (DSL)
1
2
3
4
5
指定查询的索引
/_search 集群上所有的索引
/index1/_search 索引index1
/index1,index2/_search 索引 index1,2
/index*/_search 以index开头的索引

搜索的相关性

1
2
3
4
5
6
搜索是: 用户 和 搜索引擎 的对话
用户关心的是: 搜索结果的相关系
是否可以找到所有相关的内容
有多少不相关的内容被返回了
文档的打分是否合理
结合业务需求,平衡结果排名
  • Web 搜索
    • page rank 算法 (不仅仅是内容,更重要的是内容的可信度)
  • 电商搜索
    • 扮演 销售的角色
    • 提高用户购物体验,提升网站销售业绩,去库存

衡量相关性

学科 information Retrieval

1
2
3
precision (查准率) - 尽可能返回较少的无关文档
recall (查全率) - 尽可能返回较多的相关文档
ranking - 是否能够按照相关度进行排序

URI search 详解

1
2
3
4
5
通过 URI query 实现搜索
q指定查询语句: 使用
df 默认字段, 不指定会对所有字段进行查询
sort 排序 / from 和 size 用于分页
profile 查看 查询是如何被执行的
  • 指定字段 , 泛查询(会查询所有字段)

    • q=title:2021 / q=2021
  • Term, Phrase ( 查询 beautiful mind )

    • Term : 等效 OR
    • Phrase:等效 AND, 还要求 前后顺序一致
  • 分组 与 引号

    • title:(beautiful AND mind)
    • title=”beautiful mind”
  • 布尔操作

    • AND / OR / NOT 或者 && / || / ! (必须大写)
  • 分组

    • + 表示 must
    • - 表示 must_not
    • title:(+matrix -reloaded)
  • 范围查询

    • 区间表示: []闭区间, {}开区间
    • year:{2019 TO 2018}
  • 算数符号

    • year:>2010
  • 通配符查询 ( 效率低,占用内存大,不建议使用)

    • ? 代表一个字符, * 代表 0 或 多个字符
  • 正则表达

    • title:[bt]oy
  • 模糊匹配 与 近似查询

Request Body 与 Query DSL 介绍

  • 将查询语句通过 HTTP Request Body 发送给 ES
  • Query DSL
1
2
3
4
5
6
7
8
```

## Query string 与 Simple Query string

## Dynamic Mapping 和 常见字段类型

### Mapping

类似于 数据库中的 schema 的定义, 作用:
定义索引中 字段的名称
定义字段的数据类型
字段,倒排索引的相关配置 ( Analyzed or Not Analyzed, Analyzer )

Mapping 会把 JSON文档 映射成 Lucene 所需要的扁平格式

一个Mapping属于一个索引的Type ( 7.0 开始一个索引一个type )
每个文档都属于 一个索引的type
一个type 有一个 Mapping的定义
7.0开始, 不需要在mapping定义中指定type信息

1
2
3

- 什么是 Dynamic Mapping

写入文档时: 如果索引不存在,自动创建索引
ES自动根据文档信息推算出字段的类型

有时候会推算不对,如地理信息 (类型不对,会导致一些功能出错)

1
2
3
4
5

- 能否更改mapping的字段类型

- 新增字段


dynamic 设为true, 一旦有新增字段的文档写入, mapping也同时被更新
dynamic 设为 false, mapping不会更新,新增字段的数据无法被索引,但信息会出现在 _source 中
dynamic 设置为 strict, 文档写入失败
1
2
3

- 已有字段, 不在支持修改字段定义


lucene 实现的倒排索引, 一旦生成,不允许修改
改变字段类型, 必须 Reindex API, 重建索引
1
2
3
4
5
6
7

- 原因
- 修改字段的数据类型, 导致已被索引的数据无法被搜索
- 增加新的字段不会有影响

## 显示Mapping的设置与常见参数介绍


定义一个Mapping

PUT movies
{
“mappings”:{
// 定义mapping
}
}

建议:
参考API手册, 纯手写
步骤:
创建一个临时的index, 写入一些样本数据
通过访问 mapping API 获得临时文件的动态 Mapping 定义
进行修改后,使用该配置创建真正的索引
删除临时索引

1

控制当前字段是否被索引: 默认为true, 如果要设置为不可被搜索,字段添加设置 “index”:false

null_value, 需要对null值实现搜索: 只有keyword类型支持设定 “Null_value”:”NULL”

_all 在版本7中被 copy_to 所替代: copy_to 将字段的数值拷贝到目标字段(如 firstName,lastName 两个字段拷贝到 fullName,实现全名称搜索), copy_to 目标字段不出现在_source 中

数组类型: ES不提供专门的数组类型。 但任何字段,都可以包含多个相同类型的数值

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

- 控制 倒排索引 记录内容的配置
- docs - 记录 doc id
- freqs - 记录 doc id 和 term frequencies
- positions - 记录 doc id / term frequencies / term position
- offsets - 记录 doc id / term frequencies / term position / character offects
- Text 类型默认记录 postions, 其他默认为 docs
- 记录内容越多,占用存储空间越大

## 多字段特性 及 mapping中配置自定义 Analyzer

- 多字段特性
- 厂商名字实现精确匹配
- 增加一个 keyword 字段
- 使用不同的 analyzer
- 不同语言
- pinyin 字段的搜索 ( 中文实现拼音搜索)
- 支持为 搜索和索引 指定不同的analyzer

Excat values : 包括 数字 / 日期 / 具体一个字符串 (ES中的 keyword)(在索引时,不分词)
Full Text : 全文本,非结构化的文本树 (ES中的 text)

1
2
3

### 自定义分词

当ES自带的分词器 无法满足,可以自定义分词器。 通过自组合不同组件实现:
Character Filter :
在Tokenizer之前,对文本进行第一步处理。
可配置多个,会影响Tokenizer的 position 和 offset 信息
1. HTML strip - 去除 html 标签
2. Mapping - 字符串替换
3. Pattern replace - 正则匹配替换

Tokenizer : 
    将原始文本安装一定规则,切分为词 ( term or token )
    ES内置的: whitspace / standard / uax_url_email / pattern / keyword / path hierarchy
    可使用Java开发插件,实现自己的Tokenizer

Token Filter : 
    将Tokenizer 输出的单词( term ), 进行增加,修改,删除
    ES自带的 Token Filters:  lowercase(小写) / stop(停止词) / synonym(添加近义词)
1

创建索引时, 在 settings 中 自定义 analysis

1
2
3
4
5
6
7
8

## Index Template 和 Dynamic Template

- Index template - 帮助设置 Mappings 和 Settings, 并按照一定规则,自动匹配到新创建的索引之上
- 模板 仅在一个索引被新创建时,才会产生作用。 修改模板不会影响已创建的索引
- 可设置多个 索引 模板, 这些设置会被 "merge" 在一起
- 可指定 "order" 的数值, 控制 "merging"的过程

当一个索引 被新创建时
应用ES默认的 settings 和 mappngs
应用 order 数值低的 Index Template 中的设定
应用 order 数值高的 Index Template 中的设定,之前设定被覆盖
应用 用户指定的 Settings 和 Mappings,并覆盖之前模板中的设定

1
2
3
4
5
6

- Dynamic Template : 根据ES识别的数据类型,结合字段名称,动态设定 字段类型
- 所有 字符串类型设定成 keyword, 或关闭 keyword
- is 开头的字段都设置成 boolean
- long_ 开头的都设置成 long 类型

Dynamic Template 定义在 某个索引的 Mapping 中
Template有一个 名称
匹配规则是 一个数组
为匹配到字段设置 Mapping

1
2
3
4
5

## ES 聚合分析介绍

### 聚合 ( aggregation )

ES 除搜索外,提供 针对ES数据进行统计分析的功能
实时性高
Hadoop (T+1)
通过聚合,得到数据的概览,分析和总结全套的数据
高性能, 只需要一条语句,就可以从ES中得到分析结果 (无需客户端自己去实现分析逻辑)

1

kibana 可视化报表 - ES的聚合分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

- 聚合的分类
- Bucket Aggregation - 满足特定条件文档
- Term & Range ( 时间 / 年龄区间 / 地理位置 )
- Metric Aggregation - 一些数学运算, 可以对文档字段进行统计分析
- 基于数据集 计算结果, 支持字段上的计算,也支持脚本产生的结果上计算
- 数字计算,输出一个值: min / max / sum / avg / cardinality
- 输出多个值: stats / percentiles / percentile_ranks
- Pipeline Aggregation - 对其他聚合结果进行二次聚合
- Matrix Aggregation - 支持对多个字段的操作并提供一个结果矩阵

# 深入搜索

## 基于词项和基于全文的搜索

### 基于Term的查询

- Term : 表达语意的最小单位。 搜索 和 利用统计语言模型进行自然语言处理 都需要处理Term
- 特点:
- Term Level Query: Term / Range / Exists / Prefix / wildcard
- Term查询,对输入不做分词。 在倒排索引中查找准确的词项,并为每个包含该词项的文档进行 相关度算分
- 可以通过复合查询 Constant Score 将查询转换成一个 Filtering, 跳过算分,并可以有效利用缓存, 提高性能

### 基于全文的查询

- Match Query / Match Phrase Query / Query String Query
- 特点:
- 索引 和 搜索 时都会进行分词, 查询字符串先传递到一个合适的分词器,生成一个供查询的词项列表
- 查询过程,先 对输入的查询进行分词, 然后每个词项逐个进行底层的查询打分,最终将结果汇总。 为每个文档生成一个算分。

## 结构化搜索

- 对 结构化数据 的搜索
- 日期,布尔,数字 都是结构化的。 有精确的格式,可以对这些格式进行逻辑操作。 范围,大小等
- 文本也可以结构化
- 可以做 精确匹配 或者 部分匹配 ( term查询 / prefix前缀查询 等)
- 结构化结果只有 "是" 或 "否" 两个值。 根据场景需要决定是否需要打分

## 搜索的相关性算分

### 相关性

搜索的相关性算分: 描述 文档 和 查询语句 匹配的程度。 ES会对每个匹配查询条件的结果进行算分 _score
打分的本质是 排序, 把最符合用户需求的文档排在前面。 ES5之前的默认算分采用 TF-IDF, 现在采用 BM25

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

### TF-IDF

- 词频 TF ( Term Frequency ) : 检索词在一篇文档中出现的频率
- 检索词出现的次数 除以 文档的总字数
- 度量一条查询和结果文档相关性的简单方法: 将搜索中每个词的TF进行相加
- Stop Word (停止词) , 如"的", 在文档中出现很多次,但对贡献相关度几乎没有用处,不应考虑它们的TF

- 逆文档频率IDF ( Inverse Document Frequency ) :

- DF: 检索词在所有文档中出现的频率
- 而IDF, 简单说就是公式: log(全部文档数 / 检索词出现过的文档总数)

- TF-IDF 本质上就是将 TF 求和 变成了 加权求和

- 例子: 搜索 区块链的应用 ( 分词为: 区块链 的 应用 三个词)

  TF(区块链)*IDF(区块链) + TF(的)*IDF(的) + TF(应用)*IDF(应用)
  
1
2
3

### BM25

和经典的TF-IDF, 当TF无限增加时, BM25算分会趋于一个数值

1
2
3

### 定制 Similarity

PUT /my_index
{
“settings”:{
“similarity”:{
“custom_similarity”:{
“type”:”BM25”,
“b”:0,
“k1”:2
}
}
}
}
K 默认值是 1.2, 数值越小, 饱和度越高
b 默认值是 0.75(取值范围0-1), 0代表禁止 Normalization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

### Boosting Relevance

- Boosting 控制相关度的一种手段 ( 索引,字段 或查询子条件)
- 含义:
- boost > 1 时, 打分相关度 相对性的提升
- 0 < boost < 1 , 打分权重 降低
- boost < 0 , 贡献负分

## Query & Filtering 与 多字符串多字段查询

- 高级搜索的功能: 支持多选 文本 输入, 针对多个字段进行搜索
- 搜索引擎 一般也提供 基于时间,价格等条件的过滤
- 在ES中, 有 Query 和 Filter 两种不同的 Context
- Query Context:相关性算分
- Filter Context: 不算分,利用缓存,更好性能

### bool 查询

- 一个 或者 多个 查询子句的组合 ( 4种子句)
- 相关性 除了全文本检索, 也使用 yes|no 的子句, 匹配子句越多,评分越高
- 子查询顺序任意, 可嵌套多个查询
- must : 必须匹配,贡献算分
- should : 选择性匹配, 贡献算分
- must_not :必须不匹配, 是 filter context, 不贡献算分
- filter : 过滤条件,必须匹配, 是 filter context, 不贡献算分

- 结构化查询 : 包含而不是相等 的问题 (多值字段 )
- 增加一个 count 字段进行计数

- 查询语句的结构, 对相关度算分的影响
- 同一层级的竞争字段,具有相同的权重
- 通过 嵌套bool查询,可以改变 对算分的影响

## 单字符串多字段查询

- should 算分过程
- 查询 should 语句中的两个查询
- 加和 两个查询的评分
- 乘以 匹配语句的总数
- 除以 所有语句的总数

### Dis Max Query

两字段竞争,不应 将分数简单叠加,应该找到单个最佳匹配的字段的评分

1
2
3
4
5
6
7

- dis max query
- 将任何 与 任一查询匹配的文档作为结果返回。 采用字段上最匹配的评分作为 最终评分返回
- 通过 tie_breaker 参数调整,将其他匹配语句的评分与tie_breaker 相乘,最终结果为 将最佳匹配评分与tie算法相加 (tie_breaker 介于 0-1, 0:使用最佳匹配,1:所有语句同等重要)

### Multi Match

三种场景:
最佳字段(Best Fields): 当字段之间相互竞争又相互关联。 评分来自 最匹配字段
多数字段(Most Fields):
处理英文内容时,常见手段:
在主字段(采用户English Analyzer),抽取词干,加入同义词,以匹配更多的文档
相同的文本,加入子字段(采用Standard Analyzer), 以提供更加精确的匹配
其他字段作为匹配文档提高相关度的信号。匹配字段越多则越好
混合字段(cross Field)
对某些实体, 例如人名,地址等, 需要在多个字段中确定信息,单个字段只能作为整体的一部分。 希望在任何这些字段中找到尽可能多的词

1

POST my_index/_search
{
“query”: {
“multi_match”: {
“type”: “best_fields”,
“query”: “Quick pets”,
“fields”: [“title”,”body”],
“tie_breaker”: 0.2,
“minimum_should_match”: “20%”
}
}
}

1

跨字段搜索
无法使用 Operator
可以用 copy_to 解决,但是需要额外的存储空间

cross_fields 类型的 multi_match
支持 Operator
与 copy_to 相比, 优势: 在搜索时为单个字段提升权重

1
2
3
4
5

## 多语言 及 中文分词与检索

### 多语言

不同索引使用不同语言
同一索引中,不同字段使用不同语言
一个文档的一个字段内混合不同的语言

挑战:
词干提取
不正确的文档频率 - 英文为主的文字,德文算分高(稀有)
需要判断用户搜索时使用的语言,语言识别( compact language detector) - 根据语言查询不同索引

技巧:
归一化词元 / 单词词根抽取 / 同义词 / 拼写错误

1
2
3
4
5
6
7

### 中文分词

- 常用中文分词器: hanLP / IK / pinyin

- 演变

  1. 查字典, (有的词就标示,复合词就找最长的。 不认识就分割成单字)
  2. 最小词数的分词理论 ( 一句话分词数量最少的词串, 二义性分割不行)
  3. 统计语言模型 ( 解决二义性问题, 将中文分词错误率降低。 概率问题: 动态规划+利用维特比算法 )
  4. 基于统计的机器学习算法 ( HMM,CRF,SVM,深度学习等算法, 基本思路是对汉字进行标注训练。。。)
    1
    2
    3
    4
    5

    ## Search Template 和 Index Alias 查询

    ### search Template - 解耦程序 & 搜索DSL

    ES的查询语句 对 相关性算分 / 查询性能 都至关重要

在开发初期, 可以明确查询参数,但往往还不能最终定义查询的DSL的具体结构
通过 search Template 定义一个 Contract

各司其职,解耦
开发人员 / 搜索工程师 / 性能工程师

1

创建一个 search Template

POST _scripts/tmdb
{
“script”: {
“lang”: “mustache”,
“source”: {
“_source”: [
“title”,”overview”
],
“size”: 20,
“query”: {
“multi_match”: {
“query”: ““,
“fields”: [“title”,”overview”]
}
}
}
}
}

1

搜索工程师 维护 search Template
开发工程师 使用 Template 查询, 不用感知具体的查询语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

### Index Alias

- 别名: 实现零停机运维

## 综合查询: function score query 优化算分

- 算分与排序
- ES默认会以 文档的相关度算法进行排序
- 可以通过指定 一个或多个字段进行排序
- 使用相关度算分(score)排序,不能满足某些特定条件
- 无法针对相关度,对排序实现更多控制

### Function Score Query

可以在查询结束后, 对每一个匹配的文档进行 一系列的重新算分, 根据新生成的分数进行排序

默认计算分值的函数:
Weight: 为每个文档设置一个简单而不被规范化的权重

Field Value Factor: 使用该数值修改 _score, 例如将 "热度","点赞数"作为算分的参考因素。
    新的算分=老的算分*热度 (问题,热度数值差异很大 0和10000,结果分数差异过大)
    使用 modifier 平滑曲线(使用各种 公式计算):如log1p, 则 新的算分 = 老的算分 * log(1+热度)
    
Random Score: 为每一个用户使用一个不同的 随机算分结果 
    (网站广告提高展现率, 让每个用户看到不同的随机排名,但是也希望同一个用户访问时,结果的相对顺序保持一致)
    
衰减函数: 以某个字段的值为标准,距离某个值越近,得分越高

Script Score: 自定义脚本完全控制所需逻辑
1
2
3
4
5
6
7
8
9
10
11

## Suggester

```text
用户在输入过程 自动补全或者纠错的功能
在ES中 suggester API 实现
原理: 将输入的文本分解为token,然后在索引的字典里查找相似的term返回

ES中设计了 4中类别的 Suggester
Term & Phrase Suggester
Complete & Context Suggester

kubernetes学习

容器概念入门

容器,其实是一种特殊的进程而已

容器技术核心

通过 约束 和 修改进程的动态表现, 为其创造出一个 ‘边界’

1
2
3
4
总结: 
1. 容器只是特殊的进程, 真正对隔离环境负责的是宿主机操作系统本身
2. 隔离技术: 使用 cgroups技术 制造约束(限制资源) , 使用 namespace技术 修改进程视图
3. 隔离不彻底: 使用的都是宿主机的内核,无法namespace化的资源多容器公用

cgroups : control group

1
2
3
4
5
6
制造约束。 
Linux 内核中用来为进程设置资源限制, 包括 CPU、内存、磁盘、网络带宽等等
理解: 一个子系统目录加上一组资源限制文件的组合



namespace

1
2
3
4
5
6
7
8
9
10
修改进程视图
namespace技术 只是修改了应用进程看待整个计算机“视图”,即它的“视线”被操作系统做了限制,只能“看到”某些指定的内容

linux中,创建一个新的进程用 clone(), 其中有多个可选参数。 如pid进程号,每次创建可选择创建新的PID namespace,则不同namespace之间就看不到进程号

启动容器,其实还是启动的进程,只是为这个进程加了很多 namespace参数
对于宿主机来说,这些被“隔离”了的进程跟其他进程并没有太大区别。

linux 提供的namespace:
PID, Mount、UTS、IPC、Network 和 User 这些,用来对各种不同的进程上下文进行“障眼法”操作
  • 虚拟机Hypervisor 和 Docker Engine
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Docker Engine 不对应用进程的隔离环境负责, 真正对隔离环境负责的是宿主机操作系统本身

虚拟机消耗大,本身启动就需要一定的内存, 对宿主机进行系统调用又不可避免需要经过虚拟化软件处理和拦截。 计算,网络,磁盘IO消耗都很大
而容器化的应用,本质还是一个普通进程,由宿主机操作系统统一管理,性能消耗都是忽略不计


容器优点:
“敏捷”和“高性能”

缺点: 隔离不彻底
容器只是运行在宿主机上的一种特殊的进程,多个容器之间使用的还是同一个宿主机的操作系统内核
所以跨内核跑容器是不可能的
在 Linux 内核中,有很多资源和对象是不能被 Namespace 化的,最典型的例子就是:时间。
所以修改了宿主机时间,所有容器的时间都会变

算法学习

框架思维

数据结构的存储方式

只有两种:数组(顺序存储)和链表(链式存储)

1
2
数组和链表 是 结构基础
散列表、栈、队列、堆、树、图等等各种数据结构 都是链表或者数组上的特殊操作, 是 上层建筑

数据结构的操作

遍历 + 访问 (在不同的应用场景,尽可能高效地增删查改)

  • 方式
1
2
3
4
线性的
for/while 为代表
非线性的
递归为代表

算法和数据结构

数据结构是工具,算法是通过合适的工具解决问题的方法

1
2
算法是利用数据结构进行显式利用
算法是利用数据结构进行显式利用无论怎样利用数据结构,多么高大上的算法,其解法都逃不出第二点中相应的框架

总结

1
2
3
学会从框架上看问题,而不要纠结于细节问题
即: 不要纠结 i 到底应该加到 n 还是加到 n - 1
而: 应该直接知道是使用什么数据结构进行如何 遍历和访问

趣谈网络协议

通信协议综述

为什么要学习网络协议?

1
2
要打造互联网世界的通天塔,只教给一台机器做什么是不够的,你需要学会教给一大片机器做什么。这就需要网络协议
通过网络协议,才能使一大片机器互相协作、共同完成一件事。

网络协议列举

网络分层

1
2
3
为什么分层: 复杂的程序都分层,程序设计要求

层层封装: 只要是在网络上跑的包,都是完整的。可以有下层没上层,绝对不可能有上层没下层。

ifconfig 命令

1
2
3
4
5
6
7
8
linux 查看ip地址: ifconfig,   ip addr   (工具: net-tools 和 iproute2  的故事)

大部分的网卡都会有一个 IP 地址, 不是必需
IP 地址是一个网卡在网络世界的通讯地址, 相当于门牌号, 不可冲突

例:
10.100.122.2 就是一个 IP 地址。这个地址被点分隔为四个部分,每个部分 8 个 bit,所以 IP 地址总共是 32 位
因为不够用,于是就有了 IPv6,也就是上面输出结果里面 inet6 fe80::f816:3eff:fec7:7975/64。这个有 128 位

当初设计哪知道现在会有这么多计算机, 本来 32 位的 IP 地址就不够,还被分成了 5 类
32位IP地址分类

ABC类IP最大主机数

1
2
3
4
5
对于 A、B、 C 类主要分两部分,前面一部分是网络号,后面一部分是主机号

问题:
C 类地址能包含的最大主机数量实在太少了,只有 254 个
而 B 类地址能包含的最大主机数量又太多了, 一般企业达不到6万多台机器, 闲着浪费
  • 无类型域间选路(CIDR)
1
2
3
4
5
6
7
8
9
10
将 32 位的 IP 地址一分为二,前面是网络号,后面是主机号
例:
10.100.122.2/24
这种地址表示形式,就是 CIDR。后面 24 的意思是,32 位中,前 24 位是网络号,后 8 位是主机号

伴随着 CIDR 存在的:
一个是广播地址,10.100.122.255。如果发送这个地址,所有 10.100.122 网络里面的机器都可以收到
另一个是子网掩码,255.255.255.0

将子网掩码和 IP 地址按位计算 AND,就可得到网络号: 如上面例子网络号就是: 10.100.122.0
  • 公有 IP 地址和私有 IP 地址
1
2
3
4
5
6
7
日常工作现在都是 CIDR, 几乎不用划分 A 类、B 类或者 C 类.

私有IP: 是一个组织内部的, 公网之间可以重复
公有IP: 是分配的的,需要买

在ABC类IP地址中, 私有IP在上图中
CIDR中常见的是 /24 的私有IP, 如: 192.168.0.x , 一般私有网络的出口地址,像路由器是 192.168.0.1, 而192.168.0.255是广播地址
  • D类组播地址
1
使用这一类地址,属于某个组的机器都能收到。

ip addr 的继续分析

1
2
3
4
5
6
7
8
9
10
11
12
13
root@test:~# ip addr
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default
link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
inet 127.0.0.1/8 scope host lo
valid_lft forever preferred_lft forever
inet6 ::1/128 scope host
valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state UP group default qlen 1000
link/ether fa:16:3e:c7:79:75 brd ff:ff:ff:ff:ff:ff
inet 10.100.122.2/24 brd 10.100.122.255 scope global eth0
valid_lft forever preferred_lft forever
inet6 fe80::f816:3eff:fec7:7975/64 scope link
valid_lft forever preferred_lft forever
1
2
3
4
5
6
在 IP 地址的后面有个 scope
对于 eth0 这张网卡来讲,是 global,说明这张网卡是可以对外的,可以接收来自各个地方的包。
对于 lo 来讲,是 host,说明这张网卡仅仅可以供本机相互通信。

lo 全称是 loopback,又称环回接口,往往会被分配到 127.0.0.1 这个地址。
这个地址用于本机通信,经过内核处理后直接返回,不会在任何网络中出现。
  • MAC 地址

在 IP 地址的上一行是 link/ether fa:16:3e:c7:79:75 brd ff:ff:ff:ff:ff:ff,这个被称为 MAC 地址,是一个网卡的物理地址,用十六进制,6 个 byte 表示

1
2
3
4
5
6
7
8
9
10
号称 全局唯一, 不会有两个网卡有相同的 MAC 地址,而且网卡自生产出来,就带着这个地址

误解:MAC地址唯一,那整个互联网的通信,全部用 MAC 地址好了,只要知道了对方的 MAC 地址,就可以把信息传过去。

正解: 一个网络包要从一个地方传到另一个地方,除了要有确定的地址,还需要有定位功能。 而有门牌号码属性的 IP 地址,才是有远程定位功能的

MAC 地址更像是身份证,是一个唯一的标识

MAC 地址是有一定定位功能的,只不过范围非常有限, 局限在一个子网里面。
例: 从 192.168.0.2/24 访问 192.168.0.3/24 是可以用 MAC 地址的。
  • 网络设备的状态标识

<BROADCAST,MULTICAST,UP,LOWER_UP> 是干什么的?这个叫做 net_device flags,网络设备的状态标识。

1
2
3
4
UP 表示网卡处于启动的状态;
BROADCAST 表示这个网卡有广播地址,可以发送广播包;
MULTICAST 表示网卡可以发送多播包;
LOWER_UP 表示 L1 是启动的,也即网线插着呢。
  • MTU1500

MTU1500 是指什么意思呢?是哪一层的概念呢?最大传输单元 MTU 为 1500,这是以太网的默认值。

1
2
3
MTU 是二层 MAC 层的概念。
MAC 层有 MAC 的头,以太网规定正文部分不允许超过 1500 个字节。
正文里面有 IP 的头、TCP 的头、HTTP 的头。如果放不下,就需要分片来传输。
  • qdisc 排队规则

qdisc pfifo_fast 是什么意思呢?qdisc 全称是 queueing discipline,中文叫排队规则。

1
2
3
4
5
6
7
8
内核如果需要通过某个网络接口发送数据包,它都需要按照为这个接口配置的 qdisc(排队规则)把数据包加入队列

队列类型:
pfifo : 最简单, 先进先出
pfifo_fast :
它的队列包括三个波段(band)。在每个波段里面,使用先进先出规则。
三个波段(band)的优先级也不相同。band 0 最高,band 2 最低。 如果 band 0 里面有数据包,系统就不会处理 band 1 里面的数据包
数据包是按照服务类型(Type of Service,TOS)被分配到三个波段(band)里面的。TOS 是 IP 头里面的一个字段,代表了当前的包是高优先级的,还是低优先级的

总结

  • IP 是地址,有定位功能;MAC 是身份证,无定位功能;
  • CIDR 可以用来判断是不是本地人;
  • IP 分公有的 IP 和私有的 IP

DHCP 和 PXE : IP怎么来? 怎么没?

如何配置IP地址

使用 net-tools

1
2
$ sudo ifconfig eth1 10.0.0.1/24
$ sudo ifconfig eth1 up

使用 iproute2:

1
2
$ sudo ip addr add 10.0.0.1/24 dev eth1
$ sudo ip link set up eth1
  • 思考: 192.168.1.6 就在你这台机器的旁边,甚至是在同一个交换机上,而你把机器的地址设为了 16.158.23.6。 为什么ping不通?
1
2
3
4
5
6
7
8
9
原则: 只要是在网络上跑的包,都是完整的,可以有下层没上层,绝对不可能有上层没下层。

逻辑分析:
它有自己的源 IP 地址 16.158.23.6,也有目标 IP 地址 192.168.1.6,但是包发不出去,这是因为 MAC 层还没填

Linux 首先会判断,要去的这个地址和我是一个网段的吗,或者和我的一个网卡是同一网段的吗?
只有是一个网段的,它才会发送 ARP 请求,获取 MAC 地址
如果不是, 这是一个跨网段的调用,它便不会直接将包发送到网络上,而是企图将包发送到网关。
而linux中网关的配置, 网关要和当前的网络至少一个网卡是同一个网段的
1
不同系统的配置文件格式不同,但是无非就是 CIDR、子网掩码、广播地址和网关地址。

动态主机配置协议(DHCP)(Dynamic Host Configuration Protocol)

1
2
3
他只需要配置一段共享的 IP 地址。
每一台新接入的机器都通过 DHCP 协议,来这个共享的 IP 地址里申请,然后自动配置好就可以了。
等人走了,或者用完了,还回去,这样其他的机器也能用。
  • DHCP 工作方式 新机器加入网络
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
第一步. client进行 DHCP Discover ( 广播 Boot request,我的 MAC 地址是这个,我还没有 IP)
新机器使用 IP 地址 0.0.0.0 发送了一个广播包,目的 IP 地址为 255.255.255.255。广播包封装了 UDP,UDP 封装了 BOOTP。 (其实 DHCP 是 BOOTP 的增强版)

第二步. DHCP server 进行 DHCP offer
MAC地址唯一,新MAC地址来了,分配IP地址,并为他保留 。 仍然使用广播地址作为目的地址

第三步,client 进行 DHCP request
新机器得到 offer, 如果有多个DHCP server, 甚至得到多个offer
一般选择最新到达的offer,然后向网络发送一个 DHCP Request 广播数据包,包中包含客户端的 MAC 地址、接受的租约中的 IP 地址、提供此租约的 DHCP 服务器地址等
告诉所有 DHCP Server 它将接受哪一台服务器提供的 IP 地址,告诉其他 DHCP 服务器,谢谢你们的接纳,并请求撤销它们提供的 IP 地址,以便提供给下一个 IP 租用请求者
由于还没有得到 DHCP Server 的最后确认,客户端仍然使用 0.0.0.0 为源 IP 地址、255.255.255.255 为目标地址进行广播

第四步, server 进行 DHCP ACK
当 DHCP Server 接收到客户机的 DHCP request 之后,
会广播返回给客户机一个 DHCP ACK 消息包,表明已经接受客户机的选择,并将这一 IP 地址的合法租用信息和其他的配置信息都放入该广播包,发给客户机,欢迎它加入网络大家庭。
广播也是告诉其他server, 该client在我这个server租了IP
  • IP地址的收回和续租
1
2
3
续租: 
客户机会在租期过去 50% 的时候,直接向为其提供 IP 地址的 DHCP Server 发送 DHCP request 消息包
客户机接收到该服务器回应的 DHCP ACK 消息包,会根据包中所提供的新的租期以及其他已经更新的 TCP/IP 参数,更新自己的配置

自动安装操作系统

  • 预启动执行环境(PXE)

场景: 数据中心里面的管理员可能一下子就拿到几百台空的机器,一个个安装操作系统,会累死的

1
2
3
4
5
6
7
8
9
10
11
办法: 安装的操作系统放在一个服务器上,让客户端去下载。 
问题: 没有操作系统,客户端放哪里?
解决:
操作系统的启动过程: 首先启动BIOS, 读取硬盘的 MBR 启动扇区,将 GRUB 启动起来;然后将权力交给 GRUB,GRUB 加载内核、加载作为根文件系统的 initramfs 文件;然后将权力交给内核;最后内核启动,初始化整个操作系统
在整个过程中, 只能放在BIOS启动后,因为没安装系统之前,连启动扇区都没有
这个过程叫做预启动执行环境(Pre-boot Execution Environment),简称 PXE。
PXE 协议分为客户端和服务器端,由于还没有操作系统,只能先把客户端放在 BIOS 里面。当计算机启动时,BIOS 把 PXE 客户端调入内存里面,就可以连接到服务端做一些操作了

首先 PXE 的客户端启动起来,发送一个 DHCP 的请求,让 DHCP Server 给它分配一个地址。PXE 客户端有了自己的地址
怎么知道 PXE 服务器在哪里呢? 在DHCP server 中配置 next-server,指向 PXE 服务器的地址,配置初始启动文件位置 filename
然后TFTP,从 PXE服务器下载

PXE 工作过程

PXE工作过程

底层网络知识详解: 从二层到三层

从 物理层 到 MAC层 : 学校宿舍几台电脑之间联网

物理层

1
2
3
4
5
6
7
8
9
使用路由器联网,是在第三层         

物理层联网:
两台电脑:
在物理层联网, 一根网线连接两台电脑的网口
但普通的网线不行,水晶头要做交叉线,就是所谓的 1-3、2-6 交叉接法。 (水晶头的第 1、2 和第 3、6 脚,它们分别起着收、发信号的作用。将一端的 1 号和 3 号线、2 号和 6 号线互换一下位置,就能够在物理层实现一端发送的信号,另一端能收到)
然后配置两台电脑的 IP 地址、子网掩码和默认网关, 配置成同一个网络, 例:可以一个是 192.168.0.1/24,另一个是 192.168.0.2/24
三台电脑:
使用集线器Hub,和交换机不同,没有大脑,完全在物理层工作,将收到的字节复制到其他接口

数据链路层 (第二层)

问题: 多台电脑使用Hub进行物理层联网后: 广播,一台电脑发出的包所有电脑都能收到

  1. 这个包是发给谁的?谁应该接收?
  2. 大家都在发,会不会产生混乱?有没有谁先发、谁后发的规则?
  3. 如果发送的时候出现了错误,怎么办?

在第二层, 数据链路层, 也即 MAC层解决

MAC 的全称是 Medium Access Control,即媒体访问控制。

就是控制在往媒体上发数据的时候,谁先发、谁后发, 防止发生混乱。这解决的是第二个问题。这个问题中的规则,学名叫多路访问

  • 解决第二个问题: 谁先发,谁后发?
1
2
3
方式一: 分多个车道。每个车一个车道,你走你的,我走我的。  ( 信道划分 )
方式二: 今天单号出行,明天双号出行,轮着来 ( 轮流协议 )
方式三: 不管三七二十一,有事儿先出门,发现特堵,就回去,错过高峰再出 ( 随机接入协议 ) ( 以太网就是这种 )
  • 解决第一个问题: 发给谁? 谁接收? / 解决第三个问题: 发送出错怎么办?

这里用到一个物理地址,叫作链路层地址。但是因为第二层主要解决媒体接入控制的问题,所以它常被称为 MAC 地址

第二层的网络包格式
第二层的网络包格式

1
2
3
4
5
6
目标的 MAC 地址
源的 MAC 地址
类型:
IP 数据包,然后 IP 里面包含 TCP、UDP,以及 HTTP 等,这都是里层封装的事情
ARP 数据包
CRC: 循环冗余检测
1
2
3
问题: 一个广播的网络里面接入了 N 台机器,我怎么知道每个 MAC 地址是谁呢?
ARP 协议,也就是已知 IP 地址,求 MAC 地址的协议
发送一个广播包,谁是这个 IP 谁来回答。 为了避免每次都用 ARP 请求,机器本地也会进行 ARP 缓存, 机器会不断地上线下线,IP 也可能会变,所有缓存需要过期

局域网

Hub 是广播的,不管某个接口是否需要,所有的 Bit 都会被发送出去,然后让主机来判断是不是需要

机器少没问题,多了冲突概率就高, 而且把不需要的包转发过去,纯属浪费

  • 换智能的: 二层设备 - 交换机

每个口都只连接一台电脑,这台电脑又不怎么换 IP 和 MAC 地址,只要记住这台电脑的 MAC 地址,如果目标 MAC 地址不是这台电脑的,这个口就不用转发了。

1
2
3
4
5
6
例: 
MAC1 电脑将一个包发送给 MAC2 电脑
一开始交换机也不知道 MAC2 的电脑在哪个口,所以没办法,它只能将包转发给除了来的那个口之外的其他所有的口
但是,这个时候,交换机会记住这个口 MAC1 的, 以后有包的目的地址是 MAC1 的,直接发送到这个口就可以了。

交换机学习的结果称为 转发表: 有过期时间 ( 因为地址会变 )

小结

1
2
3
MAC 层是用来解决多路访问的堵车问题的
ARP 是通过吼的方式来寻找目标 MAC 地址的,吼完之后记住一段时间,这个叫作缓存;
交换机是有 MAC 地址学习能力的,学完了它就知道谁在哪儿了,不用广播了

交换机与VLAN:办公室太复杂,我要回学校

拓扑结构

1
2
办公室,整个公司多个楼层,几百个网口。 
一台交换机肯定不够了,需要多台交换机, 然后交换机连起来, 就形成了稍微复杂的拓扑结构
  • 环路问题

当两个交换机将两个局域网同时连接起来的时候

环路问题

1
2
刚开始机器 1 访问机器 2, 广播 ARP 包
这个包会在环路里转来转去, 多个机器都发广播包,广播包越来越多。 按上面共享道路的算法,也就是路会越来越堵,最后谁也别想走
  • 如何破坏环路? STP协议
1
2
3
4
数据结构中,有一个方法叫做最小生成树。有环的我们常称为图。将图中的环破了,就生成了树
在计算机网络中,生成树的算法叫作 STP,全称 Spanning Tree Protocol

理解: 华山论剑,最终决出五岳盟主

STP中的概念

1
2
3
4
5
6
Root Bridge: 根交换机, 树的老大
Designated Bridges: 指定交换机, 理解: 我拜谁做大哥,指定我的小弟也拜这个为大哥
Bridge Protocol Data Units (BPDU): 网桥协议数据单元, 理解为 “相互比较实力”的协议
Priority Vector: 优先级向量。 可以比喻为实力 (值越小越牛)
[Root Bridge ID, Root Path Cost, Bridge ID, and Port ID]
实力比较: 先看Root Bridge ID (老大的实力), 再比 Root Path Cost(跟老大的关系远近) , 最后 Bridge ID(自己的实力)

STP 工作过程

1
2
3
4
5
1. 一开始,江湖纷争,异常混乱。大家都觉得自己是掌门,谁也不服谁。于是,所有的交换机都认为自己是掌门
2. 但每个网桥都会被分配一个ID, 网络管理员知道哪些交换机贵,哪些交换机好,就会给它们分配高的优先级, 即有些交换机生下来实力就强
3. 开始互相发送 BPDU 来比功夫
4. 赢的接着当掌门,输的做小弟。 掌门继续发BPDU, 小弟就没机会了。 只有在收到掌门发的 BPDU 的时候,转发一下,表示服从命令。
5. 出现了很多小的门派,然后小的门派,接着合并, 最后生成一棵树,武林一统
  • 广播问题, 安全问题
1
2
广播问题(性能): 机器多了,交换机也多了,就算交换机比 Hub 智能一些,但是还是难免有广播的问题。 广播一大堆,性能就下来了
安全问题: 由于在同一个广播域里面,很多包都会在一个局域网里面飘啊飘,碰到了一个会抓包的程序员,就能抓到这些包,如果没有加密,就能看到这些敏感信息了

办法一、 物理隔离

1
2
3
每个部门有单独的交换机,配置单独的子网,这样部门之间的沟通就需要路由器了

问题: 每个部门有单独的交换机,口多了浪费,少了又不够用。

办法二、 虚拟隔离 ( VLAN, 虚拟局域网 )

使用 VLAN,一个交换机上会连属于多个局域网的机器,那交换机怎么区分哪个机器属于哪个局域网呢?

在原来的二层 MAC的头上加一个 TAG,里面有一个 VLAN ID,一共 12 位
交换机VLAN识别

1
2
3
4
5
6
只要买的交换机是支持 VLAN的,当这个交换机把二层的头取下来的时候,就能够识别这个 VLAN ID。
可以设置交换机每个口所属的 VLAN
这样只有相同 VLAN 的包,才会互相转发,不同 VLAN 的包,是看不到的。这样广播问题和安全问题就都能够解决了


交换机之间怎么连接呢? 设置为 Trunk 口, 转发属于任何 VLAN 的口

ICMP与ping:投石问路的侦察兵

ICMP 全称 Internet Control Message Protocol,就是互联网控制报文协议。 ICMP 报文是封装在 IP 包里面的

ICMP 的格式

ICMP协议格式

1
2
网络包在复杂网络环境中传输遇到问题的时候,不能“死个不明不白”,要传出消息来,报告情况
ICMP 常用类型: 主动请求为 8,主动请求的应答为 0
  • 查询报文类型
1
2
3
4
5
6
7
8
主动查询网络状况
ping 就是查询报文,是一种主动请求,并且获得主动应答的 ICMP 协议。在后面增加了自己的格式

对 ping 的主动请求,进行网络抓包,称为 ICMP ECHO REQUEST。同理主动请求的回复,称为ICMP ECHO REPLY
多了两个字段:
标识符: 理解: 两队侦查兵,一队是侦查战况的,一队是去查找水源
序号: 对派出去的包编号,回来多网络好,回来少网络差
在选项数据中: ping 还会存放发送请求的时间值,来计算往返时间,说明路程的长短

ping:查询报文类型的使用

1
在ping中间的设备或者路由, 使用 tcpdump -i eth0 icmp 可以查看包有没有到达这个点
  • 差错报文类型
1
2
3
4
5
6
7
8
9
10
异常情况发起的,来报告发生了不好的事情
例:
终点不可达为 3
具体原因在代码中: 网络不可达代码为 0,主机不可达代码为 1,协议不可达代码为 2,端口不可达代码为 3,需要进行分片但设置了不分片位代码为 4
源抑制为 4
让源站放慢发送速度
超时为 11
超过网络包的生存时间还是没到
重定向为 5
让下次发给另一个路由器 (更优路径)

Traceroute:差错报文类型的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
可故意设置一些能够产生错误的场景

Traceroute 的第一个作用就是故意设置特殊的 TTL,来追踪去往目的地时沿途经过的路由器
设置为1, 即到达第一个路由或关卡就失败, 设置为2,3,最终获得中间所有路由 (公网路由都设置不会回这个ICMP,所有拿不到公网的)

如何查看UDP报文有没有到达目的主机?
发送UDP 数据报给目的主机,选择一个不可能的UDP 端口号(大于 30000)
如果到达目的主机返回端口不可达, 没到返回超时

Traceroute 还有一个作用是故意设置不分片,从而确定路径的 MTU
首先是发送分组,并设置“不分片”标志
发送的第一个分组的长度正好与出口 MTU 相等
如果中间遇到窄的关口会被卡住,会发送 ICMP 网络差错包,类型为“需要进行分片但设置了不分片位”。每次收到 ICMP“不能分片”差错时就减小分组的长度,直到到达目标主机。

出网关

1
2
3
4
5
6
7
8
9
上网: 在进行网卡配置的时候,除了 IP 地址,还需要配置一个Gateway网关
在任何一台机器上,当要访问另一个 IP 地址的时候,都会先判断目标 IP 地址,和当前机器的 IP 地址,是否在同一个网段?
判断网段是否一样: 需要 CIDR 和子网掩码

同一网段: 直接将源/目标地址放入 IP 头中,然后通过 ARP 获得 MAC 地址,将源/目的 MAC 放入 MAC 头中,发出去就可以了
不同网段: 发往默认网关。Gateway 的地址一定是和源 IP 地址是一个网段的

网关往往是一个路由器,是一个三层转发的设备:
就是把 MAC 头和 IP 头都取下来,然后根据里面的内容,看看接下来把包往哪里转发的设备
  • 静态路由
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
路由器: 多个网卡,连着多个局域网,每个网卡跟一个局域网网段相同, 一个数据包从一个口进来从哪个口出去,根据路由算法
路由分为: 静态路由, 动态路由

静态路由:
就是在路由器上配置 一条条匹配规则, 从哪个口出去是什么地址。
```

- IP 头和 MAC 头哪些变、哪些不变 ?

两种类型网关

```text
MAC 地址是一个局域网内才有效的地址
MAC 地址只要过网关,就必定会改变,因为已经换了局域网

主要看IP是否变?
IP地址不变的网关: 转发网关
而IP地址变的网关: NAT网关

转发网关
转发网关

1
局域网之间的网段不会冲突, 即源/目标IP 不可能重复, 所以只需要 MAC地址修改进行转发

NAT网关 (Network Address Translation)
NAT网关

1
2
3
4
5
6
7
8
局域网之间,各定各的网段, IP冲突。 如上两天服务器的IP地址是相同的

解决:
既然局域网之间没有商量过,各管各的。 那到国际上,也即中间的局域网里面,就需要使用另外的地址,就想出国,不用身份证,用护照

例:
服务器 A 的国际身份是 192.168.56.1 , 服务器 B 的国际身份是 192.168.56.2
在网关上记录下身份, 出国就转换为国际身份,入国就转换为国内身份, 身份转换就是 NAT网关进行的IP转换

路由协议

  • 配置路由
1
2
3
4
5
6
7
8
路由表: 
当一个入口的网络包送到路由器时,它会根据一个本地的转发信息库,来决定如何正确地转发流量。

路由规则 (至少包含三个信息):
1. 目的网络:这个包想去哪儿?
2. 出口设备:将包从哪个口扔出去?
3. 下一跳网关:下一个路由器的地址。
核心思想: 根据目的 IP 地址来配置路由
  • 配置策略路由

在真实的复杂的网络环境中, 根据多个参数来配置路由

1
2
3
可以配置多个路由表
可以根据源 IP 地址、入口设备、TOS 等选择路由表,然后在路由表中查找路由
这样可以使得来自不同来源的包走不同的路由

动态路由算法

1
2
3
4
5
6
7
8
使用动态路由路由器,可以根据路由协议算法生成动态路由表,随网络运行状况的变化而变化。

无论是一个国家内部,还是国家之间,我们都可以将复杂的路径,抽象为一种叫作图的数据结构
最终肯定是路越少越好,道路越短越好,因而这就转化成为如何在途中找到最短路径的问题。

最短路径常用的有两种方法:
Bellman-Ford 算法
Dijkstra 算法
  • 距离矢量路由( distance vector routing ) , 基于 Bellman-Ford 算法
1
2
3
4
5
6
7
8
9
基本思路: 
每个路由器保存一个路由表,包含多行,每行对应网络中的一个路由器,包含两部分信息,一个是要到目标路由器,从那条线出去,另一个是到目标路由器的距离。
每个路由器知道全局信息: 每过几秒,每个路由器都将自己所知的到达所有的路由器的距离告知邻居,每个路由器也能从邻居那里得到相似的信息。

问题:
1. 好消息传得快,坏消息传得慢。
新路由器上线能很快通知邻居然后广播出去。
但路由挂了不会广播消息,当每个路由器发现原来的道路到不了这个路由器的时候,感觉不到它已经挂了,而是试图通过其他的路径访问,直到试过了所有的路径,才发现这个路由器是真的挂了。
2. 每次发送的时候,要发送整个全局路由表
  • 链路状态路由算法(link state routing),基于 Dijkstra 算法
1
2
3
4
5
6
7
基本思路: 
路由器启动,向邻居,发送一个 echo,要求马上返回,除以二就是距离。
然后将自己和邻居之间的链路状态包广播出去,发送到整个网络的每个路由器
然后每个路由器都能在自己本地构建一个完整的图, 然后针对这个图使用 Dijkstra 算法,找到两点之间的最短路径

链路状态路由协议只广播更新的或改变的网络拓扑
而且一旦一个路由器挂了,它的邻居都会广播这个消息,可以使得坏消息迅速收敛

路由协议

  • 基于链路状态路由算法的 OSPF 路由协议

主要用在数据中心内部,用于路由决策 , 因而也称为内部网关协议(Interior Gateway Protocol,简称 IGP)。

1
2
OSPF(Open Shortest Path First,开放式最短路径优先)
多个最短的路径: 等价路由 ( 可进行负载均衡 )
  • 基于距离矢量路由算法的 BGP 路由协议

外网路由协议(Border Gateway Protocol,简称 BGP)

使用 路径矢量路由协议(path-vector protocol), 是距离矢量路由协议的升级版

1
外网除了路径远近外,还有路过的不同数据中心不同policy的问题, 哪些IP能通过/不能通过。  

AS ( Autonomous System ) 自治系统

1
2
3
Stub AS:对外只有一个连接。这类 AS 不会传输其他 AS 的包 (个人,小公司的网络)
Multihomed AS:可能有多个连接连到其他的 AS,但是大多拒绝帮其他的 AS 传输包 ( 大公司网络 )
Transit AS:有多个连接连到其他的 AS,并且可以帮助其他的 AS 传输包 ( 主干网络 )

最重要的传输层

  • 主要: TCP 、 UDP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
区别: TCP 是面向连接的,UDP 是面向无连接的
所谓的建立连接,是为了在客户端和服务端维护连接,而建立一定的数据结构来维护双方交互的状态,用这样的数据结构来保证所谓的面向连接的特性。

TCP:
提供可靠交付。 无差错、不丢失、不重复、并且按序到达。
面向字节流。 IP包是一个个包发的,变成流是TCP维护的
拥塞控制, 意识到自己包丢了或网络慢了,会调整自己的发送速度
是一个有状态服务
UDP:
不保证不丢失,不保证按顺序到达。
基于数据包,一个个收发
无状态服务

MAC 层定义了本地局域网的传输行为,IP 层定义了整个网络端到端的传输行为,这两层基本定义了这样的基因:
网络传输是以包为单位的,二层叫帧,网络层叫包,传输层叫段

UDP

包头: IP包送到某个地址, UDP则是送到某个端口

  • UDP 三个特点
1
2
3
1. 沟通简单: 相信网络通路默认就是很容易送达的
2. 轻信他人: 不会建立连接,虽然有端口号,但是监听在这个地方,谁都可以传给他数据,他也可以传给任何人数据
3. 做事不变: 不管网络情况,该怎么发就怎么发
  • 使用场景
1
2
3
4
5
6
7
1. 需要资源少,在网络情况比较好的内网,或者对于丢包不敏感的应用
DHCP(内网获取IP地址,失败可重新来), TFTP

2. 不需要一对一沟通,建立连接,而是可以广播的应用

3. 需要处理速度快,时延低,可以容忍少数丢包,但是要求即便网络拥塞,也毫不退缩,一往无前的时候
要有自己的连接策略,应用层实现
  • 例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1. 网页或者 APP 的访问 
一般基于TCP的HTTP协议,
QUIC(全称 Quick UDP Internet Connections,快速 UDP 互联网连接)是 Google 提出的一种基于 UDP 改进的通信协议,其目的是降低网络通信的延迟,提供更好的用户互动体验。
在应用层上,会自己实现快速连接建立、减少重传时延,自适应拥塞控制

2. 流媒体的协议
直播协议多使用基于 TCP 的 RTMP
但隔几个帧丢一个,其实看视频的人不会感知。因而,很多直播应用,都基于 UDP 实现了自己的视频传输协议。

3. 实时游戏
实时性比较高,采用自定义的可靠 UDP 协议,自定义重传策略,能够把丢包产生的延迟降到最低,尽量减少网络问题对游戏性造成的影响

4. IOT 物联网
资源少,维护 TCP 协议代价太大。 对实时性要求也很高。

5. 移动通信领域
移动流量上网的数据面对的协议 GTP-U 是基于 UDP 的

TCP

1
2
3
4
5
6
7
8
9
10
11
12
端口: 需要知道发给那个应用,应用监听端口
序号: 为了解决乱序
确认序号: 发出去的包应该有确认,没收到就重发。 不丢包

状态位: (TCP 是面向连接的,因而双方要维护连接的状态,这些带状态位的包的发送,会引起双方的状态变更)
SYN 是发起一个连接
ACK 是回复
RST 是重新连接
FIN 是结束连接

窗口大小:
流量控制,通信双方各声明一个窗口,标识自己当前能够的处理能力,别发送的太快,也别发的太慢
  • TCP重点关注问题
1
2
3
4
5
顺序问题
丢包问题
连接维护
流量控制
拥塞控制
  • TCP 三次握手

保证双方的消息有去有回就可以了

1
2
3
4
5
6
三次握手处理建立连接, 还沟通 TCP包的序号问题, 从哪个序号开始发送

每个连接都要有不同的序号。
这个序号的起始序号是随着时间变化的,可以看成一个 32 位的计数器,每 4 微秒加一,
如果计算一下,如果到重复,需要 4 个多小时,那个绕路的包早就死翘翘了,
因为我们都知道 IP 包头里面有个 TTL,也即生存时间
  • TCP 四次挥手
1

  • 连接建立和断开的TCP状态机

TCP 如何实现靠谱?

  • 顺序发送保证应答
1
2
3
为了保证顺序性,每一个包都有一个 ID
在建立连接的时候,会商定起始的 ID 是什么,然后按照 ID 一个个发送
为了保证不丢包,对于发送的包都要进行应答,不应答每个包,而是应答某个之前的 ID,表示都收到了,这种模式称为累计确认或者累计应答(cumulative acknowledgment)
  • 发送端和接收端分别都有缓存来保存这些记录(所有发送和接收的包)
1
2
3
4
5
6
7
8
9
10
发送端, 按照包的 ID 一个个排列, 分四部分

1. 发送了并且已经确认
2. 发送但尚未确认
3. 未发送但等待发送
4. 未发送且暂时不会发送

流量控制:
接收端会给发送端报一个窗口的大小,叫 Advertised window
窗口的大小 等于 上面的第二,三部分。 而第四部分就是超过窗口不能发送的
1
2
3
4
5
6
7
8
9
10
11
接收端, 三部分

1. 接受并且确认过的
2. 还没接收,但是马上就能接收的。 即 能够接受的最大工作量
3. 还没接收,也没法接收的。 即 超过工作量的

第一,二 部分加起来是 接收端能接收的最大数量

第一部分是 已接收确认并确认,但未被应用使用的
第二部分就是 能接收的最大工作量, 即发送给接收端的 Advertised window
在第二部分中, 收到的包可能不是按顺序的,所以只有和第一部分连续的包可以进行马上回复,如果来的包不连续需要等待
  • 顺序问题与丢包问题
1
2
3
4
5
6
7
8
9
10
确认重发机制

超时重传: 每个发送但未ACK的包,有一个定时器,超时就进行重新尝试
超时时间的确定: 必须大于往返时间 RTT

自适应重传算法(Adaptive Retransmission Algorithm):
估计往返时间,需要 TCP 通过采样 RTT 的时间,然后进行加权平均,算出一个值,而且这个值还是要不断变化的,因为网络状况不断地变化。除了采样 RTT,还要采样 RTT 的波动范围,计算出一个估计的超时时间

TCP的策略:
超时 间隔加倍。每当遇到一次超时重传的时候,都会将下一次超时时间间隔设为先前值的两倍。两次超时,就说明网络环境差,不宜频繁反复发送
  • 流量控制问题
1
2
3
4
5
接收方在对于包的确认中,同时会携带一个窗口的大小

极端情况,接收端的应用一直不读取缓存中的数据,则随着确认的包越来越多,窗口越来越小,直到为 0

发送方会定时发送窗口探测数据包,看是否有机会调整窗口的大小。 而发送方不是空出一字节就马上调整的, 是达到一定大小才更新窗口
  • 拥塞控制问题
1
2
3
4
5
6
7
8
9
也是通过窗口的大小来控制的: 
前面的滑动窗口 rwnd 是怕发送方把接收方缓存塞满
而拥塞窗口 cwnd,是怕把网络塞满
公式 LastByteSent - LastByteAcked <= min {cwnd, rwnd} ,是拥塞窗口和滑动窗口共同控制发送的速度。

通道的容量 = 带宽 × 往返延迟。
设置发送窗口,使得 发送但未确认的包 为通道的容量,就能够撑满整个管道

TCP 的拥塞控制主要来避免两种现象,包丢失和超时重传

cwnd 拥塞窗口的慢启动

1
2
3
4
5
6
一条 TCP 连接开始: 
cwnd设置为1, 一次只能发送一个, 然后收到每个确认加1, 即下次2个,然后2个确认变4,然后变8,指数增长
指数增长到 ssthresh 的值, 就慢下来,每个确认增加 1/cwnd,即每次所有确认收到后加一,变成线性增长
线性增长最终出现拥塞即出现丢包现象,降低速度。
一种是: 将 sshresh 设为 cwnd/2,将 cwnd 设为 1,重新开始慢启动。 太激进,高速传输一下停止,容易网络卡顿
二种是: 将cwnd 减半为 cwnd/2,然后 sshthresh = cwnd。 还在比较高的值,呈线性增长
1
2
3
4
5
6
TCP 拥塞控制的问题

1.丢包并不代表着通道满了,也可能是管子本来就漏水。 如公网网络状况不好,这个时候就认为拥塞了,速度降低是不对的
2. TCP 的拥塞控制要等到将中间设备的缓存都填充满了,才发生丢包,从而速度降低。 TCP 只要填满管道就可以了,不应该接着填

为了优化这两个问题,后来有了 TCP BBR 拥塞算法

基于 TCP 和 UDP 协议的 Socket 编程

1
2
3
4
5
分客户端和服务端, 理解为一根网线,一头插在客户端,一头插在服务端,然后进行通信。 在通信之前,双方都要建立一个 Socket。

参数设置:
指定是 IPv4 还是 IPv6,分别对应设置为 AF_INET 和 AF_INET6
指定是 TCP 还是 UDP, 分别对应 基于数据流SOCK_STREAM 和 基于数据报SOCK_DGRAM

基于 TCP 协议的 Socket 程序函数调用过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
服务端socket: 
先 bind 进行绑定 IP地址和端口
listen 进行监听
内核维护两个队列:
1. 已经建立了连接的队列 , 已完成三次握手, 处于 established 状态
2. 还没有完全建立连接的队列, 处于三次握手中, 处于 syn_rcvd 的状态
调用 accept 函数,拿出一个已经完成的连接进行处理

客户端socket:
在服务端进入listen状态后, 可以使用 connect 发起连接(指明连接IP和端口),进行三次握手
内核给客户端分配一个临时端口
握手成功,服务端的 accept 就会返回另一个 Socket

注意:
监听的 Socket 和真正用来传数据的 Socket 是两个: 监听socket, 已连接socket

两端连接建立后:
双方都通过 read, write 进行读写数据, 像文件流读写一样
1
2
3
4
5
6
7
8
9
10
11
12
Socket 在 Linux 中就是以文件的形式存在的
存在文件描述符。写入和读出,都是通过文件描述符

每一个进程都有一个数据结构 task_struct,里面指向一个文件描述符数组,来列出这个进程打开的所有文件的文件描述符。
文件描述符是一个整数,是这个数组的下标。 内容是指针,指向文件地址

一个文件,就会有一个 inode
只不过 Socket 对应的 inode 不像真正的文件系统一样,保存在硬盘上的,而是在内存中的。
在这个 inode 中,指向了 Socket 在内核中的 Socket 结构

socket 结构: 主要是两个队列 - 发送队列 和 接收队列
在这两个队列里面保存的是一个缓存 sk_buff。这个缓存里面能够看到完整的包的结构。 用于收发包

基于 UDP 协议的 Socket 程序函数调用过程

1
2
3
4
5
UDP 没有连接,不需要三次握手,也就不需要调用 listen 和 connect 
但是,UDP 的交互仍然需要 IP 和端口号,因而也需要 bind。

UDP 没有维护连接状态,因而不需要每对连接建立一组 Socket,而是只要有一个 Socket,就能够和多个客户端通信。
也正因为没有连接状态,每次通信的时候,都调用 sendto 和 recvfrom,都可以传入 IP 地址和端口。

服务器如何接更多的项目?

  • 最大连接数

一个四元组 标识 一个 TCP 连接:

{本机IP, 本机端口, 对端IP, 对端端口}

1
2
3
4
5
6
对服务端来说: 最大 TCP 连接数 = 客户端 IP 数×客户端端口数
对 IPv4,客户端的 IP 数最多为 2 的 32 次方,客户端的端口数最多为 2 的 16 次方,也就是服务端单机最大 TCP 连接数,约为 2 的 48 次方。

实际限制:
1. 文件描述符限制: Socket 都是文件,所以首先要通过 ulimit 配置文件描述符的数目;
2. 内存:每个 TCP 连接都要占用一定内存
  • 在资源有限的情况下,如何降低每个连接消耗的资源数目。达到更多的连接数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
1. 多进程方式 (将项目外包给其他公司)
一旦建立了一个连接,就会有一个已连接 Socket,这时候你可以创建一个子进程,然后将基于已连接 Socket 的交互交给这个新的子进程来做

Linux 下,创建子进程使用 fork 函数。这是在父进程的基础上完全拷贝一个子进程。
在 Linux 内核中,会复制文件描述符的列表,也会复制内存空间,还会复制一条记录当前执行到了哪一行程序的进程。
显然,复制的时候在调用 fork,复制完毕之后,父进程和子进程都会记录当前刚刚执行完 fork。这两个进程刚复制完的时候,几乎一模一样,只是根据 fork 的返回值来区分到底是父进程,还是子进程。如果返回值是 0,则是子进程;如果返回值是其他的整数,就是父进程。
复制了文件描述符列表,而文件描述符都是指向整个内核统一的打开文件列表的, 子进程直接就可以通过这个已连接 Socket 和客户端进行互通
最后子进程通信完成,父进程根据子进程ID查看是否退出子进程

2. 多线程方式(将项目转包给独立的项目组)
在 Linux 下,通过 pthread_create 创建一个线程,也是调用 do_fork
但很多资源,例如文件描述符列表、进程空间,是共享的,只不过多了一个引用而已。
新的线程也可以通过已连接 Socket 处理请求,从而达到并发处理的目的

上面两种问题:
每次新到来一个 TCP 连接,就需要分配一个进程或者线程
一台机器无法创建很多进程或者线程。有个 C10K 问题

3. IO 多路复用,一个线程维护多个 Socket (一个项目组支撑多个项目)
某个线程盯的所有的 Socket,都放在一个文件描述符集合 fd_set 中
然后调用 select 函数来监听这个文件描述符集合是否有变化。
一旦有变化,就会依次查看每个文件描述符。
那些发生变化的文件描述符在 fd_set 对应的位都设为 1,表示 Socket 可读或者可写,从而可以进行读写操作,
然后再调用 select,接着盯着下一轮的变化。


4. IO 多路复用,从“派人盯着”到“有事通知” (一个项目组支撑多个项目)
上面第三种方法,select查询集合的问题:
Socket文件描述符集合中有发生变化时,采用轮询的方法需要将整个集合过一遍,这样效率太低,影响线程能处理的最大socket数量
因而使用 select,能够同时盯的项目数量由 FD_SETSIZE 限制

改进: 改成事件通知的方式,
能完成这件事情的函数叫 epoll,它在内核中的实现不是通过轮询的方式,而是通过注册 callback 函数的方式,当某个文件描述符发送变化的时候,就会主动通知

进程打开了多个 socket 文件描述符,
epoll_create 创建一个 epoll 对象,也是个文件,内容是红黑树, 保存这个 epoll 监听的所有 Socket。
当 epoll_ctl 添加一个 Socket 的时候,其实是加入这个红黑树,同时红黑树里面的节点指向一个结构,将这个结构挂在被监听的 Socket 的事件列表中。当一个 Socket 来了一个事件的时候,可以从这个列表中得到 epoll 对象,并调用 call back 通知它。

使用这种方式, 能够同时监听的 Socket 的数目就非常的多了。上限就为系统定义的、进程打开的最大文件描述符个数
epoll 被称为解决 C10K 问题的利器。

应用层

HTTP

数据中心

DNS协议, 网络世界的地址簿

  • DNS 服务器
1
2
3
4
5
6
DNS 服务器,一定要设置成高可用、高并发和分布式的

分为三层:
根 DNS 服务器: 返回顶级域 DNS 服务器的 IP 地址
顶级域 DNS 服务器: 返回权威 DNS 服务器的 IP 地址
权威 DNS 服务器 :返回相应主机的 IP 地址
  • DNS 解析流程
1
2
3
4
1. 先访问 本地域名服务器 (如移动电信等网络服务商的机房)
2. 本地域名服务器 找到直接返回IP, 没找到则访问 根域名服务器(全球共 13 套。它不直接用于域名解析,返回顶级域名服务器地址)
3. 本地域名服务器 访问 顶级域名服务器( 也不直接域名解析,返回权威域名服务器的地址 )
4. 本地域名服务器 访问 权威域名服务器 ( 进行域名解析查询到对应的IP返回 )
  • DNS 负载均衡
  1. 内部负载均衡
1
2
3
多个应用访问一个数据库: 如果配置IP,IP换了就需要所有应用修改配置, 如果配置了域名,只需要将域名映射为新的IP

A应用访问应用B, 如果应用B撑不住了,可以集群部署,域名配置对应多个应用B的IP,配置域名解析的策略,进行负载均衡
  1. 全局负载均衡
1
2
3
4
5
基于 DNS 的全局负载均衡: 用来选择一个就近的同样运营商的服务器进行访问

可以再DNS服务器中配置 CNAME, 给域名起别名,让本地DNS服务器请求 转到 全局负载均衡器(GSLB: Global Server Load Balance) 进行更复杂的解析
可配置第一层 GSLB,解析跟本地DNS服务器相同的运营商, 然后再这个GSLB 同样配置 CNAME, 转到第二层GSLB
在第二层 GSLB, 解析本地DNS服务器就近的地址, 返回给本地DNS服务器,相同运营商的最近的服务器IP地址
  • 传统DNS存在的问题
  1. 域名缓存问题
1
本地服务器 对已经访问过的地址有缓存, 域名换地址后可能还是导向旧地址 
  1. 域名转发问题
1
2
有些小的运营商不是直接自己访问权威域名服务器 ,而只是进行转发,让其他大的运营商进行域名解析
就会导致: A运营商的请求,最后是B运营商访问域名服务器进行域名解析,最后返回B运营商的IP, 导致每次请求都跨运营商, 很慢
  1. 出口 NAT 问题
1
2
网络出口的时候,很多机房都会配置 NAT,也即网络地址转换,使得从这个网关出去的包,都换成新的 IP 地址
权威DNS服务器,就没办法通过这个地址,来判断客户到底是来自哪个运营商, 可能导致误判运营商,最终跨运营商访问,速度慢
  1. 域名更新问题
1
2
本地 DNS 服务器是由不同地区、不同运营商独立部署的
在权威 DNS 服务器解析变更的时候,解析结果在全网生效的周期非常漫长
  1. 解析延迟问题
1
DNS 的查询过程需要递归遍历多个 DNS 服务器, 会有时延

HttpDNS

就是不走传统的 DNS 解析, 而是自己搭建基于 HTTP 协议的 DNS 服务器集群,分布在多个地点和多个运营商。当客户端需要 DNS 解析的时候,直接通过 HTTP 协议进行请求这个服务器集群,得到就近的地址。

1
httpDNS需要绕过传统DNS, 不使用默认客户端,往往是手机应用,嵌入支持HttpDNS的客户端
  • HttpDNS的工作模式
1
2
3
4
5
6
在客户端的 SDK 里动态请求服务端,获取 HttpDNS 服务器的 IP 列表,缓存到本地

随着不断地解析域名,SDK 也会在本地缓存 DNS 域名解析的结果。
这个缓存是手机应用自己的,可以自己协调 过期更新时间等

手机客户端自然知道手机在哪个运营商、哪个地址。由于是直接的 HTTP 通信,HttpDNS 服务器能够准确知道这些信息,因而可以做精准的全局负载均衡。

CDN

1
2
3
4
5
6
7
8
9
10
11
参考思路: 物流的 "就近配送",在电商网站下单,不是从总部发送快递,从就近仓库发送。 

在全球这么多数据中心里部署几台机器,形成一个缓存的集群来缓存部分数据,让用户访问时可以就近访问

分布在各个地方的各个数据中心的节点,称为 边缘节点
边缘集群规模比较小,不可能缓存下来所有东西,因而可能无法命中
边缘节点之上是: 区域节点
再之上是: 中心节点
最后还没有就是去 源网站 访问了

CDN分发系统架构: 中心节点 -》 区域节点 -》 边缘节点
  • 客户端如何找到相应的边缘节点进行访问呢?
1
2
3
4
5
6
7
跟DNS的全局负载均衡器很像。 
在整个多区域,多运营商的分发网络下,找到就近的节点

设置了CDN的访问请求:
1. 访问请求网址, 进行第一步域名解析,网址权威DNS服务器上,设置 CNAME,返回CND网络的域名
2. 去 CDN网络域名的 权威DNS服务器上,在这个权威DNS服务器上,设置 CNAME,返回CND的全局负载均衡解析器
3. 去 全局负载均衡解析器, 根据 全局负载均衡器内的策略, 返回合适的缓存服务器。
  • CND 缓存的内容
1
2
3
4
比较容易缓存,不容易过期
静态页面, 图片等

流媒体协议: 大量采用了CDN

数据中心

VPN

Virtual Private Network,虚拟专用网

1
2
3
4
5
6
7
两个数据中心连接
走公网不安全
租用专线连接太贵
折中办法VPN: 利用开放的公众网络,建立专用数据传输通道,将远程的分支机构、移动办公人员等连接起来

VPN 通过隧道技术在公众网络上仿真一条点到点的专线,是通过利用一种协议来传输另外一种协议的技术
这里面涉及三种协议:乘客协议、隧道协议和承载协议
  • IPsec VPN ( 基于 IP 协议的安全隧道协议 )
1
2
3
4
5
6
1. 公网上信息安全的保证机制
私密性: 加密, 对称加密
完整性: 数据没有被非法篡改,通过对数据进行 hash 运算,产生类似于指纹的数据摘要
真实性: 数据确实是由特定的对端发出,通过身份认证可以保证数据的真实性。


移动网络

云计算中的网络

云中网络

1
2
从物理机到虚拟机: 软件模拟硬件, 主要模拟 CPU、内存、网络、硬盘
在数据中心里,用的是 qemu-kvm
  • 虚拟网卡
1
2
3
4
5
6
7
qemu-kvm 使用 linux中的 TUN/TAP 技术

虚拟机 是软件: 打开一个称为 TUN/TAP 的 Char Dev(字符设备文件), 在物理机上就能看到一张虚拟 TAP 网卡。

虚拟机会将打开的这个文件在内部虚拟出一个网卡,所有网络包都往这里发,虚拟机会将网络包转换成为文件流,写入字符设备,就像写入文件一样
内核中 TUN/TAP 字符设备驱动会收到这个写入的文件流,交给 TUN/TAP 的虚拟网卡驱动。
这个驱动将文件流再次转成网络包,交给 TCP/IP 协议栈,最终从虚拟 TAP 网卡发出来,成为标准的网络包。
  • 虚拟网卡连接到云中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
云计算中的网络注意点:
共享: 每个虚拟机一个或多个虚拟网卡,但物理机上只有有限几个网卡,多虚拟网卡如何共享同一个出口?
隔离: 安全隔离-两个虚拟机两个用户 , 流量隔离-两个虚拟机,一个疯狂下载另一个直接没网
互通: 一个用户两天虚拟机,在一个物理机或两个物理机, 如何通信?
灵活: 虚拟机可能经常创建删除,在不同物理机上飘,有的互通有的不同,需要灵活配置

共享和互通问题:
理解物理机是大学宿舍,虚拟机是个人电脑,之间连通需要交换机
虚拟的交换机: Linux 上的命令 brctl, 创建虚拟网桥brctl addbr br0,然后将两个虚拟机的虚拟网卡连接到这个网桥,网段一致就可以通信了

虚拟机连接外网:
桥接: 将物理网卡 也连接到虚拟交换机上, 跟内部虚拟机的虚拟网卡处于同一网段
NAT: 虚拟交互机和物理网卡之间 有一个NAT设备, 虚拟网络 和 物理网络 不是同一个网络, 还会内置一个虚拟DHCP服务器,为虚拟机分配IP

隔离问题:
1. 一台机器上的两个虚拟机不属于同一个用户, 进行隔离?
brctl 创建的网桥也是支持 VLAN 功能的
设置两个虚拟机的 tag,这样在这个虚拟网桥上,两个虚拟机是不互通的。

2. 跨物理机互通,并且实现 VLAN 的隔离呢?
命令 vconfig,可以基于物理网卡 eth0 创建带 VLAN 的虚拟网卡, 所有从这个虚拟网卡出去的包,都带这个 VLAN
为每个用户分配不同的 VLAN,在物理机上,基于物理网卡,为每个用户用 vconfig 创建一个带 VLAN 的网卡
不同的用户使用不同的虚拟网桥,带 VLAN 的虚拟网卡也连接到虚拟网桥上。

软件定义网络 ( SDN )

  • 特点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
控制和转发分离
控制平面与转发平面之间的开放接口
逻辑上的集中控制
```

- 实现 ( openFlow, openvSwitch )

```text
OpenFlow 是 SDN 控制器和网络设备之间互通的南向接口协议
OpenvSwitch 用于创建软件的虚拟交换机, 支持 openFlow协议

硬件交换机也支持 openFlow协议,从而实现 虚拟机和物理机 被SDN统一控制网络物理


SDN 控制器是如何通过 OpenFlow 协议控制网络的呢?
在 OpenvSwitch 里面,有一个流表规则,任何通过这个交换机的包,都会经过这些规则进行处理,从而接收、转发、放弃
流表: 多个表格,每个表格多行, 每一行 ( 匹配规则,优先级,执行动作 )

规则覆盖 TCP/IP 协议栈的四层
物理层:
匹配规则: 从哪个口进来
执行动作: 从哪个口出去
MAC层:
匹配规则: 源/目标 MAC 地址, 所属 VLAN
执行动作: 修改 源/目标 MAC 地址, 修改,删除 VLAN, MAC地址学习
网络层:
匹配规则: 源/目标 IP地址
执行动作: 修改 源/目标 IP地址
传输层:
匹配规则; 源/目标 端口
执行动作: 修改 源/目标 端口

网络安全

1
2
3
共有云上的端口的 安全守护措施:  
采用 ACL(Access Control List,访问控制列表)来控制 IP 和端口
设置规则,指定IP可以访问开放接口 - 安全组
  • 网络包进入机器后的流程
1
2
3
4
5
6
1. 拿下MAC头,查看是否是自己的,是就继续
2. 拿下IP头,获取其中的目标IP, 开始进行路由判断,判断之前的节点称为: PREROUTING(路由之前)
3. 如果IP是自己的,发给上面的传输层, 这个节点称为: INPUT
4. 如果不是自己的,转发出去, 这个几点称为: FORWARD
5. 上传处理完成会返回一个处理结果,处理结果会发出去,这个节点称为: OUTPUT
6. 转发还是发出去, 都是在路由判断之后,最后一个节点为: POSTROUTING

上诉五个重要节点:

1
2
3
linux内核,框架Netfilter, 可以在这些节点插入hook函数,截获数据包,对数据包进行干预
一个著名的实现: ip_tables
按功能可分为四大类:连接跟踪(conntrack)、数据包的过滤(filter)、网络地址转换(nat)和数据包的修改(mangle)
  • 安全组
1
2
3
在云上每个虚拟机都自己安装iptables然后设置规则过于麻烦
所以在云平台上,一般允许一个或者多个虚拟机属于某个安全组,
而属于不同安全组的虚拟机之间的访问以及外网访问虚拟机,都需要通过安全组进行过滤

云中的网络 Qos (Quality of Service)

1
2
3
网络控制: 
进入的方向不能控制,只能通过policy进行丢弃
出去的方向可以控制
  • 网络Qos 的控制方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
主要都是通过队列的方式进行控制

一.无类别排队规则

1. pfifo_fast
分为三个优先级的 先入先出队列Band, 根据网络包里面 TOS,判断进入哪个队列。 TOS 4位 16种类型,对应到 三个队列中

2. 随机公平队列 (Stochastic Fair Queuing)
建立很多的 FIFO 的队列,TCP Session 计算 hash 值,根据hash值分配队列, 另一边轮询从队列中拿数据包发送

3. 令牌桶规则 (TBF,Token Bucket Filte)
一个FIFO队列,但需要拿令牌才能发送

二. 基于类别的队列规则

1. 分层令牌桶规则(HTB, Hierarchical Token Bucket)


  • 如何控制
1
2
对于进入的流量,可以设置策略 Ingress policy
对于发出的流量,可以设置 QoS 规则 Egress shaping,支持 HTB

容器技术中的网络

容器网络

  • 看起来是隔离的技术: namespace (命名空间)
1
2
3
将全局性的内容,以命名空间隔离进行不重复。
网络的 namespace 由 ip netns 命令操作。它可以创建、删除、查询 namespace

  • 用起来是隔离的技术: cgroup (control groups)
1
2
3
4
是 Linux 内核提供的一种可以限制、隔离进程使用的资源机制。



即时消息技术学习

IM应用场景

  • QQ,微信等聊天类场景: 即时通讯
  • 豆瓣, 知乎等社区类场景: 点对点聊天
  • yy,抖音等直播类场景: 互动,实时弹幕
  • 小米, 京东智能家居类IOT场景:实时监控,远程控制
  • 游戏里场景: 多人互动
  • 交通类场景: 位置共享
  • 教学类场景: 在线白板

基础篇

一个完整的IM系统

以聊天系统为例

使用者眼中的聊天系统

使用者眼中的聊天系统

  • 聊天的参与需要用户,所以需要有一个用户账号,用来给用户提供唯一标识,以及头像、昵称等可供设置的选项。
  • 账号和账号之间通过某些方式(比如加好友、互粉等)构成账号间的关系链。
  • 你的好友列表或者聊天对象的列表,我们称为联系人的列表,其中你可以选择一个联系人进行聊天互动等操作。
  • 在聊天互动这个环节产生了消息。
  • 同时你和对方之间的聊天消息记录就组成了一个聊天会话,在会话里能看到你们之间所有的互动消息。

开发者眼中的聊天系统

开发者眼中的聊天系统

  • 客户端: 一般是用户用于收发消息的终端设备,内置的客户端程序和服务端进行网络通信,用来承载用户的互动请求和消息接收功能
  • 接入服务: 服务端的门户,为客户端提供消息收发的出入口
    • 主要有四块功能:连接保持、协议解析、Session 维护和消息推送。
  • 业务服务: 真正的消息业务逻辑处理层
    • 业务: 消息的存储、未读数变更、更新最近联系人等
  • 存储服务: 账号信息、关系链,以及消息本身,都需要进行持久化存储。
  • 外部接口服务: 让用户在 App 未打开时,或者在后台运行时,也能接收到新消息
    • 将消息给到第三方外部接口服务,来通过手机操作系统自身的公共连接服务来进行操作系统级的“消息推送”

接入服务 和 业务服务 为什么独立拆分?

1
2
3
4
5
6
接入服务作为消息收发的出入口,必须是一个高可用的服务,保持足够的稳定性是一个必要条件。

而业务处理服务由于随着产品需求迭代,变更非常频繁,随时有新业务需要上线重启

如果两个合一起, 会导致连接层不稳定
将“只负责网络通道维持,不参与业务逻辑,不需要频繁变更的接入层”抽离出来,不管业务逻辑如何调整变化,都不需要接入层进行变更,这样能保证连接层的稳定性,从而整体上提升消息收发的用户体验。
1
2
3
4
接入服务和业务处理服务进行拆分有助于 提升业务开发效率,降低业务开发门槛。

接入服务负责处理一切网络通信相关的部分,比如网络的稳定性、通信协议的编解码等
负责业务开发的同事就可以更加专注于业务逻辑的处理

IM系统的特性

  • 实时性: 消息实时触达
  • 可靠性: 消息不丢,不重
  • 一致性: 同一条消息,在多人、多终端需要保证展现顺序的一致性
  • 安全性: 数据传输安全,数据存储安全,消息内容安全
  • 其他: 省电,省流量等

为一个已有APP加上实时通信功能

以点对点为例

  • 消息存储: 消息内容,消息索引
1
2
3
4
5
消息参与者有两个: 发送方, 接收方
收发双方的历史消息独立, 即发送方删除消息,接收方仍有这条消息

消息内容表: 存储消息维度的一些基本信息,比如消息 ID、消息内容、消息类型、消息产生时间等
消息索引表: 收发双方的两个索引通过同一个消息 ID 和这个内容表关联

张三 给 李四 发一条消息
img.png

  • 联系人存储

联系人列表只更新存储收发双方的最新一条消息,不存储两人所有的历史消息

1
2
消息索引表的使用场景一般用于查询收发双方的历史聊天记录,是聊天会话维度;
而联系人表的使用场景用于查询某一个人最近的所有联系人,是用户全局维度。
  • 消息未读数
1
2
3
4
1.用户维度的总未读
2.会话维度的会话未读

需要支持“消息的多终端漫游”的应用需要在 IM 服务端进行未读存储,不需要支持“消息的多终端漫游”可以选择本地存储即可

轮询,长连接

  • 轮询
1
2
短轮询: 高频http请求。  费电费流量, 服务端资源压力:服务器QPS抗压,存储资源
长轮询: 避免高频无用功的问题。 只降低了入口QPS的请求, 对后端存储压力没有减少
  • 长连接
1
2
3
websocket: 双向通信, 数据交互网络开销低,web原生支持

还有各种TCP衍生的: XMPP 协议、MQTT 协议以及各种私有协议

保证消息可靠投递: ACK机制

可靠: 消息不丢,不重

发送消息分为两个部分
发送消息的ACK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
一. 前半部分 
1. 用户A 发送消息到 IM服务器
2. 服务器存储消息
3. 服务器返回给用户A确认
步骤1,2,3 都可能失败。

通过 超时重传 进行不丢处理, 但如果是步骤3失败,服务器已经存在消息会出现消息重复的问题。
通过 唯一ID 服务端进行去重,进行不重处理

二. IM服务器将 存储的消息 推送给 用户B
问题1: 可能服务器掉电没有将消息推送给客户端B
问题2: 可能服务器已经将消息推送给了客户端B,但客户端B处理出错。 即网络层面消息投递成功,但用户B看不到消息

一般参考TCP的ACK机制, 实现业务层的ACK协议

业务层ACK协议

1
2
3
4
5
6
7
8
9
10
11
1. IM 服务器在推送消息时,携带一个标识 SID(安全标识符,类似 TCP 的 sequenceId)
2. 推送出消息后会将当前消息添加到 “待 ACK 消息列表”
3. 客户端 B 成功接收完消息后,会给 IM 服务器回一个业务层的 ACK 包,包中携带有本条接收消息的 SID
4. IM 服务器接收后,会从“待 ACK 消息列表”记录中删除此条消息,本次推送才算真正结束

如果ACK过程失败
IM 服务器的“等待 ACK 队列”一般都会维护一个超时计时器,一定时间内如果没有收到用户 B 回的 ACK 包,会从“等待 ACK 队列”中重新取出那条消息进行重推

重传后导致的重复问题: 客户端B 根据唯一ID进行去重

极端情况: 服务端宕机的同时,客户端没有收到消息。 IM服务器不能进行重传机制。

补救措施: 消息完整性检查

1
2
3
4
5
用户在重新上线时,让服务端有能力进行完整性检查,发现用户 用户 “有消息丢失” 的情况,就可以重新同步或者修复丢失的数据

常见方案
时间戳比对: 客户端发送本地最新时间戳, 服务端对比发送时间戳之后的消息
时间戳可能存在多机器时钟不同步的问题, 所以在实际的实现上,也可以使用全局的自增序列作为版本号来代替

保证消息时序: 消息序号生成器

消息时序一致性: 消息顺序不对会导致语义逻辑出问题

关键问题: 找到一个时序基准,使得我们的消息具备“时序可比较性”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
时序基准: 
全局递增的序号生成器
常见的比如 Redis 的原子自增命令 incr,DB 自带的自增 id,或者类似 Twitter 的 snowflake 算法、“时间相关”的分布式序号生成服务等

时序基准的可用性问题:
面向高并发和需要保证高可用的场景,考虑这个“全局序号生成器”的可用性问题。
1. 类似 Redis 的原子自增和 DB 的自增 id,都要求在主库上来执行“取号”操作,而主库基本都是单点部署,在可用性上的保障会相对较差
2. 类似 snowflake 算法的时间相关的分布式“序号生成器”,虽然在发号性能上一般问题不大,但在时间精度 或者 时钟一致上有问题

从业务层面考虑,不需要全局递增,如群聊保证群内序号递增就好。 所以能通过哈希规则把压力分散到多个主库实例上,大量降低多群共用一个“ID 生成器”的并发压力。
对于大部分即时消息业务来说,产品层面可以接受消息时序上存在一定的细微误差, 如同一秒内消息不按严格时序,用户无感知。微博的消息就是秒间有序

时序基准的误差减少:
IM服务器集群部署, 内部逻辑多线程处理。 并不能保证 先到的消息先推送出去

大部分场景业务能接受“小误差的消息乱序”, 这种可以在接收端进行 本地消息整流
但某些特定场景需要IM 服务能保证绝对的时序, 这种只能在服务端进行 消息整流。 例子: 用户A给用户B 发送分手消息然后取关。 如果顺序倒了,会导致取关后消息发送失败

服务端包内整流:
在发送方对多个请求进行业务层合并,多条消息合并成一条;
离线推送整流: 用户上线后 生产者离线消息打包生成packageId,消费者根据每条消息的 packageID 和 seqID 进行整流,最终执行模块只有在一定超时时间内完整有序地收到所有消息才执行最终推送操作

消息接收端整流
根据序号插入会话

安全性: HttpDNS和TLS

  • 传输安全性
1
2
3
4
5
6
7
8
9
开放网络,可能存在问题: DNS 劫持会导致发往 IM 服务的请求被拦截发到其他服务器,导致内容泄露或失效;或者明文传输的消息内容被中间设备劫取后篡改内容,再发往 IM 服务器引起业务错误等问题。

主要关注两个问题: “访问入口安全” 和 “传输链路安全”

1. 保证访问入口安全:HttpDNS


2. 保证传输链路安全:TLS 传输层加密协议

  • 存储安全性
1
2
3
4
5
6
服务端存储, 内部人员非法查询,数据库'拖库' 问题

账号密码存储安全:“单向散列”算法
消息内容存储安全:端到端加密
1. 消息内容采用“端到端加密”(E2EE), 中间任何链路环节都不对消息进行解密。
2. 消息内容不在服务端存储。
  • 消息内容安全性
1
2
3
4
5
6
依托于第三方的内容识别服务来进行“风险内容”的防范

1. 建立敏感词库,针对文字内容进行安全识别。
2. 依托图片识别技术来对色情图片和视频、广告图片、涉政图片等进行识别处置。
3. 使用“语音转文字”和 OCR(图片文本识别)来辅助对图片和语音的进一步挖掘识别。
4. 通过爬虫技术来对链接内容进行进一步分析,识别“风险外链”。

分布式锁和原子性: 未读消息提醒的正确性

  • 会话未读
  • 总未读
1
2
3
4
5
从概念上来说: 总未读数 就是所有会话未读数 的 总和

但一般实现上: 总未读数 和 会话未读数 进行单独维护

总未读数量高频使用, 总未读数不单单包含即时消息的未读,还有其他业务通知的未读

单独维护 总未读数 和 会话未读数带来的 未读数一致性问题

1
2
3
4
5
6
维护的总未读数和会话未读数的总和要保持一致

保证 未读更新的原子性
分布式锁
支持事务的资源
原子化嵌入脚本

智能心跳机制: 网络的不确定性

需要维护好长连接

1
2
3
4
5
6
7
8
长连接中间链路断开, 两段无感知
需要 '快速','不间断' 感知到 连接可用性的机制: 心跳机制

IM服务端: 感知连接的变化,清理无用连接

服务端维护一些“用户在线状态”和“所有在线设备”这些信息,便于业务使用。 保持没有无效信息

客户端 断线重连,连接保活

心跳监测 实现方式

  • TCP Keepalive
1
2
3
4
5
6
7
8
9
10
TCP 的 Keepalive 作为操作系统的 TCP/IP 协议栈实现的一部分,对于本机的 TCP 连接,会在连接空闲期按一定的频次,自动发送不携带数据的探测报文,来探测对方是否存活。
操作系统默认是关闭这个特性的,需要由应用层来开启。
默认的三个配置项:心跳周期是 2 小时,失败后再重试 9 次,超时时间 75s 。 可调整

优点:
不需要其他开发工作量,上层应用只需要处理探测后的连接异常情况即可
心跳包不携带数据,带宽资源的浪费也是最少的。
缺陷:
比如心跳间隔灵活性较差,一台服务器某一时间只能调整为固定间隔的心跳
另外 TCP Keepalive 虽然能够用于连接层存活的探测,但并不代表真正的应用层处于可用状态。
  • 应用层心跳
1
客户端每隔一定时间间隔,向 IM 服务端发送一个业务层的数据包告知自身存活
  • 智能心跳
1
2
3
4
5
6
国内移动网络场景下,各个地方运营商在不同的网络类型下 NAT 超时的时间差异性很大
用固定频率的应用层心跳在实现上虽然相对较为简单,但为了避免 NAT 超时,只能将心跳间隔设置为小于所有网络环境下 NAT 超时的最短时间

所谓智能心跳,就是让心跳间隔能够根据网络环境来自动调整,通过不断自动调整心跳间隔的方式,逐步逼近 NAT 超时临界点,在保证 NAT 不超时的情况下尽量节约设备资源

需要不断尝试, 会从一定程度上降低“超时确认阶段”连接的可用性

场景篇

分布式一致性, 多端漫游

用户在任意一个设备登录后,都能获取到历史的聊天记录。

1
2
3
4
5
收发的消息在多个终端漫游,两个前置条件:
设备维度的在线状态
多个终端同时登录并在线的用户,可以让 IM 服务端在收到消息后推给接收方的多台设备,也推给发送方的其他登录设备。
离线消息存储
当用户的离线设备上线时,就能够从服务端的存储中获取到离线期间收发的消息

自动智能扩缩容: 直播互动场景中的峰值流量的应对

直播互动的流量峰值具有“短时间快速聚集”的突发性,流量紧随着主播的开播和结束而剧烈波动

1
2
3
4
5
6
7
8
消息下推的并发峰值, 理论:  
点对点: 如果两个人每 10 秒说一句话,实际上每秒的消息下推数只有 0.1
500人群聊: 群里每个人也是每 10 秒说一句话,实际每秒的消息下推数是 500 / 10 * 500 = 25000;
10万人在线直播互动: 如果直播间里每个人也每 10 秒说一句话,实际每秒可产生的消息下推数就是 100000 / 10 * 100000 = 10 亿

实际上,10 万人的直播间一般不会有这么高的发言和互动热度,
即使能达到,也会在服务端进行限流和选择性丢弃。一个是考虑服务端的承受能力基本不可能达到这个量级,
另一方面,即使消息能全部推下去,客户端也处理不了每秒一万条消息的接收,对客户端来说,一般每秒接收几十条消息就已经是极限了

直播互动挑战: 高并发压力

  • 在线状态本地化
1
2
3
4
5
6
7
8
9
10
压力: 消息下推环节中消息从一条扇出成十万条。 是消息扇出后的推送

普通聊天场景的扇出逻辑: 查询聊天接收方在哪台接入服务器,然后把消息投递过去,最后由接入服务器通过长连接进行投递

问题:
普通聊天场景,为了进行精准投递避免资源浪费,一般会维护一个中央的“在线状态",逻辑层在这里查询,然后投递到对应网关机
但在直播互动,10万人次的房间,查询量级大

优化:
每个网关机维护本机的连接用户状态, 每条消息全量发送给所有网关机,由网关机自行判断推送

直播互动场景的消息投递

  • 微服务的拆分
1
2
3
4
5
6
7
8
9
10
11
12
下推消息还受制于网关机的带宽、PPS、CPU 等方面的限制,会容易出现单机的瓶颈,
因此当有大型直播活动时,还需对这些容易出现瓶颈的服务进行水平扩容。


拆分: 核心服务和非核心服务, 对核心服务进行扩容
对于核心服务,我们需要隔离出“容易出现瓶颈点的”和“基本不会有瓶颈的”业务。

比如:
核心服务: 发弹幕、打赏、送礼、点赞、消息下推等
非核心服务: 直播回放和第三方系统的同步等

然后在核心服务中: 消息的发送行为和处理一般不容易出现瓶颈, 一个 10w 人的直播间里每秒的互动行为一般超不过 1000

直播互动场景的服务拆分

  • 自动扩缩容
1
2
3
4
监控服务或者机器的一些关键指标, 进行自动扩缩容

业务性能指标: 比如直播间人数、发消息和信令的 QPS 与耗时、消息收发延迟等;
机器性能指标: 主要是通用化的机器性能指标,包括带宽、PPS、系统负载、IOPS 等
  • 智能负载均衡
1
2
3
4
在建立长连接前,客户端先通过一个入口调度服务来查询本次连接应该连接的入口 IP,在这个入口调度服务里根据具体后端接入层机器的具体业务和机器的性能指标,来实时计算调度的权重
负载低的机器权重值高,会被入口调度服务作为优先接入 IP 下发;负载高的机器权重值低,后续新的连接接入会相对更少。

而不单纯是轮询负载,会导致有的机器承载了很多连接,有的则很少

服务高可用:保证核心链路稳定性的流控和熔断机制

流量控制

1
2
3
4
5
6
7
8
9
10
11
12
流控常用算法:
漏桶算法
控制数据注入到网络的速率,平滑网络上的突发流量
它模拟的是一个漏水的桶,所有外部的水都先放进这个水桶,而这个桶以匀速往外均匀漏水,如果水桶满了,外部的水就不能再往桶里倒了

令牌桶算法
控制一个时间窗口内通过的数据量
基本逻辑:
1. 每 1/r 秒往桶里放入一个令牌,r 是用户配置的平均发送速率(也就是每秒会有 r 个令牌放入)。
2. 桶里最多可以放入 b 个令牌,如果桶满了,新放入的令牌会被丢弃。
3. 如果来了 n 个请求,会从桶里消耗掉 n 个令牌。
4. 如果桶里可用令牌数小于 n,那么这 n 个请求会被丢弃掉或者等待新的令牌放入。

全局流控

1
2
对于单机瓶颈的问题,通过单机版的流控算法和组件就能很好地实现单机保护
但在分布式服务的场景下,很多时候的瓶颈点在于全局的资源或者依赖,这种情况就需要分布式的全局流控来对整体业务进行保护。
1
2
3
通用流控方案: 
一般是通过中央式的资源(如:Redis、Nginx)配合脚本来实现全局的计数器,
或者实现更为复杂的漏桶算法和令牌桶算法,比如可以通过 Redis 的 INCR 命令配合 Lua 实现一个限制 QPS(每秒查询量)的流控组件
  • 细粒度控制
1
2
3
4
5
6
在限制 QPS 的时候,流控粒度太粗,没有把 QPS 均匀分摊到每个毫秒里
上一秒的最后一个毫秒和下一秒的第一个毫秒都出现了最大流量,就会导致两个毫秒内的 QPS 翻倍

简单的处理方式:
把一秒分成若干个 N 毫秒的桶,通过滑动窗口的方式,将流控粒度细化到 N 毫秒
基于滑动窗口来统计 QPS,这样也能避免边界处理时不平滑的问题。
  • 流控依赖资源的瓶颈
1
2
3
4
5
6
7
8
9
10
如: 流控使用的 Redis 资源由于访问量太大导致出现不可用的情况

方案: 本地批量预取
让使用限流服务的业务进程,每次从远程资源预取多个令牌在本地缓存,
处理限流逻辑时先从本地缓存消耗令牌,本地消费完再触发从远程资源获取到本地缓存,
如果远程获取资源时配额已经不够了,本次请求就会被抛弃
注意:
本地预取可能会导致一定范围的限流误差
比如:上一秒预取的 10 个令牌,在实际业务中下一秒才用到,这样会导致下一秒业务实际的请求量会多一些
所以对于需要精准控制访问量的场景来说可能不是特别适合

自动熔断机制

针对突发流量,除了扩容和流控外,还有一个能有效保护系统整体可用性的手段就是熔断机制。

1
2
3
4
5
6
7
多依赖的微服务中的雪崩效应: 
为了便于管理和隔离,我们经常会对服务进行解耦,独立拆分解耦到不同的微服务中,微服务间通过 RPC 来进行调用和依赖
一个服务变慢,因为依赖关系,上层级联服务性能变差,最终导致系统整体性能的雪崩

一种常见的方式是手动通过开关来进行依赖的降级,微博的很多场景和业务都有用到开关来实现业务或者资源依赖的降级。
更智能的方式是自动熔断机制:
开源框架: Netflix 公司出品的 Hystrix,以及目前社区很火热的 Resilience4j 等

“限流”, “熔断机制” 和 “缓存” 一起被列为高并发应用工程实现中的三板斧

进阶篇

趣谈linux学习

学习地址

极客时间·趣谈linux

入门

自我测验

测试题1

测试题2

测试题3

测试题4

答案:

  1. A,B,C,D
  2. A,B (实模式下运行, 操作系统启动好像就只有刚开始是实模式, 流程不清楚)
  3. B ()
  4. A,B,C,D
  5. 不会

linux 学习六个坡

  • 熟练使用linux命令
  • 使用linux进行程序设计
  • 了解linux内核机制
  • 阅读linux源码
  • 实验定制linux组件
  • 落到生产实践

linux综述

电脑零件

电脑零件

外包公司业务和linux子系统对应

linux子系统

子系统:

  • 系统调用
  • 进程管理
  • 内存管理
  • 文件
  • 设备
  • 网络

基础几个系统调用

  • fork : 创建进程 ( 由 父进程 调用fork 创建 子进程, 子进程拷贝父进程 ) - 所有会有一个祖宗进程
1
2
3
4
fork 返回值:如果当前进程是子进程,就返回 0;如果当前进程是父进程,就返回子进程的进程号。
这样首先在返回值这里就有了一个区分,然后通过 if-else 语句判断,如果是父进程,还接着做原来应该做的事情;
如果是子进程,需要请求另一个系统调用execve来执行另一个程序,
这个时候,子进程和父进程就彻底分道扬镳了,也就产生了一个分支(fork)了。
  • 分配内存的系统调用,brk 和 mmap
1
2
当分配的内存数量比较小的时候,使用 brk
当分配的内存数量比较大的时候,使用 mmap,会重新划分一块区域
  • 对文件操作的系统调用 - 最重要的:open, close, create, lseek, read, write
1
2
3
4
5
6
对于已经有的文件,可以使用open打开这个文件,close关闭这个文件;
对于没有的文件,可以使用creat创建文件;
打开文件以后,可以使用lseek跳到文件的某个位置;
可以对文件的内容进行读写,读的系统调用是read,写是write

linux中 一切皆文件 - 优势: 统一操作入口

系统初始化

开放架构

  • 计算机核心: CPU
  • CPU和其他设备的连接: 总线(Bus)
  • 设备中最重要的是: 内存
  • CPU

    • 运算单元: 只管计算
    • 数据单元: 内部缓存和寄存器, 暂时存放数据和运算结果
    • 控制单元: 获得下一条指令,然后执行这条指令。 有一个 指令指针寄存器 ,它里面存放的是下一条指令在内存中的地址
  • 总线

    • 地址总线: 我想拿内存中哪个位置的数据
    • 数据总线: 真正的数据
  • 总线标准
    总线标准

8086 原理

8086原理

  • 通用寄存器 (8个 16位 ) - CPU数据单元
    • AX、BX、CX、DX、SP、BP、SI、DI。这些寄存器主要用于在计算过程中暂存数据。 (其中 AX、BX、CX、DX 可以分成两个 8 位的寄存器来使用)
  • CPU控制单元
    • IP 寄存器就是指令指针寄存器(Instruction Pointer Register),指向代码段中下一条指令的位置
    • CS 就是代码段寄存器(Code Segment Register),通过它可以找到代码在内存中的位置
    • DS 是数据段的寄存器,通过它可以找到数据在内存中的位置。
    • SS 是栈寄存器(Stack Register)。栈是程序运行中一个特殊的数据结构,数据的存取后进先出,push入栈,pop出栈

32位处理器: 80386

总线从16位变为32位, 地址位从20位变为32位

32位处理器兼容

  • 数据单元通用寄存器, 指令指针寄存器 扩展后仍然兼容
  • 但段寄存器不兼容: 原先16位总线询20位地址,是通过左移四位达到目的,段的起始地址只能是16的整除地址
    • 现在32位总线询32位地址,无所谓左移,32位4G内存都能访问到。
    • 段的起始地址放在内存的某个地方。这个地方是一个表格,表格中的一项一项是段描述符(Segment Descriptor)。这里面才是真正的段的起始地址。而段寄存器里面保存的是在这个表格中的哪一项,称为选择子(Selector)

段寄存器 寻址 不兼容咋办?

  • 模式切换: 不能无缝兼容,通过模式切换兼容
    • 实模式: 当系统刚刚启动的时候,CPU 是处于实模式的,这个时候和原来的模式是兼容的
    • 保护模式: 切换到保护模式,就能够用到 32 位 CPU 更强大的能力

从BIOS 到 bootloader

BIOS

  • BIOS
    • ROM(Read Only Memory,只读存储器)
    • 内存 RAM(Random Access Memory,随机存取存储器
1
2
3
4
5
6
7
8
9
10
主板上有部分为 ROM: 固化了一些初始化的程序,就是 BIOS (Basic Input and Output System,基本输入输出系统)

内存地址空间: 在 x86 系统中,将空间最上面的 0xF0000 到 0xFFFFF 这 64K 映射给 ROM , 到这部分地址访问的时候,会访问 ROM

当电脑刚加电的时候,会做一些重置的工作
将 CS 设置为 0xFFFF,将 IP 设置为 0x0000,所以第一条指令就会指向 0xFFFF0,正是在 ROM 的范围内。
在这里,有一个 JMP 命令会跳到 ROM 中做初始化工作的代码,于是,BIOS 开始进行初始化的工作。

BIOS: 检查硬件是否完好, 建立一个中断向量表和中断服务程序

bootloader

1
BIOS 寻找 操作系统, 操作系统在硬盘上,BIOS寻找启动盘, 一般在第一个扇区,占 512 字节,而且以 0xAA55 结束

linux系统加载流程

1
2
3
4
5
6
7
8
在Linux 里面有一个工具,叫 Grub2,  就是搞系统启动

1. grub2 第一个要安装的就是 boot.img, 由 boot.S 编译而成,一共 512 字节,正式安装到启动盘的第一个扇区。
这个扇区通常称为 MBR(Master Boot Record,主引导记录 / 扇区)。
BIOS 完成任务后,会将 boot.img 从硬盘加载到内存中的 0x7c00 来运行。
2. boot.img 字节少,做不了太多事, 主要是加载 grub的另一个镜像 core.img
首先加载 core的第一个扇区,diskboot.img, 控制权从boot到diskboot, 加载core的其他镜像, kernel是grub的内核
实模式1M空间太小, lzma_decompress会从 实模式 切换到 保护模式
  • 实模式 切换到 保护模式 工作

    1. 启用分段,就是在内存里面建立段描述符表,将寄存器里面的段寄存器变成段选择子,指向某个段描述符,这样就能实现不同进程的切换了
    2. 启动分页。能够管理的内存变大了,就需要将内存分成相等大小的块
    3. 打开 Gate A20, 8086下是20根地址总线, 到保护模式下, 打开第21根总线,开始工作
  • 总结流程

1
BIOS -》引导扇区 boot.img -》 diskboot.img -》 lzma_decompress.img 实模式切换到保护模式 -》 kernel.img 选择操作系统 -》 启动内核 

内核初始化

  1. 初始进程, 系统创建的第一个进程, 0号进程
  2. 中断门, 处理各种中断(系统调用)
  3. 内存管理模块, 调度模块
  4. 文件系统
  • 1号进程的初始化, 将运行一个用户进程。 有了 内核, 用户 的区分

    • 权限机制:x86将权限分为四个Ring
    • linux使用了 Ring0作为内核态, Ring3作为用户态
    • 系统调用执行 init文件, 内部回复寄存器,指针指向用户态, 进入用户态
    • 用户态祖先进程
  • 2号进程

    • 内核态的进程也应有一个人统一管理起来, 内核态祖先进程
    • 从内核态来看,无论是进程,还是线程,我们都可以统称为任务(Task),都使用相同的数据结构,平放在同一个链表中

系统调用

glibc 对系统调用的封装

Linux 提供了 glibc, 里面是系统调用的细节,封装成更加友好的接口。可以直接用

1
glibc 算是 办事大厅的中介

进程管理

多进程

写代码:用系统调用创建进程

  • 写代码: .h 或 .c 文件, 使用fork系统调用
  • 编译:
    • 结果: 程序的二进制文件 (格式: ELF - Executeable and Linkable Format,可执行与可链接格式 )
    • 过程:

编译过程

设计模式学习

看云 · 设计模式之禅

六大原则

单一职责原则 (Single Responsibility Principle) (简称SRP)

里氏替换原则 (Liskov Substitution Principle)(简称LSP)

面向对象的继承

  • 优点
    • 代码共享,减少创建类的工作量,每个子类都拥有父类的方法和属性;
    • 提高代码的重用性;
    • 提高代码的可扩展性
    • 提高产品或项目的开放性。
  • 缺点
    • 继承是侵入性的。只要继承,就必须拥有父类的所有属性和方法
    • 降低代码的灵活性。子类必须拥有父类的属性和方法
    • 增强了耦合性。当父类的常量、变量和方法被修改时,需要考虑子类的修改。

使用继承时,怎么才能让“利”的因素发挥最大的作用,同时减少“弊”带来的麻烦呢?解决方案是引入里氏替换原则

  • 定义: 第一种

If for each object o1 of type S there is an object o2 of type T such that for all programs P defined in terms of T,the behavior of P is unchanged when o1 is substituted for o2 then S is a subtype of T.

如果对每一个类型为S的对象o1,都有类型为T的对象o2,使得以T定义的所有程序P在所有的对象o1都代换成o2时,程序P的行为没有发生变化,那么类型S是类型T的子类型

  • 定义: 第二种

Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it.

所有引用基类的地方必须能透明地使用其子类的对象

1
通俗定义: 只要父类能出现的地方子类就可以出现,而且替换为子类也不会产生任何错误或异常, 但是,反过来就不行了,有子类出现的地方,父类未必就能适应

里氏替换原则 定义了良好的继承规范

  • 子类必须完全实现父类的方法
  • 子类可以有自己的个性
  • 覆盖或实现父类的方法时输入参数可以被放大
  • 覆写或实现父类的方法时输出结果可以被缩小

依赖倒置原则 (Dependence Inversion Principle)(简称DIP)

定义

  • 高层模块不应该依赖低层模块,两者都应该依赖其抽象
  • 抽象不应该依赖细节
  • 细节应该依赖抽象
1
2
3
4
底层模块: 不可分割原子逻辑
高层模块: 原子逻辑的再组装
抽象: 接口, 不能直接被实例化
细节: 实现类, 实现接口产生的类,可以直接实例化

更精简的定义: 面向接口编程 - OOD(Object-Oriented Design,面向对象设计)的精髓之一

优点

减少类间的耦合性,提高系统的稳定性,降低并行开发引起的风险,提高代码的可读性和可维护性

接口隔离原则

接口尽量细化,同时接口中的方法尽量少

迪米特法则 (Law of Demeter,LoD)

也称 最少知识原则(Least Knowledge Principle,LKP)

  • 核心观念: 类间解耦,弱耦合,只有弱耦合了以后,类的复用率才可以提高

开闭原则

应尽量通过扩展软件实体的行为来实现变化,而不是通过修改已有的代码来完成变化, 它是为软件实体的未来事件而制定的对现行开发设计进行约束的一个原则

23种设计模式

单例模式

  • 定义
1
2
一个类只能生成一个对象, 自行实例化并向整个系统提供这个实例 
通过定义一个私有访问权限的构造函数,避免被其他类new出来一个对象
  • 应用
1
2
3
4
5
6
7
8
9
10
11
12
内存中只有一个实例
优点:
减少了内存开支
减少了系统的性能开销
避免对资源的多重占用
在系统设置全局的访问点,优化和共享资源访问

如: 读取配置,一个写文件动作

缺点:
扩展困难
对测试不利,单例模式没有完成不能测试

工厂方法模式

  • 定义
1
2
Define an interface for creating an object,but let subclasses decide which class to instantiate.Factory Method lets a class defer instantiation to subclasses.
(定义一个用于创建对象的接口,让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其子类。)
  • 优点
1
2
3
良好封装性: 一个对象创建是有条件约束的,如一个调用者需要一个具体的产品对象,只要知道这个产品的类名,降低模块间的耦合
扩展优秀: 在增加产品类的情况下,只要适当地修改具体的工厂类或扩展一个工厂类,就可以完成“拥抱变化”

抽象工厂模式

操作系统-同步互斥

进程的并发执行

进程互斥

1
2
3
4
竞争条件: 多进程读写共享数据,结果取决于进程执行的时序
进程互斥: 多进程使用共享资源,资源排他性使用。
临界资源,互斥资源,共享变量: 一次只能被一个进程使用
临界区(互斥区):各个进程中对某个临界资源实施操作的程序片段

实现进程互斥的方案

  • 软件方案

dekker解法

1
2
两个进程P,Q , 以标志pturn, qturn 的true,false标识是否想进入临界区的意向
然后以turn标志,处理两个都有意向的时候,某一个进行谦让设置为false,让另一个进入临界区

Peterson解法

1
2
3
4
进程i:
enter_region(i)
进入临界区
leave_region(i)
  • 硬件方案

屏蔽中断, TSL(XCHG)指令

1

进程同步

多个进程发送的事件存在时序关系,需要合作完成一项任务

操作系统-处理器调度

CPU调度 概念

1
2
3
4
5
6
控制,协调 多个进程对CPU的竞争:
即 按一定的调度算法从 就绪队列中 选择一个进程,把CPU使用权交给该进程
如果没有就绪进程,系统会安排一个 系统空闲进程或idle进程

系统场景: 多个就绪进程,多个CPU
决策 给哪个进程分配哪个CPU

调度要解决的问题

1
2
3
WHAT:   按什么原则选择下一个执行的进程 -- 调度算法
WHEN: 何时进行选择 -- 调度时机
HOW: 如何让被选中的进程上CPU运行 -- 调度过程 (进程的上下文切换)
  • 调度时机
1
2
3
4
5
6
1.进程 正常终止 或  异常终止
2.新进程创建 或 等待进程变为就绪进程
3.一个进程从运行态进入阻塞态
4.一个进程从运行态变为就绪态 (时钟中断: 时间片到了)

即: 内核对 中断/异常/系统调用 处理后返回用户态时, 重新调度
  • 调度过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
是一个进程让出处理器,由另外一个进程占用处理器的过程

包括工作:
切换全局页目录以加载一个新的地址空间
切换内核栈和硬件上下文

切换过程包括了: 对原来运行进程各种状态的保存, 对新的进程各种状态的恢复

上下文切换开销:
直接开销: 内核完成切换花费的CPU时间
保存和恢复寄存器
切换地址空间(相关指令比较昂贵)
间接开销:
高速缓存(Cache), 缓冲区缓存(buffer cache), TLB(translation lookup buffer) 失效
  • CPU调度算法

不同角度有不同的要求

调度算法不同角度的要求

1
2
3
4
5
6
7
调度算法衡量指标: 
吞吐量: 单位时间完成的进程数量
周转时间: 每个进程从提出请求到完成运行完成的时间
响应时间: 从进程提出请求到第一次回应的时间
其他:
CPU利用率: CPU有效工作的时间比率
等待时间: 每个进程在 就绪队列中 等待的时间

调度算法 考虑的问题

1
2
3
4
5
6
进程控制块PCB: 
需要记录哪些 与CPU调度相关的 信息
进程优先级 及 就绪队列的组织
抢占式调度 与 非抢占式调度
I/O密集型 与 CPU密集型 进程
时间片
  • 进程优先级
1
2
3
4
5
6
7
优先级,优先数: 
优先数的大小 在不同操作系统中 表示的优先级高低不同 (可能数字小的高,也可能数字大的高)

静态优先级:
进程创建时指定,运行过程中不会改变
动态优先级:
运行过程中动态变化,如等待时间长的提升优先级
  • 进程就绪队列组织
1
2
3
4
按优先级排队:
根据优先级进入不同的就绪队列
其他:
创建时进入最高级队列,时间片轮转,动态降低优先级
  • 抢占式 和 非抢占式
1
2
3
占用CPU的方式: 
抢占式: 有比正在运行的进程 优先级更高的进程进入就绪队列时, 系统可强行剥夺CPU,提供给更高级进程
不可抢占: 某一个进程被调度运行后,除非自身原因放弃CPU,不然能一直运行
  • I/O密集型 与 CPU密集型 进程
1
2
3
4
5
6
进程执行过程的行为划分:    
I/O密集型: 频繁进行I/O,通常会花费很多时间等待 I/O 的完成
(占用CPU很短的时间就会让出CPU进入I/O等待,所以一般调度系统都会对I/O型进行偏好)

CPU密集型(计算密集型): 需要大量的CPU时间进行计算
(占用CPU时间长)
  • 时间片
1
2
3
4
5
6
7
8
一个时间段: 分配给调度到CPU上的进程,允许进程占用CPU运行的时间长度

如何选择时间片:
进程切换的开销
对响应时间的要求
就绪进程个数
CPU能力
进程的行为

批处理系统 中采用的 调度算法

1
2
3
4
5
6
7
8
9
10
11
12
13
先来先服务 ( FCFS  -- first come first serve )
先进先出, 非抢占式 ( 问题: 短的在长的后面 ,周转时间长)
最短作业优先( SJF -- shortest job first )
具有最短完成时间的进程优先执行, 非抢占式 ( 优化周转时间, 问题:长作业一直得不到执行,饥饿现象)
最短剩余时间优先 ( SRTN -- shortest remaining time next )
变为抢占式,一个就绪进程比正在运行进程具有更短的完成时间,进行抢占 ( 优化周转时间 )
最高响应比优先 ( HRRN -- highest response ratio next )
综合算法, 先计算进程响应比R, 选择R最高的进程进行执行
R = 周转时间 / 处理时间
= (等待时间 + 处理时间)/ 处理时间
= 1 + (等待时间 / 处理时间)
所以相同等待时间,处理时间越多,响应比越小。 即优先级低
然后等待时间变大,响应比就会变大。 即优先级慢慢变高

交互式系统中的调度算法

  • 时间片轮转 (Round Robin)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
为短作业改善平均响应时间
解决思路:
周期性切换
每个进程分配一个时间片
时钟中断 - 轮换

时间片分配问题:
太长: 降级为先来先服务, 延长了短作业的响应时间
太短: 进程切换浪费CPU资源, 响应时间变长
设计为: CPU开销 进程切换 为 时间片 的1%

优点: 公平,交互式计算,响应时间快
缺点: 进程切换,CPU花费较高。 对不同大小的进程有利,对相同大小的进程响应时间反而会高

  • 最高优先级调度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
系统进程 优先级 高于 用户进程
前台进程 优先级 高于 后台进程
操作系统 更偏好 I/O型进程

优先级 可以是静态不变的, 也可以是动态调整的。 (以 优先数 决定 优先级)
就绪队列按照 优先级 组织
实现简单: 不公平 (优先级低的进程 饥饿)

基于优先级的抢占式:
优先级反转问题:
一个低优先级进程 持有 高优先级进程需要的资源, 高优先级进程等待低优先级无法执行
解决方案:
设置优先级上限
优先级继承
使用中断禁止

  • 多级反馈队列 调度算法 (feedback)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unix 的一个分支 BSD 5.3版本采用的调用算法
考虑之前的算法之后的一个 择中权衡后的 综合调度算法

思路:
设置 多个 就绪队列, 第一级队列优先级最高
给不同就绪队列中的进程分配不同的时间片,第一队列时间片最小; 随着队列优先级降低,时间片增大
按优先级从高到低进行调度
每个队列按 时间片轮转的方式 进行调度
新创建进程就绪后进入 第一级队列
进程用完时间片而放弃CPU,则进入下一级队列
由于阻塞而放弃CPU的进程进入相应的等待队列,等待事件发生,进入原先队列 (队首还是队尾,时间片继续还是重新,可以看情况设计,反应对该类进程的偏好程度)

若是抢占式的:
有更高优先级的进行就绪,可抢占CPU,原运行进程进入 原优先级队列

调度算法总结

多处理器调度算法设计考虑

1
2
3
4
5
不仅要选择哪个进程, 还有选择 在哪个处理器上执行
进程在多个CPU之间迁移的开销
高速缓存实现,TLB失效
尽可能 让进程在总在同一个CPU上执行
考虑负载均衡问题 (使所有CPU保持均衡忙碌状态)

典型系统使用的调度算法

1
2
3
4
5
UNIX    动态优先数 算法
BSD5.3 多级反馈队列
LINUX 抢占式调度 (目前是 CFS 完全公平调度算法)
Windows 基于优先级的抢占式多任务调度
Solaris 综合调度算法

Windows 线程调度

1
2
3
4
5
6
7
调度单位是 线程
基于 动态优先级,抢占式调度,结合 时间配额的调整

就绪进程 按照 优先级进入相应队列
系统总是选择 优先级最高的就绪线程 运行
同一优先级的线程, 按时间片轮转进行调度
多CPU系统中, 允许多个线程并行运行

引发线程调度的条件

1
2
3
4
5
6
7
8
9
跟之前进程相同的4个条件
1.线程 正常终止 或 异常终止
2.新线程创建 或 等待线程变为就绪进程
3.一个线程从运行态进入阻塞态
4.一个线程从运行态变为就绪态 (时钟中断: 时间片到了)

增加条件
5. 线程优先级改变
6. 线程改变了它的 亲和(affinity)处理机集合 - 线程只能在这几个处理机上执行,其他处理机即便空闲了该线程也不能执行

windows 使用 32 个线程优先级 - 分为 三类

1
2
3
4
5
6
1. 实时优先级 ( 31 - 16 ) 
不会改变优先级
2. 可变优先级 ( 15 - 1 )
优先级可在一定范围内 升高 或 降低。 (可区分 基本优先级 和 当前优先级 )
3. 系统线程 ( 0 )
零页线程: 用于对系统中空闲物理页面清零

线程的时间配额

1
2
3
4
5
6
一个配额单位的整数
线程用完时间配额后,如果没有相同优先级的其他线程, 系统将重新分配一个时间配额给该线程,让它继续运行

用法:
两个线程,CPU型,I/O型, 如果直接提高CPU型线程的优先级,则CPU型线程一直运行,I/O型得不到运行。而提高CPU型进程的时间配置,就可以了

线程调度策略

1
2
3
4
5
6
7
8
9
10
11
1. 主动切换
线程等待事件,运行态 转为 阻塞态 。 系统调度新的线程运行
2. 抢占
上面线程事件发生唤醒, 优先级高,抢占CPU, 被抢占线程退回就绪队列队首, 如果是实时优先级,重新分配时间配额,如果是可变优先级,分配剩余时间配额
3. 时间配额用完
线程优先级没有降低
同优先级就绪队列有其他线程,调度其他线程运行,该线程到队列队尾
没有其他线程,分配新的时间配置,继续运行
线程优先级降低了
选择更高优先级线程执行

线程优先级提升 和 时间配额调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Windows调度策略
如何体现对某类线程的倾向性 ?
如何解决饥饿现象 ?
如何改善 系统吞吐量,响应时间等整体特征?

1. 提升线程 优先级 ,针对可变优先级范围 (1-15)
I/O操作完成 (临时提升,保证更快上CPU运行处理数据)(会把时间配额减1)
信号量,事件等待结束
前台进程中的线程, 完成一个等待操作
窗口活动 唤醒窗口线程
线程处于就绪态 并超过一定时间没有运行-饥饿
( 系统线程 "平衡集管理器", 扫描就绪队列,发现等待超300个时钟周期的饥饿线程, 优先级提升为最大的15,分配4倍的时间配额,线程运行完时间配额后,衰减回原来优先级)

2. 给线程分配一个很大的时间配额