0%

动态规划

建议观看 MIT 算法导论-动态规划中的课程。

适用于动态规划的问题,需要满足最优子结构无后效性,动态规划的求解过程,在于找到状态转移方程,进行自底向上的求解。

例题

爬楼梯问题 LeetCode 70

经典的动态规划问题之一,容易找到其状态转移方程为 dp[i] = dp[i-1] + dp[i-2],从基础的 1 和 2 个台阶两个状态开始,自底向上求解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int climbStairs(int n) {
if (n == 1) {
return 1;
}

int* dp = new int[n+1]();
dp[1] = 1;
dp[2] = 2;

for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}

return dp[n];
}

从上面的代码中看到,dp[i] 只依赖 dp[i-1]dp[i-2],因此可以将代码简化:

1
2
3
4
5
6
7
8
9
int climbStairs(int n) {
int f0 = 1, f1 = 1, i, f2;
for (i=2; i<=n; i++) {
f2 = f0 + f1;
f0 = f1;
f1 = f2;
}
return f1;
}

容易看出其实结果就是 fibonacci 数列的第 n 项。

连续子数组的最大和 LeetCode 53

dp[n] 表示元素 n 作为末尾的连续序列的最大和,容易想到状态转移方程为dp[n] = max(dp[n-1] + num[n], num[n]),从第 1 个元素开始,自顶向上求解:

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxSubArray(vector<int>& nums) {
int* dp = new int[nums.size()]();

dp[0] = nums[0];
int result = dp[0];

for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i-1] + nums[i], nums[i]);
result = max(result, dp[i]);
}

return result;
}

类似前一个问题,这个问题当中,求解 dp[i] 只依赖 dp[i-1],因此可以使用变量来存储,简化代码:

1
2
3
4
5
6
7
8
9
int maxSubArray(int A[], int n) {
int result = INT_MIN;
int f = 0;
for (int i=0; i < n; i++) {
f = max(f + A[i], A[i]);
result = max(result, f);
}
return result;
}

House Robber LeetCode 198

对于一个房子,有抢和不抢两种选择,容易得到状态转移方程 dp[i+1] = max(dp[i-1] + nums[i], dp[i]),示例代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}

vector<int> dp = vector<int>(n + 1);

dp[0] = 0;
dp[1] = nums[0];

for (int i = 1; i < nums.size(); i++) {
int v = nums[i];
dp[i+1] = max(dp[i-1] + v, dp[i]);
}

return dp[n];
}

同样的,可以使用两个变量简化代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}

int prev1 = 0;
int prev2 = 0;

for (int i = 0; i < nums.size(); i++) {
int v = nums[i];
int temp = prev1;
prev1 = max(prev2 + v, prev1);
prev2 = temp;
}

return prev1;
}

最长回文子串 LeetCode 5

dp[i][j] 表示子串 i 到 j 是否是回文,使用动态规划求解:

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
string longestPalindrome(string s) {
int m = s.size();
if (m == 0) {
return "";
}
vector<vector<int>> dp(m, vector<int>(m, 0));
int start = 0;
int length = 1;

for (int i = 0; i < m; i++) {
// 单个字符属于回文,例如 abcd
dp[i][i] = 1;

// 连续两个字符相同属于回文,例如 abb
if (i < m - 1) {
if (s[i] == s[i + 1]) {
dp[i][i + 1] = 1;
start = i;
length = 2;
}
}
}

for (int len = 2; len <= m; len++) {
for (int i = 0; i < m - len; i++) {
int j = i + len;
// 扩展长度
if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) {
dp[i][j] = 1;

if (j - i + 1 > length) {
start = i;
length = j - i + 1;
}
}
}
}

return s.substr(start, length);
}

最小编辑距离 LeetCode 72

dp[i][j] 表示从 word[0..i) 转换到 word[0..j) 的最小操作,使用动态规划求解:

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
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

// 全部删除,操作数量为 i
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}

for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 末尾字符相同,不需要编辑
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 末尾字符不同,三种编辑情况,取最小值
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}

return dp[m][n];
}

HTTP

HTTP 的特性

  • HTTP 协议构建于 TCP/IP 协议之上,是一个应用层协议,默认端口号是 80
  • HTTP 是无连接无状态

HTTP 报文

请求报文

HTTP 协议是以 ASCII 码传输,建立在 TCP/IP 协议之上的应用层规范。规范把 HTTP 请求分为三个部分:状态行、请求头、消息主体。类似于下面这样:

<method> <request-URL> <version>
<headers>

<entity-body>

HTTP 定义了与服务器交互的不同方法,最基本的方法有4种,分别是GETPOSTPUTDELETEURL全称是资源描述符,我们可以这样认为:一个URL地址,它用于描述一个网络上的资源,而 HTTP 中的GETPOSTPUTDELETE就对应着对这个资源的查,增,改,删4个操作。

  1. GET 用于信息获取,而且应该是安全的 和 幂等的。

    所谓安全的意味着该操作用于获取信息而非修改信息。换句话说,GET 请求一般不应产生副作用。就是说,它仅仅是获取资源信息,就像数据库查询一样,不会修改,增加数据,不会影响资源的状态。

    幂等的意味着对同一 URL 的多个请求应该返回同样的结果。

    GET 请求报文示例:

    GET /books/?sex=man&name=Professional HTTP/1.1
    Host: www.example.com
    User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.6)
    Gecko/20050225 Firefox/1.0.1
    Connection: Keep-Alive
  2. POST 表示可能修改变服务器上的资源的请求。

POST / HTTP/1.1
Host: www.example.com
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.6)
Gecko/20050225 Firefox/1.0.1
Content-Type: application/x-www-form-urlencoded
Content-Length: 40
Connection: Keep-Alive

sex=man&name=Professional  
  1. 注意:

    • GET 可提交的数据量受到URL长度的限制,HTTP 协议规范没有对 URL 长度进行限制。这个限制是特定的浏览器及服务器对它的限制
    • 理论上讲,POST 是没有大小限制的,HTTP 协议规范也没有进行大小限制,出于安全考虑,服务器软件在实现时会做一定限制
    • 参考上面的报文示例,可以发现 GET 和 POST 数据内容是一模一样的,只是位置不同,一个在 URL 里,一个在 HTTP 包的包体里

POST 提交数据的方式

HTTP 协议中规定 POST 提交的数据必须在 body 部分中,但是协议中没有规定数据使用哪种编码方式或者数据格式。实际上,开发者完全可以自己决定消息主体的格式,只要最后发送的 HTTP 请求满足上面的格式就可以。

但是,数据发送出去,还要服务端解析成功才有意义。一般服务端语言如 PHP、Python 等,以及它们的 framework,都内置了自动解析常见数据格式的功能。服务端通常是根据请求头(headers)中的 Content-Type 字段来获知请求中的消息主体是用何种方式编码,再对主体进行解析。所以说到 POST 提交数据方案,包含了 Content-Type 和消息主体编码方式两部分。下面就正式开始介绍它们:

  • application/x-www-form-urlencoded

这是最常见的 POST 数据提交方式。浏览器的原生 <form> 表单,如果不设置 enctype 属性,那么最终就会以 application/x-www-form-urlencoded 方式提交数据。上个小节当中的例子便是使用了这种提交方式。可以看到 body 当中的内容和 GET 请求是完全相同的。

  • multipart/form-data

这又是一个常见的 POST 数据提交的方式。我们使用表单上传文件时,必须让 <form> 表单的 enctype 等于 multipart/form-data。直接来看一个请求示例:

POST http://www.example.com HTTP/1.1
Content-Type:multipart/form-data; boundary=----WebKitFormBoundaryrGKCBY7qhFd3TrwA

------WebKitFormBoundaryrGKCBY7qhFd3TrwA
Content-Disposition: form-data; name="text"

title
------WebKitFormBoundaryrGKCBY7qhFd3TrwA
Content-Disposition: form-data; name="file"; filename="chrome.png"
Content-Type: image/png

PNG ... content of chrome.png ...
------WebKitFormBoundaryrGKCBY7qhFd3TrwA--

这个例子稍微复杂点。首先生成了一个 boundary 用于分割不同的字段,为了避免与正文内容重复,boundary 很长很复杂。然后 Content-Type 里指明了数据是以 multipart/form-data 来编码,本次请求的 boundary 是什么内容。消息主体里按照字段个数又分为多个结构类似的部分,每部分都是以 –boundary 开始,紧接着是内容描述信息,然后是回车,最后是字段具体内容(文本或二进制)。如果传输的是文件,还要包含文件名和文件类型信息。消息主体最后以 –boundary– 标示结束。关于 multipart/form-data 的详细定义,请前往 RFC1867 查看(或者相对友好一点的 MDN 文档)。

这种方式一般用来上传文件,各大服务端语言对它也有着良好的支持。

上面提到的这两种 POST 数据的方式,都是浏览器原生支持的,而且现阶段标准中原生 <form> 表单也只支持这两种方式(通过 <form> 元素的 enctype 属性指定,默认为 application/x-www-form-urlencoded。其实 enctype 还支持 text/plain,不过用得非常少)。

随着越来越多的 Web 站点,尤其是 WebApp,全部使用 Ajax 进行数据交互之后,我们完全可以定义新的数据提交方式,例如 application/jsontext/xml,乃至 application/x-protobuf 这种二进制格式,只要服务器可以根据 Content-TypeContent-Encoding 正确地解析出请求,都是没有问题的。

响应报文

HTTP 响应与 HTTP 请求相似,HTTP响应也由3个部分构成,分别是:

  • 状态行
  • 响应头(Response Header)
  • 响应正文

状态行由协议版本、数字形式的状态代码、及相应的状态描述,各元素之间以空格分隔。

常见的状态码有如下几种:

  • 200 OK 客户端请求成功
  • 301 Moved Permanently 请求永久重定向
  • 302 Moved Temporarily 请求临时重定向
  • 304 Not Modified 文件未修改,可以直接使用缓存的文件。
  • 400 Bad Request 由于客户端请求有语法错误,不能被服务器所理解。
  • 401 Unauthorized 请求未经授权。这个状态代码必须和WWW-Authenticate报头域一起使用
  • 403 Forbidden 服务器收到请求,但是拒绝提供服务。服务器通常会在响应正文中给出不提供服务的原因
  • 404 Not Found 请求的资源不存在,例如,输入了错误的URL
  • 500 Internal Server Error 服务器发生不可预期的错误,导致无法完成客户端的请求。
  • 503 Service Unavailable 服务器当前不能够处理客户端的请求,在一段时间之后,服务器可能会恢复正常。

下面是一个HTTP响应的例子:

HTTP/1.1 200 OK

Server:Apache Tomcat/5.0.12
Date:Mon,6Oct2003 13:23:42 GMT
Content-Length:112

<html>...

条件 GET

HTTP 条件 GET 是 HTTP 协议为了减少不必要的带宽浪费,提出的一种方案。详见 RFC2616

  1. HTTP 条件 GET 使用的时机?

    客户端之前已经访问过某网站,并打算再次访问该网站。

  2. HTTP 条件 GET 使用的方法?

    客户端向服务器发送一个包询问是否在上一次访问网站的时间后是否更改了页面,如果服务器没有更新,显然不需要把整个网页传给客户端,客户端只要使用本地缓存即可,如果服务器对照客户端给出的时间已经更新了客户端请求的网页,则发送这个更新了的网页给用户。

    下面是一个具体的发送接受报文示例:

    客户端发送请求:

    GET / HTTP/1.1  
    Host: www.sina.com.cn:80  
    If-Modified-Since:Thu, 4 Feb 2010 20:39:13 GMT  
    Connection: Close  

    第一次请求时,服务器端返回请求数据,之后的请求,服务器根据请求中的 If-Modified-Since 字段判断响应文件没有更新,如果没有更新,服务器返回一个 304 Not Modified响应,告诉浏览器请求的资源在浏览器上没有更新,可以使用已缓存的上次获取的文件。

    HTTP/1.0 304 Not Modified  
    Date: Thu, 04 Feb 2010 12:38:41 GMT  
    Content-Type: text/html  
    Expires: Thu, 04 Feb 2010 12:39:41 GMT  
    Last-Modified: Thu, 04 Feb 2010 12:29:04 GMT  
    Age: 28  
    X-Cache: HIT from sy32-21.sina.com.cn  
    Connection: close 

    如果服务器端资源已经更新的话,就返回正常的响应。

持久连接

我们知道 HTTP 协议采用“请求-应答”模式,当使用普通模式,即非 Keep-Alive 模式时,每个请求/应答客户和服务器都要新建一个连接,完成之后立即断开连接(HTTP 协议为无连接的协议);当使用 Keep-Alive 模式(又称持久连接、连接重用)时,Keep-Alive 功能使客户端到服务器端的连接持续有效,当出现对服务器的后继请求时,Keep-Alive 功能避免了建立或者重新建立连接。

在 HTTP 1.0 版本中,并没有官方的标准来规定 Keep-Alive 如何工作,因此实际上它是被附加到 HTTP 1.0协议上,如果客户端浏览器支持 Keep-Alive ,那么就在HTTP请求头中添加一个字段 Connection: Keep-Alive,当服务器收到附带有 Connection: Keep-Alive 的请求时,它也会在响应头中添加一个同样的字段来使用 Keep-Alive 。这样一来,客户端和服务器之间的HTTP连接就会被保持,不会断开(超过 Keep-Alive 规定的时间,意外断电等情况除外),当客户端发送另外一个请求时,就使用这条已经建立的连接。

在 HTTP 1.1 版本中,默认情况下所有连接都被保持,如果加入 “Connection: close” 才关闭。目前大部分浏览器都使用 HTTP 1.1 协议,也就是说默认都会发起 Keep-Alive 的连接请求了,所以是否能完成一个完整的 Keep-Alive 连接就看服务器设置情况。

