《Redis 设计与实现》&《Redis 实战》【转】

原文链接: https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Redis.md

一、Redis 是什么

Redis 是速度非常快的非关系型(NoSQL)内存键值数据库,可以存储键和五种不同类型的值之间的映射。

五种类型数据类型为:字符串、列表、集合、有序集合、散列表。

Redis 支持很多特性,例如将内存中的数据持久化到硬盘中,使用复制来扩展读性能,使用分片来扩展写性能。

二、五种基本类型

数据类型 可以存储的值 操作
STRING 字符串、整数或者浮点数 对整个字符串或者字符串的其中一部分执行操作
对整数和浮点数执行自增或者自减操作
LIST 链表 从两端压入或者弹出元素
读取单个或者多个元素
进行修剪,只保留一个范围内的元素
SET 无序集合 添加、获取、移除单个元素
检查一个元素是否存在于集合中
计算交集、并集、差集
从集合里面随机获取元素
HASH 包含键值对的无序散列表 添加、获取、移除单个键值对
获取所有键值对
检查某个键是否存在
ZSET 有序集合 添加、获取、删除元素
根据分值范围或者成员来获取元素
计算一个键的排名

What Redis data structures look like

1. STRING

1
2
3
4
5
6
7
8
> set hello world
OK
> get hello
"world"
> del hello
(integer) 1
> get hello
(nil)

2. LIST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
> rpush list-key item
(integer) 1
> rpush list-key item2
(integer) 2
> rpush list-key item
(integer) 3

> lrange list-key 0 -1
1) "item"
2) "item2"
3) "item"

> lindex list-key 1
"item2"

> lpop list-key
"item"

> lrange list-key 0 -1
1) "item2"
2) "item"

3. SET

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
> sadd set-key item
(integer) 1
> sadd set-key item2
(integer) 1
> sadd set-key item3
(integer) 1
> sadd set-key item
(integer) 0

> smembers set-key
1) "item"
2) "item2"
3) "item3"

> sismember set-key item4
(integer) 0
> sismember set-key item
(integer) 1

> srem set-key item2
(integer) 1
> srem set-key item2
(integer) 0

> smembers set-key
1) "item"
2) "item3"

4. HASH

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
> hset hash-key sub-key1 value1
(integer) 1
> hset hash-key sub-key2 value2
(integer) 1
> hset hash-key sub-key1 value1
(integer) 0

> hgetall hash-key
1) "sub-key1"
2) "value1"
3) "sub-key2"
4) "value2"

> hdel hash-key sub-key2
(integer) 1
> hdel hash-key sub-key2
(integer) 0

> hget hash-key sub-key1
"value1"

> hgetall hash-key
1) "sub-key1"
2) "value1"

5. ZSET

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
> zadd zset-key 728 member1
(integer) 1
> zadd zset-key 982 member0
(integer) 1
> zadd zset-key 982 member0
(integer) 0

> zrange zset-key 0 -1 withscores
1) "member1"
2) "728"
3) "member0"
4) "982"

> zrangebyscore zset-key 0 800 withscores
1) "member1"
2) "728"

> zrem zset-key member1
(integer) 1
> zrem zset-key member1
(integer) 0

> zrange zset-key 0 -1 withscores
1) "member0"
2) "982"

三、键的过期时间

Redis 可以为每个键设置过期时间,当键过期时,会自动删除该键。

1
2
3
4
5
6
7
8
9
10
11
12
> set my-key-test 1
OK
> get my-key-test
"1"
> expire my-key-test 5
(integer) 1
> ttl my-key-test
(integer) 4
> persist my-key-test
(integer) 1
> get my-key-test
"1"

对于散列表这种容器,只能为整个键设置过期时间(整个散列表),而不能为键里面的单个元素设置过期时间。

过期时间对于清理缓存数据非常有用。

四、发布与订阅

订阅者订阅了频道之后,发布者向频道发送字符串消息会被所有订阅者接收到。

发布与订阅模式和观察者模式有以下不同:

  • 观察者模式中,观察者和主题都知道对方的存在;而在发布与订阅模式中,发布者与订阅者不知道对方的存在,它们之间通过频道进行通信。
  • 观察者模式是同步的,当事件触发时,主题会去调度观察者的方法;而发布与订阅模式是异步的;

发布与订阅有一些问题,很少使用它,而是使用替代的解决方案。问题如下:

  1. 如果订阅者读取消息的速度很慢,会使得消息不断积压在发布者的输出缓存区中,造成内存占用过多;
  2. 如果订阅者在执行订阅的过程中网络出现问题,那么就会丢失断线期间发送的所有消息。

五、事务

Redis 最简单的事务实现方式是使用 MULTI 和 EXEC 命令将事务操作包围起来。

MULTI 和 EXEC 中的操作将会一次性发送给服务器,而不是一条一条发送,这种方式称为流水线,它可以减少客户端与服务器之间的网络通信次数从而提升性能。

