201902.txt

满二叉树第i层有2的(i-1)次幂个节点，n层的满二叉树共有2的n次幂-1个节点
------------------------------------------------
两个文件，每个文件中都有若干个url，找出两个文件中相同的url:
方案一：如果两个文件都很小，直接加载到内存，进行内部排序后，进行比较即可。
		如果文件很大，按照哈希，分别将两个文件拆分到可以内部排序的程度，然后分别两两比对即可；
方案二：如果预先知道相同的URL比较少，可以使用布隆过滤器。
------------------------------------------------
随机数a来生成随机数b(a != b)
// 由RandomA来生成RandomB
    // 前提条件a, b都大于1
    public static int random2Random(int a, int b) {
        if (a == b) {
            return getRandom(a);
        }

        if (a > b) { // a = 17, b = 5
            while (true) {
                int tmp = getRandom(a);
                if (tmp <= b * (a / b)) {
                    return tmp / (a / b);
                }
            }
        } else { // a < b
            // X = a * getRandom(a) + getRandom(a) 可等概率生成：0到(a^2 - 1)之间的数
            // 继续直到X >= b
            int nextA = a * a, num = 2;
            while (nextA < b) {
                nextA *= a;
                num++;
            }

            return getRandomNums(a, num);
        }
    }

    private static int getRandomNums(int x, int num) {
        int tmp = x * getRandom(x) + getRandom(x);

        while (num > 2) {
            tmp = x * tmp + getRandom(x);
            num--;
        }
        return tmp;
    }

    private static int getRandom(int x) {
        return ThreadLocalRandom.current().nextInt(x);
    }
------------------------------------------------
DDD方法论在系统建模过程中，可以为团队中的各个角色提供一套"统一语言"，避免组件划分过程中的边界错位，完成领域图预演、需求分析、架构模型、代码模型、测试等工作。
DDD的核心组件：
	1. 界限上下文；
	2. 实体；
	3. 值对象；
	4. 服务；
	5. 聚合；
	6. 聚合根；
	7. 仓储；
	8. 工厂；
------------------------------------------------
Eureka服务剔除的不是90秒没心跳的实例，剔除的是180秒没心跳的实例(Eureka的BUG导致)，如下：
加了两次duration值，com.netflix.eureka.lease.Lease#isExpired(long)

/* Renew the lease, use renewal duration if it was specified by the associated T during 
   registration, otherwise default duration is 90 seconds.
*/
public void renew() {
	lastUpdateTimestamp = System.currentTimeMillis() + duration;
}

/* Checks if the lease of a given com.netflix.appinfo.InstanceInfo has expired or not.
Note that due to renew() doing the "wrong" thing and setting lastUpdateTimestamp to +duration more than 
what it should be, the expiry will actually be 2 * duration. This is a minor bug and should only affect
 instance that ungracefully shutdown. Due to possible wide ranging impact to existing usage, this will
 not be fixed.
*/
public boolean isExired(long additionalLeaseMs) {
	return (evictionTimestamp > 0 || System.currentTimeMillis() > lastUpdateTimestamp + duration + additionalLeaseMs));
}
------------------------------------------------
选择排序：简单选择排序->树形选择排序(锦标赛排序)->堆排序 

TCP如何保证可靠传输：校验和、序列号、确认应答、超时重传、连接管理、流量控制、拥塞控制。
	1. 校验和；
	2. 确认应答和序列号；
	3. 超时重传；
	4. 连接管理：三次握手、四次挥手；
	5. 滑动窗口：流量控制和拥塞控制都是使用了滑动窗口来实现；
	6. 流量控制；
	7. 拥塞控制；

-XX:G1HeapRegionSize=xxx：使用G1时Java堆被分为大小统一的区Region。此参数可以指定每个heap区的大小。默认值将更加heap size算出最优解。最小值1M,最大值32M。
------------------------------------
所有的内部排序算法:
	1. 插入排序
		1.1 直接插入排序 
		1.2 其他插入排序: 折半插入排序，2-路插入排序，表插入排序
		1.3 希尔排序 
	2. 快速排序
	3. 选择排序 
		3.1 简单选择排序 
		3.2 树形选择排序 
		3.3 堆排序 
	4. 归并排序 
	5. 基数排序 
		5.1 多关键字的排序 
		5.2 链式基数排序
------------------------------------
-XX:+PrintGCApplicationStoppedTime:打印程序暂停时间
-XX:+PrintReferenceGC:GC清理了多少引用类型，查看各种引用对GC的影响。

GCViewer is a little tool that visualizes verbose GC output generated by Sun / Oracle, IBM, HP and BEA Java Virtual Machines. It is free software released under GNU LGPL.
You can start GCViewer (gui) by simply double-clicking on gcviewer-1.3x.jar or running java -jar gcviewer-1.3x.jar (it needs a java 1.8 vm to run).

