Notes

tags: 一致性 确定读写成功 确定读写节点在多少节点成功才可以认为写入成功：需要保证读取时至少一个包含新值。 n 个副本的情况下，写入需要 \(w\) 个节点确认，读取必须至少查询 \(r\) 个节点，则只要 \(w + r > n\) ，读取的节点中一定会包含最新值。 \(w\) 仲裁写（法定票数写） \(r\) 仲裁读（法定票说读） 一般 \(n\) 设置为奇数： \(w=r=(n+1)/2\) （向上取整）。 可容忍的失效节点数 仲裁条件 \(w+r>n\) 定义了系统可容忍的失效节点数。 \(w<n\) ，如果一个节点不可用，仍然可以处理写入。 \(r<n\) ，如果一个节点不可用，仍然可以处理读取。 \(n=3\),\(w=2\),\(r=2\)，则可以容忍一个节点不可用 \(n=5\),\(w=3\),\(r=3\), 则可以容忍两个节点不可用 局限性 如果采用了 sloppy quorum，写操作的 w 节点和读取的 r 节点可能完全不同，因此无法保证写请求一定存在重叠的节点。 并发无法明确顺序，需要进行合并并发写入。如最后写入者获胜。 同时读写，写操作在一部分节点上完成，则读取新值还是旧值存在不确定性。 部分节点写入成功，但是最终写入失败无法回滚。 新值的节点失效，但恢复数据来自某个旧值，则总的新值节点数低于 w 边界情况

没有主节点，允许任何节点接受来自客户端的写请求。 实现方式 客户端直接将其写请求发送到多节点 一个协调者代表客户端进行写入，与主节点的数据库不同，协调者并不负责写入顺序的维护。 节点失效时写入数据库 客户端将写请求并行发送给三个节点，两个可用节点接受写请求，而不可用副本则无法处理该请求。 现在失效的节点重新上线，客户端可能会读取到旧的值。 为了解决这个问题客户端并行的向多个节点发送读请求，并通过版本号来确定哪个值更新。 读修复与反熵 读修复；客户端并行读取多个节点，检测到过期的返回值，然后用新的返回值写入到返回旧值的副本。 反熵过程：后台不断查找副本之间的差异，将任何缺少的数据从一个节点复制到另一个节点。不保证特定顺序的复制写入，并且会引入明显的复制滞后问题。 Quorum 一致性 检测并发写

最常见的拓扑结构，提供更好的容错。每个节点从其他所有节点同步写入。

通过指定一个根节点，根结点将所有的写操作转发给其他所有节点。

每个节点接收来自前序节点的写入，并将这些写入（加上字节的写入）转发后后序节点。同时通过唯一 ID 防止无限循环。

每个副本总是保存最新值，允许覆盖并丢弃旧值。假定每个写请求都最终同步到所有副本，只要我们有一个明确的方法来确定哪个写入时最新的，则副本可以最终收敛到相同的值。 通过每个请求附加一个时间戳，选择最新即最大的时间戳，丢弃较早的写入。则为最后写入着获胜（last write wins，LWW）。 缺点 会造成数据丢失。 适用场景 缓存系统。 确保安全无副作用 唯一方法是只写入一次然后写入值视为不可变，这样旧避免对同一个主键的并发（覆盖）写。

多个主节点看到的执行顺序不一致，病了同时按照各自看到的写入顺序执行，那么数据库最终将处于不一致状态。 数据库必须以一种趋同的方式来解决冲突。 可能的解决方式 给每个写入分配唯一的 ID，如基于时间戳的最后写入者获胜。 为每个主节点分配一个唯一 ID，序列号高的优先于序列号低的主节点，可能导致数据丢失 以某种方式合并值，如按照字母顺序拼接在一起 利用预定义号的格式记录，然后依靠应用层逻辑，事后解决冲突（可能会提示用户）

应用层保证对特定记录的写请求总是通过同一个主节点，来避免发生些冲突。 如用户更新自己的配置总是路由到特定的数据中心。 缺点 特定数据中心发生故障不得不改变事先指定的主节点。

对于一系列按照某个顺序发生的写请求，同时读取这些内容时也会按照当时写入的顺序。 场景 分区数据库中出现的一个特殊问题。 正常对话： P: C小姐，你能看到多远的文莱？ C：大约 10s，P 先生。 但是由于复制滞后，最终能被观察到的可能是： C：大约 10s，P 先生。 P: C小姐，你能看到多远的文莱？ 解决方案 低效率：具有因果关系的写入都交给一个分区来完成。 新方法：跟踪事件因果关系。

