Fluge Site

最近在看网络编程模型，虽然Golang天然高并发的原因很大一部分是因为协程和channel,但是这个里面还是离不开底层的网络编程模型的选用 — epoll。在学习这部分的时候对IO多路复用做了一些了解。

一些概念

内核空间和用户空间

现在操作系统都是采用虚拟存储器，那么对32位操作系统而言，它的寻址空间（虚拟存储空间）为4G（2的32次方）。操作系统的核心是内核，独立于普通的应用程序，可以访问受保护的内存空间，也有访问底层硬件设备的所有权限。

为了保证用户进程不能直接操作内核，保证内核的安全，操心系统将虚拟空间划分为两部分，一部分为内核空间，一部分为用户空间。我们可以简单理解为，一张纸，四分之一给一个叫内核的人用，四分之三给一个叫用户的人用。

fd 文件操作描述符

文件描述符在形式上是一个非负整数,它是一个索引值,指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。文件描述符这一概念往往只适用于Unix和Linux这样的操作系统。

缓存IO

缓存 I/O 又被称作标准 I/O，大多数文件系统的默认 I/O 操作都是缓存 I/O。在 Linux 的缓存 I/O 机制中，操作系统会将 I/O 的数据缓存在文件系统的页缓存（ page cache ）中，也就是说，数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。就是从内核空间到用户空间需要经过两次复制操作。这些数据拷贝操作所带来的 CPU 以及内存开销是非常大的。

二叉树的各种遍历方式,包括递归和非递归的整理

1. 前、中、后三种方式的递归和非递归
2. 广度优先和层次遍历（树的深度的非递归解法）
3. 深度优先

   前序遍历

   前序遍历就是：先根节点 —> 左节点 —> 右节点

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

   //递归解法 func PreOrderTraversal(root *TreeNode) []int { if root == nil { return nil } res := make([]int, 0) res = append(res, root.Val) if root.Left != nil { res = append(res, PreOrderTraversal(root.Left)...) } if root.Right != nil { res = append(res, PreOrderTraversal(root.Right)...) } return res } //非递归解法 func PreOrderTraversal2(root *TreeNode) []int { if root == nil { return nil } stack := make([]*TreeNode, 0) res := make([]int, 0) //把根节点入栈 for root != nil || len(stack) > 0 { //不停的找做节点 for root != nil { //根节点先输出 res = append(res, root.Val) stack = append(stack, root) root = root.Left } //出栈操作 root = stack[len(stack)-1] stack = stack[:len(stack)-1] //遍历右节点 root = root.Right } return res }

TCP是一个非常复杂的面向连接的协议,在很30多年来，各种优化变种争论和修改不断,所以我先从连接的建立和终止开始写TCP。后面应该还有几篇文章写TCP的另外几个特别重要的特性。
TCP最开始被我知道就先从很有特点的链接建立和终止—三次握手和四次挥手,基本上TCP协议的可靠性就是从保证连接的可靠性开始的。

TCP链接的建立—三次握手

对于三次握手，其实是TCP比较著名的东西了,在完全不了解这个TCP的时候就知道有这个东西了，但是开始的时候总有一点让我非常的疑惑:TCP为什么是三次握手,为什么不是两次或四次？

TCP 为什么是三次握手,为什么不是两次或四次？

要解释这个问题,首先明白TCP出现的价值和思路:是为了在不可靠的互联网络上提供一个可靠的端到端字节流而设计的,并且一个TCP连接是全双工。这是TCP很重要的一个设计理念:提供了一种可靠的,面向连接的字节流运输层服务,并且是双全工的。这里需要理解双全工的意思：就是两端之间进行通信，这两端既可以是数据的接收方，也可以是数据的发送方。
1、 可靠模型:但是为了数据的安全送达，就必须在发送数据前向另一个端口进行通信

数据发送端A:嘿,我想发送数据了,可以么。
数据接收端B:好的，这边允许接受。

然后数据的发送端就可以发送数据了,这里就基本保证你发的在接收方会正常的接受并不会发错。这是发送数据的基本可靠模型。
2、 连接模型:在TCP的要求中,需要一种面向连接的通信:连接在我理解中就是相当于有一根空水管,连接两个水池(为两个水池传输东西),在水管中传输东西的效率肯定会高于用桶去一桶桶的装,来的方便。

