chapter 42 崩溃一致性​

以一个传统的结构(linux ext2)为例子

一个磁盘group

inode bitmap | data bitmap | inode block | data block

磁盘映像

super | group0 | group1 | …

想要给一个文件追加一个block，需要改inode block, data bitmap 和 data block 3处

设想中途断电，硬件原子性在磁盘上是不好做的，所以可能在三个写入之中发生任意个写入落盘的情况

断电时已经修改的数据和后果的对应:

• inode block， 元数据不一致，指向垃圾数据
• data bitmap，元数据不一致，空间泄露
• data block， 没关系
• inode block + data bitmap， 文件是乱码，问题不大
• inode block + data block，元数据不一致
• data bitmap + data block， 元数据不一致，空间泄露

早期文件系统：fsck，让不一致发生，重启时修复，只确保元数据一致

• 检查super block（发现系统大小小于分配块数等不健全的情况，可以考虑启用super block的备用副本来防止super block自身损坏）
• 空闲块：inode, 间接块，以inode为参考， 修改inode bitmap达到一致, 所有看起来在用的inode都会有bitmap标记
• inode状态：如果inode的字段不合法，认为不易修复，删掉这个inode
• inode链接：扫描整个目录树，重新计算引用计数，如果找到已经分配的inode但没有目录引用，放到lost+found
• 重复和坏块，清除不正确的指针
• 目录检查：确保无环，目录中每个inode已分配等

磁盘清理工具：重排inode的data block来减少碎片

fsck 存在的一个问题：很复杂

fsck 最关键的问题：太慢了！

另外的方法：WAL

Linux ext34, Windows NTFS 采用的方法: 加上journal block

super | **journal** | group0 | group1 | …

journal中条目的形式：

TxB | inode | bitmap | data | TxE (物理日志，也有逻辑日志的做法，可能提高性能，节省空间)

checkpoint： 成功写入journal之后，就是一个checkpoint

先写WAL, 再写文件系统元数据，最后落盘data

问题：写日志的时候崩溃？

问题发生在，一条日志（以物理为例）可能太大，以至于不能被原子写入（常态）

• 日志内的数据可以被磁盘调度为小块乱序写入
• 写入的部分错误难以检查，例如在写入data段的时候出错，但其他部分正确（但也可以checksum? 这就是ext4的一项重要更新，通过在TxB和TxE之中包含checksum来加快写入速度）
• 磁盘的写缓冲，早期OS强制写入顺序就是通过关中断实现的: 写A，关中断，写B；有缓冲的状态下，写入缓冲就会返回。还要保证顺序的话，一种是禁用写缓冲，更现代的方法是写屏障（有趣的是一些磁盘产商忽略了写屏障，即使存在错误的风险，“快速几乎总是打败慢速，即使快速是错的”）
• 所以早期的方案是这样的，先写除了TxE之外的所有块，这部分出错这个事务就是未提交的，会被重置；然后第二步再写TxE, 磁盘保证写512字节的block的原子性，因而TxE是原子的。流程称为日志写入，日志提交，加检查点

此时，恢复仅仅是重放（replay）

批处理：

和TLB缓存很像，fs可以为了性能将磁盘写入合并批处理，在内存之中标记dirty

日志长度有限：循环，checkpoint之后前面的日志可以释放掉再重新写入

物理日志严重的写放大：元数据日志（linux ext3的另一个mode, windows NTFS），WAL之中不保存data段，只保存inode, inode bitmap，block bitmap等元数据修改。此时需要先写data, 来避免指向垃圾数据

• 这样的“强制先写入被指向的对象，再写入指针”是崩溃一致性的核心

棘手的问题：块复用，感觉有点绕，总之是删除+文件夹这种递归结构+只记录元数据+重用得到了一些不好的结果，linux ext3的解决方法是删除也有revoke日志

其他崩溃一致性的解法：

• COW
• 反向指针，在被引用块里面添加引用块的引用（惰性崩溃一致性）
• 软更新，排序所有写入，复杂
• 乐观崩溃一致，例如校验和的方案

ZFS使用COW和日志

chapter43 LFS 日志文件系统​

很像LSM，同样是为了利用磁盘的顺序写，同时只做顺序写，读时读最新版本，GC回收旧版本数据

LFS将每次文件系统的更新都顺序写入（data, inode），并以写缓冲实现批量写的性能提高，带来一个问题是不知道inode在哪里了

因而引入了一个中间层imap，记录inode, addr的对，imap需要保证持久，每次写入inode时,imap进行更新

imap放在哪里？如果在固定段，由于它更新的频繁性，所以需要非常多的磁盘寻道，不可接受

所以把imap和inode一起，写到更新后面

那去哪里找imap呢？（有点像 一级一级的索引，现在要找索引入口）

在磁盘的固定处维护检查点区域CR, CR指向最新imap，而CR的性能可以通过降低更新频率，例如每30s定时更新来解决，inode的更新全放到imap了

imap还解决了递归更新的问题

读取的时候有内存缓存，直接读里面的imap就行

怎么做GC? 在data block的开头有对inode块的反向引用+自身在inode中偏移量T，称为segment summary block

所以data → segment → 查最新的imap得到inode addr → inode[T] == data ? alive : dead

更简单的空间换时间的方法，在imap里面记录版本号，在segment里面也记录版本号

清理哪些段？一种粗略的方法是冷热分离

经常覆盖内容的段是热段，尽可能保留；反之冷段可以早清

崩溃恢复

• 写CR崩溃：1. 给cr做一个副本 2.更新cr时，通过 时间戳 + CR + 时间戳的方式，检测更新的一致性，时间戳是原子的
• 其他崩溃：CR后的数据丢了，假设CR是30s, 那不超过30s, 当然可以在CR里面包含更多信息，从而在最后一个检查点之后，尽量找到日志的结尾，并尽可能恢复有效的段，称为前滚 roll forward

LFS的思想在ZFS, Linux btrfs等有所体现，通过快照来得到fs的版本化

chapter 44 检测错误​

磁盘错误：“有声的” 和“无声的”

• 前者例如意外的不可读，数据位反转，可以被ECC修复或检错的，总之会被磁盘发现
• 后者如写歪了

前者的解决方法是各种方式的RAID

后者的解决方法是校验和，xor, add, fletcher, crc

像“写歪了”（addr x写到y， 磁盘A写到B）这种如何检测？在校验和之中加入块的磁盘和扇区号这样的物理标识符

还有一个特殊的情况是写入丢失，解决方法有写入后检验，或者在inode上加校验和（这样inode + data block全写丢了才会发现不了）

何时检测：定时，磁盘的位是会衰退的

限流器​

• 放在哪里?

  • 客户端, 容易被伪造绕过
  • 服务端应用代码, 灵活性高, 但占据工程资源
  • 云上微服务, api网关等, 灵活性低

