学习路线图

SPU

SKU

分布式锁

分布式事务

分布式调度中心

分布式配置中心

分布式序列号

分布式session

分布式存储

SSO服务

redis与JVM多级缓存

消息中间件消峰异步

限流策略

服务降级

风控防刷策略

性能调优

特点

请求体

返回体

accept 

application

content type

code type

host

authorities权限

cookie

SOAP

XML

JSON

protobuffer

作用：通过非对称加密方式让服务端拿到客户端随机密码，用于后续的通信用的对称加密密钥

服务器端不应该保存状态

阻塞住业务线程

多路复用io模型，一般是阻塞在selector上

单纯底层是不会存在同步非阻塞的，因为业务线程是在不断轮询，很耗CPU

操作系统层面支持，通知机制，操作系统完成了数据内核空间到用户空间的靠背

引入异步通道，目前使用少

场景： 数据库读写库同步数据

从被调用着看，阻塞只被调用着会挂起调用着线程，让调用着释放CPU使用权

调用者角度看，调用者只做一件事，等待结果，或者一直轮询查结果

调用者角度看，调用者做别的事情，等待被调用者通知结果

单reactor单线程

单reactor多线程

主从reactor多线程

多路复用的方式，将监听链接为acceptor模块，处理消息业务handler模块 分开

父进程没有退出，父进程没有调用 wait / waitpid 回收子进程控制块，导致子进程成为僵尸进程

如果父进程死掉了，子进程会被init守护进程管理，init进程会回收子进程

类的加载

类的链接

类的初始化

bootStrapClassLoader

ExtersionClassLoader

SystemClassLoader

ApplicationClassLoader

自定义加载器

保证加载的类是唯一的，只会有一份，所以向上由父类加载

与Tomcat不满足双亲委派

adf存在于方法区的常量池，栈空间的a直接指向常量池的adf

adf存在于常量池，堆空间生成对象，对象实际存储指向常量池adf的地址，栈空间的b指向堆空间的地址

c和d栈都指向常量池的adfdf，e保存了堆中对象，对象指向的是常量池中的adfdf值

直接常量操作，返回的地址是在常量池

经过new或者不是纯常量操作，会进行一次new在堆中生成对象，对象在指向常量池中数据

final修饰的String也在常量池

出于安全考虑，java很多类都用字符串来描述

处于内存考虑，字符串被常用，共享同一块内存，减少内存使用量

1. 转成数组，toCharArray()

2. 数组操作变化值

3. String构造函数数组转为字符串

返回字符串的实际长度，字符串没有size()方法

享元模式，池的技术

-128 ~ 127 是常量，在堆中只会有一个对象

修饰注解

@Retention

@Target

@Inherited

java8新特性

数组

collection

map

集合相关的静态方法集

自然排序：实现comparable重写compareTo(Object o)方法

定制排序: 实现comparator重写compare(Object o1,Object o2)方法

返回的是元素的个数，集合是没有length方法的

toArray()  集合变数组

Arrays.asList（） 数组变集合

for循环

iterator迭代器

foreach方式

java8新特性，streem流

List<?>

拿到运行时对象的类信息

根据运行时对象信息创建对象

根据运行时对象信息使用其方法

根据运行时对象信息修改成员，修改私有成员

动态代理

类名.class

对象.getClass()

Class类的静态方法forName()

ClassLoader对象的loadClass()方法获取

Constructor 拿到类的构造函数，实例化对象

Field 拿到类的属性

Method 拿到类的方法

尽量不要getMethods()后再遍历筛选，而直接用getMethod(methodName)来根据方法名获取方法

forName获取类对象，使用缓存

接口中只有一个抽象函数

可以用注解声明接口，@FunctionInterface

util.function包下有大量的函数式接口

基本数据类型比较 值

引用类型比较地址

比较的是引用类型

重写过的equals比较的是地址，object的原生方法比较的是地址

mark word

类型指针

实例数据

对齐

mark word

类型指针

