数据模型经常是一层叠一层的:
Data models 有很多种,各自适合一些不同的场景。按你的应用的特性,选择好相应的 data models 是非常重要的事情。
Relational model 一开始被使用于事务处理(银行交易、航班预订等)和批处理上。后来变得通用化。同期的其他模型,如 network model 和 hierarchical model 都发展不起来。
NoSQL 在 2010s 开始流行开来。NoSQL 表示 Not Only SQL,目标是为了避免或者解决 relational model 中的一些问题:
普遍存在对 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:
问题:
上面的例子中,为什么表示区域和行业时,要选择 ID(region_id
, industry_id
)而不是直接用字符串(如 "Greater Seatlle Area" 和 "Philanthropy")来表示?
原因:
用 ID 可以实现:
用 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 适用于一开始的数据模型,但是随着业务发展,数据往往会倾向于互相有联系。
并没有。60s-70s 讨论过的 network model 和 hierachy model 对应用代码来说,使用的负担很重。
这一章主要从 data model 层面来做对比。
视你的业务形态而定。如果业务逻辑中有很多 many-to-one / many-to-many relationships,那么 RDBMS 合适。如果是 one-to-many 居多,或者有 collection 中的元素类型不定,可以考虑 document-based。
schema-on-read v.s. schema-on-write:
Document database 经常被称作 schemaless,但是这是不准确的。实现上数据的结构、类型是隐式的,仅在数据被读取时才被解释出来,因此称之为 schema-on-read 更合适。而 RDBMS 也可以被称作 schema-on-write,即数据库会保证写入的数据符合 schema 的定义。
类比:
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 功能,一般有这么几种做法:
对于读取:
对于写入:
将关联的数据放在一起以增加本地性,必不仅是 document database 的做法。Google Spanner Database, Oracle, HBase 等均有类似的功能。
document database 和 relational database 都在互相采纳对方优秀的点:
Imperative v.s. declarative
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;
}
声明式描述想要的最终结果。指令式描述处理的过程。声明式在数据库领域取得了胜利,它的好处有:
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 的方法,有一些明显缺陷:
selected
class 被动态移除(比如用户点击了别的 <li>
),JS 的方案并不会自动去掉蓝色背景;但是 CSS 的方案中,浏览器会自动检测到变化并去掉蓝色背景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 模型而言,map
和 reduce
函数是指令式的,你可以在里面实现简单的处理逻辑。整个框架是指令式的,一般框架都会将数据切分成多块到多台机器并行 map
,最终再 reduce
回来。
一般 map
及 reduce
函数的实现,都必须是纯函数,即无副作用的。比如他们不能查询数据库,或者对外部数据有修改,而仅仅应该接受输入参数的数据并做处理。这使得框架可以以任意顺序运行函数,或者失败时进行重试。
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。
这类模型适用于关系非常复杂的场景:
这类模型中的典型问题之一,计算两地的最短距离。
点(vertex)所表示的数据,不一定需要是相同类型的(homogeneous)。比如 Facebook 中,点即可以代表一个人,也可以代表打卡过的地方、评论和事件等等。
下面是一个图所结构化的示例:
Property graph model:
如果用关系型数据库的表来表达:
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 不能吃哪些食物。
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
上面的例子表示要找到任何满足下面条件的人:
BORN_IN
边,边的终点通过 WITHIN
链([:WITHIN*0..]
)最终指向 name
为 United States
的点LIVES_IN
边,边的终点通过 WITHIN
链([:WITHIN*0..]
)最终指向 name
为 Europe
的点person
的数据是直接 BORN_IN
United States 而不是下面的具体地区,这条查询也是能查到数据的。因为 -[:WITHIN*0..]->
表示要匹配的点可以没有 outgoing 的 WITHIN
label。使用指令式时,数据库引擎可以自动选择最高效的方式来执行查询,
Person
数据开始,找到最终的 Location
数据;Location
数据开始筛选,最终反向找到需要的 Person
SQL 也可以表达上面的查询,但是会复杂很多。需要使用 recursive common table expressions。这里不详细描述。
Triple-Stores 的基本原理是,将数据表达为 (subject, predicate, object)
组成的三元对,比如 (Jim, likes, bananas)
。其中:
subject
,对应 property graph 中的 vertexobject
,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".
}
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_recursive
及 migrated
。然后用这些新的 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 的查询方式,在写一次性查询时会略显啰嗦,但是在处理复杂数据时会更强大更易理解。