从上面可以看出Spring主要分成六个模块：

1、Spring核心容器

​ 核心容器是Spring框架的重要组成部分，也可以说是Spring框架的基础。他在整个框架中的作用是负责管理对象的创建，管理，配置等等的操作。其主要包含spring-core，spring-beans，spring-context，spring-expression，spring-context-support组件。

​ 核心容器提供spring框架的基本功能。Spring以bean的方式组织和管理Java应用中的各个组件及其关系。Spring使用BeanFactory来产生和管理Bean，它是工厂模式的实现。BeanFactory使用控制反转(IoC)模式将应用的配置和依赖性规范与实际的应用程序代码分开。BeanFactory使用依赖注入的方式提供给组件依赖。主要实现控制反转IoC和依赖注入DI、Bean配置以及加载。

spring context

​ Spring上下文是一个配置文件，向Spring框架提供上下文信息。Spring上下文包括企业服务，如JNDI、EJB、电子邮件、国际化、校验和调度功能。提供框架式Bean访问方式，其他程序可以通过Context访问Spring的Bean资源。

2、面向切面编程

​ Spring框架还提供了面向切面编程的能力，利用面向切面编程，可以实现一些面向对象编程无法很好实现的操作。例如，将日志，事务与具体的业务逻辑解耦。其主要包含spring-aop，spring-aspects组件。

​ 通过配置管理特性，Spring AOP 模块直接将面向方面的编程功能集成到了Spring框架中。所以，可以很容易地使 Spring框架管理的任何对象支持 AOP。Spring AOP 模块为基于 Spring 的应用程序中的对象提供了事务管理服务。通过使用 Spring AOP，不用依赖 EJB 组件，就可以将声明性事务管理集成到应用程序中。AOP把一个业务流程分成几部分，例如权限检查、业务处理、日志记录，每个部分单独处理，然后把它们组装成完整的业务流程。每个部分被称为切面或关注点。

AOP的实现原理为动态代理技术，一共有两种代理模式：

（1）ProxyFactoryBean代理工厂对象

Spring内置代理类，引入一个中间层，能够创建不同类型的对象，利用它可以实现任何形式的AOP。

（2）TransactionProxyFactoryBean事务代理工厂对象

常用在数据库编程上，Spring利用TransactionProxyFactoryBean对事务进行管理，在指定方法前利用AOP连接数据库并开启事务，然后在指定方法返回后利用AOP提交事务并断开数据库。

3、Instrumentation

​ 该模块提供了为JVM添加代理的功能，该模块包含spring-instrument，spring-instrument-tomcat组件，使用较少，不必过分关注。

4、数据访问与集成

​ Spring框架为了简化数据访问的操作，包装了很多关于数据访问的操作，提供了相应的模板。同时还提供了使用ORM框架的能力，可以与很多流行的ORM框架进行整合，如hibernate，mybatis等等的著名框架。还实现了数据事务的能力，能够支持事务。包含spring-jdbc，spring-tx，spring-orm，spring-oxm，spring-jms，spring-messaging组件。

Spring ORM（Object Relation Mapper）对象关系映射模块

​ Spring 与所有的主要的ORM框架都集成的很好，包括hibernate、JDO实现、TopLink和IBatis SQL Map等。Spring为所有的这些框架提供了模板之类的辅助类，达成了一致的编程风格。
Spring的ORM模块对ORM框架如Hibernate等进行了封装，Spring能够管理、维护Hibernate，使用时可直接继承HibernateDaoSupport类，该类内置一个HibernateTemplate。Hibernate的配置也转移到Spring配置文件中。

（注：ORM是通过使用描述对象和数据库之间映射的元数据，ORM框架采用元数据来描述对象–关系映射细节，元数据一般采用xml格式，并且存放在专门的对象–映射文件中）

5、Web和远程调用

​ Spring框架支持Web开发，以及与其他应用远程交互调用的方案。包含spring-web，spring-webmvc，spring-websocket，spring-webmvc-portlet组件。

Spring Web模块

Web模块建立在应用程序上下文模块之上，为基于Web的应用程序提供了上下文。Web层使用Web层框架，可选的，可以是Spring自己的MVC框架，或者提供的Web框架，如Struts、Webwork、tapestry和jsf。

Web模块用于整合Web框架，将Web框架也纳入Spring的管理之中。如Spring提供继承方式与代理方式整合Struts，继承方式不需要更改任何配置文件，只把Action继承自ActionSupport即可，但会对Spring产生依赖。代理方式需要在struts-config.xml中配置，由Spring全盘代理，因此可以使用Spring的各种资源、拦截器等。

Spring MVC

MVC框架是一个全功能的构建Web应用程序的MVC实现。通过策略接口，MVC框架变成为高度可配置的。Spring的MVC框架提供清晰的角色划分：控制器、验证器、命令对象、表单对象和模型对象、分发器、处理器映射和视图解析器。Spring支持多种视图技术。

Spring MVC 的工作流程：

（1） 客户端发送请求，请求到达 DispatcherServlet 主控制器。
（2） DispatcherServlet 控制器调用 HandlerMapping 处理。
（3） HandlerMapping 负责维护请求和 Controller 组件对应关系。 HandlerMapping 根据请求调用对应的 Controller 组件处理。
（4） 执行 Controller 组件的业务处理，需要访问数据库，可以调用 DAO 等组件。
（5）Controller 业务方法处理完毕后，会返回一个 ModelAndView 对象。该组件封装了模型数据和视图标识。
（6）Servlet 主控制器调用 ViewResolver 组件，根据 ModelAndView 信息处理。定位视图资源，生成视图响应信息。
（7）控制器将响应信息给用户输出。

6、Spring测试

​ Spring框架提供了测试的模块，可以实现单元测试，集成测试等等的测试流程，整合了JUnit或者TestNG测试框架。包含spring-test组件。

​ 以上就是Spring框架的几个主要模块。而在实际的开发过程中，不必要引入所有的Jar包，只需要引入与自己项目相关的库就行了。例如，只需要Spring框架的容器功能，实现依赖注入，那么只需要引入核心框架的几个库就完成了，其他模块例如Aop模块的库是没有必要引入的。

很多 SQL 查询都是以 SELECT 开始的。不过，最近我跟别人解释什么是窗口函数，我在网上搜索”是否可以对窗口函数返回的结果进行过滤“这个问题，得出的结论是”窗口函数必须在 WHERE 和 GROUP BY 之后，所以不能”。于是我又想到了另一个问题：SQL 查询的执行顺序是怎样的？

好像这个问题应该很好回答，毕竟自己已经写了上万个 SQL 查询了，有一些还很复杂。但事实是，我仍然很难确切地说出它的顺序是怎样的。

SQL 查询的执行顺序

于是我研究了一下，发现顺序大概是这样的。SELECT 并不是最先执行的，而是在第五个。

这张图回答了以下这些问题

这张图与 SQL 查询的语义有关，让你知道一个查询会返回什么，并回答了以下这些问题：

• 可以在 GRROUP BY 之后使用 WHERE 吗？（不行，WHERE 是在 GROUP BY 之后！）
• 可以对窗口函数返回的结果进行过滤吗？（不行，窗口函数是 SELECT 语句里，而 SELECT 是在 WHERE 和 GROUP BY 之后）
• 可以基于 GROUP BY 里的东西进行 ORDER BY 吗？（可以，ORDER BY 基本上是在最后执行的，所以可以基于任何东西进行 ORDER BY）
• LIMIT 是在什么时候执行？（在最后！）
• 但数据库引擎并不一定严格按照这个顺序执行 SQL 查询，因为为了更快地执行查询，它们会做出一些优化，这些问题会在以后的文章中解释。

所以：

• 如果你想要知道一个查询语句是否合法，或者想要知道一个查询语句会返回什么，可以参考这张图；
• 在涉及查询性能或者与索引有关的东西时，这张图就不适用了。

混合因素：列别名

有很多 SQL 实现允许你使用这样的语法：

1
2
3

SELECT CONCAT(first_name, ' ', last_name) AS full_name, count(*)
FROM table
GROUP BY full_name

从这个语句来看，好像 GROUP BY 是在 SELECT 之后执行的，因为它引用了 SELECT 中的一个别名。但实际上不一定要这样，数据库引擎可以把查询重写成这样：

1
2
3

SELECT CONCAT(first_name, ' ', last_name) AS full_name, count(*)
FROM table
GROUP BY CONCAT(first_name, ' ', last_name)

这样 GROUP BY 仍然先执行。

数据库引擎还会做一系列检查，确保 SELECT 和 GROUP BY 中的东西是有效的，所以会在生成执行计划之前对查询做一次整体检查。

数据库可能不按照这个顺序执行查询（优化）

在实际当中，数据库不一定会按照 JOIN、WHERE、GROUP BY 的顺序来执行查询，因为它们会进行一系列优化，把执行顺序打乱，从而让查询执行得更快，只要不改变查询结果。

这个查询说明了为什么需要以不同的顺序执行查询：

1
2
3

SELECT * FROM
owners LEFT JOIN cats ON owners.id = cats.owner
WHERE cats.name = 'mr darcy'

如果只需要找出名字叫“mr darcy”的猫，那就没必要对两张表的所有数据执行左连接，在连接之前先进行过滤，这样查询会快得多，而且对于这个查询来说，先执行过滤并不会改变查询结果。

数据库引擎还会做出其他很多优化，按照不同的顺序执行查询，不过我并不是这方面的专家，所以这里就不多说了。

explain

explain显示了mysql如何使用索引来处理select语句以及连接表。可以帮助选择更好的索引和写出更优化的查询语句。

使用方法，在select语句前加上explain就可以了, 如：

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

explain select c_user.*, t.cust_id, ifnull(tcc.tradeamt, 0) tradeamt,  ifnull(tcc.commission,0) commission, ifnull(ih.is_hadtrade, 0) is_hadtrade
  from crm.c_user
    left join crm.trade_fund_account t on c_user.id = t.c_user_id and t.cust_id > 0
     left join (select cust_id, sum(amount_trade) tradeamt, max(commission_ft_current_month) commission 
                     from crm.trade_commission tc 
                    where tc.bizdate between 20171001 and 20171031 
                        and tc.bid = '00000000000000007'
                group by cust_id
                ) tcc on tcc.cust_id = t.cust_id 
    left join (select cust_id, sum(amount_trade), (case when sum(amount_trade) > 0 then 1 else 0 end) is_hadtrade
                   from crm.trade_commission tc 
                  where tc.bid = '00000000000000007' 
                      and tc.bizdate < 20171022
                  group by tc.cust_id
              ) ih on ih.cust_id = t.cust_id 
 where c_user.bapp_broker_id = '00000000000000007'
   and is_hadtrade = 1

extend

​ extended关键字：仅对select语句有效，在explain后使用extended关键字，可以显示filtered列显示了通过条件过滤出的行数的百分比估计值。
​ 也可以通过show warnings显示扩展信息，输出中的 Message值SHOW WARNINGS显示优化程序如何限定SELECT语句 中的表名和列名， SELECT应用重写和优化规则后的外观，以及可能有关优化过程的其他说明。

EXPLAIN 各个列的含义

id

查询的序号，包含一组数字，表示查询中执行select子句或操作表的顺序

两种情况：

• id相同，执行顺序从上往下;
• id不同，id值越大，优先级越高，越先执行

select_type

查询类型，主要用于区别普通查询，联合查询，子查询等的复杂查询

1. simple —— 简单的select查询，查询中不包含子查询或者UNION
2. primary —— 查询中若包含任何复杂的子部分，最外层查询被标记
3. subquery —— 在select或where列表中包含了子查询
4. derived —— 在from列表中包含的子查询被标记为derived（衍生），MySQL会递归执行这些子查询，把结果放到临时表中
5. union —— 如果第二个select出现在UNION之后，则被标记为UNION，如果union包含在from子句的子查询中，外层select被标记为derived
6. union result —— UNION 的结果

table

输出的行所引用的表

type

显示联结类型，显示查询使用了何种类型，按照从最佳到最坏类型排序

1. system：表中仅有一行（=系统表）这是const联结类型的一个特例。
2. const：表示通过索引一次就找到，const用于比较primary key或者unique索引。因为只匹配一行数据，所以如果将主键置于where列表中，mysql能将该查询转换为一个常量
3. eq_ref：唯一性索引扫描，对于每个索引键，表中只有一条记录与之匹配。常见于唯一索引或者主键扫描
4. ref：非唯一性索引扫描，返回匹配某个单独值的所有行，本质上也是一种索引访问，它返回所有匹配某个单独值的行，可能会找多个符合条件的行，属于查找和扫描的混合体
5. range：只检索给定范围的行，使用一个索引来选择行。key列显示使用了哪个索引，一般就是where语句中出现了between,in等范围的查询。这种范围扫描索引扫描比全表扫描要好，因为它开始于索引的某一个点，而结束另一个点，不用全表扫描
6. index：index 与all区别为index类型只遍历索引树。通常比all快，因为索引文件比数据文件小很多。
7. all：遍历全表以找到匹配的行

