[转]后端架构师技术图谱

查看原文

《后端架构师技术图谱》

知识共享协议(CC协议)

最后更新于20180502

(Toc generated by simple-php-github-toc

数据结构

队列

集合

链表、数组

字典、关联数组

二叉树

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

完全二叉树

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

平衡二叉树

左右两个子树的高度差的绝对值不超过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

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

常用算法

排序、查找算法

选择排序

冒泡排序

插入排序

快速排序

归并排序

希尔排序

TODO

堆排序

计数排序

桶排序

基数排序

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

二分查找

Java 中的排序工具

布隆过滤器

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

字符串比较

KMP 算法

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

深度优先、广度优先

贪心算法

回溯算法

剪枝算法

动态规划

朴素贝叶斯

推荐算法

最小生成树算法

最短路径算法

并发

多线程

线程安全

一致性、事务

事务 ACID 特性

事务的隔离级别

  • 未提交读:一个事务可以读取另一个未提交的数据,容易出现脏读的情况。
  • 读提交:一个事务等另外一个事务提交之后才可以读取数据,但会出现不可重复读的情况(多次读取的数据不一致),读取过程中出现UPDATE操作,会多。(大多数数据库默认级别是RC,比如SQL Server,Oracle),读取的时候不可以修改。
  • 可重复读: 同一个事务里确保每次读取的时候,获得的是同样的数据,但不保障原始数据被其他事务更新(幻读),Mysql InnoDB 就是这个级别。
  • 序列化:所有事物串行处理(牺牲了效率)

  • 《理解事务的4种隔离级别》

  • 数据库事务的四大特性及事务隔离级别

  • 《MySQL的InnoDB的幻读问题 》

    • 幻读的例子非常清楚。
    • 通过 SELECT ... FOR UPDATE 解决。
  • 《一篇文章带你读懂MySQL和InnoDB》

    • 图解脏读、不可重复读、幻读问题。

MVCC

Java中的锁和同步类

公平锁 & 非公平锁

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

悲观锁

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

乐观锁 & CAS

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 中的读锁是共享锁。

死锁

操作系统

计算机原理

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

IOC

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

AOP

UML

微服务思想

康威定律

  • 《微服务架构的理论基础 - 康威定律》

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

运维 & 统计 & 技术支持

常规监控

命令行监控工具

APM

APM — Application Performance Management

统计分析

持续集成(CI/CD)

Jenkins

  • [《使用Jenkins进行持续集成
添加新评论