后端架构师技术图谱

转自: GitHub/architect-awesome , 大体结构如下(更新时间: 2018-06-22)

img

数据结构

队列

  • 《java队列——queue详细分析》
    • 非阻塞队列:ConcurrentLinkedQueue(无界线程安全),采用CAS机制(compareAndSwapObject原子操作)。
    • 阻塞队列:ArrayBlockingQueue(有界)、LinkedBlockingQueue(无界)、DelayQueue、PriorityBlockingQueue,采用锁机制;使用 ReentrantLock 锁。
  • 《LinkedList、ConcurrentLinkedQueue、LinkedBlockingQueue对比分析》

集合

链表、数组

字典、关联数组

二叉树

每个节点最多有两个叶子节点。

完全二叉树

  • 《完全二叉树》
    • 叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

平衡二叉树

左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二叉查找树(BST)

二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree)。

红黑树

B-,B+,B*树

MySQL是基于B+树聚集索引组织表

LSM 树

LSM(Log-Structured Merge-Trees)和 B+ 树相比,是牺牲了部分读的性能来换取写的性能(通过批量写入),实现读写之间的。 Hbase、LevelDB、Tair(Long DB)、nessDB 采用 LSM 树的结构。LSM可以快速建立索引。

  • 《LSM树 VS B+树》
    • B+ 树读性能好,但由于需要有序结构,当key比较分散时,磁盘寻道频繁,造成写性能。
    • LSM 是将一个大树拆分成N棵小树,先写到内存(无寻道问题,性能高),在内存中构建一颗有序小树(有序树),随着小树越来越大,内存的小树会flush到磁盘上。当读时,由于不知道数据在哪棵小树上,因此必须遍历(二分查找)所有的小树,但在每颗小树内部数据是有序的。
  • 《LSM树(Log-Structured Merge Tree)存储引擎》
    • 极端的说,基于LSM树实现的HBase的写性能比MySQL高了一个数量级,读性能低了一个数量级。
    • 优化方式:Bloom filter 替代二分查找;compact 小数位大树,提高查询性能。
    • Hbase 中,内存中达到一定阈值后,整体flush到磁盘上、形成一个文件(B+数),HDFS不支持update操作,所以Hbase做整体flush而不是merge update。flush到磁盘上的小树,定期会合并成一个大树。

BitSet

经常用于大规模数据的排重检查。

常用算法

排序、查找算法

选择排序

  • 《Java中的经典算法之选择排序(SelectionSort)》
    • 每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。

冒泡排序

  • 《冒泡排序的2种写法》
    • 相邻元素前后交换、把最大的排到最后。
    • 时间复杂度 O(n²)

插入排序

快速排序

  • 《坐在马桶上看算法:快速排序》
    • 一侧比另外一次都大或小。

归并排序

  • 《图解排序算法(四)之归并排序》
    • 分而治之,分成小份排序,在合并(重建一个新空间进行复制)。

希尔排序

TODO

堆排序

  • 《图解排序算法(三)之堆排序》
    • 排序过程就是构建最大堆的过程,最大堆:每个结点的值都大于或等于其左右孩子结点的值,堆顶元素是最大值。

计数排序

  • 《计数排序和桶排序》
    • 和桶排序过程比较像,差别在于桶的数量。

桶排序

基数排序

按照个位、十位、百位、…依次来排。

二分查找

  • 《二分查找(java实现)》
    • 要求待查找的序列有序。
    • 时间复杂度 O(logN)。
  • 《java实现二分查找-两种方式》
    • while + 递归。

Java 中的排序工具

  • 《Arrays.sort和Collections.sort实现原理解析》
    • Collections.sort算法调用的是合并排序。
    • Arrays.sort() 采用了2种排序算法 – 基本类型数据使用快速排序法,对象数组使用归并排序。

布隆过滤器

常用于大数据的排重,比如email,url 等。 核心原理:将每条数据通过计算产生一个指纹(一个字节或多个字节,但一定比原始数据要少很多),其中每一位都是通过随机计算获得,在将指纹映射到一个大的按位存储的空间中。注意:会有一定的错误率。 优点:空间和时间效率都很高。 缺点:随着存入的元素数量增加,误算率随之增加。

字符串比较

KMP 算法

KMP:Knuth-Morris-Pratt算法(简称KMP) 核心原理是利用一个“部分匹配表”,跳过已经匹配过的元素。

深度优先、广度优先

贪心算法

回溯算法