注意:一般保证查询至少达到range级别，最好能达到ref。

possible_keys

指出MySQL可能使用哪个索引在该表中找到行

key

显示MySQL实际决定使用的键(索引)。如果没有选择索引,键是NULL。查询中如果使用覆盖索引，则该索引和查询的select字段重叠。

key_len

表示索引中使用的字节数，该列计算查询中使用的索引的长度在不损失精度的情况下，长度越短越好。如果键是NULL,则长度为NULL。该字段显示为索引字段的最大可能长度，并非实际使用长度。

ref

显示索引的哪一列被使用了，如果有可能是一个常数，哪些列或常量被用于查询索引列上的值

rows

根据表统计信息以及索引选用情况，大致估算出找到所需的记录所需要读取的行数

filtered

显示了通过条件过滤出的行数的百分比估计值。

Extra

包含不适合在其他列中显示，但是十分重要的额外信息

1. Using filesort：说明mysql会对数据适用一个外部的索引排序。而不是按照表内的索引顺序进行读取。MySQL中无法利用索引完成排序操作称为“文件排序”
2. Using temporary：使用了临时表保存中间结果，mysql在查询结果排序时使用临时表。常见于排序order by和分组查询group by。
3. Using index：表示相应的select操作用使用覆盖索引，避免访问了表的数据行。如果同时出现using where，表名索引被用来执行索引键值的查找；如果没有同时出现using where，表名索引用来读取数据而非执行查询动作。
4. Using where：表明使用where过滤
5. using join buffer：使用了连接缓存
6. impossible where：where子句的值总是false，不能用来获取任何元组
7. select tables optimized away：在没有group by子句的情况下，基于索引优化Min、max操作或者对于MyISAM存储引擎优化count（*），不必等到执行阶段再进行计算，查询执行计划生成的阶段即完成优化。
8. distinct：优化distinct操作，在找到第一匹配的元组后即停止找同样值的动作。

一、MySQL逻辑架构

二、MySQL基本架构

​ 对于MySQL来说，虽然经历了多个版本迭代（MySQL5.5,MySQL 5.6,MySQL 5.7,MySQL 8）,但每次的迭代，都是基于MySQL基架的，MySQL基架大致包括如下几大模块组件：

1、MySQL向外提供的交互接口(Connectors)

Connectors组件，是MySQL向外提供的交互组件，如java,.net,php等语言可以通过该组件来操作SQL语句，实现与SQL的交互。

2、管理服务组件和工具组件(Management Service & Utilities)

提供对MySQL的集成管理，如备份(Backup),恢复(Recovery),安全管理(Security)等

3、连接池组件(Connection Pool)

负责监听对客户端向MySQL Server端的各种请求，接收请求，转发请求到目标模块。每个成功连接MySQL Server的客户请求都会被创建或分配一个线程，该线程负责客户端与MySQL Server端的通信，接收客户端发送的命令，传递服务端的结果信息等。

4、SQL接口组件(SQL Interface)

接收用户SQL命令，如DML,DDL和存储过程等，并将最终结果返回给用户。

5、查询分析器组件(Parser)

首先分析SQL命令语法的合法性，并尝试将SQL命令解析成抽象语法树，若解析失败，则提示SQL语句不合理

1

SELECT id, name FROM t_user WHERE status = 'ACTIVE' AND age > 18

6、优化器组件(Optimizer)

对SQL命令按照标准流程进行优化分析。

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

explain select c_user.*, t.cust_id, ifnull(tcc.tradeamt, 0) tradeamt,  ifnull(tcc.commission,0) commission, ifnull(ih.is_hadtrade, 0) is_hadtrade
  from crm.c_user
    left join crm.trade_fund_account t on c_user.id = t.c_user_id and t.cust_id > 0
     left join (select cust_id, sum(amount_trade) tradeamt, max(commission_ft_current_month) commission 
                     from crm.trade_commission tc 
                    where tc.bizdate between 20171001 and 20171031 
                        and tc.bid = '00000000000000007'
                group by cust_id
                ) tcc on tcc.cust_id = t.cust_id 
    left join (select cust_id, sum(amount_trade), (case when sum(amount_trade) > 0 then 1 else 0 end) is_hadtrade
                   from crm.trade_commission tc 
                  where tc.bid = '00000000000000007' 
                      and tc.bizdate < 20171022
                  group by tc.cust_id
              ) ih on ih.cust_id = t.cust_id 
 where c_user.bapp_broker_id = '00000000000000007'
   and is_hadtrade = 1

7、缓存主件(Caches & Buffers)

缓存和缓冲组件

8、插件式存储引擎(Pluggable Storage Engines)

9、物理文件(File System)

三、InnoDB存储引擎

1）、 当事务要修改一条记录时，Innodb需要将该记录从Disk中读到BP（Buffer Pool）中。当事务提交后（commit），BP当中的page的记录被修改，这时BP中page就和Disk中的page不一致了，所以这时候BP中的page就是Dirty Page, 需要等待刷新到Disk中；

2）、假如在BP的Dirty Pages刷新到Disk前，系统断电了那么Dirty Page中的数据修改是不是就全部丢失了呢？答案是不会的，这就是Redo Log(innodb_flush_log_at_trx_commit=1)要做的事情了。在事务提交时候，事务中的更新操作会立即保存到Redo Log. 所以就算BP中的Dirty Page在断电后全部丢失，MySQL在重启时，仍可以根据Redo Log来恢复数据；

3）、好了，现在想象一下，假如Dirty Page在flush到disk的过程中发生断电，导致部分数据丢失，Redo Log还能不能恢复这部分数据。答案是不行的，因为mysql在恢复的时候是根据page的checksum来决定这个page是否需要恢复，而这个checksum就是这个page最后一个事务的事务号。这就是partial write的问题，这时候就需要double write了；

partial write是指mysql在将数据写到数据文件的时候, 会出现只写了一半但由于某种原因剩下的数据没有写到innodb file上. 出现这种问题可能是由于系统断电, mysql crash造成的, 而造成这个问题更根本的原因是由于mysql 的page size跟系统文件的page size不一致, 导致在写数据的时候, 系统并不是把整个buffer pool page一次性写到disk上,所以当写到一半时, 系统断电,partial write也就产生了; 如果partial write产生, 会发生什么问题呢? 因为我们知道在flush buffer cache的时候,其实redo log已经写好了. 为什么还需要担心partial write呢? 这是因为mysql在恢复的时候是通过检查page的checksum来决定这个page是否需要恢复的, checksum就是当前这个page最后一个事务的事务号; 如果系统找不到checksum, mysql也就无法对这行数据执行写入操作;

4）、double write的作用就是在mysql将数据刷新到硬盘的时候，先将数据写到double write的空间，然后再某个时刻再把数据写到Disk中。

InnoDB架构

下图显示了组成InnoDB存储引擎架构的内存和磁盘结构。

有关每个结构的信息，请参阅第15.5节“InnoDB内存结构”和第15.6节“InnoDB磁盘结构”。

InnoDB内存结构

缓冲池(buffer pool)

1）、innodb_buffer_pool缓冲池提高数据库整体性能。

2）、innodb读取页操作时，先将从磁盘读到的页放在缓冲池中，下次再次读取，先判断是否缓存命中，若否，则读磁盘中的页

3）、事务提交后,InnoDB首先在buffer pool中找到对应的页,把事务更新到 buffer poll 中.

​ 当刷新脏页到磁盘时,缓冲区都干了什么? 缓冲区把脏页拷贝到doublewrite buffer，doublewirte buffer把脏页刷新到double write磁盘(这也是一次顺序IO),再把脏页刷新到数据文件中。当然buffer pool中还有其他组件,也非常重要,如插入缓冲（change buffer）,该缓冲区是为了高效维护二级非唯一索引所做的优化,把多次IO转化为一次IO来达到快速更新的目的

4）、mysql crash时，buffer pool中的数据都会丢失。

​ innodb数据文件中，会存储checkpoint信息，redo log中也存储checkpoint信息。InnoDB会对比数据文件ibd和redo log中的checkpoint信息，找出最后一次checkpoint对应的log sequence number，通过redo log的变更记录重新应用到数据库

更改缓冲区（change buffer）

• 原来就是insert buffer，后来随着update和delete缓冲加入改为change buffer。

• 缓存对二级索引的变更。二级索引通常是非唯一的，并且二级索引中的插入以相对随机的顺序发生。

log buffer

1、概念

1）、InnoDB存储引擎是基于磁盘存储的，并将其中的记录按照页的方式进行管理

• bp(buffer pool)：InnoDB数据库page的缓存。

• page：对InnoDB中数据的任何修改，首先在bp的page上进行。修改后的page标记为dirty page。

• flush list：存放dirty page，后续由专门的thread写入磁盘中。

2）、使用bp的好处：避免每次对page的修改都进行IO操作，将多次对页面的修改合并成一次IO操作。

• 引入问题：会造成数据的不一致性，RAM和Disk中数据不一致。
• 解决(数据不一致性)：使用redo log，将所有对page进行的修改操作，都写入一个专门的文件中数据库启动时，会从中恢复。
• redo log的影响：延迟了bp中page刷新到磁盘，提高了数据库的吞吐量。 额外的redo log顺序IO的写入开销，以及数据库启动时使用redo log恢复所需时间。

2、redo log相关参数

show variables like “%innodb_log%”;

• innodb_log_file_size 指定redo log日志文件大小，默认48M

• innodb_log_files_in_group redo log日志文件组中文件的数量，默认2个，ib_logfile0和ib_logfile1

• innodb_log_buffer_size redo log buffer的大小，默认为16M

日志组中的文件大小是一致的，以循环的方式运行。ib_logfile0写满时，切换到ib_logfile1，ib_logfile1写满时，再次切换到ib_logfile0。

3、redo log写入过程

1）、redo log buffer 向 redo log file 写，是按512个字节，也就是一个扇区的大小进行写入。扇区是写入的最小单位。

​ 参数innodb_flush_log_at_trx_commit用来控制事务日志刷新到磁盘的策略。

2）、将redo log buffer中的内容刷新到磁盘的redo log file（ib_logfile）中的条件。

• 保证日志先行，每次事务commit前，都会将redo log刷新到磁盘上。
• redo log是一个环(ring)结构，当redo空间快占满时，将会将部分dirty pages flush到disk上，然后释放部分redo log。

4、对比binlog

5、对比undo log

1）、Undo Log 是为了实现事务的原子性(rollback)，在MySQL数据库InnoDB存储引擎中，还用Undo Log来实现多版本并发控制(简称：MVCC)。

2）、Undo log是InnoDB MVCC事务特性的重要组成部分。当我们对记录做了变更操作时就会产生undo记录，Undo记录默认被记录到系统表空间(ibdata)中，但从5.6开始，也可以使用独立的Undo 表空间。

3）、Undo记录中存储的是老版本数据，当一个旧的事务需要读取数据时，为了能读取到老版本的数据，需要顺着undo链找到满足其可见性的记录。

InnoDB磁盘结构

• tablespace：表空间
• segment 段：
• extent 簇：物理上连续的几个页； 1MB一个簇 = 64 * 16KB = 128 * 8KB = 256 * 4KB，一个簇包含多少Page取决于Page的大小
• page 页：16KB

索引组织表

doublewrite buffer

• doublewrite buffer 是 InnoDB 的 system tablespace 中的一个区域。在 把 buffer pool 中的内容写入对应的 data file 之前，先要把数据写入 doublewirte buffer 中；

• 如果 storage 或者 mysqld 在写 page的过程中 进程崩溃，InnoDB 可以在 doublewrite buffer 中找到完成的 page 的拷贝 用来恢复；

• 尽管数据总是写两次，但 doublewrite buffer 不需要两倍的 I/O开销 或 两倍的 I/O 操作。数据作为一个大的连续块 写入 doublwrite buffer，只需对操作系统执行一次 fsync() 调用；

double write的缺点是什么?

​ 虽然mysql称double write是一个buffer, 但其实它是开在物理文件上的一个buffer, 其实也就是file, 所以它会导致系统有更多的fsync操作, 而我们知道硬盘的fsync性能是很慢的, 所以它会降低mysql的整体性能. 但是并不会降低到原来的50%. 这主要是因为: 1) double write是一个连接的存储空间, 所以硬盘在写数据的时候是顺序写, 而不是随机写, 这样性能更高. 另外将数据从double write buffer写到真正的segment中的时候, 系统会自动合并连接空间刷新的方式, 每次可以刷新多个pages;