• 经典算法:

  • 令牌桶: 固定速率产生令牌, 每个请求消耗令牌

    • pros: 容易实现, 内存占用少, 允许突发流量
    • cons: 调参困难, 可能需要不断填充桶

  • 漏桶: 请求进入一个定长FIFO队列, server给定速度从队列取数据处理

    • pros: 容易实现, 内存占用少, 请求以固定速率处理
    • cons: 突发请求占据队列使得新请求得不到处理, 调参困难,可能需要不断填充桶

  • 固定窗口计数器: 每一个给定时间窗口进行计数,例如每分钟100个请求

    • pros: 容易实现, 内存占用少
    • cons: 突发请求可以达到两倍限制的QPS(在窗口边缘有突刺)

  • 滑动窗口日志: 记录请求时间戳, 数据保存在redis等缓存,每当新请求进来的时候把过时时间戳删除, 如果请求时间戳比时间窗口的最低值还低, 拒绝请求

    • pros: 速率限制准确
    • cons: 内存开销大, 需要存储多个时间戳

  • 滑动窗口计数器: 某时刻限制请求数 = 窗口上限 - 上一个窗口请求数 * 这一个窗口的和上一个窗口的重叠百分比。例如, 窗口为每分钟1000, 上一分钟800, 在这一分钟的30秒时, 限制这一分钟窗口的请求数最多为 1000 - 30 / 60 * 800 = 600

    • 相当于假设上一个窗口的平均速率

    • pros: 平滑了流量峰值, 内存高效(只需要计数)

    • cons: 不太严格, 然而其实可以

      然而，这个问题可能并不像它看起来那么糟糕。 根据Cloudflare[10]所做的实验，在4亿个请求中，只有0.003%的请求被错误地允许或限制速率

超过速率限制

如果一个请求被限制了速率，API会向客户端返回一个HTTP响应代码429（请求太多）。根据不同的使用情况，我们可能会将速率受限的请求排队等候以后处理。 例如，如果一些订单由于系统过载而受到速率限制，我们可以保留这些订单以便以后处理。

限流器请求头

一个客户如何知道它是否被节流？客户端如何知道在被节流之前允许的剩余请求的数量？答案就在HTTP响应头中。限流器向客户端返回以下 HTTP 标头：

• X-Ratelimit-Remaining：窗口内允许请求的剩余数量
• X-Ratelimit-limit：它表示客户端在每个时间窗口可以进行多少次调用
• X-Ratelimit-Retry-After：等待的秒数，直到你可以再次提出请求而不被节流。

当用户发送过多请求时，将向客户端返回 429 too many requests 错误和 X-Ratelimit-Retry-After 标头。

• 规则被存储在磁盘上。工作者经常从磁盘中提取规则，并将其存储在高速缓存中。
• 当客户端向服务器发送请求时，该请求首先被发送到限流中间件。
• 限流中间件从缓存中加载规则。它从Redis缓存中获取计数器和最后一次请求的时间戳。根据响应，限流器决定：
  • 如果请求没有速率限制，它将被转发到API服务器。
  • 如果请求受到速率限制，限流器会向客户端返回 429 too many requests 错误。 同时，请求被丢弃或转发到队列。

分布式限流

redis:

• lua脚本
• sorted set每个用户有一个自己的set,试图执行动作时,使用MULTI原子地执行下列操作: ZREMRANGEBYSCORE 删除给定时间间隔前的元素, ZADD 添加当前时间戳, ttl设置为rate limit,计算sorted set的数量,如果超过限额,就失败 (滑动窗口日志)(有一说一我觉得这个如果没有精确的需求不如滑动窗口计数器, 开销感觉有点大)

多限流器同步: 用户hash redis集群分配之类, 尽量别做这种事情

其他层级的限流:

• iptables
• ...

一致性hash​

基本步骤如下：

1. 使用均匀分布的哈希函数将服务器和键映射到环上。
2. 要想知道一个键被映射到哪个服务器，从键的位置顺时针查找，直到找到环上的第一个服务器。

步骤是很简单的, 麻烦的是问题

环上服务器分区大小难以保证相同(添加删除服务器)

解决方法: 虚拟节点(分成更小的块)

每个服务器动态地分配小块(虚拟节点), 这样还可以考虑服务器容量自动缩放问题

一致性模型​

N = 副本数

W = 大小为 W 的规定写入。要将写入操作视为成功，必须从 W 个副本确认写入操作。

R = 大小为 R 的读取规定人数。为了使读取操作被认为是成功的，读取操作必须等待至少R个副本的响应。

如何配置N、W和R以适应我们的使用情况？

下面是一些可能的设置：

• 如果R=1，W=N，系统被优化为快速读取
• 如果W=1，R=N，系统被优化为快速写入
• 如果W+R>N，就可以保证强一致性（通常N=3，W=R=2）。
• 如果W+R<=N，则不能保证强一致性

复制->高可用->不一致

发现并解决冲突: 常用是向量时钟 vector clock, 但有几个问题

• 处理冲突逻辑复杂
• 动态增加删除服务器逻辑复杂

参考:

• https://juejin.cn/post/7205101745936203837
• https://houbb.github.io/2018/08/31/lock-vector-clock-01

实际业界的用例参考Dynamo

算法简介:在每个服务器内部维护一个所有服务器的vector

• 当自己发生事件时,增加vector[self], 并告诉需要告诉的服务器(核心就在于不广播, 没有全局时间!当然也因此不保证解决冲突)
• 当自己收到A server的事件时, vector[A] += d

最后想要觉得一个事件的全局顺序的时候, 查看所有的server的vec

如果有一个server的vec是最大的,那么严格有因果关系,取它的值就行

但如果没有最大的vec, 就需要解决冲突的策略

策略

1. 交给客户端, 如dynamo
2. 加上时间戳, vec' = [...servers, timestamp]冲突取ts最大的
3. 随机取一个

所以向量时钟算法的实质是：

（1）将逻辑上可以合并的冲突成功合并；

（2）逻辑上无法合并的冲突依旧冲突；

拓展: 向量时钟的剪枝, riak, 牺牲绝对的正确性(false merge)来换取对太长的vec clock的剪枝

gossip 协议 quorom

唯一ID生成器​

• 多主复制: 下一个id += k, k是服务器数量,拓展性差

• uuid

  • 引自维基百科，"在每秒产生10亿个UUIDs，大约100年后，创造一个重复的概率会达到50%"。

  • 优点：

    • 生成 UUID 很简单。服务器之间不需要协调，因此不会有任何同步问题。

    • 该系统易于扩展，因为每个 Web 服务器负责生成它们使用的 ID。 ID 生成器可以轻松地与 Web 服务器一起扩展。

  • 缺点：

    • ID 是 128 位长, 空间开销。
    • ID 不会随时间上升
    • ID 可以是非数字的

