高级数据结构和算法概念

[lewenweijia]

// Trie树
字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序
和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点
是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树
高。
// tips
查询效率比哈希树高
相对hash, 核心思想是空间换时间

[lewenweijia]

// 各类树的比较
 AVL树:  最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。
 红黑树: 平衡二叉树，广泛用在C++的STL中。如map和set都是用红黑树实现的。
 B/B+树: 用在磁盘文件组织 数据索引和数据库索引。
 Trie树(字典树): 用在统计和排序大量字符串，如自动机。

分而治之/hash映射 + hash统计 + 堆/快速/归并排序；
双层桶划分
Bloom filter/Bitmap；
Trie树/数据库/倒排索引；
外排序；
分布式处理之Hadoop/Mapreduce。

// 上深下高
深度是叶子无关, 根到某一处
高度是根无关, 某一处到叶子

[lewenweijia]

大数据问题常用技巧和数据结构
哈希
位图
取模(切分多个, 然后多路归并)
trie树
布隆过滤器

[lewenweijia]

// 常见问题类型
大数据处理时候的内存不足场景

[lewenweijia]

// 排序理解深入
快排?: 分区(随机数法?: 防止退化成O(n^2) + 原地 + 递归(要防止调用栈溢出)
 O(n^2)问题? -> 选择区间后, 一边的元素基本全部转到另外一边...
归并?: 稳定(复杂度能做到平均的ologn) + 非原地 + 翻倍的空间消耗

// 实际案例:
c语言中的qsort函数与中才用到的排序?: 插入排序 | 归并排序 | 快速排序
(分区点选择采用三数取中法, 堆上手动维护栈防止递归过深爆栈)

大数据情况下比快排/归并, 更快的排序方法的啊
快排/归并 -> 能达到基于比较的理论最优时间复杂度: O(nlogn)
桶排/基排/计排 -> 达到更优的O(n), 非基于比较, 对排序的数据条件要求十分苛刻
采用外排序(内存外, 即涉及内存不足, 无法一次性全部加载到内存, 部分存储在硬盘中)

// 线性排序算法的优化

// 快速排序的优化
1. 分区点选择?: 三数取中法/随机数法
2. 递归过深导致栈溢出?: 堆上手动维护栈, 手动维护出栈, 入栈

[lewenweijia]

// 时间复杂度?:
O(1): 棒极了!
O(logn): 很棒, 二分
O(n): 不错, 线性查询
O(nlogn): 可以, 归并/快排
O(n^2): 可怕, 可以接受的极限了, 再下去可以去财务那里结算工资了
O(2^n): 天啊
O(n!): ....

[lewenweijia]

// 底层相关
线程的切换? -> cpu需要对负责过的线程进行上下文的保存,下一个服务线程的状态初始化/旧状态的
恢复加载的呢 所以开销还是很可观的

[lewenweijia]

syn位就是为ISN进行护航的效果的啊

数据链路层的有效载荷为1500Byte,
所以tcp的有效载荷是1500 - 20(ip头) - 20(tcp头) = 1460byte
]
tcp段
ip包
数据链路层帧(帧的最大有效载荷是1500的啊, 除去链路层的头和尾)

netstat -i?: 查看网络接口(网卡信息), 可以查看网卡支持的数据链路层的MTU的哦)
netstat --tcp?: 查看本机进程-端口号的映射表的效果的啊

wifi和网络插口都是1500的啊

ping的话, -> 直接丢icmp包过去的效果的啊, 哈好

不让ip动用分段的操作的啊, 节省资源的哦

包体? -> 有效载荷的啊
TCP包体大小 = 1500(以太网MTU) - 20(IP固定20) - 20(TCP固定20) - 12(TCP可选头部) = 1448

TSO -> 网卡代替cpu实现packet的分段和合并的啊, 节省系统资源

tcp三阶段?
1. init
2. i/o
3. close

MSS就是为了防止IP层分段的啊, IP层的分层是十分没有效率的哦. 哈哈
 -> **若ip层的分段发现丢失的时候, 所有报文都是要重新重传的效果的啊!!***

这台服务器可能非常繁忙, 操作系统内核的tcp栈模块的可用内存不够了, 那么通过流控来降低大小的啊
或者还来不及将已经到达的数据, 从内存中读取出来的啊

如果服务器那边繁忙的呢, 处理不来那么多的数据的啊

端口是用来区分一台主机上的应用程序服务的啊

单纯控制包(不带数据) -> SYN + FIN包都是需要消费一个序列号的啊, 包头包尾的呢, 哈哈
消耗一个序列号, 因为tcp的确认机制就是通过消费序列号来的的呢

mss 分类 (告知接收端我的最大报文段大小是)
SMSS?: 发送端mss
RMSS?: 接收端mss

MSS? tcp的包体大小
tcp 20 字节的固定长度头

tcp三次握手的连接建立协商阶段的效果的啊, 哈哈, 厉害了的哦

1. 我们应用层向tcp层发的是一个流
2. 但是我们tcp开始分段了的啊

[lewenweijia]

三次握手的连接的建立信息协商的啊
执行完操作才进行状态更新的效果的啊.!

三次握手双端的状态变化?:
(CLOSED)                (CLOSED)
                                         (LISTEN)
(SYN_SEND)   SYN->      (SYN_RCVD)
             SYN+ACK<-  