redo log

• Redo Log是基于磁盘的数据结构，在崩溃恢复期间用于纠正不完整事务写入的数据。

• 默认情况下，Redo Log在磁盘上由两个名为ib_logfile0和的 文件物理表示ib_logfile1。MySQL以循环方式写入Redo Log文件。Redo Log中的数据按照受影响的记录进行编码；此数据统称为重做。

undo log

• 功能：事务回滚、MVCC

• undo log是与单个读写事务关联的 undo Log 记录的集合。undo Log 记录包含如何 撤消事务对 聚簇索引 记录的最新更改 的信息。如果另一个事务读取原始数据，就需要在 undo Log记录读取。

• undo log存在于 undo log segment。默认情况下，undo log segment 实际上是 system tablespace 的一部分 ，但它们也可以驻留在 undolog tablespace 中

•undo:相当于数据修改前的备份

•redo: 相当于数据修改后的备份,为了保证事务的持久化,redo会一直写

•Undo + Redo**事务的简化过程**
假设有A、B两个数据，值分别为1,2.
A.事务开始.
B.记录A=1到undo log.
C.修改A=3.
D.记录A=3到redo log.
E.记录B=2到undo log.
F.修改B=4.
G.记录B=4到redo log.
H.将redo log写入磁盘
I.事务提交完成

•- Undo + Redo**事务的特点**
A. 为了保证持久性，必须在事务提交前将Redo Log持久化 —一般每个事务提交时或每秒刷盘
B. 数据不需要在事务提交前写入磁盘，而是缓存在内存中。 —data在此时不需要写磁盘，但是如果redo文件过小也会触发事务未提交前数据落盘
C. Redo Log 保证事务的持久性
D. Undo Log 保证事务的原子性。
E. 有一个隐含的特点，数据必须要晚于redo log写入持久存储。

一个查询流程图

Azkaban是由Linkedin开源的一个批量工作流任务调度器。用于在一个工作流内以一个特定的顺序运行一组工作和流程。Azkaban定义了一种KV文件格式来建立任务之间的依赖关系，并提供一个易于使用的web用户界面维护和跟踪你的工作流。

1、简介

官网： https://azkaban.github.io/

下载： https://github.com/azkaban/azkaban/releases

1.1、架构

1.2、三个关键组件的作用

• Relational Database：存储元数据，如项目名称、项目描述、项目权限、任务状态、SLA规则等。
• AzkabanWebServer：项目管理、权限授权、任务调度、监控executor。
• AzkabanExecutorServer：作业流执行的Server。

1.3、三种部署模式

1)、solo-server模式

​ DB使用的是一个内嵌的H2，Web Server和Executor Server运行在同一个进程里。这种模式包含Azkaban的所有特性，但一般用来学习和测试。

2)、two-server模式

​ DB使用的是MySQL，MySQL支持master-slave架构，Web Server和Executor Server运行在不同的进程中。

3)、分布式multiple-executor模式

​ DB使用的是MySQL，MySQL支持master-slave架构，Web Server和Executor Server运行在不同机器上，且有多个Executor Server。

2、下载安装

2.1、编译环境

1
2

# 安装jdk 1.8
yum install -y git

2.2、下载源码编译

1
2

wget https://github.com/azkaban/azkaban/archive/3.38.0.tar.gz -O azkaban-3.38.0.tar.gz
tar -zxf azkaban-3.38.0.tar.gz

1
2
3

cd azkaban-3.38.0
./gradlew clean build -x test
# ./gradlew build -x test

2.3、列出编译产物

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

# solo-server模式安装包路径
[root@localhost azkaban-3.38.0]# ll azkaban-solo-server/build/distributions/
-rw-r--r--. 1 root root 24166624 Nov 21 15:27 azkaban-solo-server-0.1.0-SNAPSHOT.tar.gz
-rw-r--r--. 1 root root 24303950 Nov 21 15:27 azkaban-solo-server-0.1.0-SNAPSHOT.zip
# two-server模式和multiple-executor模式web-server安装包路径
[root@localhost azkaban-3.38.0]# ll azkaban-web-server/build/distributions/
-rw-r--r--. 1 root root 20120241 Nov 21 15:21 azkaban-web-server-0.1.0-SNAPSHOT.tar.gz
-rw-r--r--. 1 root root 20246140 Nov 21 15:21 azkaban-web-server-0.1.0-SNAPSHOT.zip
# two-server模式和multiple-executor模式exec-server安装包路径
[root@localhost azkaban-3.38.0]# ll azkaban-exec-server/build/distributions/
-rw-r--r--. 1 root root 16055070 Nov 21 15:27 azkaban-exec-server-0.1.0-SNAPSHOT.tar.gz
-rw-r--r--. 1 root root 16060378 Nov 21 15:27 azkaban-exec-server-0.1.0-SNAPSHOT.zip
# 建表sql
[root@localhost azkaban-3.38.0]# ll azkaban-db/build/sql/
-rw-r--r--. 1 root root 13887 Nov 21 15:13 create-all-sql-0.1.0-SNAPSHOT.sql

3、multiple-executor集群搭建

1、WebServer 负责管理Job，存储在mysql中

2、mysql存储Job

3、ExecutorServer从mysql中读取任务执行，ExecutorServer要部署在定时任务机器上；

Azkaban WebServer挂掉，不影响已经提交的任务执行，主要是不能通过WebUI查看Job、管理Job、跟踪Job状态。
因此，对于这个架构，主要是要解决MySQL HA和ExecutorServer HA。官方支持ExecutorServer HA，我们只需要配一个MySQL HA就行了。

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

mkdir -p /data/azkaban
tar -zxf azkaban-db/build/distributions/azkaban-db-0.1.0-SNAPSHOT.tar.gz -C /data/azkaban
tar -zxf azkaban-web-server/build/distributions/azkaban-web-server-0.1.0-SNAPSHOT.tar.gz -C /data/azkaban
tar -zxf azkaban-exec-server/build/distributions/azkaban-exec-server-0.1.0-SNAPSHOT.tar.gz -C /data/azkaban
tar -zxf azkaban-solo-server/build/distributions/azkaban-solo-server-0.1.0-SNAPSHOT.tar.gz -C /data/azkaban
# 结果
[root@localhost azkaban]# pwd
/data/azkaban
[root@localhost azkaban]# ll
total 4
drwxr-xr-x. 2 root root 4096 Nov 21 14:50 azkaban-db-0.1.0-SNAPSHOT
drwxr-xr-x. 6 root root   55 Nov 21 15:27 azkaban-exec-server-0.1.0-SNAPSHOT
drwxr-xr-x. 8 root root   77 Nov 21 15:27 azkaban-solo-server-0.1.0-SNAPSHOT
drwxr-xr-x. 6 root root   51 Nov 21 15:21 azkaban-web-server-0.1.0-SNAPSHOT

mv azkaban-web-server-0.1.0-SNAPSHOT/ webserver
mv azkaban-exec-server-0.1.0-SNAPSHOT exec-server
mv azkaban-solo-server-0.1.0-SNAPSHOT soloserver

[root@localhost azkaban]# ll
drwxr-xr-x.  2 root root 4096 Nov 21 14:50 azkaban-db-0.1.0-SNAPSHOT
drwxr-xr-x. 10 root root  202 Nov 22 10:20 exec-server
drwxr-xr-x.  8 root root   77 Nov 21 15:27 soloserver
drwxr-xr-x.  9 root root  196 Nov 22 10:07 webserver
[root@localhost azkaban]#

3.1、建立Azkaban数据库

1
2
3
4

mysqladmin create db_azkaban -h 172.18.1.51 -P 3306 -uroot -p123456
mysql -h 172.18.1.51 -P 3306 -uroot -p123456 db_azkaban < /data/azkaban/azkaban-db-0.1.0-SNAPSHOT/create-all-sql-0.1.0-SNAPSHOT.sql
# 报错：ERROR 1071 (42000) at line 64: Specified key was too long; max key length is 767 bytes
# 将数据库编码改为Latin1可解决

3.2、生成SSL

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

[root@localhost azkaban]# cd ~
[root@localhost ~]#  keytool -keystore keystore -alias jetty -genkey -keyalg RSA
Enter keystore password: 123456
Re-enter new password: 123456
What is your first and last name?
  [Unknown]: 回车
What is the name of your organizational unit?
  [Unknown]:  回车
What is the name of your organization?
  [Unknown]:  回车
What is the name of your City or Locality?
  [Unknown]:  回车
What is the name of your State or Province?
  [Unknown]:  回车
What is the two-letter country code for this unit?
  [Unknown]:  回车
Is CN=Unknown, OU=Unknown, O=Unknown, L=Unknown, ST=Unknown, C=Unknown correct?
  [no]:  yes
Enter key password for <jetty>
        (RETURN if same as keystore password):  123456
Re-enter new password: 123456
[root@localhost ~]#

3.3、设置 ExecutorServer

vi /data/azkaban/exec-server/conf/azkaban.properties

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
45
46
47
48
49
50
51

# Azkaban Personalization Settings
azkaban.name=AzkabanExecutor
azkaban.label=AzkabanExecutor
azkaban.color=#FF3601
azkaban.default.servlet.path=/index
web.resource.dir=web/
default.timezone.id=Asia/Shanghai
# Azkaban UserManager class
user.manager.class=azkaban.user.XmlUserManager
user.manager.xml.file=conf/azkaban-users.xml
# Loader for projects
executor.global.properties=conf/global.properties
azkaban.project.dir=projects
# Velocity dev mode
velocity.dev.mode=false
# Azkaban Jetty server properties.
jetty.use.ssl=false
jetty.maxThreads=25
jetty.port=8181
# Where the Azkaban web server is located
azkaban.webserver.url=http://localhost:8081
# mail settings
mail.sender=iceleader@126.com
mail.host=iceleader@126.com
# User facing web server configurations used to construct the user facing server URLs. They are useful when there is a reverse proxy between Azkaban web servers and users.
# enduser -> myazkabanhost:443 -> proxy -> localhost:8081
# when this parameters set then these parameters are used to generate email links.
# if these parameters are not set then jetty.hostname, and jetty.port(if ssl configured jetty.ssl.port) are used.
# azkaban.webserver.external_hostname=myazkabanhost.com
# azkaban.webserver.external_ssl_port=443
# azkaban.webserver.external_port=8081
job.failure.email=iceleader@126.com
job.success.email=iceleader@126.com
lockdown.create.projects=false
cache.directory=cache
# JMX stats
jetty.connector.stats=true
executor.connector.stats=true
# Azkaban plugin settings
azkaban.jobtype.plugin.dir=plugins/jobtypes
# Azkaban mysql settings by default. Users should configure their own username and password.
database.type=mysql
mysql.port=3306
mysql.host=172.18.1.51
mysql.database=db_azkaban
mysql.user=root
mysql.password=123456
mysql.numconnections=100
# Azkaban Executor settings
executor.maxThreads=50
executor.flow.threads=30

设置：

• default.timezone.id 时区配置
• user.manager.xml.file 登录用户配置
• azkaban.webserver.url 指向 webserver
• mysql.* mysql 相关配置
• mail.sender、mail.host、job.failure.email、job.success.email 邮件相关配置

启动：/data/azkaban/exec-server/bin/start-exec.sh

curl http://172.18.1.51:41096/executor?action=activate

1

curl http://${executorHost}:${executorPort}/executor?action=activate

3.4、设置 WebServer

1
2

cd /data/azkaban/webserver/conf/
vi /data/azkaban/webserver/conf/azkaban.properties

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

# 修改时区
default.timezone.id=Asia/Shanghai
# 邮箱配置
job.failure.email=iceleader@126.com
job.success.email=iceleader@126.com
# mysql配置
database.type=mysql
mysql.port=3306
mysql.host=172.18.1.51
mysql.database=db_azkaban
mysql.user=root
mysql.password=123456
mysql.numconnections=100
# SSL密码和文件路径

vi /data/azkaban/webserver/conf/azkaban-users.xml

1
2
3
4
5
6
7
8

<azkaban-users>
  <user groups="azkaban" password="azkaban" roles="admin" username="azkaban"/>
  <user password="metrics" roles="metrics" username="metrics"/>
  <user username="admin" password="admin" roles="admin" />

  <role name="admin" permissions="ADMIN"/>
  <role name="metrics" permissions="METRICS"/>
</azkaban-users>

mkdir -p /data/azkaban/webserver/plugins/jobtypes

