2017年6月23日

from:http://blog.csdn.net/MoreWindows/article/category/859207 

【白话经典算法系列之十七】 数组中只出现一次的数

数组A中,除了某一个数字x之外,其他数字都出现了三次,而x出现了一次。请给出最快的方法找到x。 这个题目非常有意思,在本人博客中有《位操作基础篇之位操作全面总结》这篇文章介绍了使用位操作的异或来解决——数组中其他数字出现二次,而x出现一次,找出x。有《【白话经典算法系列之十二】数组中只出现1次的两个数字(百度面试题)》这边文章介绍了分组异或的方法来解决——数组中其他数字出现二次,而x和y出现一次,找出x和y。而这个题目则是其他数字出现3次,x出现一次。...
2013-10-21 11:49 阅读(32100) 评论(34)
首先看看题目要求: 给定一个无序的整数数组,怎么找到第一个大于0,并且不在此数组的整数。比如[1,2,0]返回3,[3,4,-1,1]返回2,[1, 5, 3, 4, 2]返回6,[100, 3, 2, 1, 6,8, 5]返回4。要求使用O(1)空间和O(n)时间。 这道题目初看没有太好的思路,但是借鉴下《白话经典算法系列之十一道有趣的GOOGLE面试题》这篇文章,我们不发现使用“基数排序”正好可以用来解决这道题目...
2013-10-15 10:17 阅读(13580) 评论(11)
【白话经典算法系列之十五】“一步千里”之数组找数 有这样一个数组A,大小为n,相邻元素差的绝对值都是1。如:A={4,5,6,5,6,7,8,9,10,9}。现在,给定A和目标整数t,请找到t在A中的位置。除了依次遍历,还有更好的方法么?...
2013-09-02 12:57 阅读(25918) 评论(39)
【白话经典算法系列之十三】随机生成和为S的N个正整数——投影法      随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。    以生成和为20的4个数为例,可以先生成随机生成0到20之间的三个数字再排序,假设得到了4,7,18。然后在X-Y数轴上画出这三个数,如下图:然后将这些数值投影到Y轴上,可得下图:由图很容易看出AB,BC,CD,DE这四段的长度...
2013-01-04 13:46 阅读(15710) 评论(46)
微博http://weibo.com/MoreWindows已开通,欢迎关注。本系列文章地址:http://blog.csdn.net/MoreWindows/article/category/859207首先来看题目要求:在一个数组中除两个数字只出现1次外,其它数字都出现了2次, 要求尽快找出这两个数字。    考虑下这个题目的简化版——数组中除一个数字只出现1次外,其它数字都成对出现,要求尽快...
2012-11-27 09:17 阅读(35498) 评论(51)
微博http://weibo.com/MoreWindows已开通,欢迎关注。本系列文章地址:http://blog.csdn.net/MoreWindows/article/category/859207 上一篇《白话经典算法系列之十一道有趣的GOOGLE面试题》中对一道有趣的GOOGLE面试题进行了详细的讲解,使用了类似于基数排序的做法在O(N)的时间复杂度和O(1)的空间复杂度完成了题目的要...
2012-11-23 07:57 阅读(24806) 评论(52)
微博http://weibo.com/MoreWindows已开通,欢迎关注。最近在微博上看到一道有趣的GOOGLE面试题,见下图:文字版:一个大小为n的数组,里面的数都属于范围[0, n-1],有不确定的重复元素,找到至少一个重复元素,要求O(1)空间和O(n)时间。     这个题目要求用O(n)的时间复杂度,这意味着只能遍历数组一次。同时还要寻找重复元素,很容易想到建立哈希表来完成,遍历数组...
2012-11-21 09:03 阅读(47907) 评论(87)
首先来看看原题 微软2010年笔试题在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序数。如{2,4,3,1}中,2和1,4和3,4和1,3和1是逆序数对,因此整个数组的逆序数对个数为4,现在给定一数组,要求统计出该数组的逆序数对个数。 计算数列的逆序数对个数最简单的方便就最从前向后依次统计每个数字与它后面...
2012-10-15 09:15 阅读(30367) 评论(36)
在我的博客对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法进行了详细的讲解,并做成了电子书以供大家下载。下载地址为:http://download.csdn.net/detail/morewindows/4443208。       有网友提议到这本《MoreWindows白话经典算法之七大排序》电子书讲解细致用来平时学习是非常好的,但是页数有22页...
2012-09-10 10:08 阅读(42997) 评论(26)
堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。二叉堆的定义二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性:1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父...
2011-08-22 20:04 阅读(338481) 评论(188)
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考试如软考,考研中也常常出现快速排序的身影。总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话解释,希望对大家理解有帮助,达到快速排序,快...
2011-08-13 17:19 阅读(418202) 评论(284)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。//将有序数组a[]和b[]合并到c[]中 void MemeryArra...
2011-08-11 11:01 阅读(275147) 评论(154)
直接选择排序和直接插入排序类似,都将数据分为有序区和无序区,所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区,而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。   设数组为a[0…n-1]。 1.      初始时,数组全为无...
2011-08-09 11:15 阅读(29055) 评论(38)
希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。   该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增...
2011-08-08 11:41 阅读(148913) 评论(82)
直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。   设数组为a[0…n-1]。 1.      初始时,a[0]自成1个有序区,无序区为a[1..n-1]。...
2011-08-06 19:27 阅读(118661) 评论(81)
冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。 2.这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置。 3.N=N-1,如果N...
2011-08-06 19:20 阅读(166505) 评论(94)
posted @ 2017-06-23 11:17 小马歌 阅读(10) | 评论 (0)编辑 收藏

2017年6月8日

from:http://blog.csdn.net/liaodehong/article/details/51605457

本文将深入浅出地讲解 JIT 编译器在 JVM 中的运作原理,使读者能够更好的理解 Java 底层机制并且为读者在 Java 性能优化领域打开更广的视野。

JIT 简介

JIT 是 just in time 的缩写, 也就是即时编译编译器。使用即时编译器技术,能够加速 Java 程序的执行速度。下面,就对该编译器技术做个简单的讲解。

首先,我们大家都知道,通常通过 javac 将程序源代码编译,转换成 java 字节码,JVM 通过解释字节码将其翻译成对应的机器指令,逐条读入,逐条解释翻译。很显然,经过解释执行,其执行速度必然会比可执行的二进制字节码程序慢很多。为了提高执行速度,引入了 JIT 技术。

在运行时 JIT 会把翻译过的机器码保存起来,以备下次使用,因此从理论上来说,采用该 JIT 技术可以接近以前纯编译技术。下面我们看看,JIT 的工作过程。

JIT 编译过程

当 JIT 编译启用时(默认是启用的),JVM 读入.class 文件解释后,将其发给 JIT 编译器。JIT 编译器将字节码编译成本机机器代码,下图展示了该过程。

图 1. JIT 工作原理图
图 1. JIT 工作原理图

回页首

Hot Spot 编译

当 JVM 执行代码时,它并不立即开始编译代码。这主要有两个原因:

首先,如果这段代码本身在将来只会被执行一次,那么从本质上看,编译就是在浪费精力。因为将代码翻译成 java 字节码相对于编译这段代码并执行代码来说,要快很多。

当然,如果一段代码频繁的调用方法,或是一个循环,也就是这段代码被多次执行,那么编译就非常值得了。因此,编译器具有的这种权衡能力会首先执行解释后的代码,然后再去分辨哪些方法会被频繁调用来保证其本身的编译。其实说简单点,就是 JIT 在起作用,我们知道,对于 Java 代码,刚开始都是被编译器编译成字节码文件,然后字节码文件会被交由 JVM 解释执行,所以可以说 Java 本身是一种半编译半解释执行的语言。Hot Spot VM 采用了 JIT compile 技术,将运行频率很高的字节码直接编译为机器指令执行以提高性能,所以当字节码被 JIT 编译为机器码的时候,要说它是编译执行的也可以。也就是说,运行时,部分代码可能由 JIT 翻译为目标机器指令(以 method 为翻译单位,还会保存起来,第二次执行就不用翻译了)直接执行。

第二个原因是最优化,当 JVM 执行某一方法或遍历循环的次数越多,就会更加了解代码结构,那么 JVM 在编译代码的时候就做出相应的优化。

我们将在后面讲解这些优化策略,这里,先举一个简单的例子:我们知道 equals() 这个方法存在于每一个 Java Object 中(因为是从 Object class 继承而来)而且经常被覆写。当解释器遇到 b = obj1.equals(obj2) 这样一句代码,它则会查询 obj1 的类型从而得知到底运行哪一个 equals() 方法。而这个动态查询的过程从某种程度上说是很耗时的。

寄存器和主存

其中一个最重要的优化策略是编译器可以决定何时从主存取值,何时向寄存器存值。考虑下面这段代码:

清单 1. 主存 or 寄存器测试代码
public class RegisterTest {  private int sum;   public void calculateSum(int n) {  for (int i = 0; i < n; ++i) {  sum += i;  }  } }

在某些时刻,sum 变量居于主存之中,但是从主存中检索值是开销很大的操作,需要多次循环才可以完成操作。正如上面的例子,如果循环的每一次都是从主存取值,性能是非常低的。相反,编译器加载一个寄存器给 sum 并赋予其初始值,利用寄存器里的值来执行循环,并将最终的结果从寄存器返回给主存。这样的优化策略则是非常高效的。但是线程的同步对于这种操作来说是至关重要的,因为一个线程无法得知另一个线程所使用的寄存器里变量的值,线程同步可以很好的解决这一问题,有关于线程同步的知识,我们将在后续文章中进行讲解。

寄存器的使用是编译器的一个非常普遍的优化。

回到之前的例子,JVM 注意到每次运行代码时,obj1 都是 java.lang.String 这种类型,那么 JVM 生成的被编译后的代码则是直接调用 String.equals() 方法。这样代码的执行将变得非常快,因为不仅它是被编译过的,而且它会跳过查找该调用哪个方法的步骤。

当然过程并不是上面所述这样简单,如果下次执行代码时,obj1 不再是 String 类型了,JVM 将不得不再生成新的字节码。尽管如此,之后执行的过程中,还是会变的更快,因为同样会跳过查找该调用哪个方法的步骤。这种优化只会在代码被运行和观察一段时间之后发生。这也就是为什么 JIT 编译器不会理解编译代码而是选择等待然后再去编译某些代码片段的第二个原因。

回页首

初级调优:客户模式或服务器模式

