爬虫 # import requests from bs4 import BeautifulSoup prefix = 'http://mysql.taobao.org' # 获取文章名和url（文章名,url） def query_name_url(url: str): resp = requests.get(url) soup = BeautifulSoup(resp.content.decode('utf-8'), "html.parser") tags = soup.findAll('a', {'target': {'_top'}}) urls = [v for v in tags if v['href'].find('/monthly/') != -1] return [(str(v.string).strip(), prefix + v['href']) for v in urls] # 获取所有月报链接（月报名,url） def query_monthly_url(): resp = requests.get('http://mysql.taobao.org/monthly/') soup = BeautifulSoup(resp.content.decode('utf-8'), "html.parser") tags = soup.findAll('a', {'class': {'main'}}) urls = [v for v in tags if v['href'].find('/monthly/') != -1] return [(str(v.string).strip(), prefix + v['href']) for v in urls] # 获取所有文章名、URL和对应的月报链接（文章类型，文章名，url，月报名，url） def query_all_name_url(): result = [] monthly_urls = query_monthly_url() for data1 in monthly_urls: name_urls = query_name_url(data1[1]) for data2 in name_urls: result.

https://15445.courses.cs.cmu.edu/fall2021/notes/02-advancedsql.pdf output control 控制输出结果，例如order，limit等 窗口函数 CTE Common Table Expressions，把一个语句的输出视为一张临时表参与下面的语句的运算 WITH cte1 (col1) AS (SELECT 1), cte2 (col2) AS (SELECT 2) SELECT * FROM cte1, cte2; Database Storage # 数据库的存储介质当前还是磁盘，IO慢 数据库存储要点之一是使用缓存维护数据在磁盘和内存之间的数据交换，以实现数据的快速读写 顺序读写和随机读写 顺序读写的意思是需要定位到读写的位置才能操作，例如链表。 随机读写的意思是可以直接定位到读写的位置，例如数组。 由于磁盘上随机读写速度不如顺序读写，所以当前数据库还是需要想办法使用顺序读写，例如LSM，GFS等架构都是因为这个原因导致的 磁盘和内存中数据的组织格式 # 数据全部在磁盘上，按page组织数据，内存中使用buffer pool维护缓存，磁盘中有一个page专门维护page的位置信息，使用的时候先读取此page到内存，然后 然后读取其他page到buffer pool，使用buffer pool维护page的置换情况，例如LRU，或者其他算法 可以参考lab1和slide，还是比较明显的 buffer pool中的page可以用于上层的数据运算 使用mmap可以完成类似的操作，但是实际上在使用中，如果在发生缺页中断的时候，mmap需要进行置换操作，所以会阻碍程序进程。且mmap是通用的组件，所以没有对数据库 的使用场景进行一些优化， You never want to use mmap in your DBMS if you need to write. The DBMS (almost) always wants to control things itself and can do a better job at it since it knows more about the data being accessed and the queries being processed. The operating system is not your friend. 最好是需要什么就自己实现什么， 数据组织形式 # 文件

