Notes for FIT5137: Advanced database technology

Posted on Edited on

所谓的“高级数据库技术”居然是NoSQL……

W1 Intro

关系型数据库
Structured Query Language (SQL)
ACID (Atomicity, Consistency, Isolation, Durability) 原子性，一致性，隔离性，持久性

非关系型数据库（=NoSQL）
BASE (Basically Available, Soft state, Eventual consistency) 基本可用性，软状态，最终一致性

Big Data特征（3V）

  • Volume （数据）量 -> Scaling up/out->up=升配; out=加机
  • Velocity （数据输入的）速 -> stream / feedback-loop
  • Variety 多样化 -> Structured/Unstructured/Semi-structured

因此使用传统关系型数据库难以处理BigData

NoSQL的属性

  • schema-free 不受结构限制
  • Support distributed database architectures 支持分布式数据库架构
  • high scalability, high availability, and fault tolerance 高拓展，高可用，错误容忍

NoSQL的分类

  • Key-value databases
  • Document-oriented databases
  • Column-oriented databases
  • Graph databases

这个unit里不讲kv（讲kv估计要么讲太简单要么讲太难

后面三类的介绍略，在对应week会讲到

NoSQL

Adv Disadv
高拓展，可用，错误容忍 需要复杂的编程
使用低成本商品硬件 无关系——只有应用代码
支持BigData 没有事务完整性支持
k-v模型提高了存储效率 只提供了最终一致

Relational Model

Adv Disadv
使用独立表使得结构独立。表结构变化不影响数据访问或应用程序 RMDBS需要大量硬件和系统软件开销
表视图提高了概念的简单些，促进数据库设计实现管理与使用 概念上的简单些为相对未受训练的人提供了良好的系统工具，但是如果不加以检查可能会产生与文件系统中数据发生异常
基于SQL的Ad-hoc查询能力 个人和部门开发各自的应用，产生信息孤岛（islands of info）问题
强大的RMDBS将最终用户和物理层面细节隔离开，提高实践和管理的简单性

W2: Intro to MongoDB

Document-oriented databases, 本质上是K-V数据库的子类

面向文档的数据库是无模式scheme-free的。

  • 存储的数据没有预定义的结构
  • 每个文档都可以有自己的结构

文档：MongoDB 中数据的基本单位。
➢ 类似于关系数据库中的一行（但更具表现力）。
➢ 文档采用 BSON 结构——类似于 JSON（由字段和值对组成的数据结构）

集合：一组 MongoDB 文档。
➢ 类似于关系数据库中的表。
➢ 通常，集合中的所有文档都有相似或相关的目的。

数据库：集合的物理容器。

易于使用

用更灵活的模型文档替换了关系数据库中行的概念。

  • 复杂的层级关系可以用单个记录表示。
  • 没有预定义的模式：文档的key和value不是固定的类型或大小

MongoDB结合了横向扩展(scale out)的能力和各种功能，如二级索引、范围查询、排序、聚合和地理空间索引。

易于拓展

▪ MongoDB 旨在横向扩展。
▪ 面向文档的数据模型可以更轻松地跨多个服务器拆分数据。
▪ MongoDB 自动负责平衡集群中的数据和负载，自动重新分发文档并将用户请求路由到正确的机器。
➢ 允许开发人员专注于对应用程序进行编程，而不是对其进行扩展。

众多特性

MongoDB 旨在成为通用数据库。

主要特点：

  • 创建、读取、更新、删除 (CRUD) 操作
  • 索引index：MongoDB 支持通用二级索引，允许多种快速查询，并提供唯一、复合、地理空间和全文索引功能。
  • 聚合aggregation：MongoDB 支持“聚合管道”，允许从简单的片段构建复杂的聚合并允许数据库对其进行优化
  • 特殊集合类型：MongoDB 支持应在特定时间到期的数据的生存时间集合，例如会话。 它还支持固定大小的集合，这对于保存最近的数据（例如日志）很有用。
  • 文件存储：MongoDB 支持易于使用的协议来存储大文件和文件元数据。

与关系数据库不同，MongoDB 不支持join和复杂的多行事务，因为在分布式系统中很难有效地提供这两种功能。

不牺牲速度

MongoDB 的几乎每个方面都旨在保持高性能。

  • MongoDB 为文档添加动态填充并预分配数据文件以换取额外的空间使用以获得一致的性能。
  • 它使用尽可能多的 RAM 作为其缓存，并尝试自动选择正确的索引进行查询。

W3: Mongo Shell

一些MongoDB的CRUD操作。GUI上操作是在MongoDB Compass下，在w2最后讲了。w3主要是在shell里自己coding。

CRUD

Create（createCollection， insert[One/Many](<Array of Objects>)，）

Update(update[One/Many](<filter>, <update>, <options>) )

Delete(.drop(), .dropDatabase(),delete[One/Many])在GUI下很简单，这里省略。

主要需要关注R(ead)里即Query的编写：
find[One/Many](<query>, <fields>)

Projection: find的第二个字段表示输出（Project）的内容

Limit & Skip: Skip（跳过数个record）优先于Limit

Sort: 1 ascending , -1 descending

update也可以用replaceOne()，参数相同

索引

MongoDB 必须进行集合扫描（COLLSCAN）（扫描集合中的每个文档）以检索与用户查询语句匹配的文档。

通过索引（IXSCAN），可以加速查询处理。索引支持高效的数据检索，因为 MongoDB 可以使用索引来限制它必须检查的文档数量。

db.<collection name>.createIndex( { KEY1:1, KEY2:1 } )

注意：要升序索引，请使用 1。要降序索引，请使用 -1。

W4: MongoDB Aggregation

略难的部分，有点绕口

Aggregation聚合操作处理数据记录并返回计算结果。
聚合操作将来自多个文档的值组合在一起，并且可以对分组的数据进行各种操作，返回一个
单一结果。
MongoDB 提供三种聚合方式：

  • Aggregation pipeline
  • Map-reduce 功能
  • 单一目的Aggregation方法

Aggregation管道

MongoDB 的聚合框架以数据处理管道的概念为模型。文档进入多阶段管道，将文档转换为聚合结果。

