1 检验和

检验和UDP可选，TCP必须； 计算方法：将报文分成多个16位的段进行操作。

2 序列号 sequence

TCP将每个字节的数据都进行了编号，这就是序列号。
序列号的作用：
a、保证可靠性（当接收到的数据总少了某个序号的数据时，能马上知道）
b、保证数据的按序到达
c、提高效率，可实现多次发送，一次确认
d、去除重复数据
数据传输过程中的确认应答处理、重发控制以及重复控制等功能都可以通过序列号来实现

3 确认应答机制（ACK） 

标志位ACK=1时确认首部的确认字段有效。
而发送方如果收到了已发送的数据的确认报文，则继续传输下一部分数据；而如果等待了一定时间还没有收到确认报文就会启动重传机制。

4 超时重传机制

5 连接管理（三次握手，四次挥手）

6、 流量控制：

TCP 连接的每一方都有固定大小的缓冲空间，TCP的接收端只允许发送端发送接收端缓冲区能接纳的数据。当接收方来不及处理发送方的数据，能提示发送方降低发送的速率，防止包丢失。TCP 使用的流量控制协议是可变大小的滑动窗口协议。 （TCP 利用滑动窗口实现流量控制）

TCP是双工的协议,TCP会话的双方都各自维护一个发送窗口和一个接收窗口。

7 拥塞控制： 当网络拥塞时，减少数据的发送。

为此TCP引入慢启动机制，先发出少量数据，就像探路一样，先摸清当前的网络拥堵状态后，再决定按照多大的速度传送数据。

cat words.txt | sort | uniq -c | sort -k1,1nr | head -10

简单总结一下博客: 背景是搜索用户评论项目

1 总结

使用了sorted set和hash两种数据结构，

sorted set的组成： topicId(key,帖子主题) -- createdAt(score,也可以是其他标准点赞数等) -- commitId(member，提交id，关联到用户评论内容)
hash的组成： {commitId : content}


使用hash的理由： 如上，排序筛选可能用多种，创建、点赞数等，zset中存储commitId的话，可以只维护一份内容。虽然zst中可以直接存内容。

2 详述

redis一共五种数据类型：

1、String: 主要用于存储字符串，显然不支持分页和排序。
2、List: 主要用于存储一个列表，删除评论只有LPOP和RPOP，不能指定删除，而且当存在接口高并发访问时，这个list可能会无限延长，且里面的数据会存在很多重复，这就会影响到正常的业务，所以List也不太适合。
3、Set: 主要存储无序集合，无序！排除。
4、Hash: 主要用于存储key-value型数据，评论模型中全是key-value型数据，所以在这里Hash无疑会用到。
5、SortedSet: 主要存储有序集合，
    SortedSet的添加元素指令ZADD key score member [[score,member]…]会给每个添加的元素member绑定一个用于排序的值score，
    SortedSet就会根据score值的大小对元素进行排序，在这里就可以将createDate当作score用于排序，
    SortedSet中的指令ZREVRANGE key start stop又可以返回指定区间内的成员，可以用来做分页，
    SortedSet的指令ZREM key member可以根据key移除指定的成员，能满足删评论的要求，所以，SortedSet在这里是最适合的（时间复杂度O(log(N))）。

  所以，需要用到的数据类型有SortSet和Hash，SortSet用于做分页排序，Hash用于存储具体的键值对数据。
  SortSet结构中将每个主题的topicId作为set的key，将与该主题关联的评论的createDate和commentId分别作为set的score和member，commentId的顺序就根据createDate的大小进行排列。
  当需要查询某个主题某一页的评论时，就可主题的topicId通过指令zrevrange topicId (page-1)×10 (page-1)×10+perPage这样就能找出某个主题下某一页的按时间排好顺序的所有评论的commintId。page为查询第几页的页码，perPage为每页显示的条数。
  当找到所有评论的commentId后，就可以把这些commentId作为key去Hash结构中去查询该条评论对应的内容。
  这样就利用SortSet和Hash两种结构在Redis中达到了分页和排序的目的。

  当然，也可以直接只使用SrotedSet类型，而不使用Hash类型，直接将评论存放在member中。
  但为什么要将评论和排序放到不同的类型里？其中的好处是，可以对评论设置不同的排序类型，比如按时间的正反序，点赞的正反序，查看次数的正反序等。而这样只需要维护不同的SrotedSet排序，不需要维护多套评论的内容了。

Request Header:

GET /sample.Jsp HTTP/1.1  //请求行
Host: www.uuid.online/  //请求的目标域名和端口号
Origin: http://localhost:8081/  //请求的来源域名和端口号 （跨域请求时，浏览器会自动带上这个头信息）
Referer: https:/localhost:8081/link?query=xxxxx  //请求资源的完整URI
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.99 Safari/537.36 //浏览器信息
Cookie: BAIDUID=FA89F036:FG=1; BD_HOME=1; sugstore=0  //当前域名下的Cookie
Accept: text/html,image/apng  //代表客户端希望接受的数据类型是html或者是png图片类型 
Accept-Encoding: gzip, deflate  //代表客户端能支持gzip和deflate格式的压缩
Accept-Language: zh-CN,zh;q=0.9  //代表客户端可以支持语言zh-CN或者zh(值得一提的是q(0~1)是优先级权重的意思，不写默认为1，这里zh-CN是1，zh是0.9)
Connection: keep-alive  //告诉服务器，客户端需要的tcp连接是一个长连接
Response Header:

HTTP/1.1 200 OK  // 响应状态行
Date: Mon, 30 Jul 2018 02:50:55 GMT  //服务端发送资源时的服务器时间
Expires: Wed, 31 Dec 1969 23:59:59 GMT //比较过时的一种验证缓存的方式，与浏览器（客户端）的时间比较，超过这个时间就不用缓存（不和服务器进行验证），适合版本比较稳定的网页
Cache-Control:  no-cache  // 现在最多使用的控制缓存的方式，会和服务器进行缓存验证，具体见博文”Cache-Control“
etag: "fb8ba2f80b1d324bb997cbe188f28187-ssl-df"  // 一般是Nginx静态服务器发来的静态文件签名，浏览在没有“Disabled cache”情况下，接收到etag后，同一个url第二次请求就会自动带上“If-None-Match”
Last-Modified: Fri, 27 Jul 2018 11:04:55 GMT //是服务器发来的当前资源最后一次修改的时间，下次请求时，如果服务器上当前资源的修改时间大于这个时间，就返回新的资源内容
Content-Type: text/html; charset=utf-8  //如果返回是流式的数据，我们就必须告诉浏览器这个头，不然浏览器会下载这个页面，同时告诉浏览器是utf8编码，否则可能出现乱码
Content-Encoding: gzip  //告诉客户端，应该采用gzip对资源进行解码
Connection: keep-alive  //告诉客户端服务器的tcp连接也是一个长连接

拥塞控制主要是四个算法：

1.慢启动：意思是刚刚加入网络的连接，一点一点地提速，不要一上来就把路占满。
    阈值ssthresh（slow start threshold），是一个上限，当cwnd >= ssthresh时，就会进入“拥塞避免算法”
2.拥塞避免：当拥塞窗口 cwnd 达到一个阈值时，窗口大小不再呈指数上升，而是以线性上升，避免增长过快导致网络拥塞。
3.进入慢启动过程
4.快速恢复：至少收到了3个Duplicated Acks，说明网络也不那么糟糕，可以快速恢复。

CDN的全称是Content Delivery Network，即内容分发网络。CDN是构建在网络之上的内容分发网络，依靠部署在各地的边缘服务器，通过中心平台的负载均衡、内容分发、调度等功能模块，使用户就近获取所需内容，降低网络拥塞，提高用户访问响应速度和命中率。CDN的关键技术主要有内容存储和分发技术。

CDN的基本原理是广泛采用各种缓存服务器，将这些缓存服务器分布到用户访问相对集中的地区或网络中，在用户访问网站时，利用全局负载技术将用户的访问指向距离最近的工作正常的缓存服务器上，由缓存服务器直接响应用户请求。

基本思路是尽可能避开互联网上有可能影响数据传输速度和稳定性的瓶颈和环节，使内容传输的更快、更稳定。通过在网络各处放置节点服务器所构成的在现有的互联网基础之上的一层智能虚拟网络，CDN系统能够实时地根据网络流量和各节点的连接、负载状况以及到用户的距离和响应时间等综合信息将用户的请求重新导向离用户最近的服务节点上。其目的是使用户可就近取得所需内容，解决 Internet网络拥挤的状况，提高用户访问网站的响应速度。

，而内容管理和全局的网络流量管理(Traffic Management)是CDN的核心所在。通过用户就近性和服务器负载的判断，CDN确保内容以一种极为高效的方式为用户的请求提供服务。

贪心策略：
1，如果田忌的最快马快于齐王的最快马，则两者比。
（因为若是田忌的别的马很可能就赢不了了，所以两者比）
2，如果田忌的最快马慢于齐王的最快马，则用田忌的最慢马和齐王的最快马比。
（由于所有的马都赢不了齐王的最快马，所以用损失最小的，拿最慢的和他比）
3，若相等，则比较田忌的最慢马和齐王的最慢马
3.1，若田忌最慢马快于齐王最慢马，两者比。
（田忌的最慢马既然能赢一个就赢呗，而且齐王的最慢马肯定也得有个和他比，所以选最小的比他快得。）
3.2，其他，则拿田忌的最慢马和齐王的最快马比。
（反正所有的马都比田忌的最慢马快了，所以这匹马必输，选贡献最大的，干掉齐王的最快马）

