# 相关

## MQ

### RocketMQ

阿里开源的纯java开发的消息中间件，纯java开发，具有高吞吐量，高可用性，适合大规模分布式系统的特点，是基于kafka开发的，对消息的可靠传输及事务性做了优化

### Kafka

#### 如何保证消息不被重复消费/如何保证消息消费的幂等性

对于数据库这种可以采用mvcc多版本并发控制的原理来实现，通过判断行的version来看是否消费过，对于订单来说可以通过唯一键id来判断，记录关键key，具体实际中还是得看业务需要

#### 如何保证消息的顺序性

如果想要保证全局有序，那么只能由一个生产者往队列发送消息，而且一个队列内部只能有一个分区，消费者也是单线程消费，不过一般不常用。

想要保证部分有序，可以将消息队列内部划分成我们需要的队列数，将消息通过特定的策略发往固定的队列，每个队列对应一个消费者，也可以发送到多个相同策略的队列，来提高并发

#### 如何处理消息积压问题

消息挤压主要是因为消费者消费能力跟不上所导致

首先检查是否是因为bug导致多次重试所挤压，其次检查消费逻辑是否可以优化，都没得改了后可以增加topic队列和新增消费者来提高效率，减少挤压

#### 为什么要用MQ？

（1）解耦：如果多个模块或者系统中，互相调用很复杂，维护起来比较麻烦，但是这个调用又不是同步调用，就可以运用MQ到这个业务中。

（2）异步：这个很好理解，比如用户的操作日志的维护，可以不用同步处理，节约响应时间。

（3）削峰：在高峰期的时候，系统每秒的请求量达到 5000，那么调用 MySQL 的请求也是 5000，一般情况下 MySQL 的请求大概在 2000 左右，那么在高峰期的时候，数据库就被打垮了，那系统就不可用了。此时引入MQ，在系统 A 前面加个 MQ，用户请求先到 MQ，系统 A 从 MQ 中每秒消费 2000 条数据，这样就把本来 5000 的请求变为 MySQL 可以接受的请求数量了，可以保证系统不挂掉，可以继续提供服务。MQ 里的数据可以慢慢的把它消费掉。

#### 什么是传统的消息传递方法?

传统的消息传递方法包括两种：
排队：在队列中，一组用户可以从服务器中读取消息，每条消息都发送给其中一个人。
发布-订阅：在这个模型中，消息被广播给所有的用户。

#### 解释Kafka的Zookeeper是什么?我们可以在没有Zookeeper的情况下使用Kafka吗?

Zookeeper是一个开放源码的、高性能的协调服务，它用于Kafka的分布式应用。
不，不可能越过Zookeeper，直接联系Kafka broker。一旦Zookeeper停止工作，它就不能服务客户端请求。
Zookeeper主要用于在集群中不同节点之间进行通信
在Kafka中，它被用于提交偏移量，因此如果节点在任何情况下都失败了，它都可以从之前提交的偏移量中获取
除此之外，它还执行其他活动，如: leader检测、分布式同步、配置管理、识别新节点何时离开或连接、集群、节点实时状态等等。

#### Kafka的设计时什么样的呢？

Kafka将消息以topic为单位进行归纳 将向Kafka topic发布消息的程序成为producers. 将预订topics并消费消息的程序成为consumer. Kafka以集群的方式运行，可以由一个或多个服务组成，每个服务叫做一个broker. producers通过网络将消息发送到Kafka集群，集群向消费者提供消息

#### Kafka消息是采用Pull模式，还是Push模式？

Kafka最初考虑的问题是，customer应该从brokes拉取消息还是brokers将消息推送到consumer，也就是pull还push。在这方面，Kafka遵循了一种大部分消息系统共同的传统的设计：producer将消息推送到broker，consumer从broker拉取消息一些消息系统比如Scribe和Apache Flume采用了push模式，将消息推送到下游的consumer。这样做有好处也有坏处：由broker决定消息推送的速率，对于不同消费速率的consumer就不太好处理了。消息系统都致力于让consumer以最大的速率最快速的消费消息，但不幸的是，push模式下，当broker推送的速率远大于consumer消费的速率时，consumer恐怕就要崩溃了。最终Kafka还是选取了传统的pull模式

Pull模式的另外一个好处是consumer可以自主决定是否批量的从broker拉取数据。Push模式必须在不知道下游consumer消费能力和消费策略的情况下决定是立即推送每条消息还是缓存之后批量推送。如果为了避免consumer崩溃而采用较低的推送速率，将可能导致一次只推送较少的消息而造成浪费。Pull模式下，consumer就可以根据自己的消费能力去决定这些策略

