缓冲区

前言缓冲机制是对数据持久化的延迟，减少不必要的IO，提高数据落盘的效率。本文将会详细探讨拥有双Buffer的缓冲池（下文统称TwinsBufferPool）是如何实现的，读者可以依此推广，得到N-Buffer的实现原理。在此篇文章中，缓冲区（Buffer）和缓冲池（BufferPool）是两个重要的概念，很明显，两者构成了一个包含与被包含的关系，一个缓冲池内可以有一个或者多个缓冲区协同工作，缓冲池中的所有缓冲区被组织成了一个环形队列，一前一后的两个缓冲区可以互相替换角色。当然，在整个过程中，还会有其他辅助工具的出现，在下文都会逐一阐述。一、设计要点1、可扩展性。毫无疑问，可扩展性是对一个设计良好的软件的一项基本要求，而一个软件的可扩展的地方通常是有很多处的，这在某种程度上会依赖于编程者的经验，如果仅仅局限于产品需求，可能会严重限制了软件的可扩展性。缓冲池是一种相对通用的中间件，扩展点相对比较多，比如：缓冲区数量可指定，线程安全与否，缓冲区阈值调配等等。2、易用性。设计出来的中间件应该是对用户友好的，使用过程中不会有繁琐的配置，奇形怪状的API，更不能有诸多不必要的Dependencies，如果能做到代码无侵入性，那就非常完美了。基于这个要求，TwinsBufferPool做成了一个Spring Boot Starter的形式，加入到项目里的dependencies中即可开启使用。3、稳定性。这就是衡量一个中间件好坏的重要KPI之一，从外观上看，同样是一艘船，破了一个洞和完好无缺将会是一个致命的区别，用户期望自己搭上了一艘完整的船，以便能航行万里而无忧。4、高效性。说到稳定性，那就不得不说高效了，如果能帮助用户又好又快的解决问题，无疑是最完美的结果。关于TwinsBufferPool的稳定性和高效性两个指标，会在文中附上jemeter的压测结果，并加以说明。二、设计方案这一小节将会给出TwinsBufferPool完整的设计方案，我们先从配置说起。每个参数都会提供默认值，所以不做任何配置也是允许的。如下是目前TwinsBufferPool能提供的配置参数（yml）：buffer: capacity: 2000 threshold: 0.5 allow-duplicate: true pool: enable-temporary-storage: true buffer-time-in-seconds: 120下面附上参数说明表：以上参数比较浅显易懂，这里重点解释enable-temporary-storage和buffer-time-in-seconds这两个参数。根据参数说明，很明显可以感受到，这两个参数是为了预防突发情况，导致数据丢失。因为缓冲区都是基于内存的设计的，这就意味着缓冲的数据随时处于一种服务重启，或者服务宕机的高风险环境中，因此，才会有这两个参数的诞生。因为TwinsBufferPool良好的接口设计，对于以上两个参数的实现机制也是高度可扩展的。TwinsBufferPool默认的是基于Redis的实现，用户也可以用MongoDB，MySQL，FileSystem等方式实现。由此又会衍生出另外一个问题，由于各种异常情况，导致临时存储层遗留了一定量的数据，需要在下次启动的时候，恢复这一部分的数据。总而言之，数据都是通过flush动作最终持久化到磁盘上。因为大多数实际业务场景对于缓冲池的并发量是有一定要求的，所以默认就采用了线程安全的实现策略，受到JDK中ThreadPool的启发，缓冲池也具备了自身状态管理的机制。如下列出了缓冲池所有可能存在的状态，以及各个状态的流转。/** * 缓冲池暂未就绪 /private static final int ST_NOT_READY = 1;/* * 缓冲池初始化完毕，处于启动状态 /private static final int ST_STARTED = 2;/* * 如果安全关闭缓冲池，会立即进入此状态 /private static final int ST_SHUTTING_DOWN = 3;/* * 缓冲池已关闭 /private static final int ST_SHUTDOWN = 4;/* * 正在进行数据恢复 */private static final int ST_RECOVERING = 5;通过上述的一番分析，设计的方案也呼之欲出了，下面给出主要的接口设计与实现。通过以上的讲解，也不难理解BufferPool定义的接口。缓冲池的整个生命周期，以及内部的一些运作机制都得以体现。值得注意的是，在设计上，将缓冲池和存储层做了逻辑分离，使得扩展性进一步得到增强。存储相关的接口包含了一些简单的CURD，目前默认是用Redis作为临时存储层，MongoDB作为永久存储层，用户可以根据需要实现其他的存储方式。下图展现的是TwinsBufferPool的实现方式，DataBuffer是缓冲区，必须依赖的基础元素。因为设计的是环形队列，所以依赖了CycleQueue，这个环形队列的interface也是自定义的，在JDK中没有找到比较合适的实现。值得注意的是，BufferPool接口定义是灵活可扩展的，TwinsBufferPool只是提供了一种基于环形队列的实现方式，用户也可以自行设计，使用另外一种数据结构来支撑缓冲池的运作。三、压测报告使用的是个人的PC电脑，机器的配置如下：处理器：i5-7400 CPU 3.00GHZ 四核内存：8.00GB操作系统：Windows10 64位 基于x64的处理器运行环境如下：jdk 1.8.0_144SpringBoot_2.1.0，内置Tomcat9.0Redis_v4.0.1MongoDB_v3.4.7测试工具：jemeter_v5.1总共测试了四组参数，每组参数主要是针对最大容量，阈值和最大缓冲时间三个参数来做调整。第一组：buffer: capacity: 1000 threshold: 0.8 pool: buffer-time-in-seconds: 60第二组：buffer: capacity: 5000 threshold: 0.8 pool: buffer-time-in-seconds: 60第三组buffer: capacity: 5000 threshold: 0.8 pool: buffer-time-in-seconds: 300第四组buffer: capacity: 10000 threshold: 0.8 pool: buffer-time-in-seconds: 300总共采集了9个指标：CPU占用率，堆内存/M，线程数，错误率，吞吐量/sec，最长响应时间/ms，最短响应时间/ms，平均响应时间/ms，数据丢失量。限于篇幅，只展示4个指标：堆内存，数据丢失量，平均响应时间，吞吐量。总体来看，随着每秒并发量的增加，各项指标呈现了不太乐观的趋势，其中最不稳定的是第四组参数，波动较为明显，综合表现最佳的是第二组参数，其次是第三组。数据丢失量是一个比较让人关心的指标，从图中可以得知，在并发量达到4000的时候，开始有数据丢失的现象，而造成这一现象的原因并非是TwinsBufferPool实现代码的Bug，而是请求超时导致的“Connection refused”，因为每个Servlet运行容器都会有超时机制，如果排队请求时间过长，就是直接被拒绝了。因此，看数据丢失量和错误率曲线，这两者是一致的。如果设置成不超时，那么将是零丢失量，零错误率，所带来的代价就是平均响应时间会拉长。因为受限于个人的测试环境，整个测试过程显得不是很严谨，得出来的数据也并不是很完美，不过，我这里提供了一些优化调整的建议：1、硬件环境。正所谓“巧妇难为无米之炊”，如果提供的硬件性能本身就是有限的话，那么，在上面运行的软件也难以得到正常的发挥。2、软件架构。这个想象的空间很大，其中有一种方案我认为未来可以纳入到RoadMap中：多缓冲池的负载均衡。我们可以尝试在一个应用中启用多个缓冲池，通过调度算法，将缓冲数据均匀的分配给各个缓冲池，不至于出现只有一个缓冲池“疲于奔命”的状况，最起码系统的吞吐量会有所提升。3、其他中间件或者工具的辅助，比如加上消息中间件可以起到削峰的作用，各项指标也将会有所改善。4、参数调优。这里的参数指代的不仅仅是缓冲池的参数，还有包括最大连接数，最大线程数，超时时间等诸多外部参数。四、总结本文详细阐述了双Buffer缓冲池的设计原理，以及实现方式，并对TwinsBufferPool实施了压测，也对测试结果进行了一番分析。欢迎关注我的微信订阅号：技术汇。如果想查看完整的测试报告，可在订阅号内回复关键词：测试报告，即可获取到下载链接。如果想深入研究TwinsBufferPool源码的读者，可在订阅号内回复关键词：缓冲池。 ...