特性：
➢ 每一阶段接收前一阶段的输出。
➢ 应该在一个数组中，因为要遵循某些步骤。

$match：等于find

$group，精髓在于_id的选择

1
2
3
4
5
6
7
8
9
10
db.persons.aggregate([
    { $match: {gender: "female"} },
    { 
        $group: { // 表示总人数
            _id: { state: "$location.state" }, //匹配了上面所有
            totalPersons: // 新字段名字 
                { $sum: 1 } // group需要配合$sum, $avg, $max, $min, $first, $last之类的操作分组
        } 
    }
]).pretty()

$sort

1
{ $sort: { totalPersons: -1 } }

$project

1
2
3
4
5
6
7
$project: {
    _id: 0, 
    name: 1, 
    email: 1, 
    birthdate: { $convert: { input: '$dob.date', to: 'date' } }, 
    age: "$dob.age"
}

$lookup(匹配文档之间关系)生成嵌入文档

1
2
3
4
5
6
7
8
{
    $lookup: {
        from: <collection to join>,
        localField: <field from the input documents>,
        foreignField: <field from the documents of the "from" collection>,
        as: <output array field>
    }
}

例如，我们现有文档含有_id这个字段，从address这个collection（含有patron_id）之中找到和_id相同（匹配）的patron_id，然后作为一个列表放在当前文档的addresses里

1
2
3
4
5
6
7
8
9
10
11
db.patron.aggregate([
    {
        $lookup: {
            from: "address",
            localField: "_id",
            foreignField: "patron_id",
            as: "addresses"
        }
    }
])

Map-Reduce

检索每个含k的文档作为一个map，然后每个执行reduce

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
db.collection.mapReduce(
                         <map>, // function() { emit(this.cust_id, this.amount) }
                         <reduce>, // function(k, v) { return Array.sum(v) } 
                         {
                           out: <collection>,
                           query: <document>,
                           sort: <document>,
                           limit: <number>,
                           finalize: <function>,
                           scope: <document>,
                           jsMode: <boolean>,
                           verbose: <boolean>,
                           bypassDocumentValidation: <boolean>
                         }
                       )

测验常客 $unwind

单一目的Aggregation方法

.estimatedDocumentCount( )
.count( )
.distinct( )

W5 Introduction to Column-Oriented Database

▪ 源自 Google 的 BigTable 产品、HBase 和 Cassandra。
▪ 也称为列族数据库。
▪ 以键值对的形式组织数据，键映射到值组件中的一组列。
➢ Column：类似于关系数据库中一个数据单元格的键值对
➢ Key：列名
➢ Value：列中存储的数据
▪ 一组逻辑相关的列称为超级列。 所有超级列组合在一起以创建列族。 列族在概念上类似于关系模型中的表。
▪ 列族中的每个行键可以有不同的列。

▪ 面向列的 DBMS 是一种 DBMS，它将数据表存储为数据列的部分，而不是大多数 DBMS 实现中的数据行。
▪ 具有许多空值的列（称为稀疏sparse 数据）可以更有效地处理，而不会浪费空单元格的存储容量。

▪ 关系数据库既可以面向行，也可以面向列。
▪ 基于行的系统旨在高效地返回整行的数据，这与用户希望检索有关特定对象或实体的信息的常见用例相匹配。
▪ 大多数数据库系统通过数据库索引来加速搜索操作。

▪ 在面向列的数据库中，一列的所有值都放在磁盘上

Column-Oriented Databases

Adv Disadv
加快查询处理和聚合操作。 检索与单个实体有关的所有属性变得效率低下
高效的存储空间消耗（非常适合处理稀疏数据）。 Join操作将大大减慢（必须扫描每一列才能找到属于某个外部记录标识符的值）。

以下是 Google BigTable 的核心功能：
➢ 开发者可以动态控制列。
➢ 数据值由行标识符、列名和时间戳索引。
➢ 数据建模者和开发者可以控制数据的位置。
➢ 一行的读写是原子的。
➢ 行按排序顺序维护。

▪ 行由多个列族组成。 每个系列由一组相关的列组成。
▪ 数据值由行、列名和时间戳记索引

▪ 数据值按行标识符、列名和时间戳编制索引。
➢ 行标识符类似于关系数据库中的主键。
▪ 一个列值可以存在多个版本。 查询列值时默认返回最新版本。

Apache Cassandra Features

  • Distributed
  • Decentralized
  • Elastically scalable
  • Highly available & Fault-tolerant

Monolithic Architecture-> single point of failure

The Master-slave model (only master server performs writes)-> a failure of the write master

sharding to scale writes -> Requires manual shuffling of data & Failure points of the master nodes

处理领导者的死亡
▪ 提高主从系统可用性的解决方案。
▪ 采用主故障转移协议。
▪ 协议因实现而异。
▪ 原则是当前一个master失败时指定一个新的master

领导选举的不良特征
▪ 应用程序必须了解数据库拓扑。
▪ 必须仔细规划数据分区。
▪ 写入难以扩展。
▪ 故障转移通常会显着增加系统的复杂性，对于多站点数据库尤其如此。
▪ 增加容量需要重新整理数据，这可能会导致停机。

Cassandra 是一个可弹性伸缩的数据库
▪ 可扩展性——可以在性能几乎没有下降的情况下继续处理更多的请求。
➢ 纵向扩展：增加更多的硬件容量和内存。
➢ 水平扩展：添加更多的机器，上面有全部或部分数据，这样没有一台机器必须承担服务请求的全部负担。
▪ 弹性可扩展性 – 指横向可扩展性的一个特殊属性，这意味着您的集群可以无缝扩展和缩减

Cassandra 的点对点方法
▪ Cassandra 集群中的所有节点都可以接受读取和写入，无论写入或请求的数据属于集群中的哪个位置。
▪ 节点间通信通过gossip 协议进行，该协议允许所有节点快速接收更新，而无需主协调器