由于 HTTP 1.0 没有官方的 Keep-Alive 规范,并且也已经基本被淘汰,以下讨论均是针对 HTTP 1.1 标准中的 Keep-Alive 展开的。

注意:

  • HTTP Keep-Alive 简单说就是保持当前的TCP连接,避免了重新建立连接。

  • HTTP 长连接不可能一直保持,例如 Keep-Alive: timeout=5, max=100,表示这个TCP通道可以保持5秒,max=100,表示这个长连接最多接收100次请求就断开。

  • HTTP 是一个无状态协议,这意味着每个请求都是独立的,Keep-Alive 没能改变这个结果。另外,Keep-Alive也不能保证客户端和服务器之间的连接一定是活跃的,在 HTTP1.1 版本中也如此。唯一能保证的就是当连接被关闭时你能得到一个通知,所以不应该让程序依赖于 Keep-Alive 的保持连接特性,否则会有意想不到的后果。

  • 使用长连接之后,客户端、服务端怎么知道本次传输结束呢?两部分:1. 判断传输数据是否达到了Content-Length 指示的大小;2. 动态生成的文件没有 Content-Length ,它是分块传输(chunked),这时候就要根据 chunked 编码来判断,chunked 编码的数据在最后有一个空 chunked 块,表明本次传输数据结束,详见这里。什么是 chunked 分块传输呢?下面我们就来介绍一下。

Transfer-Encoding

Transfer-Encoding 是一个用来标示 HTTP 报文传输格式的头部值。尽管这个取值理论上可以有很多,但是当前的 HTTP 规范里实际上只定义了一种传输取值——chunked。

如果一个HTTP消息(请求消息或应答消息)的Transfer-Encoding消息头的值为chunked,那么,消息体由数量未定的块组成,并以最后一个大小为0的块为结束。

每一个非空的块都以该块包含数据的字节数(字节数以十六进制表示)开始,跟随一个CRLF (回车及换行),然后是数据本身,最后块CRLF结束。在一些实现中,块大小和CRLF之间填充有白空格(0x20)。

最后一块是单行,由块大小(0),一些可选的填充白空格,以及CRLF。最后一块不再包含任何数据,但是可以发送可选的尾部,包括消息头字段。消息最后以CRLF结尾。

一个示例响应如下:

HTTP/1.1 200 OK
Content-Type: text/plain
Transfer-Encoding: chunked

25
This is the data in the first chunk

1A
and this is the second one
0

注意:

  • chunked 和 multipart 两个名词在意义上有类似的地方,不过在 HTTP 协议当中这两个概念则不是一个类别的。multipart 是一种 Content-Type,标示 HTTP 报文内容的类型,而 chunked 是一种传输格式,标示报头将以何种方式进行传输。
  • chunked 传输不能事先知道内容的长度,只能靠最后的空 chunk 块来判断,因此对于下载请求来说,是没有办法实现进度的。在浏览器和下载工具中,偶尔我们也会看到有些文件是看不到下载进度的,即采用 chunked 方式进行下载。
  • chunked 的优势在于,服务器端可以边生成内容边发送,无需事先生成全部的内容。HTTP/2 不支持 Transfer-Encoding: chunked,因为 HTTP/2 有自己的 streaming 传输方式(Source:MDN - Transfer-Encoding)。

HTTP Pipelining(HTTP 管线化)

默认情况下 HTTP 协议中每个传输层连接只能承载一个 HTTP 请求和响应,浏览器会在收到上一个请求的响应之后,再发送下一个请求。在使用持久连接的情况下,某个连接上消息的传递类似于请求1 -> 响应1 -> 请求2 -> 响应2 -> 请求3 -> 响应3

HTTP Pipelining(管线化)是将多个 HTTP 请求整批提交的技术,在传送过程中不需等待服务端的回应。使用 HTTP Pipelining 技术之后,某个连接上的消息变成了类似这样请求1 -> 请求2 -> 请求3 -> 响应1 -> 响应2 -> 响应3

注意下面几点:

  • 管线化机制通过持久连接(persistent connection)完成,仅 HTTP/1.1 支持此技术(HTTP/1.0不支持)
  • 只有 GET 和 HEAD 请求可以进行管线化,而 POST 则有所限制
  • 初次创建连接时不应启动管线机制,因为对方(服务器)不一定支持 HTTP/1.1 版本的协议
  • 管线化不会影响响应到来的顺序,如上面的例子所示,响应返回的顺序并未改变
  • HTTP /1.1 要求服务器端支持管线化,但并不要求服务器端也对响应进行管线化处理,只是要求对于管线化的请求不失败即可
  • 由于上面提到的服务器端问题,开启管线化很可能并不会带来大幅度的性能提升,而且很多服务器端和代理程序对管线化的支持并不好,因此现代浏览器如 Chrome 和 Firefox 默认并未开启管线化支持

更多关于 HTTP Pipelining 的知识可以参考这里

会话跟踪

  1. 什么是会话?

    客户端打开与服务器的连接发出请求到服务器响应客户端请求的全过程称之为会话。

  2. 什么是会话跟踪?

    会话跟踪指的是对同一个用户对服务器的连续的请求和接受响应的监视。

  3. 为什么需要会话跟踪?

    浏览器与服务器之间的通信是通过HTTP协议进行通信的,而HTTP协议是”无状态”的协议,它不能保存客户的信息,即一次响应完成之后连接就断开了,下一次的请求需要重新连接,这样就需要判断是否是同一个用户,所以才有会话跟踪技术来实现这种要求。

  4. 会话跟踪常用的方法:

    1. URL 重写

      URL(统一资源定位符)是Web上特定页面的地址,URL重写的技术就是在URL结尾添加一个附加数据以标识该会话,把会话ID通过URL的信息传递过去,以便在服务器端进行识别不同的用户。

    2. 隐藏表单域

      将会话ID添加到HTML表单元素中提交到服务器,此表单元素并不在客户端显示

    3. Cookie

      Cookie 是Web 服务器发送给客户端的一小段信息,客户端请求时可以读取该信息发送到服务器端,进而进行用户的识别。对于客户端的每次请求,服务器都会将 Cookie 发送到客户端,在客户端可以进行保存,以便下次使用。

      客户端可以采用两种方式来保存这个 Cookie 对象,一种方式是保存在客户端内存中,称为临时 Cookie,浏览器关闭后这个 Cookie 对象将消失。另外一种方式是保存在客户机的磁盘上,称为永久 Cookie。以后客户端只要访问该网站,就会将这个 Cookie 再次发送到服务器上,前提是这个 Cookie 在有效期内,这样就实现了对客户的跟踪。

      Cookie 是可以被客户端禁用的。

    4. Session:

      每一个用户都有一个不同的 session,各个用户之间是不能共享的,是每个用户所独享的,在 session 中可以存放信息。

      在服务器端会创建一个 session 对象,产生一个 sessionID 来标识这个 session 对象,然后将这个 sessionID 放入到 Cookie 中发送到客户端,下一次访问时,sessionID 会发送到服务器,在服务器端进行识别不同的用户。

      Session 的实现依赖于 Cookie,如果 Cookie 被禁用,那么 session 也将失效。

跨站攻击

  • CSRF(Cross-site request forgery,跨站请求伪造)

    CSRF(XSRF) 顾名思义,是伪造请求,冒充用户在站内的正常操作。

    例如,一论坛网站的发贴是通过 GET 请求访问,点击发贴之后 JS 把发贴内容拼接成目标 URL 并访问:

    http://example.com/bbs/create_post.php?title=标题&content=内容

    那么,我们只需要在论坛中发一帖,包含一链接:

    http://example.com/bbs/create_post.php?title=我是脑残&content=哈哈

    只要有用户点击了这个链接,那么他们的帐户就会在不知情的情况下发布了这一帖子。可能这只是个恶作剧,但是既然发贴的请求可以伪造,那么删帖、转帐、改密码、发邮件全都可以伪造。

    如何防范 CSRF 攻击?可以注意以下几点:

    • 关键操作只接受 POST 请求

    • 验证码

      CSRF 攻击的过程,往往是在用户不知情的情况下构造网络请求。所以如果使用验证码,那么每次操作都需要用户进行互动,从而简单有效的防御了CSRF攻击。

      但是如果你在一个网站作出任何举动都要输入验证码会严重影响用户体验,所以验证码一般只出现在特殊操作里面,或者在注册时候使用。

    • 检测 Referer

      常见的互联网页面与页面之间是存在联系的,比如你在 www.baidu.com 应该是找不到通往www.google.com 的链接的,再比如你在论坛留言,那么不管你留言后重定向到哪里去了,之前的那个网址一定会包含留言的输入框,这个之前的网址就会保留在新页面头文件的 Referer

    通过检查 Referer 的值,我们就可以判断这个请求是合法的还是非法的,但是问题出在服务器不是任何时候都能接受到 Referer 的值,所以 Referer Check 一般用于监控 CSRF 攻击的发生,而不用来抵御攻击。

    • Token

      目前主流的做法是使用 Token 抵御 CSRF 攻击。下面通过分析 CSRF 攻击来理解为什么 Token 能够有效

      CSRF 攻击要成功的条件在于攻击者能够预测所有的参数从而构造出合法的请求。所以根据不可预测性原则,我们可以对参数进行加密从而防止 CSRF 攻击。

      另一个更通用的做法是保持原有参数不变,另外添加一个参数 Token,其值是随机的。这样攻击者因为不知道 Token 而无法构造出合法的请求进行攻击。

    Token 使用原则

    • Token 要足够随机————只有这样才算不可预测
    • Token 是一次性的,即每次请求成功后要更新Token————这样可以增加攻击难度,增加预测难度
    • Token 要注意保密性————敏感操作使用 post,防止 Token 出现在 URL 中

    注意:过滤用户输入的内容不能阻挡 csrf,我们需要做的是过滤请求的来源

  • XSS(Cross Site Scripting,跨站脚本攻击)

    XSS 全称“跨站脚本”,是注入攻击的一种。其特点是不对服务器端造成任何伤害,而是通过一些正常的站内交互途径,例如发布评论,提交含有 JavaScript 的内容文本。这时服务器端如果没有过滤或转义掉这些脚本,作为内容发布到了页面上,其他用户访问这个页面的时候就会运行这些脚本。

    运行预期之外的脚本带来的后果有很多中,可能只是简单的恶作剧——一个关不掉的窗口:

    while (true) {
        alert("你关不掉我~");
    }

    也可以是盗号或者其他未授权的操作。

    XSS 是实现 CSRF 的诸多途径中的一条,但绝对不是唯一的一条。一般习惯上把通过 XSS 来实现的 CSRF 称为 XSRF。

    如何防御 XSS 攻击?

    理论上,所有可输入的地方没有对输入数据进行处理的话,都会存在 XSS 漏洞,漏洞的危害取决于攻击代码的威力,攻击代码也不局限于 script。防御 XSS 攻击最简单直接的方法,就是过滤用户的输入。

    如果不需要用户输入 HTML,可以直接对用户的输入进行 HTML escape 。下面一小段脚本:

    <script>window.location.href=”http://www.baidu.com”;</script>

    经过 escape 之后就成了:

    &lt;script&gt;window.location.href=&quot;http://www.baidu.com&quot;&lt;/script&gt;

    它现在会像普通文本一样显示出来,变得无毒无害,不能执行了。

    当我们需要用户输入 HTML 的时候,需要对用户输入的内容做更加小心细致的处理。仅仅粗暴地去掉 script 标签是没有用的,任何一个合法 HTML 标签都可以添加 onclick 一类的事件属性来执行 JavaScript。更好的方法可能是,将用户的输入使用 HTML 解析库进行解析,获取其中的数据。然后根据用户原有的标签属性,重新构建 HTML 元素树。构建的过程中,所有的标签、属性都只从白名单中拿取。

HTTP

HTTPS 基本过程

HTTPS 即 HTTP over TLS,是一种在加密信道进行 HTTP 内容传输的协议。

TLS 的早期版本叫做 SSL。SSL 的 1.0, 2.0, 3.0 版本均已经被废弃,出于安全问题考虑广大浏览器也不再对老旧的 SSL 版本进行支持了,因此这里我们就统一使用 TLS 名称了。

TLS 的基本过程如下(取自 what-happens-when-zh_CN):

  • 客户端发送一个 ClientHello 消息到服务器端,消息中同时包含了它的 Transport Layer Security (TLS) 版本,可用的加密算法和压缩算法。
  • 服务器端向客户端返回一个 ServerHello 消息,消息中包含了服务器端的 TLS 版本,服务器所选择的加密和压缩算法,以及数字证书认证机构(Certificate Authority,缩写 CA)签发的服务器公开证书,证书中包含了公钥。客户端会使用这个公钥加密接下来的握手过程,直到协商生成一个新的对称密钥。证书中还包含了该证书所应用的域名范围(Common Name,简称 CN),用于客户端验证身份。
  • 客户端根据自己的信任 CA 列表,验证服务器端的证书是否可信。如果认为可信(具体的验证过程在下一节讲解),客户端会生成一串伪随机数,使用服务器的公钥加密它。这串随机数会被用于生成新的对称密钥
  • 服务器端使用自己的私钥解密上面提到的随机数,然后使用这串随机数生成自己的对称主密钥
  • 客户端发送一个 Finished 消息给服务器端,使用对称密钥加密这次通讯的一个散列值
  • 服务器端生成自己的 hash 值,然后解密客户端发送来的信息,检查这两个值是否对应。如果对应,就向客户端发送一个 Finished 消息,也使用协商好的对称密钥加密
  • 从现在开始,接下来整个 TLS 会话都使用对称秘钥进行加密,传输应用层(HTTP)内容

