五分钟理解一致性哈希算法(consistent hashing)

    一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题,使得分布式哈希(DHT)可以在P2P环境中真正得到应用。
    一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义:
1、平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
2、单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。
3、分散性(Spread):在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。
4、负载(Load):负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同 的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。
    在分布式集群中,对机器的添加删除,或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法,那么在有机器添加或者删除后,很多原有的数据就无法找到了,这样严重的违反了单调性原则。接下来主要讲解一下一致性哈希算法是如何设计的:
环形Hash空间
按照常用的hash算法来将对应的key哈希到一个具有2^32次方个桶的空间中,即0~(2^32)-1的数字空间中。现在我们可以将这些数字头尾相连,想象成一个闭合的环形。如下图
                                                                         
把数据通过一定的hash算法处理后映射到环上
现在我们将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值,然后散列到Hash环上。如下图:
    Hash(object1) = key1;
    Hash(object2) = key2;
    Hash(object3) = key3;
    Hash(object4) = key4;
                                                           
将机器通过hash算法映射到环上
在采用一致性哈希算法的分布式集群中将新的机器加入,其原理是通过使用与对象存储一样的Hash算法将机器也映射到环中(一般情况下对机器的hash计算是采用机器的IP或者机器唯一的别名作为输入值),然后以顺时针的方向计算,将所有对象存储到离自己最近的机器中。
假设现在有NODE1,NODE2,NODE3三台机器,通过Hash算法得到对应的KEY值,映射到环中,其示意图如下:
Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;
                                                             
通过上图可以看出对象与机器处于同一哈希空间中,这样按顺时针转动object1存储到了NODE1中,object3存储到了NODE2中,object2、object4存储到了NODE3中。在这样的部署环境中,hash环是不会变更的,因此,通过算出对象的hash值就能快速的定位到对应的机器中,这样就能找到对象真正的存储位置了。
机器的删除与添加
普通hash求余算法最为不妥的地方就是在有机器的添加或者删除之后会照成大量的对象存储位置失效,这样就大大的不满足单调性了。下面来分析一下一致性哈希算法是如何处理的。
1. 节点(机器)的删除
    以上面的分布为例,如果NODE2出现故障被删除了,那么按照顺时针迁移的方法,object3将会被迁移到NODE3中,这样仅仅是object3的映射位置发生了变化,其它的对象没有任何的改动。如下图:
                                                              
2. 节点(机器)的添加
    如果往集群中添加一个新的节点NODE4,通过对应的哈希算法得到KEY4,并映射到环中,如下图:
                                                              
    通过按顺时针迁移的规则,那么object2被迁移到了NODE4中,其它对象还保持这原有的存储位置。通过对节点的添加和删除的分析,一致性哈希算法在保持了单调性的同时,还是数据的迁移达到了最小,这样的算法对分布式集群来说是非常合适的,避免了大量数据迁移,减小了服务器的的压力。
平衡性
根据上面的图解分析,一致性哈希算法满足了单调性和负载均衡的特性以及一般hash算法的分散性,但这还并不能当做其被广泛应用的原由,因为还缺少了平衡性。下面将分析一致性哈希算法是如何满足平衡性的。hash算法是不保证平衡的,如上面只部署了NODE1和NODE3的情况(NODE2被删除的图),object1存储到了NODE1中,而object2、object3、object4都存储到了NODE3中,这样就照成了非常不平衡的状态。在一致性哈希算法中,为了尽可能的满足平衡性,其引入了虚拟节点。
    ——“虚拟节点”( virtual node )是实际节点(机器)在 hash 空间的复制品( replica ),一实际个节点(机器)对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以hash值排列。
以上面只部署了NODE1和NODE3的情况(NODE2被删除的图)为例,之前的对象在机器上的分布很不均衡,现在我们以2个副本(复制个数)为例,这样整个hash环中就存在了4个虚拟节点,最后对象映射的关系图如下:
                                                                 
根据上图可知对象的映射关系:object1->NODE1-1,object2->NODE1-2,object3->NODE3-2,object4->NODE3-1。通过虚拟节点的引入,对象的分布就比较均衡了。那么在实际操作中,正真的对象查询是如何工作的呢?对象从hash到虚拟节点到实际节点的转换如下图:
                                         
“虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设NODE1的IP地址为192.168.1.100。引入“虚拟节点”前,计算 cache A 的 hash 值:
Hash(“192.168.1.100”);
引入“虚拟节点”后,计算“虚拟节”点NODE1-1和NODE1-2的hash值:
Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2

btree索引和hash索引的区别

来源:https://www.cnblogs.com/ziqiumeng/p/7680204.html

Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引。可能很多人又有疑问了,既然 Hash 索引的效率要比 B-Tree 高很多,为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢?任何事物都是有两面性的,Hash 索引也一样,虽然 Hash 索引效率高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端,主要有以下这些。

(1)Hash 索引仅仅能满足”=”,”IN”和”<=>”查询,不能使用范围查询。

由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值,所以它只能用于等值的过滤,不能用于基于范围的过滤,因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系,并不能保证和Hash运算前完全一样。

(2)Hash 索引无法被用来避免数据的排序操作。

由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值,而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样,所以数据库无法利用索引的数据来避免任何排序运算;

(3)Hash 索引不能利用部分索引键查询。

对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。

(4)Hash 索引在任何时候都不能避免表扫描。

前面已经知道,Hash 索引是将索引键通过 Hash 运算之后,将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中,由于不同索引键存在相同 Hash 值,所以即使取满足某个 Hash 键值的数据的记录条数,也无法从 Hash 索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。

(5)Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

对于选择性比较低的索引键,如果创建 Hash 索引,那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下

2. B-Tree索引
B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL 中是如此,实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型,这主要是因为 B-Tree 索引的存储结构在数据库的数据检 索中有非常优异的表现。        一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf Node ,而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree 索引当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree ,也就是在 B-Tree 数据结构的基础上做了很小的改造,在每一个  Leaf Node 上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息,这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。        在 Innodb 存储引擎中,存在两种不同形式的索引,一种是 Cluster 形式的主键索引( Primary Key ),另外一种则是和其他存储引擎(如 MyISAM 存储引擎)存放形式基本相同的普通 B-Tree 索引,这种索引在 Innodb 存储引擎中被称为 Secondary Index 。下面我们通过图示来针对这两种索引的存放  形式做一个比较。
MySQL的btree索引和hash索引的区别
图示中左边为 Clustered 形式存放的 Primary Key ,右侧则为普通的 B-Tree 索引。两种 Root Node 和 Branch Nodes 方面都还是完全一样的。而 Leaf Nodes 就出现差异了。在 Prim中, Leaf Nodes 存放的是表的实际数据,不仅仅包括主键字段的数据,还包括其他字段的数据据以主键值有序的排列。而 Secondary Index 则和其他普通的 B-Tree 索引没有太大的差异,Leaf Nodes 出了存放索引键 的相关信息外,还存放了 Innodb 的主键值。
所以,在 Innodb 中如果通过主键来访问数据效率是非常高的,而如果是通过 Secondary Index 来访问数据的话, Innodb 首先通过 Secondary Index 的相关信息,通过相应的索引键检索到 Leaf Node之后,需要再通过 Leaf Node 中存放的主键值再通过主键索引来获取相应的数据行。MyISAM 存储引擎的主键索引和非主键索引差别很小,只不过是主键索引的索引键是一个唯一且非空 的键而已。而且 MyISAM 存储引擎的索引和 Innodb 的 Secondary Index 的存储结构也基本相同,主要的区别只是 MyISAM 存储引擎在 Leaf Nodes 上面出了存放索引键信息之外,再存放能直接定位到 MyISAM 数据文件中相应的数据行的信息(如 Row Number ),但并不会存放主键的键值信息

MySQL索引背后的数据结构及算法原理

来源:http://blog.codinglabs.org/articles/theory-of-mysql-index.html
作者 张洋 | 发布于 2011-10-18
MySQL 索引 B树 优化

摘要

本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论。

文章主要内容分为三个部分。

第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。

第二部分结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。

第三部分根据上面的理论基础,讨论MySQL中高性能使用索引的策略。

数据结构及算法基础

索引的本质

MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。

我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

看一个例子:

图1

图1展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)O(log2n)的复杂度内获取到相应数据。

虽然这是一个货真价实的索引,但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black tree)实现的,原因会在下文介绍。

B-Tree和B+Tree

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构,在本文的下一节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此广泛用于索引,这一节先单纯从数据结构角度描述它们。

B-Tree

为了描述B-Tree,首先定义一条数据记录为一个二元组[key, data],key为记录的键值,对于不同数据记录,key是互不相同的;data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构:

d为大于1的一个正整数,称为B-Tree的度。

h为一个正整数,称为B-Tree的高度。

每个非叶子节点由n-1个key和n个指针组成,其中d<=n<=2d。

每个叶子节点最少包含一个key和两个指针,最多包含2d-1个key和2d个指针,叶节点的指针均为null 。

所有叶节点具有相同的深度,等于树高h。

key和指针互相间隔,节点两端是指针。

一个节点中的key从左到右非递减排列。

所有节点组成树结构。

每个指针要么为null,要么指向另外一个节点。

如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于v(key1)v(key1),其中v(key1)v(key1)为node的第一个key的值。

如果某个指针在节点node最右边且不为null,则其指向节点的所有key大于v(keym)v(keym),其中v(keym)v(keym)为node的最后一个key的值。

如果某个指针在节点node的左右相邻key分别是keyikeyikeyi+1keyi+1且不为null,则其指向节点的所有key小于v(keyi+1)v(keyi+1)且大于v(keyi)v(keyi)

图2是一个d=2的B-Tree示意图。

图2

由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。B-Tree上查找算法的伪代码如下:

  1. BTree_Search(node, key) {
  2. if(node == null) return null;
  3. foreach(node.key)
  4. {
  5. if(node.key[i] == key) return node.data[i];
  6. if(node.key[i] > key) return BTree_Search(point[i]->node);
  7. }
  8. return BTree_Search(point[i+1]->node);
  9. }
  10. data = BTree_Search(root, my_key);

关于B-Tree有一系列有趣的性质,例如一个度为d的B-Tree,设其索引N个key,则其树高h的上限为logd((N+1)/2)logd((N+1)/2),检索一个key,其查找节点个数的渐进复杂度为O(logdN)O(logdN)。从这点可以看出,B-Tree是一个非常有效率的索引数据结构。另外,由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质,本文不打算完整讨论B-Tree这些内容,因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法,有兴趣的朋友可以在本文末的参考文献一栏找到相应的资料进行阅读。

B+Tree

B-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比,B+Tree有以下不同点:

每个节点的指针上限为2d而不是2d+1。

内节点不存储data,只存储key;叶子节点不存储指针。

图3是一个简单的B+Tree示意。

图3

由于并不是所有节点都具有相同的域,因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同,虽然B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以在实现中B-Tree往往对每个节点申请同等大小的空间。

一般来说,B+Tree比B-Tree更适合实现外存储索引结构,具体原因与外存储器原理及计算机存取原理有关,将在下面讨论。

带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针。

图4

如图4所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能,例如图4中如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。

这一节对B-Tree和B+Tree进行了一个简单的介绍,下一节结合存储器存取原理介绍为什么目前B+Tree是数据库系统实现索引的首选数据结构。

为什么使用B-Tree(B+Tree)

上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。

图5

从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

主存的存取过程如下:

当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

磁盘存取原理

上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

图6是磁盘的整体结构示意图。

图6

一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

图7是磁盘结构的示意图。

图7

盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

当一个数据被用到时,其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

B-/+Tree索引的性能分析

到这里终于可以分析B-/+Tree索引的性能了。

上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析,根据B-Tree的定义,可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:

每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

综上所述,用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。

上文还说过,B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小:

dmax=floor(pagesize/(keysize+datasize+pointsize))dmax=floor(pagesize/(keysize+datasize+pointsize))

floor表示向下取整。由于B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。

这一章从理论角度讨论了与索引相关的数据结构与算法问题,下一章将讨论B+Tree是如何具体实现为MySQL中索引,同时将结合MyISAM和InnDB存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。

MySQL索引实现

在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

图8

这里设表一共有三列,假设我们以Col1为主键,则图8是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:

图9

同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

图10

图10是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,图11为定义在Col3上的一个辅助索引:

图11

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

下一章将具体讨论这些与索引有关的优化策略。

索引使用策略及优化

MySQL的优化主要分为结构优化(Scheme optimization)和查询优化(Query optimization)。本章讨论的高性能索引策略主要属于结构优化范畴。本章的内容完全基于上文的理论基础,实际上一旦理解了索引背后的机制,那么选择高性能的策略就变成了纯粹的推理,并且可以理解这些策略背后的逻辑。

示例数据库

为了讨论索引策略,需要一个数据量不算小的数据库作为示例。本文选用MySQL官方文档中提供的示例数据库之一:employees。这个数据库关系复杂度适中,且数据量较大。下图是这个数据库的E-R关系图(引用自MySQL官方手册):