是一种比强一致性弱但是比最终一致性效应强的保证，单调读保证： 如果某个用户依次进行多次读取，则绝不会看到回滚的现象，即在读取到较新的值之后又发生读旧值的情况。 场景 用户刷新网络，读请求被随机路由到某个从节点，先后从两个不同的从节点读取到了不同的内容，比如看到一个新添加的评论一次出现，一次消失。 解决方案 按照用户 ID 进行哈希方法取代随机路由。

也称为「写后读一致性」，解决用户主节点写入后立马从从节点读取不到到情况。只能解决单用户的一致性，但是解决不了多用户的一致性。 场景 用户新提交了评论，但是自己看不到，需要等一会才能看到。 解决方案 记录更新时间戳，在指定时间内从主节点读取。

主从异步复制的情况下会导致数据库中出现明显不一致，此时从不同的从节点读取就会得到不一样的结果。这种不一致只是一个暂时状态，如果停止写入数据，经过一段时间之后，从节点最终会赶上并与主节点保持一致。 这种效应被称为最终一致性。

异步同步的情况下出出现最终一致性效应复制滞后会导致：用户提交了修改到主节点，但是从从节点没有读取到最新的变更，比如看不到自己提交的评论等。 读写一致性：读自己的写 一旦用户的数据最近发生改变则路由用户请求从主节点进行读取，规避复制滞后的问题。 缺点：只保证单一用户写后读的的一致性，但是不保证多个用户的一致性。比如发了一条评论，自己能刷新到但是同在身边的朋友可能就刷新不到。 单调读一致性 前缀一致读 解决方案 应用层可以提供比数据库更强有力的保证。 事务是数据库提供的更强保证的一种方式。

基于语句复制 优点：简单 缺点：语句副作用，或者随时间改变返回值的函数的使用会导致复制的数据产生改变。 基于预写日志（WAL）传输 优点：解决基于语句复制的问题。 缺点：日志描述过于底层：哪些磁盘块的哪些字节发生了改变，和引擎实现高度耦合，不利于模式演进。 基于行的逻辑日志复制 用一系列记录来描述数据表行级别的写请求： 对于插入行，日志包含所有相关列的新值。 对于删除行，标记主键删除。 对于行货更新，记录主键和对应列的新值。 MySQL binlog 基于此模式。 优点：更利于模式演进，支持向后兼容，同时解耦特性引擎便于外部解析。 基于触发器的复制 触发器支持注册自己的应用层代码并在数据发生改变时被调用。 优点：将复制控制交给应用层，支持更高的灵活性。 缺点：开销更大，更容易出错。

主从模式下主节点进行写入，可以从从节点进行读取。 同步复制 主节点写入，并等待从节点写入后再返回写入成功。 半同步复制 主节点写入，选举一个从节点进行同步复制，其他从节点进行异步复制，一旦同步复制的从节点出现性能下降或故障则选用一个新的从节点进行同步复制。 异步复制 主节点写入，不等待从节点写入直接返回写入成功。

主节点与从节点 复制 单个节点可以完整存放所有数据副本，节点间进行主从复制。 配置新从节点 可以通过快照来加速新从节点复制： 对主节点的数据副本产生一个一致性快照，避免长时间锁定数据库。 拷贝快照到从节点 请求快照后面的更改日志 应用数据变更 节点失效 从节点失效：追赶式恢复 主节点失效：节点切换 自动切换 确认失效 选举新的主节点 使主节点生效 挑战 从节点复制不完整 各个数据层数据不一致，如 MySQL 和 Redis 之间 多个主节点选举：脑裂 如何有效检测主节点失效 复制日志实现 复制滞后问题 多主节点复制 使用场景 多数据中心 优点： 性能 容忍数据中心失效 容忍网络问题 缺点：写冲突 离线客户端操作 协作编辑 处理写冲突 同步与异步冲突检测 同步：等待写请求完成对所有主节点的同步再通知用户写入成功。 异步：等待单一主节点写入成功后通知用户卸乳成功，稍后多主节点数据同步的时候才能检测到冲突 避免冲突 收敛于一致的状态 自定义冲突解决逻辑 写入时解决 读取时解决 拓扑结构 环形拓扑 星型拓扑 全部-至-全部型拓扑 无主节点复制