• ticket服务器, 在分布式系统之中维持一个唯一的ticket server用于签发id

  • **优点：**数字 ID，易于实施，适用于中小型应用程序

  • **缺点：**单点故障

• twitter雪花算法

  • 符号位：1 位，它将始终为 0。这是为将来使用保留的。它可以潜在地用于区分有符号数和无符号数。
  • 时间戳：41 位。自纪元或自定义纪元以来的毫秒数。我们使用 Twitter 雪花默认纪元 1288834974657，相当于 2010 年 11 月 4 日 01:42:54 UTC。
  • 数据中心 ID：5 位，这给了我们 25=3225=32 个数据中心。
  • 机器 ID：5 位，每个数据中心有 25=3225=32 台机器
  • 序列号：12 位。对于在该机器/进程上生成的每个 ID，序列号都会递增 1。该数字每毫秒重置为 0。

也就是说雪花在一台机器上1毫秒可以支持4096个新id

额外要点:

• 时钟同步。在我们的设计中，我们假设 ID 生成服务器具有相同的时钟。当服务器在多个内核上运行时，此假设可能不成立。同样的挑战存在于多机场景中。时钟同步的解决方案超出了本书的范围；但是，了解问题的存在很重要。网络时间协议是这个问题最流行的解决方案。
• 节段长度调整。例如，较少的序列号但较多的时间戳位对低并发性和长期应用是有效的。
• 高可用性。由于 ID 生成器是关键任务系统，因此它必须具有高可用性

拓展阅读: 网络时间协议

短URL​

点击较短的别名重定向到原始url

• URL缩短：给定一个长的URL => 返回一个短得多的URL

• URL重定向：给定一个短的URL => 重定向到原来的URL

• 高可用性、可扩展性和容错考虑

值得在这里讨论的一件事是 301 重定向与 302 重定向。

• 301重定向。301重定向表明，请求的URL被 "永久 "地移到了长URL上。由于是永久重定向，浏览器会缓存响应，对同一URL的后续请求将不会被发送到URL缩短服务上。相反，请求将直接被重定向到长网址服务器。

• 302重定向。302重定向意味着URL被 "暂时 "移到长URL上，这意味着对同一URL的后续请求将首先被发送到URL缩短服务上。然后，它们会被重定向到长网址服务器。

每种重定向方法都有其优点和缺点。如果优先考虑减少服务器负载，使用301重定向是有意义的，因为只有同一URL的第一个请求被发送到URL缩短服务器。然而，如果分析是重要的，302重定向是一个更好的选择，因为它可以更容易地跟踪点击率和点击的来源。

一个简单的解决方案 <shortURL, LongURL>的rdbms

假设系统支持3650亿个url=10年 * 每天1亿

可以使用0-9a-zA-Z62个字符， 62^n > 3650 亿 n = 7

方法1: hash+碰撞解决

longURL -> hash -> short -> exist on db?(opt bloomfilter + query) -> save/return/collision

collision 的一种解决方法是 longURL -> longURL + predefined string

方法2: base62转换

给每一个请求的长url分配一个数字类型的唯一id, 再对唯一id做base62转换

坏处是可能出现安全问题

longURL -> in DB ? -> yes,return short
            |
            -> no, generate new ID -> id to base62 -> save id, longurl, shorturl in db 

读多于写, 加缓存

爬虫系统​

算法侧: 从url seed开始, 将link视为边, 用BFS去爬取不同的网页

架构侧:

seed url -> url frontier -> html downloader(DNS resolver) -> content parser -> content seen(重复检测器, 例如 hash, BF) + 存储-> link extractor -> url filter -> url seen -> url storage

优先级: 简单的做法是根据Url内容变化的速度(可以基于历史抓取记录)和本身的价值（例如是个人博客还是官方网站）设计一个优先级估价函数, 根据url区分k个工作队列, 保证一个队列内只有一个url（的多个请求）, 这样就可以实现优先级

爬虫需要考虑礼貌性, DDoS

做法是每个url作为一个后端队列, 在优先级的selector出来之后, 维护一张(url,back queue)的表, 将url放到back queue里面去

对每一个url(backqueue), 维护一个时间t, 是下一次抓取的最早时间(例如当前时间+10倍前一次获取时间)

而爬虫线程每次从时间的最小堆之中取出元素, (如需要, 等待到t), 然后爬取

html下载器: Robots 排除协议, 分布式抓取, 超时

其他问题: 冗余内容, 蜘蛛陷阱, 垃圾数据, js-需要动态渲染得到链接和其他数据

通知系统​

删重, 跟踪, 限速, 用户设置(接受哪些通知), 失败时的重试机制, 安全性(客户验证)

推送流：

核心在fan out系统, 读扇出(拉模式)还是写扇出(推模式), 热键问题和速率问题

混合: 对大多数用户使用推送模式。对于名人或有很多朋友/粉丝的用户，我们让粉丝按需提取信息内容以避免系统过载

get friend IDs: graph DB

fanout service先从graph DB拿到friend ids, 再从用户缓存(用户db)得到朋友相关信息:

例如，如果你把某人调成静音，她的帖子将不会显示在你的信息流中，尽管你们仍然是朋友。帖子可能不显示的另一个原因是，用户可以有选择地与特定的朋友分享信息或对其他人隐藏信息。

把更新的需求包成任务(例如<post_id, user_id>)丢到mq

mq入库, 写缓存

缓存层级:

• News Feed：它存储了信息的ID。

• Content：它存储每个帖子的数据。受欢迎的内容被存储在热缓存中。

• Social Graph：它存储用户关系数据。

• Action：它存储有关用户是否喜欢帖子、回复帖子或对帖子执行其他操作的信息。

• Counters：它存储点赞、回复、关注者、关注等的计数器。

聊天系统​

无状态有状态分离

• 无状态的服务 http

  无状态服务是传统的面向公众的请求/响应服务，用于管理登录、注册、用户资料等。这些是许多网站和应用程序中的常见功能。

  无状态服务位于负载均衡器后面，其工作是根据请求路径将请求路由到正确的服务。这些服务可以是单体的，也可以是单独的微服务。我们不需要自己建立许多这样的无状态服务，因为市场上有一些服务可以很容易地被集成。

  我们将深入讨论的一个服务是服务发现。它的主要工作是给客户提供一个客户可以连接到的聊天服务器的DNS主机名列表。

• 有状态的服务 websocket

  唯一有状态的服务是聊天服务。该服务是有状态的，因为每个客户都与一个聊天服务器保持持久的网络连接。在这个服务中，只要服务器仍然可用，客户通常不会切换到另一个聊天服务器。服务发现与聊天服务密切协调，以避免服务器过载。我们将在深入研究中详细介绍。

