Bajins

# 技术概念

# Flag

RESTful是一种架构风格，其核心是面向资源，更简单；而WebService底层SOAP协议，主要核心是面向活动；两个都是通过web请求调用接口

注解(也称为元数据)就是代码中的特殊标记，为我们在代码中添加信息提供了一种形式化的方法，使我们可以在稍后某个时刻非常方便的使用这些数据。

Graceful/Gentle Exit（优雅退出）：指程序结束前，等待当前任务完成或做一些记录后再完全退出 逃逸分析（Escape Analysis）

是编译器用来决定程序中值的位置的过程。编译器执行静态代码分析，以确定一个构造体的实例化值是否会逃逸到堆

逃逸是指在某个方法之内创建的对象，除了在方法体之内被引用之外，还在方法体之外被其它变量引用到； 这样带来的后果是在该方法执行完毕之后，该方法中创建的对象将无法被GC回收，由于其被其它变量引用。 正常的方法调用中，方法体中创建的对象将在执行完毕之后，将回收其中创建的对象；故由于无法回收，即成为逃逸。

微服务、Service Mesh 和 Serverless

Fuction as a Service无服务器计算，目的是希望应用不用一直运行着，只有当有请求来的时候，才快速启动这个应用 ，然后请求一走就停掉这个应用，换句话说，不让应用在背景程式持续的启动着，而是有需要的时候才开启他

# 编程范式

编程范型、编程范式或程序设计法（Programming Paradigm）是某种编程语言典型的编程风格或者说是编程方式

范类：强类型/弱类型，动态语言/静态语言，编译/解释

  • 过程化（命令式）编程
  • 事件驱动编程
  • 面向对象编程
  • 链式编程
  • 函数式编程
  • 并发编程
  • 约束编程
  • 数据流编程（Dataflow programming）
  • 声明性编程
  • 分布式的编程
  • 泛型编程 (opens new window)
  • 逻辑编程
  • 元编程
  • 响应式/反应式编程（Reactive programming）
  • 面向方面/面向切面编程（AOP）
  • 过程式编程
  • 元编程（Metaprogramming）
  • 宏（Macro）

# 设计模式及原则

# 数据结构与算法

数据结构大致包含以下几种存储结构 (opens new window)：

  • 线性表，还可细分为顺序表、链表、栈和队列；
  • 树结构，包括普通树，二叉树，线索二叉树等；
  • 图存储结构；

数组、字符串、队列、栈、链表、集合、哈希表、二叉树

# 算法复杂度

O(1)、 O(n)、 O(logn)、 O(nlogn) 可表示时间复杂度，也可以表示空间复杂度

O加上()里面是一个函数f()即O(f())，函数指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。

如果ax=N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作x=logaN，读作以a为底N的对数，其中a叫做对数的底数，N叫做真数。