图12

MySQL官方文档中关于此数据库的页面为http://dev.mysql.com/doc/employee/en/employee.html。里面详细介绍了此数据库,并提供了下载地址和导入方法,如果有兴趣导入此数据库到自己的MySQL可以参考文中内容。

最左前缀原理与相关优化

高效使用索引的首要条件是知道什么样的查询会使用到索引,这个问题和B+Tree中的“最左前缀原理”有关,下面通过例子说明最左前缀原理。

这里先说一下联合索引的概念。在上文中,我们都是假设索引只引用了单个的列,实际上,MySQL中的索引可以以一定顺序引用多个列,这种索引叫做联合索引,一般的,一个联合索引是一个有序元组<a1, a2, …, an>,其中各个元素均为数据表的一列,实际上要严格定义索引需要用到关系代数,但是这里我不想讨论太多关系代数的话题,因为那样会显得很枯燥,所以这里就不再做严格定义。另外,单列索引可以看成联合索引元素数为1的特例。

以employees.titles表为例,下面先查看其上都有哪些索引:

  1. SHOW INDEX FROM employees.titles;
  2. +——–+————+———-+————–+————-+———–+————-+——+————+
  3. | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Null | Index_type |
  4. +——–+————+———-+————–+————-+———–+————-+——+————+
  5. | titles | 0 | PRIMARY | 1 | emp_no | A | NULL | | BTREE |
  6. | titles | 0 | PRIMARY | 2 | title | A | NULL | | BTREE |
  7. | titles | 0 | PRIMARY | 3 | from_date | A | 443308 | | BTREE |
  8. | titles | 1 | emp_no | 1 | emp_no | A | 443308 | | BTREE |
  9. +——–+————+———-+————–+————-+———–+————-+——+————+

从结果中可以到titles表的主索引为<emp_no, title, from_date>,还有一个辅助索引<emp_no>。为了避免多个索引使事情变复杂(MySQL的SQL优化器在多索引时行为比较复杂),这里我们将辅助索引drop掉:

  1. ALTER TABLE employees.titles DROP INDEX emp_no;

这样就可以专心分析索引PRIMARY的行为了。

情况一:全列匹配。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND title=‘Senior Engineer’ AND from_date=‘1986-06-26’;
  2. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+
  5. | 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | |
  6. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+

很明显,当按照索引中所有列进行精确匹配(这里精确匹配指“=”或“IN”匹配)时,索引可以被用到。这里有一点需要注意,理论上索引对顺序是敏感的,但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引,例如我们将where中的条件顺序颠倒:

  1. EXPLAIN SELECT * FROM employees.titles WHERE from_date=‘1986-06-26’ AND emp_no=‘10001’ AND title=‘Senior Engineer’;
  2. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+
  5. | 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | |
  6. +—-+————-+——–+——-+—————+———+———+——————-+——+——-+

效果是一样的。

情况二:最左前缀匹配。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’;
  2. +—-+————-+——–+——+—————+———+———+——-+——+——-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+———+———+——-+——+——-+
  5. | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | |
  6. +—-+————-+——–+——+—————+———+———+——-+——+——-+

当查询条件精确匹配索引的左边连续一个或几个列时,如<emp_no>或<emp_no, title>,所以可以被用到,但是只能用到一部分,即条件所组成的最左前缀。上面的查询从分析结果看用到了PRIMARY索引,但是key_len为4,说明只用到了索引的第一列前缀。

情况三:查询条件用到了索引中列的精确匹配,但是中间某个条件未提供。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND from_date=‘1986-06-26’;
  2. +—-+————-+——–+——+—————+———+———+——-+——+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+———+———+——-+——+————-+
  5. | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where |
  6. +—-+————-+——–+——+—————+———+———+——-+——+————-+

此时索引使用情况和情况二相同,因为title未提供,所以查询只用到了索引的第一列,而后面的from_date虽然也在索引中,但是由于title不存在而无法和左前缀连接,因此需要对结果进行扫描过滤from_date(这里由于emp_no唯一,所以不存在扫描)。如果想让from_date也使用索引而不是where过滤,可以增加一个辅助索引<emp_no, from_date>,此时上面的查询会使用这个索引。除此之外,还可以使用一种称之为“隔离列”的优化方法,将emp_no与from_date之间的“坑”填上。

首先我们看下title一共有几种不同的值:

  1. SELECT DISTINCT(title) FROM employees.titles;
  2. +——————–+
  3. | title |
  4. +——————–+
  5. | Senior Engineer |
  6. | Staff |
  7. | Engineer |
  8. | Senior Staff |
  9. | Assistant Engineer |
  10. | Technique Leader |
  11. | Manager |
  12. +——————–+

只有7种。在这种成为“坑”的列值比较少的情况下,可以考虑用“IN”来填补这个“坑”从而形成最左前缀:

  1. EXPLAIN SELECT * FROM employees.titles
  2. WHERE emp_no=‘10001’
  3. AND title IN (‘Senior Engineer’, ‘Staff’, ‘Engineer’, ‘Senior Staff’, ‘Assistant Engineer’, ‘Technique Leader’, ‘Manager’)
  4. AND from_date=‘1986-06-26’;
  5. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  6. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  7. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  8. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 7 | Using where |
  9. +—-+————-+——–+——-+—————+———+———+——+——+————-+

这次key_len为59,说明索引被用全了,但是从type和rows看出IN实际上执行了一个range查询,这里检查了7个key。看下两种查询的性能比较:

  1. SHOW PROFILES;
  2. +———-+————+——————————————————————————-+
  3. | Query_ID | Duration | Query |
  4. +———-+————+——————————————————————————-+
  5. | 10 | 0.00058000 | SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND from_date=‘1986-06-26’|
  6. | 11 | 0.00052500 | SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND title IN |
  7. +———-+————+——————————————————————————-+

“填坑”后性能提升了一点。如果经过emp_no筛选后余下很多数据,则后者性能优势会更加明显。当然,如果title的值很多,用填坑就不合适了,必须建立辅助索引。

情况四:查询条件没有指定索引第一列。

  1. EXPLAIN SELECT * FROM employees.titles WHERE from_date=‘1986-06-26’;
  2. +—-+————-+——–+——+—————+——+———+——+——–+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+——+———+——+——–+————-+
  5. | 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where |
  6. +—-+————-+——–+——+—————+——+———+——+——–+————-+

由于不是最左前缀,索引这样的查询显然用不到索引。

情况五:匹配某列的前缀字符串。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND title LIKE ‘Senior%’;
  2. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  5. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 56 | NULL | 1 | Using where |
  6. +—-+————-+——–+——-+—————+———+———+——+——+————-+

此时可以用到索引,但是如果通配符不是只出现在末尾,则无法使用索引。(原文表述有误,如果通配符%不出现在开头,则可以用到索引,但根据具体情况不同可能只会用其中一个前缀)

情况六:范围查询。

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no < ‘10010’ and title=‘Senior Engineer’;
  2. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  5. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where |
  6. +—-+————-+——–+——-+—————+———+———+——+——+————-+

范围列可以用到索引(必须是最左前缀),但是范围列后面的列无法用到索引。同时,索引最多用于一个范围列,因此如果查询条件中有两个范围列则无法全用到索引。

  1. EXPLAIN SELECT * FROM employees.titles
  2. WHERE emp_no < ‘10010’
  3. AND title=‘Senior Engineer’
  4. AND from_date BETWEEN ‘1986-01-01’ AND ‘1986-12-31’;
  5. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  6. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  7. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  8. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where |
  9. +—-+————-+——–+——-+—————+———+———+——+——+————-+

可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方,那就是仅用explain可能无法区分范围索引和多值匹配,因为在type中这两者都显示为range。同时,用了“between”并不意味着就是范围查询,例如下面的查询:

  1. EXPLAIN SELECT * FROM employees.titles
  2. WHERE emp_no BETWEEN ‘10001’ AND ‘10010’
  3. AND title=‘Senior Engineer’
  4. AND from_date BETWEEN ‘1986-01-01’ AND ‘1986-12-31’;
  5. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  6. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  7. +—-+————-+——–+——-+—————+———+———+——+——+————-+
  8. | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 16 | Using where |
  9. +—-+————-+——–+——-+—————+———+———+——+——+————-+

看起来是用了两个范围查询,但作用于emp_no上的“BETWEEN”实际上相当于“IN”,也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配,否则会对MySQL的行为产生困惑。

情况七:查询条件中含有函数或表达式。

很不幸,如果查询条件中含有函数或表达式,则MySQL不会为这列使用索引(虽然某些在数学意义上可以使用)。例如:

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no=‘10001’ AND left(title, 6)=‘Senior’;
  2. +—-+————-+——–+——+—————+———+———+——-+——+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+———+———+——-+——+————-+
  5. | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where |
  6. +—-+————-+——–+——+—————+———+———+——-+——+————-+

虽然这个查询和情况五中功能相同,但是由于使用了函数left,则无法为title列应用索引,而情况五中用LIKE则可以。再如:

  1. EXPLAIN SELECT * FROM employees.titles WHERE emp_no 1=‘10000’;
  2. +—-+————-+——–+——+—————+——+———+——+——–+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+——–+——+—————+——+———+——+——–+————-+
  5. | 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where |
  6. +—-+————-+——–+——+—————+——+———+——+——–+————-+

显然这个查询等价于查询emp_no为10001的函数,但是由于查询条件是一个表达式,MySQL无法为其使用索引。看来MySQL还没有智能到自动优化常量表达式的程度,因此在写查询语句时尽量避免表达式出现在查询中,而是先手工私下代数运算,转换为无表达式的查询语句。

索引选择性与前缀索引

既然索引可以加快查询速度,那么是不是只要是查询语句需要,就建上索引?答案是否定的。因为索引虽然加快了查询速度,但索引也是有代价的:索引文件本身要消耗存储空间,同时索引会加重插入、删除和修改记录时的负担,另外,MySQL在运行时也要消耗资源维护索引,因此索引并不是越多越好。一般两种情况下不建议建索引。

第一种情况是表记录比较少,例如一两千条甚至只有几百条记录的表,没必要建索引,让查询做全表扫描就好了。至于多少条记录才算多,这个个人有个人的看法,我个人的经验是以2000作为分界线,记录数不超过 2000可以考虑不建索引,超过2000条可以酌情考虑索引。

另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性(Selectivity),是指不重复的索引值(也叫基数,Cardinality)与表记录数(#T)的比值:

Index Selectivity = Cardinality / #T

显然选择性的取值范围为(0, 1],选择性越高的索引价值越大,这是由B+Tree的性质决定的。例如,上文用到的employees.titles表,如果title字段经常被单独查询,是否需要建索引,我们看一下它的选择性:

  1. SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;
  2. +————-+
  3. | Selectivity |
  4. +————-+
  5. | 0.0000 |
  6. +————-+

title的选择性不足0.0001(精确值为0.00001579),所以实在没有什么必要为其单独建索引。

有一种与索引选择性有关的索引优化策略叫做前缀索引,就是用列的前缀代替整个列作为索引key,当前缀长度合适时,可以做到既使得前缀索引的选择性接近全列索引,同时因为索引key变短而减少了索引文件的大小和维护开销。下面以employees.employees表为例介绍前缀索引的选择和使用。

从图12可以看到employees表只有一个索引<emp_no>,那么如果我们想按名字搜索一个人,就只能全表扫描了:

  1. EXPLAIN SELECT * FROM employees.employees WHERE first_name=‘Eric’ AND last_name=‘Anido’;
  2. +—-+————-+———–+——+—————+——+———+——+——–+————-+
  3. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
  4. +—-+————-+———–+——+—————+——+———+——+——–+————-+
  5. | 1 | SIMPLE | employees | ALL | NULL | NULL | NULL | NULL | 300024 | Using where |
  6. +—-+————-+———–+——+—————+——+———+——+——–+————-+

如果频繁按名字搜索员工,这样显然效率很低,因此我们可以考虑建索引。有两种选择,建<first_name>或<first_name, last_name>,看下两个索引的选择性:

  1. SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;
  2. +————-+
  3. | Selectivity |
  4. +————-+
  5. | 0.0042 |
  6. +————-+
  7. SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees;
  8. +————-+
  9. | Selectivity |
  10. +————-+
  11. | 0.9313 |
  12. +————-+

<first_name>显然选择性太低,<first_name, last_name>选择性很好,但是first_name和last_name加起来长度为30,有没有兼顾长度和选择性的办法?可以考虑用first_name和last_name的前几个字符建立索引,例如<first_name, left(last_name, 3)>,看看其选择性:

  1. SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;
  2. +————-+
  3. | Selectivity |
  4. +————-+
  5. | 0.7879 |
  6. +————-+

选择性还不错,但离0.9313还是有点距离,那么把last_name前缀加到4:

  1. SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;
  2. +————-+
  3. | Selectivity |
  4. +————-+
  5. | 0.9007 |
  6. +————-+

这时选择性已经很理想了,而这个索引的长度只有18,比<first_name, last_name>短了接近一半,我们把这个前缀索引 建上:

  1. ALTER TABLE employees.employees
  2. ADD INDEX `first_name_last_name4` (first_name, last_name(4));

此时再执行一遍按名字查询,比较分析一下与建索引前的结果:

  1. SHOW PROFILES;
  2. +———-+————+———————————————————————————+
  3. | Query_ID | Duration | Query |
  4. +———-+————+———————————————————————————+
  5. | 87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name=‘Eric’ AND last_name=‘Anido’ |
  6. | 90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name=‘Eric’ AND last_name=‘Anido’ |
  7. +———-+————+———————————————————————————+

性能的提升是显著的,查询速度提高了120多倍。

前缀索引兼顾索引大小和查询速度,但是其缺点是不能用于ORDER BY和GROUP BY操作,也不能用于Covering index(即当索引本身包含查询所需全部数据时,不再访问数据文件本身)。

InnoDB的主键选择与插入优化

在使用InnoDB存储引擎时,如果没有特别的需要,请永远使用一个与业务无关的自增字段作为主键。

经常看到有帖子或博客讨论主键选择问题,有人建议使用业务无关的自增主键,有人觉得没有必要,完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点,大多数论据都是业务层面的。如果从数据库索引优化角度看,使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。

上文讨论过InnoDB的索引实现,InnoDB使用聚集索引,数据记录本身被存于主索引(一颗B+Tree)的叶子节点上。这就要求同一个叶子节点内(大小为一个内存页或磁盘页)的各条数据记录按主键顺序存放,因此每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)。