P2P方法有几个优点：

  1. 简单。
  2. 没有节点可以是单点故障。
  3. 扩展和缩减相当简单：在集群中添加或删除服务器。
    ➢ 点对点网络中的服务器相互通信，最终为新节点分配一组数据进行管理。
    ➢ 当一个节点被移除时，托管来自被移除节点的数据副本的服务器响应读写请求。

▪ 由于P2P网络没有单一的主协调服务器，集群中的服务器负责管理主服务器将处理的许多操作，包括以下内容：
➢ 共享集群中服务器状态信息
➢ 确保节点拥有最新版本的数据
➢ 确保在应该接收写入的服务器不可用时存储写入数据
▪ Cassandra 拥有实现所有这些功能的协议。

节点间通信（Gossip）
▪ Gossip协议：
o 是对等通信协议。
o 定期交换关于它们自己和集群中其他节点的状态信息。
o 在计时器上每秒运行一次，并最多与其他三个节点交换状态消息。
o 用作分布式数据库中的自动复制机制
o 较旧的信息被特定节点的最新状态覆盖

▪ 每次将服务器添加到集群中时，以完整的服务器到服务器通信协议发送的消息数量增长得更快。

Gossiper 如何运作
▪ 每秒一次，Gossiper 将在集群中随机选择一个节点并与其初始化gossip 会话。
o 每轮gossip 需要三个消息。
▪ gossip 发起者向其选择的朋友发送 GossipDigestSynMessage。
▪ 当朋友收到这个消息时，它返回一个 GossipDigestAckMessage。
▪ 当发起者收到好友的 ack 消息时，它会向好友发送 GossipDigestAck2Message 以完成一轮gossip 。

Cassandra ——Read
▪ Cassandra 集群中的任何节点都可以处理客户端请求。
▪ 所有节点都有关于集群状态的信息，并且可以充当客户端的代理，将请求转发到集群中的适当节点。

Cassandra ——Write
▪ 如果一个节点不可用，则其他节点可以代表它接收写入请求，并在可用时将它们转发到预期节点。

什么时候使用面向列的数据库？
▪ 列族数据库是需要高水平写入性能、大量服务器或多数据中心可用性的大规模数据库部署的合适选择。
➢ Cassandra 支持多数据中心部署，包括多数据中心复制。
▪ 写密集型操作，例如社交网络应用程序中的操作，是使用列族数据库的良好候选者。
➢ Cassandra 的点对点架构支持暗示切换，这意味着只要至少有一个节点在运行且可达，数据库将始终能够接受写操作。
▪ 列族数据库也适用于需要大量服务器来满足预期工作负载的情况。

W6 Apache Cassandra Architecture & CQL

Cassandra 架构的特点

▪ Cassandra 没有主节点或从节点。
▪ 它具有环型/点对点架构。
▪ 数据自动分布在所有节点上。
▪ 跨节点复制数据以实现冗余。
▪ 数据保存在内存中并缓慢写入磁盘。
▪ 键的哈希值用于在集群中的节点之间分配数据。
▪ Cassandra 架构支持多个数据中心。
▪ 数据可以跨数据中心复制。

环和令牌

▪ Cassandra 将集群管理的数据表示为环。
▪ 环中的每个节点都由一个令牌描述。
▪ 令牌是用于标识每个分区的 64 位 ID。
▪ 令牌范围从 -263 到 263-1。
▪ 通过使用散列函数计算分区键的令牌，将数据分配给节点。

Cassandra 架构的影响

▪ Cassandra 架构支持将数据透明地分发到节点。
➢ 这意味着您可以根据数据确定您的数据在集群中的位置。

▪ 任何节点都可以接受任何请求，因为没有主节点或从节点。
➢ 如果一个节点有数据，它会返回数据。
➢ 否则，它将请求发送到有数据的节点

▪ 您可以指定数据的副本数以达到所需的冗余级别。
➢ 例如，如果数据非常关键，您可能希望指定复制因子为 4 或 5。
➢ 如果数据不重要，您可以只指定一两个。

▪ 它还提供可调整的一致性——一致性级别可以指定为与性能的权衡。
➢ 事务总是写入磁盘上的提交日志，以便它们是持久的。

关键结构

▪ 节点：您存储数据的地方。
▪ 数据中心：相关节点的集合。
▪ 集群：包含一个或多个数据中心。
▪ 提交日志：所有数据首先写入提交日志以保证持久性。
▪ Mem-table：内存常驻数据结构。
▪ SSTable：排序字符串表（SSTable）是一个不可变的数据文件，Cassandra 定期向其中写入内存表。
▪ 布隆过滤器：测试元素是否为集合成员的算法。

Cassandra 写入过程

  1. 数据写入磁盘上的提交日志。
  2. 根据哈希值将数据发送到负责节点。
  3. 节点将数据写入名为 mem-table 的内存表。
  4. 从mem-table，数据写入内存中的SSTable。
    ➢ SSTable 代表 Sorted String 表。 这具有对表的所有更新的合并数据。
  5. 从SSTable，数据更新到实际表。
  6. 如果责任节点宕机，数据将写入另一个标识为tempnode的节点。 tempnode 将暂时保存数据，直到负责的节点活跃起来。

▪ 将数据写入磁盘上的提交日志以保持持久性。
▪ 它也被写入内存中的内存表。
▪ Mem-table 数据写入 SSTable，用于更新实际表。

Cassandra 架构

▪ 数据中心和机架
➢ 机架是一组相互靠近的逻辑节点，
也许在单个设备机架中的物理机器上
➢ 数据中心是一组逻辑机架，可能位于同一
建立并通过可靠网络连接

Cassandra 读取过程

▪ Cassandra 读取过程确保快速读取。
▪ 如果节点关闭，则从数据的副本中读取数据。 副本的优先级是根据距离分配的。
▪ Cassandra 读取过程的特点是：
➢ 同一节点上的数据优先，被认为是本地数据。
➢ 同一机架上的数据具有第二优先权，被视为机架本地数据。
➢ 同一数据中心上的数据具有第三优先权，被视为数据中心本地。
➢ 不同数据中心的数据优先级最低

数据分区

