《后端架构师技术图谱》
后端架构师技术图谱》
更新于20180916
（Toc generated by simple-php-github-toc ）
数据结构
队列
非阻塞队列：ConcurrentLinkedQueue(无界线程安全)，采用CAS机制（compareAndSwapObject原子操作）。
阻塞队列：ArrayBlockingQueue(有界)、LinkedBlockingQueue（无界）、DelayQueue、PriorityBlockingQueue，采用锁机制；使用 ReentrantLock 锁。
集合
链表、数组
字典、关联数组
栈
Stack 是线程安全的。
内部使用数组保存数据，不够时翻倍。
树
二叉树
每个节点最多有两个叶子节点。
完全二叉树
叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
平衡二叉树
左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉查找树（BST）
二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree）。
红黑树
添加阶段后，左旋或者右旋从而再次达到平衡。
B，B+，B*树
MySQL是基于B+树聚集索引组织表
B+树的叶子节点链表结构相比于 B-树便于扫库，和范围检索。
LSM 树
LSM（Log-Structured Merge-Trees）和 B+ 树相比，是牺牲了部分读的性能来换取写的性能(通过批量写入)，实现读写之间的。 Hbase、LevelDB、Tair（Long DB）、nessDB 采用 LSM 树的结构。LSM可以快速建立索引。
B+ 树读性能好，但由于需要有序结构，当key比较分散时，磁盘寻道频繁，造成写性能。
LSM 是将一个大树拆分成N棵小树，先写到内存（无寻道问题，性能高），在内存中构建一颗有序小树（有序树），随着小树越来越大，内存的小树会flush到磁盘上。当读时，由于不知道数据在哪棵小树上，因此必须遍历（二分查找）所有的小树，但在每颗小树内部数据是有序的。
极端的说，基于LSM树实现的HBase的写性能比MySQL高了一个数量级，读性能低了一个数量级。
优化方式：Bloom filter 替代二分查找；compact 小数位大树，提高查询性能。
Hbase 中，内存中达到一定阈值后，整体flush到磁盘上、形成一个文件（B+数），HDFS不支持update操作，所以Hbase做整体flush而不是merge update。flush到磁盘上的小树，定期会合并成一个大树。
BitSet
经常用于大规模数据的排重检查。
常用算法
排序、查找算法
选择排序
每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。
冒泡排序
相邻元素前后交换、把最大的排到最后。
时间复杂度 O(n²)
插入排序
快速排序
一侧比另外一次都大或小。
归并排序
分而治之，分成小份排序，在合并(重建一个新空间进行复制)。
希尔排序
TODO
堆排序
排序过程就是构建最大堆的过程，最大堆：每个结点的值都大于或等于其左右孩子结点的值，堆顶元素是最大值。
计数排序
和桶排序过程比较像，差别在于桶的数量。
桶排序
桶排序将[0,1)区间划分为n个相同的大小的子区间，这些子区间被称为桶。
每个桶单独进行排序，然后再遍历每个桶。
基数排序
按照个位、十位、百位、...依次来排。
二分查找
要求待查找的序列有序。
时间复杂度 O(logN)。
while + 递归。
Java 中的排序工具
Collections.sort算法调用的是合并排序。
Arrays.sort() 采用了2种排序算法 -- 基本类型数据使用快速排序法，对象数组使用归并排序。
布隆过滤器
常用于大数据的排重，比如email，url 等。 核心原理：将每条数据通过计算产生一个指纹（一个字节或多个字节，但一定比原始数据要少很多），其中每一位都是通过随机计算获得，在将指纹映射到一个大的按位存储的空间中。注意：会有一定的错误率。 优点：空间和时间效率都很高。 缺点：随着存入的元素数量增加，误算率随之增加。
基于 Redis 的 Bitmap 数据结构。
使用Java中的 BitSet 类 和 加权和hash算法。
字符串比较
KMP 算法
KMP：Knuth-Morris-Pratt算法（简称KMP） 核心原理是利用一个“部分匹配表”，跳过已经匹配过的元素。
深度优先、广度优先
贪心算法
回溯算法
剪枝算法
动态规划
朴素贝叶斯
P(B|A)=P(A|B)P(B)/P(A)
推荐算法
最小生成树算法
最短路径算法
并发
Java 并发
多线程
线程安全
一致性、事务
事务 ACID 特性
事务的隔离级别
未提交读：一个事务可以读取另一个未提交的数据，容易出现脏读的情况。
读提交：一个事务等另外一个事务提交之后才可以读取数据，但会出现不可重复读的情况（多次读取的数据不一致），读取过程中出现UPDATE操作，会多。（大多数数据库默认级别是RC，比如SQL Server，Oracle），读取的时候不可以修改。
可重复读： 同一个事务里确保每次读取的时候，获得的是同样的数据，但不保障原始数据被其他事务更新（幻读），Mysql InnoDB 就是这个级别。
序列化：所有事物串行处理（牺牲了效率）
幻读的例子非常清楚。
通过 SELECT ... FOR UPDATE 解决。
图解脏读、不可重复读、幻读问题。
MVCC
innodb 中 MVCC 用在 Repeatable-Read 隔离级别。
MVCC 会产生幻读问题（更新时异常。）
通过隐藏版本列来实现 MVCC 控制，一列记录创建时间、一列记录删除时间，这里的时间
每次只操作比当前版本小（或等于）的 行。
锁
Java中的锁和同步类
主要包括 synchronized、ReentrantLock、和 ReadWriteLock。
有数量控制
申请用 acquire，申请不要则阻塞；释放用 release。
简单的说 就是Mutex是排它的，只有一个可以获取到资源， Semaphore也具有排它性，但可以定义多个可以获取的资源的对象。
公平锁 & 非公平锁
公平锁的作用就是严格按照线程启动的顺序来执行的，不允许其他线程插队执行的；而非公平锁是允许插队的。
默认情况下 ReentrantLock 和 synchronized 都是非公平锁。ReentrantLock 可以设置成公平锁。
悲观锁
悲观锁如果使用不当（锁的条数过多），会引起服务大面积等待。推荐优先使用乐观锁+重试。
乐观锁的方式：版本号+重试方式
悲观锁：通过 select ... for update 进行行锁(不可读、不可写，share 锁可读不可写)。
mysql的innodb存储引擎实务锁虽然是锁行，但它内部是锁索引的。
锁相同数据的不同索引条件可能会引起死锁。
乐观锁 & CAS
和MySQL乐观锁方式相似，只不过是通过和原值进行比较。
ABA 问题
由于高并发，在CAS下，更新后可能此A非彼A。通过版本号可以解决，类似于上文Mysql 中提到的的乐观锁。
AtomicStampedReference 和 AtomicStampedReference。
CopyOnWrite容器
可以对CopyOnWrite容器进行并发的读，而不需要加锁。CopyOnWrite并发容器用于读多写少的并发场景。比如白名单，黑名单，商品类目的访问和更新场景，不适合需要数据强一致性的场景。
实现读写分离，读取发生在原始数据上，写入发生在副本上。
不用加锁，通过最终一致实现一致性。
RingBuffer
可重入锁 & 不可重入锁
通过简单代码举例说明可重入锁和不可重入锁。
可重入锁指同一个线程可以再次获得之前已经获得的锁。
可重入锁可以用户避免死锁。
Java中的可重入锁：synchronized 和 java.util.concurrent.locks.ReentrantLock
synchronized 使用方便，编译器来加锁，是非公平锁。
ReenTrantLock 使用灵活，锁的公平性可以定制。
相同加锁场景下，推荐使用 synchronized。
互斥锁 & 共享锁
互斥锁：同时只能有一个线程获得锁。比如，ReentrantLock 是互斥锁，ReadWriteLock 中的写锁是互斥锁。 共享锁：可以有多个线程同时或的锁。比如，Semaphore、CountDownLatch 是共享锁，ReadWriteLock 中的读锁是共享锁。
死锁
互斥、持有、不可剥夺、环形等待。
JConsole 可以识别死锁。
jstack 可以显示死锁。
操作系统
计算机原理
CPU
多级缓存
典型的 CPU 有三级缓存，距离核心越近，速度越快，空间越小。L1 一般 32k，L2 一般 256k，L3 一般12M。内存速度需要200个 CPU 周期，CPU 缓存需要1个CPU周期。
进程
TODO
线程
协程
线程的调度是由操作系统负责，协程调度是程序自行负责
与线程相比，协程减少了无谓的操作系统切换.
实际上当遇到IO操作时做切换才更有意义，（因为IO操作不用占用CPU），如果没遇到IO操作，按照时间片切换.
Linux
设计模式
设计模式的六大原则
开闭原则：对扩展开放,对修改关闭，多使用抽象类和接口。
里氏替换原则：基类可以被子类替换，使用抽象类继承,不使用具体类继承。
依赖倒转原则：要依赖于抽象,不要依赖于具体，针对接口编程,不针对实现编程。
接口隔离原则：使用多个隔离的接口,比使用单个接口好，建立最小的接口。
迪米特法则：一个软件实体应当尽可能少地与其他实体发生相互作用，通过中间类建立联系。
合成复用原则：尽量使用合成/聚合,而不是使用继承。
23种常见设计模式
应用场景
责任链模式：通过把请求从一个对象传递到链条中下一个对象的方式，直到请求被处理完毕，以实现对象间的解耦。如 javax.servlet.Filter#doFilter()。
命令模式：将操作封装到对象内，以便存储，传递和返回，如：java.lang.Runnable。
解释器模式：定义了一个语言的语法，然后解析相应语法的语句，如，java.text.Format，java.text.Normalizer。
迭代器模式：提供一个一致的方法来顺序访问集合中的对象，如 java.util.Iterator。
中介者模式：通过使用一个中间对象来进行消息分发以及减少类之间的直接依赖，java.lang.reflect.Method#invoke()。
空对象模式：如 java.util.Collections#emptyList()。
观察者模式：它使得一个对象可以灵活的将消息发送给感兴趣的对象，如 java.util.EventListener。
模板方法模式：让子类可以重写方法的一部分，而不是整个重写，如 java.util.Collections#sort()。
抽象工厂模式：抽象工厂模式提供了一个协议来生成一系列的相关或者独立的对象，而不用指定具体对象的类型，如 java.util.Calendar#getInstance()。
建造模式(Builder)：定义了一个新的类来构建另一个类的实例，以简化复杂对象的创建，如：java.lang.StringBuilder#append()。
工厂方法：就是 一个返* 回具体对象的方法，而不是多个，如 java.lang.Object#toString()、java.lang.Class#newInstance()。
原型模式：使得类的实例能够生成自身的拷贝、如：java.lang.Object#clone()。
单例模式：全局只有一个实例，如 java.lang.Runtime#getRuntime()。
适配器：用来把一个接口转化成另一个接口，如 java.util.Arrays#asList()。
桥接模式：这个模式将抽象和抽象操作的实现进行了解耦，这样使得抽象和实现可以独立地变化，如JDBC；
组合模式：使得客户端看来单个对象和对象的组合是同等的。换句话说，某个类型的方法同时也接受自身类型作为参数，如 Map.putAll，List.addAll、Set.addAll。
装饰者模式：动态的给一个对象附加额外的功能，这也是子类的一种替代方式，如 java.util.Collections#checkedList|Map|Set|SortedSet|SortedMap。
享元模式：使用缓存来加速大量小对象的访问时间，如 valueOf(int)。
代理模式：代理模式是用一个简单的对象来代替一个复杂的或者创建耗时的对象，如 java.lang.reflect.Proxy
结构型模式：
创建模式:
行为模式：
单例模式
责任链模式
TODO
MVC
模型(model)－视图(view)－控制器(controller)
IOC
正向控制：传统通过new的方式。反向控制，通过容器注入对象。
作用：用于模块解耦。
DI：Dependency Injection，即依赖注入，只关心资源使用，不关心资源来源。