0%

MapReduce 笔记

http://nil.csail.mit.edu/6.824/2020/papers/mapreduce.pdf

1 编程模式

1.1 基本组成

  • Map 将输入处理为中间 key-value 集合,MapReduce 框架将相同 key I 的值聚合起来传递给 Reduce 函数
  • Reduce 函数接受中间 key I 和该 key 的值的集合,将这些值聚合起来组成一个更小的值的集合

1.2 数据结构

  • Map (k1, v1) -> list(k2, v2)
  • Reduce (k2, list(v2)) -> list(v2)

2 执行概览

2.1 整体流程

image-20200812235617912

  • 把输入文件分成 M 份,通常 16-64 MB 每一份
  • 共有 M 个 map 任务和 R 个 reduce 任务
  • 被分配了 map 任务的 worker 读分割文件中的内容,拿到 key-value 并传给 Map 函数,得到的中间 key-value 缓存在内存中
  • 缓存的键值对写入本地内存中,被分割函数分为 R 个区域
    • 中间 key 被分割函数划分到 R 个 Reduce 任务中,如 hash(key) mod R
  • worker 被分配给 reduce 任务后,读本地磁盘中的缓存数据。读取所有的数据后,按中间 key 排序,使相同 key 的对排在一起。如果缓存数据在内存中排序的总量过大,则需要额外的排序
  • 将排序后的中间 key-value 集传给 Reduce 函数,其输出被合并为最终的输出文件(有时不需要合并,可以作为下一个 MapReduce 调用的输入)
  • 当所有的 map 和 reduce 任务都完成时,master 唤醒用户程序

2.2 Master 的数据结构

  • 对于每个 map 和 reduce 任务都存储了任务的状态(空闲、进行中、完成)和其 worker 机器的唯一标示

  • 对于每个完成的 map 任务,master 存储了其生成的 R 个中间文件的位置和大小,不断从完成的任务获取并更新并发送给开始的 reduce 任务

2.3 容错

2.3.1 Worker 故障

master 定时给每个 worker 发送心跳,如果一段时间没有收到某个任务的心跳或者任务失败就标记其为空闲,开始重新调度

已经完成的 map 任务如果再次被执行会导致失败因为其输出存储在本地磁盘;同理完成的 reduce 任务不需要被再次执行因为其输出存储在 gfs 中

如果一个 map 任务被 worker A 执行失败后又被 worker B 执行,所有执行 reduce 任务的 worker 都会被通知并且重新执行。还没开始从 worker A 读数据的 reduce 任务会从 worker B 读数据

2.3.2 Master 故障

Master 会写入描述 master 数据结构的 checkpoints 来保证当其故障时其副本会从 checkpoints 的状态起起来

2.3.3 考虑故障的语义

当 map 任务完成时,worker 发送给 master 一条包括 R 个中间文件名的信息,若 master 已经从已完成的任务接受过完整的信息则忽略,反之将其记录在 master 的数据结构中

依赖底层文件系统的原子的重命名操作来保证最终文件系统只包含一次 reduce 任务的执行结果

2.4 定位

master 得到输入文件的位置信息,会尝试调度一个有输入数据的副本的机器去执行 map 任务;如果不成功的话会尝试调度临近输入数据副本的机器去执行(如与有副本数据的机器在同一个交换机)

2.5 任务粒度

M 和 R 应该大于 worker 机器的数量才能保证动态的负载均衡和恢复速度

2.6 候补任务

当 MapReduce 操作接近完成时,master 会调度候补执行仍然在运行中的任务,原生或者候补执行完成任务都被标记为完成,可以提高效率。

3 改进

3.1 分割函数

默认分割函数使用哈希 hash(key) mod R

3.2 顺序保证

框架保证提供给定分割函数的话,中间 key-value 对会以增序排列

3.3 Combiner 函数

可选的 combiner 函数数据从网络发出之前会调用

Reduce 函数和 Combiner 函数的唯一区别在于 MapReduce 框架如何处理函数的输出:reduce 函数的输出写入最终输出文件,combiner 函数的输出写入即将传给 reduce 任务的中间文件

3.4 输入和输出类型

输入类型只需实现 reader 接口,则不仅可以从文件读数据、也可以从数据库、内存等读数据

3.5 副作用

生成辅助文件时,依赖 writer 来使得副作用原子和幂等,如写入中间文件,当它完全生成后再将其原子重命名

3.6 跳过坏记录

有时可以接受忽略一些记录,框架提供一个模式当 MapReduce检测到一些记录造成确定的异常时跳过它们

每个 worker 安装一个可以捕捉段错误的信号 handler,当用户代码生成了一个信号时,handler 发送一个包含序列号的 last gasp UDP 包给 master,当 master 在特定的记录收到大于一个错误时,标记该记录应该被跳过

3.7 本地执行

框架提供 debug 模式能让 MapReduce 中的所有的工作都在本地机器执行

3.8 状态信息

提供一个状态 web 页面展示计算的进程

3.9 Counter

框架提供一个 counter 功能来统计事件,类似打点功能,在检查 MapReduce 操作时 Counter 十分有效

监控

术语

  • 白盒监控:依靠系统内部的性能指标进行监控

    完全依赖白盒监控意味着不知道最终用户看到的是什么样的

  • 黑盒监控:测试外部用户可见的系统行为进行监控

  • dashboard 监控台页面