当一个不可能出错的事物出错了，通常也就意味着不可修复 – Douglas Adams，《基本无害》（1992） 关于写文档 There is a secret that needs to be understood in order to write good software documentation: there isn’t one thing called documentation, there are four. They are: tutorials, how-to guides, technical reference and explanation. They represent four different purposes or functions, and require four different approaches to their creation. Understanding the implications of this will help improve most documentation - often immensely.

Actor 模型是用于单个进程中的并发模型。逻辑被封装在 Actor 中。每个 Actor 通常代表一个客户端或实体，可以具备本地状态（不共享），通过发送和接收异步消息与其他 Actor 通信。不保证消息传送：某些错误情况下，消息将丢失。每个 Actor 只处理一条消息，因此可以由框架独立调度。 Actor 框架集成了任务调度和消息流的框架。

两种模式语言：IDL 用于人工编辑，另一种更易于机器读取。 Avro 编码数据中只有对应字段的长度和具体的数据，不包含字段的类型信息。 写模式与读模式 写模式：使用所知道的模式的任何版本来编码数据（可以编译到代码中） 读模式：解码时期望数据符合某个模式，可能是构建过程中基于模式生成 Avro 的关键思想是写模式和读不必完全一样，只需要保持兼容，由读取端解决差异：通过对比查看写模式和读模式并将数据从写模式转换为读模式。 读取数据的代码中遇到出现在写模式但是不在读模式的字段，则忽略。 如果读数据的带代码需要某个字段，但是写模式不包含该字段的名称，则使用在读模式中声明的默认值填充。 模式演化 向前兼容：新版本的模式作为 writer，旧版本的模式作为 reader。 向后兼容：新版本的模式作为 reader，旧版本的模式作为 writer。 同时为了保持兼容性，只能添加莫删除具有默认值的字段。

每个字段一个标记号码，字段名可以随意调整因为编码信息中只有标记号码，没有字段名称，但是标记号码不能随意调整，基于此可以实现： 向前兼容 旧代码忽略不能识别的标记号码，并根据类型的注释来通知解析器跳过特定的字节数。 向后兼容 标记号码不变的情况下新的代码总是能够解析旧代码序列化的数据，但是新添加的字段不能标记为 required，不然会触发运行时错误。 同时为了保证前后兼容，删除字段也不能删除设置为 required 的字段，同时再次新添字段标记号码不能被再次使用。 改变类型同时也会导致前后兼容问题。

模式演化要保证： 向后兼容 较新的代码可以读取旧代码编写的数据 向前兼容 较旧的代码可以读取较新代码编写的数据 数据编码格式 语言特定格式 Python pickle Java java.io.Serializable Ruby Marshal JSON、XML与二进制变体 二进制变体 Message Pack：二进制的 JSON Thrift 与 Protocol Buffers Avro 数据流模式 基于数据库的数据流 不同是写写入不同的值 归档存储 基于服务的数据流：REST 和 RPC RPC 的问题 给人一种本地调用的错觉，却需要面临网络的不确定性：延迟和超时。 基于消息传递的数据流 消息中间件：RabbitMQ、Kafka 分布式Actor 框架：Akka、Erlang OTP

在线分析处理（Online Analytic Processing，OLAP）。

在线事务处理（Online Transaction Processing，OLTP）。

B-tree 是最广泛使用的索引结构。和排序字符串表：SSTables一样，B-tree 保留按键排序的 key-value 对， 这样可以实现高效的 key-value 查找和区间查询。 结构 B-tree 将数据库分解成固定大小的页或块，传统上 4KB，这种设计更接近底层硬件，磁盘也是以固定大小的块排列的。 分页因子 B-tree 中一个页所包含的子页引用数量称为分支因子。 添加新键 找到其范围新键的页 如果页没有足够的可用空间来容纳新键，则将其分裂为两个半满的页，并更新父页以包含新的键范围。 算法确保树保持平衡：具有 n 个键的 B-tree 总是具有 \(O(log n)\) 的深度。大多数据库适合 3~4 层的 B-tree。 分支因子为 500 的 4KB 页的四级树可以存储高达 256TB。 可靠性：WAL B-tree 底层的基本写操作是使用新的数据覆盖磁盘上的旧页。 如果发生页分裂则需要覆盖多个不同的页，同时更新父页，这个操作比较危险，如果此时发生崩溃则会破坏索引。 常见的 B-tree 使用额外的数据结构：预写日志(WAL)： 追加的写 WAL； 每个 B-tree 必须先更新 WAL 然后再修改树本身的页。 通过使用「锁存器」保护进行并发控制，保护 B-tree 页被多个线程访问而看到树不一样的状态。 优化 通过复制方案替代 WAL 进行崩溃恢复，修改的页被写入不同的位置，树中父页的新版本被创建，并指向新的位置。 保存键的缩略信息，可以压入更多的键，保持更高的分支因子，减少层数。 对树进行布局，相邻叶子页按顺序保存在磁盘。 添加额外的指针到树中，如左右兄弟页。 变体，如分形树：借鉴日志结构减少磁盘寻道。