分配速率的变化，会增加或降低GC暂停的频率，从而影响吞吐量。但只有年轻代的MinorGC受分配速率的影响，老年代GC的频率和持续时间不受分配速率(Allocation rate)的直接影响，而是受到提升速率(Promotion Rate)的影响。
有时候JVM很智能，会使用逃逸分析技术(escape analysis technique)来避免过度分配。简单来说，JIT编译器可以通过分析得知，方法创建的某些对象永远都不会"逃出"此方法的作用域。这时候就不需要在堆上分配这些对象，也就不会产生垃圾，所以JIT编译器的一种优化手段就是：消除内存分配。

过早提升: Premature Promotion 
提升速率(promotion rate), 用于衡量单位时间内从年轻代提升到老年代的数据量。一般使用 MB/sec 作为单位, 和分配速率类似。
JVM会将长时间存活的对象从年轻代提升到老年代。根据分代假设, 可能存在一种情况, 老年代中不仅有存活时间长的对象,也可能有存活时间短的对象。这就是过早提升：对象存活时间还不够长的时候就被提升到了老年代。
major GC 不是为频繁回收而设计的, 但 major GC 现在也要清理这些生命短暂的对象, 就会导致GC暂停时间过长。这会严重影响系统的吞吐量。
只能根据Minor GC计算提升速率。FGC的日志不能用于计算提升速率，因为Major GC会清理老年代中的一部分对象。
-------------------------------------------------------
让一个线程阻塞的方法: 
	1. LockSupport#park 
	2. Object#wait 
	3. Condition#await 
	4. Thread#join 
	5. Thread#sleep
	6. ExecutorService#invokeAll
	7. Future#get 
	8. ExecutorService#awaitTermination
	9. CountDownLath#await
	10. CyclicBarrier#await 
-------------------------------------------------------
OSI的七层分层：
	1. 物理层: 建立、维护、断开物理连接（由底层网络定义协议）
	2. 数据链路层：建立逻辑连接、进行硬件地址寻址、差错校验等功能(由底层网络定义协议)。将比特组合成字节进而组合成帧，用MAC地址访问介质，错误发现但不能纠正。
	3. 网络层：进行逻辑地址寻址，实现不同网络之间的路径选择；协议有：ICMP, IGMP, IPv4, IPv6；
	4. 传输层：定义传输数据的协议端口号，以及流控和差错校验。协议有：TCP, UDP，数据包一旦离开网卡即进入网络传输层。
	5. 会话层：建立、管理、终止会话。(在五层模型里已经合并到了应用层)；对应主机进程，指本地主机与远程主机正在进行的会话。
	6. 表示层：数据的表示、安全、压缩。(在五层模型里已经合并到了应用层)；格式有：Jpeg, ascii, decoic,加密格式等；
	7. 应用层：网络服务与最终用户的一个接口；协议有：HTTP, FTP, TFTP, SMTP, SNMP, DNS, TELNET, HTTPS, POP3, DHCP；

从一张大表读取数据，如何解决性能问题：
	1. 优化SQL语句：合理分页、join、order by、group by等合理使用。
	2. 增加合适的索引和合理使用索引；
	3. 设计合理的表结构；
	4. 分区表；
	5. 数据库的读写分离；
	6. 增加硬件配置：服务器、网络、IO、硬盘等；
	7. 数据库分库分表；
	8. 数据的冷热分离；
	9. 汇总表；
	10. 接入Spark；
	11. 接入Hive；
	12. 缓存；
	13. 开启查询缓存；
-------------------------------------------------------------------------------
R树是一种多级平衡树，它是B树在多维空间上的扩展。在R树中存放的数据并不是原始数据，而是这些数据的最小边界矩阵(MBR)，空间对象的MBR被包含于R树的叶节点中。在R树空间索引中，设计一些虚拟的矩阵目标，将一些空间位置相近的目标，包含在这个矩形内，这些虚拟的矩形作为空间索引，它含有所包含的空间对象的指针。虚拟矩形还可以进一步细分，即可以再套虚拟矩形形成多级空间索引。
R+树：在R树的构造中，要求虚拟矩形一般尽可能少地重叠，并且一个空间对通常仅被一个虚拟矩形所包含。但空间对象千姿百态，它们的最小矩形范围经常重叠。R+改进树的空间索引，为了平衡，它允许虚拟矩形互相重叠，并允许一个空间目标被多个虚拟矩形所包含。	