JIT 编译器在运行程序时有两种编译模式可以选择,并且其会在运行时决定使用哪一种以达到最优性能。这两种编译模式的命名源自于命令行参数(eg: -client 或者 -server)。JVM Server 模式与 client 模式启动,最主要的差别在于:-server 模式启动时,速度较慢,但是一旦运行起来后,性能将会有很大的提升。原因是:当虚拟机运行在-client 模式的时候,使用的是一个代号为 C1 的轻量级编译器,而-server 模式启动的虚拟机采用相对重量级代号为 C2 的编译器。C2 比 C1 编译器编译的相对彻底,服务起来之后,性能更高。

通过 java -version 命令行可以直接查看当前系统使用的是 client 还是 server 模式。例如:

图 2. 查看编译模式
图 2. 查看编译模式

回页首

中级编译器调优

大多数情况下,优化编译器其实只是选择合适的 JVM 以及为目标主机选择合适的编译器(-cient,-server 或是-xx:+TieredCompilation)。多层编译经常是长时运行应用程序的最佳选择,短暂应用程序则选择毫秒级性能的 client 编译器。

优化代码缓存

当 JVM 编译代码时,它会将汇编指令集保存在代码缓存。代码缓存具有固定的大小,并且一旦它被填满,JVM 则不能再编译更多的代码。

我们可以很容易地看到如果代码缓存很小所具有的潜在问题。有些热点代码将会被编译,而其他的则不会被编译,这个应用程序将会以运行大量的解释代码来结束。

这是当使用 client 编译器模式或分层编译时很频繁的一个问题。当使用普通 server 编译器模式时,编译合格的类的数量将被填入代码缓存,通常只有少量的类会被编译。但是当使用 client 编译器模式时,编译合格的类的数量将会高很多。

在 Java 7 版本,分层编译默认的代码缓存大小经常是不够的,需要经常提高代码缓存大小。大型项目若使用 client 编译器模式,则也需要提高代码缓存大小。

现在并没有一个好的机制可以确定一个特定的应用到底需要多大的代码缓存。因此,当需要提高代码缓存时,这将是一种凑巧的操作,一个通常的做法是将代码缓存变成默认大小的两倍或四倍。

可以通过 –XX:ReservedCodeCacheSize=Nflag(N 就是之前提到的默认大小)来最大化代码缓存大小。代码缓存的管理类似于 JVM 中的内存管理:有一个初始大小(用-XX:InitialCodeCacheSize=N 来声明)。代码缓存的大小从初始大小开始,随着缓存被填满而逐渐扩大。代码缓存的初始大小是基于芯片架构(例如 Intel 系列机器,client 编译器模式下代码缓存大小起始于 160KB,server 编译器模式下代码缓存大小则起始于 2496KB)以及使用的编译器的。重定义代码缓存的大小并不会真正影响性能,所以设置 ReservedCodeCacheSize 的大小一般是必要的。

再者,如果 JVM 是 32 位的,那么运行过程大小不能超过 4GB。这包括了 Java 堆,JVM 自身所有的代码空间(包括其本身的库和线程栈),应用程序分配的任何的本地内存,当然还有代码缓存。

所以说代码缓存并不是无限的,很多时候需要为大型应用程序来调优(或者甚至是使用分层编译的中型应用程序)。比如 64 位机器,为代码缓存设置一个很大的值并不会对应用程序本身造成影响,应用程序并不会内存溢出,这些额外的内存预定一般都是被操作系统所接受的。

编译阈值

在 JVM 中,编译是基于两个计数器的:一个是方法被调用的次数,另一个是方法中循环被回弹执行的次数。回弹可以有效的被认为是循环被执行完成的次数,不仅因为它是循环的结尾,也可能是因为它执行到了一个分支语句,例如 continue。

当 JVM 执行一个 Java 方法,它会检查这两个计数器的总和以决定这个方法是否有资格被编译。如果有,则这个方法将排队等待编译。这种编译形式并没有一个官方的名字,但是一般被叫做标准编译。

但是如果方法里有一个很长的循环或者是一个永远都不会退出并提供了所有逻辑的程序会怎么样呢?这种情况下,JVM 需要编译循环而并不等待方法被调用。所以每执行完一次循环,分支计数器都会自增和自检。如果分支计数器计数超出其自身阈值,那么这个循环(并不是整个方法)将具有被编译资格。

这种编译叫做栈上替换(OSR),因为即使循环被编译了,这也是不够的:JVM 必须有能力当循环正在运行时,开始执行此循环已被编译的版本。换句话说,当循环的代码被编译完成,若 JVM 替换了代码(前栈),那么循环的下个迭代执行最新的被编译版本则会更加快。

标准编译是被-XX:CompileThreshold=Nflag 的值所触发。Client 编译器模式下,N 默认的值 1500,而 Server 编译器模式下,N 默认的值则是 10000。改变 CompileThreshold 标志的值将会使编译器相对正常情况下提前(或推迟)编译代码。在性能领域,改变 CompileThreshold 标志是很被推荐且流行的方法。事实上,您可能知道 Java 基准经常使用此标志(比如:对于很多 server 编译器来说,经常在经过 8000 次迭代后改变次标志)。

我们已经知道 client 编译器和 server 编译器在最终的性能上有很大的差别,很大程度上是因为编译器在编译一个特定的方法时,对于两种编译器可用的信息并不一样。降低编译阈值,尤其是对于 server 编译器,承担着不能使应用程序运行达到最佳性能的风险,但是经过测试应用程序我们也发现,将阈值从 8000 变成 10000,其实有着非常小的区别和影响。

检查编译过程

中级优化的最后一点其实并不是优化本身,而是它们并不能提高应用程序的性能。它们是 JVM(以及其他工具)的各个标志,并可以给出编译工作的可见性。它们中最重要的就是--XX:+PrintCompilation(默认状态下是 false)。

如果 PrintCompilation 被启用,每次一个方法(或循环)被编译,JVM 都会打印出刚刚编译过的相关信息。不同的 Java 版本输出形式不一样,我们这里所说的是基于 Java 7 版本的。

编译日志中大部分的行信息都是下面的形式:

清单 2. 日志形式
timestamp compilation_id attributes (tiered_level) method_name size depot

这里 timestamp 是编译完成时的时间戳,compilation_id 是一个内部的任务 ID,且通常情况下这个数字是单调递增的,但有时候对于 server 编译器(或任何增加编译阈值的时候),您可能会看到失序的编译 ID。这表明编译线程之间有些快有些慢,但请不要随意推断认为是某个编译器任务莫名其妙的非常慢。

用 jstat 命令检查编译

要想看到编译日志,则需要程序以-XX:+PrintCompilation flag 启动。如果程序启动时没有 flag,您可以通过 jstat 命令得到有限的可见性信息。

Jstat 有两个选项可以提供编译器信息。其中,-compile 选项提供总共有多少方法被编译的总结信息(下面 6006 是要被检查的程序的进程 ID):

清单 3 进程详情
% jstat -compiler 6006 CompiledFailedInvalid TimeFailedTypeFailedMethod 206 0 0 1.97 0

注意,这里也列出了编译失败的方法的个数信息,以及编译失败的最后一个方法的名称。

另一种选择,您可以使用-printcompilation 选项得到最后一个被编译的方法的编译信息。因为 jstat 命令有一个参数选项用来重复其操作,您可以观察每一次方法被编译的情况。举个例子:

Jstat 对 6006 号 ID 进程每 1000 毫秒执行一次: %jstat –printcompilation 6006 1000,具体的输出信息在此不再描述。

回页首

高级编译器调优

这一节我们将介绍编译工作剩下的细节,并且过程中我们会探讨一些额外的调优策略。调优的存在很大程度上帮助了 JVM 工程师诊断 JVM 自身的行为。如果您对编译器的工作原理很感兴趣,这一节您一定会喜欢。

编译线程

从前文中我们知道,当一个方法(或循环)拥有编译资格时,它就会排队并等待编译。这个队列是由一个或很多个后台线程组成。这也就是说编译是一个异步的过程。它允许程序在代码正在编译时被继续执行。如果一个方法被标准编译方式所编译,那么下一个方法调用则会执行已编译的方法。如果一个循环被栈上替换方式所编译,那么下一次循环迭代则会执行新编译的代码。

这些队列并不会严格的遵守先进先出原则:哪一个方法的调用计数器计数更高,哪一个就拥有优先权。所以即使当一个程序开始执行,并且有大量的代码需要编译,这个优先权顺序将帮助并保证最重要的代码被优先编译(这也是为什么编译 ID 在 PrintComilation 的输出结果中有时会失序的另一个原因)。

当使用 client 编译器时,JVM 启动一个编译线程,而 server 编译器有两个这样的线程。当分层编译生效时,JVM 会基于某些复杂方程式默认启动多个 client 和 server 线程,涉及双日志在目标平台上的 CPU 数量。如下图所示:

分层编译下 C1 和 C2 编译器线程默认数量:

图 3. C1 和 C2 编译器默认数量
图 3. C1 C2 编译器默认数量

编译器线程的数量可以通过-XX:CICompilerCount=N flag 进行调节设置。这个数量是 JVM 将要执行队列所用的线程总数。对于分层编译,三分之一的(至少一个)线程被用于执行 client 编译器队列,剩下的(也是至少一个)被用来执行 server 编译器队列。

在何时我们应该考虑调整这个值呢?如果一个程序被运行在单 CPU 机器上,那么只有一个编译线程会更好一些:因为对于某个线程来说,其对 CPU 的使用是有限的,并且在很多情况下越少的线程竞争资源会使其运行性能更高。然而,这个优势仅仅局限于初始预热阶段,之后,这些具有编译资格的方法并不会真的引起 CPU 争用。当一个股票批处理应用程序运行在单 CPU 机器上并且编译器线程被限制成只有一个,那么最初的计算过程将比一般情况下快 10%(因为它没有被其他线程进行 CPU 争用)。迭代运行的次数越多,最初的性能收益就相对越少,直到所有的热点方法被编译完性能收益也随之终止。

回页首

结束语

本文详细介绍了 JIT 编译器的工作原理。从优化的角度讲,最简单的选择就是使用 server 编译器的分层编译技术,这将解决大约 90%左右的与编译器直接相关的性能问题。最后,请保证代码缓存的大小设置的足够大,这样编译器将会提供最高的编译性能。

转载自点击打开链接

posted @ 2017-06-08 17:27 小马歌 阅读(15) | 评论 (0)编辑 收藏
 

from:http://www.cnblogs.com/insistence/p/5901457.html

1. 什么是Just In Time编译器?

Hot Spot 编译

当 JVM 执行代码时,它并不立即开始编译代码。这主要有两个原因:

首先,如果这段代码本身在将来只会被执行一次,那么从本质上看,编译就是在浪费精力。因为将代码翻译成 java 字节码相对于编译这段代码并执行代码来说,要快很多。