索引 先来看一个世界上由 Bash 实现的最简单的数据库实现： #!/bin/bash db_set() { echo "$1,$2" >> database } db_get() { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1 } 这种数据库通过追加文件尾部的方式高效写入，许多数据库内部都是用日志，日志是一个仅支持追加更新的数据文件。但是 db_get 的性能会随着数据量的变大而下降，为了解决这个问题就需要引入新的数据结构： 索引 。 索引是基于原始数据而派生而来的额外数据结构：适当的索引可以加速读取查询，但是回减慢写速度。 key-value 索引通常使用 hash map 来实现，最简单的索引策略：保存内存中的 hash map，把每个键一一映射到数据文件中特定的字节偏移量。 优化磁盘占用 将日志分解成一定大小的段，当文件达到一定大小时就关闭它，并将后续写入到新的段文件中。 然后可以在这些段上执行压缩：丢弃重复的键，并且只保留每个键最近的更新。 同时将变小后的多个段在后台合并在一起（段在写入后不再会进行修改所以不会出现竞争）。 合并完成后将读取请求切换到新的合并段上，然后可以安全的删除旧的段文件。 实现中面临的问题 文件格式：二进制。 删除记录：通过特殊的墓碑标记。 崩溃恢复：Bitcask 通过将 hash map 快照存储到磁盘。 部分写入：文件校验丢弃损坏的部分。 并发控制：只有一个写线程。 追加的好处 顺序写性能高。 并发控制和崩溃恢复简单。 段合并避免文件碎片化。 局限性 大量的键存储在内存可能导致内存耗尽，同时需要处理哈希冲突 区间查询效率不高。

SSTables 通过按照键的顺序存储在日志段文件中来解决哈希索引面临的一些问题。它要求每个键在每个合并的段文件中只能出现一次（通过压缩确保）。 对比哈希索引的日志段 优点 合并段更加高效，即使文件大于可用内存。类似于归并排序算法中使用的方法。并发读取多个输入段文件，比较每个文件的第一个键，把最小的键拷贝到输出文件，并重复。 解决多个段文件重复：保留最新的值，因为每个段包含在某段时间内写入数据库的所有值，意味着肯定有一个值比其他所有值更新。 基于键有序的特性可以采用稀疏索引避免内存中包含所有键的索引。 将一定范围内的所有键存储到一个块中，便于需要请求范围内多个 key-value，降低磁盘 I/O。 构建和维护 保证顺序 内存中痛哦红黑树或者 AVL 树支持任意顺序插入并以排序后的顺序读取它们。 写入时，将其添加到内存中的平衡树数据结构中，成为内存表。 内存表大于某个阈值（MB级别），将其作为 SSTable 文件写入磁盘。写入同时，写入可以继续添加到一个新的内存表实例中。 处理请求顺序：首先从内存表中查找键 -> 最新的磁盘段文件 -> 次新磁盘段文件，以此类推。 后台进程周期性执行段合并与压缩，合并多个段文件并丢弃被覆盖或着删除的值。 崩溃处理 为了避免数据库崩溃最近的写入（在内存表中尚未写入磁盘）将会丢失的问题： 在磁盘上保留单独的日志，每个写入都会立即追加到该日志。并且无需排序。 内存表写入 SSTable 时，丢弃相应的日志。 使用此技术的数据库 LevelDB RocksDB 类似的 Cassandra HBase