如何判断点在多边形内部？可以通过射线法来判断点是否在多边形内部。从该点出发沿X轴画一条射线，依次判断该射线与每条边的交点，并统计交点个数，如果交点数位奇数，则在多边形内部。如果交点数是偶数，则在外部。射线法对凸和非凸多边形都适用，复杂度为O(N),其中N是边数。
一棵R树满足如下性质：
	1. 除非它是根节点，所有叶子节点包含有m到M个记录索引(条目)。作为根节点的叶子节点所具有的记录个数可以少于m。通常m=M/2；
	2. 对应所有在叶子中存储的记录(条目)，I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形(注意:此处的"矩形"是可以扩展到高维空间的)；
	3. 每一个非叶子节点拥有m至M个孩子节点，除非它是根节点；
	4. 对于在非叶子节点上的每一个条目，I是最小的可以在空间上完全覆盖这些条目代表的矩形；
	5. 所有叶子节点都位于同一层，因此R树是平衡树。


在运用X锁和S锁对数据对象加锁时，还需要约定一些规则，例如何时申请X锁或S锁、持锁时间、何时释放等。称这些规则为封锁协议(Locking Protocol)。对封锁方式规定不同的规则，就形成了各种不同的封锁协议。


数据库的三级封锁协议:
	一级封锁协议(对应read uncommitted);
	二级封锁协议(对应read committed);
	三级封锁协议(对应reapeatable read);
	四级封锁协议(对应serialization);

在含有N个关键字的B树上进行查找时，从根节点到关键字所在节点的路径上涉及的节点数不超过log[m/2]((N+1)/2) + 1。
一棵含有N个关键字的m阶的B树的最大高度是多少：log(ceil(m/2)) ((N + 1) / 2) + 1

B+树是应文件系统所需而出的一种B树的变种树。一棵m阶的B+树和m阶的B树的差异在于：
	1. 有n棵子树的节点中含有n个关键字；
	2. 所有叶子节点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子节点本身依关键字的大小自小到大顺序链接；
	3. 所有的非终端节点可以看成是索引部分，节点中仅含有其子树(根节点)中的最大/最小关键字。

B*树是B+树的变种树，在B+树的基础上(所有的叶子节点包含了全部关键字信息，及指向含有这些关键字记录的指针)，B*树中非根和非叶子节点再增加指向兄弟的指针；B*树定义了非叶子节点关键字个数至少为(2/3)*M，即块的最低使用率为2/3(代替B+树的1/2)。

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。
所以，B*树分配新节点的概率比B+树要低，空间使用率更高。

一棵R树满足如下的性质：
	1. 除非它是根结点之外，所有叶子结点包含有m至M个记录索引（条目）。作为根结点的叶子结点所具有的记录个数可以少于m。通常，m=M/2。
	2. 对于所有在叶子中存储的记录（条目），I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。
	3. 每一个非叶子结点拥有m至M个孩子结点，除非它是根结点。
	4. 对于在非叶子结点上的每一个条目，i是最小的可以在空间上完全覆盖这些条目所代表的店的矩形（同性质2）。
	5. 所有叶子结点都位于同一层，因此R树为平衡树。

实现一个保证迭代顺序的HashMap: 参考LinkedHashMap的实现。

public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> {
	static class Entry<K, V> extends HashMap.Node<K, V> {
		Entry<K, V> before, after;
		Entry(int hash, K key, V value, Node<K, V> next) {
			super(hash, key, value, next);
		}
	}
	
	private static final long serialVersionUID = 3801124242820219131L;
	//The head(eldest) of the doubly linked list.
	transient LinkedHashMap.Entry<K, V> head;
	//The tail(youngest) of the doubly linked list.
	transient LinkedHashMap.Entry<K, V> tail;
	//The iteration ordering method for this linked hash map:
	//true for access-order, false for insertion-order;
	final boolean accessOrder;

}


三者的递归公式：
	0-1背包： ks(i, t) = max {ks(i-1, t - V[i] * k)}; (0<=k<=1 && V[i] <= t)
	完全背包：ks(i, t) = max {ks(i-1, t - V[i] * k) + P[i] * k}; (0 <= k*V[i] <= t)
	多重背包：ks(i, t) = max {ks(i-1, t - V[i] * k) + P[i] * k}; (0<=k<=M[i] && 0 <= k*V[i] <= t)

简单工厂：最简单，能满足大部分日常需求；缺点：太简单，无法满足开闭原则，对多个产品的扩展不利。
工厂方法：
抽象工厂：缺点：增加一个产品族的话，会改动抽象工厂角色，具体工厂角色。改动比较多。

有向图强连通分量：在有向图G中，如果两个顶点Vi,Vj间(Vi>Vj)有一条从Vi到Vj的有向路径，同时还有从Vj到Vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

最小生成树:构造最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简称为MST的性质：假设N = (V, {E})是一个连通网，U是顶点集V的一个非空子集。若(u, v)是一条最小权值(代价)的边，其中u属于U，v属于V-U，则比存在一棵包含边(u,v)的最小生成树。(可以用反证法证明)
普里姆Prim算法和克鲁斯卡尔Kruskal算法是两个利用MST性质构造最小生成树的算法。