剪枝算法

动态规划

朴素贝叶斯

推荐算法

最小生成树算法

最短路径算法

并发

Java 并发

多线程

线程安全

一致性、事务

事务 ACID 特性

事务的隔离级别

  • 未提交读:一个事务可以读取另一个未提交的数据,容易出现脏读的情况。
  • 读提交:一个事务等另外一个事务提交之后才可以读取数据,但会出现不可重复读的情况(多次读取的数据不一致),读取过程中出现UPDATE操作,会多。(大多数数据库默认级别是RC,比如SQL Server,Oracle),读取的时候不可以修改。
  • 可重复读: 同一个事务里确保每次读取的时候,获得的是同样的数据,但不保障原始数据被其他事务更新(幻读),Mysql InnoDB 就是这个级别。
  • 序列化:所有事物串行处理(牺牲了效率)
  • 《理解事务的4种隔离级别》
  • 数据库事务的四大特性及事务隔离级别
  • 《MySQL的InnoDB的幻读问题 》
    • 幻读的例子非常清楚。
    • 通过 SELECT … FOR UPDATE 解决。
  • 《一篇文章带你读懂MySQL和InnoDB》
    • 图解脏读、不可重复读、幻读问题。

MVCC

  • 《【mysql】关于innodb中MVCC的一些理解》
    • innodb 中 MVCC 用在 Repeatable-Read 隔离级别。
    • MVCC 会产生幻读问题(更新时异常。)
  • 《轻松理解MYSQL MVCC 实现机制》
    • 通过隐藏版本列来实现 MVCC 控制,一列记录创建时间、一列记录删除时间,这里的时间
    • 每次只操作比当前版本小(或等于)的 行。

Java中的锁和同步类

  • 《Java中的锁分类》
    • 主要包括 synchronized、ReentrantLock、和 ReadWriteLock。
  • 《Java并发之AQS详解》
  • 《Java中信号量 Semaphore》
    • 有数量控制
    • 申请用 acquire,申请不要则阻塞;释放用 release。
  • 《java开发中的Mutex vs Semaphore》
    • 简单的说 就是Mutex是排它的,只有一个可以获取到资源, Semaphore也具有排它性,但可以定义多个可以获取的资源的对象。

公平锁 & 非公平锁

公平锁的作用就是严格按照线程启动的顺序来执行的,不允许其他线程插队执行的;而非公平锁是允许插队的。

  • 《公平锁与非公平锁》
    • 默认情况下 ReentrantLock 和 synchronized 都是非公平锁。ReentrantLock 可以设置成公平锁。

悲观锁

悲观锁如果使用不当(锁的条数过多),会引起服务大面积等待。推荐优先使用乐观锁+重试。

  • 《【MySQL】悲观锁&乐观锁》
    • 乐观锁的方式:版本号+重试方式
    • 悲观锁:通过 select … for update 进行行锁(不可读、不可写,share 锁可读不可写)。
  • 《Mysql查询语句使用select.. for update导致的数据库死锁分析》
    • mysql的innodb存储引擎实务锁虽然是锁行,但它内部是锁索引的。
    • 锁相同数据的不同索引条件可能会引起死锁。
  • 《Mysql并发时经典常见的死锁原因及解决方法》

乐观锁 & CAS

  • 《乐观锁的一种实现方式——CAS》
    • 和MySQL乐观锁方式相似,只不过是通过和原值进行比较。

ABA 问题

由于高并发,在CAS下,更新后可能此A非彼A。通过版本号可以解决,类似于上文Mysql 中提到的的乐观锁。

CopyOnWrite容器

可以对CopyOnWrite容器进行并发的读,而不需要加锁。CopyOnWrite并发容器用于读多写少的并发场景。比如白名单,黑名单,商品类目的访问和更新场景,不适合需要数据强一致性的场景。

RingBuffer

可重入锁 & 不可重入锁

  • 《可重入锁和不可重入锁》
    • 通过简单代码举例说明可重入锁和不可重入锁。
    • 可重入锁指同一个线程可以再次获得之前已经获得的锁。
    • 可重入锁可以用户避免死锁。
    • Java中的可重入锁:synchronized 和 java.util.concurrent.locks.ReentrantLock
  • 《ReenTrantLock可重入锁(和synchronized的区别)总结》
    • synchronized 使用方便,编译器来加锁,是非公平锁。
    • ReenTrantLock 使用灵活,锁的公平性可以定制。
    • 相同加锁场景下,推荐使用 synchronized。