监控系统的目标

  • 什么东西出故障了
  • 为什么出故障(故障出在哪里

4个黄金指标

  • 延迟

  • 流量

    QPS、网络 I/O 速率、并发会话数量…

  • 错误

    包括显式失败(500)和隐式失败(200中包含了错误内容)

  • 饱和度

    延迟增加是饱和度的前导条件

长尾问题

少部分请求占用大量时间导致平均数、中位数无法判断情况——将请求按延迟分组计数(制作直方图),将直方图的边界定义为指数型增长

监控系统的原则

  • 最能反映真实故障的规则应该越简单越好
  • 不常用的数据收集、告警配置应该定时删除
  • 收集到但是没有传给监控台或告警规则的应该定时删除

故障排查

image-20200808151310629

日志和监控图标是确定问题根源的两个工具

测试和恢复

  • 理想的测试应该具有互斥性
  • 先测试最可能的情况:按照可能发生的顺序测试
  • 测试可能产生有误导性的结果
  • 测试可能有副作用
  • 测试可能无法得出准确的结论

告警

告警粒度和频率

紧急警报太频繁会让人怀疑其有效性甚至忽略

多个报警可以被合并为一个,聚合成一个单独的故障能够减少报警信息的总数

告警方式

  • 工单
  • E-mail
  • 紧急警报

Go语言

编程细节

  • type 相关的定义可以抽到 xxx/types 的目录下,好处是可以避免循环引用
  • client 尽量复用,防止开了很多个客户端没有关闭导致 goroutine 数量暴涨
  • json.rawMessage 适用于根据情况如 type 来解结构体的情况
  • 结构体作为数据库 Model 时字段要大写,并且要与数据库中对应字段一致
  • 方便单测的编程技巧 https://juejin.im/post/5ce93447e51d45775746b8b0

工具

go-lint

基础

基础数据结构

String

string是不可变的,不能更改,故两个副本共享string的内存是安全的,s[:n]的代价也很低

编码

UTF-8 通过第一个字节开头的1来标示需要用到多少个字节

image-20200722233914366

Strings bytes strconv unicode 包提供处理字符串的函数

string 操作开销较大,可以使用 bytes.Buffer

复杂类型

Arrays

数组相当于一个固定量而非指针,所以复制传值的开销过大,切片就是解决方案

Slice

https://halfrost.com/go_slice/

Maps

image-20200724171706774

函数

Panic 和 Recover

Panic 会依次(先进先出)调用本协程的 defer() 后退出程序

Recover 会捕捉处理 panic,可以处理本协程的 panic,保证程序不会挂掉

函数引用

函数参数为值的时候传值和传指针都可以,因为 go 会将指针转换为值

Goroutines 和 Channels

异步(有缓冲区)的 Channel 用完要 close,不然会阻塞,形成死锁

MySQL基础

并发控制

读写锁

  • 共享锁(读锁):相互不阻塞,多个客户可以同时读取一个资源
  • 排他锁(写锁):写锁会 阻塞其他的写锁和读锁

锁粒度

表锁

最基本的锁策略,开销最小。

锁定整张表,用户对表进行写操作前要先获得写锁,会阻塞其他用户的所有读写操作

行级锁

可以最大程度地支持并发处理,但也是锁开销最大的

事务

ACID

  • 原子性:一个事务为不可分割的最小单元,要不全部执行,要不全部回滚,不可只执行一部分
  • 一致性:数据库总是从一个一致性的状态转到另一个一致性的状态
  • 隔离性:一个事务的修改在最终提交前对其他事务是不可见的
  • 持久性:一旦事务提交,其所作的修改就永久保存到数据库中

隔离级别

  • 未提交读(READ UNCOMMITTED):即使没有提交,对其他事务也是可见的,存在脏读问题
  • 提交读(READ COMMITTED)(不可重复读):只能看见已经提交的事务所做的修改,同一事务中多次读取同样记录的结果可能是不同的
  • 可重复读(REPEARABLE READ):同一事务中多次读取同样记录的结果是相同的,存在幻读问题
  • 可串行化(SERIALIZALE):强制事务串行执行

数据库和数据类型优化

数据类型的优化

数据类型选择原则

  • 更小的通常更好
  • 简单数据类型更好:整形比字符简单
  • 尽量避免NULL:包含NULL得列更难优化,因为索引、索引统计和值比较都更复杂
  • 时间:TIMESTAMP占的存储空间比DATATIME小得多

整数类型

TINYINT、SMALLINT\MEDIUMINT、INT、BIGINT分别用8、16、32、64位存储空间,范围从-2^(N-1) 到 2^(N-1),N为位数

如果有UNSIGNED,不允许负值,可以使正数上限提高一倍

指定宽度对于存储和计算没有意义,只是规定交互工具显示的位数

实数

FLOAT、DOUBLE使用浮点计算(近似计算)

DECIMAL存储更精确的小数,但运算比浮点运算慢。数字会打包到二进制字符串中,每4个字节存储9个数字,小数点本身占一个字节

数据量较大时可以用BIGINT代替DECIMAL,乘以相应的倍数

字符串类型

VACHAR

存储变长字符串,需要用1或2个额外字节记录长度

UPDATE时可能使行变得比原来更长,使得页内没有更多空间可以存储。可能会拆成不同片段或者分裂页来解决,视存储引擎而定

适合的情况:字符串的最大长度远大于平均长度;列的更新很少,碎片不是问题

CHAR

会自动删除所有末尾空格

定长,适合长度一定,经常变更的值

BLOB和TEXT

太大时会使用外部存储区域来存储,在行内需要1-4个字节来存储指针

排序时只对最前面的max_sort_length字节做排序

日期和时间

DATETIME能保存大范围的值,从1001年到9999年,精度为秒,YYYYMMDDHHMMSS,用8个字节的空间

TIMESTAMP的范围从1970年到2038年,只用4个字节的存储空间

位数据类型

BIT

在一个列中存储一个或多个true/false,BIT(N)代表几位,最大64

但因为存在取值之后需要转化的问题尽量少使用

SET

可以存储多个true/false,有FIND_IN_SET()等函数,但是改变列的定义的代价较高

标识列的选择

  • 整数类型:最好的选择,速度快,可以使用AUTO_INCREMENT
  • 字符串类型:消耗空间,计算慢;随机生成的值可能分布在很大空间内,使INSERT和一些SELECT语句变得很慢

特殊类型数据

可使用无符号整数来存储IP地址,INET_ATON()和INET_NTOA()可以进行转换

设计缺陷

  • 过多的列:从编码过的列转换成行数据结构的操作代价高
  • 过多的关联
  • 过度使用枚举
  • 变相的枚举:set(‘Y’, ’N‘) 应该用枚举代替,两种情况并不会同时出现
  • 过多使用NULL:用表示为空的数值代替NULL

范式和反范式

范式

优点

  • 更新操作比反范式快
  • 很少或者没有重复数据
  • 表通常较小,可以很好地放在内存中,操作更快
  • 查询时很少需要DISTINCT和GROUP BY语句(因为重复数据少)

缺点:通常需要关联

反范式

优点:避免关联

数据比内存大的时候扫全表比关联快,因为避免了随机IO

能使用更有效的索引策略:查找付费用户最近的10条信息,可以用索引代替关联查询

缓存表和汇总表

缓存表

可以简单的从数据库其他表获取但速度较慢的表

汇总表

使用GROUP BY语句聚合数据的表

如计算24小时内发送的消息数:以每小时汇总表为基础,把前23个小时的计数加起来,再 加上开始阶段和结束阶段的不完全小时的计数

影子表

重建表时保证数据在操作时仍可以使用:完成建表操作后通过一个原子重命名操作切换影子表和原表

计数器表

若只有一行数据,会导致事务只能串行执行

将表增加100行数据,再选择随机的槽进行更新,获取结果时使用聚合查询

高性能索引

索引类型

B+树索引

数据结构

1555750864587

B+树索引适用于全键值、键值范围和键前缀查找,键前缀查找只适用于最左前缀的查找

限制
  • 如果不是按照索引的最左列开始查找,则无法使用索引
  • 不能跳过索引中的列
  • 如果查询中有某个列的范围查询,则右边所有的列都无法使用索引优化查找

联合索引

数据结构

1555747263954

哈希索引

只有精确匹配索引所有列的查询才有效

索引存储对应的哈希值和行指针,结构十分紧凑,查找速度很快;关联很多查找表时哈希索引很适合

限制:

  • 不能使用索引中的值来避免读取行(哈希值没有意义)
  • 无法用于排序
  • 不支持部分索引匹配查找:索引(A,B)无法用于查询A
  • 只支持等值查询
  • 出现哈希冲突时必须遍历链表中的行指针,逐行比较
  • 冲突越多,索引维护操作的代价更高

对于较长的字符串列,可以手动计算哈希来模拟哈希函数,但这么做时不要使用SHA1()和MD5()作为哈希函数,因为其计算结构是长字符串,设计目标为最大限度消除冲突

空间数据索引(R树)

无需前缀索引,会从所有维度来索引数据

全文索引

查找文本中的关键词,并非直接比较数据

索引的优点

  • 减少服务器扫描的数据量
  • 帮助服务器避免排序和临时表
  • 可以将随机I/O变为顺序I/O

表较小时,大部分情况下扫全表更高效

高性能索引策略

独立的列

索引不能是表达式的一部分或函数的参数,必须将索引列单独放在比较符号的一侧

1
SELECT actor_id FROM actor WHERE actor_id + 1 = 5;

前缀索引和索引选择性

对于较长的字符串列可以索引开始部分的字符,节约索引空间,提高索引效率,但是会降低选择性

对于BLOB、TEXT或很长的VARCHAR的列,必须使用前缀索引

要选择长度合适的前缀

缺点:MySQL无法用前缀索引做ORDER BY和GROUP BY,也无法用前缀索引做覆盖扫描

多列索引

  • 多个索引做相交操作时(AND),需要一个包含所有相关列的多列索引
  • 多个索引做联合操作时(OR),需要消耗大量的资源,特别是当有些索引的选择性不高时

选择合适的索引列顺序

将选择性最高的列放在最前列,但是要结合实际情况分析

聚簇索引

当表有聚簇索引时,数据行放在索引的叶子页中,一个表只能有一个聚簇索引,其他索引的值为行的主键值

1555749566153

优点:

  • 可以把相关数据保存在一起,只需要从磁盘读取少量数据页就能获取某个用户的全部邮件
  • 数据访问更快,索引和数据保存在同一颗B+树中
  • 覆盖索引扫描的查询可以直接用页节点中的主键值

缺点:

  • 如果数据在内存中,访问的顺序不那么重要,就没什么优势了
  • 插入速度严重依赖于插入顺序
  • 更新聚簇索引列的代价很高
  • 插入新行时可能面临页分裂的问题
  • 可能导致扫全表变慢,尤其是行比较稀疏,或由于页分裂导致数据存储不连续时
  • 二级索引比较大,其叶节点包含了引用行的主键列
  • 二级索引需要两次索引查找
InnoDB和MyISAM的数据分布对比

MyISAM按数据插入的顺序存储在磁盘上

1555749613499

索引分布,主键和其他键相同

1555749661031

InnoDB的数据分布:叶子节点存储所有数据

1555749700200

InnoDB的二级索引分布

1555749789800

MySIAM二级索引的叶子节点存储行指针,InnoDB存储主键值

聚簇和非聚簇表对比

1555749821295

InnoDB的插入

使用InnoDB时应尽可能地按主键顺序插入数据,并且尽可能使用单调增加的聚簇键的值来插入新行。最好避免随机的(不连续且分布范围大)聚簇索引,可以使用自增列作为主键保证按顺序写入。否则:

  • 写入的目标可能刷到磁盘上并从缓存移除,插入前不得不从磁盘找到并读取目标页到内存中,导致大量随机I/O
  • 频繁页分裂,移动大量数据;页变得稀疏,被不规则填充,数据会有碎片

1555750197344

覆盖索引

一个索引包含所有需要查询的字段的值

优点:

  • 索引条目通常少于数据航,减少数据访问量
  • 所以按列值顺序存储,范围查询比从磁盘读取每一行I/O少得多
  • 对于InnoDB的聚簇索引,若二级逐渐能覆盖查询,可以避免对主键索引的二次查询

不是所有类型的索引都可以做覆盖索引:必须存储索引列的值,哈希、空间、全文索引不可以

使用索引扫描来做排序

只有当索引的列顺序和ORDER BY子句的顺序和排列方向完全一致时才能用索引来对结果排序;若查询需要关联多张表,当ORDER BY子句引用的字段全部为第一个表时才能用索引进行排序

冗余和重复索引

(A,B)和(A)为冗余索引,因为(A,B)可以被当作(A)用

(A,B)和(B,A)不是冗余索引,因为B不是最左前缀

不同类型的索引也不是B+树索引的冗余索引

索引和锁

InnoDB访问行时会对其加锁,索引能减少其访问的行数,从而减少锁的数量

InnoDB有可能无法再服务端过滤掉行后就释放锁,而必须等到适当的时候

1
SELECT actor_id FROM actor WHERE actor_id < 5 AND actor_id <> 1 FORUPDATE;

此时锁住了第1-4行,即使第1行不在结果中

即使使用索引也可能锁住不需要的数据,不使用索引可能更糟糕:锁全表

索引案例

技巧

  • 当某个查询不限制性别时,可以在查询条件中新增AND SEX IN(‘m’, ‘f’)来访MySQL选择该索引,匹配最左前缀
  • 尽可能将范围查询(age)放在最后,以便优化器使用尽可能多的索引列
  • IN(a,b,c…)条件如果太多,优化器要做的组合会指数增长

优化排序

通过覆盖索引查询返回需要的主键,再根据主键关联原表获得需要的行,减少MySQL扫描那些要丢弃的行数

1555753418063

索引和数据碎片

数据碎片类型

  • 行碎片:数据行被存储在多个地方的多个片段中,即使只访问一行记录性能也会下降
  • 行间碎片:逻辑上顺序的页或行,在磁盘上不是顺序存储的。影响全表扫描和基础索引扫描等
  • 剩余空间碎片:数据页中有大量空余空间,导致服务器读取大量不需要的数据

MyISAM表三种碎片化都可能发生;InnoDB不会出现短小的行碎片,会移动短小的行并重写到一个片段中

三个原则

  • 单行访问是很慢的
  • 按顺序访问范围数据是很快的:
    • 顺序I/O不需要多次磁盘寻道,比随机I/O要快很多
    • 如果要顺序读取数据,不需要额外的排序操作
  • 索引覆盖查询是很快的

查询性能优化

优化数据访问

分析步骤:

  • 确认应用程序是否检索大量超过需要的数据:访问太多的行或访问太多的列
  • 确认MySQL服务器是否分析大量超过需要的数据行

是否向数据库请求了不需要的数据

  • 查询不需要的记录:查询100条,返回10条;应该使用LIMIT

  • 多表关联时返回全部列

  • 总是取出全部列
  • 重复查询相同数据

MySQL是否扫描额外的记录

衡量指标:响应时间、扫描行数、返回的行数

若需扫描大量数据但返回少数行,可采取的优化方式:

  • 使用索引覆盖扫描,无需回表取对应行即可返回结果
  • 改变库表结构,如使用单独的汇总表
  • 重写复杂查询

重构查询的方式

切分查询

使用一个大语句一次性完成可能需要一次锁住多个数据,占用大量资源

分解关联查询

  • 缓存效率更高:若之前查询中行已经被缓存,之后的查询就可以减少一些查询行数
  • 减少锁的竞争
  • 减少冗余查询,在应用层做关联意味着对某条记录应用只需要查询一次,在数据层做可能要重复访问一部分数据

查询执行的基础

1555755759168

客户端/服务器通信协议

半双工:某个时刻要么是服务器向客户端发数据,要么是客户端向服务器发数据

无流量控制,必须完整接受结果后才响应

查询缓存

对一个大小写敏感的哈希查找实现。即使查询和缓存只有一个字节不同,也不会匹配缓存结果

若命中查询缓存,返回查询结果之前会检查一次用户权限,没问题则跳过所有其他阶段,查询不会被解析不生成执行计划不被执行

查询优化处理

将一个SQL转换成一个执行计划,MySQL依照这个执行计划与存储引擎交互:解析SQL、预处理、优化SQL执行计划

语法解析器和预处理

解析语句,生成解析树并检查是否合法

查询优化器

预测执行计划的成本并选择最小的一个。评估成本时不考虑任何层面的缓存,假设读取任何数据都需要一次磁盘I/O

优化策略:

  • 静态优化:只需做一次
  • 动态优化:每次执行时都重新评估

优化类型:重新定义关联表的顺序、外连接转内连接、等价变换、优化计数函数、子查询优化、覆盖索引扫描、提前终止查询(使用LIMIT时)…

IN()中有大量取值时,会先排序再进行二分查找,比等价的OR查询速度快

MySQL的关联查询

先将一系列单个查询的结果放入一个临时表中,再读出临时表数据来完成查询

1555763597538

FROM中有子查询时,先执行子查询并将其结果放到一个临时表中

执行计划

生成一棵指令树,通过存储引擎执行完成这棵指令树并返回结果

总是左侧深度优先的树

关联优化器

优化多表关联的顺序,会在所有的关联顺序中选择一个成本最小的来执行

执行计划的搜索空间过大时,使用贪婪的方法优化

排序优化

排序数据量小于缓冲区时,使用内存快速排序

内存不够排序时,将数据分块,对每个独立的块使用快速排序进行排序,合并并返回结果

查询执行引擎,返回结果给客户端

MySQL查询优化器的局限性

关联子查询

MySQL的关联子查询很糟糕,特别是WHERE条件中包含IN()的子查询语句

松散索引扫描

目前MySQL还不支持

对于语句

1
SELECT ... FROM tbl WHERE b BETWEEN 2 AND 3

扫全表

1555764941746

松散索引扫描

1555764927204

优化特定类型的查询

COUNT()

统计列值:要求列值非空(不为NULL)

统计行数:COUNT(*)时,不会扩展成所有的列,而是直接统计行数

优化LIMIT 分页

如果偏移量很大时,可能需要查询大量的记录再返回很少量的记录,代价巨大

优化方法

  • 尽可能用索引覆盖扫描
  • 将LIMIT转为已知位置的存储:WHERE position BETWEEN 50 AND 54 ORDER BY position

可变对象和不可变对象

python中所有东西都是一个对象

  • 不可变对象:int,string,float,tuple
  • 可变对象 :list,dictionary

不可变对象immutable

python中的对象存放的是对象引用,所以尽管不可变对象本身不可变,但其对象引用是可变的

1555570792969

可变对象mutable

可变对象的内容可以发生变化,但其引用不会改变

1555571056395

地址问题

id()返回一个对象的地址或者用is;==对比值

不可变对象的引用改变后,其地址发生变化;可变对象改变后其地址不变

参数传递

python中向函数传参都是引用传递(传地址)

当传的参数是不可变对象时,函数复制一份引用,所以无论怎么操作传入的参数都不会对函数外的变量造成影响;当传入的参数是可变对象时,函数内操作会改变函数外变量的内容

不要用可变对象作为参数的默认值

迭代器和生成器

1555573612285

迭代

可迭代对象:实现了iter方法的对象

1
2
for k, v in d.items()
for i, value in enumerate(['A', 'B', 'C'])

生成器

优点:对延迟操作提供了支持,在需要的时候才产生结果,而不是立即产生结果,减少资源消耗;可读性强(认准yield即可知道返回的结果)

生成器函数

每次调用next()执行,遇到yield语句返回,再次执行时从上次返回的yield语句处继续执行

1
2
3
4
5
6
7
def gensquatres(N):
for i in range(N):
yield i**2

# gensquatres是一个生成器对象
for item in gensquares(5):
print(item)
生成式表达式
1
2
3
4
5
squares = (x**2 for x in range(5))

next(squares)
for item in squares:
...

注意:生成器只能遍历一次

迭代器

迭代器:实现了迭代器协议的对象,可以用isinstance()判断

迭代器协议:对象需要提供next()方法和iter()方法返回迭代器类的实例,返回下一项或引起StopIteration异常,以终止迭代

yield from

yield from后加上可迭代对象可以将其每个元素yield出来

生成嵌套

在yield from后面加上生成器

  • 调用方:调用委派生成器的客户端(调用方)代码

  • 委托生成器:包含yield from表达式的生成器函数

  • 子生成器:yield from后面加的生成器函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 子生成器
def average_gen():
total = 0
count = 0
average = 0
while True:
new_num = yield average
count += 1
total += new_num
average = total/count

# 委托生成器
def proxy_gen():
while True:
yield from average_gen()

# 调用方
def main():
calc_average = proxy_gen()
next(calc_average) # 预激下生成器
print(calc_average.send(10)) # 打印:10.0
print(calc_average.send(20)) # 打印:15.0
print(calc_average.send(30)) # 打印:20.0

委托生成器,在调用方与子生成器之间建立一个双向通道,可以简化代码,而且会自动处理异常

函数式编程

map-reduce

1
2
3
from functools import reduce
map(f, [x1, x2, x3, x4]) = [f(x1), f(x2), f(x3), f(x4)]
reduce(f, [x1, x2, x3, x4]) = f(f(f(x1, x2), x3), x4)

配合lambda函数可以进一步简化

filter

filter()函数返回的是一个Iterator,也就是一个惰性序列,所以要强迫filter()完成计算结果,需要用list()函数获得所有结果并返回list

1
2
3
4
def is_odd(n):
return n % 2 == 1

list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15]))