vi /data/azkaban/webserver/plugins/jobtypes/commonprivate.properties

1
2

azkaban.native.lib=false
execute.as.user=false

启动服务器

sh /data/azkaban/webserver/bin/start-web.sh

sh /data/azkaban/webserver/bin/shutdown-web.sh

注意：没有 ExecutorServer 启动，WebServer就是退出

select * from db_azkaban.executors

update db_azkaban.executors set active = 1 where id = 1;

浏览器访问： http://172.18.1.51:8081/index

使用admin/admin登录

3.5、配置Job

1)、创建project

2)、定义任务并上传

每个任务格式如下

1
2
3

type=command
dependencies=dailysummary,advisor
command=echo dailysettlement

完成后打包为 dailysettlement.zip， 上传到 Project dailysettlement下

3)、定制执行计划

每小时30分执行一次

4)、查看执行计划

3.6、执行任务的问题

1、集群内存不足，去掉webserver中的内存限制

vi webserver/conf/azkaban.properties

1
2

# azkaban.executorselector.filters=StaticRemainingFlowSize,MinimumFreeMemory,CpuStatus
azkaban.executorselector.filters=StaticRemainingFlowSize,CpuStatus

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

ERROR [FlowTriggerScheduler] [Azkaban] Unable to get scheduled flow triggers
java.lang.NullPointerException
        at azkaban.flowtrigger.quartz.FlowTriggerScheduler.getScheduledFlowTriggerJobs(FlowTriggerScheduler.java:139)
        at azkaban.webapp.servlet.FlowTriggerServlet.ajaxFetchTrigger(FlowTriggerServlet.java:67)
        at azkaban.webapp.servlet.FlowTriggerServlet.handleAJAXAction(FlowTriggerServlet.java:107)
        at azkaban.webapp.servlet.FlowTriggerServlet.handleGet(FlowTriggerServlet.java:57)
        at azkaban.webapp.servlet.LoginAbstractAzkabanServlet.doGet(LoginAbstractAzkabanServlet.java:122)
        at javax.servlet.http.HttpServlet.service(HttpServlet.java:668)
        at javax.servlet.http.HttpServlet.service(HttpServlet.java:770)
        at org.mortbay.jetty.servlet.ServletHolder.handle(ServletHolder.java:511)
        at org.mortbay.jetty.servlet.ServletHandler.handle(ServletHandler.java:401)
        at org.mortbay.jetty.servlet.SessionHandler.handle(SessionHandler.java:182)
        at org.mortbay.jetty.handler.ContextHandler.handle(ContextHandler.java:766)
        at org.mortbay.jetty.handler.HandlerWrapper.handle(HandlerWrapper.java:152)
        at org.mortbay.jetty.Server.handle(Server.java:326)
        at org.mortbay.jetty.HttpConnection.handleRequest(HttpConnection.java:542)
        at org.mortbay.jetty.HttpConnection$RequestHandler.headerComplete(HttpConnection.java:928)
        at org.mortbay.jetty.HttpParser.parseNext(HttpParser.java:549)
        at org.mortbay.jetty.HttpParser.parseAvailable(HttpParser.java:212)
        at org.mortbay.jetty.HttpConnection.handle(HttpConnection.java:404)
        at org.mortbay.jetty.bio.SocketConnector$Connection.run(SocketConnector.java:228)
        at org.mortbay.thread.QueuedThreadPool$PoolThread.run(QueuedThreadPool.java:582)

2、ExcutorServer未激活，需要调用url手动去激活一下 executor，方式如下：

1

curl http://${executorHost}:${executorPort}/executor?action=activate

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

2019/11/22 14:25:23.831 +0800 ERROR [ExecutorServlet] [Azkaban] executor became inactive before setting up the flow 4
azkaban.executor.ExecutorManagerException: executor became inactive before setting up the flow 4
        at azkaban.execapp.FlowRunnerManager.createFlowRunner(FlowRunnerManager.java:403)
        at azkaban.execapp.FlowRunnerManager.submitFlow(FlowRunnerManager.java:347)
        at azkaban.execapp.ExecutorServlet.handleAjaxExecute(ExecutorServlet.java:288)
        at azkaban.execapp.ExecutorServlet.handleRequest(ExecutorServlet.java:136)
        at azkaban.execapp.ExecutorServlet.doPost(ExecutorServlet.java:93)
        at javax.servlet.http.HttpServlet.service(HttpServlet.java:727)
        at javax.servlet.http.HttpServlet.service(HttpServlet.java:820)
        at org.mortbay.jetty.servlet.ServletHolder.handle(ServletHolder.java:511)
        at org.mortbay.jetty.servlet.ServletHandler.handle(ServletHandler.java:401)
        at org.mortbay.jetty.servlet.SessionHandler.handle(SessionHandler.java:182)
        at org.mortbay.jetty.handler.ContextHandler.handle(ContextHandler.java:766)
        at org.mortbay.jetty.handler.HandlerWrapper.handle(HandlerWrapper.java:152)
        at org.mortbay.jetty.Server.handle(Server.java:326)
        at org.mortbay.jetty.HttpConnection.handleRequest(HttpConnection.java:542)
        at org.mortbay.jetty.HttpConnection$RequestHandler.content(HttpConnection.java:945)
        at org.mortbay.jetty.HttpParser.parseNext(HttpParser.java:756)
        at org.mortbay.jetty.HttpParser.parseAvailable(HttpParser.java:218)
        at org.mortbay.jetty.HttpConnection.handle(HttpConnection.java:404)
        at org.mortbay.jetty.bio.SocketConnector$Connection.run(SocketConnector.java:228)
        at org.mortbay.thread.QueuedThreadPool$PoolThread.run(QueuedThreadPool.java:582)

​ 首先明确的一点是，本文所述的是针对linux引入了虚拟内存管理机制以后所涉及的知识点。linux中页缓存的本质就是对于磁盘中的部分数据在内存中保留一定的副本，使得应用程序能够快速的读取到磁盘中相应的数据，并实现不同进程之间的数据共享。因此，linux中页缓存的引入主要是为了解决两类重要的问题：

1. 磁盘读写速度较慢（ms 级别);
2. 实现不同进程之间或者同一进程的前后不同部分之间对于数据的共享；

​ 如果没有进程之间的共享机制，那么对于系统中所启动的所有进程在打开文件的时候都要将需要的数据从磁盘加载进物理内存空间，这样不仅造成了加载速度变慢（每次都从磁盘中读取数据），而且造成了物理内存的浪费。为了解决以上问题，linux操作系统使用了缓存机制。在虚拟内存机制出现以前，操作系统使用块缓存机制，但是在虚拟内存出现以后操作系统管理IO的粒度更大，因此采用了页缓存机制。此后，和后备存储的数据交互普遍以页为单位。页缓存是基于页的、面向文件的一种缓存机制。

​ 说到这里，我们只是对于页缓存的重要性做了介绍。但是，还有三个问题（当然也是本文的重点）还没有解释，分别如下：

1. 页缓存究竟是如何实现，其和文件系统是如何关联的？
2. 页缓存、内存以及文件IO之间的关系是怎样的？
3. 页缓存中的数据如何实现和后备存储之间的同步？

接下来我们将对这三个问题进行详细的解释。

页缓存的实现

​ 既然页缓存是以页为单位进行数据管理的，那么必须在内核中标识该物理页。其实每个真正存放数据的物理页帧都对应一个管理结构体，称之为struct page，其结构体如下。

1
2
3
4
5
6
7
8
9
10

struct page  {
    unsigned long    flags;
    atomic_t    _count;
    atomic_t    _mapcount;
    unsigned long    private;
    struct address_space    *mapping;
    pgoff_t    index;
    struct list_head    lru;
    void*    virtual;
};

下面详细介绍一下物理页结构体中各个成员的含义：

• flags: 描述page当前的状态和其他信息，如当前的page是否是脏页PG_dirty；是否是最新的已经同步到后备存储的页PG_uptodate; 是否处于lru链表上等；
• _count：引用计数，标识内核中引用该page的次数，如果要操作该page，引用计数会+1，操作完成之后-1。当该值为0时，表示没有引用该page的位置，所以该page可以被解除映射，这在内存回收的时候是有用的；
• _mapcount: 页表被映射的次数，也就是说page同时被多少个进程所共享，初始值为-1，如果只被一个进程的页表映射了，该值为0。
• _mapping有三种含义：
  a. 如果mapping = 0，说明该page属于交换缓存（swap cache); 当需要地址空间时会指定交换分区的地址空间swapper_space;
  b. 如果mapping != 0, bit[0] = 0, 说明该page属于页缓存或者文件映射，mapping指向文件的地址空间address_space；
  c. 如果mapping != 0, bit[0] !=0 说明该page为匿名映射，mapping指向struct anon_vma对象；
• 注意区分_count和_mapcount，_mapcount表示的是被映射的次数，而_count表示的是被使用的次数；被映射了不一定被使用，但是被使用之前肯定要先被映射）。
• index: 在映射的虚拟空间（vma_area)内的偏移；一个文件可能只是映射了一部分，假设映射了1M的空间，那么index指的是1M空间内的偏移，而不是在整个文件内的偏移；
• private : 私有数据指针；
• lru:当page被用户态使用或者是当做页缓存使用的时候，将该page连入zone中的lru链表，供内存回收使用；

​ 页缓存就是将一个文件在内存中的所有物理页所组成的一种树形结构，我们称之为基数树，用于管理属于同一个文件在内存中的缓存内容。

​ 如上所述，一个文件在内存中对应的所有物理页组成了一棵基数树。而一个文件在内存中具有唯一的inode结构标识，inode结构中有该文件所属的设备及其标识符，因而，根据一个inode能够确定其对应的后备设备。为了将文件在物理内存中的页缓存和文件及其后备设备关联起来，linux内核引入了address_space结构体。可以说address_space结构体是将页缓存和文件系统关联起来的桥梁，其组成如下：

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

struct address_space {
    struct inode*    host;/*指向与该address_space相关联的inode节点*/
    struct radix_tree_root    page_tree;/*所有页形成的基数树根节点*/
    spinlock_t    tree_lock;/*保护page_tree的自旋锁*/
    unsigned int    i_map_writable;/*VM_SHARED的计数*/
    struct prio_tree_root    i_map;         
    struct list_head    i_map_nonlinear;
    spinlock_t    i_map_lock;/*保护i_map的自旋锁*/
    atomic_t    truncate_count;/*截断计数*/
    unsigned long    nrpages;/*页总数*/
    pgoff_t    writeback_index;/*回写的起始位置*/
    struct address_space_operation*    a_ops;/*操作表*/
    unsigned long    flags;/*gfp_mask掩码与错误标识*/
    struct backing_dev_info*    backing_dev_info;/*预读信息*/
    spinlock_t    private_lock;/*私有address_space锁*/
    struct list_head    private_list;/*私有address_space链表*/
    struct address_space*    assoc_mapping;/*相关的缓冲*/
}

下面对address_space成员中的变量做相关的解释：

• host: 指向与该address_space相关联的inode节点，inode节点与address_space之间是一一对应关系；
• struct radix_tree_root:指向的host文件在该内存中映射的所有物理页形成的基数树的根节点，参考博客。
• struct prio_tree_root:与该地址空间相关联的所有进程的虚拟地址区间vm_area_struct所对应的整个进程地址空间mm_struct形成的优先查找树的根节点;vm_area_struct中如果有后备存储，则存在prio_tree_node结构体，通过该prio_tree_node和prio_tree_root结构体，构成了所有与该address_space相关联的进程的一棵优先查找树，便于查找所有与该address_space相关联的进程；

下面列出struct prio_tree_root和struct prio_tree_node的结构体。

1
2
3
4
5
6
7
8
9
10
11

struct  prio_tree_root {
    struct prio_tree_node*  prio_tree_root;
    unsigned short              index_bits;
};
struct prio_tree_node {
    struct prio_tree_node*  left;
    struct prio_tree_node*  right; 
    struct prio_tree_node*  parent;
    unsigned long                start;
    unsigned long                last;
};

为了便于形成页缓存、文件和进程之间关系的清晰思路，文章画出一幅图，如图2所示

从以上可以解释可以看出，address_space成为构建页缓存和文件、页缓存和共享该文件的所有进程之间的桥梁。

​ 每个进程的地址空间使用mm_struct结构体标识，该结构体中包含一系列的由vm_area_struct结构体组成的连续地址空间链表。每个vm_area_struct中存在struct file* vm_file用于指向该连续地址空间中所打开的文件，而vm_file通过struct file中的struct path与struct dentry相关联。 struct dentry中通过inode指针指向inode，inode与address_space一一对应，至此形成了页缓存与文件系统之间的关联；为了便于查找与某个文件相关联的所有进程，address_space中的prio_tree_root指向了所有与该页缓存相关联的进程所形成的优先查找树的根节点。关于这种关系的详细思路请参考图1，这里画出其简化图，如图3：