服务器的切分:

• chat server 管理信息的收发
• presence server 管理在线/离线状态
• api server 处理无状态服务
• notification server 推送通知

DB选择: KV数据库

为什么？聊天数据的读写模式

• 数据量巨大 需要水平拓展
• 只有最近的聊天记录才会被频繁访问
• 但“最近”里面也不完全是顺序的, 引用, 跳转, 提及等
• 读写比约为1:1, 读并不远远高于写

这样的wkld下kv比关系型的优势:

• 水平拓展轻松
• 分层架构对热数据容易优化
• 关系型数据库的index在数据量变大时昂贵

消息ID设计:

一对一聊天: 主键message id

群聊: 复合主键 {channel_id, message_id}

问题: id用什么?

要求: 唯一性 + 可以按照时间排序

• 自增: 分布式实现困难
• 全局序列号发生器: 将时间项提前就可以按照时间排序
• 本地序列号生成器: 只保证消息在一个组内(channel内)唯一, 实现比较简单

发送信息的流程

1. 用户A向聊天服务器1发送了一条聊天信息。
2. 聊天服务器1从ID生成器获得一个信息ID。
3. 聊天服务器1将消息发送至消息同步队列。
4. 消息被储存在一个键值存储中。
5. a. 如果用户B在线，信息被转发到用户B所连接的聊天服务器2。
6. b. 如果用户B处于离线状态，则从推送通知（PN）服务器发送推送通知。
7. 聊天服务器2将消息转发给用户B，用户B和聊天服务器2之间有一个持久的WebSocket连接。

群组聊天:

第一种方法: A发消息, 在每一个成员的收件箱里面复制一个副本, 适用于群组人数较少的时候(例如微信的500人约束); 每个收件人有自己的收件箱(消息同步队列), 所以并不保证一致性

在线状态指示器:

• naive的做法: 建立连接就在线, 断开就离线。问题在网络波动时候, 变化太快
• 更优雅的做法, 心跳
• 推送, 类似微信这种小群(500人限制)可以直接查询实时的ws连接。大群需要懒加载

扩展聊天应用程序以支持媒体文件，如照片和视频。媒体文件的大小明显大于文本。压缩、云存储和缩略图是值得讨论的话题。

• 端到端加密。Whatsapp支持信息的端到端加密。只有发件人和收件人可以阅读信息。有兴趣的读者请参考参考资料中的文章[9]。
• 在客户端缓存信息，可以有效地减少客户端和服务器之间的数据传输。
• 提高加载时间。Slack建立了一个地理分布的网络来缓存用户的数据、频道等，以获得更好的加载时间[10]。
• 故障处理。
  • 聊天服务器错误。可能有数十万，甚至更多的，坚持不懈的连接到一个聊天服务器。如果一个聊天服务器离线，服务发现（Zookeeper）会提供一个新的聊天服务器，让客户建立新的连接。
  • 消息重发机制。重试和排队是重发消息的常用技术。

多媒体支持的大体流程

• client 通过 rest 将多媒体资源发送到服务器
• 服务器转换媒体文件(例如图片生成缩略图, 压缩)
• 服务器存到s3
• 服务器通过s3链接响应client
• 客户端再将s3链接通过ws发送(广播)给聊天的其他用户
• 其他client 收到s3连接, 根据定义的消息类型进行渲染

简单的搜索支持: trie​

topK: 先找到前缀, 再遍历子树

问题: 太慢

解决方法:

• 在每个节点缓存常用的前k个查询
• 控制前缀的最大长度

更新trie: 数据搜集, 对于实时应用服务, 短时间间隔; 对于非实时的, 可以例如一周定时更新一次

合法性: 自动完成可以根据hash等过一个filter, 避免补出禁止的网站等

多语言：unicode trie

分片: 可以基于字母, 但是要考虑到频率问题

实时(趋势)搜索: 流式, 领域特定, AI

视频流

核心是分成几个部分, 一部分类似传统的server, 提供视频metadata

另一部分依托云服务和CDN, 做好视频传输和解码编码

其中特定部分的逻辑复杂, 例如解编码的模块化和引擎化, CDN贵所以视频基于历史数据做冷热分离, 冷视频走自建而不是CDN

还有比如错误处理, 数字版权之类

具体好多细节

临近服务​

由于是读远多于写的情况, 所以常见用关系型db

关系型的问题是, 如果是经纬度, 二维数据index利用率低

解决方法是二维转一维再index搜索, 例如geohash, R tree, 四叉树, google s2

geohash: 经纬度网格编码再转base32, 共享前缀越长, 越接近

边界问题: 反过来不成立, 接近的两个地块可能共享前缀并不长(在子午线/赤道等大格子边界), 所以geohash LIKE 'sth%'检索出来结果不全

方法是不仅检索自己格子的geohash, 也把邻居格子的一起检索

业务问题：范围内部商家不够, 解决方法是放大格子继续检索

google s2: 基于希尔伯特曲线的球面->1d算法, 保证2d上接近在1d上也接近

vgg​

内存占用大，推理慢（深），但效果好

卷积层参数小，全连接层最大问题是参数太大过拟合

所以最后一层全连接是很大的问题

大参数还有内存 bound 的问题

NiN​

用卷积层替代全连接

两个 1*1 卷积无 padding, stride1 起全连接的作用(只做通道混合)

每个卷积后面跟两个全连接作为 NiN block

交替使用 NiN 块和 stride = 2 的 maxpooling 逐步减小高宽和增大通道数

最后使用全局平均池化得到输出(通道数 = 分类个数)

打印结构:

for layer in net:
    X = layer(X)
    print(layer.__class__.__name__, "output shape:\t", X.shape)

超级宽的 hidden layer: 非常容易过拟合

泛化性提高-> 收敛变慢

全连接的方案: 非常强, 收敛很快

GoogLeNet​

inception 块: 不做选择, 全都要

output = output1 + o2 + o3 + o4

o1 = conv1x1

o2 = conv1x1 + conv3x3, padding 1

o3 = conv1x1 + conv3x3, padding 1 + conv5x5, padding 2

o4 = 3x3 maxpool, padding 1

四条路径从不同层面抽取信息, 在输出通道合并 concatenation

四条路径分配不同的通道数(你认为那种模式哪个通道的信息更重要)

降低通道数来控制模型复杂度

googlenet 5 段, 9 个 inception 块

不降低维数的 1x1 卷积就是通道融合

第一个 stage 总是把通道数拉上去, 高宽减下去, 先筛选出足够多的特征

v2: batch normalization

v3: 5x5-> 3x3, 5x5-> 1x7+7x1(单长和单宽)

