xindoo
TA的个人档案
xindoo_个人页
文章
14
问答
0
视频
0
个人介绍
CSDN博客专家，9年博主
擅长的技术
- Java
- Python
- 前端开发
- Linux
获得更多能力
通用技术能力：
-
Java
初级
能力说明：
了解变量作用域、Java类的结构，能够创建带main方法可执行的java应用，从命令行运行java程序；能够使用Java基本数据类型、运算符和控制结构、数组、循环结构书写和运行简单的Java程序。
-
Linux
中级
能力说明：
掌握Linux文件管理方式和技巧，对用户和组管理有基本认知，掌握Linux网络知识，对TCP/IP协议及OSI七层模型有较为清晰的概念，掌握Linux磁盘与文件系统管理技巧，知道如何安装Linux软件包，逐步掌握Shell脚本的编程技巧。
云产品技术能力：
暂时未有相关云产品技术能力~
阿里云技能认证
详细说明-
发表了文章 2020-07-23
JDK11现存性能bug(JDK-8221393)深度解析
这是一篇鸽了很久的博客，因为博客内容和素材早就准备差不多了，但就是一直懒得整理，今天终于下定决心终于整理出来了，这也是这个bug JDK-8221393唯一一篇中文介绍博客。 先大致介绍下这个bug，准确说这个应该是jdk11新引入的zgc的一个bug，该bug在被触发的情况下会导致进程CPU使用率会逐渐升高，如果不管的话最终CPU会到100% 影响服务可用性，而且这个性能bug在jdk11最新的代码中仍未修复。不过不用担心，这个bug触发的要求比较苛刻，估计这也是jdk开发者不修复该bug的原因之一。另外，我在翻看jdk13源码时发现该bug已被修复，并且有些相关设计上的提升。该bug的表象如上图，在业务和代码逻辑无变更的情况下，CPU使用率大概每隔10天就会翻倍，重启后恢复正常。上图中我们分别在11月19和11月29日重启过，CPU明显下跌，然后又开启一轮新的轮回…… 这个服务是我们很重要的一个服务，我们有同事很长时间都在找原因，也尝试做过很多优化，一直都没解决，我们的服务只好靠定期重启续命了。 不过这事在我介入后的第二天就立马有了眉目，嘿嘿嘿。。。 (不是我能打，而是他们缺少一把趁手的“兵器”) 排查过程 作为一名工程师，面对上面的现象，你会怎么做？ 我想你的第一反应肯定是业务代码有问题？是不是有什么地方导致内存泄露？ 是不是业务代码里有什么地方加载的数据太多，越来越慢？…… 同事尝试过dump堆里的内容，dump jstak线程…… 都没看出来什么异常，也优化了业务代码里之前一些不合理的逻辑，始终没有解决问题。 当时的问题是他们都没有往热点代码的方向排查，主要是因为他们不知道有啥好用的工具。 而我恰好当时在关注过阿里的Arthas，知道当时正好Arthas新增了性能排查命令profiler 可以生成CPU火焰图，而我又恰好看过阮一峰老师的如何读懂火焰图？。然后我就给同事推荐了Arthas并建议同事用Arthas生成CPU的火焰图，看下到底是哪个地方耗费CPU，然后就发现了异常。 火焰图该怎么读？ 不知道怎么看火焰图不要紧，其实很简单，具体可参考阮一峰老师的如何读懂火焰图？。 y 轴表示调用栈，每一层都是一个函数。调用栈越深，火焰就越高，顶部就是正在执行的函数，下方都是它的父函数。x 轴表示抽样数，如果一个函数在 x 轴占据的宽度越宽，就表示它被抽到的次数多，即执行的时间长。注意，x 轴不代表时间，而是所有的调用栈合并后，按字母顺序排列的。火焰图就是看顶层的哪个函数占据的宽度最大。只要有"平顶"（plateaus），就表示该函数可能存在性能问题。 你可以简单认为每一块越宽，它就越耗费CPU，用火焰图做性能分析的关键就是去找那些你觉得本应该很窄但实际却很宽的函数。上图中就是我们有问题服务长期运行后和刚启动时的生成的火焰图(同样的代码和环境)，左图明显有异常，它有好几个"平顶"，也就是说该函数消耗了过多的CPU，大概率这就是问题的根源了。 这里我特意找到了该函数调用的堆栈信息，然后就发现了我们代码中不合理的地方。 [0x00007f2091c15000] java.lang.Thread.State: RUNNABLE at java.lang.StackStreamFactory$AbstractStackWalker.fetchStackFrames(java.base@11/Native Method) at java.lang.StackStreamFactory$AbstractStackWalker.fetchStackFrames(java.base@11/StackStreamFactory.java:386) at java.lang.StackStreamFactory$AbstractStackWalker.getNextBatch(java.base@11/StackStreamFactory.java:322) at java.lang.StackStreamFactory$AbstractStackWalker.peekFrame(java.base@11/StackStreamFactory.java:263) at java.lang.StackStreamFactory$AbstractStackWalker.hasNext(java.base@11/StackStreamFactory.java:351) at java.lang.StackStreamFactory$StackFrameTraverser.tryAdvance(java.base@11/StackStreamFactory.java:593) at java.util.stream.ReferencePipeline.forEachWithCancel(java.base@11/ReferencePipeline.java:127) at java.util.stream.AbstractPipeline.copyIntoWithCancel(java.base@11/AbstractPipeline.java:502) at java.util.stream.AbstractPipeline.copyInto(java.base@11/AbstractPipeline.java:488) at java.util.stream.AbstractPipeline.wrapAndCopyInto(java.base@11/AbstractPipeline.java:474) at java.util.stream.FindOps$FindOp.evaluateSequential(java.base@11/FindOps.java:150) at java.util.stream.AbstractPipeline.evaluate(java.base@11/AbstractPipeline.java:234) at java.util.stream.ReferencePipeline.findFirst(java.base@11/ReferencePipeline.java:543) at org.apache.logging.log4j.util.StackLocator.lambda$getCallerClass$6(StackLocator.java:54) at org.apache.logging.log4j.util.StackLocator$$Lambda$94/0x00007f238e2cacb0.apply(Unknown Source) at java.lang.StackStreamFactory$StackFrameTraverser.consumeFrames(java.base@11/StackStreamFactory.java:534) at java.lang.StackStreamFactory$AbstractStackWalker.doStackWalk(java.base@11/StackStreamFactory.java:306) at java.lang.StackStreamFactory$AbstractStackWalker.callStackWalk(java.base@11/Native Method) at java.lang.StackStreamFactory$AbstractStackWalker.beginStackWalk(java.base@11/StackStreamFactory.java:370) at java.lang.StackStreamFactory$AbstractStackWalker.walk(java.base@11/StackStreamFactory.java:243) at java.lang.StackWalker.walk(java.base@11/StackWalker.java:498) at org.apache.logging.log4j.util.StackLocator.getCallerClass(StackLocator.java:53) at org.apache.logging.log4j.util.StackLocatorUtil.getCallerClass(StackLocatorUtil.java:61) at org.apache.logging.slf4j.Log4jLoggerFactory.getContext(Log4jLoggerFactory.java:43) at org.apache.logging.log4j.spi.AbstractLoggerAdapter.getLogger(AbstractLoggerAdapter.java:46) at org.apache.logging.slf4j.Log4jLoggerFactory.getLogger(Log4jLoggerFactory.java:29) at org.slf4j.LoggerFactory.getLogger(LoggerFactory.java:358) at org.slf4j.LoggerFactory.getLogger(LoggerFactory.java:383) at com.xxxxxxx.infra.cache.redis.ReadCommandTemplate.<init>(ReadCommandTemplate.java:21) at com.xxxxxxx.infra.cache.redis.RedisClient$4.<init>(RedisClient.java:138) at com.xxxxxxx.infra.cache.redis.RedisClient.hget(RedisClient.java:138) ... ... ReadCommandTemplate是我们公司封装的一个redis client，每读写一次redis就会实例化一个ReadCommandTemplate，我们的业务逻辑中每个请求都会读一次redis，所以导致ReadCommandTemplate这个类生成很多个实例。本身这个类很轻量，按理来说多次实例话也没关系，但其中用了logger，而且logger没有声明为static，所以没new 一个ReadCommandTemplate，都会同时生成一个logger，从火焰图来看，似乎是生成logger的过程中产生了性能问题。 public abstract class ReadCommandTemplate<T> { private Logger logger = LoggerFactory.getLogger(ReadCommandTemplate.class); /** * 其他代码逻辑省略 */ } 有经验的java开发者一眼就能看出来上面代码的不合理之处，但应该只是稍微影响性能，不会出现文首那种诡异的现象！ 确实，这个redis client在我们部分被广泛使用，其他的应用都没出现问题。。。 会不会是这个应用恰巧凑齐了某个bug触发的所有条件？？ Bug的确认 要想确认bug是否是这个非static的logger导致的，有两个方案：1. 修复logger的问题，看CPU是否会上涨。 2. 真正搞清楚这个bug的原理。因为方案1需要至少等待一周才能实锤，所以我们选择了二者并行。同事修复了logger，而我开启了问题探索和jvm源码阅读之旅。后来方案1确实也正式了是logger导致的，而我也找到了19年有人给jvm团队反馈bug后jvm团队讨论的邮件列表。 jdk的开发者Stefan Karlsson确认并大致给出了这个bug出现的原因，如上图。这里我大致解释下，JVM在查找方法的时候会调用"ResolvedMethodTable::lookup"，其实这里是查找一个只有1007个bucket的hash表，因为jdk11的zgc没有定期对ResolvedMethodTable做清理，所以里面的数据会越来越多，查询会越来越慢。 问题是用jdk11+zgc+log4j组合的人也非常多，为什么偏偏就我们的代码触发了bug？？ 深度剖析 为了深入理解这个bug，我们首先来看下我们调LoggerFactory.getLogger()的时候发生了什么！！在jdk9及以后的版本中，log4j使用了新的StackWalker来获取线程的堆栈信息，然后遍历每个栈帧，所以StackWalker就调用native方法fetchStackFrames从JVM里获取这个栈帧。 我翻阅了JVM代码，找到了ResolvedMethodTable::lockup()在做啥！ 不过首先我们得知道ResolvedMethodTable是啥？ ResolvedMethodTable可以简单认为是JVM中存储所有已经解析到的方法信息的一个hashtable，它只有1007的bucket(为什么设计这么小？)，这么小的bucket必然很容易产生hash冲突，处理hash冲突的方式就是开链，而lockup()在查找过程中，需要遍历单链表，所以如果单链表过长，lookup的查询性能就下来了，lookup()的源码如下。 oop ResolvedMethodTable::lookup(Method* method) { unsigned int hash = compute_hash(method); int index = hash_to_index(hash); return lookup(index, hash, method); } oop ResolvedMethodTable::lookup(int index, unsigned int hash, Method* method) { for (ResolvedMethodEntry* p = bucket(index); p != NULL; p = p->next()) { if (p->hash() == hash) { oop target = p->object_no_keepalive(); if (target != NULL && java_lang_invoke_ResolvedMethodName::vmtarget(target) == method) { ResourceMark rm; log_debug(membername, table) ("ResolvedMethod entry found for %s index %d", method->name_and_sig_as_C_string(), index); return p->object(); } } } return NULL; } 现在的问题是究竟是什么导致ResolvedMethodTable数据太多，从而使得其中单个bucket的链表过长？ 我们还是从该bug的邮件讨论列表里找到答案http://mail.openjdk.java.net/pipermail/zgc-dev/2019-March/000612.html，这里我大概翻译如下: GC除了卸载不用的类时，也会做好多其他的清理工作，比如清理ResolvedMethodTable和StringTable中不用的信息。ResolvedMethodTable保存着java中ResolvedMethodName类实例的弱指针，如果ResolvedMethodName不可达，正常情况下gc就会清理掉这个不可达对象。而ResolvedMethodName是MemberName中的一部分。StackWalker遍历栈帧的时候，就会创建MemberName java对象并放到StackFrameInfo.memberName中，jvm中的代码实现如下: void java_lang_StackFrameInfo::set_method_and_bci(Handle stackFrame, const methodHandle& method, int bci, TRAPS) { ... // 创建ResolvedMethodName对象并插入到ResolvedMethodTable中 CallInfo info(method(), ik, CHECK); // 把ResolveMethodName对象放到MemberName中 MethodHandles::init_method_MemberName(mname, info); 堆栈调用信息如下： java_lang_StackFrameInfo::set_method_and_bci(Handle, methodHandle const&, int, Thread*) JavaFrameStream::fill_frame(int, objArrayHandle, methodHandle const&, Thread*) StackWalk::fill_in_frames(long, BaseFrameStream&, int, int, objArrayHandle, int&, Thread*) StackWalk::fetchNextBatch(Handle, long, long, int, int, objArrayHandle, Thread*) JVM_MoreStackWalk java.lang.StackStreamFactory$AbstractStackWalker.fetchStackFrames 后续，如果StackFrameInfos不用之后，这些对象会被从类的引用关系中移除，并被gc回收掉，然后gc会移除ResolvedMethodTable中相应的ResolvedMethodName。但问题是jdk11中，zgc并没有真正移除这些ResolvedMethodName，从而导致ResolvedMethodTable中的数据量越来越大，单链越来越长，查找效率越来越低。 在JDK11的源码中SymbolTable::unlink()中实现了ResolvedMethodTable中无用信息的卸载，其他几个老gc都调用了，而zgc中确实没有调用，不知道这是忘记了还是特意为之…… 简单梳理下就是：每次调用StackWalker遍历栈帧的时候，每个栈帧都会生成一个ResolvedMethodName对象放到jvm中的ResolvedMethodTable中，但jdk11的zgc不能有效清理其中不用的对象。因为ResolvedMethodTable是个定容的hashtable，随着其中的数据越来越多，每个bucket的单链表越来越长，查询效率会越来越慢。 所以最终导致CPU的使用率越来越高。 避坑指南 如果你看懂了上文的bug原理，相信你已经知道了如何闭坑，如果没看懂也没关系， 一句话 不要使用jdk11+zgc的同时频繁使用StackWalker(比如错误使用log4j)。当然也不是完全不能使用log4j了，只要不是频繁调用StackWalker就没问题，像我们代码中的logger只需要声明成static，这样StackWalker只会在类初始化的时候调用，就不会有问题了。知道了原理，也就能解释清楚为什么我们很多其他应用用了jdk11也用了有问题的RedisClient没有出现cpu异常的现象，就是因为其他应用没有启用zgc。 当然这个bug的本质就是jdk11+zgc+StackWalker的bug，三者都是bug触发的必要条件，如果你能避免其中一条就可以完美避开这个bug了，比如升级到jdk12+，比如不用zgc…… Bugfix 对于我们应用来说，只需按照上面的避坑指南操作即可，但对于jdk团队来说，这个bug他们肯定是要修复的。 从官网bug页面可以看到这个bug在jdk13中已经修复了，我们来看看他们是如何修复的。是不是只需要在zgc合适的地方调一下SymbolTable::unlink()就行了？是的，但jdk团队做的远不止于此，除了unlink之外，他们还优化了ResolvedMethodTable的实现，支持了动态扩缩容，可以避免单链表过长的问题，具体可以看下jdk源码中src/hotspot/share/prims/resolvedMethodTable.cpp的文件。 void ResolvedMethodTable::do_concurrent_work(JavaThread* jt) { _has_work = false; double load_factor = get_load_factor(); log_debug(membername, table)("Concurrent work, live factor: %g", load_factor); // 人工load_factor大于2，并且没有达到最大限制，就执行bucket扩容，并且移除无用的entry if (load_factor > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached()) { grow(jt); } else { clean_dead_entries(jt); } } void ResolvedMethodTable::grow(JavaThread* jt) { ResolvedMethodTableHash::GrowTask gt(_local_table); if (!gt.prepare(jt)) { return; } log_trace(membername, table)("Started to grow"); { TraceTime timer("Grow", TRACETIME_LOG(Debug, membername, table, perf)); while (gt.do_task(jt)) { gt.pause(jt); { ThreadBlockInVM tbivm(jt); } gt.cont(jt); } } gt.done(jt); _current_size = table_size(); log_info(membername, table)("Grown to size:" SIZE_FORMAT, _current_size); } 总结 这个bug触发的主要原因其实还是我们自己的代码写的不够规范(logger未声明为static)，而这个不规范其实也对其他没有触发这个bug的应用也产生了影响，毕竟生成logger也是会消耗性能的，我们代码fix后其他应用升级，有些服务CPU占用率降低5%+。这也充分说明代码质量的重要性，尤其是那种被广泛采用的基础代码。 另外是不是有些人还有个疑问，这个bug为什么不在jdk11后续版本中修掉，而是选择在jdk13中彻底修掉，不怕影响到使用jdk11的用户吗？对这个问题我有个想法，其实这个bug并不是很容易触发的严重bug(jdk11+zgc+log4j的频繁调用)，而且即便是触发了，jdk的使用者也很容易通过修改自己的代码来规避这个bug，所以对jdk的开发者而言这不是一个重要且紧急的bug，后续修复掉就行了。 参考资料 阿里巴巴开源java问题排查工具 Arthas. 如何读懂火焰图？ 阮一峰 jdk开发者关于bug讨论的邮件列表
-
发表了文章 2020-06-03
从0到1打造正则表达式执行引擎(二)
@[toc]在上篇博客从0到1打造正则表达式执行引擎(一)中我们已经构建了一个可用的正则表达式引擎，相关源码见https://github.com/xindoo/regex，但上文中只是用到了NFA，NFA的引擎建图时间复杂度是O(n)，但匹配一个长度为m的字符串时因为涉及到大量的递归和回溯，最坏时间复杂度是O(mn)。与之对比DFA引擎的建图时间复杂度O(n^2)，但匹配时没有回溯，所以匹配复杂度只有O(m)，性能差距还是挺大的。 DFA和NFA 我们已经多次提到了NFA和DFA，它俩究竟是啥？有啥区别？ 首先，NFA和DFA都是有限状态机，都是有向图，用来描述状态和状态之间的关系。其中NFA全称是非确定性有限状态自动机(Nondeterministic finite automaton)，DFA全称是确定性有限状态自动机(Deterministic finite automaton)。 二者的差异主要在于确定性和非确定性，何为确定性？ 确定性是指面对同一输入，不会出现有多条可行的路径执行下一个节点。有点绕，看完图你就理解了。 图示分别是一个NFA和DFA，上图之所以是NFA是因为它有节点具备不确定性，比如0节点，在输入"a"之后它分别可以到0 1 2 节点。还有，上图有$\epsilon$边，它可以在没有输入的情况下跳到下一个节点，这也带来了不确定性。相反，下图DFA中，每个节点对某一特定的输入都只有最多一条边。 总结下NFA和DFA的区别就是，有ε边或者某个节点对同一输入对应多个状态的一定是NFA。 DFA和NFA存在等价性，也就是说任何NFA都可以转化为等价的DFA。由于NFA的非确定性，在面对一个输入的时候可能有多条可选的路径，所以在一条路径走不通的情况下，需要回溯到选择点去走另外一条路径。但DFA不同，在每个状态下，对每个输入不会存在多条路径，就不需要递归和回溯了，可以一条路走到黑。DFA的匹复杂度只有O(n)，但因为要递归和回溯NFA的匹配复杂度达到了O(n^2)。 这也是为什么我们要将引擎中的NFA转化为DFA的主要原因。 NFA转DFA 算法 NFA转DFA的算法叫做子集构造法，其具体流程如下。 步骤1: NFA的初始节点和初始节点所有ε可达的节点共同构成DFA的初始节点，然后对初始DFA节点执行步骤2。 步骤2: 对当前DFA节点，找到其中所有NFA节点对输入符号X所有可达的NFA节点，这些节点沟通构成的DFA节点作为当前DFA节点对输入X可达的DFA节点。 步骤3: 如果步骤2中找到了新节点，就对新节点重复执行步骤2。 步骤4: 重复步骤2和步骤3直到找不DFA新节点为止。 步骤5: 把所有包含NFA终止节点的DFA节点标记为DFA的终止节点。 语言描述比较难理解，我们直接上例子。 我们已经拿上一篇网站中的正则表达式 a(b|c) 为例，我在源码https://github.com/xindoo/regex中加入了NFA输出的代码， a(b|c) 的NFA输出如下。 from to input 0-> 1 a 1-> 8 Epsilon 8-> 9 Epsilon 8-> 6 Epsilon 6-> 2 Epsilon 6-> 4 Epsilon 2-> 3 b 4-> 5 c 3-> 7 Epsilon 5-> 7 Epsilon 7-> 9 Epsilon 7-> 6 Epsilon 绘图如下：我们在上图的基础上执行步骤1 得到了节点0作为DFA的开始节点。 然后对DFA的节点0执行步骤1，找到NFA中所有a可达的NFA节点(1#2#4#6#8#9)构成NFA中的节点1，如下图。 我以dfa1为出发点，发现了a可达的所有NFA节点(2#3#4#6#7#9)和b可达的所有节点(2#4#5#6#7#9)，分别构成了DFA中的dfa2和dfa3，如下图。 然后我们分别在dfa2 dfa3上执行步骤三，找不到新节点，但会找到几条新的边，补充如下，至此我们就完成了对 a(b|c)* 对应NFA到DFA的转化。 可以看出DFA图节点明显少于NFA，但NFA更容易看出其对应的正则表达式。之前我还写过DFA生成正则表达式的代码，详见文章https://blog.csdn.net/xindoo/article/details/102643270 代码实现 代码其实就是对上文流程的表述，更多细节见https://github.com/xindoo/regex。 private static DFAGraph convertNfa2Dfa(NFAGraph nfaGraph) { DFAGraph dfaGraph = new DFAGraph(); Set<State> startStates = new HashSet<>(); // 用NFA图的起始节点构造DFA的起始节点 步骤1 startStates.addAll(getNextEStates(nfaGraph.start, new HashSet<>())); if (startStates.size() == 0) { startStates.add(nfaGraph.start); } dfaGraph.start = dfaGraph.getOrBuild(startStates); Queue<DFAState> queue = new LinkedList<>(); Set<State> finishedStates = new HashSet<>(); // 如果BFS的方式从已找到的起始节点遍历并构建DFA queue.add(dfaGraph.start); while (!queue.isEmpty()) { // 步骤2 DFAState curState = queue.poll(); for (State nfaState : curState.nfaStates) { Set<State> nextStates = new HashSet<>(); Set<String> finishedEdges = new HashSet<>(); finishedEdges.add(Constant.EPSILON); for (String edge : nfaState.next.keySet()) { if (finishedEdges.contains(edge)) { continue; } finishedEdges.add(edge); Set<State> efinishedState = new HashSet<>(); for (State state : curState.nfaStates) { Set<State> edgeStates = state.next.getOrDefault(edge, Collections.emptySet()); nextStates.addAll(edgeStates); for (State eState : edgeStates) { // 添加E可达节点 if (efinishedState.contains(eState)) { continue; } nextStates.addAll(getNextEStates(eState, efinishedState)); efinishedState.add(eState); } } // 将NFA节点列表转化为DFA节点，如果已经有对应的DFA节点就返回，否则创建一个新的DFA节点 DFAState nextDFAstate = dfaGraph.getOrBuild(nextStates); if (!finishedStates.contains(nextDFAstate)) { queue.add(nextDFAstate); } curState.addNext(edge, nextDFAstate); } } finishedStates.add(curState); } return dfaGraph; } public class DFAState extends State { public Set<State> nfaStates = new HashSet<>(); // 保存对应NFAState的id,一个DFAState可能是多个NFAState的集合,所以拼接成String private String allStateIds; public DFAState() { this.stateType = 2; } public DFAState(String allStateIds, Set<State> states) { this.allStateIds = allStateIds; this.nfaStates.addAll(states); //这里我将步骤五直接集成在创建DFA节点的过程中了 for (State state : states) { if (state.isEndState()) { this.stateType = 1; } } } public String getAllStateIds() { return allStateIds; } } 另外我在DFAGraph中封装了有些NFA节点列表到DFA节点的转化和查找，具体如下。 public class DFAGraph { private Map<String, DFAState> nfaStates2dfaState = new HashMap<>(); public DFAState start = new DFAState(); // 这里用map保存NFAState结合是已有对应的DFAState, 有就直接拿出来用 public DFAState getOrBuild(Set<State> states) { String allStateIds = ""; int[] ids = states.stream() .mapToInt(state -> state.getId()) .sorted() .toArray(); for (int id : ids) { allStateIds += "#"; allStateIds += id; } if (!nfaStates2dfaState.containsKey(allStateIds)) { DFAState dfaState = new DFAState(allStateIds, states); nfaStates2dfaState.put(allStateIds, dfaState); } return nfaStates2dfaState.get(allStateIds); } } DFA引擎匹配过程 dfa引擎的匹配也可以完全复用NFA的匹配过程，所以对之前NFA的匹配代码，可以针对DFA模式取消回溯即可(不取消也没问题，但会有性能影响)。 private boolean isMatch(String text, int pos, State curState) { if (pos == text.length()) { if (curState.isEndState()) { return true; } for (State nextState : curState.next.getOrDefault(Constant.EPSILON, Collections.emptySet())) { if (isMatch(text, pos, nextState)) { return true; } } return false; } for (Map.Entry<String, Set<State>> entry : curState.next.entrySet()) { String edge = entry.getKey(); // 如果是DFA模式,不会有EPSILON边 if (Constant.EPSILON.equals(edge)) { for (State nextState : entry.getValue()) { if (isMatch(text, pos, nextState)) { return true; } } } else { MatchStrategy matchStrategy = MatchStrategyManager.getStrategy(edge); if (!matchStrategy.isMatch(text.charAt(pos), edge)) { continue; } // 遍历匹配策略 for (State nextState : entry.getValue()) { // 如果是DFA匹配模式,entry.getValue()虽然是set,但里面只会有一个元素,所以不需要回溯 if (nextState instanceof DFAState) { return isMatch(text, pos + 1, nextState); } if (isMatch(text, pos + 1, nextState)) { return true; } } } } return false; } 因为DFA的匹配不需要回溯，所以可以完全改成非递归代码。 private boolean isDfaMatch(String text, int pos, State startState) { State curState = startState; while (pos < text.length()) { boolean canContinue = false; for (Map.Entry<String, Set<State>> entry : curState.next.entrySet()) { String edge = entry.getKey(); MatchStrategy matchStrategy = MatchStrategyManager.getStrategy(edge); if (matchStrategy.isMatch(text.charAt(pos), edge)) { curState = entry.getValue().stream().findFirst().orElse(null); pos++; canContinue = true; break; } } if (!canContinue) { return false; } } return curState.isEndState(); } DFA和NFA引擎性能对比 我用jmh简单做了一个非严格的性能测试，随手做的 看看就好，结果如下: Benchmark Mode Cnt Score Error Units RegexTest.dfaNonRecursion thrpt 2 144462.917 ops/s RegexTest.dfaRecursion thrpt 2 169022.239 ops/s RegexTest.nfa thrpt 2 55320.181 ops/s DFA的匹配性能远高于NFA，不过这里居然递归版还比非递归版快，有点出乎意料， 详细测试代码已传至Github https://github.com/xindoo/regex，欢迎查阅。 参考资料 nfa转dfa
-
发表了文章 2020-06-03
从0到1打造正则表达式执行引擎(一)
首先声明，这篇文章不是教你如何写正则表达式，而是教你写一个能执行正则表达式的执行引擎。 网上教你写正则表达式的文章、教程很多，但教你写引擎的并不多。很多人认为我就是用用而已，没必要理解那么深，但知道原理是在修炼内功，正则表达式底层原理并不单单是用在这，而是出现在计算机领域的各个角落。理解原理可以让你以后写字符串匹配时正则表达式能够信手拈来，理解原理也是触类旁通的基础。废话不多说，直接开始正式内容。 本文是我个人做的动手实践性项目，所以未完整支持所有语法，而且因为是用NFA实现的所以性能比生产级的执行引擎差好多。目前源码已开放至https://github.com/xindoo/regex，后续会继续更新，欢迎Star、Fork 提PR。 目前支持的正则语义如下: 基本语法: . ? * + () | 字符集合: [] 特殊类型符号: d D s S w W 前置知识 声明：本文不是入门级的文章，所以如果你想看懂后文的内容，需要具备以下的基本知识。 基本的编程知识，虽然这里我是用java写的，但并不要求懂java，懂其他语法也行，基本流程都是类似，就是语法细节不同。 了解正则表达式，知道简单的正则表达式如何写。 基本的数据结构知识，知道有向图的概念，知道什么是递归和回溯。 有限状态机 有限状态机(Finite-state machine)，也被称为有限状态自动机(finite-state automation)，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型(From 维基百科 状态机) 。 听起来晦涩难懂，我用大白话描述一遍，状态机其实就是用图把状态和状态之间的关系描述出来，状态机中的一个状态可以在某些给定条件下变成另外一种状态。举个很简单的例子你就懂了。 比如我今年18岁，我现在就是处于18岁的状态，如果时间过了一年，我就变成19岁的状态了，再过一年就20了。当然我20岁时时光倒流2年我又可以回到18岁的状态。这里我们就可以把我的年龄状态和时间流逝之间的关系用一个自动机表示出来，如下。每个圈代表一个节点表示一种状态，每条有向边表示一个状态到另一个状态的转移条件。上图中状态是我的年龄，边表示时间正向或者逆向流逝。 有了状态机之后，我们就可以用状态机来描述特定的模式，比如上图就是年龄随时间增长的模式。如果有人说我今年18岁，1年后就20岁了。照着上面的状态机我们来算下，1年后你才19岁，你这不是瞎说吗！ 没错，状态机可以来判定某些内容是否符合你状态机描述的模式了。哟，一不小心就快扯到正则表达式上了。 我们这里再引入两种特殊的状态：起始态和接受态(终止态)，见名知意，不用我过多介绍了吧，起始态和终止态的符号如下。 我们拿状态机来做个简单的字符串匹配。比如我们有个字符串“zsx”，要判断其他字符串是否和"zxs"是一致的，我们可以为"zxs"先建立一个自动机，如下。对于任意一个其他的字符串，我们从起始态0开始，如果下一个字符能匹配到0后边的边上就往后走，匹配不上就停止，一直重复，如果走到终止态3说明这个字符串和”zxs“一样。任意字符串都可以转化成上述的状态机，其实到这里你就知道如何实现一个只支持字符串匹配的正则表达式引擎了，如果想支持更多的正则语义，我们要做的更多。 状态机下的正则表达式 我们再来引入一条特殊的边，学名叫$\epsilon$闭包(emm！看到这些符号我就回想起上学时被数学支配的恐惧)，其实就是一条不需要任何条件就能转移状态的边。 没错，就只这条红边本边了，它在正则表达式状态机中起着非常重要的连接作用，可以不依赖其他条件直接跳转状态，也就是说在上图中你可以直接从1到2。 有了 $\epsilon$闭包的加持，我们就可以开始学如何画正则表达式文法对应的状态机了。 串联匹配 首先来看下纯字符匹配的自动机，其实上面已经给过一个"zxs"的例子了，这里再贴一下，其实就是简单地用字符串在一起而已，如果还有其他字符，就继续往后串。两个表达式如何传在一起，也很简单，假如我们已经有两个表达式A B对应的状态机，我们只需要将其用$\epsilon$串一起就行了。 并联匹配 (正则表达式中的 |) 正则表达式中的| 标识二选一都可以，比如A|B A能匹配 B也能匹配，那么A|B就可以表示为下面这样的状态图。 从0状态走A或B都可以到1状态，完美的诠释了A|B语义。 重复匹配(正则表达式中的 ? + *) 正则表达式里有4种表示重复的方式，分别是： ？重复0-1次 重复1次以上 重复0次以上 {n,m} 重复n到m次 我来分别画下这4种方式如何在状态机里表示。 重复0-1次 ？ 0状态可以通过E也可以依赖$\epsilon$直接跳过E到达1状态，实现E的0次匹配。 重复1次以上 0到1后可以再通过$\epsilon$跳回来，就可以实现E的1次以上匹配了。 重复0次以上 仔细看其实就是? +的结合。 匹配指定次数 这种建图方式简单粗暴，但问题就是如果n和m很大的话，最后生成的状态图也会很大。其实可以把指定次数的匹配做成一条特殊的边，可以极大减小图的大小。 特殊符号(正则表达式中的 . d s……) 正则表达式中还支持很多某类的字符，比如.表示任意非换行符，d标识数字，[]可以指定字符集…… ，其实这些都和图的形态无关，只是某调特殊的边而已，自己实现的时候可以选择具体的实现方式，比如后面代码中我用了策略模式来实现不同的匹配策略，简化了正则引擎的代码。 子表达式(正则表达式 () ) 子表达可以Tompson算法，其实就是用递归去生成()中的子图，然后把子图拼接到当前图上面。（什么Tompson说的那么高大上，不就是递归吗！） 练习题 来练习画下 a(a|b)* 的状态图，这里我也给出我画的，你可以参考下。 代码实现 建图 看完上文之后相信你一直知道如果将一个正则表达式转化为状态机的方法了，这里我们要将理论转化为代码。首先我们要将图转化为代码标识，我用State表示一个节点，其中用了Map> next表示其后继节点，next中有个key-value就是一条边，MatchStrategy用来描述边的信息。 public class State { private static int idCnt = 0; private int id; private int stateType; public State() { this.id = idCnt++; } Map<MatchStrategy, List<State>> next = new HashMap<>(); public void addNext(MatchStrategy path, State state) { List<State> list = next.get(path); if (list == null) { list = new ArrayList<>(); next.put(path, list); } list.add(state); } protected void setStateType() { stateType = 1; } protected boolean isEndState() { return stateType == 1; } } NFAGraph表示一个完整的图，其中封装了对图的操作，比如其中就实现了上文中图串 并联和重复的操作（注意我没有实现{}）。 public class NFAGraph { public State start; public State end; public NFAGraph(State start, State end) { this.start = start; this.end = end; } // | public void addParallelGraph(NFAGraph NFAGraph) { State newStart = new State(); State newEnd = new State(); MatchStrategy path = new EpsilonMatchStrategy(); newStart.addNext(path, this.start); newStart.addNext(path, NFAGraph.start); this.end.addNext(path, newEnd); NFAGraph.end.addNext(path, newEnd); this.start = newStart; this.end = newEnd; } // public void addSeriesGraph(NFAGraph NFAGraph) { MatchStrategy path = new EpsilonMatchStrategy(); this.end.addNext(path, NFAGraph.start); this.end = NFAGraph.end; } // * 重复0-n次 public void repeatStar() { repeatPlus(); addSToE(); // 重复0 } // ? 重复0次哦 public void addSToE() { MatchStrategy path = new EpsilonMatchStrategy(); start.addNext(path, end); } // + 重复1-n次 public void repeatPlus() { State newStart = new State(); State newEnd = new State(); MatchStrategy path = new EpsilonMatchStrategy(); newStart.addNext(path, this.start); end.addNext(path, newEnd); end.addNext(path, start); this.start = newStart; this.end = newEnd; } } 整个建图的过程就是依照输入的字符建立边和节点之间的关系，并完成图的拼接。 private static NFAGraph regex2nfa(String regex) { Reader reader = new Reader(regex); NFAGraph nfaGraph = null; while (reader.hasNext()) { char ch = reader.next(); String edge = null; switch (ch) { // 子表达式特殊处理 case '(' : { String subRegex = reader.getSubRegex(reader); NFAGraph newNFAGraph = regex2nfa(subRegex); checkRepeat(reader, newNFAGraph); if (nfaGraph == null) { nfaGraph = newNFAGraph; } else { nfaGraph.addSeriesGraph(newNFAGraph); } break; } // 或表达式特殊处理 case '|' : { String remainRegex = reader.getRemainRegex(reader); NFAGraph newNFAGraph = regex2nfa(remainRegex); if (nfaGraph == null) { nfaGraph = newNFAGraph; } else { nfaGraph.addParallelGraph(newNFAGraph); } break; } case '[' : { edge = getCharSetMatch(reader); break; } case '^' : { break; } case '$' : { break; } case '.' : { edge = "."; break; } // 处理特殊占位符 case '\\' : { char nextCh = reader.next(); switch (nextCh) { case 'd': { edge = "\\d"; break; } case 'D': { edge = "\\D"; break; } case 'w': { edge = "\\w"; break; } case 'W': { edge = "\\W"; break; } case 's': { edge = "\\s"; break; } case 'S': { edge = "\\S"; break; } // 转义后的字符匹配 default:{ edge = String.valueOf(nextCh); break; } } break; } default : { // 处理普通字符 edge = String.valueOf(ch); break; } } if (edge != null) { NFAState start = new NFAState(); NFAState end = new NFAState(); start.addNext(edge, end); NFAGraph newNFAGraph = new NFAGraph(start, end); checkRepeat(reader, newNFAGraph); if (nfaGraph == null) { nfaGraph = newNFAGraph; } else { nfaGraph.addSeriesGraph(newNFAGraph); } } } return nfaGraph; } 这里我用了设计模式中的策略模式将不同的匹配规则封装到不同的MatchStrategy类里，目前我实现了. d D s S w w，具体细节请参考代码。这么设计的好处就是简化了匹配策略的添加，比如如果我想加一个x 只匹配16进制字符，我只需要加个策略类就好了，不必改很多代码。 匹配 其实匹配的过程就出从起始态开始，用输入作为边，一直往后走，如果能走到终止态就说明可以匹配，代码主要依赖于递归和回溯，代码如下。 public boolean isMatch(String text) { return isMatch(text, 0, nfaGraph.start); } private boolean isMatch(String text, int pos, State curState) { if (pos == text.length()) { if (curState.isEndState()) { return true; } return false; } for (Map.Entry<MatchStrategy, List<State>> entry : curState.next.entrySet()) { MatchStrategy matchStrategy = entry.getKey(); if (matchStrategy instanceof EpsilonMatchStrategy) { for (State nextState : entry.getValue()) { if (isMatch(text, pos, nextState)) { return true; } } } else { if (!matchStrategy.isMatch(text.charAt(pos))) { continue; } // 遍历匹配策略 for (State nextState : entry.getValue()) { if (isMatch(text, pos + 1, nextState)) { return true; } } } } return false; } 下集预告 还有下集？没错，虽然到这里已经是实现了一个基本的正则表达式引擎，但距离可用在生产环境还差很远，预告如下。 功能完善化 本身上面的引擎对正则语义支持不是很完善，后续我会继续完善代码，有兴趣可以收藏下源码https://github.com/xindoo/regex，但应该不会出一篇新博客了，因为原理性的东西都在这里，剩下的就是只是一些编码工作 。 DFA引擎 上文只是实现了NFA引擎，NFA的引擎建图时间复杂度是O(n)，但匹配一个长度为m的字符串时因为涉及到大量的递归和回溯，最坏时间复杂度是O(mn)。与之对比DFA引擎的建图时间复杂度O(n^2)，但匹配时没有回溯，所以匹配复杂度只有O(m)，性能差距还是挺大的。 DFA引擎实现的大体流程是先构造NFA(本文内容)，然后用子集构造法将NFA转化为DFA，预计未来我会出一篇博客讲解细节和具体实现。 正则引擎优化 首先DFA引擎是可以继续优化的，使用Hopcroft算法可以进一步将DFA图压缩，更少的状态节点更少的转移边可以实现更好的性能。其次，目前生产级的正则引擎很多都不是单纯用NFA或者DFA实现的，而是二者的结合，不同正则表达式下用不同的引擎可以达到更好的综合性能，简单说NFA图小但要回溯，DFA不需要回溯但有些情况图会特别大。敬请期待我后续博文。
-
发表了文章 2020-03-09
Antlr实战之JSON解析器slowjson
最近一直在学习编译原理，然后就了解到了antlr4这个强大的工具，antlr的全称是(Another Tool for Language Recognition)，是一款很强大的词法和语法分析工具，虽然是用java写成的，但它也能生成c++、go……等语言的代码。它的主要作用就是你可以用巴科斯范式来描述语法规则，然后它帮你生成对应的解析器。 大家都知道实践是最好的学习方式，要快速深刻地理解antlr的操作和相关接口就不得不找一个练手的东西。回想到去年连续报安全漏洞的fastjson，所以我准备霍霍一下json解析器。咱写不出来比fastjson更快、bug更少、更安全的json解析器，难道还写不出来一个bug更多、更慢、更不安全的解析器吗，正面拼不赢咱反其道而行。 为了对标阿里的fastjson，我给它起名 __slowjson__，源码已在github slowjson 欢迎star。为了推广slowjson，我都想好广告词了。 你想升职加薪吗？你想拿年终奖吗？你想成为同事眼中的性能优化小能手吗？ 今天用slowjson，年底做性能优化换回fastjson，十倍性能不是梦，升职加薪准能成。 解析JSON字符串 说这么多进入正题，json解析器该怎么写？实际上你并不需要自己动手写词法分析器、语法分析器……，今天的主角antlr都会帮你生成，你只需要用巴科斯范式把json的语法规则描述清楚就行了，这份描述你可以直接在json.org找到，在antlr的github代码库里也有，二者看起来稍有差别，json官网的规则更详细些。这里我直接用antlr提供的规则描述。 grammar JSON; json : value ; obj : '{' pair (',' pair)* '}' | '{' '}' ; pair : STRING ':' value ; array : '[' value (',' value)* ']' | '[' ']' ; value : STRING | NUMBER | obj | array | 'true' | 'false' | 'null' ; STRING : '"' (ESC | SAFECODEPOINT)* '"' ; fragment ESC : '\\' (["\\/bfnrt] | UNICODE) ; fragment UNICODE : 'u' HEX HEX HEX HEX ; fragment HEX : [0-9a-fA-F] ; fragment SAFECODEPOINT : ~ ["\\\u0000-\u001F] ; NUMBER : '-'? INT ('.' [0-9] +)? EXP? ; fragment INT : '0' | [1-9] [0-9]* ; // no leading zeros fragment EXP : [Ee] [+\-]? INT ; // \- since - means "range" inside [...] WS : [ \t\n\r] + -> skip ; 把这个文件保存成 __JSON.g4__，然后执行下面命令，当然前提是你得正确安装antlr4。 antlr4 JSON.g4 -no-listener -package xyz.xindoo.slowjson 这个时候antlr就会帮你生成json的词法分析器JSONLexer.java和语法分析器JSONParser.java。 private static String jsonStr = "{\"key1\":\"value1\",\"sub\":{\"subkey\":\"subvalue1\"}}"; public static JSONParser.ObjContext parse() { JSONLexer lexer = new JSONLexer(CharStreams.fromString(jsonStr)); CommonTokenStream tokens = new CommonTokenStream(lexer); //生成token JSONParser parser = new JSONParser(tokens); JSONParser.ObjContext objCtx = parser.obj(); // 将token转化为抽象语法树(AST) return new objCtx; } 实际上你只需要写上面这么多代码，就可以完成对一个jsonStr的解析，不过这里解析后的结果是antlr内部封装的抽象语法树，利用antlr的idea插件，我们可以将解析后的AST可视化出来， "{"key1":"value1","sub":{"subkey":"subvalue1"}}"的语法树长下面这样。 JSON字符到JSONObject 虽然已经完成了json字符串的解析，但如果你想像fastjson那样使用，你还得完成对语法树节点到JSONObject的转化。antlr根据语法规则，已经自动帮你生成了每个节点类型，实际上你只需要遍历整个树，然后把每个节点转化为JSONObject或者k-v对就可以了。 package xyz.xindoo.slowjson; import org.antlr.v4.runtime.CharStreams; import org.antlr.v4.runtime.CommonTokenStream; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Random; public class JSONObject { private Map<String, Object> map; public JSONObject() { this.map = new HashMap<>(); } protected JSONObject(JSONParser.ObjContext objCtx) { this.map = new HashMap<>(); for (JSONParser.PairContext pairCtx: objCtx.pair()) { String key = pairCtx.STRING().getText(); map.put(key.substring(1, key.length()-1), pairCtx.value()); } } public JSONObject getJSONObject(String key) { JSONParser.ValueContext value = (JSONParser.ValueContext)map.get(key); if (value == null) { return null; } return new JSONObject(value.obj()); } public String getString(String key) { Object value = map.get(key); if (value == null) { return null; } if (JSONParser.ValueContext.class.isInstance(value)) { JSONParser.ValueContext ctx = (JSONParser.ValueContext)value; String newValue = ctx.STRING().getText(); map.put(key, newValue.substring(1, newValue.length()-1)); } return (String)map.get(key); } public int getInt(String key) { String value = getString(key); if (value == null || "".equals(value)) { return 0; } return Integer.parseInt(value); } public long getLong(String key) { String value = getString(key); if (value == null || "".equals(value)) { return 0L; } return Long.parseLong(value); } public double getDouble(String key) { String value = getString(key); if (value == null || "".equals(value)) { return 0.0; } return Double.parseDouble(value); } public JSONArray getJSONArray(String key) { JSONParser.ValueContext value = (JSONParser.ValueContext)map.get(key); if (value == null) { return null; } return new JSONArray(value.array()); } public void put(String key, Object object) { map.put(key, object); } public static JSONObject parseObject(String text) { JSONLexer lexer = new JSONLexer(CharStreams.fromString(text)); CommonTokenStream tokens = new CommonTokenStream(lexer); JSONParser parser = new JSONParser(tokens); JSONParser.ObjContext objCtx = parser.obj(); return new JSONObject(objCtx); } public static JSONArray parseArray(String text) { if (text == null) { return null; } JSONArray array = JSONArray.parseArray(text); return array; } } 代码中我并没有遍历整个AST并将其转化为JSONObject，而是等到需要的时候再转，实现起来比较方便。看到这里有没有发现slowjson的API和fastjson的很像！ 没错，我就是抄的fastjson，而且我还没抄全。。。 性能测试 接下来做个很随便的性能测试，我随便找了个json字符串，并拉来了slowjson的几个主要竞争对手 fastjson、jackson、gson，测试结果如下： Benchmark Mode Cnt Score Error Units Test.fastjson thrpt 2 235628.511 ops/s Test.gson thrpt 2 237975.534 ops/s Test.jackson thrpt 2 212453.073 ops/s Test.slowjson thrpt 2 29905.109 ops/s 性能只差一个数量级，没我预期的慢……这这么行呢，加上随机自旋…… private static void randomSpin() { Random random = new Random(); int nCPU = Runtime.getRuntime().availableProcessors(); int spins = (random.nextInt()%8 + nCPU) * SPIN_UNIT; while (spins > 0) { spins--; float a = random.nextFloat(); } } 然后在所有get的方法里先调用一次随机自旋，消耗掉cpu。再来测试下性能。 Benchmark Mode Cnt Score Error Units Test.fastjson thrpt 2 349994.543 ops/s Test.gson thrpt 2 318087.884 ops/s Test.jackson thrpt 2 244393.573 ops/s Test.slowjson thrpt 2 2681.164 ops/s 嗯~ 这次差两个量级了，达到了我生产环境的性能标准，可以上线了…… JSONObject到JSON字符串 wait wait 桥都麻袋，目前只实现了json字符串到JSONObject的转换，没有实现从JSONObject到json字符串的转化，功能不完整啊。不过这个也简单，我们按照JSONObject里对象的层次，递归地来做toSting，代码如下。 @Override public String toString() { return toJSONString(); } public String toJSONString() { StringBuilder sb = new StringBuilder(); List<String> list = new ArrayList<>(map.size()); for (Map.Entry<String, Object> entry : map.entrySet()) { String key = entry.getKey(); Object object = entry.getValue(); String value = null; if (String.class.isInstance(object)) { value = "\"" + object.toString() + "\""; } else if (JSONObject.class.isInstance(object)) { value = object.toString(); } else if (JSONArray.class.isInstance(object)) { value = object.toString(); } else { value = ((JSONParser.ValueContext)object).getText(); } list.add("\"" + key + "\":" + value); } sb.append("{"); sb.append(String.join(",", list)); sb.append("}"); return sb.toString(); } JSONArray 上面始终没有提到JSONArray，其实JSONArray也是JSON中重要组成部分，之所以没提是因为JSONArray和JSONObject的实现思路是非常相似的，而且简单多了，我的封装如下。 package xyz.xindoo.slowjson; import org.antlr.v4.runtime.CharStreams; import org.antlr.v4.runtime.CommonTokenStream; import java.util.ArrayList; import java.util.List; import java.util.stream.Collectors; public class JSONArray { private final List<JSONObject> list; public JSONArray() { this.list = new ArrayList<>(); } public JSONArray(List<JSONObject> list) { this.list = new ArrayList<>(list.size()); this.list.addAll(list); } protected JSONArray(JSONParser.ArrayContext arrayCtx) { this.list = arrayCtx.value() .stream() .map(valueContext -> new JSONObject(valueContext.obj())) .collect(Collectors.toList()); } public static JSONArray parseArray(String text) { JSONLexer lexer = new JSONLexer(CharStreams.fromString(text)); CommonTokenStream tokens = new CommonTokenStream(lexer); JSONParser parser = new JSONParser(tokens); JSONParser.ArrayContext arrayCtx = parser.array(); return new JSONArray(arrayCtx); } public JSONObject getJSONObject(int index) { return list.get(index); } public void add(JSONObject jsonObject) { list.add(jsonObject); } @Override public String toString() { return toJSONString(); } public String toJSONString() { StringBuilder sb = new StringBuilder(); sb.append("["); List<String> strList = list.stream().map(JSONObject::toString).collect(Collectors.toList()); sb.append(String.join(",", strList)); sb.append("]"); return sb.toString(); } } Todo 上传至maven中心仓库，方便大家冲KPI，嘿嘿嘿。 完善API，虽然抄了fastjson的api，但确实没抄全。 完善类型，json规范里其实是支持null, boolean, 数字类型的，我这图简单都用了String类型。 完善Excption，目前如果抛Exception都是抛的antlr的，会对用户有误导作用。 增加控制随机自旋的API，性能控制交于用户。 实际上列Todo是为了让slowjson看起来像个项目，至于做不做就随缘了，毕竟不完美才是slowjson最大的特点。。。。 最后所有源码已上传至github slowjson ，欢迎star。
-
发表了文章 2020-02-23
Java volatile 关键词
@[toc] Java中的volatile关键词被用来将变量标记为“存储在内存中”。准确地的讲每次volatile变量的读取和写入都是直接操作内存，而不是cpu cache。 实际上自从java 5之后，__volatile__关键词保证除了volatile变量直接读写内存外，它也被赋予了更多的含义，文章后续会解释。 变量可见性问题 java volatile 关键词保证变量在多线程间变化的可见性。听起来有点抽闲，让我详细说明下。 在多线程应用中，当线程操作非volatile变量时，因为性能上的考虑，每个线程会把变量从内存中拷贝一份到cpu cache里（译者注：读写一次磁盘需要100ns，level1 cache只需要1ns）。如果你的电脑有多个cpu，每个线程运行在不同的cpu上，这就意味着每个线程会将变量拷贝到不同的cpu cache上，如下图。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t6i5t6sU-1582458028402)(http://note.youdao.com/yws/res/34449/F285A84E6F1540149190E27A1FEF12D6)]对于非volatile变量，JVM不会保证每次都写都是从内存中读写，这可能会导致一系列的问题。 试想下这样一个场景，多个线程操作一个包含计数器的变量，如下。 public class SharedObject { public int counter = 0; } 如果只有线程1会增加counter，但线程1和线程2会时不时读counter。 如果counter没有被声明成volatile，jvm不会保证每次counter写cpu cache都会被同步到主存。这就意味着cpu cache里的数据和主存中的有可能不一致，如下图所示。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OYeZckOT-1582458028405)(http://note.youdao.com/yws/res/34465/E8CC82943BB04F76ACB0FCCF8AE85F1A)] 另一个线程线程没法读到最新的变量值，因为数据还没有从cpu cache里同步到主存中，这就是 __可见性问题__，数据的更新对其他线程不可见。 Java volatile可见性保证 Java volatile的诞生就是为了解决可见性问题。把counter变量声明为volatile，所有counter的写入都会被立刻写会到主存里，所有的读都会从主存里直接读。 volatile的用法如下： public class SharedObject { public volatile int counter = 0; } 把变量声明为volatile保证了其他线程对这个变量更新的可见性。 在上面的例子中，线程1修改counter变量，线程2只读不修改，把counter声明为volatile就可以保证线程2读取数据的正确性了。 当时，如果线程1线程2都会修改这个变量，那volatile也无法保证数据的准确性了，后续会详解。 volatile 完全可见性保证 实际上，Java volatile可见性保证超出了volatile变量本身。可见性保证如下。 如果线程A修改一个volatile变量，并且线程B随后读取了同一个变量，你们线程A在写volatile变量前的所有变量操作在线程B读取volatile变化后对线程B都可见。 如果线程A读取了volatile变量，那么在它之后线程A读取都所有变量都将从主存中重新读取。测试代码如下： public class MyClass { private int years; private int months private volatile int days; public void update(int years, int months, int days){ this.years = years; this.months = months; this.days = days; } } update()方法写了三个变量，但只有days被声明为volatile。volatile完全可见性保证的含义是：当线程修改了days，所有的变量都会被同步到主存中，在这里years和months也会被同步到主存中。 在读取years、months、days的时候，你可以这么做。 public class MyClass { private int years; private int months private volatile int days; public int totalDays() { int total = this.days; total += months * 30; total += years * 365; return total; } public void update(int years, int months, int days){ this.years = years; this.months = months; this.days = days; } } 当调用totalDays()方法后，当读取days之后到total变量后，months和years也会从主存中同步。如果按上面的顺序，可以保证你一定读到days,months和years的最新值。 译者注：在上面这个特定读写顺序下，虽然只有days是volatile变量，但days和months也实现了volatile。我猜测原因和cpu硬件有关，volatile变量读取前将要读取的地址在cpu cache中置为失效，这样就保证了每次读取前必须从内存中做数据更新。同样写入后会强制同步cache数据到主存中，这样就实现了volatile语义。但实际上cpu cache在管理cache数据的时候并不是以单个地址为单位，而是以一个block为单位，所以一个block中只要有一个volatile变量，那么读写这个变量都会导致整个block和主存同步。 综上所述，我认为原作者博客中这部分内容不具备参考性，java没有承诺过类似的保证，而且这种可见性估计和具体的cpu实现有关，可能不具备可迁移性，不建议大家这么用。所以如果有多个变量需要可见性保证，还是得都加volatile标识。 指令重排序挑战 Jvm和cpu为性能考虑都可能会最大指令进行重排序，但都会保证语义的一致性。例如： int a = 1; int b = 2; a++; b++; 这些指令在保证语义正确性下可以被重排为下面的次序。 int a = 1; a++; int b = 2; b++; 但当一个变量是volatile的时候，指令重排序会面临一个挑战。 让我们再来看下上面提到的MyClass()的例子。 public class MyClass { private int years; private int months private volatile int days; public void update(int years, int months, int days){ this.years = years; this.months = months; this.days = days; } } 当update()方法写入days变量后，years和months最新的变量也会被写入，但如果jvm像下面一样重新排列了指令： public void update(int years, int months, int days){ this.days = days; this.months = months; this.years = years; } 虽然months和years最终也会被写入到主存中，但却不是实时的，无法保证对其他线程的立即可见。实际语义也会因为指令重排序而改变。 Java 实际上已经解决了这个问题，让我们接着看下去。 Java volatile和有序性(Happens-Before)保证 为了解决重排序的挑战，java volatile关键词可见性之上也保证了"有序性(happens-before)"，有序性的保证含义如下。 对其他变量的读和写如果原来就在volatile变量写之前，就不能重排到volatile变量的写之后。 一个volatile变量写之前的的读/写保证在写之前。请注意有特殊情况，例如，对volatile的写操作之后的其他变量的读/写操作会在对volatile的写操作之前重新排序。而不是反过来。从后到前是允许的，但从前到后是不允许的。 如果对其他变量的读/写如果最初就在对volatile变量的读/写之后，则不能将其重排序到volatile读之前。请注意，在读取volatile变量之前发生的其他变量的读取可以在读取volatile变量之后重新排序。而不是反过来。从前到后是允许的，但从后到前是不允许的。 上面的happens-before保证确保了volatile关键字强可见性。 volatile还不够 尽管volatile保证数据的读写都是从主存中直接操作的，但还有好多情况下volatile语义还是不够的。在前面的例子中，线程1写counter变量，如果将counter声明为volatile，线程2总能看到最新的值。 但事实上，如果多个线程都可以写共享的volatile变量且每次写入的新值不依赖于旧值，依旧可以保证变量值的准确性，换句话说就是有个线程写之前不需要先读一次再在读入的数据上计算出下一个值。 在读出-计算-写入的模式下就无法再保证数值的正确性了，因为在计算的过程中，这个时间差下数据可能已经被其他线程更新过了，多个线程可能竞争写入数据，就会产生数据覆盖的情况。 所以在上面例子中，多个线程共同更新counter的情况下，volatile就无法保证counter数值的准确性了。下面会详细解释这种情况。 想象下线程1读到的counter变量是0，然后它加了1，但没有写回到主存里，而是写在cpu cache里。这个时候线程2同样也看到的counter是0，它也同样加了1并只写到自己的cpu cache中，就像下图这样。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gZS3nLAL-1582458028407)(http://note.youdao.com/yws/res/34603/EA677F096A7E40A9B8119C28F65C07D2)] 这个时候线程1和线程2的数据实际上是不同步的。我们预期的counter实际值应该是2，但在主存中是0，在某个cpu cache中是1。最终某个线程cpu cache中的数据会同步会主存，但数据是错的。 什么时候volatile就足够了？ 像上文中提到的一样，如果有多个线程都读写volatile变量，只用volatile远远不够，你需要用synchronized来保证读和写是一个原子操作。 读和写一个volatile变量不会阻塞其他的线程，为了避免这种情况发生，你必须使用synchronized关键词。 除了synchronized之外，你还可以使用java.util.concurrent包中提供的原子数据类型，比如AtomicLong或者AtomicReferences。如果只有一个线程写入，其他线程都是只读，那么volatile就足够了，但不使用volatile的话是不能保证数据可见性的。 注意：volatile只保证32位和64位变量的可见性。 volatile的性能考量 volatile会导致数据的读写都直接操作主存，读写主存要不读写cpu cache慢的多。volatile也禁止了指令重排序，指令重排序是常见的性能优化手段，所以你应该只在真正需要强制变量可见性时才使用volatile。 原文地址 http://tutorials.jenkov.com/java-concurrency/volatile.html
-
发表了文章 2020-02-05
持续学习——程序猿的军备竞赛
“持续学习”是几乎所有大神都会给菜鸟们的建议之一，这个概念也不是最近被提出来的，早在两千多年前古希腊哲学家梭伦就提出“活到老学到老”，这可算最早的“持续学习”。近些年来持续学习在IT领域里又不不断被提及，程序猿们成为持续学习最大的一群实践者，我从没看到过那个其他行业的普通员工要像程序猿一样学习那么多东西(也可能是我少见多怪)。 究其原因，我觉得有这样几点。 技术涉及面广 有些人在公司承担着很大的责任，可能什么Spark、数据库、网络、linux……都得懂一些，要知道这随便一个方向，都有耗费一个人几个月甚至几年的能力。但幸运的是其实你不用知道太深，够用就好了。但这个“够用”可能是实际工作中够用，但面试中不够用。 轮子多 这点貌似在前端领域尤其明显，像前端框架有什么react、angularjs、vue……，每个框架目的都是为了简化前端的开发，但在具体实现上各自不同，而且各自有各自的优势，缺少一个集大成者的框架。了一个原因是计算机行业细分领域比较多，有些领域比较新，缺少一种工具，然后有人就会跳出来开发一个。另外可能会有人觉得这个工具不好，再开发一个，需要经过长期的技术迭代，才会逐渐有个比较成熟的工具和框架。 技术迭代快 计算机行业一直在追热点，10年11年比较时髦的物联网，后来的大数据与云计算，区块链、机器学习，深度学习，AI，AR，然后今年的5G…… 还有很多比较小众的热点。有些确实是炒作出来的热点，啥实质性的东西也没留下，有些确实给整个技术行业带来的变革。但是追上了某个热点，对于程序猿来说就是加薪 加薪……。毫无疑问，这些热点都是技术快速迭代的产物，要想追上这些热点就意味着你得学习。 行业竞争压力大 计算机行业的高压力很多人都有耳闻，996是经常的事，996ICU几个月前还火了一把。但依旧有好多人拼命往计算机行业里挤，而且之前网络统计，计算机专业成为了高考考生的新宠，为什么？ 其实就是因为程序猿的工资高啊，之前看数据某国内top10院校毕业生5年后的平均薪资，可以被一个渣本院校刚毕业的程序猿秒掉，就这样，大家当然想做程序猿了。但大批人的涌入，各个公司对程序猿的要求也水涨船高，你不学新东西，如果有一天你被裁，你连其他公司面试都过不了。之前在油管看某个硅谷大佬的视频，几年前leetcode你随便刷100-200题，基本上硅谷哪些公司可以随便选，现在远远不够了。 国内在以宇宙条为代表的公司不懈的努力下，刷leetcode的军备竞赛已经逐渐开始了。 互联网行业，随着大家学习的热情越来越高，线上培训也越来越多。像之前，好多人遇到技术问题都是上网查博客，查官方文档，有想法的人还会在问题解决之后写个博客，方便其他人。现在不行了，好多人都等不到问题发生的时候，都想着在问题发生前学会问题的解决方案。这当然是个好事，未雨绸缪，等到问题真正发生时从容应对，但有些不良商家或者个人借机牟取私利，借机推出一些《为什么程序猿都该懂点xxx》之类的课程，赚取你的血汗钱。要知道报班就像办健身卡一样，你是为了提升自己，但公司只是为了赚钱，如果你报了一次都不去，你这钱不就是打水漂了吗。我敢肯定，肯定有好多人报班和办健身卡一样，报了就没下文了。 抛开那些一开始就放弃的人，那些人肯定很难提升自己。我们来说说那些坚持下来的人。你以为你自己把课程里的内容仔仔细细看一遍，你就会了？too young too simple, some time naive！还差的远呢。就拿最近很火的极客时间为例，我感觉好多课程都是在以一种科普的形式来给你讲述某个东西，当然我不是说这种方式不好，但这种方式有个缺点就是可能会有些浅显。所以意味着你学了也许只是学了表面一些花里胡哨的东西，而内功毫无提升。 当然我不是diss极客时间的课程，其实里面有好多好课，我个人已经买了20多个课程了(如果内容质量差我是不会买这么多的)。说下我的感受，有些课程我学的比较轻松，比如《linux性能优化》《计算机网络》，因为我之前做过两年的运维，好多问题是我曾经实际遇到过的，当时我解决不了别人解决了的，但这个问题曾经我心中盘踞了好久的，这些课程给了我曾经苦苦思索好久的答案。我之所以学的轻松，除了老师讲的好之外，比较重要的一点是我理解这些问题之后的背景，我已经有足够的基础了。 当然我肯定也买一些对我毫无用处的课程，比如《机器学习40讲》《go语言核心36讲》…… 很多都没看，都是一时冲动买下来的。因为目前我也不从事这些领域，虽然感兴趣但没有什么精力去学。但是如果我以后有时间精力还是会回过头来看下这些内容的。发表下我对极客时间课程的感受：你能很轻易看懂的不一定是好课，因为你可能很多都会了。你很难看懂的不一定是坏课，可能你基础不够。但是能启发你思考，给你实践带来指引的，一般都是好课。 再回到“报班”这个话题上，首先大家理性报班，不要被标题软文一忽悠就乖乖掏钱，你得评估自身需求，合理规划自己的时间精力之后再报。另外现在在线培训机构课程众多，内容质量良莠不济，做选择时要擦亮自己的眼睛，选择一些口碑平台比较好的课程。 说了这么多，再来说下持续学习的负面。没错“持续学习”，一个积极向上，非常正能量的词，也是有负面的。很多程序猿都会在业余时间刷下脉脉匿名圈，圈子里除了哪些秀offer、秀收入让人很酸的内容外，还有一些是对面试的吐槽。其中比较有名的有那次关于头条面试手写红黑树的吐槽了，现在已经演变成头条自带红黑树buff的梗了。除此之外，还有很多面试都是问的绝大多数人实际工作中完全不会用到的东西。如果所有的面试都这样，再加上近年来各种裁员、996的的新闻，越来越多的程序猿势必会以面试为导向提升自己，可能会花费大量时间精力学习一些完全无用的技能。“面试造火箭，入职拧螺丝”这一说法也不是空穴来风。 为什么越来越多的公司会在面试上来难为应聘者？我简单分析下并谈谈我的看法。 求职者越来越多，其中不乏滥竽充数之人 当竞争越来越激烈的时候，坑就那么多，当然得提升通过的门槛。拿什么来筛，肯定不能用有些人人都能快速学会的东西筛啊，所以好多面试官都会选择用算法题，或者有些框架的细节来面试，这些都是需要大量时间积累大量的练习才能学会的。 喜欢炫技的面试官 首先我觉得这是为人的问题。这种面试官的都是拿自己擅长的冷门知识点去面别人，比人上面说的头条的手写红黑树，我猜测可能就是出自这种人。如果遇到喜欢炫技的面试官，除了自认倒霉外，可以尝试翻转主动权，要让对方绝对你比他牛逼（瞎说的），实在遇到人品不行的，可以反怼回去。 不合格的面试官 有些公司有些团队可能都比较年轻，资历尚浅，不懂的挖掘出候选者背后的潜力。他们常用的面试方式是拿自己会的去面别人，相当于拿自己所在的知识圈去圈候选者的知识圈。人人都有自己的知识盲区，都有自己的擅长点，如果面试官这样面，最后看到的肯定只有交集那部分，很可能会错误估计候选者的能力，错失人才。当然如果面试官的知识圈足够大，这样也没问题，怕就怕面试官自己都能力不够。所以让新人去当面试官，除了对候选人的不尊重外，也可能会得出错误的面试评估。 对候选人不合理的要求 上招聘网站随便找个岗位看下职位要求，我相信他们组内很多人都达不到，这些要求可能就是想让这个岗位显得高大上一些，当然也增加了面试的难度。 如果你想跳槽，你肯定得考虑到上面这些问题。你不可能改变面试官，你能改变的只有自己。面试官不合格，你只能尽可能释放出更多的光辉让他看到。所以努力学习吧，去刷leetcode，去看框架源码，你只要学的比别人多，你肯定能脱颖而出。但是你也别忘记了，别人也在学，所以这就是一场知识的军备竞赛，谁停下来谁死、谁慢谁死、谁低效谁死。 持续学习的人，除了真正想提升自己的，除了面向面试学习的，还有一波面向自我安慰学习的，这些人学习只是为了缓解自己的知识焦虑。我相信大多数人都有一颗上进的心，但很少有人真正有上进的执行力，这些人可能觉得看一篇博客、看一本书就会有提升，以为简单付出就会有收获，所以持续学习成了他们的安慰剂，缓解了他们的知识焦虑。最可恨的是还有好多人靠贩卖知识焦虑来挣钱。 最后，理性看待持续学习，不要随波逐流，不要随意追热点，不要轻易放弃。我刚毕业那会儿，因为技术太差，而且缺乏正确的指引，所以一直啥都想学，当时是做运维，就学linux、python，后来学docker，再后来学java，而且曾经还花时间学过机器学习，没一个学精的，都是略懂皮毛。转开发之后，主力学java，现在也能算是一个合格的java工程师了。学了这么多，最大的体会就是自己的时间精力有限，要学会合理分配利用，还有一点是基础东西才是最优价值的，比如什么正则表达式、gc都在《编译原理》(龙书)里有介绍，感觉编译原理会为你铲除很多技术的学习门槛。
-
发表了文章 2020-02-05
Java弱引用(WeakReferences)
前一段时间当我面试有些来应聘高级java开发工程师岗位的候选人时，在我问的众多问题中，有个问题是“你能告诉我弱引用是啥吗”，我不期望得到像论文中的细节一样的答案。我很可能从有个20多年的老工程师口中得到“嗯……是不是和gc有关”这样的答案，所有哪些至少有5年以上经验的工程师只有两个人知道弱引用的存在，只有其中一个知道引用的相关知识。我甚至尝试给他们解释下看是否有人会有“哦，原来是这样”的反应，然而并没有。我不确定为啥这个知识点鲜为人知，但自Java1.2之后发布的弱引用确实是有个非常有用的功能。 虽然作为一个java工程师我不建议你成为弱引用的专家，但我认为你至少应该知道他们是啥。换句话说你应该知道如何用他们。一直以来弱引用貌似是一个鲜为人知的功能，这里简单介绍下弱引用，以及如何使用和何时使用他们。 强引用(Strong references) 首先我们需要先来复习下强引用，强引用就是你每天在java中用到的最常见的引用，例如： StringBuffer buffer = new StringBuffer(); 上面一行代码创建了一个StringBuffer对象，并且用一个变量buffer存储了它的强引用。是的，就是这么简单，但请耐心听我说完。强引用最重要的部分，它强在哪里？是如何和gc交互的？ 明确的说，如果一个对象通过强引用链可达，它就不会被gc掉。因为谁也不希望垃圾收集器毁掉我们正在用的对象。 强应用太强？ 应用程序使用不能合理的继承的类的情况并不少见，这些类可能被简单标记为final，或者更复杂一些，比如由工厂方法返回的接口，该方法由数量未知(甚至不可知)的具体实现支持。假设你必须使用Widget类，但因为某些原因，不可能添加新功能。 如果你想持续追踪这个对象的额外信息会发生什么？ 这种情况下，假设我们需要跟踪每个Widget的序列号，但是Widget类实际上没有序列号属性，而且因为Widget不能继承，我们也加不了。没关系，我们可以用hashmap。 serialNumberMap.put(widget, widgetSerialNumber); 表面上看起来可以了，但widget的强引用肯定会导致问题。我们必须百分百确定何时Widget的序列号没有在被用了，然后我们可以从map中移除这个实体。否则就会发生内存泄露（如果未移除不用的widget）或者莫名其妙的丢失序列号（如果移除还在用的widget）。这些问题听起来很熟悉吧，这是那些没有gc的语言在尝试管理内存时遇到的问题，在java这样的现代语言中，我们不用担心这个问题。 另一个常见的强引用问题就是缓存中，尤其是缓存像图片那样非常大的数据时。假设你一个给用户提供图片的应用，就像网页设计应用工具。你很自然的想到去缓存那些图片，因为从硬盘加载成本太高了，并且你也希望避免在内存中存在两份图片副本的可能性。 因为图片缓存应该可以避免我们每次都重新加载图片，但你会很快意识到cache任何时候都会包含已经加载到内存中图片的引用。但是，对于普通的强引用，该引用本身将强制图片保留在内存中，这就要求你(如上所述)以某种方式确定何时不再需要该图片，并将其从缓存中删除，这样它就有能被gc掉了。你又被迫重复实现了垃圾收集器的功能。 弱引用(Weak references) 弱引用，简单说就是不是那么能够强到让对象保持在内存中的应用。 弱引用能让你拥有GC的能力，让你能确定对象的可达性。你不用自己做，你只需要像下面一样创建一个弱引用就行了。 WeakReference<Widget> weakWidget = new WeakReference<Widget>(widget); 在代码的其他地方你就可以用weakWidget.get() 真正的Widget对象了。弱应用没有强大到能阻挡GC，所以你会发现当没有强引用指向widget时，weakWidget.get()会返回null。 为了解决上文提到的widget序列号的问题，最简单的方式用就是用WeakHashMap，WeakHashMap和HashMap的工作方式很像，除了WeakHashMap把key替换为弱引用(不是Value)，如果WeakHashMap的key变成了垃圾对象，整个entry会被自动清除。这种方式避免了我提到的陷阱，而且也只是需要把HashMap替换为WeakHashMap就足够了。如果你代码遵循Map的接口标准，甚至都不需要改其他代码。 引用队列(Reference queues) 一旦弱引用开始返回null，它指向的对象肯定已经被gc掉了，弱引用对象也没啥用了。通常这意味着可以做一些清理工作了。对于WeakHashMap而言，它会清理到没用的entry，从而避免存着越来越多的死弱引用。 引用队列让跟踪死引用变得容易。如果你给WeakReference传一个ReferenceQuene的构造参数，当弱引用所指向的对象变成垃圾对象后，引用对象会被自动插入到引用队列中。然后你就可以通过引用队列里的对象来做一些必要的清理工作了。 各种不同强度的应用 Different degrees of weakness 除了上面我提到的弱引用外，其实java总共有4中不同的引用，其引用强度从强到弱分别是强应用、软引用、弱引用、虚引用。我们上文已经讨论过强应用和弱引用，接下来我们看下软引用和虚引用。 软引用(Soft references) 软引用和弱引用很想，除了它并没有弱引用那么急着想扔掉它引用的对象。一个只被弱引用引用的对象会在下次gc的时候被处理掉，但被软引用引用的对象会存在一段时间。 软引用和弱引用行为没啥不同，但在实际过程中，只要内存足够，软引用引用的对象会一直被保留。这是作为缓存很好的一个基础，比如上面提到的图片缓存问题，然后你就可以让gc去考虑哪些对象可达和这些对象消耗了多少内存。 虚引用(Phantom references) 虚引用和软引用、弱引用都不同。他对对象的应用非常弱，弱到你都不能通过get方法获取的对象（get始终返回null）。他只能用来跟踪某个对象何时进入引用队列，只要它进队列了，就说明对象已死，但这和弱引用有什么区别？ 区别就是入队的发生发生时间不一样。弱引用只要对象变成弱可达就入队列，是在finalization和GC之前，理论上，对象可以被某些非正规的finalize复活，但指向其的弱引用则不会。虚引用只会在对象从内存中移除时入队，get()始终返回null是为了防止你复活将死的对象。 那虚引用有什么好的地方？我只列举两点。首先，它可以让你判断是否一个对象已经被从内存中删除，事实上只有这一种方法判断，大部分情况下这个没啥用，但在某些非常特殊的情况下，比如操作大型图像时，它可能会派上用场:如果您确定某个映像应该被gc掉，那么你可以等到它确实被gc之后再尝试加载下一个图片，从而低OutOfMemoryError发生的可能性。 其次，虚引用避免了finalize()通过创建强应用复活一个对象的问题。你说啥？问题是如果一个对象重载了finalize()方法，通过两次gc周期它才能被回收。第一次是确定它是否是垃圾对象，然后它就变成finalization。因为有可能它在finalization过程中会被复活，gc收集器必须重新gc来确保对象被真正去除掉。并且由于finalization可能没有及时发生，因此在对象再被gc掉前可以经历了非常多次的gc周期。 这可能意味着实际清理垃圾对象的严重延迟，这就是为什么即使堆里大多数对象都是垃圾也会导致OutOfMemoryErrors。 用虚引用，这种情况是不可能出现的，绝对没有方法获取到一个指向已死对象的指针（因为已经不在内存里了）。因为虚引用不能用来复活一个对象，这个对象可以在gc的第一阶段发现只有虚引用引用的时候被清理掉。然后你可以在方便的时候处理你需要的任何资源。 可以说，finalize()最开始就不应当被提供。虚引用比finalize()更加高效和安全，放弃finalize()也可以让VM更简单。还有很长的路要走，我承认我大多数时候仍然用finalize()，但好消息是你至少有个选择。 结论 看到这你肯定已经在发恼骚了，因为我正在给你们讲已经有近10年历史的api，而且也没讲新内容。 但这确实是事实，好多java程序猿真的不了解弱引用，而且也需要学习下。我希望你能从这篇文章学到一些东西。 参考资料 Understanding Weak References(原文) 理解Java中的弱引用
-
发表了文章 2020-02-05
局部性原理——各类优化的基石
学过计算机底层原理、了解过很多架构设计或者是做过优化的同学，应该很熟悉局部性原理。即便是非计算机行业的人，在做各种调优、提效时也不得不考虑到局部性，只不过他们不常用局部性一词。如果抽象程度再高一些，甚至可以说地球、生命、万事万物都是局部性的产物，因为这些都是宇宙中熵分布布局、局部的熵低导致的，如果宇宙中处处熵一致，有的只有一篇混沌。 所以什么是 局部性 ？这是一个常用的计算机术语，是指处理器在访问某些数据时短时间内存在重复访问，某些数据或者位置访问的概率极大，大多数时间只访问_局部_的数据。基于局部性原理，计算机处理器在设计时做了各种优化，比如现代CPU的多级Cache、分支预测…… 有良好局部性的程序比局部性差的程序运行得更快。虽然局部性一词源于计算机设计，但在当今分布式系统、互联网技术里也不乏局部性，比如像用redis这种memcache来减轻后端的压力，CDN做素材分发减少带宽占用率…… 局部性的本质是什么？其实就是概率的不均等，这个宇宙中，很多东西都不是平均分布的，平均分布是概率论中几何分布的一种特殊形式，非常简单，但世界就是没这么简单。我们更长听到的发布叫做高斯发布，同时也被称为正态分布，因为它就是正常状态下的概率发布，起概率图如下，但这个也不是今天要说的。 其实有很多情况，很多事物有很强的头部集中现象，可以用概率论中的泊松分布来刻画，这就是局部性在概率学中的刻画形式。上面分别是泊松分布的示意图和概率计算公式，$\lambda$ 表示单位时间(或单位面积)内随机事件的平均发生次数，$e$表示自然常数2.71828..，k表示事件发生的次数。要注意在刻画局部性时$\lambda$表示不命中高频数据的频度，$\lambda$越小，头部集中现象越明显。 局部性分类 局部性有两种基本的分类， 时间局部性 和 空间局部性 ，按Wikipedia的资料，可以分为以下五类，其实有些就是时间局部性和空间局部性的特殊情况。 时间局部性(Temporal locality): 如果某个信息这次被访问，那它有可能在不久的未来被多次访问。时间局部性是空间局部性访问地址一样时的一种特殊情况。这种情况下，可以把常用的数据加cache来优化访存。 空间局部性(Spatial locality): 如果某个位置的信息被访问，那和它相邻的信息也很有可能被访问到。 这个也很好理解，我们大部分情况下代码都是顺序执行，数据也是顺序访问的。 内存局部性(Memory locality): 访问内存时，大概率会访问连续的块，而不是单一的内存地址，其实就是空间局部性在内存上的体现。目前计算机设计中，都是以块/页为单位管理调度存储，其实就是在利用空间局部性来优化性能。 分支局部性(Branch locality) 这个又被称为顺序局部性，计算机中大部分指令是顺序执行，顺序执行和非顺序执行的比例大致是5:1，即便有if这种选择分支，其实大多数情况下某个分支都是被大概率选中的，于是就有了CPU的分支预测优化。 等距局部性(Equidistant locality) 等距局部性是指如果某个位置被访问，那和它相邻等距离的连续地址极有可能会被访问到，它位于空间局部性和分支局部性之间。 举个例子，比如多个相同格式的数据数组，你只取其中每个数据的一部分字段，那么他们可能在内存中地址距离是等距的，这个可以通过简单的线性预测就预测是未来访问的位置。 实际应用 计算机领域关于局部性非常多的利用，有很多你每天都会用到，但可能并没有察觉，另外一些可能离你会稍微远一些，接下来我们举几个例子来深入了解下局部性的应用。 计算机存储层级结构 上图来自极客时间徐文浩的《深入浅出计算机组成原理》，我们以目前常见的普通家用电脑为例 ，分别说下上图各级存储的大小和访问速度，数据来源于https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html。 从最快的L1 Cache到最慢的HDD，其两者的访存时间差距达到了6个数量级，即便是和内存比较，也有几百倍的差距。举个例子，如果CPU在运算是直接从内存中读取指令和数据，执行一条指令0.3ns，然后从内存读下一条指令，等120ns，这样CPU 99%计算时间都会被浪费掉。但就是因为有局部性的存在，每一层都只有少部分数据会被频繁访问，我们可以把这部分数据从底层存储挪到高层存储，可以降低大部分的数据读取时间。 可能有些人好奇，为什么不把L1 缓存做的大点，像内存那么大，直接替代掉内存，不是性能更好吗？虽然是这样，但是L1 Cache单位价格要比内存单位的价格贵好多(大概差200倍)，有兴趣可以了解下DRAM和SRAM。 我们可以通过编写高速缓存友好的代码逻辑来提升我们的代码性能，有两个基本方法 。 让最常见的情况运行的快，程序大部分的运行实际都花在少了核心函数上，而这些函数把大部分时间都花在少量循环上，把注意力放在这些代码上。 让每个循环内缓存不命中率最小。比如尽量不要列遍历二维数组。 MemCache MemCache在大型网站架构中经常看到。DB一般公司都会用mysql，即便是做了分库分表，数据数据库单机的压力还是非常大的，这时候因为局部性的存在，可能很多数据会被频繁访问，这些数据就可以被cache到像redis这种memcache中，当redis查不到数据，再去查db，并写入redis。 因为redis的水平扩展能力和简单查询能力要比mysql强多了，查起来也快。所以这种架构设计有几个好处： 加快了数据查询的平均速度。 大幅度减少DB的压力。 CDN CDN的全称是Content Delivery Network，即内容分发网络(图片来自百度百科) 。CDN常用于大的素材下发，比如图片和视频，你在淘宝上打开一个图片，这个图片其实会就近从CDN机房拉去数据，而不是到阿里的机房拉数据，可以减少阿里机房的出口带宽占用，也可以减少用户加载素材的等待时间。 CDN在互联网中被大规模使用，像视频、直播网站，电商网站，甚至是12306都在使用，这种设计对公司可以节省带宽成本，对用户可以减少素材加载时间，提升用户体验。看到这，有没有发现，CDN的逻辑和Memcache的使用很类似，你可以直接当他是一个互联网版的cache优化。 Java JIT JIT全称是Just-in-time Compiler，中文名为即时编译器，是一种Java运行时的优化。Java的运行方式和C++不太一样，因为为了实现write once, run anywhere的跨平台需求，Java实现了一套字节码机制，所有的平台都可以执行同样的字节码，执行时有该平台的JVM将字节码实时翻译成该平台的机器码再执行。问题在于字节码每次执行都要翻译一次，会很耗时。 图片来自郑雨迪Introduction to Graal ，Java 7引入了tiered compilation的概念，综合了C1的高启动性能及C2的高峰值性能。这两个JIT compiler以及interpreter将HotSpot的执行方式划分为五个级别： level 0：interpreter解释执行 level 1：C1编译，无profiling level 2：C1编译，仅方法及循环back-edge执行次数的profiling level 3：C1编译，除level 2中的profiling外还包括branch（针对分支跳转字节码）及receiver type（针对成员方法调用或类检测，如checkcast，instnaceof，aastore字节码）的profiling level 4：C2编译 通常情况下，一个方法先被解释执行（level 0），然后被C1编译（level 3），再然后被得到profile数据的C2编译（level 4）。如果编译对象非常简单，虚拟机认为通过C1编译或通过C2编译并无区别，便会直接由C1编译且不插入profiling代码（level 1）。在C1忙碌的情况下，interpreter会触发profiling，而后方法会直接被C2编译；在C2忙碌的情况下，方法则会先由C1编译并保持较少的profiling（level 2），以获取较高的执行效率（与3级相比高30%）。 这里将少部分字节码实时编译成机器码的方式，可以提升java的运行效率。可能有人会问，为什么不预先将所有的字节码编译成机器码，执行的时候不是更快更省事吗？首先机器码是和平台强相关的，linux和unix就可能有很大的不同，何况是windows，预编译会让java失去夸平台这种优势。 其次，即时编译可以让jvm拿到更多的运行时数据，根据这些数据可以对字节码做更深层次的优化，这些是C++这种预编译语言做不到的，所以有时候你写出的java代码执行效率会比C++的高。 CopyOnWrite CopyOnWrite写时复制，最早应该是源自linux系统，linux中在调用fork() 生成子进程时，子进程应该拥有和父进程一样的指令和数据，可能子进程会修改一些数据，为了避免污染父进程的数据，所以要给子进程单独拷贝一份。出于效率考虑，fork时并不会直接复制，而是等到子进程的各段数据需要写入才会复制一份给子进程，故此得名 写时复制 。 在计算机的世界里，读写的分布也是有很大的局部性的，大多数情况下读远大于写， 写时复制 的方式，可以减少大量不必要的复制，提升性能。 另外这种方式也不仅仅是用在linux内核中，java的concurrent包中也提供了CopyOnWriteArrayList CopyOnWriteArraySet。像Spark中的RDD也是用CopyOnWrite来减少不必要的RDD生成。 处理 上面列举了那么多局部性的应用，其实还有很多很多，我只是列举出了几个我所熟知的应用，虽然上面这些例子，我们都利用局部性得到了能效、成本上的提升。但有些时候它也会给我们带来一些不好的体验，更多的时候它其实就是一把双刃剑，我们如何识别局部性，利用它好的一面，避免它坏的一面？ 识别 文章开头也说过，局部性其实就是一种概率的不均等性，所以只要概率不均等就一定存在局部性，因为很多时候这种概率不均太明显了，非常好识别出来，然后我们对大头做相应的优化就行了。但可能有些时候这种概率不均需要做很详细的计算才能发现，最后还得核对成本才能考虑是否值得去做，这种需要具体问题具体分析了。 如何识别局部性，很简单，看概率分布曲线，只要不是一条水平的直线，就一定存在局部性。 利用 发现局部性之后对我们而言是如何利用好这些局部性，用得好提升性能、节约资源，用不好局部性就会变成阻碍。而且不光是在计算机领域，局部性在非计算机领域也可以利用。 ##### 性能优化 上面列举到的很多应用其实就是通过局部性做一些优化，虽然这些都是别人已经做好的，但是我们也可以参考其设计思路。 恰巧最近我也在做我们一个java服务的性能优化，利用jstack、jmap这些java自带的分析工具，找出其中最吃cpu的线程，找出最占内存的对象。我发现有个redis数据查询有问题，因为每次需要将一个大字符串解析很多个键值对，中间会产生上千个临时字符串，还需要将字符串parse成long和double。redis数据太多，不可能完全放的内存里，但是这里的key有明显的局部性，大量的查询只会集中在头部的一些key上，我用一个LRU Cache缓存头部数据的解析结果，就可以减少大量的查redis+解析字符串的过程了。 另外也发现有个代码逻辑，每次请求会被重复执行几千次，耗费大量cpu，这种热点代码，简单几行改动减少了不必要的调用，最终减少了近50%的CPU使用。 ##### 非计算机领域 《高能人士的七个习惯》里提到了一种工作方式，将任务划分为重要紧急、不重要但紧急、重要但不紧急、不重要不紧急四种，这种划分方式其实就是按单位时间的重要度排序的，按单位时间的重要度越高收益越大。《The Effective Engineer》里直接用leverage(杠杆率)来衡量每个任务的重要性。这两种方法差不多是类似的，都是优先做高收益率的事情，可以明显提升你的工作效率。 这就是工作中收益率的局部性导致的，只要少数事情有比较大的收益，才值得去做。还有一个很著名的法则__82法则__，在很多行业、很多领域都可以套用，_80%的xxx来源于20%的xxx_ ，80%的工作收益来源于20%的工作任务，局部性给我们的启示“永远关注最重要的20%” 。 避免 上面我们一直在讲如何通过局部性来提升性能，但有时候我们需要避免局部性的产生。 比如在大数据运算时，时常会遇到数据倾斜、数据热点的问题，这就是数据分布的局部性导致的，数据倾斜往往会导致我们的数据计算任务耗时非常长，数据热点会导致某些单节点成为整个集群的性能瓶颈，但大部分节点却很闲，这些都是我们需要极力避免的。 一般我们解决热点和数据切斜的方式都是提供过重新hash打乱整个数据让数据达到均匀分布，当然有些业务逻辑可能不会让你随意打乱数据，这时候就得具体问题具体分析了。感觉在大数据领域，局部性极力避免，当然如果没法避免你就得通过其他方式来解决了，比如HDFS中小文件单节点读的热点，可以通过减少加副本缓解。其本质上没有避免局部性，只增加资源缓解热点了，据说微博为应对明星出轨Redis集群也是采取这种加资源的方式。 参考资料 维基百科局部性原理 《计算机组成与设计》 David A.Patterson / John L.Hennessy 《深入浅出计算机组成原理》 极客时间 徐文浩 《深入理解计算机系统》 Randal E.Bryant / David O'Hallaron 龚奕利 / 雷迎春(译) interactive latencies Introduction to Graal 郑雨迪
-
发表了文章 2020-02-05
一文告诉你CPU分支预测对性能影响有多大
来源于stackoverflow上的一个问题为什么处理有序数组比处理无需数组快，原文中已经有了一些探讨，这里我们首先来复现下结果，然后再解释下为什么！ 我们有如下两段代码，代码看起来都是差不多的，实际上逻辑也是一样的，都是统计数组中小于THRESHOLD数的个数，唯一的区别是一个是在无序数组中统计，另一个是在有序数组中统计。如果两个数组数据源是一致的（数组大小、数据都是一致的），只是一个无序一个有序，你觉得两个函数的性能差距会有多大？ public static void countUnsortedArr() { int cnt = 0; for (int i = 0; i < MAX_LENGTH; i++) { if (arr[i] < THRESHLOD) { cnt++; } } } public static void countSortedArr() { int cnt = 0; for (int i = 0; i < MAX_LENGTH; i++) { if (arrSotred[i] < THRESHLOD) { cnt++; } } } 直觉上，两段代码的逻辑完全一样，因为数据源一致统计结果也是一致的，所以性能上不会有什么差异，但真的是这样吗？我们用OpenJdk中的基准测试工具JMH来测试下。 测试环境 MacBook Pro (13-inch, 2017) CPU: 2.5 GHz Intel Core i7 JMH version: 1.21 VM version: JDK 11, Java HotSpot(TM) 64-Bit Server VM, 11+28测试方式：预热一轮，然后对每个函数做三轮的压测，每轮都是10s 结果如下，SCore表示执行一次这个函所需要的微秒数，数值越小性能越高。 Benchmark Mode Cnt Score Error Units BranchPredictionTest.countSortedArr avgt 3 5212.052 ± 7848.382 us/op BranchPredictionTest.countUnsortedArr avgt 3 31854.238 ± 5393.947 us/op 是不是很出乎意料，明显有序数组中统计快的多，性能差距足足有 6倍 。而且经过我多次测试，这个性能差距非常稳定。是不是感觉不符合逻辑，大多数程序猿都是用高级语言编写代码，其实语言本身就封装了很多底层的细节，事实上，CPU对分支跳转指令是有优化的，这就是我们标题中提到的CPU分支预测。在详细分支预测前先申明一句，本文目标不是讲清楚分支预测，而是告诉你分支预测对性能的影响，想了解更多关于CPU分支预测的内容，文末列出了几篇参考资料。 要说分支预测，还得提到现代CPU的指令流水线模式。如上图所示，现代CPU为了提升指令的吞吐率，将单个指令切分成多个阶段，大致分为__取指(fetch)，译码(decode)，执行(execute)，回写(write-back)__，一条指令不必等上一条完全执行完成就可以开始执行了，就好比工厂中的流水线，可以大大提升指令执行的吞吐率。现代CPU实际上不止4个阶段，像intel和arm的处理器基本上都有十多个阶段，流水线吞吐率的优势更加明显。 但理想很美好，显示很骨干。不是说所有的指令多可以再上一条指令执行完成前就开始执行，可能这条指令会依赖上一条指令的执行结果。为了应对这种数据依赖情况下导致到吞吐率下降，CPU的设计者提出了好多优化方式，比如指令冒险),指令乱序执行,预测，我们今天提到的__分支预测__就属于“预测”的一种。 分支预测的思路也很简单，既然依赖的数据还没算出来，那我就猜一个结果，然后提前开始执行指令，当然也不是随机猜测，现代CPU的预测思路是看前几次预测的结果，就好比前天下雨、昨天也下雨，那我可以简单粗暴的认为今天也下雨，具体细节见文末参考资料。思路很简单，但效果却出奇的好，从Wikipedia的数据我们可以知道现代CPU的分支预测准确率可以到90%以上。 既然准确率不是100%，就意味着有失败的时候。如果CPU发现预测错误会把所有预测之后的指令执行结果全部抛弃，然后从预测分支那重新开始执行，相当于很多指令白跑了，预测失败的代价很高，正常一条指令执行需要10-20个指令周期，预测失败的话可能额外多出30-40个指令周期。 回到我们上面的测试代码，我准备的数据是100w个从0-100w之间的数，然后统计小于50w的数的个数。无序的情况下相当于会有50%的可能性分支预测失败，有序情况下100w次预测只会有一次失败，分支预测失败就是产生性能差距的原因。 性能优化 知道了原因，如何优化性能？既然有序数组最快，是不是我们直接将数组排序，然后做遍历就行？别忘了，额外做排序带来的性能损失远超过分支预测失败带来的性能损失。既然提升分支预测成功率的方式行不通我们就干脆直接干掉会导致分支预测的逻辑，How? 优化1 对于我这个简单的统计逻辑，可以直接用位运算来完成。位运算看着复杂，但其实思路很简单，就是将整数的符号位直接转化成0和1，再加到cnt上。没有了if小于判断，生成的指令里也就没有了jmp指令，从而避免CPU分支预测错误导致的性能消耗。 代码如下： @Benchmark public static void count1() { int cnt = 0; for (int i = 0; i < MAX_LENGTH; i++) { cnt += (-~(THRESHLOD-arr[i]) >> 31); } } 优化2 既然我都对位运算标了优化1，那肯定还有优化2，事实上用 ? : 三目运算符也能优化性能。 public static void count2() { int cnt = 0; for (int i = 0; i < MAX_LENGTH; i++) { cnt += arr[i] < THRESHLOD ? 1 : 0; } } 我们把四种方式放一起再看一下性能差距，位运算毫无疑问是最快的，使用?:三目运算符的方式也相当快，和有序数据统计差不多，可以确定三目运算符也成功避免了分支预测错误代码来的性能损失。 Benchmark Mode Cnt Score Error Units BranchPredictionTest.count1 avgt 3 3807.000 ± 16265.107 us/op BranchPredictionTest.count2 avgt 3 4706.082 ± 19757.705 us/op BranchPredictionTest.countSortedArr avgt 3 4458.783 ± 107.975 us/op BranchPredictionTest.countUnsortedArr avgt 3 30719.090 ± 4517.611 us/op ?:三目运算为什么这么快? ?:表达式里有有小于判断，为什么就没有分支跳转了？这个问题我也疑惑了好久，后来我用C语言代码生成了if和?:逻辑的汇编代码，终于发现了其中的不同。 C代码 int fun1(int x) { int cnt = 0; if (x < 0) { cnt += 1; } return cnt; } int fun2(int x) { int cnt = 0; cnt += x > 0 ? 1 : 0; return cnt; } 汇编代码 .section __TEXT,__text,regular,pure_instructions .build_version macos, 10, 14 .globl _fun1 ## -- Begin function fun1 .p2align 4, 0x90 _fun1: ## @fun1 .cfi_startproc ## %bb.0: pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset %rbp, -16 movq %rsp, %rbp .cfi_def_cfa_register %rbp movl %edi, -4(%rbp) movl $0, -8(%rbp) cmpl $0, -4(%rbp) jge LBB0_2 ## 如果cmpl指令判断的结果是大于等于，就跳转到LBB0_2代码块 ## %bb.1: movl -8(%rbp), %eax addl $1, %eax movl %eax, -8(%rbp) LBB0_2: movl -8(%rbp), %eax popq %rbp retq .cfi_endproc ## -- End function .globl _fun2 ## -- Begin function fun2 .p2align 4, 0x90 _fun2: ## @fun2 .cfi_startproc ## %bb.0: pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset %rbp, -16 movq %rsp, %rbp .cfi_def_cfa_register %rbp xorl %eax, %eax movl %edi, -4(%rbp) movl $0, -8(%rbp) movl -4(%rbp), %edi cmpl $0, %edi movl $1, %edi cmovll %edi, %eax addl -8(%rbp), %eax movl %eax, -8(%rbp) movl -8(%rbp), %eax popq %rbp retq .cfi_endproc ## -- End function .subsections_via_symbols 从汇编代码可以看出，fun2中没有jge指令(jump when greater or equal)，这是一个典型的跳转指令，它会根据cmpl指令的结果来跳转到某个代码块，上文已经提到了，CPU只有在跳转指令时才会做分支预测。而?:的实现完全不同，虽然也有cmpl指令，后面跟的是cmovll指令，这个指令会根据cmp的结果把值放到%eax寄存器中，后续所有的指令都是串行执行的，完全没有跳转指令，所以不会出现分支预测失败导致的性能损失。 和我之前想象的不太一样，__跳转指令不是大小比较产生的，而是像if for这种逻辑分叉产生的，条件跳转只是依赖大小比较的结果而已。__ 完整基准测试代码： @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MICROSECONDS) @State(Scope.Thread) @Fork(3) @Warmup(iterations = 1) @Measurement(iterations = 3) public class BranchPredictionTest { private static Random random = new Random(); private static int MAX_LENGTH = 10_000_000; private static int[] arr; private static int[] arrSotred; private static int THRESHLOD = MAX_LENGTH >> 1; @Setup public static void init() { arr = new int[MAX_LENGTH]; for (int i = 0; i < MAX_LENGTH; i++) { arr[i] = random.nextInt(MAX_LENGTH); } arrSotred = Arrays.copyOf(arr, arr.length); Arrays.sort(arrSotred); } @Benchmark public static void countUnsortedArr() { int cnt = 0; for (int i = 0; i < MAX_LENGTH; i++) { if (arr[i] < THRESHLOD) { cnt++; } } } @Benchmark public static void countSortedArr() { int cnt = 0; for (int i = 0; i < MAX_LENGTH; i++) { if (arrSotred[i] < THRESHLOD) { cnt++; } } } public static void main(String[] args) throws RunnerException { Options opt = new OptionsBuilder() .include(BranchPredictionTest.class.getSimpleName()) .forks(1) .build(); new Runner(opt).run(); } } 结语 CPU分支预测本身是为了提升流水线下避免流水线等待的手段，其实本质上是利用了局部性原理，因为局部性的存在，大多数情况下这个技术本身给性能带来的是正向的(要不然它今天也不会存在了)，所以我们大多数情况下都不需要关注它的存在，还是放心大胆的写代码吧，不要因为我们这篇博客就把所有的if改成?:三目运算，可能对代码可读性的影响远大于性能提升的收益。再次强调下，我今天只是构造了一个极端的数据来验证其性能差异，因为局部性的存在大多数情况下分支预测都是对的。 最后，我还发现如果把上面基准测试中所有的小于号改成大于号，所有的性能差异就都消失了，实际测试结果如下。想不通，看起来是没有分支预测了，有知道的大佬解释下吗？ Benchmark Mode Cnt Score Error Units BranchPredictionTest.count1 avgt 3 3354.059 ± 3995.160 us/op BranchPredictionTest.count2 avgt 3 4047.069 ± 2285.700 us/op BranchPredictionTest.countSortedArr avgt 3 5732.614 ± 6491.716 us/op BranchPredictionTest.countUnsortedArr avgt 3 5251.890 ± 64.813 us/op 参考资料 维基百科指令流水线 维基百科分支预测 CPU分支预测 局部性原理
-
发表了文章 2020-02-05
用正则表达式匹配3的任意倍数
正则表达式能匹配3的任意倍数?(注意是任意倍数) ，我曾经也很震惊，但确实可以。我5年多前练习正则表达式，在Regex Golf这个正则表达式测试网站上发现了这个题，当时完全没有任何头绪，于是我在知乎提问正则表达式如何匹配 3 的倍数 ，但是得到了好多知乎大佬的关注，也上了当天的热榜。 排名第一的答主已经给出了答案和思路，但这么多年来我一直都没看懂，最近学习编译原理，看到正则表达式和DFA，于是仔细研究了一下这个问题，并将问题扩展至匹配N的倍数，最后给出通用解法和代码。 ^(([0369]|[147][0369]*[258])|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))*$ 先给出答案，上面这个正则表达式确实能够匹配任意3的着倍数，再次强调是任意，它确实能匹配任意长度的3的倍数(严谨一点应该是正整数倍，这里不再细究)。 这个正则表达式是这么来的？实际上它是由下面这个DFA(确定性有穷状态机)生成的。 构造DFA 那这个DFA又是如何来的？首先我们来解释下何为DFA(Deterministic finite automata)，首先DFA是一种状态机(automata)，状态机是用来描述状态在不同条件下相互转换的关系，DFA就是在指定条件下，这个状态转换路径是确定且唯一的，这也是它和NFA(Nondeterministic finite automata)的区别。 在正则表达式中，DFA就是在给定某个字符的情况状态如何转移，一般情况下有个初始状态和终止状态，如上图所示状态A就是终止状态，一般用双层环表示，上图并为标识初始状态，其实这里初始状态也是A。在正则表达式对应的DFA中如果当前状态是终止状态，说明正则表达式匹配成功。 如果我们要生成一个匹配N的倍数的DFA，我们的思路是这样的，如果一个数X是N的倍数，那么一定是X % N == 0，这也是我们用来判断X是不是N的倍数方法，我们是把X看成是一个数字一个整体。其实我们这里也是通过取mod是否为零来做的，但我们需要对取mod的过程稍微改造下，举例如下： 0128%3 == (((((0 % 3)*10 + 1) % 3)*10 + 2)*10 + 8) % 3 左右两边的表达式计算结果是等价的，只是我们右边是把每位拆开来单独计算。仔细看看右边的表达式，我们从高位到低位挨个计算mod 3的结果，然后把计算结果乘以10再加到下一位上继续计算，直到后面没有其他数字为止。这种从前到后按位去mod的方式就和正则表达式从前到后按字符去匹配的方式一致了，我们可以按当前状态和新到的数字去计算下一个状态是啥了。 理解了这点，我们就可以开始构造我们的DFA了，我们可以以mod N之后余几做作为状态，比如N为3时，总共有0 1 2 三种状态。每增加一个数字，一个状态都可以转移到了一个状态，例如：状态$S_k$新增数字m的情况下可以转移到状态$S_{(k*10 + m) \% 3}$，接下来我们只需要建立每个状态在每种不同输入下状态转移的关系就行了，伪代码如下。 for i = 0 to N: for j = 0 to N: if i*10 + k) % n == : 建立一条状态Si到Sj的边 将上面建立好的关系绘制成图就得到了如下DFA。 DFA推导出正则表达式 对于上文中匹配3的倍数的DFA，因为状态还算比较少，我们可以人肉推导出来。从上图我们可以看出ABC三个状态是相互依存的关系，我们可以把这种关系列成三个方程式。 A = A[0369] | B[258] | C[147] B = A[147] | B[0369] | C[258] C = A[258] | B[147] | C[0369] 根据Arden定理 若$X = XA | B$则$X = BA*$ ，我们可以再做如下转化。 A = (| B[258] | C[147])[0369]* (1) B = (A[147] | C[258])[0369]* (2) C = (A[258] | B[147])[0369]* (3) 为了让你理解如何计算出A这里我做一个不恰当但很合理的转化，你可以把连接和 | 分别看出四则运算里的乘和加，把ABC分别看成三个未知数，然后我们就得到了一个三元一次方程组，而我们只需要求解出A，求解过程如下： 把(3)带入(1)(2)分别得到： A = (| B[258] | (A[258] | B[147])[0369]*[147])[0369]* (4) B = (A[147] | (A[258] | B[147])[0369]*[258])[0369]* (5) 用分配律展开 (5) 中的竖线得到 B = A[147][0369]* | A[258][0369]*[258][0369]* | B[147][0369]*[258][0369]* 这里再用一次Arden定理 得到 B = A[147][0369]*([147][0369]*[258][0369]*)* | A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)* (6) 把(6)带入到(4)中，并继续用Arden定理 消去右侧的A A = (| B[258] | (A[258] | B[147])[0369]*[147])[0369]* = [0369]* | B[258][0369]* | A[258][0369]*[147][0369]* | B[147][0369]*[147][0369]* = [0369]* | A[147][0369]*([147][0369]*[258][0369]*)*[258][0369]* | A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[258][0369]* | A[258][0369]*[147][0369]* | A[147][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]* | A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]* = [0369]* ( [147][0369]*([147][0369]*[258][0369]*)*[258][0369]* | [258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[258][0369]* | [147][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]* | [258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]* | [258][0369]*[147][0369]* )* = [0369]* ( ( [147][0369]* | [258][0369]*[258][0369]* ) ([147][0369]*[258][0369]*)* ( [258][0369]* | [147][0369]*[147][0369]* ) | [258][0369]*[147][0369]* )* 加上^ 和 $ 就得到了能够匹配3的倍数的正则表达式，推导过程很艰辛，有没有什么方法可以自动把DFA转为正则表达式？ 你可能注意到这个正则表达式和我在文章开头给出的不一样，但这个正则表达式也是正确的。这个正则表达式我自己实在是没推导出来，所以推导过程引用了知乎的内容，但我找到了能够将任意DFA转成正则表达式的方法，文章开头的正则表达式就是我用代码自动生成的，接下来就教你DFA如何自动转正则表达式。 任意DFA转正则表达式的方法 DFA转Regex的核心思想也很简单，逐个删除中间状态(非初始状态和终止状态)，删除过程中把经过这个状态的路径合并到其他路径上，举例如下：我们删除q时，需要对经过状态q的路径做合并。（__·__ 表示连接符，star()表示Kleene star，其实就是正则表达式中的星号，表示出现0次或任意多次） L[p->r] = L[p-q] · star[L[q->q]] · L[q-r] L[r->p] = L[r-q] · star[L[q->q]] · L[q-p] 经装换后得到了如下DFA。如果p为初始状态，r为终止状态，我们可以直接把这个DFA通过如下公式转为正则表达式。 star(L[s,s]) · L[s,f] · star(L[f,s] · star(L[s,s]) · L[s,f] + L[f,f])为了加深理解，我们再举个例子。 在删除完状态2之后，1->3的路径需要并上经过状态2的路径，也就是1->2->3。 同理 3->1的路径需要并上3->2->1，最后DFA变成如下。 用同样的方式删除完状态3之后，我们只剩下状态1，因为状态1即是初始状态，又是终止状态，所以我们要的正则表达式就是0->0的路径。在只剩下初始状态$State_s$和终止状态$State_e$的DFA，$State_s$->$State_e$的路径就可以代表整个原始DFA，这个路径也可以当成正则表达式直接使用。 最后得到了(??+(?+??)(??)*(?+??))*，把+ 替换为 |，并把ab分别替换成状态转移条件就变成一个可用的正则表达式。 在给出完整代码前，我先给出DFA转Regex的伪代码： # 首先需要把两个状态间的多条边合并成1条 for i = 1 to n: for j = 1 to n: if i == j then: L[i,j] := ε else: L[i,j] := ∅ for a in Σ: if trans(i, a, j): L[i,j] := L[i,j] + a remove(k): for i = 1 to n: for j = 1 to n: L[i,j] += L[i,k] . star(L[k,k]) . L[k,j] # 逐个删除中间状态 for i = 1 to n: if not(final(i)) and not(initial(i)): remove(i) 我用Java实现了N任意倍数的DFA生成，并实现了DFA转Regex的功能，完整代码如下。调用getDFA(3)返回的就是绘制成图就是上文中出现多次的DFA，这里我用了HashMap存储各个状态之间的关系。 代码 public class DFA2regex { private final static int INITSTATE = 0; private final static int FINALSTATE = 0; private final static Set<Integer> set = new HashSet<>(); // 生成DFA时我直接将多条边合并成了一条 private static Map<String, String> getDFA(int n) { Map<String, List<String>> map = new HashMap<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < 10; k++) { String key = key(i, j); if (!map.containsKey(key)) { map.put(key, new LinkedList<>()); } if ((i*10 + k) % n == j) { List<String> list = map.get(key); list.add(String.valueOf(k)); } } } } Map<String, String> finalRes = new HashMap<>(); for (HashMap.Entry<String, List<String>> entry : map.entrySet()) { String key = entry.getKey(); String val = entry.getValue().stream().reduce("", String::concat); if (val.length() > 1) { val = "[" + val + "]"; } finalRes.put(key, val); } return finalRes; } private static void remove(int k, int n, Map<String, String> dfa) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (set.contains(i) || set.contains(j)) { continue; } dfa.put(key(i, j), concat(dfa.get(key(i, j)), dfa.get(key(i, k)), star(dfa.get(key(k, k))), dfa.get(key(k, j)))); } } } private static String concat(String s1, String s2, String s3, String s4) { String str1 = s1; String str2 = s2 + s3 + s4; if (str1.length() > 0 && str2.length() > 0) { str1 += "|"; } String res = str1 + str2; if (res.contains("|") || res.contains("*")) { return "(" + res + ")"; } return res; } private static String star(String s) { if (s.equals("") || s.equals("|")) { return ""; } return s + "*"; } private static String key(int s, int e) { return s + "_" + e; } public static void main(String[] args) { int n = 4; Map<String, String> dfa = getDFA(n); for (int i = 0; i < n; i++) { if (INITSTATE != i && FINALSTATE != i) { set.add(i); remove(i, n, dfa); } } System.out.println("^" + star(dfa.get("0_0")) + "$"); } } 写上面代码的过程中我踩到几个坑，正则表达式各运算符是有优先级的，所以需要再状态消除过程中对中间表达式左右添加 () ，为了让生成的正则表达式简洁，我在concat()中做了一些特殊的处理，让最终结果没有多余的_小括号_ 和 | 符号。 彩蛋 这里分别列一下能匹配1-6的任意倍数的正则表达式。为什么不列更多，因为后面生成的正则表达式已经越来越长了，列不下了，7的就已经几千个字符了，有兴趣大家可以自己跑下上面代码生成下。事实上因为正则表达式越来越长，数字越大越耗资源，我自己电脑跑16就跑不出结果了。 1 ^[0123456789]*$ 2 ^([02468]|[13579][13579]*[02468])*$ 3 ^(([0369]|[147][0369]*[258])|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))*$ 4 ^((([048]|[159][37]*[26])|([26]|[159][37]*[048])([26]|[159][37]*[048])*([048]|[159][37]*[26]))|(([37]|[159][37]*[159])|([26]|[159][37]*[048])([26]|[159][37]*[048])*([37]|[159][37]*[159]))(([159]|[37][37]*[159])|([048]|[37][37]*[048])([26]|[159][37]*[048])*([37]|[159][37]*[159]))*(([26]|[37][37]*[26])|([048]|[37][37]*[048])([26]|[159][37]*[048])*([048]|[159][37]*[26])))*$ 5 ^(((([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05])))|((([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49])))((([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49])))*((([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05]))))*$ 6 ^((((([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))|(((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([28]|[39][39]*[28])|(4|[39][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))))|((((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17])))|(((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([17]|[39][39]*[17])|(4|[39][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))))(((([39]|5[39]*[17])|([06]|5[39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17])))|((([28]|5[39]*[06])|([06]|5[39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([17]|[39][39]*[17])|(4|[39][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))))*((((4|5[39]*[28])|([06]|5[39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))|((([28]|5[39]*[06])|([06]|5[39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([28]|[39][39]*[28])|(4|[39][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))))*$ 参考资料 知乎：正则表达式如何匹配 3 的倍数？ How to convert finite automata to regular expressions? Arden定理
-
发表了文章 2020-02-05
布隆过滤器(BloomFilter)原理 实现和性能测试
@TOC布隆过滤器(BloomFilter)是一种大家在学校没怎么学过，但在计算机很多领域非常常用的数据结构，它可以用来高效判断某个key是否属于一个集合，有极高的插入和查询效率(O(1))，也非常省存储空间。当然它也不是完美无缺，它也有自己的缺点，接下来跟随我一起详细了解下BloomFilter的实现原理，以及它优缺点、应用场景，最后再看下Google guava包中BloomFilter的实现，并对比下它和HashSet在不同数据量下内存空间的使用情况。 学过数据结构的人都知道，在计算机领域我们经常通过牺牲空间换时间，或者牺牲时间换空间，BloomFilter给了我们一种新的思路——牺牲准确率换空间。是的，BloomFilter不是100%准确的，它是有可能有误判，但绝对不会有漏判断，说通俗点就是，BloomFilter有可能错杀好人，但不会放过任何一个坏人。BloomFilter最大的优点就是省空间，缺点就是不是100%准确，这点当然和它的实现原理有关。 BloomFilter的原理 在讲解BloomFilter的实现前，我们先来了解下什么叫Bitmap(位图)，先给你一道《编程珠玑》上的题目。 给你一个有100w个数的集合S，每个数的数据大小都是0-100w，有些数据重复出现，这就意味着有些数据可能都没出现过，让你以O(n)的时间复杂度找出0-100w之间没有出现在S中的数，尽可能减少内存的使用。 既然时间复杂度都限制是O(N)了，意味着我们不能使用排序了，我们可以开一个长为100w的int数组来标记下哪些数字出现过，在就标1，不在标0。但对于每个数来说我们只需要知道它在不在，只是0和1的区别，用int(32位)有点太浪费空间了，我们可以按二进制位来用每个int，这样一个int就可以标记32个数，空间占用率一下子减少到原来的1/32，于是我们就有了位图，Bitmap就是用n个二进制位来记录0-m之间的某个数有没有出现过。 Bitmap的局限在于它的存储数据类型有限，只能存0-m之间的数，其他的数据就存不了了。如果我们想存字符串或者其他数据怎么办？其实也简单，只需要实现一个hash函数，将你要存的数据映射到0-m之间就行了。这里假设你的hash函数产生的映射值是均匀的，我们来计算下一个m位的Bitmap到底能存多少数据? 当你在Bitmap中插入了一个数后，通过hash函数计算它在Bitmap中的位置并将其置为1，这时任意一个位置没有被标为1的概率是： $$ 1 - \frac{1}{m} $$ 当插入n个数后，这个概率会变成： $$ (1 - \frac{1}{m})^n $$ 所以任意一个位置被标记成1的概率就是： $$ P_1 = 1 - (1 - \frac{1}{m})^n $$ 这时候你判断某个key是否在这个集合S中时，只需要看下这个key在hash在Bitmap上对应的位置是否为1就行了，因为两个key对应的hash值可能是一样的，所以有可能会误判，你之前插入了a，但是hash(b)==hash(a)，这时候你判断b是否在集合S中时，看到的是a的结果，实际上b没有插入过。 从上面公式中可以看出有 $P_1$ 的概率可能会误判，尤其当n比较大时这个误判概率还是挺大的。 如何减少这个误判率？我们最开始是只取了一个hash函数，如果说取k个不同的hash函数呢！我们每插入一个数据，计算k个hash值，并对k位置为1。在查找时，也是求k个hash值，然后看其是否都为1，如果都为1肯定就可以认为这个数是在集合S中的。 问题来了，用k个hash函数，每次插入都可能会写k位，更耗空间，那在同样的m下，误判率是否会更高呢？我们来推导下。 在k个hash函数的情况下，插入一个数后任意一个位置依旧是0的概率是： $$ (1 - \frac{1}{m})^k $$ 插入n个数后任意一个位置依旧是0的概率是： $$ (1 - \frac{1}{m})^{kn} $$ 所以可知，插入n个数后任意一个位置是1的概率是 $$ 1 - (1 - \frac{1}{m})^{kn} $$ 因为我们用是用k个hash共同来判断是否是在集合中的，可知当用k个hash函数时其误判率如下。它一定是比上面1个hash函数时误判率要小（虽然我不会证明） $$ \left(1-\left[1-\frac{1}{m}\right]^{k n}\right)^{k} < (1 - \left[1 - \frac{1}{m}\right]^n) $$ 维基百科也给出了这个误判率的近似公式（虽然我不知道是怎么来的，所以这里就直接引用了） $$ \left(1-\left[1-\frac{1}{m}\right]^{k n}\right)^{k} \approx\left(1-e^{-k n / m}\right)^{k} $$ 到这里，我们重新发明了Bloomfilter，就是这么简单，说白了Bloomfilter就是在Bitmap之上的扩展而已。对于一个key，用k个hash函数映射到Bitmap上，查找时只需要对要查找的内容同样做k次hash映射，通过查看Bitmap上这k个位置是否都被标记了来判断是否之前被插入过，如下图。 通过公式推导和了解原理后，我们已经知道Bloomfilter有个很大的缺点就是不是100%准确，有误判的可能性。但是通过选取合适的bitmap大小和hash函数个数后，我们可以把误判率降到很低，在大数据盛行的时代，适当牺牲准确率来减少存储消耗还是很值得的。 除了误判之外，BloomFilter还有另外一个很大的缺点 __只支持插入，无法做删除__。如果你想在Bloomfilter中删除某个key，你不能直接将其对应的k个位全部置为0，因为这些位置有可能是被其他key共享的。基于这个缺点也有一些支持删除的BloomFilter的变种，适当牺牲了空间效率，感兴趣可以自行搜索下。 如何确定最优的m和k？ 知道原理后再来了解下怎么去实现，我们在决定使用Bloomfilter之前，需要知道两个数据，一个是要存储的数量n和预期的误判率p。bitmap的大小m决定了存储空间的大小，hash函数个数k决定了计算量的大小，我们当然都希望m和k都越小越好，如何计算二者的最优值，我们大概来推导下。（备注：推导过程来自Wikipedia） 由上文可知，误判率p为 $$ p \approx \left(1-e^{-k n / m}\right)^{k} \ (1) $$ 对于给定的m和n我们想让误判率p最小，就得让 $$ k=\frac{m}{n} \ln2 \ (2) $$ 把(2)式代入(1)中可得 $$ p=\left(1-e^{-\left(\frac{m}{n} \ln 2\right) \frac{n}{m}}\right)^{\frac{m}{n} \ln 2} \ (3) $$ 对(3)两边同时取ln并简化后，得到 $$ \ln p=-\frac{m}{n}(\ln 2)^{2} $$ 最后可以计算出m的最优值为 $$ m=-\frac{n \ln p}{(\ln 2)^{2}} $$ 因为误判率p和要插入的数据量n是已知的，所以我们可以直接根据上式计算出m的值，然后把m和n的值代回到(2)式中就可以得到k的值。至此我们就知道了实现一个bloomfilter所需要的所有参数了，接下来让我们看下Google guava包中是如何实现BloomFilter的。 guava中的BloomFilter BloomFilter无法通过new去创建新对象，而它提供了create静态方法来生成对象，其核心方法如下。 static <T> BloomFilter<T> create( Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) { checkNotNull(funnel); checkArgument( expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions); checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp); checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp); checkNotNull(strategy); if (expectedInsertions == 0) { expectedInsertions = 1; } long numBits = optimalNumOfBits(expectedInsertions, fpp); int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits); try { return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy); } catch (IllegalArgumentException e) { throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e); } } 从代码可以看出，需要4个参数，分别是 funnel 用来对参数做转化,方便生成hash值 expectedInsertions 预期插入的数据量大小，也就是上文公式中的n fpp 误判率，也就是上文公式中的误判率p strategy 生成hash值的策略，guava中也提供了默认策略，一般不需要你自己重新实现 从上面代码可知，BloomFilter创建过程中先检查参数的合法性，之后使用n和p来计算bitmap的大小m（optimalNumOfBits(expectedInsertions, fpp)），通过n和m计算hash函数的个数k（optimalNumOfHashFunctions(expectedInsertions, numBits)）,这俩方法的具体实现如下。 static int optimalNumOfHashFunctions(long n, long m) { // (m / n) * log(2), but avoid truncation due to division! return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); } static long optimalNumOfBits(long n, double p) { if (p == 0) { p = Double.MIN_VALUE; } return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); } 其实就是上文中列出的计算公式。后面插入和查找的逻辑就比较简单了，这里不再赘述，有兴趣可以看下源码，我们这里通过BloomFilter提供的方法列表了解下它的功能就行。 从上图可以看出，BloomFilter除了提供创建和几个核心的功能外，还支持写入Stream或从Stream中重新生成BloomFilter，方便数据的共享和传输。 使用案例 HBase、BigTable、Cassandra、PostgreSQ等著名开源项目都用BloomFilter来减少对磁盘的访问次数，提升性能。 Chrome浏览器用BloomFilter来判别恶意网站。 爬虫用BloomFilter来判断某个url是否爬取过。 比特币也用到了BloomFilter来加速钱包信息的同步。 …… 和HashSet对比 我们一直在说BloomFilter有巨大的存储优势，做个优势到底有多明显，我们拿jdk自带的HashSet和guava中实现的BloomFilter做下对比，数据仅供参考。 测试环境 测试平台 Macguava(28.1)BloomFilter，JDK11(64位) HashSet 使用om.carrotsearch.java-sizeof计算实际占用的内存空间 测试方式 BloomFilter vs HashSet 分别往BloomFilter和HashSet中插入UUID，总计插入100w个UUID，BloomFilter误判率为默认值0.03。每插入5w个统计下各自的占用空间。结果如下，横轴是数据量大小，纵轴是存储空间，单位kb。 可以看到BloomFilter存储空间一直都没有变，这里和它的实现有关，事实上你在告诉它总共要插入多少条数据时BloomFilter就计算并申请好了内存空间，所以BloomFilter占用内存不会随插入数据的多少而变化。相反，HashSet在插入数据越来越多时，其占用的内存空间也会越来越多，最终在插入完100w条数据后，其内存占用为BloomFilter的100多倍。 在不同fpp下的存储表现 在不同的误判率下，插入100w个UUID，计算其内存空间占用。结果如下，横轴是误判率大小，纵轴是存储空间，单位kb。 fpp,size 0.1,585.453125 0.01,1170.4765625 1.0E-3,1755.5 1.0E-4,2340.53125 1.0E-5,2925.5546875 1.0E-6,3510.578125 1.0E-7,4095.6015625 1.0E-8,4680.6328125 1.0E-9,5265.65625 1.0E-10,5850.6796875 可以看出，在同等数据量的情况下，BloomFilter的存储空间和ln(fpp)呈反比，所以增长速率其实不算快，即便误判率减少9个量级，其存储空间也只是增加了10倍。 参考资料 wikipedia bloom filter
-
发表了文章 2020-02-05
Web服务压测神器wrk
wrk是一款开源的高性能http压测工具(也支持https)，非常小巧，可以执行文件只有3M（其中主要是luajit和openssl占用绝大多数空间），别看核心代码3-5年没更新了，但依旧非常好用。虽然很早之前我就知道有这么个工具了，当时学习这个工具的时候我还拿它压测了我们的个人网站xindoo.me，发现mysql性能不行后加了wp-cache，通过cache把我网站的承载能力提升了10多倍。但当时之前简单使用它的初级功能，最近工作中恰好有个http服务需要压测，然后就拿wrk做了。这次使用了wrk lua高级功能实现了压测，我们找到了我们服务的瓶颈，同时也被wrk的超高性能所震惊。 如上图，我用单机(40 cores)压90台机器的集群，压到了31w的QPS，最后压不上去不是因为这台机器抗不住了，而是因为我们服务扛不住了。一个有复杂业务逻辑的服务和一个毫无逻辑的压测相比有失公允，但在压测过程中我也干垮了4台机器的nginx集群（这里nginx也只是个方向代理而已），这足见wrk性能之高。依赖lua脚本，wrk也可以完成复杂http请求的压测，接下来跟我一起了解下wrk的具体使用吧。 wrk的一切内容都在githubhttps://github.com/wg/wrk上，不像其他各种流行的工具包包一样，它并没有提供各个平台的可执行包，只有在mac上可以通过brew安装(应该也不是作者提供的)。好在编译wrk并不难，也不需要什么特殊的配置，git clone https://github.com/wg/wrk.git 或从github上直接下载zip包，进入项目目录后直接执行make，你就可以得到一个可执行文件wrk 。 Options: -c, --connections <N> Connections to keep open # 指定建立多少个网络链接，所有线程复用这些链接 -d, --duration <T> Duration of test # 指定总共起多少个线程 -t, --threads <N> Number of threads to use # 压测持续多长时间 -s, --script <S> Load Lua script file # 指定lua脚本文件，后文会详细介绍 -H, --header <H> Add header to request # 指定http请求的header头 --latency Print latency statistics --timeout <T> Socket/request timeout -v, --version Print version details # 输出版本号，经我测试实际上是用不了的 wrk这个命令提供的参数也不多，运用这些参数可以一行命令完成一个简单http请求的压测，我们以国民检测网络情况最常用的一个网站为例。 > ./wrk https://www.baidu.com -c100 -t10 -d100s Running 20s test @ https://www.baidu.com 10 threads and 100 connections Thread Stats Avg Stdev Max +/- Stdev Latency 145.48ms 91.46ms 1.24s 93.71% Req/Sec 71.11 16.91 144.00 66.95% 14161 requests in 20.09s, 211.91MB read Socket errors: connect 0, read 137, write 0, timeout 0 Requests/sec: 705.00 Transfer/sec: 10.55MB 通过一行shell命令就可以轻而易举完成对百度首页的压测，但如果你需要压一些复杂的http请求时，指定这些参数明显做不到，这时候就需要wrk的高级功能，通过-s指定lua脚本。 当然lua脚本也不是随便写了就能用的，需要按wrk的规范去写wrk才能正常调用。 wrk封装了一个http请求的结构，他是通过wrk这个结构体中的内容去完成一次http请求的，所以你想让http请求不同只需要修改这里面的内容即可，wrk提供了让你修改内容的方法。注意：wrk每个线程都是单独的lua运行环境，互不干扰，没有交集。如果你想在多线程共享一些数据的话，你可以用table这个全局变量来共享。 wrk = { scheme = "http", host = "localhost", port = nil, method = "GET", path = "/", headers = {}, body = nil, thread = <userdata>, } 除了上述结构体外，wrk允许你重写有些给的的function来实现你请求的自定义，以下是其方法名和调用时机。 global setup -- 线程启动前调用一次 global init -- 线程启动后调用一次 global delay -- 每次发起一个请求都会调用 global request -- 每发起一个请求前都会调用 global response -- 获取到请求响应结果后调用 global done -- 压测结束后会调用一次 每个方法都是可选的， 如果你想重定义某个阶段的行为，你可以选择重写该方法，具体方法介绍如下。 setup function setup(thread)是有参数传入的，传入的内容就是当前的线程，setup是在ip地址解析后并且所有线程初始化后，但没用启动前执行的，所以这个时候你可以对thread的构造做一些自定义。 thread.addr - 设置当前线程压测的ip，可以指定线程只压测某个ip thread:get(key) - 读取线程中某个key对应的值，后面可以用key-value执行不同的逻辑 thread:set(key, value) - 在线程环境中设置一个KV thread:stop() - 停掉线程，只能在线程还在运行的情况下调用 init function init(args)是在线程启动后调用，这里是可以传参数的，在启动命令后加-- arg1 arg2，你就可以在init里通过args[1], args[2]获取到arg1和arg2，举例如下。 > ./wrk https://www.baidu.com -c100 -t10 -d100s -- 10 20 function init(args) print(args[1]) -- 输出10 print(args[2]) -- 输出20 end 所以这里可以通过这种方式定义更多的自定义参数，然后通过init(args)做解析，后续可以实现多的功能。 delay function delay()就很简单了，它是为了让你去控制请求发送的之间间隔，如果你想隔10ms发送一次请求，直接return 10就行了，通过delay()可以实现qps大小的控制。 request() function request()主要功能是为了定制每次请求的参数数据，如果你想构造一些复杂的请求，request()是不得不改的，你可以再request()中修改上文wrk 结构体中的所有值，基本上最长改动的就是wrk.header, wrk.path, wrk.body。这里需要注意，request()是要求有返回值的，其返回值是wrk.format(method, path, headers, body)，wrk.format会将这些参数构造成一个http请求可用的请求数据。 response function response(status, headers, body)是在每次wrk收到http请求响应后调用，wrk会将请求响应中的http status、headers和body作为参数传递进来，你可以通过这些参数信息做响应统计、调整压测流量、甚至停止压测……等比较自动化的操作。 done function done(summary, latency, requests)是在压测结束后wrk会调用一次，即便有多个线程也只调用一次。wrk会将压测过程中的统计信息通过参数传递给你，你可以挑其中有用的部分输出。也可以输出你在response()中自行统计的内容。 wrk已经为你提供了以下的统计信息： latency.min -- 最小延迟 latency.max -- 最大延迟 latency.mean -- 平均延迟 latency.stdev -- 延迟的标准差 latency:percentile(99.0) -- 99分位的延迟 latency(i) -- raw value and count summary = { duration = N, -- 运行的时间ms requests = N, -- 总请求数 bytes = N, -- 总过收到的字节数 errors = { connect = N, -- 链接错误数 read = N, -- socket数据读取出错数量 write = N, -- socket数据写入出错数量 status = N, -- http code 大于399的数量 timeout = N -- 超时请求的总数量 } } 流量控制方法 wrk使用了多路复用的技术。多路复用使得用一个线程可以异步发起很多个请求，所以不太好用线程数来控制请求数。但一个http连接同时只能处理一个请求，所以可以按一次请求的latency估算出一个连接可以承载的qps数，调整连接数即可控制压测请求大小qps = 1000/latency * Connectnum。 这里需要注意的是单个线程只能占用一个cpu核心，当cpu到瓶颈时也可能压不上去，需要调整线程数。 另外一个方法，把连接数设置的非常大，让连接数不再是发压的瓶颈，然后调整脚本中的delayTime和线程数，可以精确控制qps。 qps = 1000/delayTime * threadnum 总结 在实际压测过程中，我曾用一个线程压出过几十万qps，也好奇过为什么一个线程能压出这么高的qps。我们每次请求需要5ms，所以按道理一个线程只能压出200qps，那实际上几百倍的差异是如何来的？后来大致了解到wrk的作者使用了多路复用的技术(epoll,kqueue)，每次请求后并不是阻塞等在在那里，而且异步等待结果，同时也可以发起下一个请求，这和redis很像吧，其实wrk的作者代码都是抄的redis的，哈哈。 所以这里要注意-c和-t连接数和参数的设置，一个线程只能占用一个cpu核，如果还没到cpu的瓶颈，决定qps的是连接处和瓶颈响应时间，举个例子，如果只有一个线程，链接数10，平均响应时间10ms，那么一个链接一秒能过100个请求，所以总共能压出1000qps。当cpu到瓶颈后，不管怎么去调大连接数qps都不会上去，这个时候就需要考虑调大线程数了，利用多核心的资源提升qps。 最后附上我们压测中实际使用的lua脚本，结构也比较简单，大家可以大致参考下。 local list = {} local delaytime = 0 -- 默认delay是0ms local filename = "reqdata.txt" -- 默认请求数据文件 setup = function(thread) for k,v in pairs(wrk.addrs) do print(v) end end init = function(args) if (args[1] ~= nil) then delaytime = args[1] -- 启动命令中可以指定延迟时间，如未指定，使用默认文件 end if (args[2] ~= nil) then filename = args[2] -- 启动命令中可以指定请求文件目录，如未指定，使用默认文件 end math.randomseed(os.time()) local i = 0 for line in io.lines(filename) -- 把请求包体读入后写到list里，方便后续使用 do list[i] = line i = i+1 end end request = function() wrk.body = list[math.random(0, #list)] -- 随机使用一个包体 wrk.method = "POST" wrk.scheme = "http" wrk.path = "/appstore/uploadLogSDK" wrk.headers["Content-Type"]="application/x-www-form-urlencoded" return wrk.format() end delay = function() return delaytime end response = function(status, headers, body) --这里我没做特殊统计，只是在调试过程中输出了一些内容 --print(status) --print(body) --print(wrk.format(wrk.method, wrk.path, wrk.headers, wrk.body)) --wrk.thread:stop() end done = function(summary, latency, requests) print("99 latency:"..latency:percentile(99.0)) -- 这里我只是额外输出了99分位的延时，貌似数据不太对 end
-
发表了文章 2020-02-05
10行命令60秒快速定位性能瓶颈
今天为大家翻译一篇来自Netflix技术博客的Linux Performance Analysis in 60,000 Milliseconds，作者是著名linux内核工程师&性能优化专家Brendan D. Gregg和Netflix性能团队。这篇文章会教你怎么用10个常用的linux工具在60秒内完成对性能问题的初步诊断。 当你登录到linux服务器处理性能问题的时候，最开始的一分钟你会做些啥？ Netflix有大量的EC2云服务主机，也有很多检测和排查性能问题的工具。比如像云监控工具Atlas和实例分析工具Vector。这些工具帮我们解决了大部分性能问题，但有时候我们仍需要登录到服务器上运行一些标准的Linux性能排查工具。 综述 在这篇文章中，Netflix团队将展示如何用你随手可及的Linux命令行工具在60s内完成一次性能问题排查。通过以下10个命令，你可以在60秒内对系统的资源使用率和进程运行状况有个整体的了解。首先查看错误和饱和度指标，因为这两者都很容易理解，其次就是查看资源利用率。饱和度是指资源的负载是否超过了它所能承受的负载，这个指标可以反映出出任务队列长度情况或者是任务等待时间的情况。 uptime dmesg | tail vmstat 1 mpstat -P ALL 1 pidstat 1 iostat -xz 1 free -m sar -n DEV 1 sar -n TCP,ETCP 1 top 注意，有些命令需要安装sysstat包。这些命令暴露出来的数据可以帮你完成一次性能优化方法学的实践，这套方法学包括检查所有系统资源(cpu、内存、磁盘……)的使用率、饱和度和错误指标。这些命令也能让你检查所有的地方，通过排除法缩小排查范围，为后续分析指明方向。 文章接下来的部分会介绍这些命令，并给出实际的例子。关于这些命令更详细的介绍请参考相关手册。 1. uptime $ uptime 23:51:26 up 21:31, 1 user, load average: 30.02, 26.43, 19.02 uptime可以快速看到系统的平均负载情况。在Linux中，这些数字表示平均每秒钟处于运行态、可执行态和不可中断状态(通常是磁盘IO)的任务数量。这些数据可以让我们对整个系统资源有个整体的认识，但没有其他工具我们依旧没法理解根因，不过uptime依旧很值得快速瞄一眼。 那这三个数字究竟是什么含义呢！其实这三个数字分别表示1分钟、5分钟、15分钟内的平均负载情况，是通过过去某个时间窗口的数据通过指数衰减求和得到的。这三个数字可以让你了解到过去某段时间的负载状况。比如，如果你上线查性能问题，你看到load1远低于load15，那你可能已经错过这次性能问题了。 在上面的例子中，负载一直在增长，load1已经到30了，而load15只有19，这给了我们很重要的信息，有可能是CPU使用率高了，还得用vmstat和mpstat确认下，这两个命令我们会在3和4中介绍。 2. dmesg|tail $ dmesg | tail [1880957.563150] perl invoked oom-killer: gfp_mask=0x280da, order=0, oom_score_adj=0 [...] [1880957.563400] Out of memory: Kill process 18694 (perl) score 246 or sacrifice child [1880957.563408] Killed process 18694 (perl) total-vm:1972392kB, anon-rss:1953348kB, file-rss:0kB [2320864.954447] TCP: Possible SYN flooding on port 7001. Dropping request. Check SNMP counters. 如果有的话，这条命令将会展示系统最近的10条信息。 找出其中可能导致性能问题的错误。上面这个例子中包含一条因为oom导致进程被kill和tcp丢请求的信息。 不要跳过这步，dmesg非常值得查看。 3. vmstat 1 $ vmstat 1 procs ---------memory---------- ---swap-- -----io---- -system-- ------cpu----- r b swpd free buff cache si so bi bo in cs us sy id wa st 34 0 0 200889792 73708 591828 0 0 0 5 6 10 96 1 3 0 0 32 0 0 200889920 73708 591860 0 0 0 592 13284 4282 98 1 1 0 0 32 0 0 200890112 73708 591860 0 0 0 0 9501 2154 99 1 0 0 0 32 0 0 200889568 73712 591856 0 0 0 48 11900 2459 99 0 0 0 0 32 0 0 200890208 73712 591860 0 0 0 0 15898 4840 98 1 1 0 0 ^C vmstat是有个广泛存在于各类linux系统中的命令(几十年前为BSD所创造的)，可以展出虚拟内存相关的概要信息，每一行都是服务器虚拟内存的关键统计信息。 后面的参数1表示每隔1秒输出一次。注意，输出的第一行是自系统启动以来的数据，而不是前一秒的，所以可以跳过第一行数据。 每列的含义 r: 正在运行和等待运行的进程数量。这个指标可以比load更好的揭示出CPU的负载情况，因为这里不包含I/O进程。如果r值大于CPU核数说明CPU已经饱和。 free: 空闲内存的容量(单位kB)，如果数字多的数不清说明你还有很多空闲内存可用。在下文第7条中的free -m命令可以更直观看到空闲内存情况。 si,so: swap分区的换进和换出。如果数字不是0说明你内存已经不够了，开始使用swap分区了。 us,sy,id,wa,st: 这些是CPU平均使用时长的细致划分，分别是用户时长、系统时长(内核)、空闲时长、等待IO时长、被盗用时长(被其他访客或者Xen盗用，访客有自己独立的驱动域)。 对CPU时间(用户时长+系统时长)的细致划分可以确认CPU是否繁忙。如果等待IO时长搞定不变，说明磁盘IO是瓶颈。这也能解释为什么CPU是空闲的，因为任务都因为等待IO被阻塞掉了。所以你可以将等待I/O看作是CPU空闲的另一种形式，它提供了有关为什么它们是空闲的线索。 对于IO型的进程，系统时长非常重要，如果平均系统时长超过20%就很值得深入探究下了，这可能说明内核IO处理很低效。 上面的例子中，CPU几乎都被用户态所占用，平均CPU利用率也超过90%，这通常没什么大问题，还是重点关注下r这列数据吧。 4. mpstat -P ALL 1 $ mpstat -P ALL 1 Linux 3.13.0-49-generic (titanclusters-xxxxx) 07/14/2015 _x86_64_ (32 CPU) 07:38:49 PM CPU %usr %nice %sys %iowait %irq %soft %steal %guest %gnice %idle 07:38:50 PM all 98.47 0.00 0.75 0.00 0.00 0.00 0.00 0.00 0.00 0.78 07:38:50 PM 0 96.04 0.00 2.97 0.00 0.00 0.00 0.00 0.00 0.00 0.99 07:38:50 PM 1 97.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 2.00 07:38:50 PM 2 98.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 07:38:50 PM 3 96.97 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 3.03 [...] 这个命令把每个CPU核的细致划分出来，从这份数据中可以看出CPU核心负载是否均衡，如果单个CPU核心出现热点说明有单线程的应用。 5. pidstat 1 $ pidstat 1 Linux 3.13.0-49-generic (titanclusters-xxxxx) 07/14/2015 _x86_64_ (32 CPU) 07:41:02 PM UID PID %usr %system %guest %CPU CPU Command 07:41:03 PM 0 9 0.00 0.94 0.00 0.94 1 rcuos/0 07:41:03 PM 0 4214 5.66 5.66 0.00 11.32 15 mesos-slave 07:41:03 PM 0 4354 0.94 0.94 0.00 1.89 8 java 07:41:03 PM 0 6521 1596.23 1.89 0.00 1598.11 27 java 07:41:03 PM 0 6564 1571.70 7.55 0.00 1579.25 28 java 07:41:03 PM 60004 60154 0.94 4.72 0.00 5.66 9 pidstat 07:41:03 PM UID PID %usr %system %guest %CPU CPU Command 07:41:04 PM 0 4214 6.00 2.00 0.00 8.00 15 mesos-slave 07:41:04 PM 0 6521 1590.00 1.00 0.00 1591.00 27 java 07:41:04 PM 0 6564 1573.00 10.00 0.00 1583.00 28 java 07:41:04 PM 108 6718 1.00 0.00 0.00 1.00 0 snmp-pass 07:41:04 PM 60004 60154 1.00 4.00 0.00 5.00 9 pidstat ^C pidstat有点像top命令关于每个进程的统计，和top命令不同的是它是滚动输出而不是清屏输出，这种模式可以很方便看过去的变化情况，也可以很方便的复制粘贴在你排查过程中。 上面的例子中，有两个java进程消耗了大量的CPU，1591%说明这个java进程占用了将近16个核心。 6. iostat -xz 1 $ iostat -xz 1 Linux 3.13.0-49-generic (titanclusters-xxxxx) 07/14/2015 _x86_64_ (32 CPU) avg-cpu: %user %nice %system %iowait %steal %idle 73.96 0.00 3.73 0.03 0.06 22.21 Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz avgqu-sz await r_await w_await svctm %util xvda 0.00 0.23 0.21 0.18 4.52 2.08 34.37 0.00 9.98 13.80 5.42 2.44 0.09 xvdb 0.01 0.00 1.02 8.94 127.97 598.53 145.79 0.00 0.43 1.78 0.28 0.25 0.25 xvdc 0.01 0.00 1.02 8.86 127.79 595.94 146.50 0.00 0.45 1.82 0.30 0.27 0.26 dm-0 0.00 0.00 0.69 2.32 10.47 31.69 28.01 0.01 3.23 0.71 3.98 0.13 0.04 dm-1 0.00 0.00 0.00 0.94 0.01 3.78 8.00 0.33 345.84 0.04 346.81 0.01 0.00 dm-2 0.00 0.00 0.09 0.07 1.35 0.36 22.50 0.00 2.55 0.23 5.62 1.78 0.03 [...] ^C iostat是查看块设备负载和性能信息最好用的工具，可以查看以下信息： r/s, w/s, rkB/s, wkB/s: 设备每秒的读、写次数和读、写数据量(kB)。这些指标可以量化IO设备负载，有些性能问题可能就是因为负载过高导致的。 await: 等待IO的毫秒数。这是应用程序所感受到的时间，包括排队时间和等待时间。如果超过平均预期时间说明设备已饱和或者设备故障。 avgqu-sz: 设备的平均请求数。如果值大于1可能是设备已饱和(尽管设备通常可以并行操作请求，特别是位于多个后端磁盘前的虚拟设备)。 %util: 设备的使用率。这是设备真实忙碌的时间比例，展示了每秒设备实际工作的时间。超过60%可能导致设备性能降低，当然这也取决于设备自身。接近100%说明设备已经饱和了。 如果存储设备只是由多块磁盘组成的逻辑设备，100%的利用率也仅仅意味着100%的时间用来处理IO了，后端物理磁盘远远没有达到它们所能处理的性能极限。 请记住，磁盘I/O性能差不一定导致应用程序出问题。许多技术通常使用了异步I/O，这样应用程序就不会被阻塞也感受不到延迟(例如，预读和写Buffer)。 7. free -m $ free -m total used free shared buffers cached Mem: 245998 24545 221453 83 59 541 -/+ buffers/cache: 23944 222053 Swap: 0 0 0 最右边有两列buffers和cached buffers: 缓冲区，用于块设备IO。 cached: 内存页缓存，用在文件系统。 我们只需要检查下它们的大小是否接近于0，接近0可能导致更高的磁盘I/O(使用iostat进行确认)和更差的性能。上面的例子看起来很好，每一项都有很多兆。 “-/+ buffers/cache” 为已使用和空闲内存大小提供了明确的值。linux用空闲内存作为cache，如果应用需要更多内存也可以很快释放掉，所以cached部分的内存也应当包含在free列里，这一行数据就是这样，这里可能让人摸不着头脑，更详细内容可以查看这个网页linuxatemyram.com/。 如果linux系统用了ZFS会更让人迷惑，因为ZFS有自己的文件系统缓存，free -m 并不能反映出这些文件缓存的大小。所以可能出现看起来内存不足，但实际上可以按需从ZFS cache里释放一些内存。 8. sar -n DEV 1 $ sar -n DEV 1 Linux 3.13.0-49-generic (titanclusters-xxxxx) 07/14/2015 _x86_64_ (32 CPU) 12:16:48 AM IFACE rxpck/s txpck/s rxkB/s txkB/s rxcmp/s txcmp/s rxmcst/s %ifutil 12:16:49 AM eth0 18763.00 5032.00 20686.42 478.30 0.00 0.00 0.00 0.00 12:16:49 AM lo 14.00 14.00 1.36 1.36 0.00 0.00 0.00 0.00 12:16:49 AM docker0 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 12:16:49 AM IFACE rxpck/s txpck/s rxkB/s txkB/s rxcmp/s txcmp/s rxmcst/s %ifutil 12:16:50 AM eth0 19763.00 5101.00 21999.10 482.56 0.00 0.00 0.00 0.00 12:16:50 AM lo 20.00 20.00 3.25 3.25 0.00 0.00 0.00 0.00 12:16:50 AM docker0 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 ^C 这个命令可以查看网络吞吐量，rxkB/s和txkB/s，可以度量工作负载，也可以查看是否达到了限制。在上面的例子中，eth0接收达到了22MB/s，也就是176Ms/S(远低于1Gb/s的限制)。 这个版本也有个%ifutil来表示设备利用率(全双工的两个方向的最大值)，我们用Brendan的nicstat也可以查看。就像使用nicstat一样，很难得到正确的结果，而且在本例中似乎不能正常工作(0.00)。 9. sar -n TCP,ETCP 1 $ sar -n TCP,ETCP 1 Linux 3.13.0-49-generic (titanclusters-xxxxx) 07/14/2015 _x86_64_ (32 CPU) 12:17:19 AM active/s passive/s iseg/s oseg/s 12:17:20 AM 1.00 0.00 10233.00 18846.00 12:17:19 AM atmptf/s estres/s retrans/s isegerr/s orsts/s 12:17:20 AM 0.00 0.00 0.00 0.00 0.00 12:17:20 AM active/s passive/s iseg/s oseg/s 12:17:21 AM 1.00 0.00 8359.00 6039.00 12:17:20 AM atmptf/s estres/s retrans/s isegerr/s orsts/s 12:17:21 AM 0.00 0.00 0.00 0.00 0.00 ^C 这个命令可以查看tcp指标数据，包括： active/s: 每秒钟本地发起的主动连接数(比如调用 connect())。 passive/s: 每秒钟收到的远程被动连接数(比如调用accept())。 retrans/s: 每秒钟tcp重传数。 主动和被动连接数通常可以作为服务器负载的粗略度量:新接受连接的数量(被动)和下游连接的数量(主动)。可以简单将active视为出，将passive视为入，但这并不完全正确(例如，localhost发起到localhost的连接)。 重传数可以看做是网络或者服务问题的一个信号，可能是网络不可靠(比如公网)，或者是因为服务已经过载而导致的丢包。上面这个例子中每秒只有一个新建连接。 10. top $ top top - 00:15:40 up 21:56, 1 user, load average: 31.09, 29.87, 29.92 Tasks: 871 total, 1 running, 868 sleeping, 0 stopped, 2 zombie %Cpu(s): 96.8 us, 0.4 sy, 0.0 ni, 2.7 id, 0.1 wa, 0.0 hi, 0.0 si, 0.0 st KiB Mem: 25190241+total, 24921688 used, 22698073+free, 60448 buffers KiB Swap: 0 total, 0 used, 0 free. 554208 cached Mem PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 20248 root 20 0 0.227t 0.012t 18748 S 3090 5.2 29812:58 java 4213 root 20 0 2722544 64640 44232 S 23.5 0.0 233:35.37 mesos-slave 66128 titancl+ 20 0 24344 2332 1172 R 1.0 0.0 0:00.07 top 5235 root 20 0 38.227g 547004 49996 S 0.7 0.2 2:02.74 java 4299 root 20 0 20.015g 2.682g 16836 S 0.3 1.1 33:14.42 java 1 root 20 0 33620 2920 1496 S 0.0 0.0 0:03.82 init 2 root 20 0 0 0 0 S 0.0 0.0 0:00.02 kthreadd 3 root 20 0 0 0 0 S 0.0 0.0 0:05.35 ksoftirqd/0 5 root 0 -20 0 0 0 S 0.0 0.0 0:00.00 kworker/0:0H 6 root 20 0 0 0 0 S 0.0 0.0 0:06.94 kworker/u256:0 8 root 20 0 0 0 0 S 0.0 0.0 2:38.05 rcu_sched top命令中包含很多我们前面已经提到过的指标，可以方便地运行它来查看指标的变化。 top的一个缺点是，top不像vmstat和pidstat等提供滚动输出的工具一样，它看不到之前的数据。如果你没有足够快地暂停输出(Ctrl-S暂停，Ctrl-Q继续)，屏幕上的数据就会被清除，你很难截取到证据。 后续分析 还有很多命令行工具和方法可以深入挖掘，参见Brendan的Linux性能工具指南，里面列出了超过40种工具，包含了观测、基准测试、调优、静态性能调优、概要分析和追踪。
2022年05月
-
05.03 19:54:25
发表了文章
2022-05-03 19:54:25
如何写出高性能代码之优化内存回收(GC)
如何写出高性能代码之优化内存回收(GC)
2020年07月
-
07.23 17:40:22发表了文章
2020-07-23 17:40:22
JDK11现存性能bug(JDK-8221393)深度解析
JDK11现存性能bug(JDK-8221393)深度解析
-
发表了文章
2022-05-03
如何写出高性能代码之优化内存回收(GC)
-
发表了文章
2020-07-23
JDK11现存性能bug(JDK-8221393)深度解析
-
发表了文章
2020-06-03
从0到1打造正则表达式执行引擎(二)
-
发表了文章
2020-06-03
从0到1打造正则表达式执行引擎(一)
-
发表了文章
2020-03-09
Antlr实战之JSON解析器slowjson
-
发表了文章
2020-02-23
Java volatile 关键词
-
发表了文章
2020-02-05
持续学习——程序猿的军备竞赛
-
发表了文章
2020-02-05
Java弱引用(WeakReferences)
-
发表了文章
2020-02-05
局部性原理——各类优化的基石
-
发表了文章
2020-02-05
一文告诉你CPU分支预测对性能影响有多大
-
发表了文章
2020-02-05
用正则表达式匹配3的任意倍数
-
发表了文章
2020-02-05
布隆过滤器(BloomFilter)原理 实现和性能测试
-
发表了文章
2020-02-05
Web服务压测神器wrk
-
发表了文章
2020-02-05
10行命令60秒快速定位性能瓶颈
滑动查看更多
暂无更多信息
暂无更多信息