USC CSCI-585 notes

E-R

什么是实体-关系模型？

实体-关系模型，简称 E-R 模型，是基于一个简单的理念：现实世界由实体 (entities) 和 关系 (relationships) 组成。这个模型帮助我们把现实世界中的事物抽象成数据库中的结构。

1. 实体 (Entities)

• 定义：实体是客观存在且可以与其他事物区分开来的“东西”。这些“东西”可以是具体的，比如一个学生（Joe），也可以是抽象的，比如一支橄榄球队（SF-49ers）。
• 属性 (Attributes)：每个实体都有一组属性来描述它的特性。比如，一个名为 Joe 的实体可以有 social-security number、phone number 和 salary 等属性。属性是把实体映射到某个值域的函数。
• 实体集 (Entity Set)：同一类型的实体集合被称为实体集。例如，所有的橄榄球队可以组成一个实体集。

2. 关系 (Relationships)

• 定义：关系是两个或多个实体之间的联系。比如，“Joe 是 SF-49ers 的球迷”就是一个关系。
• 关系集 (Relationship Set)：同一类型的关系集合被称为关系集。
• 关系也有属性：一个关系集也可以有自己的属性。比如，PROJECT-WORKER（项目-工人）这个关系集可以有一个 PERCENTAGE-OF-TIME（所占时间百分比）的属性。这个属性既不属于 EMPLOYEE 也不属于 PROJECT 实体，因为它的含义取决于员工和项目两者。

E-R 模型中的重要概念：键 (Keys)

在 E-R 模型中，键是用来唯一标识实体和关系的属性组合。

• 键 (Key)：一个或多个属性的组合。比如，social-security number 或 name 和 social-security number 的组合都可以作为键。

• 超键 (Superkey)：任何能够唯一标识一个实体或关系集的键都是超键。例如，

  social-security number、phone number 或 name 和 social-security number 的组合都是超键。

• 候选键 (Candidate Key)：能够唯一标识实体或关系集的最小超键。

  social-security number 和 phone number 都可能是候选键。

• 主键 (Primary Key)：数据库设计者从候选键中选定的一个键，用来唯一标识实体集中的实体。主键通常被用来在插入和更新操作中检查数据的唯一性。

• 外键 (Foreign Key)：外键是一个或多个属性的集合，用于构建弱实体集的区分符。弱实体集的主键由其所依赖的强实体集的主键构成。

强实体集与弱实体集

• 强实体集 (Strong Entity Set)：拥有主键的实体集称为强实体集。

• 弱实体集 (Weak Entity Set)：没有足够属性来形成主键的实体集。弱实体集的存在必须依赖于一个识别性或所有者实体集。eg：DEPENDENT（员工的家属）不能只用名字唯一标识，因为很多员工可能都有家属叫 “John”。所以 DEPENDENT 的主键 = (EMPLOYEE-NO, DEPENDENT-NAME)。

E-R 模型与传统模型的比较

E-R 模型可以作为统一不同数据模型的基础，例如网络模型、关系模型和实体集模型。

• 网络模型：网络模型通过分离实体和关系来提供更自然的数据视图。

• 关系模型：关系模型基于关系理论，提供了更高程度的数据独立性。关系模型由一系列表格组成，每个表格都有一个唯一的名称。

• 实体集模型：实体集模型的基本元素是实体。与 E-R 模型不同的是，实体集模型将所有事物都视为实体，包括值。这可能会导致语义上的歧义。此外，实体集模型只使用二元关系，而 E-R 模型可以使用 N 元关系。

E-R 模型图 (E-R Diagram)

E-R 模型使用一种特殊的图表技术作为数据库设计的工具。

• 实体：通常用矩形表示。
• 关系：通常用菱形表示。
• 属性：用椭圆形表示。
• 连接：线条连接实体和关系。

在关系图中，你还可以用特定的符号来表示额外的约束：

• 双线：表示完全参与（Total Participation）。这意味着一个实体集中的所有成员都必须参与到某个关系中。例如，在“People 喜欢 Football Teams”的关系中，双线表示所有人都必须是某个球队的球迷。

• 基数（Cardinality）：表示两个实体集之间的映射约束，例如 1:1, 1:N, N:1, M:N。

押题

1. 基础概念 (Basic Concepts)

• EN: Define the core components of the Entity-Relationship model: Entity, Entity Set, Relationship, Relationship Set, and Attribute. Explain the difference between an attribute and a value set.
• 中文: 定义实体-关系模型的核心组成部分：实体、实体集、关系、关系集和属性。并解释属性（Attribute）和值集（Value Set）之间的区别。

答案: 实体-关系模型的核心组成部分包括：

• 实体 (Entity): 一个客观存在且可以被明确识别的“事物”或对象。
• 实体集 (Entity Set): 具有相同类型或属性的实体的集合。例如，所有员工构成一个“员工”实体集。
• 关系 (Relationship): 两个或多个实体之间的关联。一个关系是n个实体的元组 [e₁, e₂, ..., eₙ]，其中每个实体 eᵢ 来自一个实体集 Eᵢ。
• 关系集 (Relationship Set): 相同类型关系的集合。
• 属性 (Attribute): 一个将实体集或关系集映射到一个或多个值集的函数。它用于描述实体或关系的特性。

属性和值集是不同的概念。属性是一个函数，它将一个实体映射到一个值。值集则包含了特定类型的值。多个不同的属性可以映射到同一个或同一组值集。例如，NAME 和 ALTERNATIVE-NAME 是两个不同的属性，但它们都从 EMPLOYEE 实体集映射到 FIRST-NAME 和 LAST-NAME 这两个值集。

2. 弱实体集 (Weak Entity Sets)

• EN: What is a weak entity set, and how does it differ from a strong entity set? Explain the roles of an identifying relationship and a discriminator in the context of a weak entity set.
• 中文: 什么是弱实体集，它与强实体集有何不同？请解释在弱实体集的背景下，标识关系（identifying relationship）和分辨符（discriminator）的作用。

答案:

• 弱实体集 (Weak Entity Set): 是一个没有足够的自身属性来形成主键的实体集。它的存在依赖于一个“所有者”或“标识”实体集。
• 强实体集 (Strong Entity Set): 是一个拥有主键的实体集。

弱实体集与强实体集通过一个标识关系 (identifying relationship) 相关联。这个关系对于弱实体集来说是多对一的，并且弱实体集在其中的参与是完全的（total participation）。

分辨符 (discriminator) 是弱实体集自身的属性，用于在与同一个强实体关联的一组弱实体中区分彼此。弱实体集的主键是由其所依赖的强实体集的主键（作为外键）与它自身的分辨符组合而成的。例如，员工的“家属”是一个弱实体集，它的存在依赖于“员工”这个强实体集。家属的“姓名”可以作为分辨符，但只有当它与对应员工的“员工编号”组合时，才能唯一确定一个家属。

3. ER图绘制 (ER Diagramming)

• EN: A university database needs to store information about professors, courses, and departments... Draw an ER diagram for this scenario...
• 中文: 一个大学数据库需要存储关于教授、课程和院系的信息... 请为此场景绘制一个ER图...

答案: 该场景的ER图如下：

• 实体集: PROFESSOR, COURSE, DEPARTMENT 被表示为矩形框。
• 属性: 每个实体的属性（如ID, Name等）都已列出。
• 关系集: TEACHES (教授与课程之间) 和 OFFERS (院系与课程之间) 被表示为菱形框。
• 映射基数:
  • TEACHES: 关系是 1:N（一个教授可以教多门课，一门课仅由一位教授教）。
  • OFFERS: 关系是 1:N（一个院系可以开设多门课，一门课仅由一个院系开设）。
• 参与约束:
  • COURSE 在 TEACHES 和 OFFERS 关系中的参与都是“完全的”（total），因为每门课都必须有一位教授和一个开设院系。这在图中由从 COURSE 实体到关系的双线表示。

4. 关系属性 (Attributes on Relationships)

• EN: Using the example of an EMPLOYEE entity and a PROJECT entity, explain why an attribute like PERCENTAGE-OF-TIME should be an attribute of the PROJECT-WORKER relationship...
• 中文: 请以员工 (EMPLOYEE)实体和项目 (PROJECT)实体为例，解释为什么像投入时间百分比 (PERCENTAGE-OF-TIME)这样的属性应该属于项目-员工 (PROJECT-WORKER)这个关系...

答案: 关系本身也可以拥有属性。在 EMPLOYEE 和 PROJECT 的例子中，PERCENTAGE-OF-TIME 这个属性描述的是一个特定员工在一个特定项目上投入的时间比例。

这个属性的意义完全依赖于员工和项目的组合，它既不是员工的固有属性（一个员工可能参与多个项目，在每个项目上的投入时间都不同），也不是项目的固有属性（一个项目有多个员工，每个员工的投入时间也不同）。因此，PERCENTAGE-OF-TIME 必须作为 PROJECT-WORKER 关系集自身的属性，而不是 EMPLOYEE 或 PROJECT 实体集的属性。

5. ER模型 vs. 关系模型 (ER Model vs. Relational Model)

• EN: How does the ER model provide clearer semantics than the relational model? Discuss with respect to the distinction between entities and relationships, and the potential for ambiguity when performing a "join" operation in the relational model.
• 中文: ER模型如何比关系模型提供更清晰的语义？请从业实体与关系的区分，以及在关系模型中执行“连接（join）”操作时可能出现的语义模糊性这两个方面进行讨论。

答案: ER模型通过明确区分实体和关系，提供了比关系模型更清晰的语义，而关系模型可能丢失一些重要的语义信息。

1. 实体与关系的区分: ER模型通过不同的图形符号（矩形和菱形）在概念上清晰地区分了实体集和关系集。这提供了一种对现实世界更自然的看法。而在关系模型中，实体和关系都被统一表示为“关系”（即表），这种概念上的差异被模糊了。
2. Join操作的语义模糊性: 在关系模型中，对两个表进行“连接（join）”操作仅仅是基于具有相同名称的列（domain）。这种操作可能导致语义上的问题，因为不同表中的同名列可能代表完全不同的现实含义。例如，将“员工”表和“轮船”表都在“年数”(NO-OF-YEARS) 这一列上进行连接是没有意义的，尽管它们列名相同。在ER模型中，这两个属性会被明确定义为“员工的年龄”和“轮船的船龄”，其语义非常清晰，从而可以避免这种无意义的操作。

6. ER模型 vs. 网络模型 (ER Model vs. Network Model)

• EN: Explain the meaning of an arrow in a network model's data-structure diagram. Does it always represent a conceptual relationship between entities as in an ER model? Use the representation of a many-to-many relationship to illustrate the difference.
• 中文: 解释网络模型数据结构图中“箭头”的含义。它是否像ER模型中那样，总是代表实体之间的概念关系？请以多对多（many-to-many）关系的表示为例来说明二者的区别。

答案: 网络模型数据结构图中的箭头并不总是代表实体间的概念关系。一个箭头代表的是两个记录类型 (record types) 之间的1:n关系，并且它隐含了一条从“属主记录 (owner-record)”到“成员记录 (member-records)”的物理访问路径。因此，数据结构图更多是表示记录的组织方式（Level 4），而非实体和关系的精确表示（Level 1）。

以多对多关系为例，比如员工和项目之间的PROJECT-WORKER关系 ：

• 在ER模型中，这被直接表示为一个连接EMPLOYEE和PROJECT两个实体集的菱形。
• 在网络模型中，必须创建一个额外的“关系记录 (relationship record)”类型，例如PROJECT-WORKER记录。然后，从EMPLOYEE记录类型和PROJECT记录类型分别画一个箭头指向这个新的PROJECT-WORKER记录。在这里，箭头连接的是实体记录和关系记录，而不是直接连接两个实体记录，这清晰地表明了它与ER模型在概念上的不同。

7. ER模型 vs. 实体集模型 (ER Model vs. Entity Set Model)

• EN: What is the fundamental conceptual difference between the ER model and the Entity Set model in their treatment of "values" like "blue" or "36"? Discuss one potential semantic problem that might arise from the Entity Set model's approach.
• 中文: 实体-关系模型和实体集模型在处理像“蓝色”或“36”这样的“值”时，最根本的概念区别是什么？ 讨论实体集模型的方法可能导致的一个潜在语义问题。

答案: 最根本的概念区别在于，实体集模型将一切都视为实体。在ER模型中，像“蓝色”或“36”这样的信息通常被当作值 (values)，它们是实体属性的取值。但在实体集模型中，"COLOR/BLACK" 或 "NO-OF-YEARS/45" 本身也被视为实体。

这种方法可能导致的一个潜在语义问题是混淆不同类型的实体。例如，在实体集模型的视图中，"EMPLOYEE-NO/2566" (代表一个员工实体) 和 "NAME/Peter Jones" (代表一个姓名值) 都被当作实体。这会让人难以区分哪个是主要的可识别对象，哪个仅仅是描述性的值，从而造成语义上的困惑。

Gamma Database

分治，让多台廉价的普通计算机协同工作，从而高效地完成任务。

三种关键技术：Data Declustering（round-robin，hashed，range）；Data Flow Execution Paradigm（将复杂的查询任务分解成一系列简单的操作符，不同的操作符可以在不同的节点上并行执行）；Hash-based Parallel Algorithms：基于哈希的并行算法，实现复杂的连接和聚合等操作。

查询管理器（Query Manager）、调度器（Scheduler）和操作符进程（Operator Processes）

哈希连接的两个阶段

1. 构建阶段（Build Phase）

• 选择小表： 首先，算法会选择两个需要连接的表中的一个，通常是较小的那个，作为“构建表”。
• 创建哈希表： 算法会遍历这个“构建表”的每一行，对连接列（比如 “客户ID”）进行哈希运算。这个哈希值决定了这一行数据将被存放在哪个哈希桶（hash bucket）里。
• 内存哈希表： 理想情况下，整个哈希表都可以存储在内存中。这样，查找速度会非常快。如果表太大，无法完全放入内存，算法会把一部分哈希桶写入磁盘，这个过程会稍后解释。

2. 探测阶段（Probe Phase）

• 遍历大表： 接下来，算法会遍历另一个表，也就是较大的“探测表”。
• 哈希匹配： 对于“探测表”中的每一行，同样对它的连接列进行哈希运算。这个哈希值会告诉算法应该去“构建表”的哪个哈希桶里寻找匹配的行。
• 找到匹配： 算法只在这个特定的哈希桶中查找匹配的行，而不是遍历整个哈希表。一旦找到匹配的行，就将它们连接起来并输出结果。

Chained Declustering 是一种更高效的数据冗余技术，它在提供高可用性的同时，降低了存储开销。

它的核心思想是：