sorted

装饰器

被用于有切面需求的场景,较为经典的有插入日志、性能测试、事务处理等。为已经存在的对象添加额外的功能,并重用代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def log(text):
def decorator(func):
def wrapper(*args, **kw):
print('%s %s():' % (text, func.__name__))
return func(*args, **kw)
return wrapper
return decorator
...
@log('execute')
def now():
print('2015-3-25')
...
>>> now()
execute now():
2015-3-25

另一个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from functools import wraps

def makebold(fn):
@wraps(fn)
def wrapped(*args, **kwargs):
return "<b>" + fn(*args, **kwargs) + "</b>"
return wrapped

def makeitalic(fn):
@wraps(fn)
def wrapped(*args, **kwargs):
return "<i>" + fn(*args, **kwargs) + "</i>"
return wrapped

@makebold
@makeitalic
def hello():
return "hello world"

@makebold
@makeitalic
def log(s):
return s
1
print hello()        # returns "<b><i>hello world</i></b>"

面向对象

类中定义的函数只有一点不同,就是第一个参数永远是实例变量self,并且,调用时,不用传递该参数

私有变量

__开头的变量,原理为将该变量重命名为(真正的私有变量)

1
_classname__varname

_开头是一种约定,为私有变量

函数重载

函数重载能解决的问题:

  • 可变参数类型:python 可以接受任何类型的参数,如果函数的功能相同,那么不同的参数类型在 python 中很可能是相同的代码,没有必要做成两个不同函数
  • 可变参数个数:对那些缺少的参数设定为缺省参数即可解决问题。因为你假设函数功能相同,那么那些缺少的参数终归是需要用的

故python中不需要函数重载

属性

实例可以任意绑定属性和方法。给实例绑定属性的方法是通过实例变量,或者通过self变量

类属性直接在class中定义属性

注意实例属性会屏蔽类属性,故类属性和实例属性不要重名

__slots _

_slots__变量用于限制该class实例能添加的属性

1
2
class Student(object):
__slots__ = ('name', 'age') # 用tuple定义允许绑定的属性名称

仅对当前类实例起作用,对继承的子类是不起作用的

@property

既能检查参数,又可以用类似属性这样简单的方式来访问类的变量

1
2
3
4
5
6
7
8
9
10
11
12
13
class Student(object):

@property
def score(self):
return self._score

@score.setter
def score(self, value):
if not isinstance(value, int):
raise ValueError('score must be an integer!')
if value < 0 or value > 100:
raise ValueError('score must between 0 ~ 100!')
self._score = value
1
2
3
4
5
6
7
8
>>> s = Student()
>>> s.score = 60 # OK,实际转化为s.set_score(60)
>>> s.score # OK,实际转化为s.get_score()
60
>>> s.score = 9999
Traceback (most recent call last):
...
ValueError: score must between 0 ~ 100!

静态方法、实例方法、类方法

\ 实例方法 类方法 静态方法
a = A() a.foo(x) a.class_foo(x) a.static_foo(x)
A 不可用 A.class_foo(x) A.static_foo(x)

init()和new()方法

__new()方法在init()方法之前执行

真正创建实例是new方法,init__方法做的事情是在对象创建好之后初始化变量

new方法返回一个创建的实例,init方法不返回

异常处理

捕获错误时也会捕获其子类

序列化

class和json的转化

1
2
3
4
5
json.dumps(item, default=lambda obj: obj.__dict__)
json.loads(json_str, object_hook=dict2student)

def dict2student(d):
return Student(d['name'], d['age'], d['score'])

协程

python对协程的支持是通过generator实现的

特点

  • 在单线程里实现任务的切换的

  • 利用同步的方式去实现异步

  • 不再需要锁,提高了并发性能

生产者消费者:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def consumer():
r = ''
while True:
n = yield r
if not n:
return
print('[CONSUMER] Consuming %s...' % n)
r = '200 OK'

def produce(c):
c.send(None)
n = 0
while n < 5:
n = n + 1
print('[PRODUCER] Producing %s...' % n)
r = c.send(n)
print('[PRODUCER] Consumer return: %s' % r)
c.close()

c = consumer()
produce(c)

注意 send(n)为将参数传给yield

垃圾回收机制

Python GC主要使用引用计数(reference counting)来跟踪和回收垃圾。在引用计数的基础上,通过“标记-清除”(mark and sweep)解决容器对象可能产生的循环引用问题,通过“分代回收”(generation collection)以空间换时间的方法提高垃圾回收效率