互斥锁 & 共享锁

互斥锁:同时只能有一个线程获得锁。比如,ReentrantLock 是互斥锁,ReadWriteLock 中的写锁是互斥锁。 共享锁:可以有多个线程同时或的锁。比如,Semaphore、CountDownLatch 是共享锁,ReadWriteLock 中的读锁是共享锁。

死锁

  • 《“死锁”四个必要条件的合理解释》
    • 互斥、持有、不可剥夺、环形等待。
  • Java如何查看死锁?
    • JConsole 可以识别死锁。
  • java多线程系列:死锁及检测
    • jstack 可以显示死锁。

操作系统

计算机原理

CPU

多级缓存

典型的 CPU 有三级缓存,距离核心越近,速度越快,空间越小。L1 一般 32k,L2 一般 256k,L3 一般12M。内存速度需要200个 CPU 周期,CPU 缓存需要1个CPU周期。

进程

TODO

线程

协程

  • 《终结python协程—-从yield到actor模型的实现》
    • 线程的调度是由操作系统负责,协程调度是程序自行负责
    • 与线程相比,协程减少了无谓的操作系统切换.
    • 实际上当遇到IO操作时做切换才更有意义,(因为IO操作不用占用CPU),如果没遇到IO操作,按照时间片切换.

Linux

设计模式

设计模式的六大原则

  • 《设计模式的六大原则》
    • 开闭原则:对扩展开放,对修改关闭,多使用抽象类和接口。
    • 里氏替换原则:基类可以被子类替换,使用抽象类继承,不使用具体类继承。
    • 依赖倒转原则:要依赖于抽象,不要依赖于具体,针对接口编程,不针对实现编程。
    • 接口隔离原则:使用多个隔离的接口,比使用单个接口好,建立最小的接口。
    • 迪米特法则:一个软件实体应当尽可能少地与其他实体发生相互作用,通过中间类建立联系。
    • 合成复用原则:尽量使用合成/聚合,而不是使用继承。

23种常见设计模式

应用场景

  • 《细数JDK里的设计模式》
    • 结构型模式:
    • 适配器:用来把一个接口转化成另一个接口,如 java.util.Arrays#asList()。
    • 桥接模式:这个模式将抽象和抽象操作的实现进行了解耦,这样使得抽象和实现可以独立地变化,如JDBC;
    • 组合模式:使得客户端看来单个对象和对象的组合是同等的。换句话说,某个类型的方法同时也接受自身类型作为参数,如 Map.putAll,List.addAll、Set.addAll。
    • 装饰者模式:动态的给一个对象附加额外的功能,这也是子类的一种替代方式,如 java.util.Collections#checkedList|Map|Set|SortedSet|SortedMap。
    • 享元模式:使用缓存来加速大量小对象的访问时间,如 valueOf(int)。
    • 代理模式:代理模式是用一个简单的对象来代替一个复杂的或者创建耗时的对象,如 java.lang.reflect.Proxy
    • 创建模式:
    • 抽象工厂模式:抽象工厂模式提供了一个协议来生成一系列的相关或者独立的对象,而不用指定具体对象的类型,如 java.util.Calendar#getInstance()。
    • 建造模式(Builder):定义了一个新的类来构建另一个类的实例,以简化复杂对象的创建,如:java.lang.StringBuilder#append()。
    • 工厂方法:就是 一个返* 回具体对象的方法,而不是多个,如 java.lang.Object#toString()、java.lang.Class#newInstance()。
    • 原型模式:使得类的实例能够生成自身的拷贝、如:java.lang.Object#clone()。
    • 单例模式:全局只有一个实例,如 java.lang.Runtime#getRuntime()。
    • 行为模式:
    • 责任链模式:通过把请求从一个对象传递到链条中下一个对象的方式,直到请求被处理完毕,以实现对象间的解耦。如 javax.servlet.Filter#doFilter()。
    • 命令模式:将操作封装到对象内,以便存储,传递和返回,如:java.lang.Runnable。
    • 解释器模式:定义了一个语言的语法,然后解析相应语法的语句,如,java.text.Format,java.text.Normalizer。
    • 迭代器模式:提供一个一致的方法来顺序访问集合中的对象,如 java.util.Iterator。
    • 中介者模式:通过使用一个中间对象来进行消息分发以及减少类之间的直接依赖,java.lang.reflect.Method#invoke()。
    • 空对象模式:如 java.util.Collections#emptyList()。
    • 观察者模式:它使得一个对象可以灵活的将消息发送给感兴趣的对象,如 java.util.EventListener。
    • 模板方法模式:让子类可以重写方法的一部分,而不是整个重写,如 java.util.Collections#sort()。
  • 《Spring-涉及到的设计模式汇总》
  • 《Mybatis使用的设计模式》