v4: 残差连接

优点是模型参数少, 计算复杂度低

批量归一化​

损失出现在最后, 后面的层训练快

反向传播: loss 在顶层, 数据在最底部, 底部的层(前面的层)训练慢, 底部层一变, 所有都得跟着变

导致离 loss 近的后面层需要重新学习多次, 导致收敛变慢

有没有方法让学习前面层的时候避免变化后面层?

批量归一化: 将分布固定, 来让输出模式稳定一些, 固定小批量的均值和方差

正则化, 将数据分布固定为 $N(0,1)$ 正态分布, 数据的修改只是在变化正态分布的超参数, 限制变化不要太剧烈

对于全连接, 作用 在激活函数前面, 作用在特征维度

对卷积, 作用在通道维

效果太好了, 原始论文觉得是减少内部协变量转移, 后续发现 可能就是等效于在每个小批量里面加入噪音来控制模型, 均值近似于随机偏移, 方差近似于随机缩放

因此没必要和丢弃混合使用

加速收敛(模式更稳定之后可以把 lr 调得更大), 但一般不改变模型精度

根据内存挑 batch size, 不能太大也不能太小, 然后调学习率和 epoch

ResNet​

残差的重要性不必多言

深网络必有残差思想

新硬件​

DSP 主要做数字计算处理长指令, FPGA 可编程阵列

工具链质量良莠不齐, 一次 "编译" 需要很久

AI ASIC: Google TPU eg

核心 systolic array, 专门做大矩阵乘法 2d 计算单元(PE)阵列, 卷积换成矩阵乘法

一般的矩阵乘: 切开和填充匹配 SA 大小

批量输入来降低延时, 其他硬件单元来处理别的 NN 操作子, 例如激活层

多卡并行​

数据并行(切割小批量), 模型并行(切割模型, 适用于模型太大的时候),

all reduce: 将所有 gpu 的结果放到一个 gpu 上, 然后相加, 加完再复制回其他 gpu

nn.parallel.scatter

nn.DataParallel

多卡时也要相应的加大 batchsize 和 lr

大 batch size 在小模型上会采出重复样本导致浪费和一定程度上的过拟合

分布式

GPU 和 GPU 通信快, 和 CPU 通信慢, 和交换机网卡更慢

• 类似存储器山

解法是把 parameter server 尽量从 cpu 搬到 gpu 上

这样简单的 parameter 迁移分配就能在 gpu 本地完成, 不涉及到 cpu 的 copy(感觉像 DMA)

每个 worker 拿参数, 复制到 GPU 上, 每个 GPU 算自己的梯度, GPU 梯度求和, 传回服务器, 再更新, 回发

类似 mr, server mapper, 本地 gpu 完成计算和 combine, 在 server reduce

同步 SGD, 每个 worker 同步计算一个批量

所以需要调 batch size, 来针对并行省下的时间与通信开销做 trade off

实践:

• 大数据集
• 好的 GPU-GPU 和机器-机器带宽
• 高效的数据读取和预处理
• 好的计算(FLOP)和通信(model size)比 Inception > ResNet > AlexNet
• 足够大的 batch size
• 高效优化算法（因为 batch size 变大了, 如何适配）
• 更复杂的分布式有异步, 模型并行

一般 N 个类, batch size 差不多到 10N 再往上就不太能 fit 了

数据增广​

已有数据集让他有更多多样性

• 在语言里面加背景噪音
• 改变图片的亮度, 颜色, 形状

一般的做法: 原始数据在线生成, 随机增强

测试不做增强

翻转:

• 左右翻转, 上下翻转
• 切割, 随即高宽比, 随机大小, 随机位置

其他:

• 高斯模糊
• 锐化
• 变形
• 滤镜
• 马赛克（相当于遮挡, 逼着去看全局）
• ...

从实际部署的场景反推需要什么样的增强

异常检测, 偏斜数据, 重采样, 增广

mixup 增广: 有效但不知道为什么

torchvision.transforms

微调(迁移学习)​

标注一个数据集很贵

希望在大数据集上做好的东西, 能以小代价迁移到小数据集上

神经网络分层两块: 特征提取+线性分类

dl: 让特征提取变得可以学习, 而不是人来提取特征

训练:

• 更强正则化
• 更小学习率
• 更少的数据迭代

源数据集远复杂于目标, 微调效果更好

固定一些层, 固定底部一些层的参数, 不参与更新

低层次的特征更加通用

小 trick, 微调的时候最后一层用大学习率, 前面用小的

迁移的也不能差太大, 否则效果很可能不够好

目标检测​

bounding box

锚框: 提出多个被称为锚框的区域, 预测每个框里面是否有关注的物体, 如果是, 预测锚框到真实框的偏移

交并比 IoU

每个锚框是一个训练样本, 要么标注成背景, 要么关联一个真实边缘框

可能生成大量锚框, 导致大量的负类样本

选择合适的锚框(赋予锚框标号):

先生成一堆框, 之后算锚框 i 和真实框 j 的 IoU, 在 i, j 之中找最大的, 就得到了一组锚框和真实框的对应

然后从集合中剔除这个锚框 i 和边缘框 j(删除矩阵行列), 再找下一组

重复直到真实框为空, 这就是正类样本, 剩下的锚框挑一些作为负类样本

锚框生成: 一种固定切分画格子

NMS 非极大抑制: 合并相似的预测框

• 选中非背景类的最大预测值
• 去掉所有和它 IoU 大于阈值的预测
• 重复直到所有预测要么被选中, 要么被去掉

生成锚框的另一种示例方法

宽度 $ws\sqrt r$, 高度 $hs/\sqrt{r}$

对给定几组 $(s,r)$ 对每(n)个像素生成

算法的核心之一: 如何生成高质量锚框

锚框到偏移的算法: 多种多样

autogluon

工业界很少用模型融合和测试增强, 计算代价过高

通常固定模型超参数, 简单模型, 精力花在提升数据质量和加入的新数据

RCNN:

启发式搜索算法选择锚框

预训练模型对每个锚框抽取特征

训练一个 SVM 对类别分类

训练一个线性回归来预测偏移

RoI pooling

锚框均匀分割 mxn, 输出每块里面的最大值

不管锚框多大, 总是输出 mn

Fast RCNN

不再对每一个锚框抽取特征

而是将所有的锚框丢进 cnn(输入里面对应的映射区域), 一次 CNN 对整个图片抽取

Faster RCNN: 使用区域提议网络代替启发式搜索来获得更好的锚框

2-stage

Mask RCNN 如果有像素级别的编号, 给每个像素做预测, 用 FCN 利用信息

Faster RCNN: 速度非常慢, 精度高

SSD: single stage

基础网络抽特征, 多个 conv 减半高宽