从上面的过程可以看到,TLS 的完整过程需要三个算法(协议),密钥交互算法,对称加密算法,和消息认证算法(TLS 的传输会使用 MAC(message authentication code) 进行完整性检查)。

我们以 Github 网站使用的 TLS 为例,使用浏览器可以看到它使用的加密为 TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256。其中密钥交互算法是 ECDHE_RSA,对称加密算法是 AES_128_GCM,消息认证(MAC)算法为 SHA256

TLS 证书机制

HTTPS 过程中很重要的一个步骤,是服务器需要有 CA 颁发的证书,客户端根据自己的信任 CA 列表验证服务器的身份。现代浏览器中,证书验证的过程依赖于证书信任链。

所谓证书信任链,即一个证书要依靠上一级证书来证明自己是可信的,最顶层的证书被称为根证书,拥有根证书的机构被称为根 CA。

还是以 Github 为例,在浏览器中我们可以看到它的证书信任链如下:

DigiCert High Assurance EV Root CA -> DigiCert SHA2 Extended Validation Server CA -> Github.com

从上到下即 Root CA -> 二级 CA -> 网站。

前面提到,证书当中包括 CN(Common Name),浏览器在验证证书的同时,也会验证 CN 的正确性。即不光需要验证“这是一个合法的证书”,还需要验证“这是一个用于 Github.com 的证书”。

既然所有的信任,最终要落到根 CA 上,根证书本身又是怎么获得的呢?答案也很简单,根证书一般是操作系统自带的。不管是桌面系统 Windows,macOS 还是移动端系统 Android, iOS 都会内置一系列根证书。随着操作系统本身的升级,根证书也会随着升级进行更新。

对浏览器而已,浏览器当然也有选择信任某个根证书的权利。Chrome 浏览器一般是跟随系统根证书信任的。Firefox 浏览器通常是使用自带的一套证书信任机制,不受系统证书的影响。

在使用 curl 等工具时,我们还可以自行选择证书进行信任。

有权威的信任,最终都要落到一个单点信任,不管是 Root CA,还是微软,苹果,谷歌等操作系统厂商。

中间人攻击

HTTPS 的过程并不是密不透风的,HTTPS 有若干漏洞,给中间人攻击(Man In The Middle Attack,简称 MITM)提供了可能。

所谓中间人攻击,指攻击者与通讯的两端分别建立独立的联系,并交换其所收到的数据,使通讯的两端认为他们正在通过一个私密的连接与对方直接对话,但事实上整个会话都被攻击者完全控制。在中间人攻击中,攻击者可以拦截通讯双方的通话并插入新的内容。

SSL 剥离

SSL 剥离即阻止用户使用 HTTPS 访问网站。由于并不是所有网站都只支持 HTTPS,大部分网站会同时支持 HTTP 和 HTTPS 两种协议。用户在访问网站时,也可能会在地址栏中输入 http:// 的地址,第一次的访问完全是明文的,这就给了攻击者可乘之机。通过攻击 DNS 响应,攻击者可以将自己变成中间人。

DNS 作为基于 UDP 的协议是相当不安全的,为了保证 DNS 的安全可以使用 DNS over TCP 等机制,这里不赘述了。

HSTS

为了防止上面说的这种情况,一种叫做 HSTS 的技术被引入了。HSTS(HTTP Strict Transport Security)是用于强制浏览器使用 HTTPS 访问网站的一种机制。它的基本机制是在服务器返回的响应中,加上一个特殊的头部,指示浏览器对于此网站,强制使用 HTTPS 进行访问:

1
Strict-Transport-Security: max-age=31536000; includeSubdomains; preload

可以看到如果这个过期时间非常长,就是导致在很长一段时间内,浏览器都会强制使用 HTTPS 访问该网站。

HSTS 有一个很明显的缺点,是需要等待第一个服务器的影响中的头部才能生效,但如果第一次访问该网站就被攻击呢?为了解决这个问题,浏览器中会带上一些网站的域名,被称为 HSTS preload list。对于在这个 list 的网站来说,直接强制使用 HTTPS。

伪造证书攻击

HSTS 只解决了 SSL 剥离的问题,然而即使在全程使用 HTTPS 的情况下,我们仍然有可能被监听。

假设我们想访问 www.google.com,但我们的 DNS 服务器被攻击了,指向的 IP 地址并非 Google 的服务器,而是攻击者的 IP。当攻击者的服务器也有合法的证书的时候,我们的浏览器就会认为对方是 Google 服务器,从而信任对方。这样,攻击者便可以监听我们和谷歌之前的所有通信了。

可以看到攻击者有两步需要操作,第一步是需要攻击 DNS 服务器。第二步是攻击者自己的证书需要被用户信任,这一步对于用户来说是很难控制的,需要证书颁发机构能够控制自己不滥发证书。

2015 年 Google 称发现赛门铁克旗下的 Thawte 未经同意签发了众多域名的数千个证书,其中包括 Google 旗下的域名和不存在的域名。当年 12 月,Google 发布公告称 Chrome、Android 及其他 Google 产品将不再信任赛门铁克旗下的”Class 3 Public Primary CA”根证书。

2016 年 Mozilla 发现沃通 CA 存在严重的信任问题,例如偷签 github.com 的证书,故意倒填证书日期绕过浏览器对 SHA-1 证书的限制等,将停止信任 WoSign 和 StartCom 签发的新证书。

HPKP

HPKP 技术是为了解决伪造证书攻击而诞生的。

HPKP(Public Key Pinning Extension for HTTP)在 HSTS 上更进一步,HPKP 直接在返回头中存储服务器的公钥指纹信息,一旦发现指纹和实际接受到的公钥有差异,浏览器就可以认为正在被攻击:

1
Public-Key-Pins: pin-sha256="base64=="; max-age=expireTime [; includeSubDomains][; report-uri="reportURI"]

和 HSTS 类似,HPKP 也依赖于服务器的头部返回,不能解决第一次访问的问题,浏览器本身也会内置一些 HPKP 列表。

HPKP 技术仍然不能阻止第一次访问的攻击问题,部署和配置 HPKP 相当繁琐,一旦网站配置错误,就会导致网站证书验证失败,且在过期时间内无法有效恢复。HPKP 的机制也引来了一些安全性问题。Chrome 67 中废除了对 HPKP 的支持,在 Chrome 72 中 HPKP 被彻底移除。

IP

IP 协议简介

IP 协议位于 TCP/IP 协议的第三层——网络层。与传输层协议相比,网络层的责任是提供点到点(hop by hop)的服务,而传输层(TCP/UDP)则提供端到端(end to end)的服务。

IP 地址的分类

A类地址

B类地址

C类地址

D 类地址

广播与多播

广播和多播仅用于UDP(TCP是面向连接的)。

  • 广播

    一共有四种广播地址:

    1. 受限的广播

      受限的广播地址为255.255.255.255。该地址用于主机配置过程中IP数据报的目的地址,在任何情况下,router不转发目的地址为255.255.255.255的数据报,这样的数据报仅出现在本地网络中。

    2. 指向网络的广播

      指向网络的广播地址是主机号为全1的地址。A类网络广播地址为netid.255.255.255,其中netid为A类网络的网络号。

      一个router必须转发指向网络的广播,但它也必须有一个不进行转发的选择。

    3. 指向子网的广播

      指向子网的广播地址为主机号为全1且有特定子网号的地址。作为子网直接广播地址的IP地址需要了解子网的掩码。例如,router收到128.1.2.255的数据报,当B类网路128.1的子网掩码为255.255.255.0时,该地址就是指向子网的广播地址;但是如果子网掩码为255.255.254.0,该地址就不是指向子网的广播地址。

    4. 指向所有子网的广播

      指向所有子网的广播也需要了解目的网络的子网掩码,以便与指向网络的广播地址区分开来。指向所有子网的广播地址的子网号和主机号为全1.例如,如果子网掩码为255.255.255.0,那么128.1.255.255就是一个指向所有子网的广播地址。

      当前的看法是这种广播是陈旧过时的,更好的方式是使用多播而不是对所有子网的广播。

    广播示例:

    1
    2
    3
    4
    5
    6
    7
    PING 192.168.0.255 (192.168.0.255): 56 data bytes
    64 bytes from 192.168.0.107: icmp_seq=0 ttl=64 time=0.199 ms
    64 bytes from 192.168.0.106: icmp_seq=0 ttl=64 time=45.357 ms
    64 bytes from 192.168.0.107: icmp_seq=1 ttl=64 time=0.203 ms
    64 bytes from 192.168.0.106: icmp_seq=1 ttl=64 time=269.475 ms
    64 bytes from 192.168.0.107: icmp_seq=2 ttl=64 time=0.102 ms
    64 bytes from 192.168.0.106: icmp_seq=2 ttl=64 time=189.881 ms

    可以看到的确收到了来自两个主机的答复,其中 192.168.0.107 是本机地址。

  • 多播

    多播又叫组播,使用D类地址,D类地址分配的28bit均用作多播组号而不再表示其他。

    多播组地址包括1110的最高4bit和多播组号。它们通常可以表示为点分十进制数,范围从224.0.0.0到239.255.255.255。

    多播的出现减少了对应用不感兴趣主机的处理负荷。

    多播的特点:

    • 允许一个或多个发送者(组播源)发送单一的数据包到多个接收者(一次的,同时的)的网络技术
    • 可以大大的节省网络带宽,因为无论有多少个目标地址,在整个网络的任何一条链路上只传送单一的数据包
    • 多播技术的核心就是针对如何节约网络资源的前提下保证服务质量。

    多播示例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    PING 224.0.0.1 (224.0.0.1): 56 data bytes
    64 bytes from 192.168.0.107: icmp_seq=0 ttl=64 time=0.081 ms
    64 bytes from 192.168.0.106: icmp_seq=0 ttl=64 time=123.081 ms
    64 bytes from 192.168.0.107: icmp_seq=1 ttl=64 time=0.122 ms
    64 bytes from 192.168.0.106: icmp_seq=1 ttl=64 time=67.312 ms
    64 bytes from 192.168.0.107: icmp_seq=2 ttl=64 time=0.132 ms
    64 bytes from 192.168.0.106: icmp_seq=2 ttl=64 time=447.073 ms
    64 bytes from 192.168.0.107: icmp_seq=3 ttl=64 time=0.132 ms
    64 bytes from 192.168.0.106: icmp_seq=3 ttl=64 time=188.800 ms

BGP

  • 边界网关协议(BGP)是运行于 TCP 上的一种自治系统的路由协议

  • BGP 是唯一一个用来处理像因特网大小的网络的协议,也是唯一能够妥善处理好不相关路由域间的多路连接的协议

  • BGP是一种外部网关协议(Exterior Gateway Protocol,EGP),与OSPF、RIP等内部网关协议(Interior Gateway Protocol,IGP)不同,BGP不在于发现和计算路由,而在于控制路由的传播和选择最佳路由

  • BGP使用TCP作为其传输层协议(端口号179),提高了协议的可靠性

  • BGP既不是纯粹的矢量距离协议,也不是纯粹的链路状态协议

  • BGP支持CIDR(Classless Inter-Domain Routing,无类别域间路由)

  • 路由更新时,BGP只发送更新的路由,大大减少了BGP传播路由所占用的带宽,适用于在Internet上传播大量的路由信息

  • BGP路由通过携带AS路径信息彻底解决路由环路问题

  • BGP提供了丰富的路由策略,能够对路由实现灵活的过滤和选择

  • BGP易于扩展,能够适应网络新的发展

TCP

TCP 的特性

  • TCP 提供一种面向连接的、可靠的字节流服务
  • 在一个 TCP 连接中,仅有两方进行彼此通信。广播和多播不能用于 TCP
  • TCP 使用校验和,确认和重传机制来保证可靠传输
  • TCP 给数据分节进行排序,并使用累积确认保证数据的顺序不变和非重复
  • TCP 使用滑动窗口机制来实现流量控制,通过动态改变窗口的大小进行拥塞控制

注意:TCP 并不能保证数据一定会被对方接收到,因为这是不可能的。TCP 能够做到的是,如果有可能,就把数据递送到接收方,否则就(通过放弃重传并且中断连接这一手段)通知用户。因此准确说 TCP 也不是 100% 可靠的协议,它所能提供的是数据的可靠递送或故障的可靠通知。

三次握手与四次挥手

所谓三次握手(Three-way Handshake),是指建立一个 TCP 连接时,需要客户端和服务器总共发送3个包。

三次握手的目的是连接服务器指定端口,建立 TCP 连接,并同步连接双方的序列号和确认号,交换 TCP 窗口大小信息。在 socket 编程中,客户端执行 connect() 时。将触发三次握手。

  • 第一次握手(SYN=1, seq=x):

    客户端发送一个 TCP 的 SYN 标志位置1的包,指明客户端打算连接的服务器的端口,以及初始序号 X,保存在包头的序列号(Sequence Number)字段里。

    发送完毕后,客户端进入 SYN_SEND 状态。

  • 第二次握手(SYN=1, ACK=1, seq=y, ACKnum=x+1):

    服务器发回确认包(ACK)应答。即 SYN 标志位和 ACK 标志位均为1。服务器端选择自己 ISN 序列号,放到 Seq 域里,同时将确认序号(Acknowledgement Number)设置为客户的 ISN 加1,即X+1。
    发送完毕后,服务器端进入 SYN_RCVD 状态。

  • 第三次握手(ACK=1,ACKnum=y+1)

    客户端再次发送确认包(ACK),SYN 标志位为0,ACK 标志位为1,并且把服务器发来 ACK 的序号字段+1,放在确定字段中发送给对方,并且在数据段放写ISN的+1

    发送完毕后,客户端进入 ESTABLISHED 状态,当服务器端接收到这个包时,也进入 ESTABLISHED 状态,TCP 握手结束。