Redis只能保证事务的每个命令连续执行,但是如果事务中的一个命令失败了,并不回滚其他命令,比如使用的命令类型不匹配。当事务的执行过程中,如果redis意外的挂了。很遗憾只有部分命令执行了,后面的也就被丢弃了。当然如果我们使用的append-only file方式持久化,redis会用单个write操作写入整个事务内容。即是是这种方式还是有可能只部分写入了事务到磁盘。发生部分写入事务的情况 下,redis重启时会检测到这种情况,然后失败退出。可以使用redis-check-aof工具进行修复,修复会删除部分写入的事务内容。修复完后就能够重新启动了。(redis学习笔记之事务

六、持久化

Redis 是内存型数据库,为了保证数据在断电后不会丢失,需要将内存中的数据持久化到硬盘上。

1. 快照持久化

将某个时间点的所有数据都存放到硬盘上。

可以将快照复制到其它服务器从而创建具有相同数据的服务器副本。

如果系统发生故障,将会丢失最后一次创建快照之后的数据。

如果数据量很大,保存快照的时间会很长。

2. AOF 持久化

将写命令添加到 AOF 文件(Append Only File)的末尾。

对硬盘的文件进行写入时,写入的内容首先会被存储到缓冲区,然后由操作系统决定什么时候将该内容同步到硬盘,用户可以调用 file.flush() 方法请求操作系统尽快将缓冲区存储的数据同步到硬盘。

将写命令添加到 AOF 文件时,要根据需求来保证何时将添加的数据同步到硬盘上,有以下同步选项:

选项 同步频率
always 每个写命令都同步
everysec 每秒同步一次
no 让操作系统来决定何时同步

always 选项会严重减低服务器的性能;everysec 选项比较合适,可以保证系统奔溃时只会丢失一秒左右的数据,并且 Redis 每秒执行一次同步对服务器性能几乎没有任何影响;no 选项并不能给服务器性能带来多大的提升,而且也会增加系统奔溃时数据丢失的数量。

随着服务器写请求的增多,AOF 文件会越来越大;Redis 提供了一种将 AOF 重写的特性,能够去除 AOF 文件中的冗余写命令。

七、复制

通过使用 slaveof host port 命令来让一个服务器成为另一个服务器的从服务器。

一个从服务器只能有一个主服务器,并且不支持主主复制。

从服务器连接主服务器的过程

  1. 主服务器创建快照文件,发送给从服务器,并在发送期间使用缓冲区记录执行的写命令。快照文件发送完毕之后,开始向从服务器发送存储在缓冲区中的写命令;

  2. 从服务器丢弃所有旧数据,载入主服务器发来的快照文件,之后从服务器开始接受主服务器发来的写命令;

  3. 主服务器每执行一次写命令,就向从服务器发送相同的写命令。

主从链

随着负载不断上升,主服务器可能无法很快地更新所有从服务器,或者重新连接和重新同步从服务器将导致系统超载。为了解决这个问题,可以创建一个中间层来分担主服务器的复制工作。中间层的服务器是最上层服务器的从服务器,又是最下层服务器的主服务器。

八、处理故障

要用到持久化文件来恢复服务器的数据。

持久化文件可能因为服务器出错也有错误,因此要先对持久化文件进行验证和修复。对 AOF 文件就行验证和修复很容易,修复操作将第一个出错命令和其后的所有命令都删除;但是只能验证快照文件,无法对快照文件进行修复,因为快照文件进行了压缩,出现在快照文件中间的错误可能会导致整个快照文件的剩余部分无法读取。

当主服务器出现故障时,Redis 常用的做法是新开一台服务器作为主服务器,具体步骤如下:假设 A 为主服务器,B 为从服务器,当 A 出现故障时,让 B 生成一个快照文件,将快照文件发送给 C,并让 C 恢复快照文件的数据。最后,让 B 成为 C 的从服务器。

九、分片

Redis 中的分片类似于 MySQL 的分表操作,分片是将数据划分为多个部分的方法,对数据的划分可以基于键包含的 ID、基于键的哈希值,或者基于以上两者的某种组合。通过对数据进行分片,用户可以将数据存储到多台机器里面,也可以从多台机器里面获取数据,这种方法在解决某些问题时可以获得线性级别的性能提升。

假设有 4 个 Reids 实例 R0,R1,R2,R3,还有很多表示用户的键 user:1,user:2,… 等等,有不同的方式来选择一个指定的键存储在哪个实例中。最简单的方式是范围分片,例如用户 id 从 0~1000 的存储到实例 R0 中,用户 id 从 1001~2000 的存储到实例 R1 中,等等。但是这样需要维护一张映射范围表,维护操作代价很高。还有一种方式是哈希分片,使用 CRC32 哈希函数将键转换为一个数字,再对实例数量求模就能知道应该存储的实例。

1. 客户端分片

客户端使用一致性哈希等算法决定键应当分布到哪个节点。

2. 代理分片

将客户端请求发送到代理上,由代理转发请求到正确的节点上。

3. 服务器分片

Redis Cluster。

十、事件

事件类型

1. 文件事件

服务器有许多套接字,事件产生时会对这些套接字进行操作,服务器通过监听套接字来处理事件。常见的文件事件有:客户端的连接事件;客户端的命令请求事件;服务器向客户端返回命令结果的事件;

2. 时间事件

又分为两类:定时事件是让一段程序在指定的时间之内执行一次;周期性时间是让一段程序每隔指定时间就执行一次。

事件的调度与执行

服务器需要不断监听文件事件的套接字才能得到待处理的文件事件,但是不能监听太久,否则时间事件无法在规定的时间内执行,因此监听时间应该根据距离现在最近的时间事件来决定。

事件调度与执行由 aeProcessEvents 函数负责,伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def aeProcessEvents():

# 获取到达时间离当前时间最接近的时间事件
time_event = aeSearchNearestTimer()

# 计算最接近的时间事件距离到达还有多少毫秒
remaind_ms = time_event.when - unix_ts_now()

# 如果事件已到达,那么 remaind_ms 的值可能为负数,将它设为 0
if remaind_ms < 0:
remaind_ms = 0

# 根据 remaind_ms 的值,创建 timeval
timeval = create_timeval_with_ms(remaind_ms)

# 阻塞并等待文件事件产生,最大阻塞时间由传入的 timeval 决定
aeApiPoll(timeval)

# 处理所有已产生的文件事件
procesFileEvents()

# 处理所有已到达的时间事件
processTimeEvents()

将 aeProcessEvents 函数置于一个循环里面,加上初始化和清理函数,就构成了 Redis 服务器的主函数,伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
def main():

# 初始化服务器
init_server()

# 一直处理事件,直到服务器关闭为止
while server_is_not_shutdown():
aeProcessEvents()

# 服务器关闭,执行清理操作
clean_server()

从事件处理的角度来看,服务器运行流程如下:

十一、Redis 与 Memcached 的区别

两者都是非关系型内存键值数据库。有以下主要不同:

数据类型

Memcached 仅支持字符串类型,而 Redis 支持五种不同种类的数据类型,使得它可以更灵活地解决问题。

数据持久化

Redis 支持两种持久化策略:RDB 快照和 AOF 日志,而 Memcached 不支持持久化。

分布式

Memcached 不支持分布式,只能通过在客户端使用像一致性哈希这样的分布式算法来实现分布式存储,这种方式在存储和查询时都需要先在客户端计算一次数据所在的节点。

Redis Cluster 实现了分布式的支持。

内存管理机制

在 Redis 中,并不是所有数据都一直存储在内存中,可以将一些很久没用的 value 交换到磁盘。而 Memcached 的数据则会一直在内存中。

Memcached 将内存分割成特定长度的块来存储数据,以完全解决内存碎片的问题,但是这种方式会使得内存的利用率不高,例如块的大小为 128 bytes,只存储 100 bytes 的数据,那么剩下的 28 bytes 就浪费掉了。

十二、Redis 适用场景

缓存

将热点数据放到内存中。

消息队列

List 类型是双向链表,很适合用于消息队列。

计数器

Redis 这种内存数据库能支持计数器频繁的读写操作。

好友关系

使用 Set 类型的交集操作很容易就可以知道两个用户的共同好友。

十三、数据淘汰策略

可以设置内存最大使用量,当内存使用量超过时施行淘汰策略,具体有 6 种淘汰策略。

策略 描述
volatile-lru 从已设置过期时间的数据集中挑选最近最少使用的数据淘汰
volatile-ttl 从已设置过期时间的数据集中挑选将要过期的数据淘汰
volatile-random 从已设置过期时间的数据集中任意选择数据淘汰
allkeys-lru 从所有数据集中挑选最近最少使用的数据淘汰
allkeys-random 从所有数据集中任意选择数据进行淘汰
no-envicition 禁止驱逐数据

如果使用 Redis 来缓存数据时,要保证所有数据都是热点数据,可以将内存最大使用量设置为热点数据占用的内存量,然后启用 allkeys-lru 淘汰策略,将最近最少使用的数据淘汰。

作为内存数据库,出于对性能和内存消耗的考虑,Redis 的淘汰算法(LRU、TTL)实际实现上并非针对所有 key,而是抽样一小部分 key 从中选出被淘汰 key。抽样数量可通过 maxmemory-samples 配置。

十四、一个简单的论坛系统分析

该论坛系统功能如下:

  • 可以发布文章;
  • 可以对文章进行点赞;
  • 在首页可以按文章的发布时间或者文章的点赞数进行排序显示;

文章信息

文章包括标题、作者、赞数等信息,在关系型数据库中很容易构建一张表来存储这些信息,在 Redis 中可以使用 HASH 来存储每种信息以及其对应的值的映射。

Redis 没有关系型数据库中的表这一概念来将同类型的数据存放在一起,而是使用命名空间的方式来实现这一功能。键名的前面部分存储命名空间,后面部分的内容存储 ID,通常使用 : 来进行分隔。例如下面的 HASH 的键名为 article:92617,其中 article 为命名空间,ID 为 92617。

点赞功能

当有用户为一篇文章点赞时,除了要对该文章的 votes 字段进行加 1 操作,还必须记录该用户已经对该文章进行了点赞,防止用户点赞次数超过 1。可以建立文章的已投票用户集合来进行记录。

为了节约内存,规定一篇文章发布满一周之后,就不能再对它进行投票,而文章的已投票集合也会被删除,可以为文章的已投票集合设置一个一周的过期时间就能实现这个规定。

对文章进行排序

为了按发布时间和点赞数进行排序,可以建立一个文章发布时间的有序集合和一个文章点赞数的有序集合。(下图中的 score 就是这里所说的点赞数;下面所示的有序集合分值并不直接是时间和点赞数,而是根据时间和点赞数间接计算出来的)

参考资料


《高性能 MySQL》【转】

原文链接: https://github.com/CyC2018/Interview-Notebook/blob/master/notes/MySQL.md

一、存储引擎

InnoDB

InnoDB 是 MySQL 默认的事务型存储引擎,只有在需要 InnoDB 不支持的特性时,才考虑使用其它存储引擎。

采用 MVCC 来支持高并发,并且实现了四个标准的隔离级别,默认级别是可重复读。

表是基于聚簇索引建立的,它对主键的查询性能有很高的提升。

内部做了很多优化,包括从磁盘读取数据时采用的可预测性读、能够自动在内存中创建哈希索引以加速读操作的自适应哈希索引、能够加速插入操作的插入缓冲区等。

通过一些机制和工具支持真正的热备份。

MyISAM

MyISAM 提供了大量的特性,包括全文索引、压缩、空间函数(GIS)等。但 MyISAM 不支持事务和行级锁,而且崩溃后无法安全恢复。应该注意的是,MySQL5.6.4 添加了对 InnoDB 引擎的全文索引支持。

只能对整张表加锁,而不是针对行。

可以手工或者自动执行检查和修复操作,但是和事务恢复以及崩溃恢复不同,可能导致一些数据丢失,而且修复操作是非常慢的。

可以包含动态或者静态的行。

如果指定了 DELAY_KEY_WRITE 选项,在每次修改执行完成时,不会立即将修改的索引数据写入磁盘,而是会写到内存中的键缓冲区,只有在清理键缓冲区或者关闭表的时候才会将对应的索引块写入磁盘。这种方式可以极大的提升写入性能,但是在数据库或者主机崩溃时会造成索引损坏,需要执行修复操作。

如果表在创建并导入数据以后,不会再进行修改操作,那么这样的表适合采用 MyISAM 压缩表。

对于只读数据,或者表比较小、可以容忍修复操作,则依然可以继续使用 MyISAM。

MyISAM 设计简单,数据以紧密格式存储,所以在某些场景下性能很好。

比较

  1. 事务:InnoDB 是事务型的。
  2. 备份:InnoDB 支持在线热备份。
  3. 崩溃恢复:MyISAM 崩溃后发生损坏的概率比 InnoDB 高很多,而且恢复的速度也更慢。
  4. 并发:MyISAM 只支持表级锁,而 InnoDB 还支持行级锁。
  5. 其它特性:MyISAM 支持,地理空间索引。

二、数据类型

整型

TINYINT, SMALLINT, MEDIUMINT, INT, BIGINT 分别使用 8, 16, 24, 32, 64 位存储空间,一般情况下越小的列越好。

INT(11) 中的数字只是规定了交互工具显示字符的个数,对于存储和计算来说是没有意义的。

浮点数

FLOAT 和 DOUBLE 为浮点类型,DECIMAL 为高精度小数类型。CPU 原生支持浮点运算,但是不支持 DECIMAl 类型的计算,因此 DECIMAL 的计算比浮点类型需要更高的代价。

FLOAT、DOUBLE 和 DECIMAL 都可以指定列宽,例如 DECIMAL(18, 9) 表示总共 18 位,取 9 位存储小数部分,剩下 9 位存储整数部分。

字符串

主要有 CHAR 和 VARCHAR 两种类型,一种是定长的,一种是变长的。

VARCHAR 这种变长类型能够节省空间,因为只需要存储必要的内容。但是在执行 UPDATE 时可能会使行变得比原来长,当超出一个页所能容纳的大小时,就要执行额外的操作。MyISAM 会将行拆成不同的片段存储,而 InnoDB 则需要分裂页来使行放进页内。

VARCHAR 会保留字符串末尾的空格,而 CHAR 会删除。

VARCHAR 的长度表示的是字符的数量,而不是字节数。MySQL 屏蔽了底层的编码细节。

时间和日期

MySQL 提供了两种相似的日期时间类型:DATATIME 和 TIMESTAMP。

1. DATATIME

能够保存从 1001 年到 9999 年的日期和时间,精度为秒,使用 8 字节的存储空间。

它与时区无关。

默认情况下,MySQL 以一种可排序的、无歧义的格式显示 DATATIME 值,例如“2008-01-16 22:37:08”,这是 ANSI 标准定义的日期和时间表示方法。

2. TIMESTAMP

和 UNIX 时间戳相同,保存从 1970 年 1 月 1 日午夜(格林威治时间)以来的秒数,使用 4 个字节,只能表示从 1970 年 到 2038 年。

它和时区有关。

MySQL 提供了 FROM_UNIXTIME() 函数把 UNIX 时间戳转换为日期,并提供了 UNIX_TIMESTAMP() 函数把日期转换为 UNIX 时间戳。

默认情况下,如果插入时没有指定 TIMESTAMP 列的值,会将这个值设置为当前时间。

应该尽量使用 TIMESTAMP,因为它比 DATETIME 空间效率更高。

三、索引

索引是在存储引擎层实现的,而不是在服务器层实现的,所以不同存储引擎具有不同的索引类型和实现。

索引能够轻易将查询性能提升几个数量级。

对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效。对于中到大型的表,索引就非常有效。但是对于特大型的表,建立和使用索引的代价将会随之增长。这种情况下,需要用到一种技术可以直接区分出需要查询的一组数据,而不是一条记录一条记录地匹配,例如可以使用分区技术。

索引分类

1. B+Tree 索引

《高性能 MySQL》一书使用 B-Tree 进行描述,其实从技术上来说这种索引是 B+Tree。

B+Tree 索引是大多数 MySQL 存储引擎的默认索引类型。

因为不再需要进行全表扫描,只需要对树进行搜索即可,因此查找速度快很多。

可以指定多个列作为索引列,多个索引列共同组成键。B+Tree 索引适用于全键值、键值范围和键前缀查找,其中键前缀查找只适用于最左前缀查找。

除了用于查找,还可以用于排序和分组。

如果不是按照索引列的顺序进行查找,则无法使用索引。

2. 哈希索引

基于哈希表实现,优点是查找非常快。

在 MySQL 中只有 Memory 引擎显式支持哈希索引。

InnoDB 引擎有一个特殊的功能叫“自适应哈希索引”,当某个索引值被使用的非常频繁时,会在 B+Tree 索引之上再创建一个哈希索引,这样就让 B+Tree 索引具有哈希索引的一些优点,比如快速的哈希查找。

限制:哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行。不过,访问内存中的行的速度很快,所以大部分情况下这一点对性能影响并不明显;无法用于分组与排序;只支持精确查找,无法用于部分查找和范围查找;如果哈希冲突很多,查找速度会变得很慢。

3. 空间索引(R-Tree)

MyISAM 存储引擎支持空间索引,可以用于地理数据存储。

空间索引会从所有维度来索引数据,可以有效地使用任意维度来进行组合查询。

4. 全文索引

MyISAM 存储引擎支持全文索引,用于查找文本中的关键词,而不是直接比较索引中的值。

使用 MATCH AGAINST,而不是普通的 WHERE。

索引的优点

  • 大大减少了服务器需要扫描的数据量;

  • 帮助服务器避免进行排序和创建临时表;

  • 将随机 I/O 变为顺序 I/O。

索引优化

1. 独立的列

在进行查询时,索引列不能是表达式的一部分,也不能是函数的参数,否则无法使用索引。

例如下面的查询不能使用 actor_id 列的索引:

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

2. 前缀索引

对于 BLOB、TEXT 和 VARCHAR 类型的列,必须使用前缀索引,只索引开始的部分字符。

对于前缀长度的选取需要根据 索引选择性 来确定:不重复的索引值和记录总数的比值。选择性越高,查询效率也越高。最大值为 1,此时每个记录都有唯一的索引与其对应。

3. 多列索引

在需要使用多个列作为条件进行查询时,使用多列索引比使用多个单列索引性能更好。例如下面的语句中,最好把 actor_id 和 film_id 设置为多列索引。

1
2
SELECT film_id, actor_ id FROM sakila.film_actor
WhERE actor_id = 1 AND film_id = 1;

4. 索引列的顺序

让选择性最强的索引列放在前面,例如下面显示的结果中 customer_id 的选择性比 staff_id 更高,因此最好把 customer_id 列放在多列索引的前面。

1
2
3
4
SELECT COUNT(DISTINCT staff_id)/COUNT(*) AS staff_id_selectivity,
COUNT(DISTINCT customer_id)/COUNT(*) AS customer_id_selectivity,
COUNT(*)
FROM payment;
1
2
3
   staff_id_selectivity: 0.0001
customer_id_selectivity: 0.0373
COUNT(*): 16049

5. 聚簇索引

聚簇索引并不是一种索引类型,而是一种数据存储方式。

术语“聚簇”表示数据行和相邻的键值紧密地存储在一起,InnoDB 的聚簇索引的数据行存放在 B+Tree 的叶子页中。

因为无法把数据行存放在两个不同的地方,所以一个表只能有一个聚簇索引。

优点

  1. 可以把相关数据保存在一起,减少 I/O 操作;
  2. 因为数据保存在 B+Tree 中,因此数据访问更快。

缺点

  1. 聚簇索引最大限度提高了 I/O 密集型应用的性能,但是如果数据全部放在内存,就没必要用聚簇索引。
  2. 插入速度严重依赖于插入顺序,按主键的顺序插入是最快的。
  3. 更新操作代价很高,因为每个被更新的行都会移动到新的位置。
  4. 当插入到某个已满的页中,存储引擎会将该页分裂成两个页面来容纳该行,页分裂会导致表占用更多的磁盘空间。
  5. 如果行比较稀疏,或者由于页分裂导致数据存储不连续时,聚簇索引可能导致全表扫描速度变慢。

6. 覆盖索引

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

优点

  1. 因为索引条目通常远小于数据行的大小,所以若只读取索引,能大大减少数据访问量。
  2. 一些存储引擎(例如 MyISAM)在内存中只缓存索引,而数据依赖于操作系统来缓存。因此,只访问索引可以不使用系统调用(通常比较费时)。
  3. 对于 InnoDB 引擎,若二级索引能够覆盖查询,则无需访问聚簇索引。

B-Tree 和 B+Tree 原理

1. B-Tree

为了描述 B-Tree,首先定义一条数据记录为一个二元组 [key, data],key 为记录的键,data 为数据记录除 key 外的数据。

B-Tree 是满足下列条件的数据结构:

  • 所有叶节点具有相同的深度,也就是说 B-Tree 是平衡的;
  • 一个节点中的 key 从左到右非递减排列;
  • 如果某个指针的左右相邻 key 分别是 keyi 和 keyi+1,且不为 null,则该指针指向节点的所有 key 大于 keyi 且小于 keyi+1

在 B-Tree 中按 key 检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的 data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到 null 指针,前者查找成功,后者查找失败。

由于插入删除新的数据记录会破坏 B-Tree 的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持 B-Tree 性质。

2. B+Tree

与 B-Tree 相比,B+Tree 有以下不同点:

  • 每个节点的指针上限为 2d 而不是 2d+1;
  • 内节点不存储 data,只存储 key,叶子节点不存储指针。

3. 带有顺序访问指针的 B+Tree

一般在数据库系统或文件系统中使用的 B+Tree 结构都在经典 B+Tree 基础上进行了优化,在叶子节点增加了顺序访问指针,做这个优化的目的是为了提高区间访问的性能。

4. 为什么使用 B-Tree 和 B+Tree

红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用 B-/+Tree 作为索引结构。

页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页的大小通常为 4k),主存和磁盘以页为单位交换数据。

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。为了减少磁盘 I/O,磁盘往往不是严格按需读取,而是每次都会预读。这样做的理论依据是计算机科学中著名的局部性原理:当一个数据被用到时,其附近的数据也通常会马上被使用。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次 I/O 就可以完全载入。B-Tree 中一次检索最多需要 h-1 次 I/O(根节点常驻内存),渐进复杂度为 O(h)=O(logdN)。一般实际应用中,出度 d 是非常大的数字,通常超过 100,因此 h 非常小(通常不超过 3)。而红黑树这种结构,h 明显要深的多。并且于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,效率明显比 B-Tree 差很多。