如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:

图13

这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置:

图14

此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

因此,只要可以,请尽量在InnoDB上采用自增字段做主键。

后记

这篇文章断断续续写了半个月,主要内容就是上面这些了。不可否认,这篇文章在一定程度上有纸上谈兵之嫌,因为我本人对MySQL的使用属于菜鸟级别,更没有太多数据库调优的经验,在这里大谈数据库索引调优有点大言不惭。就当是我个人的一篇学习笔记了。

其实数据库索引调优是一项技术活,不能仅仅靠理论,因为实际情况千变万化,而且MySQL本身存在很复杂的机制,如查询优化策略和各种引擎的实现差异等都会使情况变得更加复杂。但同时这些理论是索引调优的基础,只有在明白理论的基础上,才能对调优策略进行合理推断并了解其背后的机制,然后结合实践中不断的实验和摸索,从而真正达到高效使用MySQL索引的目的。

另外,MySQL索引及其优化涵盖范围非常广,本文只是涉及到其中一部分。如与排序(ORDER BY)相关的索引优化及覆盖索引(Covering index)的话题本文并未涉及,同时除B-Tree索引外MySQL还根据不同引擎支持的哈希索引、全文索引等等本文也并未涉及。如果有机会,希望再对本文未涉及的部分进行补充吧。

参考文献

[1] Baron Scbwartz等 著,王小东等 译;高性能MySQL(High Performance MySQL);电子工业出版社,2010

[2] Michael Kofler 著,杨晓云等 译;MySQL5权威指南(The Definitive Guide to MySQL5);人民邮电出版社,2006

[3] 姜承尧 著;MySQL技术内幕-InnoDB存储引擎;机械工业出版社,2011

[4] D Comer, Ubiquitous B-tree; ACM Computing Surveys (CSUR), 1979

[5] Codd, E. F. (1970). “A relational model of data for large shared data banks”. Communications of the ACM, , Vol. 13, No. 6, pp. 377-387

[6] MySQL5.1参考手册 – http://dev.mysql.com/doc/refman/5.1/zh/index.html

Spring IOC原理总结(转)

来源:https://zhuanlan.zhihu.com/p/29344811

Spring IOC原理总结

Spring IOC原理总结

94 人赞了该文章

Spring容器高层视图

Spring 启动时读取应用程序提供的Bean配置信息,并在Spring容器中生成一份相应的Bean配置注册表,然后根据这张注册表实例化Bean,装配好Bean之间的依赖关系,为上层应用提供准备就绪的运行环境。

Bean缓存池:HashMap实现

IOC容器介绍

Spring 通过一个配置文件描述 Bean 及 Bean 之间的依赖关系,利用 Java 语言的反射功能实例化 Bean 并建立 Bean 之间的依赖关系。 Spring 的 IoC 容器在完成这些底层工作的基础上,还提供了 Bean 实例缓存、生命周期管理、 Bean 实例代理、事件发布、资源装载等高级服务。

  • BeanFactory 是 Spring 框架的基础设施,面向 Spring 本身;
  • ApplicationContext 面向使用 Spring 框架的开发者,几乎所有的应用场合我们都直接使用 ApplicationContext 而非底层的 BeanFactory。

BeanFactory

BeanFactory体系架构:

  • BeanDefinitionRegistry: Spring 配置文件中每一个<bean>节点元素在 Spring 容器里都通过一个 BeanDefinition 对象表示,它描述了 Bean 的配置信息。而 BeanDefinitionRegistry 接口提供了向容器手工注册 BeanDefinition 对象的方法。
  • BeanFactory 接口位于类结构树的顶端 ,它最主要的方法就是 getBean(String beanName),该方法从容器中返回特定名称的 Bean,BeanFactory 的功能通过其他的接口得到不断扩展:
  • ListableBeanFactory:该接口定义了访问容器中 Bean 基本信息的若干方法,如查看Bean 的个数、获取某一类型 Bean 的配置名、查看容器中是否包括某一 Bean 等方法;
  • HierarchicalBeanFactory:父子级联 IoC 容器的接口,子容器可以通过接口方法访问父容器; 通过 HierarchicalBeanFactory 接口, Spring 的 IoC 容器可以建立父子层级关联的容器体系,子容器可以访问父容器中的 Bean,但父容器不能访问子容器的 Bean。Spring 使用父子容器实现了很多功能,比如在 Spring MVC 中,展现层 Bean 位于一个子容器中,而业务层和持久层的 Bean 位于父容器中。这样,展现层 Bean 就可以引用业务层和持久层的 Bean,而业务层和持久层的 Bean 则看不到展现层的 Bean。
  • ConfigurableBeanFactory:是一个重要的接口,增强了 IoC 容器的可定制性,它定义了设置类装载器、属性编辑器、容器初始化后置处理器等方法;
  • AutowireCapableBeanFactory:定义了将容器中的 Bean 按某种规则(如按名字匹配、按类型匹配等)进行自动装配的方法;
  • SingletonBeanRegistry:定义了允许在运行期间向容器注册单实例 Bean 的方法;

例子:

使用 Spring 配置文件为 Car 提供配置信息:beans.xml:

<?xml version="1.0" encoding="UTF-8" ?> 
<beans xmlns="Index of /schema/beans" 
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
    xmlns:p="http://www.springframework.org/schema/p" 
    xsi:schemaLocation="Index of /schema/beans 
    http://www.springframework.org/schema/beans/spring-beans-3.0.xsd"> 
    
    <bean id="car1" class="com.baobaotao.Car" 
        p:brand="红旗CA72" 
        p:color="黑色" 
        p:maxSpeed="200" /> 
</beans>

通过 BeanFactory 装载配置文件,启动 Spring IoC 容器:

public class BeanFactoryTest { 
    public static void main(String[] args) throws Throwable{
        ResourcePatternResolver resolver = new PathMatchingResourcePatternResolver();
        Resource res = resolver.getResource("classpath:com/baobaotao/beanfactory/beans.xml"); 
        BeanFactory bf = new XmlBeanFactory(res);
        System.out.println("init BeanFactory.");
        Car car = bf.getBean("car",Car.class);
        System.out.println("car bean is ready for use!");
}
  • XmlBeanFactory 通过 Resource 装载 Spring 配置信息并启动 IoC 容器,然后就可以通过 BeanFactory#getBean(beanName)方法从 IoC 容器中获取 Bean 了。通过 BeanFactory 启动IoC 容器时,并不会初始化配置文件中定义的 Bean,初始化动作发生在第一个调用时。
  • 对于单实例( singleton)的 Bean 来说,BeanFactory会缓存 Bean 实例,所以第二次使用 getBean() 获取 Bean 时将直接从 IoC 容器的缓存中获取 Bean 实例。Spring 在 DefaultSingletonBeanRegistry 类中提供了一个用于缓存单实例 Bean 的缓存器,它是一个用HashMap 实现的缓存器,单实例的 Bean 以 beanName 为键保存在这个HashMap 中。
  • 值得一提的是,在初始化 BeanFactory 时,必须为其提供一种日志框架,比如使用Log4J, 即在类路径下提供 Log4J 配置文件,这样启动 Spring 容器才不会报错。

ApplicationContext

ApplicationContext 由 BeanFactory 派生而来,提供了更多面向实际应用的功能。

在BeanFactory 中,很多功能需要以编程的方式实现,而在 ApplicationContext 中则可以通过配置的方式实现。

ApplicationContext 继承了 HierarchicalBeanFactory 和 ListableBeanFactory 接口,在此基础上,还通过多个其他的接口扩展了 BeanFactory 的功能:

  • ClassPathXmlApplicationContext:默认从类路径加载配置文件
  • FileSystemXmlApplicationContext:默认从文件系统中装载配置文件
  • ApplicationEventPublisher:让容器拥有发布应用上下文事件的功能,包括容器启动事件、关闭事件等。实现了 ApplicationListener 事件监听接口的 Bean 可以接收到容器事件 , 并对事件进行响应处理 。 在 ApplicationContext 抽象实现类AbstractApplicationContext 中,我们可以发现存在一个 ApplicationEventMulticaster,它负责保存所有监听器,以便在容器产生上下文事件时通知这些事件监听者。
  • MessageSource:为应用提供 i18n 国际化消息访问的功能;
  • ResourcePatternResolver : 所 有 ApplicationContext 实现类都实现了类似于PathMatchingResourcePatternResolver 的功能,可以通过带前缀的 Ant 风格的资源文件路径装载 Spring 的配置文件。
  • LifeCycle:该接口是 Spring 2.0 加入的,该接口提供了 start()和 stop()两个方法,主要用于控制异步处理过程。在具体使用时,该接口同时被 ApplicationContext 实现及具体 Bean 实现, ApplicationContext 会将 start/stop 的信息传递给容器中所有实现了该接口的 Bean,以达到管理和控制 JMX、任务调度等目的。
  • ConfigurableApplicationContext 扩展于 ApplicationContext,它新增加了两个主要的方法: refresh()和 close(),让 ApplicationContext 具有启动、刷新和关闭应用上下文的能力。在应用上下文关闭的情况下调用 refresh()即可启动应用上下文,在已经启动的状态下,调用 refresh()则清除缓存并重新装载配置信息,而调用close()则可关闭应用上下文。这些接口方法为容器的控制管理带来了便利,但作为开发者,我们并不需要过多关心这些方法。

使用:

如果配置文件放置在类路径下,用户可以优先使用 ClassPathXmlApplicationContext 实现类:

ApplicationContext ctx = new ClassPathXmlApplicationContext("com/baobaotao/ context/beans.xml");

如果配置文件放置在文件系统的路径下,则可以优先考虑使用 FileSystemXmlApplicationContext 实现类:

ApplicationContext ctx = new FileSystemXmlApplicationContext("com/baobaotao/ context/beans.xml");

Spring 3.0 支持基于类注解的配置方式,主要功能来自于 Spring 的一个名为 JavaConfig 子项目,目前 JavaConfig已经升级为 Spring核心框架的一部分。

ApplicationContext 在初始化应用上下文时就实例化所有单实例的 Bean。

WebApplicationContext

WebApplication体系架构:

  • WebApplicationContext 是专门为 Web 应用准备的,它允许从相对于 Web 根目录的路径中装载配置文件完成初始化工作。从WebApplicationContext 中可以获得 ServletContext 的引用,整个 Web 应用上下文对象将作为属性放置到 ServletContext 中,以便 Web 应用环境可以访问 Spring 应用上下文。 WebApplicationContext 定义了一个常量ROOT_WEB_APPLICATION_CONTEXT_ATTRIBUTE,在上下文启动时, WebApplicationContext 实例即以此为键放置在 ServletContext 的属性列表中,因此我们可以直接通过以下语句从 Web 容器中获取WebApplicationContext:
WebApplicationContext wac = (WebApplicationContext)servletContext.getAttribute(WebApplicationContext.ROOT_WEB_APPLICATION_CONTEXT_ATTRIBUTE);

Spring 和 Web 应用的上下文融合:

  • WebApplicationContext 的初始化方式:WebApplicationContext 需要 ServletContext 实例,它必须在拥有 Web 容器的前提下才能完成启动的工作。可以在 web.xml 中配置自启动的 Servlet 或定义 Web 容器监听器( ServletContextListener),借助这两者中的任何一个就可以完成启动 Spring Web 应用上下文的工作。Spring 分别提供了用于启动 WebApplicationContext 的 Servlet 和 Web 容器监听器:
    • org.springframework.web.context.ContextLoaderServlet;
    • org.springframework.web.context.ContextLoaderListener
    • 由于 WebApplicationContext 需要使用日志功能,比如日志框架使用Log4J,用户可以将 Log4J 的配置文件放置到类路径 WEB-INF/classes 下,这时 Log4J 引擎即可顺利启动。如果 Log4J 配置文件放置在其他位置,用户还必须在 web.xml 指定 Log4J 配置文件位置。

Bean的生命周期

  • 1.当调用者通过 getBean(beanName)向容器请求某一个 Bean 时,如果容器注册了org.springframework.beans.factory.config.InstantiationAwareBeanPostProcessor 接口,在实例化 Bean 之前,将调用接口的 postProcessBeforeInstantiation()方法;
  • 2.根据配置情况调用 Bean 构造函数或工厂方法实例化 Bean;
  • 3.如果容器注册了 InstantiationAwareBeanPostProcessor 接口,在实例化 Bean 之后,调用该接口的 postProcessAfterInstantiation()方法,可在这里对已经实例化的对象进行一些“梳妆打扮”;
  • 4.如果 Bean 配置了属性信息,容器在这一步着手将配置值设置到 Bean 对应的属性中,不过在设置每个属性之前将先调用InstantiationAwareBeanPostProcessor 接口的postProcessPropertyValues()方法;
  • 5.调用 Bean 的属性设置方法设置属性值;
  • 6.如果 Bean 实现了 org.springframework.beans.factory.BeanNameAware 接口,将调用setBeanName()接口方法,将配置文件中该 Bean 对应的名称设置到 Bean 中;
  • 7.如果 Bean 实现了 org.springframework.beans.factory.BeanFactoryAware 接口,将调用 setBeanFactory()接口方法,将 BeanFactory 容器实例设置到 Bean 中;
  • 8.如果 BeanFactory 装配了 org.springframework.beans.factory.config.BeanPostProcessor后处理器,将调用 BeanPostProcessor 的 Object postProcessBeforeInitialization(Object bean, String beanName)接口方法对 Bean 进行加工操作。其中入参 bean 是当前正在处理的 Bean,而 beanName 是当前 Bean 的配置名,返回的对象为加工处理后的 Bean。用户可以使用该方法对某些 Bean 进行特殊的处理,甚至改变 Bean 的行为, BeanPostProcessor 在 Spring 框架中占有重要的地位,为容器提供对 Bean 进行后续加工处理的切入点, Spring 容器所提供的各种“神奇功能”(如 AOP,动态代理等)都通过 BeanPostProcessor 实施;
  • 9.如果 Bean 实现了 InitializingBean 的接口,将调用接口的 afterPropertiesSet()方法;
  • 10.如果在<bean>通过 init-method 属性定义了初始化方法,将执行这个方法;
  • 11.BeanPostProcessor 后处理器定义了两个方法:其一是 postProcessBeforeInitialization() 在第 8 步调用;其二是 Object postProcessAfterInitialization(Object bean, String beanName)方法,这个方法在此时调用,容器再次获得对 Bean 进行加工处理的机会;
  • 12.如果在<bean>中指定 Bean 的作用范围为 scope=“prototype”,将 Bean 返回给调用者,调用者负责 Bean 后续生命的管理, Spring 不再管理这个 Bean 的生命周期。如果作用范围设置为 scope=“singleton”,则将 Bean 放入到 Spring IoC 容器的缓存池中,并将 Bean引用返回给调用者, Spring 继续对这些 Bean 进行后续的生命管理;
  • 13.对于 scope=“singleton”的 Bean,当容器关闭时,将触发 Spring 对 Bean 的后续生命周期的管理工作,首先如果 Bean 实现了 DisposableBean 接口,则将调用接口的afterPropertiesSet()方法,可以在此编写释放资源、记录日志等操作;
  • 14.对于 scope=“singleton”的 Bean,如果通过<bean>的 destroy-method 属性指定了 Bean 的销毁方法, Spring 将执行 Bean 的这个方法,完成 Bean 资源的释放等操作。

可以将这些方法大致划分为三类:

  • Bean 自身的方法:如调用 Bean 构造函数实例化 Bean,调用 Setter 设置 Bean 的属性值以及通过<bean>的 init-method 和 destroy-method 所指定的方法;
  • Bean 级生命周期接口方法:如 BeanNameAware、 BeanFactoryAware、 InitializingBean 和 DisposableBean,这些接口方法由 Bean 类直接实现;
  • 容器级生命周期接口方法:在上图中带“★” 的步骤是由 InstantiationAwareBean PostProcessor 和 BeanPostProcessor 这两个接口实现,一般称它们的实现类为“ 后处理器” 。 后处理器接口一般不由 Bean 本身实现,它们独立于 Bean,实现类以容器附加装置的形式注册到 Spring 容器中并通过接口反射为 Spring 容器预先识别。当Spring 容器创建任何 Bean 的时候,这些后处理器都会发生作用,所以这些后处理器的影响是全局性的。当然,用户可以通过合理地编写后处理器,让其仅对感兴趣Bean 进行加工处理

ApplicationContext 和 BeanFactory 另一个最大的不同之处在于:ApplicationContext会利用 Java 反射机制自动识别出配置文件中定义的 BeanPostProcessor、 InstantiationAwareBeanPostProcessor 和 BeanFactoryPostProcessor,并自动将它们注册到应用上下文中;而后者需要在代码中通过手工调用 addBeanPostProcessor()方法进行注册。这也是为什么在应用开发时,我们普遍使用 ApplicationContext 而很少使用 BeanFactory 的原因之一

IOC容器工作机制

容器启动过程

web环境下Spring容器、SpringMVC容器启动过程:

  1. 首先,对于一个web应用,其部署在web容器中,web容器提供其一个全局的上下文环境,这个上下文就是ServletContext,其为后面的spring IoC容器提供宿主环境;
  2. 其次,在web.xml中会提供有contextLoaderListener(或ContextLoaderServlet)。在web容器启动时,会触发容器初始化事件,此时contextLoaderListener会监听到这个事件,其contextInitialized方法会被调用,在这个方法中,spring会初始化一个启动上下文,这个上下文被称为根上下文,即WebApplicationContext,这是一个接口类,确切的说,其实际的实现类是XmlWebApplicationContext。这个就是spring的IoC容器,其对应的Bean定义的配置由web.xml中的context-param标签指定。在这个IoC容器初始化完毕后,spring容器以WebApplicationContext.ROOTWEBAPPLICATIONCONTEXTATTRIBUTE为属性Key,将其存储到ServletContext中,便于获取;
  3. 再次,contextLoaderListener监听器初始化完毕后,开始初始化web.xml中配置的Servlet,这个servlet可以配置多个,以最常见的DispatcherServlet为例(Spring MVC),这个servlet实际上是一个标准的前端控制器,用以转发、匹配、处理每个servlet请求。DispatcherServlet上下文在初始化的时候会建立自己的IoC上下文容器,用以持有spring mvc相关的bean,这个servlet自己持有的上下文默认实现类也是XmlWebApplicationContext。在建立DispatcherServlet自己的IoC上下文时,会利用WebApplicationContext.ROOTWEBAPPLICATIONCONTEXTATTRIBUTE先从ServletContext中获取之前的根上下文(即WebApplicationContext)作为自己上下文的parent上下文(即第2步中初始化的XmlWebApplicationContext作为自己的父容器)。有了这个parent上下文之后,再初始化自己持有的上下文(这个DispatcherServlet初始化自己上下文的工作在其initStrategies方法中可以看到,大概的工作就是初始化处理器映射、视图解析等)。初始化完毕后,spring以与servlet的名字相关(此处不是简单的以servlet名为Key,而是通过一些转换)的属性为属性Key,也将其存到ServletContext中,以便后续使用。这样每个servlet就持有自己的上下文,即拥有自己独立的bean空间,同时各个servlet共享相同的bean,即根上下文定义的那些bean。

Bean加载过程

Spring的高明之处在于,它使用众多接口描绘出了所有装置的蓝图,构建好Spring的骨架,继而通过继承体系层层推演,不断丰富,最终让Spring成为有血有肉的完整的框架。所以查看Spring框架的源码时,有两条清晰可见的脉络:
1)接口层描述了容器的重要组件及组件间的协作关系;
2)继承体系逐步实现组件的各项功能。

接口层清晰地勾勒出Spring框架的高层功能,框架脉络呼之欲出。有了接口层抽象的描述后,不但Spring自己可以提供具体的实现,任何第三方组织也可以提供不同实现, 可以说Spring完善的接口层使框架的扩展性得到了很好的保证。纵向继承体系的逐步扩展,分步骤地实现框架的功能,这种实现方案保证了框架功能不会堆积在某些类的身上,造成过重的代码逻辑负载,框架的复杂度被完美地分解开了。

Spring组件按其所承担的角色可以划分为两类:

  • 1)物料组件:Resource、BeanDefinition、PropertyEditor以及最终的Bean等,它们是加工流程中被加工、被消费的组件,就像流水线上被加工的物料;
    • BeanDefinition:Spring通过BeanDefinition将配置文件中的<bean>配置信息转换为容器的内部表示,并将这些BeanDefinition注册到BeanDefinitionRegistry中。Spring容器的后续操作直接从BeanDefinitionRegistry中读取配置信息。
  • 2)加工设备组件:ResourceLoader、BeanDefinitionReader、BeanFactoryPostProcessor、InstantiationStrategy以及BeanWrapper等组件像是流水线上不同环节的加工设备,对物料组件进行加工处理。
    • InstantiationStrategy:负责实例化Bean操作,相当于Java语言中new的功能,并不会参与Bean属性的配置工作。属性填充工作留待BeanWrapper完成
    • BeanWrapper:继承了PropertyAccessor和PropertyEditorRegistry接口,BeanWrapperImpl内部封装了两类组件:(1)被封装的目标Bean(2)一套用于设置Bean属性的属性编辑器;具有三重身份:(1)Bean包裹器(2)属性访问器 (3)属性编辑器注册表。PropertyAccessor:定义了各种访问Bean属性的方法。PropertyEditorRegistry:属性编辑器的注册表

该图描述了Spring容器从加载配置文件到创建出一个完整Bean的作业流程:

  • 1、ResourceLoader从存储介质中加载Spring配置信息,并使用Resource表示这个配置文件的资源;
  • 2、BeanDefinitionReader读取Resource所指向的配置文件资源,然后解析配置文件。配置文件中每一个<bean>解析成一个BeanDefinition对象,并保存到BeanDefinitionRegistry中;
  • 3、容器扫描BeanDefinitionRegistry中的BeanDefinition,使用Java的反射机制自动识别出Bean工厂后处理后器(实现BeanFactoryPostProcessor接口)的Bean,然后调用这些Bean工厂后处理器对BeanDefinitionRegistry中的BeanDefinition进行加工处理。主要完成以下两项工作:
    • 1)对使用到占位符的<bean>元素标签进行解析,得到最终的配置值,这意味对一些半成品式的BeanDefinition对象进行加工处理并得到成品的BeanDefinition对象;
    • 2)对BeanDefinitionRegistry中的BeanDefinition进行扫描,通过Java反射机制找出所有属性编辑器的Bean(实现java.beans.PropertyEditor接口的Bean),并自动将它们注册到Spring容器的属性编辑器注册表中(PropertyEditorRegistry);
  • 4.Spring容器从BeanDefinitionRegistry中取出加工后的BeanDefinition,并调用InstantiationStrategy着手进行Bean实例化的工作;
  • 5.在实例化Bean时,Spring容器使用BeanWrapper对Bean进行封装,BeanWrapper提供了很多以Java反射机制操作Bean的方法,它将结合该Bean的BeanDefinition以及容器中属性编辑器,完成Bean属性的设置工作;
  • 6.利用容器中注册的Bean后处理器(实现BeanPostProcessor接口的Bean)对已经完成属性设置工作的Bean进行后续加工,直接装配出一个准备就绪的Bean。

总结

  • Spring IOC容器主要有继承体系底层的BeanFactory、高层的ApplicationContext和WebApplicationContext
  • Bean有自己的生命周期
  • 容器启动原理:Spring应用的IOC容器通过tomcat的Servlet或Listener监听启动加载;Spring MVC的容器由DispatchServlet作为入口加载;Spring容器是Spring MVC容器的父容器
  • 容器加载Bean原理:
  1. BeanDefinitionReader读取Resource所指向的配置文件资源,然后解析配置文件。配置文件中每一个<bean>解析成一个BeanDefinition对象,并保存到BeanDefinitionRegistry中;
  2. 容器扫描BeanDefinitionRegistry中的BeanDefinition;调用InstantiationStrategy进行Bean实例化的工作;使用BeanWrapper完成Bean属性的设置工作;
  3. 单例Bean缓存池:Spring 在 DefaultSingletonBeanRegistry 类中提供了一个用于缓存单实例 Bean 的缓存器,它是一个用 HashMap 实现的缓存器,单实例的 Bean 以 beanName 为键保存在这个HashMap 中。