引用计数

PyObject是每个对象必有的内容,其中ob_refcnt就是做为引用计数。当一个对象有新的引用时,它的ob_refcnt就会增加,当引用它的对象被删除,它的ob_refcnt就会减少.引用计数为0时,该对象生命就结束了。

优点:

  • 简单
  • 实时性

缺点:

  • 维护引用计数消耗资源
  • 循环引用

标记-清除机制

基本思路是先按需分配,等到没有空闲内存的时候从寄存器和程序栈上的引用出发,遍历以对象为节点、以引用为边构成的图,把所有可以访问到的对象打上标记,然后清扫一遍内存空间,把所有没标记的对象释放

分代技术

将系统中的所有内存块根据其存活时间划分为不同的集合,每个集合就成为一个“代”,垃圾收集频率随着“代”的存活时间的增大而减小,存活时间通常利用经过几次垃圾回收来度量

单例模式

new方法

1
2
3
4
5
6
7
8
9
class Singleton(object):
def __new__(cls, *args, **kw):
if not hasattr(cls, '_instance'):
orig = super(Singleton, cls)
cls._instance = orig.__new__(cls, *args, **kw)
return cls._instance

class MyClass(Singleton):
a = 1

装饰器版本

1
2
3
4
5
6
7
8
9
10
11
def singleton(cls, *args, **kw):
instances = {}
def getinstance():
if cls not in instances:
instances[cls] = cls(*args, **kw)
return instances[cls]
return getinstance

@singleton
class MyClass:
...

GIL线程全局锁

线程全局锁(Global Interpreter Lock),即Python为了保证线程安全而采取的独立线程运行的限制,就是一个核只能在同一时间运行一个线程.

解决办法就是多进程和下面的协程(协程也只是单CPU,但是能减小切换代价提升性能)

闭包

  • 在一个外函数中定义了一个内函数
  • 内函数里运用了外函数的临时变量
  • 外函数的返回值是内函数的引用

其中的临时变量只能被读取不能更改,若要等该要引入nonlocal语句

作用:类似装饰器

1
2
3
4
5
6
7
8
9
10
11
def make_sing(animal):
def make_voice(voice):
return "{} sings {}".format(animal, voice)
return make_voice

>>> dog = make_sing("dog")
>>> dog("wong")
'dog sings wong'
>>> cow = make_sing("cow")
>>> cow("mow")
'cow sings mow'

细节

连续赋值

1
a, b = b, a + b

相当于

1
2
3
t = (b, a + b) # t是一个tuple
a = t[0]
b = t[1]

*args & **kwargs

  • *args:可以传递任意数量的参数,index-value
  • **kwargs:可以使用没有事先定义的参数名,name-value

拷贝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import copy
a = [1, 2, 3, 4, ['a', 'b']] #原始对象

b = a #赋值,传对象的引用
c = copy.copy(a) #对象拷贝,浅拷贝
d = copy.deepcopy(a) #对象拷贝,深拷贝

a.append(5) #修改对象a
a[4].append('c') #修改对象a中的['a', 'b']数组对象

print 'a = ', a
print 'b = ', b
print 'c = ', c
print 'd = ', d

输出结果:
a = [1, 2, 3, 4, ['a', 'b', 'c'], 5]
b = [1, 2, 3, 4, ['a', 'b', 'c'], 5]
c = [1, 2, 3, 4, ['a', 'b', 'c']]
d = [1, 2, 3, 4, ['a', 'b']]

本文为《图解http》的笔记,主要补充http相关的计算机网络知识

HTTP基础

URI

某个协议方案表示的资源定位标识符。协议方案指访问资源所用的协议类型名称。

1555410041635

请求URI可以为绝对URI,也可以为相对URI并且在首部字段Host中写明网络域名或IP地址

报文

报文=报文首部 + 报文主体,由一个空行(CR+LF)划分

报文VS实体

  • 报文:http通信的基本单位,由8位字节流组成
  • 实体:作为请求或响应的有效载荷数据被传输,由实体首部和实体主体组成
  • 通常,报文主体等于实体主体,只有当传输中进行编码操作时,实体主体的内容才会发生变化,区别于报文主体

请求报文

1555410100190

响应报文

1555410136328

HTTP方法

GET、POST

PUT

上传文件,在报文主体中包含文件内容;但不带验证机制,存在安全性问题,一般不使用

和GET一样,但是不返回报文主体部分,用于确认URI的有效性和资源更新的日期时间等

DELETE

与PUT相反,也不带验证机制

PUT和DELETE配合Web的验证机制,遵守REST标准时可以开放使用

OPTIONS

查询URI的资源支持的方法

TRACE

追踪路径,在Max-Forwards首部填入数值(跳数),最后接收到请求的服务器返回200OK

不常用,而且容易引发XST(跨站追踪)攻击

CONNECT

要求与代理服务器通信时建立隧道,用隧道协议进行TCP通信,主要用SSL和TLS进行加密

1555496635805

分块传输编码

将实体主体分为多个部分,每一块用16进制来标记块的大小,实体主体的最后一块会使用“0(CR+LF)”来标记

获取部分内容的范围请求

用首部字段Range来指定资源的byte范围

1
Range:bytes=5001-10000

对于范围请求会返回状态码为206Partial Content的响应报文;若服务器无法响应范围请求,会返回状态码200OK的完整实体内容

HTTP状态码

类别 原因短语
1xx Informational 请求正在处理
2xx Success 请求处理完毕
3xx Redirection 需要附加操作来完成请求
4xx Client Error 服务器无法处理请求
5xx Server Error 服务器处理请求出错

2XX 成功

200 OK

正常处理

204 No Content

成功处理,但返回的相应报文中不包含实体的主体部分。一般在只需从客户端往服务器发送信息,而对客户端不需要发送新信息内容的情况下使用。

如在PUT请求中进行资源更新,但是不需要改变当前展示给用户的页面。

206 Partial Content

进行了范围请求,服务器成功执行,响应报文中用Content-Range指定范围的实体内容

3XX 重定向

301 Moved Permanently

永久重定向。浏览器会跳转到重定向的URI并记录下来,以后每次访问次URI都会进行跳转,而不会对该URI发起请求

302 Found

临时重定向。跳转到重定向的URI,但不会记录在浏览器中

303 See Other

类似302,通常作为 PUT或 POST操作的返回结果,区别在于表示客户端应该使用GET方法获取资源

浏览器得到301302303时,都会把POST改为GET,删除请求报文中的主体,自动重发

304 Not Modified

未满足请求报文中的条件,不包含响应的主体部分

307 Temporary Redirect

与302相同,但是不会从POST变为GET

注意POST请求的重定向要使用307

4XX 客户端错误

400 Bad Request

报文中存在语法错误

401 Unauthorized

第一次发送表示需要有用过Http认证的认证信息;第二次发送表示用户认证失败

403 Forbidden

请求资源的访问被服务器拒绝

404 Not Found

5XX 服务器错误

500 Internal Server Error

服务端在执行请求时发生错误

502 Bad Gateway

上游服务器故障

504 Gateway Timeout

扮演网关或者代理的服务器无法在规定的时间内获得想要的响应,上游服务执行超时(超过代理网关的等待时间)

重定向

1555500154422

永久重定向之间的区别

1555500178747

临时重定向的区别

1555500199054

Web服务器

数据转发

代理

服务器和客户端的中间人

代理不改变URI,每次通过代理服务器转发请求或响应时,会追加写入Via首部信息

1555499743903

优点:使用缓存减少流量;实现特定URI访问控制、获取访问日志..

  • 缓存代理:将资源副本保存在服务器上,代理再次收到相同请求时可以不获取资源,直接将缓存的资源作为响应返回
  • 透明代理:不对报文做任何加工

网关

转发其他服务器通信数据的服务器,类似代理但可以提供非HTTP服务

可以提高通信安全性,因为可以在客户端和网关之间的通信线路上加密确保安全

隧道

在客户端和服务器间中转,并保持双方通信连接。目的是确保客户端和服务器进行安全的通信。隧道不会解析HTTP请求,保持原样

缓存

大致可归为两类:私有与共享缓存。共享缓存存储的响应能够被多个用户使用。私有缓存只能用于单独用户。包括浏览器与代理缓存,除此之外还有网关缓存、CDN、反向代理缓存和负载均衡器等部署在服务器上

1555500564455

1555500598866

若不超过缓存的有效期限则不请求服务器,直接返回

客户端的缓存

缓存在浏览器中,称为临时网络文件

缓存验证

强校验器

ETag响应头是一个对用户代理不透明的值。对于像浏览器这样的HTTP UA,不知道ETag代表什么,不能预测它的值是多少。如果资源请求的响应头里含有ETag, 客户端可以在后续的请求的头中带上 If-None-Match头来验证缓存

用首部If-Match来比较ETag

弱校验器

Last-Modified响应头可以作为一种弱校验器。说它弱是因为它只能精确到一秒。如果响应头里含有这个信息,客户端可以在后续的请求中带上 If-Modified-Since来验证缓存

带Vary头的响应

决定了对于后续的请求头,如何判断是请求一个新的资源还是使用缓存的文件

当缓存服务器收到一个请求,只有当前的请求和原始(缓存)的请求头跟缓存的响应头里的Vary都匹配,才能使用缓存的响应

1555501195373

HTTP首部

End2End VS HopbyHop

  • End2End会转发给最终目标
  • HopbyHop只对单次转发有效
  • Http/1.1之后如果要使用HopbyHop首部,需提供Connection首部字段

通用首部

Cache-Control

指定缓存工作机制(是否、最大Age值…)

请求指令:no-cache、no-store、max-age=100….

响应指令:public、no-cache、no-transform…

1555501712193

Cache-Control详细指令的含义

Connection

作用:控制不再转发给代理的首部字段、管理持久连接

Connection:不再转发的首部字段名

服务器端想明确断开连接时,Connection:Close

Date

表明创建HTTP报文的日期和时间

Pragama

仅作为与HTTP/1.0的向后兼容而定义

Trailer

实现说明在报文主体后记录了哪些首部字段

Transfer-Encoding

规定传输报文主体时采用的编码方式,HTTP/1.1的传输编码方式仅对分块传输编码有效

Upgrade

检测HTTP协议及其他协议是否可以使用更高版本进行通信

1555502713615

Via