原文
TCP的可靠性不止建立在建立一个稳固的链接上，还有就是数据包丢失的重传机制,和防止网络波动的拥塞处理机制,这些都是慢慢发展而来的。
要先了解TCP的重传和拥塞处理,需要先了解两个很常见的变量–RTT和RTO,这两个是对重传和拥塞很重要的概念。

RTT(Round Trip Time):就是发送一个数据包的往返时间的测量,由于路由器和网络流量均会变化，因此我们认为这个时间可能经常会发生变化，TCP应该跟踪这些变化并相应地改变其超时时间。
RTO(Retransmission TimeOut):重传超时时间,是根据RTT计算得到的。

重传

在重传机制中，首先在介绍重传的几个机制前，要注意。接收端给发送端的Ack确认只会确认最后一个连续的包。比如：发送端发了1,2,3,4,5一共五份数据，接收端收到了1,2,于是回ack 3,然后收到了4(注意此时3没收到，3丢失)此时的TCP会怎么办?我们要知道,因为正如前面所说的,SeqNum和Ack是以字节数为单位,所以ack的时候,不能跳着确认,只能确认最大的连续收到的包,不然,发送端就以为之前的都收到了。

从HashMap并发的死循环可以知道,Hashmap是没办法在多线程的情况下使用的，为了解决这个问题，在Java4之前用的是hashtable,只是现在不推荐的。在Java5之后就比较推荐使用java.util.concurrent.ConcurrentHashMap，这个在多线程的情况下，也能有很好的性能。从这里引入了Java里面一类很重要的概念—并发。先解决完上一个问题。高并发下ConcurrentHashMap的结构。

并发的一些初步了解–synchronized和volatile

在多线程的并发的情况下有安全的访问变量，为了解决这个问题引入一个机制—锁机制。让多线程不能同时访问一个共享变量。在并发过程中有需要简单的了解两个东西的含义。

Java中的synchronized的简单分析

synchronized的用法要弄清晰一个问题:synchronized锁住的是代码还是对象？
首先是一个被synchronized修饰的代码块

基本认识

首先有一点必须特别的清楚： 因为HTTP协议是无状态的，客户每次读取web页面时，服务器都打开新的会话，而且服务器也不会自动维护客户的上下文信息，对于一个浏览器发出的多次请求，WEB服务器无法区分 是不是来源于同一个浏览器，更别说是否是来自同一用户。为了保持用户的状态，有了两种机制，一般用户客户端的cookie机制，和用于服务器端的session机制，这两种机制都是为了保持状态，既有联系又有区别。

cookie基本实现机制

现在的cookie是HTTP协议的一部分，一般存在HTTP的响应头，内容是一系列的键值对的形式，简单说：cookie就是服务器在用户的浏览器中存储的一小段文本文件（大小不能超过3K）不包含任何可执行代码，里面一般包含的是用户的登录信息之类的比较少的，用来验证用户是否合法（不止局限与此，cookie是用来记录状态的，也可以是购物的等一系列状态，让服务器知道我们浏览了那些地方，购物对那些感兴趣，一般很多广告都是根据这个东西来推送的，你在某购物网站买了一个东西，然后浏览别的网站，发现广告都是和你浏览的相关）。 cookie的内容主要包括：key-value,Expires（过期时间），path和domain。path和domain一起构成cookie的作用范围。

    现在的cookie，内容经过加密了
cookie的实现流程：

1. 浏览器向某个URL发起HTTP请求 （可以是任何请求，比如GET，POST等）
2. 对应的服务器收到该HTTP请求，并做相应的响应（响应头和请求体两部分），在响应的头中加入Set-Cookie字段（设置相应的cookie，cookie是多个key-value组成的）
   阅读全文

HashMap从设计上来说就不适合在并发的情况的下使用,因为HashMap每次在put()时，总会检查一遍对应桶的容量，如果桶满了，或者超过了设定的值，就会reserve()来进行扩容,然后通过get()来取出相应的值。这个过程在单线程下是没什么问题的，但是如果在并发的条件下，多个线程同时reserve桶，然后有线程这个时候执行get()就有可能产生死循环，造成CPU的100%占用，具体等会看源码。在Java里面有一个很老的hashtable就是加了锁的HashMap。现在Java中多线程里一般使用ConcurrentHashMap，至于为什么。会在下一篇博文里分析。

HashMap的rehash源代码