数组长度 length 4字节

实例数据

对齐

二级缓存 -> 一级缓存 -> 数据库

二级缓存是跨SqlSession的

一级缓存是SqlSession级缓存

#将传入的数据都当成一个字符串，会对自动传入的数据加一个双引号

#可以防止sql注入

$将传入的数据直接显示生成在sql中

控制反转

bean(默认是单例)

怎么解决循环依赖的？

哪种循环依赖不能被解决？

依赖注入

切面编程

横切，将同一个代码切入多个业务逻辑，减少代码量，代码结构清晰；增强功能

结构

隔离级别依赖数据库的隔离级别

事务传播行为

@Transaction底层实现-----AOP

视图解析

自动配置

内嵌web容器，打包成jar包，不用打包成war包

starter场景启动器，自动版本控制

运行时监控，与云计算的集成

@bean注解

@Cacheable

@Configuration

@ConditionalOnClass()

@SpringBootApplication

@EnableAutoConfiguration 开启自动配置

获取配置值

profile

自动配置原理

1 自己添加配置的bean到容器，使用@bean注解 @Component

2. 编写配置类，WebMvcConfigureAdapter，扩展MVC

3. Spring boot有很多 XXXConfigurer 帮助进行扩展配置

1. 浏览器：默认错误页面，客户端：默认错误json

2. 参考 ErrorMvcAutoConfiguration，错误处理默认配置

修改容器配置

切换容器：

容器启动原理

加入了spring5的 webflux 响应式web编程

webflux是 非阻塞IO 多路复用

MVC 本质是同步阻塞IO

run方法不会抛异常

需要Thread的start方法启动多线程

java只能单继承，所以扩展收到限制

future拿到返回值

call方法会抛异常

需要Thread的start方法启动多线程

set()往里面放数据

get() 从里面取当前线程的数据

使用完get和set后要用remove去除 内部map的key与value的引用关系，因为 key是弱引用，下次gc的时候被回收，导致value会被线程长期持有，造成内存泄漏

保证可见性

不保证原子性

禁止指令重排

可见性  主内存 线程工作内存

原子性

有序性质

单例模式的double check （禁止了指令重排）

代理模式

工作内存与主存数据比较一样的时候修改，不一样的时候重复读取主存，跟新工作内存数据

CAS底层，unsafe的理解

CAS缺点

是什么：公平锁只等待锁的线程按先来先得顺序得到锁

两者区别： 公平锁按FIFO的等待队列等待锁，锁操作耗时

ReentrantLock默认是非公平锁，synchronize是非公平锁

Synchronize ，每个对象的头部markword字段有标志标志，monitorenter 和 monitorexit 指令来实现同步的，monitor管程来控制

头部mark word字段，有锁状态，是否偏向锁，锁标志

JVM级的不需要业务代码控制

偏向锁的核心思想是，如果一个线程获得了锁，那么锁就进入偏向模式，此时Mark Word 的结构也变为偏向锁结构，当这个线程再次请求锁时，无需再做任何同步操作，即获取锁的过程，这样就省去了大量有关锁申请的操作

是什么：同一个线程外层函数获取锁后，内存递归函数仍然能获得锁

ReentrantLock和Snychronize是典型的可重入锁

底层实现原理，ReentrantLock是AQS同步队列，Snychronize是锁住的对象头部字段记录的标志，在monitor中会做计数

SpinLock，短时间的自旋，不会释放CPU

ReentrantReadWriteLock

写的时候排他，读的时候共享排他写锁

偏向锁-> 轻量级锁 -> 自旋锁 -> 重量级锁

让一些线程阻塞，知道一些线程完成操作

一些线程执行await()阻塞，一些线程完成操作后执行CountDown()减数

案例：等待人到齐，才开会

一些线程阻塞在一个点，然后同时进行

await()方法阻塞

案例: 跑步比赛到齐开始

用于并大资源数量的控制，同一时间只能有固定数的线程进入临界区

案例：抢车位