追踪客户端和服务器之间的请求和响应报文的传输路径。经过代理或网关时会现在Via中附加该服务器的信息,再转发。Via还可以避免请求回环的发生。常和TRACE方法一起使用

请求首部字段

Accept

通知服务器用户代理能处理的媒体类型及相对优先级

可以使用q=来表示额外的权重 0-1 用分号隔离

Accep-Charset

支持的字符集和相对优先级

Accept-Encoding

支持的内容编码和相对优先级

Accept-Language

支持的语言和相对优先级

Authorization

用户代理的认证信息

Host

虚拟主机运行在同一个IP上,用Host加以区分

If-xxx

条件请求,只有当条件为真服务器才会处理请求

If-Modified-Since

告知服务器若字段值早于资源更新的时间则处理该请求,否则返回304

Max-Forwards

可经过的服务器最大数目,每经过一个服务器-1

User-Agent

传达浏览器的种类

响应首部字段

ETag

告知客户端实体标识

Location

重定向时提供重定向的URI

WWW-Authenticate

用于HTTP访问认证,告知客户端适用的认证方案

实体首部字段

Allow

通知客户端能够支持URI指定资源的所有HTTP方法

Content-Encoding

对实体的主题部分选用的内容编码方式,主要包括:gzip、compress、deflate、identity

Content-Location

报文主体返回资源对应的URI

如返回的页面内容与实际请求的对象不同时会写明URI

Cookie相关字段

Cookie作用:对无状态协议HTTP的补充

1555504189653

1555504200465

HttpOnly可以放止跨站脚本攻击(XSS)对Cookie信息的窃取,即无法通过doument.cookie获取Cookie内容

其他首部字段

X-XSS-Protection

用于控制浏览器XSS防护机制的开关

Web安全

HTTP缺点

  • 明文通信,内容可能被窃听:SSL和TLS组合使用进行加密
  • 不验证通信方身份,可能遭遇伪装:在开始通信前先确认服务器的证书
  • 很迷报文的完整性,可能被篡改:散列值校验、数字签名

HTTPS

HTTPS = HTTP + 加密 + 认证 + 完整性保护

1555505046673

HTTPS采用混合加密机制,若密钥能实现安全交换,则考虑仅用公开密钥加密,但是其处理速度比共享密钥加密要慢

1555505242502

证书

作用:证明密钥正确性

1555505794662

HTTPS通信

1555505910689

1555506163122

1555506189416

以上流程中,应用层发送数据时会附加MAC的报文摘要,查知报文是否被篡改,保护报文完整性

但HTTPS也存在速度慢,消耗CPU和你内存资源的问题

身份认证

BASIC认证

1555506908313

Base64不是加密处理,不需要附加信息即可解码

DIGEST认证

使用质询/响应的方式,不直接发送明文密码。即一方先发送认证要求给另一方,接着使用从另一方接收到的质询码计算生成响应码,再返回给对方

1555507128268

SSL客户端认证

  • 接收到需要认证资源的请求,服务器发送Certificate Request报文,要求客户端提供客户端证书
  • 客户端将证书信息以Client Certificate报文方式发送给服务器
  • 服务器验证证书通过后方可领取其中公开密钥,开始HTTPS加密通信

基于HTTP功能的追加协议

HTTP瓶颈

Ajax

通过js脚本调用和服务器进行http通信,可以从已加载完毕的Web页面上发起请求,只更新局部页面

Comet

将响应置于挂起状态,当服务器有内容更新时再返回响应,但会消耗更多资源

WebSocket

浏览器和服务器之间的全双工通信标准

优点:推送功能、减少通信量

在HTTP连接建立后需要一次握手来告知服务器通信协议改变,Upgrade:websocket

1555507877036

服务器可以调用websocket Api来发送数据

Web攻击

攻击

跨站脚本攻击

恶意web用户将代码植入到提供给其它用户使用的页面中,包括HTML代码和客户端脚本,骗取个人信息、窃取Cookie等

嵌入URL

1555509389819

窃取Cookie

1555509441737

1555509420941

SQL注入攻击

1555509497778

预防:变量采用占位符进行占位,实现转义

OS命令注入攻击

执行非法的操作系统命令,在能调用Shell函数的地方就存在被攻击的风险

1555509669501

1555509677609

HTTP首部注入攻击

在响应首部字段内插入换行或添加内容,可能设置任何Cookie信息、重定向至任意URL、显示任意主体(HTTP响应截断攻击)

HTTP响应截断攻击:插入%0D%0A%0D%0A,截断主体

目录遍历攻击

通过非法截断不公开的文件目录路径后形成攻击

1555509957604

安全漏洞

强制浏览

1555510070913

不正确的错误信息

  • Web应用抛出的错误信息:“未注册”信息可以被用于确认账号是否存在
  • 数据库抛出的错误信息

开放重定向

对指定的任意URL做重定向

1555510186494

会话管理疏忽

获取会话ID的途径:推测、窃听、会话固定攻击

会话固定攻击

1555556011317

跨站点请求伪造

CSRF,利用已认证用户的权限更新设定信息、购买商品、发表评论等

1555557659047

点击劫持

利用透明的按钮或链接做成陷阱覆盖在Web页面上,诱使用户点击

Dos攻击

集中利用访问请求导致资源过载;通过攻击安全漏洞使服务停止

其他

访问控制(CORS)

HTTP访问控制(CORS)文档

CORS中间件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func Cors() gin.HandlerFunc {
return func(c *gin.Context) {
method := c.Request.Method
fmt.Println(method)
c.Header("Access-Control-Allow-Origin", "*")
c.Header("Access-Control-Allow-Headers", "Content-Type,AccessToken,X-CSRF-Token, Authorization, Token")
c.Header("Access-Control-Allow-Methods", "POST, GET, OPTIONS, PUT, PATCH, DELETE")
c.Header("Access-Control-Expose-Headers", "Content-Length, Access-Control-Allow-Origin, Access-Control-Allow-Headers, Content-Type")
c.Header("Access-Control-Allow-Credentials", "true")

// 放行所有OPTIONS方法,因为有的模板是要请求两次的
if method == "OPTIONS" {
c.AbortWithStatus(http.StatusNoContent)
}
// 处理请求
c.Next()
}
}

JWT

英文介绍

阮一峰教程

Localstorage

localstorage 必知必会

Window.localStorage文档

SQL语句基础

数据库

选择数据库

1
USE crashcourse;

展示数据库

1
SHOW DATABASES;

展示表

1
SHOW TABLES;

展示表列

1
2
SHOW COLUMNS FROM customers;
DESCRIBE customers;

检索数据

检索列

1
2
SELECT prod_name, prod_name
FROM products;
  • 所有列:*

检索不重复的行

1
2
SELECT DISTINCT vend_id
FROM products

限制结果(返回前几行或第几行)

1
2
3
SELECT prod_name
FROM products
LIMIT 5,5

LIMIT的两种情况

  • LIMIT 检索的开始行 行数
  • LIMIT 行数()从第一行开始

排序数据

1
2
3
SELECT prod_name
FROM products
ORDER BY prod_name

按多个列排序

1
2
3
SELECT prod_name
FROM products
ORDER BY prod_name, prod_price

逆序

1
2
3
SELECT prod_name
FROM products
ORDER BY prod_name DESC
  • 顺序关键字为ASC,顺序逆序关键字只应用到直接位于其前面的列名

过滤数据

1
2
3
SELECT prod_name
FROM products
WHERE prod_name = test

WHERE子句操作符

1
=, <>, !=, <, <=, >, >=, BETWEEN, IS NULL
  • 在过滤数据时,无论匹配过滤还是不匹配过滤都不会返回NULL值的行

组合过滤关键字

1
AND, OR, IN, NOT
  • AND的优先级比OR高

    1
    WHERE vend_id = 1002 OR vend_id = 1003 AND prod_price >= 10
  • IN表示范围中的每个条件都可以进行匹配

    1
    WHERE vend_id IN (1002, 1003)

    相当于

    1
    WHERE vned_id = 1002 OR vwnd_id = 1003

    IN可以包含其他SELECT语句

用通配符过滤

通配符:匹配值的一部分的特殊字符

LIKE操作符

%通配符

%表示任何字符出现任意次数

1
2
3
4
5
6
7
8
所有以jet开头的产品
SELECT prod_id, prod_name
FROM products
WHERE prod_name LIKE 'jet%'

在任何位置包含文本jet的值
...
WHERE prod_name LIKE '%jet%'
  • 区分大小写
  • %能匹配0、1或多个字符
  • 尾空格会干扰通配符匹配,解决方法:在搜索模式最后附加一个%
  • %通配符不能匹配NULL
_通配符

用法类似%,但只匹配单个字符

1
2
3
4
产品名形如 1 ton anvil, e ton_anvil
SELECT prod_id, prod_name
FROM products
WHERE prod_name LIKE '_ ton anvil'
  • 通配符搜索的处理较慢,不要过度使用通配符,若其他操作符能做到,就用其他操作符
  • 除非必要,否则不要把通配符用在搜索模式的开始处,搜索起来最慢

用正则表达式进行搜索

REGEXP

REGEXP后所跟的东西作为正则表达式

1
2
3
SELECT prod_name
FROM products
WHERE prod_name REGEXP '1000'

.

.在正则表达式中表示匹配任意一个字符

  • LIKE和REGEXP的区别:
    • LIKE匹配整个列(整个串),REGEXP在列值内进行匹配(子串)
    • 正则表达式不区别大小写

|

用于OR匹配

1
WHERE prod_name REGEXP '1000|2000|3000'

[]

匹配几个字符之一

1
WHERE prod_name REGEXP '[123] Ton'

[-]

匹配范围

1
2
3
WHERE prod_name REGEXP '[1-5]'
等价于
WHERE prod_name REGEXP ‘1|2|3|4|5'

特殊字符

1
2
3
\\.表示查找.
\\-表示查找-
\\\表示查找\

空白元字符

元字符 说明
\ \ f 换页
\ \ n 换行
\ \ r 回车
\ \ t 制表
\ \ v 纵向制表

匹配字符类

说明
[:alnum:] 任意字母和数字(同[a-zA-Z0-9])
[:alpha:] 任意字符(同[a-zA-Z])
[:blank:] 空格和制表(同[\t])
[:cntrl:] ASCII控制字符(ASCII 0到31和127)
[:digit:] 任意数字(同[0-9])
[:graph:] 与[:print:]相同,但不包括空格
[:lower:] 任意小写字母(同[a-z])
[:print:] 任意可打印字符
[:punct:] 既不在[:alnum:]又不在[:cntrl:]中的任意字符
[:space:] 包括空格在内的任意空白字符(同[\f\n\r\t\v])
[:upper:] 任意大写字母(同[A-Z])
[:xdigit:] 任意十六进制数字(同[a-fA-F0-9])