译文 原文 有用的飞书文档 和其他的算法相比 Strong leader 日志只能从领导者发送到其他节点 Leader election 随机计时器选举领导，在心跳机制上加上一些额外的工作 Membership changes 角色变换 Replicated state machines # 复制状态机一般基于日志实现，通俗的理解只要所有的机器按照相同的顺序执行指令，那么每个节点的状态都是确定的，所以需要把指令日志复制到其他节点上去，这就是一致性算法的工作 如果只是要求最终所有的节点都执行一样顺序的指令，而不要求实时性，则可以限定 只有一个节点可以进行写操作，因为只有写操作才可以改变系统的状态 写节点同步指令到其他节点，最终所有节点指令顺序一致 一致性算法的共有特性 安全性 不会返回一个错误结果，只要是在非拜占庭错误情况下，包括网络延迟，乱序，丢包，分区，冗余等都可以保障正确性 可用性 集群只要大多数机器可以正常通信，就可以确保可用，失败节点可以忽略或者后续恢复状态，大多数指的是半数以上 不依赖时序保证一致性 时钟错误或者消息延迟只有在极端情况下才会导致可用性 慢节点不会影响消息的反馈，消息可以快速的响应 拜占庭将军问题 Paxos # 难以理解 没有公认的可以实现的基础架构，大部分系统从Paxos开始，在遇到问题的时候自行想办法解决，导致最后的系统实现只能是类似Paxos的算法 Raft # 管理复制状态机的一种算法，他会在集群中选举一个leader，之后会复制所有的日志到其他节点实现一致性 他可以分解为三个问题 领导选举 一个新的领导人需要被选举出来，当先存的领导人宕机的时候 日志复制 领导人必须从客户端接收日志然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同 安全性 在 Raft 中安全性的关键是在图 3 中展示的状态机安全：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令 可以在这个网站查看实例 节点有三种状态 Follower Candidate Leader 他们之间的转换关系如下图 任期在 Raft 算法中充当逻辑时钟的作用，这会允许服务器节点查明一些过期的信息比如陈旧的领导者。每一个节点存储一个当前任期号，这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号；如果一个服务器的当前任期号比其他人小，那么他会更新自己的编号到较大的编号值。如果一个候选人或者领导者发现自己的任期号过期了，那么他会立即恢复成跟随者状态。如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。 下面是详细的细节参数 下面的参数要求在节点上持久存在 currentTerm 服务器最后一次知道的任期号，初始化为 0，持续递增 votedFor 当前获得选票的候选人的Id log[] 日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的任期号 下面的参数在节点上是随时变化的 commitIndex 已知的最大的已经被提交的日志条目的索引值 lastApplied 最后被应用到状态机的日志条目索引值，初始化为 0，持续递增 下面的参数需要在leader重新选举之后变化的 nextIndex[] 对于每一个服务器，需要发送给他的下一个日志条目的索引值，初始化为领导人最后索引值加一 matchIndex[] 对于每一个服务器，已经复制给他的日志的最高索引值 这篇图表示的是rpc的参数信息以及返回值，由领导人负责调用来复制日志指令；也会用作heartbeat 参数 term 领导人的任期号 leaderId 领导人的 Id，以便于跟随者重定向请求 prevLogIndex 新的日志条目紧随之前的索引值 prevLogTerm prevLogIndex 条目的任期号 entries[] 准备存储的日志条目，表示心跳时为空；一次性发送多个是为了提高效率 leaderCommit 领导人已经提交的日志的索引值 返回值 term 当前的任期号，用于领导人去更新自己 success 跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真 如果 term < currentTerm 就返回 false 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false 如果已经已经存在的日志条目和新的产生冲突（相同偏移量但是任期号不同），删除这一条和之后所有的 附加任何在已有的日志中不存在的条目 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个 由候选人负责调用用来征集选票