当 然,如果一段代码频繁的调用方法,或是一个循环,也就是这段代码被多次执行,那么编译就非常值得了。因此,编译器具有的这种权衡能力会首先执行解释后的代 码,然后再去分辨哪些方法会被频繁调用来保证其本身的编译。其实说简单点,就是 JIT 在起作用,我们知道,对于 Java 代码,刚开始都是被编译器编译成字节码文件,然后字节码文件会被交由 JVM 解释执行,所以可以说 Java 本身是一种半编译半解释执行的语言。Hot Spot VM 采用了 JIT compile 技术,将运行频率很高的字节码直接编译为机器指令执行以提高性能,所以当字节码被 JIT 编译为机器码的时候,要说它是编译执行的也可以。也就是说,运行时,部分代码可能由 JIT 翻译为目标机器指令(以 method 为翻译单位,还会保存起来,第二次执行就不用翻译了)直接执行。

第二个原因是最优化,当 JVM 执行某一方法或遍历循环的次数越多,就会更加了解代码结构,那么 JVM 在编译代码的时候就做出相应的优化。

我 们将在后面讲解这些优化策略,这里,先举一个简单的例子:我们知道 equals() 这个方法存在于每一个 Java Object 中(因为是从 Object class 继承而来)而且经常被覆写。当解释器遇到 b = obj1.equals(obj2) 这样一句代码,它则会查询 obj1 的类型从而得知到底运行哪一个 equals() 方法。而这个动态查询的过程从某种程度上说是很耗时的。

在主流商用JVM(HotSpot、J9)中,Java程序一开始是通过解释器(Interpreter)进行解释执行的。当JVM发现某个方法或代码块运行特别频繁时,就会把这些代码认定为“热点代码(Hot Spot Code)”,然后JVM会把这些代码编译成与本地平台相关的机器码,并进行各种层次的优化,完成这个任务的编译器称为:即时编译器(Just In Time Compiler,JIT)

JIT编译器是“动态编译器”的一种,相对的“静态编译器”则是指的比如:C/C++的编译器

JIT并不是JVM的必须部分,JVM规范并没有规定JIT必须存在,更没有限定和指导JIT。但是,JIT性能的好坏、代码优化程度的高低却是衡量一款JVM是否优秀的最关键指标之一,也是虚拟机中最核心且最能体现虚拟机技术水平的部分。


2. 编译器与解释器

首先,不是所有JVM都采用编译器和解释器并存的架构,但主流商用虚拟机,都同时包含这两部分。

2.1 配合过程

  1. 当程序需要迅速启动然后执行的时候,解释器可以首先发挥作用,编译器不运行从而省去编译时间,立即执行程序

  2. 在程序运行后,随着时间的推移,编译器逐渐发挥作用,把越来越多的代码编译成本地代码之后,可以获得更高的执行效率

  3. 当程序运行环境中内存资源限制较大(如部分嵌入式系统中),可以使用解释执行来节约内存;反之,则可以使用编译执行来提升效率。

  4. 同时,解释器还可以作为编译器(C2才会激进优化)激进优化时的一个“逃生门”,让编译器根据概率选择一些大多数时候都能提升运行速度的优化手段,当激进优化假设不成立。如:加载了新类后,类型继承结构出现变化,出现“罕见陷阱(Uncommon Trap)”时,可以通过逆优化(Deoptimization)退回到解释状态继续执行 
    (部分没有解释器的虚拟机,也会采用不进行激进优化的C1编译器担任“逃生门”的角色)

    这里写图片描述

2.2 解释器 - Interpreter

Interpreter解释执行class文件,好像JavaScript执行引擎一样

特殊的例子:

  • 最早的Sun Classic VM只有Interpreter
  • BEA JRockit VM则只有Compiler,但它主要面向服务端应用,部署在其上的应用不重点关注启动时间

2.3 编译器 - Compiler

只说HotSpot JVM

1. C1和C2:

HotSpot虚拟机内置了两个即时编译器,分别称为Client Compiler和Server Compiler,习惯上将前者称为C1,后者称为C2

2. 使用C1还是C2?

HotSpot默认采用解释器和其中一个编译器直接配合的方式工作,使用那个编译器取决于虚拟机运行的模式,HotSpot会根据自身版本和宿主机器硬件性能自动选择模式,用户也可以使用“-client”或”-server”参数去指定

  1. 混合模式(Mixed Mode) 
    默认的模式,如上面描述的这种方式就是mixed mode

  2. 解释模式(Interpreted Mode) 
    可以使用参数“-Xint”,在此模式下全部代码解释执行

  3. 编译模式(Compiled Mode) 
    参数“-Xcomp”,此模式优先采用编译,但是无法编译时也会解释(在最新的HotSpot中此参数被取消)

    可以看到,我的JVM现在是mixed mode 
    这里写图片描述

重要:↓

在JDK1.7(1.7仅包括Server模式)之后,HotSpot就不是默认“采用解释器和其中一个编译器”配合的方式了,而是采用了分层编译,分层编译时C1和C2有可能同时工作


3. 分层编译

3.1 为什么要分层编译?

由于编译器compile本地代码需要占用程序时间,要编译出优化程度更高的代码所花费的时间可能更长,且此时解释器还要替编译器收集性能监控信息,这对解释执行的速度也有影响

所以,为了在程序启动响应时间与运行效率之间达到最佳平衡,HotSpot在JDK1.6中出现了分层编译(Tiered Compilation)的概念并在JDK1.7的Server模式JVM中作为默认策略被开启

3.2 编译层 tier(或者叫级别)

分层编译根据编译器编译、优化的规模与耗时,划分了不同的编译层次(不只以下3种),包括:

  • 第0层,程序解释执行(没有编译),解释器不开启性能监控功能,可触发第1层编译。

  • 第1层,也称C1编译,将字节码编译为本地代码,进行简单、可靠的优化,如有必要将加入性能监控的逻辑

  • 第2层(或2层以上),也称为C2编译,也是将字节码编译为本地代码,但是会启用一些编译耗时较长的优化,甚至会根据性能监控信息进行一些不可靠的激进优化

实施分层编译后,C1和C2将会同时工作,许多代码会被多次编译,用C1获取更高的编译速度,用C2来获取更好的编译质量,且在解释执行的时候解释器也无须再承担收集性能监控信息的任务


4. 编译对象与触发条件

1. 谁被编译了?

编译对象就是之前说的“热点代码”,它有两类:

  1. 被多次调用的方法 
    • 一个方法被多次调用,理应称为热点代码,这种编译也是虚拟机中标准的JIT编译方式
  2. 被多次执行的循环体 
    • 编译动作由循环体出发,但编译对象依然会以整个方法为对象
    • 这种编译方式由于编译发生在方法执行过程中,因此形象的称为:栈上替换(On Stack Replacement- OSR编译,即方法栈帧还在栈上,方法就被替换了)

2. 触发条件

1. 综述

上面的方法和循环体都说“多次”,那么多少算多?换个说法就是编译的触发条件。

判断一段代码是不是热点代码,是不是需要触发JIT编译,这样的行为称为:热点探测(Hot Spot Detection),有几种主流的探测方式:

  1. 基于计数器的热点探测(Counter Based Hot Spot Detection) 
    虚拟机会为每个方法(或每个代码块)建立计数器,统计执行次数,如果超过阀值那么就是热点代码。缺点是维护计数器开销。

  2. 基于采样的热点探测(Sample Based Hot Spot Detection) 
    虚拟机会周期性检查各个线程的栈顶,如果某个方法经常出现在栈顶,那么就是热点代码。缺点是不精确。

  3. 基于踪迹的热点探测(Trace Based Hot Spot Detection) 
    Dalvik中的JIT编译器使用这种方式

2. HotSpot

HotSpot使用的是第1种,因此它为每个方法准备了两类计数器:方法调用计数器(Invocation Counter)和回边计数器(Back Edge Counter)

  1. 方法计数器

    • 默认阀值,在Client模式下是1500次,Server是10000次,可以通过参数“-XX:CompileThreshold”来设定

    • 当一个方法被调用时会首先检查是否存在被JIT编译过得版本,如果存在则使用此本地代码来执行;如果不存在,则将方法计数器+1,然后判断“方法计数器和回边计数器之和”是否超过阀值,如果是则会向编译器提交一个方法编译请求

    • 默认情况下,执行引擎并不会同步等待上面的编译完成,而是会继续解释执行。当编译完成后,此方法的调用入口地址会被系统自动改写为新的本地代码地址

    • 还有一点,热度是会衰减的,也就是说不是仅仅+,也会-,热度衰减动作是在虚拟机的GC执行时顺便进行的

  2. 回边计数器

    • 回边,顾名思义,只有执行到大括号”}”时才算+1

    • 默认阀值,Client下13995,Server下10700

    • 它的调用逻辑和方法计数器差不多,只不过遇到回边指令时+1、超过阀值时会提交OSR编译请求以及这里没有热度衰减


5. 编译过程

编译过程是在后台线程(daemon)中完成的,可以通过参数“-XX:-BackgroundCompilation”来禁止后台编译,但此时执行线程就会同步等待编译完成才会执行程序

  1. Client Compiler 
    C1编译器是一个简单快速的三段式编译器,主要关注“局部性能优化”,放弃许多耗时较长的全局优化手段 
    过程:class -> 1. 高级中间代码 -> 2. 低级中间代码 -> 3. 机器代码
  2. Server Compiler 
    C2是专门面向服务器应用的编译器,是一个充分优化过的高级编译器,几乎能达到GNU C++编译器使用-O2参数时的优化强度。

使用参数“-XX:+PrintCompilation”会让虚拟机在JIT时把方法名称打印出来,如图: 
这里写图片描述


6. Java和C/C++的编译器对比

这里不是比Java和C/C++谁快这种大坑问题,只是比较编译器(我认为开发效率上Java快,执行效率上C/C++快)

这种对比代表了经典的即时编译器与静态编译期的对比,其实总体来说Java编译器有优有劣。主要就是动态编译时间压力大能做的优化少,还要做一些动态校验。而静态编译器无法实现一些开发上很有用的动态特性

posted @ 2017-06-08 17:26 小马歌 阅读(20) | 评论 (0)编辑 收藏
 
from:http://www.tuicool.com/articles/r6Z7vaj

JVM自动监控这所有方法的执行,如果某个方法是热点方法,JVM就计划把该方法的字节码代码编译成本地机器代码,编译成机器代码的过程是在独立线程中执行的,不会影响程序的执行,这个过程就是JIT(just in time)。