B+Tree 更适合外存索引,原因和内节点出度 d 有关。由于 B+Tree 内节点去掉了 data 域,因此可以拥有更大的出度,拥有更好的性能。

四、查询性能优化

Explain

用来分析 SQL 语句,分析结果中比较重要的字段有:

  • select_type : 查询类型,有简单查询、联合查询和子查询

  • key : 使用的索引

  • rows : 扫描的行数

减少返回的列

慢查询主要是因为访问了过多数据,除了访问过多行之外,也包括访问过多列。

最好不要使用 SELECT * 语句,要根据需要选择查询的列。

减少返回的行

最好使用 LIMIT 语句来取出想要的那些行。

还可以建立索引来减少条件语句的全表扫描。例如对于下面的语句,不使用索引的情况下需要进行全表扫描,而使用索引只需要扫描几行记录即可,使用 Explain 语句可以通过观察 rows 字段来看出这种差异。

1
SELECT * FROM sakila.film_actor WHERE film_id = 1;

拆分大的 DELETE 或 INSERT 语句

如果一次性执行的话,可能一次锁住很多数据、占满整个事务日志、耗尽系统资源、阻塞很多小的但重要的查询。

1
DELETE FROM messages WHERE create < DATE_SUB(NOW(), INTERVAL 3 MONTH);
1
2
3
4
5
rows_affected = 0
do {
rows_affected = do_query(
"DELETE FROM messages WHERE create < DATE_SUB(NOW(), INTERVAL 3 MONTH) LIMIT 10000")
} while rows_affected > 0