利用普通机器组成的大规模计算集群进行并行的,高容错,高性能的数据处理函数框架 原始论文点这里,论文翻译点这里，有时间的话，自行对比翻译和原文 最终实现的目标是–实现一个分布式系统，对程序员隐藏底层分布式细节，程序员只需要定义map和reduce 函数即可。 map reduce实现为简单的kv输出，其中map接受源数据，生成kv的中间结果，中间结果保存在worker节点上。 reduce负责处理map产生的中间结果的kv数据，只是简单的数据处理过程. 他最先是受到lisp中map和reduce原语的启发，再加上当时Google现实的处理大量数据的需求，从他们现有的系统抽象而来的。 在论文中，使用了一个单词统计的案例，此时实现map函数用来分割文本，切分出最基本的单词。然后再使用reduce进行聚合操作， // 输出单词以及出现的次数，map端输出1 map(String key,String value): // key: 文档名 // value: 文档内容 for each word w in value: EmitIntermediate(w,"1"); // 针对相同的key，次数+1 reduce(String key, Iterator values): // key: 一个单词 // value: 计数值列表 int result = 0; for each v in values: result += ParseInt(v); Emit(AsString(result)); 执行过程 文件划分 主节点划分任务 按照划分的任务启动worker，执行map任务 worker节点的数据生成为中间结果，保存在本节点 所有map任务执行完成之后，reduce得到对应中间节点的文件路径，通过rpc读取文件，进行reduce任务 reduce任务完成之后，最终结果写入目标文件 一个mr任务完成之后，回得到n(reduce)个结果文件，可以按照需求处理文件，可以直接使用，或者继续作为其他mr的输入，mr任务是可以嵌套的。 主节点 记录map和reduce任务的状态，例如是否开始，是否结束，执行时间等 协调工作节点，确定工作状态。确定任务是否需要重试，是否需要back up等 容错性 工作节点失败 主机点定时检测工作节点状态，如果无法链接，此时需要把此丢失的工作节点上的所有的任务重新安排到其他节点上执行。包括已完成的map任务，因为mr任务是需要等所有map任务结束之后才能执行reduce任务，其map任务的数据在保存在worker节点上的。所以需要重新执行map任务。至于reduce任务，由于他的输出之最终的数据结果，且需要记录到文件。所以为了避免重复的数据产生，已完成的reduce任务不重试，前提是输出数据已经保存到其他节点上。 主节点错误 一般是直接重试整个mr任务，因为mr的主节点应该是需要选择集群中比较可靠的节点，此时有理由怀疑其他节点也可能出现问题，所以此时选择整个重新执行，当然也可以恢复主节点，从记录的回复点重新执行 backup task mr中由于任务切分不一定均衡或者不同节点计算能力不同，有的任务执行格外慢，此时可以在其他空闲节点上执行相同的任务，此时集群中可能有多个相同的任务，最终哪一个任务先完成，主节点就会终止其他未完成的工作节点。 上面就是原始的mr描述，理所当然的可以想到一些提升的地方 平均的划分任务文件，尽量任务均衡 流式计算，在中间结果产生的时候，直接保存中间文件到reduce节点，避免最后集中处理中间结果时候的网络带宽消耗 本地计算mr，有的mr任务没必要在不同节点上执行，直接划分到一个节点或把的某些任务划分到一个节点上，实现本地计算。避免网络IO 提前进行reduce操作，可以使用reduce任务提前处理中间结果，减少中间结果的大小 记录计算节点的状态，多次执行任务的时候，可以记录某节点的处理速度，在下一个mr任务划分的时候，按照此信息划分任务 https://www.zhihu.com/question/303101438 map和reduce之间是完全串行的，如果有多个MR任务嵌套的话，由于每个mr必须实现map和reduce，会导致链路过长，实现和调试困难 性能无法达到要求 6.824 LAB # 先掌握go，重点为go的协程，管道，以及channel 代码框架已经给出来了，需要自己实现分布式的worker和master 可以先实现简单的无状态的mr，可以通过test-mr.sh中的前面的测试 worker # map和reduce的执行节点，需要从master获得任务，按照任务的类型，执行不同的job func Worker(mapf func(string, string) []KeyValue, reducef func(string, []string) string) { for { job := getJob() if job.

2022-05-17 基础语法 2022-05-24 复合类型，goroutine，channel 基础语法 # Packages # go使用Packages维护模块，使用import导入模块，import最后一个元素才是需要导入的模块 import ( "fmt" "math/rand" ) import 可以单独一个导入一个模块，也可以批量导入， 与之对应的是export，go不显示声明export，首字母大写的变量或方法自动export，外部只能使用导出的变量或者方法，类似c++中类的私有和共有的概念。 Functions # 与c++或者Java或者其他语言不同的是，go的函数签名格式为func func_name(parm1 [type], parm2 [type]....) retype {}，先声明名字，再声明变量的类型，参数列表中有多个参数且类型一致的时候，前面的参数类型可以省略，只需要保留之后一个 func add(x, y int) int { return x + y } 且go可以很轻易的实现多返回值的功能，如下 func swap(x, y string) (string, string) { return y, x } func main() { a, b := swap("hello", "world") fmt.Println(a, b) } 上面的功能在c++中需要使用结构体或者tuple或者Paris才能实现。 go的return还可以使用不带参数的 “naked” return，此时要求函数签名中的return参数必须有名字，且在函数体中必须为参数赋值，此时使用return直接返回，参数可以直接传递到外部，但是需要注意的时候，如果函数体过于庞大且有多个出口，不建议使用，难于阅读 func split(sum int) (x, y int) { x = sum * 4 / 9 y = sum - x return } 变量 # 使用var声明变量，声明多个变量的时候可以类似参数列表中的参数，前面参数不需要声明类型。初始化的时候按顺序初始化，且初始化的参数个数必须前后一致 var i, j, k int = 1,2,0 // true var i, j, k int = 1,2 // false 初始化的时候还可以省略类型，程序会进行参数推导。 函数内部还可以使用 :=替换var声明变量，此时必须初始化，但是在函数体外部，由于go规定，每条语句必须由特定的关键字开头，所以外部不可使用此语法。