参考来源:
《Spring 3.x企业应用开发实战》
blog.csdn.net/caomiao20

(本文首发于公众号:EnjoyMoving)

聊聊HTTPS和SSL/TLS协议(转)

要说清楚 HTTPS 协议的实现原理,至少需要如下几个背景知识。
1. 大致了解几个基本术语(HTTPS、SSL、TLS)的含义
2. 大致了解 HTTP 和 TCP 的关系(尤其是“短连接”VS“长连接”)
3. 大致了解加密算法的概念(尤其是“对称加密与非对称加密”的区别)
4. 大致了解 CA 证书的用途

考虑到很多技术菜鸟可能不了解上述背景,俺先用最简短的文字描述一下。如果你自认为不是菜鸟,请略过本章节,直接去看“HTTPS 协议的需求”。

先澄清几个术语——HTTPS、SSL、TLS

1. “HTTP”是干嘛用滴?

首先,HTTP 是一个网络协议,是专门用来帮你传输 Web 内容滴。关于这个协议,就算你不了解,至少也听说过吧?比如你访问俺的博客的主页,浏览器地址栏会出现如下的网址

http://www.techug.com/

俺加了粗体的部分就是指 HTTP 协议。大部分网站都是通过 HTTP 协议来传输 Web 页面、以及 Web 页面上包含的各种东东(图片、CSS 样式、JS 脚本)。

2. “SSL/TLS”是干嘛用滴?

SSL 是洋文“Secure Sockets Layer”的缩写,中文叫做“安全套接层”。它是在上世纪90年代中期,由网景公司设计的。(顺便插一句,网景公司不光发明了 SSL,还发明了很多 Web 的基础设施——比如“CSS 样式表”和“JS 脚本”)
为啥要发明 SSL 这个协议捏?因为原先互联网上使用的 HTTP 协议是明文的,存在很多缺点——比如传输内容会被偷窥(嗅探)和篡改。发明 SSL 协议,就是为了解决这些问题。
到了1999年,SSL 因为应用广泛,已经成为互联网上的事实标准。IETF 就在那年把 SSL 标准化。标准化之后的名称改为 TLS(是“Transport Layer Security”的缩写),中文叫做“传输层安全协议”。
很多相关的文章都把这两者并列称呼(SSL/TLS),因为这两者可以视作同一个东西的不同阶段。

3. “HTTPS”是啥意思?

解释完 HTTP 和 SSL/TLS,现在就可以来解释 HTTPS 啦。咱们通常所说的 HTTPS 协议,说白了就是“HTTP 协议”和“SSL/TLS 协议”的组合。你可以把 HTTPS 大致理解为——“HTTP over SSL”或“HTTP over TLS”(反正 SSL 和 TLS 差不多)。

再来说说 HTTP 协议的特点

作为背景知识介绍,还需要再稍微谈一下 HTTP 协议本身的特点。HTTP 本身有很多特点,考虑到篇幅有限,俺只谈那些和 HTTPS 相关的特点。

1. HTTP 的版本和历史

如今咱们用的 HTTP 协议,版本号是 1.1(也就是 HTTP 1.1)。这个 1.1 版本是1995年底开始起草的(技术文档是 RFC2068),并在1999年正式发布(技术文档是 RFC2616)。
在 1.1 之前,还有曾经出现过两个版本“0.9 和 1.0”,其中的 HTTP 0.9 【没有】被广泛使用,而 HTTP 1.0 被广泛使用过。
另外,据说明年(2015)IETF 就要发布 HTTP 2.0 的标准了。俺拭目以待。

2. HTTP 和 TCP 之间的关系

简单地说,TCP 协议是 HTTP 协议的基石——HTTP 协议需要依靠 TCP 协议来传输数据。

在网络分层模型中,TCP 被称为“传输层协议”,而 HTTP 被称为“应用层协议”。

有很多常见的应用层协议是以 TCP 为基础的,比如“FTP、SMTP、POP、IMAP”等。
TCP 被称为“面向连接”的传输层协议。关于它的具体细节,俺就不展开了(否则篇幅又失控了)。你只需知道:传输层主要有两个协议,分别是 TCP 和 UDP。TCP 比 UDP 更可靠。你可以把 TCP 协议想象成某个水管,发送端这头进水,接收端那头就出水。并且 TCP 协议能够确保,先发送的数据先到达(与之相反,UDP 不保证这点)。

3. HTTP 协议如何使用 TCP 连接?

HTTP 对 TCP 连接的使用,分为两种方式:俗称“短连接”和“长连接”(“长连接”又称“持久连接”,洋文叫做“Keep-Alive”或“Persistent Connection”)
假设有一个网页,里面包含好多图片,还包含好多【外部的】CSS 文件和 JS 文件。在“短连接”的模式下,浏览器会先发起一个 TCP 连接,拿到该网页的 HTML 源代码(拿到 HTML 之后,这个 TCP 连接就关闭了)。然后,浏览器开始分析这个网页的源码,知道这个页面包含很多外部资源(图片、CSS、JS)。然后针对【每一个】外部资源,再分别发起一个个 TCP 连接,把这些文件获取到本地(同样的,每抓取一个外部资源后,相应的 TCP 就断开)
相反,如果是“长连接”的方式,浏览器也会先发起一个 TCP 连接去抓取页面。但是抓取页面之后,该 TCP 连接并不会立即关闭,而是暂时先保持着(所谓的“Keep-Alive”)。然后浏览器分析 HTML 源码之后,发现有很多外部资源,就用刚才那个 TCP 连接去抓取此页面的外部资源。

在 HTTP 1.0 版本,【默认】使用的是“短连接”(那时候是 Web 诞生初期,网页相对简单,“短连接”的问题不大);
到了1995年底开始制定 HTTP 1.1 草案的时候,网页已经开始变得复杂(网页内的图片、脚本越来越多了)。这时候再用短连接的方式,效率太低下了(因为建立 TCP 连接是有“时间成本”和“CPU 成本”滴)。所以,在 HTTP 1.1 中,【默认】采用的是“Keep-Alive”的方式。
关于“Keep-Alive”的更多介绍,可以参见维基百科词条(在“这里”)

谈谈“对称加密”和“非对称加密”的概念

1. 啥是“加密”和“解密”?

通俗而言,你可以把“加密”和“解密”理解为某种【互逆的】数学运算。就好比“加法和减法”互为逆运算、“乘法和除法”互为逆运算。
“加密”的过程,就是把“明文”变成“密文”的过程;反之,“解密”的过程,就是把“密文”变为“明文”。在这两个过程中,都需要一个关键的东东——叫做“密钥”——来参与数学运算。

2. 啥是“对称加密”?

所谓的“对称加密技术”,意思就是说:“加密”和“解密”使用【相同的】密钥。这个比较好理解。就好比你用 7zip 或 WinRAR 创建一个带密码(口令)的加密压缩包。当你下次要把这个压缩文件解开的时候,你需要输入【同样的】密码。在这个例子中,密码/口令就如同刚才说的“密钥”。

3. 啥是“非对称加密”?

所谓的“非对称加密技术”,意思就是说:“加密”和“解密”使用【不同的】密钥。这玩意儿比较难理解,也比较难想到。当年“非对称加密”的发明,还被誉为“密码学”历史上的一次革命。
由于篇幅有限,对“非对称加密”这个话题,俺就不展开了。有空的话,再单独写一篇扫盲。

4. 各自有啥优缺点?

看完刚才的定义,很显然:(从功能角度而言)“非对称加密”能干的事情比“对称加密”要多。这是“非对称加密”的优点。但是“非对称加密”的实现,通常需要涉及到“复杂数学问题”。所以,“非对称加密”的性能通常要差很多(相对于“对称加密”而言)。
这两者的优缺点,也影响到了 SSL 协议的设计。

CA 证书的原理及用途

关于这方面,请看俺4年前写的《数字证书及CA的扫盲介绍》。这里就不再重复唠叨了,免得篇幅太长。

HTTPS 协议的需求是啥?

花了好多口水,终于把背景知识说完了。下面正式进入正题。先来说说当初设计 HTTPS 是为了满足哪些需求?
很多介绍 HTTPS 的文章一上来就给你讲实现细节。个人觉得:这是不好的做法。早在2009年开博的时候,发过一篇《学习技术的三部曲:WHAT、HOW、WHY》,其中谈到“WHY 型问题”的重要性。一上来就给你讲协议细节,你充其量只能知道 WHAT 和 HOW,无法理解 WHY。俺在前一个章节讲了“背景知识”,在这个章节讲了“需求”,这就有助于你理解:当初

为什么

要设计成这样?——这就是 WHY 型的问题。

兼容性

因为是先有 HTTP 再有 HTTPS。所以,HTTPS 的设计者肯定要考虑到对原有 HTTP 的兼容性。
这里所说的兼容性包括很多方面。比如已有的 Web 应用要尽可能无缝地迁移到 HTTPS;比如对浏览器厂商而言,改动要尽可能小;……
基于“兼容性”方面的考虑,很容易得出如下几个结论:
1. HTTPS 还是要基于 TCP 来传输
(如果改为 UDP 作传输层,无论是 Web 服务端还是浏览器客户端,都要大改,动静太大了)
2. 单独使用一个新的协议,把 HTTP 协议包裹起来
(所谓的“HTTP over SSL”,实际上是在原有的 HTTP 数据外面加了一层 SSL 的封装。HTTP 协议原有的 GET、POST 之类的机制,基本上原封不动)

打个比方:如果原来的 HTTP 是塑料水管,容易被戳破;那么如今新设计的 HTTPS 就像是在原有的塑料水管之外,再包一层金属水管。一来,原有的塑料水管照样运行;二来,用金属加固了之后,不容易被戳破。

可扩展性

前面说了,HTTPS 相当于是“HTTP over SSL”。
如果 SSL 这个协议在“可扩展性”方面的设计足够牛逼,那么它除了能跟 HTTP 搭配,还能够跟其它的应用层协议搭配。岂不美哉?
现在看来,当初设计 SSL 的人确实比较牛。如今的 SSL/TLS 可以跟很多常用的应用层协议(比如:FTP、SMTP、POP、Telnet)搭配,来强化这些应用层协议的安全性。

接着刚才打的比方:如果把 SSL/TLS 视作一根用来加固的金属管,它不仅可以用来加固输水的管道,还可以用来加固输煤气的管道。

保密性(防泄密)

HTTPS 需要做到足够好的保密性。
说到保密性,首先要能够对抗嗅探(行话叫 Sniffer)。所谓的“嗅探”,通俗而言就是监视你的网络传输流量。如果你使用明文的 HTTP 上网,那么监视者通过嗅探,就知道你在访问哪些网站的哪些页面。
嗅探是最低级的攻击手法。除了嗅探,HTTPS 还需要能对抗其它一些稍微高级的攻击手法——比如“重放攻击”(后面讲协议原理的时候,会再聊)。

完整性(防篡改)

除了“保密性”,还有一个同样重要的目标是“确保完整性”。关于“完整性”这个概念,在之前的博文《扫盲文件完整性校验——关于散列值和数字签名》中大致提过。健忘的同学再去温习一下。
在发明 HTTPS 之前,由于 HTTP 是明文的,不但容易被嗅探,还容易被篡改。
举个例子:
比如咱们天朝的网络运营商(ISP)都比较流氓,经常有网友抱怨说访问某网站(本来是没有广告的),竟然会跳出很多中国电信的广告。为啥会这样捏?因为你的网络流量需要经过 ISP 的线路才能到达公网。如果你使用的是明文的 HTTP,ISP 很容易就可以在你访问的页面中植入广告。
所以,当初设计 HTTPS 的时候,还有一个需求是“确保 HTTP 协议的内容不被篡改”。

真实性(防假冒)

在谈到 HTTPS 的需求时,“真实性”经常被忽略。其实“真实性”的重要程度不亚于前面的“保密性”和“完整性”。
举个例子:
你因为使用网银,需要访问该网银的 Web 站点。那么,你如何确保你访问的网站确实是你想访问的网站?(这话有点绕口令)
有些天真的同学会说:通过看网址里面的域名,来确保。为啥说这样的同学是“天真的”?因为 DNS 系统本身是不可靠的(尤其是在设计 SSL 的那个年代,连 DNSSEC 都还没发明)。由于 DNS 的不可靠(存在“域名欺骗”和“域名劫持”),你看到的网址里面的域名【未必】是真实滴!
(不了解“域名欺骗”和“域名劫持”的同学,可以参见俺之前写的《扫盲 DNS 原理,兼谈“域名劫持”和“域名欺骗/域名污染”》)
所以,HTTPS 协议必须有某种机制来确保“真实性”的需求(至于如何确保,后面会细聊)。

性能

