Designing Data-intensive Applications Ch02

20th August 2020 at 2:19pm
Designing Data-intensive Applications

数据模型经常是一层叠一层的:

  1. 应用开发者一般会将现实世界的内容抽象成数据结构并提供 API 操作它们。这些数据结构一般是不通用的,仅适用于你的应用程序
  2. 为了存储或者展示这些数据,你经常需要使用 JSON / XML 文档,或者关系型数据库中的表等等
  3. 你所使用的数据库软件,会决定这些数据(比如关系型数据库中的表)在内存、磁盘或者网络上是怎样表现的,并且决定这些数据可以怎样被查询、修改等
  4. 在更底层,硬件工程师决定了各个字节怎样用电流、脉冲、磁场等形式来表示

Data models 有很多种,各自适合一些不同的场景。按你的应用的特性,选择好相应的 data models 是非常重要的事情。

Relational Model Versus Document Model

Relational model 一开始被使用于事务处理(银行交易、航班预订等)和批处理上。后来变得通用化。同期的其他模型,如 network model 和 hierarchical model 都发展不起来。

The Birth of NoSQL

NoSQL 在 2010s 开始流行开来。NoSQL 表示 Not Only SQL,目标是为了避免或者解决 relational model 中的一些问题:

  • 提高扩展性(scalability),特别是在大的数据集(dataset)和非常高的写入量时
  • 优先使用开源软件而不是商业软件
  • 支持一些 relational model 中无法比较好支持的查询方式
  • 支持比 relational schema 更灵活、有表达力的数据模型

The Object-Relational Mismatch

普遍存在对 SQL 数据模型的一个批判是,它引入了 impedance mismatch,即在业务代码和数据库数据间需要一层转换(比如把一行数据转为一个类实例)。比如下面 Bill Gates 的简历中,涉及一对多的部分(Experience, Education, Contact Info),需要用额外的表来存储:

当然新的 SQL 标准也加入了一些对结构化数据的支持,比如可以定义一个列为 JSON 数据,并对里面的 key 做索引等。不过这些能力并没有被广泛应用。

像简历这种 self-contained document,用 JSON 来表达是比较合适的。面向文档的数据库,如 MongoDB,RethinkDB 等支持这种数据模型:

{
  "user_id": 251,
  "first_name": "Bill",
  "last_name": "Gates",
  "summary": "Co-chair of the Bill & Melinda Gates... Active blogger.",
  "region_id": "us:91",
  "industry_id": 131,
  "photo_url": "/p/7/000/253/05b/308dd6e.jpg",
  "positions": [
    {"job_title": "Co-chair", "organization": "Bill & Melinda Gates Foundation"},
    {"job_title": "Co-founder, Chairman", "organization": "Microsoft"}
  ],
  "education": [
    {"school_name": "Harvard University",       "start": 1973, "end": 1975},
    {"school_name": "Lakeside School, Seattle", "start": null, "end": null}
  ],
  "contact_info": {
    "blog": "http://thegatesnotes.com",
    "twitter": "http://twitter.com/BillGates"
  }
}

JSON model:

  • 减少了 impedance mismatch,业务代码和数据模型结合更紧密
  • 增进了 locality,查同样的内容,RDBMS 需要多次查询或者联表查询,document-oriented database 只需要一次
  • Lack of schema:这个特性存在争论,有优点也有缺点,后面会有

Many-to-One and Many-to-Many Relationships

问题:

上面的例子中,为什么表示区域和行业时,要选择 ID(region_id, industry_id)而不是直接用字符串(如 "Greater Seatlle Area" 和 "Philanthropy")来表示?

原因:

用 ID 可以实现:

  • 一致的样式和拼写
  • 避免含糊不清(比如多个城市带有同个名字)
  • 容易更新,比如城市名发生变化后
  • 容易实现本地化,以别的语言展示
  • 更好进行搜索,比如后台如果纪录了西雅图是华盛顿中的一个城市,那么搜「华盛顿里的慈善家」也可以搜索出 Bill Gates

用 ID 的好处是,它本质上对于人类来说没有含义,所以即使它背后的数据发生了变化,ID 本身也不用变。用 ID 也可以避免用具体文本带来的需要批量更新问题。去除数据库中的重复数据,这个过程称之为 normalization。

Many-to-one Relationships and Many-to-many Relationships:

多对一关系(many-to-one relationships),比如「很多人居住在某个城市」(一般人只会居住在一个城市)。多对多关系(many-to-many relationships),比如「人们任职过某家公司」,一个人可能任职过多家公司,多家公司也可能有过不同的人任职。

对于这两种关系,一般适合在 RDBMS 中 normalize(因为有 join),但是在 document database 中则难以做到,它们的 join 能力一般会差一点。对于这种情况,你可能需要在应用代码中去做 join 的工作,比如发起多个数据库查询请求。

另外,即使 document database 适用于一开始的数据模型,但是随着业务发展,数据往往会倾向于互相有联系。

Are Document Databases Repeating History?

并没有。60s-70s 讨论过的 network model 和 hierachy model 对应用代码来说,使用的负担很重。

Relational Versus Document Databases Today

这一章主要从 data model 层面来做对比。

Which data model leads to simpler application code?

视你的业务形态而定。如果业务逻辑中有很多 many-to-one / many-to-many relationships,那么 RDBMS 合适。如果是 one-to-many 居多,或者有 collection 中的元素类型不定,可以考虑 document-based。

Schema flexibility in the document model

schema-on-read v.s. schema-on-write:

Document database 经常被称作 schemaless,但是这是不准确的。实现上数据的结构、类型是隐式的,仅在数据被读取时才被解释出来,因此称之为 schema-on-read 更合适。而 RDBMS 也可以被称作 schema-on-write,即数据库会保证写入的数据符合 schema 的定义。

类比:

  • Document databases, schema-on-read, 类似动态语言的运行时类型检查
  • RDBMS, schema-on-write, 类似静态语言的编译期类型检查

Data Migration:

Data Migration 涉及的数据变化的种类,见 Data Migration

RDBMS 利用 “statically typed” database schema 的特性,可以在 DB 层面提供支持:

ALTER TABLE users ADD COLUMN first_name text;
UPDATE users SET first_name = split_part(name, ' ', 1);        -- PostgreSQL
UPDATE users SET first_name = substring_index(name, ' ', 1);   -- MySQL

Document database 则没有 DB 层面的 migration 功能,一般有这么几种做法:

  • 单独写脚本去负责数据的迁移和回滚
  • 数据在业务代码中被读取时才更新。这会带来额外的代码复杂度。

Data locality for queries

对于读取:

  • 如果读的数据,对于 relational model 来说需要多次联表,对于 document model 则不需要查多次,因此后者的数据本地性(data locality)强,即可以消耗更少的时间、I/O 查询出结果
  • 如果 document 比较大,但是每次只需要读取其中一小块数据,那么 RDBMS 可能性能更佳