五、切分

随着时间和业务的发展,数据库中的表会越来越多,并且表中的数据量也会越来越大,那么读写操作的开销也会随着增大。

垂直切分

将表按功能模块、关系密切程度划分出来,部署到不同的库上。例如,我们会建立商品数据库 payDB、用户数据库 userDB 等,分别用来存储项目与商品有关的表和与用户有关的表。

水平切分

把表中的数据按照某种规则存储到多个结构相同的表中,例如按 id 的散列值、性别等进行划分。

切分的选择

如果数据库中的表太多,并且项目各项业务逻辑清晰,那么垂直切分是首选。

如果数据库的表不多,但是单表的数据量很大,应该选择水平切分。

存在的问题

1. 事务问题

在执行分库分表之后,由于数据存储到了不同的库上,数据库事务管理出现了困难。如果依赖数据库本身的分布式事务管理功能去执行事务,将付出高昂的性能代价;如果由应用程序去协助控制,形成程序逻辑上的事务,又会造成编程方面的负担。

2. 跨库跨表连接问题

在执行了分库分表之后,难以避免会将原本逻辑关联性很强的数据划分到不同的表、不同的库上。这时,表的连接操作将受到限制,我们无法连接位于不同分库的表,也无法连接分表粒度不同的表,导致原本只需要一次查询就能够完成的业务需要进行多次才能完成。

3. 额外的数据管理负担和数据运算压力

最显而易见的就是数据的定位问题和数据的增删改查的重复执行问题,这些都可以通过应用程序解决,但必然引起额外的逻辑运算。

六、故障转移和故障恢复

故障转移也叫做切换,当主库出现故障时就切换到备库,使备库成为主库。故障恢复顾名思义就是从故障中恢复过来,并且保证数据的正确性。

提升备库或切换角色

提升一台备库为主库,或者在一个主-主复制结构中调整主动和被动角色。

虚拟 IP 地址和 IP 托管

为 MySQL 实例指定一个逻辑 IP 地址,当 MySQL 实例失效时,可以将 IP 地址转移到另一台 MySQL 服务器上。

中间件解决方案

通过代理,可以路由流量到可以使用的服务器上。

在应用中处理故障转移

将故障转移整合到应用中可能导致应用变得太过笨拙。

参考资料


《数据库系统概论》【转】

原文链接: https://github.com/CyC2018/Interview-Notebook/blob/master/notes/数据库系统原理.md

一、事务

概念

事务指的是满足 ACID 特性的一系列操作。在数据库中,可以通过 Commit 提交一个事务,也可以使用 Rollback 进行回滚。

四大特性

1. 原子性(Atomicity)

事务被视为不可分割的最小单元,要么全部提交成功,要么全部失败回滚。

2. 一致性(Consistency)

事务执行前后都保持一致性状态。在一致性状态下,所有事务对一个数据的读取结果都是相同的。

3. 隔离性(Isolation)

一个事务所做的修改在最终提交以前,对其它事务是不可见的。

4. 持久性(Durability)

一旦事务提交,则其所做的修改将会永远保存到数据库中。即使系统发生崩溃,事务执行的结果也不能丢失。可以通过数据库备份和恢复来保证持久性。

二、并发一致性问题

在并发环境下,一个事务如果受到另一个事务的影响,那么事务操作就无法满足一致性条件。

问题

1. 丢失修改

T1 和 T2 两个事务都对一个数据进行修改,T1 先修改,T2 随后修改,T2 的修改覆盖了 T1 的修改。

2. 读脏数据

T1 修改一个数据,T2 随后读取这个数据。如果 T1 撤销了这次修改,那么 T2 读取的数据是脏数据。

3. 不可重复读

T2 读取一个数据,T1 对该数据做了修改。如果 T2 再次读取这个数据,此时读取的结果和和第一次读取的结果不同。

4. 幻影读

T1 读取某个范围的数据,T2 在这个范围内插入新的数据,T1 再次读取这个范围的数据,此时读取的结果和和第一次读取的结果不同。

解决方法

产生并发不一致性问题主要原因是破坏了事务的隔离性,解决方法是通过并发控制来保证隔离性。

在没有并发的情况下,事务以串行的方式执行,互不干扰,因此可以保证隔离性。在并发的情况下,如果能通过并发控制,让事务的执行结果和某一个串行执行的结果相同,就认为事务的执行结果满足隔离性要求,也就是说是正确的。把这种事务执行方式称为 可串行化调度

并发控制可以通过封锁来实现,但是封锁操作需要用户自己控制,相当复杂。数据库管理系统提供了事务的隔离级别,让用户以一种更轻松的方式处理并发一致性问题。

三、封锁

封锁粒度

应该尽量只锁定需要修改的那部分数据,而不是所有的资源。锁定的数据量越少,发生锁争用的可能就越小,系统的并发程度就越高。