装饰(Decorator)模式的定义：指在不改变现有对象结构的情况下，动态地给该对象增加一些职责(即增加其额外功能)的模式，它属于对象结构型模式。
装饰(Decorator)模式的主要优点有：
	- 采用装饰模式扩展对象的功能比采用继承更加灵活；
	- 可以设计出多个不同的具体装饰类，创造出多个不同行为的组合。
装饰(Decorator)模式的缺点：装饰模式增加了许多个子类，如果过度使用会使程序变得复杂。
装饰模式的结构与实现：通常情况下，扩展一个类的功能会使用继承方式来实现。但继承具有静态特征，耦合度高，并且随着扩展功能的增多，子类会很膨胀。如果使用组合关系来创建一个包装对象（即装饰对象）来包裹真实对象，并在保持真实对象的类结构不变的前提下，为其提供额外的功能，这就是装饰模式的目标。

装饰模式的主要角色如下：
	- 抽象构件(Component)角色：定义一个抽象接口以规范准备接收附加责任的对象。
	- 具体构件(ConcreteComponent)角色：实现抽象构件，通过装饰角色为其添加一些职责。
	- 抽象装饰(Decorator)角色：继承抽象构件，并包含具体构件的实例，可以通过其子类扩展具体构件的功能。
	- 具体装饰(ConcreteDecorator)角色：实现抽象装饰的相关方法，并给具体构件对象添加附加的责任。

/* A Red-Black tree based NavigableMap implementation. The map is sorted according to the Comparable natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the #containsKey, #get and #remove operations.
*/
public class TreeMap<K, V> extends AbstractMap<K, V> 
					implements NavigableMap<K, V>, Cloneable, java.io.Serializable {
	private final Comparator<? super K> comparator;
	private transient Entry<K, V> root;
	private transient int size;
	private transient int modCount = 0;
	...
	// Views
	/* Fields initialized to contain an instance of the entry set view the first time this view is requested. 
	* Views are stateless, so there's no reason to create more than one.
	*/
	private transient EntrySet entrySet;
	private transient KeySet<K> navigableKeySet;
	private transient NavigableMap<K, V> descendingMap;
	...
	// Red-black mechanics
	private static final boolean RED = false;
	private static final boolean BLACK = true;
	...
}

TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合， NavigableMap（更多）则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法 。

红黑树的五点规则：
	1、每个节点都只能是红色或者黑色
	2、根节点是黑色
	3、每个叶节点（NIL节点，空节点）是黑色的。
	4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
	5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的5个约束规则强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

对于新节点的插入有如下三个关键地方：
	1. 插入新节点总是红色节点；
	2. 如果插入节点的父节点是黑色，能维持性质；
	3. 如果插入节点的父节点是红色，破坏了性质。故插入算法就是通过重新着色或旋转，来维持性质；

七大设计原则：
	1. 开闭原则: Open Closed Principle, OCP
	2. 里氏替换原则：Liskov Subsitution, LSP
	3. 依赖倒置原则：Dependence Inversion Principle, DIP
	4. 单一职责原则：Single Responsibility Principle, SRP
	5. 接口隔离原则：Interface Segregation Principle, ISP
	6. 迪米特法则：Law of Demeter, LoD;又叫做最少知识原则: Least Knowledge Principle: LKP
	7. 合成复用原则：Composite Reuse Principle, CRP;又叫做组合/聚合复用原则: Composition/Aggregate Reuse Principle, CARP

接口隔离原则和单一职责都是为了提高类的内聚性、降低它们之间的耦合性，体现了封装的思想，但两者是不同的：
	- 单一职责原则注重的是职责，而接口隔离原则注重的是对接口依赖的隔离；
	- 单一职责原则主要是约束类，它针对的是程序中的实现和细节；接口隔离原则主要约束接口，主要针对抽象和程序整体框架的构建；

这7种设计原则是软件设计模式必须尽量遵循的原则，各种原则要求的侧重点不同。其中，开闭原则是总纲，告诉我们要对扩展开放，对修改关闭；里氏替换原则告诉我们不要破坏继承体系；依赖倒置原则告诉我们要面向接口编程；单一职责原则告诉我们要实现类的职责单一；接口隔离原则告诉我们设计接口的时候要精简单一；迪米特法则告诉我们要降低耦合度；合成复用原则告诉我们要优先使用组合或者聚合关系复用，少用继承关系复用。

创建型模式的主要关注点是“怎样创建对象？”，它的主要特点是“将对象的创建与使用分离”。这样可以降低系统的耦合度，使用者不需要关注对象的创建细节，对象的创建由相关的工厂来完成。

实际上，JDK8种的Lambda表达式在大多数虚拟机种采用invokeDynamic指令实现，相对于匿名内部类在效率上会更高一些。

为类指定final修饰符，可以让类不可以被继承；如果指定了一个类为final,则该类所有的方法都是final的，Java编译器会寻找机会内联所有的final方法。内联对于提升Java运行效率作用重大，具体可参加Java运行期优化，能够使性能平均提高50%。