再来说最后一个需求——性能。
引入 HTTPS 之后,【不能】导致性能变得太差。否则的话,谁还愿意用?
为了确保性能,SSL 的设计者至少要考虑如下几点:
1. 如何选择加密算法(“对称”or“非对称”)?
2. 如何兼顾 HTTP 采用的“短连接”TCP 方式?
(SSL 是在1995年之前开始设计的,那时候的 HTTP 版本还是 1.0,默认使用的是“短连接”的 TCP 方式——默认不启用 Keep-Alive)

 来源:http://www.techug.com/post/https-ssl-tls.html

Mysql的分页查询性能优化

MySQL limit分页查询的性能优化

 

Mysql的分页查询十分简单,但是当数据量大的时候一般的分页就吃不消了。

传统分页查询:SELECT c1,c2,cn… FROM table LIMIT n,m

MySQL的limit工作原理就是先读取前面n条记录,然后抛弃前n条,读后面m条想要的,所以n越大,偏移量越大,性能就越差。

推荐分页查询方法:

1、尽量给出查询的大致范围

  1. SELECT c1,c2,cn… FROM table WHERE id>=20000 LIMIT 10;

2、子查询法

  1. SELECT c1,c2,cn… FROM table WHERE id>=
  2. (
  3. SELECT id FROM table LIMIT 20000,1
  4. )
  5. LIMIT 10;

3、高性能MySQL一书中提到的只读索引方法

优化前SQL:

  1. SELECT c1,c2,cn… FROM member ORDER BY last_active LIMIT 50,5

优化后SQL:

  1. SELECT c1, c2, cn .. .
  2. FROM member
  3. INNER JOIN (SELECT member_id FROM member ORDER BY last_active LIMIT 50, 5)
  4. USING (member_id)

分别在于,优化前的SQL需要更多I/O浪费,因为先读索引,再读数据,然后抛弃无需的行。而优化后的SQL(子查询那条)只读索引(Cover index)就可以了,然后通过member_id读取需要的列。

4、第一步用用程序读取出ID,然后再用IN方法读取所需记录

程序读ID:

  1. SELECT id FROM table LIMIT 20000, 10;
  2. SELECT c1, c2, cn .. . FROM table WHERE id IN (id1, id2, idn.. .)

 

 

==============

 

 

MySQL的limit用法和分页查询的性能分析及优化

一、limit用法

在我们使用查询语句的时候,经常要返回前几条或者中间某几行数据,这个时候怎么办呢?不用担心,mysql已经为我们提供了这样一个功能。

SELECT * FROM table LIMIT [offset,] rows | `rows OFFSET offset ` 
(LIMIT offset, `length`)
SELECT
*
FROM table
where condition1 = 0
and condition2 = 0
and condition3 = -1
and condition4 = -1
order by id asc
LIMIT 2000 OFFSET 50000

LIMIT 子句可以被用于强制 SELECT 语句返回指定的记录数。LIMIT 接受一个或两个数字参数。参数必须是一个整数常量。如果给定两个参数,第一个参数指定第一个返回记录行的偏移量第二个参数指定返回记录行的最大数目初始记录行的偏移量是 0(而不是 1): 为了与 PostgreSQL 兼容,MySQL 也支持句法: LIMIT # OFFSET #。

mysql> SELECT * FROM table LIMIT 5,10; // 检索记录行 6-15 

//为了检索从某一个偏移量到记录集的结束所有的记录行,可以指定第二个参数为 -1:

mysql> SELECT * FROM table LIMIT 95,-1; // 检索记录行 96-last. 

//如果只给定一个参数,它表示返回最大的记录行数目:
mysql> SELECT * FROM table LIMIT 5; //检索前 5 个记录行
//换句话说,LIMIT n 等价于 LIMIT 0,n

二、Mysql的分页查询语句的性能分析

MySql分页sql语句,如果和MSSQL的TOP语法相比,那么MySQL的LIMIT语法要显得优雅了许多。使用它来分页是再自然不过的事情了。

最基本的分页方式:

SELECT ... FROM ... WHERE ... ORDER BY ... LIMIT ... 

在中小数据量的情况下,这样的SQL足够用了,唯一需要注意的问题就是确保使用了索引:
举例来说,如果实际SQL类似下面语句,那么在category_id, id两列上建立复合索引比较好:

SELECT * FROM articles WHERE category_id = 123 ORDER BY id LIMIT 50, 10

子查询的分页方式:

随着数据量的增加,页数会越来越多,查看后几页的SQL就可能类似:
SELECT * FROM articles WHERE category_id = 123 ORDER BY id LIMIT 10000, 10

一言以蔽之,就是越往后分页,LIMIT语句的偏移量就会越大,速度也会明显变慢
此时,我们可以通过子查询的方式来提高分页效率,大致如下:

SELECT * FROM articles WHERE  id >=  
(SELECT id FROM articles  WHERE category_id = 123 ORDER BY id LIMIT 10000, 1) LIMIT 10 

JOIN分页方式

SELECT * FROM `content` AS t1   
JOIN (SELECT id FROM `content` ORDER BY id desc LIMIT ".($page-1)*$pagesize.", 1) AS t2   
WHERE t1.id <= t2.id ORDER BY t1.id desc LIMIT $pagesize; 

经过我的测试,join分页和子查询分页的效率基本在一个等级上,消耗的时间也基本一致。
explain SQL语句:

id select_type table type possible_keys key key_len ref rows Extra
1 PRIMARY <derived2> system NULL NULL NULL NULL 1  
1 PRIMARY t1 range PRIMARY PRIMARY 4 NULL 6264 Using where
2 DERIVED content index NULL PRIMARY 4 NULL 27085 Using index

为什么会这样呢?因为子查询是在索引上完成的,而普通的查询时在数据文件上完成的,通常来说,索引文件要比数据文件小得多,所以操作起来也会更有效率。

实际可以利用类似策略模式的方式去处理分页,比如判断如果是一百页以内,就使用最基本的分页方式,大于一百页,则使用子查询的分页方式。

三、对于有大数据量的mysql表来说,使用LIMIT分页存在很严重的性能问题。

查询从第1000000之后的30条记录:

SQL代码1:平均用时6.6秒 SELECT * FROM `cdb_posts` ORDER BY pid LIMIT 1000000 , 30

SQL代码2:平均用时0.6秒 SELECT * FROM `cdb_posts` WHERE pid >= (SELECT pid FROM  
`cdb_posts` ORDER BY pid LIMIT 1000000 , 1) LIMIT 30

因为要取出所有字段内容,第一种需要跨越大量数据块并取出,而第二种基本通过直接根据索引字段定位后,才取出相应内容,效率自然大大提升。对limit的优化,不是直接使用limit,而是首先获取到offset的id,然后直接使用limit size来获取数据。

可以看出,越往后分页,LIMIT语句的偏移量就会越大,两者速度差距也会越明显。

实际应用中,可以利用类似策略模式的方式去处理分页,比如判断如果是一百页以内,就使用最基本的分页方式,大于一百页,则使用子查询的分页方式。

优化思想:避免数据量大时扫描过多的记录

为了保证index索引列连续,可以为每个表加一个自增字段,并且加上索引

参考:mysql分页offset过大,Sql优化经验

 

 

========

 

 

MySQL单表百万数据记录分页性能优化

背景:

自己的一个网站,由于单表的数据记录高达了一百万条,造成数据访问很慢,Google分析的后台经常报告超时,尤其是页码大的页面更是慢的不行。

测试环境:

先让我们熟悉下基本的sql语句,来查看下我们将要测试表的基本信息

use infomation_schema
SELECT * FROM TABLES WHERE TABLE_SCHEMA = ‘dbname’ AND TABLE_NAME = ‘product’

查询结果:

从上图中我们可以看到表的基本信息:

表行数:866633
平均每行的数据长度:5133字节
单表大小:4448700632字节

关于行和表大小的单位都是字节,我们经过计算可以知道
平均行长度:大约5k
单表总大小:4.1g
表中字段各种类型都有varchar、datetime、text等,id字段为主键

测试实验

1.   直接用limit start, count分页语句, 也是我程序中用的方法:

select * from product limit start, count
当起始页较小时,查询没有性能问题,我们分别看下从10, 100, 1000, 10000开始分页的执行时间(每页取20条), 如下:

select * from product limit 10, 20   0.016秒
select * from product limit 100, 20   0.016秒
select * from product limit 1000, 20   0.047秒
select * from product limit 10000, 20   0.094秒

我们已经看出随着起始记录的增加,时间也随着增大, 这说明分页语句limit跟起始页码是有很大关系的,那么我们把起始记录改为40w看下(也就是记录的一般左右)                                    select * from product limit 400000, 20   3.229秒

再看我们取最后一页记录的时间
select * from product limit 866613, 20   37.44秒

难怪搜索引擎抓取我们页面的时候经常会报超时,像这种分页最大的页码页显然这种时
间是无法忍受的。

从中我们也能总结出两件事情:
1)limit语句的查询时间与起始记录的位置成正比
2)mysql的limit语句是很方便,但是对记录很多的表并不适合直接使用。

2.   对limit分页问题的性能优化方法

利用表的覆盖索引来加速分页查询
我们都知道,利用了索引查询的语句中如果只包含了那个索引列(覆盖索引),那么这种情况会查询很快。

因为利用索引查找有优化算法,且数据就在查询索引上面,不用再去找相关的数据地址了,这样节省了很多时间。另外Mysql中也有相关的索引缓存,在并发高的时候利用缓存就效果更好了。

在我们的例子中,我们知道id字段是主键,自然就包含了默认的主键索引。现在让我们看看利用覆盖索引的查询效果如何:

这次我们之间查询最后一页的数据(利用覆盖索引,只包含id列),如下:
select id from product limit 866613, 20 0.2秒
相对于查询了所有列的37.44秒,提升了大概100多倍的速度

那么如果我们也要查询所有列,有两种方法,一种是id>=的形式,另一种就是利用join,看下实际情况:

SELECT * FROM product WHERE ID > =(select id from product limit 866613, 1) limit 20
查询时间为0.2秒,简直是一个质的飞跃啊,哈哈

另一种写法
SELECT * FROM product a JOIN (select id from product limit 866613, 20) b ON a.ID = b.id
查询时间也很短,赞!

其实两者用的都是一个原理嘛,所以效果也差不多

来源:https://www.cnblogs.com/scotth/p/7995856.html

Java8系列之重新认识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]是何物。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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后,得到数组下标,把数据放在对应下标元素的链表上。例如程序执行下面代码:

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

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

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

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

1
2
3
4
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方法的离散性能。先看看源码的实现(方法一+方法二):