类型 意义 举例
O(1) 最低复杂度，常量值也就是耗时/ 耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变 哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标 (不考虑冲突的话)
O(n) 数据量增大几倍，耗时也增大几倍 遍历算法
O(n^2) 对n个数排序，需要扫描 n x n 次 冒泡排序
O(logn) 当数据增大n倍时，耗时增大logn 倍(这里的log是以2为底的，比 如，当数据增大256倍时，耗时只增大8倍, 二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标
O(nlogn) 就是n乘以logn,当数据增大256倍 时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。 归并排 序就是O(nlogn)的时间复杂度
数据结构 查找（平均） 查找（最坏） 插入（平均） 插入（最坏） 删除（平均） 删除（最坏） 遍历
数组 O(N) O(N) O(N) O(N) O(N) O(N)
有序数组 O(logN) O(n) O(N) O(N) O(N) O(N) O(N)
链表 O(N) O(N) O(1) O(1) O(1) O(1)
有序链表 O(N) O(N) O(N) O(N) O(1) O(1) O(N)
二叉查找树 O(logN) O(N) O(logN) O(N) O(logN) O(N) O(N)
红黑树 O(logN) O(logN) O(logN) O(logN) O(logN) O(logN) O(N)
平衡树 O(logN) O(logN) O(logN) O(logN) O(logN) O(logN) O(N)
二叉堆 优先队列 O(1) O(1) O(logN) O(logN) O(logN) O(logN) O(N)
哈希表 O(1) O(1) O(1) O(1) O(1) O(1) O(N)

排序、双指针、查找、分治、动态规划、递归、回溯、贪心、位运算、DFS、BFS、图

# 迭代循环遍历递归

  • 循环（loop），指的是在满足条件的情况下，重复执行同一段代码。比如，while语句。
    • 循环则即能对应集合，列表，数组等，也能对执行代码进行操作。
  • 遍历（traversal），指的是按照一定的规则访问树形结构中的每个节点，而且每个节点都只访问一次。
    • 遍历同迭代一样，也不能对执行代码进行遍历。
  • 迭代（iterate），指的是按照某种顺序逐个访问列表中的每一项。比如，for语句。
    • 迭代只能对应集合，列表，数组等。不能对执行代码进行迭代。
    • 环结构，从初始状态开始，每次迭代都遍历这个环，并更新状态，多次迭代直到到达结束状态
  • 递归（recursion），指的是一个函数不断调用自身的行为。比如，以编程方式输出著名的斐波纳契数列。
    • 线性递归(单向递归)和尾递归（tail recursion）。单向递归 → 尾递归 → 迭代
    • 树结构，从字面可以其理解为重复“递推”和“回归”的过程，当“递推”到达底部时就会开始“回归”，其过程相当于树的深度优先遍历

理论上递归和迭代时间复杂度方面是一样的，但实际应用中（函数调用和函数调用堆栈的开销）递归比迭代效率要低。

将递归方案转换为迭代的方案我们通常只需要两步即可：

  1. 我们在函数中使用堆或队列数据结构，以取代系统调用栈的作用。在每一次递归出现时，我们简单地将参数作为一个新元素压入到我们创建的数据结构中，来代替递归调用。
  2. 另外，我们在之前创建的数据结构上做一个循环操作。递归的调用链就被迭代的循环操作替代了。

# directory和folder区别

  • directory 目录，简称 dir
  • folder 文件夹

两者一般情况下是可以相互通用的，都表示文件夹的意思；但是细细纠来，还是有区别的：

Hi, please go to D:\files\images\directory, and then double click and open folder "travelImg".

  • 看完上面那句话，相信大家有点知道意思了：

directory 也是一个folder，但是我们在说一个directory的时候，通常指它含有路径的意思在里面；

folder 一般情况，是说某一个文件夹，通常不包含路径的意思，比如：双击这个文件夹，在里面找找看。

# 进程/线程/协程

DRF-SC：无数据竞争的程序以顺序一致的方式执行

  • happens-before
  • memory barrier

在操作系统中，线程是最小的执行单元，进程是最小的资源管理单元。进程和线程由操作系统管理，协程由应用程序管理。

协程(Coroutine)编译器级的，进程(Process)和线程(Thread)操作系统级的，Process -> Thread -> Coroutine

并发

同一时间段有几个程序都处于已经启动到运行完毕之间，并且这几个程序都在同一个处理机上运行，并发的两种关系是同步和互斥；

  • 结构化并发（Structured Concurrency）

并行

单处理器中进程被交替执行，表现出一种并发的外部特征；在多处理器中，进程可以交替执行，还能重叠执行， 实现并行处理，并行就是同事发生的多个并发事件，具有并发的含义，但并发不一定是并行，也就是说事件之间不一定要同一时刻发生；

互斥

进程之间访问临界资源时相互排斥的现象；

同步

进程之间存在依赖关系，一个进程结束的输出作为另一个进程的输入。具有同步关系的一组并发进程之间发送的信息称为消息或者事件；

异步

和同步相对，同步是顺序执行，而异步是彼此独立，在等待某个事件的过程中继续做自己的事，不要等待这一事件完成后再工作。 线程是实现异步的一个方式，异步是让调用方法的主线程不需要同步等待另一个线程的完成，从而让主线程干其他事情。

  • Rust: async/await/tokio/async-std
  • Go: goroutines/sync.WaitGroup
  • Java: Future/CompletableFuture/parallelStream/RecursiveTask
  • C#: async/await/Task/BeginInvoke/BackgroundWorker
  • Python: async/await/asyncio
  • Node.js: async/await/Promise
  • Elixir: Task
  • Erlang: spawn

异步和线程

不是同等关系，异步是目的，线程只是实现异步的一个手段，实现异步可以采用线程技术或者交给其他进程来处理

进程/系统进程/平台进程

线程/平台线程/内核线程/系统线程

多线程是进程中并发运行的一段代码，能够实现线程之间的切换执行；应该被池化，利用线程池减少线程创建的开销。

  • 作用域值（Scoped Values）
  • IO密集型线程数量控制

线程数 = CPU核心数/(1-阻塞系数)

Blocking Coefficient(阻塞系数)（一般为0.8~0.9之间） = 阻塞时间/(阻塞时间+使用CPU的时间)

  • 计算密集型线程数量控制

CPU有超线程：线程数 = CPU内核线程数*2

CPU无超线程：线程数 = CPU核数+1

协程/纤程/绿色线程/虚拟线程/用户线程/微线程/轻量进程

协程（微线程、纤程、绿色线程、虚拟线程、用户线程、微线程）。是一种轻量级的用户态线程，实现的是非抢占式的调度，即由当前协程切换到其他协程由当前协程来控制。 协程本身可以做在用户态，每个协程的体积比线程要小得多，因此一个进程可以容纳数量相当可观的协程

  • coroutine解决的是"协作式多任务"
  • visitor（访问者）模式解决的是"对修改关闭，对扩展开放", "它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作"

Java语言并没有对协程的原生支持，但是某些开源框架模拟出了协程的功能，Project Loom AJDK-Wisp

信号量

进程间通信之-信号量semaphore (opens new window)

信号量的使用主要是用来保护共享资源，使得资源在一个时刻只有一个进程（线程）所拥有。

信号量的值为正的时候，说明它空闲。所测试的线程可以锁定而使用它。若为0，说明它被占用，测试的线程要进入睡眠队列中，等待被唤醒。

上下文切换

什么是进程、线程、协程 (opens new window)

进程的切换者是操作系统，切换时机是根据操作系统自己的切换策略，用户是无感知的。 进程的切换内容包括页全局目录、内核栈、硬件上下文，切换内容保存在内存中。进程切换过程是由“用户态到内核态到用户态”的方式，切换效率低。

线程的切换者是操作系统，切换时机是根据操作系统自己的切换策略，用户无感知。 线程的切换内容包括内核栈和硬件上下文。线程切换内容保存在内核栈中。线程切换过程是由“用户态到内核态到用户态”， 切换效率中等。

协程的切换者是用户（编程者或应用程序），切换时机是用户自己的程序所决定的。 协程的切换内容是硬件上下文，切换内存保存在用户自己的变量（用户栈或堆）中。协程的切换过程只有用户态，即没有陷入内核态，因此切换效率高。

多线程并不一定是要在多核处理器才支持的，就算是单核也是可以支持多线程的。

CPU 通过给每个线程分配一定的时间片，由于时间非常短通常是几十毫秒，所以 CPU 可以不停的切换线程执行任务从而达到了多线程的效果。

但是由于在线程切换的时候需要保存本次执行的信息，在该线程被 CPU 剥夺时间片后又再次运行恢复上次所保存的信息的过程就称为上下文切换。

  • 上下文切换是非常耗效率的。通常有以下解决方案:
  1. 采用无锁编程，比如将数据按照 Hash(id) 进行取模分段，每个线程处理各自分段的数据，从而避免使用锁。
  2. 采用 CAS(compare and swap) 算法，如 Atomic 包就是采用 CAS 算法。
  3. 合理的创建线程，避免创建了一些线程但其中大部分都是处于 waiting 状态，因为每当从 waiting 状态切换到 running 状态都是一次上下文切换。

# 缓存

  • 缓存穿透

在高并发下，查询一个不存在的值时，缓存不会被命中，导致大量请求直接落到数据库上，如活动系统里面查询一个不存在的活动。

  • 缓存击穿

在高并发下，对一个特定的值进行查询，但是这个时候缓存正好过期了，缓存没有命中，导致大量请求直接落到数据库上，如活动系统里面查询活动信息，但是在活动进行过程中活动缓存突然过期了。

  • 缓存雪崩

在高并发下，大量的缓存key在同一时间失效，导致大量的请求落到数据库上，如活动系统里面同时进行着非常多的活动，但是在某个时间点所有的活动缓存全部过期。

  • 缓存命中率

命中：直接从缓存中读取到想要的数据。

不命中：缓存中没有想要的数据，还需要到数据库进行一次查询才能读取到想要的数据。

  • 缓存丢失

常见解决方案

  • 直接缓存NULL值（时间不能过长，防止影响正常值）
  • 过滤器（如白名单，符合某种规则等）
  • 限流
  • 缓存预热
  • 分级缓存
  • 缓存永远不过期

常见算法

  1. Least Frequently Used (LFU)
  2. Least Recently Used (LRU)
  3. Least Recently Used2 (LRU2)
  4. Two Queue (2Q)

# 锁和事务

锁

单进程的系统中，存在多线程同时操作一个公共变量，此时需要加锁对变量进行同步操作，保证多线程的操作线性执行消除并发修改。 解决的是单进程中的多线程并发问题。

分布式锁

只要的应用场景是在集群模式的多个相同服务，可能会部署在不同机器上，解决进程间安全问题，防止多进程同时操作一个变量或者数据库。 解决的是多进程的并发问题。

事务

解决一个会话过程中，上下文的修改对所有数据库表的操作要么全部成功，要不全部失败。所以应用在service层。 解决的是一个会话中的操作的数据一致性。

分布式事务

解决一个联动操作，比如一个商品的买卖分为:（1）添加商品到购物车，（2）修改商品库存-1； 此时购物车服务和商品库存服务可能部署在两台电脑，这时候需要保证对两个服务的操作都全部成功或者全部回退。 解决的是组合服务的数据操作的一致性问题。

# 定时任务

分布式定时任务解决方案

  • 分时方案：严格划分时间片，交替运行计划任务，当主系统宕机后，备用系统仍然工作，但处理初期被拉长
  • HA（High Availability）高可用方案：正常情况下主系统工作，备用系统守候，心跳检测发现主系统出现故障备用系统启动
  • 多路心跳方案：
    • 采用多路心跳，做服务级，进程级的，IP和端口级别的心跳检测，正常情况是主系统工作，备用系统守候
    • 心跳检测主系统出现故障，备用系统启动，当再次检测到主系统工作，则将执行权交回主系统
  • 任务抢占方案：
    • A，B两台服务器同时工作，启动需要存在一前一后，谁先启动谁率先加锁，其他服务器只能等待
    • 他们同时对互斥锁进行监控，一旦发现锁被释放，其他服务那个先抢到，那个运行，运行前加排他锁。
  • 任务轮询或任务轮询+抢占排队方案：
    • 每个服务器首次启动时加入队列；
    • 每次任务运行首先判断自己是否是当前可运行任务，如果是便运行；
    • 如果不是当前运行的任务，检查自己是否在队列中，如果在，便推出，如果不在队列中，便键入队列

← 文档处理 →