阻塞队列空的时候，从队列获取数据的线程会被阻塞

阻塞队列满的时候，往队列放数据的线程会被阻塞

不需要关心什么时候阻塞线程，什么时候唤醒，阻塞队列帮处理了

抛异常

返回特殊值

一直阻塞

超时退出

ArrayBlockingQueue基于数组的有界

LinkedBlockingDeque基于链表的有界，默认界值很大

SynchronousQueue同步队列，不存数据，生产一个消费一个

PriorityBlockingQueue 有优先级的无界阻塞队列

delayQueue 延迟无界阻塞队列

LinkedTransferQueue 链表结构的无界阻塞队列

LinkedBlockingDeque链表结构阻塞双端队列

生产者消费者模式

线程池

消息中间件

充分利用CPU

减少频繁创建线程的性能消耗

自定义线程池，继承ThreadPoolExecutor

线程池函数

corePoolSize 线程池的常驻核心线程数

maximumpoolSize线程池能够容纳的最多线程数

keepAliveTime 多余核心线程数的空闲线程的最多存活时间

unit keepAliveTime的单位

workqueue 任务队列，提交到线程池还未处理的任务

threadFactory 线程池中线程的工厂，用于创建线程

handler 拒绝策略，任务丢列满，线程数达到最大时，做的处理

创建线程池后等待提交任务

调用execute添加任务，线程池做的判断：

当一个线程任务处理完，会从任务队列中取下一个任务执行

当一个线程空闲时间超过keepAliveTime时候，线程池处理

AbortPolicy 直接抛出异常RejectedException，阻止系统运行

CallerRunPolicy 由提交任务的业务线程处理

DiscardOldestPolicy 抛弃队列中等待最久的任务，然后把最新的任务加入任务队列

DiscardPolicy 直接丢弃任务，不予处理，也不抛出异常，允许任务丢弃

使用自定义线程池

executors线程池问题： 1. 默认使用链表有界阻塞队列，界很大，导致内存溢出
2. 缓存调度线程池会创建大量线程导致资源占用大

CPU密集型操作: cpu核心数+1

IO密集型操作：2xcpu核心数

系统资源不足

资源分配不当

线程执行顺序不合适

线程互斥，资源持有等待，不可剥夺

多线程共享

多线程私有，拷贝的主内存

Java内存模型中定义的两项操作之间的偏序关系，如果操作A先行发生于操作B，其意思就是说，在发生操作B之前，操作A产生的影响都能被操作B观察到

Java内存模型中定义的两项操作之间的偏序关系，如果操作A先行发生于操作B，其意思就是说，在发生操作B之前，操作A产生的影响都能被操作B观察到

具体规则：

1/3 新生代

2/3的老年代

静态集合添加很多数据

类内部方法，有new大对象，长期持有

大对象

代码太多

引用第三方库太多

深度递归

对线数太多

-Xss参数太大

netty使用

一般栈变量引用的对象，不会被回收对象

SoftReference修饰使用的，一般不会回收，在内存不够用的时候会被回收

WeakReference修饰使用的，一般两次垃圾回收会被回收内存

PhantomReference修饰使用的，内次垃圾回收都会被回收对象

执行流程：初始标记 STW，并发标记，重新标记STW，并发清理

使用算法：标记清理

串行 serial copy （复制）

并行 ParNew （复制）

并行回收Parallel  /  parallel Scavenge （复制）

串行 serial Old （标整）

并行 Parallel Old （标整）

并发 标记清理 CMS (和Serial Old联合使用) （标清）

场景：服务端垃圾收集，应用于多处理器和大容量内存环境，高吞吐的同时尽可能的满足垃圾收集暂停时间的要求

特点：

内存区域划分

收集过程 小区域收集+产生连续的内存块

执行过程

常配置参数

与CMS比较

序执行了System.gc() //建议jvm执行fullgc，并不一定会执行

jmap -histo:live pid命令 //这个会立即触发fullgc