但是加锁需要消耗资源,锁的各种操作,包括获取锁,检查锁是否已经解除、释放锁,都会增加系统开销。因此封锁粒度越小,系统开销就越大。需要在锁开销以及数据安全性之间做一个权衡。

MySQL 中提供了两种封锁粒度:行级锁以及表级锁。

封锁类型

1. 排它锁与共享锁

  • 排它锁(Exclusive),简写为 X 锁,又称写锁。
  • 共享锁(Shared),简写为 S 锁,又称读锁。

有以下两个规定:

  1. 一个事务对数据对象 A 加了 X 锁,就可以对 A 进行读取和更新。加锁期间其它事务不能对 A 加任何锁。
  2. 一个事务对数据对象 A 加了 S 锁,可以对 A 进行读取操作,但是不能进行更新操作。加锁期间其它事务能对 A 加 S 锁,但是不能加 X 锁。

锁的兼容关系如下:

- X S
X No No
S No Yes

2. 意向锁

意向锁(Intention Locks)可以支持多粒度封锁。它本身是一个表锁,通过在原来的 X/S 锁之上引入了 IX/IS,用来表示一个事务想要在某个数据行上加 X 锁或 S 锁。

有以下两个规定:

  1. 一个事务在获得某个数据行对象的 S 锁之前,必须先获得 IS 锁或者更强的锁;
  2. 一个事务在获得某个数据行对象的 X 锁之前,必须先获得 IX 锁。

各种锁的兼容关系如下:

- X IX S IS
X No No No No
IX No Yes No Yes
S No No Yes Yes
IS No Yes Yes Yes

封锁协议

1. 三级封锁协议

一级封锁协议

事务 T 要修改数据 A 时必须加 X 锁,直到 T 结束才释放锁。

可以解决丢失修改问题,因为不能同时有两个事务对同一个数据进行修改,那么一个事务的修改就不会被覆盖。

T1 T1
lock-x(A)
read A=20
lock-x(A)
wait
write A=19
commit
unlock-x(A)
obtain
read A=19
write A=21
commit
unlock-x(A)

二级封锁协议

在一级的基础上,要求读取数据 A 时必须加 S 锁,读取完马上释放 S 锁。

可以解决读脏数据问题,因为如果一个事务在对数据 A 进行修改,根据 1 级封锁协议,会加 X 锁,那么就不能再加 S 锁了,也就是不会读入数据。

T1 T1
lock-x(A)
read A=20
write A=19
lock-s(A)
wait
rollback
A=20
unlock-x(A)
obtain
read A=20
commit
unlock-s(A)

三级封锁协议

在二级的基础上,要求读取数据 A 时必须加 S 锁,直到事务结束了才能释放 S 锁。

可以解决不可重复读的问题,因为读 A 时,其它事务不能对 A 加 X 锁,从而避免了在读的期间数据发生改变。

T1 T1
lock-s(A)
read A=20
lock-x(A)
wait
read A=20
commit
unlock-s(A)
obtain
read A=20
write A=19
commit
unlock-X(A)

2. 两段锁协议

加锁和解锁分为两个阶段进行,事务 T 对数据 A 进行读或者写操作之前,必须先获得对 A 的封锁,并且在释放一个封锁之后,T 不能再获得任何的其它锁。

事务遵循两段锁协议是保证并发操作可串行化调度的充分条件。例如以下操作满足两段锁协议,它是可串行化调度。

1
lock-x(A)...lock-s(B)...lock-s(c)...unlock(A)...unlock(C)...unlock(B)

但不是必要条件,例如以下操作不满足两段锁协议,但是它还是可串行化调度。

1
lock-x(A)...unlock(A)...lock-s(B)...unlock(B)...lock-s(c)...unlock(C)...

四、隔离级别

1. 未提交读(READ UNCOMMITTED)

事务中的修改,即使没有提交,对其它事务也是可见的。

2. 提交读(READ COMMITTED)

一个事务只能读取已经提交的事务所做的修改。换句话说,一个事务所做的修改在提交之前对其它事务是不可见的。

3. 可重复读(REPEATABLE READ)

保证在同一个事务中多次读取同样数据的结果是一样的。

4. 可串行化(SERIALIXABLE)

强制事务串行执行。

四个隔离级别的对比

隔离级别 脏读 不可重复读 幻影读
未提交读 YES YES YES
提交读 NO YES YES
可重复读 NO NO YES
可串行化 NO NO NO

五、多版本并发控制

(Multi-Version Concurrency Control, MVCC)是 MySQL 的 InnoDB 存储引擎实现隔离级别的一种具体方式,用于实现提交读和可重复读这两种隔离级别。而未提交读隔离级别总是读取最新的数据行,无需使用 MVCC;可串行化隔离级别需要对所有读取的行都加锁,单纯使用 MVCC 无法实现。

版本号

  • 系统版本号:是一个递增的数字,每开始一个新的事务,系统版本号就会自动递增。
  • 事务版本号:事务开始时的系统版本号。

InooDB 的 MVCC 在每行记录后面都保存着两个隐藏的列,用来存储两个版本号:

  • 创建版本号:指示创建一个数据行的快照时的系统版本号;
  • 删除版本号:如果该快照的删除版本号大于当前事务版本号表示该快照有效,否则表示该快照已经被删除了。

Undo 日志

InnoDB 的 MVCC 使用到的快照存储在 Undo 日志中,该日志通过回滚指针把一个数据行(Record)的所有快照连接起来。

实现过程

以下过程针对可重复读隔离级别。

1. SELECT

该操作必须保证多个事务读取到同一个数据行的快照,这个快照是最近的一个有效快照。但是也有例外,如果有一个事务正在修改该数据行,那么它可以读取事务本身所做的修改,而不用和其它事务的读取结果一致。

当开始新一个事务时,该事务的版本号肯定会大于当前所有数据行快照的创建版本号,理解这一点很关键。

把没对一个数据行做修改的事务称为 T,T 所要读取的数据行快照的创建版本号必须小于 T 的版本号,因为如果大于或者等于 T 的版本号,那么表示该数据行快照是其它事务的最新修改,因此不能去读取它。

除了上面的要求,T 所要读取的数据行快照的删除版本号必须大于 T 的版本号,因为如果小于等于 T 的版本号,那么表示该数据行快照是已经被删除的,不应该去读取它。

2. INSERT

将系统版本号作为数据行快照的创建版本号。

3. DELETE

将系统版本号作为数据行快照的删除版本号。

4. UPDATE

将系统版本号作为更新后的数据行快照的创建版本号,同时将系统版本号作为更新前的数据行快照的删除版本号。可以理解为先执行 DELETE 后执行 INSERT。

快照读与当前读

1. 快照读

读取快照中的数据。

引入快照读的目的主要是为了免去加锁操作带来的性能开销,但是当前读需要加锁。

1
select * from table ....;

2. 当前读

读取最新的数据。

需要加锁,以下第一个语句加 S 锁,其它都加 X 锁。

1
2
3
4
5
select * from table where ? lock in share mode;
select * from table where ? for update;
insert;
update ;
delete;

六、Next-Key Locks

Next-Key Locks 也是 MySQL 的 InnoDB 存储引擎的一种锁实现。MVCC 不能解决幻读的问题,Next-Key Locks 就是为了解决这个问题而存在的。在可重复读隔离级别下,MVCC + Next-Key Locks,就可以防止幻读的出现。

Record Locks

锁定的对象是索引,而不是数据。如果表没有设置索引,InnoDB 会自动在主键上创建隐藏的聚集索引,因此 Record Locks 依然可以使用。

Grap Locks

锁定一个范围内的索引,例如当一个事务执行以下语句,其它事务就不能在 t.c 中插入 15。

1
SELECT c FROM t WHERE c BETWEEN 10 and 20 FOR UPDATE;

Next-Key Locks

它是 Record Locks 和 Gap Locks 的结合。在 user 中有以下记录:

1
2
3
4
5
6
7
8
|   id | last_name   | first_name   |   age |
|------|-------------|--------------|-------|
| 4 | stark | tony | 21 |
| 1 | tom | hiddleston | 30 |
| 3 | morgan | freeman | 40 |
| 5 | jeff | dean | 50 |
| 2 | donald | trump | 80 |
+------|-------------|--------------|-------+

那么就需要锁定以下范围:

1
2
3
4
5
6
(-∞, 21]
(21, 30]
(30, 40]
(40, 50]
(50, 80]
(80, ∞)

七、关系数据库设计理论

函数依赖

记 A->B 表示 A 函数决定 B,也可以说 B 函数依赖于 A。