• 不是为每个数据块创建完整的副本，而是为每个数据块创建一个部分副本。
• 这些部分副本以“链式”的方式存储在不同的节点上。

简单来说，如果一个关系（数据表）被分区并存储在 N 个节点上，Chained Declustering 会将每个数据块的备份存储在下一个节点上。例如：

• 节点 1 的数据备份存储在节点 2 上。
• 节点 2 的数据备份存储在节点 3 上。
• 节点 N 的数据备份存储在节点 1 上（形成一个闭环）。

这样，整个系统的存储开销只有 1 / N，远低于简单的镜像技术。

故障恢复过程

当一个节点发生故障时，系统会从它“链式”的下一个节点中恢复数据。由于数据是分散存储的，恢复过程也可以并行进行。

往年题

• Gamma uses a multiprocessor hash-join algorithm to join two tables together. How does Gamma implement this algorithm? The join operator executes in two phases, build and probe. During the build phase, tuples from the inner relation are inserted into a memory-resident hash table by hashing on the join attribute value. After the first phase has completed, the probing phase of the join is initiated in which tuples from the outer relation are used to probe the hash table for matching tuples.

• Gamma uses chained declustering to handle failures. 2.a. (10 Points) How does this technique operate during normal mode of operation?

  It maintains two copies of each fragment of a relation, primary and its backup, consistent with one another.

  2.b. (10 Points) What does this technique do once a node fails?

  It maintains a balanced load across the remaining nodes by pushing (a) the load of a failed primary fragment to its backup and (b) a fraction of the load of each live primary fragment to its backup for load balancing.

押题

1. 核心架构 (Core Architecture)

• EN: What are the three key technical ideas that enable the Gamma database machine's architecture to be scaled to hundreds of processors?
• 中文: 支撑Gamma数据库机架构扩展至数百个处理器的三个关键技术思想是什么？

答案/Answer: The three key technical ideas are:

1. Horizontal Partitioning: All relations are horizontally partitioned across multiple disk drives, enabling relations to be scanned in parallel.
2. Hash-Based Parallel Algorithms: Novel parallel algorithms based on hashing are used to implement complex relational operators like join and aggregate functions, which require no centralized control.
3. Dataflow Scheduling: Dataflow scheduling techniques are used to coordinate multi-operator queries with minimal coordination, which is essential for configurations with a large number of processors.

这三个关键技术思想是：

1. 水平分区 (Horizontal Partitioning): 所有关系都被水平分区到多个磁盘驱动器上，使得关系可以被并行扫描。
2. 基于哈希的并行算法 (Hash-Based Parallel Algorithms): 采用基于哈希的新型并行算法来实现如连接和聚合函数这类复杂的关系操作符，这些算法不需要中心化控制。
3. 数据流调度 (Dataflow Scheduling): 采用数据流调度技术来协调多操作符查询的执行，只需极少的协调工作，这对于包含大量处理器的配置至关重要。

2. 数据分区策略 (Data Partitioning Strategies)

• EN: Describe the three alternative declustering (partitioning) strategies provided by Gamma and their respective advantages.
• 中文: 描述Gamma提供的三种可选的数据分区（declustering）策略及其各自的优点。

答案/Answer: Gamma provides three declustering strategies:

1. Round-Robin: Tuples are distributed in a round-robin fashion among the disk drives. This is the default strategy and is useful for ensuring an even data distribution when access patterns are unknown.
2. Hashed: A hash function is applied to the partitioning attribute of each tuple to select a storage unit. Its advantage is that selection queries with equality predicates on the partitioning attribute can be directed to a single site, avoiding the participation of other nodes.
3. Range Partitioned: The user specifies a range of key values for each storage site. Its advantage is that the query scheduler can restrict query execution to only those processors whose ranges overlap with the selection predicate, which works for both equality and range predicates.

Gamma提供了三种分区策略：

1. 轮询 (Round-Robin): 元组以轮询的方式分布在各个磁盘驱动器上。这是默认策略，在访问模式未知时，有助于确保数据的均匀分布。
2. 哈希分区 (Hashed): 对每个元组的分区属性应用一个哈希函数来选择存储单元。其优点在于，对分区属性进行等值谓词查询时，可以只将查询定向到单个站点，从而避免了其他节点的参与。
3. 范围分区 (Range Partitioned): 用户为每个存储站点指定一个键值的范围。其优点在于，查询调度器可以将查询执行限制在那些范围与选择谓词重叠的处理器上，这对于等值谓词和范围谓词查询都有效。

3. 查询处理流程 (Query Processing Flow)

• EN: Explain the roles of the Query Manager, Scheduler, and Operator Processes in executing a multi-site query in Gamma.
• 中文: 解释在Gamma中，查询管理器（Query Manager）、调度器（Scheduler）和操作符进程（Operator Processes）在执行一个多站点查询时各自扮演的角色。

答案/Answer: The roles are as follows:

• Query Manager (QM): One QM is associated with each user. It is responsible for query parsing, optimization, and compilation into a query tree. For a multi-site query, the QM sends the compiled query to an available Scheduler process.
• Scheduler Process: Each multi-site query is controlled by a Scheduler process. This process is responsible for activating the Operator Processes on the relevant processors needed to execute the nodes of the query tree. It only handles control messages, not data routing.
• Operator Process: For each operator in the query tree, at least one Operator Process is used at each participating processor. These processes execute the actual relational operations (e.g., scan, join), reading a stream of input tuples and producing a stream of output tuples.

它们各自的角色如下：

• 查询管理器 (Query Manager, QM): 每个用户关联一个查询管理器。它负责查询的解析、优化和编译，生成查询树。对于多站点查询，查询管理器会将编译好的查询发送给一个空闲的调度器进程。
• 调度器进程 (Scheduler Process): 每个多站点查询由一个调度器进程控制。该进程负责在相关处理器上激活执行查询树节点所需的操作符进程。它只处理控制消息，不参与实际的数据路由。
• 操作符进程 (Operator Process): 查询树中的每个操作符，在每个参与的处理器上至少由一个操作符进程来执行。这些进程执行实际的关系运算（如扫描、连接），读取输入的元组流并产生输出的元组流。

4. 混合哈希连接算法 (Hybrid Hash-Join Algorithm)

• EN: Briefly describe how Gamma's parallel Hybrid Hash-Join algorithm works, especially when the inner relation does not fit in memory.
• 中文: 简述Gamma的并行混合哈希连接算法是如何工作的，特别是当内层关系无法完全载入内存时。

答案/Answer: Gamma's parallel Hybrid Hash-Join operates in phases based on hash partitioning:

1. Partitioning Phase: The algorithm uses a hash function to partition the inner (smaller) relation R into N buckets. The number of buckets (N) is chosen to ensure each bucket is small enough to fit in the aggregate main memory of the joining processors.
2. In-Memory Build: The tuples of the first bucket are not written to disk; instead, they are used to build in-memory hash tables on the joining processors.
3. Spilling: The remaining N-1 buckets of the inner relation are written to temporary files on disk, partitioned across all available disk sites.
4. Probing and Partitioning Outer Relation: The outer relation S is then partitioned using the same hash function. Tuples belonging to the first bucket are immediately used to probe the in-memory hash tables built in step 2. The other N-1 buckets of S are written to disk.
5. Joining Spilled Buckets: Finally, the algorithm joins the remaining N-1 pairs of buckets from relations R and S that were written to disk. Each pair of buckets is processed sequentially; a bucket from R is read to build a hash table, which is then probed by the corresponding bucket from S.

Gamma的并行混合哈希连接基于哈希分区，分阶段进行：

1. 分区阶段: 算法使用一个哈希函数将内层（较小的）关系R分割成N个桶。桶的数量（N）被精心选择，以确保每个桶的大小都能装入参与连接的处理器们的总内存中。
2. 内存构建: 第一个桶的元组不会被写入磁盘，而是直接用于在参与连接的处理器上构建内存哈希表。
3. 溢出到磁盘: 内层关系余下的N-1个桶被写入磁盘上的临时文件，并被分区到所有可用的磁盘站点上。
4. 探测并分区外层关系: 接着，使用相同的哈希函数对外层关系S进行分区。属于第一个桶的元组被立即用来探测步骤2中构建的内存哈希表。S关系的其他N-1个桶也被写入磁盘。
5. 连接溢出桶: 最后，算法连接从R和S关系中写入磁盘的其余N-1对桶。每一对桶被顺序处理；从R中读取一个桶来构建哈希表，然后用S中对应的桶来探测该哈希表。

5. 切分表 (Split Tables)

• EN: What is the purpose and function of a split table in Gamma's query execution?
• 中文: 在Gamma的查询执行中，切分表（split table）的用途和功能是什么？

答案/Answer: A split table defines a mapping of values to a set of destination processes. Its function is to allow an operator process to route its output stream of tuples to other processes.