minor gc的时候进行的一系列检查

用了大对象 //大对象会直接进入老年代

程序中长期持有了对象的引用 //对象年龄达到指定阈值也会进入老年代

查找报警对应的进程  ps -ef|grep XX

查看Gc情况

Dump文件分析

查看内存文件

jstack Dump 日志文件中的线程状态

准备

执行分析：   ./ParseHeapDump.sh m.hprof org.eclipse.mat.api:suspects org.eclipse.mat.api:overview org.eclipse.mat.api:top_components

mat目录下会生成3份.zip结尾的报告和一些m.相关的文件，将生成的m.hprof相关的文件都下载到windows本地磁盘

浏览器打开index.html文件内容，查看分析报告

查看Class Histogram一项

-XX:+PrintGC 打印GC信息

-XX:+PrintGCTimeStamps 打印GC时间

-XX:+PrintGCDetails 打印GC详细信息

-XX:+PrintGCApplicationStoppedTime 打印GC时程序暂停时间

-XX:+PrintGCApplicationConcurrentTime 打印GC中程序未暂停时间

-XX:+PrintHeapAtGC GC前后堆栈信息

-Xloggc:filename GC日志入文件

XX:+PrintTenuringDistribution miniGC存活阀值

-XX:+UseParallelGC  年轻代并行，老年代串行

-XX:+UseParNewGC 设置年轻代未并行

-XX:ParallelGCThreads 并行收集器的线程数

-XX:+UseParallelOldGC 设置老年代为并行收集

XX:MaxGCPauseMillis 年轻代垃圾收集的最长停顿时间

-XX:+UseConcMarkSweepGC 使用CMS收集器

-XX:CMSFullGCsBeforeCompaction CMS多少次后进行内存压缩

-XX:+UseG1GC 使用G1收集器

-Xms 初始堆大小

-Xmx 最大堆大小

-Xmn 年轻代大小

-XX:NewSize 年轻代大小

-XX:MaxNewSize 年轻代最大值

-XX:PermSize 持久代初始值

-XX:MaxPermSize 持久代最大值

-Xss 线程栈大小

-XX:NewRatio 年轻代与老年代的比值

-XX:SurvivorRatio Eden区与Survivor的比值

-XX:LargePageSizeInBytes 内存页的大小

-XX:MaxTenuringThreshold 垃圾最大年龄

-XX:SoftRefLRUPolicyMSPerMB 软引用存活时间

-XX:PretenureSizeThreshold 大对象再老年代生产

-XX:+CollectGen0First FullGC时是否先Young区收集

查看每个cpu核的负载信息

cpu的空闲率，数字越大越好

进程id

进程的执行命令名

系统的平均负载

有三个数据，分别是1分支，5分钟，15分钟的负载值

上面三个数相加 / 3 * 100% 超过了60%，表示系统负载

r

b

us

sy

查看内存

-h可以让参数有单位

每2秒刷一次，共3条数据

%util :表示io情况，越大说明越差

r/s

w/s

1(文件类型) + 3（用户的rwx）+ 3（用户组用户的rwx） 3(任何用户rwx)

0.0.0.0:80 表示端口可以被外部访问

127.0.0.1:80 表示端口只可以被本地访问

-m 显示所有线程

-p 进程的cpu时间

-o 按格式输出

一个系统拆分成多个子系统 （并行，每次都被用到）

一个系统部署多份 (串行,每次只用一个)

多个线程线程数大于CPU核心数

多个线程数等于CPU核心数

Nginx反向代理

LVS/F5 负载均衡多个Nginx

DNS负载均衡

后台系统朝外部请求，经过的代理

内部服务只看到一个地址，正向代理将请求路由到目标地址

外部请求到反向代理，外部请求只看到一个代理

反向代理将外部请求分发到后台多个服务机器上

四层反向代理

七层反向代理

ehcache

guava cache

集合

在消费者端做的缓存

单机

哨兵

集群

RDB

AOP

缓存穿透

缓存击穿