所有的private方法会隐式地被指定final修饰符，所以无须再为其指定final修饰符。

if-else语句，每个if条件语句都要加装计算，直到if条件语句为true为止。switch语句进行了跳转优化，Java中采用tableswitch或lookupswitch指令实现，对于多常量选择分支处理效率更高。经过试验证明：在每个分支出现概率相同的情况下，低于5个分支时if-else语句效率更高，高于5个分支时switch语句效率更高。

推荐使用System.arraycopy拷贝数组，也可以使用Arrays.copyOf拷贝数组。

SRE: Site Reliability Engineering

API批量服务能力：批量的服务能力，提升整体服务性能。

这里解释下上图中CPU内部集成的存储单元SRAM ，正好和主存中的DRAM对应， RAM 是随机访问内存，就是给一个地址就能访问到数据，而磁盘这种存储媒介必须顺序访问，而RAM又分为动态和静态两种，静态RAM 由于集成度较低，一般容量小，速度快，而动态RAM集成度较高，主要通过给电容充电和放电实现，速度没有静态RAM快，所以一般将动态RAM做为主存，而静态RAM作为 CPU和主存之间的高速缓存（cache），用来屏蔽CPU和主存速度上的差异，也就是我们经常看到的L1，L2缓存。每一级别缓存速度变低，容量变大。

JVM为了提高运行效率也可以将某些热点代码(一个方法内的代码)一次全部编译成机器指令后然后再执行，也就是和解释执行对应的即时编译(JIT)，JVM启动的时候可以通过-Xint和-Xcomp来控制执行模式。

在保护模式下，每一个进程都有自己的独立的地址空间，所以段基地址是固定的，只需要给出段内偏移地址就可以了，而这个偏移地址称为线性地址，线性地址是连续的，而内存将连续的线性地址和分页后的物理地址相关联，这样逻辑上的连续线性地址可以对应不连续的物理地址。
物理地址空间可以被多个进程共享，而这个映射关系将通过页表（ page table）进行维护。 标准页的尺寸一般为 4KB ，分页后，物理内存被分成若干个 4KB 的数据页，进程申请内存的时候，可以映射为多个 4KB 大小的物理内存，而应用程序读取数据的时候会以页为最小单位，当需要和硬盘发生交换的时候也是以页为单位。
因为他是独占的，也保护了各自进程不被其他进程破坏，另外，他把主存看成磁盘的一个缓存，主存中仅保存活动的程序段和数据段，当主存中不存在数据的时候发生缺页中断，然后从磁盘加载进来，当物理内存不足的时候会发生 swap 到磁盘。页表保存了虚拟地址和物理地址的映射，页表是一个数组，每个元素为一个页的映射关系，这个映射关系可能是和主存地址，也可能和磁盘，页表存储在主存，我们将存储在高速缓冲区 cache  中的页表称为快表 TLAB 。

在Java中，使用MappedByteBuffer来实现内存映射，这是一个堆外内存，在映射完之后，并没有立即占用物理内存，而是访问数据页的时候，先查页表，发现还没加载，发起缺页异常，然后在从磁盘将数据加载进内存，所以一些实时性要求很高的中间件，例如rocketmq,消息存储在一个大小1G的文件中，为了加快读写速度，会将这个文件映射到内存后，在每个页写一比特数据，这样就可以把整个1G文件都加载进内存，在实际读写的时候就不会发生缺页了，这个在rocketmq内部叫做文件预热。

JVM 为了内存对齐，会对字段进行重排序，这里的对齐主要指  Java  虚拟机堆中的对象的起始地址为 8 的倍数，如果一个对象用不到 8N 个字节，那么剩下的就会被填充，另外子类继承的属性的偏移量和父类一致，以 Long 为例，他只有一个非 static 属性 value ，而尽管对象头只占有 12 字节，而属性 value 的偏移量只能是 16， 其中 4 字节只能浪费掉，所以字段重排就是为了避免内存浪费， 所以我们很难在 Java 字节码被加载之前分析出这个 Java 对象占有的实际空间有多大，我们只能通过递归父类的所有属性来预估对象大小，而真实占用的大小可以通过  Java agent 中的 Instrumentation获取。
当然内存对齐另外一个原因是为了让字段只出现在同一个CPU的缓存行中，如果字段不对齐，就有可能出现一个字段的一部分在缓存行 1中，而剩下的一半在缓存行2 中，这样该字段的读取需要替换两个缓存行，而字段的写入会导致两个缓存行上缓存的其他数据都无效，这样会影响程序性能。