重复元字符

元字符 说明
* 0个或多个匹配
+ 1个或多个匹配(等于{1,})
? 0个或1个匹配(等于{0,1})
{n} 指定数目的匹配
{n,} 不少于指定数目的匹配
{n,m} 匹配数目的范围(m不超过255)
1
2
3
4
匹配形如
TNT (1 stick)
TNT (5 sticks)
REGEXP '\\([0-9] sticks?\\)'
1
2
匹配连在一起的4位数字
REGEXP '[[:digit:]]{4}'

定位符

匹配特定位置的文本

元字符 说明
^ 文本的开始
$ 文本的结尾
[[:<:]] 词的开始
[[:>:]] 词的结尾
1
2
匹配以数字或.开头的列值
REGEXP '^[0-9\\.]'

计算字段

拼接字段

Concat()拼接两个列,各个串之间用逗号分隔

1
2
3
SELECT Concat(vend_name, '(', vend_country, ')')
FROM vendors
ORDER BY vend_name
  • 多数DBMS用+或||来实现拼接,MySQL用Concat()实现

RTrim()用于删除数据右侧多余的空格来整理数据,LTrim()删除左侧多余空格

使用别名

AS赋予别名

1
2
3
SELECT Concat(vend_name, '(', vend_country, ')') AS vend_title
FROM vendors
ORDER BY vend_name

算术运算

可以在SELECT中使用加减乘除

1
2
3
SELECT quantity*item AS expanded_price
FROM orderitems
WHERE order_num = 20005

函数

文本处理函数

函数 说明
Left() 返回串左边的字符
Length() 返回串的长度
Locate() 找出串的一个子串
Lower() 将串转换为小写
LTrim() 去掉串左边的空格
Right() 返回串右边的字符
RTrim() 去掉串右边的空格
Soundex() 返回串的SOUNDEX值
SubString() 返回子串的字符
Upper() 将串转换为大写

日期和时间处理函数

函数 说明
AddDate() 增加一个日期(天、周等)
AddTime() 增加一个时间(时、分等)
CurDate() 返回当前日期
CurTime() 返回当前时间
Date() 返回日期时间的日期部分
DateDiff() 计算两个日期之差
Date_Add() 高度灵活的日期运算函数
Date_Format() 返回一个格式化的日期或时间串
Day() 返回一个日期的天数部分
DayOfWeek() 对于一个日期,返回对应的星期几
Hour() 返回一个时间的小时部分
Minute() 返回一个时间的分钟部分
Month() 返回一个日期的月份部分
Now() 返回当前日期和时间
Second() 返回一个时间的秒部分
Time() 返回一个日期时间的时间部分
Year() 返回一个日期的年份部分
  • 检索时间时要注意转化

    1
    2
    3
    SELECT cust_id, order_num
    FROM orders
    WHERE order_date = '2005-09-01'

    若order_date = ‘2005-09-01 11:30:05’则匹配失败

    应改为

    1
    2
    3
    SELECT cust_id, order_num
    FROM orders
    WHERE Date(order_date) = '2005-09-01'
  • 检索2005年9月的所有订单

    1
    2
    3
    SELECT cust_id, order_num
    FROM orders
    WHERE Date(order_date) BETWEEN '2005-09-01' AND '2005-09-30'

    1
    2
    3
    SELECT cust_id, order_num
    FROM orders
    WHERE Year(order_date) = 2005 AND Month(order_date) = 9

数值处理函数

函数 说明
Abs() 返回一个数的绝对值
Cos() 返回一个角度的余弦
Exp() 返回一个数的指数值
Mod() 返回除操作的余数
Pi() 返回圆周率
Rand() 返回一个随机数
Sin() 返回一个角度的正弦
Sqrt() 返回一个数的平方根
Tan() 返回一个角度的正切

汇总数据

聚集函数

函数 说明
AVG() 返回某列的平均值
COUNT() 返回某列的行数
MAX() 返回某列的最大值
MIN() 返回某列的最小值
SUM() 返回某列值之和
  • 如果指定列名,则指定列的值为空的行被COUNT()函数忽略,但如果COUNT()函数中用的是*,则不忽略
  • MAX()、MIN()、SUM()函数忽略值为NULL的行

聚集不同的值

指定DISTINCT参数

1
2
3
SELECT AVG(DISTINCT prod_price) AS avg_price
FROM products
WHERE vend_id = 1003
  • DISTINCT必须使用列名,不能用于计算或表达式或*
  • DISTINCT一般只用于COUNT(),用于MIN(),MAX()无意义

分组数据

分组将数据分为多个逻辑组,便于对每个组进行聚集计算

创建分组

用GROUP BY创建分组

1
2
3
SELECT vend_id, COUNT(*) AS num_prods
FROM products
GROUP BY vend_id
  • GROUP BY子句必须出现在WHERE子句之后,ORDER BY子句之前
  • 如果分组列中具有NULL值,则NULL将作为一个分组返回。如果列中有多行NULL值,它们将分为一组

过滤分组

HAVING过滤分组(WHERE过滤行)

1
2
3
4
SELECT cust_id, COUNT(*) AS orders
FROM orders
GROUP BY vend_id
HAING COUNT(*) >= 2
  • HAVING和WHERE的区别:WHERE在数据分组之前过滤,HAVING在分组后进行过滤;WHERE排除的行不包括在分组中

    1
    2
    3
    4
    5
    SELECT cust_id, COUNT(*) AS orders
    FROM orders
    WHERE prod_price >= 10
    GROUP BY vend_id
    HAING COUNT(*) >= 2

子查询

1
2
3
4
5
SELECT cust_id
FROM orders
WHERE order_num IN(SELECT order_num
FROM orderitems
WHERE prod_id = 'TNT2')

联结表

内部联结

1
2
3
SELECT vend_name, prod_name, prod_price
FROM vendors v INNER JOIN products p
ON v.vend_id = p.vend_id

创建高级联结

自联结

1
2
3
4
SELECT p1.prod_id, p1.prod_name
FROM products AS p1, products AS p2
WHERE p1.vend_id = p2.vend_id
AND p2.prod_id = 'DTNTR'

外部联结

包含在相关表中没有关联行的行:OUT JOIN

在使用OUTER JOIN语法时,必须使用RIGHT或LEFT关键字指定包括其所有行的表

  • LEFT JOIN从左边的表中选择所有行
  • RIGHT JOIN从右边的表中选择所有行
1
2
3
SELECT customers.cust_id, orders.order_num
FROM customers RIGHT OUTER JOIN orders
ON orders.cust_id = customers.cust_id

组合查询

合并结果集

在各语句之间放上关键字UNION

1
2
3
4
5
6
7
SELECT vend_id, prod_id, prod_price
FROM products
WHERE prod_price <= 5
UNION
SELECT vend_id, prod_id, prod_price
FROM products
WHERE vend_id IN (1001, 1002)
  • UNION中的每个查询必须包含相同的列、表达式或聚集函数(不过各个列不需要以相同的次序列出)
  • 列数据类型必须兼容:类型不必完全相同,但必须是DBMS可以隐含地转换的类型(例如,不同的数值类型或不同的日期类型)
  • UNION从查询结果集中自动去除了重复的行,如果想返回所有匹配行,可使用UNION ALL而不是UNION

排序组合查询

在用UNION组合查询时,只能使用一条ORDER BY子句,它必须出现在最后一条SELECT语句之后

1
2
3
4
5
6
7
8
SELECT vend_id, prod_id, prod_price
FROM products
WHERE prod_price <= 5
UNION
SELECT vend_id, prod_id, prod_price
FROM products
WHERE vend_id IN (1001, 1002)
ORDER BY vend_id, prod_price

全文本搜索

两个最常使用的引擎为MyISAM和InnoDB,前者支持全文本搜索,而后者不支持

正则搜索的限制:

  • 性能
  • 难以明确控制

全文本搜索中数据是索引的,所以速度很快

启用全文本搜索支持

在CREATE时FULLTEXT(note_text)

进行全文本搜索

Match()指定被搜索的列,Against()指定要使用的搜索表达式

1
2
3
4
5
SELECT note_text
FROM productnotes
WHERE Match(note_text) Against('rabbit')
可以用LIKE
WHERE note_text LIKE '%rabbit%'
  • 传递给Match()的值必须与FULLTEXT()定义的相同,若指定多个列,就必须列出它们(而且次序正确)
  • 搜索不区分大小写

插入数据

插入完整的行

1
2
3
4
5
6
7
8
9
10
INSERT INTO customers
VALUES(NULL,
'Pep E',
'100 Main Street',
'Los Angeles',
'CA',
'90046',
'USA',
NULL,
NULL)
  • 没有输出
  • 可以省略都写列,但必须允许为NULL或给出默认值

插入多个行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
INSERT INTO customers
VALUES(NULL,
'Pep E',
'100 Main Street',
'Los Angeles',
'CA',
'90046',
'USA',
NULL,
NULL),
(NULL,
'Pep E',
'100 Main Street',
'Los Angeles',
'CA',
'90046',
'USA',
NULL,
NULL),

插入检索的数据

不一定要求列名匹配

更新和删除数据

更新数据

更新时注意不要省略WHERE子句,否则会更新所有行

1
2
3
4
UPDATE customers
SET cust_email = 'elmer@qq.com'
cust_name = 'Wynton'
WHERE cust_id = 10005
  • 可以使用子查询,使得能用检索出来的数据更新列数据
  • IGNORE可以在更新多行时,即使发生错误也能继续更新,否则整个UPDATE操作将被取消
  • 删除某个列的值可以设置其为NULL(若允许)

删除数据

1
2
DELETE FROM customers
WHERE cust_id = 10006

更新和删除时先用SELECT进行测试

创建和操纵表

创建表

1
2
3
4
5
6
7
8
CREATE TABLE customers
(
cust_id int NOT NULL AUTO_INCREMENT,
cust_name char(50) NOT NULL,
cust_address char(50) NULL,
cust_city char(50) NULL DEFAULT 'Los',
PRIMARY KEY (cust_id)
)ENGINE=InnoDB
  • AUTO_INCREMENT表示,本列每当增加一行时自动增量
  • 每个表只允许一个AUTO_INCREMENT列,而且它必须被索引(如,通过使它成为主键)
  • 默认值用DEFAULT指定
  • ENGINE指定引擎类型