缓存雪崩

热点key(缓存击穿)

索引相当于mysql的库

每个索引可以设定分片数，默认是5个 primary shard

每个primary shard 可以设置制定指定个replicate shard副本分片(根据机器数决定，至少一个副本分片)

副本分片的作用是实现冗余数据实现高可用，在primary主分片挂了后，副本分片会被升级为主分片；还有一个作用是支持查询不支持写，提升的并发能力

分片的目的是将document文档分块的存在不同的集器上，实现存储分布式

副本shard 可以提供数据读不可以写，从而提升集群的性能

documentid 可以手动生成也可以自动生成，routing_id来做分片，没有设置默认用documentid主要用来分片

元数据库中数据以及由唯一的id，导入es的时候可以作为es的documentid

主primary shard 先写 buffer缓存 -> 1秒 refresh 进os cache + 同步追加写trancelog日志 -> 30分钟或者trancelog日志太大进行commit操作，flush内存数据进磁盘 segment file新文件  ->  当segment file文件多到一定程度，进行merge操作，将多个segment file文件合并为一个，并删除.del文件 （删除的数据标记在.del文件）

将被搜文档的分词提取出来，将包含关键分词的文档路径归属到当前分词关键字

主节点 （存储了集群的元数据，管理集群，可以配置存数据也可以不存数据）

数据节点 

协调节点 

9300端口上，自动加入集群，配置统一的集群名称

查询birth字段不存在数据

表无结构限制

索引

高可用

数据非分布式存储 ，数据量受限于单台机器容量

数据分布式存储

分布式，可扩展，海量数据的，非关系型数据库，做大表；数据量越大使用性价比越好

基于HDFS的，支持随机写

逻辑上类似mysql的表结构，实际数据存储是key-value的

结构：

数据模型

架构

DDL

DML

本身是分布式高可用的

建表预分区

rowkey设计原则

内存优化

MR

Hive

Innodb

MyISAM

联合索引

索引数据结构 B+数

聚集索引/非聚集索引

覆盖索引

四大特性

隔离级别

锁分类

最大可以达到 2000w条

500w~1000w之间  300w会有性能问题

数据量到2G

mysql-sharding

mycat

垂直分

水平分

binlog日志同步数据

binlog日志格式

方案步骤：sql优化 -> 索引优化 -> 分区 -> 读写分离 -> 缓存 -> 集群 -> 向上扩展 -> 分库分表 -> nosql 大数据

explain分析

开启慢查询日志 （最好不要在生产开启）

profile分析

数据模型优化

DBA运维 数据库实例配置参数优化

图数据库

数据以节点和关系来存储的

基于jvm的 非关系数据库

关系数据库多对多的查询性能的下降，空间的浪费

数据的复杂关系 （人脉网络，交通网络）

有管理界面

支持事务 ACID

有图查询语言  cypher语句

高性能

高可用集群

复杂的数据模型

节点

关系

路径

CREATE

MATCH

RETURN

WHERE

DELETE

REMOVE

SET

ORDER BY

UNION

LIMIT 和 SKIP

MERGE

IN

Exists

仅订阅

仅注册

基于观察者模式的服务管理框架， == 文件系统+通知机制

特点

数据结构

应用场景

配置参数

选举算法过程

监听器原理

部署架构

CP模式

节点类型

数据节点类型

数据操作

state结构体

写数据过程

选举算法

状态同步算法

部署架构

AP方式

部署架构

减少系统的耦合

加快系统响应

系统高峰期，请求留存在消息队列

高可用

存在丢消息

功能完善

ms级，万级吞吐

社区不活跃

万级吞吐，Elang语言开发，性能好，延迟低

社区活跃

功能强大的管理界面

十万级吞吐，功能完备

阿里出品，java语言开发

topic可以达到很多个

十万级吞吐

mq功能简单

容量易扩展

做持久化

集群每个节点都一样，没有主从之分，存储是分布式的

用于消息的分类，逻辑上的概念