每段都生成锚框

• 底部段拟合小物体, 顶部段拟合大物体

对每个锚框预测类别和边缘框

yolo: 追求快

ssd 锚框大量重叠, 浪费计算

均匀切分 SxS 个锚框, 每个锚框预测 B 个边缘框

后续有许多微调和改进

工业常用

非锚框: 例如 central net

语义分割​

像素级分类

应用: 背景虚化, 路面分割

另一个相近的概念: 实例分割

数据集: 输入是图片, label 也是图片(每个像素的值就是 label)

crop: 怎么做, 对输入进行裁剪, 在 label 上也要相对应的裁剪

拉伸也是需要特殊处理的

旋转? 一种是可以加一个 label 是旋转角度, 另一个是可以在转完的斜框上涨再画一个大框框住斜框

人像: 难点在光照, 阴影和背景

人像语义分割: pretrain model 已经很成熟

转置卷积​

卷积的问题：不能很有效的增加高宽

类似语义分割这种-> 卷积不断减小高宽, 会影响像素级别的输出

$Y[i:i+h, j:j+w] += X[i,j] \times K$

增大输入高宽

为什么是转置卷积:

卷积等价于矩阵乘法 $Y = VX$, 转置卷积就是 $Y = V^{T}X$

nn.ConvTranspose2d

卷积是下采样, 卷积是上采样

转置卷积与线性插值: 可以用线性插值作为转置卷积核的初始值

FCN​

全连接卷积神经网络

用 dl 做语义分割的最早工作

用转置卷积替换 CNN 最后的全连接层+全局池化

• 先过 1x1 conv 压缩通道
• 再过转置卷积拉大图片, 得到像素级别的切分
  • 思想是每个像素的的 label 信息这个 feature 应该存在 channels 里面

net = nn.Sequential(*list(pretrained_cnn.children()))[:-2]

可以用双线性插值的矩阵初始化转置卷积层的 kernel

loss: 由于每一个像素都有了 label

所以在矩阵上做均值再 cross_entropy

样式迁移​

基于 CNN 的样式迁移

核心思想: 训练一个 CNN, 将他作用在内容图片上得到输出, 在样式图片上得到输出

而输出图片在内容层上的输出和内容图片在内容层上的输出相近(content loss)

输出图片在样式层上的输出和样式图片在样式层上的输出相近(style loss)

训练的不是 CNN, 而是输入网络的的“输出图片”

哪些层是“style layer”, 哪些是 "content layer"?

样式: 最小, 中间和上层, 较均匀

• 样式有全局的特征和局部的特征, 各个尺度均有

内容: 偏末尾的层, 靠近 loss

• 允许内容上更多的变形

内容损失可以是简单的 MSE

• 元素值, 通道里面的值, 认为是内容

样式损失? 通道内部和之间的统计分布, 认为是样式

• 分布匹配, 一阶平均值, 二阶协方差, 用二阶就还不错

最后: tv_loss, 不要有噪点, 每个像素和周围像素不要差太多, 计算每个与周围的 MSE 再求平均

这几个损失如何加起来? 加权平均, 权值是超参数

style 一般更重要, 例如 content:style:tv=1:1000:10

这几个超参数的调整是训练几次之后, 观察三种 loss, 调到差不多大小得出的

不更新: y.detach()

卷积只作为抽特征

麻烦: 后续技术, GAN, 使用 CNN 接收随机输入生成图片等

序列模型​

标号和样本是一个东西: 自回归模型 t-k ~ t-1 -> t

方法 A: 马尔可夫假设: 假设当前数据只和 k 个过去数据点相关

方法 B: 潜变量模型: 引入潜变量 $h_t$ 来表示过去信息 $x_t = p(x_t|h_t)$, $h_t = f(x_1,...x_{t-1})$

那我们就可以将预测拆成两步:

1. $h_t = Model1(h_{t-1}, x_{t-1})$
2. $x_t = Model2(h_t, x_{t-1})$

文本预处理​

预处理的核心是分词

GPU 上存算的是 token 索引而非字符串

语言模型:

给定文本序列, 估计联合概率

• 做预训练模型
• 生成文本
• 判断多个序列之中哪个更常见

简单方法: 基于计数建模

序列很长的时候, 由于文本量不够大, 可能 $n(x_1,...x_t)\le 1$

使用马尔可夫假设缓解, n 元语法假设, 假设只和前 n 个词相关

以二元为例, 则有 $p(x_1,x_2,x_3,x_4) = \frac{n(x_1)}{x1} \frac{n(x_1,x_2)}{n(x1)} \frac{n(x_2,x_3)}{n(x2)} \frac{n(x_3,x_4)}{n(x3)}$

RNN​

更新隐藏状态: $h_t = \phi (W_{hh}h_{t-1} + W_{hx}x_{t-1} + b_h)$

输出: $o_t = \phi (W_{ho}h_t + b_o)$

训练的模型: $W_{hh}, W_{hx}, W_{ho}, b_h, b_o$

如果没有 $W_{hh}h_{t-1}$ 就是 MLP

loss 设计: 困惑度 perplexity

把输出看成是词典大小为 label 数量的话, 可以用交叉熵, 然后对整个句子取平均

但实际不是用这个, 而是用 exp(平均交叉熵)

梯度裁剪: 在 T 个时间步上的梯度, 反向传播 O(T)矩阵乘法, 梯度爆炸

如果梯度长度超过 $\theta$, 变回 $\theta$

$g \times min(1, \frac{\theta}{||g||}) \to g$

更多的 RNN:

• 1 对多: 文本生成
• 多对 1: 文本分类
• 多对多: 问答, 机器翻译
• 多对多: tag 生成

GRU&LSTM​

对于一个序列, 记住相关观察需要 更新门(能关注的机制) + 重置门(能遗忘的机制)

$R_t = \sigma (X_tW_{xr} + H_{t-1}W_{hr} + b_r)$ reset gate

$Z_t = \sigma (X_tW_{xz} + H_{t-1}W_{hz} + b_z)$ update gate

候选隐状态

$H_{cand(t)} = tanh(X_tW_{xh} + (R_t \odot H_{t-1})W_{hh}+b_h)$

$R_t$ : $[0,1]$ 软控制

$H_t = Z_t \odot H_{t-1} + (1 - Z_t) \odot H_{cand(t)}$

隐藏层多大? 例如 128,256, 长序列就 1024

实际不考虑 RNN, 一般 GRU/LSTM

超过 100,1000 这样的长度量级, 考虑 Attention

LSTM

忘记门: 将值朝 0 减少

输入门: 决定是不是忽略输入

输出门: 决定是不是使用隐状态

更深(多个隐藏层)的 RNN, 更多的非线性性

双向 RNN