更新表定义

1
2
3
ALTER TABLE vendors
ADD vend_phone CHAR(20)
DROP COLUMN vend_phone

删除表

1
DROP TABLE customers2

重命名表

1
RENAME TABLE customers TO customers2

使用视图

视图常见应用

  • 重用SQL语句
  • 简化复杂的SQL操作。在编写查询后,可以方便地重用它而不必知道它的基本查询细节
  • 使用表的组成部分而不是整个表
  • 保护数据。可以给用户授予表的特定部分的访问权限而不是整个表的访问权限
  • 更改数据格式和表示。视图可返回与底层表的表示和格式不同的数据

使用视图

  • 视图用CREATE VIEW语句来创建
  • 使用SHOW CREATE VIEW viewname;来查看创建视图的语句
  • 用DROP删除视图,其语法为DROP VIEW viewname;
  • 更新视图时,可以先用DROP再用CREATE,也可以直接用CREATE ORREPLACE VIEW
1
2
3
4
CREATE VIEW productcustomers AS
SELECT cust_name,...
FROM customers,...
WHERE ...
  • 使用视图可以一次性编写基础SQL,根据需要多次使用

利用视图格式化检索出的数据

1
2
3
4
5
CREATE VIEW productcustomers AS
SELECT Concat(RTrim(cust_name),...) AS vend_title
FROM customers,...
WHERE ...
ORDER BY ...

利用视图过滤不想要的数据

1
2
3
4
CREATE VIEW customereamillist AS
SELECT cust_id, cust_name, cust_email
FROM customers
WHERE cust_email IS NOT NULL

利用视图与计算字段

使用存储过程

优点:简单、安全、高性能

执行存储过程

1
2
3
CALL productpricing(@pricelow
@pricehigh
@priceaverage)

创建存储过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
CREATE PROCEDURE productpricing(
OUT pl DECIMAL(8, 2)
OUT ph DECIMAL(8, 2)
OUT pa DECIMAL(8, 2)
)
BEGIN
SELECT MIN(prod_price)
INTO pl
FROM products;
SELECT MAX(prod_price)
INTO ph
FROM products;
SELECT AVG(prod_price)
INTO pa
FROM products;
END;

使用游标

使用游标的原因

使用简单的SELECT语句,例如,没有办法得到第一行、下一行或前10行,也不存在每次一行
地处理所有行的简单方法(相对于成批地处理它们)
有时,需要在检索出来的行中前进或后退一行或多行,游标(cursor)是一个存储在MySQL服务器上的数据库查询,它不是一条SELECT语句,而是被该语句检索出来的结果集

创建游标

1
2
3
4
5
6
CREATE PROCEDURE processorders()
BEGIN
DECLARE ordernumbers CURSOR
FOR
SELECT order_num FROM orders;
END;

打开和关闭游标

1
2
OPEN ordernumbers
CLOSE ordernumbers

使用游标数据

将数据检索到一个o的局部声明的变量中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
CREATE PROCEDURE processorders()
BEGIN
DECLARE o INT;

DECLARE ordernumbers CURSOR
FOR
SELECT order_num FROM orders;

OPEN ordernumbers;

FETCH ordernumbers INTO o;

CLOSE ordernumbers;
END;

1
2
3
4
5
...
REPEAT
FETCH ordernumbers INTO o;
UNTIL done END REPEAT;
...

加入条件语句的复杂版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
CREATE PROCEDURE processorders()
BEGIN
DECLARE done BOOLEAN DEFAULT 0;
DECLARE 0 INT;
DECLARE t DECIMAL(8,2);

DECLARE ordernumbers CURSOR
FOR SELECT order_num FROM orders;
DECLARE CONTINUE HANDLER FOR SQLSTATE '02000' SET done=1;

CREATE TABLE IF NOT EXITS ordertotals
OPEN ordernumbers;

REPEAT
FETCH orders INTO o;
CALL ordertotal(o,1,t)
INSERT INTO ordertotals(order_num, total)
VALUES(o,t);
UNTIL done END REPEAT;
CLOSE ordernumbers;
END;

使用触发器

触发器是MySQL响应以下任意语句而自动执行的一条MySQL语句

  • DELETE
  • INSERT
  • UPDATE

创建触发器

1
2
CREATE TRIGGER newproduct AFTER INSERT ON products
FOR EACH ROW SELECT 'Product added'

删除触发器

1
DROP TRIGGER newproduct

INSERT触发器

  • 在INSERT触发器代码内,可引用一个名为NEW的虚拟表,访问被插入的行
  • 在BEFORE INSERT触发器中,NEW中的值也可以被更新(允许更改被插入的值)
  • 对于AUTO_INCREMENT列,NEW在INSERT执行之前包含0,在INSERT执行之后包含新的自动生成值
1
2
CREATE TRIGGER neworder AFTER INSERT ON orders
FOR EACH ROW SELECT NEW.order_num

DELETE触发器

  • 在DELETE触发器代码内,你可以引用一个名为OLD的虚拟表,访问被删除的行
1
2
3
4
5
CREATE TRIGGER deleteorder BEFORE DELETE ON orders
FOR EACH ROW
BEGIN
INSERT INTO archive_orders(order_num, order_date, cust_id)
VALUES(OLD.order_num, OLD.order_date, OLD.cust_id)

UPDATE触发器

  • 在UPDATE触发器代码中,你可以引用一个名为OLD的虚拟表访问以前(UPDATE语句前)的值,引用一个名为NEW的虚拟表访问新更新的值
  • 在BEFORE UPDATE触发器中,NEW中的值可能也被更新(允许更改将要用于UPDATE语句中的值)
  • OLD中的值全都是只读的,不能更新
1
2
CREATE TRIGGER updatevendor BEFORE UPDATE ON vendors
FOR EACH ROW SET NEW.vend_state = Upper(NEW.vend_state)

使用事务管理

事务处理可以用来维护数据库的完整性,它保证成批的MySQL操作要么完全执行,要么完全不执行

标识事务的开始

1
START TRANSACTION

ROLLBACK回退SQL语句

1
2
3
4
5
6
SELECT * FROM ordertotals;
START TRANSACTION;
DELETE FROM ordertotals;
SELECT * FROM ordertotals;
ROLLBACK;
SSELECT * FROM ordertotals;

使用COMMIT

1
2
3
4
START TRANSACTION
DELETE FROM orderitems WHERE order_num = 20010;
DELETE FROM orders WHERE order_num = 20010;
COMMIT;

使用保留点

1
SAVEPOINT delete1;
1
ROLLBACK TO delete1;

听力

做题流程

  • 播放每段听力前有一段时间可以看题
  • 看定位词:具体的难以替换的名词
  • 看限定词:e.g.best、today、in the festival…
  • 用圈圈圈出可能被同义替换的词,用下划线画出定位词

  • 预判词性和内容,在每个空后面写出可能的词性(听的时候注意该词性的词)

  • 听到的词打勾(防止听飞了)
  • 否定词是重点:e.g.without…
  • 转折是重点:e.g.but、wait a minute…

  • 写的时候不用拼完整个单词,否则很容易漏掉下一题

  • 字数
  • 词性
  • 单复数
  • 拼写

练习方法

精听

  • 泛听一遍
  • 总结:生词、连读、同义替换、答案规律
  • 听写(理解文章80%后)
    • 听弱点
    • 边听边记录(实词)&听完理解意思后写(补虚词)
    • 有干扰项的要整句听写
      • 选择题:整句听写
      • 填空题:单词听写

跟读

先看懂原文,看懂但听不懂的再跟读

  • 第一遍:边听边读(不出声)
  • 第二遍:听一句读一句(并录音)

题型

填空题

比较简单

  • 第一题会比较难听到
  • 一般表示街道等名字的词是小学级别的词汇:e.g.Forrest Road

选择题

一般情况下,原文原词不会是正确答案,每个选项都会在原文中出现,但会做同义替换

  • 选项中难以被同义替换的词很可能不选:e.g.Monday,Thursday and Friday
  • 不能听原文原词,要听同义替换

表格题

  • 表头都是定位词

配对题

答案紧凑,如果迟疑很容易错过下一题

  • 要读开头的问句:有可能会设置陷阱

  • 判断是选项/题干较有可能发生同义替换,决定看题重点

  • 提纲式填空:S4主考题型

    小标题是定位词,如果听飞了可以用小标题找回来

  • 听的时候有几种写的方法,看情况使用

    • 正常写
    • 将题号写在选项旁边
    • 写关键词(一般不用)
  • 看题时可以合并同类项,如上升的用线连起来,下降的…

  • 同义选项中更泛的一般不会选

地图题

Tips

  • -ty和-teen的区别:听重音的区别
  • 同义替换是重点!!
  • 状语从句可能发生答案前置
  • 听到类似between、range of时要注意范围

  • 表示时间的格式:27,1,2017/December,27/27,December

  • 表示街道:Road/Street/Drive/Lane/Avenue
  • A NUMBER 可以是数字+字母

无线网络

无线链路的特征(与有线区别)

  • 递减的信号强度:电磁波在穿过物体时强度减弱
  • 来自其他源的干扰:同一频段发送信号的电波源将相互干扰
  • 多路径传播:走了不同长度的路径

信噪比

收到的信号和噪声强度的相对测量,较大的SNR使接收方更容易提取传输的信号

802.11MAC协议

无线LAN采用随机访问协议:带碰撞避免的CSMA(CSMA/CA)

802.11使用链路层确认/重传(ARQ)机制

802.11未实现碰撞检测
  • 接收信号的强度通常远远小于发送信号的强度,构建具有检测碰撞能力的硬件代价较大
  • 适配器会由于隐藏终端问题和衰减问题无法检测到所有的碰撞
802.11的CSMA/CA协议
  • 若初始时某站点监听到信道空闲,在一个分布式帧间间隔(DIFS)的短时间段后发送该帧
  • 否则,选取一个随机回退值并且在侦听信道空闲时递减该值,侦听到信道忙时,计数值保持不变
  • 当计数值减为0时(只可能发生在信道被侦听为空闲时),站点发送整个数据帧并等待确认
  • 若果收到确认,发送站知道它的帧已经被目的站接收了

链路层

概述

链路层协议采取的动作包括差错检测、重传、流量控制和随机接入

链路层协议的任务:将网络层的数据报通过路径中的单端链路节点到节点地传送

