java面试资料.pdf(共283页)

【核心代码】

1. 目录
1. 目录.........................................................................................................................................................1
2. JVM.......................................................................................................................................................19
2.1. 线程 ......................................................................................................................................................20
2.2. JVM 内存区域 .....................................................................................................................................21
2.2.1. 程序计数器(线程私有)................................................................................................................22
2.2.2. 虚拟机栈(线程私有)....................................................................................................................22
2.2.3. 本地方法区(线程私有)................................................................................................................23
2.2.4. 堆（Heap-线程共享）-运行时数据区 ......................................................................................23
2.2.5. 方法区/永久代（线程共享） .....................................................................................................23
2.3. JVM 运行时内存 .................................................................................................................................24
2.3.1. 新生代 ..........................................................................................................................................24
2.3.1.1. Eden 区....................................................................................................................................................24
2.3.1.2. ServivorFrom...........................................................................................................................................24
2.3.1.3. ServivorTo ..............................................................................................................................................24
2.3.1.4. MinorGC 的过程（复制->清空->互换） .......................................................................................24
1：eden、servicorFrom 复制到 ServicorTo，年龄 1...................................................................................25
2：清空 eden、servicorFrom.............................................................................................................................25
3：ServicorTo 和 ServicorFrom 互换................................................................................................................25
2.3.2. 老年代 ..........................................................................................................................................25
2.3.3. 永久代 ..........................................................................................................................................25
2.3.3.1. JAVA8 与元数据.................................................................................................................................25
2.4. 垃圾回收与算法 ..................................................................................................................................26
2.4.1. 如何确定垃圾 ..............................................................................................................................26
2.4.1.1. 引用计数法...............................................................................................................................................26
2.4.1.2. 可达性分析...............................................................................................................................................26
2.4.2. 标记清除算法（Mark-Sweep） ..............................................................................................27
2.4.3. 复制算法（copying）.................................................................................................................27
2.4.4. 标记整理算法(Mark-Compact)..................................................................................................28
2.4.5. 分代收集算法 ..............................................................................................................................29
2.4.5.1. 新生代与复制算法 ..............................................................................................................................29
2.4.5.2. 老年代与标记复制算法 ......................................................................................................................29
2.5. JAVA 四中引用类型 ...........................................................................................................................30
2.5.1. 强引用 ..........................................................................................................................................30
2.5.2. 软引用 ..........................................................................................................................................30
2.5.3. 弱引用 ..........................................................................................................................................30
2.5.4. 虚引用 ..........................................................................................................................................30
2.6. GC 分代收集算法 VS 分区收集算法................................................................................................30
2.6.1. 分代收集算法 ..............................................................................................................................30
2.6.1.1. 在新生代-复制算法.............................................................................................................................30
2.6.1.2. 在老年代-标记整理算法.....................................................................................................................30
2.6.2. 分区收集算法 ..............................................................................................................................31
2.7. GC 垃圾收集器 ...................................................................................................................................31
2.7.1. Serial 垃圾收集器（单线程、复制算法）................................................................................31
2.7.2. ParNew 垃圾收集器（Serial 多线程）...................................................................................31
2.7.3. Parallel Scavenge 收集器（多线程复制算法、高效）..........................................................32
2.7.4. Serial Old 收集器（单线程标记整理算法 ） ...........................................................................32
2.7.5. Parallel Old 收集器（多线程标记整理算法） .........................................................................33
2.7.6. CMS 收集器（多线程标记清除算法）.....................................................................................33
2.7.6.1. 初始标记..............................................................................................................................................33
13/04/2018 Page 2 of 283
2.7.6.2. 并发标记..............................................................................................................................................34
2.7.6.3. 重新标记..............................................................................................................................................34
2.7.6.4. 并发清除..............................................................................................................................................34
2.7.7. G1 收集器....................................................................................................................................34
2.8. JAVA IO/NIO.......................................................................................................................................34
2.8.1. 阻塞 IO 模型 ................................................................................................................................34
2.8.2. 非阻塞 IO 模型 ............................................................................................................................35
2.8.3. 多路复用 IO 模型 ........................................................................................................................35
2.8.4. 信号驱动 IO 模型 ........................................................................................................................36
2.8.5. 异步 IO 模型 ................................................................................................................................36
2.8.1. JAVA IO 包..................................................................................................................................36
2.8.2. JAVA NIO....................................................................................................................................37
2.8.2.1. NIO 的缓冲区 .....................................................................................................................................38
2.8.2.2. NIO 的非阻塞 .....................................................................................................................................38
2.8.3. Channel .......................................................................................................................................40
2.8.4. Buffer............................................................................................................................................40
2.8.5. Selector........................................................................................................................................40
2.9. JVM 类加载机制 .................................................................................................................................41
2.9.1.1. 加载 ..........................................................................................................................................................41
2.9.1.2. 验证 ..........................................................................................................................................................41
2.9.1.3. 准备 ..........................................................................................................................................................41
2.9.1.4. 解析 ..........................................................................................................................................................41
2.9.1.5. 符号引用..............................................................................................................................................42
2.9.1.6. 直接引用..............................................................................................................................................42
2.9.1.7. 初始化 ......................................................................................................................................................42
2.9.1.8. 类构造器<client>..............................................................................................................................42
2.9.2. 类加载器 ......................................................................................................................................42
2.9.2.1. 启动类加载器(Bootstrap ClassLoader) .........................................................................................43
2.9.2.2. 扩展类加载器(Extension ClassLoader)..........................................................................................43
2.9.2.3. 应用程序类加载器(Application ClassLoader)： ..........................................................................43
2.9.3. 双亲委派 ......................................................................................................................................43
2.9.4. OSGI（动态模型系统） ............................................................................................................44
2.9.4.1. 动态改变构造......................................................................................................................................44
2.9.4.2. 模块化编程与热插拔 ..........................................................................................................................44
3. JAVA 集合............................................................................................................................................45
3.1. 接口继承关系和实现 ..........................................................................................................................45
3.2. LIST.......................................................................................................................................................47
3.2.1. ArrayList（数组）.......................................................................................................................47
3.2.2. Vector（数组实现、线程同步）...............................................................................................47
3.2.3. LinkList（链表）.........................................................................................................................47
3.3. SET .......................................................................................................................................................48
3.3.1.1. HashSet（Hash 表）.............................................................................................................................48
3.3.1.2. TreeSet（二叉树） ................................................................................................................................49
3.3.1.3. LinkHashSet（HashSet LinkedHashMap）...................................................................................49
3.4. MAP.......................................................................................................................................................50
3.4.1. HashMap（数组 链表 红黑树）.............................................................................................50
3.4.1.1. JAVA7 实现 .............................................................................................................................................50
3.4.1.2. JAVA8 实现 .............................................................................................................................................51
3.4.2. ConcurrentHashMap..................................................................................................................51
3.4.2.1. Segment 段..............................................................................................................................................51
3.4.2.2. 线程安全（Segment 继承 ReentrantLock 加锁）..............................................................................51
3.4.2.3. 并行度（默认 16） .................................................................................................................................52
3.4.2.4. Java8 实现 （引入了红黑树） ..............................................................................................................52
13/04/2018 Page 3 of 283
3.4.3. HashTable（线程安全） ...........................................................................................................53
3.4.4. TreeMap（可排序） ..................................................................................................................53
3.4.5. LinkHashMap（记录插入顺序）..............................................................................................53
4. JAVA 多线程并发.................................................................................................................................54
4.1.1. JAVA 并发知识库 .......................................................................................................................54
4.1.2. JAVA 线程实现/创建方式 ..........................................................................................................54
4.1.2.1. 继承 Thread 类........................................................................................................................................54
4.1.2.2. 实现 Runnable 接口。............................................................................................................................54
4.1.2.3. ExecutorService、Callable<Class>、Future 有返回值线程.............................................................55
4.1.2.4. 基于线程池的方式...................................................................................................................................56
4.1.3. 4 种线程池 ...................................................................................................................................56
4.1.3.1. newCachedThreadPool.........................................................................................................................57
4.1.3.2. newFixedThreadPool.............................................................................................................................57
4.1.3.3. newScheduledThreadPool....................................................................................................................58
4.1.3.4. newSingleThreadExecutor .................................................................................................................58
4.1.4. 线程生命周期(状态)....................................................................................................................58
4.1.4.1. 新建状态（NEW） .................................................................................................................................58
4.1.4.2. 就绪状态（RUNNABLE）：.................................................................................................................59
4.1.4.3. 运行状态（RUNNING）： ....................................................................................................................59
4.1.4.4. 阻塞状态（BLOCKED）：....................................................................................................................59
等待阻塞（o.wait->等待对列）：......................................................................................................................59
同步阻塞(lock->锁池) ..........................................................................................................................................59
其他阻塞(sleep/join) ............................................................................................................................................59
4.1.4.5. 线程死亡（DEAD）................................................................................................................................59
正常结束................................................................................................................................................................59
异常结束................................................................................................................................................................59
调用 stop...............................................................................................................................................................59
4.1.5. 终止线程 4 种方式 ......................................................................................................................60
4.1.5.1. 正常运行结束...........................................................................................................................................60
4.1.5.2. 使用退出标志退出线程...........................................................................................................................60
4.1.5.3. Interrupt 方法结束线程...........................................................................................................................60
4.1.5.4. stop 方法终止线程（线程不安全）.......................................................................................................61
4.1.6. sleep 与 wait 区别.......................................................................................................................61
4.1.7. start 与 run 区别..........................................................................................................................62
4.1.8. JAVA 后台线程 ...........................................................................................................................62
4.1.9. JAVA 锁 .......................................................................................................................................63
4.1.9.1. 乐观锁 ......................................................................................................................................................63
4.1.9.2. 悲观锁 ......................................................................................................................................................63
4.1.9.3. 自旋锁 ......................................................................................................................................................63
自旋锁的优缺点....................................................................................................................................................63
自旋锁时间阈值（1.6 引入了适应性自旋锁）..................................................................................................63
自旋锁的开启........................................................................................................................................................64
4.1.9.4. Synchronized 同步锁..............................................................................................................................64
Synchronized 作用范围.......................................................................................................................................64
Synchronized 核心组件.......................................................................................................................................64
Synchronized 实现...............................................................................................................................................64
4.1.9.5. ReentrantLock.........................................................................................................................................66
Lock 接口的主要方法...........................................................................................................................................66
非公平锁................................................................................................................................................................66
公平锁....................................................................................................................................................................67
ReentrantLock 与 synchronized ........................................................................................................................67
ReentrantLock 实现.............................................................................................................................................67
Condition 类和 Object 类锁方法区别区别.........................................................................................................68
tryLock 和 lock 和 lockInterruptibly 的区别........................................................................................................68
4.1.9.6. Semaphore 信号量.................................................................................................................................68
实现互斥锁（计数器为 1）.................................................................................................................................68
代码实现................................................................................................................................................................68
Semaphore 与 ReentrantLock ...........................................................................................................................69
4.1.9.7. AtomicInteger..........................................................................................................................................69
13/04/2018 Page 4 of 283
4.1.9.8. 可重入锁（递归锁）...............................................................................................................................69
4.1.9.9. 公平锁与非公平锁...................................................................................................................................70
公平锁（Fair）.....................................................................................................................................................70
非公平锁（Nonfair）...........................................................................................................................................70
4.1.9.10. ReadWriteLock 读写锁......................................................................................................................70
读锁........................................................................................................................................................................70
写锁........................................................................................................................................................................70
4.1.9.11. 共享锁和独占锁 ..................................................................................................................................70
独占锁....................................................................................................................................................................70
共享锁....................................................................................................................................................................70
4.1.9.12. 重量级锁（Mutex Lock） ................................................................................................................71
4.1.9.13. 轻量级锁..............................................................................................................................................71
锁升级....................................................................................................................................................................71
4.1.9.14. 偏向锁..................................................................................................................................................71
4.1.9.15. 分段锁..................................................................................................................................................71
4.1.9.16. 锁优化..................................................................................................................................................71
减少锁持有时间....................................................................................................................................................72
减小锁粒度............................................................................................................................................................72
锁分离....................................................................................................................................................................72
锁粗化....................................................................................................................................................................72
锁消除....................................................................................................................................................................72
4.1.10. 线程基本方法 ..............................................................................................................................72
4.1.10.1. 线程等待（wait）...............................................................................................................................73
4.1.10.2. 线程睡眠（sleep）.............................................................................................................................73
4.1.10.3. 线程让步（yield）..............................................................................................................................73
4.1.10.4. 线程中断（interrupt）........................................................................................................................73
4.1.10.5. Join 等待其他线程终止......................................................................................................................74
4.1.10.6. 为什么要用 join()方法？ ....................................................................................................................74
4.1.10.7. 线程唤醒（notify）.............................................................................................................................74
4.1.10.8. 其他方法：..........................................................................................................................................74
4.1.11. 线程上下文切换 ..........................................................................................................................75
4.1.11.1. 进程......................................................................................................................................................75
4.1.11.2. 上下文..................................................................................................................................................75
4.1.11.3. 寄存器..................................................................................................................................................75
4.1.11.4. 程序计数器..........................................................................................................................................75
4.1.11.5. PCB-“切换桢”.................................................................................................................................75
4.1.11.6. 上下文切换的活动： ..........................................................................................................................76
4.1.11.7. 引起线程上下文切换的原因 ..............................................................................................................76
4.1.12. 同步锁与死锁 ..............................................................................................................................76
4.1.12.1. 同步锁..................................................................................................................................................76
4.1.12.2. 死锁......................................................................................................................................................76
4.1.13. 线程池原理 ..................................................................................................................................76
4.1.13.1. 线程复用..............................................................................................................................................76
4.1.13.2. 线程池的组成......................................................................................................................................76
4.1.13.3. 拒绝策略..............................................................................................................................................78
4.1.13.4. Java 线程池工作过程 .........................................................................................................................78
4.1.14. JAVA 阻塞队列原理....................................................................................................................79
4.1.14.1. 阻塞队列的主要方法 ..........................................................................................................................80
插入操作：............................................................................................................................................................80
获取数据操作：....................................................................................................................................................81
4.1.14.2. Java 中的阻塞队列 .............................................................................................................................81
4.1.14.3. ArrayBlockingQueue（公平、非公平） .......................................................................................82
4.1.14.4. LinkedBlockingQueue（两个独立锁提高并发） .........................................................................82
4.1.14.5. PriorityBlockingQueue（compareTo 排序实现优先）..............................................................82
4.1.14.6. DelayQueue（缓存失效、定时任务 ）..........................................................................................82
4.1.14.7. SynchronousQueue（不存储数据、可用于传递数据）..............................................................83
4.1.14.8. LinkedTransferQueue......................................................................................................................83
13/04/2018 Page 5 of 283
4.1.14.9. LinkedBlockingDeque.....................................................................................................................83
4.1.15. CyclicBarrier、CountDownLatch、Semaphore 的用法........................................................84
4.1.15.1. CountDownLatch（线程计数器 ） ................................................................................................84
4.1.15.2. CyclicBarrier（回环栅栏-等待至 barrier 状态再全部同时执行） ...............................................84
4.1.15.3. Semaphore（信号量-控制同时访问的线程个数） .......................................................................85
4.1.16. volatile 关键字的作用（变量可见性、禁止重排序） .............................................................87
变量可见性............................................................................................................................................................87
禁止重排序............................................................................................................................................................87
比 sychronized 更轻量级的同步锁.....................................................................................................................87
适用场景................................................................................................................................................................87
4.1.17. 如何在两个线程之间共享数据...................................................................................................88
将数据抽象成一个类，并将数据的操作作为这个类的方法.............................................................................88
Runnable 对象作为一个类的内部类 ..................................................................................................................89
4.1.18. ThreadLocal 作用（线程本地存储）........................................................................................90
ThreadLocalMap（线程的一个属性） ..............................................................................................................90
使用场景................................................................................................................................................................91
4.1.19. synchronized 和 ReentrantLock 的区别 ..................................................................................91
4.1.19.1. 两者的共同点： ..................................................................................................................................91
4.1.19.2. 两者的不同点： ..................................................................................................................................92
4.1.20. ConcurrentHashMap 并发.........................................................................................................92
4.1.20.1. 减小锁粒度..........................................................................................................................................92
4.1.20.2. ConcurrentHashMap 分段锁..........................................................................................................92
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成.................................................93
4.1.21. Java 中用到的线程调度 .............................................................................................................93
4.1.21.1. 抢占式调度：......................................................................................................................................93
4.1.21.2. 协同式调度：......................................................................................................................................93
4.1.21.3. JVM 的线程调度实现（抢占式调度） .............................................................................................94
4.1.21.4. 线程让出 cpu 的情况： .....................................................................................................................94
4.1.22. 进程调度算法 ..............................................................................................................................94
4.1.22.1. 优先调度算法......................................................................................................................................94
4.1.22.2. 高优先权优先调度算法 ......................................................................................................................95
4.1.22.3. 基于时间片的轮转调度算法 ..............................................................................................................96
4.1.23. 什么是 CAS（比较并交换-乐观锁机制-锁自旋） ..................................................................96
4.1.23.1. 概念及特性..........................................................................................................................................96
4.1.23.2. 原子包 java.util.concurrent.atomic（锁自旋） ...........................................................................97
4.1.23.3. ABA 问题.............................................................................................................................................98
4.1.24. 什么是 AQS（抽象的队列同步器）.........................................................................................98
Exclusive 独占资源-ReentrantLock ...................................................................................................................99
Share 共享资源-Semaphore/CountDownLatch ...............................................................................................99
同步器的实现是 ABS 核心（state 资源状态计数）.......................................................................................100
ReentrantReadWriteLock 实现独占和共享两种方式.....................................................................................100
5. JAVA 基础..........................................................................................................................................101
5.1.1. JAVA 异常分类及处理..............................................................................................................101
5.1.1.1. 概念....................................................................................................................................................101
5.1.1.2. 异常分类............................................................................................................................................101
Error.....................................................................................................................................................................101
Exception（RuntimeException、CheckedException） ...........................................................................101
5.1.1.3. 异常的处理方式 ................................................................................................................................102
遇到问题不进行具体处理，而是继续抛给调用者 （throw,throws）.........................................................102
try catch 捕获异常针对性处理方式..................................................................................................................102
5.1.1.4. Throw 和 throws 的区别： ............................................................................................................102
13/04/2018 Page 6 of 283
位置不同..............................................................................................................................................................102
功能不同：..........................................................................................................................................................102
5.1.2. JAVA 反射 .................................................................................................................................103
5.1.2.1. 动态语言............................................................................................................................................103
5.1.2.2. 反射机制概念 （运行状态中知道类所有的属性和方法）............................................................103
5.1.2.3. 反射的应用场合 ................................................................................................................................103
编译时类型和运行时类型..................................................................................................................................103
的编译时类型无法获取具体方法......................................................................................................................104
5.1.2.4. Java 反射 API....................................................................................................................................104
反射 API 用来生成 JVM 中的类、接口或则对象的信息。 ............................................................................104
5.1.2.5. 反射使用步骤（获取 Class 对象、调用对象方法） .....................................................................104
5.1.2.6. 获取 Class 对象的 3 种方法 ............................................................................................................104
调用某个对象的 getClass()方法.......................................................................................................................104
调用某个类的 class 属性来获取该类对应的 Class 对象................................................................................104
使用 Class 类中的 forName()静态方法(最安全/性能最好)............................................................................104
5.1.2.7. 创建对象的两种方法 ........................................................................................................................105
Class 对象的 newInstance().............................................................................................................................105
调用 Constructor 对象的 newInstance()..........................................................................................................105
5.1.3. JAVA 注解 .................................................................................................................................106
5.1.3.1. 概念 ........................................................................................................................................................106
5.1.3.2. 4 种标准元注解......................................................................................................................................106
@Target 修饰的对象范围 .................................................................................................................................106
@Retention 定义 被保留的时间长短...............................................................................................................106
@Documented ᧿述-javadoc................................................................................................................................106
@Inherited 阐述了某个被标注的类型是被继承的 ..............................................................................................106
5.1.3.3. 注解处理器.............................................................................................................................................107
5.1.4. JAVA 内部类 .............................................................................................................................109
5.1.4.1. 静态内部类.............................................................................................................................................109
5.1.4.2. 成员内部类.............................................................................................................................................110
5.1.4.3. 局部内部类（定义在方法中的类）.....................................................................................................110
5.1.4.4. 匿名内部类（要继承一个父类或者实现一个接口、直接使用 new 来生成一个对象的引用）.....111
5.1.5. JAVA 泛型 .................................................................................................................................112
5.1.5.1. 泛型方法（<E>）.............................................................................................................................112
5.1.5.2. 泛型类<T> .............................................................................................................................................112
5.1.5.3. 类型通配符? ..........................................................................................................................................113
5.1.5.4. 类型擦除 ................................................................................................................................................113
5.1.6. JAVA 序列化(创建可复用的 Java 对象).................................................................................113
保存(持久化)对象及其状态到内存或者磁盘....................................................................................................113
序列化对象以字节数组保持-静态成员不保存.................................................................................................113
序列化用户远程对象传输..................................................................................................................................113
Serializable 实现序列化 ....................................................................................................................................113
ObjectOutputStream 和 ObjectInputStream 对对象进行序列化及反序列化...............................................113
writeObject 和 readObject 自定义序列化策略................................................................................................113
序列化 ID.............................................................................................................................................................113
序列化并不保存静态变量..................................................................................................................................114
序列化子父类说明..............................................................................................................................................114
Transient 关键字阻止该变量被序列化到文件中............................................................................................114
5.1.7. JAVA 复制 .................................................................................................................................114
5.1.7.1. 直接赋值复制.........................................................................................................................................114
5.1.7.2. 浅复制（复制引用但不复制引用的对象）.....................................................................................114
5.1.7.3. 深复制（复制对象和其应用对象）.................................................................................................115
5.1.7.4. 序列化（深 clone 一中实现）........................................................................................................115
6. SPRING 原理 .....................................................................................................................................116
6.1.1. Spring 特点................................................................................................................................116
6.1.1.1. 轻量级................................................................................................................................................116
13/04/2018 Page 7 of 283
6.1.1.2. 控制反转............................................................................................................................................116
6.1.1.3. 面向切面............................................................................................................................................116
6.1.1.4. 容器....................................................................................................................................................116
6.1.1.5. 框架集合............................................................................................................................................116
6.1.2. Spring 核心组件........................................................................................................................117
6.1.3. Spring 常用模块........................................................................................................................117
6.1.4. Spring 主要包............................................................................................................................118
6.1.5. Spring 常用注解........................................................................................................................118
6.1.6. Spring 第三方结合....................................................................................................................119
6.1.7. Spring IOC 原理........................................................................................................................120
6.1.7.1. 概念 ........................................................................................................................................................120
6.1.7.2. Spring 容器高层视图 ............................................................................................................................120
6.1.7.3. IOC 容器实现.........................................................................................................................................120
BeanFactory-框架基础设施..............................................................................................................................120
1.1..1.1.1 BeanDefinitionRegistry 注册表.................................................................................................121
1.1..1.1.2 BeanFactory 顶层接口..............................................................................................................121
1.1..1.1.3 ListableBeanFactory .................................................................................................................121
1.1..1.1.4 HierarchicalBeanFactory 父子级联..........................................................................................121
1.1..1.1.5 ConfigurableBeanFactory.........................................................................................................121
1.1..1.1.6 AutowireCapableBeanFactory 自动装配 ................................................................................122
1.1..1.1.7 SingletonBeanRegistry 运行期间注册单例 Bean...................................................................122
1.1..1.1.8 依赖日志框框.............................................................................................................................122
ApplicationContext 面向开发应用....................................................................................................................122
WebApplication 体系架构 .................................................................................................................................123
6.1.7.4. Spring Bean 作用域..............................................................................................................................123
singleton：单例模式（多线程下不安全） ......................................................................................................123
prototype:原型模式每次使用时创建 ................................................................................................................124
Request：一次 request 一个实例....................................................................................................................124
session................................................................................................................................................................124
global Session....................................................................................................................................................124
6.1.7.5. Spring Bean 生命周期..........................................................................................................................124
实例化..................................................................................................................................................................124
IOC 依赖注入......................................................................................................................................................124
setBeanName 实现............................................................................................................................................124
BeanFactoryAware 实现...................................................................................................................................124
ApplicationContextAware 实现.........................................................................................................................125
postProcessBeforeInitialization 接口实现-初始化预处理..........................................................................125
init-method..........................................................................................................................................................125
postProcessAfterInitialization...........................................................................................................................125
Destroy 过期自动清理阶段 ...............................................................................................................................125
destroy-method 自配置清理 .............................................................................................................................125
6.1.7.6. Spring 依赖注入四种方式....................................................................................................................126
构造器注入..........................................................................................................................................................126
setter 方法注入...................................................................................................................................................127
静态工厂注入......................................................................................................................................................127
实例工厂..............................................................................................................................................................127
6.1.7.7. 5 种不同方式的自动装配......................................................................................................................128
6.1.8. Spring APO 原理 ......................................................................................................................129
6.1.8.1. 概念 ........................................................................................................................................................129
6.1.8.2. AOP 核心概念 .......................................................................................................................................129
6.1.8.1. AOP 两种代理方式 ...............................................................................................................................130
JDK 动态接口代理 .............................................................................................................................................130
CGLib 动态代理..................................................................................................................................................131
6.1.8.2. 实现原理 ................................................................................................................................................131
6.1.9. Spring MVC 原理......................................................................................................................132
6.1.9.1. MVC 流程...............................................................................................................................................132
Http 请求到 DispatcherServlet .......................................................................................................................133
HandlerMapping 寻找处理器............................................................................................................................133
调用处理器 Controller........................................................................................................................................133
13/04/2018 Page 8 of 283
Controller 调用业务逻辑处理后，返回 ModelAndView.................................................................................133
DispatcherServlet 查询 ModelAndView ..........................................................................................................133
ModelAndView 反馈浏览器 HTTP ...................................................................................................................133
6.1.9.1. MVC 常用注解.......................................................................................................................................133
6.1.10. Spring Boot 原理.......................................................................................................................134
1. 创建独立的 Spring 应用程序.............................................................................................................................134
2. 嵌入的 Tomcat，无需部署 WAR 文件.............................................................................................................134
3. 简化 Maven 配置................................................................................................................................................134
4. 自动配置 Spring .................................................................................................................................................134
5. ᨀ供生产就绪型功能，如指标，健康检查和外部配置...................................................................................134
6. 绝对没有代码生成和对 XML 没有要求配置 [1]...............................................................................................134
6.1.11. JPA 原理....................................................................................................................................134
6.1.11.1. 事务....................................................................................................................................................134
6.1.11.2. 本地事务............................................................................................................................................134
6.1.11.1. 分布式事务........................................................................................................................................135
6.1.11.1. 两阶段ᨀ交........................................................................................................................................136
1 准备阶段...........................................................................................................................................................136
2 ᨀ交阶段：.......................................................................................................................................................136
6.1.12. Mybatis 缓存..............................................................................................................................137
6.1.12.1. Mybatis 的一级缓存原理（sqlsession 级别）..............................................................................138
6.1.12.2. 二级缓存原理（mapper 基本）.....................................................................................................138
具体使用需要配置：..........................................................................................................................................139
6.1.13. Tomcat 架构..............................................................................................................................139
7. 微服务 .................................................................................................................................................140
7.1.1. 服务注册发现 ............................................................................................................................140
7.1.1.1. 客户端注册（zookeeper）..................................................................................................................140
7.1.1.2. 第三方注册（独立的服务 Registrar）...............................................................................................140
7.1.1.3. 客户端发现.............................................................................................................................................141
7.1.1.4. 服务端发现.............................................................................................................................................142
7.1.1.5. Consul....................................................................................................................................................142
7.1.1.6. Eureka....................................................................................................................................................142
7.1.1.7. SmartStack............................................................................................................................................142
7.1.1.8. Etcd ........................................................................................................................................................142
7.1.2. API 网关.....................................................................................................................................142
7.1.2.1. 请求转发 ................................................................................................................................................143
7.1.2.2. 响应合并 ................................................................................................................................................143
7.1.2.3. 协议转换 ................................................................................................................................................143
7.1.2.4. 数据转换 ................................................................................................................................................143
7.1.2.5. 安全认证 ................................................................................................................................................144
7.1.3. 配置中心 ....................................................................................................................................144
7.1.3.1. zookeeper 配置中心.............................................................................................................................144
7.1.3.2. 配置中心数据分类.................................................................................................................................144
7.1.4. 事件调度（kafka）...................................................................................................................144
7.1.5. 服务跟踪（starter-sleuth）...................................................................................................144
7.1.6. 服务熔断（Hystrix） ................................................................................................................145
7.1.6.1. Hystrix 断路器机制................................................................................................................................146
7.1.7. API 管理.....................................................................................................................................146
8. NETTY 与 RPC ..................................................................................................................................147
8.1.1. Netty 原理..................................................................................................................................147
8.1.2. Netty 高性能..............................................................................................................................147
8.1.2.1. 多路复用通讯方式 ............................................................................................................................147
8.1.2.1. 异步通讯 NIO....................................................................................................................................148
8.1.2.2. 零拷贝（DIRECT BUFFERS 使用堆外直接内存）..........................................................................149
8.1.2.3. 内存池（基于内存池的缓冲区重用机制） .........................................................................................149
8.1.2.4. 高效的 Reactor 线程模型.....................................................................................................................149
Reactor 单线程模型...........................................................................................................................................149
Reactor 多线程模型...........................................................................................................................................150
13/04/2018 Page 9 of 283
主从 Reactor 多线程模型..................................................................................................................................150
8.1.2.5. 无锁设计、线程绑定.............................................................................................................................151
8.1.2.6. 高性能的序列化框架.............................................................................................................................151
小包封大包，防止网络阻塞..............................................................................................................................152
软中断 Hash 值和 CPU 绑定.............................................................................................................................152
8.1.3. Netty RPC 实现.........................................................................................................................152
8.1.3.1. 概念 ........................................................................................................................................................152
8.1.3.2. 关键技术 ................................................................................................................................................152
8.1.3.3. 核心流程 ................................................................................................................................................152
8.1.3.1. 消息编解码.............................................................................................................................................153
息数据结构（接口名称 方法名 参数类型和参数值 超时时间  requestID） ...........................................153
序列化..................................................................................................................................................................154
8.1.3.1. 通讯过程 ................................................................................................................................................154
核心问题(线程暂停、消息乱序) .......................................................................................................................154
通讯流程..............................................................................................................................................................154
requestID 生成-AtomicLong .............................................................................................................................154
存放回调对象 callback 到全局 ConcurrentHashMap ....................................................................................154
synchronized 获取回调对象 callback 的锁并自旋 wait..................................................................................154
监听消息的线程收到消息，找到 callback 上的锁并唤醒 ..............................................................................155
8.1.4. RMI 实现方式............................................................................................................................155
8.1.4.1. 实现步骤 ................................................................................................................................................155
8.1.5. Protoclol Buffer.........................................................................................................................156
8.1.5.1. 特点 ........................................................................................................................................................157
8.1.6. Thrift ...........................................................................................................................................157
9. 网络.....................................................................................................................................................159
9.1.1. 网络 7 层架构 ............................................................................................................................159
9.1.2. TCP/IP 原理...............................................................................................................................160
9.1.2.1. 网络访问层(Network Access Layer)...................................................................................................160
9.1.2.2. 网络层(Internet Layer) .........................................................................................................................160
9.1.2.3. 传输层(Tramsport Layer-TCP/UDP) ..................................................................................................160
9.1.2.4. 应用层(Application Layer)....................................................................................................................160
9.1.3. TCP 三次握手/四次挥手 ..........................................................................................................161
9.1.3.1. 数据包说明.............................................................................................................................................161
9.1.3.2. 三次握手 ................................................................................................................................................162
9.1.3.3. 四次挥手 ................................................................................................................................................163
9.1.4. HTTP 原理.................................................................................................................................164
9.1.4.1. 传输流程 ................................................................................................................................................164
1：地址解析 .......................................................................................................................................................164
2：封装 HTTP 请求数据包 ...............................................................................................................................165
3：封装成 TCP 包并建立连接..........................................................................................................................165
4：客户机发送请求命........................................................................................................................................165
5：服务器响应....................................................................................................................................................165
6：服务器关闭 TCP 连接..................................................................................................................................165
9.1.4.2. HTTP 状态 .............................................................................................................................................165
9.1.4.3. HTTPS ...................................................................................................................................................166
建立连接获取证书..............................................................................................................................................167
证书验证..............................................................................................................................................................167
数据加密和传输..................................................................................................................................................167
9.1.5. CDN 原理...................................................................................................................................167
9.1.5.1. 分发服务系统.........................................................................................................................................167
9.1.5.2. 负载均衡系统：.....................................................................................................................................168
9.1.5.3. 管理系统：.............................................................................................................................................168
10. 日志 .................................................................................................................................................169
10.1.1. Slf4j ............................................................................................................................................169
10.1.2. Log4j ..........................................................................................................................................169
10.1.3. LogBack.....................................................................................................................................169
10.1.3.1. Logback 优点...................................................................................................................................169
10.1.4. ELK.............................................................................................................................................170
13/04/2018 Page 10 of 283
11. ZOOKEEPER .................................................................................................................................171
11.1.1. Zookeeper 概念 ........................................................................................................................171
11.1.1. Zookeeper 角色 ........................................................................................................................171
11.1.1.1. Leader...............................................................................................................................................171
11.1.1.2. Follower............................................................................................................................................171
11.1.1.3. Observer...........................................................................................................................................171
11.1.1.1. ZAB 协议 ...........................................................................................................................................172
事务编号 Zxid（事务请求计数器  epoch） ...................................................................................................172
epoch...................................................................................................................................................................172
Zab 协议有两种模式-恢复模式（选主）、广播模式（同步）......................................................................172
ZAB 协议 4 阶段.................................................................................................................................................172
Leader election（选举阶段-选出准 Leader） ................................................................................................172
Discovery（发现阶段-接受ᨀ议、生成 epoch、接受 epoch）....................................................................173
Synchronization（同步阶段-同步 follower 副本）.........................................................................................173
Broadcast（广播阶段-leader 消息广播）.......................................................................................................173
ZAB 协议 JAVA 实现（FLE-发现阶段和同步合并为 Recovery Phase（恢复阶段））............................173
11.1.1.2. 投票机制............................................................................................................................................173
11.1.2. Zookeeper 工作原理（原子广播）.........................................................................................174
11.1.3. Znode 有四种形式的目录节点 ................................................................................................174
12. KAFKA............................................................................................................................................175
12.1.1. Kafka 概念 .................................................................................................................................175
12.1.2. Kafka 数据存储设计 .................................................................................................................175
12.1.2.1. partition 的数据文件（offset，MessageSize，data）............................................................175
12.1.2.2. 数据文件分段 segment（顺序读写、分段命令、二分查找）....................................................176
12.1.2.3. 数据文件索引（分段索引、稀疏存储）.........................................................................................176
12.1.3. 生产者设计 ................................................................................................................................176
12.1.3.1. 负载均衡（partition 会均衡分布到不同 broker 上）.................................................................176
12.1.3.2. 批量发送............................................................................................................................................177
12.1.3.3. 压缩（GZIP 或 Snappy）...............................................................................................................177
12.1.1. 消费者设计 ................................................................................................................................177
12.1.1.1. Consumer Group ...........................................................................................................................178
13. RABBITMQ ....................................................................................................................................179
13.1.1. 概念 ............................................................................................................................................179
13.1.2. RabbitMQ 架构 .........................................................................................................................179
13.1.2.1. Message ...........................................................................................................................................180
13.1.2.2. Publisher ..........................................................................................................................................180
13.1.2.3. Exchange（将消息路由给队列 ） .................................................................................................180
13.1.2.4. Binding（消息队列和交换器之间的关联）..................................................................................180
13.1.2.5. Queue ...............................................................................................................................................180
13.1.2.6. Connection......................................................................................................................................180
13.1.2.7. Channel ............................................................................................................................................180
13.1.2.8. Consumer.........................................................................................................................................180
13.1.2.9. Virtual Host .....................................................................................................................................180
13.1.2.10. Broker...............................................................................................................................................181
13.1.3. Exchange 类型 .........................................................................................................................181
13.1.3.1. Direct 键（routing key）分布： ..................................................................................................181
13.1.3.2. Fanout（广播分发）.......................................................................................................................181
13.1.3.3. topic 交换器（模式匹配） ...................................................................................................182
13/04/2018 Page 11 of 283
14. HBASE............................................................................................................................................183
14.1.1. 概念 ............................................................................................................................................183
14.1.2. 列式存储 ....................................................................................................................................183
14.1.3. Hbase 核心概念........................................................................................................................184
14.1.3.1. Column Family 列族.......................................................................................................................184
14.1.3.2. Rowkey（Rowkey 查询，Rowkey 范围扫描，全表扫描）.......................................................184
14.1.3.3. Region 分区......................................................................................................................................184
14.1.3.4. TimeStamp 多版本..........................................................................................................................184
14.1.4. Hbase 核心架构........................................................................................................................184
14.1.4.1. Client：.............................................................................................................................................185
14.1.4.2. Zookeeper：....................................................................................................................................185
14.1.4.3. Hmaster............................................................................................................................................185
14.1.4.4. HregionServer.................................................................................................................................185
14.1.4.5. Region 寻址方式（通过 zookeeper .META）............................................................................186
14.1.4.6. HDFS .................................................................................................................................................186
14.1.5. Hbase 的写逻辑........................................................................................................................187
14.1.5.1. Hbase 的写入流程 ...........................................................................................................................187
获取 RegionServer ............................................................................................................................................187
请求写 Hlog ........................................................................................................................................................187
请求写 MemStore ..............................................................................................................................................187
14.1.5.2. MemStore 刷盘...............................................................................................................................187
全局内存控制......................................................................................................................................................188
MemStore 达到上限...........................................................................................................................................188
RegionServer 的 Hlog 数量达到上限...............................................................................................................188
手工触发..............................................................................................................................................................188
关闭 RegionServer 触发....................................................................................................................................188
Region 使用 HLOG 恢复完数据后触发............................................................................................................188
14.1.6. HBase vs Cassandra...............................................................................................................188
15. MONGODB.....................................................................................................................................190
15.1.1. 概念 ............................................................................................................................................190
15.1.2. 特点 ............................................................................................................................................190
16. CASSANDRA.................................................................................................................................192
16.1.1. 概念 ............................................................................................................................................192
16.1.2. 数据模型 ....................................................................................................................................192
Key Space（对应 SQL 数据库中的 database）................................................................................................192
Key（对应 SQL 数据库中的主键）......................................................................................................................192
column（对应 SQL 数据库中的列）....................................................................................................................192
super column（SQL 数据库不支持）..................................................................................................................192
Standard Column Family（相对应 SQL 数据库中的 table）............................................................................192
Super Column Family（SQL 数据库不支持） ...................................................................................................192
16.1.3. Cassandra 一致 Hash 和虚拟节点 .........................................................................................192
一致性 Hash（多米诺 down 机）.........................................................................................................................192
虚拟节点（down 机多节点托管）........................................................................................................................193
16.1.4. Gossip 协议...............................................................................................................................193
Gossip 节点的通信方式及收敛性 .........................................................................................................................194
Gossip 两个节点（A、B）之间存在三种通信方式（push、pull、push&pull）........................................194
gossip 的协议和 seed list（防止集群分列） ..................................................................................................194
16.1.5. 数据复制 ....................................................................................................................................194
Partitioners（计算 primary key token 的 hash 函数）.......................................................................................194
两种可用的复制策略： ..........................................................................................................................................194
SimpleStrategy：仅用于单数据中心，...........................................................................................................194
将第一个 replica 放在由 partitioner 确定的节点中，其余的 replicas 放在上述节点顺时针方向的后续节
点中。..................................................................................................................................................................194
13/04/2018 Page 12 of 283
NetworkTopologyStrategy：可用于较复杂的多数据中心。.........................................................................194
可以指定在每个数据中心分别存储多少份 replicas。...................................................................................194
16.1.6. 数据写请求和协调者 ................................................................................................................195
协调者(coordinator)................................................................................................................................................195
16.1.7. 数据读请求和后台修复 ............................................................................................................195
16.1.8. 数据存储（CommitLog、MemTable、SSTable）...........................................................196
SSTable 文件构成（BloomFilter、index、data、static）................................................................................196
16.1.9. 二级索引（对要索引的 value 摘要，生成 RowKey）..........................................................196
16.1.10. 数据读写 ................................................................................................................................197
数据写入和更新（数据追加） ..............................................................................................................................197
数据的写和删除效率极高..................................................................................................................................197
错误恢复简单......................................................................................................................................................197
读的复杂度高......................................................................................................................................................197
数据删除（column 的墓碑） ................................................................................................................................197
墓碑......................................................................................................................................................................198
垃圾回收 compaction ........................................................................................................................................198
数据读取（memtable SStables）................................................................................................................198
行缓存和键缓存请求流程图 ..................................................................................................................................199
Row Cache（SSTables 中频繁被访问的数据）............................................................................................199
Bloom Filter（查找数据可能对应的 SSTable）.............................................................................................200
Partition Key Cache（查找数据可能对应的 Partition key） ........................................................................200
Partition Summary（内存中存储一些 partition index 的样本）...................................................................200
Partition Index（磁盘中） ................................................................................................................................200
Compression offset map（磁盘中）...............................................................................................................200
17. 设计模式..........................................................................................................................................201
17.1.1. 设计原则 ....................................................................................................................................201
17.1.2. 工厂方法模式 ............................................................................................................................201
17.1.3. 抽象工厂模式 ............................................................................................................................201
17.1.4. 单例模式 ....................................................................................................................................201
17.1.5. 建造者模式 ................................................................................................................................201
17.1.6. 原型模式 ....................................................................................................................................201
17.1.7. 适配器模式 ................................................................................................................................201
17.1.8. 装饰器模式 ................................................................................................................................201
17.1.9. 代理模式 ....................................................................................................................................201
17.1.10. 外观模式 ................................................................................................................................201
17.1.11. 桥接模式 ................................................................................................................................201
17.1.12. 组合模式 ................................................................................................................................201
17.1.13. 享元模式 ................................................................................................................................201
17.1.14. 策略模式 ................................................................................................................................201
17.1.15. 模板方法模式 ........................................................................................................................201
17.1.16. 观察者模式 ............................................................................................................................201
17.1.17. 迭代子模式 ............................................................................................................................201
17.1.18. 责任链模式 ............................................................................................................................201
17.1.19. 命令模式 ................................................................................................................................201
17.1.20. 备忘录模式 ............................................................................................................................201
17.1.21. 状态模式 ................................................................................................................................202
17.1.22. 访问者模式 ............................................................................................................................202
17.1.23. 中介者模式 ............................................................................................................................202
17.1.24. 解释器模式 ............................................................................................................................202
18. 负载均衡..........................................................................................................................................203
18.1.1. 四层负载均衡 vs 七层负载均衡 ..............................................................................................203
18.1.1.1. 四层负载均衡（目标地址和端口交换）.........................................................................................203
F5：硬件负载均衡器，功能很好，但是成本很高。......................................................................................203
lvs：重量级的四层负载软件。 .........................................................................................................................203
nginx：轻量级的四层负载软件，带缓存功能，正则表达式较灵活。 .........................................................203
13/04/2018 Page 13 of 283
haproxy：模拟四层转发，较灵活。................................................................................................................203
18.1.1.2. 七层负载均衡（内容交换） ............................................................................................................203
haproxy：天生负载均衡技能，全面支持七层代理，会话保持，标记，路径转移；.................................204
nginx：只在 http 协议和 mail 协议上功能比较好，性能与 haproxy 差不多；............................................204
apache：功能较差.............................................................................................................................................204
Mysql proxy：功能尚可。.................................................................................................................................204
18.1.2. 负载均衡算法/策略 ...................................................................................................................204
18.1.2.1. 轮循均衡（Round Robin） ...........................................................................................................204
18.1.2.2. 权重轮循均衡（Weighted Round Robin）................................................................................204
18.1.2.3. 随机均衡（Random） ....................................................................................................................204
18.1.2.4. 权重随机均衡（Weighted Random）.........................................................................................204
18.1.2.5. 响应速度均衡（Response Time 探测时间）...............................................................................204
18.1.2.6. 最少连接数均衡（Least Connection）........................................................................................205
18.1.2.7. 处理能力均衡（CPU、内存） ........................................................................................................205
18.1.2.8. DNS 响应均衡（Flash DNS） .......................................................................................................205
18.1.2.9. 哈希算法............................................................................................................................................205
18.1.2.10. IP 地址散列（保证客户端服务器对应关系稳定）........................................................................205
18.1.2.11. URL 散列...........................................................................................................................................205
18.1.3. LVS.............................................................................................................................................206
18.1.3.1. LVS 原理............................................................................................................................................206
IPVS ....................................................................................................................................................................206
18.1.3.1. LVS NAT 模式 ..................................................................................................................................207
18.1.3.2. LVS DR 模式（局域网改写 mac 地址）........................................................................................208
18.1.3.3. LVS TUN 模式（IP 封装、跨网段）..............................................................................................209
18.1.3.4. LVS FULLNAT 模式.........................................................................................................................210
18.1.4. Keepalive...................................................................................................................................211
18.1.5. Nginx 反向代理负载均衡 .........................................................................................................211
18.1.5.1. upstream_module 和健康检测........................................................................................................212
18.1.5.1. proxy_pass 请求转发.......................................................................................................................212
18.1.6. HAProxy ....................................................................................................................................213
19. 数据库 .............................................................................................................................................214
19.1.1. 存储引擎 ....................................................................................................................................214
19.1.1.1. 概念....................................................................................................................................................214
19.1.1.2. InnoDB（B 树） .............................................................................................................................214
19.1.1.3. TokuDB（Fractal Tree-节点带数据） ..........................................................................................215
19.1.1.4. MyIASM.............................................................................................................................................215
19.1.1.5. Memory..............................................................................................................................................215
19.1.2. 索引 ............................................................................................................................................215
19.1.2.1. 常见索引原则有 ................................................................................................................................216
1.选择唯一性索引 ..............................................................................................................................................216
2.为经常需要排序、分组和联合操作的字段建立索引： ...............................................................................216
3．为常作为查询条件的字段建立索引。........................................................................................................216
4．限制索引的数目：........................................................................................................................................216
尽量使用数据量少的索引..................................................................................................................................216
尽量使用前缀来索引..........................................................................................................................................216
7．删除不再使用或者很少使用的索引............................................................................................................216
8 . 最左前缀匹配原则，非常重要的原则。.....................................................................................................216
10 . 尽量选择区分度高的列作为索引 ..............................................................................................................216
11 .索引列不能参与计算，保持列“干净”：带函数的查询不参与索引。 ................................................216
12 .尽量的扩展索引，不要新建索引。............................................................................................................216
19.1.3. 数据库三范式 ............................................................................................................................216
19.1.3.1. 第一范式(1st NF －列都是不可再分).............................................................................................216
19.1.3.2. 第二范式(2nd NF－每个表只描述一件事情).................................................................................216
19.1.3.3. 第三范式(3rd NF－ 不存在对非主键列的传递依赖).....................................................................217
19.1.4. 数据库是事务 ............................................................................................................................217
13/04/2018 Page 14 of 283
原子性（Atomicity）..........................................................................................................................................217
一致性（Consistency）....................................................................................................................................217
隔离性（Isolation）...........................................................................................................................................218
永久性（Durability） .........................................................................................................................................218
19.1.5. 存储过程(特定功能的 SQL 语句集)........................................................................................218
存储过程优化思路： ..............................................................................................................................................218
19.1.6. 触发器(一段能自动执行的程序)..............................................................................................218
19.1.7. 数据库并发策略 ........................................................................................................................218
19.1.7.1. 乐观锁................................................................................................................................................218
19.1.7.2. 悲观锁................................................................................................................................................219
19.1.7.3. 时间戳................................................................................................................................................219
19.1.8. 数据库锁 ....................................................................................................................................219
19.1.8.1. 行级锁................................................................................................................................................219
19.1.8.2. 表级锁................................................................................................................................................219
19.1.8.1. 页级锁................................................................................................................................................219
19.1.9. 基于 Redis 分布式锁 ................................................................................................................219
19.1.10. 分区分表 ................................................................................................................................220
垂直切分(按照功能模块) ...................................................................................................................................220
水平切分(按照规则划分存储) ...........................................................................................................................220
19.1.11. 两阶段ᨀ交协议 ....................................................................................................................220
19.1.11.1. 准备阶段............................................................................................................................................221
19.1.11.2. ᨀ交阶段............................................................................................................................................221
19.1.11.3. 缺点....................................................................................................................................................221
同步阻塞问题......................................................................................................................................................221
单点故障..............................................................................................................................................................221
数据不一致（脑裂问题）..................................................................................................................................221
二阶段无法解决的问题（数据状态不确定） ..................................................................................................221
19.1.12. 三阶段ᨀ交协议 ....................................................................................................................222
19.1.12.1. CanCommit 阶段 ..............................................................................................................................222
19.1.12.2. PreCommit 阶段 ...............................................................................................................................222
19.1.12.3. doCommit 阶段.................................................................................................................................222
19.1.13. 柔性事务 ................................................................................................................................222
19.1.13.1. 柔性事务............................................................................................................................................222
两阶段型..............................................................................................................................................................222
补偿型..................................................................................................................................................................222
异步确保型..........................................................................................................................................................223
最大努力通知型（多次尝试）..........................................................................................................................223
19.1.14. CAP........................................................................................................................................224
一致性（C）： .......................................................................................................................................................224
可用性（A）： .......................................................................................................................................................224
分区容忍性（P）：................................................................................................................................................224
20. 一致性算法......................................................................................................................................225
20.1.1. Paxos .........................................................................................................................................225
Paxos 三种角色：Proposer，Acceptor，Learners ...........................................................................................225
Proposer： .........................................................................................................................................................225
Acceptor：..........................................................................................................................................................225
Learner：............................................................................................................................................................225
Paxos 算法分为两个阶段。具体如下：...............................................................................................................225
阶段一（准 leader 确定 ）：............................................................................................................................225
阶段二（leader 确认）：..................................................................................................................................225
20.1.2. Zab .............................................................................................................................................225
1.崩溃恢复：主要就是 Leader 选举过程.........................................................................................................226
2.数据同步：Leader 服务器与其他服务器进行数据同步..............................................................................226
3.消息广播：Leader 服务器将数据发送给其他服务器..................................................................................226
20.1.3. Raft.............................................................................................................................................226
20.1.3.1. 角色....................................................................................................................................................226
Leader（领导者-日志管理） ............................................................................................................................226
Follower（追随者-日志同步）..........................................................................................................................226
Candidate（候选者-负责选票）.......................................................................................................................226
13/04/2018 Page 15 of 283
20.1.3.2. Term（任期）...................................................................................................................................226
20.1.3.3. 选举（Election）..............................................................................................................................227
选举定时器..........................................................................................................................................................227
20.1.3.4. 安全性（Safety）.............................................................................................................................227
20.1.3.5. raft 协议和 zab 协议区别 .................................................................................................................227
20.1.4. NWR...........................................................................................................................................228
N：在分布式存储系统中，有多少份备份数据................................................................................................228
W：代表一次成功的更新操作要求至少有 w 份数据写入成功 ......................................................................228
R： 代表一次成功的读数据操作要求至少有 R 份数据成功读取..................................................................228
20.1.5. Gossip........................................................................................................................................228
20.1.6. 一致性 Hash..............................................................................................................................229
20.1.6.1. 一致性 Hash 特性.............................................................................................................................229
20.1.6.2. 一致性 Hash 原理.............................................................................................................................229
1.建构环形 hash 空间：....................................................................................................................................229
2.把需要缓存的内容(对象)映射到 hash 空间..................................................................................................229
3.把服务器(节点)映射到 hash 空间 .................................................................................................................229
4.把对象映射到服务节点...................................................................................................................................229
考察 cache 的变动.............................................................................................................................................230
虚拟节点..............................................................................................................................................................230
21. JAVA 算法 ......................................................................................................................................232
21.1.1. 二分查找 ....................................................................................................................................232
21.1.2. 冒泡排序算法 ............................................................................................................................232
21.1.3. 插入排序算法 ............................................................................................................................233
21.1.4. 快速排序算法 ............................................................................................................................234
21.1.1. 希尔排序算法 ............................................................................................................................236
21.1.2. 归并排序算法 ............................................................................................................................237
21.1.3. 桶排序算法 ................................................................................................................................240
21.1.4. 基数排序算法 ............................................................................................................................241
21.1.5. 剪枝算法 ....................................................................................................................................243
21.1.6. 回溯算法 ....................................................................................................................................243
21.1.7. 最短路径算法 ............................................................................................................................243
21.1.8. 最大子数组算法 ........................................................................................................................243
21.1.9. 最长公共子序算法 ....................................................................................................................243
21.1.10. 最小生成树算法 ....................................................................................................................243
22. 数据结构..........................................................................................................................................245
22.1.1. 栈（stack）...............................................................................................................................245
22.1.2. 队列（queue） .........................................................................................................................245
22.1.3. 链表（Link）.............................................................................................................................245
22.1.4. 散列表（Hash Table）............................................................................................................246
22.1.5. 排序二叉树 ................................................................................................................................246
22.1.5.1. 插入操作............................................................................................................................................246
22.1.5.2. 删除操作............................................................................................................................................247
22.1.5.3. 查询操作............................................................................................................................................248
22.1.6. 红黑树 ........................................................................................................................................248
22.1.6.1. 红黑树的特性....................................................................................................................................248
22.1.6.1. 左旋....................................................................................................................................................248
22.1.6.1. 右旋....................................................................................................................................................249
22.1.6.1. 添加....................................................................................................................................................250
22.1.6.2. 删除....................................................................................................................................................251
22.1.7. B-TREE......................................................................................................................................252
22.1.8. 位图 ............................................................................................................................................254
23. 加密算法..........................................................................................................................................255
23.1.1. AES ............................................................................................................................................255
23.1.2. RSA............................................................................................................................................255
23.1.3. CRC............................................................................................................................................256
23.1.4. MD5............................................................................................................................................256
13/04/2018 Page 16 of 283
24. 分布式缓存......................................................................................................................................257
24.1.1. 缓存雪崩 ....................................................................................................................................257
24.1.2. 缓存穿透 ....................................................................................................................................257
24.1.3. 缓存预热 ....................................................................................................................................257
24.1.4. 缓存更新 ....................................................................................................................................257
24.1.5. 缓存降级 ....................................................................................................................................257
25. HADOOP ........................................................................................................................................259
25.1.1. 概念 ............................................................................................................................................259
25.1.2. HDFS .........................................................................................................................................259
25.1.2.1. Client..................................................................................................................................................259
25.1.2.2. NameNode........................................................................................................................................259
25.1.2.3. Secondary NameNode .................................................................................................................259
25.1.2.4. DataNode.........................................................................................................................................259
25.1.3. MapReduce...............................................................................................................................260
25.1.3.1. Client.................................................................................................................................................260
25.1.3.2. JobTracker .......................................................................................................................................260
25.1.3.3. TaskTracker......................................................................................................................................261
25.1.3.4. Task ...................................................................................................................................................261
25.1.3.5. Reduce Task 执行过程 ...................................................................................................................261
25.1.4. Hadoop MapReduce 作业的生命周期...................................................................................262
1.作业ᨀ交与初始化...........................................................................................................................................262
2.任务调度与监控。...........................................................................................................................................262
3.任务运行环境准备...........................................................................................................................................262
4.任务执行 ..........................................................................................................................................................262
5.作业完成。 ......................................................................................................................................................262
26. SPARK............................................................................................................................................263
26.1.1. 概念 ............................................................................................................................................263
26.1.2. 核心架构 ....................................................................................................................................263
Spark Core .........................................................................................................................................................263
Spark SQL ..........................................................................................................................................................263
Spark Streaming................................................................................................................................................263
Mllib .....................................................................................................................................................................263
GraphX................................................................................................................................................................263
26.1.3. 核心组件 ....................................................................................................................................264
Cluster Manager-制整个集群，监控 worker .................................................................................................264
Worker 节点-负责控制计算节点.......................................................................................................................264
Driver： 运行 Application 的 main()函数.........................................................................................................264
Executor：执行器，是为某个 Application 运行在 worker node 上的一个进程..........................................264
26.1.4. SPARK 编程模型......................................................................................................................264
26.1.5. SPARK 计算模型......................................................................................................................265
26.1.6. SPARK 运行流程......................................................................................................................266
1. 构建 Spark Application 的运行环境，启动 SparkContext....................................................................267
2. SparkContext 向资源管理器（可以是 Standalone，Mesos，Yarn）申请运行 Executor 资源，并启
动 StandaloneExecutorbackend，..................................................................................................................267
3. Executor 向 SparkContext 申请 Task .....................................................................................................267
4. SparkContext 将应用程序分发给 Executor............................................................................................267
5. SparkContext 构建成 DAG 图，将 DAG 图分解成 Stage、将 Taskset 发送给 Task Scheduler，最
后由 Task Scheduler 将 Task 发送给 Executor 运行.....................................................................................267
6. Task 在 Executor 上运行，运行完释放所有资源...................................................................................267
26.1.7. SPARK RDD 流程 ....................................................................................................................267
26.1.8. SPARK RDD.............................................................................................................................267
（1）RDD 的创建方式...........................................................................................................................................267
（2）RDD 的两种操作算子（转换（Transformation）与行动（Action））..............................................268
27. STORM ...........................................................................................................................................269
13/04/2018 Page 17 of 283
27.1.1. 概念 ............................................................................................................................................269
27.1.1. 集群架构 ....................................................................................................................................269
27.1.1.1. Nimbus（master-代码分发给 Supervisor） ................................................................................269
27.1.1.2. Supervisor（slave-管理 Worker 进程的启动和终止）...............................................................269
27.1.1.3. Worker（具体处理组件逻辑的进程）............................................................................................269
27.1.1.4. Task ...................................................................................................................................................270
27.1.1.5. ZooKeeper ........................................................................................................................................270
27.1.2. 编程模型（spout->tuple->bolt）.......................................................................................270
27.1.2.1. Topology............................................................................................................................................270
27.1.2.2. Spout..................................................................................................................................................270
27.1.2.3. Bolt.....................................................................................................................................................270
27.1.2.4. Tuple..................................................................................................................................................270
27.1.2.5. Stream ...............................................................................................................................................271
27.1.3. Topology 运行...........................................................................................................................271
(1). Worker（进程） (2). Executor（线程） (3). Task..................................................................................271
27.1.3.1. Worker(1 个 worker 进程执行的是 1 个 topology 的子集) .......................................................271
27.1.3.2. Executor(executor 是 1 个被 worker 进程启动的单独线程)......................................................271
27.1.3.3. Task(最终运行 spout 或 bolt 中代码的单元)...............................................................................272
27.1.4. Storm Streaming Grouping.....................................................................................................272
27.1.4.1. huffle Grouping.................................................................................................................................273
27.1.4.2. Fields Grouping................................................................................................................................273
27.1.4.3. All grouping ：广播..........................................................................................................................273
27.1.4.4. Global grouping................................................................................................................................274
27.1.4.5. None grouping ：不分组.................................................................................................................274
27.1.4.6. Direct grouping ：直接分组 指定分组 ...........................................................................................274
28. YARN ..............................................................................................................................................275
28.1.1. 概念 ............................................................................................................................................275
28.1.2. ResourceManager ...................................................................................................................275
28.1.3. NodeManager...........................................................................................................................275
28.1.4. ApplicationMaster .................................................................................................................276
28.1.5. YARN 运行流程 ....................................................................................................................277
29. 机器学习..........................................................................................................................................278
29.1.1. 决策树 ........................................................................................................................................278
29.1.2. 随机森林算法 ............................................................................................................................278
29.1.3. 逻辑回归 ....................................................................................................................................278
29.1.4. SVM............................................................................................................................................278
29.1.5. 朴素贝叶斯 ................................................................................................................................278
29.1.6. K 最近邻算法.............................................................................................................................278
29.1.7. K 均值算法.................................................................................................................................278
29.1.8. Adaboost 算法 ..........................................................................................................................278
29.1.9. 神经网络 ....................................................................................................................................278
29.1.10. 马尔可夫 ................................................................................................................................278
30. 云计算 .............................................................................................................................................279
30.1.1. SaaS ..........................................................................................................................................279
30.1.2. PaaS ..........................................................................................................................................279
30.1.3. IaaS............................................................................................................................................279
30.1.4. Docker........................................................................................................................................279
30.1.4.1. 概念....................................................................................................................................................279
30.1.4.2. Namespaces.....................................................................................................................................280
30.1.4.3. 进程(CLONE_NEWPID 实现的进程隔离)......................................................................................281
30.1.4.4. Libnetwork 与网络隔离....................................................................................................................281
30.1.4.5. 资源隔离与 CGroups .......................................................................................................................282
30.1.4.6. 镜像与 UnionFS................................................................................................................................282
30.1.4.7. 存储驱动............................................................................................................................................282
13/04/2018 Page 18 of 283
30.1.5. Openstack .................................................................................................................................283