▪ Cassandra 通过按以下方式对数据进行水平分区来执行数据的透明分发：
➢ 根据数据的主键计算哈希值。
➢ 键的哈希值映射到集群中的一个节点
➢ 数据的第一个副本存储在该节点上。
➢ 分布是透明的，因为您可以计算哈希值并确定特定行的存储位置

分区器

▪ 分区器决定数据如何在集群中的节点之间分布。
▪ 分区键用于数据分区。 每行都有一个分区键，用于标识分区。
▪ Cassandra 中提供了三种类型的分区器：
➢ Murmur3Partitioner – Cassandra 中的默认分区器。
➢ RandomPartitioner – 与 Murmur3Partitioner 类似，不同之处在于它使用 MD5（消息摘要版本 5）哈希函数来计算哈希值。
➢ ByteOrderedPartitioner – 使用分区键值对行进行排序。

复制

▪ 复制是指为每一行维护的副本数。
▪ 复制为容错提供数据冗余。
▪ N 的复制因子意味着系统中维护了 N 个数据副本。
▪ Cassandra 允许基于节点、机架和数据中心的复制。
▪ 跨数据中心的复制即使在数据中心停机时也能保证数据可用性。

复制策略

▪ 复制策略决定了如何维护一个数据行的多个副本。
▪ 复制是在keyspace 级别指定的，不同的keyspace 可以有不同的策略。
▪ Cassandra 以对用户透明的方式跨节点复制数据。
▪ 复制因子是集群中将接收相同数据副本的节点数。
▪ Cassandra 提供两种常见的复制策略：
➢ SimpleStrategy：将副本放置在环周围的连续节点上。
➢ NetworkTopologyStrategy：为每个数据中心指定不同的复制因子，将副本分配到不同的机架rack以最大化可用性。

告密者snitches

▪ snitches确定哪些数据中心和机架节点属于。
▪ 任务是确定集群中每个节点的相对主机接近度。
▪ snitches会找出节点相对于其他节点的位置。
▪ 两种最流行的snitches：
➢ Simple Snitch - Simple Snitch 用于没有机架的单个数据中心。
➢ 属性文件 Snitch - 属性文件 Snitch 用于具有多个机架的多个数据中心。
▪ Cassandra 中的复制基于snitches。

故障检测

▪ 节点故障的影响：
➢ 其他节点检测节点故障。
➢ 该节点上的数据请求被路由到拥有该数据副本的其他节点。
➢ 写入由临时节点处理，直到节点重新启动。
➢ 任何丢失的 memtable 或 sstable 数据都从 commitlog 中恢复。
➢ 可以使用 nodetool 实用程序永久删除节点。

▪ 磁盘故障的影响：

➢ 磁盘上的数据无法访问。
➢ 无法从节点读取数据。
➢ 此问题将被视为该部分数据的节点故障。
➢ Memtable 和 sstable 不受影响，因为它们是内存表。
➢ Commitlog 有副本，它们将用于恢复。

▪ 机架rack故障的影响：

➢ 机架上的所有节点都无法访问。
➢ 无法从机架节点读取数据。
➢ 读取将路由到数据的其他副本。
➢ 这将被视为机架中的每个节点都发生了故障。

▪ 数据中心故障的影响：

➢ 数据中心内的所有数据都将无法访问。
➢ 所有读取都必须路由到其他数据中心。
➢ 将使用其他数据中心的副本副本。
➢ 虽然系统将运行，但客户可能会注意到由于网络延迟而变慢。 这是因为多个数据中心通常位于不同的物理位置并通过广域网连接

一致性级别

▪ Cassandra 提供可调的一致性级别。
▪ 可以为每个读取或写入查询指定一致性级别。
➢ 对于读查询，一致性级别指定了有多少副本节点必须响应读请求。
➢ 对于写操作，一致性级别指定了必须响应多少副本节点才能上报写操作。
➢ R + W > N = 强一致性
➢ R：读副本数 W：写副本数 N：复制因子

W7 Designing Column-Oriented Databases 列数据库设计

Primary & Compound Keys 主键与复合键

Cassandra 中的主键可以是复合键，复合键是指由多列组成的键。
当指定复合键时，第一个键被考虑用于数据分区，称为分区键。
每个分区中的数据按剩余的键进行聚类和排序。

Guidelines for Designing Tables 表设计

面向列的数据库的实现方式与关系数据库不同。
▪ 重要的是要了解：
➢ 列族数据库被实现为稀疏的多维映射。
➢ 行之间的列可以不同。
➢ 可以动态添加列。
➢ 不使用连接； 数据被非规范化。
列数据库的这些特性将影响数据库设计指南

在面向列的数据库中设计表时的几个准则：
➢ 非规范化而不是连接。
➢ 利用无值的列。
➢ 使用列名和列值来存储数据。
➢ 使用单行对实体进行建模。
➢ 避免行键热点。
➢ 保留适当数量的列值版本。
➢ 避免列值中的复杂数据结构。
▪ 应该注意的是，其中一些建议（例如 使用适当数量的列值版本）并不适用于所有列族数据库系统。

Denormalize Instead of Join
面向列的数据库通常需要比关系数据库更少的表。
➢ 它对数据进行非规范化以避免需要连接。

Make Use of Valueless Columns
该表没有像“ProductPurchased1”这样名称为“PR _ B1839”的列，而是简单地将产品 ID 存储为列名

Use Both Column Names and Column Values to Store Data
▪ 列名和列值都可以存储数据。
▪ 使用无值列的一种变体使用列值进行非规范化。
▪ 非规范化数据的缺点：在客户表中保留产品名称的副本会增加使用的存储量。
▪ 非规范化数据的好处：客户和他们购买的产品的报告是通过只引用一张表而不是两张表来生成的。
▪ 实际上，我们是在牺牲对额外存储的需求来提高读取性能。

Model an Entity with a Single Row
▪ 单个实体，例如特定客户或特定产品，应将其所有属性放在一行中。
➢ 这可能导致某些行存储的列值多于其他行的情况，但这在列族数据库中并不少见。
▪ ColumnFamily数据库不提供与关系数据库相同级别的事务控制。 通常，写入一行是原子的。 如果您更新表中的多个列，它们将全部更新，或者它们都不更新。