单例模式

责任链模式

TODO

MVC

  • 《MVC 模式》
    • 模型(model)-视图(view)-控制器(controller)

IOC

  • 《理解 IOC》
  • 《IOC 的理解与解释》
    • 正向控制:传统通过new的方式。反向控制,通过容器注入对象。
    • 作用:用于模块解耦。
    • DI:Dependency Injection,即依赖注入,只关心资源使用,不关心资源来源。

AOP

  • 《轻松理解AOP(面向切面编程)》
  • 《Spring AOP详解》
  • 《Spring AOP的实现原理》
    • Spring AOP使用的动态代理,主要有两种方式:JDK动态代理和CGLIB动态代理。
  • 《Spring AOP 实现原理与 CGLIB 应用》
    • Spring AOP 框架对 AOP 代理类的处理原则是:如果目标对象的实现类实现了接口,Spring AOP 将会采用 JDK 动态代理来生成 AOP 代理类;如果目标对象的实现类没有实现接口,Spring AOP 将会采用 CGLIB 来生成 AOP 代理类

UML

微服务思想

康威定律

  • 《微服务架构的理论基础 - 康威定律》
    • 定律一:组织沟通方式会通过系统设计表达出来,就是说架构的布局和组织结构会有相似。
    • 定律二:时间再多一件事情也不可能做的完美,但总有时间做完一件事情。一口气吃不成胖子,先搞定能搞定的。
    • 定律三:线型系统和线型组织架构间有潜在的异质同态特性。种瓜得瓜,做独立自治的子系统减少沟通成本。
    • 定律四:大的系统组织总是比小系统更倾向于分解。合久必分,分而治之。
  • 《微服务架构核⼼20讲》

运维 & 统计 & 技术支持

常规监控

  • 《腾讯业务系统监控的修炼之路》
    • 监控的方式:主动、被动、旁路(比如舆情监控)
    • 监控类型: 基础监控、服务端监控、客户端监控、 监控、用户端监控
    • 监控的目标:全、块、准
    • 核心指标:请求量、成功率、耗时
  • 《开源还是商用?十大云运维监控工具横评》
    • Zabbix、Nagios、Ganglia、Zenoss、Open-falcon、监控宝、 360网站服务监控、阿里云监控、百度云观测、小蜜蜂网站监测等。
  • 《监控报警系统搭建及二次开发经验》

命令行监控工具

APM

APM — Application Performance Management

统计分析

  • 《流量统计的基础:埋点》
    • 常用指标:访问与访客、停留时长、跳出率、退出率、转化率、参与度
  • 《APP埋点常用的统计工具、埋点目标和埋点内容》
    • 第三方统计:友盟、百度移动、魔方、App Annie、talking data、神策数据等。
  • 《美团点评前端无痕埋点实践》
    • 所谓无痕、即通过可视化工具配置采集节点,在前端自动解析配置并上报埋点数据,而非硬编码。

持续集成(CI/CD)

Jenkins

环境分离

开发、测试、生成环境分离。

自动化运维

Ansible

puppet

chef

测试

TDD 理论

  • 《深度解读 - TDD(测试驱动开发)》
    • 基于测试用例编码功能代码,XP(Extreme Programming)的核心实践.
    • 好处:一次关注一个点,降低思维负担;迎接需求变化或改善代码的设计;提前澄清需求;快速反馈;

单元测试

  • 《Java单元测试之JUnit篇》
  • 《JUnit 4 与 TestNG 对比》
    • TestNG 覆盖 JUnit 功能,适用于更复杂的场景。
  • 《单元测试主要的测试功能点》
    • 模块接口测试、局部数据结构测试、路径测试 、错误处理测试、边界条件测试 。

压力测试

全链路压测

A/B 、灰度、蓝绿测试

虚拟化

KVM

Xen

OpenVZ

容器技术

Docker

云技术

OpenStack

DevOps

文档管理

中间件

Web Server