对于写入:

  • 如果 document 比较大,但是写入时仅需要更新其中部分字段,那么:
    • 如果写后 document 的体积没有显著变大,那么一般 document database 可以做到 in-place update,对性能影响小(参考 MongoDB 文章,关键字 "in-place update)
    • 如果写后 document 的体积显著变大,则难以做到 in-place update,需要整个 document 重写进数据库,对性能影响大
  • RDBMS 一般比较少存在这种问题

将关联的数据放在一起以增加本地性,必不仅是 document database 的做法。Google Spanner Database, Oracle, HBase 等均有类似的功能。

Convergence of document and relational databases

document database 和 relational database 都在互相采纳对方优秀的点:

  • 一些 RDBMS(如 MySQL,Postgres)支持将 XML / JSON 数据作为一列并将里面数据进行索引
  • 一些 document database 支持 join,如 RethinkDB
  • 一些 MongoDB driver 会在 client 通过多次查询模拟 join

Query Languages for Data

Imperative v.s. declarative

  • SQL: a declarative query language
  • IMS and CODASYL queried the database using imperative code

Declarative (声明式):

SELECT * FROM animals WHERE family = 'Sharks';

Imperative (指令式):

function getSharks() {
  var sharks = [];
  for (var i = 0; i < animals.length; i++) {
    if (animals[i].family === "Sharks") {
      sharks.push(animals[i]);
    }
  }
  return sharks;
}

声明式描述想要的最终结果。指令式描述处理的过程。声明式在数据库领域取得了胜利,它的好处有:

  • 对于使用者友好,更简单明了,使用者无需知道数据库底层工作原理
  • 相对声明式,对数据库软件来说更容易优化,比如数据库可以在不影响上层用户使用的情况下,对引擎进行优化,利用多核 CPU 等特性

Declarative Queries on the Web

Declarative query 不仅局限于数据库。网页上也有类似的例子。考虑下面的 HTML 结构:

<ul>
    <li class="selected">
        <p>Sharks</p>
        <ul>
            <li>Great White Shark</li>
            <li>Tiger Shark</li>
            <li>Hammerhead Shark</li>
        </ul>
    </li>
    <li>
        <p>Whales</p>
        <ul>
            <li>Blue Whale</li>
            <li>Humpback Whale</li>
            <li>Fin Whale</li>
        </ul>
    </li>
</ul>

如果你想将被选中的元素(class="seleted")的标题(<p>)的背景色置为蓝色,你可以用 CCS 表达,它是声明式的:

li.selected > p {
    background-color: blue;
}

如果不用声明式而用指令式,那么你可以用 JavaScript 这样写:

var liElements = document.getElementsByTagName("li");
for (var i = 0; i < liElements.length; i++) {
    if (liElements[i].className === "selected") {
        var children = liElements[i].childNodes;
        for (var j = 0; j < children.length; j++) {
            var child = children[j];
            if (child.nodeType === Node.ELEMENT_NODE && child.tagName === "P") {
                child.setAttribute("style", "background-color: blue");
            }
        }
    }
}

这里的 JS 对应上面 CSS 的方法,有一些明显缺陷:

  • JS 更长更难读懂
  • 如果 selected class 被动态移除(比如用户点击了别的 <li>),JS 的方案并不会自动去掉蓝色背景;但是 CSS 的方案中,浏览器会自动检测到变化并去掉蓝色背景
  • 如果 DOM 出了新的性能更好的 API,JS 需要被重写才能得到优化。但是如果是 CSS,优化可以被浏览器自己实现,不需要使用者关心

MapReduce Querying

MapReduce 是一个被用来在多台机器同时处理大量数据的 编程模型。它的实现介于 declarative 和 imperative 之间:处理数据的逻辑是用代码表达的,同时这些代码被框架所重复执行。

例子:

你是个海洋生物学家,你想统计每个月观察到的鲨鱼数量。

纯命令式:

你可以在 PostgreSQL 数据库里面这样写:

SELECT date_trunc('month', observation_timestamp) AS observation_month,
       sum(num_animals) AS total_animals
FROM observations
WHERE family = 'Sharks'
GROUP BY observation_month;

Using MongoDB’s MapReduce Feature:

db.observations.mapReduce(
    function map() {
        var year = this.observationTimestamp.getFullYear();
        var month = this.observationTimestamp.getMonth() + 1;
        emit(year + "-" + month, this.numAnimals);
    },
    function reduce(key, values) {
        return Array.sum(values);
    },
    {
        query: { family: "Sharks" },
        out: "monthlySharkReport"
    }
);

比如像这样的 observations:

[{
    observationTimestamp: Date.parse("Mon, 25 Dec 1995 12:34:56 GMT"),
    family: "Sharks",
    species: "Carcharodon carcharias",
    numAnimals: 3
},
{
    observationTimestamp: Date.parse("Tue, 12 Dec 1995 16:17:18 GMT"),
    family: "Sharks",
    species: "Carcharias taurus",
    numAnimals: 4
}]

会先经过 map 处理,emit 出两个 k-v 对,("1995-12", 3), ("1995-12", 4)。这两个 k-v 对在 reduce 时被聚合,reduce("1995-12", [3, 4]),结果返回 7。

总结:

对于 MapReduce 模型而言,mapreduce 函数是指令式的,你可以在里面实现简单的处理逻辑。整个框架是指令式的,一般框架都会将数据切分成多块到多台机器并行 map,最终再 reduce 回来。

一般 mapreduce 函数的实现,都必须是纯函数,即无副作用的。比如他们不能查询数据库,或者对外部数据有修改,而仅仅应该接受输入参数的数据并做处理。这使得框架可以以任意顺序运行函数,或者失败时进行重试。

MapReduce 模型并 不是 分布式数据处理的必须。很多数据库也实现了分布式处理,但是不用 Map-Reduce。SQL 的语法并不关心底层是 Map-Reduce 还是其他实现。

扩展:

MapReduce 的编写难度相对高,而且 DB 引擎难对其进行优化。因此 MongoDB 也提供了一种声明式查询语言 aggregation pipeline:

db.observations.aggregate([
    { $match: { family: "Sharks" } },
    {
        $group: {
            _id: {
                year: { $year: "$observationTimestamp" },
                month: { $month: "$observationTimestamp" }
            },
            totalAnimals: { $sum: "$numAnimals" }
        }
    }
]);

这可能是 JSON 形式的 SQL reinvent。

Graph-Like Data Models

Note
这种数据模型在应用上不广泛,在比较少的领域,如数据分析、知识图谱、SEO 优化等场景被使用到。

这类模型适用于关系非常复杂的场景:

  • 社交网络图,人是点(vertices),关系是线(edges)
  • 网页图,页面是点,页面上的超链接是线
  • 铁路图等

这类模型中的典型问题之一,计算两地的最短距离。

点(vertex)所表示的数据,不一定需要是相同类型的(homogeneous)。比如 Facebook 中,点即可以代表一个人,也可以代表打卡过的地方、评论和事件等等。

下面是一个图所结构化的示例:

Property Graphs

Property graph model:

  • 每个点由这些信息组成:
    • 唯一 ID
    • 一组以此点为起点的边
    • 一组以此点为终点的边
    • 一组 k-v 对,用来表示属性
  • 每个边由这些信息组成:
    • 唯一 ID
    • 边的起点(the tail vertex)
    • 边的终点(the head vertex)
    • 一个标签(label),用来表示两个点间的关系
    • 一组 k-v 对,用来表示属性

如果用关系型数据库的表来表达:

CREATE TABLE vertices (
    vertex_id integer PRIMARY KEY,
    properties json
);
CREATE TABLE edges (
    edge_id     integer PRIMARY KEY,
    tail_vertex integer REFERENCES vertices (vertex_id),
    head_vertex integer REFERENCES vertices (vertex_id),
    label       text,
    properties  json
);
CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

这种模型灵活性很高。你可以表示不同颗粒度的信息,比如 Lucy 的当前居住地为具体某一城市,但是它的出生地可以只标记在州这一级别。扩展性也很高。你可以往图中不停加入新数据,比如将 Lucy 的过敏源纪录进来,并纪录各过敏源所对应的食物,这样就可以判断出 Lucy 不能吃哪些食物。

The Cypher Query Language

Cypher 是 property graph 模型的一个声明式的查询语言。上面的例子用 Cypher 出来是这样的:

CREATE
  (NAmerica:Location {name:'North America', type:'continent'}),
  (USA:Location      {name:'United States', type:'country' }),
  (Idaho:Location    {name:'Idaho',         type:'state'}),
  (Lucy:Person       {name:'Lucy' }),
  (Idaho) -[:WITHIN]->  (USA)   -[:WITHIN]-> (NAmerica),
  (Lucy)  -[:BORN_IN]-> (Idaho)

有了数据后,我们就可以用 Cypher 查询出想的数据,例如查询出生在欧洲,但是居住在美国的人群:

MATCH
  (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
  (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

上面的例子表示要找到任何满足下面条件的人:

  • 它有一个 outgoing 的 BORN_IN 边,边的终点通过 WITHIN 链([:WITHIN*0..])最终指向 nameUnited States 的点
  • 它有一个 outgoing 的 LIVES_IN 边,边的终点通过 WITHIN 链([:WITHIN*0..])最终指向 nameEurope 的点
Note
如果有 person 的数据是直接 BORN_IN United States 而不是下面的具体地区,这条查询也是能查到数据的。因为 -[:WITHIN*0..]-> 表示要匹配的点可以没有 outgoing 的 WITHIN label。

使用指令式时,数据库引擎可以自动选择最高效的方式来执行查询,

  • 它即可以从 Person 数据开始,找到最终的 Location 数据;
  • 也可以从 Location 数据开始筛选,最终反向找到需要的 Person

Graph Queries in SQL

SQL 也可以表达上面的查询,但是会复杂很多。需要使用 recursive common table expressions。这里不详细描述。

Triple-Stores and SPARQL

Triple-Stores 的基本原理是,将数据表达为 (subject, predicate, object) 组成的三元对,比如 (Jim, likes, bananas)。其中:

  • subject,对应 property graph 中的 vertex
  • object
    • 可以是原子类型(如字符串或者数字),对应 property graph 中 vertex 的 properties
    • 也可以是图表中的另外一个 vertex,此时三元对对应 property graph 中的边
  • predicate 则类似于 property graph 中的边的 label

例如:

@prefix : <urn:example:>.
_:lucy     a       :Person.
_:lucy     :name   "Lucy".
_:lucy     :bornIn _:idaho.
_:idaho    a       :Location.
_:idaho    :name   "Idaho".
_:idaho    :type   "state".
_:idaho    :within _:usa.
_:usa      a       :Location.
_:usa      :name   "United States".
_:usa      :type   "country".
_:usa      :within _:namerica.
_:namerica a       :Location.
_:namerica :name   "North America".
_:namerica :type   "continent".

Triple-Stores 在设计之初并没有准备作为 semantic web 的实现手段,但是在 2000s 开始讨论并流行的 semantic web 风潮借鉴了它。The semantic web 认为网页已经是 human-readable 的了,那么为何不更进一步将其中的数据,变成 machine-readable 呢?期望最终达成 a kind of internet-wide “database of everything”。但是一直没有好的实现出现,同时标准屡次修改,后来并没有被推广开。

在此过程中产生了 Resource Description Framework (RDF)。RDF 虽然也是 triple-store 的理念,但是使用 XML。同时产生了 SPARQL (SPARQL Protocol and RDF Query Language),它是一门设计得不错的查询语言,后来前文提到的 Cypher 借鉴了它:

PREFIX : <urn:example:>
SELECT ?personName WHERE {
  ?person :name ?personName.
  ?person :bornIn / :within* / :name "United States".
  ?person :livesIn / :within* / :name "Europe".
}

The Foundation: Datalog

下面的 Datalog 例子感觉非常 inspiring。需要重点理解。

Datalog 这门查询语言比 SPARQL 及 Cypher 更老,在 80 年代被广泛用于教学上。它的一个实现,Cascalog,被使用在 Hadoop 的数据处理和查询功能中。

Datalog 的数据模型与 triple-store 类似,但它使用的是更泛化的 predicate(subject, object),如:

name(namerica, 'North America').
type(namerica, continent).

name(usa, 'United States').
type(usa, country).
within(usa, namerica).

name(idaho, 'Idaho').
type(idaho, state).
within(idaho, usa).

name(lucy, 'Lucy').
born_in(lucy, idaho).

对于之前用其他模型实现过的,查询生于欧洲但是现居住于美国的人,可以这样实现:

within_recursive(Location, Name) :- name(Location, Name).      /* Rule 1 */

within_recursive(Location, Name) :- within(Location, Via),     /* Rule 2 */
                                    within_recursive(Via, Name).

migrated(Name, BornIn, LivingIn) :- name(Person, Name),        /* Rule 3 */
                                    born_in(Person, BornLoc),
                                    within_recursive(BornLoc, BornIn),
                                    lives_in(Person, LivingLoc),
                                    within_recursive(LivingLoc, LivingIn).
?- migrated(Who, 'United States', 'Europe').
/* Who = 'Lucy'. */

对比于 Cypher 和 SPARQL 使用一条 SELECT 语句查出结果,Datalog 采用了更渐进式的方式来做。上面定义了三条规则,用来告诉数据库如何生成新的 predicate,比如 within_recursivemigrated。然后用这些新的 predicate 进行查询。

理解这几条规则的要点在于:

  • 大写字母开头的表示变量,如 Location, Name, Via 等
  • 每提供一条规则给到数据库,数据库会按此规则扫描现有的 predicate 并生成新的 predicate
  • 生成新的 predicate 的前提是,:- 操作符中定义的条件需要全部满足

例如:

// Existed predicate applied with rule 1, new predicate generated:
+ name(namerica, 'North America') 
    => within_recursive(namerica, 'North America')
      
// Existed predicate, cooperate with predicated generated in previous rule, applied with rule 2:
+ within(usa, namerica)
+ within_recursive(namerica, 'North America')
    => within_recursive(usa, 'North America')

下面的图描述了这一过程:

Datalog 的查询方式,在写一次性查询时会略显啰嗦,但是在处理复杂数据时会更强大更易理解。