Avoid Hotspotting in Row Keys
分布式系统使您能够利用大量服务器来解决问题。 在一台或几台机器上指挥过多的工作而其他机器未得到充分利用是低效的。

Keep an Appropriate Number of Column Value Versions
▪ HBase 使您能够存储列值的多个版本。
▪ 列值带有时间戳，因此您可以确定最新和最早的值。
▪ 与其他形式的版本控制一样，如果您
需要回滚您对列值所做的更改。
▪ 这不适用于 Apache Cassandra

Avoid Complex Data Structures in Column Values
例如，关于客户的 JSON 文档可能包含一个存储地址信息的嵌入文档，如下所示：
▪ 这种类型的数据结构可能存储在一个列值中，但不推荐使用，除非有特殊原因需要维护这种结构。
▪ 为每个属性使用单独的列可以更轻松地将数据库功能应用于属性。 例如，为街道、城市、州和邮政编码创建单独的列意味着您可以对这些值创建二级索引。
▪ 此外，将属性分成单独的列允许您在需要时使用不同的列族。 使用二级索引的能力和根据列的使用方式分隔列的选项都可以提高数据库性能。

Using Secondary Indexes Managed by the Column Family Database System
使用 ColumnFamily 数据库系统管理的二级索引
如果您需要列值的二级索引并且列族数据库系统提供了自动管理的二级索引，那么您应该使用它们。
▪ 使用自动管理的二级索引的主要优点是与替代方法相比，它们需要更少的代码来维护。
▪ 有时您不应该使用自动管理的索引。 在以下情况下避免或至少仔细测试索引的使用：
➢ 列中有少量不同的值。
➢ 一列有很多唯一unique值。
➢ 列值稀疏

▪ 有很少不同值的列不是二级索引的良好候选。
▪ 当列中不同值的数量（称为列的基数）很小时，索引不会对性能有太大帮助——它甚至可能会受到伤害。
▪ 具有太多不同值的行也不适合用作索引。
▪ 自动管理的索引在这里可能没有多大帮助，因为索引必须维护如此多的数据，搜索索引和检索数据可能比扫描表以获取特定值花费更多的时间
▪ 在许多行不使用列的情况下，二级索引可能无济于事。
▪ 不应为稀疏填充的列编制索引

何时使用表创建和管理二级索引
▪ 帮助生成列出购买特定产品的所有客户的报告。
▪ 他们还想要一份关于特定产品以及哪些客户购买了这些产品的报告

Guidelines for Indexing 索引设计

Cassandra Data Model 数据模型

Rules

▪ 最大化写入次数
➢ Cassandra 针对高写入性能进行了优化。
➢ 最大化写入对于读取性能和数据可用性很有用。
▪ 最大化数据复制
➢ 数据非规范化和数据重复是 Cassandra 的事实。
➢ 磁盘空间通常是最便宜的资源（与 CPU、内存、磁盘 IOP 或网络相比），Cassandra 是围绕这一事实构建的。 为了获得最高效的读取，您经常需要复制数据。
➢ 数据复制提供即时数据可用性和无单点故障。

Goals

▪ 在集群周围均匀分布数据
➢ 您希望集群中的每个节点具有大致相同的数据量。
➢ 行基于分区键的散列分布在集群中，分区键是 PRIMARY KEY 的第一个元素。 因此，均匀分布数据的关键是：选择一个好的主键。
▪ 最小化查询数据时读取的分区数
➢ 分区是共享相同分区键的行组。 当您发出读取查询时，您希望从尽可能少的分区读取行。
➢ 需要选择均衡数量的分区。

W8 Non-Relational Database Transactions

BASE

  1. Data Management in Big Data
  2. ACID vs BASE
  3. CAP Theorem

▪ 数据库旨在做两件事：存储数据和检索数据。
▪ 为了实现这些目标，数据库管理系统必须做三件事：
➢ 持久存储数据
➢ 保持数据一致性
➢ 确保数据可用性

持久存储

▪ 数据必须持久存储；即必须以数据库服务器关闭时数据不丢失的方式进行存储。
▪ 如果数据只存储在内存（即 RAM）中，那么当内存断电时，数据就会丢失。
▪ 只有存储在磁盘、闪存、磁带或其他长期存储设备上的数据才被视为永久存储
▪ 数据必须可用于检索。
▪ 您可以通过多种不同的方式检索永久存储的数据。
➢ 存储在闪存设备上的数据直接从其存储位置读取。
➢ 磁盘和磁带驱动器的可移动部件放置到位，使设备的读头位于要读取的数据块上。
▪ 可以将数据库设计为简单地从数据文件的开头开始，并在执行读取操作时搜索您需要的记录。
➢ 这会导致极其漫长的响应时间和宝贵的计算资源的浪费。
➢ 无需扫描全表查找数据，您可以使用数据库索引快速找到特定数据块的位置。

数据一致

▪ 确保将正确数据写入持久存储设备非常重要。
➢ 如果写或读操作不能准确记录或检索数据，数据库将没有多大用处。
➢ 除非出现硬件故障，否则这很少成为问题。
▪ 当两个或更多人使用数据库并希望同时使用相同的数据时，会出现一个更常见的读写问题。
▪ 数据库返回的结果表明客户已支付其帐户的应付余额，而不将该付款也包括在可用资金记录中，这将是不一致的。
▪ 关系数据库系统旨在支持此类必须被视为单个操作或事务的多步骤过程。

数据可用

▪ 数据应在需要时可用。
➢ 这很难保证。
o硬件可能会出现故障。
o数据库服务器上的操作系统可能需要打补丁。
o您可能需要安装新版本的数据库管理系统。
o在单个服务器上运行的数据库可能由于多种原因不可用。
▪ 避免数据库服务器不可用问题的一种方法是拥有两台数据库服务器：一个用于更新数据和响应查询，而另一个用作备份，以防第一台服务器出现故障。
▪ 用于更新和响应查询的服务器称为主服务器，另一个是备份服务器。
▪ 备份服务器从主服务器上的数据库副本开始。
▪ 使用数据库时，对主数据库的任何更改也会反映在备份数据库中。
▪ 回想一下，数据库事务是由多个步骤组成的操作，必须完成所有步骤才能完成事务。
▪ 如果多个步骤中的任何一个失败，则整个交易失败。
▪ 更新两个数据库使每次更新成为一个多步骤过程。
➢ 当公司使用单台服务器时，更新仓库中特定产品的数量只需一步