消息格式

partition 实现分布式存储  一个topic的消息会被分到多个partition

同一个topic 只能被同一个组的消费者消费

按消费者组+ topic+ partition维度维护的offest

https://zhuanlan.zhihu.com/p/82998949

保证消息不丢失，不能保证不重发

kafka 内部保证幂等性，存数据的时候做去重 （0.1版本解决的，0.11版本支持事务）
配置参数 enable.idompotence = true

pull

push

一个消费者组中的消费者只能消费一个partition
如果消费者小于partition的时候，会做轮询消费------限制条件当前消费者组只能消费一个主题

自动回写offset 大概1秒，程序自己回写offset，自己回写offset保证消息不丢

没有被消费的消息，kafka默认存7天

保证消息的消费幂等性，不重复消费

发布订阅的设计模式

多副本

强一致

多租户

持久形和非持久形

非分区topic(默认)

分区topic

生产者是关联到topic的程序，它发布消息到Pulsar的broker上。

MessageListener接口。在这个接口中，一旦接受到新的消息，received方法将被调用

exclusive

Shared

Failover

单机

伪集群

镜像集群

事务

confirm模式

可能有重复消息，只能保证不丢，不能保证重发

自动响应ack

程序响应ack

mq收到消费者回写的ack后会删除消息

用起来考虑的点多，容易死锁或者锁不住 。集群中出现问题时使用 redLock 模式。

简单，session断可能导致锁不住

TM 事务控制

RM 资源控制

 AP 应用

2pc是强一致的，数据库层的事务

过程

数据库资源层的锁占用事务控制

在2pc基础上引入超时，防止阻塞

人肉回滚

对业务渗入

不在意RM模块是否支持本地事务

引入中间状态

try准备

confirm确认

cancel回滚

尽最大努力通知

TCC两阶段补偿

可靠消息最终一致

具有不同标志

当一个对象用于对事物进行描述而没有唯一标识时

负责来协调这些领域对象完成操作而已，那么我们可以归类它们为领域服务

定义领域对象之间清晰的所属关系以及边界来实现领域模型的内聚，以此来避免形成错综复杂的、难以维护的对象关系网

创建对象

把对象的存储和访问都委托给资源库来完成

常用方法

持久层 orm 映射，持久对应实体

熔断关闭

熔断开启

半熔断状态

接口层的限流，令牌桶，漏桶，信号量

限制接口的线程数，通过队列缓冲

消息队列，令牌，漏桶，滑窗

并发数限流

QPS限流

范围： 单机限流、集群限流

RateLimiter (令牌桶)

sential (滑窗)

部分不可用

全部不可用

延迟可用

随机拒绝访问

xml

json

dubbo

hanssion

protobuf

thrift

固定时间内，接口超时或者失败次数，达到一定比例，进行熔断措施

到恢复时间，会先开放一半流量恢复请求，无问题后，全开

timeout：方法调用超时

retries：失败重试次数，默认重试 2 次

loadbalance：负载均衡算法，默认随机

actives 消费者端，最大并发调用限制

缺省会在启动时检查依赖的服务是否可用，不可用时会抛出异常，阻止 Spring 初始化完成，默认 check="true"，可以通过 check="false" 关闭检查。

推荐使用Hessian序列化，还有Duddo、FastJson、Java自带序列化。

Dubbo 默认使用 Netty 框架，也是推荐的选择，另外内容还集成有Mina、Grizzly。

配置环境点对点直连，绕过注册中心，将以服务接口为单位，忽略注册中心的提供者列表

一个接口有多种实现时，可以用 group 属性来分组，服务提供方和消费方都指定同一个 group 即可。

可以用版本号（version）过渡，多个不同版本的服务注册到注册中心，版本号不同的服务相互间不引用

默认是同步等待结果阻塞的，支持异步调用

使用 Pinpoint 和 Apache Skywalking(Incubator) 实现分布式服务追踪，当然还有其他很多方案。