​ 这里需要说明的linux中文件系统的一点是，内核为每个进程在其地址空间中都维护了结构体struct* fd_array[]用于维护该进程地址空间中打开的文件的指针；同时内核为所有被打开的文件还维护了系统级的一个文件描述符表用以记录该系统打开的所有文件，供所有进程之间共享；每个被打开的文件都由一个对应的inode结构体表示，由系统级的文件描述符表指向。所以，进程通过自己地址空间中的打开文件描述符表可以找到系统级的文件描述符表，进而找到文件。

页缓存、内存、文件IO之间的关系

​ 关于文件IO我们常说的两句话“普通文件IO需要复制两次，内存映射文件mmap只需要复制一次”。下面，我们对普通文件IO做详细的解释。文章对页缓存和文件IO做了详细的介绍，不过都是英文的，本文在基于对上文理解、翻译的基础上，加入自己对于页缓存的理解。读者可以选择直接去看对应的英文原版说明。

读

​ 为了能够深入理解页缓存和文件IO操作之间的关系，假设系统中现在存在一个名为render的进程，该进程打开了文件scene.dat，并且每次读取其中的512B(一个扇区的大小)，将读取的文件数据放入到堆分配的块中（每个进程自己的地址空间对应的物理内存）。先以普通IO为例介绍一下读取数据的过程，第一次读取的过程大致如图4（图4-8来源于该文章）。

进程发起读请求的过程如下：

1. 进程调用库函数read()向内核发起读文件的请求；
2. 内核通过检查进程的文件描述符定位到虚拟文件系统已经打开的文件列表项，调用该文件系统对VFS的read()调用提供的接口；
3. 通过文件表项链接到目录项模块，根据传入的文件路径在目录项中检索，找到该文件的inode；
4. inode中，通过文件内容偏移量计算出要读取的页；
5. 通过该inode的i_mapping指针找到对应的address_space页缓存树—基数树，查找对应的页缓存节点；
   （1）如果页缓存节点命中，那么直接返回文件内容；
   （2）如果页缓存缺失，那么产生一个缺页异常，首先创建一个新的空的物理页框，通过该inode找到文件中该页的磁盘地址，读取相应的页填充该页缓存（DMA的方式将数据读取到页缓存），更新页表项；重新进行第5步的查找页缓存的过程；
6. 文件内容读取成功；

​ 也就是说，所有的文件内容的读取（无论一开始是命中页缓存还是没有命中页缓存）最终都是直接来源于页缓存。当将数据从磁盘复制到页缓存之后，还要将页缓存的数据通过CPU复制到read调用提供的缓冲区中，这就是普通文件IO需要的两次复制数据复制过程。其中第一次是通过DMA的方式将数据从磁盘复制到页缓存中，本次过程只需要CPU在一开始的时候让出总线、结束之后处理DMA中断即可，中间不需要CPU的直接干预，CPU可以去做别的事情；第二次是将数据从页缓存复制到进程自己的的地址空间对应的物理内存中，这个过程中需要CPU的全程干预，浪费CPU的时间和额外的物理内存空间。

假如读取了12KB的数据之后，那么render进程的堆地址空间和相关的地址空间如图5所示（ 读取12KB数据之后，进程render的地址空间和页缓存示意图）：

​ 看起来该过程很简单，但是这其中存在着很多的知识点。首先，render使用了常规的read()系统调用读取了12KB的数据，现在scene.dat中三个大小为4KB的页也存在于页缓存中，就像先前所说的所有的文件IO都是通过页缓存进行的。在X86架构的linux体系中，内核以4KB大小的页为单位组织文件中的数据，所以即使你从一个文件中仅仅读取几个字节的数据，那么包含这些字节的整个页的数据都会从硬盘读入页缓存中。这对于提高硬盘的吞吐量很有帮助，并且用户通常每次读取的数据不仅仅是只有几个字节而已。页缓存记录了每个4KB中的页在文件中的位置，如图中的#0， #1等。

​ 然而，在一次文件读取的过程中，必须将文件的内容从页缓存拷贝到用户的空间。这个过程和缺页异常(通过DMA调入需要的页)不一样，这个拷贝过程需要通过CPU进行，因此浪费了CPU的时间。另一个弊端就是浪费了物理内存，因为需要为同样的数据在内存中维护两个副本，如图6 render进程的heap所对应的堆中的数据和页缓存中的数据存在重复，并且如果系统中有多个这样的进程的话，那么需要为每个进程维护同样的一份数据副本，严重浪费了CPU的时间和物理内存空间。

​ 好在，通过内存映射IO—mmap，进程不但可以直接操作文件对应的物理内存，减少从内核空间到用户空间的数据复制过程，同时可以和别的进程共享页缓存中的数据，达到节约内存的作用。关于mmap的实现请参考博客。

​ 当映射一个文件到内存中的时候，内核将虚拟地址直接映射到页缓存中。正如博客4中介绍的，当映射一个文件的时候，如果文件的内容不在物理内存中，操作系统不会将所映射的文件部分的全部内容直接拷贝到物理内存中，而是在使用虚拟地址访问物理内存的时候通过缺页异常将所需要的数据调入内存中。如果文件本身已经存在于页缓存中，则不再通过磁盘IO调入内存。如果采用共享映射的方式，那么数据在内存中的布局如图6所示（文件共享映射示意图）：

写

​ 由于页缓存的架构，当一个进程调用write系统调用的时候，对于文件的更新仅仅是被写到了文件的页缓存中，相应的页被标记为dirty。具体过程如下：

前面5步和读文件是一致的，在address_space中查询对应页的页缓存是否存在：

6. 如果页缓存命中，直接把文件内容修改写在页缓存的页中。写文件就结束了。这时候文件修改位于页缓存，并没有写回到磁盘文件中去。

7. 如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode找到该文件页的磁盘地址，读取相应的页填充页缓存。此时缓存页命中，进行第6步。

​ 普通的IO操作需要将写的数据从自己的进程地址空间复制到页缓存中，完成对页缓存的写入；但是mmap通过虚拟地址（指针）可以直接完成对页缓存的写入，减少了从用户空间到页缓存的复制。

​ 由于写操作只是写到了页缓存中，因此进程并没有被阻塞到磁盘IO发生，因此当计算机崩溃的时候，写操作所引起的改变可能并没有发生在磁盘上。所以，对于一些要求严格的写操作，比如数据库系统，就需要调用fsync等操作及时将数据同步到磁盘上（虽然这中间也可能存在磁盘的驱动程序崩溃的情况）。读操作与写不同，一般会阻塞到进程读取到数据（除非调用非阻塞IO，即使使用IO多路复用技术也是将进程阻塞在多个监听描述符上，本质上还是阻塞的）。为了减轻读操作的这种延迟，linux操作系统的内核使用了”预读”技术，也就是当从磁盘中读取你所需要的数据的时候，内核将会多读取一些页到页缓存中。

​ 普通文件IO中所有的文件内容的读取（无论一开始是命中页缓存还是没有命中页缓存）最终都是直接来源于页缓存。当将数据通过缺页中断从磁盘复制到页缓存之后，还要将页缓冲的数据通过CPU复制到read调用提供的缓冲区中。这样，必须通过两次数据拷贝过程，才能完成用户进程对文件内容的获取任务。写操作也是一样的，待写入的buffer在用户空间，必须将其先拷贝到内核空间对应的主存中，再写回到磁盘中，也是需要两次数据拷贝。mmap的使用减少了数据从用户空间到页缓存的复制过程，提高了IO的效率，尤其是对于大文件而言；对于比较小的文件而言，由于mmap执行了更多的内核操作，因此其效率可能比普通的文件IO更差。

​ 在专门介绍mmap的博客中，我们说文件映射分为私有映射(private)和共享映射（shared)两种，二者之间的区别就是一个进程对文件所做的改变能否被其他的进程所看到，且能否同步到后备的存储介质中。那么，如果一个进程仅仅是读取文件中的内容的话，那么共享映射和私有映射对应的物理内存布局如图5所示。但是，如果采用私有映射的方式，且一个进程对文件内容作出了改变，那么会发生怎样的情况呢？内核采用了写时复制技术完成私有映射下对文件内容的改动，下面举例说明。

​ 假设系统中存在两个进程分别为render和render3d，它们都私有映射同一个文件scene.dat到内存中，然后render进程对映射的文件做出了写操作，如图7所示（私有映射写文件示意图）：

​ 图6中的“只读”标志不是说映射的内容是只读的，这仅仅是内核为了节省物理内存而采用的对于物理内存的一种“欺骗手段”而已。如果两个进程只是读取文件中的内容，不做任何的改动，那么文件只在物理内存中保留一份；但是如果有一个进程，如render，要对文件中的内容做出改动，那么会触发缺页中断，内核采用写时复制技术，为要改动的内容对应的页重新分配一个物理页框，将并将被改动的内容对应的物理页框中的数据复制到新分配的物理页框中，再进行改动。此时新分配的物理页框对于render而言是它自己“私有的”，别的进程是看不到的，也不会被同步到后备的存储中。但是如果是共享映射，所有的进程都是共享同一块页缓存的，此时被映射的文件的数据在内存中只保留一份。任何一个进程对映射区进行读或者写，都不会导致对页缓冲数据的复制。

​ mmap的系统调用函数原型为void* mmap(void* addr, size_t len, int prot, int flag, int fd, off_t off)。其中，flag指定了是私有映射还是共享映射，私有映射的写会引发缺页中断，然后复制对应的物理页框到新分配的页框中。prot指定了被映射的文件是可读、可写、可执行还是不可访问。如果prot指定的是可读，但是却对映射文件执行写操作，则此时却缺页中断会引起段错误，而不是进行写时复制。

​ 那么此时存在另一个问题就是当最后一个render进程退出之后，存储scene.dat的页缓存是不是会被马上释放掉？当然不是！在一个进程中打开一个文件使用完之后该进程退出，然后在另一个进程中使用该文件这种情况通常是很常见的，页缓存的管理中必须考虑到这种情况。况且从页缓存中读取数据的时间是ns级别，但是从硬盘中读取数据的时间是ms级别，因此如果能够在使用数据的时候命中页缓存，那么对于系统的性能将非常有帮助。那么，问题来了，什么时候该文件对应的页缓存要被换出内存呢?就是系统中的内存紧张，必须要换出一部分物理页到硬盘中或者交换区中，以腾出更多的空间给即将要使用的数据的时候。所以只要系统中存在空闲的内存，那么页缓存就不会被换出，直到到达页缓存的上限为止。是否换出某一页缓存不是由某一个进程决定的，而是由操作系统在整个系统空间中的资源分配决定的。毕竟，从页缓存中读取数据要比从硬盘上读取数据要快的多了。

​ 内存映射的一个典型应用就是动态共享库的加载。图8（进程动态共享库的加载）展示了两个同一份程序的两个实例使用动态共享库时，进程的虚拟地址空间及对应的物理内存空间的布局。

页缓存中数据如何实现和后备存储之间的同步？

​ 普通文件IO，都是将数据直接写在页缓存上，那么页缓存中的数据何时写回后备存储？怎么写回？

何时写回

1. 空闲内存的值低于一个指定的阈值的时候，内核必须将脏页写回到后备存储以释放内存。因为只有干净的内存页才可以回收。当脏页被写回之后就变为PG_uptodate标志，变为干净的页，内核就可以将其所占的内存回收；

2. 当脏页在内存中驻留的时间超过一个指定的阈值之后，内核必须将该脏页写回到后备存储，以确定脏页不会在内存中无限期的停留；

3. 当用户进程显式的调用fsync、fdatasync或者sync的时候，内核按照要求执行回写操作。

由谁写回

• 为了能够不阻塞写操作，并且将脏页及时的写回后备存储。linux在当前的内核版本中使用了flusher线程负责将脏页回写。
• 为了满足第一个何时回写的条件，内核在可用内存低于一个阈值的时候唤醒一个或者多个flusher线程，将脏页回写；
• 为了满足第二个条件，内核将通过定时器定时唤醒flusher线程，将所有驻留时间超时的脏页回写。

原文链接：https://blog.csdn.net/GDJ0001/article/details/80136364

页面置换算法

操作系统将内存按照页的进行管理，在需要的时候才把进程相应的部分调入内存。当产生缺页中断时，需要选择一个页面写入。如果要换出的页面在内存中被修改过，变成了“脏”页面，那就需要先写会到磁盘。页面置换算法，就是要选出最合适的一个页面，使得置换的效率最高。页面置换算法有很多，简单介绍几个，重点介绍比较重要的LRU及其实现算法。