put()方法的Java8源码分析看我的Java里的hashMap和golang里的map，在Java8中优化了扩容的hash算法，更加高效。在这分析死循环用的是Java7的源码。更加清晰点。

同源策略

这套安全策略由Netscape提出，并延续至今。它规定：JavaScript脚本只能访问与其同一来源的资源(现在很多资源是通过ajax发起异步请求来获取的，如果没有跨域这个是禁止的)。
所谓同源是指，域名，协议，端口相同。不同源的客户端脚本(javascript、ActionScript)在没明确授权的情况下，不能读写对方的资源。严格隔离不相关的网站提供的内容，防止客户端数据机密性或完整性丢失。
假设你已经成功登录Gmail服务器，同时在同一个浏览器访问恶意站点（另一个浏览器选项卡）。没有同源策略，攻击者可以通过JavaScript获取你的用户信息，你的邮件以及其他敏感信息，比如说阅读你的私密邮件，发送虚假邮件，看你的聊天记录等等。假如把这个换成银行账户，那就很恐怖了。
可以说同源策略是现如今浏览器安全的基石。但是如果不能突破同源策略，把所有的资源放在同一服务器下，现在看来是不现实，必须有一中方式去平衡这种安全和便捷的机制–跨域。现在一般的跨域使用的是CORS(基本所有浏览器支持)和JSONP(一些比较的老的应用使用)。

CROS跨域

CORS是一个W3C标准，全称是”跨域资源共享”(Cross-origin resource sharing)。它允许浏览器向跨源服务器,发出XMLHttpRequest请求，从而克服了AJAX只能同源使用的限制。
简单说一下我对CROS的理解。就相当于我想跟一个邻居借东西(浏览器向服务器发送跨域请求)。我首先要去敲门，然后就是几种情况，一种是邻居家里你敲门没有反应(服务器端没有设置跨域)，你跟不知道邻居家里的具体情况，借东西肯定是失败的。一种是邻居进行了应答，但是告诉你我跟你不熟，不借东西给你。另外一种就是邻居进行了应答，并借给你东西。

ICMP网络控制报文协议

ICMP经常被认为是IP层的一个组成部分,它传递差错报文以及其他需要注意的信息。ICMP报文通常被IP层或更高层协议（UDP,TCP）使用。ICMP报文是在IP数据报内部传输的。由于IP是不可靠的协议，不能保证IP数据报能够成功到达目的主机，无法进行差错控制。但是这些信息会由ICMP将错误信息封包，然后传递给主机，让主机有处理错误的机会。

ICMP数据报由8bit的错误类型和8bit的代码（表示制定类型中的一个功能，如果只有一个功能，代码就置0）以及16bit的校验和组成，检验和字段覆盖整个ICMP报文。
ICMP报文大致可以分为：差错报文和查询报文。因为对ICMP的差错报文需要做一些特殊响应，需要进行区分。比如在对差错报文进行响应的时候，永远不会产生另一个ICMP差错报文，防止不断的产生差错一直循环。同时一下几种情况也不会产生ICMP差错报文：

1. ICMP差错报文不会产生
2. 目的地址是广播地址或多播地址的IP数据报
3. 作为链路层广播的数据报
4. 不是IP分片的第一片
5. 源地址不是单个主机的数据报
   阅读全文

哈希表

哈希表就是一种以键-值(key-value)存储数据的结构,我们只要输入待查找的键即Key,即可找到对应的值。
使用哈希找查有两个步骤:

1. 使用哈希函数将被找查的键转换为数组的索引.在理想的情况下,不同的键会被装换为不同的索引值,但是在有些情况下我们需要处理多个键被哈希到同一个索引值得情况。所以哈希查找的第二个步骤是处理冲突。
2. 处理哈希碰撞冲突。一般处理哈希碰撞用拉链法和开放寻址法等方法。

   开放地址法:当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
   拉链法:当通过哈希函数把键转换为数组的索引时,如果索引重复,就在该位置用链表顺序 存储该键值对。

Java中的HashMap

基本认识：基于Map接口,允许null键/值,非同步,不保证有序,也不保证顺序不随时间变化。
HashMap中和Map一样，键值对都是保存在一个内部类中的,而在HashMap类中有一个很重要的字段，那就是Node[] table，即是一个哈希桶数组。Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。

1
2
3
4
5
6
7
8
9

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
       /.../
}