▪ 更新两个数据库的过程与其他多步事务类似：两个数据库都必须成功，操作才能成功。
▪ 主数据库和备份数据库必须一致。
▪ 两阶段提交：
➢ 在操作的第一阶段，数据库将数据写入或提交到主服务器的磁盘。
➢ 在操作的第二阶段，数据库将数据写入备份服务器的磁盘。

W9 Introduction to Graph Databases

▪ 图数据库基于称为图论的数学分支。
▪ 该数学领域的技术可用于分析实体之间的联系和联系。

什么是图？

▪ 图是由两部分组成的数学对象：顶点和边。
➢ 顶点有时被称为节点。
▪ 每个顶点/节点代表一个实体（人、地点、事物、类别或其他数据）。
▪ 每条边代表两个顶点/节点之间的关系（代表两个节点如何关联）。

顶点Vertex

▪ 一个顶点代表一个用唯一标识符标记的实体。
➢ 类似于列族数据库中的行键或关系数据库中的主键。
▪ 一个顶点实际上可以代表任何与另一个实体有关系的实体，例如：
➢ 社交网络中的人
➢ 高速公路连接的城市
➢ 与体内其他蛋白质相互作用的蛋白质
➢ 公司分销网络中的仓库
➢ 集群中的计算服务器
▪ 顶点用于表示对象。
▪ 顶点可以有属性。
o 例如，社交网络中的一个顶点代表一个人； 它具有姓名、地址和出生日期等属性。
o 高速公路系统图使用顶点来表示城市。 城市有人口、经度和纬度以及名称，并且位于地理区域内。

边Edge

▪ 边，也称为链接link或弧arc，定义顶点或连接顶点的对象之间的关系。
o 例如，在一个家谱数据库中，顶点可以代表人，而边代表他们之间的关系，例如“女儿”和“父亲”。
o 在高速公路数据库的情况下，城市用顶点表示，而边表示连接城市的高速公路。
▪ 边代表顶点之间的关系。
▪ 与顶点非常相似，边也有属性。
o 例如，在高速公路数据库中，所有边都将具有属性，例如距离、限速和车道数。
o 在家族树示例中，边可能具有诸如指示两个人是否因婚姻、收养或生物学相关的属性。
▪ 一个常用的属性称为边的权重。
▪ 权重代表关系的某些价值。
o 例如，在高速公路的情况下，权重可能是城市之间的距离。
o 在社交网络中，权重可以表明两个人在彼此的墙上发帖或评论彼此的帖子的频率。
▪ 一般而言，权重可以表示成本、距离或由顶点表示的对象之间关系的其他度量。

▪ 边有两种类型：有向和无向。
▪ 有向边有一个方向。 这用于指示应如何解释由边建模的关系。
▪ 然而，方向并不总是需要的。 例如，假设交通双向流动，高速公路图可能是无向的。

图形数据库比关系数据库管理系统 (RDBMS) 更易于理解。

Neo4j Highlights:

  • A native graph database
  • Whiteboard friendly.
  • Supports rapid development.
  • Designed for business-critical and high-performance operations.

图形数据库将数据存储在图形中，图形是最通用的数据结构，能够以高度可访问的方式优雅地表示任何类型的数据。Neo4j 图基于属性图模型。

W10 & W11 Graph Databases

路径

▪ 通过图的路径是一组顶点以及这些顶点之间的边。
▪ 图中的顶点都彼此不同。
▪ 如果边是有向的，则路径为有向路径。 如果图是无向图，则其中的路径是无向路径。
▪ 示例：从 B 到 D 到 H 到 I 的顶点和边是从顶点 B 到顶点 I 的路径。
▪ 路径很重要，因为它们捕获有关图中顶点如何相关的信息。
▪ 例如：
o 在家庭图中，一个人是其他人的祖先，仅当存在从该人到其祖先的有向路径时。
o 就家谱而言，从一个人到一个祖先只有一条路径。
o 在高速公路图的情况下，城市之间可能有多条路径。
▪ 使用图形时遇到的一个常见问题是找到两个顶点之间的权重最小的路径。
➢ 权重可以表示使用边的成本、遍历边所需的时间或您试图最小化的其他一些度量。

环

▪ 环是将顶点与其自身相连的边。
▪ 例如，在生物学中，蛋白质可以与其他蛋白质相互作用。 一些蛋白质与相同类型的其他蛋白质分子相互作用。 可以使用循环来表示这一点。
▪ 但是，与方向一样，在某些图中允许循环可能没有意义。 例如，循环在家庭树图中没有多大意义； 人们不能成为自己的父母或孩子。

图数据库非常适用于容易用实体和实体之间的关系描述的问题域。
▪ 实体几乎可以是任何东西，从蛋白质到行星。
▪ 图数据库应用程序经常包括涉及以下内容的查询和分析：
o 识别两个实体之间的关系。
o 从节点识别边的共同属性。
o 从节点计算边的聚合属性。
o 计算节点属性的聚合值。

图的操作

▪ 对数据库执行的常见操作包括插入、读取、更新和删除数据。 图数据库也执行这些操作。
▪ 图数据库也非常适合一组额外的操作。 具体来说，操作可用于跟踪路径或检测顶点之间关系中的重复模式。
图形独有的三个重要操作：
▪ 图的联合
▪ 图的交集
▪ 图遍历

图的并集（Union）是图中顶点和边的组合集合。

图的交集（intersection ）是两个图共有的顶点和边的集合。

图遍历
▪ 图遍历是以特定方式访问图中所有顶点的过程。 这样做的目的通常是设置或读取图形中的某些属性值。
图遍历是访问图中所有节点的过程

图和节点的属性