如果 {A1,A2,… ,An} 是关系的一个或多个属性的集合,该集合决定了关系的其它所有属性并且是最小的,那么该集合就称为键码。

对于 W->A,如果能找到 W 的真子集 W’,使得 W’-> A,那么 W->A 就是部分函数依赖,否则就是完全函数依赖;

异常

以下的学生课程关系的函数依赖为 Sno, Cname -> Sname, Sdept, Mname, Grade,键码为 {Sno, Cname}。也就是说,确定学生和课程之后,就能确定其它信息。

Sno Sname Sdept Mname Cname Grade
1 学生-1 学院-1 院长-1 课程-1 90
2 学生-2 学院-2 院长-2 课程-2 80
2 学生-2 学院-2 院长-2 课程-1 100

不符合范式的关系,会产生很多异常,主要有以下四种异常:

  1. 冗余数据,例如学生-2 出现了两次。
  2. 修改异常,修改了一个记录中的信息,但是另一个记录中相同的信息却没有被修改。
  3. 删除异常,删除一个信息,那么也会丢失其它信息。例如如果删除了课程-1,需要删除第一行和第三行,那么学生-1 的信息就会丢失。
  4. 插入异常,例如想要插入一个学生的信息,如果这个学生还没选课,那么就无法插入。

范式

范式理论是为了解决以上提到四种异常。高级别范式的依赖于低级别的范式。

1. 第一范式 (1NF)

属性不可分;

2. 第二范式 (2NF)

每个非主属性完全函数依赖于键码。

可以通过分解来满足。

分解前

Sno Sname Sdept Mname Cname Grade
1 学生-1 学院-1 院长-1 课程-1 90
2 学生-2 学院-2 院长-2 课程-2 80
2 学生-2 学院-2 院长-2 课程-1 100

以上学生课程关系中,{Sno, Cname} 为键码,有如下函数依赖:

  • Sno, Cname -> Sname, Sdept, Mname
  • Son -> Sname, Sdept
  • Sdept -> Mname
  • Sno -> Manme
  • Sno, Cname-> Grade

Grade 完全函数依赖于键码,它没有任何冗余数据,每个学生的每门课都有特定的成绩。

Sname, Sdept 和 Manme 都函数依赖于 Sno,而部分依赖于键码。当一个学生选修了多门课时,这些数据就会出现多次,造成大量冗余数据。

分解后

关系-1

Sno Sname Sdept Mname
1 学生-1 学院-1 院长-1
2 学生-2 学院-2 院长-2

有以下函数依赖:

  • Sno -> Sname, Sdept, Mname
  • Sdept -> Mname

关系-2

Sno Cname Grade
1 课程-1 90
2 课程-2 80
2 课程-1 100

有以下函数依赖:

  • Sno, Cname -> Grade

3. 第三范式 (3NF)

非主属性不传递依赖于键码。

上面的关系-1 中存在以下传递依赖:Sno -> Sdept -> Mname,可以进行以下分解:

关系-11

Sno Sname Sdept
1 学生-1 学院-1
2 学生-2 学院-2

关系-12

Sdept Mname
学院-1 院长-1
学院-2 院长-2

4. BC 范式(BCNF)

所有属性不传递依赖于键码。

关系 STC(Sname, Tname, Cname, Grade) 的四个属性分别为学生姓名、教师姓名、课程名和成绩,它的键码为 (Sname, Cname, Tname),有以下函数依赖:

  • Sname, Cname -> Tname
  • Sname, Cname -> Grade
  • Sname, Tname -> Cname
  • Sname, Tname -> Grade
  • Tname -> Cname

存在着以下函数传递依赖:

  • Sname -> Tname -> Cname

可以分解成 SC(Sname, Cname, Grade) 和 ST(Sname, Tname),对于 ST,属性之间是多对多关系,无函数依赖。

八、数据库系统概述

基本术语

1. 数据模型

由数据结构、数据操作和完整性三个要素组成。

2. 数据库系统

数据库系统包含所有与数据库相关的内容,包括数据库、数据库管理系统、应用程序以及数据库管理员和用户,还包括相关的硬件和软件。

数据库的三层模式和两层映像

  • 外模式:局部逻辑结构
  • 模式:全局逻辑结构
  • 内模式:物理结构

1. 外模式

又称用户模式,是用户和数据库系统的接口,特定的用户只能访问数据库系统提供给他的外模式中的数据。例如不同的用户创建了不同数据库,那么一个用户只能访问他有权限访问的数据库。

一个数据库可以有多个外模式,一个用户只能有一个外模式,但是一个外模式可以给多个用户使用。

2. 模式

可以分为概念模式和逻辑模式,概念模式可以用概念-关系来描述;逻辑模式使用特定的数据模式(比如关系模型)来描述数据的逻辑结构,这种逻辑结构包括数据的组成、数据项的名称、类型、取值范围。不仅如此,逻辑模式还要描述数据之间的关系、数据的完整性与安全性要求。

3. 内模式

又称为存储模式,描述记录的存储方式,例如索引的组织方式、数据是否压缩以及是否加密等等。

4. 外模式/模式映像

把外模式的局部逻辑结构和模式的全局逻辑结构联系起来。该映像可以保证数据和应用程序的逻辑独立性。

5. 模式/内模式映像

把模式的全局逻辑结构和内模式的物理结构联系起来,该映像可以保证数据和应用程序的物理独立性。

九、关系数据库建模

ER 图

Entity-Relationship,有三个组成部分:实体、属性、联系。

1. 实体的三种联系

联系包含一对一,一对多,多对多三种。

如果 A 到 B 是一对多关系,那么画个带箭头的线段指向 B;如果是一对一,画两个带箭头的线段;如果是多对多,画两个不带箭头的线段。下图的 Course 和 Student 是一对多的关系。

2. 表示出现多次的关系

一个实体在联系出现几次,就要用几条线连接。下图表示一个课程的先修关系,先修关系出现两个 Course 实体,第一个是先修课程,后一个是后修课程,因此需要用两条线来表示这种关系。

3. 联系的多向性

虽然老师可以开设多门课,并且可以教授多名学生,但是对于特定的学生和课程,只有一个老师教授,这就构成了一个三元联系。

一般只使用二元联系,可以把多元关系转换为二元关系。

4. 表示子类

用一个三角形和两条线来连接类和子类,与子类有关的属性和联系都连到子类上,而与父类和子类都有关的连到父类上。

十、约束

1. 键码

用于唯一表示一个实体。

键码可以由多个属性构成,每个构成键码的属性称为码。

2. 单值约束

某个属性的值是唯一的。

3. 引用完整性约束

一个实体的属性引用的值在另一个实体的某个属性中存在。

4. 域约束

某个属性的值在特定范围之内。

5. 一般约束

比如大小约束,数量约束。

参考资料


博客迁移到Hexo

上午把一些很占资源的大图给删掉了,研究了一下现在 Github Pages 博客的最新进展,发现很多人都开始用基于 Node.js 的 Hexo 了。功能比较丰富,而且配置简单,主题也多,所以就把博客从 Jekyll 迁移过来了。

本地写博客的话,还是起一个服务就够了。

1
2
hexo new "create-new-post"
hexo server

只不过发布比较麻烦,下面的命令生成静态文件后会自动push到Github的master分支,挺暴力的。

1
hexo clean && hexo generate && hexo deploy

所以现在写作的源代码就放在 hexo 分支下了,master分支是生成后的文件。一定要注意!这样的话,在克隆代码时需要加点料:

1
git clone --recurse-submodules -j2 -b hexo git@github.com:kingfree/kingfree.github.io.git

老的代码提交记录也在这个分支,因为master已经被暴力清空了TAT

接下来还要解决一下竖排模板的问题。


Git如何永久删除文件(包括历史记录)【转】

原文链接:http://www.cnblogs.com/shines77/p/3460274.html

有些时候不小心上传了一些敏感文件(例如密码), 或者不想上传的文件(没及时或忘了加到.gitignore里的),

而且上传的文件又特别大的时候, 这将导致别人clone你的代码或下载zip包的时候也必须更新或下载这些无用的文件,

因此, 我们需要一个方法, 永久的删除这些文件(包括该文件的历史记录).

首先, 可以参考 github 的帮助:https://help.github.com/articles/remove-sensitive-data

步骤一: 从你的资料库中清除文件

以Windows下为例(Linux类似), 打开项目的Git Bash,使用命令:

1
$ git filter-branch --force --index-filter 'git rm --cached --ignore-unmatch <path-to-your-remove-file>' --prune-empty --tag-name-filter cat -- --all