题目We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of ‘a’, widths[1] is the width of ‘b’, …, and widths[25] is the width of ‘z’.Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.Example :Input: widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]S = “abcdefghijklmnopqrstuvwxyz"Output: [3, 60]Explanation: All letters have the same length of 10. To write all 26 letters,we need two full lines and one line with 60 units.Example :Input: widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]S = “bbbcccdddaaa"Output: [2, 4]Explanation: All letters except ‘a’ have the same length of 10, and “bbbcccdddaa” will cover 9 * 10 + 2 * 4 = 98 units.For the last ‘a’, it is written on the second line becausethere is only 2 units left in the first line.So the answer is 2 lines, plus 4 units in the second line.Note:The length of S will be in the range [1, 1000].S will only contain lowercase letters.widths is an array of length 26.widths[i] will be in the range of [2, 10].题目地址讲解这道题有点写缓冲区的意思，很考验逻辑性。如果缓冲区还没满，就塞一个试试如果大于缓冲区的长度，就换一行，并让新的缓冲区重新接收；如果缓冲区恰好满了，也是换一行，缓冲区长度置0.Java代码class Solution { public int[] numberOfLines(int[] widths, String S) { if(S==null){ return new int[]{0, 0}; } char[] c = S.toCharArray(); int count=1; int len = 0; for(int i=0;i<c.length;i++){ if(len<100){ len += widths[c[i]-‘a’]; } if(len>100){ len = widths[c[i]-‘a’]; count++; }else if(len==100){ len = 0; count++; } } return new int[]{count, len}; }} ...