LegGasai's CSLearning

创建型模式结构型模式行为模式参考策略设计模式 (refactoringguru.cn)

简介分布式事务是指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于不同的分布式系统的不同节点之上。在分布式系统中，可能涉及到多个参与者，每个参与者负责管理自己的本地数据。分布式事务的目标是确保在整个分布式环境中，所有相关的操作要么全部成功，要么全部失败，以保持数据的一致性。（All or nothing） 基本理论CAP理论CAP是 Consistency、Availability、Partition tolerance三个词语的缩写，分别表示一致性、可用性、分区容忍性。 一致性(Consistency) ：更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致，不能存在中间状态。（这里指强一致性） 可用性(Availability) ： 系统提供的服务必须一直处于可用的状态，对于用户的每一个操作请求总是能够在有限时间内返回结果。 **分区容错性(Partition tolerance) **：分布式系统在遇到任何网络分区故障时，仍然需要能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境都发生了故障。 任何一个分布式系统都无法同时满足一致性（ ...

一、基本概念1.1 概念串行、并行、并发串行：多个程序按序执行。上一个做完，接着做下一个。并行：多个程序同时执行，一般需要多核处理器的支持。并发：多个程序交错执行，就像看上去是同时执行的一样。 同步异步、阻塞非阻塞同步和异步：当前线程是否需要等待方法调用执行完毕。 1234567891011121314// 同步isFinished = doTask();// wait for finished if isFinished{ // 任务完成}// 异步doTask({ // 任务完成 // 执行回调 send a message}) 在异步调用下的代码逻辑相对而言不太直观，需要借助回调或事件通知，这在复杂逻辑下对编码能力的要求较高。而同步调用就是直来直去，等待执行完毕然后拿到结果紧接着执行下面的逻辑，对编码能力的要求较低，也更不容易出错。所以你会发现有很多方法它是异步调用的方式，但是最终的使用还是异步转同步。比如你向线程池提交一个任务，得到一个future，此时是异步的，然后你在紧接着在代码里调用 future.get()，那就变成等待这个任务执 ...

简介课程网站：https://pdos.csail.mit.edu/6.828/2021/schedule.html 课程翻译：https://mit-public-courses-cn-translatio.gitbook.io/mit6-s081/ 课程Lecture1Lecture3隔离性（isolation)不同应用程序进程之间应该相互独立。假设不存在操作系统层，应用程序直接和硬件进行交互。会产生CPU调度问题（某个应用程序一直占用CPU，其他应用无法被调度）、内存安全问题（应用程序修改了其他应用程序的内存数据） 应用程序不能直接与CPU交互，只能与进程交互。操作系统内核会完成不同进程在CPU上的切换。所以，操作系统不是直接将CPU提供给应用程序，而是向应用程序提供“进程”，进程抽象了CPU，这样操作系统才能在多个应用程序之间复用一个或者多个CPU。 多个进程同一时间不可以使用同一个CPU核，一般都是分时复用。 fork抽象了CPU、exec抽象了内存、files抽象了磁盘。理解这些系统调用的抽象和隔离性。 防御性（Defensive)需要考虑应用程序不能通过某些恶意手段使得操 ...

介绍在这个实验中，你将实现基于日志的回滚（rollback）用于撤销操作和基于日志的崩溃恢复。我们为你提供了定义日志格式并在事务期间在适当的时候向日志文件附加记录的代码。你将使用日志文件的内容来实现回滚和恢复。 我们提供的日志代码生成用于物理整页撤销和重做的记录。当首次读取页面时，我们的代码将原始内容记住为一个前镜像。当事务更新页面时，相应的日志记录包含该记住的前镜像以及修改后的页面内容作为后镜像。在中止期间，你将使用前镜像进行回滚，并在恢复期间撤销失败的事务，而使用后镜像在恢复期间重做成功的事务。 我们之所以能够使用整页物理撤销（而 ARIES 必须进行逻辑撤销）是因为我们使用页面级别的锁定，并且因为我们没有可能在 UNDO 时具有与初始写入日志时不同结构的索引。页面级别锁定简化了事情的原因在于，如果一个事务修改了一个页面，它必须拥有它的独占锁定，这意味着没有其他事务在同时修改它，因此我们可以通过简单地覆盖整个页面来 UNDO 对它的更改。 你的 BufferPool 已经通过删除脏页来实现中止，并通过仅在提交时将脏页强制写入磁盘来模拟原子提交。日志记录允许更灵活的缓冲区管理（STE ...

介绍在这个实验中，你将实现一个B+树索引，用于高效的查找和范围扫描。我们已经为你提供了所有需要实现树结构的底层代码。你将实现搜索、页面分裂、在页面之间重新分配元组以及页面合并。 阅读教材中的第10.3至10.7节可能会对B+树的结构以及搜索、插入和删除的伪代码有详细的了解，这可能对你有所帮助。 正如教材和课堂上讨论的那样，B+树中的内部节点包含多个条目，每个条目由一个键值、一个左子指针和一个右子指针组成。相邻的键共享一个子指针，因此包含m个键的内部节点有m+1个子指针。叶子节点可以包含数据条目，也可以包含指向其他数据库文件中的数据条目的指针。为了简化起见，我们将实现一个B+树，其中叶子页面实际上包含数据条目。相邻的叶子页面通过右和左兄弟指针链接在一起，因此范围扫描只需要通过根和内部节点进行一次初始搜索，以找到第一个叶子页面。随后的叶子页面通过跟随右（或左）兄弟指针找到。 任务Search查看index/和BTreeFile.java。这是B+树实现的核心文件，也是你在本实验中编写所有代码的地方。与HeapFile不同，BTreeFile由四种不同类型的页面组成。正如你所预期的那样，树的 ...