JIT针对下面的几种方式进行优化

  • 把bytecode编译成本地代码
  • 单态调度(monomorphic dispatch),当个对象的类和其父类间有方法重写时,JVM调用对象的方法可以通过对象的类型路径来判断应该调用父类的方法还是子类的方法,对此JIT进行优化,这种优化是C++所不具备的,C++中需要查找虚函数表。
  • 循环展开(loop unrolling)
  • 类型锐化
  • 逃逸分析(escape analysis)
  • 移除无用代码(这个现在IDE会提示我们的,比如:intellij idea)
  • Intrinsics
  • 分支预测
  • 方法内联(inlining,对性能的提升很大),默认情况,<= 35字节码的方法可以进行内联,通过这个来修改内联方法的最大值:-XX:MaxInlineSize=,通过-XX:FreqInlineSize=来设置频繁调用方法的临界值

这些优化方法通常是层层依赖的,所以当JIT优化后的代码被JVM应用,就会开始尝试进行更上一层次的优化。因此我们写代码的时候,应该尽量往这些优化方式上面靠。

输出JIT编译过的方法

在JVM启动参数中添加如下的启动参数:

-XX:+PrintCompilation 

输出内容类似这样:

31    23 s!    sun.misc.URLClassPath::getLoader (136 bytes) 
  • 第1列  31:为JVM启动后到该方法被编译相隔的时间,单位为毫秒
  • 第2列  23:编译ID,用来跟踪一个方法的编译、优化、深度优化
  • 第3列  s!:s是指该方法是synchronized,感叹号是指该方法有对异常的处理
  • 第4列  sun.misc.URLClassPath::getLoader:被编译的方法
  • 第5列  (136 bytes):方法的字节大小

输出JIT编译的细节信息

通过添加参数-XX:+PrintCompilation,可以看到的信息其实并不具体,比如:那些方法进行了内联,内联后的二进制代码是怎么样的都没有。而要输出JIT编译的细节信息,就需要在JVM启动参数中添加这个参数:

-XX:+LogCompilation -XX:+UnlockDiagnosticVMOptions -XX:+TraceClassLoading -XX:+PrintAssembly 

输出的编译信息,默认情况是在启动JVM的目录下一个名为:hotspot_pid<PID>.log的文件

如果想指定文件路径和文件名的话,可以再添加一个启动参数:

-XX:LogFile=<pathto file> 

输出的是一个很大的xml文件,可能有几百兆,内容大致如下:

<nmethodcompile_id='2' compiler='C1' level='3'  entry='0x00000001023fe240' size='1224'  address='0x00000001023fe0d0' relocation_offset='288'  insts_offset='368' stub_offset='880' scopes_data_offset='1032'  scopes_pcs_offset='1104' dependencies_offset='1200'  nul_chk_table_offset='1208'  method='java/lang/String hashCode ()I' bytes='55' count='512'  backedge_count='8218' iicount='512' stamp='0.350'/> 

而且内容很难读懂,建议使用JITWatch( https://github.com/AdoptOpenJDK/jitwatch/ )的可视化界面来查看JIT编译的细节信息。同时JITWatch还可以给出很多优化建议,给我们有效的优化代码提供参考,详见下文。

JIT编译模式

C1: 通常用于那种快速启动的GUI应用,对应启动参数:-client

C2: 通常用于长时间允许的服务端应用,对应启动参数:-server

分层编译模式(tiered compilation):这是自从Java SE 7以后的新特性,可通过添加启动参数来开启:

-XX:+TieredCompilation 

这个特性在应用启动阶段使用C1模式以达到快速启动的效果,一旦应用程序运行起来以后,C2模式将取代C1模式,以进行更深度的优化。在Java SE 8中,这个特性是默认的。

JITWatch

前面也提到了,JITWatch可以通过可视化界面来帮助我们分析JVM输出的JIT编译输出日志,还可以帮助我们静态分析jar中的代码是否符合JIT编译优化的条件,还可以以曲线图形的方式展示JIT编译的整个过程中的一些指标,非常好用的工具。

下载

JITWatch需要在github上把代码clone下来,然后用maven来运行,地址为: https://github.com/AdoptOpenJDK/jitwatch/

运行JITWwatch

在代码根目录下执行 launchUI.sh( Linux/Mac)或则 launchUI.bat(windows)

如果你使用maven,也可以在代码根目录下这样运行(其他运行方式,请参考JITWatch的github首页)

mvncleancompileexec:java 

如果你使用的是mac,而且idk版本是jdk7,且运行mvn clean compile exec:java时出现下面的错误和异常时: 

Causedby: java.lang.NullPointerException  atcom.sun.t2k.MacFontFinder.initPSFontNameToPathMap(MacFontFinder.java:339)  atcom.sun.t2k.MacFontFinder.getFontNamesOfFontFamily(MacFontFinder.java:390)  atcom.sun.t2k.T2KFontFactory.getFontResource(T2KFontFactory.java:233)  atcom.sun.t2k.LogicalFont.getSlot0Resource(LogicalFont.java:184)  atcom.sun.t2k.LogicalFont.getSlotResource(LogicalFont.java:228)  atcom.sun.t2k.CompositeStrike.getStrikeSlot(CompositeStrike.java:86)  atcom.sun.t2k.CompositeStrike.getMetrics(CompositeStrike.java:132)  atcom.sun.javafx.font.PrismFontUtils.getFontMetrics(PrismFontUtils.java:31)  atcom.sun.javafx.font.PrismFontLoader.getFontMetrics(PrismFontLoader.java:466)  atjavafx.scene.text.Text.<init>(Text.java:153)  atcom.sun.javafx.scene.control.skin.Utils.<clinit>(Utils.java:52)  ... 13 more   [ERROR] Failedto executegoalorg.codehaus.mojo:exec-maven-plugin:1.5.0:java (default-cli) onprojectjitwatch-ui: Anexceptionoccuredwhile executingtheJavaclass. null: InvocationTargetException: Exceptionin Applicationstartmethod: ExceptionInInitializerError: NullPointerException -> [Help 1] 

请在org.adoptopenjdk.jitwatch.launch.LaunchUI类的main函数开头处添加下面的代码(或者直接使用我fork修改好的 JITWatch ):

final Class<?> macFontFinderClass = Class.forName("com.sun.t2k.MacFontFinder"); final java.lang.reflect.FieldpsNameToPathMap = macFontFinderClass.getDeclaredField("psNameToPathMap"); psNameToPathMap.setAccessible(true); if (psNameToPathMap.get(null) == null) {     psNameToPathMap.set(         null, new java.util.HashMap<String, String>()); } final java.lang.reflect.FieldallAvailableFontFamilies = macFontFinderClass.getDeclaredField("allAvailableFontFamilies"); allAvailableFontFamilies.setAccessible(true); if (allAvailableFontFamilies.get(null) == null) {     allAvailableFontFamilies.set(         null, new String[] {}); } 

然后重新运行即可看到JITWatch的界面。

Reference

http://www.oracle.com/technetwork/articles/java/architect-evans-pt1-2266278.html

https://www.chrisnewland.com/images/jitwatch/HotSpot_Profiling_Using_JITWatch.pdf

posted @ 2017-06-08 16:48 小马歌 阅读(21) | 评论 (0)编辑 收藏

2017年6月2日

     摘要: from:http://yemengying.com/2016/05/07/threadsafe-hashmap/ 2016-05-07 JAVAHASHMAP HASHMAP, JAVA文章目录1. 为什么HashMap是线程不安全的1.1. HashMap的内部存储结构1.2. HashMap的自动扩容机制1.3. ...  阅读全文
posted @ 2017-06-02 17:57 小马歌 阅读(30) | 评论 (0)编辑 收藏
 
from:http://tech.meituan.com/java-hashmap.html

摘要

HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别,深入探讨HashMap的结构实现和功能原理。

简介

Java为数据结构中的映射定义了一个接口java.util.Map,此接口主要有四个常用的实现类,分别是HashMap、Hashtable、LinkedHashMap和TreeMap,类继承关系如下图所示:

java.util.map类图

下面针对各个实现类的特点做一些说明:

(1) HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

(2) Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

(4) TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。

通过上面的比较,我们知道了HashMap是Java的Map家族中一个普通成员,鉴于它可以满足大多数场景的使用条件,所以是使用频度最高的一个。下文我们主要结合源码,从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

内部实现

搞清楚HashMap,首先需要知道HashMap是什么,即它的存储结构-字段;其次弄明白它能干什么,即它的功能实现-方法。下面我们针对这两个方面详细展开讲解。

存储结构-字段

从结构实现来讲,HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,如下如所示。

hashMap内存结构图

这里需要讲明白两个问题:数据底层具体存储的是什么?这样的存储方式有什么优点呢?

(1) 从源码可知,HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组,明显它是一个Node的数组。我们来看Node[JDK1.8]是何物。

static class Node<K,V> implements Map.Entry<K,V> {         final int hash;    //用来定位数组索引位置         final K key;         V value;         Node<K,V> next;   //链表的下一个node          Node(int hash, K key, V value, Node<K,V> next) { ... }         public final K getKey(){ ... }         public final V getValue() { ... }         public final String toString() { ... }         public final int hashCode() { ... }         public final V setValue(V newValue) { ... }         public final boolean equals(Object o) { ... } } 

Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。

(2) HashMap就是使用哈希表来存储的。哈希表为解决冲突,可以采用开放地址法和链地址法等来解决问题,Java中HashMap采用了链地址法。链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。例如程序执行下面代码:

    map.put("美团","小美"); 

系统将调用"美团"这个key的hashCode()方法得到其hashCode 值(该方法适用于每个Java对象),然后再通过Hash算法的后两步运算(高位运算和取模运算,下文有介绍)来定位该键值对的存储位置,有时两个key会定位到相同的位置,表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。

如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案就是好的Hash算法和扩容机制。

在理解Hash和扩容流程之前,我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知,构造函数就是对下面几个字段进行初始化,源码如下:

     int threshold;             // 所能容纳的key-value对极限       final float loadFactor;    // 负载因子      int modCount;        int size; 

首先,Node[] table的初始化长度length(默认值是16),Load factor为负载因子(默认值是0.75),threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。

结合负载因子的定义公式可知,threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目,超过这个数目就重新resize(扩容),扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子Load factor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。

size这个字段其实很好理解,就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

在HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),这是一种非常规的设计,常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数,具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159,Hashtable初始化桶大小为11,就是桶大小设计为素数的应用(Hashtable扩容后不能保证还是素数)。HashMap采用这种非常规设计,主要是为了在取模和扩容时做优化,同时为了减少冲突,HashMap定位哈希桶索引位置时,也加入了高位参与运算的过程。

这里存在一个问题,即使负载因子和Hash算法设计的再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响HashMap的性能。于是,在JDK1.8版本中,对数据结构做了进一步的优化,引入了红黑树。而当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。本文不再对红黑树展开讨论,想了解更多红黑树数据结构的工作原理可以参考http://blog.csdn.net/v_july_v/article/details/6105630

功能实现-方法

HashMap的内部功能实现很多,本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入展开讲解。

1. 确定哈希桶数组索引位置

不管增加、删除、查找键值对,定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,不用遍历链表,大大优化了查询的效率。HashMap定位数组索引位置,直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):