When an operator process generates an output tuple, it applies a function (e.g., a hash function on an attribute) to the tuple to get a value. This value is then used as an index into the split table to obtain the address (Processor #, Port #) of the destination process that should receive the tuple. This mechanism allows for modular software design and decentralized data routing without involving the central scheduler.

切分表定义了一个从值到一组目标进程的映射。它的功能是让一个操作符进程能将其输出的元组流路由到其他进程。

当一个操作符进程生成一个输出元组时，它会对该元组应用一个函数（例如，对某个属性应用哈希函数）以获得一个值。这个值随后被用作切分表的索引，以获取应该接收该元组的目标进程的地址（处理器号，端口号）。这种机制实现了模块化的软件设计和去中心化的数据路由，且无需中央调度器的参与。

6. 高可用性 (High Availability: Chained Declustering)

• EN: Describe the Chained Declustering mechanism used in Gamma for data availability. How does it handle a node failure?
• 中文: 描述Gamma中用于数据可用性的链式解聚（Chained Declustering）机制。它如何处理节点故障？

答案/Answer: Chained declustering is a data replication technique used to ensure high availability.

• Data Placement: It maintains two copies of each relation: a primary and a backup. The fragments of the primary copy are declustered across a group of nodes (a relation cluster). The i-th primary fragment (Ri) is stored on node i mod M, and its corresponding backup fragment (ri) is stored on the adjacent node (i+1) mod M. This links the disks together like a chain.
• Failure Handling: During normal operation, reads are directed to the primary copy. When a node fails (e.g., node 1), the primary fragment on that node (R1) becomes unavailable. Accesses that would have gone to R1 are redirected to its backup fragment r1 on node 2. To prevent node 2 from being overloaded, a portion of the workload for its primary fragment (R2) is offloaded to its backup fragment (r2) on node 3, and so on down the chain. This dynamic reassignment distributes the workload of the failed node uniformly across all remaining operational nodes in the cluster.

链式解聚是一种用于确保高可用性的数据复制技术。

• 数据布局: 该机制维护每个关系的两个副本：一个主副本和一个备份副本。主副本的分片被分区存储在一组节点（关系簇）上。第i个主分片(Ri)存储在第i mod M个节点上，其对应的备份分片(ri)则存储在相邻的第(i+1) mod M个节点上。这种方式像链条一样将磁盘连接起来。
• 故障处理: 在正常操作期间，读取请求被定向到主副本。当一个节点（例如节点1）发生故障时，其上的主分片(R1)将无法访问。原本访问R1的请求会被重定向到节点2上的备份分片r1。为了防止节点2过载，其主分片(R2)的部分负载会被转移到节点3上的备份分片r2，以此类推，沿着链条向下传递。这种动态的负载重分配将故障节点的负载均匀地分布到集群中所有剩余的健康节点上。

7. 哈希分区 vs. 范围分区 (Hash vs. Range Partitioning)

• EN: What types of queries benefit most from hash partitioning versus range partitioning?
• 中文: 哪种类型的查询分别从哈希分区和范围分区中获益最多？

答案/Answer:

• Hash Partitioning: This strategy is most beneficial for selection queries that have equality predicates on the partitioning attribute. The hash function allows the query to be directed to a single, specific node where the data resides, thus minimizing the number of participating processors.
• Range Partitioning: This strategy benefits selection queries with both equality and range predicates (e.g., salary < 50K) on the partitioning attribute. The query scheduler can use the defined ranges to identify and activate only the subset of nodes that contain the relevant data, rather than all of them.
• 哈希分区 (Hash Partitioning): 这种策略对于在分区属性上有等值谓词的选择查询最为有利。哈希函数使得查询可以直接被路由到数据所在的单个特定节点，从而最大限度地减少了参与查询的处理器数量。
• 范围分区 (Range Partitioning): 这种策略对于在分区属性上有等值谓词和范围谓词（例如 salary < 50K）的选择查询都有利。查询调度器可以利用预定义的范围信息，来识别并仅激活那些包含相关数据的节点子集，而不是所有节点。

8. 调度器的角色 (Role of the Scheduler)

• EN: Describe the role of the Scheduler process in Gamma. Is it directly involved in routing data tuples between operator processes?
• 中文: 描述Gamma中调度器进程（Scheduler process）的角色。它是否直接参与在操作符进程之间路由数据元组？

答案/Answer: The Scheduler process is responsible for controlling and coordinating the execution of each multi-site query. Its main tasks are to receive a compiled query from a Query Manager and activate the necessary operator processes on the participating processors to execute the query plan. It communicates with operator processes via control messages, such as "Initiate" to start an operator and receiving "Done" messages upon completion.

However, the Scheduler is NOT involved in the routing of the actual data tuples. It only exchanges control messages. The data flow between operator processes is handled directly by the operators themselves using split tables, without the scheduler as an intermediary.

调度器进程负责控制和协调每个多站点查询的执行。它的主要任务是从查询管理器接收一个编译好的查询，并在参与的处理器上激活必要的操作符进程来执行查询计划。它通过控制消息与操作符进程通信，例如发送“Initiate”消息来启动一个操作符，并在操作符完成后接收“Done”消息。

然而，调度器不直接参与实际数据元组的路由。它只交换控制消息。操作符进程之间的数据流是由操作符自己使用切分表直接处理的，调度器不作为中间人。

FoundationDB

分布式键值存储系统。

• 架构设计: 控制平面（Control Plane）和数据平面（Data Plane）。
  • 控制平面: 负责集群管理，包括协调器（Coordinators）、集群控制器（ClusterController）、数据分发器（DataDistributor）和速率控制器（RateKeeper）。
  • 数据平面: 负责处理事务，包括事务系统（Transaction System）、日志系统（Log System）和存储系统（Storage System）。
• 事务处理: 事务遵循乐观并发控制（OCC）。一个事务的流程通常是：客户端首先向代理服务器（ProxyServer）请求一个读取版本（Read Version）；然后，直接向存储服务器（StorageServers）发出读取请求；写入操作则在客户端本地进行缓冲。当客户端准备提交时，会将读写集合发送给代理服务器，代理服务器会向解析器（Resolver）发起冲突检查，并在检查通过后将变动（mutations）发送到日志服务器（LogServers）进行持久化。

往年题

FDB separates the read path of a transaction from its write path.

• 5.a. (10 Points) Explain FDB's read path, i.e., how does the FDB client read the value of a key?
  1. When a client wants to read a key, it starts a transaction by contacting one of the Proxies to obtain a read version to ensure consistency (0.5 points)
  2. The Proxy then asks the Sequencer for a read version (version with the maximum commit at the given time), and sends this read version back to the client (1 points)
  3. The client then sends the read request with the key and read version to the Storage Server (6.5 points)
  4. The Storage Server (using MVCC) returns the value of the key using the specified read version (2 points)
• 5.b. (5 Points) What features cause FDB's write path to be more time consuming than its read path? OCC (concurrency control protocol, Resolver), MVCC, Logging. 2 out of 3 receives full points.

The architecture of FoundationDB consists of a data plane and a control plane.

• (10 Points) What is the functionality of the data plane? Transactions with ACID semantics and data storage.

• (10 Points) What is the functionality of the control plane? Load balancing, failure handling. System metadata and cluster-wide orchestration.

押题

1. 核心架构 (Core Architecture)

• EN: Describe FoundationDB's "divide-and-conquer" design principle. What are the main components and responsibilities of the Control Plane and the Data Plane?
• 中文: 描述FoundationDB的“分而治之”设计原则。它的控制平面（Control Plane）和数据平面（Data Plane）各有哪些主要组件和职责？

答案/Answer: FoundationDB's "divide-and-conquer" principle involves decoupling its main systems so they can be scaled independently. The architecture is unbundled into a Control Plane and a Data Plane.

• Control Plane: This plane manages cluster metadata and orchestration. Its components include:
  • Coordinators: Persist critical system metadata and form a Paxos group to elect a ClusterController.
  • ClusterController: A singleton process that monitors all servers in the cluster.
  • DataDistributor: A singleton responsible for monitoring failures and balancing data among Storage Servers.
  • Ratekeeper: A singleton that provides overload protection for the cluster.
• Data Plane: This plane is responsible for transaction processing and data storage. It is composed of three subsystems:
  • Transaction System (TS): A stateless system that includes the Sequencer (assigns read/commit versions to transactions), Proxies (provide read versions to clients and orchestrate commits), and Resolvers (check for transaction conflicts).
  • Log System (LS): Comprised of LogServers, this system stores the Write-Ahead-Log (WAL) for the Transaction System.
  • Storage System (SS): Comprised of StorageServers, this system stores data in contiguous key ranges (shards) and serves client read requests.
• 控制平面 (Control Plane): 该平面负责管理集群的元数据和进行整体协调。其组件包括：
  • 协调器 (Coordinators): 持久化关键的系统元数据，并组成一个Paxos组来选举一个集群控制器。
  • 集群控制器 (ClusterController): 一个单例进程，负责监控集群中的所有服务器。
  • 数据分发器 (DataDistributor): 一个单例进程，负责监控故障并在存储服务器之间均衡数据。
  • 速率控制器 (Ratekeeper): 一个单例进程，为集群提供过载保护。
• 数据平面 (Data Plane): 该平面负责处理事务和存储数据。它由三个子系统组成：
  • 事务系统 (Transaction System, TS): 一个无状态系统，包括定序器 (Sequencer)（为事务分配读版本和提交版本）、代理 (Proxies)（向客户端提供读版本并协调事务提交）和解析器 (Resolvers)（检查事务冲突）。
  • 日志系统 (Log System, LS): 由日志服务器 (LogServers)组成，该系统为事务系统存储预写日志（WAL）。
  • 存储系统 (Storage System, SS): 由存储服务器 (StorageServers)组成，该系统以连续的键范围（分片）形式存储数据，并处理客户端的读请求。

2. 事务处理流程 (Transaction Process)

• EN: Describe the end-to-end process of a read-write transaction in FoundationDB, from the client requesting a read version to a successful commit.
• 中文: 描述在FoundationDB中一个读写事务的端到端完整流程，从客户端请求读版本开始，直到成功提交为止。

答案/Answer: A read-write transaction in FoundationDB involves the following steps:

1. Get Read Version: The client sends a request to a Proxy for a read version. The Proxy, in turn, gets this read version from the Sequencer. This version is guaranteed to be at least as large as any previously committed version.
2. Reads: The client issues reads directly to the appropriate Storage Servers for the keys it needs, requesting the data at the specific read version obtained in step 1.
3. Writes: All writes are buffered locally at the client; the cluster is not contacted during this phase.
4. Commit: To commit, the client sends its read set and write set to a Proxy. The Proxy then orchestrates the commit:
   • (3.1) It asks the Sequencer for a commit version, which will be larger than any existing read or commit version.
   • (3.2) It sends the transaction's read and write sets to the appropriate range-based Resolvers to check for read-write conflicts. If a conflict is detected, the transaction aborts.
   • (3.3) If there are no conflicts, the Proxy sends the committed data (mutations) to the Log Servers to be made durable.
   • (3.4) A transaction is considered committed once the designated Log Servers have replied to the Proxy. The Proxy then reports success to the client.

在FoundationDB中，一个读写事务包含以下步骤：

1. 获取读版本 (Get Read Version): 客户端向一个代理（Proxy）发送请求以获取一个读版本。代理再从定序器（Sequencer）获取这个读版本。该版本号被保证不小于任何先前已提交事务的版本号。
2. 读取 (Reads): 客户端根据它需要的键，直接向对应的存储服务器（Storage Servers）发起读请求，并请求在步骤1中获得的特定版本的数据。
3. 写入 (Writes): 所有的写操作都在客户端本地进行缓冲；在此阶段不会联系集群。
4. 提交 (Commit): 提交时，客户端将其读集合和写集合发送给一个代理。代理随后协调提交过程：
   • (3.1) 它向定序器请求一个提交版本，该版本将大于任何现有的读版本或提交版本。
   • (3.2) 它将事务的读写集合发送给对应的基于范围的解析器（Resolvers），以检查读写冲突。如果检测到冲突，事务将中止。
   • (3.3) 如果没有冲突，代理会将已提交的数据（变更）发送给日志服务器（Log Servers）进行持久化。
   • (3.4) 一旦指定的日志服务器向代理回复确认，事务即被视为已提交。代理随后向客户端报告成功。

3. 并发控制 (Concurrency Control)

• EN: How does FoundationDB achieve strict serializability? Explain the roles of Multi-Version Concurrency Control (MVCC), Optimistic Concurrency Control (OCC), and the Resolver component in this process.
• 中文: FoundationDB是如何实现严格可串行化（strict serializability）的？请解释多版本并发控制（MVCC）、乐观并发控制（OCC）以及解析器（Resolver）组件在此过程中的作用。

答案/Answer: FoundationDB achieves strict serializability by combining Optimistic Concurrency Control (OCC) and Multi-Version Concurrency Control (MVCC).

• MVCC: Storage Servers maintain multiple versions of data, allowing read operations to access a consistent snapshot of the data at a specific "read version" without blocking writes. When a client reads a key, it specifies the read version it received from the Sequencer, and the Storage Server returns the value of the key at the largest version less than or equal to the requested read version.
• OCC: FDB uses an optimistic approach where transactions do not take locks. Instead, conflicts are checked at commit time. This is the primary role of the Resolver.
• Resolver: The Resolver is the component that implements OCC. When a transaction is ready to commit, the Proxy sends its read and write key ranges to the Resolver(s). Each Resolver maintains a history of recently committed key ranges and their commit versions. It checks if the transaction's read set conflicts with any writes from other transactions that have committed since the current transaction's read version was issued. If a conflict is found, the transaction is aborted; otherwise, it is allowed to commit.

Because the Sequencer ensures a transaction's read version is up-to-date and its commit version defines a serial history, and the Resolver prevents conflicts, FDB achieves strict serializability.

FoundationDB通过结合乐观并发控制（OCC）和多版本并发控制（MVCC）来实现严格可串行化。

• MVCC: 存储服务器维护数据的多个版本，允许读操作在特定的“读版本”上访问一致的数据快照，而不会阻塞写操作。当客户端读取一个键时，它会指定从定序器获得的读版本，存储服务器会返回不大于该读版本的最新版本的数据。
• OCC: FDB使用一种乐观方法，即事务不加锁，而是在提交时检查冲突。这正是解析器（Resolver）的主要职责。
• 解析器 (Resolver): 解析器是实现OCC的组件。当一个事务准备提交时，代理会将其读、写键范围发送给解析器。每个解析器维护着近期已提交事务修改的键范围及其提交版本的历史记录。它会检查当前事务的读集合是否与自该事务获取读版本以来已提交的其他事务的写集合有冲突。如果发现冲突，事务将被中止；否则，它被允许提交。

由于定序器确保了事务的读版本是最新的，并且其提交版本定义了一个串行历史，同时解析器防止了冲突的发生，因此FDB实现了严格可串行化。

4. 故障恢复 (Fault Tolerance)

• EN: Describe FoundationDB's approach to failure recovery, which is guided by the principle "make failure a common case". Why is its recovery process typically faster than traditional database recovery methods?
• 中文: 描述FoundationDB在“让故障成为常态”原则指导下的故障恢复方法。为什么它的恢复过程通常比传统数据库的恢复方法更快？

答案/Answer: FoundationDB's approach is to handle all failures through a single, well-tested recovery path. When a failure is detected in the Transaction System (TS) or Log System (LS), the Sequencer proactively terminates. The ClusterController detects this and immediately recruits a new Sequencer, which then bootstraps a new TS and LS, beginning a new "epoch". This process is called reconfiguration.

The recovery process is fast (median time of 3.08 seconds in production) for two main reasons:

1. No Undo Log Processing: Unlike traditional ARIES-style recovery, FDB recovery does not need to apply undo log entries. The recovery process only needs to determine the end of the redo log from the old epoch (the Recovery Version, or RV), and any data after that version is simply discarded by the Storage Servers.
2. Not Bounded by Data Size: The recovery time is not dependent on the size of the database or transaction logs. It is only related to the size of the system metadata, which is very small. The new Transaction System can begin accepting new transactions even before all data from the old Log Servers has been replayed by the Storage Servers.

FoundationDB的方法是通过一个单一且经过充分测试的恢复路径来处理所有故障。当在事务系统（TS）或日志系统（LS）中检测到故障时，定序器会主动终止。集群控制器（ClusterController）会检测到此情况并立即招募一个新的定序器，该定序器会引导启动一个新的TS和LS，开启一个新的“纪元（epoch）”。这个过程被称为重新配置（reconfiguration）。

恢复过程之所以很快（在生产环境中位恢复时间为3.08秒），主要有两个原因 ：

1. 无需处理Undo日志: 与传统的ARIES式恢复不同，FDB的恢复过程不需要应用Undo日志条目。恢复过程只需确定旧纪元中Redo日志的末尾（即恢复版本号，RV），存储服务器会简单地丢弃任何版本号大于RV的数据。
2. 不受数据大小限制: 恢复时间不依赖于数据库或事务日志的大小。它只与系统元数据的大小有关，而元数据非常小。新的事务系统甚至可以在旧日志服务器的所有数据被存储服务器完全重放之前就开始接受新的事务。

Nova-LSM

基于组件的分布式 LSM-树键值存储系统，其核心思想是将软件分解为三个可以独立扩展的组件，以应对现代数据存储的需求。

• LSM-树组件（LTC）：负责管理内存表（memtable）和 SSTables。它会监控 SSTable 的状态，并决定何时进行压缩或将数据卸载到存储组件。
• 日志记录组件（LogC）：负责提供持久化日志记录功能，确保数据的完整性。
• 存储组件（StoC）：负责存储、检索和管理可变大小的数据块。这些数据块可以存储在多种介质上，如 DRAM、NVMe 或磁盘。

解决的关键挑战

1. 写入停滞（Write Stalls）
   • Vertical Scaling：increase the amount of memory allocated to an LTC.
   • Horizontal Scaling: increase the number of Storage Components (StoCs).
2. 大型内存中的读取与扫描变慢（Scans are slowed down）
   • Scans are slowed down：动态范围（Dynamic Ranges）：系统在运行时会根据工作负载动态构建数据范围。这使得扫描操作只需在相应的memtable子集和第 0 级 SSTables 中进行，从而加速了扫描。
   • Gets are slowed down：查找索引（Lookup Index）：通过使用查找索引，系统能够快速定位键的位置。如果一个键存在于查找索引中，它只需在一个内存表或一个第 0 级 SSTable 中进行搜索，显著提高了读取速度。
3. 临时瓶颈 Temporary Bottlenecks
   • Partition SSTables：将一个 SSTable 的数据块分散到多个 StoC 上，以平衡负载。
   • Power-of-d：将写入请求发送到队列最短的 StoC，进一步减少了瓶颈的发生。
4. 日志记录与高可用性
   • Replicating Log Records：在 StoC 的内存中复制日志记录。这种方法使得数据库能够在几秒钟内恢复 GB 级别的数据，而非数小时。
5. 倾斜访问模式 Skewed Access Pattern
   • In-Memory Pre-compaction：利用其动态范围分区 (Dranges) 的特性，能够识别出某个特定的、很小的键范围（即“热点”数据）正在被频繁地更新，当系统检测到多个内存中的 Immutable Memtables 都包含对这个热点数据的更新时，它不会像传统方法那样，把每一个 Memtable 都完整地刷写到磁盘 。取而代之的是，计算节点 (LTC) 会先在内存里将这些 Memtable 进行合并 。最后，只有一个包含了干净、最新数据的、经过压缩的新 Memtable 会被刷写到存储节点 (StoC) 。

往年题

Nova-LSM separates storage (StoC) from processing (LTC), enabling each to scale independent of the other. LTCs share StoCs. When LTCs assign SSTables to StoCs randomly, temporary bottlenecks may form due to random collision of many writes to a few, potentially one, StoC. Name one technique that LTCs implement to minimize the impact of these collisions.

Partitioning of a SSTable across multiple StoCs, power-of-d to assign write requests to StoCs.

Why is it important for modern database management systems to separate their storage from processing?

To scale each independent of the other based on the characteristics of the workload.

押题

1. 核心架构 (Core Architecture)

• EN: Describe the core design principle of Nova-LSM and list its three main components. What is the primary role of each component?
• 中文: 描述Nova-LSM的核心设计原则，并列出其三个主要组件。每个组件的主要职责是什么？

答案/Answer: The core design principle of Nova-LSM is the disaggregation of a monolithic LSM-tree key-value store into components that separate storage from processing. This allows each component to scale independently. The three main components are:

• LSM-tree Component (LTC): This is a processing component. It implements the in-memory structures of an LSM-tree (memtables), processes application requests (Get, Put, Scan), and manages the compaction process by identifying which SSTables need to be compacted.
• Logging Component (LogC): This component is responsible for durability and availability by generating and managing log records. It can be configured to replicate log records in memory for high availability or persist them to storage for durability.
• Storage Component (StoC): This is the storage layer. Its role is to store, retrieve, and manage variable-sized blocks of data, such as SSTables and log files, on various storage devices (DRAM, NVMe, Disk).

Nova-LSM的核心设计原则是将单体LSM-tree键值存储分解（disaggregation）为多个组件，实现了存储和计算的分离。这使得每个组件都可以独立扩展。其三个主要组件是：

• LSM-tree组件 (LTC): 这是一个计算组件。它负责实现LSM-tree的内存结构（memtables），处理应用的请求（Get, Put, Scan），并通过识别需要合并的SSTable来管理合并（compaction）过程。
• 日志组件 (LogC): 该组件通过生成和管理日志记录来负责持久性和可用性。它可以被配置为在内存中复制日志记录以实现高可用性，或将日志持久化到存储中以实现持久性。
• 存储组件 (StoC): 这是存储层。其职责是在各种存储设备（DRAM、NVMe、磁盘）上存储、检索和管理可变大小的数据块，例如SSTable和日志文件。

2. 写入暂停问题与解决方案 (Write Stalls and Solutions)

• EN: What is a "write stall" in an LSM-tree based system? According to the documents, how does Nova-LSM's disaggregated architecture solve this problem through both vertical and horizontal scaling?
• 中文: 在基于LSM-tree的系统中，什么是“写入暂停” (write stall)？根据所给材料，Nova-LSM的分解式架构是如何通过垂直和水平扩展来解决这个问题的？

答案/Answer: A write stall is a period when an LSM-tree system must suspend the processing of new writes. This happens for two main reasons: 1) all in-memory memtables are full and the system must wait for one to be flushed to disk , or 2) the number or size of SSTables at Level 0 exceeds a threshold, forcing writes to wait for compaction to complete.