1 采用Hadoop海量数据处理，将海量字符串分到不同的map任务中，每个任务，进行对字符串在相应的node上进行查找，接着对于所有的map的结果交给reduce任务分析，这仅仅是个方案，具体时间复杂度的话，看你有多少个map任务了

2 采用trie树，对这海量字符串构建一颗trie树，然后在trie树中查找该字符串，trie树的优势在于对于前缀一样的字符串都可以在一次匹配查找中得到，时间复杂度在于构建trie树复杂度，和trie树的高度。

如果数据量不大

1 桶排序

2 采用正则表达式匹配，比如还是happy，假如将原始集合中的所有字符串和正则表达式pattern = ^h[A-Za-z]+y$进行匹配，接着在对app这个子串和子集合中进行正则表达式匹，pattern=^a[A-Za-z]+p$,最后对p进行匹配即可，时间复杂度O(mn)

正确的原理就是通过发号策略，给每一个过来的长地址，发一个号即可，小型系统直接用mysql的自增索引就搞定了。如果是大型应用，可以考虑各种分布式key-value系统做发号器。不停的自增就行了。第一个使用这个服务的人得到的短地址是 http://xx.xx/0 第二个是 http://xx.xx/1 第11个是 http://xx.xx/a 第依次往后，相当于实现了一个62进制的自增字段即可。

为什么是62进制： 62= 10数字 + 26大写字母 + 26小写字母

问题1： 62进制如何用数据库或者KV存储来做？

其实我们并不需要在存储中用62进制，用10进制就好了。比如第10000个长地址，我们给它的短地址对应的编号是9999，我们通过存储自增拿到9999后，再做一个10进制到62进制的转换，转成62进制数即可。这个10～62进制转换，你完全都可以自己实现。

问题2： 如何保证同一个长地址，每次转出来都是一样的短地址

一个网址，多次请求短地址，造成一长对多短，并不一一对应。

我的方案是：用key-value存储，保存“最近”生成的长对短的一个对应关系。注意是“最近”，也就是说，我并不保存全量的长对短的关系，而只保存最近的。比如采用一小时过期的机制来实现LRU淘汰。

这样的话，长转短的流程变成这样：

在这个“最近”表中查看一下，看长地址有没有对应的短地址
有就直接返回，并且将这个key-value对的过期时间再延长成一小时
如果没有，就通过发号器生成一个短地址，并且将这个“最近”表中，过期时间为1小时
所以当一个地址被频繁使用，那么它会一直在这个key-value表中，总能返回当初生成那个短地址，不会出现重复的问题。如果它使用并不频繁，那么长对短的key会过期，LRU机制自动就会淘汰掉它。

当然，这不能保证100%的同一个长地址一定能转出同一个短地址，比如你拿一个生僻的url，每间隔1小时来转一次，你会得到不同的短地址。但是这真的有关系吗？

问题3： 如何保证发号器的大并发高可用

上面设计看起来有一个单点，那就是发号器。如果做成分布式的，那么多节点要保持同步加1，多点同时写入，这个嘛，以CAP理论看，是不可能真正做到的。其实这个问题的解决非常简单，我们可以退一步考虑，我们是否可以实现两个发号器，一个发单号，一个发双号，这样就变单点为多点了？依次类推，我们可以实现1000个逻辑发号器，分别发尾号为0到999的号。每发一个号，每个发号器加1000，而不是加1。这些发号器独立工作，互不干扰即可。而且在实现上，也可以先是逻辑的，真的压力变大了，再拆分成独立的物理机器单元。1000个节点，估计对人类来说应该够用了。如果你真的还想更多，理论上也是可以的。

问题4 跳转用301还是302

301是永久重定向，302是临时重定向。短地址一经生成就不会变化，所以用301是符合http语义的。同时对服务器压力也会有一定减少。

但是如果使用了301，我们就无法统计到短地址被点击的次数了。而这个点击次数是一个非常有意思的大数据分析数据源。能够分析出的东西非常非常多。所以选择302虽然会增加服务器压力，但是我想是一个更好的选择。

1. 十五匹马，每次只能同时让五匹马赛跑，不借助任何工具，如何找出跑得最快的五匹马。

1) 先每5匹马分一个赛组，各组赛跑，每组最快的拿出来组成超级赛组；
2) 超级组赛跑，取最快的拿出来,这就是第一名；
3) 让最快的马来源赛组的第二名加入组成超级赛组，选出第二名；
4) 让第二名马来源赛组选出当前最快的马加入组成超级赛组，选出第三名；
...
n) 直至选出第5名

一共进行了 3(小组赛) + 5(超级赛), 一共8次比赛；