tags: Tree 日志结构合并树（Log-Structured Merge-Tree）：基于合并和压缩排序文件原理的存储引擎通常都被称为 LSM 存储引擎。 压缩排序文件基于排序字符串表：SSTables。 LSM-Tree 基本思想：保存在后台并合并的排序字符串表：SSTables。即使数据集远远大于可用内存，仍然能够正常工作。 基于有序的特性，可以有效的执行区间查询，并且由于磁盘是顺序写入，所以 LSM-Tree 可以支持非常高的写入吞吐量。 性能优化 通过布隆过滤器优化 LSM-Tree 查找不存在的键性能低下的问题。 通过大小分级和分层压缩优化 SSTables 压缩和合并时的具体顺序和时机。 大小分级：较新和较小的 SSTables 被连续合并到较旧和较大的 SSTables。 分层压缩：键的范围分裂成多个更小的 SSTables，就数据被移动到单独的“层级”，这样压缩可以逐步进行并节省磁盘空间。

存储引擎 哈希索引 日志结构存储引擎：LSM-Tree 面向页的存储引擎：B-trees 对比 LSM-Tree 和 B-trees 项目 LSM-Tree B-trees 备注 性能 写入更快，吞吐更高 读取更快 具体场景上需要进行基准测试 存储 可变大小的段，通常 nMB 固定大小的页，传统 4KB 写入 追加，写入更多不利于 SSD 新的数据覆盖磁盘上旧的页 并发控制 后台合并进行原子替换 锁存器 其他索引结构 在索引中存储值 多列索引 全文索引和模糊索引 在内存中保存所有内容 优点：可以支持更复杂的数据结构，而无需考虑数据存储结构。 事务处理与分析处理 事务处理：OLTP 分析处理：OLAP 对比 属性 OLTP OLAP 主要读属性 基于键，每次查询返回少量记录 对于大量记录进行汇总 主要写属性 随机访问，低延迟写入用户的输入 批量导入（ETL）或事件流 典型使用场景 终端用户，通过网络应用程序 内部分析师，为决策提供支持 数据表征 最新的数据状态（当前时间点） 随着事件而变化的所有事件历史 数据规模 GB 到 TB TB 到 PB 数据仓库 星型与雪花型分析模式 星型模型也称为维度建模。 列式存储 列压缩