一、最优页面置换算法

最理想的状态下，我们给页面做个标记，挑选一个最远才会被再次用到的页面。当然，这样的算法不可能实现，因为不确定一个页面在何时会被用到。

二、最近未使用页面置换算法（NRU）

系统为每一个页面设置两个标志位：当页面被访问时设置R位，当页面（修改）被写入时设置M位。当发生缺页中断时，OS检查所有的页面，并根据它们当前的R和M位的值，分为四类：

（1）！R&！M（2）！R&M（3）R&！M（4）R&M

编号越小的类，越被优先换出。即在最近的一个时钟滴答内，淘汰一个没有被访问但是已经被修改的页面，比淘汰一个被频繁使用但是“clean”的页面要好。

三、先进先出页面置换算法（FIFO）及其改进

这种算法的思想和队列是一样的，OS维护一个当前在内存中的所有页面的链表，最新进入的页面在尾部，最久的在头部，每当发生缺页中断，就替换掉表头的页面并且把新调入的页面加入到链表末尾。

这个算法的问题，显然是太过于“公正了”，没有考虑到实际的页面使用频率。

一种合理的改进，称为第二次机会算法。即给每个页面增加一个R位，每次先从链表头开始查找，如果R置位，清除R位并且把该页面节点放到链表结尾；如果R是0，那么就是又老又没用到，替换掉。

四、时钟页面置换算法（clock）

这种算法只是模型像时钟，其实就是一个环形链表的第二次机会算法，表针指向最老的页面。缺页中断时，执行相同的操作，包括检查R位等。

五、最近最少使用页面置换算法（LRU）

缺页中断发生时，置换未使用时间最长的页面，称为LRU（least recently used）。

LRU是可以实现的，需要维护一个包含所有页面的链表，并且根据实时使用情况更新这个链表，代价是比较大的。

于是，需要对这个算法进行一些改进，也可以说是简化。将每一个页面与一个计数器关联，每次时钟终端，扫描所有页面，将每个页面的R位加到计数器上，这样就大致跟踪了每个页面的使用情况。这种方法称为NFU（not frequently used，最不常用）算法。

这样还是存在一个问题，即很久之前的一次使用，与最近的使用权重相等。

所以，再次改进，将计数器在每次时钟滴答时，右移一位，并把R位加在最高位上。这种算法，称为老化（aging）算法，增加了最近使用的比重。

老化算法只能采用有限的位数，所以可能在一定程度上精度会有所损失。

六、工作集算法

简单来说，工作集就是在最近k次内存访问所使用过的页面的集合。原始的工作集算法同样代价很大，对它进行简化：在过去Nms的北村访问中所用到的页面的集合。

所以，在实现的时候，可以给每个页面一个计时器。需要置换页面时，同实际时间进行对比，R为1，更新到现在时间；R为0，在规定阈值之外的页面可以被置换。

同样，这个算法也可以用时钟的思想进行改进。

七、Linux使用的页面置换算法

Linux区分四种不同的页面：不可回收的、可交换的、可同步的、可丢弃的。

不可回收的：保留的和锁定在内存中的页面，以及内核态栈等。

可交换的：必须在回收之前写回到交换区或者分页磁盘分区。

可同步的：若为脏页面，必须要先写回。

可丢弃的：可以被立即回收的页面。

Linux并没有像我们之前单纯讨论算法时那样，在缺页中断产生的时候才进行页面回收。Linux有一个守护进程kswapd，比较每个内存区域的高低水位来检测是否有足够的空闲页面来使用。每次运行时，仅有一个确定数量的页面被回收。这个阈值是受限的，以控制I/O压力。

每次执行回收，先回收容易的，再处理难的。回收的页面会加入到空闲链表中。

算法是一种改进地LRU算法，维护两组标记：活动/非活动和是否被引用。第一轮扫描清除引用位，如果第二轮运行确定被引用，就提升到一个不太可能回收的状态，否则将该页面移动到一个更可能被回收的状态。

处于非活动列表的页面，自从上次检查未被引用过，因而是移除的最佳选择。被引用但不活跃的页面同样会被考虑回收，是因为一些页面是守护进程访问的，可能很长时间不再使用。

另外，内存管理还有一个守护进程pdflush，会定期醒来，写回脏页面；或者可用内存下降到一定水平后被内核唤醒。

B树

​ B-tree树即B树，B即Balanced，平衡的意思。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生[误解]。如人们可能会以为B-树是一种树，而B树又是另一种树。而事实上是，B-tree就是指的B树。特此说明。

二叉搜索树

1.所有非叶子结点至多拥有两个儿子（Left和Right）；

2.所有结点存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

如：

二叉搜索树

从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；

否则，如果查询关键字比结点关键字小，就进入左儿子；

如果比结点关键字大，就进入右儿子;

如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

​ 如果二叉搜索树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树

的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变二叉搜索树结构

（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

但二叉搜索树在经过多次插入与删除后，有可能导致不同的结构：

右边也是一个二叉搜索树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的

树结构索引；所以，使用二叉搜索树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就

是所谓的“平衡”问题；

平衡二叉树

​ 实际使用的二叉搜索树都是在原二叉搜索树的基础上加上平衡算法，即“平衡二叉树”；如何保持B树

结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在二叉搜索树中插入和删除结点的

策略；

红黑树

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

1. 每个节点要么是黑色，要么是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。
4. 每个红色结点的两个子结点一定都是黑色。
5. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

从性质5又可以推出：

性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点
图1就是一颗简单的红黑树。其中Nil为叶子结点，并且它是黑色的。(值得提醒注意的是，在Java中，叶子结点是为null的结点。)

红黑树并不是一个完美平衡二叉查找树，从图1可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。

介绍到此，为了后面讲解不至于混淆，我们还需要来约定下红黑树一些结点的叫法，如图2所示

B树（B-树）

B树（B-树）是一种多路搜索树（并不是二叉的）：

1. 定义任意非叶子结点最多只有M个儿子；且M>2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8. 所有叶子结点位于同一层；

如：（M=3）

B-树的搜索

​ 从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果
命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为
空，或已经是叶子结点；

B-树的特性

1. 关键字集合分布在整颗树中；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束；
4. 其搜索性能等价于在关键字全集内做一次二分查找；
5. 自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为：

​ 其中，M为设定的非叶子结点最多子树个数，N为关键字总数；所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；

​ 由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；

B+树

B+树是B-树的变体，也是一种多路搜索树：

1. 其定义基本与B-树同，除了：

2. 非叶子结点的子树指针与关键字个数相同；

3. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

4. 为所有叶子结点增加一个链指针；

5. 所有关键字都在叶子结点出现；

如：（M=3）

B+与B-树区别

B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性

1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2. 不可能在非叶子结点命中；

3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4. 更适合文件索引系统；

B*树

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂

当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂

当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

小结

二叉搜索树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；

B（B-）树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

1、缓存 IO

​ 缓存 I/O 又称 标准 I/O，大都数文件系统的默认 I/O 操作 都是操作缓存 I/O。在Linux的缓存 I/O 机制中，数据先从磁盘复制到内核空间的缓冲区，然后从内核空间缓冲区复制到 应用程序的地址空间。

​ 读操作：操作系统检查内核的缓存区 有没有需要的数据，如果已经缓存了，那么就直接从缓存中返回；否则从磁盘中读取，然后缓存在操作系统的缓冲中。

​ 写操作：将数据从用户空间复制到内核空间的缓冲区中。这时对用户程序来说写操作已经完成，至于什么时候再写到磁盘中由操作系统决定，除非显式调用了sync同步命令（详情操作《【珍藏】linux 同步IO: sync、fsync与fdatasync》）

​ 缓存I/O的优点：① 在一定程度上分离了内核空间和用户空间，保护系统本身的运行安全；② 可以减少读盘的次数，从而提高性能；

​ 缓冲I/O的缺点：在缓存 I/O 机制中，DMA方式可以将数据直接从磁盘读到页缓存中，或者将数据从页缓存直接写回到磁盘上，而不能直接在应用程序地址空间和磁盘之间进行数据传输，这样，数据在传输过程中需要在应用程序的地址空间（用户空间）和缓存（内核空间）之间进行多次数据拷贝操作，这些数据拷贝操作所带来的CPU以及内存开销是非常大的。

2、直接IO

​ 直接 I/O 就是应用程序直接访问磁盘数据，而不经过内核缓冲区，这样做的目的是减少一次内核缓冲区到用户程序缓存的数据复制。比如说 数据库管理系统这类应用，他们更倾向于选择他们自己的缓存机制，因为数据库管理系统往往比操作系统更了解数据库中存在的数据，数据库管理系统可以提供一种更加有效的缓存机制来提高数据库中数据的存取性能。

​ 直接IO的缺点：如果访问的数据不在应用程序缓存中，那么每次数据都会直接从磁盘加载，这种加载会非常缓慢。通常 直接IO与异步IO结合使用，会得到比较好的性能。

​ 异步IO：当访问数据的线程发出请求后，线程接着去处理其他事，而不是阻塞等待；

​ 下图分析了写场景下的 DirectIO 和 BufferIO：

首先，磁盘IO主要的延时是由（以15000rpm硬盘为例）： 机械转动延时（机械磁盘的主要性能瓶颈，平均为2ms） + 寻址延时（2~3ms） + 块传输延时（一般4k每块，40m/s的传输速度，延时一般为0.1ms) 决定。（平均为5ms）

而网络IO主要延时由： 服务器响应延时 + 带宽限制 + 网络延时 + 跳转路由延时 + 本地接收延时 决定。（一般为几十到几千毫秒，受环境干扰极大）

所以两者一般来说网络IO延时要大于磁盘IO的延时。

PIO与DMA

有必要简单的说说慢速I/O设备和内存之间的数据传输方式。

PIO

我们拿磁盘来说，很早以前，磁盘和内存之间的数据传输是需要CPU控制的，也就是说如果我们读取磁盘文件到内存中，数据要经过CPU存储转发，这种方式称为PIO。显然这种方式非常不合理，需要占用大量的CPU时间来读取文件，造成文件访问时系统几乎停止响应。

DMA

后来，DMA（直接内存访问，Direct Memory Access）取代了PIO，它可以不经过CPU而直接进行磁盘和内存的数据交换。在DMA模式下，CPU只需要向DMA控制器下达指令，让DMA控制器来处理数据的传送即可，DMA控制器通过系统总线来传输数据，传送完毕再通知CPU，这样就在很大程度上降低了CPU占有率，大大节省了系统资源，而它的传输速度与PIO的差异其实并不十分明显，因为这主要取决于慢速设备的速度。

可以肯定的是，PIO模式的计算机我们现在已经很少见到了。

标准文件访问方式

具体步骤：

当应用程序调用read接口时，操作系统检查在内核的高速缓存有没有需要的数据，如果已经缓存了，那么就直接从缓存中返回，如果没有，则从磁盘中读取，然后缓存在操作系统的缓存中。

应用程序调用write接口时，将数据从用户地址空间复制到内核地址空间的缓存中，这时对用户程序来说，写操作已经完成，至于什么时候再写到磁盘中，由操作系统决定，除非显示调用了sync同步命令。

内存映射

减少数据在用户空间和内核空间之间的拷贝操作,适合大量数据传输

Linux内核提供一种访问磁盘文件的特殊方式，它可以将内存中某块地址空间和我们要指定的磁盘文件相关联，从而把我们对这块内存的访问转换为对磁盘文件的访问，这种技术称为内存映射（Memory Mapping）。

操作系统将内存中的某一块区域与磁盘中的文件关联起来，当要访问内存中的一段数据时，转换为访问文件的某一段数据。这种方式的目的同样是减少数据从内核空间缓存到用户空间缓存的数据复制操作，因为这两个空间的数据是共享的。

内存映射是指将硬盘上文件的位置与进程逻辑地址空间中一块大小相同的区域一一对应，当要访问内存中一段数据时，转换为访问文件的某一段数据。这种方式的目的同样是减少数据在用户空间和内核空间之间的拷贝操作。当大量数据需要传输的时候，采用内存映射方式去访问文件会获得比较好的效率。

使用内存映射文件处理存储于磁盘上的文件时，将不必再对文件执行I/O操作，这意味着在对文件进行处理时将不必再为文件申请并分配缓存，所有的文件缓存操作均由系统直接管理，由于取消了将文件数据加载到内存、数据从内存到文件的回写以及释放内存块等步骤，使得内存映射文件在处理大数据量的文件时能起到相当重要的作用。