Nginx

  • 《Ngnix的基本学习-多进程和Apache的比较》
    • Nginx 通过异步非阻塞的事件处理机制实现高并发。Apache 每个请求独占一个线程,非常消耗系统资源。
    • 事件驱动适合于IO密集型服务(Nginx),多进程或线程适合于CPU密集型服务(Apache),所以Nginx适合做反向代理,而非web服务器使用。
  • 《nginx与Apache的对比以及优缺点》
    • nginx只适合静态和反向代理,不适合处理动态请求。

OpenResty

  • 官方网站
  • 《浅谈 OpenResty》
    • 通过 Lua 模块可以在Nginx上进行开发。

Apache Httpd

Tomcat

架构原理

调优方案

  • 《Tomcat 调优方案》
    • 启动NIO模式(或者APR);调整线程池;禁用AJP连接器(Nginx+tomcat的架构,不需要AJP);
  • 《tomcat http协议与ajp协议》
  • 《AJP与HTTP比较和分析》
    • AJP 协议(8009端口)用于降低和前端Server(如Apache,而且需要支持AJP协议)的连接数(前端),通过长连接提高性能。
    • 并发高时,AJP协议优于HTTP协议。

Jetty

  • 《Jetty 的工作原理以及与 Tomcat 的比较》
  • 《jetty和tomcat优势比较》
    • 架构比较:Jetty的架构比Tomcat的更为简单。
    • 性能比较:Jetty和Tomcat性能方面差异不大,Jetty默认采用NIO结束在处理I/O请求上更占优势,Tomcat默认采用BIO处理I/O请求,Tomcat适合处理少数非常繁忙的链接,处理静态资源时性能较差。
    • 其他方面:Jetty的应用更加快速,修改简单,对新的Servlet规范的支持较好;Tomcat 对JEE和Servlet 支持更加全面。

缓存

本地缓存

客户端缓存

服务端缓存

Web缓存

Memcached

Redis

  • 《Redis 教程》
  • 《redis底层原理》
    • 使用 ziplist 存储链表,ziplist是一种压缩链表,它的好处是更能节省内存空间,因为它所存储的内容都是在连续的内存区域当中的。
    • 使用 skiplist(跳跃表)来存储有序集合对象、查找上先从高Level查起、时间复杂度和红黑树相当,实现容易,无锁、并发性好。
  • 《Redis持久化方式》
    • RDB方式:定期备份快照,常用于灾难恢复。优点:通过fork出的进程进行备份,不影响主进程、RDB 在恢复大数据集时的速度比 AOF 的恢复速度要快。缺点:会丢数据。
    • AOF方式:保存操作日志方式。优点:恢复时数据丢失少,缺点:文件大,回复慢。
    • 也可以两者结合使用。
  • 《分布式缓存–序列3–原子操作与CAS乐观锁》

架构

回收策略

Tair

  • 官方网站
  • 《Tair和Redis的对比》
  • 特点:可以配置备份节点数目,通过异步同步到备份节点
  • 一致性Hash算法。
  • 架构:和Hadoop 的设计思想类似,有Configserver,DataServer,Configserver 通过心跳来检测,Configserver也有主备关系。

几种存储引擎:

  • MDB,完全内存性,可以用来存储Session等数据。
  • Rdb(类似于Redis),轻量化,去除了aof之类的操作,支持Restfull操作
  • LDB(LevelDB存储引擎),持久化存储,LDB 作为rdb的持久化,google实现,比较高效,理论基础是LSM(Log-Structured-Merge Tree)算法,现在内存中修改数据,达到一定量时(和内存汇总的旧数据一同写入磁盘)再写入磁盘,存储更加高效,县比喻Hash算法。
  • Tair采用共享内存来存储数据,如果服务挂掉(非服务器),重启服务之后,数据亦然还在。

消息队列

  • 《消息队列-推/拉模式学习 & ActiveMQ及JMS学习》
    • RabbitMQ 消费者默认是推模式(也支持拉模式)。
    • Kafka 默认是拉模式。
    • Push方式:优点是可以尽可能快地将消息发送给消费者,缺点是如果消费者处理能力跟不上,消费者的缓冲区可能会溢出。
    • Pull方式:优点是消费端可以按处理能力进行拉去,缺点是会增加消息延迟。
  • 《Kafka、RabbitMQ、RocketMQ等消息中间件的对比 —— 消息发送性能和区别》

消息总线

消息总线相当于在消息队列之上做了一层封装,统一入口,统一管控、简化接入成本。

消息的顺序

RabbitMQ

支持事务,推拉模式都是支持、适合