数据模型 关系模型 突出数据之间的关联。 文档模型 数据来自于包含文档，文档间关联很少。 图状数据模型 针对所有数据都可能互相关联。 数据查询语言 Web 上声明式查询 CSS 选择器。 MapReduce 查询 MapReduce 是一种编程模型，用于在许多机器上批量处理海量数据。 MongoDB 中的 MapReduce db.observations.mapReduce( function map() { // 2 var year = this.observationTimestamp.getFullYear(); var month = this.obbservationTimestamp.getMonth() + 1; emit(year + "-" + month, this.numAnimals); // 3 }, function reduce(key, values) { // 4 return Array.sum(values); // 5 }, { query: {family: "Sharks"}, // 1 out: "monthlySharkReport" // 6 } ); 过滤器声明式执行鲨鱼种类（MongoDB 特有扩展）。 mapper：对于每个匹配的文档都会调用一次这个 JavaScript 函数。 mapper 发射一个「键-值」对，键是 “2013-12” 格式的字符串，值是动物的数量 mapper 发射的键值对按键分组，对于相同键的所有「键-值」对，调用 reduce 函数。 reducer 函数将特定月份的所有观察到的动物数量相加。 最终输出写入到 monthlySharkReport 集合中

可靠性 故障与失效 故障（faults）或者错误：组件偏离其正常规格，可以提供容错（fault-tolerant）机制 失效（failure）意味系统作为一个整体停止 硬件故障 软件错误 人为失误 避免优化方式： 以最小出错方式设计系统。抽象、提供管理界面，使“做正确的事很轻松”，防止限制过多。 分离最容易出错的地方，提供沙箱用以放心尝试。 充分测试。 提供快速恢复机制尽量减少故障影响：快速回滚，提供校验数据的工具。 设置详细而清晰的监控系统 培训和流程 可扩展性 描述负载 QPS 数据库写入比例 同时在线活动用户数 缓存命中率等。 描述性能 吞吐量（throughput）/每秒处理数据量 延迟（latency）/响应时间（response time）：延迟是处理时间，响应时间是客户端看到的。 最好通过百分位数来监控指标：p50/p80/p90/p95/p99/p999，p50 指标表示一半请求在这个指标之下，一半在这个指标之上。 应对负载增加 无状态很方便扩容 但有状态的分布式面临一定的挑战 可维护性 可运维性：运维更轻松 监控、文档、自动化、良好的默认配置、可手动控制系统状态让系统自我修复（比如熔断机制）。 简单性：简化复杂度 抽象！ 可演化性：易于改变 TDD 重构

tags: 读书笔记,Bigdata,分布式,数据库 数据系统基础 可靠、可扩展与可维护的应用系统 数据模型与查询语言 数据存储与检索 数据编码与演化 分布式数据系统 目的：扩展性、容错和高可用、延迟考虑（多机房） 扩展： 垂直扩展：提升单机性能 水平扩展：无共享结构，由软件实现核心逻辑 复制与分区： 复制：多节点冗余 分区：数据库拆分 分片：分区分配给不同的节点 数据复制 数据分区 事务 分布式系统挑战 一致性与共识 派生数据 记录系统：真实数据系统，拥有数据的权威版本。 派生数据系统：从另一个数据系统获取，丢失可以根据数据源重建，如缓存等。 批处理系统 流处理系统

tags: 技术随想 几何结构 mobius Klein Trefoil knot Penrose triangle 植物 bonsai broccoli 科幻 tardis dalek 消灭 神话

tags: macOS,macOS Cheatsheet 通常你沟通苹果的官方支持一般都会给你三板斧： 重启：按住电源键 10 秒中，然后等几秒钟后再开机 重置 SMC：关机然后按住：Ctrl + Option + 右侧Shift + 电源键 7 秒钟关机，等待几秒钟后开机。

tags: macOS 查看 TimeMachine 日志： printf '\e[3J' && log show --predicate 'subsystem == "com.apple.TimeMachine"' --debug --last 6m

tags: Learning English 一些通用的规则： 音标后面的 ː 提示拖长音。 元音 大而圆 音标 中文 发音技巧 常见单词 拼读规则 /​æ​/ 爱 张大嘴发中文的「爱」,发音短促有力。 bag map dad sad a /​e​/ 爱 音同 /​æ​/ 但是嘴形要小一些。 get let pen yes e /​ɔː​/ 哦 嘴巴轮圆了发音，并拖长音 floor door store sport oor,ore,or /​ɔ​/ 哦 /​ɔː​/ 的短音 lot dog hot shop o 扁扁扁 音标 中文 发音技巧 常见单词 拼读规则 /iː​/ 一 相比一嘴要扁一些，稍稍更用力一些 see meet he she ee, e /​i​/ 一 /iː​/ 短音 happy daddy honey 词尾的 y 或 ey /​I​/ 一 用 /​e​/ 的嘴形发 /​i​/ this give it city i /əː​/ 呃 相比中文嘴要扁一些，稍稍更用力一些 work girl dirt sir or, ir /​ə​/ 呃 /əː​/ 的短音 again a father weather 单独的 a 及词尾的 er 需要额外注意的： ...

tags: Algorithm,Data Structures,Binary Search Tree 分为三种：前序、后序和中序，其中最容易用栈改写的是后序。 前序(Preorder)：Root -> Left -> Right class Solution { public: void processPreorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processPreorderTraversal(root->left, collector); collector.push_back(root->val); processPreorderTraversal(root->right, collector); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processPreorderTraversal(root, ret); return ret; } }; 中序(Inorder): Left -> Root -> Right class Solution { public: void processInorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processInorderTraversal(root->left, collector); collector.push_back(root->val); processInorderTraversal(root->right, collector); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processInorderTraversal(root, ret); return ret; } }; 后序(Postorder)：Left -> Right -> Root class Solution { public: void processPostorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processPostorderTraversal(root->left, collector); processPostorderTraversal(root->right, collector); collector.push_back(root->val); } vector<int> postorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processPostorderTraversal(root, ret); return ret; } }; 非递归遍历 【刷题】二叉树非递归遍历

tags: Taking Notes, Org Mode 方案一：通过 Emacs 批处理模式 emacs file.org --batch -f org-hugo-export-wim-to-md --kill --batch 默认不启用配置文件，可以使用 -l emacs file.org --batch -l ~/.emacs.d/init.el -f org-hugo-export-wim-to-md --kill 方案二：通过 LISP 遍历 (mapc (lambda (x) (with-current-buffer (find-file-noselect x) (org-hugo-export-wim-to-md t))) (directory-files "/Users/wh/codes/notes/roam-research-notes-hugo/journal" nil "^[0-9]+$" t))