Nova-LSM's architecture addresses this by allowing independent scaling:

• Vertical Scaling: One can increase the amount of memory allocated to an LTC. More memory allows for a larger number of memtables, which absorbs write bursts and gives the system more time to flush and compact in the background, thus reducing the frequency of stalls caused by full memtables. Experiments show increasing memory from 32 MB to 4 GB improved average throughput by 5 times.
• Horizontal Scaling: One can increase the number of Storage Components (StoCs). This increases the aggregate disk bandwidth available for flushing memtables and performing compactions. With sufficient memory, increasing the number of StoCs from 1 to 10 significantly diminished write stalls and improved throughput by 27 times compared to the base configuration.

“写入暂停”是指LSM-tree系统必须暂停处理新写入请求的时期。这主要由两个原因导致：1) 所有内存中的memtable都已写满，系统必须等待其中一个被刷写到磁盘 ；2) 第0层的SSTable数量或大小超过了阈值，导致写入必须等待合并（compaction）完成。

Nova-LSM的架构通过独立的扩展方式来解决这个问题：

• 垂直扩展: 可以增加分配给LTC的内存量。更多的内存意味着可以容纳更多的memtable，这能更好地吸收突发的写入流量，并给予系统更多在后台进行刷写和合并的时间，从而减少因memtable写满而导致的暂停。实验表明，将内存从32MB增加到4GB，平均吞吐量提升了5倍。
• 水平扩展: 可以增加存储组件（StoCs）的数量。这增加了可用于刷写memtable和执行合并的总磁盘带宽。在内存充足的情况下，将StoC数量从1个增加到10个，显著减少了写入暂停，吞吐量相比基础配置提升了27倍。

3. 动态范围 (Dynamic Ranges)

• EN: What are Dynamic Ranges (Dranges) in Nova-LSM? How do they help solve the challenges of slow compactions and expensive reads when using a large amount of memory?
• 中文: Nova-LSM中的动态范围（Dranges）是什么？它们如何帮助解决在使用大量内存时，合并速度慢和读取成本高昂的挑战？

答案/Answer: Dynamic Ranges (Dranges) are partitions of an application's key-space range constructed by an LTC at runtime. The objective is to balance the write load evenly across these Dranges.

Dranges solve two main challenges:

1. Slow Compactions: Without Dranges, a large number of Level 0 SSTables often have overlapping key ranges and must be compacted together, which is a long, monolithic process that can cause write stalls. Dranges partition the keyspace so that Level 0 SSTables in different Dranges are mutually exclusive. This allows compactions for different Dranges to proceed independently and in parallel, breaking one large task into many smaller, faster ones and utilizing idle resources.
2. Expensive Reads/Scans: A large number of memtables and Level 0 SSTables means a get or scan operation must search many places to find the latest key. By assigning writes to the active memtable of the Drange that contains its key, Dranges prevent different versions of a key from being scattered across all memtables. A scan can then be processed by searching only the subset of memtables and SSTables within the relevant Dranges, significantly reducing the search space.

动态范围（Dranges）是LTC在运行时根据工作负载动态构建的对应用键空间的内部划分。其目标是在这些Dranges之间均匀地平衡写入负载。

Dranges解决了两个主要挑战：

1. 合并速度慢: 如果没有Dranges，大量的第0层SSTable通常会有重叠的键范围，必须一起进行合并，这是一个漫长的单一过程，容易导致写入暂停。Dranges对键空间进行划分，使得不同Drange中的第0层SSTable键范围互不重叠。这使得针对不同Drange的合并可以独立并行地进行，将一个大任务分解为多个更小、更快的任务，并利用了空闲资源。
2. 读取/扫描成本高: 大量的memtable和第0层SSTable意味着get或scan操作需要搜索很多地方才能找到最新的键。通过将写操作分配到包含其键的Drange的活动memtable中，Dranges避免了单个键的不同版本分散在所有memtable中。这样，扫描操作只需搜索相关Drange内的memtable和SSTable子集，从而大大减少了搜索空间。

4. 读性能优化 (Read Performance Optimization)

• EN: When an LSM-tree uses a large number of memtables, get (point read) operations can become slow. What specific index does Nova-LSM implement to address this, and how does it work?
• 中文: 当LSM-tree使用大量memtable时，get（点读取）操作会变慢。Nova-LSM实现了哪种特定的索引来解决这个问题，其工作原理是什么？

答案/Answer: To address slow get operations, Nova-LSM implements a Lookup Index.

How it works: The lookup index identifies either the specific memtable or the Level 0 SSTable that contains the latest value of a given key. When a get request arrives, the LTC first consults this index.

• If the key is found in the index (a hit), the request is directed to search only one specific memtable or one Level 0 SSTable, and the value is returned immediately upon being found.
• If the key is not in the index (a miss), it means the latest version of the key is not in any memtable or Level 0 SSTable. The search then proceeds to the higher, sorted levels (Level 1 and above) as usual.

This index effectively prevents get requests for recent keys from having to search through all memtables and Level 0 SSTables, significantly improving performance, especially for skewed workloads.

为了解决get操作变慢的问题，Nova-LSM实现了一个查找索引 (Lookup Index)。

工作原理: 查找索引能够识别出包含某个给定键的最新值的具体memtable或第0层SSTable。当一个get请求到达时，LTC会首先查询这个索引。

• 如果键在索引中找到（命中），该请求将被引导去仅搜索一个特定的memtable或一个第0层的SSTable，一旦找到值就立即返回。
• 如果键不在索引中（未命中），这意味着该键的最新版本不在任何memtable或第0层SSTable中。此时，搜索将照常进入更高、有序的层级（第1层及以上）进行。

这个索引有效地避免了对新近写入的键的get请求需要遍历所有memtable和第0层SSTable，从而显著提升了性能，尤其是在倾斜的工作负载下。

5. 负载均衡与网络 (Load Balancing and Networking)

• EN: How does Nova-LSM use the "power-of-d" strategy to balance load and avoid temporary bottlenecks when writing SSTables to Storage Components (StoCs)? What role does RDMA play in the communication between components?
• 中文: 在将SSTable写入存储组件（StoCs）时，Nova-LSM如何使用“d次方选择 (power-of-d)”策略来平衡负载并避免临时瓶颈？RDMA在组件间通信中扮演什么角色？

答案/Answer: Nova-LSM addresses temporary bottlenecks at the storage layer, which occur when multiple concurrent writes randomly collide on a few StoCs, creating queuing delays.

The power-of-d strategy is used to mitigate this. When an LTC needs to write a SSTable (or a fragment of it) to p StoCs, it does not simply choose p StoCs randomly. Instead, it:

1. Randomly selects d StoCs from the available pool (where d is typically 2*p).
2. Peeks at the disk queue sizes of these d StoCs.
3. Chooses the p StoCs with the shortest disk queues to write to. This simple technique significantly reduces the probability of hitting heavily loaded StoCs and improves throughput by minimizing queuing delays.

RDMA (Remote Direct Memory Access) is the high-speed network that interconnects the components (LTCs, LogCs, StoCs). It is critical because it provides high bandwidth and very low latency. Specifically, its one-sided RDMA WRITE verb allows an LTC to write data directly into the memory buffer of a remote StoC, bypassing the remote CPU, which is highly efficient for flushing SSTables and replicating logs.

Nova-LSM解决了存储层的临时瓶颈问题，这种瓶颈发生在多个并发写入随机地碰撞到少数几个StoC上，从而产生排队延迟。

d次方选择 (power-of-d) 策略被用来缓解此问题。当一个LTC需要将一个SSTable（或其分片）写入p个StoC时，它不是简单地随机选择p个StoC，而是：

1. 从可用的StoC池中随机选择d个（通常d=2*p）。
2. 探查这d个StoC的磁盘队列长度。
3. 选择其中磁盘队列最短的p个StoC进行写入。 这种简单的技术显著降低了碰到重负载StoC的概率，通过最小化排队延迟来提高吞吐量。

RDMA (远程直接内存访问) 是连接各个组件（LTCs, LogCs, StoCs）的高速网络。它至关重要，因为它提供了高带宽和极低的延迟。特别是，其单边RDMA WRITE操作允许LTC直接将数据写入远程StoC的内存缓冲区，绕过了远程CPU，这对于刷写SSTable和复制日志来说非常高效。

HRPS

新型数据分片技术，旨在优化“无共享 (Shared-Nothing)”架构的多处理器数据库系统的性能。

1. 细粒度分片：HRPS首先将一个关系（数据表）分割成许多个小的逻辑“片段” (fragments)。每个片段包含一个特定范围的属性值，并且包含大约相同数量的元组。
2. 分片数量的确定：分片的数量不是由系统中的处理器数量决定的，而是由工作负载（即查询的特性）决定的。作者提出了一个数学模型，通过分析查询的CPU、磁盘I/O、网络资源消耗以及并行开销，计算出一个“最优”的并行处理器数量 M。然后根据这个M值来确定每个逻辑片段的大小。
3. 片段的分配：这些逻辑片段以轮询的方式被分配到系统中的所有物理处理器上。

HRPS 的工作原理

• 对于资源消耗大（复杂）的查询：这类查询需要检索大量数据。由于数据被分成了很多小片段并分散在不同处理器上，查询会涉及多个片段，从而激活多个处理器进行并行处理，达到类似哈希策略的效果，缩短响应时间。
• 对于资源消耗小（简单）的查询：这类查询只检索少量数据。它可能只涉及一两个逻辑片段。由于HRPS知道每个片段的存储位置，查询只会被发送到存储着这些片段的少数几个处理器上执行，避免了不必要的并行开销，达到类似范围策略的效果。

通过这种方式，HRPS巧妙地在“完全并行”（如哈希策略）和“有限并行”（如范围策略）之间找到了一个平衡点，能够适应混合型的查询负载。

往年题

A key concept of the hybrid range partitioning strategy (HRPS) is to use a degree of parallelism M that maximizes the benefits of parallelism. What may happen to the system response time and throughput if M=1 is used for a query that performs a lot of disk I/O, e.g., a 10% selection using a B+-tree? Make sure to answer concisely for each of the response time (10 points) and throughput (10 points) metrics.

Increases response time by performing many disk I/Os sequentially instead of concurrently using parallelism. Reduces throughput by resulting in formation of hotspots and bottlenecks due to its requirement for one node to do more than its fair share of work.

HRPS considers four factors to determine how many records should constitute a fragment. Name two of these factors.

• The resource requirements of the queries accessing the relation
• the processing capability of the system
• the overhead of using each additional processor to execute a query
• the cost of searching the range table constructed by the hybrid-range declustering strategy.

押题

好的，根据您提供的关于混合范围分区策略（HRPS）的论文和课件，以下是几道基于两者共同知识点的问题及其参考答案。

题目 1: 核心动机 (Core Motivation)

• EN: What is the fundamental performance trade-off between the Range and Hash partitioning strategies that motivates the development of the Hybrid-Range Partitioning Strategy (HRPS)?
• 中文: 范围分区（Range Partitioning）和哈希分区（Hash Partitioning）策略之间存在什么根本的性能权衡，从而催生了混合范围分区策略（HRPS）？

答案/Answer: The fundamental trade-off is between minimizing overhead for small queries and maximizing parallelism for large queries[cite: 13, 14, 15, 16, 9136, 9137, 9138, 9139].

• Range Partitioning excels with queries that have minimal resource requirements (e.g., retrieving a few tuples)[cite: 256, 257]. It can localize the query's execution to a single processor, avoiding the overhead associated with startup, communication, and termination of a multi-processor query[cite: 14, 257]. However, for resource-intensive queries, its sequential execution on one or two processors leads to poor response times[cite: 33, 426].
• Hash Partitioning excels with queries that have high resource requirements[cite: 262, 263]. It directs the query to all processors, effectively using intra-query parallelism to achieve the best possible response time[cite: 263]. However, for small range queries, it unnecessarily directs them to all processors, incurring significant overhead that degrades system throughput[cite: 31, 378, 379].

HRPS was developed to strike a compromise, providing good performance for both types of queries by obtaining the appropriate degree of parallelism based on the query's characteristics[cite: 34, 35, 36, 84].

根本的权衡在于为小型查询最小化开销与为大型查询最大化并行度之间的矛盾 [cite: 13, 14, 15, 16, 9136, 9137, 9138, 9139]。

• 范围分区对于资源需求极小的查询（例如，检索少量元组）表现出色。它能将查询的执行本地化到单个处理器上，从而避免了多处理器查询所带来的启动、通信和终止的开销。但是，对于资源密集型的大查询，其在少数处理器上的顺序执行会导致响应时间过长。
• 哈希分区对于资源需求高的查询表现出色 [cite: 262, 263]。它将查询分发到所有处理器，有效利用查询内并行性以获得最佳响应时间 [cite: 263]。然而，对于小范围查询，它不必要地将查询分发到所有处理器，从而引入了显著的开销，降低了系统吞吐量 [cite: 31, 378, 379]。