一个前向 RNN 隐层

一个反向 RNN 隐层

合并两个得到输出

output 是前向和反向的共同贡献

推理怎么推? 非常不适合做推理, 几乎不能推

主要作用: 对句子做特征提取, 填空, 而不是预测未来

输入需要定长(为了以 batch 的形式读入)

如何做不定长的? 填充或者截断, 例如翻译

encoder-decoder 架构​

encoder: 将输入编程成中间表达形式(特征)

decoder: 将中间表示解码成输出

encoder 将 state 传给解码器做输入

seq2seq​

encoder 是一个 RNN, 可以双向

decoder 是另一个 RNN

编码器是没有输出的 RNN

encoder 最后时间步的 hidden state 作为 decoder 的初始 hidden state

训练, 训练时 decoder 用目标句子作为输入

衡量生成序列的好坏: BLEU

exp 项: 防止 pred 句子长度过短偷懒提高精度

BLEU 越大越好

seq2seq: 从一个句子生成另一个句子

sequence_mask：在序列中屏蔽不相关的项(padding)

拓展 softmax 来屏蔽不相关的预测(padding 对应的 output)

预测

最开始输入 <bos>, 然后 RNN 每次输出作为下一个的输入

seq2seq 可以纯 transformer

束搜索​

beam search

seq2seq：用当前时刻预测概率最大词输出（贪心）

但贪心很可能不是最优的

暴搜指数级增长肯定不行

bin search: 对每个时刻, 保存最好的 K 个序列

每一次新预测会对 k 的 kn 个可能的下一个序列之中再调最好的 k 个

如何选择 "最好"?

单纯的概率乘总是倾向于选择短句子, 需要给长句子加权

每个候选的最终分数 $\frac{1}{L^{\alpha}}logp(y_1,...y_L)$, 取 $\alpha=0.75 < 1$ 给长句子加权

Attention​

卷积, 全连接, 池化只考虑“不随意”的线索

• "最大值", 明显的特征

注意力机制显式地考虑随意线索

• 随意线索被称为查询 query
• 每个输入是一个值 value 和不随意线索 key 的对
• 通过注意力池化层来对有偏向性的选择某些输入

非参(不需要任何先验参数)注意力池化层

给定数据(环境, 先验, context) $(x_i,y_i)$

查询: 给定一个 x, 求对应的 $y=f(x)$

注意力: $f(x)=\sum_i \alpha(x,x_i)y_i$, $\alpha(x,x_i)$ 就是注意力权重

最简单的方法: 平均池化, $f(x)=\frac{1}{n}\sum_i y_i$

更好的方案是 60 年代的 Nadaraya-Watson 核回归

$f(x)=\sum_{i} \frac{K(x-x_i)}{\sum_j K(x-x_j)}y_i$

高斯核 $K(u)=\frac{1}{\sqrt{2\pi}}exp(-\frac{u^2}{2})$

$f(x)= \sum_{i} softmax(-\frac{1}{2}(x-x_i)^2)y_i$

参数化:

再引入可以学习的 w

$f(x)= \sum_{i} softmax(-\frac{1}{2}((x-x_i)w)^2)y_i$

相较非参的注意力, 变得更不平滑

拓展到高维度 $\alpha(q, k_i)$

1. Additive Attention: 可学参数 $W_k \in R^{h\times k}$, $W_q \in R^{h\times q}$, $v \in R^{h}$

$a(k,q) = v^{T}tanh(W_kk + W_qq)$

等价于将 kv 合并之后放入一个隐藏大小为 h, 输出大小为 1 的单隐藏层 MLP

也是当 q, k 不一样长的时候最常用的做法

如果 q, k 都是同样长度的

2.Scaled Dot-Product Attention

$a(q,k_i)=<q,k_i>/\sqrt{d_k}$, 相当于 q 在 k 基上的分量+归一化

$a(Q,K)=QK^{T}/\sqrt{d}$

$f=softmax(a(Q,K))V$

Q, K, V 是一个矩阵？self-attention 自注意力 $f=softmax(XX^{T}/\sqrt d))X$

但实际运用会给 X 做不同线性线性变换后再输入

$f=softmax(XW_QX^{T}W_K/\sqrt d))XW_V$

Attention 机制的 seq2seq​

翻译的词可能相关于原始句子之中不同的值

原始 seq2seq 只能看到单一词的输入, 虽然有隐藏层, 但长距离丢失信息

• encoder 的对每个词的输出作为 key 和 value（key = value）

• decoder RNN 对上一个词的输出是 query

• attention 的输出和下一个词的 embedding 合并进入 decoder

原始的 seq2seq 相当于是只将上一个词的 state+t-1 时刻的 encoder 输出丢到了 decoder 里面

$decoder(state_{t}, eoutput_{t}, output_{t-1})$

现在拓展其表达力, 认为 decoder 应该获取的不是单单最后一个词的输出, 而是和之前的词输出(更长的上下文)都有点关系, 具体关系用 attention 学习, 以编码器的 output 作为 query key, 获取这个 output 最相关的上下文, 并认为翻译的文本之中也应该有类似的上下文关系

$decoder(state_t, attention(output_{t-1}, eoutputs, eoutputs))$

tokenizer: sentencepiece

embedding: 专业词, 需要调整 tokenizer, 需要添加词 pair, 需要训练新添加的 embedding, 正常领域 frozen 不动, 加 LoRA/Adapter

自注意力​

self-attention

序列长度是 n, 卷积核大小 k

自注意力适合处理长文本

代价: 计算代价 $n^2$ 增长

位置编码:

和 CNN, RNN 不同, 自注意力没有记录位置的信息, 位置编码将位置信息注入到输入里

• 输入 $X\in R^{n\times d}$, 叠加位置编码 P, X+P 作为自编码输入

$p_{i,2j}=sin(\frac{i}{10000^{2j/d}}),p_{i,2j+1}=cos(\frac{i}{10000^{2j/d}})$

为什么这么设计

记 $\omega_j = 1/10000^{2j/d}$, $p_{i+\delta} = RotateMatrix(\delta \omega_j) \times p_{i,\delta}$

所以实际上是相对位置的编码

也就是对于同一个序列 j, 位置 i 有 <i, i+k> 的关系的 pair 始终是一个相同的关系

Transformer​

纯基于(self-)attention

encoder-decoder 架构

multi-head attention

对同一的 QKV, 希望抽取不同的信息

使用 h 个独特的注意力池化

attention 没有时序信息, encoder 无所谓

decoder 不应该看到不该看到的信息, 需要加入掩码

计算 $x_i$ 输出时, 假装当前序列长度为 i

基于位置的前馈网络 Positionwise FFN

将输入形状 $(b, n, d)$ 变换成 $(bn, d)$, 输出再换回来