▪ 图形和节点的几个属性在比较和分析图形时很有用。
▪ 这些包括：

o 同构Isomorphisms：

▪ 如果第一个图中的每个顶点在另一个图中都有一个对应的顶点，则两个图被认为是同构的。
▪ 此外，对于第一个图中一对顶点之间的每条边，在另一个图中对应的顶点之间都有一条相应的边。
▪ 如果您试图检测一组图中的模式，则图同构很重要。
➢ 示例：社交网络图、流行病学

o 顺序和大小Order and Size

▪ 顺序和大小是图形大小的度量。
➢ 图的阶数是顶点数，图的大小是图中边数。
▪ 图形的顺序和大小很重要，因为它们会影响执行操作所需的时间和空间。
➢ 很明显，在小图上执行并集或交集比在大图上执行相同操作花费的时间更少。
➢ 也很容易假设遍历小图比遍历大图花费的时间更少。

o 等级Degress

▪ 度数是链接到顶点的边数，是衡量图中任何给定顶点重要性的一种方法。
▪ 度数高的顶点比度数低的顶点与其他顶点的连接更直接。
▪ 在解决通过网络传播信息或财产的问题时，学位很重要。

o 距离Closeness

▪ Closeness 是一个顶点的属性，表示该顶点与图中所有其他顶点的距离。
▪ 如果您想了解信息在社交网络中的传播、社区中的传染病或分发网络中的材料移动，紧密度是一个重要的衡量标准。
▪ 接近度值高的顶点可以比接近度值小的顶点更快地到达网络中的其他顶点。

o 介数Betweenness

▪ 介数衡量给定顶点的瓶颈程度。
▪ 想象一座河上的城市，有许多道路，但只有一座桥
▪ 介数有助于识别网络中潜在的脆弱部分

图形建模

▪ 图形可用于对许多不同领域中的结构和流程进行建模。
➢ 有时，图形表示实体之间的关系，例如人或城市。
➢ 在其他情况下，图形表示材料或物体通过系统的流动，例如流经市政供水系统的水或高速公路上的卡车。
▪ 图表类型：
➢ 无向图和有向图
➢ 流网络
➢ 二部图
➢ 多重图
➢ 加权图

▪ 无向图是边没有方向的图。
➢ 这种类型的图用于对方向没有意义的关系或流进行建模。 例如，您可以使用无向边对家庭关系中的夫妻进行建模。
▪ 有向图是具有有向边的图。
➢ 您可以对具有有向边的父子关系建模。

无向图和有向图
▪ 在某些情况下，图中的某些边是有向的，而有些则不是。
➢ 例如，如果您对企业中的员工进行建模，则某些边可能表示员工和经理之间的“报告对象”关系。 这将使用有向边。
➢ 另一方面，同行之间的“合作”关系将是没有方向的。 它也可以建模为两个有向边。

流网络
▪ 流网络是一个有向图，其中每条边都有一个容量，每个顶点都有一组输入和输出边。
▪ 入边容量总和不能大于出边容量总和。
▪ 此规则的两个例外是源顶点和汇顶点。 源没有输入但有输出，而汇有输入但没有输出。

▪ 流网络也称为运输网络。
▪ 图数据库可用于模拟流动网络，如道路系统或交通网络。
▪ 它们还可用于模拟连续流动的过程，例如吸收雨水（源头）并使其流入河流（汇）的雨水渠网络。

二分图
▪ 二部图（bigraph）是具有两组不同顶点的图，其中一组中的每个顶点仅连接到另一组中的顶点。
▪ 在对不同类型对象之间的关系建模时，二部图很有用。
▪ 例如，一组顶点可能代表企业，另一组顶点可能代表人。 如果此人为该企业工作，则该人与该企业之间就会出现边缘。
▪ 其他示例包括教师和学生、成员和团体以及火车车厢和火车。

多重图
▪ 多重图是顶点之间具有多条边的图。

加权图
▪ 加权图是每条边都分配有编号的图。 该数字可以反映成本、容量或其他一些边缘度量。
▪ 这通常用于优化问题，例如寻找顶点之间的最短路径。
➢ 找到最短路径的一种方法称为 Dijkstra 算法，由 Edsger Dijkstra 创建。
➢ Dijkstra 算法用于寻找网络中的最短路径。 这是在 Internet 上路由数据包或为送货卡车寻找最有效路线的理想选择

解决最短路径问题的最常用算法

▪ Dijkstra 算法
▪ 增量网络扩展 (INE)
▪ 增量欧几里得限制 (IER)
▪ 范围网络扩展 (RNE)
▪ 范围欧几里得限制 (RER)
图搜索算法有两种基本类型：
▪ 深度优先，以及
▪ 广度优先。

▪ 深度优先算法从一个起始节点到某个结束节点，然后从同一起始节点沿着不同的路径重复搜索，直到查询得到回答。
▪ 通常，在尝试发现离散信息时，深度优先是一个不错的选择。 它们也是一般图遍历的好策略。
▪ 深度优先的最经典或基本级别是无信息搜索，其中算法搜索路径直到到达图的末尾，然后回溯到起始节点并尝试不同的路径。

▪ 与深度优先相反，处理语义丰富的图数据库允许进行广度优先算法，如果发现没有兼容的传出关系的节点，则提前终止搜索。
▪ 因此，广度优先算法的执行时间也较短。
▪ 广度优先算法通过一次探索一个图来进行搜索。
▪ 它们从离起始节点深一层的节点开始，然后是深度为 2 的节点，然后是深度为 3 的节点，依此类推，直到遍历了整个图

W12 Selecting a Database

选择 NoSQL 数据库

Relational Database NoSQL Database
在关系数据库设计中，实体的结构和关系驱动设计。 在 NoSQL 数据库设计中，性能比保留关系模型更重要。
关系模型的出现是出于务实的原因，即数据异常和难以将现有数据库重用于新应用程序 NoSQL 数据库的出现是出于务实的原因，特别是无法扩展以满足对大量读写操作不断增长的需求。
以提高读写性能作为交换，您可能会失去关系数据库的其他功能，例如即时一致性和 ACID 事务。