HRPS的开发目的就是为了在这种权衡中取得折衷，通过根据查询特性来获得适当的并行度，从而为两种类型的查询都提供良好的性能。

题目 2: HRPS 的核心机制 (Core Mechanism of HRPS)

• EN: How does the Hybrid-Range Partitioning Strategy (HRPS) determine the optimal number and size of the fragments for a relation? Explain the roles of M (desired degree of parallelism) and FC (fragment cardinality).
• 中文: 混合范围分区策略（HRPS）是如何确定一个关系的“最佳”分片数量和大小的？请解释M（期望并行度）和FC（分片基数）在其中的作用。

答案/Answer: The HRPS determines the fragment size based on the optimal number of processors (M) that should execute an average query, not the total number of physical processors in the system

1. Calculating M: M represents the desired degree of parallelism that minimizes a query's response time. It is calculated by modeling the response time RT(M) as a function of the number of processors M, taking into account the query's resource requirements (CPU, Disk, Network) and the system's overhead per processor (CP)[cite: 118, 119, 120, 9817, 9818]. The formula is: \(RT(M) = \frac{CPU_{Ave} + Disk_{Ave} + Net_{Ave}}{M} + M * CP\) The optimal M is found by setting the first derivative of this function to zero[cite: 126, 9819]: \(M = \sqrt{\frac{CPU_{Ave} + Disk_{Ave} + Net_{Ave}}{CP}}\)

2. Calculating FC: Once M is determined, the fragment cardinality (FC), which is the desired number of tuples per fragment, is calculated. It is the average number of tuples retrieved by a query (TuplesPerQ_Ave) divided by M. \(FC = \frac{TuplesPerQ_{Ave}}{M}\)

The relation is then physically partitioned into many small fragments, each containing approximately FC tuples and a unique range of the partitioning attribute[cite: 86, 9940]. The total number of fragments is the relation's cardinality divided by FC[cite: 9941].

HRPS根据应该执行平均查询的“最佳”处理器数量（M）来决定分片大小，而不是根据系统中的物理处理器总数。

1. 计算M: M代表能够最小化查询响应时间的期望并行度。它通过将响应时间RT(M)建模为处理器数量M的函数来计算，该函数考虑了查询的资源需求（CPU、磁盘、网络）和系统为每个额外处理器付出的开销（CP。其公式为： \(RT(M) = \frac{CPU_{Ave} + Disk_{Ave} + Net_{Ave}}{M} + M * CP\) 最佳的M值通过将该函数的一阶导数设为零来求解 ： \(M = \sqrt{\frac{CPU_{Ave} + Disk_{Ave} + Net_{Ave}}{CP}}\)

2. 计算FC: 一旦确定了M，就可以计算出分片基数（FC），即每个分片应包含的元组数量。它是平均查询检索的元组数（TuplesPerQ_Ave）除以M [cite: 145]。 \(FC = \frac{TuplesPerQ_{Ave}}{M}\) [cite: 145, 9937, 9938]

然后，关系被物理地分割成许多小分片，每个分片大约包含FC个元组，并对应分区属性的一个唯一值范围 [cite: 86, 9940]。总分片数量为关系的总基数除以FC [cite: 9941]。

---

题目 3: 分区策略对比 (Partitioning Strategy Comparison)

• EN: Consider a system where the number of physical processors (N) is greater than the optimal degree of parallelism (M) for an average query (i.e., N > M). For a query that retrieves a range of tuples, how would the Hash, Range, and Hybrid-Range partitioning strategies differ in the number of processors they utilize?
• 中文: 假设一个系统中，物理处理器数量（N）大于平均查询的最佳并行度（M）（即N > M）。对于一个检索一定范围元组的查询，哈希、范围和混合范围这三种分区策略在所使用的处理器数量上有何不同？

答案/Answer: In the scenario where N > M, the three strategies behave differently:

• Hash Partitioning: Because it cannot localize range queries, the hash strategy must direct the query to all N processors, incurring unnecessary overhead for startup, communication, and termination on more processors than is optimal.
• Range Partitioning: This strategy will decluster the relation into N large fragments. A query will typically overlap the range of only one or two fragments. Therefore, it will direct the query to only 1 or 2 processors, using fewer than the optimal number of processors and leading to a longer response time for resource-intensive queries.
• Hybrid-Range Partitioning (HRPS): HRPS partitions the relation into many small fragments independent of N. A query that spans TuplesPerQ tuples will overlap approximately M fragments (TuplesPerQ / FC = M). Since these fragments are distributed across the N processors in a round-robin fashion, the query will be localized to approximately M processors, which is the optimal number.

在N > M的场景下，三种策略表现不同：

• 哈希分区: 由于无法将范围查询本地化，哈希策略必须将查询定向到全部N个处理器，这在比最佳数量更多的处理器上产生了不必要的启动、通信和终止开销。
• 范围分区: 该策略会将关系分区成N个大分片。一个查询通常只会与一或两个分片的范围重叠。因此，它只会将查询定向到1到2个处理器，使用的处理器数量少于最佳值，导致资源密集型查询的响应时间变长。
• 混合范围分区 (HRPS): HRPS将关系分割成许多与N无关的小分片。一个跨越TuplesPerQ个元组的查询将大约与M个分片重叠（TuplesPerQ / FC = M）。由于这些分片以轮询方式分布在N个处理器上，该查询将被本地化到大约M个处理器上，这正是最佳数量。

---

题目 4: 混合工作负载 (Mixed Workload)

• EN: For a mixed workload with conflicting requirements (e.g., a mix of very small, low-resource queries and very large, high-resource queries), why does HRPS provide superior throughput compared to both pure Range and pure Hash partitioning?
• 中文: 对于具有冲突需求（例如，混合了资源需求极小的小查询和资源需求极大的大查询）的混合工作负载，为什么HRPS能提供比纯范围分区和纯哈希分区都更优的吞吐量？

答案/Answer: HRPS provides superior performance because it is the only strategy that can satisfy the conflicting partitioning requirements of the mixed workload[cite: 432].

• Range partitioning would perform well on the small queries by localizing them, but it would create a bottleneck for the large queries by executing them sequentially on only a few processors, thus lowering the overall system throughput[cite: 460, 462].
• Hash partitioning would perform well on the large queries by parallelizing them across all processors, but it would degrade system throughput by incurring high overhead on the numerous small queries by unnecessarily sending them to all processors[cite: 459, 462].
• HRPS resolves this conflict. It declusters the relation into many small fragments. Small queries only touch one or a few fragments and are thus localized to a small number of processors (similar to Range). Large queries span many fragments and are thus executed in parallel across many processors (similar to Hash). By providing the appropriate execution paradigm for both query types, HRPS outperforms the other two strategies[cite: 458, 500].

HRPS之所以能提供更优的性能，是因为它是唯一能够满足混合工作负载中相互冲突的分区需求的策略 [cite: 432]。

• 范围分区通过将小查询本地化执行而表现良好，但它会通过在少数处理器上顺序执行大查询而形成瓶颈，从而降低了系统的总吞吐量 [cite: 460, 462]。
• 哈希分区通过将大查询并行化到所有处理器上而表现良好，但它会不必要地将大量的小查询发送到所有处理器，从而产生高昂的开销，降低了系统吞吐量 [cite: 459, 462]。
• HRPS解决了这一冲突。它将关系分割成许多小分片。小查询只触及一个或少数几个分片，因此被本地化到少数处理器上执行（类似于范围分区）。大查询则跨越许多分片，因此能在多个处理器上并行执行（类似于哈希分区）。通过为两种类型的查询都提供了合适的执行模式，HRPS的性能超越了其他两种分区策略 [cite: 458, 500]。

---

题目 5: 数据倾斜 (Data Skew)

• EN: How does the Hybrid-Range Partitioning Strategy (HRPS) provide support for relations with a non-uniform distribution of partitioning attribute values (i.e., data skew)?
• 中文: 混合范围分区策略（HRPS）是如何为分区属性值分布不均（即数据倾斜）的关系提供支持的？

答案/Answer: HRPS handles skewed data distributions because its fragmentation is based on cardinality (a fixed number of tuples per fragment, FC), not on the range of the attribute's values[cite: 549, 550].

If a particular attribute value is very frequent (a "hot" value), those tuples will not be placed into a single fragment. Instead, after sorting the relation, these tuples will be distributed among several consecutive fragments, each containing FC tuples[cite: 552, 553]. Since fragments are assigned to physical processors in a round-robin fashion, these multiple fragments containing the same hot value will be placed on different processors[cite: 553].

As a result, an exact-match query on this hot value will be directed to multiple processors for parallel execution, naturally balancing the load and avoiding the hotspot that would have occurred with traditional range or hash partitioning, where all tuples with the same value would go to a single processor[cite: 554].

HRPS能够处理数据倾斜，因为它的分片是基于基数（每个分片包含固定数量的元组，FC），而不是基于属性值的范围 [cite: 549, 550]。

如果某个特定的属性值出现得非常频繁（一个“热点”值），这些元组不会被放在同一个分片里。相反，在对关系进行排序后，这些具有相同值的元组将被分配到多个连续的分片中，每个分片包含大约FC个元组 [cite: 552, 553]。由于分片是以轮询方式分配给物理处理器的，这些包含相同热点值的多个分片将被放置在不同的处理器上 [cite: 553]。

因此，一个针对此热点值的精确匹配查询将被定向到多个处理器上并行执行，从而自然地实现了负载均衡，避免了传统范围或哈希分区（这两种策略会将所有相同值的元组都发送到单个处理器）下会形成的热点问题 [cite: 554]。

Grasper

Grasper 的架构主要包括：

• 客户端 (Clients)：通过 TCP/IP 连接到查询服务器，提交查询并接收结果。
• 查询服务器 (Query Servers)：由多个节点组成，通过高性能的 RDMA 网络连接。每个服务器包含两个关键组件：
  • 数据存储 (Data Store)：负责在多台机器上存储分区后的属性图数据。
  • 查询引擎 (Query Engine)：负责解析和执行查询。
• 主节点 (Master)：监控各个查询引擎的负载情况，并将来自客户端的查询分配给合适的服务器。

混合式原生图存储与 RDMA

Grasper 将每个服务器的内存分为两部分：

• 普通内存 (Normal Memory)：存储本地访问的数据，主要是图的拓扑结构（即顶点和边的连接关系）和查询的中间结果。
• RDMA 内存 (RDMA Memory)：存储可以被其他服务器远程访问的数据，主要是顶和边的标签和属性值。这部分内存构成了一个分布式的、支持 RDMA 的键值存储（KVS）。

为什么这么设计？

• 分离存储：图的拓扑结构（连接关系）和属性（描述信息）被分开存储。拓扑信息存储在本地，以支持高效的图遍历操作。属性信息通过 RDMA 进行低延迟的远程访问。
• 负载均衡：如果将属性和顶点/边一起分区，可能会因为不同顶点/边属性数量差异巨大而导致数据分布不均和负载失衡。分开分区可以更好地均衡存储和计算负载。
• 发挥 RDMA 优势：RDMA 是一种允许网络中的计算机直接访问对方内存的技术，它绕过了操作系统，支持零拷贝传输，从而提供了极低的延迟和非常高的带宽。Grasper 利用单边 RDMA 读/写操作来高效地远程获取属性数据和进行节点间通信。

Expert Model (专家模型)：核心查询执行引擎

这是 Grasper 最核心的创新。它不是简单地一个线程处理一个查询，而是提供了一种更精细、更高效的查询处理机制。

Expert Model 的三大特性：

1. 自适应并行度控制 (Adaptive Parallelism Control)：
2. 量身定制的优化 (Tailored Optimizations)：
3. 本地化感知的线程绑定和负载均衡 (Locality-Aware Thread Binding and Load Balancing)：

1. BG Benchmark

1.1 核心概念与目标

• BG 基准测试的定义和目的
  • BG是一个用于评估数据存储系统处理交互式社交网络动作性能的基准测试。
  • 它的核心目标是量化地比较不同的数据存储系统（如SQL、NoSQL、CASQL等）及其设计选择 。
  • 可用于：
    • 比较不同的数据存储系统。
    • 评估数据存储系统中的替代设计权衡（如物理数据设计、不同形式的一致性）。
    • 量化数据存储在面临故障时的性能特征（如CAP定理中的CP或AP）。
    • 帮助应用开发者选择最合适的解决方案。
• 性能评估的“大局” (Big Picture)
  • 对于传统的数据库管理系统（DBMS），重点关注性能（响应时间、吞吐量），因为通常假设结果质量（准确性、精确性、召回率）必须是100%。
  • BG基准测试通过将不可预测数据量（Unpredictable Data）提升为一流指标，打破了这一假设，并将其纳入服务水平协议（SLA）进行量化评估 。
• 性能与结果质量的权衡
  • BG的验证阶段可以计算不可预测数据（即陈旧、不一致或简单无效的数据）的数量。
  • CASQL（Cache Augmented SQL，即带缓存的SQL）可以通过提高TTL（Time To Live）来提高性能（更快的响应时间），但同时会增加不可预测数据（陈旧数据）的量，体现了性能与一致性的权衡。
  • 对于某些应用（如银行），一致性是必须的；对于社交网络（如Facebook），可用性可能更受青睐 。

1.2 关键指标 (Key Metrics)

BG基准测试使用服务水平协议 (SLA)来量化性能，并基于SLA计算两个核心评分指标：

• 服务水平协议 (SLA)
  • SLA要求至少有一定百分比 (\(\alpha\)) 的请求在规定的最大响应时间 (\(\beta\)) 内完成，同时不可预测数据的百分比 (\(\tau\)) 必须低于某个最大值，且持续时间 \(\Delta\)。
  • 示例SLA：95%的请求响应时间等于或快于100毫秒 (\(\beta=100\text{ msec}\))，且在固定时长内不可预测数据量不超过0.1% (\(\tau=0.1\%\)) 。
• Social Action Rating (SoAR)
  • 定义：满足指定SLA要求的最高吞吐量（每秒完成的动作数）max completed actions/sec under SLA 。
• Socialites
  • 定义：满足指定SLA要求的最大并发线程数（即最大的 T 值） 。它量化了数据存储的多线程能力。max concurrent threads under SLA.