(ESTABLISH)  ACK->      (ESTABLISH)

 成功交换连接初始化信息后, 就自然进入`established`状态的啊, 无关谁先发

不管是三握还是四挥? -> 都是被动关闭方接受最后一个ack包的啊, 主动关闭方发送最后一个ack包的啊 
 -- > 假想倒数第二个包在网络中迷失, 被动关闭方超时尝试重传!

客户端得接收到最后一个fin才能进入`time-wait`状态的啊

[lewenweijia]

有意思的啊, 故意不回ack, 让你那边一直retries, 哈哈, 有点浪费资源!

四次挥手可以变成三次吗
反过来, 三次握手可以弄成四次吗?
理论可以 -> 满足数据交换就可以了的啊. 就拿 四次挥手变三次

半连接(syn queue)/全连接(accept queue) -- > 半连接/全连接队列(服务端调用listen创建服务时候)
  -同步队列 / 接受队列
半关闭/全关闭

接受到syn包, 将该连接放入半连接队列并回复seq+ack, // 若成功收到ack包, 移入accept队列
满足条件, 是有效连接, 可以被上层进行消费(上层调用accept( ) 函数来取出有效连接)

accept队列中包含所有完成三次握手的连接!, 还未被应用取走的连接的啊
若accept队列满的状态(listen的backlog定义大小), syn队列中的半连接的ack会被舍弃
 => 模拟, 创建listen, 就是在程序main.c中不调用accept的啊, 哈哈,故意让accept队列处满的状态

各种的实际已排队连接的啊

syn队列中的半连接
accept队列中的全连接(完成三次握手的连接, 等待被应用取走消费)

[lewenweijia]

客户端的syn包发送后, 经历多次重传后, 发现还是没打入服务端的accept队列, 该连接无希望, 
系统回收释放资源??

accept队列满状态, syn队列有item来了个ack, 否决, 无达成确认. 因为synack包没有得到ack确认, 
服务端这边重发synack, 期望客户端重新来个ack来进行达成全连接状态

linux backlog ->  accept队列的大小默认是128的啊
java? -> 默认50

(默认行为)accept队列满状态? 服务端否决syn队列中的ack, 并同时重发synack
tcp_abort_on_overflow  --> 这里的overflow是指accept队列的啊, 充满了等待被应用accept取走的
全连接
0: 作为服务端三次握手最后一步, accept队列满的状态下, 丢弃ack, 重发synack
1: 直接RST  ==> (客户端会疑惑, 是该端口没有进程监听呢, 还是该端口有进程监听, 只是该
监听进程的accept队列满了的效果的啊, 哈哈)

通过backlog参数来研究syn队列和accept队列的啊

[lewenweijia]

// 针对tcp的攻击
syn flood攻击, 导致服务端的syn队列爆满, 无法服务其他正常请求连接

防止syn flood攻击? -> 96年的tcp_syncookie, 接收到syn只是计算个cookie给它, 最后ack回来的时候
才分配连接资源的哦
2. 调小synack_retries的次数

nginx是多进程模式, 多个进程监听同个端口?? 来尽量避免上下文切换带来的性能消耗

[lewenweijia]

三次连接太耗时? 出现各种连接重用的技术的啊
1. 连接重用, SO_REUSEADDR, 完全没有损耗
2. TFO, 减少新建的性能损耗
因为握手涉及RTT, RTT涉及网络传输, 速度很慢啊!

tfo? 要求已经建立过正常的三次握手
客户端主动请求tfo-cookie的效果的啊 --> 发送一个带tfo-cookie请求的syn包的效果的啊
tfo可以实现0-RTT的效果的啊... -> 直接`syn + cookie + HTTP GET`

也就是需要一个TFO支持的UA的效果的哦

如果cookie验证通过, 直接将该syn包中的数据交给上层的啊

一般来说, syn包是不携带数据的哦

1. 请求TFOcookie
2. 真正的TFO

降低请求延迟的方法?
tcp层面的优化的啊! tfo

主动fin方一般是客户端, 但是遇到服务器程序崩溃的时候, 服务端可能也会主动发fin
 --> 有2MSL, 这时候服务器重启又来消费这个端口, 会被系统拒绝 -> already in use

服务端才需要考虑SO_REUSEADDR的问题的效果的啊, 厉害了的哦, unbelievable的呢
有事说事, 不然当信息发错人...

[lewenweijia]

每发送一个数据包, tcp协议栈都会开启一个定时器进行跟踪的效果的呢, 哈哈, 厉害了的哦

tcp连接是有两种关闭方式的啊?:
1. FIN, 优雅关闭
2. RST, 暴力关闭!

因为是主动关闭, 所以2MSL的灾难在自己这边的啊
简直了的啊, 如果服务器那边获得2MSL的TIME_WAIT时间的效果的啊

so_linger, 改变调用close时候的行为
1. 默认下, 内核缓冲区中所有数据都写出去, 才进行关闭2
2. 放弃缓冲队列的数据, close立即返回
3. 一定时间内推缓冲区中的数据, 若时间完还未推完, 强制返回+数据丢弃!

不想等那么久进行连接的关闭 -> SO_LINGER徘徊登场, 哈哈

我们要明确, 只有主动关闭方才会进入TIME_WAIT状态, 获得2MSL加成