三次握手的过程的示意图如下:

three-way-handshake

TCP 的连接的拆除需要发送四个包,因此称为四次挥手(Four-way handshake),也叫做改进的三次握手。客户端或服务器均可主动发起挥手动作,在 socket 编程中,任何一方执行 close() 操作即可产生挥手操作。

  • 第一次挥手(FIN=1,seq=x)

    假设客户端想要关闭连接,客户端发送一个 FIN 标志位置为1的包,表示自己已经没有数据可以发送了,但是仍然可以接受数据。

    发送完毕后,客户端进入 FIN_WAIT_1 状态。

  • 第二次挥手(ACK=1,ACKnum=x+1)

    服务器端确认客户端的 FIN 包,发送一个确认包,表明自己接受到了客户端关闭连接的请求,但还没有准备好关闭连接。

    发送完毕后,服务器端进入 CLOSE_WAIT 状态,客户端接收到这个确认包之后,进入 FIN_WAIT_2 状态,等待服务器端关闭连接。

  • 第三次挥手(FIN=1,seq=y)

    服务器端准备好关闭连接时,向客户端发送结束连接请求,FIN 置为1。

    发送完毕后,服务器端进入 LAST_ACK 状态,等待来自客户端的最后一个ACK。

  • 第四次挥手(ACK=1,ACKnum=y+1)

    客户端接收到来自服务器端的关闭请求,发送一个确认包,并进入 TIME_WAIT状态,等待可能出现的要求重传的 ACK 包。

    服务器端接收到这个确认包之后,关闭连接,进入 CLOSED 状态。

    客户端等待了某个固定时间(两个最大段生命周期,2MSL,2 Maximum Segment Lifetime)之后,没有收到服务器端的 ACK ,认为服务器端已经正常关闭连接,于是自己也关闭连接,进入 CLOSED 状态。

四次挥手的示意图如下:

four-way-handshake

SYN攻击

  • 什么是 SYN 攻击(SYN Flood)?

    在三次握手过程中,服务器发送 SYN-ACK 之后,收到客户端的 ACK 之前的 TCP 连接称为半连接(half-open connect)。此时服务器处于 SYN_RCVD 状态。当收到 ACK 后,服务器才能转入 ESTABLISHED 状态.

    SYN 攻击指的是,攻击客户端在短时间内伪造大量不存在的IP地址,向服务器不断地发送SYN包,服务器回复确认包,并等待客户的确认。由于源地址是不存在的,服务器需要不断的重发直至超时,这些伪造的SYN包将长时间占用未连接队列,正常的SYN请求被丢弃,导致目标系统运行缓慢,严重者会引起网络堵塞甚至系统瘫痪。

    SYN 攻击是一种典型的 DoS/DDoS 攻击。

  • 如何检测 SYN 攻击?

    检测 SYN 攻击非常的方便,当你在服务器上看到大量的半连接状态时,特别是源IP地址是随机的,基本上可以断定这是一次SYN攻击。在 Linux/Unix 上可以使用系统自带的 netstats 命令来检测 SYN 攻击。

  • 如何防御 SYN 攻击?

    SYN攻击不能完全被阻止,除非将TCP协议重新设计。我们所做的是尽可能的减轻SYN攻击的危害,常见的防御 SYN 攻击的方法有如下几种:

    • 缩短超时(SYN Timeout)时间
    • 增加最大半连接数
    • 过滤网关防护
    • SYN cookies技术

TCP KeepAlive

TCP 的连接,实际上是一种纯软件层面的概念,在物理层面并没有“连接”这种概念。TCP 通信双方建立交互的连接,但是并不是一直存在数据交互,有些连接会在数据交互完毕后,主动释放连接,而有些不会。在长时间无数据交互的时间段内,交互双方都有可能出现掉电、死机、异常重启等各种意外,当这些意外发生之后,这些 TCP 连接并未来得及正常释放,在软件层面上,连接的另一方并不知道对端的情况,它会一直维护这个连接,长时间的积累会导致非常多的半打开连接,造成端系统资源的消耗和浪费,为了解决这个问题,在传输层可以利用 TCP 的 KeepAlive 机制实现来实现。主流的操作系统基本都在内核里支持了这个特性。

TCP KeepAlive 的基本原理是,隔一段时间给连接对端发送一个探测包,如果收到对方回应的 ACK,则认为连接还是存活的,在超过一定重试次数之后还是没有收到对方的回应,则丢弃该 TCP 连接。

TCP-Keepalive-HOWTO 有对 TCP KeepAlive 特性的详细介绍,有兴趣的同学可以参考。这里主要说一下,TCP KeepAlive 的局限。首先 TCP KeepAlive 监测的方式是发送一个 probe 包,会给网络带来额外的流量,另外 TCP KeepAlive 只能在内核层级监测连接的存活与否,而连接的存活不一定代表服务的可用。例如当一个服务器 CPU 进程服务器占用达到 100%,已经卡死不能响应请求了,此时 TCP KeepAlive 依然会认为连接是存活的。因此 TCP KeepAlive 对于应用层程序的价值是相对较小的。需要做连接保活的应用层程序,例如 QQ,往往会在应用层实现自己的心跳功能。

UDP

UDP 简介

UDP 是一个简单的传输层协议。和 TCP 相比,UDP 有下面几个显著特性:

  • UDP 缺乏可靠性。UDP 本身不提供确认,序列号,超时重传等机制。UDP 数据报可能在网络中被复制,被重新排序。即 UDP 不保证数据报会到达其最终目的地,也不保证各个数据报的先后顺序,也不保证每个数据报只到达一次
  • UDP 数据报是有长度的。每个 UDP 数据报都有长度,如果一个数据报正确地到达目的地,那么该数据报的长度将随数据一起传递给接收方。而 TCP 是一个字节流协议,没有任何(协议上的)记录边界。
  • UDP 是无连接的。UDP 客户和服务器之前不必存在长期的关系。UDP 发送数据报之前也不需要经过握手创建连接的过程。
  • UDP 支持多播和广播。

Socket

Socket 基本概念

Socket 是对 TCP/IP 协议族的一种封装,是应用层与TCP/IP协议族通信的中间软件抽象层。从设计模式的角度看来,Socket其实就是一个门面模式,它把复杂的TCP/IP协议族隐藏在Socket接口后面,对用户来说,一组简单的接口就是全部,让Socket去组织数据,以符合指定的协议。

Socket 还可以认为是一种网络间不同计算机上的进程通信的一种方法,利用三元组(ip地址,协议,端口)就可以唯一标识网络中的进程,网络中的进程通信可以利用这个标志与其它进程进行交互。

Socket 起源于 Unix ,Unix/Linux 基本哲学之一就是“一切皆文件”,都可以用“打开(open) –> 读写(write/read) –> 关闭(close)”模式来进行操作。因此 Socket 也被处理为一种特殊的文件。

写一个简易的 WebServer

一个简易的 Server 的流程如下:

  • 1.建立连接,接受一个客户端连接。
  • 2.接受请求,从网络中读取一条 HTTP 请求报文。
  • 3.处理请求,访问资源。
  • 4.构建响应,创建带有 header 的 HTTP 响应报文。
  • 5.发送响应,传给客户端。

省略流程 3,大体的程序与调用的函数逻辑如下:

  • socket() 创建套接字
  • bind() 分配套接字地址
  • listen() 等待连接请求
  • accept() 允许连接请求
  • read()/write() 数据交换
  • close() 关闭连接

代码如下:

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <unistd.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <string>
#include <cstring>
#include <iostream>

using namespace std;

const int port = 9090;
const int buffer_size = 1<<20;
const int method_size = 1<<10;
const int filename_size = 1<<10;
const int common_buffer_size = 1<<10;

void handleError(const string &message);
void requestHandling(int *sock);
void sendError(int *sock);
void sendData(int *sock, char *filename);
void sendHTML(int *sock, char *filename);
void sendJPG(int *sock, char *filename);

int main()
{
int server_sock;
int client_sock;

struct sockaddr_in server_address;
struct sockaddr_in client_address;

socklen_t client_address_size;

server_sock = socket(PF_INET, SOCK_STREAM, 0);

if (server_sock == -1)
{
handleError("socket error");
}

memset(&server_address,0,sizeof(server_address));
server_address.sin_family = AF_INET;
server_address.sin_addr.s_addr = htonl(INADDR_ANY);
server_address.sin_port = htons(port);

if(bind(server_sock,(struct sockaddr*)&server_address, sizeof(server_address)) == -1){
handleError("bind error");
}

if(listen(server_sock, 5) == -1) {
handleError("listen error");
}

while(true) {
client_address_size = sizeof(client_address);
client_sock = accept(server_sock, (struct sockaddr*) &client_address, &client_address_size);

if (client_sock == -1) {
handleError("accept error");
}
requestHandling(&client_sock);
}

//system("open http://127.0.0.1:9090/index.html");
close(server_sock);

return 0;
}

void requestHandling(int *sock){
int client_sock = *sock;
char buffer[buffer_size];
char method[method_size];
char filename[filename_size];

read(client_sock, buffer, sizeof(buffer)-1);

if(!strstr(buffer, "HTTP/")) {
sendError(sock);
close(client_sock);
return;
}

strcpy(method, strtok(buffer," /"));
strcpy(filename, strtok(NULL, " /"));

if(0 != strcmp(method, "GET")) {
sendError(sock);
close(client_sock);
return;
}

sendData(sock, filename);
}

void sendData(int *sock, char *filename) {
int client_sock = *sock;
char buffer[common_buffer_size];
char type[common_buffer_size];

strcpy(buffer, filename);

strtok(buffer, ".");
strcpy(type, strtok(NULL, "."));

if(0 == strcmp(type, "html")){
sendHTML(sock, filename);
}else if(0 == strcmp(type, "jpg")){
sendJPG(sock, filename);
}else{
sendError(sock);
close(client_sock);
return ;
}
}

void sendHTML(int *sock, char *filename) {
int client_sock = *sock;
char buffer[buffer_size];
FILE *fp;

char status[] = "HTTP/1.0 200 OK\r\n";
char header[] = "Server: A Simple Web Server\r\nContent-Type: text/html\r\n\r\n";

write(client_sock, status, strlen(status));
write(client_sock, header, strlen(header));

fp = fopen(filename, "r");
if(!fp){
sendError(sock);
close(client_sock);
handleError("failed to open file");
return ;
}

fgets(buffer,sizeof(buffer), fp);
while(!feof(fp)) {
write(client_sock, buffer, strlen(buffer));
fgets(buffer, sizeof(buffer), fp);
}

fclose(fp);
close(client_sock);
}

void sendJPG(int *sock, char *filename) {
int client_sock = *sock;
char buffer[buffer_size];
FILE *fp;
FILE *fw;

char status[] = "HTTP/1.0 200 OK\r\n";
char header[] = "Server: A Simple Web Server\r\nContent-Type: image/jpeg\r\n\r\n";

write(client_sock, status, strlen(status));
write(client_sock, header, strlen(header));

fp = fopen(filename, "rb");
if(NULL == fp){
sendError(sock);
close(client_sock);
handleError("failed to open file");
return ;
}

fw = fdopen(client_sock, "w");
fread(buffer, 1, sizeof(buffer), fp);
while (!feof(fp)){
fwrite(buffer, 1, sizeof(buffer), fw);
fread(buffer, 1, sizeof(buffer), fp);
}

fclose(fw);
fclose(fp);
close(client_sock);
}

void handleError(const string &message) {
cout<<message;
exit(1);
}

void sendError(int *sock){
int client_sock = *sock;

char status[] = "HTTP/1.0 400 Bad Request\r\n";
char header[] = "Server: A Simple Web Server\r\nContent-Type: text/html\r\n\r\n";
char body[] = "<html><head><title>Bad Request</title></head><body><p>400 Bad Request</p></body></html>";

write(client_sock, status, sizeof(status));
write(client_sock, header, sizeof(header));
write(client_sock, body, sizeof(body));
}

1. Basic Operations

a. export

Displays all environment variables. If you want to get details of a specific variable, use echo $VARIABLE_NAME.

1
export

Example:

1
2
3
4
$ export
LANG=en_US.UTF-8
LC_CTYPE=en_US.UTF-8
LESS=-R

b. whatis

whatis shows description for user commands, system calls, library functions, and others in manual pages

1
whatis something

Example:

1
2
$ whatis bash
bash (1) - GNU Bourne-Again SHell

c. whereis

whereis searches for executables, source files, and manual pages using a database built by system automatically.

1
whereis name

Example:

1
2
$ whereis java
/usr/bin/java

d. which

which searches for executables in the directories specified by the environment variable PATH. This command will print the full path of the executable(s).

1
which program_name

Example:

1
2
$ which java
/usr/bin/java

e. clear

Clears content on window.

1.1. File Operations

cat chmod chown cp diff file find gunzip gzcat gzip head
lpq lpr lprm ls more mv rm tail touch

a. cat

It can be used for the following purposes under UNIX or Linux.

  • Display text files on screen
  • Copy text files
  • Combine text files
  • Create new text files
1
2
3
4
cat filename
cat file1 file2
cat file1 file2 > newcombinedfile
cat < file1 > file2 #copy file1 to file2

b. chmod

The chmod command stands for “change mode” and allows you to change the read, write, and execute permissions on your files and folders. For more information on this command check this link.

1
chmod -options filename

c. chown

The chown command stands for “change owner”, and allows you to change the owner of a given file or folder, which can be a user and a group. Basic usage is simple forward first comes the user (owner), and then the group, delimited by a colon.

1
chown -options user:group filename

d. cp

Copies a file from one location to other.

1
cp filename1 filename2