在大多数情况下，使用内存映射可以提高磁盘I/O的性能，它无须使用read()或write()等系统调用来访问文件，而是通过mmap()系统调用来建立内存和磁盘文件的关联，然后像访问内存一样自由地访问文件。
有两种类型的内存映射，共享型和私有型，前者可以将任何对内存的写操作都同步到磁盘文件，而且所有映射同一个文件的进程都共享任意一个进程对映射内存的修改；后者映射的文件只能是只读文件，所以不可以将对内存的写同步到文件，而且多个进程不共享修改。显然，共享型内存映射的效率偏低，因为如果一个文件被很多进程映射，那么每次的修改同步将花费一定的开销。

直接I/O

绕过内核缓冲区,自己管理I/O缓存区

在Linux 2.6中，内存映射和直接访问文件没有本质上差异，因为数据从进程用户态内存空间到磁盘都要经过两次复制，即在磁盘与内核缓冲区之间以及在内核缓冲区与用户态内存空间。
引入内核缓冲区的目的在于提高磁盘文件的访问性能，因为当进程需要读取磁盘文件时，如果文件内容已经在内核缓冲区中，那么就不需要再次访问磁盘；而当进程需要向文件中写入数据时，实际上只是写到了内核缓冲区便告诉进程已经写成功，而真正写入磁盘是通过一定的策略进行延迟的。

然而，对于一些较复杂的应用，比如数据库服务器，它们为了充分提高性能，希望绕过内核缓冲区，由自己在用户态空间实现并管理I/O缓冲区，包括缓存机制和写延迟机制等，以支持独特的查询机制，比如数据库可以根据更加合理的策略来提高查询缓存命中率。另一方面，绕过内核缓冲区也可以减少系统内存的开销，因为内核缓冲区本身就在使用系统内存。

应用程序直接访问磁盘数据，不经过操作系统内核数据缓冲区，这样做的目的是减少一次从内核缓冲区到用户程序缓存的数据复制。这种方式通常是在对数据的缓存管理由应用程序实现的数据库管理系统中。
直接I/O的缺点就是如果访问的数据不在应用程序缓存中，那么每次数据都会直接从磁盘进行加载，这种直接加载会非常缓慢。通常直接I/O跟异步I/O结合使用会得到较好的性能。

Linux提供了对这种需求的支持，即在open()系统调用中增加参数选项O_DIRECT，用它打开的文件便可以绕过内核缓冲区的直接访问，这样便有效避免了CPU和内存的多余时间开销。

顺便提一下，与O_DIRECT类似的一个选项是O_SYNC，后者只对写数据有效，它将写入内核缓冲区的数据立即写入磁盘，将机器故障时数据的丢失减少到最小，但是它仍然要经过内核缓冲区。

sendfile/零拷贝

网络I/O，kafka用到此特性

普通的网络传输步骤如下

1、操作系统将数据从磁盘复制到操作系统内核的页缓存中；
2、应用将数据从内核缓存复制到应用的缓存中；
3、应用将数据写回内核的Socket缓存中；
4、操作系统将数据从Socket缓存区复制到网卡缓存，然后将其通过网络发出；

解析：

1、当调用read系统调用时，通过DMA（Direct Memory Access）将数据copy到内核模式；
2、然后由CPU控制将内核模式数据copy到用户模式下的 buffer中；
3、read调用完成后，write调用首先将用户模式下 buffer中的数据copy到内核模式下的socket buffer中；
4、最后通过DMA copy将内核模式下的socket buffer中的数据copy到网卡设备中传送；

从上面的过程可以看出，数据白白从内核模式到用户模式走了一圈，浪费了两次copy，而这两次copy都是CPU copy，即占用CPU资源；

sendfile

通过sendfile传送文件只需要一次系统调用，当调用sendfile时：

1、首先通过 DMA copy 将数据从磁盘读取到 kernel buffer 中；

2、然后通过 CPU copy 将数据从 kernel buffer 复制到 socket buffer 中；

3、最终通过 DMA copy 将 socket buffer 中的数据复制到 网卡buffer 中；

sendfile与read/write方式相比，少了 一次模式切换一次CPU copy。但是从上述过程中也可以发现从kernel buffer中将数据copy到socket buffer是没必要的。

为此，Linux2.4内核对sendfile做了改进，下图所示：

改进后的处理过程如下：

1、DMA copy 将 磁盘数据 复制到 kernel buffer 中；

2、向 socket buffer 中追加当前要发送的数据在 kernel buffer 中的位置和偏移量；

3、DMA gather copy 根据 socket buffer 中的位置和偏移量直接将 kernel buffer 中的数据copy到网卡上；

经过上述过程，数据只经过了2次copy就从磁盘传送出去了。（事实上这个Zero copy是针对内核来讲的，数据在内核模式下是Zero－copy的）。

当前许多高性能http server都引入了sendfile机制，如nginx，lighttpd等。

1
2

// Java中的零拷贝
FileChannel.transferTo(long position,long count, WriteableByteChannel target);

Java NIO中FileChannel.transferTo(long position, long count, WriteableByteChannel target)方法将当前通道中的数据传送到目标通道target中，在支持Zero-Copy的linux系统中，transferTo()的实现依赖于 sendfile()调用;

整个数据通路涉及4次数据复制和2个系统调用，如果使用sendfile则可以避免多次数据复制，操作系统可以直接将数据从内核页缓存中复制到网卡缓存，这样可以大大加快整个过程的速度;

大多数时候，我们都在向Web服务器请求静态文件，比如图片、样式表等，根据前面的介绍，我们知道在处理这些请求的过程中，磁盘文件的数据先要经过内核缓冲区，然后到达用户内存空间，因为是不需要任何处理的静态数据，所以它们又被送到网卡对应的内核缓冲区，接着再被送入网卡进行发送。

数据从内核出去，绕了一圈，又回到内核，没有任何变化，看起来真是浪费时间。在Linux 2.4的内核中，尝试性地引入了一个称为khttpd的内核级Web服务器程序，它只处理静态文件的请求。引入它的目的便在于内核希望请求的处理尽量在内核完成，减少内核态的切换以及用户态数据复制的开销。

同时，Linux通过系统调用将这种机制提供给了开发者，那就是sendfile()系统调用。它可以将磁盘文件的特定部分直接传送到代表客户端的socket描述符，加快了静态文件的请求速度，同时也减少了CPU和内存的开销。

在OpenBSD和NetBSD中没有提供对sendfile的支持。通过strace的跟踪看到了Apache在处理151字节的小文件时，使用了mmap()系统调用来实现内存映射，但是在Apache处理较大文件的时候，内存映射会导致较大的内存开销，得不偿失，所以Apache使用了sendfile64()来传送文件，sendfile64()是sendfile()的扩展实现，它在Linux 2.4之后的版本中提供。

这并不意味着sendfile在任何场景下都能发挥显著的作用。对于请求较小的静态文件，sendfile发挥的作用便显得不那么重要，通过压力测试，我们模拟100个并发用户请求151字节的静态文件，是否使用sendfile的吞吐率几乎是相同的，可见在处理小文件请求时，发送数据的环节在整个过程中所占时间的比例相比于大文件请求时要小很多，所以对于这部分的优化效果自然不十分明显。

一、概览

Java的 I/O 大概可以分成以下几类：

• 磁盘操作：File
• 字节操作：InputStream 和 OutputStream
• 字符操作：Reader 和 Writer
• 对象操作：Serializable
• 网络操作：Socket
• 非阻塞输入/输出：NIO

二、磁盘操作

File 类可以用于表示文件和目录的信息，但是它不表示文件的内容。

递归的列出一个目录下所有文件：

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

public static void listAllFiles(File dir) {
    if (dir == null || !dir.exists()) {
        return;
    }
    if (dir.isFile()) {
        System.out.println(dir.getName());
        return;
    }
    for (File file : dir.listFiles()) {
        listAllFiles(file);
    }
}

从 Java7 开始，可以用 Paths 和 Files 代替 File。

三、字节操作

实现文件复制

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

public static void copyFile(String src, String dist) throws IOException {
    FileInputStream in = new FileInputStream(src);
    FileOutputStream out = new FileOutputStream(dist);

    byte[] buffer = new byte[20 * 1024];
    int cnt;

    // read() 最多读取 buffer.length 个字节
    // 返回的是实际读取的个数
    // 返回 -1 的时候表示读到 eof，即文件尾
    while ((cnt = in.read(buffer, 0, buffer.length)) != -1) {
        out.write(buffer, 0, cnt);
    }

    in.close();
    out.close();
}

装饰者模式

Java I/O 使用了装饰者模式来实现。以 InputStream 为例，

• InputStream 是抽象组件；
• FileInputStream 是 InputStream 的子类，属于具体组件，提供了字节流的输入操作；
• FilterInputStream 属于抽象装饰者，装饰者用于装饰组件，为组件提供额外的功能。例如 BufferedInputStream 为 FileInputStream 提供缓存的功能。

实例化一个具有哦缓存功能的字节流对象是，只需要在FileInputStream对象上再套一层 BufferedInputStream 对象即可。

1
2

FileInputStream fileInputStream = new FileInputStream(filePath);
BufferedInputStream bufferedInputStream = new BufferedInputStream(fileInputStream)

DataInputStream 装饰者提供了对更多数据类型进行输入的操作，比如 int、double 等基本类型。

四、字符操作

编码与解码

编码就是吧字符转换为字节，而解码是把字节重新组合成字符；

如果编码和解码过程使用不同的编码方式，那么就出现了乱码；

• GBK 编码中，中文字符占 2 个字节，英文字符占 1 个字节；
• UTF-8 编码中，中文字符占 3 个字节，英文字符占 1 个字节；
• UTF-16be 编码中，中文字符和英文字符各占 2 个字节；

UTF-16be 中的 be 指的是 Big Endian，也就是大端。相应的也有 UTF-16le，le 指的是 Little Endian，也就是小端；

Java 的内存编码使用 双字节编码 UTF-16be，这不是指 Java 只支持这一种编码方式，而是说 char 这种类型使用 UTF-16be 进行编码。char 类型占16 位，也就是两个字节，Java 使用这种双字节编码是为了让一个中文或者一个英文 都能使用 一个 char 来存储；

String 的编码方式

String 可以看成是一个字符序列，可以指定一个编码方式，将它编码为字节序列，也可以指定一个编码方式 将一个字节序列 解码为 String。

1
2
3
4

String str1 = "中文";
byte[] bytes = str1.getBytes("UTF-8");
String str2 = new String(bytes, "UTF-8");
System.out.println(str2);

在调用无参数 getBytes() 方法时，默认的编码方式不是 UTF-16be。双字节编码的好处是 可以使用一个 char 存储中文和英文，而将 String转化为 bytes[] 字节数组 就不再需要这个好处，因此也就不再需要双字节编码。getBytes() 的默认编码方式与平台有关，一般为 UTF-8。

1

byte[] bytes = str1.getBytes();

Reader 和 Writer

不管是磁盘还是网络传输，最小的存储单元都是字节，而不是字符。但是在程序中操作的通常是字符解释的数据，英雌需要提供对字符进行操作的方法。

• InputStreamReader 实现从 字节流 解码成 字符流；
• OutputStreamWriter 实现从 字符流 编码成 字节流；

实现逐行输出文本文件的内容

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

public static void readFileContent(String filePath) throws IOException {
    FileReader fileReader = new FileReader(filePath);
    BufferedReader bufferedReader = new BufferedReader(fileReader);

    String line;
    while ((line = bufferedReader.readLine()) != null) {
        System.out.println(line);
    }

    // 装饰者模式使得 BufferedReader 组合了一个 Reader 对象
    // 在调用 BufferedReader 的 close() 方法时会去调用 Reader 的 close() 方法
    // 因此只要一个 close() 调用即可
    bufferedReader.close();
}

五、对象操作

序列化

序列化就是一个将对象转换成字节序列，方便存储和传输

• 序列化：ObjectOutputStream.writeObject()
• 反序列化：ObjectInputStream.readObject()

不会对静态变量进行序列化，因为序列化只是保存对象的状态，静态变量属于类的状态。

Serializable

序列化的类需要实现 Serializable 接口，它只是一个标准，没有任何方法需要实现，但是如果不如实现它的话而进行序列化，会抛出异常。

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

public static void main(String[] args) throws IOException, ClassNotFoundException {

    A a1 = new A(123, "abc");
    String objectFile = "file/a1";

    ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream(objectFile));
    objectOutputStream.writeObject(a1);
    objectOutputStream.close();

    ObjectInputStream objectInputStream = new ObjectInputStream(new FileInputStream(objectFile));
    A a2 = (A) objectInputStream.readObject();
    objectInputStream.close();
    System.out.println(a2);
}