通过内存对齐可以避免一个字段同时存在两个缓存行里的情况，但还是无法完全规避缓存伪共享的问题，也就是一个缓存行中存了多个变量，而这几个变量在多核 CPU 并行的时候，会导致竞争缓存行的写权限，当其中一个 CPU 写入数据后，这个字段对应的缓存行将失效，导致这个缓存行的其他字段也失效。
在 Disruptor 中，通过填充几个无意义的字段，让对象的大小刚好在 64 字节，一个缓存行的大小为64字节，这样这个缓存行就只会给这一个变量使用，从而避免缓存行伪共享，但是在 jdk7 中，由于无效字段被清除导致该方法失效，只能通过继承父类字段来避免填充字段被优化，而 jdk8 提供了注解@Contended 来标示这个变量或对象将独享一个缓存行，使用这个注解必须在 JVM 启动的时候加上 -XX:-RestrictContended 参数，其实也是用空间换取时间。

按照教科书的定义，进程是资源管理的最小单位，而线程是 CPU 调度执行的最小单位，线程的出现是为了减少进程的上下文切换（线程的上下文切换比进程小很多），以及更好适配多核心 CPU 环境，例如一个进程下多个线程可以分别在不同的 CPU 上执行，而多线程的支持，既可以放在Linux内核实现，也可以在核外实现，如果放在核外，只需要完成运行栈的切换，调度开销小，但是这种方式无法适应多 CPU 环境，底层的进程还是运行在一个 CPU 上，另外由于对用户编程要求高，所以目前主流的操作系统都是在内核支持线程，而在Linux中，线程是一个轻量级进程，只是优化了线程调度的开销。

而在 JVM 中的线程和内核线程是一一对应的，线程的调度完全交给了内核，当调用Thread.run 的时候，就会通过系统调用 fork() 创建一个内核线程，这个方法会在用户态和内核态之间进行切换，性能没有在用户态实现线程高，当然由于直接使用内核线程，所以能够创建的最大线程数也受内核控制。目前 Linux上 的线程模型为 NPTL （ Native POSIX Thread Library），他使用一对一模式，兼容 POSIX 标准，没有使用管理线程，可以更好地在多核 CPU 上运行。

对进程而言，就三种状态，就绪，运行，阻塞，而在 JVM 中，阻塞有四种类型，我们可以通过 jstack 生成 dump 文件查看线程的状态。
	- BLOCKED(on object monitor)通过 synchronized(obj) 同步块获取锁的时候，等待其他线程释放对象锁，dump 文件会显示 waiting to lock <0x00000000e1c9f108>
	- TIMED WAITING(on object monitor)和WAITING(on object monitor)在获取锁后，调用了 object.wait() 等待其他线程调用 object.notify()，两者区别是是否带超时时间
	- TIMED WAITING(sleeping)程序调用了 thread.sleep()，这里如果 sleep(0) 不会进入阻塞状态，会直接从运行转换为就绪
	- TIMED WAITING(parking)和WAITING(parking)程序调用了 Unsafe.park()，线程被挂起，等待某个条件发生，waiting on condition

POSIX 定义了五种同步对象，互斥锁，条件变量，自旋锁，读写锁，信号量，这些对象在 JVM 中也都有对应的实现，并没有全部使用 POSIX 定义的 api，通过 Java 实现灵活性更高，也避免了调用native方法的性能开销，当然底层最终都依赖于 pthread 的 互斥锁 mutex 来实现，这是一个系统调用，开销很大，所以 JVM 对锁做了自动升降级，基于AQS的实现以后在分析，这里主要说一下关键字 synchronized 。
当声明 synchronized 的代码块时，编译而成的字节码会包含一个 monitorenter 和 多个 monitorexit （多个退出路径，正常和异常情况），当执行 monitorenter 的时候会检查目标锁对象的计数器是否为0，如果为0则将锁对象的持有线程设置为自己，然后计数器加1，获取到锁，如果不为0则检查锁对象的持有线程是不是自己，如果是自己就将计数器加1获取锁，如果不是则阻塞等待，退出的时候计数器减1，当减为0的时候清楚锁对象的持有线程标记，可以看出 synchronized 是支持可重入的。

刚刚说到线程的阻塞是一个系统调用，开销大，所以 JVM 设计了自适应自旋锁，就是当没有获取到锁的时候， CPU 回进入自旋状态等待其他线程释放锁，自旋的时间主要看上次等待多长时间获取的锁，例如上次自旋5毫秒没有获取锁，这次就6毫秒，自旋会导致 CPU 空跑，另一个副作用就是不公平的锁机制，因为该线程自旋获取到锁，而其他正在阻塞的线程还在等待。除了自旋锁， JVM 还通过 CAS 实现了轻量级锁和偏向锁来分别针对多个线程在不同时间访问锁和锁仅会被一个线程使用的情况。后两种锁相当于并没有调用底层的信号量实现（通过信号量来控制线程A释放了锁例如调用了 wait()，而线程B就可以获取锁，这个只有内核才能实现，后面两种由于场景里没有竞争所以也就不需要通过底层信号量控制），只是自己在用户空间维护了锁的持有关系，所以更高效。