方法一: static final int hash(Object key) {   //jdk1.8 & jdk1.7      int h;      // h = key.hashCode() 为第一步 取hashCode值      // h ^ (h >>> 16)  为第二步 高位参与运算      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 方法二: static int indexFor(int h, int length) {  //jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的      return h & (length-1);  //第三步 取模运算 } 

这里的Hash算法本质上就是三步:取key的hashCode值、高位运算、取模运算

对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,模运算的消耗还是比较大的,在HashMap中是这样做的:调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙,它通过h & (table.length -1)来得到该对象的保存位,而HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

在JDK1.8的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

下面举例说明下,n为table的长度。

hashMap哈希算法例图

2. 分析HashMap的put方法

HashMap的put方法执行过程可以通过下图来理解,自己有兴趣可以去对比源码更清楚地研究学习。

hashMap put方法执行流程图

①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

JDK1.8HashMap的put方法源码如下:

 1 public V put(K key, V value) {  2     // 对key的hashCode()做hash  3     return putVal(hash(key), key, value, false, true);  4 }  5   6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  7                boolean evict) {  8     Node<K,V>[] tab; Node<K,V> p; int n, i;  9     // 步骤①:tab为空则创建 10     if ((tab = table) == null || (n = tab.length) == 0) 11         n = (tab = resize()).length; 12     // 步骤②:计算index,并对null做处理  13     if ((p = tab[i = (n - 1) & hash]) == null)  14         tab[i] = newNode(hash, key, value, null); 15     else { 16         Node<K,V> e; K k; 17         // 步骤③:节点key存在,直接覆盖value 18         if (p.hash == hash && 19             ((k = p.key) == key || (key != null && key.equals(k)))) 20             e = p; 21         // 步骤④:判断该链为红黑树 22         else if (p instanceof TreeNode) 23             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 24         // 步骤⑤:该链为链表 25         else { 26             for (int binCount = 0; ; ++binCount) { 27                 if ((e = p.next) == null) { 28                     p.next = newNode(hash, key,value,null);                         //链表长度大于8转换为红黑树进行处理 29                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st   30                         treeifyBin(tab, hash); 31                     break; 32                 }                     // key已经存在直接覆盖value 33                 if (e.hash == hash && 34                     ((k = e.key) == key || (key != null && key.equals(k))))  35                            break; 36                 p = e; 37             } 38         } 39          40         if (e != null) { // existing mapping for key 41             V oldValue = e.value; 42             if (!onlyIfAbsent || oldValue == null) 43                 e.value = value; 44             afterNodeAccess(e); 45             return oldValue; 46         } 47     }  48     ++modCount; 49     // 步骤⑥:超过最大容量 就扩容 50     if (++size > threshold) 51         resize(); 52     afterNodeInsertion(evict); 53     return null; 54 } 

3. 扩容机制

扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。

我们分析下resize的源码,鉴于JDK1.8融入了红黑树,较复杂,为了便于理解我们仍然使用JDK1.7的代码,好理解一些,本质上区别不大,具体区别后文再说。

 1 void resize(int newCapacity) {   //传入新的容量  2     Entry[] oldTable = table;    //引用扩容前的Entry数组  3     int oldCapacity = oldTable.length;           4     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了  5         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了  6         return;  7     }  8    9     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组 10     transfer(newTable);                         //!!将数据转移到新的Entry数组里 11     table = newTable;                           //HashMap的table属性引用新的Entry数组 12     threshold = (int)(newCapacity * loadFactor);//修改阈值 13 } 

这里就是使用一个容量更大的数组来代替已有的容量小的数组,transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

 1 void transfer(Entry[] newTable) {  2     Entry[] src = table;                   //src引用了旧的Entry数组  3     int newCapacity = newTable.length;  4     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组  5         Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素  6         if (e != null) {  7             src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)  8             do {  9                 Entry<K,V> next = e.next; 10                 int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置 11                 e.next = newTable[i]; //标记[1] 12                 newTable[i] = e;      //将元素放在数组上 13                 e = next;             //访问下一个Entry链上的元素 14             } while (e != null); 15         } 16     } 17 } 

newTable[i]的引用赋给了e.next,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话),这一点和Jdk1.8有区别,下文详解。在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。

下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。其中的哈希桶数组table的size=2, 所以key = 3、7、5,put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1,即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4,然后所有的Node重新rehash的过程。

jdk1.7扩容例图

下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现,我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

hashMap 1.8 哈希算法例图1

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

hashMap 1.8 哈希算法例图2

因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:

jdk1.8 hashMap扩容例图

这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码,写的很赞,如下:

 1 final Node<K,V>[] resize() {  2     Node<K,V>[] oldTab = table;  3     int oldCap = (oldTab == null) ? 0 : oldTab.length;  4     int oldThr = threshold;  5     int newCap, newThr = 0;  6     if (oldCap > 0) {  7         // 超过最大值就不再扩充了,就只好随你碰撞去吧  8         if (oldCap >= MAXIMUM_CAPACITY) {  9             threshold = Integer.MAX_VALUE; 10             return oldTab; 11         } 12         // 没超过最大值,就扩充为原来的2倍 13         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 14                  oldCap >= DEFAULT_INITIAL_CAPACITY) 15             newThr = oldThr << 1; // double threshold 16     } 17     else if (oldThr > 0) // initial capacity was placed in threshold 18         newCap = oldThr; 19     else {               // zero initial threshold signifies using defaults 20         newCap = DEFAULT_INITIAL_CAPACITY; 21         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 22     } 23     // 计算新的resize上限 24     if (newThr == 0) { 25  26         float ft = (float)newCap * loadFactor; 27         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 28                   (int)ft : Integer.MAX_VALUE); 29     } 30     threshold = newThr; 31     @SuppressWarnings({"rawtypes","unchecked"}) 32         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 33     table = newTab; 34     if (oldTab != null) { 35         // 把每个bucket都移动到新的buckets中 36         for (int j = 0; j < oldCap; ++j) { 37             Node<K,V> e; 38             if ((e = oldTab[j]) != null) { 39                 oldTab[j] = null; 40                 if (e.next == null) 41                     newTab[e.hash & (newCap - 1)] = e; 42                 else if (e instanceof TreeNode) 43                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 44                 else { // 链表优化重hash的代码块 45                     Node<K,V> loHead = null, loTail = null; 46                     Node<K,V> hiHead = null, hiTail = null; 47                     Node<K,V> next; 48                     do { 49                         next = e.next; 50                         // 原索引 51                         if ((e.hash & oldCap) == 0) { 52                             if (loTail == null) 53                                 loHead = e; 54                             else 55                                 loTail.next = e; 56                             loTail = e; 57                         } 58                         // 原索引+oldCap 59                         else { 60                             if (hiTail == null) 61                                 hiHead = e; 62                             else 63                                 hiTail.next = e; 64                             hiTail = e; 65                         } 66                     } while ((e = next) != null); 67                     // 原索引放到bucket里 68                     if (loTail != null) { 69                         loTail.next = null; 70                         newTab[j] = loHead; 71                     } 72                     // 原索引+oldCap放到bucket里 73                     if (hiTail != null) { 74                         hiTail.next = null; 75                         newTab[j + oldCap] = hiHead; 76                     } 77                 } 78             } 79         } 80     } 81     return newTab; 82 } 

线程安全性

在多线程使用场景中,应该尽量避免使用线程不安全的HashMap,而使用线程安全的ConcurrentHashMap。那么为什么说HashMap是线程不安全的,下面举例子说明在并发的多线程使用场景中使用HashMap可能造成死循环。代码例子如下(便于理解,仍然使用JDK1.7的环境):

public class HashMapInfiniteLoop {        private static HashMap<Integer,String> map = new HashMap<Integer,String>(2,0.75f);       public static void main(String[] args) {           map.put(5, "C");            new Thread("Thread1") {               public void run() {                   map.put(7, "B");                   System.out.println(map);               };           }.start();           new Thread("Thread2") {               public void run() {                   map.put(3, "A);                   System.out.println(map);               };           }.start();             }   } 

其中,map初始化为一个长度为2的数组,loadFactor=0.75,threshold=2*0.75=1,也就是说当put第二个key的时候,map就需要进行resize。

通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行;然后放开线程2的的断点,让线程2进行resize。结果如下图。

jdk1.7 hashMap死循环例图1

注意,Thread1的 e 指向了key(3),而next指向了key(7),其在线程二rehash后,指向了线程二重组后的链表。

线程一被调度回来执行,先是执行 newTalbe[i] = e, 然后是e = next,导致了e指向了key(7),而下一次循环的next = e.next导致了next指向了key(3)。

jdk1.7 hashMap死循环例图2

jdk1.7 hashMap死循环例图3

e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意:此时的key(7).next 已经指向了key(3), 环形链表就这样出现了。

jdk1.7 hashMap死循环例图4

于是,当我们用线程一调用map.get(11)时,悲剧就出现了——Infinite Loop。

JDK1.8与JDK1.7的性能对比

HashMap中,如果key经过hash算法得出的数组索引位置全部不相同,即Hash算法非常好,那样的话,getKey方法的时间复杂度就是O(1),如果Hash算法技术的结果碰撞非常多,假如Hash算极其差,所有的Hash算法结果得出的索引位置一样,那样所有的键值对都集中到一个桶中,或者在一个链表中,或者在一个红黑树中,时间复杂度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化,总体性能优于JDK1.7,下面我们从两个方面用例子证明这一点。

Hash较均匀的情况

为了便于测试,我们先写一个类Key,如下:

class Key implements Comparable<Key> {      private final int value;      Key(int value) {         this.value = value;     }      @Override     public int compareTo(Key o) {         return Integer.compare(this.value, o.value);     }      @Override     public boolean equals(Object o) {         if (this == o) return true;         if (o == null || getClass() != o.getClass())             return false;         Key key = (Key) o;         return value == key.value;     }      @Override     public int hashCode() {         return value;     } } 

这个类复写了equals方法,并且提供了相当好的hashCode函数,任何一个值的hashCode都不会相同,因为直接使用value当做hashcode。为了避免频繁的GC,我将不变的Key实例缓存了起来,而不是一遍一遍的创建它们。代码如下:

public class Keys {      public static final int MAX_KEY = 10_000_000;     private static final Key[] KEYS_CACHE = new Key[MAX_KEY];      static {         for (int i = 0; i < MAX_KEY; ++i) {             KEYS_CACHE[i] = new Key(i);         }     }      public static Key of(int value) {         return KEYS_CACHE[value];     } } 

现在开始我们的试验,测试需要做的仅仅是,创建不同size的HashMap(1、10、100、......10000000),屏蔽了扩容的情况,代码如下:

   static void test(int mapSize) {          HashMap<Key, Integer> map = new HashMap<Key,Integer>(mapSize);         for (int i = 0; i < mapSize; ++i) {             map.put(Keys.of(i), i);         }          long beginTime = System.nanoTime(); //获取纳秒         for (int i = 0; i < mapSize; i++) {             map.get(Keys.of(i));         }         long endTime = System.nanoTime();         System.out.println(endTime - beginTime);     }      public static void main(String[] args) {         for(int i=10;i<= 1000 0000;i*= 10){             test(i);         }     } 

在测试中会查找不同的值,然后度量花费的时间,为了计算getKey的平均时间,我们遍历所有的get方法,计算总的时间,除以key的数量,计算一个平均值,主要用来比较,绝对值可能会受很多环境因素的影响。结果如下:

性能比较表1.png

通过观测测试结果可知,JDK1.8的性能要高于JDK1.7 15%以上,在某些size的区域上,甚至高于100%。由于Hash算法较均匀,JDK1.8引入的红黑树效果不明显,下面我们看看Hash不均匀的的情况。

Hash极不均匀的情况

假设我们又一个非常差的Key,它们所有的实例都返回相同的hashCode值。这是使用HashMap最坏的情况。代码修改如下:

class Key implements Comparable<Key> {      //...      @Override     public int hashCode() {         return 1;     } } 

仍然执行main方法,得出的结果如下表所示:

性能比较表2.png

从表中结果中可知,随着size的变大,JDK1.7的花费时间是增长的趋势,而JDK1.8是明显的降低趋势,并且呈现对数增长稳定。当一个链表太长的时候,HashMap会动态的将它替换成一个红黑树,这话的话会将时间复杂度从O(n)降为O(logn)。hash算法均匀和不均匀所花费的时间明显也不相同,这两种情况的相对比较,可以说明一个好的hash算法的重要性。

      测试环境:处理器为2.2 GHz Intel Core i7,内存为16 GB 1600 MHz DDR3,SSD硬盘,使用默认的JVM参数,运行在64位的OS X 10.10.1上。

小结

(1) 扩容是一个特别耗性能的操作,所以当程序员在使用HashMap的时候,估算map的大小,初始化的时候给一个大致的数值,避免map进行频繁的扩容。

(2) 负载因子是可以修改的,也可以大于1,但是建议不要轻易修改,除非情况非常特殊。

(3) HashMap是线程不安全的,不要在并发的环境中同时操作HashMap,建议使用ConcurrentHashMap。

(4) JDK1.8引入红黑树大程度优化了HashMap的性能。

(5) 还没升级JDK1.8的,现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。

参考

  1. JDK1.7&JDK1.8 源码。
  2. CSDN博客频道,HashMap多线程死循环问题,2014。
  3. 红黑联盟,Java类集框架之HashMap(JDK1.8)源码剖析,2015。
  4. CSDN博客频道, 教你初步了解红黑树,2010。
  5. Java Code Geeks,HashMap performance improvements in Java 8,2014。
  6. Importnew,危险!在HashMap中将可变对象用作Key,2014。
  7. CSDN博客频道,为什么一般hashtable的桶数会取一个素数,2013。


posted @ 2017-06-02 17:56 小马歌 阅读(9) | 评论 (0)编辑 收藏

2017年5月17日

from:http://blog.csdn.net/hemeinvyiqiluoben/article/details/62439861

课程安排
第一天 
上午
一、机器学习基础1.线性代数
(1).矩阵运算  (2).向量运算
(3).SVD      (4).PCA
2.概率信息论
(1).概率分布  (2).期望、方差、协方差
(3). 贝叶斯   (4).结构概率模型
3.数值优化
二、深度学习基础1.深度学习介绍 
(1).发展历史  (2).主要应用
2.感知器      
3.人工神经网络
4.前馈神经网络  
5.BP算法      
6.Hessian矩阵
第一天
  下午
三、深度学习进阶---卷积神经网络1.CNN卷积神经网络
(1).卷积层(一维卷积、二维卷积)
(2).池化层(均值池化、最大池化)
(3). 全连接层
(4).激活函数层
(5).Softmax层
2.CNN卷积神经网络改进
(1).R-CNN (SPPNET)
(2).Fast-R-CNN
(3).Faster-R-CNN (YOLO、SSD)
3.深度学习的模型训练技巧
4.梯度下降的优化方法详解
第二天
上午
四、深度学习软件1.深度学习相关软件的安装配置与使用介绍
(1).Caffe
(2).Tensorflow
(3).Torch
(4).MXNet
第二天
下午
五、 CNN应用案例(1).CNN与手写数字集分类
(2).YOLO实现目标检测
(3).PixelNet原理与实现
(4).利用卷积神经网络做图像风格结合
第三天
上午
六、深度学习——循环神经网络1.RNN循环神经网络
(1).梯度计算
(2).BPTT
2.RNN循环神经网络改进
(1).LSTM
(2).GRU
(3).Bi-RNN
(4).Attention based RNN
3.RNN实际应用
(1).Seq2Seq的原理与实现   
第三天
下午
、强化学习1.强化学习的理论知识
2.经典模型DQN讲解
3.AlphaGo原理讲解
4.RL实际应用
(1).实现一个AlphaGo     
第四天
上午
八、对抗性生成网络1.GAN的理论知识
2.GAN经典模型
(1).GAN,CGAN,LAPGAN,DCGAN,
3.GAN经典模型
(1). INFOGAN,WGAN,S2-GAN
4.GAN实际应用
(1).DCGAN提高模糊图片分辨率
5.GAN实际应用
(1).InfoGAN做特定的样本生成
第四天
下午
九、迁移学习1.迁移学习的理论概述
2.迁移学习的常见方法
(1).基于特征的迁移
(2).基于实例的迁移
(3).基于数据的迁移
(4).深度迁移学习
(5).强化迁移学习
(6).迁移学习的研究案例
(7).迁移学习的应用
(8).2017年AAAI最佳论文讲解:利用物理定理的知识迁移到视频理解
posted @ 2017-05-17 11:28 小马歌 阅读(74) | 评论 (0)编辑 收藏

2017年5月15日

from:http://mobile.51cto.com/hot-439693.htm

背景:除去大名鼎鼎的QQ这款即时聊天工具,还有许多细分行业的IM,比如淘宝阿里旺旺、网易泡泡、YY语音......。恰巧公司产品也要开发一款基于我 们自己行业的类IM系统,很有幸我担当了这个产品的架构师,核心代码编写、实现者。下面把我近年来从技术上我对IM系统(即时消息的传输,不包括语音,视频,文件的传输)的理解和设计分享出来,浅薄之见,望大家别见笑,欢迎给出批评意见。

一.网络传输协议的选择

目前我知晓的所有IM系统传输即时消息无外乎使用UDP、TCP、基于TCP的http这几种协议中的一种或几种。比如QQ主要采用UDP协议,MSN主要采用TCP协议,而且他们也都支持HTTP协议的代理模式。更多资料,请参加这篇文章《一些常用软件的网络端口协议分类介绍》

我们该如何选择呢?

  • UDP协议实时性更好,但是如何处理安全可靠的传输并且处理不同客户端之间的消息交互是个难题,实现起来过于复杂;

  • HTTP协议属于扩展支持,我们在产品的初始阶段可以不用支持;

  • 那就非TCP协议莫属了,要考虑的同样也有很多,特别是如果有海量用户的需求。如何保证单机服务器高并发量,如何做到灵活,扩展的架构。

Tips: QQ 为什么采用 UDP 协议,而不采用 TCP 协议实现?

二.应该选择什么格式的数据协议

二进制格式?文本格式?这个话题转到我的这篇文章《网络传输数据格式的选择》,从我们当前的需求和产品周期上我觉得选择JSON形式的数据协议是最好的。

三.架构设计

首先我们来提炼一下一个IM系统的主要需求,包括账号,关系链,在线状态显示,消息交互......。

架构考量:

  • 由于采用可靠传输协议TCP,考虑到负载问题(短连接实现账号、关系链相关业务,长连接实现上线、信息推送);

  • 后台架构的灵活性、可扩展性,支持分布式部署——把网络层、业务逻辑层、数据层分离,网络层和业务层支持负载均衡策略、数据层支持分布式存储;

  • 客户端SDK的易用性:把网络层、数据层分离、业务逻辑层分离;

后台架构简化图

架构示意图

架构细化图

说明

  • 从< 架构细化图>中可以看出对于上线服务由于建立的是TCP长连接,对于单台服务器往往由于硬件资源、系统资源、网络资源的限制无法做到海量用户的同时 在线,所以设计为根据服务器负载支持多服务器上线,同时由于多服务器上线造成了对整个系统交互(不同的客户端的交互,协作部门应用服务和客户的交互)的分 割,引入消息转发服务器作为粘合点。另外对于多服务器上线造成的统一账户信息(在线状态,消息)数据的分割,引入统一的数据层(内存存储 层:session、状态信息存储、消息队列存储;数据库:账号信息存储)做到业务和数据的分离,也就做到了支持分布式部署。参见我的这篇文章《构建高性能服务的考量》

  • 对于部分业务服务:做到网络层、业务层、数据层的完全分离。首先对于TCP短连接来说不会如长连接那般消耗资源,即使后期遇到海量的并发访问请求依然可以从容的通过负载均衡策略和数据分布式部署策略进行解决。参见我的这篇文章《服务端架构中的“网关服务器”》

服务端平台及技术选型

  • 系统开发平台: CentOS——Linux发行版的一种,稳定可靠、可定制优化、支持丰富;

  • 网络支撑层: libevent——减小开发成本,增强稳定性;

  • 缓存存储层: Redis——支持丰富的存储结构,支持分布式存储;

  • 数据库: MySQL——最适合互联网的数据库,免授权、高效稳定、可控性高;

  • 开发语言: C/C++;

部分热点问题考量

  • 系统性能考量:

    • 编码角度:采用高效的网络模型,线程模型,I/O处理模型,合理的数据库设计和操作语句的优化;

    • 垂直扩展:通过提高单服务器的硬件资源或者网络资源来提高性能;

    • 水平扩展:通过合理的架构设计和运维方面的负载均衡策略将负载分担,有效提高性能;后期甚至可以考虑加入数据缓存层,突破IO瓶颈;

  • 系统的高可用性:(防止单点故障)

    • 在架构设计时做到业务处理和数据的分离,从而依赖分布式的部署使得在单点故障时能保证系统可用。

    • 对于关键独立节点可以采用双机热备技术进行切换。

    • 数据库数据的安全性可以通过磁盘阵列的冗余配置和主备数据库来解决。

主要学习资料: 请自行google。

  • 《1.4亿在线背后的故事》;

  • 《BasicDB的架构演变》;

  • 《微信之道-至简》;

本文出自51博客 “永远的朋友” ,转载请务必保留此出处http://yaocoder.blog.51cto.com/2668309/1412029

posted @ 2017-05-15 14:22 小马歌 阅读(40) | 评论 (0)编辑 收藏

2017年3月1日

     摘要: from:https://zhangge.net/4703.html昨天,同事告诉我发现一个诡异的问题,grep无法搜索shell中的变量,着实很惊讶。到他所说的服务器上试了下,还真是不行!大概就是这样一个要求:①、有个文本为userid.txt,里面每一行一个用户id,类似如下:Shell1234500010003000500070009②、另外还有一个文本为record...  阅读全文
posted @ 2017-03-01 16:59 小马歌 阅读(55) | 评论 (0)编辑 收藏

2016年10月25日

来自: http://tonybai.com/2016/02/26/deploy-a-private-docker-registry/

安装部署一个私有的Docker Registry是引入、学习和使用 Docker 这门技术的必经之路之一。尤其是当Docker被所在组织接受,更多人、项目和产品开始接触和使用Docker时,存储和分发自制的Docker image便成了刚需。Docker Registry一如既往的继承了“Docker坑多”的特点,为此这里将自己搭建”各类”Registry过程中执行的步骤、遇到的问题记录下来,为己备忘,为他参考。

Docker在2015年推出了 distribution 项目,即Docker Registry 2。相比于 old registry ,Registry 2使用Go实现,在安全性、性能方面均有大幅改进。Registry设计了全新的Rest API,并且在image存储格式等方面不再兼容于old Registry。去年8月份,docker官方hub使用Registriy 2.1替代了原先的old Registry。如果你要与Registry2交互,你的Docker版本至少要是Docker 1.6。

Docker的开发者也一直在致力于改善Registry安装和使用的体验,通过提供 官方Registry Image以及 Docker Compose工具 等来简化Registry的配置。不过在本文中,我们只是利用Docker以及Registry的官方Image来部署Registry,这样更便于全面了解Registry的部署配置细节。

Registry2在镜像存储方面不仅支持本地盘,还支持诸多主流第三方存储方案。通过分布式存储系统你还可以实现一个分布式Docker Registry服务。这里仅以本地盘以及single node registry2为例。

一、环境

这里还是复用以往文章中的Docker环境:

Docker Registry Server: 10.10.105.71 Ubuntu 14.04 3.16.0-57-generic;docker 1.9.1

其他两个工作Server:
10.10.105.72 Ubuntu 14.04 3.19.0-25-generic; docker 1.9.1
10.10.126.101 Ubuntu 12.04 3.16.7-013607-generic; docker 1.9.1

本次Registry使用当前最新stable版本:Registry 2.3.0。由于镜像采用本地磁盘存储,root分区较小,需要映射使用其他volume。

二、初次搭建

本以为Docker Registry的搭建是何其简单的,甚至简单到通过一行命令就可以完成的。比如我们在Registry Server上执行:

在~/dockerregistry下,执行:

$sudo docker run -d -p 5000:5000 -v `pwd`/data:/var/lib/registry --restart=always --name registry registry:2
Unable to find image 'registry:2' locally
2: Pulling from library/registry
f32095d4ba8a: Pull complete
9b607719a62a: Pull complete
973de4038269: Pull complete
2867140211c1: Pull complete
8da16446f5ca: Pull complete
fd8c38b8b68d: Pull complete
136640b01f02: Pull complete
e039ba1c0008: Pull complete
c457c689c328: Pull complete
Digest: sha256:339d702cf9a4b0aa665269cc36255ee7ce424412d56bee9ad8a247afe8c49ef1
Status: Downloaded newer image for registry:2
e9088ef901cb00546c59f89defa4625230f4b36b0a44b3713f38ab3d2a5a2b44

$ docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             VIRTUAL SIZE
registry            2                   c457c689c328        9 days ago          165.7 MB

$ docker ps
CONTAINER ID        IMAGE               COMMAND                  CREATED              STATUS              PORTS                    NAMES
e9088ef901cb        registry:2          "/bin/registry /etc/d"   About a minute ago   Up About a minute   0.0.0.0:5000->5000/tcp   registry

Registry container已经跑起来了,其启动日志可以通过:docker logs registry查看。

我们在71本地给busybox:latest打一个tag,并尝试将新tag下的image push到Registry中去:

$ docker tag busybox:latest 10.10.105.71:5000/tonybai/busybox:latest
$ docker images
REPOSITORY                          TAG                 IMAGE ID            CREATED             VIRTUAL SIZE
registry                            2                   c457c689c328        9 days ago          165.7 MB
busybox                             latest              65e4158d9625        9 days ago          1.114 MB
10.10.105.71:5000/tonybai/busybox   latest              65e4158d9625        9 days ago          1.114 MB
... ...

push到Registry中:

$ docker push 10.10.105.71:5000/tonybai/busybox
The push refers to a repository [10.10.105.71:5000/tonybai/busybox] (len: 1)
unable to ping registry endpoint https://10.10.105.71:5000/v0/
v2 ping attempt failed with error: Get https://10.10.105.71:5000/v2/: Tunnel or SSL Forbidden
 v1 ping attempt failed with error: Get https://10.10.105.71:5000/v1/_ping: Tunnel or SSL Forbidden

出错了!简单分析了一下,可能是71上docker daemon配置中加了http代理的缘故,导致无法ping通registry endpoint。于是在/etc/default/docker中注释掉export http_proxy=”xxx”的设置,并重启docker daemon。

再次尝试push:

$ docker push 10.10.105.71:5000/tonybai/busybox
The push refers to a repository [10.10.105.71:5000/tonybai/busybox] (len: 1)
unable to ping registry endpoint https://10.10.105.71:5000/v0/
v2 ping attempt failed with error: Get https://10.10.105.71:5000/v2/: tls: oversized record received with length 20527
 v1 ping attempt failed with error: Get https://10.10.105.71:5000/v1/_ping: tls: oversized record received with length 20527

虽然还是失败,但错误信息已有所不同了。这次看来连接是可以建立的,但client端通过https访问server端,似乎想tls通信,但这一过程并未完成。

在其他机器上尝试push image到registry也遇到了同样的错误输出,如下:

10.10.105.72:

$ docker push 10.10.105.71:5000/tonybai/ubuntu
The push refers to a repository [10.10.105.71:5000/tonybai/ubuntu] (len: 1)
unable to ping registry endpoint https://10.10.105.71:5000/v0/
v2 ping attempt failed with error: Get https://10.10.105.71:5000/v2/: tls: oversized record received with length 20527
 v1 ping attempt failed with error: Get https://10.10.105.71:5000/v1/_ping: tls: oversized record received with length 20527

从错误信息来看,client与Registry交互,默认将采用https访问,但我们在install Registry时并未配置指定任何tls相关的key和crt文件,https访问定然失败。要想弄清这个问题,只能查看 Registry Manual 。

三、Insecure Registry

Registry的文档还是相对详尽的。在文档中,我们找到了 Insecure Registry ,即接收plain http访问的Registry的配置和使用方法,虽然这不是官方推荐的。

实际上对于我们内部网络而言,Insecure Registry基本能满足需求,部署过程也避免了secure registry的那些繁琐步骤,比如制作和部署证书等。

为了搭建一个Insecure Registry,我们需要先清理一下上面已经启动的Registry容器。

$ docker stop registry
registry
$ docker rm registry
registry

修改Registry server上的Docker daemon的配置,为DOCKER_OPTS增加–insecure-registry:

DOCKER_OPTS="--insecure-registry 10.10.105.71:5000 ....

重启Docker Daemon,启动Registry容器:

$ sudo service docker restart
docker stop/waiting
docker start/running, process 6712
$ sudo docker run -d -p 5000:5000 -v `pwd`/data:/var/lib/registry --restart=always --name registry registry:2
5966e92fce9c34705050e19368d19574e021a272ede1575385ef35ecf5cea019

尝试再次Push image:

$ docker push 10.10.105.71:5000/tonybai/busybox
The push refers to a repository [10.10.105.71:5000/tonybai/busybox] (len: 1)
65e4158d9625: Pushed
5506dda26018: Pushed
latest: digest: sha256:800f2d4558acd67f52262fbe170c9fc2e67efaa6f230a74b41b555e6fcca2892 size: 2739

这回push ok!

我们将本地的tag做untag处理,再从Registry pull相关image:

$ docker images
REPOSITORY                          TAG                 IMAGE ID            CREATED             VIRTUAL SIZE
registry                            2                   c457c689c328        9 days ago          165.7 MB
10.10.105.71:5000/tonybai/busybox   latest              65e4158d9625        9 days ago          1.114 MB
busybox                             latest              65e4158d9625        9 days ago          1.114 MB
ubuntu                              14.04               6cc0fc2a5ee3        5 weeks ago         187.9 MB

$ docker rmi 10.10.105.71:5000/tonybai/busybox
Untagged: 10.10.105.71:5000/tonybai/busybox:latest

$ docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             VIRTUAL SIZE
registry            2                   c457c689c328        9 days ago          165.7 MB
busybox             latest              65e4158d9625        9 days ago          1.114 MB
ubuntu              14.04               6cc0fc2a5ee3        5 weeks ago         187.9 MB

$ docker pull 10.10.105.71:5000/tonybai/busybox
Using default tag: latest
latest: Pulling from tonybai/busybox
Digest: sha256:800f2d4558acd67f52262fbe170c9fc2e67efaa6f230a74b41b555e6fcca2892
Status: Downloaded newer image for 10.10.105.71:5000/tonybai/busybox:latest

$ docker images
REPOSITORY                          TAG                 IMAGE ID            CREATED             VIRTUAL SIZE
registry                            2                   c457c689c328        9 days ago          165.7 MB
10.10.105.71:5000/tonybai/busybox   latest              65e4158d9625        9 days ago          1.114 MB
busybox                             latest              65e4158d9625        9 days ago          1.114 MB
ubuntu                              14.04               6cc0fc2a5ee3        5 weeks ago         187.9 MB

可以看到:Pull过程也很顺利。

在Private Registry2中查看或检索Repository或images, 将不能用docker search :

$ docker search 10.10.105.71:5000/tonybai/busybox/
Error response from daemon: Unexpected status code 404

但通过v2版本的API,我们可以实现相同目的:

$curl  http://10.10.105.71:5000/v2/_catalog
{"repositories":["tonybai/busybox"]}

$ curl  http://10.10.105.71:5000/v2/tonybai/busybox/tags/list
{"name":"tonybai/busybox","tags":["latest"]}

在其他主机上,我们尝试pull busybox:

10.10.105.72:

$docker pull 10.10.105.71:5000/tonybai/busybox
Using default tag: latest
Error response from daemon: unable to ping registry endpoint https://10.10.105.71:5000/v0/
v2 ping attempt failed with error: Get https://10.10.105.71:5000/v2/: tls: oversized record received with length 20527
 v1 ping attempt failed with error: Get https://10.10.105.71:5000/v1/_ping: tls: oversized record received with length 20527

我们发现依旧不能pull和push!在Registry手册中讲到,如果采用insecure registry的模式,那么所有与Registry交互的主机上的Docker Daemon都要配置:–insecure-registry选项。

我们按照上面的配置方法,修改105.72上的/etc/default/docker,重启Docker daemon,再执行pull/push就会得到正确的结果:

$ sudo vi /etc/default/docker
$ sudo service docker restart
docker stop/waiting
docker start/running, process 10614
$ docker pull 10.10.105.71:5000/tonybai/busybox
Using default tag: latest
latest: Pulling from tonybai/busybox
5506dda26018: Pull complete
65e4158d9625: Pull complete
Digest: sha256:800f2d4558acd67f52262fbe170c9fc2e67efaa6f230a74b41b555e6fcca2892
Status: Downloaded newer image for 10.10.105.71:5000/tonybai/busybox:latest

$ docker images
REPOSITORY                          TAG                 IMAGE ID            CREATED             VIRTUAL SIZE
ubuntu                              14.04               36248ae4a9ac        8 days ago          187.9 MB
10.10.105.71:5000/tonybai/ubuntu    14.04               36248ae4a9ac        8 days ago          187.9 MB
10.10.105.71:5000/tonybai/busybox   latest              65e4158d9625        9 days ago          1.114 MB

$ docker push 10.10.105.71:5000/tonybai/ubuntu
The push refers to a repository [10.10.105.71:5000/tonybai/ubuntu] (len: 1)
36248ae4a9ac: Pushed
8ea5373bf5a6: Pushed
2e0188208e83: Pushed
e3c70beaa378: Pushed
14.04: digest: sha256:72e56686cb9fb38438f0fd68fecf02ef592ce2ef7069bbf97802d959d568c5cc size: 6781

四、Secure Registry

Docker官方是推荐你采用Secure Registry的工作模式的,即transport采用tls。这样我们就需要为Registry配置tls所需的key和crt文件了。

我们首先清理一下环境,将上面的Insecure Registry停掉并rm掉;将各台主机上Docker Daemon的DOCKER_OPTS配置中的–insecure-registry去掉,并重启Docker Daemon。

如果你拥有一个域名,域名下主机提供Registry服务,并且你拥有某知名CA签署的证书文件,那么你可以建立起一个Secure Registry。不过我这里没有现成的证书,只能使用自签署的证书。严格来讲,使用自签署的证书在Docker官方眼中依旧属于Insecure,不过这里只是借助自签署的证书来说明一下Secure Registry的部署步骤罢了。

1、制作自签署证书

如果你有知名CA签署的证书,那么这步可直接忽略。

$ openssl req -newkey rsa:2048 -nodes -sha256 -keyout certs/domain.key -x509 -days 365 -out certs/domain.crt
Generating a 2048 bit RSA private key
..............+++
............................................+++
writing new private key to 'certs/domain.key'
-----
You are about to be asked to enter information that will be incorporated
into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN.
There are quite a few fields but you can leave some blank
For some fields there will be a default value,
If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) [AU]:CN
State or Province Name (full name) [Some-State]:Liaoning
Locality Name (eg, city) []:shenyang
Organization Name (eg, company) [Internet Widgits Pty Ltd]:foo
Organizational Unit Name (eg, section) []:bar
Common Name (e.g. server FQDN or YOUR name) []:mydockerhub.com
Email Address []:bigwhite.cn@gmail.com

2、启动Secure Registry

启动带证书的Registry:

$ docker run -d -p 5000:5000 --restart=always --name registry \
  -v `pwd`/data:/var/lib/registry \
  -v `pwd`/certs:/certs \
  -e REGISTRY_HTTP_TLS_CERTIFICATE=/certs/domain.crt \
  -e REGISTRY_HTTP_TLS_KEY=/certs/domain.key \
  registry:2
35e8ce77dd455f2bd50854e4581cd52be8a137f4aaea717239b6d676c5ea5777

由于证书的CN是mydockerhub.com,我们需要修改一下/etc/hosts文件:

10.10.105.71 mydockerhub.com

重新为busybox制作一个tag:

$docker tag busybox:latest mydockerhub.com:5000/tonybai/busybox:latest

Push到Registry:

$ docker push mydockerhub.com:5000/tonybai/busybox
The push refers to a repository [mydockerhub.com:5000/tonybai/busybox] (len: 1)
unable to ping registry endpoint https://mydockerhub.com:5000/v0/
v2 ping attempt failed with error: Get https://mydockerhub.com:5000/v2/: x509: certificate signed by unknown authority
 v1 ping attempt failed with error: Get https://mydockerhub.com:5000/v1/_ping: x509: certificate signed by unknown authority

push失败了!从错误日志来看,docker client认为server传输过来的证书的签署方是一个unknown authority(未知的CA),因此验证失败。我们需要让docker client安装我们的CA证书:

$ sudo mkdir -p /etc/docker/certs.d/mydockerhub.com:5000
$ sudo cp certs/domain.crt /etc/docker/certs.d/mydockerhub.com:5000/ca.crt
$ sudo service docker restart //安装证书后,重启Docker Daemon

再执行Push,我们看到了成功的输出日志。由于data目录下之前已经被push了tonybai/busybox repository,因此提示“已存在”:

$docker push mydockerhub.com:5000/tonybai/busybox
The push refers to a repository [mydockerhub.com:5000/tonybai/busybox] (len: 1)
65e4158d9625: Image already exists
5506dda26018: Image already exists
latest: digest: sha256:800f2d4558acd67f52262fbe170c9fc2e67efaa6f230a74b41b555e6fcca2892 size: 2739

3、外部访问Registry

我们换其他机器试试访问这个secure registry。根据之前的要求,我们照猫画虎的修改一下hosts文件,安装ca.cert,去除–insecure-registry选项,并重启Docker daemon。之后尝试从registry pull image:

$ docker pull mydockerhub.com:5000/tonybai/busybox
Using default tag: latest
latest: Pulling from tonybai/busybox

Digest: sha256:800f2d4558acd67f52262fbe170c9fc2e67efaa6f230a74b41b555e6fcca2892
Status: Downloaded newer image for mydockerhub.com:5000/tonybai/busybox:latest

$ docker images
REPOSITORY                             TAG                 IMAGE ID            CREATED             VIRTUAL SIZE
10.10.105.71:5000/tonybai/ubuntu       14.04               36248ae4a9ac        9 days ago          187.9 MB
ubuntu                                 14.04               36248ae4a9ac        9 days ago          187.9 MB
10.10.105.71:5000/tonybai/busybox      latest              65e4158d9625        9 days ago          1.114 MB
mydockerhub.com:5000/tonybai/busybox   latest              65e4158d9625        9 days ago          1.114 MB

这样来看,如果使用自签署的证书,那么所有要与Registry交互的Docker主机都需要安装mydockerhub.com的ca.crt(domain.crt)。但如果你使用知名CA,这一步也就可以忽略。

五、Registry的鉴权管理

Registry提供了一种基础的鉴权方式。我们通过下面步骤即可为Registry加上基础鉴权:

在Register server上,为Registry增加foo用户,密码foo123:(之前需要停掉已有的Registry,并删除之)

//生成鉴权密码文件
$ mkdir auth
$ docker run --entrypoint htpasswd registry:2 -Bbn foo foo123  > auth/htpasswd
$ ls auth
htpasswd

//启动带鉴权功能的Registry:
$ docker run -d -p 5000:5000 --restart=always --name registry \
   -v `pwd`/auth:/auth \
   -e "REGISTRY_AUTH=htpasswd" \
   -e "REGISTRY_AUTH_HTPASSWD_REALM=Registry Realm" \
   -e REGISTRY_AUTH_HTPASSWD_PATH=/auth/htpasswd \
   -v `pwd`/data:/var/lib/registry \
   -v `pwd`/certs:/certs \
   -e REGISTRY_HTTP_TLS_CERTIFICATE=/certs/domain.crt \
   -e REGISTRY_HTTP_TLS_KEY=/certs/domain.key \
   registry:2
199ad0b3591fb9613b21b1c96f017267f3c39661a7025d30df636c6805e7ab50

在105.72上,我们尝试push image到Registry:

$ docker push mydockerhub.com:5000/tonybai/busybox
The push refers to a repository [mydockerhub.com:5000/tonybai/busybox] (len: 1)
65e4158d9625: Image push failed
Head https://mydockerhub.com:5000/v2/tonybai/busybox/blobs/sha256:a3ed95caeb02ffe68cdd9fd84406680ae93d633cb16422d00e8a7c22955b46d4: no basic auth credentials

错误信息提示:鉴权失败。

在72上执行docker login:

$docker login mydockerhub.com:5000
Username: foo
Password:
Email: bigwhite.cn@gmail.com
WARNING: login credentials saved in /home/baiming/.docker/config.json
Login Succeeded

login成功后,再行Push:

$ docker push mydockerhub.com:5000/tonybai/busybox
The push refers to a repository [mydockerhub.com:5000/tonybai/busybox] (len: 1)
65e4158d9625: Image already exists
5506dda26018: Image already exists
latest: digest: sha256:800f2d4558acd67f52262fbe170c9fc2e67efaa6f230a74b41b555e6fcca2892 size: 2739

Push ok!

六、Registry中images的管理

前面提到过,通过V2版Rest API可以查询Repository和images:

$ curl --cacert domain.crt  --basic --user foo:foo123 https://mydockerhub.com:5000/v2/_catalog
{"repositories":["tonybai/busybox","tonybai/ubuntu"]}

但如果要删除Registry中的Repository或某个tag的Image,目前v2还不支持,原因见 Registry的roadmap中的说明 。

不过如果你的Registry的存储引擎使用的是本地盘,倒是有一些第三方脚本可供使用,比如:delete-docker-registry-image 。

七、小结

Registry2发布不到1年,目前还有许多问题待解决,就比如delete image的问题,相信在2.4以及后续版本这些问题会被逐个解决掉或能找到一个相对理想的方案。

posted @ 2016-10-25 14:24 小马歌 阅读(66) | 评论 (0)编辑 收藏
仅列出标题  下一页