查询推动了数据模型的设计。
➢ 因为查询描述了数据的使用方式。
➢ 查询也是了解各种 NoSQL 数据库如何满足您需求的良好起点。
▪ 您还需要了解其他因素，例如
o读写量
o对副本中不一致数据的容忍度
o实体之间关系的性质以及它如何影响查询模式
o可用性和灾难恢复要求
o数据模型的灵活性需求
o延迟要求

文档数据库

▪ 文档数据库的设计具有灵活性。
▪ 如果应用程序需要能够存储各种属性以及大量数据，那么文档数据库是一个不错的选择。
➢ 例如，为了在关系数据库中表示产品，建模者可以使用一个表用于公共属性，并为每个产品子类型使用附加表来存储仅在产品子类型中使用的属性。
➢ 文档数据库可以轻松应对这种情况

▪ 文档数据库提供嵌入式文档，这对于反规范化很有用。
▪ 不是将数据存储在不同的表中，而是将经常一起查询的数据一起存储在同一个文档中。
▪ 文档数据库改进了带有索引的键值数据库的查询能力以及基于文档属性过滤文档的能力。
▪ 文档数据库可能是最受欢迎的 NoSQL 数据库，因为它们具有灵活性、性能和易用性。

▪ 这些数据库非常适合许多用例，包括：
o对具有大量读取和写入的网站的后端支持
o管理具有可变属性的数据类型，例如产品
o跟踪元数据的可变类型
o使用 JSON 数据结构的应用程序
o通过在结构中嵌入结构而受益于非规范化的应用程序

列族数据库

列族数据库专为海量数据、读写性能和高可用性而设计。
➢ Google 推出了 BigTable 来满足其服务的需求。
➢ Facebook 开发了 Cassandra 来支持其收件箱搜索服务。
▪ 这些数据库管理系统在多台服务器的集群上运行。
▪ 如果您的数据小到可以在单个服务器上运行，那么列族数据库可能超出您的需要——考虑使用文档或键值数据库

▪ 列族数据库非常适合用于：
o需要能够始终写入数据库的应用程序
o地理上分布在多个数据中心的应用程序
o可以容忍副本中一些短期不一致的应用程序
o具有动态字段的应用程序
o具有真正大量数据（例如数百 TB）潜力的应用程序

▪ 多个领域可以使用这种大数据处理能力，例如：
o使用网络流量和日志数据模式进行安全分析
oBig Science，例如使用遗传和蛋白质组学数据的生物信息学
o使用交易数据进行股市分析
oWeb 规模的应用程序，例如搜索
o社交网络服务

图数据库

▪ 适合表示为连接实体网络的问题域非常适合图数据库。
▪ 评估图形数据库有用性的一种方法是确定实体实例是否与其他实体实例有关系。
▪ 现在考虑图数据库讨论中提到的例子，例如连接城市的高速公路、蛋白质与其他蛋白质的相互作用以及员工与其他员工一起工作。 在所有这些情况下，两个实体实例之间都存在某种类型的连接、链接或直接关系。

▪ 电子商务应用程序中的两个订单可能彼此没有联系。
▪ 它们可能由同一位客户订购，但这是一个共享属性，而不是连接。

▪ 与前一种情况类似，一个游戏玩家的配置和游戏状态与其他游戏玩家的配置几乎没有关系。
▪ 像这样的实体很容易用键值、文档或关系数据库建模。

▪ 连接城市的高速公路、蛋白质与其他蛋白质的相互作用以及员工与其他员工一起工作。
▪ 在所有这些情况下，两个实体实例之间都存在某种类型的连接、链接或直接关系。

▪ 一些非常适合图数据库的问题域示例包括：
o网络和 IT 基础设施管理
o身份和访问管理
o业务流程管理
o推荐产品和服务
o社交网络
▪ 从这些例子中，很明显，当需要对实体之间的显式关系建模并快速遍历实体之间的路径时，图数据库是一个很好的数据库选择。

NoSQL vs 关系数据库

▪ NoSQL 和关系数据库是互补的。
▪ 关系数据库提供了许多保护数据完整性和降低数据异常风险的功能。
➢ 关系数据库会产生提供这些功能的操作开销。
▪ 在某些用例中，性能比确保即时一致性或支持 ACID 事务更重要。 在这些情况下，NoSQL 数据库可能是更好的解决方案。
▪ 选择数据库是为工作选择正确工具的过程。 您的工作组合越多样化，您的工具包就越多样化。

关系数据库将继续支持事务处理系统和商业智能应用程序。
➢ 数十年来在事务处理系统和数据仓库方面的工作已经产生了继续满足企业、政府和其他组织需求的最佳实践和设计原则。
➢ 同时，这些组织正在适应最初制定关系模型时不存在的技术。
➢ 面向客户的 Web 应用程序、移动服务和大数据分析可能适用于关系数据库，但在某些情况下则不然。
▪ 当前的技术格局需要多种数据库技术。

正如没有最好的编程语言，也没有最好的数据库管理系统。
▪ 存在比其他问题更适合某些问题的数据库系统，开发人员和设计人员的工作是为手头的需求找到最佳数据库。

概括

▪ 应用程序开发人员可以选择他们使用的编程语言、他们工作的开发环境以及他们部署的 Web 框架。 在数据库管理系统方面，他们也有选择。
➢ 开发不同类型的数据库管理系统都是为了解决其他类型数据库无法解决的现实问题。
▪ 开发人员和设计人员的工作之一是为他们的应用程序选择合适的数据库系统。
▪ 您可以通过了解您的问题域和您的用户要求来做到这一点。 通常你会有选择。
▪ 数据库的选择应由您的需求驱动

Exam

选择题10marks

NoSQL基础及Doc-O DB问答题10marks

mongodb案例10marks

Col-O DB问答题10marks

Cassandra案例10marks

Neo4j案例10marks（Mock里没看到query要求

考试要求一张纸，估计要画图（可能是画Neo4J设计）

Mock问答：

定义（建议去db的wiki网站找）&类比
优势
用例

Mock最后有ref提供三类db的参考（想必实际考试来不及看