介绍在本实验中，您将在 SimpleDB 中实现一个简单的基于锁的事务系统。您需要在代码的适当位置添加锁和解锁调用，并添加代码来跟踪每个事务持有的锁，并在需要时向事务授予锁。 本文档的其余部分将介绍添加事务支持所涉及的内容，并提供如何在数据库中添加该支持的基本概要。 与前一个实验室一样，我们建议您尽早开始。锁定和事务的调试可能相当棘手！ 概念在开始之前，您应该确保了解什么是事务，以及严格的两阶段锁（您将使用它来确保事务的隔离性和原子性）是如何工作的。 在本节的其余部分，我们将简要概述这些概念，并讨论它们与 SimpleDB 的关系。 Transactions事务是一组以原子方式执行的数据库操作（如插入、删除和读取），也就是说，要么所有操作都完成，要么一个操作都没完成，而且数据库外部观察者不会发现这些操作不是作为一个不可分割的单一操作的一部分完成的。 ACID为了帮助您了解事务管理在 SimpleDB 中的工作原理，我们将简要回顾它是如何确保满足 ACID 属性的： 原子性：严格的两阶段锁定和谨慎的缓冲区管理可确保原子性。 一致性：由于原子性，数据库具有事务一致性。其他 ...

介绍在这个实验中，您将在 SimpleDB 的基础上实现一个查询优化器。主要任务包括实现一个选择性估算框架和一个基于成本的优化器。您在具体实现方面有一定的自由度，但我们建议使用类似于课堂上讨论的 Selinger 基于成本的优化器（第9讲）。 本文档的其余部分描述了添加优化器支持所涉及的内容，并提供了如何进行的基本概述。 与之前的实验一样，我们建议您尽早开始。 提示 实现 TableStats 类中的方法，使其能够使用直方图（为 IntHistogram 类提供了框架）或您设计的其他形式的统计信息，估算过滤器的选择性和扫描成本。 实现 JoinOptimizer 类中的方法，使其能够估算连接的成本和选择性。 编写 JoinOptimizer 中的 orderJoins 方法。该方法必须针对一系列连接（可能使用 Selinger 算法），根据在前两个步骤中计算的统计信息生成最佳的连接顺序。 优化大纲请记住，基于成本的优化器的主要思想是： 利用关于表的统计信息来估算不同查询计划的“成本”。通常，计划的成本与中间连接和选择所产生的元组数量（基数），以及过滤和连接谓词的选择性相关。 利用这 ...

介绍在这个实验任务中，你将编写一组SimpleDB的运算符，用于实现表的修改（例如，插入和删除记录）、选择、连接和聚合操作。这些操作将在Lab 1中构建的基础之上，为你提供一个能够在多个表上执行简单查询的数据库系统。 此外，在Lab 1中我们忽略了缓冲池管理的问题：我们没有处理在数据库的生命周期内引用超过内存容量的页面时会出现的问题。在Lab 2中，你将设计一种逐出策略，以将陈旧的页面从缓冲池中清除。 在这个Lab中，你不需要实现事务或锁。 提示实现Filter和Join运算符，并验证它们相应的测试是否有效。这些运算符的Javadoc注释包含了它们应该如何工作的详细信息。我们已经为你提供了Project和OrderBy的实现，这可能有助于你理解其他运算符的工作原理。 实现IntegerAggregator和StringAggregator。在这里，你将编写实际计算在一系列输入元组中跨多个组对特定字段执行聚合的逻辑。对于计算平均值，使用整数除法，因为SimpleDB只支持整数。StringAggregator只需要支持COUNT聚合，因为其他操作对于字符串来说没有意义。 实现Aggreg ...

介绍课程官网：6.5830/6.5831: Lecture Notes and Assignments (mit.edu)项目仓库：MIT-DB-Class/simple-db-hw-2021 (github.com) 理论Lecture5Buffer Pool Optimizations Lecture7Basic Join Summary上面的图列举了将两个表进行join操作时，CPU和I/O的开销。{R}指表R中行数，|R|指表R在磁盘上存储的页面数，如果每页存B条记录，则|R|={R}/B。 External Join Summary Lecture8Query Optimization Objective 谓词下推（Predicate Pushdown)：将尽可能多的判断更贴近数据源，以使查询时能跳过无关的数据。用在SQL优化上来说，就是先过滤再做聚合**等操作。 Lecture10Transaction: Begin：在开始修改数据库的SQL语句之后 Commit：使事务生效，即持久化到磁盘中，对其他事 ...