控制台主要包含：路由规则，动态配置，服务降级，访问控制，权重调整，负载均衡，等管理功能。

-a 全部分支

-r 远端分支

-D 删除本地分支

--all  添加全部目录

-u 是建立关联

-f 是强制推到分支，覆盖之前的提交

git init

增加.gitignore

git add README 添加文件

git commit -m 'first commit'

git remote add origin git@github.com:linuxhex/dgraph-test.git

push

f8单步

f9 跳到下个断点

ctrl+shift+c mvn清理clean

ctrl+shift+b mvn编译compile

编译打包，不部署本地仓库和远端私服

编译打包，部署到本地仓库，不部署到私服

编译打包，部署到远端仓库和私服

说明依赖的包，没有下载成功

语言 -> 功能模块 -> 框架

类内部成员表示

类之间关系

单一原则

开闭原则

里氏替换

接口隔离

迪米特法则

依赖倒转

合成复用

创建型

结构型

行为型

先进先出

先进后出

数组实现栈

顺序存储

稀疏数组

数组实现环形队列

链式存储

存在：带头节点和不带头节点的链表

单链表： 查找方向只有一个

双向链表：可以实现节点自我删除

跳跃表： 

左孩子节点小于根节点，根节点小于右孩子节点

会退化成数组

根节点比左右孩子节点都大

根节点比左右孩子节点都小

是二叉排序树

左右子树的高度差为1

多用于内存存储，需要排序的结构

加入红黑节点，减少了平衡二叉树的平衡操作次数，提升性能

n个权值作为n个叶子节点

WPL带权路径长度最短

权值越大离根越近

用于数据压缩

区别：

多用于磁盘存储

多路查询树

b+比b的优势，排序范围查找

多hash算法的筛选

hash环映射，一个点坏了，最坏只有一个区数据需要调整

冒泡

快排

插入

选择

希尔

堆排

桶排序

计数

基数排序

有序无序

有序

需要记录部分匹配表

字符串1和字符串2 字符串匹配

时间复杂度O(n+m)

空间复杂度O(1)

最短路径 A*算法

以起点为出发点，进行广度优先

解决子问题的过程中得到主问题的解, 有可能前面两步的结果可以算出本次结果

时间复杂度O(n)

空间复杂度O(1)

节点个数

是否有环

约瑟夫

倒数第k个节点

单链表反转

从尾到头打印单链表

汉诺塔

迷宫

最短路劲

八皇后

马踏棋盘

深度遍历

计算 5+ 6 * 3

经纬度划分网格：按照桶排序的思想，经度范围划分多个桶，维度范围划分多个桶；根据经纬度所在的桶缩小范围

多变量占用空间，用一位表示一个

无序数组，第k大的数

基于HDFS和MR

基于HDFS计算数据

迭代式计算

基于内存的计算，可以扩展

和hadoop联合使用，只用hadoop的存储模块

内核

YRAN调度器

Spark SQL

Spark Stream

Spark 机器学习

Spark 图像处理

driver 计算调度

Excutor 计算执行

local

source

channel

sink

Flow消息流

Event 消息处理的最小单位

Agent 一个独立的Flume进程

source 以event为单位接受消息

Channel 缓存信息，确保消息被sink消费的前不会丢失

Sink 从channel中拉去数据并处理

Interceptor 是event的拦截，可以修改或者丢弃event

filebeat

logstash

flume

致命弊端：不支持分布式存储

分布式存储

部分开源

go开发，潜力最好

支持PB级别的数据量查询

优点： 有类似neo4j的管理界面

风险：小公司在推，文档上，存在风险

分片存储

完全开源

本身不是数据库，依赖于其他组件，橡一个框架

缺点：依赖组件多，增加运维成本，排查问题的成本

优点：相对来说国内商用的比较多，网上资料多

分布式存储

单点计算

完全开源技术门槛高

依赖的东西多，像一个框架

衍生自Titan的一个分支

逻辑回归

SVM

流形

PCA