随堂笔记 # Why do people build distributed systems? to increase capacity via parallel processing to tolerate faults via replication to match distribution of physical devices e.g. sensors to achieve security via isolation 分布式的困难点： 大量的并发操作 具有容错性 难于实现 Lab 1: distributed big-data framework (like MapReduce) Lab 2: fault tolerance library using replication (Raft) Lab 3: a simple fault-tolerant database Lab 4: scalable database performance via sharding A big goal: hide the complexity of distribution from applications. Topic: fault tolerance 1000s of servers, big network -> always something broken We’d like to hide these failures from the application. “High availability”: service continues despite failures

leveldb 源码总结分析

NOTE # 论文阅读笔记The Volcano Optimizer Generator: Extensibility and Efficient Search 可扩展 面向对象 自顶向下 剪枝 原型是EXODUS， Volcano是对他的改进 可以单独使用的优化器 优化搜索时间和搜索空间 可扩展 可以使用启发式算法和有效的代价模型来扩展和减少搜索空间，【剪枝】 灵活的成本计算模型 一个框架，优化器生成器，可以由“optimizer implementor”自行实现关键函数，整个优化器框架的输入是AST，输出是一个执行计划，算子的集合 SQL是基于关系代数，Volcano把关系表达式分为逻辑表达式和物理表达式，逻辑表达式之间使用transformation进行转换，物理表达式使用基于代价的implementation和逻辑表达式映射的，关系不一定是意义对应的，例如scan可以同时一起实现projection 在表达式进行转换的时候可以使用condition进行模式判断，满足条件的时候可以进行变换 表达式使用特征描述输出， enforcers会强制添加某属性，用于指导优化器进行优化，例如指定表的scan方式 Logical Operator Operator set，也就是可以描述在目标data model上可以执行的代数运算合 Transformation rules + Condition，对每条等价变换规则，在满足condition时才可以应用 Logical properties : 逻辑属性，用来描述代数运算的输出所具有的一些特征，这些特征与运算的具体执行方式无关，是逻辑的，例如输出的行数，结果集的schema等 Physical Operator Algorithm + Enforcer set，即可应用的物理实现算法 + 可添加的Enforcer集合 Implementation rules + Condition，满足Condition的前提下，可以尝试该物理算法 Cost model + Cost formula，基于cost选择最优的物理算法 Physical property，与logical property对应，物理属性是选择了特定的算法实现后，输出的数据所具有的物理上的特性，例如数据是否有序、是否具有唯一性，数据在多机上的分布情况等，不同的物理算法，会决定执行该operator产生的物理属性，例如sort merge join会在join key上产生有序属性 Applicability function : 决定一个物理算法，其输出是否可以满足要求父算子对自身的physical property要求，且决定它对自身的输入具有什么样的physical property要求 Enforcer是search engine中一个重要的概念，它用来强制产生某种物理属性。例如上层是join算子，在枚举时会考虑使用sort merge join的物理执行方式(Implementation），但当递归到下层时，子节点可以选择table scan（无序输出），或者index scan（目标序输出），当选择table scan时，由于输出不满足父算子对自身输出的物理属性要求，就可以通过Order Enforcer来产生目标输出，Enforcer表示了排序这个操作，同时也包含了排序操作会产生的代价。 The Search Engine # 搜索实现 // PhysProp：： 此LogExpr锁具有的物理属性的要求 FindBestPlan (LogExpr, PhysProp, Limit) // 如果可以在look-up table找到满足的计划，则代表以及算过，直接返回 if the pair LogExpr and PhysProp is in the look-up table if the cost in the look-up table < Limit return Plan and Cost else return failure /* else: optimization required */ // 否则进行优化，由三种优化方式 // 1.