其中, <path-to-your-remove-file> 就是你要删除的文件的相对路径(相对于git仓库的跟目录), 替换成你要删除的文件即可. 注意一点,这里的文件或文件夹,都不能以 ‘/‘ 开头,否则文件或文件夹会被认为是从 git 的安装目录开始。

如果你要删除的目标不是文件,而是文件夹,那么请在 git rm --cached 命令后面添加 -r 命令,表示递归的删除(子)文件夹和文件夹下的文件,类似于 rm -rf 命令。

此外,如果你要删除的文件很多, 可以写进一个.sh文件批量执行, 如果文件或路径里有中文, 由于MinGW或CygWin对中文路径设置比较麻烦, 你可以使用通配符号, 例如: sound/music_.mp3, 这样就把sound目录下以music_开头的mp3文件都删除了.

例如这样, 新建一个 bash 脚本文件,del-music-mp3.sh:

1
2
3
4
#!/bin/bash

git filter-branch --force --index-filter 'git rm --cached --ignore-unmatch projects/Moon.mp3' --prune-empty --tag-name-filter cat -- --all
git filter-branch --force --index-filter 'git rm --cached --ignore-unmatch sound/Music_*.mp3' --prune-empty --tag-name-filter cat -- --all

如果你看到类似下面这样的, 就说明删除成功了:

1
2
Rewrite 48dc599c80e20527ed902928085e7861e6b3cbe6 (266/266)
# Ref 'refs/heads/master' was rewritten

如果显示 xxxxx unchanged, 说明repo里没有找到该文件, 请检查路径和文件名是否正确.

注意: 补充一点, 如果你想以后也不会再上传这个文件或文件夹, 请把这个文件或文件夹添加到.gitignore文件里, 然后再push你的repo.

步骤二: 推送我们修改后的repo

以强制覆盖的方式推送你的repo, 命令如下:

1
$ git push origin master --force

这个过程其实是重新上传我们的repo, 比较耗时, 虽然跟删掉重新建一个repo有些类似, 但是好处是保留了原有的更新记录, 所以还是有些不同的. 如果你实在不在意这些更新记录, 也可以删掉重建, 两者也差不太多, 也许后者还更直观些.

执行结果类似下面:

1
2
3
4
5
6
7
Counting objects: 4669, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (4352/4352), done.
Writing objects: 100% (4666/4666), 35.16 MiB | 51 KiB/s, done.
Total 4666 (delta 1361), reused 0 (delta 0)
To https://github.com/defunkt/github-gem.git
+ beb839d...81f21f3 master -> master (forced update)

为了能从打了 tag 的版本中也删除你所指定的文件或文件夹,您可以使用这样的命令来强制推送您的 Git tags:

1
$ git push origin master --force --tags

步骤三: 清理和回收空间

虽然上面我们已经删除了文件, 但是我们的repo里面仍然保留了这些objects, 等待垃圾回收(GC), 所以我们要用命令彻底清除它, 并收回空间.

命令如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
$ rm -rf .git/refs/original/

$ git reflog expire --expire=now --all

$ git gc --prune=now

Counting objects: 2437, done.
# Delta compression using up to 4 threads.
# Compressing objects: 100% (1378/1378), done.
# Writing objects: 100% (2437/2437), done.
# Total 2437 (delta 1461), reused 1802 (delta 1048)

$ git gc --aggressive --prune=now

Counting objects: 2437, done.
# Delta compression using up to 4 threads.
# Compressing objects: 100% (2426/2426), done.
# Writing objects: 100% (2437/2437), done.
# Total 2437 (delta 1483), reused 0 (delta 0)

现在你再看看你的.git目录文件大小是不是变小了.

参考自:


日行小詩

原文载简书:https://www.jianshu.com/p/51e40a1bb9e2

記戊戌年二月北海道遊

伊達驛前路漫漫,長途左涉國道邊。

山清水遠車行稀,峰迴路轉洞爺前。

湖邊景色卻看好,又轉山間雪忽霾。

雪上雪下雪紛飛,路平路曲路綿延。

迷茫霧里尋彩雲,千里迢迢水潺潺。

不上山頂不覓爽,下山搖杏案火山。

我本是為麻將來,奈何竟然見圓盤!

風復靜,雪云開,湖若明鏡顯蓮台。

小學校,白石苔,松柏不動人愈還。

北去不上有珠山,南來未下鹿兒島。

何以東西都飄雪,是唯冬去春又來!


戊戌正月初八

原文载简书:https://www.jianshu.com/p/805c44d8d3ed

戊戌新年自安回滬,已無旅日之前放浪之心。無大興致于動畫,無大趣味于展會,唯心所欲,無不在于讀書、學問。然而學之不及,有耐久之心,無耐久之力。熄燈就寢,輾轉思緒,願有志矣。

思量錢財,故及房產。查閱戶籍制度之繁雜,感歎限購政策之艱難。所思而得最易者,竟是大學。京滬之難,知矣;鄭安之敗,顯矣;川渝之興,得矣。且尋重慶大學之門戶,遂知有博雅學院一說,又為中山大學所立。鏈其所見,無不與我思維同衷,感情相和。驚然歎曰:“吾當學于此!”

噫!高考之難,我已經矣;就業之難,我已悼矣。今放浪形骸于中日城鄉,三年而知孰輕孰重。人之不為學則廢矣,此世何容我哉!唯今所想追求經世之道,非中國之大學不能成,故棄留學之計劃,立高考之微願。是其難矣,錢多發自當以節流理蓄,體多弱自當以鍛煉健康,學多病自當以激勵勉強。自是以後兩年,以此三者張之,其可成也讚于天,其不可成也往繼續之,終可成矣。 今為此文,以彰我誰。

二〇一八年二月二十三日戊戌年正月初八


2017年终总结

2017年换了两次工作,前半年在新郑远程办公,绕着成都-重庆-武汉-广州-上海-南京-北京,天南海北玩了一遍。7月底在广州看麽多,LIVE结束后一个电话过来,立马买机票会郑,决定离职,在本地找到下家,随后又辗转来到上海面试,遂移居至此至今。来沪后,几乎每周都有ACG相关活动,也几乎是每场必去。一年下来,参加的活动有去年两倍不止,可谓是真正的Eventer了。然而,物极必反,在数场喧闹的演唱会之间,我的心态却在年末的这段时间逐渐变化了,开始反思这样过度的娱乐。得益于上海图书馆建设的完善,我开始读书、开始寻求知识了。在不断的阅读中,我越发感到我的志向所在,而且越发理解自己的不成熟和对教育的强烈需求。那么,既然志不在此,就不必再花太多时间和精力放在没兴趣的事情上了,这也是我列定明年计划的基本准则。

从2010年9月到2017年8月,我在郑州整整待了七年:三年难以忘怀却又悔之不及的高中;两年切磋琢磨却是抱怨离开的大学;两年得意风生终于得偿玩心的工作。未来的两年,将会决定重读本科的目标以及终生研究的方向。我虽然年轻,但对于学习已经老了;我虽然老了,但对于学识还太年轻!

对于今年,我定一汉字为“沪”,这是在上海的开始。明年,务必治于学!