Where filename1 is the source path to the file and filename2 is the destination path to the file.

e. diff

Compares files, and lists their differences.

1
diff filename1 filename2

f. file

Determine file type.

1
file filename

Example:

1
2
$ file index.html
index.html: HTML document, ASCII text

g. find

Find files in directory

1
find directory options pattern

Example:

1
2
$ find . -name README.md
$ find /home/user1 -name '*.png'

h. gunzip

Un-compresses files compressed by gzip.

1
gunzip filename

i. gzcat

Lets you look at gzipped file without actually having to gunzip it.

1
gzcat filename

j. gzip

Compresses files.

1
gzip filename

k. head

Outputs the first 10 lines of file

1
head filename

l. lpq

Check out the printer queue.

1
lpq

Example:

1
2
3
4
$ lpq
Rank Owner Job File(s) Total Size
active adnanad 59 demo 399360 bytes
1st adnanad 60 (stdin) 0 bytes

m. lpr

Print the file.

1
lpr filename

n. lprm

Remove something from the printer queue.

1
lprm jobnumber

o. ls

Lists your files. ls has many options: -l lists files in ‘long format’, which contains the exact size of the file, who owns the file, who has the right to look at it, and when it was last modified. -a lists all files, including hidden files. For more information on this command check this link.

1
ls option

Example:

$ ls -la
rwxr-xr-x   33 adnan  staff    1122 Mar 27 18:44 .
drwxrwxrwx  60 adnan  staff    2040 Mar 21 15:06 ..
-rw-r--r--@  1 adnan  staff   14340 Mar 23 15:05 .DS_Store
-rw-r--r--   1 adnan  staff     157 Mar 25 18:08 .bumpversion.cfg
-rw-r--r--   1 adnan  staff    6515 Mar 25 18:08 .config.ini
-rw-r--r--   1 adnan  staff    5805 Mar 27 18:44 .config.override.ini
drwxr-xr-x  17 adnan  staff     578 Mar 27 23:36 .git
-rwxr-xr-x   1 adnan  staff    2702 Mar 25 18:08 .gitignore

p. more

Shows the first part of a file (move with space and type q to quit).

1
more filename

q. mv

Moves a file from one location to other.

1
mv filename1 filename2

Where filename1 is the source path to the file and filename2 is the destination path to the file.

Also it can be used for rename a file.

1
mv old_name new_name

r. rm

Removes a file. Using this command on a directory gives you an error.
rm: directory: is a directory
To remove a directory you have to pass -r which will remove the content of the directory recursively. Optionally you can use -f flag to force the deletion i.e. without any confirmations etc.

1
rm filename

s. tail

Outputs the last 10 lines of file. Use -f to output appended data as the file grows.

1
tail filename

t. touch

Updates access and modification time stamps of your file. If it doesn’t exists, it’ll be created.

1
touch filename

Example:

1
$ touch trick.md

1.2. Text Operations

awk cut echo egrep fgrep fmt grep nl sed sort
tr uniq wc

a. awk

awk is the most useful command for handling text files. It operates on an entire file line by line. By default it uses whitespace to separate the fields. The most common syntax for awk command is

1
awk '/search_pattern/ { action_to_take_if_pattern_matches; }' file_to_parse

Lets take following file /etc/passwd. Here’s the sample data that this file contains:

1
2
3
4
5
root:x:0:0:root:/root:/usr/bin/zsh
daemon:x:1:1:daemon:/usr/sbin:/usr/sbin/nologin
bin:x:2:2:bin:/bin:/usr/sbin/nologin
sys:x:3:3:sys:/dev:/usr/sbin/nologin
sync:x:4:65534:sync:/bin:/bin/sync

So now lets get only username from this file. Where -F specifies that on which base we are going to separate the fields. In our case it’s :. { print $1 } means print out the first matching field.

1
awk -F':' '{ print $1 }' /etc/passwd

After running the above command you will get following output.

1
2
3
4
5
root
daemon
bin
sys
sync

For more detail on how to use awk, check following link.

b. cut

Remove sections from each line of files

example.txt

1
red riding hood went to the park to play

show me columns 2 , 7 , and 9 with a space as a separator

1
cut -d " " -f2,7,9 example.txt
1
riding park play

c. echo

Display a line of text

display “Hello World”

1
echo Hello World
1
Hello World

display “Hello World” with newlines between words

1
echo -ne "Hello\nWorld\n"
1
2
Hello
World

d. egrep

Print lines matching a pattern - Extended Expression (alias for: ‘grep -E’)

example.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Lorem ipsum
dolor sit amet,
consetetur
sadipscing elitr,
sed diam nonumy
eirmod tempor
invidunt ut labore
et dolore magna
aliquyam erat, sed
diam voluptua. At
vero eos et
accusam et justo
duo dolores et ea
rebum. Stet clita
kasd gubergren,
no sea takimata
sanctus est Lorem
ipsum dolor sit
amet.

display lines that have either “Lorem” or “dolor” in them.

1
2
3
egrep '(Lorem|dolor)' example.txt
or
grep -E '(Lorem|dolor)' example.txt
1
2
3
4
5
6
Lorem ipsum
dolor sit amet,
et dolore magna
duo dolores et ea
sanctus est Lorem
ipsum dolor sit

e. fgrep

Print lines matching a pattern - FIXED pattern matching (alias for: ‘grep -F’)

example.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Lorem ipsum
dolor sit amet,
consetetur
sadipscing elitr,
sed diam nonumy
eirmod tempor
foo (Lorem|dolor)
invidunt ut labore
et dolore magna
aliquyam erat, sed
diam voluptua. At
vero eos et
accusam et justo
duo dolores et ea
rebum. Stet clita
kasd gubergren,
no sea takimata
sanctus est Lorem
ipsum dolor sit
amet.

Find the exact string ‘(Lorem|dolor)’ in example.txt

1
2
3
fgrep '(Lorem|dolor)' example.txt
or
grep -F '(Lorem|dolor)' example.txt
1
foo (Lorem|dolor)

f. fmt

Simple optimal text formatter

example: example.txt (1 line)

1
Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.

output the lines of example.txt to 20 character width

1
cat example.txt | fmt -w 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Lorem ipsum
dolor sit amet,
consetetur
sadipscing elitr,
sed diam nonumy
eirmod tempor
invidunt ut labore
et dolore magna
aliquyam erat, sed
diam voluptua. At
vero eos et
accusam et justo
duo dolores et ea
rebum. Stet clita
kasd gubergren,
no sea takimata
sanctus est Lorem
ipsum dolor sit
amet.

g. grep

Looks for text inside files. You can use grep to search for lines of text that match one or many regular expressions, and outputs only the matching lines.

1
grep pattern filename

Example:

1
2
3
4
$ grep admin /etc/passwd
_kadmin_admin:*:218:-2:Kerberos Admin Service:/var/empty:/usr/bin/false
_kadmin_changepw:*:219:-2:Kerberos Change Password Service:/var/empty:/usr/bin/false
_krb_kadmin:*:231:-2:Open Directory Kerberos Admin Service:/var/empty:/usr/bin/false

You can also force grep to ignore word case by using -i option. -r can be used to search all files under the specified directory, for example:

1
$ grep -r admin /etc/

And -w to search for words only. For more detail on grep, check following link.

h. nl

Number lines of files

example.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Lorem ipsum
dolor sit amet,
consetetur
sadipscing elitr,
sed diam nonumy
eirmod tempor
invidunt ut labore
et dolore magna
aliquyam erat, sed
diam voluptua. At
vero eos et
accusam et justo
duo dolores et ea
rebum. Stet clita
kasd gubergren,
no sea takimata
sanctus est Lorem
ipsum dolor sit
amet.

show example.txt with line numbers

1
nl -s". " example.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 1. Lorem ipsum
2. dolor sit amet,
3. consetetur
4. sadipscing elitr,
5. sed diam nonumy
6. eirmod tempor
7. invidunt ut labore
8. et dolore magna
9. aliquyam erat, sed
10. diam voluptua. At
11. vero eos et
12. accusam et justo
13. duo dolores et ea
14. rebum. Stet clita
15. kasd gubergren,
16. no sea takimata
17. sanctus est Lorem
18. ipsum dolor sit
19. amet.

i. sed

Stream editor for filtering and transforming text

example.txt

1
Hello This is a Test 1 2 3 4

replace all spaces with hyphens

1
sed 's/ /-/g' example.txt
1
Hello-This-is-a-Test-1-2-3-4

replace all digits with “d”

1
sed 's/[0-9]/d/g' example.txt
1
Hello This is a Test d d d d

j. sort

Sort lines of text files

example.txt

1
2
3
4
5
6
7
f
b
c
g
a
e
d

sort example.txt

1
sort example.txt
1
2
3
4
5
6
7
a
b
c
d
e
f
g

randomize a sorted example.txt

1
sort example.txt | sort -R
1
2
3
4
5
6
7
b
f
a
c
d
g
e

k. tr

Translate or delete characters

example.txt

1
Hello World Foo Bar Baz!

take all lower case letters and make them upper case

1
cat example.txt | tr 'a-z' 'A-Z'
1
HELLO WORLD FOO BAR BAZ!

take all spaces and make them into newlines

1
cat example.txt | tr ' ' '\n'
1
2
3
4
5
Hello
World
Foo
Bar
Baz!

l. uniq

Report or omit repeated lines

example.txt

1
2
3
4
5
6
7
8
a
a
b
a
b
c
d
c

show only unique lines of example.txt (first you need to sort it, otherwise it won’t see the overlap)

1
sort example.txt | uniq
1
2
3
4
a
b
c
d

show the unique items for each line, and tell me how many instances it found

1
sort example.txt | uniq -c
1
2
3
4
3 a
2 b
2 c
1 d

m. wc

Tells you how many lines, words and characters there are in a file.

1
wc filename

Example:

1
2
$ wc demo.txt
7459 15915 398400 demo.txt

Where 7459 is lines, 15915 is words and 398400 is characters.

1.3. Directory Operations

cd mkdir pwd

a. cd

Moves you from one directory to other. Running this

1
$ cd

moves you to home directory. This command accepts an optional dirname, which moves you to that directory.

1
cd dirname

b. mkdir

Makes a new directory.

1
mkdir dirname

You can use this to create multiple directories at once within your current directory.

1
mkdir 1stDirectory 2ndDirectory 3rdDirectory

You can also use this to create parent directories at the same time. For instance, if you wanted a directory named ‘project1’ in another subdirectory at ‘/samples/bash/projects/‘, you could run:

1
mkdir /samples/bash/projects/project1

If any of these directories did no already exist, they would be created as well.

c. pwd

Tells you which directory you currently are in.

1
pwd

1.4. SSH, System Info & Network Operations

bg cal date df dig du fg finger jobs last
man passwd ping ps quota scp ssh top uname uptime
w wget whoami whois

a. bg

Lists stopped or background jobs; resume a stopped job in the background.

b. cal

Shows the month’s calendar.

c. date

Shows the current date and time.

d. df

Shows disk usage.

e. dig

Gets DNS information for domain.

1
dig domain

f. du

Shows the disk usage of files or directories. For more information on this command check this link

1
du [option] [filename|directory]

Options:

  • -h (human readable) Displays output it in kilobytes (K), megabytes (M) and gigabytes (G).
  • -s (supress or summarize) Outputs total disk space of a directory and supresses reports for subdirectories.

Example:

1
2
du -sh pictures
1.4M pictures

g. fg

Brings the most recent job in the foreground.

h. finger

Displays information about user.

1
finger username

i. jobs

Lists the jobs running in the background, giving the job number.

j. last

Lists your last logins of specified user.

1
last yourUsername

k. man

Shows the manual for specified command.

1
man command

l. passwd

Allows the current logged user to change their password.

m. ping

Pings host and outputs results.

1
ping host

n. ps

Lists your processes.

1
ps -u yourusername

Use the flags ef. e for every process and f for full listing.

1
ps -ef

o. quota

Shows what your disk quota is.

1
quota -v

p. scp

Transfer files between a local host and a remote host or between two remote hosts.

copy from local host to remote host

1
scp source_file user@host:directory/target_file

copy from remote host to local host

1
2
scp user@host:directory/source_file target_file
scp -r user@host:directory/source_folder target_folder

This command also accepts an option -P that can be used to connect to specific port.

1
scp -P port user@host:directory/source_file target_file

q. ssh

ssh (SSH client) is a program for logging into and executing commands on a remote machine.

1
ssh user@host

This command also accepts an option -p that can be used to connect to specific port.

1
ssh -p port user@host

r. top

Displays your currently active processes.

s. uname

Shows kernel information.

1
uname -a

t. uptime

Shows current uptime.

u. w

Displays who is online.

v. wget

Downloads file.

1
wget file

w. whoami

Return current logged in username.

x. whois

Gets whois information for domain.

1
whois domain

1.5. Process Monitoring Operations

kill killall & nohup

a. kill

Kills (ends) the processes with the ID you gave.

1
kill PID

b. killall

Kill all processes with the name.

1
killall processname

c. &

The & symbol instructs the command to run as a background process in a subshell.

1
command &

d. nohup

nohup stands for “No Hang Up”. This allows to run command/process or shell script that can continue running in the background after you log out from a shell.

1
nohup command

Combine it with & to create background processes

1
nohup command &

2. Basic Shell Programming

The first line that you will write in bash script files is called shebang. This line in any script determines the script’s ability to be executed like a standalone executable without typing sh, bash, python, php etc beforehand in the terminal.

1
#!/usr/bin/env bash

2.1. Variables

Creating variables in bash is similar to other languages. There are no data types. A variable in bash can contain a number, a character, a string of characters, etc. You have no need to declare a variable, just assigning a value to its reference will create it.

Example:

1
str="hello world"