tags: 技术，技术概念 中间件可以对系统进行解耦，比如上层系统对下层系统进行网络请求，考虑下面结构 - U - / | \ /--- | ---\ / | \ A B C 如果下层系统增加节点的话就需要重启 U。 引入 HAProxy 或者 Nginx 之类的中间件可以对两层系统进行解耦： U | +------+ | HA | +------+ / | \ /--- | ---\ / | \ A B C 这样上层和下层系统都依赖中间件，但是系统之间不再强耦合，下层系统可以依赖中间件随意的进行所扩容而不用被上层系统感知。 这时候中间件只要保证中间件稳定即可，可以在中间件上进行热重启。

项目代号 技术概念

tags: C/C++ source: All about thread-local storage

tags: macOS fix “Too many open files in system” error

tags: GDB thread apply all bt

tags: Emacs,LSP,C/C++,CMake 通过如下命令生成 clangd 识别的编译配置文件 mkdir build cd build cmake -DCMAKE_EXPORT_COMPILE_COMMANDS=1 .. mv compile_commands.json ../ 然后重启 M-x lsp-restart-workspace RET 即可。

tags: Translate,Incomplete,Python Python 幕后 #2: CPython 编译器如何工作 今天的主题（Today’s subject） 在本系列的第一篇文章中我们研究了 Python 虚拟机。我们学了解到它通过执行一系列叫做字节码（bytecode）的指令。 我们也看到 Python 字节码没有完全描述代码片段的行为。这也是为什么存在一个代码对象（code object）的概念。 执行诸如函数或模块的代码块也就是执行对应的代码对象。代码对象包含了代码块的字节码，包含代码中使用的常量和变量名， 还有代码块的一些属性。 通常，一个 Python 程序员不用编写字节码，并且也不用创建代码对象，而是编写正常的 Python 代码。所有 CPython 必须 能够将源代码转换成代码对象。CPython 编译器就负责这部分工作。我们将通过这部分内容探索它是如何工作的。 Note: 本文参考 CPython 3.9。一些实现细节将必然会随着 CPython 的演进而改变。 我将会尝试关注一些重要的改变并添加更新备注。 什么是 CPython 编译器（What CPython compiler is） 我们已经了解了 CPython 编译器的职责，但是在我们进入到它是如何实现的之前，让我们首先来搞清楚为什么我们称之为编译器？ 在通常情况加，编译器是一个将一个程序语言翻译到另一个与之等价的程序语言的程序。编译器有许多种类，但是通常情况下我们 讨论的都是静态编译：将一个高级语言的程序翻译成机器码。CPython 编译器也是这样吗？要回答这个问题，我们先看一下静态编 译器的传统三阶段设计（three-stage design）。 编译器前端（frontend）将源代码转换成一种中间语言（IR,intermediate representation）。然后优化器（optimzer）拿到中间语言 对其进行优化并把优化过的中间语言传递给编译器后端生成机器码。如果我们选择一种源语言和目标机器无关的中间语言，我们就 得到了三阶段设计的关键益处：对于一个编译器来说，支持一种新的源语言仅仅需要新增一个对应的编译器前端，支持一种新的目标机器 仅仅需要新增一个对应的编译器后端。 LLVM 工具集（toolchain）就是这个模型的一个很好的成功的例子。有很多编译器前端如 C、Rust、Swift 等其他很多编程语言基于 LLVM 提供给编译器更加复杂的部分。LLVM 的创建者 Chris Latter 提供了一个很好的 LLVM 架构概览。 CPython 尽管不需要支持多个源语言和目标机器，尔仅仅需要支持 Python 代码和 CPython 虚拟机。不过，CPython 同样实现了三阶段设计。 如果想知道为什么，我们需要更加详细的解释编译器的三阶段的每个阶段。 ...

tags: Emacs M-x straight-thaw-versions RET 恢复到锁定的版本 M-x straight-pull-all RET 更新所有包 M-x straight-freeze-versions RET 锁定当前版本 Duplicated with straight.el 更新所有已安装的包

straight-thaw-versions straight-pull-all straight-freeze-versions

tags: Emacs source: https://www.gnu.org/software/emacs/manual/html%5Fnode/emacs/Uniquify.html

具有“长度”概念的函数。在线性代数、泛函分析等相关数学领域，是一个函数，其为向量空间内所有向量赋予非零的正长度或大小。

\[MAE(X,h) = \frac{1}{m}\sum_{i=1}^{m}\left\lvert h(x^{(i)} - y ^{i})\right\rvert\]