人生三大樂事,讀書美食LIVE三者爾。子在齊聞韶,三月不知肉味,曰:「不圖爲樂之至於斯也!」我其嚮哉!

  1. 1月23日。郑州。
    • 年会。
  2. 1月25日~2月2日。安阳。
    • 过年。
  3. 2月。郑州。
    • 离职。转职。
  4. 3月。新郑。
    • 租新郑港区房。
  5. 3月4日~9日。成都。
    • CD19。
    • 都江堰。
  6. 3月9日~11日。重庆。
  7. 3月11日。武汉。
  8. 3月18日~19日。广州。
    • 福原绫香 见面会。
  9. 4月。郑州。
    • 搬家。退市区租房。
  10. 4月7日~9日。安阳。
  11. 4月29日~5月3日。上海。
  12. 7月8日。武汉。
  13. 7月9日~10日。上海。
    • CCG2017。花木路。
    • 《动画同好会》见面会。本渡枫千本木彩花 等。
  14. 7月11日~12日。南京。
    • 中山陵。孝陵。
  15. 7月14日~19日。北京。
    • Saki 萌战群聚会。日麻。
    • 八达岭。故宫。
  16. 7月19日~20日。安阳。
  17. 7月28日~30日。广州。
    • 石原夏织 见面会。
    • 田所梓 见面会。
    • 麽多动漫嘉年华。广体。中岛爱大桥彩香 等。
  18. 7月31日~8月10日。郑州。
    • 回郑。居郑。赴沪。
  19. 8月11日~15日。自此移居上海,下不单列。
    • 面试、租房、就职。
  20. 8月27日。
    • CP20.5。漕宝路。
  21. 9月1日~3日。新郑。
    • 搬家。退新郑港区租房。
  22. 9月9日。
    • 《刀剑神域》。伊藤加奈惠 等。虹桥艺术中心。
  23. 9月17日。
    • 《刀剑神域》 S1 观影会。SFC上影喜马拉雅。
  24. 9月23日。
    • 偶像大师 only。灵石路。
    • 《URAHARA》等观影会。世博源。
    • 水岛精二
  25. 10月1日。
    • Y3。上海展览中心。
    • 萤火虫。花木路。
    • 天真·珈百璃·怀特
  26. 10月2日~4日。广州。
    • CICF Day2。大空直美 见面会。
    • CICF Day3。安济知佳 见面会。
    • 虹野梦
  27. 10月8日。23岁生日。
    • 纯k。天山路。
  28. 10月14日。
    • 铃木木乃美 亚洲巡演。浅水湾。
  29. 11月18日。
    • 《Wake Up, Girls!》演唱会。浅水湾。田中美海 等。
  30. 11月19日。
    • ANIMERCI 动漫音乐节。
  31. 11月25日。
    • 初音未来 演唱会。花木路。
  32. 12月2日。
    • GARNiDELiA 亚洲巡演。浅水湾。
  33. 12月3日。
    • N1。上海大学。
  34. 12月8日/9日。
    • 《偶像大师灰姑娘》5th 观影会。浅水湾。
    • 黑泽知叶佳村遥福原绫香高森奈津美 见面会。
  35. 12月9日。
    • 田所梓 演唱会。浅水湾。
  36. 12月24日。
    • 歌魂。伊犁路。
  37. 12月31日。
    • DAM-K 跨年活动。

明年计划

  1. 深扎Web开发,技术方面心无旁骛。
  2. 完成日本旅行,考察和研究留日计划。
  3. 学习英语,通过托福。
  4. 复习国内文科高考内容。
  5. 学习日本留学生考试内容。
  6. 读完《绎史》《资治通鉴》《续通鉴》,略读明清民国现代史。
  7. 每周略读一本社会科学类的经典书籍。
  8. 尽可能地参加上海本地的见面会和LIVE。
  9. 锻炼身体,保证脑力。

《經學歷史》

《序言》周予同

  1. 經學的三大派:
    1. 西漢今文學:以孔子為政治家,微言大義,功利、狂妄
    2. 東漢古文學:以孔子為史學家,名物訓詁,考證、繁瑣
    3. 宋學/理學:以孔子為哲學家,文以載道,玄想、空疏
  2. 經學史的重要性和分類:經學已死,經學史方生
  3. 皮錫瑞今文,章太炎古文
  4. 本書有價值但不可全信:
    1. “孔教救國”
    2. “六經致用”
    3. “緯候足徵”

一、經學開闢時代

孔子刪定(古文)/創作(今文)六經:《詩》《書》《禮》《樂》《易》《春秋》。

二、經學流傳時代

秦漢之際。

三、經學昌明時代

漢武經學最為純正。

四、經學極盛時代

光武中興。白虎通義、五經異義。漢隸體石經。鄭玄注百萬。

五、經學中衰時代

鄭玄注集今古文,魏晉時人不復專門之學。

六、經學分立時代

南北朝時,南學浮華、北學質樸。

七、經學統一時代

隋北學併入南學,唐孔穎達勘定五經正義。

大經《禮記》《左傳》,中經《毛詩》《周禮》《公羊》,小經《周易》《尚書》《儀禮》《穀梁》。

八、經學變古時代

宋慶曆始一大變,反古文尚書,反毛詩,反左傳,宋人托古言今、繕發義理,疑經刪經自成其說。

九、經學積衰時代

墨義取義不取經。程子、朱子開宋學。

十、經學復盛時代

明末顧炎武謂八股之害,是為訓詁之學。清人輯佚書、精校勘、通小學。

【國學】

梁啟超、章太炎、陳寅恪、錢穆。


《為學十六法》

一、讀書的方法

由面及點,由淺入深。

先精讀,后略讀。(把書讀厚,把書讀薄,再把書讀厚)

二、青年何以報國

先讀科學書,再讀古書。

三、整理舊籍

經史子集。

入手當從目錄學始:清《四庫書目》、張之洞《書目答問》。

四、讀經之法

經子價值相同,但經之註疏多,故先經后子。

治經當從漢人之書入,當分清今古文家數。

入門書目:皮錫瑞《經學歷史》、廖平《今古文考》、康有為《新學偽經考》、《禮記·王制註疏》、《周禮註疏》、陳立《白虎通疏證》、陳壽祺《五經異義疏證》。日讀一小時,速則三月,至遲半年。

經傳皆可信。

五、呂思勉學習歷史的歷程

少時得益于父母師友。14歲讀《通鑒》《續通鑒》《明記》,15歲讀《史記》、後四史、23歲讀完正史,匆匆讀過。

社會科學是史學的根基。

六、讀中國歷史

章太炎:“史書文義平易,兩三點鐘之功,足閱兩卷有餘,一部二十四史,三千二百三十九卷,日讀兩卷,一日不脫,四年可了,有志之士,正須以此自勉。”

三大門檻:1.昔人所重者亦重之,2.今日研究不能以昔人重者為限,當補昔人所未備,3.初步門徑仍不可不略事探討。

讀史三法:

  1. 正史暫可緩讀。《資治通鑒》、《續資治通鑒》、《明記》/《明通鑒》、《清通考》,《通志·二十略》,顧祖禹《讀史方輿紀要》,前四史,南北史和新舊史第一遍只讀一組。
  2. 古史、四裔必藉他部或近來之書補正。宋羅泌《路史》、劉恕《通鑒外紀》、馬骕《繹史》。外國史另從大家。
  3. 讀史方法,亦參考今人著述。劉知幾《史通》、章學誠《文史通義》。顧炎武《日知錄》、趙甌北《廿二史札記》。(馬克思歷史唯物主義史觀、全球史觀、文明史觀等亦要學習)

七、乙部舉要

  1. 正史:
    1. 治亂興亡:
      1. 編年史:司馬光《通鑒》。朱熹《綱目》。
      2. 紀事本末:《通鑒~》《左傳~》《左傳事緯》《宋史~》《元史~》《明史~》《西夏~》
    2. 典章制度:
      1. 三通:唐《通典》宋《通志》元《通考》
      2. 會要
      3. 會典
      4. 禮儀
      5. 律禮
  2. 別史
  3. 外國史

讀史:《通鑒》《續通鑒》《明通鑒》《通志·二十略》《通考(有用之門)》《繹史》《讀史方略紀要》,日讀三時,三年可畢。

八、讀舊史法

門徑:《資治通鑒》《文獻通考》

初讀求速不求甚解。

九、治古史

治經子:讀經本文,略知訓詁。知漢宋之別。

疑古、證古。

十、作史

搜集、考訂、編纂。

十一、史學研究五法

常識:社會學、考古學、地理學、文學。

觀念:史事是進化的,不是循環的;馬克思;西洋科學;知崇古之利弊和由來。

研究出社會的法則是史學的最大任務。

史學研究五法:

  1. 史家宗旨古今不同:古人偏重政治、英雄、軍事,用以獎勵道德、激勵愛國、傳播神教、偏重生計、偏重文學。皆史家之弊。當重平常人、平常事。
  2. 史材:史籍、家語、金石、文集、傳述;人體、古物、圖畫、政俗。
  3. 搜集:本不以為史材者,向以為史材而不知關係者。
  4. 考證:設身處地,注意時空,絕對證據,小事見大,作者境況,進退大勢,科學定律,取易摒難,不取別有用心之語。
  5. 論史:因果關係。古人論事粗,今人論事精。

十二、讀子之法

讀子順序:《老子》《莊子》《管子》《韓子》《墨子》《荀子》《呂氏春秋》《淮南子》

求其大義,隨時札記,嚴別真偽。

十二、先秦諸子

可分家而不可分人。

十三、學習國文

文學:古文(先秦)、駢文(漢至南北朝)、散文(唐以後)。

中學治國文:一二年閱集類(大小蘇、老蘇、歐公、南豐、半山、柳州、昌黎),三年史類,四年經子。

十四、中學國文教學

十五、大學國文教學

附录

  1. 国学大师网