如上图所示，如果线程进入 monitorenter 会将自己放入该 objectmonitor 的 entryset 队列，然后阻塞，如果当前持有线程调用了 wait 方法，将会释放锁，然后将自己封装成 objectwaiter 放入 objectmonitor 的 waitset 队列，这时候 entryset 队列里的某个线程将会竞争到锁，并进入 active 状态，如果这个线程调用了 notify 方法，将会把 waitset 的第一个 objectwaiter 拿出来放入 entryset （这个时候根据策略可能会先自旋），当调用 notify 的那个线程执行 moniterexit 释放锁的时候， entryset 里的线程就开始竞争锁后进入 active 状态。

LockSupport.park(long nans)   Condition.await()调用的该方法， ScheduledExecutorService 用的 condition.await() 来实现阻塞一定的超时时间，其他带超时参数的方法也都通过他来实现，目前大多定时器都是通过这个方法来实现的，该方法也提供了一个布尔值来确定时间的精度。

抽象工厂(AbstractFactory)模式的定义：是一种为访问类提供一个创建一组相关或互相依赖对象的接口，且访问类无需指定所要产品的具体类就能得到同族的不同等级的产品的模式结构。
抽象工厂模式是工厂方法模式的升级版本，工厂方法模式只生产一个等级的产品，而抽象工厂模式可生产多个等级的产品。
使用抽象工厂模式一般要满足以下条件：
	- 系统中有多个产品族，每个具体工厂创建同一族但属于不同等级结构的产品；
	- 系统一次只可能消费其中某一族产品，即同族的产品一起使用；
抽象工厂模式除了具有工厂方法模式的优点外，其他主要优点如下：
	- 可以在类的内部堆产品族相关联的多等级产品共同管理，而不必专门引入多个新的类来进行管理；
	- 当增加一个新的产品族时不需要修改原代码，满足开闭原则；
其缺点是：当产品族中需要增加一个新的产品时，所有的工厂类都需要进行修改。

抽象工厂模式的应用场景：
	1. 当需要创建的对象是一系列相互关联或相互依赖的产品族时，如电器工厂中的电视机、洗衣机、空调等。
	2. 系统中有多个产品族，但每次只使用其中的某一族产品。如有人只喜欢穿某一个品牌的衣服和鞋。
	3. 系统中提供了产品的类库，且所有产品的接口相同，客户端不依赖产品实例的创建细节和内部结构。

模式的扩展：
抽象工厂模式的扩展有一定的“开闭原则”倾斜性：
	1. 当增加一个新的产品族时只需增加一个新的具体工厂，不需要修改原代码，满足开闭原则。
	2. 当产品族中需要增加一个新种类的产品时，则所有的工厂类都需要进行修改，不满足开闭原则。
另一方面，当系统中只存在一个等级结构的产品时，抽象工厂模式将退化到工厂方法模式。


在性能优化这个领域，并没有一个严格的流程定义，但是对于绝大多数的优化场景，我们可以将其过程抽象为下面四个步骤。
	1. 准备阶段：主要工作是是通过性能测试，了解应用的概况、瓶颈的大概方向，明确优化目标；
	2. 分析阶段：通过各种工具或手段，初步定位性能瓶颈点；
	3. 调优阶段：根据定位到的瓶颈点，进行应用性能调优；
	4. 测试阶段：让调优过的应用进行性能测试，与准备阶段的各项指标进行对比，观测其是否符合预期，如果瓶颈点没有消除或者性能指标不符合预期，则重复步骤2和3。

在进行性能优化时，有以下注意事项：
	1. 性能瓶颈点通常呈现2/8分布，即80%的性能问题通常是由20%的性能瓶颈点导致的，2/8 原则也意味着并不是所有的性能问题都值得去优化；
	2. 性能优化是一个渐进、迭代的过程，需要逐步、动态地进行。记录基准后，每次改变一个变量，引入多个变量会给观测、优化过程造成干扰；
	3. 不要过度追求应用的单机性能，如果单机表现良好，则应该从系统架构的角度去思考；不要过度追求单一维度上的极致优化，如过度追求CPU的性能而忽略了内存方面的瓶颈；
	4. 旋转合适的性能优化工具，可以使得性能优化取得事半功倍的效果；
	5. 整个应用的优化，应该与线上系统隔离，新的代码上线应该有降级方案；

如果瓶颈点在应用层和系统层均呈现多变量分布，建议此时使用ZProfiler, JProfiler等工具对应用进行Profiling, 获取应用的综合性能信息(Profiling指的是在应用运行时，通过事件(Event-based)、统计抽样(Sampling Statistical)或植入附加指令(Byte-Code instrumentattion)等方法，收集应用运行时的信息，来研究应用行为的动态分析方法)。譬如，可以对CPU进行抽样统计，结合各种符号表信息，得到一段时间内的代码热点。