Pull有个缺点是，如果broker没有可供消费的消息，将导致consumer不断在循环中轮询，直到新消息到t达。为了避免这点，Kafka有个参数可以让consumer阻塞知道新消息到达(当然也可以阻塞知道消息的数量达到某个特定的量这样就可以批量发

#### Kafka的消费者如何消费数据

消费者每次消费数据的时候，消费者都会记录消费的物理偏移量（offset）的位置 等到下次消费时，他会接着上次位置继续消费。同时也可以按照指定的offset进行重新消费。

## ElasticSearch

### 介绍

是基于 Lucene 引擎构建的开源分布式搜索分析引擎，可以提供针对 PB 数据的近实时查询，广泛用在全文检索、日志分析、监控分析等场景。

它主要有以下三个特点:

- 轻松支持各种复杂的查询条件: 它是分布式实时文件存储，会把**每一个字段**都编入索引（倒排索引），利用高效的倒排索引，以及自定义打分、排序能力与丰富的分词插件等，能实现任意复杂查询条件下的全文检索需求
- 可扩展性强：天然支持分布式存储，通过极其简单的配置实现几百上千台服务器的分布式横向扩容，轻松处理 PB 级别的结构化或非结构化数据。
- 高可用，容灾性能好：通过使用主备节点，以及故障的自动探测与恢复，有力地保障了高可用


通过类比的形式不难看出 ES 的以下几个概念
*1、* MySQL 的数据库（DataBase）相当于 Index（索引），数据的逻辑集合，ES 的工作主要也是创建索引，查询索引。
*2、* 一个数据库里会有多个表，同样的一个 Index 也会有多个 type
*3、* 一个表会有多行（Row），同样的一个 Type 也会有多个 Document。
*4、* Schema 指定表名，表字段，是否建立索引等，同样的 Mapping 也指定了 Type 字段的处理规则，即索引如何建立，是否分词，分词规则等
*5、* 在 MySQL 中索引是需要手动创建的，而在 ES 一切字段皆可被索引，只要在 Mapping 在指定即可

### 那么 ES 中的索引为何如此高效，能在海量数据下达到秒级的效果呢？

最主要的原因是它采用了一种叫做**倒排索引**的方式来生成索引，避免了全文档扫描，那么什么是倒排索引呢，通过文档来查找关键词等数据的我们称为正排索引，返之，通过关键词来查找文档的形式我们称之为倒排索引，假设有以下三个文档（Document）


要在其中找到含有 comming 的文档，如果要正排索引，那么要把每个文档的内容拿出来查找是否有此单词，毫无疑问这样的话会导致全表扫描，那么用倒排索引会怎么查找呢，它首先会将每个文档内容进行分词，小写化等，然后建立每个分词与包含有此分词的文档之前的映射关系，如果有多个文档包含此分词，那么就会按重要程度即文档的权重（通常是用 TF-IDF 给文档打分）将文档进行排序，于是我们可以得到如下关系


这样的话我们我要查找所有带有 comming 的文档，就只需查一次，而且这种情况下查询多个单词性能也是很好的，只要查询多个条件对应的文档列表，再取交集即可，极大地提升了查询效率。

## 网络

### TCP与UDP的异同

TCP/IP是一个协议簇。UDP是其中一个，因为TCP/IP最重要，所用用其命名

TCP（传输控制协议）和UDP（用户数据报协议）都是在网络层，是传输层协议，都能保护网络层的传输，双方通信都需要开放端口

TCP特点：

- 传输是可靠传输
- 是基于连接的协议，在正式收发数据前，必须和对方建立可靠的链接
- 负载相对较大，采用套接字（socket）或者端口（port）来建立通信
- TCP包含序号、确认信号、数据偏移、控制标志等信息
- 提供超时重发，丢弃重复数据，校验数据，流量控制等功能，保证数据能从一端传到另一端
- 发送数据包前有三次握手机制，确保双方准备好，传输包期间，TCP会根据链路中数据流量大小来调节传送的速率，如果发现丢包，会有严格的重传机制，所以传输速度较慢
- 支持全双工（收发可以同时进行）和并发的TCP连接，提供确认、重传与拥塞控制

UDP特点：

- 传输是不可靠的
- UDP是和TCP相对应的协议，它是面向非连接的协议，它不与对方建立连接，而是直接把数据包发送出去
- 因为不可靠，所以负载较小
- UDP包含长度、校验和信息
- 它只把应用程序传给ip的数据报发出去，但是不保证能到达目的地
- 因为不用建立连接，也没有超时重发等机制，所以传输速度很快
- UDP适用对性能要求高于数据完整性的要求，如简短快捷的数据交换

### 网络各层结构与功能

TCP/IP四层协议，和折中的五层协议


- 应用层：通过应用进程间的交互来完成特定的网络应用，对于不同的网络应用需要不同的应用层协议，如域名系统的DNS协议；万维网的HTTP协议；电子邮件的SMTP协议。
- 域名系统简称DNS它可以将域名和ip地址相互映射，能够跟方便的访问互联网
- HTTP超文本传输协议，所有的www（万维网）文件都必须遵守，提供了一种发布和接受HTML页面的方法
- 运输层：负责向两台主机进程之间的通信提供通用的数据传输服务，主要使用以下两种协议
- 传输控制协议TCP：面向连接的，可靠的传输服务
- 用户数据协议UDP：提供无连接的，尽最大努力的数据传输服务
- 网络层：计算机网络中进行通信的两个计算机之间可能会经过很多数据链路，网络层的任务就是选择合适的网间路由和交换节点，确保数据及时传送
- 数据链路层：两台主机之间的数据传输，总是在一段一段的链路上传送的，这就需要专门的链路层的协议。
- 物理层：实现相邻计算机节点之间比特流的透明传送，尽可能屏蔽具体传输介质和物理设备的差异

### 三次握手

1. 客户端发送带有SYN标志的数据包，服务端确认了对方发送正常，自己接受正常。
2. 服务端发送带有SYN/ACK标志的数据包，客户端确认了自己一切正常，服务端不能确认自己发送正常
3. 客户端发送ACK标志的数据包，双方确认一切正常

客户端传回服务端发送的SYN是为了告诉服务端，我收到的是你发送的

### 四次挥手

1. 客户端发送一个FIN，告诉服务器已进入半关闭状态
2. 服务端收到后，返回一个ACK，告诉客户端已经收到
3. 服务器要关闭时发送一个FIN，告诉客户端服务器进入半关闭状态
4. 客户端回发ACK报文，表示确认收到，双端关闭

### 进程间的通信方式

- 管道/匿名管道（pipes）：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信
- 有名管道（name pipes）：有名管道严格遵循先进先出，以磁盘文件方式存在，可以实现任意两个进程通信
- 信号（signal）：信号是一种比较复杂的通信方式，用于通知接受进程某个事件已经发生
- 消息队列（message queuing）：消息队列是消息的链表，有标识符表示，存放在内核中，只有内核重启或者删除时，才会被真正删除。克服了信号承载信息量少，管道只能承载无格式字节流及缓冲区大小受限的缺陷
- 信号量（Semaphores）：是一个计数器，用于多进程对共享数据的访问，主要解决与同步相关的问题并避免竞争条件
- 共享内存（Shared memory）：使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新，是最有效的进程间通信方式
- 套接字（Sockets）：主要用于在客户端和服务器之间通过网络进行通信，套接字是Tcp/ip的网络通信最基本的操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单来说就是通信的两方约定

### 在浏览器中输入url后发生了什么


## Linux

### 常用命令

- ls：列出当前工作目录的内容
- ls -a：列出包括隐藏的文件
- ls -l：列出文件详细信息
- mkdir：新建文件夹
- pwd：显示当前工作目录
- cd：切换文件路径
- rmdir：删除给定目录
- rm：删除给定文件
- rm -rf：删除目录及其中所有
- mv：移动文件
- cp：复制
- cp -i：如果目标文件以存在进行提示
- cat：用于查看文件内容，顺序
- tac：同上，逆序
- tail：用于查看文件末尾，常用来查看日志
- more less 一页一页显示
- \> [filename]：情况日志文件内容
- awk：行处理器，通常用来格式化文本信息
- grep：擅长查找
- sed：取行和替换
- find：用来查找文件
- find 路径 参数 名字
- tar：创建提取tar压缩文件
- tar -cvf：创建压缩文件
- tar -tvf：查看压缩文件
- gzip：同上
- su：切换用户
- ps：显示系统运行进程
- top：默认按照cpu占用情况显示进程
- chmod：修改权限
- kill：结束进程

## 分布式

### CAP理论

- consistency（一致性）：所有节点访问同一份最新的
- Availability（可用性）：非故障节点在合理的时间内返回合理的相应
- Partition Tolerance（分区容错性）：分布式系统出现网络分区的时候，仍能对外提供服务

#### 网络分区

本来联通的多个节点，因为某些故障，比如节点网络出现问题，导致连不通，整个网络分成了几块区域，就叫网络分区

#### 3选2？

必须在分区容错性的基础上满足C或A，如果出现分区故障，c a二选一。因为如果出现分区后，为了保证c，需要禁止其他节点的读写，这就造成了和a的冲突，反之亦然。如果分区正常的话，不存在P的问题，所以ca能同时保证

#### 注册中心

负责服务地址的注册与查找，相当于目录服务，服务提供者和消费者只在启动时与注册中心交互，注册中心不转发请求，压力较小，常见的注册中心组件有：

- ZooKeeper：保证CP，任何时刻对ZooKeeper的读请求都能得到一致性的结果，但是，ZooKeeper不保证每次请求的可用性，比如在leader选举过程中或者半数以上的机器不可用的时候，服务就不可用
- Eureka：保证AP，不存在leader节点，每个节点都一样，只要有一个节点可用就行，不过数据可能不是最新

### BASE

- Basically Available（基本可用）：在分布式系统出现故障时，允许损失部分可用性，如：响应时间增加，非核心功能失效
- Soft state （软状态）：允许系统中的数据存在中间状态（cap理论中数据不一致的情况），并认为该中间状态的存在不影响系统整体可用性，允许系统在不同节点的数据副本进行同步时存在延时。
- Eventually Consistent（最终一致性）：强调的是系统中所有的数据副本，经过一段时间的同步后，最终达到一个一致性的状态。本质是需要系统保证最终数据能够达到一致

base理论是对cap中一致性c和可用性a权衡的结果，由cap演化而来，降低了对系统的要求

#### 核心思想

即使无法做到强一致性，但每个应用都可以根据自身特点，采用适当的方法来使系统达到最终一致性，如系统发生分区故障，在故障恢复后，系统应该达到最终一致性，这就是base理论

#### 分布式一致性的三种级别

- 强一致性：写入了什么，读出的就是什么
- 弱一致性：不一定可以读取到最新写入的值，也不保证多少时间后读到的值是最新的，只是会尽量保证某个时刻到达数据一致的状态
- 最终一致性：弱一致性的升级版，系统会保证在一定时间内达到数据一致性的状态

#### 最终一致性的实现方案

- 读时修复：读取时检测到不一致，就进行修复，检测到不同节点的副本数据不一致
- 写时修复：在写入时，检测数据的不一致时，进行修复，远程写数据的时候，如果写失败就缓存下来，然后定时重传，修复数据不一致性
- 异步修复：最常用的，定时对账检测数据一致性，并修复

## 数据结构

### 二叉树

每个结点至多只有两棵子树，有左右之分，次序不能颠倒

- 满二叉树：除最后一层无任何子节点外，每一层上的结点都有两个子节点，所有叶子节点必须在同一层上
- 完全二叉树：所有节点都集中在最左边


### 二叉查找树

又称二叉排序树、二叉搜索树

- 若左子树不空，则左子树上的结点的值均小于它的根节点的值；
- 若右子树不空，则右子树所有结点的值均大于或等于它的根结点的值；
- 左右子树也分别为二叉排列树；
- 没有键值相等的结点

对二叉查找树进行中序遍历，即可得到有序的数组

插入和查找的时间复杂度为O（logn）,但是在最坏的情况下就会有O（n）的时间复杂度，他的高度决定了查找树的查找效率

### 二叉平衡树

被称为AVL树，他是一颗空树，或者左右两个子树的高度差绝不超过1，并且左右两个子树都是二叉平衡树

通过树旋来重新平衡这个树，解决了二叉查找树在极端情况下退化成链表的问题，把增删改的最好和最坏情况都维持在O（logN）。但是频繁旋转会使插入和删除牺牲更多是时间，不过时间稳定了很多

### 红黑树

- 根节点为黑色，节点是红色或者黑色
- 每个叶子节点（为空的节点）是黑色
- 如果一个节点是红色，则它的子节点必须是黑色的
- 从一个节点到该节点的子孙节点的所有路径上，包含相同数目的节点

优势：

- 近似平衡，检索时效率差不多，但对于插入删除等操作效率提高很多。它允许局部不完全平衡，对效率影响不大
- 就插入节点导致树失衡的情况，二叉平衡树（AVL）和红黑树都是通过两次旋转来实现复衡；而删除导致失衡，AVL需要维护从被删除节点到根节点所有节点的平衡，而RB-tree只需选择三次，开销更小
- 因为AVL的结构相较于红黑树更平衡，所以查询效率更高，但红黑树是对增删改查效率的折衷解决方案，综合实力强，所以更合适hashmap。

### B树

### B+树

见mysql -- 索引 -- 索引结构

### Trie树

称为字典树，又称单词查找树，是一种树形结构，是一种哈希树的变种，用于统计排序和保存大量字符串。通过字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高

- 根节点不包含字符，除根节点外每个节点都只包含一个字符
- 从根节点到某一结点，路径上经过的字符串连接起来，为该节点对应的字符串
- 每个节点的所有子节点包含的字符都不相同