两层全连接, 添加非线性, 做更多的特征融合

$FFN(x)=f(xW^{T}_{1})W_2$

Add&Norm: 残差+归一化

编码器的输出 y_1, ... y_n

作为解码器之中第 i 个 transformer 块之中多头注意力的 key 和 value

预测, t+1 输出

decoder 输入前 t 个预测值作为 key, value, 第 t 个预测还作为 query

Bert​

nlp 的迁移学习

使用 pretrain 的模型抽取词句的特征

不更新 pretrain 模型

问题: 1. 做 embedding 的话忽略了时序信息 2.后续模型还要自己设计, 只有 embedding 似乎没有很大用处

Bert: 能不能也通过改最后一层复用?

只有编码器的 transformer

对输入的修改:

• 每个样本都是一个句子对

• 加入额外的片段嵌入

• 位置编码可学习

三种 embedding: position, segment, token

通用的任务?

任务 1: 带掩码的语言模型

带掩码的语言模型每次随机(15%概率)将一些词元换成 <mask>

微调任务之中不出现 <mask>

微调任务是没有 <mask> 标记的，如果设计方案是：只要 token 被选中 mask 处理，并且处理方法只要一种就是 token 别替换为 <mask>，这样的话，预训练任务和微调任务的数据太不一样了。BERT 的 3 种 mask 方法，可以使得，有 20%情况，句子对没有 <mask> 标记。

我理解的说白了就是不仅仅是因为看到了 <mask> 才去找上下文的信息，而是一直保持联系上下文的“习惯”

• 80%下, 变成 <mask>
• 10%, 随机(错误的结果)
• 10%, 原有(正确的结果)

10%的词会被替换成随机词元的原因： 作者在论文中谈到了采取上面的 mask 策略的好处。大致是说采用上面的策略后，Transformer encoder 就不知道会让其预测哪个单词，或者说不知道哪个单词会被随机单词给替换掉，那么它就不得不保持每个输入 token 的一个上下文的表征分布(a distributional contextual representation)。也就是说如果模型学习到了要预测的单词是什么，那么就会丢失对上下文信息的学习，而如果模型训练过程中无法学习到哪个单词会被预测，那么就必须通过学习上下文的信息来判断出需要预测的单词，这样的模型才具有对句子的特征表示能力。另外，由于随机替换相对句子中所有 tokens 的发生概率只有 1.5%(即 15%的 10%)，所以并不会影响到模型的语言理解能力。（网上复制的，这是我找到的可以说服我自己的一个解释）

任务 2: 下一句子预测:

训练样本之中, 50%选择相邻句子对, 50%选择随机句子对

微调 Bert​

bert 对每一个次元返回抽取了上下文信息的特征向量

不同的任务取不同的特征

• 句子分类, 将 <cls> 对应的向量输入到 MLP 分类
• 命名实体识别, 识别一个词元是不是命名实体, 例如人名机构位置
  • 把每一个非特殊词元(不是 <cls><sep>...)放进 MLP 分类
• 问题回答: 给定一个问题和描述文字, 找一个片段作为回答
  • 对片段的每一个词元预测是不是回答的开头或者结束

实用机器学习

不讲模型, 讲数据

知识积累, 学会读论文, 经典论文需要读懂每一句话

结合代码了解细节

对读过的论文做整理

自旋锁->自旋N次(N自适应, 取决于先前历史,当前负载等)->升级为重量级锁

重量级, mutex 本质上的syscall, 轻量级, CAS去尝试拿到对象头中的锁标识字节MarkWord

更新成功说明没人抢

偏向锁: 当某个线程第一次获取锁时, 接下来都没有其他线程拿, 那这个线程后续拿锁就连CAS也不需要

无锁->偏向锁->自旋锁->重量级锁

JMM

所有可能出现竞争的变量(成员, 静态等)均在主内存

局部变量线程私有, 工作内存相互隔离, 只能通过主内存同步

volatile

需要立即看到修改的值, 每一次读取都从主线程读, 每一次写都把工作内存的值刷新到主线程

Lab0​

这个lab纯纯的热身lab, part1是用webget简单进行个请求, 类似csapp的网络lab part1

part2字符串操作, 恶心一点的就是string_view的peek和一个ring buffer不太能兼容, 总之我的代码效率也挺低的就不拿出来献丑了()

Lab1​

这个lab要求实现tcp字节流抽象的重组部分Reassembler

调的时候还是很恶心的, 非常多的edge case, 建议好好看测试是怎么构造的

写的时间最久的一个lab, 但这里笔记没有多少, 因为Lab1结束到Lab2开始的两个星期干别的去记不清当时的感受了()

还是放个源代码

#include "reassembler.hh"

lec5 多处理器编程：​

理解程序：状态机模型，我们把一个程序看成一个状态机，程序的状态是{寄存器，内存}，而每次取出一条指令、再执行的过程的就是状态迁移到过程。

由这个状态机模型，我们可以有非常多的 trick，例如 debug 单步执行，例如模拟器，例如如果某些指令是“可逆”的，就可以在 debug 的时候反向执行，“时间倒流”（gdb 也提供了这一模式）……

对于并发程序，多处理器模型，我们的直觉告诉我们，可以把这个程序看成是多个状态机，并发的过程就是每次取出一个状态机，执行一步，而所有的状态机有共享的内存（线程模型）…… 这样的模型已经足够复杂，状态数是指数增长的，解决需要考虑所有状态的问题是 NP 完全的。

并发编程的问题：

1. load/store 的非原子性
2. 编译器的优化

配置文件

server 虚拟主机, 根据 {listen, server_name}的IP-port或者domain-port对来进行唯一性标识, 可以单项相同, 会匹配另一项转发

location + root, index指定主页等

配置静态页面结束

反向代理: server端请求转发

server {
    listen 8001;
    server_name any_name;
    location / {

Unit 1: Internet and IP​

网络四层模型:application, transport, network, link

7层OSI, 拆app,trans,link为更细的两个

网络的基础和底层是IP, 只有IP model是不可替代的“细腰”,上层的application、transport和下层的link都是可以替换的

application 应用层,smtp, ftp, http, ssh

transport 传输层,tcp, udp, rdp

link 连接层,4G, WiFi, ...

网络连接的几种常见例子:

client-server, BitTorren 一服务器多client的集群, ......

网络 application上 :read/write

Django mosh

shell django-admin

django-admin startproject <proj name> .

run server

python manage.py runserver

app 可以通过 proj 初始 settings.py 集成

splay tree​

1. Counting Binary Tree

ref: 卡特兰数（Catalan number）（二） - 知乎 (zhihu.com), stackoverflow 专栏

给定节点数 n，二叉树的种类数？ 卡塔兰数 C(n).