1. CPU利用率: CPU Utilization
2. CPU平均负载: Load Average
3. 上下文切换次数：Context Switch 

使用vmstat命令，可以查看到【上下文切换次数】这个指标，vmstat 1：每隔1秒输出1组数据。
cs：context switch每秒上下文切换的次数，按照不同场景，CPU上下文切换还可以分为中断上下文切换、线程上下文切换和进程上下文切换三种，但是无论是哪一种，过多的上下文切换，都会把CPU时间消耗在寄存器、内核栈以及虚拟内存等数据的保存和恢复上，从而缩短进程真正运行的时间，导致系统的整体性能大幅下降。
vmstat的输出只给出了系统总体的上下文切换情况，要想查看每个进程的上下文切换详情(如自愿和非自愿)，需要使用pidstat，该命令还可以查看某个进程用户态和内核态的CPU利用率。

buff/cache 是缓存和缓冲区的大小。缓存（cache）：是从磁盘读取的文件的或者向磁盘写文件时的临时存储数据，面向文件。使用 cachestat 可以查看整个系统缓存的读写命中情况，使用 cachetop 可以观察每个进程缓存的读写命中情况。缓冲区（buffer）是写入磁盘数据或从磁盘直接读取的数据的临时存储，面向块设备。free 命令的输出中，这两个指标是加在一起的，使用 vmstat 命令可以区分缓存和缓冲区，还可以看到 Swap 分区换入和换出的内存大小。


内存相关指标异常后，分析思路是怎么样的？
	1. 使用 free/top 查看内存的全局使用情况，如系统内存的使用、Swap 分区内存使用、缓存/缓冲区占用情况等，初步判断内存问题存在的方向：进程内存、缓存/缓冲区、Swap 分区；
	2. 观察一段时间内存的使用趋势。如通过 vmstat 观察内存使用是否一直在增长；通过 jmap 定时统计对象内存分布情况，判断是否存在内存泄漏，通过 cachetop 命令，定位缓冲区升高的根源等；
	3. 根据内存问题的类型，结合应用本身，进行详细分析。

举例：使用 free 发现缓存/缓冲区占用不大，排除缓存/缓冲区对内存的影响后 -> 使用 vmstat 或者 sar 观察一下各个进程内存使用变化趋势 -> 发现某个进程的内存时候用持续走高 -> 如果是 Java 应用，可以使用 jmap / VisualVM / heap dump 分析等工具观察对象内存的分配，或者通过 jstat 观察 GC 后的应用内存变化 -> 结合业务场景，定位为内存泄漏/GC参数配置不合理/业务代码异常等。

结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式，前者采用继承机制来组织接口和类，后者釆用组合或聚合来组合对象。
由于组合关系或聚合关系比继承关系耦合度低，满足“合成复用原则”，所以对象结构型模式比类结构型模式具有更大的灵活性。
结构型模式分为以下 7 种：
	1. 代理（Proxy）模式：为某对象提供一种代理以控制对该对象的访问。即客户端通过代理间接地访问该对象，从而限制、增强或修改该对象的一些特性。
	2. 适配器（Adapter）模式：将一个类的接口转换成客户希望的另外一个接口，使得原本由于接口不兼容而不能一起工作的那些类能一起工作。
	3. 桥接（Bridge）模式：将抽象与实现分离，使它们可以独立变化。它是用组合关系代替继承关系来实现的，从而降低了抽象和实现这两个可变维度的耦合度。
	4. 装饰（Decorator）模式：动态地给对象增加一些职责，即增加其额外的功能。
	5. 外观（Facade）模式：为多个复杂的子系统提供一个一致的接口，使这些子系统更加容易被访问。
	6. 享元（Flyweight）模式：运用共享技术来有效地支持大量细粒度对象的复用。
	7. 组合（Composite）模式：将对象组合成树状层次结构，使用户对单个对象和组合对象具有一致的访问性。
以上 7 种结构型模式，除了适配器模式分为类结构型模式和对象结构型模式两种，其他的全部属于对象结构型模式。


综上，没有结构化编程，程序就无法从一块块可证伪的逻辑搭建，没有面向对象编程，跨越组件边界是一个非常麻烦而危险的过程，而函数式编程，让组件更加高效而稳定。没有编程范式，架构设计将无从谈起。

和编程范式(结构化编程、面向对象编程、函数式编程)相比，进行架构设计的主导原则是OCP(开闭原则)，在类和代码的层级上有：SRP(单一职责原则)、LSP(里氏替换原则)、ISP(接口隔离原则)、DIP(依赖倒转原则)；在组件的层级上有：REP(复用、发布等同原则)、CCP(共同闭包原则)、CRP(共同复用原则)，处理组件依赖问题的三原则：无依赖环原则、稳定依赖原则、稳定抽象原则。