1
2
3
4
5
6
7
8
9
10
11
方法一:
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))))                                            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的环境):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class HashMapInfiniteLoop { 
    private static HashMap<Integer,String> map = new HashMap<Integer,String>(20.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,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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实例缓存了起来,而不是一遍一遍的创建它们。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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),屏蔽了扩容的情况,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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最坏的情况。代码修改如下:

1
2
3
4
5
6
7
8
9
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。

Java对于内存的需要知道的知识

内存

内存大家都知道(当然不是硬盘啊)。与c、c++相比呢,Java在内存管理的方面一个优越之处就是我们不用显式的去对对象进行内存的分配和内存的回收,可能有人会着迷于对内存使用分配的这种快感,但是随着程序变大,对于内存的维护工作也就越来越大。Java的JVM的自动内存管理机制,凸显出了强大的优越感。。。。

但反而是因为这样的一个现状,就弱化了我们在写Java程序时遇到内存溢出等问题时的定位能力和解决问题的能力。就在这个时候一本书应运而生— 《深入理解java虚拟机》 这本书也算是我旁边落灰最严重的一本了,但写程序就是这样如果不沉到底,程序浮于表面那就只是单纯的应用,不能变的熟练。
只有我们真正的了解了JVM如何管理内存后,才能遇见OutOfMemory错误时,快速的根据异常日志信息定位和解决问题。

Java内存分配方式

Java内存分配方式

咱们看看上面这张图,颜色这么鲜艳,这次一定能记住了!

  1. 静态 存储区

    内存在程序编译的时候就已经分配好了,这块内存在程序的整个运行期间都存在。比如,static 、全局变量

  2. 在  上创建

    在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分匹配运算内置于处理器的指令集中、效率很高、但是分配的内存容量非常有限。

  3. 在  上分配

    动态内存分配。在c和c++中运行程序时用 malloc 或 new申请任意大小的内存,我们需要自己决定自己在何时何地使用使用free和delete来释放内存。

Java虚拟机内存模型是Java程序运行的基础。虚拟机在执行Java程序的过程中会把他所管理的内存划分为若干的不同的数据区域,ok,这里加重 是分为不同的数据区域,这些区域都有自己的用途以及创建和销毁的时间。看一下下图,

太好了,又画了一个带颜色的图~那就说一说为什么带不同的颜色吧

  • 紫色,由所有线程共享的数据区
  • 线程隔离的数据区

程序计数器

寄存器里面有一个叫指令寄存器,用来储存现在正在被运行的指令。想象一下,在JVM中怎么办,程序寄存器就是这样的功能。

程序技术器是一块较小的内存空间,它可以看做是当前线程所执行的字节码的行号指示器。“字节码”就是Java程序被编译之后的形态,JVM有字节码解释器,这个解释器要解释程序的哪段,就由这个程序技术器来决定的。

Java虚拟机栈

Java虚拟机栈也是线程私有的,生命周期与线程相同,虚拟机栈描述的是Java方法执行的内存模型。每个方法在执行的同时会创建栈帧,保存

  • 局部变量表
  • 操作数栈
  • 动态链接
  • 方法出口
    每个方法从调用直到执行完成的过程,就对应整一个栈帧在虚拟机栈中入栈和出栈的过程。
    平时咱们在讨论的时候总会提到“栈”和“堆”这两种内存区域,那么其中的栈,就是这里所指的栈,更细一点说,就是虚拟机栈中局部变量的部分。

在换一个方面讲解一下,虚拟机栈是用来被快速访问的存储区域,一般该区域位于通用RAM里,

这个RAM叫随机存储器,是与CPU直接交换数据的内存存储器,也叫主存,可以随时随地的写,而且速度快,通常作为操作系统或其他正在运行中的程序的临时数据存储媒介。

在虚拟机栈中,使用栈指针来访问处理器。我们都学过栈这种数据结构,它是一种快速有效的 分配 存储的方法,存储速度仅次于寄存器,堆栈指针若向下移动,则分配新的内存,若向上移动则释放那些内存。由于Java编译器需要预先去生成相应的内存空间,所以,当我们尝试创建程序的时候,Java编译器必须知道被存储在站内的所有数据的确切大小和声明周期。一遍可以像上面描述的那样去分配内存空间。

栈相对于堆的优势就是比堆存取快,在栈中重要被用来存放一下基本类型的变量,例如int、short、long、byte、float、double、boolean、char,以及对象的引用(对象本身一般都存放在堆中)

StackOverFlow和OutOfMemoryError

Java虚拟机规范允许Java栈的大小是动态的或者是固定不变的。如果线程在计算过程中,请求的栈深度大于最大可用的栈深度,则在程序运行过程中会抛出StackOverFlow异常、如果Java栈可以动态扩展,而在扩展的过程中没有足够的内存空间支持栈的发展,在运行过程中会抛出OutOfMemoryError异常。

本地方法栈

本地方法栈与虚拟机栈所发挥的作用十分相似,区别就是虚拟机栈执行Java(字节码)的方法,本地栈是为虚拟机使用到Native方法。

Java堆

Java堆(Heap)是Java虚拟机所管理的内存中最大的一块。堆是被所有线程共享的一块内存区域,在虚拟机启动时创建。次内存却与的唯一目的就是存放对象示例,刚才在栈的部分也说了,栈中存的是对象的索引,而对象的实例存放在堆中。

在Java虚拟机规范中描述:所有的对象实例以及数组都要被在堆上分配内存。

GC(Garbage Collection)垃圾回收

由于堆和栈结构上的不同,所以其内存回收的机制也是不一样的。

Java中对可以细分为:

  • 新生代
  • 老年代

再细分…

  • Eden空间
  • From Survivor空间
  • To Survivor

在内存的角度来看,线程共享的Java堆中可能划分出多个线程私有的分配缓存区(Thread Local Allocation Buffer,TLAB)。Java堆可以处于物理上不连续的内存空间中,只要逻辑上是连续的即可,就像我们的磁盘空间一样,在实现是,既可以实现成固定大小的,也可以是可扩展的,不过当前主流的虚拟机都是按照可扩展来实现的

-Xmx

-Xms
在堆中没有内存完成实例分配,并且堆也无法在扩展时会抛出OutOfMemoryError异常。

方法区

方法区和Java堆是一样的,是各个线程共享的内存区域,他用于储存已被虚拟机加载的类的信息、常量、静态变量、即时编译器编译后的代码等数据。

来源:https://www.cnblogs.com/luanpeng/p/6964818.html

Dubbo基本原理机制

转自:http://blog.csdn.net/paul_wei2008/article/details/19355681

分布式服务框架:

–高性能和透明化的RPC远程服务调用方案

–SOA服务治理方案

-Apache MINA 框架基于Reactor模型通信框架,基于TCP长连接

Dubbo缺省协议采用单一长连接和NIO异步通讯,适合于小数据量大并发的服务调用,以及服务消费者机器数远大于服务提供者机器数的情况。

分析源代码,基本原理如下:

client一个线程调用远程接口,生成一个唯一的ID(比如一段随机字符串,UUID等),Dubbo是使用AtomicLong从0开始累计数字的

将打包的方法调用信息(如调用的接口名称,方法名称,参数值列表等),和处理结果的回调对象callback,全部封装在一起,组成一个对象object

向专门存放调用信息的全局ConcurrentHashMap里面put(ID, object)

将ID和打包的方法调用信息封装成一对象connRequest,使用IoSession.write(connRequest)异步发送出去

当前线程再使用callback的get()方法试图获取远程返回的结果,在get()内部,则使用synchronized获取回调对象callback的锁, 再先检测是否已经获取到结果,如果没有,然后调用callback的wait()方法,释放callback上的锁,让当前线程处于等待状态。

服务端接收到请求并处理后,将结果(此结果中包含了前面的ID,即回传)发送给客户端,客户端socket连接上专门监听消息的线程收到消息,分析结果,取到ID,再从前面的ConcurrentHashMap里面get(ID),从而找到callback,将方法调用结果设置到callback对象里。

监听线程接着使用synchronized获取回调对象callback的锁(因为前面调用过wait(),那个线程已释放callback的锁了),再notifyAll(),唤醒前面处于等待状态的线程继续执行(callback的get()方法继续执行就能拿到调用结果了),至此,整个过程结束。

当前线程怎么让它“暂停”,等结果回来后,再向后执行?

答:先生成一个对象obj,在一个全局map里put(ID,obj)存放起来,再用synchronized获取obj锁,再调用obj.wait()让当前线程处于等待状态,然后另一消息监听线程等到服 务端结果来了后,再map.get(ID)找到obj,再用synchronized获取obj锁,再调用obj.notifyAll()唤醒前面处于等待状态的线程。

正如前面所说,Socket通信是一个全双工的方式,如果有多个线程同时进行远程方法调用,这时建立在client server之间的socket连接上会有很多双方发送的消息传递,前后顺序也可能是乱七八糟的,server处理完结果后,将结果消息发送给client,client收到很多消息,怎么知道哪个消息结果是原先哪个线程调用的?

答:使用一个ID,让其唯一,然后传递给服务端,再服务端又回传回来,这样就知道结果是原先哪个线程的了。

邮件服务优化方案(2018年3月23日)

Skip to end of metadata

 

Go to start of metadata

 

 

 

一、问题

1、report耗时

从目前来看,一次report的耗时从1个半小时到2个小时不等,时间略长。每次report的邮件数从3万-6万不等,得出这个数据的过程可以参考附件。

2、内存

不仅仅是邮件服务,JVM老年代内存逐渐上涨直至报警,需要重启来解决的问题在各个系统中几乎全部存在,只不过邮件服务的迭代周期较长(重启的次数很低),所以报警问题较为突出。

二、分析

1、report

工作的线程模型可以用下图来表示:

阶段一

阶段一在定时任务线程中执行,这一步所做的工作是从数据库中一次性查出最近3天内需要进行report的所有邮件(总数在3万-6万不等),并提交到pull线程池中。

阶段二

直接上源码,MailReportPullJobs.doPull:

for (MailReports mailReports : reportList) {
    executor.execute(() -> {
        MailReportRequest mailReportRequest = new MailReportRequest();
        String messageId = mailReports.getMessageId();
        mailReportRequest.setMessageId(messageId);
        //为了兼容老数据,需要去mails表里查询toMail字段
        String recipient = "";
        if(StringUtils.isBlank(mailReports.getToMail())){
            Mails mail = mailService.getMails(mailReports.getMailId());
            recipient = mail != null ? mail.getToMail() : "";
        }else{
            recipient = mailReports.getToMail();
        }
        mailReportRequest.setRecipient(recipient);
        if(StringUtils.isNotBlank(messageId) && StringUtils.isNotBlank(recipient)) {
            mailStrategy.doPullReport(mailReportRequest, mailReports.getId());
        }
    });
}

由于在当前的数据中可以直接获得toMail,所以这里不会进行一次数据库查询,即:全部是简单的、步骤有限的内存操作,所以可以进一步得出推论:这个pull线程池没有存在的必要

下面是此线程池的定义:

private static final ThreadPoolExecutor executor =
        new ThreadPoolExecutor(Runtime.getRuntime().availableProcessors(), Runtime.getRuntime().availableProcessors() * 10, 0L, TimeUnit.MILLISECONDS,
        new LinkedBlockingQueue<>(), ThreadUtils.newThreadFactoryByName("pullExecutor"));

由于队列大小上限是int最大值,考虑到目前需要report的邮件数远小于此值,所以此时线程池maximumPoolSize参数实际上失去了意义,即线程数永远不会达到此值

Q: Why?

A: 参考ThreadPoolExecutor的execute方法源码:

public void execute(Runnable command) {
    int c = ctl.get();
    if (workerCountOf(c) < corePoolSize) {
        if (addWorker(command, true))
            return;
        c = ctl.get();
    }
    if (isRunning(c) && workQueue.offer(command)) {
        int recheck = ctl.get();
        if (! isRunning(recheck) && remove(command))
            reject(command);
        else if (workerCountOf(recheck) == 0)
            addWorker(nullfalse);
    }
    else if (!addWorker(command, false))
        reject(command);
}

概括来说,一个任务被提交的步骤是:

  1. 如果当前线程数未达到corePoolSize,提升线程数,并将任务直接交给新创建的线程池执行。
  2. 如果已达到corePoolSize,那么尝试提交到任务队列,如果提交成功,返回。
  3. 如果线程数尚未达到maximumPoolSize,那么提升线程数。
  4. 此时仍未成功,那么触发reject。

我们可以在线上机器执行report时用jstack打印线程堆栈的方式来正式这一点。2018年3月22日15点的report由机器l-mail2.ter.prod.aws.dm完成,查看其堆栈:

得证。

阶段三

此阶段是report操作的核心所在,归纳为两步:

可以明显的看出,这是一个IO密集型操作。从目前日志来看,阶段三的耗时约1秒。

下面是其线程池的定义:

private static final int QUEUE_SIZE = 50000;
private static final ThreadPoolExecutor reportExecutor =
        new ThreadPoolExecutor(Runtime.getRuntime().availableProcessors(), Runtime.getRuntime().availableProcessors() * 2, 10L, TimeUnit.MILLISECONDS,
                new LinkedBlockingQueue<>(QUEUE_SIZE), ThreadUtils.newThreadFactoryByName("reportExecutor"));

这是一个有界队列(准确来说,int最大值也是有界…),仍以2018年3月22日l-mail2.ter.prod.aws.dm这次report为例,共有6万多report请求,所以我们可以推断,实际的工作线程数为8(核心数4):

同样得证。

但是,如果需要report的邮件数不足5万,那么实际工作的线程数便只有四个,以30607封为例,那么:

30607 / 4(线程数) / 1(秒) / 60 / 60 = 2.12小时

通过日志便可以印证此结论。进一步延伸,当邮件数超过5万(以51000为例),此时的耗时为:

51000 / 8 / 1 / 3600 = 1.77小时

反而比更少的邮件数时耗时低。

2、内存

这里重点关注老年代中的不可达对象,即垃圾。

 

可见,这里有大约300MB的由report线程池导致的垃圾,原因很容易想到:

每次report时都会有大量的MailReportRequest对象等待被处理。

3、昂贵的连接

我们服务请求mail gun使用的是HTTPS连接,众所周知,TCP连接的建立需要三次握手,断开需要四次挥手,是一个较重的操作。而HTTPS连接又加重了这一情形。但是:

我们的服务并未使用连接池(HTTP 1.1版本默认开始keep-alive,即连接复用),这就意味这每个时段的report需要执行5万次(约)TCP连接建立与HTTPS握手

无需测试,只需脑补即可想象这有多痛苦。

下面用debug的方法证明上述论断。使用MailGunMailVendor的getReports方法作为切入点,源码:

@Override
public List<MailReportResponse> getReports(MailReportEvent mailReportEvent) {
    WebResource webResource = client.resource(MAIL_EVENT_API);
 
    String responseBody = webResource.queryParams(queryParams).get(String.class);
 
    return mailReportResponses;
}

一路跟下去,核心点位于URLConnectionClientHandler的_invoke方法,如下图:

openConnection即JDK中URL类的方法,这就直接证明了我们上面的结论。所以,对昂贵的HTTPS连接进行复用是势在必行的。

4、并发更新

如果一封邮件mail gun有了状态变化,那么系统将拉取到的最新的状态更新到数据库中,按照原有的线程模型,有三个潜在的问题:

  1. 拉取report和更新状态为串行操作,无法充分利用多线程并发处理的优势。
  2. 单次更新按照主键进行,性能并不是问题,但是总体来看,会产生大量的小事物的提交。
  3. 每次与MySQL的交互均需要通过网络I/O完成。

所以,本次优化将其改为异步化、批量化。

三、优化

1、report线程池

提升report线程池的corePoolSize(比如改为40)即可,注意改pull线程池是没有作用的。

2、线程模型调整

消耗

每次report都会创建3万-6万的MailReportRequest对象、3万-6万的Runnable实现类对象(提交到线程池用)、3-6万的LinkedBlockingQueue的Node对象。我们来看看三种对象分别有多大。

MailReportRequest

com.vipkid.mail.MailReportRequest.limit @12 (int, 4b)
com.vipkid.mail.MailReportRequest.startTime @16 (java.lang.String, 4b)
com.vipkid.mail.MailReportRequest.endTime @20 (java.lang.String, 4b)
com.vipkid.mail.MailReportRequest.recipient @24 (java.lang.String, 4b)
com.vipkid.mail.MailReportRequest.from @28 (java.lang.String, 4b)
com.vipkid.mail.MailReportRequest.messageId @32 (java.lang.String, 4b)
size = 40

共40字节。

Runnable

size = 16

LinkedBlockingQueue$Node

外部无法访问其内部类Node,目测为4 + 4 + 8 = 16字节。

总结

简单计算一下,每天需要执行24 / 3 = 8次report,随机分配至3台机器,即每台机器每天执行约3次,故有:

40000(假设每次report邮件数) * 72B(每次邮件report消耗老年代大小) * 3(每台机器每天report次数) * 36(重启后到报警所需的天数) / 1024(KB) / 1024(MB) = 296.6MB

感觉和实际差不多。

新的线程模型

概括

总的来说,可以从下面两方面入手:

  1. 干掉pull线程池。此优化的意义不在于能够提升多少性能(或者说降低多少内存消耗),而是简化代码结构、线程模型。原因是将MailReportRequest提交到线程池其实是一个非常高效的操作,预计这里创建的Runnable对象可以在 Minor GC中就得到回收。
  2. 引入disruptor

示意图

图中report、更新DB的线程数只是一个示意。Disruptor是一个lock-free实现的高性能环形队列,当然这里引入disruptor的主要原因并不是其无锁特性(因为目前的处理速度锁应该还不是瓶颈),而是其事件对象预分配且固定

这就意味着上面提到的MailReportRequest、Runnable和Node不断堆积的问题便得到解决了。

3、连接池

我们服务使用的是1.9版本的jersey客户端,结合Apache HttpClient可以实现连接池的效果,这里参考:

Connection pooling using jersey client

Jersey Client 1.x Example

Q: Jersey如何处理连接关闭?

A: 既然有了”池”的概念,那么就不得不提资源的close/回收方法,我们下面来看看引入了连接池后jersey是在何时何地进行连接回收的。仍以下面请求代码为例:

String responseBody = webResource.queryParams(queryParams).get(String.class);

这里返回的是String类型,这很重要。跳过复杂的调用关系,核心位于org.apache.commons.httpclient.AutoCloseInputStream的close方法:

public void close() {
    if (!selfClosed) {
        selfClosed = true;
        notifyWatcher();
    }
}
notifyWatcher方法:
private void notifyWatcher() throws IOException {
    if (streamOpen) {
        super.close();
        streamOpen = false;
 
        if (watcher != null) {
            watcher.responseConsumed();
        }
    }
}

连接的回收最终就是在这里完成的。watcher在HttpMethodBase的readResponseBody方法中设置,部分源码:

private InputStream readResponseBody(HttpConnection conn){
    InputStream result = null;
    // if there is a result - ALWAYS wrap it in an observer which will
    // close the underlying stream as soon as it is consumed, and notify
    // the watcher that the stream has been consumed.
    if (result != null) {
        result = new AutoCloseInputStream(
            result,
            new ResponseConsumedWatcher() {
                public void responseConsumed() {
                    responseBodyConsumed();
                }
            }
        );
    }
    return result;
}

responseBodyConsumed方法最终会触发连接的回收。回收触发的时机便是当读取响应完成(遇到EOF)或显式调用close方法时

其中连接池参数设置参考了此篇文章,作者结合了在京东的实战经验,2333:

使用httpclient必须知道的参数设置及代码写法、存在的风险

本次新增的三个核心配置如下:

jersey.report.maxPoolSizePerHost=500
jersey.report.maxPoolSize=500
# milliseconds
jersey.connect.poolTimeout=500
jersey.send.maxPoolSize=200
jersey.send.maxPoolSizePerHost=200

这里maxPoolSizePerHost和maxPoolSize的取值相等,因为目前jersey只对mail gun一个host进行请求。除此之外,这里对发送和report连接池进行了隔离,防止大量的并发report对发送产生影响。

Q: Apache http client是如何检查连接是否有效的?

A: HttpConnection的closeIfStale方法:

public boolean closeIfStale() throws IOException {
    if (isOpen && isStale()) {
        LOG.debug("Connection is stale, closing...");
        close();
        return true;
    }
    return false;
}

核心逻辑位于isStale:

protected boolean isStale() throws IOException {
    boolean isStale = true;
    if (isOpen) {
        // the connection is open, but now we have to see if we can read it
        // assume the connection is not stale.
        isStale = false;
        try {
            if (inputStream.available() <= 0) {
                try {
                    socket.setSoTimeout(1);
                    inputStream.mark(1);
                    int byteRead = inputStream.read();
                    if (byteRead == -1) {
                        // again - if the socket is reporting all data read,
                        // probably stale
                        isStale = true;
                    else {
                        inputStream.reset();
                    }
                finally {
                    socket.setSoTimeout(this.params.getSoTimeout());
                }
            }
        catch (InterruptedIOException e) {
            if (!ExceptionUtil.isSocketTimeoutException(e)) {
                throw e;
            }
            // aha - the connection is NOT stale - continue on!
        catch (IOException e) {
            // oops - the connection is stale, the read or soTimeout failed.
            LOG.debug(
                "An error occurred while reading from the socket, is appears to be stale",
                e
            );
            isStale = true;
        }
    }
 
    return isStale;
}

总结为:

  1. 判断(inputStream.available() <= 0)的目的是支持BufferedInputStream,如果此时连接已经断开但是buffer中尚有未处理的数据,仍然认为是有效的。
  2. 核心的检查逻辑是首先设置一个较短的超时时间,然后执行读操作,如果返回-1,那么说明已断开,如果抛出超时异常(SocketTimeoutException),那么我们依然认为是有效的
  3. 如果抛出其它异常(非SocketTimeoutException),那么认为已断开。

其实这样的判断逻辑依然有问题,即如果网络断开,那么此方法依然会认为是有效的。真正可以准确判断TCP连接断开的方式是write,而不是read,但是精确的判断需要一个较长的耗时(甚至可以达到15分钟)。所以,此种判断方式其实是在准确性和性能之间做了一个折中与取舍。

Q: 服务器是否开启了keep-alive支持?

A: 首先,mail gun服务使用的是HTTP 1.1协议,而此协议默认是开启了keep-alive,我们直接使用curl工具打印一下请求report的响应头,命令:

curl -i -s --user 'api:key-5f57bf6ed1fe62dfed144e551c60b07f' -G \
      https://api.mailgun.net/v3/vipkid.net/events \
      --data-urlencode begin='Fri, 3 May 2013 09:00:00 -0000' \
      --data-urlencode ascending=yes \
      --data-urlencode limit=25 \
      --data-urlencode pretty=yes \
      --data-urlencode recipient=zhangpeilei@vipkid.com.cn \
      --data-urlencode message-id=20180410103836.1.A1CC5A23FBE20FF4@vipkid.net

响应头如下所示:

HTTP/1.1 200 OK
Access-Control-Allow-Headers: Content-Type, x-requested-with
Access-Control-Allow-Methods: GET, POST, PUT, DELETE, OPTIONS
Access-Control-Allow-Origin: *
Access-Control-Max-Age: 600
Content-Type: application/json
Date: Wed, 11 Apr 2018 03:32:21 GMT
Content-Length: 5107
Server: nginx
Connection: keep-alive

注意最后两行,说明mail gun的服务器是nginx且支持keep-alive,但是这里还是有一个隐藏的问题,即:mail gun的nginx设置的超时时间是多少?

此参数由配置keepalive_timeout决定,默认为75秒,设置为0即关闭keep-alive,所以我们的连接池中的连接可以复用多久取决于mail gun的配置。

如果在nginx中配置为:

http {
    keepalive_timeout  0;
}

那么响应头其实是这样的:

对比一下大于零时:

即可进一步得出结论:我们虽然不知道mail gun服务器设置的keep-alive超时时间是多少,但是可以肯定必定大于零

另外,nginx除了对连接有时间上的限制外,还在一个连接处理的请求数维度上进行了限制,来自官方文档:

下面从WireShark的角度确认连接池确实已生效,测试的方法为对两封邮件进行report,注意应该先将连接池的最大连接数设置为1,否则看不到效果,如下:

非常和谐的结果,一次握手,两次交互。

与之对比,使用相同的数据、原来的代码进行测试,如下:

明显的两次握手,两次交互,证明我们的连接池是确实生效的。

Q: HTTP的keep-alive和TCP的keep alive什么区别?

A: Google, Baidu…

4、异步更新

如上面线程模型图,初步设置的批量更新的批次大小为100。这里有个问题,100条是否过大会导致执行失败?

首先MySQL似乎并没有对这个批量的条数有明确的限制,摘自官方文档:

所以唯一的限制应该是喜闻乐见的max_allowed_packet参数,即每次与MySQL服务器交互最大的包大小。可以在nods平台执行以下语句查看其取值:

show VARIABLES like '%max_allowed_packet%';

线上的执行结果如下图:

即128MB。这是MySQL服务器的设置,在jdbc驱动层面上同样可以对此参数进行设置,以下是官方文档:

由于在jdbc层面上我们没有对此参数进行设置,所以最终的上限就是64MB。

一个典型的update语句如下:

UPDATE mail_reports SET status = 1, content = '[{"recipient":"hasekiue@hotmail.com","event":"delivered","timestamp":"1.522422415268628E9","result":1},{"recipient":"hasekiue@hotmail.com","event":"accepted","timestamp":"1.522422414412456E9","result":0}]' WHERE id = 98842348;

长度为273B,所以100条的长度为:273B * 100 / 1024 = 27KB,可以得出最终结论:

100条update语句的大小远小于单次交互字节数上限,不必担心

5、参数调整

-Xms4608M -Xmx4608M -XX:MaxDirectMemorySize=200M -XX:NewRatio=2

思路:

  1. 降低整个堆的大小,内存报警很大程度是由于配置不合理导致,堆内存 + Metaspace等空间 + 其它程序占用内存早已超过物理内存。
  2. 限制堆外内存(NIO用)大小,默认情况下为堆内存减去一个Survivor,虽然在目前的业务场景下堆外内存不会大量使用,但仍然是一个隐患。
  3. 在降低堆的总大小的前提下保持新生代大小不变:4608M / 3 == 6144M / 4.

同时按照如下公式:

4608MB * 70%(CMS回收阈值) + 0.5GB(Metaspace) + 0.5GB(CompressedClassSpaceSize) + 1GB(机器上的其它进程(比如:日志收集进程)) + 0.2GB(Direct buffer) = 5.35GB

而:

5.35GB / 7GB = 76%

未达到报警阈值的80%,所以这样也不会导致内存报警。

Q: NIO用的direct buffer默认上限是多大?

A: 堆内存上限(Xmx)减去一个survivor,非常恐怖。

四、不可描述

  1. 邮件服务从启动到开始报警,没有一次Full GC,也就是说,直到报警,堆的占用率也未达到CMS垃圾回收的阈值 从上图可以看出,堆的最大占用率为59.6%,而我们设置的CMS垃圾回收阈值是70%.
  2. 目前线上Minor GC的频率约为3分钟一次。
  3. 内存暴涨和report之间的关系: 以mail2的GC日志server-gc.log.201804120649为例,内存增长曲线图: 明显有几个暴涨的时间点,这里的时间点是一个相对值(相对于启动时间),结合系统在2018年4月12号早晨6点49启动,所以可以大体推断出绝对值。通过日志查看下mail2机器report执行情况: 后两次report与启动时间的相对值分别为8和14,大体和前两个暴涨的时间点吻合,所以这似乎可以说明report对老年代的增长起到了很大的作用。

五、参考

  1. Shallow heap & Retained heap
  2. LMAX Disruptor
  3. 高性能队列——Disruptor
  4. 新生代和老年代怎样的比例比较合适
  5. JVM源码分析之Metaspace解密
  6. MySQL 加锁处理分析
  7. connector-j-reference-configuration-properties
  8. packet-too-large
  9. [HotSpot VM] JVM调优的”标准参数”的各种陷阱
  10. keepalive_timeout
  11. TCP keepalive 和 http keep-alive

六、附件

server-gc.log.201804120649