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上也接近

自旋锁->自旋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).

一些细节和思考：

Q: wait for reading the source code and thinking

A: after reading the source code and thinking