首页 文章 精选 留言 我的

精选列表

搜索[图像理解]，共10000篇文章
优秀的个人博客,低调大师

Flink State 状态原理解析 | 京东物流技术团队

一、Flink State 概念 State 用于记录 Flink 应用在运行过程中，算子的中间计算结果或者元数据信息。运行中的 Flink 应用如果需要上次计算结果进行处理的，则需要使用状态存储中间计算结果。如 Join、窗口聚合场景。 Flink 应用运行中会保存状态信息到 State 对象实例中，State 对象实例通过 StateBackend 实现将相关数据存储到 FS 文件系统或者 RocksDB 数据库中。在Flink应用运行过程中，通过 checkpoint 快照定期地保存状态数据。并在 Flink 应用重启时加载checkpoint/savepoint 来实现状态的恢复，从而让 Flink 应用继续完成之前的数据计算，实现数据精确一次向下游传递。 1.1 Apache Flink 中 State 的存储实现 StateBackend 分类 分为以下3类： 基于内存的 HeapStateBackend。状态存储在内存中。 基于 HDFS 或 OSS 的 FsStateBackend。状态存储在内存，并在做 cp（checkpoint）时存到远端。 基于 RocksDB 的 RocksDBStateBackend。将对象序列化成二进制存在内存和本地磁盘的 RocksDB 数据中，并在 cp 时存到远端。 HeapStateBackend 和 RocksDBStateBackend 分别对应在 TaskManager 内存模型中的位置： RocksDBStateBackend 中存储结构：  namespace: 在不同的 namespace 下存在相同名称的状态。 1.1.1 State 状态持久化 通过 Chandy-Lamport 分布式快照算法进行 checkpoint 完成状态数据的持久化。然后在 Flink 应用重启时读取 State 状态数据，进行运行现场的还原。 chekcpoint 分类： 基于内存的全量 checkpoint HDFS 全量 checkpoint RocksDB 全量 checkpoint/增量 checkpoint 1.2 State 基于算子和数据分组的分类 State 可分为 Operator State 和 Keyed State 两类。 Operator State（称为 non-keyed state） 常常存在于Source, Sink中。具体实现类例如： BroadcastState 例：Kafka Source 中用 OperatorState 记录 offset。 Keyed State 任何类型的 keyed state 都可以有有效期(TTL)，所有状态类型都支持单元素的 TTL。 这意味着 List 元素和 Map 映射元素将独立到期。 例：SQL GroupBy/PartitionBy 后的窗口中的数据，每个 key 都有对应的 State。key 与 key 之间的 State 数据不可见。 keyed state 的具体实现类： ValueState MapState ListState AggregatingState ReducingState 。。。。。 Flink State思维导图：   Keyed State Operator State 适用算子类型 只适用于KeyedStream上的算子 可用于所有算子 状态分配 每个Key对应一个状态 一个算子子任务对应一个状态 横向扩展 状态随着keyBy的分组KeyGroup自动在多个算子子任务上迁移 有多种状态重新分配的方式 创建和访问方式 自定义算子（重写RichFunction，通过State 名称从 getRuntimeContext方法创建或获得 State ） 实现 CheckpointedFunction 等接口 支持数据结构 ValueState、ListState、MapState等 ListState、BroadcastState等 二、常见状态相关处理流程 2.1 Flink 应用中状态是如何存储的？  1. Kafka Source 如何存储 OperatorState？ class FlinkKafkaConsumerBase { private transient ListState<Tuple2<KafkaTopicPartition, Long>> unionOffsetStates; // state名称："topic-partition-offset-states" // 特殊的State类型：Union State } unionOffsetStates这个变量就是 OperatorState类型的。 2. Map算子如何存储需要累计的数据？ ValueState/MapState/ListState/...... 思考：keyby 后的数据分发与多并行度 subtask 之间的关系是怎样的？ 首先，datastream 中数据经过 keyby 之后，会划分到各个 KeyedStream 中。每个 KeyedStream 有自己的 KeyedState(如ValueState/ListState/MapState)。 其次，KeyedStream 中的数据会以 KeyGroup 方式组织在一起。KeyGroup 是 Flink 重新分发 key state 的最小单元。 最后，KeyGroup 中的数据会通过取模最大并行度的方式分散到各个 subtask 中。以下是关键源码： KeyGroupStreamPartitioner#selectChannel(record) { K key; key = keySelector.getKey(record.getInstance().getValue()); return KeyGroupRangeAssignment.assignKeyToParallelOperator( key, maxParallelism, numberOfChannels); } --KeyGroupRangeAssignment#assignKeyToParallelOperator（） { return computeOperatorIndexForKeyGroup(maxParallelism, parallelism, assignToKeyGroup(key, maxParallelism)); } --KeyGroupRangeAssignment#computeOperatorIndexForKeyGroup（） 公式：OperatorIndex = keyGroupId * parallelism / maxParallelism --KeyGroupRangeAssignment#assignToKeyGroup() { return computeKeyGroupForKeyHash(key.hashCode(), maxParallelism); } 2.2 修改并行度场景时 State 状态存储的变化  2.3 State 与 Checkpoint 关系 分布式快照 Checkpoint 的概念，定期将 State 持久化到 外部存储系统（HDFS/OSS） 上。用户可以通过实现 CheckpointedFunction 接口来使用 operator state。通过 barrier 来对齐 checkpoint，等待 State 持久化完成（此过程参数不同也可能是异步的）。 常见 State 与 CP 相关的问题： State 状态过大。现象为多个算子或单个算子多个 subtask 做 checkpoint 慢，可导致 CP 对齐时间长，严重时会导致 CP 超时。 数据倾斜导致某个 subtask 处理不及时。现象为单个算子少数几个 subtask 做 checkpoint 慢，导致 CP 对齐时间长。严重时会导致 CP 超时。 大作业（并行度搞）频繁做 CP，会频繁上传小文件，导致 HDFS 集群小文件过多。 常用解决措施：调大托管内存大小。 三、参考文档： Flink State 官方文档：Flink 状态与容错 https://cloud.tencent.com/developer/article/1403939 https://www.modb.pro/db/81206 作者：京东物流 吴云涛 来源：京东云开发者社区 自猿其说Tech 转载请注明来源
2023-12-06
优秀的个人博客,低调大师

SpringBoot自动配置原理解析 | 京东物流技术团队

1: 什么是SpringBoot自动配置 首先介绍一下什么是SpringBoot，SpringBoost是基于Spring框架开发出来的功能更强大的Java程序开发框架，其最主要的特点是：能使程序开发者快速搭建一套开发环境。SpringBoot能将主流的开发框架（例如SpringMVC,Dubbo,Mybatis,Redis等），做到像Maven导入Jar包一样的简洁快速，做到开箱即用。其中最关键的技术就是SpringBoot定制的各种Starter，通Maven引入Starter就能快速搭建开发环境。 2: SpringBoot Starter自动装配案例 在以前单独使用SpringMVC Web编程框架时，我们需要单独配置DispatcherServlet和Tomcat，使用SpringBoot之后，我们只需要引入SpringBoot-Starter-Web就能直接开始编写Controller等Web相关的代码，这就是SpringBoot为们提供的开箱即用的便捷能力，下面就以SpringBoot-Starter-Web来说明SpringBoot自动配置的关键原理 3: SpringBoot自动装配案例源码解析 3.1 DispatcherServlet的自动配置原理 首先我们定位到SpringBoot自动配置的Maven依赖 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-autoconfigure</artifactId> <version>${spring-boot.version}</version> </dependency> 在依赖的Jar包中我们可以在META-INF/spring.factories中找到自动配置类： org.springframework.boot.autoconfigure.web.servlet.DispatcherServletAutoConfiguration 在这个类中存在有一个静态内部类： org.springframework.boot.autoconfigure.web.servlet.DispatcherServletAutoConfiguration.DispatcherServletConfiguration 下图是这个配置类的主要源码和解析： 下面将上图中关键的注解功能，分别进行功能说明 3.1.1：@EnableConfigurationProperties({WebMvcProperties.class})注解解析 这个注解表示使WebMvcProperties.class类上的@ConfigurationProperties这个注解生效，同时@ConfigurationProperties这个注解是将application.xml中以spring.mvc开头的配置参数自动注入到WebMvcProperties.class类的字段中 3.1.2：@Conditional({DefaultDispatcherServletCondition.class}注解解析 该注解的原理就是将满足特定条件情况下的Bean自动加载到Spring容器中，该注解对应的Spring接口就是org.springframework.context.annotation.Condition这个接口 public interface Condition { boolean matches(ConditionContext var1, AnnotatedTypeMetadata var2); } 3.1.3：@ConditionOnClass注解解析 @ConditionOnClass这个注解是在当程序代码环境classpath下存在xxx.class的情况下条件成立，同时最终也会调用到matches方法中，其中关键的源码如下： protected static Class<?> resolve(String className, ClassLoader classLoader) throws ClassNotFoundException { return classLoader != null ? Class.forName(className, false, classLoader) : Class.forName(className); } 从上面可以看到，代码利用Class.forName方法加载classpath下的xxx.class类，如果加载成功条件就会成立。最后，在满足了所有@ConditionOnal注解条件后，SpringBoot就会自动为我们在Spring容器中注入DispatcherServlet了，无需单独配置了，直接引入spring-boot-starter-webr即可开始使用web相关功能。 3.1.4：总结 我们以DispatcherServlet是如何自动配置到容器中为例，探究了SpringBoot Starter的自动配置原理，其中涉及了几个关键的注解和步骤： 第一步：涉及到了配置文件的读取和个性化配置，这里就涉及到了下面这两个注解 @ConfigurationProperties @EnableConfigurationProperties 第二步：设计到了在什么条件下才自动配置的注解 @Conditional @ConditionalOnClass 第三步：约定了自动配置类的加载路径 /META-INF/spring-factories org.springframework.boot.autoconfigure.EnableAutoConfiguration=自动配置类全路径名称 在我们了解到了SpringBoot自动配置的原理之后，我们就可以自定义一个SpringBoot Starter来快速搭建我们的开发环境了 4:自定义一个打印输入输出日志的Starter 4.1 首先定义一个标记需要打印出入参日志的注解@PrintLog @Target(ElementType.METHOD) @Retention(RetentionPolicy.RUNTIME) public @interface PrintLog { } 4.2 定义一个存放打印日志配置的实体类 //自动注入application配置文件中已log.switch开头的配置参数 @ConfigurationProperties("log.switch") public class LogProperties { //是否启用打印日志功能 private Boolean enabled = false; //是否打印调用者ip private Boolean printIp = false; //是否打印调用者url private Boolean printUrl = false } 4.3 定义一个@PrintLog注解的切面类 @Aspect public class LogAspect { private static final Log LOGGER = LogFactory.getLog(LogAspect.class); private LogProperties logProperties; @Pointcut("@annotation(com.zl.annotation.PrintLog)") public void Log(){} @Around("Log()") public Object doAround(ProceedingJoinPoint joinPoint) throws Throwable { ServletRequestAttributes attributes = (ServletRequestAttributes) RequestContextHolder.getRequestAttributes(); HttpServletRequest request = attributes.getRequest(); MethodSignature signature = (MethodSignature) joinPoint.getSignature(); Method method = signature.getMethod(); String methodName = method.getName(); //打印调用url if (Boolean.TRUE.equals(logProperties.getPrintUrl())){ LOGGER.info("URL:" + request.getRequestURL().toString()); } //打印ip if (Boolean.TRUE.equals(logProperties.getPrintIp())) { LOGGER.info("IP :" + request.getRemoteAddr()); } //打印方法 LOGGER.info("method :" + methodName); //打印参数 LOGGER.info("parameter :" + Arrays.toString(joinPoint.getArgs())); Object result = joinPoint.proceed(); //打印返回结果 LOGGER.info("return :" + JSON.toJSONString(result)); return result; } } 4.4 定义一个打印日志的自动配置类 @Configuration @EnableConfigurationProperties({LogProperties.class}) //表示在application配置文件中必须配置log.switch.enabled = true才启动自动配置 @ConditionalOnProperty(prefix = "log.switch", value = "enabled", havingValue = "true") public class LogAutoConfigure { @Bean //Advice.class是aop切面中关键的切面方法类(@Before，@After等) //程序中有Advice.class类说明需要使用切面功能，这时才加载自定义的切面类 @ConditionalOnClass(Advice.class) public LogAspect webLogAspect(LogProperties logProperties){ return new LogAspect(logProperties); } } @ConditionalOnProperty表示在application配置文件中必须存在相应的配置才能使条件成立 4.5 配置自定义配置类的加载路径 META-INF/spring.factories org.springframework.boot.autoconfigure.EnableAutoConfiguration=\ com.zl.autoConfigure.LogAutoConfigure 4.6 Maven打包部署 maven install 5:开始使用自定义的Starter 5.1 在项目中引入Starter <dependency> <groupId>com.zl.demo</groupId> <artifactId>LogStarter</artifactId> <version>1.0-SNAPSHOT</version> </dependency> 5.2 在application.yml中配置参数 log: switch: enabled: true //启用打印日志功能 printIp: true //打印请求ip printUrl: true //打印请求url 经过上面两个步骤就，打印日志的功能就已经开启了，接下来就可以进行编码测试了 5.3 定义一个Controller并标上打印日志的注解 @RestController @RequestMapping("/test") public class HelloWorldController { @PrintLog @RequestMapping("/hello") public String helleWorld(String test){ return "hello world!"; } } 5.4 启动项目开始测试 com.zl.aspect.LogAspect : URL:http://localhost:8080/test/hello com.zl.aspect.LogAspect : IP :0:0:0:0:0:0:0:1 com.zl.aspect.LogAspect : method :helleWorld com.zl.aspect.LogAspect : parameter :[test] com.zl.aspect.LogAspect : return :"hello world!" 可以看到上面的入参和返回值都已经打印出来了，说明了自定义的starter已经生效了。 6：总结 SpringBoot自动配置功能带给我们的是开箱即用，快速便捷的功能，自动配置为我们研发人员带来的优点，我主要总结为以下两点： 1：提高研发效率。我们可以快速构建开发环境，对于开发中使用到的开源组件和中间件，我们直接引入对应的Starter就可以直接开发了，例如Redis和Mybatis等，可以直接引入对应的spring-boot-starter-data-redis就可以直接使用RedisTemplate来操作Redis了，这样可以极大的提高研发的效率，无需再进行复杂的起步配置了和各种版本依赖管理了。 2：标准模块复用。对于业务开发中的一些标准模块，例如常用的一些三方服务，我们可以利用Starter直接配置好，在需要使用的项目中直接引入这个starter就可以立即使用了，无需再去引入Jar包和编写配置文件等，同样的，对于一些标准非业务强耦合的功能，例如监控，鉴权等，也可以定义一个Starter，需要使用鉴权和监控功能的项目就可以直接复用了，无需再次开发。 作者：京东零售 钟磊 来源：京东云开发者社区 自猿其说Tech 转载请注明来源
2023-10-25
优秀的个人博客,低调大师

深入理解MySQL索引底层数据结构

1 引言 在日常工作中，我们会遇见一些慢SQL，在分析这些慢SQL时，我们通常会看下SQL的执行计划，验证SQL执行过程中有没有走索引。通常我们会调整一些查询条件，增加必要的索引，SQL执行效率就会提升几个数量级。我们有没有思考过，为什么加了索引就会能提高SQL的查询效率，为什么有时候加了索引SQL执行反而会没有变化，本文就从MySQL索引的底层数据结构和算法来进行详细分析。 2 索引数据结构对比 索引的定义：索引(Index)是帮助MySQL高效获取数据的排好序的数据结构。 索引中常见的数据结构有以下几种： Hash表 二叉树 红黑树 B-Tree B+Tree Hash表 通过索引的key进行一次hash计算，就可以快速获取磁盘文件指针，对于指定索引查找文件非常快，但是对于范围查找没法支持，有时候也会出现Hash冲突的情况。 二叉树 二叉树的特点：左边子节点的数据小于父节点数据，右边子节点的数据大于父节点数据。如下图所示，如果col2是索引，查找索引为65的行元素，只需要查找两次，就可以获取到行元素所在的磁盘指针地址。 但如果是一个按照顺序递增的值，例如为col1建立索引，不再适合使用二叉树建立索引，因为此时使用二叉树建立索引将会变成一个链式索引，此时的索引结构如下图所示，如果查找6节点需要6次遍历才能找到。 红黑树 红黑树是一种二叉平衡树，可以提高查询效率，此时若再查找6节点只需要遍历3次就能找到了。但红黑树也有缺点，当存储大数据量时，树的高度就会变的不可控， 数量越大，树的高度越高，查询的效率将会大大降低。 B-Tree B-Tree是一种多路二叉树，所具有的特点：1 叶节点具有相同的深度，叶节点的指针为空；2 所有索引元素不重复；3 节点中的数据索引从左到右递增排列。 B+Tree B+Tree是B-Tree的变种，所具有的特点：1 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引；2 叶子节点包含所有索引字段；3 叶子节点用指针连接，提高区间访问的性能。 与红黑树相比，B-Tree和B+Tree两种数据结构都更加矮胖，存储相同数量级的索引数据时，层级更低。 B-Tree和B+Tree之间一个很大的不同，是B+Tree的节点上不储存value，只储存key，而叶子节点上储存了所有key-value集合，并且节点之间都是有序的。这样的好处是每一次磁盘IO能够读取的节点更多，也就是树的度(Max.Degree)可以设置的更大一些，因为每次磁盘IO读取的磁盘页数是一定的。例如，每次磁盘IO能够读取1页=4kb，那么省去value的情况下同样一页数据能够读取更多的key，这样就大大减少了磁盘的IO次数。 此外，B+Tree也是排好序的数据结构，数据库中><或者order by等都可以直接依赖这一特性。 MySQL中对于索引使用的主要数据结构也是B+Tree，目的也是在读取数据时能够减少磁盘IO。 3 千万级数据如何用B+树索引快速查找 MySQL 官方对非叶子节点(如最上层 h = 1的节点，B+Tree高度为3) 的大小是有限制的，最大的大小是16K，可以通过以下SQL语句查询到，当然这个值是可以调的，既然官方给出这个阈值说明再大的话会影响磁盘IO效率。 从执行结果，可以看到大小为 16384，即 16K大小。 假如：B+Tree的表都存满了。主键索引的类型为BigInt，大小为8B，指针存储了下个节点的文件地址，大小为6B。最后一层，假如 存放的数据data为1K 大小，那么 第一层最大节点数为： 16k / (8B + 6B) ≈ 1170 (个)； 第二层最大节点数也应为：1170个； 第三层最大节点数为：16K / 1K = 16 (个)。 则，一张B+Tree的表最多存放 1170117016 ≈ 2千万。 所以，通过分析，我们可以得出，B+Tree结构的表可以容纳千万数据量的查询。而且一般来说，MySQL会把 B+Tree 根节点放在内存中，那只需要两次磁盘IO就行。 4 存储引擎索引实现 MySQL中索引储存在哪里呢？和数据一样，索引以文件形式储存在硬盘上。 在MyISAM储存引擎中，数据和索引文件试试分开储存的，数据存在.MYD结尾的文件中，索引单独存在.MYI结尾的文件中。 在InnoDB中，数据和索引文件是合起来储存的，注意下图中没有了.MYI结尾的文件，只有一个.ibd结尾的文件。 MyISAM索引文件和数据文件是分离的(非聚集)，并且主键索引和辅助索引（二级索引）的储存方式是一样的。 InnoDB中索引文件和数据文件是同一个文件（聚集），并且主键索引和二级索引储存方式有所不同，如图所示，二级索引的叶子节点不储存数据，仅储存主键ID。 这里思考几个问题： 为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？ 为什么非主键索引结构叶子节点存储的是主键值？ 如果我们在创建表时不设置主键，InnoDB会自动帮我们从第一列开始筛选一列数据不重复的列做为主键，如果找不到这样的列，就会创建一个隐藏的列（rowid）做为主键，这会增加很多MySQL的工作，所以建议我们在创建InnoDB表时一定要设置主键。 整型的字段做为主键，一方面在数据比较时不需要进行转换，另一方面存储也比较节省空间。那为什么要强调主键自增呢？如果主键id是无序的，那么很有可能新插入的值会导致当前节点分裂，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。反之，如果每次插入有序，那就会在当前页后面连续写入，写不下就会重新分配一个节点，内存都是连续的，这样效率自然也就最高了。 非主键索引的叶子节点存储主键值而非全部数据，主要也是为了一致性和节省空间。如果二级索引储存的也是数据，那么每次插入MySQL都不得不更新每棵索引树，这样就加剧了新增编辑时的性能损耗，并且这样一来空间利用率也不高，必然产生了大量冗余数据。 5 联合索引底层数据结构又是怎样的 联合索引又叫复合索引，例如下表： CREATE TABLE `test` ( `id` bigint NOT NULL AUTO_INCREMENT, `name` varchar(24) NOT NULL, `age` int NOT NULL, `position` varchar(32) NOT NULL, `address` varchar(128) NOT NULL, `birthday` date NOT NULL, PRIMARY KEY (`id`), UNIQUE KEY `idx_name_age_position` (`name`,`age`,`position`) USING BTREE ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8; 如下索引就是一个联合索引。 `idx_name_age_position` (`name`,`age`,`position`) USING BTREE 联合索引底层数据结构长什么样？ 比较相等时，先比较第一列的值，如果相等，再继续比较第二列，以此类推。 了解了联合索引的存储结构，我们就知道了索引最左前缀优化原则是怎么回事了，在使用联合索引时，对于索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引（name,age,position），MySQL会从最左边的列优先匹配，如果最左边的带头大哥name没有使用到，在未使用覆盖索引的情况下，就只能全表扫描。 联合底层数据结构思考：MySQL会优先以联合索引第一列匹配，此后才会匹配下一列，如果不指定第一列匹配的值，也就无法得知下一步查询哪个节点。 6 总结 索引本质上是一种排好序的数据结构，了解了MySQL索引的底层数据结构及存储原理，可以帮助我们更好地进行SQL优化。其实数据库索引调优是一项技术活，不能仅仅靠理论，因为实际情况千变万化，而且MySQL本身存在很复杂的机制，如查询优化策略和各种引擎的实现差异等都会使情况变得更加复杂。但同时这些理论是索引调优的基础，只有在明白理论的基础上，才能对调优策略进行合理推断并了解其背后的机制，然后结合实践中不断的实验和摸索，从而真正达到高效使用MySQL索引的目的。 最后，如果大家想再温习一下数据结构的知识，这个数据结构网站（https://www.cs.usfca.edu/~galles/visualization/Algorithms.html）不可错过，可以很好地帮助我们演示数据结构的存储过程。 作者：京东物流于朔
2023-04-06
优秀的个人博客,低调大师

深入理解跳表及其在Redis中的应用

前言 跳表可以达到和红黑树一样的时间复杂度 O(logN)，且实现简单，Redis 中的有序集合对象的底层数据结构就使用了跳表。其作者威廉·普评价：跳跃链表是在很多应用中有可能替代平衡树的一种数据结构。本篇文章将对跳表的实现及在Redis中的应用进行学习。 一. 跳表的基础概念 跳表，即跳跃链表（Skip List），是基于并联的链表数据结构，操作效率可以达到O(logN)，对并发友好，跳表的示意图如下所示。 跳表的特点，可以概括如下。 •跳表是多层（level）链表结构； •跳表中的每一层都是一个有序链表，并且按照元素升序（默认）排列； •跳表中的元素会在哪一层出现是随机决定的，但是只要元素出现在了第 k 层，那么 k 层以下的链表也会出现这个元素； •跳表的底层的链表包含所有元素； •跳表头节点和尾节点不存储元素，且头节点和尾节点的层数就是跳表的最大层数； •跳表中的节点包含两个指针，一个指针指向同层链表的后一节点，一个指针指向下层链表的同元素节点。 以上图中的跳表为例，如果要查找元素 71，那么查找流程如下图所示。 从顶层链表的头节点开始查找，查找到元素71的节点时，一共遍历了4个节点，但是如果按照传统链表的方式（即从跳表的底层链表的头节点开始向后查找），那么就需要遍历7个节点，所以跳表以空间换时间，缩短了操作跳表所需要花费的时间。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。这种数据结构是由William Pugh(音译为威廉·普)发明的，最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。 谷歌上找到一篇作者关于跳表的论文，感兴趣强烈建议下载阅读： https://epaperpress.com/sortsearch/download/skiplist.pdf 跳表在动态查找过程中使用了一种非严格的平衡机制来让插入和删除都更加便利和快捷，这种非严格平衡是基于概率的，而不是平衡树的严格平衡。说到非严格平衡，首先想到的是红黑树RbTree，它同样采用非严格平衡来避免像AVL那样调整树的结构，这里就不展开讲红黑树了，看来跳表也是类似的路子，但是是基于概率实现的。 二. 跳表的节点 已知跳表中的节点，需要有指向当前层链表后一节点的指针，和指向下层链表的同元素节点的指针，所以跳表中的节点，定义如下。 public class SkiplistNode { public int data; public SkiplistNode next; public SkiplistNode down; public int level; public SkiplistNode(int data, int level) { this.data = data; this.level = level; } 上述是跳表中的节点的最简单的定义方式，存储的元素 data 为整数，节点之间进行比较时直接比较元素 data 的大小。 三. 跳表的初始化 跳表初始化时，将每一层链表的头尾节点创建出来并使用集合将头尾节点进行存储，头尾节点的层数随机指定，且头尾节点的层数就代表当前跳表的层数。初始化后，跳表结构如下所示。 跳表初始化的相关代码如下所示。 public LinkedList<SkiplistNode> headNodes; public LinkedList<SkiplistNode> tailNodes; public int curLevel; public Random random; public Skiplist() { random = new Random(); //headNodes用于存储每一层的头节点 headNodes = new LinkedList<>(); //tailNodes用于存储每一层的尾节点 tailNodes = new LinkedList<>(); //初始化跳表时，跳表的层数随机指定 curLevel = getRandomLevel(); //指定了跳表的初始的随机层数后，就需要将每一层的头节点和尾节点创建出来并构建好关系 SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0); SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0); for (int i = 0; i <= curLevel; i++) { head.next = tail; headNodes.addFirst(head); tailNodes.addFirst(tail); SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1); SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1); headNew.down = head; tailNew.down = tail; head = headNew; tail = tailNew; } } 四. 跳表的添加方法 每一个元素添加到跳表中时，首先需要随机指定这个元素在跳表中的层数，如果随机指定的层数大于了跳表的层数，则在将元素添加到跳表中之前，还需要扩大跳表的层数，而扩大跳表的层数就是将头尾节点的层数扩大。下面给出需要扩大跳表层数的一次添加的过程。 初始状态时，跳表的层数为 2，如下图所示。 现在要往跳表中添加元素 120，并且随机指定的层数为 3，大于了当前跳表的层数 2，此时需要先扩大跳表的层数，2如 下图所示。 现在要往跳表中添加元素 120，并且随机指定的层数为 3，大于了当前跳表的层数 2，此时需要先扩大跳表的层数，2如 下图所示。 将元素 120 插入到跳表中时，从顶层开始，逐层向下插入，如下图所示。 跳表的添加方法的代码如下所示。 public void add(int num) { //获取本次添加的值的层数 int level = getRandomLevel(); //如果本次添加的值的层数大于当前跳表的层数 //则需要在添加当前值前先将跳表层数扩充 if (level > curLevel) { expanLevel(level - curLevel); } //curNode表示num值在当前层对应的节点 SkiplistNode curNode = new SkiplistNode(num, level); //preNode表示curNode在当前层的前一个节点 SkiplistNode preNode = headNodes.get(curLevel - level); for (int i = 0; i <= level; i++) { //从当前层的head节点开始向后遍历，直到找到一个preNode //使得preNode.data < num <= preNode.next.data while (preNode.next.data < num) { preNode = preNode.next; } //将curNode插入到preNode和preNode.next中间 curNode.next = preNode.next; preNode.next = curNode; //如果当前并不是0层，则继续向下层添加节点 if (curNode.level > 0) { SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1); //curNode指向下一层的节点 curNode.down = downNode; //curNode向下移动一层 curNode = downNode; } //preNode向下移动一层 preNode = preNode.down; } } private void expanLevel(int expanCount) { SkiplistNode head = headNodes.getFirst(); SkiplistNode tail = tailNodes.getFirst(); for (int i = 0; i < expanCount; i++) { SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1); SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1); headNew.down = head; tailNew.down = tail; head = headNew; tail = tailNew; headNodes.addFirst(head); tailNodes.addFirst(tail); } } 五. 跳表的搜索方法 在跳表中搜索一个元素时，需要从顶层开始，逐层向下搜索。搜索时遵循如下规则。 •目标值大于当前节点的后一节点值时，继续在本层链表上向后搜索； •目标值大于当前节点值，小于当前节点的后一节点值时，向下移动一层，从下层链表的同节点位置向后搜索； •目标值等于当前节点值，搜索结束。 •下图是一个搜索过程的示意图。 •跳表的搜索的代码如下所示。 public boolean search(int target) { //从顶层开始寻找，curNode表示当前遍历到的节点 SkiplistNode curNode = headNodes.getFirst(); while (curNode != null) { if (curNode.next.data == target) { //找到了目标值对应的节点，此时返回true return true; } else if (curNode.next.data > target) { //curNode的后一节点值大于target //说明目标节点在curNode和curNode.next之间 //此时需要向下层寻找 curNode = curNode.down; } else { //curNode的后一节点值小于target //说明目标节点在curNode的后一节点的后面 //此时在本层继续向后寻找 curNode = curNode.next; } } return false; } 六. 跳表的删除方法 当在跳表中需要删除某一个元素时，则需要将这个元素在所有层的节点都删除，具体的删除规则如下所示。 •首先按照跳表的搜索的方式，搜索待删除节点，如果能够搜索到，此时搜索到的待删除节点位于该节点层数的最高层； •从待删除节点的最高层往下，将每一层的待删除节点都删除掉，删除方式就是让待删除节点的前一节点直接指向待删除节点的后一节点。 •下图是一个删除过程的示意图。 •跳表的删除的代码如下所示。 public boolean erase(int num) { //删除节点的遍历过程与寻找节点的遍历过程是相同的 //不过在删除节点时如果找到目标节点，则需要执行节点删除的操作 SkiplistNode curNode = headNodes.getFirst(); while (curNode != null) { if (curNode.next.data == num) { //preDeleteNode表示待删除节点的前一节点 SkiplistNode preDeleteNode = curNode; while (true) { //删除当前层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点 preDeleteNode.next = curNode.next.next; //当前层删除完后，需要继续删除下一层的待删除节点 //这里让preDeleteNode向下移动一层 //向下移动一层后，preDeleteNode就不一定是待删除节点的前一节点了 preDeleteNode = preDeleteNode.down; //如果preDeleteNode为null，说明已经将底层的待删除节点删除了 //此时就结束删除流程，并返回true if (preDeleteNode == null) { return true; } //preDeleteNode向下移动一层后，需要继续从当前位置向后遍历 //直到找到一个preDeleteNode，使得preDeleteNode.next的值等于目标值 //此时preDeleteNode就又变成了待删除节点的前一节点 while (preDeleteNode.next.data != num) { preDeleteNode = preDeleteNode.next; } } } else if (curNode.next.data > num) { curNode = curNode.down; } else { curNode = curNode.next; } } return false; } 七. 跳表完整代码 跳表完整代码如下所示。 public class Skiplist { public LinkedList<SkiplistNode> headNodes; public LinkedList<SkiplistNode> tailNodes; public int curLevel; public Random random; public Skiplist() { random = new Random(); //headNodes用于存储每一层的头节点 headNodes = new LinkedList<>(); //tailNodes用于存储每一层的尾节点 tailNodes = new LinkedList<>(); //初始化跳表时，跳表的层数随机指定 curLevel = getRandomLevel(); //指定了跳表的初始的随机层数后，就需要将每一层的头节点和尾节点创建出来并构建好关系 SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0); SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0); for (int i = 0; i <= curLevel; i++) { head.next = tail; headNodes.addFirst(head); tailNodes.addFirst(tail); SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1); SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1); headNew.down = head; tailNew.down = tail; head = headNew; tail = tailNew; } } public boolean search(int target) { //从顶层开始寻找，curNode表示当前遍历到的节点 SkiplistNode curNode = headNodes.getFirst(); while (curNode != null) { if (curNode.next.data == target) { //找到了目标值对应的节点，此时返回true return true; } else if (curNode.next.data > target) { //curNode的后一节点值大于target //说明目标节点在curNode和curNode.next之间 //此时需要向下层寻找 curNode = curNode.down; } else { //curNode的后一节点值小于target //说明目标节点在curNode的后一节点的后面 //此时在本层继续向后寻找 curNode = curNode.next; } } return false; } public void add(int num) { //获取本次添加的值的层数 int level = getRandomLevel(); //如果本次添加的值的层数大于当前跳表的层数 //则需要在添加当前值前先将跳表层数扩充 if (level > curLevel) { expanLevel(level - curLevel); } //curNode表示num值在当前层对应的节点 SkiplistNode curNode = new SkiplistNode(num, level); //preNode表示curNode在当前层的前一个节点 SkiplistNode preNode = headNodes.get(curLevel - level); for (int i = 0; i <= level; i++) { //从当前层的head节点开始向后遍历，直到找到一个preNode //使得preNode.data < num <= preNode.next.data while (preNode.next.data < num) { preNode = preNode.next; } //将curNode插入到preNode和preNode.next中间 curNode.next = preNode.next; preNode.next = curNode; //如果当前并不是0层，则继续向下层添加节点 if (curNode.level > 0) { SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1); //curNode指向下一层的节点 curNode.down = downNode; //curNode向下移动一层 curNode = downNode; } //preNode向下移动一层 preNode = preNode.down; } } public boolean erase(int num) { //删除节点的遍历过程与寻找节点的遍历过程是相同的 //不过在删除节点时如果找到目标节点，则需要执行节点删除的操作 SkiplistNode curNode = headNodes.getFirst(); while (curNode != null) { if (curNode.next.data == num) { //preDeleteNode表示待删除节点的前一节点 SkiplistNode preDeleteNode = curNode; while (true) { //删除当前层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点 preDeleteNode.next = curNode.next.next; //当前层删除完后，需要继续删除下一层的待删除节点 //这里让preDeleteNode向下移动一层 //向下移动一层后，preDeleteNode就不一定是待删除节点的前一节点了 preDeleteNode = preDeleteNode.down; //如果preDeleteNode为null，说明已经将底层的待删除节点删除了 //此时就结束删除流程，并返回true if (preDeleteNode == null) { return true; } //preDeleteNode向下移动一层后，需要继续从当前位置向后遍历 //直到找到一个preDeleteNode，使得preDeleteNode.next的值等于目标值 //此时preDeleteNode就又变成了待删除节点的前一节点 while (preDeleteNode.next.data != num) { preDeleteNode = preDeleteNode.next; } } } else if (curNode.next.data > num) { curNode = curNode.down; } else { curNode = curNode.next; } } return false; } private void expanLevel(int expanCount) { SkiplistNode head = headNodes.getFirst(); SkiplistNode tail = tailNodes.getFirst(); for (int i = 0; i < expanCount; i++) { SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1); SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1); headNew.down = head; tailNew.down = tail; head = headNew; tail = tailNew; headNodes.addFirst(head); tailNodes.addFirst(tail); } } private int getRandomLevel() { int level = 0; while (random.nextInt(2) > 1) { level++; } return level; } } 八. 跳表在Redis中的应用 ZSet结构同时包含一个字典和一个跳跃表，跳跃表按score从小到大保存所有集合元素。字典保存着从member到score的映射。这两种结构通过指针共享相同元素的member和score，不会浪费额外内存。 typedef struct zset { dict *dict; zskiplist *zsl; } zset; ZSet中的字典和跳表布局： 1.ZSet中跳表的实现细节 随机层数的实现原理： 跳表是一个概率型的数据结构，元素的插入层数是随机指定的。Willam Pugh在论文中描述了它的计算过程如下：指定节点最大层数 MaxLevel，指定概率 p， 默认层数 lvl 为1； 生成一个0~1的随机数r，若r<p，且lvl<MaxLevel ，则lvl ++； 重复第 2 步，直至生成的r >p 为止，此时的 lvl 就是要插入的层数。 论文中生成随机层数的伪码： 在Redis中对跳表的实现基本上也是遵循这个思想的，只不过有微小差异，看下Redis关于跳表层数的随机源码src/z_set.c： /* Returns a random level for the new skiplist node we are going to create. * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL * (both inclusive), with a powerlaw-alike distribution where higher * levels are less likely to be returned. */ int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1; return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; } 其中两个宏的定义在redis.h中： #defineZSKIPLIST_MAXLEVEL32/*Shouldbeenoughfor2^32elements*/ #defineZSKIPLIST_P0.25/*SkiplistP=1/4*/ 可以看到while中的： (random()&0xFFFF)<(ZSKIPLIST_P*0xFFFF) 第一眼看到这个公式，因为涉及位运算有些诧异，需要研究一下Antirez为什么使用位运算来这么写？ 最开始的猜测是random()返回的是浮点数[0-1]，于是乎在线找了个浮点数转二进制的工具，输入0.5看了下结果： 可以看到0.5的32bit转换16进制结果为0x3f000000，如果与0xFFFF做与运算结果还是0，不符合预期。 实际应用时对于随机层数的实现并不统一，重要的是随机数的生成，在LevelDB中对跳表层数的生成代码是这样的： template <typename Key, typename Value> int SkipList<Key, Value>::randomLevel() { static const unsigned int kBranching = 4; int height = 1; while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) { height++; } assert(height > 0); assert(height <= kMaxLevel); return height; } uint32_t Next( uint32_t& seed) { seed = seed & 0x7fffffffu; if (seed == 0 || seed == 2147483647L) { seed = 1; } static const uint32_t M = 2147483647L; static const uint64_t A = 16807; uint64_t product = seed * A; seed = static_cast<uint32_t>((product >> 31) + (product & M)); if (seed > M) { seed -= M; } return seed; } 可以看到leveldb使用随机数与kBranching取模，如果值为0就增加一层，这样虽然没有使用浮点数，但是也实现了概率平衡。 2.跳表结点的平均层数 我们很容易看出，产生越高的节点层数出现概率越低，无论如何层数总是满足幂次定律越大的数出现的概率越小。 如果某件事的发生频率和它的某个属性成幂关系，那么这个频率就可以称之为符合幂次定律。 幂次定律的表现是少数几个事件的发生频率占了整个发生频率的大部分， 而其余的大多数事件只占整个发生频率的一个小部分。 幂次定律应用到跳表的随机层数来说就是大部分的节点层数都是黄色部分，只有少数是绿色部分，并且概率很低。 定量的分析如下： •节点层数至少为1，大于1的节点层数满足一个概率分布。 •节点层数恰好等于1的概率为p^0(1-p) •节点层数恰好等于2的概率为p^1(1-p) •节点层数恰好等于3的概率为p^2(1-p) •节点层数恰好等于4的概率为p^3(1-p) 依次递推节点层数恰好等于K的概率为p^(k-1)(1-p) 因此如果我们要求节点的平均层数，那么也就转换成了求概率分布的期望问题了： 表中P为概率，V为对应取值，给出了所有取值和概率的可能，因此就可以求这个概率分布的期望了。方括号里面的式子其实就是高一年级学的等比数列，常用技巧错位相减求和，从中可以看到结点层数的期望值与1-p成反比。对于Redis而言，当p=0.25时结点层数的期望是1.33。 总结 跳表的时间复杂度与AVL树和红黑树相同，可以达到O(logN)，但是AVL树要维持高度的平衡，红黑树要维持高度的近似平衡，这都会导致插入或者删除节点时的一些时间开销，所以跳表相较于AVL树和红黑树来说，省去了维持高度的平衡的时间开销，但是相应的也付出了更多的空间来存储多个层的节点，所以跳表是用空间换时间的数据结构。以Redis中底层的数据结构zset作为典型应用来展开，进一步看到跳跃链表的实际应用。
2023-02-23
优秀的个人博客,低调大师

深入理解 WKWebView (渲染篇) —— DOM 树的构建

全文12003字，预计阅读时间24分钟 当客户端 App 主进程创建 WKWebView 对象时，会创建另外两个子进程:渲染进程与网络进程。主进程 WKWebView 发起请求时，先将请求转发给渲染进程，渲染进程再转发给网络进程，网络进程请求服务器。如果请求的是一个网页，网络进程会将服务器的响应数据 HTML 文件字符流吐给渲染进程。渲染进程拿到 HTML 文件字符流，首先要进行解析，将 HTML 文件字符流转换成 DOM 树，然后在 DOM 树的基础上，进行渲染操作，也就是布局、绘制。最后渲染进程通知主进程 WKWebView 创建对应的 View 展现视图。整个流程如下图所示: 一、什么是DOM树 渲染进程获取到 HTML 文件字符流，会将HTML文件字符流转换成 DOM 树。下图中左侧是一个 HTML 文件，右边就是转换而成的 DOM 树。 可以看到 DOM 树的根节点是 HTMLDocument，代表整个文档。根节点下面的子节点与 HTML 文件中的标签是一一对应的，比如 HTML 中的 <head> 标签就对应 DOM 树中的 head 节点。同时 HTML 文件中的文本，也成为 DOM 树中的一个节点，比如文本 'Hello, World!'，在 DOM 树中就成为div节点的子节点。 在 DOM 树中每一个节点都是具有一定方法与属性的对象，这些对象由对应的类创建出来。比如 HTMLDocument 节点，它对应的类是 class HTMLDocument，下面是 HTMLDocument 的部分源码: class HTMLDocument : public Document { // 继承自 Document ... WEBCORE_EXPORT int width(); WEBCORE_EXPORT int height(); ... } 从源码中可以看到，HTMLDocument 继承自类 Document，Document 类的部分源码如下: class Document : public ContainerNode // Document继承自 ContainerNode，ContainerNode继承自Node , public TreeScope , public ScriptExecutionContext , public FontSelectorClient , public FrameDestructionObserver , public Supplementable<Document> , public Logger::Observer , public CanvasObserver { WEBCORE_EXPORT ExceptionOr<Ref<Element>> createElementForBindings(const AtomString& tagName); // 创建Element的方法 WEBCORE_EXPORT Ref<Text> createTextNode(const String& data); // 创建文本节点的方法 WEBCORE_EXPORT Ref<Comment> createComment(const String& data); // 创建注释的方法 WEBCORE_EXPORT Ref<Element> createElement(const QualifiedName&, bool createdByParser); // 创建Element方法 .... } 上面源码可以看到 Document 继承自 Node，而且还可以看到前端十分熟悉的 createElement、createTextNode 等方法，JavaScript 对这些方法的调用，最后都转换为对应 C++ 方法的调用。 类 Document 有这些方法，并不是没有原因的，而是 W3C 组织给出的标准规定的，这个标准就是 DOM(DocumentObjectModel，文档对象模型)。DOM 定义了 DOM 树中每个节点需要实现的接口和属性，下面是 HTMLDocument、Document、HTMLDivElement 的部分 IDL(InteractiveDataLanguage，接口描述语言，与具体平台和语言无关)描述，完整的 IDL 可以参看 W3C 。 在 DOM 树中，每一个节点都继承自类 Node，同时 Node 还有一个子类 Element，有的节点直接继承自类 Node，比如文本节点，而有的节点继承自类 Element，比如 div 节点。因此针对上面图中的 DOM 树，执行下面的 JavaScript 语句返回的结果是不一样的: document.childNodes; // 返回子Node集合，返回DocumentType与HTML节点，都继承自Node document.children; // 返回子Element集合，只返回HTML节点，DocumentType不继承自Element 下图给出部分节点的继承关系图: 二、DOM树构建 DOM 树的构建流程可以分为4个步骤:解码、分词、创建节点、添加节点。 2.1 解码 渲染进程从网络进程接收过来的是 HTML 字节流，而下一步分词是以字符为单位进行的。由于各种编码规范的存在，比如 ISO-8859-1、UTF-8 等，一个字符常常可能对应一个或者多个编码后的字节，解码的目的就是将 HTML 字节流转换成 HTML 字符流，或者换句话说，就是将原始的 HTML 字节流转换成字符串。 2.1.1 解码类图 从类图上看，类 HTMLDocumentParser 处于解码的核心位置，由这个类调用解码器将 HTML 字节流解码成字符流，存储到类 HTMLInputStream 中。 2.1.2 解码流程 整个解码流程当中，最关健的是如何找到正确的编码方式。只有找到了正确的编码方式，才能使用对应的解码器进行解码。解码发生的地方如下面源代码所示，这个方法在上图第3个栈帧被调用: // HTMLDocumentParser是DecodedDataDocumentParser的子类 void DecodedDataDocumentParser::appendBytes(DocumentWriter& writer, const uint8_t* data, size_t length) { if (!length) return; String decoded = writer.decoder().decode(data, length); // 真正解码发生在这里 if (decoded.isEmpty()) return; writer.reportDataReceived(); append(decoded.releaseImpl()); } 上面代码第7行 writer.decoder() 返回一个 TextResourceDecoder 对象，解码操作由 TextResourceDecoder::decode 方法完成。下面逐步查看 TextResourceDecoder::decode 方法的源码: // 只保留了最重要的部分 StringTextResourceDecoder::decode(constchar*data,size_tlength) { ... //如果是HTML文件，就从head标签中寻找字符集 if((m_contentType==HTML||m_contentType==XML)&&!m_checkedForHeadCharset)//HTMLandXML if(!checkForHeadCharset(data,length,movedDataToBuffer)) returnemptyString(); ... //m_encoding存储者从HTML文件中找到的编码名称 if(!m_codec) m_codec=newTextCodec(m_encoding);//创建具体的编码器 ... //解码并返回 Stringresult=m_codec->decode(m_buffer.data()+lengthOfBOM,m_buffer.size()-lengthOfBOM,false,m_contentType==XML&&!m_useLenientXMLDecoding,m_sawError); m_buffer.clear();//清空存储的原始未解码的HTML字节流 returnresult; } 从源码中可以看到，TextResourceDecoder 首先从 HTML 的 <head> 标签中去找编码方式，因为 <head> 标签可以包含 <meta> 标签，<meta> 标签可以设置 HTML 文件的字符集: <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <!-- 字符集指定--> <title>DOM Tree</title> <script>window.name = 'Lucy';</script> </head> 如果能找到对应的字符集，TextResourceDeocder 将其存储在成员变量 m_encoding 当中，并且根据对应的编码创建真正的解码器存储在成员变量 m_codec 中，最终使用 m_codec 对字节流进行解码，并且返回解码后的字符串。如果带有字符集的 <meta> 标签没有找到，TextResourceDeocder 的 m_encoding 有默认值 windows-1252(等同于ISO-8859-1)。 下面看一下 TextResourceDecoder 寻找 <meta> 标签中字符集的流程，也就是上面源码中第8行对 checkForHeadCharset 函数的调用: // 只保留了关健代码 bool TextResourceDecoder::checkForHeadCharset(const char* data, size_t len, bool& movedDataToBuffer) { ... // This is not completely efficient, since the function might go // through the HTML head several times. size_t oldSize = m_buffer.size(); m_buffer.grow(oldSize + len); memcpy(m_buffer.data() + oldSize, data, len); // 将字节流数据拷贝到自己的缓存m_buffer里面 movedDataToBuffer = true; // Continue with checking for an HTML meta tag if we were already doing so. if (m_charsetParser) return checkForMetaCharset(data, len); // 如果已经存在了meta标签解析器，直接开始解析 .... m_charsetParser = makeUnique<HTMLMetaCharsetParser>(); // 创建meta标签解析器 return checkForMetaCharset(data, len); } 上面源代码中第11行，类 TextResourceDecoder 内部存储了需要解码的 HTML 字节流，这一步骤很重要，后面会讲到。先看第17行、21行、22行，这3行主要是使用<meta>标签解析器解析字符集，使用了懒加载的方式。下面看下 checkForMetaCharset 这个函数的实现: bool TextResourceDecoder::checkForMetaCharset(const char* data, size_t length) { if (!m_charsetParser->checkForMetaCharset(data, length)) // 解析meta标签字符集 return false; setEncoding(m_charsetParser->encoding(), EncodingFromMetaTag); // 找到后设置字符编码名称 m_charsetParser = nullptr; m_checkedForHeadCharset = true; return true; } 上面源码第3行可以看到，整个解析 <meta> 标签的任务在类 HTMLMetaCharsetParser::checkForMetaCharset 中完成。 // 只保留了关健代码 bool HTMLMetaCharsetParser::checkForMetaCharset(const char* data, size_t length) { if (m_doneChecking) // 标志位，避免重复解析 return true; // We still don't have an encoding, and are in the head. //Thefollowingtagsareallowedin<head>: // SCRIPT|STYLE|META|LINK|OBJECT|TITLE|BASE // // We stop scanning when a tag that is not permitted in <head> // is seen, rather when </head> is seen, because that more closely // matches behavior in other browsers; more details in // <http://bugs.webkit.org/show_bug.cgi?id=3590>. // // Additionally, we ignore things that looks like tags in <title>, <script> // and <noscript>; see <http://bugs.webkit.org/show_bug.cgi?id=4560>, // <http://bugs.webkit.org/show_bug.cgi?id=12165> and // <http://bugs.webkit.org/show_bug.cgi?id=12389>. // // Since many sites have charset declarations after <body> or other tags // that are disallowed in <head>, we don't bail out until we've checked at // least bytesToCheckUnconditionally bytes of input. constexpr int bytesToCheckUnconditionally = 1024; // 如果解析了1024个字符还未找到带有字符集的<meta>标签，整个解析也算完成，此时没有解析到正确的字符集，就使用默认编码windows-1252(等同于ISO-8859-1) bool ignoredSawErrorFlag; m_input.append(m_codec->decode(data,length,false,false,ignoredSawErrorFlag));//对字节流进行解码 while (auto token = m_tokenizer.nextToken(m_input)) { // m_tokenizer进行分词操作，找meta标签也需要进行分词，分词操作后面讲 bool isEnd = token->type() == HTMLToken::EndTag; if (isEnd || token->type() == HTMLToken::StartTag) { AtomString tagName(token->name()); if (!isEnd) { m_tokenizer.updateStateFor(tagName); if (tagName == metaTag && processMeta(*token)) { // 找到meta标签进行处理 m_doneChecking = true; return true; // 如果找到了带有编码的meta标签，直接返回 } } if(tagName!=scriptTag&&tagName!=noscriptTag && tagName != styleTag && tagName != linkTag && tagName != metaTag && tagName != objectTag && tagName != titleTag && tagName != baseTag && (isEnd || tagName != htmlTag) && (isEnd || tagName != headTag)) { m_inHeadSection = false; } } if (!m_inHeadSection && m_input.numberOfCharactersConsumed() >= bytesToCheckUnconditionally) { // 如果分词已经进入了<body>标签范围，同时分词数量已经超过了1024，也算成功 m_doneChecking = true; return true; } } return false; } 上面源码第29行，类 HTMLMetaCharsetParser 也有一个解码器 m_codec，解码器是在 HTMLMetaCharsetParser 对象创建时生成，这个解码器的真实类型是 TextCodecLatin1(Latin1编码也就是ISO-8859-1，等同于windows-1252编码)。之所以可以直接使用 TextCodecLatin1 解码器，是因为 <meta> 标签如果设置正确，都是英文字符，完全可以使用 TextCodecLatin1 进行解析出来。这样就避免了为了找到 <meta> 标签，需要对字节流进行解码，而要解码就必须要找到 <meta> 标签这种鸡生蛋、蛋生鸡的问题。 代码第37行对找到的 <meta> 标签进行处理，这个函数比较简单，主要是解析 <meta> 标签当中的属性，然后查看这些属性名中有没有 charset。 bool HTMLMetaCharsetParser::processMeta(HTMLToken& token) { AttributeList attributes; for (auto& attribute : token.attributes()) { // 获取meta标签属性 String attributeName = StringImpl::create8BitIfPossible(attribute.name); String attributeValue = StringImpl::create8BitIfPossible(attribute.value); attributes.append(std::make_pair(attributeName, attributeValue)); } m_encoding = encodingFromMetaAttributes(attributes); // 从属性中找字符集设置属性charset return m_encoding.isValid(); } 上面分析 TextResourceDecoder::checkForHeadCharset 函数时，讲过第11行 TextResourceDecoder 类存储 HTML 字节流的操作很重要。原因是可能整个 HTML 字节流里面可能确实没有设置 charset 的 <meta> 标签，此时 TextResourceDecoder::checkForHeadCharset 函数就要返回 false，导致 TextResourceDecoder::decode 函数返回空字符串，也就是不进行任何解码。是不是这样呢？真实的情况是，在接收HTML字节流整个过程中由于确实没有找到带有 charset 属性的 <meta> 标签，那么整个接收期间都不会解码。但是完整的 HTML 字节流会被存储在 TextResourceDecoder 的成员变量 m_buffer 里面，当整个 HTML 字节流接收结束的时，会有如下调用栈: 从调用栈可以看到，当 HTML 字节流接收完成，最终会调用 TextResourceDecoder::flush 方法，这个方法会将 TextResourceDecoder 中有 m_buffer 存储的 HTML 字节流进行解码，由于在接收 HTML 字节流期间未成功找到编码方式，因此 m_buffer 里面存储的就是所有待解码的 HTML 字节流，然后在这里使用默认的编码 windows-1252 对全部字节流进行解码。因此，如果 HTML 字节流中包含汉字，那么如果不指定字符集，最终页面就会出现乱码。解码完成后，会将解码之后的字符流存储到 HTMLDocumentParser 中。 void DecodedDataDocumentParser::flush(DocumentWriter& writer) { String remainingData = writer.decoder().flush(); if (remainingData.isEmpty()) return; writer.reportDataReceived(); append(remainingData.releaseImpl()); // 解码后的字符流存储到HTMLDocumentParser } 2.1.3 解码总结 整个解码过程可以分为两种情形: 第一种情形是 HTML 字节流可以解析出带有 charset 属性的 <meta> 标签，这样就可以获取相应的编码方式，那么每接收到一个 HML 字节流，都可以使用相应的编码方式进行解码，将解码后的字符流添加到 HTMLInputStream 当中；第二种是 HTML 字节流不能解析带有 charset 属性的 <meta> 标签，这样每接收到一个 HTML 字节流，都缓存到 TextResourceDecoder 的 m_buffer 缓存，等完整的 HTML 字节流接收完毕，就会使用默认的编码 windows-1252 进行解码。 2.2 分词 接收到的 HTML 字节流经过解码，成为存储在 HTMLInputStream 中的字符流。分词的过程就是从 HTMLInputStream 中依次取出每一个字符，然后判断字符是否是特殊的 HTML 字符' <'、'/'、'>'、'=' 等。根据这些特殊字符的分割，就能解析出 HTML 标签名以及属性列表，类 HTMLToken 就是存储分词出来的结果。 2.2.1 分词类图 从类图中可以看到，分词最重要的是类 HTMLTokenizer 和类 HTMLToken。下面是类 HTMLToken 的主要信息: // 只保留了主要信息 classHTMLToken{ public: enumType{//Token的类型 Uninitialized,//Token初始化时的类型 DOCTYPE,//代表Token是DOCType标签 StartTag,//代表Token是一个开始标签 EndTag,//代表Token是一个结束标签 Comment,//代表Token是一个注释 Character,//代表Token是文本 EndOfFile,//代表Token是文件结尾 }; structAttribute{//存储属性的数据结构 Vector<UChar,32>name;//属性名 Vector<UChar,64>value;//属性值 //UsedbyHTMLSourceTracker. unsignedstartOffset; unsignedendOffset; }; typedefVector<Attribute,10>AttributeList;//属性列表 typedefVector<UChar,256>DataVector;//存储Token名 ... private: Typem_type; DataVectorm_data; //ForStartTagandEndTag boolm_selfClosing;//Token是注入<img>一样自结束标签 AttributeListm_attributes; Attribute*m_currentAttribute;//当前正在解析的属性 }; 2.2.2 分词流程 上面分词流程中 HTMLDocumentParser::pumpTokenizerLoop 方法是最重要的，从方法名字可以看出这个方法里面包含循环逻辑: // 只保留关健代码 bool HTMLDocumentParser::pumpTokenizerLoop(SynchronousMode mode, bool parsingFragment, PumpSession& session) { do { // 分词循环体开始 ... if (UNLIKELY(mode == AllowYield && m_parserScheduler->shouldYieldBeforeToken(session))) // 避免长时间处于分词循环中，这里根据条件暂时退出循环 return true; if (!parsingFragment) m_sourceTracker.startToken(m_input.current(), m_tokenizer); auto token = m_tokenizer.nextToken(m_input.current()); // 进行分词操作，取出一个token if (!token) return false; // 分词没有产生token，就跳出循环 if (!parsingFragment) m_sourceTracker.endToken(m_input.current(), m_tokenizer); constructTreeFromHTMLToken(token); // 根据token构建DOM树 } while (!isStopped()); return false; } 上面代码中第7行会有一个 yield 退出操作，这是为了避免长时间处于分词循环，占用主线程。当退出条件为真时，会从分词循环中返回，返回值为 true。下面是退出判断代码: // 只保留关健代码 bool HTMLParserScheduler::shouldYieldBeforeToken(PumpSession& session) { ... // numberOfTokensBeforeCheckingForYield是静态变量，定义为4096 // session.processedTokensOnLastCheck表示从上一次退出为止，以及处理过的token个数 // session.didSeeScript表示在分词过程中是否出现过script标签 if (UNLIKELY(session.processedTokens > session.processedTokensOnLastCheck + numberOfTokensBeforeCheckingForYield || session.didSeeScript)) return checkForYield(session); ++session.processedTokens; return false; } bool HTMLParserScheduler::checkForYield(PumpSession& session) { session.processedTokensOnLastCheck = session.processedTokens; session.didSeeScript = false; Seconds elapsedTime = MonotonicTime::now() - session.startTime; return elapsedTime > m_parserTimeLimit; // m_parserTimeLimit的值默认是500ms，从分词开始超过500ms就要先yield } 如果命中了上面的 yield 退出条件，那么什么时候再次进入分词呢？下面的代码展示了再次进入分词的过程: // 保留关键代码 void HTMLDocumentParser::pumpTokenizer(SynchronousMode mode) { ... if (shouldResume) // 从pumpTokenizerLoop中yield退出时返回值为true m_parserScheduler->scheduleForResume(); } void HTMLParserScheduler::scheduleForResume() { ASSERT(!m_suspended); m_continueNextChunkTimer.startOneShot(0_s); // 触发timer(0s后触发)，触发后的响应函数为HTMLParserScheduler::continueNextChunkTimerFired } // 保留关健代码 void HTMLParserScheduler::continueNextChunkTimerFired() { ... m_parser.resumeParsingAfterYield(); // 重新Resume分词过程 } void HTMLDocumentParser::resumeParsingAfterYield() { // pumpTokenizer can cause this parser to be detached from the Document, // but we need to ensure it isn't deleted yet. Ref<HTMLDocumentParser> protectedThis(*this); // We should never be here unless we can pump immediately. // Call pumpTokenizer() directly so that ASSERTS will fire if we're wrong. pumpTokenizer(AllowYield); // 重新进入分词过程，该函数会调用pumpTokenizerLoop endIfDelayed(); } 从上面代码可以看出，再次进入分词过程是通过触发一个 Timer 来实现的，虽然这个 Timer 在0s后触发，但是并不意味着 Timer 的响应函数会立刻执行。如果在此之前主线程已经有其他任务到达了执行时机，会有被执行的机会。 继续看 HTMLDocumentParser::pumpTokenizerLoop 函数的第13行，这一行进行分词操作，从解码后的字符流中分出一个 token。实现分词的代码位于 HTMLTokenizer::processToken: // 只保留关键代码 bool HTMLTokenizer::processToken(SegmentedString& source) { ... if (!m_preprocessor.peek(source, isNullCharacterSkippingState(m_state))) // 取出source内部指向的字符，赋给m_nextInputCharacter return haveBufferedCharacterToken(); UChar character = m_preprocessor.nextInputCharacter(); // 获取character // https://html.spec.whatwg.org/#tokenization switch (m_state) { // 进行状态转换，m_state初始值为DataState ... } return false; } 这个方法由于内部要做很多状态转换，总共有1200多行，后面会有4个例子来解释状态转换的逻辑。 首先来看 InputStreamPreprocessor::peek 方法: // Returns whether we succeeded in peeking at the next character. // The only way we can fail to peek is if there are no more // characters in |source| (after collapsing \r\n, etc). ALWAYS_INLINE bool InputStreamPreprocessor::peek(SegmentedString& source, bool skipNullCharacters = false) { if (UNLIKELY(source.isEmpty())) return false; m_nextInputCharacter = source.currentCharacter(); // 获取字符流source内部指向的当前字符 // Every branch in this function is expensive, so we have a // fast-reject branch for characters that don't require special // handling. Please run the parser benchmark whenever you touch // this function. It's very hot. constexpr UChar specialCharacterMask = '\n' | '\r' | '\0'; if (LIKELY(m_nextInputCharacter & ~specialCharacterMask)) { m_skipNextNewLine = false; return true; } return processNextInputCharacter(source, skipNullCharacters); // 跳过空字符，将\r\n换行符合并成\n } bool InputStreamPreprocessor::processNextInputCharacter(SegmentedString& source, bool skipNullCharacters) { ProcessAgain: ASSERT(m_nextInputCharacter == source.currentCharacter()); // 针对\r\n换行符，下面if语句处理\r字符并且设置m_skipNextNewLine=true，后面处理\n就直接忽略 if (m_nextInputCharacter == '\n' && m_skipNextNewLine) { m_skipNextNewLine = false; source.advancePastNewline(); // 向前移动字符 if (source.isEmpty()) return false; m_nextInputCharacter = source.currentCharacter(); } // 如果是\r\n连续的换行符，那么第一次遇到\r字符，将\r字符替换成\n字符，同时设置标志m_skipNextNewLine=true if (m_nextInputCharacter == '\r') { m_nextInputCharacter = '\n'; m_skipNextNewLine = true; return true; } m_skipNextNewLine = false; if (m_nextInputCharacter || isAtEndOfFile(source)) return true; // 跳过空字符 if (skipNullCharacters && !m_tokenizer.neverSkipNullCharacters()) { source.advancePastNonNewline(); if (source.isEmpty()) return false; m_nextInputCharacter = source.currentCharacter(); goto ProcessAgain; // 跳转到开头 } m_nextInputCharacter = replacementCharacter; return true; } 由于 peek 方法会跳过空字符，同时合并 \r\n 字符为 \n 字符，所以一个字符流 source 如果包含了空格或者 \r\n 换行符，实际上处理起来如下图所示: HTMLTokenizer::processToken 内部定义了一个状态机，下面以四种情形来进行解释。 Case1：标签 BEGIN_STATE(DataState) // 刚开始解析是DataState状态if (character == '&') ADVANCE_PAST_NON_NEWLINE_TO(CharacterReferenceInDataState);if (character == '<') {// 整个字符流一开始是'<'，那么表示是一个标签的开始if (haveBufferedCharacterToken()) RETURN_IN_CURRENT_STATE(true); ADVANCE_PAST_NON_NEWLINE_TO(TagOpenState); // 跳转到TagOpenState状态，并取去下一个字符是'!" }if (character == kEndOfFileMarker)return emitEndOfFile(source); bufferCharacter(character); ADVANCE_TO(DataState);END_STATE()// ADVANCE_PAST_NON_NEWLINE_TO定义#define ADVANCE_PAST_NON_NEWLINE_TO(newState) \do { \if (!m_preprocessor.advancePastNonNewline(source, isNullCharacterSkippingState(newState))) { \ // 如果往下移动取不到下一个字符 m_state = newState; \ // 保存状态return haveBufferedCharacterToken(); \ // 返回 } \ character = m_preprocessor.nextInputCharacter(); \ // 先取出下一个字符 goto newState; \ // 跳转到指定状态 } while (false)BEGIN_STATE(TagOpenState)if (character == '!') // 满足此条件 ADVANCE_PAST_NON_NEWLINE_TO(MarkupDeclarationOpenState); // 同理，跳转到MarkupDeclarationOpenState状态，并且取出下一个字符'D'if (character == '/') ADVANCE_PAST_NON_NEWLINE_TO(EndTagOpenState);if (isASCIIAlpha(character)) { m_token.beginStartTag(convertASCIIAlphaToLower(character)); ADVANCE_PAST_NON_NEWLINE_TO(TagNameState); }if (character == '?') { parseError();// The spec consumes the current character before switching// to the bogus comment state, but it's easier to implement// if we reconsume the current character. RECONSUME_IN(BogusCommentState); } parseError(); bufferASCIICharacter('<'); RECONSUME_IN(DataState);END_STATE()BEGIN_STATE(MarkupDeclarationOpenState)if (character == '-') { auto result = source.advancePast("--");if (result == SegmentedString::DidMatch) { m_token.beginComment(); SWITCH_TO(CommentStartState); }if (result == SegmentedString::NotEnoughCharacters) RETURN_IN_CURRENT_STATE(haveBufferedCharacterToken()); } else if (isASCIIAlphaCaselessEqual(character, 'd')) { // 由于character == 'D'，满足此条件 auto result = source.advancePastLettersIgnoringASCIICase("doctype"); // 看解码后的字符流中是否有完整的"doctype"if (result == SegmentedString::DidMatch) SWITCH_TO(DOCTYPEState); // 如果匹配，则跳转到DOCTYPEState，同时取出当前指向的字符，由于上面source字符流已经移动了"doctype"，因此此时取出的字符为'>'if (result == SegmentedString::NotEnoughCharacters) // 如果不匹配 RETURN_IN_CURRENT_STATE(haveBufferedCharacterToken()); // 保存状态，直接返回 } else if (character == '[' && shouldAllowCDATA()) { auto result = source.advancePast("[CDATA[");if (result == SegmentedString::DidMatch) SWITCH_TO(CDATASectionState);if (result == SegmentedString::NotEnoughCharacters) RETURN_IN_CURRENT_STATE(haveBufferedCharacterToken()); } parseError(); RECONSUME_IN(BogusCommentState);END_STATE()#define SWITCH_TO(newState) \do { \if (!m_preprocessor.peek(source, isNullCharacterSkippingState(newState))) { \ m_state = newState; \return haveBufferedCharacterToken(); \ } \ character = m_preprocessor.nextInputCharacter(); \ // 取出下一个字符 goto newState; \ // 跳转到指定的state } while (false)#define RETURN_IN_CURRENT_STATE(expression) \do { \ m_state = currentState; \ // 保存当前状态return expression; \ } while (false)BEGIN_STATE(DOCTYPEState)if (isTokenizerWhitespace(character)) ADVANCE_TO(BeforeDOCTYPENameState);if (character == kEndOfFileMarker) { parseError(); m_token.beginDOCTYPE(); m_token.setForceQuirks();return emitAndReconsumeInDataState(); } parseError(); RECONSUME_IN(BeforeDOCTYPENameState);END_STATE()#define RECONSUME_IN(newState) \do { \ // 直接跳转到指定state goto newState; \ } while (false) BEGIN_STATE(BeforeDOCTYPENameState)if (isTokenizerWhitespace(character)) ADVANCE_TO(BeforeDOCTYPENameState);if (character == '>') { // character == '>'，匹配此处，到此DOCTYPE标签匹配完毕 parseError(); m_token.beginDOCTYPE(); m_token.setForceQuirks();return emitAndResumeInDataState(source); }if (character == kEndOfFileMarker) { parseError(); m_token.beginDOCTYPE(); m_token.setForceQuirks();return emitAndReconsumeInDataState(); } m_token.beginDOCTYPE(toASCIILower(character)); ADVANCE_PAST_NON_NEWLINE_TO(DOCTYPENameState);END_STATE()inline bool HTMLTokenizer::emitAndResumeInDataState(SegmentedString& source){ saveEndTagNameIfNeeded(); m_state = DataState; // 重置状态为初始状态DataState source.advancePastNonNewline(); // 移动到下一个字符return true;} DOCTYPE Token 经历了6个状态最终被解析出来，整个过程如下图所示: 当 Token 解析完毕之后，分词状态又被重置为 DataState，同时需要注意的时，此时字符流 source 内部指向的是下一个字符 '<'。 上面代码第61行在用字符流 source 匹配字符串 "doctype" 时，可能出现匹配不上的情形。为什么会这样呢？这是因为整个 DOM 树的构建流程，并不是先要解码完成，解码完成之后获取到完整的字符流才进行分词。从前面解码可以知道，解码可能是一边接收字节流，一边进行解码的，因此分词也是这样，只要能解码出一段字符流，就会立即进行分词。整个流程会出现如下图所示: 由于这个原因，用来分词的字符流可能是不完整的。对于出现不完整情形的 DOCTYPE 分词过程如下图所示: 上面介绍了解码、分词、解码、分词处理 DOCTYPE 标签的情形，可以看到从逻辑上这种情形与完整解码再分词是一样的。后续介绍时都会只针对完整解码再分词的情形，对于一边解码一边分词的情形，只需要正确的认识 source 字符流内部指针的移动，并不难分析。 Case2：标签 <html> 标签的分词过程和 <!DOCTYPE> 类似，其相关代码如下: BEGIN_STATE(TagOpenState) if (character == '!') ADVANCE_PAST_NON_NEWLINE_TO(MarkupDeclarationOpenState); if (character == '/') ADVANCE_PAST_NON_NEWLINE_TO(EndTagOpenState); if (isASCIIAlpha(character)) { // 在开标签状态下，当前字符为'h' m_token.beginStartTag(convertASCIIAlphaToLower(character)); // 将'h'添加到Token名中 ADVANCE_PAST_NON_NEWLINE_TO(TagNameState); // 跳转到TagNameState，并移动到下一个字符't' } if (character == '?') { parseError(); // The spec consumes the current character before switching // to the bogus comment state, but it's easier to implement // if we reconsume the current character. RECONSUME_IN(BogusCommentState); } parseError(); bufferASCIICharacter('<'); RECONSUME_IN(DataState); END_STATE() BEGIN_STATE(TagNameState) if (isTokenizerWhitespace(character)) ADVANCE_TO(BeforeAttributeNameState); if (character == '/') ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState); if (character == '>') // 在这个状态下遇到起始标签终止字符 return emitAndResumeInDataState(source); // 当前分词结束，重置分词状态为DataState if (m_options.usePreHTML5ParserQuirks && character == '<') return emitAndReconsumeInDataState(); if (character == kEndOfFileMarker) { parseError(); RECONSUME_IN(DataState); } m_token.appendToName(toASCIILower(character)); // 将当前字符添加到Token名 ADVANCE_PAST_NON_NEWLINE_TO(TagNameState); // 继续跳转到当前状态，并移动到下一个字符 END_STATE() Case3：带有属性的标签 <div> HTML 标签可以带有属性，属性由属性名和属性值组成，属性之间以及属性与标签名之间用空格分隔: <!-- div标签有两个属性，属性名为class和align，它们的值都带有引号 --> <div class="news" align="center">Hello,World!</div> <!-- 属性值也可以不带引号 --> <div class=news align=center>Hello,World!</div> 整个 <div> 标签的解析中，标签名 div 的解析流程和上面的 <html> 标签解析一样，当在解析标签名的过程中，碰到了空白字符，说明要开始解析属性了，下面是相关代码: BEGIN_STATE(TagNameState)if (isTokenizerWhitespace(character)) // 在解析TagName时遇到空白字符，标志属性开始 ADVANCE_TO(BeforeAttributeNameState);if (character == '/') ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState);if (character == '>')return emitAndResumeInDataState(source);if (m_options.usePreHTML5ParserQuirks && character == '<')return emitAndReconsumeInDataState();if (character == kEndOfFileMarker) { parseError(); RECONSUME_IN(DataState); } m_token.appendToName(toASCIILower(character)); ADVANCE_PAST_NON_NEWLINE_TO(TagNameState);END_STATE()#define ADVANCE_TO(newState) \do { \if (!m_preprocessor.advance(source, isNullCharacterSkippingState(newState))) { \ // 移动到下一个字符 m_state = newState; \return haveBufferedCharacterToken(); \ } \ character = m_preprocessor.nextInputCharacter(); \ goto newState; \ // 跳转到指定状态 } while (false)BEGIN_STATE(BeforeAttributeNameState)if (isTokenizerWhitespace(character)) // 如果标签名后有连续空格，那么就不停的跳过，在当前状态不停循环 ADVANCE_TO(BeforeAttributeNameState);if (character == '/') ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState);if (character == '>')return emitAndResumeInDataState(source);if (m_options.usePreHTML5ParserQuirks && character == '<')return emitAndReconsumeInDataState();if (character == kEndOfFileMarker) { parseError(); RECONSUME_IN(DataState); }if (character == '"' || character == '\'' || character == '<' || character == '=') parseError(); m_token.beginAttribute(source.numberOfCharactersConsumed()); // Token的属性列表增加一个，用来存放新的属性名与属性值 m_token.appendToAttributeName(toASCIILower(character)); // 添加属性名 ADVANCE_PAST_NON_NEWLINE_TO(AttributeNameState); // 跳转到AttributeNameState，并且移动到下一个字符END_STATE()BEGIN_STATE(AttributeNameState)if (isTokenizerWhitespace(character)) ADVANCE_TO(AfterAttributeNameState);if (character == '/') ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState);if (character == '=') ADVANCE_PAST_NON_NEWLINE_TO(BeforeAttributeValueState); // 在解析属性名的过程中如果碰到=，说明属性名结束，属性值就要开始if (character == '>')return emitAndResumeInDataState(source);if (m_options.usePreHTML5ParserQuirks && character == '<')return emitAndReconsumeInDataState();if (character == kEndOfFileMarker) { parseError(); RECONSUME_IN(DataState); }if (character == '"' || character == '\'' || character == '<' || character == '=') parseError(); m_token.appendToAttributeName(toASCIILower(character)); ADVANCE_PAST_NON_NEWLINE_TO(AttributeNameState);END_STATE()BEGIN_STATE(BeforeAttributeValueState)if (isTokenizerWhitespace(character)) ADVANCE_TO(BeforeAttributeValueState);if (character == '"') ADVANCE_PAST_NON_NEWLINE_TO(AttributeValueDoubleQuotedState); // 有的属性值有引号包围，这里跳转到AttributeValueDoubleQuotedState，并移动到下一个字符if (character == '&') RECONSUME_IN(AttributeValueUnquotedState);if (character == '\'') ADVANCE_PAST_NON_NEWLINE_TO(AttributeValueSingleQuotedState);if (character == '>') { parseError();return emitAndResumeInDataState(source); }if (character == kEndOfFileMarker) { parseError(); RECONSUME_IN(DataState); }if (character == '<' || character == '=' || character == '`') parseError(); m_token.appendToAttributeValue(character); // 有的属性值没有引号包围，添加属性值字符到Token ADVANCE_PAST_NON_NEWLINE_TO(AttributeValueUnquotedState); // 跳转到AttributeValueUnquotedState，并移动到下一个字符END_STATE()BEGIN_STATE(AttributeValueDoubleQuotedState)if (character == '"') { // 在当前状态下如果遇到引号，说明属性值结束 m_token.endAttribute(source.numberOfCharactersConsumed()); // 结束属性解析 ADVANCE_PAST_NON_NEWLINE_TO(AfterAttributeValueQuotedState); // 跳转到AfterAttributeValueQuotedState，并移动到下一个字符 }if (character == '&') { m_additionalAllowedCharacter = '"'; ADVANCE_PAST_NON_NEWLINE_TO(CharacterReferenceInAttributeValueState); }if (character == kEndOfFileMarker) { parseError(); m_token.endAttribute(source.numberOfCharactersConsumed()); RECONSUME_IN(DataState); } m_token.appendToAttributeValue(character); // 将属性值字符添加到Token ADVANCE_TO(AttributeValueDoubleQuotedState); // 跳转到当前状态END_STATE()BEGIN_STATE(AfterAttributeValueQuotedState)if (isTokenizerWhitespace(character)) ADVANCE_TO(BeforeAttributeNameState); // 属性值解析完毕，如果后面继续跟着空白字符，说明后续还有属性要解析，调回到BeforeAttributeNameStateif (character == '/') ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState);if (character == '>')return emitAndResumeInDataState(source); // 属性值解析完毕，如果遇到'>'字符，说明整个标签也要解析完毕了，此时结束当前标签解析，并且重置分词状态为DataState，并移动到下一个字符if (m_options.usePreHTML5ParserQuirks && character == '<')return emitAndReconsumeInDataState();if (character == kEndOfFileMarker) { parseError(); RECONSUME_IN(DataState); } parseError(); RECONSUME_IN(BeforeAttributeNameState);END_STATE()BEGIN_STATE(AttributeValueUnquotedState)if (isTokenizerWhitespace(character)) { // 当解析不带引号的属性值时遇到空白字符(这与带引号的属性值不一样，带引号的属性值可以包含空白字符)，说明当前属性解析完毕，后面还有其他属性，跳转到BeforeAttributeNameState，并且移动到下一个字符 m_token.endAttribute(source.numberOfCharactersConsumed()); ADVANCE_TO(BeforeAttributeNameState); }if (character == '&') { m_additionalAllowedCharacter = '>'; ADVANCE_PAST_NON_NEWLINE_TO(CharacterReferenceInAttributeValueState); }if (character == '>') { // 解析过程中如果遇到'>'字符，说明整个标签也要解析完毕了，此时结束当前标签解析，并且重置分词状态为DataState，并移动到下一个字符 m_token.endAttribute(source.numberOfCharactersConsumed());return emitAndResumeInDataState(source); }if (character == kEndOfFileMarker) { parseError(); m_token.endAttribute(source.numberOfCharactersConsumed()); RECONSUME_IN(DataState); }if (character == '"' || character == '\'' || character == '<' || character == '=' || character == '`') parseError(); m_token.appendToAttributeValue(character); // 将遇到的属性值字符添加到Token ADVANCE_PAST_NON_NEWLINE_TO(AttributeValueUnquotedState); // 跳转到当前状态，并且移动到下一个字符END_STATE() 从代码中可以看到，当属性值带引号和不带引号时，解析的逻辑是不一样的。当属性值带有引号时，属性值里面是可以包含空白字符的。如果属性值不带引号，那么一旦碰到空白字符，说明这个属性就解析结束了，会进入下一个属性的解析当中。 Case4：纯文本解析 这里的纯文本指起始标签与结束标签之间的任何纯文字，包括脚本文、CSS 文本等等，如下所示: <!-- div标签中的纯文本 Hello,Word! --> <divclass=newsalign=center>Hello,World!</div> <!-- script标签中的纯文本 window.name = 'Lucy'; --> <script>window.name = 'Lucy';</script> 纯文本的解析过程比较简单，就是不停的在 DataState 状态上跳转，缓存遇到的字符，直到遇见一个结束标签的 '<' 字符，相关代码如下: BEGIN_STATE(DataState) if (character == '&') ADVANCE_PAST_NON_NEWLINE_TO(CharacterReferenceInDataState); if (character == '<') { // 如果在解析文本的过程中遇到开标签，分两种情况 if (haveBufferedCharacterToken()) // 第一种，如果缓存了文本字符就直接按当前DataState返回，并不移动字符，所以下次再进入分词操作时取到的字符仍为'<' RETURN_IN_CURRENT_STATE(true); ADVANCE_PAST_NON_NEWLINE_TO(TagOpenState); // 第二种，如果没有缓存任何文本字符，直接进入TagOpenState状态，进入到起始标签解析过程，并且移动下一个字符 } if (character == kEndOfFileMarker) return emitEndOfFile(source); bufferCharacter(character); // 缓存遇到的字符 ADVANCE_TO(DataState); // 循环跳转到当前DataState状态，并且移动到下一个字符 END_STATE() 由于流程比较简单，下面只给出解析div标签中纯文本的结果: 2.3 创建节点与添加节点 2.3.1 相关类图 2.3.2 创建、添加流程 上面的分词循环中，每分出一个 Token，就会根据 Token 创建对应的 Node，然后将 Node 添加到 DOM 树上(HTMLDocumentParser::pumpTokenizerLoop 方法在上面分词中有介绍)。 上面方法中首先看 HTMLTreeBuilder::constructTree，代码如下: // 只保留关健代码 void HTMLTreeBuilder::constructTree(AtomHTMLToken&& token) { ... if (shouldProcessTokenInForeignContent(token)) processTokenInForeignContent(WTFMove(token)); else processToken(WTFMove(token)); // HTMLToken在这里被处理 ... m_tree.executeQueuedTasks(); // HTMLContructionSiteTask在这里被执行，有时候也直接在创建的过程中直接执行，然后这个方法发现队列为空就会直接返回 // The tree builder might have been destroyed as an indirect result of executing the queued tasks. } void HTMLConstructionSite::executeQueuedTasks() { if (m_taskQueue.isEmpty()) // 队列为空，就直接返回 return; // Copy the task queue into a local variable in case executeTask // re-enters the parser. TaskQueue queue = WTFMove(m_taskQueue); for (auto& task : queue) // 这里的task就是HTMLContructionSiteTask executeTask(task); // 执行task // We might be detached now. } 上面代码中 HTMLTreeBuilder::processToken 就是处理 Token 生成对应 Node 的地方，代码如下所示: void HTMLTreeBuilder::processToken(AtomHTMLToken&& token) { switch (token.type()) { case HTMLToken::Uninitialized: ASSERT_NOT_REACHED(); break; case HTMLToken::DOCTYPE: // HTML中的DOCType标签 m_shouldSkipLeadingNewline = false; processDoctypeToken(WTFMove(token)); break; case HTMLToken::StartTag: // 起始HTML标签 m_shouldSkipLeadingNewline = false; processStartTag(WTFMove(token)); break; case HTMLToken::EndTag: // 结束HTML标签 m_shouldSkipLeadingNewline = false; processEndTag(WTFMove(token)); break; case HTMLToken::Comment: // HTML中的注释 m_shouldSkipLeadingNewline = false; processComment(WTFMove(token)); return; case HTMLToken::Character: // HTML中的纯文本 processCharacter(WTFMove(token)); break; case HTMLToken::EndOfFile: // HTML结束标志 m_shouldSkipLeadingNewline = false; processEndOfFile(WTFMove(token)); break; } } 可以看到上面代码对7类 Token 做了处理，由于处理的流程都是类似的，这里分析5个节点case的创建添加过程，分别是<!DOCTYPE> 标签，<html>起始标签，<title> 起始标签，<title> 文本，<title> 结束标签，剩下的过程都使用图表示。 Case1：!DOCTYPE 标签 // 只保留关健代码 void HTMLTreeBuilder::processDoctypeToken(AtomHTMLToken&& token) { ASSERT(token.type() == HTMLToken::DOCTYPE); if (m_insertionMode == InsertionMode::Initial) { // m_insertionMode的初始值就是InsertionMode::Initial m_tree.insertDoctype(WTFMove(token)); // 插入DOCTYPE标签 m_insertionMode = InsertionMode::BeforeHTML; // 插入DOCTYPE标签之后，m_insertionMode设置为InsertionMode::BeforeHTML，表示下面要开是HTML标签插入 return; } ... } // 只保留关健代码 void HTMLConstructionSite::insertDoctype(AtomHTMLToken&& token) { ... // m_attachmentRoot就是Document对象，文档根节点 // DocumentType::create方法创建出DOCTYPE节点 // attachLater方法内部创建出HTMLContructionSiteTask attachLater(m_attachmentRoot, DocumentType::create(m_document, token.name(), publicId, systemId)); ... } // 只保留关健代码 void HTMLConstructionSite::attachLater(ContainerNode& parent, Ref<Node>&& child, bool selfClosing) { ... HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Insert); // 创建HTMLConstructionSiteTask task.parent = &parent; // task持有当前节点的父节点 task.child = WTFMove(child); // task持有需要操作的节点 task.selfClosing = selfClosing; // 是否自关闭节点 // Add as a sibling of the parent if we have reached the maximum depth allowed. // m_openElements就是HTMLElementStack，在这里还看不到它的作用，后面会讲。这里可以看到这个stack里面加入的对象个数是有限制的，最大不超过512个。 // 所以如果一个HTML标签嵌套过多的子标签，就会触发这里的操作 if (m_openElements.stackDepth() > m_maximumDOMTreeDepth && task.parent->parentNode()) task.parent = task.parent->parentNode(); // 满足条件，就会将当前节点添加到爷爷节点，而不是父节点 ASSERT(task.parent); m_taskQueue.append(WTFMove(task)); // 将task添加到Queue当中 } 从代码可以看到，这里只是创建了 DOCTYPE 节点，还没有真正添加。真正执行添加的操作，需要执行 HTMLContructionSite::executeQueuedTasks，这个方法在一开始有列出来。下面就来看下每个 Task 如何被执行。 // 方法位于HTMLContructionSite.cpp static inline void executeTask(HTMLConstructionSiteTask& task) { switch (task.operation) { // HTMLConstructionSiteTask存储了自己要做的操作，构建DOM树一般都是Insert操作 case HTMLConstructionSiteTask::Insert: executeInsertTask(task); // 这里执行insert操作 return; // All the cases below this point are only used by the adoption agency. case HTMLConstructionSiteTask::InsertAlreadyParsedChild: executeInsertAlreadyParsedChildTask(task); return; case HTMLConstructionSiteTask::Reparent: executeReparentTask(task); return; case HTMLConstructionSiteTask::TakeAllChildrenAndReparent: executeTakeAllChildrenAndReparentTask(task); return; } ASSERT_NOT_REACHED(); } // 只保留关健代码，方法位于HTMLContructionSite.cpp static inline void executeInsertTask(HTMLConstructionSiteTask& task) { ASSERT(task.operation == HTMLConstructionSiteTask::Insert); insert(task); // 继续调用插入方法 ... } // 只保留关健代码，方法位于HTMLContructionSite.cpp static inline void insert(HTMLConstructionSiteTask& task) { ... ASSERT(!task.child->parentNode()); if (task.nextChild) task.parent->parserInsertBefore(*task.child, *task.nextChild); else task.parent->parserAppendChild(*task.child); // 调用父节点方法继续插入 } // 只保留关健代码 void ContainerNode::parserAppendChild(Node& newChild) { ... executeNodeInsertionWithScriptAssertion(*this, newChild, ChildChange::Source::Parser, ReplacedAllChildren::No, [&] { if (&document() != &newChild.document()) document().adoptNode(newChild); appendChildCommon(newChild); // 在Block回调中调用此方法继续插入 ... }); } // 最终调用的是这个方法进行插入 void ContainerNode::appendChildCommon(Node& child) { ScriptDisallowedScope::InMainThread scriptDisallowedScope; child.setParentNode(this); if (m_lastChild) { // 父节点已经插入子节点，运行在这里 child.setPreviousSibling(m_lastChild); m_lastChild->setNextSibling(&child); } else m_firstChild = &child; // 如果父节点是首次插入子节点，运行在这里 m_lastChild = &child; // 更新m_lastChild } 经过执行上面方法之后，原来只有一个根节点的 DOM 树变成了下面的样子: Case2：html 起始标签 // processStartTag内部有很多状态处理，这里只保留关健代码 void HTMLTreeBuilder::processStartTag(AtomHTMLToken&& token) { ASSERT(token.type() == HTMLToken::StartTag); switch (m_insertionMode) { case InsertionMode::Initial: defaultForInitial(); ASSERT(m_insertionMode == InsertionMode::BeforeHTML); FALLTHROUGH; case InsertionMode::BeforeHTML: if (token.name() == htmlTag) { // html标签在这里处理 m_tree.insertHTMLHtmlStartTagBeforeHTML(WTFMove(token)); m_insertionMode = InsertionMode::BeforeHead; // 插入完html标签，m_insertionMode = InsertionMode::BeforeHead，表明即将处理head标签 return; } ... } } // 只保留关健代码 void HTMLConstructionSite::insertHTMLHtmlStartTagBeforeHTML(AtomHTMLToken&& token) { auto element = HTMLHtmlElement::create(m_document); // 创建html节点 setAttributes(element, token, m_parserContentPolicy); attachLater(m_attachmentRoot, element.copyRef()); // 同样调用了attachLater方法，与DOCTYPE类似 m_openElements.pushHTMLHtmlElement(HTMLStackItem::create(element.copyRef(), WTFMove(token))); // 注意这里，这里向HTMLElementStack中压入了正在插入的html起始标签 executeQueuedTasks(); // 这里在插入操作直接执行了task，外面HTMLTreeBuilder::constructTree方法调用的executeQueuedTasks方法就会直接返回 ... } 执行上面代码之后，DOM 树变成了如下图所示: Case3：title 起始标签 当插入 <title> 起始标签之后，DOM 树以及 HTMLElementStack m_openElements 如下图所示: Case4：title 标签文本 <title> 标签的文本作为文本节点插入，生成文本节点的代码如下: // 只保留关健代码 void HTMLConstructionSite::insertTextNode(const String& characters, WhitespaceMode whitespaceMode) { HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Insert); task.parent = &currentNode(); // 直接取HTMLElementStack m_openElements的栈顶节点，此时节点是title unsigned currentPosition = 0; unsigned lengthLimit = shouldUseLengthLimit(*task.parent) ? Text::defaultLengthLimit : std::numeric_limits<unsigned>::max(); // 限制文本节点最大包含的字符个数为65536 // 可以看到如果文本过长，会将分割成多个文本节点 while (currentPosition < characters.length()) { AtomString charactersAtom = m_whitespaceCache.lookup(characters, whitespaceMode); auto textNode = Text::createWithLengthLimit(task.parent->document(), charactersAtom.isNull() ? characters : charactersAtom.string(), currentPosition, lengthLimit); // If we have a whole string of unbreakable characters the above could lead to an infinite loop. Exceeding the length limit is the lesser evil. if (!textNode->length()) { String substring = characters.substring(currentPosition); AtomString substringAtom = m_whitespaceCache.lookup(substring, whitespaceMode); textNode = Text::create(task.parent->document(), substringAtom.isNull() ? substring : substringAtom.string()); // 生成文本节点 } currentPosition += textNode->length(); // 下一个文本节点包含的字符起点 ASSERT(currentPosition <= characters.length()); task.child = WTFMove(textNode); executeTask(task); // 直接执行Task插入 } } 从代码可以看到，如果一个节点后面跟的文本字符过多，会被分割成多个文本节点插入。下面的例子将 <title> 节点后面的文本字符个数设置成85248，使用 Safari 查看确实生成了2个文本节点: ![图片](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/584362db5ed04e2fb9d761f8d6f2d83c~tplv-k3u1fbpfcp-zoom-1.image) **Case5：结束标签** 当遇到 <title> 结束标签，代码处理如下: // 代码内部有很多状态处理，这里只保留关健代码 void HTMLTreeBuilder::processEndTag(AtomHTMLToken&& token) { ASSERT(token.type() == HTMLToken::EndTag); switch (m_insertionMode) { ... case InsertionMode::Text: // 由于遇到title结束标签之前插入了文本，因此此时的插入模式就是InsertionMode::Text m_tree.openElements().pop(); // 因为遇到了title结束标签，整个标签已经处理完毕，从HTMLElementStack栈中弹出栈顶元素title m_insertionMode = m_originalInsertionMode; // 恢复之前的插入模式 break; } 每当遇到一个标签的结束标签，都会像上面一样将 HTMLElementStack m_openElementsStack 的栈顶元素弹出。执行上面代码之后，DOM 树与 HTMLElementStack 如下图所示: 三、内存中的DOM树 当整个 DOM 树构建完成之后，DOM 树和 HTMLElementStack m_openElements 如下图所示: 从上图可以看到，当构建完 DOM，HTMLElementStack m_openElements 并没有将栈完全清空，而是保留了2个节点: html 节点与 body 节点。这可以从 Xcode 的控制台输出看到: 同时可以看到，内存中的 DOM 树结构和文章开头画的逻辑上的 DOM 树结构是不一样的。逻辑上的 DOM 树父节点有多少子节点，就有多少指向子节点的指针，而内存中的 DOM 树，不管父节点有多少子节点，始终只有2个指针指向子节点: m_firstChild 与 m_lastChild。同时，内存中的 DOM 树兄弟节点之间也相互有指针引用，而逻辑上的 DOM 树结构是没有的。 举个例子，如果一棵 DOM 树只有1个父节点，100个子节点，那么使用逻辑上的 DOM 树结构，父节点就需要100个指向子节点的指针。如果一个指针占8字节，那么总共占用800字节。使用上面内存中 DOM 树的表示方式，父节点需要2个指向子节点的指针，同时兄弟节点之间需要198个指针，一共200个指针，总共占用1600字节。相比逻辑上的 DOM 树结构，内存上并不占优势，但是内存中的 DOM 树结构，无论父节点有多少子节点，只需要2个指针就可以了，不需要添加子节点时，频繁动态申请内存，创建新的指向子节点的指针。 ---------- END ---------- 百度 Geek 说 百度官方技术公众号上线啦！ 技术干货 · 行业资讯 · 线上沙龙 · 行业大会 招聘信息 · 内推信息 · 技术书籍 · 百度周边
2022-03-22
优秀的个人博客,低调大师

【Kafka核心原理解析】之调优策略解析

上一篇文章中，我们为大家讲解了Kafka的分区分配策略，StickyAssignor分配策略、RoundRobinAssignor分配策略、RangeAssignor分配策略，详细内容参加 Kafka分区分配策略详解，本片文章，我们来看看Kafka的调优策略都有哪些。 ⼀般说到调优都离不开监控，kafka本身没有提供很好的图形化监控系统，但是有很多第三⽅的kafka监控⼯具都做的相对不错： Burrow Kafka Monitor Kafka Offset Monitor Kafka Eagle 在平时的开发中，开发者使⽤kafka来发送数据已经⾮常熟悉，但是在使⽤的过程中，很多开发者并没有深⼊的探索kafka使⽤过程中的参数配置，带来的损失就是没有充分的发挥出kfka的优势，⽆法很好的满⾜业务场景。 生产者配置与说明 Properties props = new Properties(); props.put("bootstrap.servers", "localhost:9092"); props.put("key.serializer", "org.apache.kafka.common.serialization.StringSerializer"); props.put("value.serializer", "org.apache.kafka.common.serialization.StringSerializer"); props.put("buffer.memory", 67108864); props.put("batch.size", 131072); props.put("linger.ms", 100); props.put("max.request.size", 10485760); props.put("acks", "1"); props.put("retries", 10); props.put("retry.backoff.ms", 500); KafkaProducer<String, String> producer = new KafkaProducer<String, String> (props); buffer.memory Kafka的客户端发送数据到服务器，⼀般要经过缓冲，当你通过KafkaProducer发送出去的消息是先进⼊到客户端本地的内存缓冲⾥，然后把很多消息收集成⼀个⼀个的Batch，再发送到Broker上去的。所以这个“buffer.memory”的本质就是⽤来约束KafkaProducer能够使⽤的内存缓冲的⼤⼩的，它的默认值是32MB。既然了解了这个含义，试想⼀下，在⽣产项⽬⾥，这个参数应该怎么来设置呢？ 可以先想⼀下，如果这个内存缓冲设置的过⼩的话，可能会导致⼀个什么问题？⾸先要明确⼀点，在内存缓冲⾥⼤量的消息会缓冲在⾥⾯，形成⼀个⼀个的Batch，每个Batch⾥包含多条消息。然后KafkaProducer的Sender线程会把多个Batch打包成⼀个Request发送到Kafka服务器上去。 如果要是内存设置的太⼩，可能导致⼀个问题，消息快速的写⼊内存缓冲⾥⾯，但是Sender线程来不及把Request发送到Kafka服务器。这样是不是会造成内存缓冲很快就被写满？⼀旦被写满，就会阻塞⽤户线程，不让继续往Kafka写消息了。所以对于“buffer.memory”这个参数应该结合⾃⼰的实际情况来进⾏压测，需要测算⼀下在⽣产环境，你的⽤户线程会以每秒多少消息的频率来写⼊内存缓冲。假如说每秒300条消息，那么你就需要压测⼀下，假设内存缓冲就32MB，每秒写300条消息到内存缓冲，是否会经常把内存缓冲写满？经过这样的压测，你可以调试出来⼀个合理的内存⼤⼩。 batch.size batch.size是Batch数据量⼤⼩，默认值是16KB，⼀般可以尝试把这个参数调节⼤⼀些，可以利⽤⾃⼰的⽣产环境发消息的负载来测试⼀ 下。⽐如说发送消息的频率就是每秒300条，那么如果“batch.size”调节到了32KB，或者64KB，是否可以提升发送消息的整体吞吐量。理论上来说，提升batch的⼤⼩，可以允许更多的数据缓冲在⾥⾯， 那么⼀次Request发送出去的数据量就更多了，这样吞吐量可能会有所提升。但是也不能⽆限⼤，过于⼤了之后，数据缓冲在Batch⾥发送出去，那么岂发送消息的延迟就会很⾼。 举个例子，⼀条消息进⼊了Batch，但是要等待5秒钟Batch才凑满了64KB，然后才发送出去。那这条消息的延迟就是5秒钟。所以需要在这⾥按照⽣产环境的发消息的速率，调节不同的Batch⼤⼩⾃⼰测⼀下最终出去的吞吐量以及消息的延迟，设置⼀个最合理的参数。 linger.ms 要是⼀个Batch迟迟⽆法凑满，此时就需要引⼊另外⼀个参数了“linger.ms”。它的含义是，Batch被创建之后，最多过多久，不管这个Batch有没有写满，都必须发送出去了。 举个例⼦，一个batch.size是16kb，现在某个低峰时间段，发送消息很慢。这就导致可能Batch被创建之后，陆陆续续有消息进来，但是迟迟⽆法凑够16KB，难道此时就⼀直等着吗？如果你现在设置“linger.ms”是50ms，那么只要这个Batch从创建开始到现在已经过了50ms了，哪怕它还没满16KB，也要发送出去了。所以“linger.ms”决定了你的消息⼀旦写⼊⼀个Batch，最多等待这么多时间，他⼀定会跟着Batch⼀起发送出去。避免⼀个Batch迟迟凑不满，导致消息⼀直积压 在内存⾥发送不出去的情况。 要配合batch.size⼀起来设置。举个例⼦，⾸先假设一个Batch是32KB，我们需要估算下，正常情况下，⼀般多久会凑够⼀个Batch，⽐如可能20ms就会凑够⼀个Batch。那么linger.ms就可以设置为25ms，也就是说，⼤部分的Batch在20ms内都会凑满，但是你的linger.ms可以保 证，哪怕遇到低峰时期，20ms凑不满⼀个Batch，还是会在25ms之后强制Batch发送出去。 如果要是你 把linger.ms设置的太⼩了，⽐如默认就是0ms，或者你设置个5ms，那可能导致你的Batch虽然设置了32KB，但是经常是还没凑够32KB的数据，5ms之后就直接强制Batch发送出去，这样会导致你的Batch形同虚设，⼀直凑不满数据。 max.request.size 最⼤请求大小 ：max.request.size，这个参数决定了每次发送给Kafka服务器请求的最⼤数值，同时也会限制你⼀条消息的最⼤也不能超过这个参数设置的值，你可以根据⾃⼰的消息的⼤⼩来灵活的调整。举个例⼦，发送的消息都是⼤的报⽂消息，每条消息都是很多的数据，⼀条消息可能都要20KB。此时你的batch.size是不是就需要调节⼤⼀些？ ⽐如设置个512KB？然后你的buffer.memory是不是要给的⼤⼀些？设置128MB？只有这样，才能让你在⼤消息的场景下，还能使⽤Batch打包多条消息的机制。此时 “max.request.size”可以适当调⼤⼀些，⽐如调节到5MB。 retries与retries.backoff.ms “retries”和“retries.backoff.ms”决定了重试机制，也就是如果⼀个请求失败了可以重试⼏次，每次重试 的间隔是多少毫秒。 确认机制：acks 此配置是表明当⼀次produce请求被认为完成时的确认值。特别是，多少个其他brokers必须已经提交了 数据到他们的log并且向它们的leader确认了这些信息。典型的值包括： 0： 表示producer从来不等待来⾃broker的确认信息，这个选择提供了最⼩的时延但同时⻛险最⼤（因 为当server宕机时，数据将会丢失）。 1：表示获得leader replica已经接收了数据的确认信息。这个选择时延较⼩同时确保了server确认接收 成功。 -1：producer会获得所有同步replicas都收到数据的确认。同时时延最⼤，然⽽，这种⽅式并没有完全 消除丢失消息的⻛险，因为同步replicas的数量可能是1。如果你想确保某些replicas接收到数据，那么你 应该在topic-level设置中选项min.insync.replicas设置⼀下。 min.insync.replicas 当⽣产者设置应答为"all"(或“-1”)时，此配置指定了成功写⼊的副本应答的最⼩数。如果没满⾜此最⼩数，则⽣产者将引发异常(NotEnoughReplicas或NotEnoughReplicasAfterAppend) min.insync.replicas和acks强制更⼤的耐⽤性时。典型的情况是创建⼀个副本为3的topic，将min.insync.replicas设置为2，并设置acks为“all”。如果多数副本没有收到写⼊，这将确保⽣产者引发异常。 消费者端配置和说明 fetch.min.bytes: 每次fetch请求时，server应该返回的最⼩字节数。如果没有⾜够的数据返回，请求会等待，直到⾜够的 数据才会返回。 auto.commit.enable 如果为真，consumer所fetch的消息的offset将会⾃动的同步到broker。这项提交的offset将在进程挂掉 时，由新的consumer使⽤。 更多福利 云智慧已开源集轻量级、聚合型、智能运维为一体的综合运维管理平台OMP（Operation Management Platform） ，具备 纳管、部署、监控、巡检、自愈、备份、恢复 等功能，可为用户提供便捷的运维能力和业务管理，在提高运维人员等工作效率的同时，极大提升了业务的连续性和安全性。点击下方地址链接，欢迎大家给OMP点赞送star，了解更多相关内容～ GitHub地址：https://github.com/CloudWise-OpenSource/OMP Gitee地址：https://gitee.com/CloudWise/OMP 微信扫描识别下方二维码，备注【OMP】加入AIOps社区运维管理平台OMP开发者交流群，与OMP项目PMC当面交流，和更多行业大佬一起交流学习～
2022-01-24
优秀的个人博客,低调大师

每日一博 | 深入理解 Ribbon 的架构原理

大家好，我是悟空。 本篇主要内容如下： 前言 今天我们来看下微服务中非常重要的一个组件：Ribbon。它作为负载均衡器在分布式网络中扮演着非常重要的角色。 在介绍 Ribbon 之前，不得不说下负载均衡这个比较偏僻的名词。为什么说它偏僻了，因为在面试中，聊得最多的是消息队列和缓存来提高系统的性能，支持高并发，很少有人会问负载均衡，究其原因，负载均衡的组件选择和搭建一般都是运维团队或者架构师去做的，开发人员确实很少接触到。不过没关系，我们不止有 CRUD，还要有架构思维。 简单来说，负载均衡就是将网络流量（负载）分摊到不同的网络服务器（可以平均分配，也可以不平均），系统就可以实现服务的水平横向扩展。 那么如果让你设计一个负载均衡组件，你会怎么设计？ 我们需要考虑这几个因素： 如何获取及同步服务器列表？涉及到与注册中心的交互。 如何将负载进行分摊？涉及到分摊策略。 如何将客户端请求进行拦截然后选择服务器进行转发？涉及到请求拦截。 抱着这几个问题，我们从负载均衡的原理 + Ribbon 的架构来学习如何设计一个负载均衡器，相信会带给你一些启发。 一、负载均衡 1.1 概念 上次我在这篇文章中详细讲解了何为高可用，里面没有涉及到负载均衡机制，其实负载均衡也是高可用网络的关键组件。 两个基本点： 选择哪个服务器来处理客户端请求。 将客户端请求转发出去。 一个核心原理：通过硬件或软件的方式维护一个服务列表清单。当用户发送请求时，会将请求发送给负载均衡器，然后根据负载均衡算法从可用的服务列表中选出一台服务器的地址，将请求进行转发，完成负载功能。 1.2 负载均衡的特性 高性能：可根据不同的分配规则自动将流量进行分摊。 可扩展性：可以很方便增加集群中设备或链路的数量。 高可靠性：系统中某个设备或链路发生故障，不会导致服务中断。 易配置性：配置和维护方便。 透明性：用户感知不到如何进行负载均衡的，也不用关心负载均衡。 1.3 负载均衡分类 负载均衡技术可以按照软件或硬件进行分类，也可以按照服务器列表存放的位置划分为服务端负载和客户端负载均衡。 1.3.1 硬件负载均衡 F5 就是常见的硬件负载均衡产品。 优点：性能稳定，具备很多软件负载均衡不具备的功能，如应用交换，会话交换、状态监控等。 缺点：设备价格昂贵、配置冗余，没有软件负载均衡灵活，不能满足定制化需求。 1.3.2 软件负载均衡 Nginx：性能好，可以负载超过 1W。工作在网络的7层之上，可以针对http应用做一些分流的策略。Nginx也可作为静态网页和图片服务器。Nginx仅能支持http、https和Email协议。 LVS（Linux Virtual Server）：是一个虚拟服务器集群系统，采用 IP 地址均衡技术和内容请求分发技术实现负载均衡。接近硬件设备的网络吞吐和连接负载能力。抗负载能力强、是工作在网络4层之上仅作分发之用。自身有完整的双机热备方案，如LVS+Keepalived。软件本身不支持正则表达式处理，不能做动静分离。 1.3.3 服务端负载均衡 Nginx 和 F5 都可以划分到服务端的负载均衡里面，后端的服务器地址列表是存储在后端服务器中或者存在专门的 Nginx 服务器或 F5 上。 服务器的地址列表的来源是通过注册中心或者手动配置的方式来的。 1.3.4 客户端负载均衡 终于轮到 Ribbon 登场了，它属于客户端负载均衡器，客户端自己维护一份服务器的地址列表。这个维护的工作就是由 Ribbon 来干的。 Ribbon 会从 Eureka Server 读取服务信息列表，存储在 Ribbon 中。如果服务器宕机了，Ribbon 会从列表剔除宕机的服务器信息。 Ribbon 有多种负载均衡算法，我们可以自行设定规则从而请求到指定的服务器。 二、 均衡策略 上面已经介绍了各种负载均衡分类，接下来我们来看下这些负载均衡器如何通过负载均衡策略来选择服务器处理客户端请求。 常见的均衡策略如下。 2.1 轮循均衡（Round Robin） 原理：如果给服务器从 0 到 N 编号，轮询均衡策略会从 0 开始依次选择一个服务器作为处理本次请求的服务器。- 场景：适合所有父亲都有相同的软硬件配置，且请求频率相对平衡。 2.2 权重轮询均衡（Weighted Round Robin） 原理：按照服务器的不同处理能力，给服务器分配不同的权重，然后请求会按照权重分配给不同的服务器。 场景：服务器的性能不同，充分利用高性能的服务器，同时也能照顾到低性能的服务器。 2.3 随机均衡（Random） 原理：将请求随机分配给不同的服务器。 场景：适合客户端请求的频率比较随机的场景。 2.4 响应速度均衡（Response Time) 原理：负载均衡设备对每个服务器发送一个探测请求，看看哪台服务器的响应速度更快， 场景：适合服务器的响应性能不断变化的场景。 注意：响应速度是针对负载均衡设备和服务器之间的。 三、Ribbon 核心组件 接下来就是我们的重头戏了，来看下 Ribbon 这个 Spring Cloud 中负载均衡组件。 Ribbon 主要有五大功能组件：ServerList、Rule、Ping、ServerListFilter、ServerListUpdater。 3.1 负载均衡器 LoadBalancer 用于管理负载均衡的组件。初始化的时候通过加载 YMAL 配置文件创建出来的。 3.2 服务列表 ServerList ServerList 主要用来获取所有服务的地址信息，并存到本地。 根据获取服务信息的方式不同，又分为静态存储和动态存储。 静态存储：从配置文件中获取服务节点列表并存储到本地。 动态存储：从注册中心获取服务节点列表并存储到本地 3.3 服务列表过滤 ServerListFilter 将获取到的服务列表按照过滤规则过滤。 通过 Eureka 的分区规则对服务实例进行过滤。 比较服务实例的通信失败数和并发连接数来剔除不够健康的实例。 根据所属区域过滤出同区域的服务实例。 3.4 服务列表更新 ServerListUpdater 服务列表更新就是 Ribbon 会从注册中心获取最新的注册表信息。是由这个接口 ServerListUpdater 定义的更新操作。而它有两个实现类，也就是有两种更新方式： 通过定时任务进行更新。由这个实现类 PollingServerListUpdater 做到的。 利用 Eureka 的事件监听器来更新。由这个实现类 EurekaNotificationServerListUpdater 做到的。 3.5 心跳检测 Ping IPing 接口类用来检测哪些服务可用。如果不可用了，就剔除这些服务。 实现类主要有这几个：PingUrl、PingConstant、NoOpPing、DummyPing、NIWSDiscoveryPing。 心跳检测策略对象 IPingStrategy，默认实现是轮询检测。 3.6 负载均衡策略 Rule Ribbon 的负载均衡策略和之前讲过的负载均衡策略有部分相同，先来个全面的图，看下 Ribbon 有哪几种负载均衡策略。 再来看下 Ribbon 源码中关于均衡策略的 UML 类图。 由图可以看到，主要由以下几种均衡策略： 线性轮询均衡 （RoundRobinRule）：轮流依次请求不同的服务器。优点是无需记录当前所有连接的状态，无状态调度。 可用服务过滤负载均衡（AvailabilityFilteringRule）：过滤多次访问故障而处于断路器状态的服务，还有过滤并发连接数量超过阈值的服务，然后对剩余的服务列表按照轮询策略进行访问。默认情况下，如果最近三次连接均失败，则认为该服务实例断路。然后保持 30s 后进入回路关闭状态，如果此时仍然连接失败，那么等待进入关闭状态的时间会随着失败次数的增加呈指数级增长。 加权响应时间负载均衡（WeightedResponseTimeRule）：为每个服务按响应时长自动分配权重，响应时间越长，权重越低，被选中的概率越低。 区域感知负载均衡（ZoneAvoidanceRule）：更倾向于选择发出调用的服务所在的托管区域内的服务，降低延迟，节省成本。Spring Cloud Ribbon 中默认的策略。 重试负载均衡（RetryRule)：通过轮询均衡策略选择一个服务器，如果请求失败或响应超时，可以选择重试当前服务节点，也可以选择其他节点。 高可用（Best Available)：忽略请求失败的服务器，尽量找并发比较低的服务器。注意：这种会给服务器集群带来成倍的压力。 随机负载均衡（RandomRule）：随机选择服务器。适合并发比较大的场景。 四、 Ribbon 拦截请求的原理 本文最开始提出了一个问题：负载均衡器如何将客户端请求进行拦截然后选择服务器进行转发？ 结合上面介绍的 Ribbon 核心组件，我们可以画一张原理图来梳理下 Ribbon 拦截请求的原理： 第一步：Ribbon 拦截所有标注@loadBalance注解的 RestTemplate。RestTemplate 是用来发送 HTTP 请求的。 第二步：将 Ribbon 默认的拦截器 LoadBalancerInterceptor 添加到 RestTemplate 的执行逻辑中，当 RestTemplate 每次发送 HTTP 请求时，都会被 Ribbon 拦截。 第三步：拦截后，Ribbon 会创建一个 ILoadBalancer 实例。 第四步：ILoadBalancer 实例会使用 RibbonClientConfiguration 完成自动配置。就会配置好 IRule，IPing，ServerList。 第五步：Ribbon 会从服务列表中选择一个服务，将请求转发给这个服务。 五、Ribbon 初始化的原理 当我们去剖析 Ribbon 源码的时候，需要找到一个突破口，而 @LoadBalanced 注解就是一个比较好的入口。 先来一张 Ribbon 初始化的流程图： 添加注解的代码如下所示： @LoadBalanced @Bean public RestTemplate getRestTemplate() { return new RestTemplate(); } 第一步：Ribbon 有一个自动配置类 LoadBalancerAutoConfiguration，SpringBoot 加载自动配置类，就会去初始化 Ribbon。 第二步：当我们给 RestTemplate 或者 AsyncRestTemplate 添加注解后，Ribbon 初始化时会收集加了 @LoadBalanced 注解的 RestTemplate 和 AsyncRestTemplate ，把它们放到一个 List 里面。 第三步：然后 Ribbon 里面的 RestTemplateCustomizer 会给每个 RestTemplate 进行定制化，也就是加上了拦截器：LoadBalancerInterceptor。 第四步：从 Eureka 注册中心获取服务列表，然后存到 Ribbon 中。 第五步：加载 YMAL 配置文件，配置好负载均衡配置，创建一个 ILoadbalancer 实例。 六、Ribbon 同步服务列表原理 Ribbon 首次从 Eureka 获取全量注册表后，就会隔一定时间获取注册表。原理图如下： 之前我们提到过 Ribbon 的核心组件 ServerListUpdater，用来同步注册表的，它有一个实现类 PollingServerListUpdater ，专门用来做定时同步的。默认1s 后执行一个 Runnable 线程，后面就是每隔 30s 执行 Runnable 线程。这个 Runnable 线程就是去获取 Eureka 注册表的。 七、Eureka 心跳检测的原理 我们知道 Eureka 注册中心是通过心跳检测机制来判断服务是否可用的，如果不可用，可能会把这个服务摘除。为什么是可能呢？因为 Eureka 有自我保护机制，如果达到自我保护机制的阀值，后续就不会自动摘除。 这里我们可以再复习下 Eureka 的自我保护机制和服务摘除机制。 Eureka 心跳机制：每个服务每隔 30s 自动向 Eureka Server 发送一次心跳，Eureka Server 更新这个服务的最后心跳时间。如果 180 s 内（版本1.7.2 bug ）未收到心跳，则任务服务故障了。 Eureka 自我保护机制：如果上一分钟实际的心跳次数，比我们期望的心跳次数要小，就会触发自我保护机制，不会摘除任何实例。期望的心跳次数：服务实例数量 * 2 * 0.85。 Eureka 服务摘除机制：不是一次性将服务实例摘除，每次最多随机摘除 15%。如果摘除不完，1 分钟之后再摘除。 说完 Eureka 的心跳机制和服务摘除机制后，我们来看下 Ribbon 的心跳机制。 八、Ribbon 心跳检测的原理 Ribbon 的心跳检测原理和 Eureka 还不一样，Ribbon 不是通过每个服务向 Ribbon 发送心跳或者 Ribbon 给每个服务发送心跳来检测服务是否存活的。 先来一张图看下 Ribbon 的心跳检测机制： Ribbon 心跳检测原理：对自己本地缓存的 Server List 进行遍历，看下每个服务的状态是不是 UP 的。具体的代码就是 isAlive 方法。 核心代码： isAlive = status.equals(InstanceStatus.UP); 那么多久检测一次呢？ 默认每隔 30s 执行以下 PingTask 调度任务，对每个服务执行 isAlive 方法，判断下状态。 九、Ribbon 常用配置项 9.1 禁用 Eureka # 禁用 Eureka ribbon.eureka.enabled=false 服务注册列表默认是从 Eureka 获取到的，如果不想使用 Eureka，可以禁用掉。然后我们需要手动配置服务列表。 9.2 配置服务列表 ribbon-config-passjava.ribbon.listOfServers=localhost:8081,localhost:8083 这个配置是针对具体服务的，前缀就是服务名称，配置完之后就可以和之前一样使用服务名称来调用接口了。 9.3 其他配置项 十、总结 本篇深入讲解了 Spring Cloud 微服务中 负载均衡组件 Ribbon 架构原理，分为几大块： Ribbon 的六大核心组件 Ribbon 如何拦截请求并进行转发的。 Ribbon 初始化的原理。 Ribbon 如何同步 Eureka 注册表的原理。 Eureka 和 Ribbon 两种 心跳检测的原理 Ribbon 的常用配置项。 https://www.cnblogs.com/zhixiang-org-cn/archive/2019/10/31/11769320.html https://my.oschina.net/u/3748584/blog/4814474 作者简介：悟空，8年一线互联网开发和架构经验，用故事讲解分布式、架构设计、Java 核心技术。《JVM性能优化实战》专栏作者，开源了《Spring Cloud 实战 PassJava》项目，公众号：悟空聊架构。本文已收录至www.passjava.cn
2021-12-08

资源下载

更多资源
Nacos

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

时间: 2026-09-24 大小: 189MB 下载: 9次
Spring

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

时间: 2026-08-21 大小: 5MB 下载: 2次
Rocky Linux

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

时间: 2026-08-21 大小: 1.42GB 下载: 6次
Sublime Text

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

时间: 2026-08-21 大小: 9.84MB 下载: 40次
热门标签
DeepSeek Jdk25 OpenAi HarmonyOS6 Nacos3 SpringBoot4 SpringCloud Docker Kubernetes Service Mesh Redis Gemini3 Rocky

欢迎您来访！

登录后，您将获得更多功能！
热门文章
联系我们

有任何问题或合作意向欢迎联系我们

Email: 99873273@qq.com

QQ: 99873273

用户登录
用户注册