数据报在不同的链路上可能由不同链路层协议所承载

链路层能提供的服务

  • 成帧
  • 链路接入
  • 可靠交付通过确认和重传取得
  • 流量控制
  • 差错检测和纠正
  • 半全工和双全工:可否同时传输和接收

链路层的主体部分在网络适配器中实现,也称为网络接口卡

差错检测和纠错

比特级差错检测和纠错

奇偶校验

奇检测

包含一个附加比特,使得d+1个比特中1的总数总为奇数;偶检测相反

只能检测奇数个比特差错

二维奇偶校验

可以纠错单个比特差错,可以检测(但不能纠正)一个分组中两个比特差错的任何组合

检验和方法

将k比特的整数加起来,并且用得到的和作为差错检测比特

循环冗余检测

  • r+1比特模式,R有r个比特
  • CRC采用模2算术操作,加法不进位减法不借位

接收方检验:用G去除d+r,余数为0则无差错

多路访问协议

信道划分协议

分类
  • 时分多路复用(TDM):将时间划分为时间帧,并进一步划分为N个时隙
  • 频分多路复用(FDM)
  • 码分多址(CDMA):每个节点分配不同的编码
FDM、TDM的缺陷
  • 节点被限制在R/N的平均速率,即使它为唯一有分组要发送的节点
  • 节点必须总是等待它再传输序列中的轮次,即使它是唯一一个有帧要发送的节点
FDM、TDM优点
  • 避免碰撞、公平划分带宽
CMDA

CDMA对每个节点只分配一种不同的编码,不同的节点能同时传输,互不干扰

随机接入协议

一个节点总是以信道的全部速率进行发送,有碰撞时,涉及碰撞的节点反复重发它的帧,直至无碰撞为止。但不是立刻重发,而是等待一个随机时延

效率

当有大量活跃节点且每个节点总有大量的帧要发送时,长期运行中成功时隙的份额

时隙ALOHA

如果有碰撞,节点在时隙结束之前检测到这次碰撞,以概率p在后续每个时隙中重传它的帧,直到该帧被无碰撞地传输出去

优点:只有一个活跃节点时工作出色

当有N个节点时其效率为Np(1-p)^(N-1),最大效率约为1/2e(0.37)

ALOHA

若发生碰撞,下一时隙以p概率重传该帧,以(1-p)概率等待一帧;等待之后如前

最大效率为1/2e

载波侦听多路访问CSMA
  • 载波侦听:发送前先侦听,若空闲则发送,否则等待
  • 碰撞检测:若碰撞则停止传输

有碰撞检测的CSMA:CSMA/CD

由于存在信道传播时延,即使进行了载波侦听,仍可能出现碰撞。信道传输时延越大,载波侦听节点越可能不能侦听到网络中另一节点已开始传输

轮流协议

轮询协议

指定节点之一为主节点,主节点以循环的方式轮询每个节点

缺点:

  • 若只有一个节点时活跃的,主节点也必须依次轮询
  • 若主节点有故障,整个信道不可操作
令牌传递协议

没有主节点,有帧要发送的节点才持有令牌,否则将令牌转发,效率高

缺点:一个节点的故障会使整个信道崩溃

LANs

LAN:Local Area Network 局域网

MAC地址

LAN地址、物理地址、MAC地址

同个子网下,数据链路层在网络适配器间传输数据使用的地址标识

长度6个字节,每个字节为一对16进制数,具有扁平结构(所以具备可迁移性)

MAC广播地址:FF-FF-FF-FF-FF-FF

地址解析协议ARP

将网络层地址转换为链路层地址

每个节点(主机或路由器)的ARP模块都有一个ARP表

DNS和ARP的区别

DNS为因特网中任何地方的主机解析主机名,但ARP只为同一个子网下的节点解析IP地址

ARP表
IP地址 MAC地址 TTL
222.222.222.221 88-B2-2F-54-1A-0F 13:45:00

生存期(TTL):从表中删除每个映射的时间

ARP寻址的过程
  • 发送节点构造并广播ARP查询分组,其中包括发送节点和接受节点的MAC地址和IP地址(接受节点的MAC地址为广播地址)
  • 子网中的适配器接收后,向上传递给节点中的ARP模块,检查IP地址是否与ARP分组中的匹配
  • 一个匹配的节点给查询节点发送回一个响应ARP分组
  • 发送节点更新ARP表
发送数据报到子网以外的节点

源IP地址,源MAC地址:主机的IP地址和MAC地址

目的IP地址,目的MAC地址:目的主机IP地址,网关的MAC地址(路由器响应接口的MAC地址)

若直接使用目的主机的MAC地址,子网中的适配器都不会将其传递到网络层,因为该帧的目的地址都不与子网中适配器的MAC地址匹配

具体过程:

  • 主机通过ARP获取通往目的子网的路由器与本地网相连端口的MAC地址,创建帧并将其放入子网中
  • 路由器接收该帧,并将数据报交付给网络层,查询转发表,获取转发接口后,将数据转发到该接口
  • 接口将数据报交付给其适配器,适配器将数据报封装到一个新的帧中,该帧的目的地址为最终目的地址的MAC地址(MAC地址通过ARP获得),同时源MAC地址为此时适配器的MAC地址

以太网

提供无连接、不可靠服务

以太网帧结构
  • 数据字段 46-1500字节:以太网最大传输单元(MTU)为1500字节,数据段最小长度为46字节,如果不足需要填充
  • 目的地址 6字节:目的适配器的MAC地址
  • 源地址 6字节:传输该帧到LAN上的适配器的MAC地址
  • 类型字段 2字节:允许以太网复用多种网络协议
  • 循环冗余检测CRC 4字节:目的是使得接收适配器检测帧中是否进入了差错
  • 前同步码 8字节:前七个字节为10101010,最后一个字节为10101011,用于唤醒接收适配器,同步其时钟与发送方时钟
CSMA/CD

以太网的多路访问协议

CSMA/CD机制:

  • 适配器可以在任何时刻开始传输,没有时隙概念
  • 载波侦听:当适配器侦听到有其他适配器正在传输,不传输帧
  • 碰撞检测:当传输中的适配器检测到有其他适配器正在传输,终止传输
  • 重传前适配器等待一个随机时间,通常比传输一帧的时间短

CSMA/CD工作方式:

  • 适配器从网络层得到一个数据报,准备一个以太网帧并放到适配器缓存区中
  • 若适配器侦听到信道空闲,开始传输
  • 传输过程中监视来自其他适配器的信号能量
  • 如果检测到来自其他适配器的信号能量,停止传输
  • 中止后适配器进入指数后退阶段,在该帧经受了n次连续碰撞后,适配器随机从{0,1,2,…,2^m-1}为K选择一个值,m=min{n,10},适配器等待K*512比特时间,返回第二步(随机、指数增长的上界)
以太网效率

网线越长,效率越低

交换机

交换机是即插即用设备

交换机功能
  • 过滤:决定一个帧应该转发还是丢弃

  • 转发:决定一个帧应该被导向哪个接口,并移动帧

  • 借助交换机表完成,交换机表:

    | MAC地址 | 到达节点的交换机接口 | 表项放置在表中的时间 |
    | —————– | ——————– | ——————– |
    | 62-FE-F7-11-89-A3 | 1 | 9:32 |

交换机工作过程

假定有目的地址DD-DD-DD-DD-DD-DD的帧从交换机接口x到达

  • 若表中没有DD-DD-DD-DD-DD-DD的表项,交换机广播该帧
  • 若存在表项将DD-DD-DD-DD-DD-DD与接口x联系起来,交换机丢弃该帧(过滤功能)
  • 若存在表项将DD-DD-DD-DD-DD-DD与接口y(!= x)联系起来,交换机将该帧转发到y接口,并将信息添加到表项中
自学习
  • 交换机表初始为空
  • 对于接口收到的每个帧,交换机在其表中记录
    • 该帧源地址字段中的MAC地址
    • 该帧到达的接口
    • 当前的时间
  • 接下来一段时间(老化期)中,交换机没有接收到以该址为源地址的帧,则删除该地址
交换机的性质
  • 消除碰撞
  • 异质的链路:交换机将链路彼此隔离
  • 管理
交换机和路由器的比较
  • 由于交换机只需要查看二层数据帧 的头部即可决策转发地址,策略十分简单,可以直接通过硬件芯片实现相应功能,所以可以做到廉价高速,被大量应用在接入层。
  • 而路由器由于需要处理跨网络的连接,必须在接收到完整的 IP数据包 后才能转发数据,路由协议又比较复杂,所以只能使用软件的方式实现相应的功能,要达到高性能只能付出更高的价格
  • 交换机的优缺点
    • 优点:即插即用;具有相对高的分组过滤和转发速率
    • 缺点:对广播风暴不提供保护措施
  • 路由器的优缺点
    • 优点:即使网络存在冗余路径,分组也不会通过路由器循环;对第二层的广播风暴提供了防火墙保护
    • 缺点:非即插即用;处理时间较长

PPP

高级数据链路控制协议(HDLC)

PPP数据成帧
  • 标志 1字节
  • 地址 1字节
  • 控制 1字节
  • 协议 1或2字节
  • 信息 可变长度
  • 检验和 2或4字节
  • 标志 1字节

VLAN

局域网缺点

  • 缺乏流量隔离
  • 交换机的无效使用
  • 管理用户

支持VLAN的交换机允许经一个单一的物理局域网基础设施定义多个虚拟局域网

多协议标签交换MPLS

MPLS首部

标签、实验、S、TTL

Web请求

DHCP(UDP)、AQP、DNS(UDP)、HTTP、FTP

RIP/OSPF、BGP

详见PPT 或 课本p330

DHCP

  • DHCP请求报文 生成UDP报文段 放入以太网帧 广播
  • 被分解 CIDR分配地址 收到DHCPACK

ARP

  • DNS查询报文
  • ARP查询报文查询网关路由器MAC地址
  • ARP回答,获取网关路由器的MAC地址

DNS

  • 网关路由器接收转发 通过域内协议和域间协议BGP
  • 找到DNS源记录 查询权威DNS 生成DNS回答报文 放入UDP IP数据报

TCP

  • 生成TCP套接字
  • 三次握手:TCPSYN报文段 TCPSYNACK报文段

HTTP

  • HTTP请求 HTTP GET报文
  • 服务器生成HTTP响应报文 放入请求内容 发送到TCP套接字
  • 获取响应 渲染