The above line creates a variable str and assigns “hello world” to it. The value of variable is retrieved by putting the $ in the beginning of variable name.

Example:

1
echo $str   # hello world

2.2. Array

Like other languages bash has also arrays. An array is a variable containing multiple values. There’s no maximum limit on the size of array. Arrays in bash are zero based. The first element is indexed with element 0. There are several ways for creating arrays in bash which are given below.

Examples:

1
2
3
4
5
array[0]=val
array[1]=val
array[2]=val
array=([2]=val [0]=val [1]=val)
array=(val val val)

To display a value at specific index use following syntax:

1
${array[i]}     # where i is the index

If no index is supplied, array element 0 is assumed. To find out how many values there are in the array use the following syntax:

1
${#array[@]}

Bash has also support for the ternary conditions. Check some examples below.

1
2
3
4
${varname:-word}    # if varname exists and isn't null, return its value; otherwise return word
${varname:=word} # if varname exists and isn't null, return its value; otherwise set it word and then return its value
${varname:+word} # if varname exists and isn't null, return word; otherwise return null
${varname:offset:length} # performs substring expansion. It returns the substring of $varname starting at offset and up to length characters

2.3 String Substitution

Check some of the syntax on how to manipulate strings

1
2
3
4
5
6
7
${variable#pattern}         # if the pattern matches the beginning of the variable's value, delete the shortest part that matches and return the rest
${variable##pattern} # if the pattern matches the beginning of the variable's value, delete the longest part that matches and return the rest
${variable%pattern} # if the pattern matches the end of the variable's value, delete the shortest part that matches and return the rest
${variable%%pattern} # if the pattern matches the end of the variable's value, delete the longest part that matches and return the rest
${variable/pattern/string} # the longest match to pattern in variable is replaced by string. Only the first match is replaced
${variable//pattern/string} # the longest match to pattern in variable is replaced by string. All matches are replaced
${#varname} # returns the length of the value of the variable as a character string

2.4. Functions

As in almost any programming language, you can use functions to group pieces of code in a more logical way or practice the divine art of recursion. Declaring a function is just a matter of writing function my_func { my_code }. Calling a function is just like calling another program, you just write its name.

1
2
3
function name() {
shell commands
}

Example:

1
2
3
4
5
6
7
8
9
10
#!/bin/bash
function hello {
echo world!
}
hello

function say {
echo $1
}
say "hello world!"

When you run the above example the hello function will output “world!”. The above two functions hello and say are identical. The main difference is function say. This function, prints the first argument it receives. Arguments, within functions, are treated in the same manner as arguments given to the script.

2.5. Conditionals

The conditional statement in bash is similar to other programming languages. Conditions have many form like the most basic form is if expression then statement where statement is only executed if expression is true.

1
2
3
4
5
if [ expression ]; then
will execute only if expression is true
else
will execute if expression is false
fi

Sometime if conditions becoming confusing so you can write the same condition using the case statements.

1
2
3
4
5
6
7
case expression in
pattern1 )
statements ;;
pattern2 )
statements ;;
...
esac

Expression Examples:

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
statement1 && statement2  # both statements are true
statement1 || statement2 # at least one of the statements is true

str1=str2 # str1 matches str2
str1!=str2 # str1 does not match str2
str1<str2 # str1 is less than str2
str1>str2 # str1 is greater than str2
-n str1 # str1 is not null (has length greater than 0)
-z str1 # str1 is null (has length 0)

-a file # file exists
-d file # file exists and is a directory
-e file # file exists; same -a
-f file # file exists and is a regular file (i.e., not a directory or other special type of file)
-r file # you have read permission
-s file # file exists and is not empty
-w file # you have write permission
-x file # you have execute permission on file, or directory search permission if it is a directory
-N file # file was modified since it was last read
-O file # you own file
-G file # file's group ID matches yours (or one of yours, if you are in multiple groups)

file1 -nt file2 # file1 is newer than file2
file1 -ot file2 # file1 is older than file2

-lt # less than
-le # less than or equal
-eq # equal
-ge # greater than or equal
-gt # greater than
-ne # not equal

2.6. Loops

There are three types of loops in bash. for, while and until.

Different for Syntax:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for x := 1 to 10 do
begin
statements
end

for name [in list]
do
statements that can use $name
done

for (( initialisation ; ending condition ; update ))
do
statements...
done

while Syntax:

1
2
3
while condition; do
statements
done

until Syntax:

1
2
3
until condition; do
statements
done

3. Tricks

Set an alias

Open bash_profile by running following command vim ~/.bash_profile

alias dockerlogin=’ssh www-data@adnan.local -p2222’ # add your alias in .bash_profile

To quickly go to a specific directory

vim ~/.bashrc

export hotellogs=”/workspace/hotel-api/storage/logs”

1
2
source ~/.bashrc
cd $hotellogs

Re-execute the previous command

This goes back to the days before you could rely on keyboards to have an “up” arrow key, but can still be useful.
To run the last command in your history

!!
A common error is to forget to use sudo to prefix a command requiring privileged execution. Instead of typing the whole command again, you can:
sudo !!
This would change a mkdir somedir into sudo mkdir somedir

Exit traps

Make your bash scripts more robust by reliably performing cleanup.

1
2
3
4
5
function finish {
# your cleanup here. e.g. kill any forked processes
jobs -p | xargs kill
}
trap finish EXIT

Saving your environment variables

When you do export FOO = BAR, your variable is only exported in this current shell and all its children, to persist in the future you can simply append in your ~/.bash_profile file the command to export your variable

1
echo export FOO=BAR >> ~/.bash_profile

Accessing your scripts

You can easily access your scripts by creating a bin folder in your home with mkdir ~/bin, now all the scripts you put in this folder you can access in any directory.

If you can not access, try append the code below in your ~/.bash_profile file and after do source ~/.bash_profile.

1
2
3
4
# set PATH so it includes user's private bin if it exists
if [ -d "$HOME/bin" ] ; then
PATH="$HOME/bin:$PATH"
fi

4. Debugging

You can easily debug the bash script by passing different options to bash command. For example -n will not run commands and check for syntax errors only. -v echo commands before running them. -x echo commands after command-line processing.

1
2
3
bash -n scriptname
bash -v scriptname
bash -x scriptname

Customer Obsession

Leaders start with the customer and work backwards. They work vigorously to earn and keep customer trust. Although leaders pay attention to competitors, they obsess over customers.

Ownership

Leaders are owners. They think long term and don’t sacrifice long-term value for short-term results. They act on behalf of the entire company, beyond just their own team. They never say “that’s not my job.”

Invent and Simplify

Leaders expect and require innovation and invention from their teams and always find ways to simplify. They are externally aware, look for new ideas from everywhere, and are not limited by “not invented here.” As we do new things, we accept that we may be misunderstood for long periods of time.

Are Right, A Lot

Leaders are right a lot. They have strong judgment and good instincts. They seek diverse perspectives and work to disconfirm their beliefs.

Learn and Be Curious

Leaders are never done learning and always seek to improve themselves. They are curious about new possibilities and act to explore them.

Hire and Develop the Best

Leaders raise the performance bar with every hire and promotion. They recognize exceptional talent, and willingly move them throughout the organization. Leaders develop leaders and take seriously their role in coaching others. We work on behalf of our people to invent mechanisms for development like Career Choice.

Insist on the Highest Standards

Leaders have relentlessly high standards -; many people may think these standards are unreasonably high. Leaders are continually raising the bar and drive their teams to deliver high quality products, services, and processes. Leaders ensure that defects do not get sent down the line and that problems are fixed so they stay fixed.

Think Big

Thinking small is a self-fulfilling prophecy. Leaders create and communicate a bold direction that inspires results. They think differently and look around corners for ways to serve customers.

Bias for Action

Speed matters in business. Many decisions and actions are reversible and do not need extensive study. We value calculated risk taking.

Frugality

Accomplish more with less. Constraints breed resourcefulness, self-sufficiency, and invention. There are no extra points for growing headcount, budget size, or fixed expense.

Earn Trust

Leaders listen attentively, speak candidly, and treat others respectfully. They are vocally self-critical, even when doing so is awkward or embarrassing. Leaders do not believe their or their team’s body odor smells of perfume. They benchmark themselves and their teams against the best.

Dive Deep

Leaders operate at all levels, stay connected to the details, audit frequently, and are skeptical when metrics and anecdote differ. No task is beneath them.

Have Backbond; Disagree and Commit

Leaders are obligated to respectfully challenge decisions when they disagree, even when doing so is uncomfortable or exhausting. Leaders have conviction and are tenacious. They do not compromise for the sake of social cohesion. Once a decision is determined, they commit wholly.

Deliver Results

Leaders focus on the key inputs for their business and deliver them with the right quality and in a timely fashion. Despite setbacks, they rise to the occasion and never settle.

How To Read Source Code

What do we mean when we say “reading source code”?

Reading for comprehension

… to find bugs

… to find interactions

… to review

… to see the interface

… to learn!


Reading isn’t linear

We skip back and forth from chapter to chapter, module to module. We can read the module straight through but we won’t have the definitions of things from other modules. We can read in execution order, but we won’t know where we’re going more than one call site down.


Reading Order

Do you start at the entry point of a package?

How about in a browser?

Maybe find the biggest source code file and read that first.

Try setting a breakpoint early and tracing down through functions in a debugger.

Try setting a breakpoint deep in the code, and reading each function in the call stack.


Kinds of source code

  • Javascript
  • C++
  • ES6
  • Coffee Script
  • Shell Script

  • SNOBOL
  • APL
  • Befunge
  • Forth
  • Perl
  • Other people’s javascript

Another way to think of kinds of source code

  • Glue
  • Interface-defining
  • Implementation
  • Algorithmic
  • Configuring
  • Tasking

There’s a lot of study of algorithmic source code out there because that’s what academia produces: algorithms, the little, often mathematical ways of doing things. All the others are a lot more nebulous but I think a lot more interesting. They’re certainly the bulk of what most people write when they’re programming computers.

Of course, sometimes, something does more than one of these things. Many times, in fact. Figuring out what it’s trying to be can be one of the first tasks.


What’s ‘Glue’?

Not all the interfaces we want to use play nice together. Glue is the plumbing connecting things together. Middleware, promises vs callbacks binding code, inflating arguments into objects or breaking objects apart. All that’s glue.


How do you read glue?

We’re looking for how two interfaces are shaped differently, and what’s common between them.


This is from Ben Drucker’s stream-to-promise

1
2
3
4
5
6
internals.writable = function (stream) {
return new Promise(function (resolve, reject) {
stream.once('finish', resolve);
stream.once('error', reject);
});
};

The two interfaces we’re talking about here are node streams and promises.

The things they have in common are that they do work until they finish, in node with an event, in promises by calling the resolution functions.

Now the thing you can notice while you’re reading is that promises really can only be resolved once, but streams can actually emit the same event multiple times. They don’t usually, but as programmers we usually know the difference between can’t and shouldn’t.


More glue!

1
2
3
4
5
var record = {
name: (input.name || '').trim(),
age: isNaN(Number(input.age)) ? null : Number(input.age),
email: validateEmail(input.email.trim())
}

More things to think about in glue: How are errors handled?

It’s worth asking if any of these things throw? Do they delete bad values? Maybe they coerce them into being okay-enough values? Are these the right choices for the context they’re operating in? Are conversions lossy?


What’s interface-defining code?

You know how you have some modules that are really only used one or two places, they’re kinda internal, and you hope nobody looks at them too hard?

Interface-defining is the opposite of that. It’s the hard boundaries of your module.


From node’s events.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
exports.usingDomains = false;

function EventEmitter() { }
exports.EventEmitter = EventEmitter;

EventEmitter.prototype.setMaxListeners = function setMaxListeners(n) { };
EventEmitter.prototype.emit = function emit(type) { };
EventEmitter.prototype.addListener = function addListener(type, listener) { };
EventEmitter.prototype.on = EventEmitter.prototype.addListener;
EventEmitter.prototype.once = function once(type, listener) { };
EventEmitter.prototype.removeListener = function removeListener(type, listener) { };
EventEmitter.prototype.removeAllListeners = function removeAllListeners(type) {};
EventEmitter.prototype.listeners = function listeners(type) { };
EventEmitter.listenerCount = function(emitter, type) { };

We’re defining the interface for EventEmitter here.

Some things to ask here are is this complete? What guarantees does this make? Are internal details exposed?

If you have strong interface contracts, this is where you should expect to find them.

Like glue code, look for how errors are handled and exposed. Is that consistent? Does it distinguish errors due to internal inconsistency from errors because the user of the interface didn’t understand it?


Implementation


1
2
startRouting: function() {
this.router = this.router || this.constructor.map(K);
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
var router = this.router;
var location = get(this, 'location');
var container = this.container;
var self = this;
var initialURL = get(this, 'initialURL');
var initialTransition;

// Allow the Location class to cancel the router setup while it refreshes
// the page
if (get(location, 'cancelRouterSetup')) {
return;
}

this._setupRouter(router, location);

container.register('view:default', _MetamorphView);
container.register('view:toplevel', EmberView.extend());

location.onUpdateURL(function(url) {
self.handleURL(url);
});

if (typeof initialURL === "undefined") {
initialURL = location.getURL();
}
initialTransition = this.handleURL(initialURL);
if (initialTransition && initialTransition.error) {
throw initialTransition.error;
}

From Ember.Router

This is what that always needs more documentation about why and not so much about what.

Things to look for when reading here are how it fits into the larger whole.

What’s coming from the public interface to this module? What needs validation? Are these variables going to contain what we think they contain? What other parts does this touch? What’s the risk to changing it when adding new features? What might break? Do we have tests for that?

What’s the lifetime of these variables? (this is an easy one: This looks really well designed and doesn’t store needless state with a long lifetime.) Though maybe we should look at _setupRouter


Process entailment

Or, looking forward: How much is required to use this thing correctly?

and backward: If we’re here, what got us to this point?

It’s pretty easy to see what functions call what other functions. However, the reverse is more interesting! So one of the things you can look for when reading source code, and in particular the implementation bits is look at what things have to happen to set up the state the process needs to be in to begin.

Is that state explicit, passed in via parameters? Is it assumed to be there, as an instance variable or property? Is there a single path to get there, with an obvious place that state is set up? Or is it diffuse?


Algorithms

So algorithmic code is a kind of special case of implementation code. It’s not so exposed to the outside world, it’s the meat of a program. Quite often it’s business logic or the core processes of the software.


1
2
3
4
5
6
7
8
9
10
11
12
13
function Grammar(rules) {
// Processing The Grammar
//
// Here we begin defining a grammar given the raw rules, terminal
// symbols, and symbolic references to rules
//
// The input is a list of rules.
//
// The input grammar is amended with a final rule, the 'accept' rule,
// which if it spans the parse chart, means the entire grammar was
// accepted. This is needed in the case of a nulling start symbol.
rules.push(Rule('_accept', [Ref('start')]));
rules.acceptRule = rules.length - 1;

This bit is from a parser engine I’ve been working on called lotsawa. More on the next slide.

It’s been said a lot that good comments say why something is done or done that way, rather than what it’s doing. Algorithms usually need more explanation of what’s going on since if they were trivial, they’d probably be built into our standard library. Quite often to get good performance out of something, the exactly what-and-how matters a lot.

This is the stuff that those of you with CS degrees get to drool over (or maybe have traumatic memories of).


1
2
3
4
5
6
// Build a list of all the symbols used in the grammar so they can be numbered instead of referred to
// by name, and therefore their presence can be represented by a single bit in a set.
function censusSymbols() {
var out = [];
rules.forEach(function(r) {
if (!~out.indexOf(r.name)) out.push(r.name);
  r.symbols.forEach(function(s, i) {
    var symNo = out.indexOf(s.name);
    if (!~out.indexOf(s.name)) {
      symNo = out.length;
      out.push(s.name);
    }

    r.symbols[i] = symNo;
  });

  r.sym = out.indexOf(r.name);
});

return out;
}

rules.symbols = censusSymbols();

Reads like a math paper, doesn’t it?

One of the things that you usually need to see in algorithmic code is the actual data structures. This one is building a list of symbols and making sure there’s no duplicates.

Look also for hints as to the running time of the algorithm. You can see in this part, I’ve got two loops. In Big-O notation, that’s O(n * m), then you can see that there’s an indexOf inside that. That’s another loop in Javascript, so that actually adds another factor to the running time. (twice – looks like I could make this more optimal by re-using one of the values here) Good thing this isn’t the main part of the algorithm!


Configuration

The line between source code and configuration file is super thin. There’s a constant tension between having a configuration be expressive and readable and direct.


1
2
3
4
5
6
app.configure('production', 'staging', function() {
app.enable('emails');
});
app.configure('test', function() {
app.disable('emails');
});

An example using Javascript for configuration.

What we can run into here is combinatorial explosion of options. How many environments do we configure? Then, how many things do we configure for a specific instance of that environment. It’s really easy to go overboard and end up with all the possible permutations, and to have bugs that only show up in one of them. Keeping an eye out for how many degrees of freedom the configuration allows is super useful.


1
2
3
4
5
6
"express": {
"env": "", // NOTE: `env` is managed by the framework. This value will be overwritten.
"x-powered-by": false,
"views": "path:./views",
"mountpath": "/"
},
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"middleware": {

"compress": {
"enabled": false,
"priority": 10,
"module": "compression"
},

"favicon": {
"enabled": false,
"priority": 30,
"module": {
"name": "serve-favicon",
"arguments": [ "resolve:kraken-js/public/favicon.ico" ]
}
},
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

A bit of `kraken` config file.

Kraken took a 'low power language' approach to configuration and chose JSON. A little more "configuration" and a little less "source code". One of the goals was keeping that combinatorial explosion under control. There's a reason a lot of tools use simple key-value pairs or ini-style files for configuration, even though they're not terribly expressive.

---

Configuration source code has some interesting and unique constraints that are worth looking for.

* Lifetime
* Machine writability
* Responsible people vary a lot more
* Have to fit in weird places like environment variables
* Often store security-sensitive information

---

Tasking
-------

---

What do charging 50 credit cards, building a complex piece of software with a compiler and build tools, and sending 100 emails have in common?

Transactionality. Often, some piece of the system needs to happen exactly once, and not at all if there's an error. A compiler that leaves bad build products around is a great source of bugs. Double charging customers is bad. Flooding someone's inbox because of a retry cycle is terrible.

Resumabilty. A need to continue where they left off given the state of the system.

Sequentiality. If they're not strictly linear processes, there's usually a very directed flow through the code. Loops tend to be big ones, around the whole shebang.

---

Reading Messy Code
------------------

---

So how do you deal with this?

```javascript
DuplexCombination.prototype.on = function(ev, fn) {
switch (ev) {
case 'data':
case 'end':
case 'readable':
this.reader.on(ev, fn);
return this
case 'drain':
case 'finish':
this.writer.on(ev, fn);
return this
default:
return Duplex.prototype.on.call(this, ev, fn);
}
};

You are seeing that right. That’s reverse indendation. Blame Isaac.


Rose tinted glasses!

standard -F dc.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
DuplexCombination.prototype.on = function (ev, fn) {
switch (ev) {
case 'data':
case 'end':
case 'readable':
this.reader.on(ev, fn)
return this
case 'drain':
case 'finish':
this.writer.on(ev, fn)
return this
default:
return Duplex.prototype.on.call(this, ev, fn)
}
}

It’s okay to use tools while reading!


How do you read this?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(function(t,e){if(typeof define==="function"&&define.amd){define(["underscore","
jquery","exports"],function(i,r,s){t.Backbone=e(t,s,i,r)})}else if(typeof export
s!=="undefined"){var i=require("underscore");e(t,exports,i)}else{t.Backbone=e(t,
{},t._,t.jQuery||t.Zepto||t.ender||t.$)}})(this,function(t,e,i,r){var s=t.Backbo
ne;var n=[];var a=n.push;var o=n.slice;var h=n.splice;e.VERSION="1.1.2";e.$=r;e.
noConflict=function(){t.Backbone=s;return this};e.emulateHTTP=false;e.emulateJSO
N=false;var u=e.Events={on:function(t,e,i){if(!c(this,"on",t,[e,i])||!e)return t
his;this._events||(this._events={});var r=this._events[t]||(this._events[t]=[]);
r.push({callback:e,context:i,ctx:i||this});return this},once:function(t,e,r){if(
!c(this,"once",t,[e,r])||!e)return this;var s=this;var n=i.once(function(){s.off
(t,n);e.apply(this,arguments)});n._callback=e;return this.on(t,n,r)},off:functio
n(t,e,r){var s,n,a,o,h,u,l,f;if(!this._events||!c(this,"off",t,[e,r]))return thi
s;if(!t&&!e&&!r){this._events=void 0;return this}o=t?[t]:i.keys(this._events);fo
r(h=0,u=o.length;h<u;h++){t=o[h];if(a=this._events[t]){this._events[t]=s=[];if(e
||r){for(l=0,f=a.length;l<f;l++){n=a[l];if(e&&e!==n.callback&&e!==n.callback._ca
llback||r&&r!==n.context){s.push(n)}}}if(!s.length)delete this._events[t]}}retur
n this},trigger:function(t){if(!this._events)return this;var e=o.call(arguments,
1);if(!c(this,"trigger",t,e))return this;var i=this._events[t];var r=this._event
s.all;if(i)f(i,e);if(r)f(r,arguments);return this},stopListening:function(t,e,r)
{var s=this._listeningTo;if(!s)return this;var n=!e&&!r;if(!r&&typeof e==="objec

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



---

`uglifyjs -b < backbone-min.js`

```javascript
(function(t, e) {
if (typeof define === "function" && define.amd) {
define([ "underscore", "jquery", "exports" ], function(i, r, s) {
t.Backbone = e(t, s, i, r);
});
} else if (typeof exports !== "undefined") {
var i = require("underscore");
e(t, exports, i);
} else {
t.Backbone = e(t, {}, t._, t.jQuery || t.Zepto || t.ender || t.$);
}
})(this, function(t, e, i, r) {
var s = t.Backbone;
var n = [];
var a = n.push;
var o = n.slice;
var h = n.splice;
e.VERSION = "1.1.2";
e.$ = r;
e.noConflict = function() {

Human Parts

Or: guessing intent is dangerous but you learn so much


There’s a lot of tricks for figuring out what the author of something meant.


Look for guards and coercions

1
2
if (typeof arg != 'number') throw new TypeError("arg must be a number");

Looks like the domain of whatever function we’re in is ‘numbers’.


1
2
arg = Number(arg)

Coerce things to numeric. Same domain as above, but doesn’t reject errors via exceptions. There might be NaNs though. Probably smart to read and check if there’s comparisons that will be false against those.


Look for defaults

1
2
arg = arg || {}

Default to an empty object.

1
2
arg = (arg == null ? true : arg)

Default to true only if a value wasn’t explicitly passed.


Look for layers

req and res from Express are tied to the web; how deep do they go?

Is there an interface boundary you can find?


Look for tracing

Are there inspection points?

Debug logs?

Do those form a complete narrative? Or are they ad-hoc leftovers from the last few bugs?


Look for reflexivity

Are identifiers being dynamically generated?

Is there eval? Metaprogramming? New function creation?

func.toString() is your friend!


Look at lifetimes

  • Who initializes this?
  • When does it change?
  • Who changes it?
  • Is this information somewhere else in the mean time?
  • Is it ever inconsistent?

^ Somewhere, someone typed the value you see into a keyboard, generated it from a random number generator, or computed it and saved it.

^ Somewhere else, some time else, that value will affect some human or humans. Who are these people?

^ What or who chooses who they are?

^ Is that value ever going to change?

^ Who changes it?


Look for hidden state machines

^ Sometimes boolean variables get used together as a decomposed state machine

^ For example, the variables isReadied and isFinished might show a state machine like so:

1
2
var isReadied = false;
var isFinished = false;

Or

START -> READY -> FINISHED


Look for hidden state machines

1
2
3
4
5
6
7

| isReadied | isFinished | state |
| --------- | ---------- | -------- |
| false | false | START |
| false | true | invalid |
| true | false | READY |
| true | true | FINISHED |

^ Note that they can also express the state !isReadied && isFinished – which might be an interesting source of bugs, if something can end up at the finished state without first being ready.


Look for composition and inheritance

Is this made of parts I can recognize? Do those parts have names?


Look for common operations

map.

reduce.

cross-join.


It’s time to go read some source code.

Enjoy!

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

整理学习到的databse知识。

Storage

Hierachy (speed fast to slow):

​ CPU Register -> Cache -> Main Memory -> Disk -> Tapes

Disk Capacity

​ Disk Capacity = #tracks per surface x (2 x #platter) x #sector per track x byte per sector.

  • Access time = seek time + rotational delay + transfer time + other delay

    • Seek time: time to move the arm to position disk head on the right track.
    • Rotational delay: time to wait for sector to rotate under the disk head.
    • Average rotational delay: time for 1/2 revolution.
    • transfer time: block size / transfer rate.
    Buffer Management

​ Pages in memory is like blocks in hard disk.

Example 1
1
2
3
Given a total revolution of 7200 RPM.
One rotation = 1/(7200/60s)*1000ms = 8.33ms
Average rotational latency = 4.16ms
Example 2
1
2
3
4
5
6
7
8
9
3600 RPM = 60 revolutions/s -> 1 rev = 16.66 ms
128 cylinders = 2^7
10% overhead between blocks
time over useful data = 16.66 x 0.9 = 14.99ms
time over gaps = 16.66 x 0.1 = 1.66ms

T1 = time to read one random block
T1 = seek + rotational delay + transfer time
T1 = 25 + 16.66/2 + 0.117 = 33.45ms

Record Layout

Conventional Indexes

Types:
  1. Dense index: index record appears for every search-key value
  2. Sparse index: contains index records for only some search-key value
  3. Multilevel index: if primary index does not fit in memory, access becomes expensive.
    1. Outer index: a sparse index of primary index.
    2. Inner index: the primary index file
  4. Duplicate keys:
    1. Dense index: only keep record in index for first data record with each search key value.
    2. Sparse index: has key-pointer pairs corresponding to the first search key on each block of the data file.

B+ Tree

Characteristics:

​ full(packed) and balanced(almost uniform height).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Consider a DBMS has following characteristics: Pointers:4 bytes. Keys: 4 bytes. Blocks:100 bytes.
Compute the maximum number of records we can index with:
a).2-level B Tree
b).2-level B+ Tree

a).2-level B Tree
Find largest integer value of n such that 4n+4(2n+1)<100. n=8.
Root has 8 keys + 8 record pointers + 9 children pointers
= 8 x 4 + 8 x 4 + 9 x 4 = 100bytes.
Each of 9 children has 12 records pointers
= 12 x (4 + 4) + 4 = 100bytes.
So maximum # of records = 12 x 9 + 8 = 116.

b).2-level B+ Tree
Find largest integer value of n such that 4n+(4n+1)<100. n=12.
Root has 12 keys + 13 children pointers
= 12 x 4 + 13 x 4 = 100 bytes.
Each of 13 children has 12 record pointers
= 12 x (4 + 4) + 4 = 100 bytes.
So maximum # of records = 13 x 12 = 156.

B Tree

Hashing

Characteristics:

$$
Avg\ occupancy = \frac{r}{n\times\gamma}
$$

n: The number of buckets that is currently in use.

r: current number of search keys stored in the buckets.

$\gamma$: block size(# search keys that can be stored in 1 block).

Relational Algebra

Algebra expressions / Translate SQL into relational algebra / Equivlaence.

Query Process
  • parsing: translating the query into a parsing tree.
  • query rewrite: the parse tree is transformed into an expression tree of relational algebra (logical query plan)
  • physical plan generation: translate the logical plan into a physical plan
    • select algorithms to implement each operator
    • choose order of operations.
Physical Query Plan
  • Sequential-Scan
    • Read tuples from the relation R by reading data blocks - one block at a time from disk to memory.
  • Index-Scan
    • The relation R must have an index
    • The index is scanned to find blocks that contain the desired tuples.
    • All the blocks containing desired tuples are then read into the memory - one block at a time.
Clustered and unclustered files/relations/indexes
  • Clustered file: A file that stores records of one relation.
  • Unclustered file: A file that stores records of multiple relations.
  • Clustered index: Index that allows tuples to be read in an order that corresponds to physical order.
  • Relation R is clustered.
Operator I/O cost Explanation
Sequential-Scan B(R) Read all blocks, and there are B(R) blocks.
Index-Scan ≤B(R) Depends on number of values in the index is scanned.
  • Relation R is unclustered.
Operator I/O cost Explanation
Sequential-Scan ~T(R) Assuming next tuple is not found in the current block. We will read 1 block per tuple
Index-Scan ≤T(R) Depends on number of values in the index is scanned.
SQL grammer
1
2
3
4
5
6
7
8
9
10
11
12
<Query> ::= SELECT <SelList>
FROM <From List>
WHERE <Condition>

<SelList> ::= <Attribute> | <Attribute> , <SelList>

<FromList> ::= <Relation> | <Relation> , <FromList>

<Condition> ::= <Condition> AND <Condition> |
<Attribute> IN (<Query>) |
<Attribute> = <Attribute>
<Attribute> LIKE <Pattern>
Example of parse trees
1
2
3
4
SELECT movieTitle
FROM StarsIn, MovieStar
WHERE starName = name
AND birthdate LIKE '%1960'

Example 2 of parse trees
1
2
3
4
5
SELECT movieTitle
FROM StarsIn
WHERE starName IN (SELECT name
FROM MovieStar
WHERE birthdate LIKE '%1960')

example2OfParseTrees

Virtual Relation Pre-Processing
1
2
3
4
CREATE VIEW Paramount_Movies AS
(SELECT title, year
FROM Movies
WHERE StudioName = 'Paramount')

image-20191206021435872

Consider the following query on the virtual table Paramount_Movies:
1
2
3
SELECT	title
FROM Paramount_Movies
WHERE year = 1979

image-20191206021508616

Then, the virtual table is replaced by the corresponding logical query plan

image-20191206021527531

Convert Parse Tree into initial L.Q.P

convertParseTreeIntoInitialLQP

Set vs Bag semantics
  • Set semantics: No duplicate entries.
  • Bag semantics: Allow duplicate entries.
Operators
  • Selection
    • Syntax: σ c (R)
    • Set: { t | t ∈ R AND t fulfills c}
    • Bag: { $t^n$ | $t^n$ ∈ R AND t fulfills c}
  • Renaming
    • Syntax: ρ A (R)
    • Set: { t.A | t∈R}
    • Bag: { $(t.A)^n$ | $t^n$ ∈R}
    • Example: $ρ_c$←a(R)
  • Projection
    • Syntax: π A (R)
    • Set: { t.A | t∈R}
    • Bag: { $(t.A)^n$ | $t^n$ ∈R}
  • Joins
    • Theta, natural, cross-product, outer, anti
    • Cross Product
      • Syntax: R × S
      • Set: { (t,s) | t∈R AND s∈S}
      • Bag: { (t,s)^n×m | t^n ∈R AND s^m ∈S}
    • Join
      • Syntax: $R\bowtie_{c}S$
      • Set: { (t,s) | t∈R AND s∈S AND (t,s) matches c}
      • Bag: { $(t,s)^{n×m}$ |$t^n$ ∈R AND $s^m$ ∈S AND (t,s) matches c}
    • Natural Join
      • Syntax: $R\bowtie S$
      • All combinations of tuples from R and S that match on common attributes
      • A = common attributes of R and S
      • C = exclusive attributes of S
      • Set: {(t,s.C) | t∈R AND s∈S AND t.A=s.A}
      • Bag: {$(t,s.C)^{n×m}$ | $t^n$ ∈R AND $s^m$ ∈S AND t.A=s.A}
    • Left-outer Join
      • Syntax:$R=\bowtie{c} S$
      • Contains all tuples in R join S
      • Also includes every tuple in R that is not joined with a tuple in S, after padding a NULL
      • $R=\bowtie _{a=d}S$
      • left_outer_join_example
    • Right-outer Join
      • Syntax:$R\bowtie =S$
      • s∈S without match, fill R attributes with NULLrigh
      • $R\bowtie =_{a=d}S$
      • right_outer_join_example
    • Full-outer Join
      • Syntax: $R=\bowtie =_{c}S$
      • $R=\bowtie=_{a=d}S$
      • full_outer_join_example
  • Aggregation
    • All operators treat a relation as a bag of tuples.
    • SUM: computes the sum of a column with numerical values.
    • AVG: computes the average of a column with numerical values.
    • MIN and MAX: Natural Order
    • COUNT: computes the number of non-NULL tuples in a column.
    • Grouping and aggregation generally need to be implemented and optimized together
    • Syntax: $G\gamma A(R)$
      • A is list of aggregation functions
      • G is list of group by attributes
    • Build groups of tuples according G and compute the aggregation functions from each group
    • $b\gamma sum(a)(R)$
    • aggregation_example
  • Duplicate removal
    • Syntax: $\delta(R)$: is the relation containing exactly one copy of each tuple in R.
    • $\delta(R)$
    • duplicate_removal
  • Set operations.
  • Union, Intersection and Difference
    • Union
      • Syntax: $R\cup S$
      • unionExample
    • Intersection
      • Syntax: $R\cap S$
      • intersectionExample
    • Set Difference
      • Syntax: $R-S$
      • setExample

Canonical Translation to Relational Algebra

  • FROM clause into joins and crossproducts
  • WHERE clause into selection
  • SELECT clause into projection and renaming
    • If it has aggregation functions use aggregation
    • DISTINCT into duplicate removal
  • GROUP BY clause into aggregation
  • HAVING clause into selection
  • ORDER BY - no counter-part

Set Operations

  • UNION ALL into union
  • UNION duplicate removal over union
  • INTERSECT ALL into intersection
  • INTERSECT add duplicate removal
  • EXCEPT ALL into set difference
  • EXCEPT apply duplicate removal to inputs and then apply set difference

Conversion into Relational Algebra

Example 1
1
SELECT name FROM MovieStar WHERE birthdate LIKE '%1960';

image-20191206021614275

Example 2
1
2
3
SELECT movieTitle
FROM StarsIn, MovieStar
WHERE starName = name AND birthdate LIKE '%1960';

image-20191206021630157

Example 3
1
2
3
SELECT sum(a)
FROM R
GROUP BY b

image-20191206021643102

Example 4
1
2
3
4
5
SELECT dep, headcnt
FROM (SELECT count(*) AS headcnt, dep
FROM Employee
GROUP BY dep)
WHERE headcnt > 100

image-20191206021656629

Example 5
1
SELECT title FROM StarsIn WHERE starName IN (<Query>);

conversion_into_relationExample5

Query Processing and Optimization

Query Optimization

image-20191206022236925

Relational Algebra Optimization
Algebraic Laws:
  • Joins and Products
    • Natural joins and product are both associative and commutative
    • theta-join is commutative but not always associative.
  • Union and Intersect
    • Union and intersection are both associative and commutative
  • Laws for Bags and Sets can differ
    • Holds for sets, but guarentee for bags
  • Select
    • reduces the number of tuples (size of relation)
    • an important general rule in optimization is to push selects as far down the tree as possible
    • commutative
    • must be pushed through both arguments for union:
      • Union: σ p (R ∪ S) = σ p (R) ∪ σ p (S)
    • must be pushed through first arguments, optionally second for difference:
      • Difference: σ p (R - S) = σ p (R) - S
    • For the other operators it is only required that the selection be pushed to one argument.
      • σ p (R × S) = σ p (R) × S, if p contains only attributes from R
    • Derivation
      • image-20191206024632637
    • Amendment to the simple push down the select
      • Use this algebraic law in the reverse order: $\sigma _p(R\bowtie S) = \sigma _p(R)\bowtie S$ to push the σ year=1996 operation up the tree
      • image-20191206025216352
      • Then use the algebraic law in the forward order: $\sigma _p(R\bowtie S) = \sigma _p(R)\bowtie \sigma _p(S)$ push the $\sigma _{year=1996}$ operation down the tree.
      • image-20191206025413264
  • Projection
    • image-20191206025519667
  • Example
    • image-20191206030745130
    • image-20191206030801787
    • image-20191206030815185
    • image-20191206030824074
    • image-20191206030838597
  • Summary
    • Selections
      • push down tree as far as possible
      • if condition is an AND, split and push separately
      • sometimes need to push up before pushing down
    • Projections
      • can be pushed down
      • new ones can be added (but be careful)
    • duplicate eliminations can sometimes be removed (e.g., if one key)
    • Selection/product combinations
      • can sometimes be replaced with join
    • Many transformations lead to “promising” plans

Maven Introduction

整理学习到的maven知识。

Concept

  1. Maven 是一个可以用于构建和管理任何基于Java的项目的工具.
    1. Maven 不仅帮我们自动化构件,还能够抽象构建过程,提供构建任务实现。
    2. Maven 跨平台。
  2. Maven 还是一个依赖管理工具和项目管理工具,提供了中央仓库,能自动下载依赖。

Maven 常用命令

  • mvn clean:表示运行清理操作(会默认把target文件夹中的数据清理)。如果要把项目部署到生产环境,需使用mvn clean package命令,确保部署的是最新的内容。
  • mvn package: Maven根据pom文件里packaging的配置,决定是生成jar文件还是war文件,并放到target目录下。此命令需要在项目的根目录(也就是pom.xml文件所在的目录)下运行,Maven才知道打包哪个项目。
  • mvn test: 该命令执行后会去运行所有的单元测试
  • mvn clean install: 该命令会把你的项目打包并放到本地仓库,可以别人就可以引用了。
  • mvn site: 该命令会为你的项目生产一个文档站点,介绍你的项目,存储位置为target/site,该命令可能只有开源项目有用吧,毕竟平常没人会去关注你的项目信息。

Maven 使用

1
2
3
4
5
6
7
8
9
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>com.twitter</groupId>
    <artifactId>twitter</artifactId>
    <version>0.0.1-SNAPSHOT</version>
    <name>twitter</name>
</project>
  • 代码的第一行是XML头,指定了该xml文档的版本和编码方式。
  • project是所有pom.xml的根元素,它还声明了一些POM相关的命名空间及xsd元素。
  • 根元素下的第一个子元素modelVersion指定了当前的POM模型的版本,对于Maven3来说,它只能是4.0.0 代码中最重要是包含了groupId,artifactId和version了。这三个元素定义了一个项目基本的坐标,在Maven的世界,任何的jar、pom或者jar都是以基于这些基本的坐标进行区分的。
  • groupId定义了项目属于哪个组,随意命名,比如谷歌公司的myapp项目,就取名为 com.google.myapp
  • artifactId定义了当前Maven项目在组中唯一的ID,比如定义hello-world。
  • version指定了项目当前的版本0.0.1-SNAPSHOT,SNAPSHOT意为快照,说明该项目还处于开发中,是不稳定的。
  • name元素生命了一个对于用户更为友好的项目名称,虽然这不是必须的,但还是推荐为每个POM声明name,以方便信息交流

Dependency 配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<project>
...
<dependencies>
    <dependency>
        <groupId>实际项目</groupId>
<artifactId>模块</artifactId>
<version>版本</version>
<type>依赖类型</type>
<scope>依赖范围</scope>
<optional>依赖是否可选</optional>
<!—主要用于排除传递性依赖-->
<exclusions>
<exclusion>
<groupId></groupId>
<artifactId></artifactId>
</exclusion>
</exclusions>
</dependency>
<dependencies>
...
</project>

根元素project下的dependencies可以包含一个或者多个dependency元素,以声明一个或者多个项目依赖。每个依赖可以包含的元素有:

  • grounpId、artifactId和version:以来的基本坐标,对于任何一个依赖来说,基本坐标是最重要的,Maven根据坐标才能找到需要的依赖。
  • type:依赖的类型,对于项目坐标定义的packaging。大部分情况下,该元素不必声明,其默认值为jar
  • scope:依赖的范围
  • optional:标记依赖是否可选
  • exclusions:用来排除传递性依赖

仓库的分类

本地仓库

​ 一般来说,在Maven项目目录下,没有诸如lib/这样用来存放依赖文件的目录。当Maven在执行编译或测试时,如果需要使用依赖文件,它总是基于坐标使用本地仓库的依赖文件。

远程仓库-中央仓库

​ 由于最原始的本地仓库是空的,Maven必须知道至少一个可用的远程仓库,才能在执行Maven命令的时候下载到需要的构件。中央仓库就是这样一个默认的远程仓库,Maven的安装文件自带了中央仓库的配置。

​ 中央仓库包含了这个世界上绝大多数流行的开源Java构件,以及源码、作者信息、SCM,信息、许可证信息等,每个月这里都会接受全世界Java程序员大概1亿次的访问,它对全世界Java开发者的贡献由此可见一斑。