• 其他指标
  • 响应时间 (Response Time)：用户发出请求到收到响应的经过时间。
  • 百分位数 (Percentiles)：响应时间低于此值的一个给定百分比的响应时间（例如，95%的请求响应时间低于95th百分位数） 。
  • 吞吐量 (Throughput)：系统处理请求的速率 。
  • 新鲜度置信度 (Freshness Confidence)：在更新发生后，一定百分比的请求能在特定时间 T 内观察到最新值 。

1.3 社交网络动作 (Social Actions)

BG基准测试通过模拟社交网络应用的交互式动作来生成工作负载。

• 典型动作 (Simple Operations)
  • 包括View Profile (VP)、List Friends (LF)、Invite Friend (IF)、Accept Friend Request (AFR)、Post Comment on a Resource (PCR) 等 。
• Read/Write动作分类
  • VP、LF、VFR (View Friend Requests)、VTR (View Top-K Resources)、VCR (View Comments on a Resource) 属于读取 (Read) 动作 。
  • IF、AFR、RFR (Reject Friend Request)、TF (Thaw Friendship)、PCR、DCR (Delete Comment from a Resource)、SR (Share Resource) 属于写入 (Write) 动作 。
• 动作对性能的影响
  • 图像大小：图像的存在和大小对VP动作的性能（SoAR）有显著影响。图像越大，SoAR越低。
  • List Friends (LF)：在测试中，对于LF动作，关系型数据库（SQL-X/CASQL）的表现优于文档存储（MongoDB），表明在这种情况下，关系连接不一定比文档处理慢。
• Why SNAs are Expensive：They involve multi-hop graph traversal, multiple relationships, multiple entities, and multiple reads/writes within a single action. 涉及多跳图遍历、多实体、多关系，一次动作包含多次读写，复杂度远超过简单 KV 或 SQL 负载。

1.4 BG的架构与实现

• 分布式架构
  • BG使用共享无架构 (Shared-nothing architecture)，通过BG协调器 (BGCoord) 和多个BG客户端 (BGClients) 实现可伸缩的基准测试框架 。
  • BGCoord：负责计算SoAR/Socialites、管理BGClients、分配工作负载和聚合最终结果。
  • BGClients：是工作进程，负责创建Schema、加载数据、生成工作负载、测量性能和计算不可预测数据 。
• 可伸缩性
  • 为确保并发的Socialites（用户）的唯一性，BG将社交网络数据逻辑上划分为 N 个自我包含的片段 (self-contained fragments)，分别分配给 N 个BGClient 。
  • BGCoord通过调整每个BGClient模拟的线程数，确保所有BGClient大致同时终止，从而补偿节点之间的性能差异 。
  • 采用D-Zipfian分布（分布式Zipfian）来确保在不同数量的BGClient下生成相同的请求分布。
• 快速评分技术 (Quick Rating)
  • 启发式搜索 (Heuristic Search)：为避免从 T=1 开始进行耗时的穷尽搜索，BGCoord使用启发式搜索（如倍增和二分查找）来快速找到SoAR和Socialites的最佳 T 值。
  • 敏捷数据加载技术 (Agile Data Loading)：
    • 数据库镜像加载 (DBIL)：通过创建和重复使用数据库的磁盘映像，可将加载时间从天减少到分钟。
    • RepairDB：通过将数据库恢复到实验前的原始状态，可将加载时间从天减少到10小时。

1.5 质量结果指标 (Quality of Results Metrics)

这是BG将结果质量纳入评估的扩展，主要应用于预测系统或弱一致性系统。

• 混淆矩阵 (Confusion Matrix)

  • 定义了四种结果：True Positive (TP), True Negative (TN), False Positive (FP), 和 False Negative (FN) 。

• 准确率 (Accuracy)

  \[ Accuracy=\frac{TruePositives+TrueNegatives}{TotalPredictions}。 \]

  • 局限性：在数据高度不平衡时可能产生误导（例如，预测所有患者都健康，准确率仍可达99.9%，但忽略了少数的病患） 。

• 精确率 (Precision)

  \[ Precision=\frac{TruePositives}{TruePositives+FalsePositives}。 \]

  • 意义：系统所有“判断为阳性”的结果中，实际正确的百分比 。
  • 局限性：可能遗漏大量实际阳性（例如，只预测100个欺诈交易中的1个，精确率100%，但漏掉了99%的欺诈） 。

• 召回率 (Recall)

  \[ Recall=\frac{TruePositives}{TruePositives+FalseNegatives}。 \]

  • 意义：所有实际为阳性的结果中，系统正确识别的百分比（完整性）。

1.6 CAP定理和NoSQL (CAP Theorem and NoSQL)

• CAP定理

  • 多节点系统在任何给定时间点，最多只能提供以下三种保证中的

    两种。

    • C - Consistency (一致性)：读取请求能观察到最近的写入操作，否则返回错误。
    • A - Availability (可用性)：请求能观察到非错误响应，即使有节点故障。
    • P - Partition Tolerance (分区容错性)：系统在节点之间无法通信时仍能继续运行 。

• NoSQL运动 (NoSQL Movement)

  • NoSQL的定义不一，但通常包括：忘记第一范式 (1NF) 、不使用SQL前端（简单调用接口）、可扩展性 (Scale) 、提供弱于ACID的BASE（Basically Available, Soft state, Eventually consistent）一致性、高效使用分布式索引和内存 、动态添加新属性。

• 最终一致性 (Eventually Consistent)

  • DynamoDB等系统默认使用最终一致性读取。
  • 这意味着响应可能不会反映最近完成的写入操作结果，但重复读取后会最终返回最新项。
  • 风险：不适用于需要强一致性的事务处理（如银行转账），可能导致金钱损失。最终一致性读取的成本通常是强一致性读取的一半 。

2. CAMP

2.1 基础：为什么需要 CAMP？

关键问题： LRU 只看“最近被访问时间”，但 不看大小 (size)、不看计算代价 (cost)。 在有多种应用、不同价值的 key-value 的大规模缓存系统中（如 Facebook/Twitter memcached），LRU 很容易做出糟糕选择。

典型例子

• 用户 profile：几 ms 的轻查询 → 低 cost
• 广告/ML 结果：训练几个小时 → 高 cost ，LRU 会因为 profile 访问频繁而把广告结果全赶出去，造成巨大计算浪费。

2.2 LRU 回顾（为什么不够）

LRU 用一个 doubly-linked list + hash table 实现 O(1) 更新。

优点：快 缺点：信息太少

• 不考虑大小 → 大对象可能挤掉更多小对象
• 不考虑代价 → 高成本对象被轻易驱逐
• 在 memcached 中导致 整体性能不稳定

2.3 人工调参（Human Tuning）为什么不行？

Facebook 真实做法（NSDI 2013）

• 将内存分成多个 pool
• 每个 pool 只存“相似 cost/size 的 key-value”
• 每个 pool 用 LRU

问题：

• 人类无法对 万亿级 key-value 做准确分组
• 工作负载每天变化 → Pool 要不停调整
• 等于“将军把自己的军队分散”（divide resources） → 容易失败

因此需要：自动化、动态、自适应、不分区 的方法。

2.4 GDS（GreedyDualSize）概念 – CAMP 的基础

GDS 引入一个优先级值： H(p) = L + cost(p)/size(p)

• L：全局变量，随时间单调递增
• cost/size：对象的“价值密度”
• H 越低，越容易被驱逐
• 每次访问 p 时：H(p) 重新设为 L + cost/size（变“新鲜”）

重点理解：

• 如果 A 的 cost/size 是 B 的 3 倍，A 在 cache 中 大约会活 3 倍时间
• 驱逐最小 H 的对象 → 综合考虑 最近性 + 成本 + 大小

缺点：必须维护一个优先队列（heap），每次调整都要 O(log n)，在数千万 KV 时太慢

2.5 CAMP 的核心创新（考试重点）

CAMP 是 GDS 的 高效可落地实现 关键思想：

(1) 将 cost/size “分桶（rounding）” → 只保留 p 个高位 bit

这样所有 KV 被分成有限数量的 cost/size 桶：