private static class A implements Serializable {
    private int x;
    private String y;

    A(int x, String y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "x = " + x + "  " + "y = " + y;
    }
}

transient

transient 关键字 可以使一些属性不会被序列化。

ArrayList中存储数组的 elementData 是用 transient 修饰的，因为这个数组是动态扩展的，并不是所有的空间都被使用，因此就不需要所有的内容都被序列化。通过重写 序列化 和 反序列化方法，使得可以只序列化数组中有内容的那部分数据。

1

private transient Object[] elementData;

六、网络操作

Java中的网络支持：

• InetAddress： 用于表示网络上的硬件资源，即 IP 地址；
• URL：统一资源定位符；
• Sockets：使用 TCP 协议实现网络通信；
• Datagram：使用 UDP 协议实现网络通信；

InetAddress

没有共有的构造函数，只能通过静态方法来创建实例

1
2

InetAddress.getByName(String host);
InetAddress.getByAddress(byte[] address);

URL

可以直接从 URL 中读取字节流数据

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

public static void main(String[] args) throws IOException {
    URL url = new URL("http://www.baidu.com");
    /* 字节流 */
    InputStream is = url.openStream();
    /* 字符流 */
    InputStreamReader isr = new InputStreamReader(is, "utf-8");
    /* 提供缓存功能 */
    BufferedReader br = new BufferedReader(isr);
    String line;
    while ((line = br.readLine()) != null) {
        System.out.println(line);
    }
    br.close();
}

Sockets

• ServerSocket：服务器端类；
• Socket：客户端类；
• 服务器 和 客户端 通过 InputStream 和 OutputStream 进行输入输出；

Datagram

• DatagramSocket：通信类；
• DatagramPacket：数据包类；

七、NIO

新的输入/输出（NIO）库是在JDK 1.4 中引入的，弥补了原来的 I/O 的不足，提供了高速的，面向块的 I/O。

流与块

I/O 与 NIO 最重要的区别是：数据打包和传输的方式，I/O以流的方式处理数据，而 NIO 以块的方式处理数据。

面向流的 I/O 一次处理一个字节数据：一个输入流产生一个字节数据，一个输出流消费一个字节数据。为流式数据创建过滤器非常容易，链接几个过滤器，以便每个过滤器只负责复杂机制的一部分。不利的一面是，面向流的 I/O 通常相当慢。

面向块的 I/O 一次处理一个数据块，按块处理数据 比 按流处理数据要快的多。但面向块的 I/O 缺少一些面向流的 I/O 所具有的 优雅性 和 简单性。

I/O 包 和 NIO 已经很好的集成了，java.io.* 已经以 NIO 为基础重新实现了，所以现在它可以利用 NIO 的一些特性。例如，java.io.* 包中的一些类包含以块的形式读写数据的方法，这使得即使在面向流的系统汇总，处理速度也会更快。

通道与缓冲区

1、通道

通道 Channel 是 对原 I/O 包中流的模拟，可以通过它读取和写入数据。

通道与流的不同之处在于，流只能在一个方向上移动（一个流必须是InputStream 或者 OutputStream 的子类），而通道是双向的，可以用于读、写或者同时用于读写。

通道包括以下类型：

• FileChannel：从文件读写数据；
• DatagramChannel：通过 UDP 读写网络中数据；
• SocketChannel：通过 TCP 读写网络中数据；
• ServerSocketChannel：可以监听新进来的 TCP 连接，对每一个新进来的连接都会创建一个SocketChannel；

2、缓冲区

发送给一个通道的所有数据都必须首先放到缓冲区中，同样的，从通道中读取的任何数据都要先读到缓冲区中。也就是说，不会直接对通道进行读写数据，而是先经过缓冲区。

缓冲区实质上是一个数组，但它不仅仅是一个数组。缓冲区提供了对数据的结构化访问，而且还可以跟踪系统的读/写进程。

缓冲区包括以下类型：

• ByteBuffer
• CharBuffer
• ShortBuffer
• IntBuffer
• LongBuffer
• FloatBuffer
• DoubleBuffer

缓冲区状态变量

• capacity：最大容量；
• position：当前已经读写的字节数；
• limit：还可以读写的字节数；

状态变量的改变过程举例：

① 新建一个大小为 8 个字节的缓冲区，此时 position 为 0， 而 limit = capacity = 8。capacity 变量不会改变，下面的讨论会忽略它;

② 从输入通道中读取 5个字节数据写入缓冲区中，此时 position 为 5，limit 保持不变;

③ 在将缓冲区的数据写到输出通道之前，需要先调用 flip() 方法，这个方法将 limit 设置为 当前position，并将 position 设置为 0;

④ 从缓冲区中取 4个字节到输出缓冲中，此时 position 设为 4；

⑤ 最后需要调用 clear() 方法来清空缓冲区，此时 position 和 limit 都被设置为 最初位置。

文件 NIO 实例

以下展示了使用 NIO 快速复制文件的实例：

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

public static void fastCopy(String src, String dist) throws IOException {
    /* 获得源文件的输入字节流 */
    FileInputStream fin = new FileInputStream(src);
    /* 获取输入字节流的文件通道 */
    FileChannel fcin = fin.getChannel();
    /* 获取目标文件的输出字节流 */
    FileOutputStream fout = new FileOutputStream(dist);
    /* 获取输出字节流的文件通道 */
    FileChannel fcout = fout.getChannel();
    /* 为缓冲区分配 1024 个字节 */
    ByteBuffer buffer = ByteBuffer.allocateDirect(1024);
    while (true) {
        /* 从输入通道中读取数据到缓冲区中 */
        int r = fcin.read(buffer);
        /* read() 返回 -1 表示 EOF */
        if (r == -1) {
            break;
        }
        /* 切换读写 */
        buffer.flip();
        /* 把缓冲区的内容写入输出文件中 */
        fcout.write(buffer);
        /* 清空缓冲区 */
        buffer.clear();
    }
}

选择器Selector

NIO 常常被叫做 非阻塞 IO，主要是因为 NIO 在网络中的非阻塞特性被广泛使用。

NIO 实现了 IO 多路复用中的 Reactor 模型，一个线程 Thread 使用一个选择器 Selector 通过轮询的方式去监听多个通道 Channel上的事件，从而让一个线程就可以处理多个事件。

通过配置监听的通道 Channel 为非阻塞， 那么当Channel 上的 IO 事件还未到达时，就不会进入阻塞状态一直等待，而是继续轮序其他 Channel，找到 IO 事件已经到达的 Channel 执行。

因为创建 和 切换线程的开销很大，因此使用一个线程来处理 多个事件 而不是一个线程处理一个事件，对于 IO 密集型 应用 具有很好的性能。

应该注意的是，只有套接字 Channel 才能配置为 非阻塞，而 FileChannel 不能，为 FileChannel 配置非阻塞也没有意义。

1、创建选择器

1

Selector selector = Selector.open();

2、将通道注册到选择器上

1
2
3

ServerSocketChannel ssChannel = ServerSocketChannel.open();
ssChannel.configureBlocking(false);
ssChannel.register(selector, SelectionKey.OP_ACCEPT);

通道必须配置为 非阻塞模式，否则使用选择器就没有任何意义了，因为如果通道在某个事件上被阻塞，那么服务器就不能响应其他事件，必须等待这个事件处理完毕才能去处理其它事件，显然这和选择器的作用背道而驰。

在将通道注册到selector上时，还需要指定要注册的具体事件，主要有以下几类：

• SelectionKey.OP_CONNECT
• SelectionKey.OP_ACCEPT
• SelectionKey.OP_READ
• SelectionKey.OP_WRITE

它们在 SelectionKey 的定义如下：

1
2
3
4

public static final int OP_READ = 1 << 0;
public static final int OP_WRITE = 1 << 2;
public static final int OP_CONNECT = 1 << 3;
public static final int OP_ACCEPT = 1 << 4;

可以看出每个事件可以被当成一个位域，从而组成事件集整数。例如：

1

int interestSet = SelectionKey.OP_READ | SelectionKey.OP_WRITE;

3、监听事件

1

int num = selector.select();

使用 select() 来监听到达的事件，它会一直阻塞直到有至少一个事件到达。

4、获取达到的事件

1
2
3
4
5
6
7
8
9
10
11

Set<SelectionKey> keys = selector.selectedKeys();
Iterator<SelectionKey> keyIterator = keys.iterator();
while (keyIterator.hasNext()) {
    SelectionKey key = keyIterator.next();
    if (key.isAcceptable()) {
        // ...
    } else if (key.isReadable()) {
        // ...
    }
    keyIterator.remove();
}

5、事件循环

因为一次 select() 调用不能处理完所有的事件，并且服务器端有可能需要一直监听事件，因此服务器端处理事件的代码一般会放在一个死循环内。

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

while (true) {
    int num = selector.select();
    Set<SelectionKey> keys = selector.selectedKeys();
    Iterator<SelectionKey> keyIterator = keys.iterator();
    while (keyIterator.hasNext()) {
        SelectionKey key = keyIterator.next();
        if (key.isAcceptable()) {
            // ...
        } else if (key.isReadable()) {
            // ...
        }
        keyIterator.remove();
    }
}

套接字 NIO 实例

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

public class NIOServer {

    public static void main(String[] args) throws IOException {

        Selector selector = Selector.open();

        ServerSocketChannel ssChannel = ServerSocketChannel.open();
        ssChannel.configureBlocking(false);
        ssChannel.register(selector, SelectionKey.OP_ACCEPT);

        ServerSocket serverSocket = ssChannel.socket();
        InetSocketAddress address = new InetSocketAddress("127.0.0.1", 8888);
        serverSocket.bind(address);

        while (true) {

            selector.select();
            Set<SelectionKey> keys = selector.selectedKeys();
            Iterator<SelectionKey> keyIterator = keys.iterator();

            while (keyIterator.hasNext()) {

                SelectionKey key = keyIterator.next();

                if (key.isAcceptable()) {

                    ServerSocketChannel ssChannel1 = (ServerSocketChannel) key.channel();

                    // 服务器会为每个新连接创建一个 SocketChannel
                    SocketChannel sChannel = ssChannel1.accept();
                    sChannel.configureBlocking(false);

                    // 这个新连接主要用于从客户端读取数据
                    sChannel.register(selector, SelectionKey.OP_READ);

                } else if (key.isReadable()) {

                    SocketChannel sChannel = (SocketChannel) key.channel();
                    System.out.println(readDataFromSocketChannel(sChannel));
                    sChannel.close();
                }

                keyIterator.remove();
            }
        }
    }

    private static String readDataFromSocketChannel(SocketChannel sChannel) throws IOException {

        ByteBuffer buffer = ByteBuffer.allocate(1024);
        StringBuilder data = new StringBuilder();

        while (true) {

            buffer.clear();
            int n = sChannel.read(buffer);
            if (n == -1) {
                break;
            }
            buffer.flip();
            int limit = buffer.limit();
            char[] dst = new char[limit];
            for (int i = 0; i < limit; i++) {
                dst[i] = (char) buffer.get(i);
            }
            data.append(dst);
            buffer.clear();
        }
        return data.toString();
    }
}

1
2
3
4
5
6
7
8
9

public class NIOClient {
    public static void main(String[] args) throws IOException {
        Socket socket = new Socket("127.0.0.1", 8888);
        OutputStream out = socket.getOutputStream();
        String s = "hello world";
        out.write(s.getBytes());
        out.close();
    }
}

内存映射文件

内存映射文件 I/O 是一种读和写文件数据的方法，它可以比常规的基于流或者基于通道的 I/O 快得多。

向内存映射文件写入可能是危险的，只是改变数组的单个元素这样的简单操作，就可能会直接修改磁盘上的文件。修改数据与将数据保存到磁盘是没有分开的。

下面代码行将文件的前 1024 个字节映射到内存中，map() 方法返回一个 MappedByteBuffer，它是 ByteBuffer 的子类。因此，可以像使用其他任何 ByteBuffer 一样使用新映射的缓冲区，操作系统会在需要时负责执行映射。

1

MappedByteBuffer mbb = fc.map(FileChannel.MapMode.READ_WRITE, 0, 1024);

对比

NIO 与普通 I/O 的区别主要有以下两点：

• NIO 是非阻塞的；
• NIO 是面向块，I/O 面向流；

八、参考资料

• IBM: NIO 入门
• Java NIO Tutorial
• Java NIO 浅析
• IBM: 深入分析 Java I/O 的工作机制
• IBM: 深入分析 Java 中的中文编码问题
• IBM: Java 序列化的高级认识
• NIO 与传统 IO 的区别
• Decorator Design Pattern
• Socket Multicast