• 每个桶内部：形成一个 LRU queue
• 每个桶只维护“队首的 H 值”
• 一个小 heap 仅存“每个队首的 H” → log(#queues)，而非 log(#items)

效果：

• 实际只维护几十上百个 LRU 队列
• 更新成本接近 LRU 的 O(1)

(2) 桶内 LRU = 自动按 H 值排序（关键直觉）

因为：

• 同 bucket 的 cost/size 一样
  • \(H = L_{at\ last\ access} + cost/size\)
• 越早访问，L 越小 → H 越小 → 自然排在队头

因此：

用 LRU 就能保持按 H 排序，无需额外排序结构 这是 CAMP 能高效落地的根本原因。

(3) 驱逐策略

从所有 LRU 桶中取“队头 H 最小”的那个 → 驱逐

类似 GDS，但：

• 更快
• H 值是近似（但证明：误差 ≤ 2⁻(p-1)）

(4) CAMP 的四大特性（总结）

1. 性能 O(1) 级别，和 LRU 一样快
2. 近似 GDS，驱逐质量几乎一致
3. 同时考虑 recency + size + cost
4. 不需要人工调参、不分 pool、自适应 workload

2.6 CAMP 的精度参数 p

• 保留的 cost/size 高位 bit 越多 → 精度越高 → 越接近 GDS
• p 越小 → bucket 越少 → heap 越小 → 开销更低

证明：CAMP 的竞争比 = (1 + 2⁻(p−1))·k → 精度可控且“可渐进逼近 GDS”

考试常见问法： “p 越大越好吗？”

不是。p 越大 → queue 越多 → heap 更新开销变大。但实验显示小 p 已经足够好。

camp就是把cost-to-size ratio差不多的那些内容group到一起，放到一个LRU里管理，然后所有的group放到一个最小堆里。这里group的数量ideal的话不超过10个

为了group到一起，要对每个cost-to-size ratio的值进行四舍五入的约分，传统的约分就是把每个数的后四个bit抹掉变成0，好无趣，好无聊，而camp的约分就是保留最高位开始的4位bit，好好玩（ppt 66页）

camp的约分可以只保留最高位的一位数字，效果其实也不错

终极复习路线图（3 分钟速记版）

① LRU 只看时间 → 不够聪明

因为不看 cost 和 size

② 人工 pool 方式不可靠，难维护

③ GDS = L + cost/size → 综合价值指标 H(p)

但太慢（heap on millions KV）

④ CAMP = 高效版 GDS

• cost/size rounding → 分桶
• 每桶 = LRU queue
• heap 只管每个桶的队头
• 近似 GDS，却和 LRU 一样快

⑤ 优点：快、准、自适应、无需人工

3. Raft

3.1 分布式一致性 / 共识（Consensus）基本概念

核心目标

• Agreement：所有非故障节点最终决定同一个值
• Non-triviality：决定的值来自提案
• Termination：非故障节点最终能做出决定

与一致性相关的协议类型

• Clock synchronization（钟同步）
• Leader election（选主）
• Consensus（重点）
• Byzantine agreement
• Atomic multicast
• Replication
• Transaction commit

CAP 定理

不可能同时满足：

• Consistency
• Availability
• Partition Tolerance

实际系统几乎都选择 P + (C 或 A)。

3.2 FLP 不可能性

在 异步网络 + 节点可能宕机 情况下：不存在保证终止的共识协议（可能永不结束），但 安全性（safety）可以保证，所以 Paxos / Raft 等只保证 safety，不保证暴力终止。

3.3 Paxos：单值共识（single-decree Paxos）

角色

• Proposer（提案者）
• Acceptor（投票者）
• Learner（学习者）

消息流 & 三阶段：

• Phase 1: Prepare
  • Proposer 发送 Prepare(n)
  • Acceptor 若 n > max，则回复 Promise(n, last_accepted) 并承诺不再接受编号更小的提案
• Phase 2: Accept
  • Proposer 按规则选择 value
  • 发送 Accept(n, v)
  • 多数 Acceptor 接受后，value 被“选定”
• Phase 3: Learn
  • Proposer 或 acceptor 告知 Learner（Chosen(v)）

关键安全性保证（为什么不冲突）

• Acceptors 永不接受小编号
• 新提案必须继承先前已记录的最高编号 value 多个提案可能被选中，但值不会不一致

关键问题 & 解决方式

• 多 proposer 冲突 → 不保证活性（liveness）
• 需要 leader election（但不是协议本身一部分）
• 使用超时 + exponential backoff 解决冲突

3.4 Multi-Paxos（多项共识 / 日志复制）

用于 连续多个 log entry 的共识（RSM 必备）

关键优化：

1. 长时间保持同一个 leader
2. Phase 1（Prepare）可以一次性对所有 slots 预处理
3. 后续每条 log 只需要 Phase 2 一轮 RTT 完成写入（与 Raft 一样的性能）

3.5 Raft：可理解性更高的共识协议（重点）

Raft 目标：与 Paxos 同等安全，但更易理解、更易实现

核心思想：强 leader（strong leader）

• 所有 log 由 leader 管理、由 leader 发出
• 数据流 单向：leader → followers
• 没有 Paxos 那种并发 proposer 混乱

Raft 分解为三个独立子问题（可单独理解）：

1. Leader Election 选主
2. Log Replication 日志复制
3. Safety（尤其是 Leader Completeness）

Raft 关键机制

（1）Leader Election（随机选举）

• follower 选举超时 → 成为 candidate
• candidate 给所有节点发 RequestVote
• 获得多数票 → 成为 leader

主要特性：

• 随机选举超时避免平票
• term 单调递增

（2）日志复制（AppendEntries）

Leader：

• 接收客户端命令 → append 到自己 log
• 给 followers 发送 AppendEntries
• 多数 follower append 成功 → commit

Log rules：

• leader 永远 只追加（append-only）
• followers 从 leader 回滚冲突 entry

（3）Raft Safety

5个重要安全性：

1. Election Safety：每个 term 最多一个 leader

2. Leader Append-Only

3. Log Matching Property：相同 index+term → 前缀一致

4. Leader Completeness：已 commit 的 entry 必然出现在之后所有 term 的 leader 中

5. State Machine Safety：相同 index 不会执行不同命令

Membership change（Joint Consensus）

特点：

• 使用 overlapping majority
• 在两种配置共同存在时，仍保持安全性

3.6 Replicated State Machine（RSM）

模型假设

• 多台服务器的执行必须 确定性
• 必须对所有操作建立一致的顺序（total order）

实现方式：

• 使用 Paxos / Raft 来 对输入序列达成一致
• 应用到本地状态机

应用：

• Chubby, Zookeeper, 现代数据库、元数据服务

3.7 故障模型（考试必考）

1. Fail-stop（假设）

• 节点只会突然停止，不会说谎 ➡️ Paxos / Raft 支持的模型

2. Byzantine（恶意）

• 篡改消息、撒谎、作弊 ➡️ 需要 PBFT 等协议，远比 Paxos / Raft 复杂

3.8 Primary-Backup vs RSM

Primary-backup（主备）

• Primary 处理请求
• Backup 做状态复制 缺点：性能差，failover 慢，复杂

RSM（复制状态机）

• 所有节点执行同一操作序列
• 更强的一致性和容错能力
• 现代系统主流方式

两阶段提交 (Two-phase Commit, 2PC)

• Phase I (收集/准备)：协调者 (Coordinator) 发送 prepare 消息给所有参与者。所有参与者必须返回 ready，否则事务必须中止 。
• Phase II (提交)：协调者收到所有参与者的 ready 后，做出提交决定并发送 commit 消息。参与者收到后返回 ack 。
• 重要特性：一旦参与者回复 ready，它就必须将更新记录在稳定存储中，并准备好提交或中止。
• 故障问题：如果协调者在收到所有 ready 和发送 commit/abort 决定之间失败，参与者将进入等待状态（不确定窗口），必须等待协调者恢复才能知晓结果，无法单方面决定中止 。

BASE 事务 (BASE Transactions)

• BASE = Basically Available, Soft-state, Eventually consistent（基本上可用，软状态，最终一致）。
• 避免 2PC，只使用本地事务 。
• 通过可靠消息传递（例如 Kafka 或 Multi-Paxos/Raft 共享日志）将更新排队发送给远程站点，并异步执行 。
• 优势：高可用性、良好性能、仅需本地事务 。
• 劣势：最终一致性、无隔离性/冲突解决 。
• exactly once (恰好执行一次) 问题：对于非幂等 (non-idempotent) 操作（如银行转账），需要通过将上次执行的操作的序列号存储在数据库中（作为同一本地事务的一部分），来确保恰好执行一次 。

最终复习建议

重点掌握：

概念类

• Consensus 三大性质（agreement / non-triviality / termination）
• CAP 的真正含义（并非“选两项”）
• FLP 不可能性

Paxos

• 三阶段流程
• 为什么需要 prepare
• 多 proposer 时如何保持安全
• leader election 不是协议本身

Multi-Paxos

• 为什么能做到 1 RTT
• 与单 Paxos 的区别

Raft

• 三大模块
• 五大 safety properties
• 日志一致性规则
• 选主流程
• membership change

RSM & Replication

• 日志复制 → 状态机执行
• 为什么必须 deterministic
• 客户端如何处理重试

4. IQ

4.1 Motivation 动机：为什么需要 Cache-Augmented SQL？

EN

• Modern applications (social networks, chat apps, messaging systems) must support millions of read requests per minute.

• SQL DBMS are slow because of:

  • Buffer pool manager

  • Latching

  • Locking

  • Logging

  • Hand-coded optimizations

    (Only ~7% instructions do useful work.) IQ

• Solution: Add a fast in-memory KVS (Memcached / Redis) in front of the DB.

• Reads hit the KVS → extremely fast response time.

• Writes still must update DB + maintain cache consistency.

中文

• 现代社交网络/消息系统需要每分钟处理 百万级读请求。

• SQL 数据库太慢，因为：

  • buffer pool 管理

  • latch 加锁

  • lock 锁管理

  • 日志记录

  • 多线程同步开销

    （有效工作不到 7%。） IQ

• 解决方案：加一个内存 KVS（Memcached/Redis）作为前置缓存。

• 读走缓存 → 极快。

• 写必须更新数据库，并保持缓存一致性。

4.2 The Problem: 为什么会产生 Stale Data？（核心）

The DBMS does not know the KVS exists;

The KVS does not know DBMS exists.

→ All coordination is left to the application, which causes race conditions.

DBMS 不知道有缓存，缓存也 不知道有数据库。所有一致性要靠应用代码完成，极易写出竞态条件。

Two major causes:

1. Undesirable race conditions

   Example: deletion + lookup interleave → deleted row reappears in cache.

2. Snapshot Isolation (MVCC) inserting stale data

   • SI guarantees “repeatable reads,” NOT external consistency.
   • A read may see an old version V1 while DB commits V2.
   • The application then inserts stale V1 into cache.

两大导致陈旧数据（stale data）的原因：

1. 不良竞态（Undesirable Race Conditions）

   例如：管理员删除 Alice → 用户同时登录 → 旧数据被重新放入缓存。

2. 快照隔离（Snapshot Isolation, MVCC）产生陈旧值

   • SI 只保证事务内部一致，不保证外部可串行化。
   • 读会读到旧版本 V1，而 V2 已经提交。
   • 应用把 V1 写回缓存 → 缓存比数据库更旧。

4.3. Three Existing Techniques 缓存更新的三种方式（重要考点）

这三种方式都可能造成 stale data，IQ Framework 就是为了解决这个问题。

(1) Invalidate 失效（删除缓存键）

1. Application computes affected key(s)

2. Deletes them from KVS

3. Next lookup → KVS miss → recompute from DB

4. 计算受影响的 key

5. 从 KVS 删除

6. 下次访问时从数据库重建缓存

(2) Refresh / Refill（读–改–写）

1. Read key from KVS

2. Modify value in app memory

3. Write back new value

4. 从缓存读取 key

5. 在应用程序中修改 value

6. 把修改后的值写回缓存

(3) Incremental Update（增量更新 δ）

1. Application sends deltas: increment, append, prepend

2. KVS applies the operator directly

3. 应用发送增量更新（加1、append、prepend 等）

4. KVS 直接对 value 做修改

问题：Three approaches 都可能导致 stale data

论文实验数据（BG benchmark）：并发≥10 时就开始出现陈旧数据。

4.4 IQ Framework（重中之重）

论文 & 课堂核心贡献。

它通过 两个非阻塞 lease（I lease + Q lease）提供强一致性。

4.4.1 Session 定义

EN

A session consists of:

• At most one DBMS transaction
• Followed by (or preceded by) one or more KVS operations
• Session must acquire leases like 2PL

中文

Session 定义：

• 至多一个数据库事务
• 前后包含若干 KVS 操作
• Session 必须像两段锁协议一样获取/释放 leases

4.4.2 I Lease（Inhibit）— 为读 miss 提供可串行化

EN

• Granted to read sessions experiencing a KVS miss
• Only one I lease can exist for a given key
• Protects DB round trip + cache population
• Other sessions must wait / retry
• If I lease is invalidated, KVS must IGNORE the write-back

中文

• 当读操作遇到 KVS miss 时，获得 I lease
• 一个 key 最多允许一个 I lease
• 保护读 DB + 填充缓存的过程
• 其他 session 只能等待或重试
• 若 I lease 在过程中被抢占（被 Q lease 否决），该 session 的写入会被忽略

4.4.3 Q Lease（Quarantine）— 为写提供隔离/序列化

EN

• Required for write/update/delete/δ/RMW

• Guarantees the write session sees its own writes

• If encountering an existing I lease:

  → Invalidate I lease (读 session 被中止)

• Prevents SI from inserting stale values

• Prevents write-write and write-read races

中文

• 写/删/RMW/增量更新都必须先获取 Q lease

• 确保写 session 能看到自己写入的最新值

• 如果遇到 I lease：

  → 直接使 I lease 失效（抢占），防止读写冲突

• 解决 MVCC stale data 问题

• 解决写写、写读竞态

4.5. Why IQ Works? 为什么 IQ 能提供强一致

Because the system enforces:

1. Single writer per key via Q lease

2. Single DB lookup per key via I lease

3. Writes override stale reads

4. All stale write-backs ignored

5. Cache + DB are always in equilibrium

   (“equal effect on both side”)

中文

IQ 提供强一致的原因：

1. Q lease 保证 同一 key 同一时刻只有一个写者

2. I lease 保证 只有一个读会去 DB 查询

3. 写操作对读具有优先级

4. 被抢占的 I lease 产生的写回会被 自动忽略

5. 缓存与数据库永远保持“平衡”

   —— 两者对数据的影响是一致的

4.6 ACID at Session Level

论文指出 IQ 实现的是 session-level ACID：

Property	EN	中文
Atomicity	Both DB + KVS operations apply together; may delete KVS keys	原子性：DB/KVS 要么一起成功，要么一起失败，可通过删除 KVS key 实现
Consistency	Session transitions DB & KVS from one valid state to another	一致性：Session 让 DB/KVS 从一个有效状态到下一个有效状态
Isolation	Session sees its own updates; others cannot	隔离性：Session 能看到自己的写，其它 session 看不到
Durability	Guaranteed by RDBMS; KVS 只是缓存	持久性：由数据库保证，KVS 本身是易失的

4.7 押题

编号	中文问题	Question in English	答案要点 (Key Answer Points)
Q1	为什么在缓存增强型 SQL 系统 (CADBMS) 中难以实现强一致性？	Why is it difficult to achieve strong consistency in a Cache Augmented SQL System (CADBMS)?	中文: RDBMS 和 KVS 彼此不感知 。应用程序可能因为不期望的竞态条件 和 快照隔离 (Snapshot Isolation) 机制，将陈旧数据插入缓存 。这导致 KVS 状态与 RDBMS 状态发生背离。 English: The RDBMS and the cache (KVS) are unaware of one another. The application may insert stale data in the cache due to undesirable race conditions and Snapshot Isolation, causing the cache state to diverge from the RDBMS state.
Q2	解释 IQ 框架中 I 租约（Inhibit Lease）的作用和工作机制。	Explain the purpose and mechanism of the Inhibit Lease (I Lease) in the IQ Framework.	中文: I 租约用于解决 Thundering Herd 问题 10101010。它确保对同一 Key 的缓存缺失，最多只有一个会话被授权去查询 RDBMS、计算缺失值并填充缓存。所有其他并发请求必须 Back Off（退避） 。 English: The I Lease solves the Thundering Herd problem It ensures that on a cache miss for a key, at most one session is granted the lease to query the RDBMS, compute the missing value, and populate the cache. All other concurrent requests must Back Off.
Q3	解释 IQ 框架中 Q 租约（Quarantine Lease）的作用和工作机制，以及它如何与 I 租约互动。	Explain the purpose and mechanism of the Quarantine Lease (Q Lease) and how it interacts with the I Lease.	中文: Q 租约用于确保写操作（Write/Delete/R-M-W）的强一致性。写会话必须获得 Q 租约。当 Q 租约请求遇到现有 I 租约时，IQ 框架会撤销（void/invalidate）该 I 租约并授予 Q 租约。这使得持有被撤销 I 租约的读会话后续的缓存插入操作被 KVS 忽略，从而防止陈旧数据写入缓存。 English: The Q Lease ensures strong consistency for write operations. A writing session must obtain a Q Lease. When a Q Lease request encounters an existing I Lease, the IQ framework voids/invalidates the I Lease and grants the Q Lease. The KVS then ignores the subsequent insert operation by the invalidated reader , preventing stale data from being written to the cache.
Q4	为什么 IQ 框架选择使用“租约（Lease）”而非“锁（Lock）”来实现并发控制？	Why does the IQ Framework use a "Lease" instead of a "Lock" for concurrency control?	中文: 租约具有有限的生命周期（fixed life time）。这使得 KVS 在托管应用程序的节点失败或网络中断时，能够自动释放租约并继续处理操作 。如果使用锁，故障可能导致 Key 被无限期持有，数据变为不可用。 English: A Lease has a fixed life time. This allows the KVS to release the lease automatically and continue processing operations in the presence of node failures or network detachments. If a lock were used, failures could cause the data to be held indefinitely and become unavailable.
Q5	在 IQ 框架中，使用 Refresh/Refill 范式时，Q 租约的兼容性矩阵与 Invalidate 范式有何关键区别？为什么？	What is the key difference in the Q Lease compatibility matrix for Refresh/Refill vs. Invalidate, and why?	中文: 在 Refresh/Refill 中，Q 租约遇到 Q 租约的请求时，结果是 Reject and Abort requester（拒绝并中止请求者）。而在 Invalidate 中，结果是 Grant Q 。这是因为 Refresh/Refill (读-修改-写) 存在脏读（Dirty Read）的风险，需要 Q 租约的互斥性来防止并发写操作看到彼此未提交的中间状态。 English: In Refresh/Refill, a Q requesting lease encountering an existing Q lease results in Reject and Abort requester. In Invalidate, the result is Grant Q. This is because Refresh/Refill (Read-Modify-Write) risks Dirty Reads , requiring Q lease exclusivity to prevent concurrent writers from seeing each other's uncommitted intermediate states.

5. Map Reduce

5.0 MapReduce 是什么？（核心定义）

英文

MapReduce is a programming model and runtime framework for processing large datasets across thousands of commodity machines.

It automatically handles parallelization, fault tolerance, data distribution, and load balancing.

中文

MapReduce 是一种大规模数据处理模型与运行框架，可在成千上万台廉价机器上执行任务，并自动处理 并行化、容错、数据分布、负载均衡 等问题。

5.1 Motivation（动机）

英文

• Google has many large-scale computations:

  inverted index, link graph, term vectors, logs, query statistics.

• Data is huge → needs hundreds/thousands of machines.

• Hard problems:

  • parallel programming
  • data distribution
  • handling failures
  • load balancing

• Need a simple abstraction.

中文

• Google 要处理许多超大规模数据：倒排索引、网页图结构、Term Vector、日志、查询统计等。
• 数据量巨大 → 必须分布到数百、上千台机器。
• 难点：并行编程、数据分布、容错、负载均衡。
• 迫切需要一个简单的抽象屏蔽复杂性。

5.2 Why Not RDBMS ?（为什么不用关系数据库）

英文

• HTML pages are unstructured.
• Constant updates → not suitable for RDBMS.
• No need for transactions or crash recovery.
• Only need the ability to build inverted index.
• RDBMS restarts queries on failure ⇒ unacceptable for multi-day jobs.

中文

• HTML 页面是非结构化数据，不适合关系模式。
• 网页频繁变化，RDBMS 更新成本极高。
• 不需要事务与崩溃恢复。
• 仅需要构建倒排索引功能。
• RDBMS 遇到故障会重启整个查询 → 多天任务无法接受。

5.3 Commodity Hardware（廉价服务器）

英文

• Google prefers commodity PCs
  • cheaper to buy
  • cheaper to maintain
  • fail frequently
• MapReduce handles failures automatically.

中文

• Google 使用便宜的商用 PC：
  • 便宜易买
  • 维护成本低
  • 但容易故障
• MapReduce 利用框架自动处理故障。

5.4 MapReduce 两大函数（核心考试点）

Map()

Input: (key1, value1)

Output: list of (key2, value2)

Reduce()

Input: (key2, list of value2)

Output: aggregated values

5.5 Execution Pipeline（执行过程）

1. Split 输入切分

• MapReduce 将输入切成 M 份
• 通常 16MB–64MB（论文），PPT 讲 64MB

2. Master / Worker 启动

• 一个 master
• 多个 worker

3. Map 阶段

• Worker 读取 split
• 执行 map → 产生中间 key/value
• 写入本地磁盘（分成 R 份）

4. Shuffle 阶段（最重要）

• Reduce workers 从 map workers 拉取中间数据
• 按 key 排序
• 相同 key 聚在一起

5. Reduce 阶段

• 对每个 key 执行 reduce
• 输出到 R 个输出文件

6. 完成

• 用户消费输出文件
• 通常不需要合并，因为会作为下一轮 MapReduce 输入。

5.6 Fault Tolerance（容错机制）

Worker Failure

英文

• Master pings workers.
• If worker fails:
  • redo map tasks
  • redo reduce tasks in-progress
• Completed reduce tasks don’t redo (stored in global FS)

中文

• master 定期 ping worker。
• worker 掉线：
  • 该 worker 完成的 map 任务全部重跑
  • 正在运行的 reduce 任务重跑
• 已完成的 reduce 不需重跑（输出在全局文件系统）

Map 任务一定要重跑的原因（PPT 强调）

英文

Map output stored on local disk → lost if worker dies.

中文

Map 输出存在本地 → worker 掉线就丢失 → 必须重跑。

5.7 Deterministic Semantics（一致性语义）

英文

If map/reduce functions are deterministic, MapReduce guarantees the same result as a sequential execution.

中文

如果 map/reduce 是确定性的，MapReduce 保证输出与顺序执行一致。

5.8 Backup Tasks（Stragglers 问题）— 考试常考（样卷考了）

英文

To handle stragglers (slow workers), master launches backup tasks near the end of a job.

中文

为解决拖慢整体速度的慢 worker，master 会启动“备份任务”。

样卷题目：Define stragglers (5 Points), what causes them (5 Points) and how the MapReduce

framework addresses them (10 Points)?

答案：A machine that takes an unusually long time to complete one of the last few map or reduce tasks in a MapReduce computation is referred to as a straggler (5 Points).

One of the following would secure 5 Points for the cause:

1. Load imbalance

2. Hardware failure (a machine with a bad disk)

3. Scheduling system may have scheduled other tasks on the machine, causing it to execute the MapReduce code more slowly due to competition for resources (CPU, memory, local disk, or network bandwidth)

4. A bug in the code that slows down a processor: a bug in machine initialization code that caused processor caches to be disabled

To address stragglers, when a MapReduce operation is close to completion, the master schedules backup executions of the remaining in-progress tasks (10 Points).

5.9 Data Shipping vs Function Shipping（PPT 重点）

英文

• Map stage uses function shipping: send map function to where data lives.
• Reduce stage uses data shipping: data moves to reducers.

中文

• Map 阶段是函数下推（function shipping）：把 map 函数送到数据所在节点执行。
• Reduce 阶段是数据传输（data shipping）：把数据移动到 reducer。

5.10 Inverted Index（倒排索引）

map(doc, content) → emit(word, docID)

reduce(word, list(docID)) → sorted list, emit(word, docList)

5.11 常见 MapReduce Examples

1. Word Count
2. Distributed Grep
3. URL Count
4. Reverse Web Link Graph
5. Term Vector per Host
6. Inverted Index
7. Distributed Sort

所有例子都用同样模式：

map → shuffle → reduce

5.12 集群结构

硬件

• x86 机器
• 2–4GB DRAM（论文）
• 各节点通过 Gigabit Ethernet

共享架构

• Shared-nothing architecture
• Google File System (GFS) 提供数据复制
• Bigtable 存储结构化数据
• MapReduce 在 Bigtable 之上进行批处理

5.13 输入/输出格式

map(k1, v1) → list(k2, v2)

reduce(k2, list(v2)) → list(v2)

输入 key-value 与输出 key-value 类型不必相同。

5.14 Master Data Structure（考点）

master 存储：

• map 任务状态
• reduce 任务状态
• 中间文件（位置 + 大小）
• 分发到相应 reducer worker

5.15 Shuffle（最常考）

Shuffle groups intermediate values by key and distributes them to reducers.

Shuffle 将所有相同 key 的中间结果分组，并分发给对应的 reducer。

6. RAID

6.1 提出 RAID 的背景 / Motivation

CPU 与内存发展太快，但磁盘太慢

CN： CPU 和 DRAM 性能增长极快，但 HDD 受机械结构限制，seek + rotation 提升极慢，导致 I/O 成为瓶颈。

EN： CPU and DRAM performance grow rapidly, but HDD performance improves very slowly due to mechanical seek and rotation delays, leading to an I/O bottleneck.

Amdahl’s Law 表明 I/O 会限制系统性能

CN： 即使把 cache 提升 10 倍，如果程序有 10% 是 I/O，整体加速只有 5 倍，而不是 10 倍。

EN： Even if cache becomes 10× faster, if 10% of the workload is I/O, the overall speedup is only 5×, not 10×.

因此必须解决 I/O 性能问题

CN： 系统最终会被 I/O 限制，需要新的方式提升性能。

EN： The system eventually becomes dominated by I/O, requiring a new solution to improve performance.

6.2 为什么不是买大而贵的磁盘？ / Why Not SLED?

CN： 大型企业级磁盘（SLED）更贵、能耗大、IOPS/actuator 并不比小磁盘显著更好。

EN： SLEDs are expensive, consume more power, and their IOPS per actuator are not significantly better than inexpensive disks.

CN： 多个便宜小磁盘“并联”（array）可获得更高吞吐、更低价格、更大规模。

EN： Many inexpensive disks combined in an array provide higher throughput, lower cost, and better scalability.

6.3 RAID 的核心思想 / Key Idea of RAID

Striping + Redundancy

CN： RAID 使用条带化提升性能，并用冗余提升可靠性。

EN： RAID uses striping for performance and redundancy for reliability.

目标：

1. 高吞吐（large reads/writes）
2. 高 IOPS（small reads/writes）
3. 高可靠性（disk failure protection）

6.4 关键术语 / Terminology

（1）XOR：奇偶校验的核心

XOR = 无进位加法。可逆（A⊕B=Q → 已知 A 和 Q 可求 B）。

（2）Disk Block

磁盘以 block 为单位读写；1 block = 4KB = 8 个 512B sector。

（3）可靠性参数

• D：数据盘数量 number of data disks
• G：每组数据盘数 number of data disks per group
• C：校验盘数 number of check disks
• MTTR：修复时间 mean time to repair
• MTTF：平均故障时间 mean time to failure

6.5 RAID Level 1–5

RAID 1 — Mirroring（磁盘镜像）

CN：

• 数据完整复制两份（复制因子=2）
• 大读吞吐：可从两个盘并行读取 → 2×
• 写：必须双写 → 与单盘相同
• 容量利用率：50%
• 可靠性极高

EN：

• Data stored identically on two disks (replication factor=2)
• Large reads: 2× faster via parallel reading
• Writes: same as single disk (must write twice)
• Storage efficiency: 50%
• Excellent reliability

RAID 2 — Hamming Code（几乎不使用）

位级 striping + 海明码；复杂、成本高、不实用。

RAID 3 — Byte-level Striping + 单独校验盘

CN：

• 所有盘同步操作
• 一个独立 parity 盘（C=1）
• 非常适合大规模顺序 I/O
• 不适合并发小请求（被 parity 盘锁住）

EN：

• Synchronous operations across disks
• Single dedicated parity disk
• Excellent for large sequential reads/writes
• Poor for concurrent small requests

RAID 4 — Block Striping + Dedicated Parity Disk

数据以扇区/块为单位交错分散，而不是按位 。每个独立的数据单元存储在一个磁盘的单个扇区上 。校验信息集中在一个专用的奇偶校验盘上 。（C=1）

CN：

• 小读可并行（每个盘能独立读）
• 小写被 parity disk 卡住 → 写瓶颈

EN：

• Small reads are parallel
• Small writes bottlenecked at the parity disk

RAID 5 — Block Striping + Distributed Parity

CN：

• parity 分布在所有磁盘上
• 解决 RAID4 的单盘瓶颈
• 小读、更快
• 小写：需要读旧数据、读旧 parity、写数据、写 parity（4 次 I/O）
• 适合 OLTP、数据库系统

EN：

• Parity distributed across disks
• Removes RAID4 parity bottleneck
• Fast small reads
• Small writes involve 4 I/Os (read old data, read old parity, write data, write parity)
• Ideal for OLTP systems

6.6 读写性能总结 / Performance Summary

RAID Level	大读	大写	小读	小写	Summary
RAID1	2×	=1×	2×	1×	Best read performance, expensive
RAID3	高	中	差	差	Sequential workloads
RAID4	中	差（parity 瓶颈）	高	差	Good small reads
RAID5	高	中等	高	中	Balanced, ideal for OLTP

6.7 可靠性（论文公式）/ Reliability

关键直觉：

CN： RAID 可容忍 1 块盘故障，但不能在修复完成前再坏第二块。

EN： RAID tolerates one disk failure, but not a second failure before repair completes.

论文公式（简化解释）

\[ MTTF_{Group} = \frac{(MTTF_{Disk})^2}{(G+C) \times (G+C-1) \times MTTR} \quad \]

\[ MTTF_{RAID} = \frac{(MTTF_{Disk})^2}{(G+C) \times (G+C-1) \times MTTR \times n_{G}} \quad \]

CN：

• MTTF 取决于“第二次故障是否发生在修复前”
• MTTR 越短越安全

EN：

• MTTF depends on probability of a second failure during repair
• Lower MTTR ⇒ higher reliability

6.8. RAID 的应用场景 / Workload Suitability

（1）Scientific Workloads

CN： 需要高吞吐的大读写，适合 RAID3 / RAID5

EN： Require high data rate; RAID3/5 are suitable.

（2）Online Transaction Processing

CN： 需要高 IOPS 的 4KB 随机访问；RAID5 最合适

EN： Needs high small-I/O concurrency; RAID5 is ideal.

6.9. 考试重点问答

Q1：RAID 为什么诞生？

• CN： 因为 CPU/DRAM 增长太快，而磁盘性能太慢，I/O 将主导系统性能。
• EN： Because CPU/DRAM grew rapidly while HDD performance lagged, making I/O the system bottleneck.

Q2：为什么 XOR 适用于 RAID？

• CN： XOR 可逆；知道 parity 和其他块就能恢复丢失块。
• EN： XOR is reversible; lost blocks can be reconstructed using parity and surviving data

Q3：RAID4 为什么有写瓶颈？

• CN： 所有写都必须访问同一个 parity disk。
• EN： All writes must update the single parity disk, creating a bottleneck.

Q4：RAID5 如何解决？

• CN： 将 parity 分布到所有磁盘，消除单盘瓶颈。
• EN： By distributing parity across disks to remove the single-disk bottleneck.

6.10 老师讲的可能出现在考试中的

①：关于 parity group、D、G 的公式（非常重点）

“In the above example, if I have three (parity) disks, what is the total number of disks including the parity disk? Guys this could be on your exam.”

考点：

• \(D_{Total} = D + C_{Total}\)
• \(D_{Total} = D + (C \times n_{G}) \quad \text{or} \quad D_{Total} = D + \left(C \times \frac{D}{G}\right)\)

你必须会：

• 给你 12 data disks，每组 4 data disks → G = 12/4 = 3 → total = 15
• 这是非常简单但老师明确说会考。

②：为什么 RAID group size 变大效率会变好？

老师花了很长时间重复、强调：

“These are very subtle. At the same time they are very simple. Please take time to understand this stuff.”

考点：

• parity group size 10 → 有 10 个 data + 1 个 parity
• parity group size 25 → 有更多 data disks 可用于读
• 大 group = fewer parity disks = more data bandwidth = 更高 large reads 吞吐

考试可能问：

Why does RAID-5 or RAID-3 performance increase when parity group size increases?

③：关于 AND/OR/XOR（特别是 XOR 特性）

老师明确说“要知道这个术语。老师反复强调：

“XOR is fundamental to today’s lecture and to the paper you are reading.”

“You MUST know how XOR works because parity-based RAID depends on it.”

考试可能问：

• 什么是 XOR？
• 为什么 parity 用 XOR？
• XOR 如何恢复 missing bit？（非常常考）

④：RAID-1、RAID-3、RAID-4、RAID-5 的性能比较表

老师强调：RAID 1/3/4/5 差异是考试重点。字幕中老师重复讲：

“This table is very important. You should know these numbers.”

你必须知道：

RAID level	Small reads	Small writes	Large reads	Large writes	为什么
RAID-1	强	弱	好	一般	需要写两份
RAID-3	小读弱	小写弱	大读强	大写强	bit striping
RAID-4	小读强	小写弱	大读强	大写强	parity 瓶颈
RAID-5	小读强	小写较好	大读强	大写强	rotated parity

⑤：slowdown factor S（>=1, <=2）

老师重复强调：Slowdown factor S。老师原话：

“This S factor is extremely important. You need to know what it means.”

“If you disagree, set S = 1. But you must know why S exists.”

👉 考点：

• 多个 disk 同时读取大块数据 → seek/rotation 不同步
• S ∈ [1, 2]
• 真实 HDD → S > 1
• SSD → S ≈ 1

考试可能问：

Why does S exist? When is S = 1?

⑥：为什么 small reads/writes 与 large reads/writes 性能完全不同？

（大概率考试）老师强调：small I/O vs large I/O 的区别。老师反复强调：

“This is very subtle but extremely important. Understand this difference.”

👉 考点：

• 大 IO：读所有 disk → throughput ~ D / S
• 小 IO：只读某一个 disk → throughput ~ number of parity groups

考试会问：

Why RAID-3 is bad for small reads/writes?

答案：因为必须读取整个 parity group 的所有 disks（bit striping）。

⑦：RAID-4 parity disk bottleneck

老师直接点名：

“This parity disk bottleneck is a very important concept.”

“RAID-5 fixes this. You must understand how.”

👉 考点：

• RAID-4：所有 writes 都要更新 parity → parity disk = bottleneck
• RAID-5：parity rotated → no single disk bottleneck

⑧：Failure / Mean time to repair (MTTR)

老师说：

“This is important. You must understand how rebuild works and when data is lost.”

必考内容：

• RAID-1：两个盘同时坏 → 数据丢失
• RAID-3/4/5：一个盘坏可恢复；两个盘坏（同组） → 数据丢失
• eager rebuild vs lazy rebuild

⑨：Amdahl’s Law

老师明确强调：

“You should know Amdahl’s law. This applies to storage too.”

考试可能问：

为什么加速 IO 对整体系统加速有限？

答：受限于未加速部分 → Amdahl's Law。