Hardware Faults

When we think of causes of system failure, hardware faults quickly come to mind. Hard disks crash, RAM becomes faulty, the power grid has a blackout, someone unplugs the wrong network cable. Anyone who has worked with large datacenters can tell you that these things happen all the time when you have a lot of machines.

当我们考虑系统故障的原因时，硬件故障很快就会跳入脑海。硬盘崩溃，内存损坏，电网停电，有人拔了错误的网络电缆。任何曾在大型数据中心工作过的人都可以告诉你，当你有很多机器时，这些事情经常发生。

Hard disks are reported as having a mean time to failure (MTTF) of about 10 to 50 years [ 5 , 6 ]. Thus, on a storage cluster with 10,000 disks, we should expect on average one disk to die per day.

硬盘通常被报告有一个平均故障时间（MTTF）约为10到50年[5, 6]。因此，在一个拥有10,000个硬盘的存储群集中，我们平均每天应该期望有一块硬盘损坏。

Our first response is usually to add redundancy to the individual hardware components in order to reduce the failure rate of the system. Disks may be set up in a RAID configuration, servers may have dual power supplies and hot-swappable CPUs, and datacenters may have batteries and diesel generators for backup power. When one component dies, the redundant component can take its place while the broken component is replaced. This approach cannot completely prevent hardware problems from causing failures, but it is well understood and can often keep a machine running uninterrupted for years.

我们通常的第一反应是将冗余添加到个别硬件组件中，以降低系统的故障率。可以将磁盘设置为RAID配置，服务器可以拥有双重电源和可热插拔的CPU，数据中心可以拥有备用电源的电池和柴油发电机。当一个组件出现故障时，冗余组件可以代替它的位置，而破损的组件则需要被更换。这种方法不能完全防止硬件问题导致故障，但是它是众所周知的，并且通常可以使一台机器连续运行多年。

Until recently, redundancy of hardware components was sufficient for most applications, since it makes total failure of a single machine fairly rare. As long as you can restore a backup onto a new machine fairly quickly, the downtime in case of failure is not catastrophic in most applications. Thus, multi-machine redundancy was only required by a small number of applications for which high availability was absolutely essential.

直到最近，硬件组件的冗余对于大多数应用程序来说已经足够，因为它使单台机器的完全失效变得相当罕见。只要能够相当快地将备份恢复到新机器上，在大多数应用程序中，发生故障时停机时间并不是灾难性的。因此，仅有少数应用程序需要多台机器的冗余，这对于绝对必要的高可用性是必需的。

However, as data volumes and applications’ computing demands have increased, more applications have begun using larger numbers of machines, which proportionally increases the rate of hardware faults. Moreover, in some cloud platforms such as Amazon Web Services (AWS) it is fairly common for virtual machine instances to become unavailable without warning [ 7 ], as the platforms are designed to prioritize flexibility and elasticity ⁱ over single-machine reliability.

然而，随着数据量和应用程序的计算需求增加，更多的应用程序开始使用更多的机器，这些机器的故障率也相应增加。此外，在一些云平台，例如AWS，虚拟机实例经常会在没有警告的情况下变得不可用[7]，因为这些平台的设计更注重灵活性和弹性而不是单机可靠性。

Hence there is a move toward systems that can tolerate the loss of entire machines, by using software fault-tolerance techniques in preference or in addition to hardware redundancy. Such systems also have operational advantages: a single-server system requires planned downtime if you need to reboot the machine (to apply operating system security patches, for example), whereas a system that can tolerate machine failure can be patched one node at a time, without downtime of the entire system (a rolling upgrade ; see Chapter 4 ).

因此，现在越来越倾向于使用软件容错技术来替代或补充硬件冗余，以实现整个机器的失效容忍系统。这样的系统还具有操作上的优势：单服务器系统需要计划停机时间才能重新启动机器（例如，应用操作系统安全补丁），而能够容忍机器故障的系统可以逐个升级节点而不需要整个系统停机（滚动升级；参见第四章）。

Software Errors

We usually think of hardware faults as being random and independent from each other: one machine’s disk failing does not imply that another machine’s disk is going to fail. There may be weak correlations (for example due to a common cause, such as the temperature in the server rack), but otherwise it is unlikely that a large number of hardware components will fail at the same time.

通常我们认为硬件故障是随机和相互独立的：一台机器的硬盘故障并不意味着另一台机器的硬盘会发生故障。可能存在一些弱相关性（例如由于共同的原因，例如服务器机架中的温度），但除此之外，大量硬件组件同时发生故障的可能性很小。

Another class of fault is a systematic error within the system [ 8 ]. Such faults are harder to anticipate, and because they are correlated across nodes, they tend to cause many more system failures than uncorrelated hardware faults [ 5 ]. Examples include:

另一类故障是系统内的系统性错误[8]。 这种故障很难预测，因为它们在节点之间存在相关性，因此它们往往比不相关的硬件故障导致更多的系统故障[5]。 例如：

• A software bug that causes every instance of an application server to crash when given a particular bad input. For example, consider the leap second on June 30, 2012, that caused many applications to hang simultaneously due to a bug in the Linux kernel [ 9 ].

  一个软件错误导致每个应用服务器在接收到特定的错误输入后都会崩溃。例如，考虑2012年6月30日的闰秒导致许多应用程序同时挂起，原因是Linux内核的错误[9]。

• A runaway process that uses up some shared resource—CPU time, memory, disk space, or network bandwidth.

  一个耗尽了一些共享资源的失控进程——CPU时间、内存、磁盘空间或网络带宽。

• A service that the system depends on that slows down, becomes unresponsive, or starts returning corrupted responses.

  系统依赖的服务变慢、无响应或返回错误响应。

• Cascading failures, where a small fault in one component triggers a fault in another component, which in turn triggers further faults [ 10 ].

  级联故障，一个组件的小故障会引发另一个组件的故障，接着又会触发更多的故障[10]。

The bugs that cause these kinds of software faults often lie dormant for a long time until they are triggered by an unusual set of circumstances. In those circumstances, it is revealed that the software is making some kind of assumption about its environment—and while that assumption is usually true, it eventually stops being true for some reason [ 11 ].

导致这些软件故障的错误通常会在很长一段时间内处于休眠状态，直到它们被一组不寻常的情况激活。在那种情况下，软件会揭示出它对环境做出某种假设——虽然这个假设通常是正确的，但它最终由于某种原因停止成立[11]。

There is no quick solution to the problem of systematic faults in software. Lots of small things can help: carefully thinking about assumptions and interactions in the system; thorough testing; process isolation; allowing processes to crash and restart; measuring, monitoring, and analyzing system behavior in production. If a system is expected to provide some guarantee (for example, in a message queue, that the number of incoming messages equals the number of outgoing messages), it can constantly check itself while it is running and raise an alert if a discrepancy is found [ 12 ].

软件系统存在系统性故障问题并非能立即解决。有许多小方法可以帮助解决：认真考虑系统中的假设和交互作用；进行彻底的测试；隔离处理；允许进程崩溃和重新启动；在生产中测量、监控和分析系统的行为。如果一个系统要提供某种保证（例如，在消息队列中，输入消息数等于输出消息数），它可以在运行时不断检查本身，并在发现差异时发出警报 [12]。

Human Errors

Humans design and build software systems, and the operators who keep the systems running are also human. Even when they have the best intentions, humans are known to be unreliable. For example, one study of large internet services found that configuration errors by operators were the leading cause of outages, whereas hardware faults (servers or network) played a role in only 10–25% of outages [ 13 ].

人类设计和构建软件系统，保持系统运行的操作员也是人类。即使他们有最好的意图，人类被证明是不可靠的。例如，一项针对大型互联网服务的研究发现，运营商的配置错误是停机的主要原因，而硬件故障（服务器或网络）仅在10-25%的停机中发挥作用[13]。

How do we make our systems reliable, in spite of unreliable humans? The best systems combine several approaches:

我们如何在人类不可靠的情况下使我们的系统可靠？最好的系统结合了几种方法：

• Design systems in a way that minimizes opportunities for error. For example, well-designed abstractions, APIs, and admin interfaces make it easy to do “the right thing” and discourage “the wrong thing.” However, if the interfaces are too restrictive people will work around them, negating their benefit, so this is a tricky balance to get right.

  以最小化错误机会的方式设计系统。例如，设计良好的抽象、API和管理界面可以使“正确的事情”变得容易，并避免“错误的事情”。然而，如果接口太严格，人们会绕过它们，抵消其好处，因此这是一个棘手的平衡问题。

• Decouple the places where people make the most mistakes from the places where they can cause failures. In particular, provide fully featured non-production sandbox environments where people can explore and experiment safely, using real data, without affecting real users.

  将人们经常犯错的地方与可能导致失败的地方分离开来。特别是，提供完整功能的非生产沙盒环境，人们可以在其中安全地探索和实验，使用真实数据，而不会影响真实用户。

• Test thoroughly at all levels, from unit tests to whole-system integration tests and manual tests [ 3 ]. Automated testing is widely used, well understood, and especially valuable for covering corner cases that rarely arise in normal operation.

  彻底测试各个层面，从单元测试到整个系统集成测试和手动测试[3]。自动化测试被广泛使用，被很好地理解，并且在覆盖在正常操作中很少出现的边缘情况时尤为有价值。

• Allow quick and easy recovery from human errors, to minimize the impact in the case of a failure. For example, make it fast to roll back configuration changes, roll out new code gradually (so that any unexpected bugs affect only a small subset of users), and provide tools to recompute data (in case it turns out that the old computation was incorrect).

  允许快速轻松地从人为错误中恢复，以最小化故障的影响。例如，快速回滚配置更改，逐步推出新代码（以便任何意外错误只影响一小部分用户），并提供重新计算数据的工具（以防旧计算结果不正确）。

• Set up detailed and clear monitoring, such as performance metrics and error rates. In other engineering disciplines this is referred to as telemetry . (Once a rocket has left the ground, telemetry is essential for tracking what is happening, and for understanding failures [ 14 ].) Monitoring can show us early warning signals and allow us to check whether any assumptions or constraints are being violated. When a problem occurs, metrics can be invaluable in diagnosing the issue.

  建立详细和清晰的监控，例如性能指标和错误率。在其他工程学科中，这被称为遥测。 （一旦火箭离开地面，遥测对于跟踪发生的情况和理解故障至关重要[14]。）监测可以向我们显示早期警告信号，并允许我们检查是否违反任何假设或约束。当问题发生时，指标可以非常有价值地诊断问题。

• Implement good management practices and training—a complex and important aspect, and beyond the scope of this book.

  实施良好的管理实践和培训——这是一个复杂而重要的方面，超出本书的范围。

How Important Is Reliability?

Reliability is not just for nuclear power stations and air traffic control software—more mundane applications are also expected to work reliably. Bugs in business applications cause lost productivity (and legal risks if figures are reported incorrectly), and outages of ecommerce sites can have huge costs in terms of lost revenue and damage to reputation.

可靠性不仅针对核电站和空中交通控制软件——更普通的应用程序同样需要保证可靠运行。商业应用程序中的漏洞会导致生产力下降（如果数字报告不正确，还会面临法律风险），电子商务网站的停机则会造成巨额损失，且声誉受损。

Even in “noncritical” applications we have a responsibility to our users. Consider a parent who stores all their pictures and videos of their children in your photo application [ 15 ]. How would they feel if that database was suddenly corrupted? Would they know how to restore it from a backup?

即使在“非关键”应用程序中，我们也有责任对我们的用户负责。考虑一个将他们所有的孩子的照片和视频存储在你的照片应用程序[15]中的父母。如果该数据库突然损坏，他们会感觉如何？他们知道如何从备份中恢复它吗？

There are situations in which we may choose to sacrifice reliability in order to reduce development cost (e.g., when developing a prototype product for an unproven market) or operational cost (e.g., for a service with a very narrow profit margin)—but we should be very conscious of when we are cutting corners.

在某些情况下，我们可能选择在可靠性方面做出牺牲，以降低开发成本（例如，针对未经证实的市场开发原型产品）或运营成本（例如，针对利润非常微薄的服务）——但我们应该非常清醒地意识到我们是在削减开销。

Describing Load

First, we need to succinctly describe the current load on the system; only then can we discuss growth questions (what happens if our load doubles?). Load can be described with a few numbers which we call load parameters . The best choice of parameters depends on the architecture of your system: it may be requests per second to a web server, the ratio of reads to writes in a database, the number of simultaneously active users in a chat room, the hit rate on a cache, or something else. Perhaps the average case is what matters for you, or perhaps your bottleneck is dominated by a small number of extreme cases.

首先，我们需要简洁地描述系统上的当前负载；只有这样我们才能讨论增长问题（如果我们的负载翻倍会发生什么？）。负载可以用一些数字来描述，我们称之为负载参数。参数的最佳选择取决于您系统的架构：可能是每秒钟对Web服务器的请求，数据库中读写比例，聊天室中的同时活跃用户数量，缓存命中率或其他内容。也许对您来说平均情况最重要，或者您的瓶颈由少数几个极端情况主导。

To make this idea more concrete, let’s consider Twitter as an example, using data published in November 2012 [ 16 ]. Two of Twitter’s main operations are:

为了使这个想法更具体化，让我们以Twitter为例，使用2012年11月发表的数据[16]。 Twitter的两个主要操作是：

Post tweet

A user can publish a new message to their followers (4.6k requests/sec on average, over 12k requests/sec at peak).

一个用户可以向他们的关注者发布一条新信息（平均每秒4.6k个请求，峰值时每秒超过12k个请求）。

Home timeline

A user can view tweets posted by the people they follow (300k requests/sec).

一个用户可以查看其关注者发布的推文（每秒300k次请求）。

Simply handling 12,000 writes per second (the peak rate for posting tweets) would be fairly easy. However, Twitter’s scaling challenge is not primarily due to tweet volume, but due to fan-out ⁱⁱ —each user follows many people, and each user is followed by many people. There are broadly two ways of implementing these two operations:

处理每秒12000次写入（发布推文的峰值速率）将相当容易。然而，Twitter的扩展挑战不主要是由于推文数量，而是由于扇出-每个用户都关注许多人，每个用户都被许多人关注。实现这两个操作通常有两种方式：

1. Posting a tweet simply inserts the new tweet into a global collection of tweets. When a user requests their home timeline, look up all the people they follow, find all the tweets for each of those users, and merge them (sorted by time). In a relational database like in Figure 1-2 , you could write a query such as:

   发布一条推文只会将其插入到全球推文集合中。当用户请求其主页时间线时，找出他们关注的所有人，找到每个用户的所有推文，并合并它们（按时间排序）。在关系型数据库中，可以编写查询语句，例如图1-2中的查询语句：

   SELECT tweets.*, users.* FROM tweets
     JOIN users   ON tweets.sender_id    = users.id
     JOIN follows ON follows.followee_id = users.id
     WHERE follows.follower_id = current_user

2. Maintain a cache for each user’s home timeline—like a mailbox of tweets for each recipient user (see Figure 1-3 ). When a user posts a tweet , look up all the people who follow that user, and insert the new tweet into each of their home timeline caches. The request to read the home timeline is then cheap, because its result has been computed ahead of time.

   为每个用户的主页时间线维护一个缓存——就像每个接受者用户的推文邮箱（参见图1-3）。当用户发布一条推文时，查找所有关注该用户的人，并将新的推文插入到他们每个人的主页时间线缓存中。因为结果已经提前计算出来，所以读取主页时间线的请求非常便宜。

Figure 1-2. Simple relational schema for implementing a Twitter home timeline.

Figure 1-3. Twitter’s data pipeline for delivering tweets to followers, with load parameters as of November 2012 [ 16 ].

The first version of Twitter used approach 1, but the systems struggled to keep up with the load of home timeline queries, so the company switched to approach 2. This works better because the average rate of published tweets is almost two orders of magnitude lower than the rate of home timeline reads, and so in this case it’s preferable to do more work at write time and less at read time.

Twitter的第一版使用方法1，但是那时系统很难跟上主页时间轴查询的负载，所以公司转而使用方法2。这个方法效果更好，因为发布推文的平均速率比主页时间轴读取的速率低了近两个数量级，所以在这种情况下，在写入时做更多的工作，而在读取时做更少的工作更好。

However, the downside of approach 2 is that posting a tweet now requires a lot of extra work. On average, a tweet is delivered to about 75 followers, so 4.6k tweets per second become 345k writes per second to the home timeline caches. But this average hides the fact that the number of followers per user varies wildly, and some users have over 30 million followers. This means that a single tweet may result in over 30 million writes to home timelines! Doing this in a timely manner—Twitter tries to deliver tweets to followers within five seconds—is a significant challenge.

然而，方法2的缺点是现在发布推文需要额外的工作量。平均而言，一条推文会被传递给约75个关注者，因此每秒4.6k条推文就变成了对主页时间轴缓存的345k次写入。但这个平均数隐藏了一个事实，即每个用户的关注者数量差异很大，有些用户拥有超过3000万的关注者。这意味着一条推文可能会导致3000万次对主页时间轴的写入！而在Twitter尝试在五秒内向关注者传递推文的情况下及时完成这项工作是一个巨大的挑战。

In the example of Twitter, the distribution of followers per user (maybe weighted by how often those users tweet) is a key load parameter for discussing scalability, since it determines the fan-out load. Your application may have very different characteristics, but you can apply similar principles to reasoning about its load.

以 Twitter 为例，用户的关注者分布（可能根据其推文频率加权）是讨论可扩展性的关键负载参数，因为它决定了扇出负载。你的应用程序可能具有非常不同的特点，但你可以应用类似的原则来推理它的负载。

The final twist of the Twitter anecdote: now that approach 2 is robustly implemented, Twitter is moving to a hybrid of both approaches. Most users’ tweets continue to be fanned out to home timelines at the time when they are posted, but a small number of users with a very large number of followers (i.e., celebrities) are excepted from this fan-out. Tweets from any celebrities that a user may follow are fetched separately and merged with that user’s home timeline when it is read, like in approach 1. This hybrid approach is able to deliver consistently good performance. We will revisit this example in Chapter 12 after we have covered some more technical ground.

发推特轶事的最后转折：现在实现了方法2，推特正在朝着两种方法的混合方式迈进。大多数用户的推特在发布时仍会在主页时间轴上扇出，但有一小部分拥有大量粉丝（即名人）的用户会被例外。用户可能会关注的任何名人的推特会单独获取并在读取时与该用户的主页时间轴合并，类似于方法1。这种混合方法能够提供一致的良好性能。在我们覆盖了一些更技术性的地面后，我们将在第12章重新审视这个例子。

Describing Performance

Once you have described the load on your system, you can investigate what happens when the load increases. You can look at it in two ways:

一旦你描述了系统的负载，你就可以调查当负载增加时会发生什么。你可以从两个方面来看待它：

• When you increase a load parameter and keep the system resources (CPU, memory, network bandwidth, etc.) unchanged, how is the performance of your system affected?

  当您增加负载参数并保持系统资源（CPU，内存，网络带宽等）不变时，系统的性能会受到影响吗？

• When you increase a load parameter, how much do you need to increase the resources if you want to keep performance unchanged?

  当你增加负载参数时，如果想保持性能不变，需要增加多少资源？

Both questions require performance numbers, so let’s look briefly at describing the performance of a system.

两个问题都需要性能数字，因此让我们简要地描述一下系统的性能。

In a batch processing system such as Hadoop, we usually care about throughput —the number of records we can process per second, or the total time it takes to run a job on a dataset of a certain size. ⁱⁱⁱ In online systems, what’s usually more important is the service’s response time —that is, the time between a client sending a request and receiving a response.

在像Hadoop这样的批处理系统中，我们通常关心吞吐量——每秒可以处理的记录数量，或者在特定大小的数据集上运行作业所需的总时间。在在线系统中，更重要的是服务的响应时间——即客户端发送请求和接收响应之间的时间。

Even if you only make the same request over and over again, you’ll get a slightly different response time on every try. In practice, in a system handling a variety of requests, the response time can vary a lot. We therefore need to think of response time not as a single number, but as a distribution of values that you can measure.

即使你一遍又一遍地做出相同的请求，每次尝试得到的响应时间也会稍有不同。在实践中，对于处理各种请求的系统，响应时间可能会有很大的差异。因此，我们需要将响应时间看作一组可以测量的值的分布，而不是一个单一的数字。

In Figure 1-4 , each gray bar represents a request to a service, and its height shows how long that request took. Most requests are reasonably fast, but there are occasional outliers that take much longer. Perhaps the slow requests are intrinsically more expensive, e.g., because they process more data. But even in a scenario where you’d think all requests should take the same time, you get variation: random additional latency could be introduced by a context switch to a background process, the loss of a network packet and TCP retransmission, a garbage collection pause, a page fault forcing a read from disk, mechanical vibrations in the server rack [ 18 ], or many other causes.

在图1-4中，每个灰色条代表对服务的请求，其高度显示了该请求所花费的时间。大多数请求的速度都比较快，但偶尔会出现一些耗时更长的异常值。也许慢请求本质上更昂贵，例如因为它们处理的数据更多。但即使在所有请求应该花费相同时间的情况下，你也会得到变化：随机额外的延迟可能会由于切换到后台进程、网络数据包的丢失和TCP重传、垃圾收集暂停、在服务器架中机械振动 [18] 或其他许多原因引入。

Figure 1-4. Illustrating mean and percentiles: response times for a sample of 100 requests to a service.

It’s common to see the average response time of a service reported. (Strictly speaking, the term “average” doesn’t refer to any particular formula, but in practice it is usually understood as the arithmetic mean : given n values, add up all the values, and divide by n .) However, the mean is not a very good metric if you want to know your “typical” response time, because it doesn’t tell you how many users actually experienced that delay.

通常会报告服务的平均响应时间。（严格来说，“平均值”一词并不指代任何特定的公式，但在实践中通常被理解为算术平均值：给定 n 个值，将所有值相加，然后除以 n。）然而，如果你想知道你的“典型”响应时间，平均数不是一个很好的度量标准，因为它不告诉你有多少个用户实际上经历了那个延迟。

Usually it is better to use percentiles . If you take your list of response times and sort it from fastest to slowest, then the median is the halfway point: for example, if your median response time is 200 ms, that means half your requests return in less than 200 ms, and half your requests take longer than that.

通常最好使用百分位数。如果您将响应时间列表按从最快到最慢进行排序，则中位数是中间点：例如，如果中位数响应时间为200毫秒，则表示您一半的请求在200毫秒以下返回，一半的请求需要更长时间。

This makes the median a good metric if you want to know how long users typically have to wait: half of user requests are served in less than the median response time, and the other half take longer than the median. The median is also known as the 50th percentile , and sometimes abbreviated as p50 . Note that the median refers to a single request; if the user makes several requests (over the course of a session, or because several resources are included in a single page), the probability that at least one of them is slower than the median is much greater than 50%.

这使得中位数成为一种良好的度量方法，如果您想知道用户通常需要等待多长时间：一半的用户请求在低于中位响应时间的情况下得到服务，另一半需要比中位数更长的时间。中位数也被称为第50个百分位数，并有时缩写为p50。请注意，中位数是指单个请求;如果用户发出多个请求（在会话期间或因为单个页面包括多个资源），则至少有一个请求慢于中位数的概率远大于50％。

In order to figure out how bad your outliers are, you can look at higher percentiles: the 95th , 99th , and 99.9th percentiles are common (abbreviated p95 , p99 , and p999 ). They are the response time thresholds at which 95%, 99%, or 99.9% of requests are faster than that particular threshold. For example, if the 95th percentile response time is 1.5 seconds, that means 95 out of 100 requests take less than 1.5 seconds, and 5 out of 100 requests take 1.5 seconds or more. This is illustrated in Figure 1-4 .

为了弄清异常数据有多严重，你可以查看更高的百分位数：95％、99％和99.9％百分位数是常见的（简写为p95、p99和p999）。它们是响应时间阈值，其中95％、99％或99.9％的请求速度比特定阈值更快。举例来说，如果95％分位数的响应时间为1.5秒，就意味着100个请求中有95个会在1.5秒内完成，而有5个需要1.5秒或更长时间。这在图1-4中有所说明。

High percentiles of response times, also known as tail latencies , are important because they directly affect users’ experience of the service. For example, Amazon describes response time requirements for internal services in terms of the 99.9th percentile, even though it only affects 1 in 1,000 requests. This is because the customers with the slowest requests are often those who have the most data on their accounts because they have made many purchases—that is, they’re the most valuable customers [ 19 ]. It’s important to keep those customers happy by ensuring the website is fast for them: Amazon has also observed that a 100 ms increase in response time reduces sales by 1% [ 20 ], and others report that a 1-second slowdown reduces a customer satisfaction metric by 16% [ 21 , 22 ].

高响应时间的百分位，也称为尾部延迟，非常重要，因为直接影响用户对服务的体验。例如，亚马逊在内部服务中以99.9百分位的响应时间要求为例，即使只影响了1,000个请求中的1个。这是因为最慢请求的客户通常是那些拥有许多账户数据的客户，因为他们进行了多次购买，即他们是最有价值的客户[19]。通过确保网站对这些客户快速，可以保持这些客户的满意度：亚马逊还观察到，响应时间增加100毫秒会导致销售额下降1%[20]，其他人则报告，1秒的减速会将客户满意度指标降低16% [21,22]。

On the other hand, optimizing the 99.99th percentile (the slowest 1 in 10,000 requests) was deemed too expensive and to not yield enough benefit for Amazon’s purposes. Reducing response times at very high percentiles is difficult because they are easily affected by random events outside of your control, and the benefits are diminishing.

另一方面，优化第99.99个百分位数（最慢的10000个请求中的1个）被认为对于亚马逊的目的来说太昂贵且利益不足。在非常高的百分位数上降低响应时间很困难，因为它们很容易受到无法控制的随机事件的影响，而且效益逐渐变小。

For example, percentiles are often used in service level objectives (SLOs) and service level agreements (SLAs), contracts that define the expected performance and availability of a service. An SLA may state that the service is considered to be up if it has a median response time of less than 200 ms and a 99th percentile under 1 s (if the response time is longer, it might as well be down), and the service may be required to be up at least 99.9% of the time. These metrics set expectations for clients of the service and allow customers to demand a refund if the SLA is not met.

例如，百分位数通常用于服务水平目标（SLO）和服务水平协议（SLA），这些协议定义了服务的预期性能和可用性。SLA 可以说明，如果服务的中位响应时间小于 200 毫秒且 99 百分位数小于 1 秒，则认为该服务处于上线状态（如果响应时间更长，则可以认为已经下线），并且该服务可能需要保持至少 99.9% 的可用性。这些指标为服务的客户设定了期望，并允许客户在未达到 SLA 的情况下要求退款。

Queueing delays often account for a large part of the response time at high percentiles. As a server can only process a small number of things in parallel (limited, for example, by its number of CPU cores), it only takes a small number of slow requests to hold up the processing of subsequent requests—an effect sometimes known as head-of-line blocking . Even if those subsequent requests are fast to process on the server, the client will see a slow overall response time due to the time waiting for the prior request to complete. Due to this effect, it is important to measure response times on the client side.

排队延迟通常占高百分位响应时间的很大一部分。由于一个服务器只能处理少量并行事项（例如受其CPU核心数量限制），只需要极少量缓慢请求就足以阻塞后续请求的处理——这种效应有时被称为头阻塞。即使这些后续请求在服务器上处理很快，客户端也会因等待先前请求完成而看到较慢的总响应时间。由于此效应，客户端测量响应时间非常重要。

When generating load artificially in order to test the scalability of a system, the load-generating client needs to keep sending requests independently of the response time. If the client waits for the previous request to complete before sending the next one, that behavior has the effect of artificially keeping the queues shorter in the test than they would be in reality, which skews the measurements [ 23 ].

当人工产生负载以测试系统的可扩展性时，产生负载的客户端需要独立于响应时间继续发送请求。如果客户端在发送下一个请求之前等待前一个请求完成，这种行为会在测试中人为地使队列比实际上要短，从而扭曲测量结果[23]。

Figure 1-5. When several backend calls are needed to serve a request, it takes just a single slow backend request to slow down the entire end-user request.

Approaches for Coping with Load

Now that we have discussed the parameters for describing load and metrics for measuring performance, we can start discussing scalability in earnest: how do we maintain good performance even when our load parameters increase by some amount?

现在我们已经讨论了描述负载的参数和测量性能的指标，我们可以认真讨论可扩展性了：即使我们的负载参数增加了一定量，我们如何保持良好的性能？

An architecture that is appropriate for one level of load is unlikely to cope with 10 times that load. If you are working on a fast-growing service, it is therefore likely that you will need to rethink your architecture on every order of magnitude load increase—or perhaps even more often than that.

如果一种架构适合某个负载水平，那么它很可能无法应对10倍于此的负载。如果你在开发一个快速增长的服务，那么在每一次负载增加一个数量级时，你很可能需要重新思考你的架构，甚至需要更频繁地重构。

People often talk of a dichotomy between scaling up ( vertical scaling , moving to a more powerful machine) and scaling out ( horizontal scaling , distributing the load across multiple smaller machines). Distributing load across multiple machines is also known as a shared-nothing architecture. A system that can run on a single machine is often simpler, but high-end machines can become very expensive, so very intensive workloads often can’t avoid scaling out. In reality, good architectures usually involve a pragmatic mixture of approaches: for example, using several fairly powerful machines can still be simpler and cheaper than a large number of small virtual machines.

人们经常谈论缩放的二分法（垂直缩放，移动到更强大的机器和水平缩放，将负载分布在多台较小的机器上）。在多台机器上分布负载也被称为“不共享任何东西”的架构。可以在单个机器上运行的系统通常更简单，但高端机器可能非常昂贵，因此非常密集的工作负载通常无法避免缩放。实际上，良好的架构通常涉及实用主义的方法混合：例如，使用几台相对强大的机器仍然可能比大量小虚拟机更简单，更便宜。

Some systems are elastic , meaning that they can automatically add computing resources when they detect a load increase, whereas other systems are scaled manually (a human analyzes the capacity and decides to add more machines to the system). An elastic system can be useful if load is highly unpredictable, but manually scaled systems are simpler and may have fewer operational surprises (see “Rebalancing Partitions” ).

一些系统是弹性的，意味着它们在检测到负载增加时可以自动添加计算资源，而其他系统则需要手动扩容（由人员分析容量并决定是否需要添加更多机器）。当负载高度不可预测时，弹性系统可能非常有用，但手动扩容的系统更简单，可能会有更少的操作意外（请参见“重新平衡分区”）。

While distributing stateless services across multiple machines is fairly straightforward, taking stateful data systems from a single node to a distributed setup can introduce a lot of additional complexity. For this reason, common wisdom until recently was to keep your database on a single node (scale up) until scaling cost or high-availability requirements forced you to make it distributed.

将无状态服务分发到多台机器上相对来说相当简单，但将有状态数据系统从单节点迁移至分布式环境则可能引入大量额外复杂性。因此，直到不久之前，通常被认为明智之举是将数据库保持在单一节点上（纵向扩展）直至扩展成本或高可用性需求迫使你将其变为分布式环境。

As the tools and abstractions for distributed systems get better, this common wisdom may change, at least for some kinds of applications. It is conceivable that distributed data systems will become the default in the future, even for use cases that don’t handle large volumes of data or traffic. Over the course of the rest of this book we will cover many kinds of distributed data systems, and discuss how they fare not just in terms of scalability, but also ease of use and maintainability.

随着分布式系统的工具和抽象层的不断完善，这些普遍的认识可能会改变，至少对某些应用而言是如此。未来，分布式数据系统有可能成为默认选择，即使是用于不处理大量数据或流量的案例。在本书的其余部分，我们将涵盖许多种分布式数据系统，并讨论它们在可扩展性、易用性和可维护性方面的表现。

The architecture of systems that operate at large scale is usually highly specific to the application—there is no such thing as a generic, one-size-fits-all scalable architecture (informally known as magic scaling sauce ). The problem may be the volume of reads, the volume of writes, the volume of data to store, the complexity of the data, the response time requirements, the access patterns, or (usually) some mixture of all of these plus many more issues.

大规模操作系统的架构通常高度特定于应用程序——没有通用的、一刀切的可扩展架构（俗称神奇扩展酱）。问题可能是读取量、写入量、存储数据量、数据复杂性、响应时间要求、访问模式，或（通常）所有这些问题的混合，加上许多其他问题。

For example, a system that is designed to handle 100,000 requests per second, each 1 kB in size, looks very different from a system that is designed for 3 requests per minute, each 2 GB in size—even though the two systems have the same data throughput.

例如，一个被设计为每秒处理100,000个1kB请求的系统，看起来与一个被设计为每分钟处理3个2GB请求的系统非常不同，即使这两个系统具有相同的数据吞吐量。

An architecture that scales well for a particular application is built around assumptions of which operations will be common and which will be rare—the load parameters. If those assumptions turn out to be wrong, the engineering effort for scaling is at best wasted, and at worst counterproductive. In an early-stage startup or an unproven product it’s usually more important to be able to iterate quickly on product features than it is to scale to some hypothetical future load.

一种可适用于特定应用的可扩展架构是基于哪些操作是常见的和哪些是罕见的假设——负载参数来构建的。如果这些假设被证明是错误的，那么扩展的工程努力将至少是浪费的，而在最坏的情况下可能是适得其反的。在初创阶段的创业公司或未经验证产品中，能够快速迭代产品特性通常比将来某个假设负载的扩展更加重要。

Even though they are specific to a particular application, scalable architectures are nevertheless usually built from general-purpose building blocks, arranged in familiar patterns. In this book we discuss those building blocks and patterns.

尽管可扩展架构是针对特定应用而设计的，但通常是由常见的通用构建块组成的，排列成熟悉的模式。在本书中，我们将讨论这些构建块和模式。

Operability: Making Life Easy for Operations

It has been suggested that “good operations can often work around the limitations of bad (or incomplete) software, but good software cannot run reliably with bad operations” [ 12 ]. While some aspects of operations can and should be automated, it is still up to humans to set up that automation in the first place and to make sure it’s working correctly.

有人建议“好的操作通常可以克服不好（或不完整）的软件限制，但是好的软件不能可靠地运行不良操作”[12]。虽然某些操作方面可以和应该被自动化，但最终还是需要人类来进行第一次自动化设置，并确保其正确地运行。

Operations teams are vital to keeping a software system running smoothly. A good operations team typically is responsible for the following, and more [ 29 ]:

运维团队对于保持软件系统平稳运行非常重要。一个优秀的运维团队通常负责以下工作，以及更多其他事项 [29]：

• Monitoring the health of the system and quickly restoring service if it goes into a bad state

  监控系统的健康状况，如果系统状态不佳，迅速恢复服务。

• Tracking down the cause of problems, such as system failures or degraded performance

  追踪问题的原因，例如系统故障或性能降低。

• Keeping software and platforms up to date, including security patches

  保持软件和平台更新，包括安全补丁。

• Keeping tabs on how different systems affect each other, so that a problematic change can be avoided before it causes damage

  监控不同系统之间的相互影响，以避免出现可能导致破坏的问题性变化。

• Anticipating future problems and solving them before they occur (e.g., capacity planning)

  预料未来的问题并在它们发生之前解决它们（例如，容量规划）。

• Establishing good practices and tools for deployment, configuration management, and more

  建立好的实践和工具，用于部署、配置管理等方面。

• Performing complex maintenance tasks, such as moving an application from one platform to another

  执行复杂的维护任务，例如将一个应用程序从一个平台移动到另一个平台。

• Maintaining the security of the system as configuration changes are made

  随着配置变化的发生，维护系统的安全性。

• Defining processes that make operations predictable and help keep the production environment stable

  定义使操作可预测并帮助保持生产环境稳定的流程。

• Preserving the organization’s knowledge about the system, even as individual people come and go

  保留组织对系统的知识，即使个别人员进出。

Good operability means making routine tasks easy, allowing the operations team to focus their efforts on high-value activities. Data systems can do various things to make routine tasks easy, including:

良好的可操作性意味着使日常任务变得更加容易，使运营团队可以将精力集中在高价值的活动上。数据系统可以采取各种方式来简化日常任务，其中包括：

• Providing visibility into the runtime behavior and internals of the system, with good monitoring

  提供对系统运行行为和内部情况的可见性，带有良好的监控。

• Providing good support for automation and integration with standard tools

  为自动化提供良好支持并与标准工具进行集成。

• Avoiding dependency on individual machines (allowing machines to be taken down for maintenance while the system as a whole continues running uninterrupted)

  避免依赖特定的机器（使机器可以在维护期间关闭，而整个系统仍能无间断地运行）。

• Providing good documentation and an easy-to-understand operational model (“If I do X, Y will happen”)

  提供良好的文档和易于理解的操作模型（“如果我做 X，就会发生 Y”）。

• Providing good default behavior, but also giving administrators the freedom to override defaults when needed

  提供良好的默认行为，但也给管理员在需要时覆盖默认值的自由。

• Self-healing where appropriate, but also giving administrators manual control over the system state when needed

  在必要时进行自愈，但也在需要时赋予管理员手动控制系统状态的能力。

• Exhibiting predictable behavior, minimizing surprises

  展示可预测的行为，最小化惊喜。

Simplicity: Managing Complexity

Small software projects can have delightfully simple and expressive code, but as projects get larger, they often become very complex and difficult to understand. This complexity slows down everyone who needs to work on the system, further increasing the cost of maintenance. A software project mired in complexity is sometimes described as a big ball of mud [ 30 ].

小型软件项目可以拥有简单明了且表达清晰的代码，但随着项目规模的扩大，往往会变得非常复杂且难以理解。这种复杂性会拖慢每一个需要处理该系统的人，进一步增加了维护成本。一个陷入复杂困境的软件项目有时被描述为一个沉重的泥球。[30]

There are various possible symptoms of complexity: explosion of the state space, tight coupling of modules, tangled dependencies, inconsistent naming and terminology, hacks aimed at solving performance problems, special-casing to work around issues elsewhere, and many more. Much has been said on this topic already [ 31 , 32 , 33 ].

复杂性可能会出现各种症状：状态空间爆炸，模块之间紧密耦合，依赖关系错综复杂，命名和术语不一致，为解决性能问题而进行的修改，为解决其他问题而进行的特殊处理等等。已经有很多关于这个话题的讨论[31，32，33]。

When complexity makes maintenance hard, budgets and schedules are often overrun. In complex software, there is also a greater risk of introducing bugs when making a change: when the system is harder for developers to understand and reason about, hidden assumptions, unintended consequences, and unexpected interactions are more easily overlooked. Conversely, reducing complexity greatly improves the maintainability of software, and thus simplicity should be a key goal for the systems we build.

当复杂性使得维护困难时，预算和计划常常会超支。在复杂的软件中，更容易引入错误风险：当开发人员难以理解和推理系统时，隐藏的假设、意外的后果和意外的交互就很容易被忽视。相反，减少复杂性极大地提高了软件的可维护性，因此简单性应成为我们构建系统的关键目标。

Making a system simpler does not necessarily mean reducing its functionality; it can also mean removing accidental complexity. Moseley and Marks [ 32 ] define complexity as accidental if it is not inherent in the problem that the software solves (as seen by the users) but arises only from the implementation.

简化系统不一定意味着减少其功能；这也可能意味着消除偶然复杂性。Moseley和Marks [32]将复杂性定义为偶然的，如果它不是软件解决的问题本身固有的（如用户所看到的），而仅仅是由实现引起的。

One of the best tools we have for removing accidental complexity is abstraction . A good abstraction can hide a great deal of implementation detail behind a clean, simple-to-understand façade. A good abstraction can also be used for a wide range of different applications. Not only is this reuse more efficient than reimplementing a similar thing multiple times, but it also leads to higher-quality software, as quality improvements in the abstracted component benefit all applications that use it.

我们用来消除无意的复杂性的最佳工具之一是抽象化。良好的抽象化可以在一个干净、简单易懂的立面后面隐藏许多实现细节。良好的抽象化也可以用于广泛的不同应用。这种重用不仅比多次重新实现相似的东西更有效率，而且还会导致高质量的软件，因为在被抽象化的组件中的质量改进将使所有使用它的应用受益。

For example, high-level programming languages are abstractions that hide machine code, CPU registers, and syscalls. SQL is an abstraction that hides complex on-disk and in-memory data structures, concurrent requests from other clients, and inconsistencies after crashes. Of course, when programming in a high-level language, we are still using machine code; we are just not using it directly , because the programming language abstraction saves us from having to think about it.

例如，高级编程语言是抽象层，它们隐藏了机器码、CPU寄存器和系统调用。SQL是一个抽象层，它隐藏了复杂的磁盘和内存数据结构，其他客户端的并发请求，以及崩溃后的不一致性。当然，当使用高级语言编程时，我们仍然使用机器码；我们只是不直接使用它，因为编程语言的抽象层帮助我们不必考虑它。

However, finding good abstractions is very hard. In the field of distributed systems, although there are many good algorithms, it is much less clear how we should be packaging them into abstractions that help us keep the complexity of the system at a manageable level.

然而，寻找好的抽象概念是非常困难的。在分布式系统领域，虽然有许多好的算法，但我们如何将它们打包成有助于我们将系统的复杂性保持在可控范围内的抽象概念，却不太清楚。

Throughout this book, we will keep our eyes open for good abstractions that allow us to extract parts of a large system into well-defined, reusable components.

在本书中，我们将密切关注好的抽象，以便将大系统的部分提取到明确定义的可重用组件中。

Evolvability: Making Change Easy

It’s extremely unlikely that your system’s requirements will remain unchanged forever. They are much more likely to be in constant flux: you learn new facts, previously unanticipated use cases emerge, business priorities change, users request new features, new platforms replace old platforms, legal or regulatory requirements change, growth of the system forces architectural changes, etc.

你的系统需求永远不可能保持不变。它们更可能是不断变化的：你会学习到新的知识，出现以前未预料到的用例，业务重点会改变，用户会要求新的功能，新平台会取代旧平台，法律或监管要求会改变，系统的增长会迫使架构发生改变，等等。

In terms of organizational processes, Agile working patterns provide a framework for adapting to change. The Agile community has also developed technical tools and patterns that are helpful when developing software in a frequently changing environment, such as test-driven development (TDD) and refactoring.

在组织流程方面，敏捷工作模式提供了一个适应变化的框架。敏捷社区还开发了技术工具和模式，在频繁变化的环境中开发软件非常有帮助，例如测试驱动开发（TDD）和重构。

Most discussions of these Agile techniques focus on a fairly small, local scale (a couple of source code files within the same application). In this book, we search for ways of increasing agility on the level of a larger data system, perhaps consisting of several different applications or services with different characteristics. For example, how would you “refactor” Twitter’s architecture for assembling home timelines ( “Describing Load” ) from approach 1 to approach 2?

大多数关于这些敏捷技术的讨论都聚焦于相当小的、局部的范围（同一应用程序中的几个源代码文件）。在本书中，我们寻求在更大的数据系统层面上增加敏捷性的方法，这些系统可能包括多个具有不同特点的应用程序或服务。例如，您将如何将 Twitter 的首页时间线组装架构（“描述负载”）从方法1改进到方法2？

The ease with which you can modify a data system, and adapt it to changing requirements, is closely linked to its simplicity and its abstractions: simple and easy-to-understand systems are usually easier to modify than complex ones. But since this is such an important idea, we will use a different word to refer to agility on a data system level: evolvability [ 34 ].

你能够轻松修改和适应不断变化的需求的数据系统的能力，与其简单性和抽象性密切相关：易于理解的简单系统通常比复杂系统更容易修改。但由于这是一个非常重要的想法，因此我们将使用一个不同的词来指代数据系统层面的敏捷性：可发展性[34]。

The Birth of NoSQL

Now, in the 2010s, NoSQL is the latest attempt to overthrow the relational model’s dominance. The name “NoSQL” is unfortunate, since it doesn’t actually refer to any particular technology—it was originally intended simply as a catchy Twitter hashtag for a meetup on open source, distributed, nonrelational databases in 2009 [ 3 ]. Nevertheless, the term struck a nerve and quickly spread through the web startup community and beyond. A number of interesting database systems are now associated with the #NoSQL hashtag, and it has been retroactively reinterpreted as Not Only SQL [ 4 ].

现在，在2010年代， NoSQL是最新的尝试，试图推翻关系模型的统治地位。由于最初它只是一个流行的 Twitter 标签，用于描述开放源代码、分布式和非关系型数据库的会议，因此“NoSQL”这个名称有些不幸。然而，这个术语引起了人们的注意，并很快在网络创业社区和其他领域传播开来。现在，一些有趣的数据库系统与 #NoSQL 标签相关联，并被重新解释为“Not Only SQL”。

There are several driving forces behind the adoption of NoSQL databases, including:

NoSQL数据库被采用的原因有几个驱动力，包括：

• A need for greater scalability than relational databases can easily achieve, including very large datasets or very high write throughput

  需要更大规模的可扩展性，超过关系数据库可以轻松实现的范围，包括非常大的数据集或非常高的写入吞吐量。

• A widespread preference for free and open source software over commercial database products

  使用免费和开放源码软件的普遍选择，胜过于商业数据库产品。

• Specialized query operations that are not well supported by the relational model

  不受关系模型很好支持的专业查询操作。

• Frustration with the restrictiveness of relational schemas, and a desire for a more dynamic and expressive data model [ 5 ]

  对关系模式限制性的挫败感，以及对更动态和富有表现力的数据模型的渴望。

Different applications have different requirements, and the best choice of technology for one use case may well be different from the best choice for another use case. It therefore seems likely that in the foreseeable future, relational databases will continue to be used alongside a broad variety of nonrelational datastores—an idea that is sometimes called polyglot persistence [ 3 ].

不同的应用有不同的需求，而一个用例的最佳技术选择可能与另一个用例的最佳选择不同。因此，有可能在可预见的未来，关系型数据库将继续与各种非关系型数据存储一起使用，这个想法有时被称为多语言持久性。

The Object-Relational Mismatch

Most application development today is done in object-oriented programming languages, which leads to a common criticism of the SQL data model: if data is stored in relational tables, an awkward translation layer is required between the objects in the application code and the database model of tables, rows, and columns. The disconnect between the models is sometimes called an impedance mismatch . ⁱ

如今，大多数应用程序开发都是使用面向对象的编程语言完成的，这导致了对 SQL 数据模型的普遍批评：如果数据存储在关系表中，则应用程序代码中的对象和基于表、行和列的数据库模型之间需要使用一种笨拙的翻译层来建立联系。这种模型之间的不连贯有时被称为阻抗不匹配。

Object-relational mapping (ORM) frameworks like ActiveRecord and Hibernate reduce the amount of boilerplate code required for this translation layer, but they can’t completely hide the differences between the two models.

对象关系映射（ORM）框架如ActiveRecord和Hibernate可减少翻译层所需的样板代码量，但它们无法完全隐藏两个模型之间的差异。

For example, Figure 2-1 illustrates how a résumé (a LinkedIn profile) could be expressed in a relational schema. The profile as a whole can be identified by a unique identifier, user_id . Fields like first_name and last_name appear exactly once per user, so they can be modeled as columns on the users table. However, most people have had more than one job in their career (positions), and people may have varying numbers of periods of education and any number of pieces of contact information. There is a one-to-many relationship from the user to these items, which can be represented in various ways:

例如，图2-1说明了如何将简历（LinkedIn个人资料）表达为关系模式。整个个人资料可以通过唯一标识符user_id进行识别。像first_name和last_name这样的字段每个用户只出现一次，因此它们可以被建模为用户表中的列。然而，大多数人在他们的职业生涯中都有过多个工作（职位），人们可能会有不同数量的教育期间和任何数量的联系方式。从用户到这些项目的关系是一对多的，可以用不同的方法来表示。

• In the traditional SQL model (prior to SQL:1999), the most common normalized representation is to put positions, education, and contact information in separate tables, with a foreign key reference to the users table, as in Figure 2-1 .

  在传统的SQL模型（SQL:1999之前），最常见的标准化表示法是将职位，教育和联系信息放置在单独的表中，并参照用户表进行外键引用，如图2-1。

• Later versions of the SQL standard added support for structured datatypes and XML data; this allowed multi-valued data to be stored within a single row, with support for querying and indexing inside those documents. These features are supported to varying degrees by Oracle, IBM DB2, MS SQL Server, and PostgreSQL [ 6 , 7 ]. A JSON datatype is also supported by several databases, including IBM DB2, MySQL, and PostgreSQL [ 8 ].

  SQL标准的更新版本支持结构化数据类型和XML数据；这使得可以将多值数据存储在单个行中，并支持在这些文档内进行查询和索引。这些功能在Oracle、IBM DB2、MS SQL Server和PostgreSQL [6、7]中的支持程度有所不同。JSON数据类型也被多个数据库支持，包括IBM DB2、MySQL和PostgreSQL [8]。

• A third option is to encode jobs, education, and contact info as a JSON or XML document, store it on a text column in the database, and let the application interpret its structure and content. In this setup, you typically cannot use the database to query for values inside that encoded column.

  第三个选项是将工作、教育和联系信息编码为JSON或XML文档，将其存储在数据库的文本列中，并让应用程序解释其结构和内容。在这种设置中，您通常无法使用数据库查询该编码列内部的值。

Figure 2-1. Representing a LinkedIn profile using a relational schema. Photo of Bill Gates courtesy of Wikimedia Commons, Ricardo Stuckert, Agência Brasil.

For a data structure like a résumé, which is mostly a self-contained document , a JSON representation can be quite appropriate: see Example 2-1 . JSON has the appeal of being much simpler than XML. Document-oriented databases like MongoDB [ 9 ], RethinkDB [ 10 ], CouchDB [ 11 ], and Espresso [ 12 ] support this data model.

对于像简历这样的数据结构，它主要是一个自包含的文档，JSON表示可以非常适合：参见例子2-1。JSON比XML简单得多，具有吸引力。文档导向型数据库，如MongoDB、RethinkDB、CouchDB和Espresso都支持这种数据模型。

{
  "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"
  }
}

Some developers feel that the JSON model reduces the impedance mismatch between the application code and the storage layer. However, as we shall see in Chapter 4 , there are also problems with JSON as a data encoding format. The lack of a schema is often cited as an advantage; we will discuss this in “Schema flexibility in the document model” .

一些开发人员认为，JSON模型减少了应用程序代码和存储层之间的阻抗失配。然而，正如我们将在第4章中看到的那样，JSON作为数据编码格式也存在问题。缺乏模式通常被引用作为优点;我们将在“文档模型中的模式灵活性”中讨论这个问题。

The JSON representation has better locality than the multi-table schema in Figure 2-1 . If you want to fetch a profile in the relational example, you need to either perform multiple queries (query each table by user_id ) or perform a messy multi-way join between the users table and its subordinate tables. In the JSON representation, all the relevant information is in one place, and one query is sufficient.

JSON表示法比2-1图中的多表模式具有更好的局部性。如果您想在关系示例中获取配置文件，您需要执行多个查询（通过user_id查询每个表）或在用户表及其从属表之间执行混乱的多向连接。在JSON表示法中，所有相关信息都在一个地方，只需要一次查询即可。

The one-to-many relationships from the user profile to the user’s positions, educational history, and contact information imply a tree structure in the data, and the JSON representation makes this tree structure explicit (see Figure 2-2 ).

用户档案与用户职位，教育历史和联系方式之间的一对多关系意味着数据中的树形结构，JSON表示明确了这种树形结构（请参见图2-2）。

Figure 2-2. One-to-many relationships forming a tree structure.

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

In Example 2-1 in the preceding section, region_id and industry_id are given as IDs, not as plain-text strings "Greater Seattle Area" and "Philanthropy" . Why?

为什么在前面的章节中的示例2-1中，region_id和industry_id是作为ID给出的，而不是作为纯文本字符串"Greater Seattle Area"和"Philanthropy"呢？

If the user interface has free-text fields for entering the region and the industry, it makes sense to store them as plain-text strings. But there are advantages to having standardized lists of geographic regions and industries, and letting users choose from a drop-down list or autocompleter:

如果用户界面有用于输入地区和行业的自由文本字段，则将它们存储为纯文本字符串是有意义的。但是，具有标准化的地理区域和行业列表，并让用户从下拉列表或自动完成器中选择是有优势的：

• Consistent style and spelling across profiles

  个人资料中风格和拼写要保持一致。

• Avoiding ambiguity (e.g., if there are several cities with the same name)

  避免歧义（例如，如果有几个同名城市）

• Ease of updating—the name is stored in only one place, so it is easy to update across the board if it ever needs to be changed (e.g., change of a city name due to political events)

  易于更新——名称只存储在一个地方，如果需要更改（例如，由于政治事件更改城市名称），则可以轻松在整个平台上进行更新。

• Localization support—when the site is translated into other languages, the standardized lists can be localized, so the region and industry can be displayed in the viewer’s language

  本地化支持-当网站翻译为其他语言时，标准化列表可以本地化，以便在观看者的语言中显示地区和行业。

• Better search—e.g., a search for philanthropists in the state of Washington can match this profile, because the list of regions can encode the fact that Seattle is in Washington (which is not apparent from the string "Greater Seattle Area" )

  更好的搜索-例如，在华盛顿州搜寻慈善家可以匹配此档案，因为地区列表可以编码西雅图是华盛顿州的事实（这一点在“大西雅图地区”这个字符串中不明显）。

Whether you store an ID or a text string is a question of duplication. When you use an ID, the information that is meaningful to humans (such as the word Philanthropy ) is stored in only one place, and everything that refers to it uses an ID (which only has meaning within the database). When you store the text directly, you are duplicating the human-meaningful information in every record that uses it.

无论你存储一个ID还是文本字符串，都是一个重复的问题。当你使用ID时，对于人类有意义的信息（例如“慈善”这个词）只存储在一个位置，而所有引用它的内容都使用ID（它只有在数据库中有意义）。当你直接存储文本时，你将在每个使用它的记录中复制人类有意义的信息。

The advantage of using an ID is that because it has no meaning to humans, it never needs to change: the ID can remain the same, even if the information it identifies changes. Anything that is meaningful to humans may need to change sometime in the future—and if that information is duplicated, all the redundant copies need to be updated. That incurs write overheads, and risks inconsistencies (where some copies of the information are updated but others aren’t). Removing such duplication is the key idea behind normalization in databases. ⁱⁱ

使用ID的优点在于，由于它对人类没有意义，所以它永远不需要更改：即使所识别的信息发生更改，ID仍然可以保持不变。对人类有意义的任何内容都可能在将来需要更改 - 如果该信息被复制，所有冗余副本都需要更新。这会增加写入开销，并存在不一致性的风险（其中一些信息的副本得到更新，但其他副本没有）。消除这种重复是数据库规范化的关键思想。

Unfortunately, normalizing this data requires many-to-one relationships (many people live in one particular region, many people work in one particular industry), which don’t fit nicely into the document model. In relational databases, it’s normal to refer to rows in other tables by ID, because joins are easy. In document databases, joins are not needed for one-to-many tree structures, and support for joins is often weak. ⁱⁱⁱ

不幸的是，将这些数据进行规范化需要多对一的关系（许多人居住在一个特定地区，许多人在一个特定行业工作），这些关系不适合文档模型。在关系数据库中，通常通过ID引用其他表中的行，因为连接很容易。在文档数据库中，连接不需要用于一对多树结构，并且对连接的支持通常较弱。

If the database itself does not support joins, you have to emulate a join in application code by making multiple queries to the database. (In this case, the lists of regions and industries are probably small and slow-changing enough that the application can simply keep them in memory. But nevertheless, the work of making the join is shifted from the database to the application code.)

如果数据库本身不支持连接，你需要在应用程序代码中通过对数据库进行多次查询来模拟连接。(在这种情况下，地区和行业列表可能很小且变化缓慢，应用程序可以将它们保留在内存中处理。但是，将连接的工作从数据库转移到应用程序代码。)

Moreover, even if the initial version of an application fits well in a join-free document model, data has a tendency of becoming more interconnected as features are added to applications. For example, consider some changes we could make to the résumé example:

此外，即使应用程序的初始版本适合无连接文档模型，随着功能的增加，数据往往会变得更加相互关联。例如，考虑以下我们可以对在线简历进行的更改：

Organizations and schools as entities

In the previous description, organization (the company where the user worked) and school_name (where they studied) are just strings. Perhaps they should be references to entities instead? Then each organization, school, or university could have its own web page (with logo, news feed, etc.); each résumé could link to the organizations and schools that it mentions, and include their logos and other information (see Figure 2-3 for an example from LinkedIn).

在先前的描述中，组织（用户所在的公司）和学校名称仅仅是字符串。也许它们应该是实体的引用？这样每个组织、学校或大学都可以有自己的网页（包含标志、新闻源等）。每份简历都可以链接到所提及的组织和学校，并包含它们的标志和其他信息（参见LinkedIn上的示例，如图2-3）。

Recommendations

Say you want to add a new feature: one user can write a recommendation for another user. The recommendation is shown on the résumé of the user who was recommended, together with the name and photo of the user making the recommendation. If the recommender updates their photo, any recommendations they have written need to reflect the new photo. Therefore, the recommendation should have a reference to the author’s profile.

假设你想添加一个新的功能：一位用户可以给另一位用户写一份推荐。这份推荐会显示在被推荐用户的个人简历上，同时还会附带推荐人的姓名和照片。如果推荐人更新了自己的照片，那么他所写的所有推荐都应该显示最新的照片。因此，推荐应该引用作者的个人资料。

Figure 2-3. The company name is not just a string, but a link to a company entity. Screenshot of linkedin.com.

Figure 2-4 illustrates how these new features require many-to-many relationships. The data within each dotted rectangle can be grouped into one document, but the references to organizations, schools, and other users need to be represented as references, and require joins when queried.

图2-4说明了这些新功能需要多对多的关系。每个虚线矩形中的数据可以分组成一个文档，但对组织、学校和其他用户的引用必须表示为引用，并在查询时需要连接。

Figure 2-4. Extending résumés with many-to-many relationships.

Are Document Databases Repeating History?

While many-to-many relationships and joins are routinely used in relational databases, document databases and NoSQL reopened the debate on how best to represent such relationships in a database. This debate is much older than NoSQL—in fact, it goes back to the very earliest computerized database systems.

尽管在关系型数据库中经常使用多对多关系和连接，但文档数据库和NoSQL重新打开了在数据库中表示这种关系的最佳方式的辩论。这个辩论比NoSQL要古老得多，实际上可以追溯到最早的计算机化数据库系统。

The most popular database for business data processing in the 1970s was IBM’s Information Management System (IMS), originally developed for stock-keeping in the Apollo space program and first commercially released in 1968 [ 13 ]. It is still in use and maintained today, running on OS/390 on IBM mainframes [ 14 ].

20世纪70年代，商业数据处理的最流行数据库是IBM的信息管理系统（IMS），最初为阿波罗航天计划的存货管理开发，于1968年首次商业发布[13]。它仍在使用和维护，运行在IBM主机的OS/390上[14]。

The design of IMS used a fairly simple data model called the hierarchical model , which has some remarkable similarities to the JSON model used by document databases [ 2 ]. It represented all data as a tree of records nested within records, much like the JSON structure of Figure 2-2 .

IMS的设计使用了一个相当简单的数据模型，称为分层模型，这与文档数据库使用的JSON模型有一些相似之处。它将所有数据表示为嵌套在记录中的记录树，就像图2-2中的JSON结构一样。

Like document databases, IMS worked well for one-to-many relationships, but it made many-to-many relationships difficult, and it didn’t support joins. Developers had to decide whether to duplicate (denormalize) data or to manually resolve references from one record to another. These problems of the 1960s and ’70s were very much like the problems that developers are running into with document databases today [ 15 ].

像文档数据库一样，IMS适用于一对多关系，但却使得多对多关系更加困难，并且不支持连接查询。开发者们不得不决定是复制（去规范化）数据还是手动解决从一个记录到另一个记录的引用。这些上世纪60年代和70年代的问题与今天开发者们在文档数据库中遇到的问题非常相似[15]。

Various solutions were proposed to solve the limitations of the hierarchical model. The two most prominent were the relational model (which became SQL, and took over the world) and the network model (which initially had a large following but eventually faded into obscurity). The “great debate” between these two camps lasted for much of the 1970s [ 2 ].

有许多解决分层模型限制的解决方案被提出。其中最著名的两个是关系模型（成为SQL并统治了世界）和网络模型（最初有很大的追随者，但最终逐渐被遗忘）。这两个阵营之间的“大辩论”持续了很长一段时间，一直到1970年代晚期。

Since the problem that the two models were solving is still so relevant today, it’s worth briefly revisiting this debate in today’s light.

由于两个模型所解决的问题仍然如此相关，因此在今天的光环下简要回顾这场争论是值得的。

Relational Versus Document Databases Today

There are many differences to consider when comparing relational databases to document databases, including their fault-tolerance properties (see Chapter 5 ) and handling of concurrency (see Chapter 7 ). In this chapter, we will concentrate only on the differences in the data model.

当比较关系型数据库和文档数据库时，需要考虑许多差异，包括它们的容错性质（见第五章）和并发处理（见第七章）。在本章中，我们将仅集中讨论数据模型的差异。

The main arguments in favor of the document data model are schema flexibility, better performance due to locality, and that for some applications it is closer to the data structures used by the application. The relational model counters by providing better support for joins, and many-to-one and many-to-many relationships.

文档数据模型的主要优点是模式灵活性、由于局部性能更好，某些应用程序更接近于数据结构。关系模型则通过提供更好的联接支持以及一对多和多对多关系来反驳这些优点。

if (user && user.name && !user.first_name) {
    // Documents written before Dec 8, 2013 don't have first_name
    user.first_name = user.name.split(" ")[0];
}

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

Declarative Queries on the Web

The advantages of declarative query languages are not limited to just databases. To illustrate the point, let’s compare declarative and imperative approaches in a completely different environment: a web browser.

声明式查询语言的优点不仅限于数据库。为了说明这一点，让我们比较声明式和命令式方法在一个完全不同的环境下：Web浏览器。

Say you have a website about animals in the ocean. The user is currently viewing the page on sharks, so you mark the navigation item “Sharks” as currently selected, like this:

假设你有一个关于海洋动物的网站。用户目前正在查看关于鲨鱼的页面，那么你可以将导航条目“鲨鱼”标记为当前选中状态，就像这样：

<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>

The selected item is marked with the CSS class "selected" .

所选择的项目带有CSS类“selected”。

<p>Sharks</p> is the title of the currently selected page.

当前选定页面的标题是“鲨鱼”。

Now say you want the title of the currently selected page to have a blue background, so that it is visually highlighted. This is easy, using CSS:

现在假设您想要当前选定页面的标题具有蓝色背景，以便在视觉上突出显示。使用 CSS 很容易实现：

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

Here the CSS selector li.selected > p declares the pattern of elements to which we want to apply the blue style: namely, all <p> elements whose direct parent is an <li> element with a CSS class of selected . The element <p>Sharks</p> in the example matches this pattern, but <p>Whales</p> does not match because its <li> parent lacks class="selected" .

此处 CSS 选择器 li.selected > p 声明我们要应用蓝色样式的元素模式：即所有直接父元素为 class="selected" 的 <li> 元素的 <p> 元素。在示例中，元素 <p>Sharks</p> 符合此模式，但 <p>Whales</p> 不符合，因为其 <li> 父元素缺少 class="selected"。

If you were using XSL instead of CSS, you could do something similar:

如果你使用XSL而不是CSS，你可以做类似的事情：

<xsl:template match="li[@class='selected']/p">
    <fo:block background-color="blue">
        <xsl:apply-templates/>
    </fo:block>
</xsl:template>

Here, the XPath expression li[@class='selected']/p is equivalent to the CSS selector li.selected > p in the previous example. What CSS and XSL have in common is that they are both declarative languages for specifying the styling of a document.

这里，XPath表达式li[@class='selected']/p相当于前面例子中的CSS选择器li.selected > p。CSS和XSL的共同点在于它们都是用于指定文档样式的声明性语言。

Imagine what life would be like if you had to use an imperative approach. In JavaScript, using the core Document Object Model (DOM) API, the result might look something like this:

想象一下，如果你必须使用命令式方法来生活会是什么样子。在 JavaScript 中，使用核心文档对象模型 (DOM) API，结果可能看起来像这样:

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");
            }
        }
    }
}

This JavaScript imperatively sets the element <p>Sharks</p> to have a blue background, but the code is awful. Not only is it much longer and harder to understand than the CSS and XSL equivalents, but it also has some serious problems:

这个JavaScript命令式地将元素<p>鲨鱼</p>的背景设为蓝色，但代码十分糟糕。它不仅比CSS和XSL等价物更长，更难理解，而且还有一些严重的问题：

• If the selected class is removed (e.g., because the user clicks a different page), the blue color won’t be removed, even if the code is rerun—and so the item will remain highlighted until the entire page is reloaded. With CSS, the browser automatically detects when the li.selected > p rule no longer applies and removes the blue background as soon as the selected class is removed.

  如果所选的类别被删除（例如，因为用户点击了不同的页面），即使重新运行代码，蓝色也不会删除，因此该项将保持突出显示，直到整个页面重新加载。使用CSS，浏览器会自动检测li.selected > p规则不再适用并在移除所选类别时立即删除蓝色背景。

• If you want to take advantage of a new API, such as document.getElementsByClassName("selected") or even document.evaluate() —which may improve performance—you have to rewrite the code. On the other hand, browser vendors can improve the performance of CSS and XPath without breaking compatibility.

  如果您想利用新API，例如document.getElementsByClassName（“selected”）或document.evaluate（），可能会提高性能，那么您必须重新编写代码。另一方面，浏览器厂商可以提高CSS和XPath的性能，而不会破坏兼容性。 如果想利用新的 API，比如document.getElementsByClassName("selected")，甚至是document.evaluate()——这些可能会提升性能——那么就必须重新编写代码。另一方面，浏览器厂商可以提升CSS和XPath的性能，而不毁于兼容性。

In a web browser, using declarative CSS styling is much better than manipulating styles imperatively in JavaScript. Similarly, in databases, declarative query languages like SQL turned out to be much better than imperative query APIs. ^vi

在Web浏览器中，使用声明性CSS样式比在JavaScript中使用命令式样式要好得多。同样，在数据库中，声明性查询语言例如SQL被证明比命令式查询API更好用。

MapReduce Querying

MapReduce is a programming model for processing large amounts of data in bulk across many machines, popularized by Google [ 33 ]. A limited form of MapReduce is supported by some NoSQL datastores, including MongoDB and CouchDB, as a mechanism for performing read-only queries across many documents.

MapReduce是一种编程模型，用于在许多计算机上批量处理大量数据，由Google流行化[33]。一些NoSQL数据存储支持MapReduce的有限形式，包括MongoDB和CouchDB，作为在许多文档上执行只读查询的机制。

MapReduce in general is described in more detail in Chapter 10 . For now, we’ll just briefly discuss MongoDB’s use of the model.

总体上说，MapReduce在第10章中有更详细的描述。现在，我们只是简要讨论MongoDB使用该模型的情况。

MapReduce is neither a declarative query language nor a fully imperative query API, but somewhere in between: the logic of the query is expressed with snippets of code, which are called repeatedly by the processing framework. It is based on the map (also known as collect ) and reduce (also known as fold or inject ) functions that exist in many functional programming languages.

MapReduce不是声明性查询语言也不是完全的命令式查询API，而是介于两者之间：查询逻辑用代码片段表达，这些代码片段在处理框架中被重复调用。它基于在许多功能编程语言中存在的map（也称为collect）和reduce（也称为fold或inject）函数。

To give an example, imagine you are a marine biologist, and you add an observation record to your database every time you see animals in the ocean. Now you want to generate a report saying how many sharks you have sighted per month.

举个例子，比如你是一位海洋生物学家，每当你在海洋中看到动物时，你都会添加一条观察记录到你的数据库中。现在你想生成一份报告，说明每个月你观察到了多少只鲨鱼。

In PostgreSQL you might express that query like this:

在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;

The date_trunc('month', timestamp) function determines the calendar month containing timestamp , and returns another timestamp representing the beginning of that month. In other words, it rounds a timestamp down to the nearest month.

"date_trunc('month', timestamp)"函数确定包含时间戳的日历月份，并返回表示该月份开头的另一个时间戳。换句话说，它将时间戳向下舍入到最近的月份。

This query first filters the observations to only show species in the Sharks family, then groups the observations by the calendar month in which they occurred, and finally adds up the number of animals seen in all observations in that month.

该查询首先按照“鲨鱼”物种筛选观察记录，然后按照所发生的日历月份对观测进行分组，最后计算该月份所有观测中看到的动物数量。

The same can be expressed with MongoDB’s MapReduce feature as follows:

可以使用MongoDB的MapReduce功能以如下方式表达相同的内容：

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" 
    }
);

The filter to consider only shark species can be specified declaratively (this is a MongoDB-specific extension to MapReduce).

可以通过声明性的方式指定只考虑鲨鱼物种的过滤器（这是MongoDB特有的MapReduce扩展功能）。

The JavaScript function map is called once for every document that matches query , with this set to the document object.

JavaScript 函数map会针对每个与查询匹配的文档调用一次，将this设置为文档对象。

The map function emits a key (a string consisting of year and month, such as "2013-12" or "2014-1" ) and a value (the number of animals in that observation).

“map”函数发射一个键（由年份和月份组成的字符串，如“2013-12”或“2014-1”）和一个值（观察中动物的数量）。

The key-value pairs emitted by map are grouped by key. For all key-value pairs with the same key (i.e., the same month and year), the reduce function is called once.

map 发出的键值对根据键分组。对于所有具有相同键（即相同的月份和年份）的键值对，会调用一次 reduce 函数。

The reduce function adds up the number of animals from all observations in a particular month.

"reduce函数将特定月份内所有观察结果的动物数量相加。"

The final output is written to the collection monthlySharkReport .

最终输出将被写入集合monthlySharkReport。

For example, say the observations collection contains these two documents:

例如，假设观察集合包含以下两个文档：

{
    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
}

The map function would be called once for each document, resulting in emit("1995-12", 3) and emit("1995-12", 4) . Subsequently, the reduce function would be called with reduce("1995-12", [3, 4]) , returning 7 .

“map”函数将针对每个文档调用一次，导致“emit（“1995-12”，3）”和“emit（“1995-12”，4）” 。随后，reduce函数将使用reduce（“1995-12”，[3,4]）进行调用，返回7。

The map and reduce functions are somewhat restricted in what they are allowed to do. They must be pure functions, which means they only use the data that is passed to them as input, they cannot perform additional database queries, and they must not have any side effects. These restrictions allow the database to run the functions anywhere, in any order, and rerun them on failure. However, they are nevertheless powerful: they can parse strings, call library functions, perform calculations, and more.

映射和归约函数在其允许执行的操作上有一定的限制。它们必须是纯函数，这意味着它们只能使用作为输入传递给它们的数据，不能执行额外的数据库查询，也不能产生任何副作用。这些限制使得数据库可以在任何地方以任何顺序运行这些函数，并在失败时重新运行它们。然而，它们仍然非常强大：它们可以解析字符串、调用库函数、执行计算等等。

MapReduce is a fairly low-level programming model for distributed execution on a cluster of machines. Higher-level query languages like SQL can be implemented as a pipeline of MapReduce operations (see Chapter 10 ), but there are also many distributed implementations of SQL that don’t use MapReduce. Note there is nothing in SQL that constrains it to running on a single machine, and MapReduce doesn’t have a monopoly on distributed query execution.

MapReduce是一个基于集群机器分布式执行的相对较低级的编程模型。高级查询语言如SQL可以作为MapReduce操作的流水线来实现（见第10章），但也有许多分布式的SQL实现不使用MapReduce。需要注意的是，SQL并不局限于单机运行，而MapReduce也不是唯一的分布式查询执行方案。

Being able to use JavaScript code in the middle of a query is a great feature for advanced queries, but it’s not limited to MapReduce—some SQL databases can be extended with JavaScript functions too [ 34 ].

JavaScript代码在查询过程中的使用是高级查询的重要功能，但它并不局限于MapReduce—某些SQL数据库也可以使用JavaScript函数扩展。[34]。

A usability problem with MapReduce is that you have to write two carefully coordinated JavaScript functions, which is often harder than writing a single query. Moreover, a declarative query language offers more opportunities for a query optimizer to improve the performance of a query. For these reasons, MongoDB 2.2 added support for a declarative query language called the aggregation pipeline [ 9 ]. In this language, the same shark-counting query looks like this:

MapReduce存在的一个可用性问题是你需要编写两个精心协调的JavaScript函数，通常比编写单个查询更困难。此外，声明性查询语言提供了更多的机会让查询优化器提高查询性能。出于这些原因，MongoDB 2.2添加了支持称为聚合管道的声明性查询语言[9]。在这种语言中，同样的鲨鱼计数查询看起来像这样：

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

The aggregation pipeline language is similar in expressiveness to a subset of SQL, but it uses a JSON-based syntax rather than SQL’s English-sentence-style syntax; the difference is perhaps a matter of taste. The moral of the story is that a NoSQL system may find itself accidentally reinventing SQL, albeit in disguise.

聚合管道语言在表达能力上与 SQL 的子集类似，但它使用基于 JSON 的语法，而不是 SQL 的英语句子样式语法；这种差异可能只是口味问题。故事的道德是，NoSQL 系统可能会意外地重新发明 SQL，尽管是伪装的。

Property Graphs

In the property graph model, each vertex consists of:

在属性图模型中，每个顶点由以下内容组成：

• A unique identifier

  一个唯一标识符

• A set of outgoing edges

  出边集合

• A set of incoming edges

  一组入边

• A collection of properties (key-value pairs)

  一组属性（键值对）

Each edge consists of:

每个边缘由：

• A unique identifier

  一个唯一标识符

• The vertex at which the edge starts (the tail vertex )

  边起始的顶点（尾部顶点）

• The vertex at which the edge ends (the head vertex )

  边缘的终点顶点（头顶点）。

• A label to describe the kind of relationship between the two vertices

  两个各自描述不同的实体之间关系类型的标签。

• A collection of properties (key-value pairs)

  一组属性（键值对）

You can think of a graph store as consisting of two relational tables, one for vertices and one for edges, as shown in Example 2-2 (this schema uses the PostgreSQL json datatype to store the properties of each vertex or edge). The head and tail vertex are stored for each edge; if you want the set of incoming or outgoing edges for a vertex, you can query the edges table by head_vertex or tail_vertex , respectively.

你可以将图存储视为由两个关系表组成，一个存储顶点，另一个存储边，如示例2-2所示（此架构使用PostgreSQL json数据类型来存储每个顶点或边的属性）。每个边都存储头部和尾部顶点；如果您想要一个顶点的传入或传出边的集合，则可以分别通过head_vertex或tail_vertex查询edges表。

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);

Some important aspects of this model are:

这个模型的一些重要方面是：

1. Any vertex can have an edge connecting it with any other vertex. There is no schema that restricts which kinds of things can or cannot be associated.

   任何顶点都可以与任何其他顶点连接一条边。没有任何模式限制哪些物品可以或不能关联。

2. Given any vertex, you can efficiently find both its incoming and its outgoing edges, and thus traverse the graph—i.e., follow a path through a chain of vertices—both forward and backward. (That’s why Example 2-2 has indexes on both the tail_vertex and head_vertex columns.)

   给定任何一个顶点，你可以高效地找到它的入边和出边，从而可以在图中遍历，即沿着顶点链条向前和向后走。（这就是为什么示例2-2在tail_vertex和head_vertex列上都有索引的原因。）

3. By using different labels for different kinds of relationships, you can store several different kinds of information in a single graph, while still maintaining a clean data model.

   通过为不同类型的关系使用不同的标签，您可以在单个图中存储多种不同类型的信息，同时仍然保持清晰的数据模型。

Those features give graphs a great deal of flexibility for data modeling, as illustrated in Figure 2-5 . The figure shows a few things that would be difficult to express in a traditional relational schema, such as different kinds of regional structures in different countries (France has départements and régions , whereas the US has counties and states ), quirks of history such as a country within a country (ignoring for now the intricacies of sovereign states and nations), and varying granularity of data (Lucy’s current residence is specified as a city, whereas her place of birth is specified only at the level of a state).

这些特性赋予图形数据建模以极大的灵活性，如图2-5所示。该图显示了一些传统关系模式难以表达的东西，例如不同国家的不同地区结构（法国有départements和régions，而美国有郡和州），历史上的奇怪现象，如国家内的国家（暂时忽略主权国家和民族的复杂性），以及数据的变化粒度（Lucy的目前居住地指定为城市，而她的出生地仅在州一级指定）。

You could imagine extending the graph to also include many other facts about Lucy and Alain, or other people. For instance, you could use it to indicate any food allergies they have (by introducing a vertex for each allergen, and an edge between a person and an allergen to indicate an allergy), and link the allergens with a set of vertices that show which foods contain which substances. Then you could write a query to find out what is safe for each person to eat. Graphs are good for evolvability: as you add features to your application, a graph can easily be extended to accommodate changes in your application’s data structures.

你可以想象将该图扩展以包括有关Lucy和Alain或其他人的许多其他事实。例如，您可以使用它来指示他们有哪些食物过敏症（通过为每种过敏原引入一个顶点，并在人和过敏原之间添加一条边来表示过敏症），并使用一组显示哪些食物含有哪些物质的顶点将过敏原连接起来。然后，您可以编写查询以查找每个人可以安全食用的食物。 图表很适合扩展性：随着您向应用程序添加功能，图表可以轻松扩展以适应应用程序数据结构的变化。

The Cypher Query Language

Cypher is a declarative query language for property graphs, created for the Neo4j graph database [ 37 ]. (It is named after a character in the movie The Matrix and is not related to ciphers in cryptography [ 38 ].)

Cypher是一种面向属性图的声明式查询语言，为Neo4j图数据库创建[37]。 (它的名字来源于电影《黑客帝国》中的一个角色，并与密码学中的加密术语[38]无关。)

Example 2-3 shows the Cypher query to insert the lefthand portion of Figure 2-5 into a graph database. The rest of the graph can be added similarly and is omitted for readability. Each vertex is given a symbolic name like USA or Idaho , and other parts of the query can use those names to create edges between the vertices, using an arrow notation: (Idaho) -[:WITHIN]-> (USA) creates an edge labeled WITHIN , with Idaho as the tail node and USA as the head node.

示例2-3展示了将图2-5左侧部分插入图形数据库的Cypher查询。图中其他部分可以类似地添加，为了便于阅读而被省略。每个顶点都被赋予一个象征性的名称，例如美国或爱达荷，查询的其他部分可以使用这些名称来创建顶点之间的边，使用箭头符号：“（爱达荷）-[:WITHIN]->（美国）”创建了一个标记为WITHIN的边，其中爱达荷作为尾部节点，美国作为头节点。

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)

When all the vertices and edges of Figure 2-5 are added to the database, we can start asking interesting questions: for example, find the names of all the people who emigrated from the United States to Europe . To be more precise, here we want to find all the vertices that have a BORN_IN edge to a location within the US, and also a LIVING_IN edge to a location within Europe, and return the name property of each of those vertices.

当图2-5的所有顶点和边被添加到数据库后，我们可以开始提出有趣的问题：例如，查找所有从美国移民到欧洲的人的名字。 更准确地说，我们要找到所有顶点，它们具有一条指向美国境内位置的BORN_IN边和一条指向欧洲境内位置的LIVING_IN边，并返回每个该顶点的名称属性。

Example 2-4 shows how to express that query in Cypher. The same arrow notation is used in a MATCH clause to find patterns in the graph: (person) -[:BORN_IN]-> () matches any two vertices that are related by an edge labeled BORN_IN . The tail vertex of that edge is bound to the variable person , and the head vertex is left unnamed.

例2-4展示了如何用Cypher表达该查询。在MATCH子句中使用相同的箭头符号来查找图中的模式：（person）- [：BORN_IN] - >（）匹配通过标记为BORN_IN的边缘相关的任意两个顶点。该边的尾顶点绑定到变量person，而头顶点则未命名。

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

The query can be read as follows:

该查询可以理解为:

Find any vertex (call it person ) that meets both of the following conditions:

寻找符合以下两个条件的任何顶点（称之为个人）：

1. person has an outgoing BORN_IN edge to some vertex. From that vertex, you can follow a chain of outgoing WITHIN edges until eventually you reach a vertex of type Location , whose name property is equal to "United States" .

   某人将BORN_IN出边传递到某个顶点。从该顶点出发，您可以沿着输出WITHIN边的链，直到最终到达类型为“Location”的顶点，其名称属性等于“美国”。

2. That same person vertex also has an outgoing LIVES_IN edge. Following that edge, and then a chain of outgoing WITHIN edges, you eventually reach a vertex of type Location , whose name property is equal to "Europe" .

   同样的顶点还具有一个向外的“居住于”边。沿着那条边，然后是一系列的向外的“位于”边，你最终会到达一个类型为位置的顶点，其名称属性等于“欧洲”。

For each such person vertex, return the name property.

对于每个这样的人顶点，返回名称属性。

There are several possible ways of executing the query. The description given here suggests that you start by scanning all the people in the database, examine each person’s birthplace and residence, and return only those people who meet the criteria.

有几种可能的执行查询的方式。这里给出的描述建议您首先扫描数据库中的所有人员，检查每个人的出生地和居住地，只返回符合条件的人员。

But equivalently, you could start with the two Location vertices and work backward. If there is an index on the name property, you can probably efficiently find the two vertices representing the US and Europe. Then you can proceed to find all locations (states, regions, cities, etc.) in the US and Europe respectively by following all incoming WITHIN edges. Finally, you can look for people who can be found through an incoming BORN_IN or LIVES_IN edge at one of the location vertices.

然而同等地，你也可以从两个位置顶点开始向后推导。如果名称属性上有索引，你可能可以有效地找到代表美国和欧洲的两个顶点。然后，你可以通过跟随所有传入的WITHIN边缘，分别找到美国和欧洲的所有位置（州，地区，城市等）。最后，你可以在位置顶点之一通过传入的BORN_IN或LIVES_IN边缘查找可以找到的人。

As is typical for a declarative query language, you don’t need to specify such execution details when writing the query: the query optimizer automatically chooses the strategy that is predicted to be the most efficient, so you can get on with writing the rest of your application.

作为声明式查询语言的典型特点，写查询时无需指定执行细节：查询优化器会自动选择预测为最有效的策略，因此您可以继续编写应用程序的其他部分。

Graph Queries in SQL

Example 2-2 suggested that graph data can be represented in a relational database. But if we put graph data in a relational structure, can we also query it using SQL?

示例2-2指出图形数据可以在关系型数据库中表示。但是如果将图形数据放入关系结构中，我们是否也可以使用SQL查询它？

The answer is yes, but with some difficulty. In a relational database, you usually know in advance which joins you need in your query. In a graph query, you may need to traverse a variable number of edges before you find the vertex you’re looking for—that is, the number of joins is not fixed in advance.

答案是肯定的，但需要一些困难。在关系数据库中，你通常已经知道了你查询需要哪些连接。而在图形查询中，你可能需要遍历不同数量的边缘，才能找到你想要的顶点——也就是说，连接的数量在事先是不固定的。

In our example, that happens in the () -[:WITHIN*0..]-> () rule in the Cypher query. A person’s LIVES_IN edge may point at any kind of location: a street, a city, a district, a region, a state, etc. A city may be WITHIN a region, a region WITHIN a state, a state WITHIN a country, etc. The LIVES_IN edge may point directly at the location vertex you’re looking for, or it may be several levels removed in the location hierarchy.

在我们的示例中，这发生在Cypher查询中的()-[:WITHIN*0..]->()规则中。一个人的“居住在”边缘可能指向任何类型的位置：一条街道，一个城市，一个区域，一个地区，一个州等等。一个城市可能在一个地区内，在一个地区内在一个州内，在一个州内在一个国家内等等。 “居住在”边缘可以直接指向您正在查找的位置顶点，也可以在位置层次结构中被移除数个级别。

In Cypher, :WITHIN*0.. expresses that fact very concisely: it means “follow a WITHIN edge, zero or more times.” It is like the * operator in a regular expression.

在密码中，:WITHIN*0..表达了这个事实非常简洁：它的意思是“遵循一个WITHIN边缘，零次或多次。” 就像正则表达式中的*操作符一样。

Since SQL:1999, this idea of variable-length traversal paths in a query can be expressed using something called recursive common table expressions (the WITH RECURSIVE syntax). Example 2-5 shows the same query—finding the names of people who emigrated from the US to Europe—expressed in SQL using this technique (supported in PostgreSQL, IBM DB2, Oracle, and SQL Server). However, the syntax is very clumsy in comparison to Cypher.

自从1999年的SQL版本开始，可以使用称为“带递归的公共表达式”（WITH RECURSIVE语法）的东西来表达查询中的可变长度遍历路径这个思想。例如，示例2-5展示了通过使用这种技术（在PostgreSQL、IBM DB2、Oracle和SQL Server中支持）表达的查询——找到移民从美国到欧洲的人的姓名。但是，与Cypher相比，语法非常笨拙。

WITH RECURSIVE

  -- in_usa is the set of vertex IDs of all locations within the United States
  in_usa(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'United States' 
    UNION
      SELECT edges.tail_vertex FROM edges 
        JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
        WHERE edges.label = 'within'
  ),

  -- in_europe is the set of vertex IDs of all locations within Europe
  in_europe(vertex_id) AS (
      SELECT vertex_id FROM vertices WHERE properties->>'name' = 'Europe' 
    UNION
      SELECT edges.tail_vertex FROM edges
        JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
        WHERE edges.label = 'within'
  ),

  -- born_in_usa is the set of vertex IDs of all people born in the US
  born_in_usa(vertex_id) AS ( 
    SELECT edges.tail_vertex FROM edges
      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
      WHERE edges.label = 'born_in'
  ),

  -- lives_in_europe is the set of vertex IDs of all people living in Europe
  lives_in_europe(vertex_id) AS ( 
    SELECT edges.tail_vertex FROM edges
      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
      WHERE edges.label = 'lives_in'
  )

SELECT vertices.properties->>'name'
FROM vertices
-- join to find those people who were both born in the US *and* live in Europe
JOIN born_in_usa     ON vertices.vertex_id = born_in_usa.vertex_id 
JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

If the same query can be written in 4 lines in one query language but requires 29 lines in another, that just shows that different data models are designed to satisfy different use cases. It’s important to pick a data model that is suitable for your application.

如果同样的查询在一种查询语言中可以写成4行，而在另一种语言中需要29行，那只说明不同的数据模型是为满足不同的用例而设计的。选择适合您应用的数据模型非常重要。

Triple-Stores and SPARQL

The triple-store model is mostly equivalent to the property graph model, using different words to describe the same ideas. It is nevertheless worth discussing, because there are various tools and languages for triple-stores that can be valuable additions to your toolbox for building applications.

三元组模型基本上等同于财产图模型，只是使用不同的词语来描述相同的思想。然而，这值得讨论，因为有各种工具和语言可以用于三元组存储，这些都可以成为构建应用程序工具箱中有价值的补充。

In a triple-store, all information is stored in the form of very simple three-part statements: ( subject , predicate , object ). For example, in the triple ( Jim , likes , bananas ), Jim is the subject, likes is the predicate (verb), and bananas is the object.

在三元组存储中，所有信息都以非常简单的三部分语句（主语，谓语，宾语）的形式存储。例如，在三元组（Jim，likes，bananas）中，Jim是主语，likes是谓语（动词），bananas是宾语。

The subject of a triple is equivalent to a vertex in a graph. The object is one of two things:

一个三元组的主语相当于图中的一个顶点。宾语则是两种情况之一：

1. A value in a primitive datatype, such as a string or a number. In that case, the predicate and object of the triple are equivalent to the key and value of a property on the subject vertex. For example, ( lucy , age , 33 ) is like a vertex lucy with properties {"age":33} .

   简化版： 一个原始数据类型的值，例如字符串或数字。在这种情况下，三元组的谓词和对象等同于主题顶点上属性的键和值。例如，（卢西，年龄，33）就像一个具有属性{"age":33}的顶点卢西。

2. Another vertex in the graph. In that case, the predicate is an edge in the graph, the subject is the tail vertex, and the object is the head vertex. For example, in ( lucy , marriedTo , alain ) the subject and object lucy and alain are both vertices, and the predicate marriedTo is the label of the edge that connects them.

   图形中的另一个顶点。在这种情况下，谓词是图形中的一条边，主语是尾顶点，宾语是头顶点。例如，在(lucy，marriedTo，alain)中，主语和宾语lucy和alain都是顶点，谓词marriedTo是连接它们的边的标签。

Example 2-6 shows the same data as in Example 2-3 , written as triples in a format called Turtle , a subset of Notation3 ( N3 ) [ 39 ].

示例2-6展示了与示例2-3相同的数据，以称为Turtle的格式编写的三元组的形式表示，它是Notation3（N3）的子集。[39]。

@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".

In this example, vertices of the graph are written as _: someName . The name doesn’t mean anything outside of this file; it exists only because we otherwise wouldn’t know which triples refer to the same vertex. When the predicate represents an edge, the object is a vertex, as in _:idaho :within _:usa . When the predicate is a property, the object is a string literal, as in _:usa :name "United States" .

在这个例子中，图形的顶点被写成_:someName。这个名字并没有任何意义，存在的唯一目的是因为我们不知道哪些三元组引用同一个顶点。当谓词表示边时，对象是顶点，例如_:idaho :within _:usa。当谓词是属性时，对象是一个字符串文字，例如_:usa :name "United States"。

It’s quite repetitive to repeat the same subject over and over again, but fortunately you can use semicolons to say multiple things about the same subject. This makes the Turtle format quite nice and readable: see Example 2-7 .

重复地反复讲同一个主题相当乏味，但幸运的是，你可以使用分号来表达关于同一个主题的多个事情。这使得Turtle格式非常好读：见示例2-7。

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

<rdf:RDF xmlns="urn:example:"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">

  <Location rdf:nodeID="idaho">
    <name>Idaho</name>
    <type>state</type>
    <within>
      <Location rdf:nodeID="usa">
        <name>United States</name>
        <type>country</type>
        <within>
          <Location rdf:nodeID="namerica">
            <name>North America</name>
            <type>continent</type>
          </Location>
        </within>
      </Location>
    </within>
  </Location>

  <Person rdf:nodeID="lucy">
    <name>Lucy</name>
    <bornIn rdf:nodeID="idaho"/>
  </Person>
</rdf:RDF>

PREFIX : <urn:example:>

SELECT ?personName WHERE {
  ?person :name ?personName.
  ?person :bornIn  / :within* / :name "United States".
  ?person :livesIn / :within* / :name "Europe".
}

(person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (location)   # Cypher

?person :bornIn / :within* ?location.                   # SPARQL

(usa {name:'United States'})   # Cypher

?usa :name "United States".    # SPARQL

The Foundation: Datalog

Datalog is a much older language than SPARQL or Cypher, having been studied extensively by academics in the 1980s [ 44 , 45 , 46 ]. It is less well known among software engineers, but it is nevertheless important, because it provides the foundation that later query languages build upon.

Datalog比SPARQL或Cypher语言更为古老，已经在20世纪80年代被学者广泛研究过。虽然在软件工程师中不是很知名，但它仍然非常重要，因为后来的查询语言都建立在它的基础上。

In practice, Datalog is used in a few data systems: for example, it is the query language of Datomic [ 40 ], and Cascalog [ 47 ] is a Datalog implementation for querying large datasets in Hadoop. ^viii

在实践中，Datalog 在一些数据系统中使用：例如，它是 Datomic 的查询语言 [40]，Cascalog是一个用于在 Hadoop 中查询大数据集的 Datalog 实现 [47]。

Datalog’s data model is similar to the triple-store model, generalized a bit. Instead of writing a triple as ( subject , predicate , object ), we write it as predicate ( subject , object ). Example 2-10 shows how to write the data from our example in Datalog.

Datalog的数据模型类似于三元组存储模型，但稍微推广一下。我们将三元组的写法 (主语，谓语，宾语) 转换成谓语(主语，宾语)的形式。例如，示例 2-10 展示了如何在 Datalog 中写入我们示例中的数据。

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).

Now that we have defined the data, we can write the same query as before, as shown in Example 2-11 . It looks a bit different from the equivalent in Cypher or SPARQL, but don’t let that put you off. Datalog is a subset of Prolog, which you might have seen before if you’ve studied computer science.

现在我们已经定义了数据，我们可以像示例2-11那样编写与之前相同的查询。它看起来与Cypher或SPARQL中的等效语句有些不同，但不要让它吓到你。Datalog是Prolog的一个子集，如果你学过计算机科学，可能已经见过它了。

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 and SPARQL jump in right away with SELECT , but Datalog takes a small step at a time. We define rules that tell the database about new predicates: here, we define two new predicates, within_recursive and migrated . These predicates aren’t triples stored in the database, but instead they are derived from data or from other rules. Rules can refer to other rules, just like functions can call other functions or recursively call themselves. Like this, complex queries can be built up a small piece at a time.

Cypher和SPARQL会立即使用SELECT，但Datalog会逐步迈出小步。我们定义规则来告诉数据库新谓词的存在：在这里，我们定义了两个新谓词，within_recursive和migrated。这些谓词不是存储在数据库中的三元组，而是从数据或其他规则派生出来的。规则可以引用其他规则，就像函数可以调用其他函数或递归调用自己一样。通过这种方式，可以逐步构建复杂的查询。

In rules, words that start with an uppercase letter are variables, and predicates are matched like in Cypher and SPARQL. For example, name(Location, Name) matches the triple name(namerica, 'North America') with variable bindings Location = namerica and Name = 'North America' .

规则中，以大写字母开头的单词是变量，谓词的匹配方式类似于Cypher和SPARQL。例如，name(Location，Name)与三元组name(namerica，'North America')匹配，绑定变量为Location = namerica和Name ='North America'。

A rule applies if the system can find a match for all predicates on the righthand side of the :- operator. When the rule applies, it’s as though the lefthand side of the :- was added to the database (with variables replaced by the values they matched).

当系统可以在“：-”运算符的右侧找到所有谓词的匹配时，规则适用。当规则适用时，就好像“：-”的左侧已被添加到数据库中（变量被匹配的值替换）。

One possible way of applying the rules is thus:

一种可能的规则应用方式如下：

1. name(namerica, 'North America') exists in the database, so rule 1 applies. It generates within_recursive(namerica, 'North America') .

   名称(name) (namerica, '北美洲') 在数据库中已存在，因此规则1适用。它生成within_recursive(namerica, '北美洲')。

2. within(usa, namerica) exists in the database and the previous step generated within_recursive(namerica, 'North America') , so rule 2 applies. It generates within_recursive(usa, 'North America') .

   在数据库中存在 `within(usa, namerica)`，并且之前一步生成了 `within_recursive(namerica, 'North America')`，因此应用了规则 2。它生成了 `within_recursive(usa, 'North America')`。

3. within(idaho, usa) exists in the database and the previous step generated within_recursive(usa, 'North America') , so rule 2 applies. It generates within_recursive(idaho, 'North America') .

   在数据库中存在位于美国爱达荷州的数据，并且之前的步骤生成了within_recursive(美国, '北美洲')，因此规则2适用。它会生成within_recursive(爱达荷州, '北美洲')。

By repeated application of rules 1 and 2, the within_recursive predicate can tell us all the locations in North America (or any other location name) contained in our database. This process is illustrated in Figure 2-6 .

通过反复应用规则1和规则2，within_recursive谓词可以告诉我们所有在我们数据库中包含的北美（或任何其他位置名称）的位置。该过程在图2-6中说明。

Figure 2-6. Determining that Idaho is in North America, using the Datalog rules from Example 2-11 .

Now rule 3 can find people who were born in some location BornIn and live in some location LivingIn . By querying with BornIn = 'United States' and LivingIn = 'Europe' , and leaving the person as a variable Who , we ask the Datalog system to find out which values can appear for the variable Who . So, finally we get the same answer as in the earlier Cypher and SPARQL queries.

现在规则3可以查找出生在BornIn某地并住在LivingIn某地的人。通过查询BornIn = 'United States'和LivingIn = 'Europe'，并将人作为变量Who，我们要求Datalog系统查找哪些值可以出现在变量Who中。因此，最终我们得到与早期Cypher和SPARQL查询相同的答案。

The Datalog approach requires a different kind of thinking to the other query languages discussed in this chapter, but it’s a very powerful approach, because rules can be combined and reused in different queries. It’s less convenient for simple one-off queries, but it can cope better if your data is complex.

Datalog方法需要与本章中讨论的其他查询语言不同的思维方式，但它是一种非常强大的方法，因为规则可以在不同的查询中组合和重复使用。对于简单的一次性查询来说可能不太方便，但如果你的数据较为复杂，它处理起来更加从容。

Hash Indexes

Let’s start with indexes for key-value data. This is not the only kind of data you can index, but it’s very common, and it’s a useful building block for more complex indexes.

让我们从键值数据的索引开始。这不是你可以索引的唯一类型，但是它非常常见，是更复杂索引的有用基石。

Key-value stores are quite similar to the dictionary type that you can find in most programming languages, and which is usually implemented as a hash map (hash table). Hash maps are described in many algorithms textbooks [ 1 , 2 ], so we won’t go into detail of how they work here. Since we already have hash maps for our in-memory data structures, why not use them to index our data on disk?

键值存储与大多数编程语言中的字典类型非常类似，通常实现为哈希表。哈希映射可以在许多算法教材中找到描述。既然我们已经在内存数据结构中使用了哈希映射，为什么不使用它们来索引我们的磁盘数据呢？

Let’s say our data storage consists only of appending to a file, as in the preceding example. Then the simplest possible indexing strategy is this: keep an in-memory hash map where every key is mapped to a byte offset in the data file—the location at which the value can be found, as illustrated in Figure 3-1 . Whenever you append a new key-value pair to the file, you also update the hash map to reflect the offset of the data you just wrote (this works both for inserting new keys and for updating existing keys). When you want to look up a value, use the hash map to find the offset in the data file, seek to that location, and read the value.

假设我们的数据存储仅仅是在一个文件中添加内容，和前面的例子一样。那么最简单的索引策略是：在内存中保持一个哈希映射，其中每个键都被映射到数据文件中的一个字节偏移量，也就是值所在的位置，如图3-1所示。每当你把一个新的键值对添加到文件中，你也要更新哈希映射，以反映出你刚刚写入的数据的偏移量（这对于插入新键和更新现有键都适用）。当你想要查找一个值时，使用哈希映射来找到数据文件中的偏移量，把指针定位到该位置，然后读取值。

Figure 3-1. Storing a log of key-value pairs in a CSV-like format, indexed with an in-memory hash map.

This may sound simplistic, but it is a viable approach. In fact, this is essentially what Bitcask (the default storage engine in Riak) does [ 3 ]. Bitcask offers high-performance reads and writes, subject to the requirement that all the keys fit in the available RAM, since the hash map is kept completely in memory. The values can use more space than there is available memory, since they can be loaded from disk with just one disk seek. If that part of the data file is already in the filesystem cache, a read doesn’t require any disk I/O at all.

这听起来很简单，但这是一种可行的方法。实际上，这就是Bitcask（Riak的默认存储引擎）的基本操作[3]。 Bitcask提供高性能的读写功能，要求所有键都适合可用的RAM，因为哈希映射被完全保存在内存中。值可以使用比可用内存更多的空间，因为它们可以通过只进行一次磁盘搜索，从磁盘加载。如果该数据文件的部分已经在文件系统高速缓存中，那么读取就不需要任何磁盘I/O。

A storage engine like Bitcask is well suited to situations where the value for each key is updated frequently. For example, the key might be the URL of a cat video, and the value might be the number of times it has been played (incremented every time someone hits the play button). In this kind of workload, there are a lot of writes, but there are not too many distinct keys—you have a large number of writes per key, but it’s feasible to keep all keys in memory.

像Bitcask这样的存储引擎非常适用于每个键的值经常更新的情况。例如，键可以是猫视频的URL，而值可以是播放次数（每次有人点击播放按钮就会增加）。在这种负载下，有很多写入操作，但是不会有太多不同的键 - 每个键有大量的写入操作，但是在内存中保留所有键是可行的。

As described so far, we only ever append to a file—so how do we avoid eventually running out of disk space? A good solution is to break the log into segments of a certain size by closing a segment file when it reaches a certain size, and making subsequent writes to a new segment file. We can then perform compaction on these segments, as illustrated in Figure 3-2 . Compaction means throwing away duplicate keys in the log, and keeping only the most recent update for each key.

到目前为止，我们只添加到文件，那么我们如何避免最终用尽磁盘空间？一个好的解决方案是将日志分成一定大小的段，当一个段文件达到一定大小时关闭它，并在新的段文件中进行后续写操作。然后我们可以对这些段执行压缩，如图3-2所示。压缩是指在日志中丢弃重复键，并仅保留每个键的最新更新。

Figure 3-2. Compaction of a key-value update log (counting the number of times each cat video was played), retaining only the most recent value for each key.

Moreover, since compaction often makes segments much smaller (assuming that a key is overwritten several times on average within one segment), we can also merge several segments together at the same time as performing the compaction, as shown in Figure 3-3 . Segments are never modified after they have been written, so the merged segment is written to a new file. The merging and compaction of frozen segments can be done in a background thread, and while it is going on, we can still continue to serve read and write requests as normal, using the old segment files. After the merging process is complete, we switch read requests to using the new merged segment instead of the old segments—and then the old segment files can simply be deleted.

此外，由于紧缩通常会使段变得更小（假设一个键在一个段内被平均覆盖多次），所以我们也可以在紧缩的同时合并多个段，如图3-3所示。段一旦被写入后就不会被修改，因此合并的段被写入一个新文件中。冻结段的合并和紧缩可以在后台线程中完成，而在此期间，我们仍然可以像往常一样使用旧段文件来继续提供读写请求。在合并过程完成后，我们将读取请求切换到使用新合并的段而不是旧的段，然后旧的段文件可以被简单删除。

Figure 3-3. Performing compaction and segment merging simultaneously.

Each segment now has its own in-memory hash table, mapping keys to file offsets. In order to find the value for a key, we first check the most recent segment’s hash map; if the key is not present we check the second-most-recent segment, and so on. The merging process keeps the number of segments small, so lookups don’t need to check many hash maps.

现在每个分段都有自己的内存哈希表，将键映射到文件偏移量。为了查找键的值，我们首先检查最近的分段哈希映射；如果键不存在，则检查第二个最近的分段，依此类推。合并过程使分段数保持较小，因此查找不需要检查许多哈希映射。

Lots of detail goes into making this simple idea work in practice. Briefly, some of the issues that are important in a real implementation are:

制作这个简单的想法需要考虑许多细节。简要来说，一些实际实现中重要的问题包括：

File format

CSV is not the best format for a log. It’s faster and simpler to use a binary format that first encodes the length of a string in bytes, followed by the raw string (without need for escaping).

CSV不是日志的最佳格式。使用一种二进制格式更快，更简单，首先会对字符串的长度进行编码（以字节为单位），然后是原始字符串（无需转义）。

Deleting records

If you want to delete a key and its associated value, you have to append a special deletion record to the data file (sometimes called a tombstone ). When log segments are merged, the tombstone tells the merging process to discard any previous values for the deleted key.

如果您想删除一个键和它相关联的值，必须向数据文件附加一个特殊的删除记录（有时称为墓碑）。当日志段合并时，墓碑会告诉合并过程丢弃已删除键的任何先前值。

Crash recovery

If the database is restarted, the in-memory hash maps are lost. In principle, you can restore each segment’s hash map by reading the entire segment file from beginning to end and noting the offset of the most recent value for every key as you go along. However, that might take a long time if the segment files are large, which would make server restarts painful. Bitcask speeds up recovery by storing a snapshot of each segment’s hash map on disk, which can be loaded into memory more quickly.

如果数据库重新启动，内存中的哈希映射会丢失。原则上，可以通过从头到尾读取每个段文件并记录每个键的最新值的偏移量来恢复每个段的哈希映射。但是，如果段文件很大，这样做可能需要很长时间，从而使服务器重新启动非常痛苦。Bitcask通过在磁盘上存储每个段的哈希映射快照来加速恢复，可以更快地将其加载到内存中。

Partially written records

The database may crash at any time, including halfway through appending a record to the log. Bitcask files include checksums, allowing such corrupted parts of the log to be detected and ignored.

数据库可能会在任何时候崩溃，包括在将记录附加到日志的一半之处。 Bitcask 文件包括校验和，使可以检测和忽略日志中的这些损坏的部分。

Concurrency control

As writes are appended to the log in a strictly sequential order, a common implementation choice is to have only one writer thread. Data file segments are append-only and otherwise immutable, so they can be read concurrently by multiple threads.

由于写入操作必须严格按顺序附加到日志中，因此常见的实现选择是仅使用一个写入线程。数据文件段是只追加且不可变的，因此它们可以被多个线程同时读取。

An append-only log seems wasteful at first glance: why don’t you update the file in place, overwriting the old value with the new value? But an append-only design turns out to be good for several reasons:

“乍一看，仅追加日志似乎很浪费：为什么不在原地更新文件，用新值覆盖旧值？但事实证明，仅追加设计在多个方面都非常优秀：”

• Appending and segment merging are sequential write operations, which are generally much faster than random writes, especially on magnetic spinning-disk hard drives. To some extent sequential writes are also preferable on flash-based solid state drives (SSDs) [ 4 ]. We will discuss this issue further in “Comparing B-Trees and LSM-Trees” .

  添加与段合并是连续写入操作，通常比随机写入快得多，尤其是在磁盘硬盘上。在基于闪存的固态硬盘（SSD）上，一定程度上也更喜欢连续写入[4]。我们将在“比较B-树和LSM-树”中进一步讨论此问题。

• Concurrency and crash recovery are much simpler if segment files are append-only or immutable. For example, you don’t have to worry about the case where a crash happened while a value was being overwritten, leaving you with a file containing part of the old and part of the new value spliced together.

  如果分段文件是只追加或不可变的，那么并发和崩溃恢复就要简单得多。例如，你不必担心在值被覆盖时发生崩溃的情况，使得你只得到一个包含新值和旧值的部分拼接在一起的文件。

• Merging old segments avoids the problem of data files getting fragmented over time.

  合并旧部分可以避免数据文件随着时间的推移而变得分散。

However, the hash table index also has limitations:

然而，哈希表索引也有一些限制：

• The hash table must fit in memory, so if you have a very large number of keys, you’re out of luck. In principle, you could maintain a hash map on disk, but unfortunately it is difficult to make an on-disk hash map perform well. It requires a lot of random access I/O, it is expensive to grow when it becomes full, and hash collisions require fiddly logic [ 5 ].

  哈希表必须适合内存，所以如果您有大量的键，您就没那么幸运了。原则上，您可以在磁盘上维护哈希映射，但不幸的是很难使磁盘上的哈希映射表现良好。它需要大量的随机访问I/O，当它变满时扩展它是昂贵的，并且哈希冲突需要费力的逻辑 [5]。

• Range queries are not efficient. For example, you cannot easily scan over all keys between kitty00000 and kitty99999 —you’d have to look up each key individually in the hash maps.

  范围查询不是高效的。例如，您无法轻松地在kitty00000和kitty99999之间扫描所有键-您必须逐个查找散列映射中的每个键。

In the next section we will look at an indexing structure that doesn’t have those limitations.

在下一部分中，我们将看到一种没有这些限制的索引结构。

SSTables and LSM-Trees

In Figure 3-3 , each log-structured storage segment is a sequence of key-value pairs. These pairs appear in the order that they were written, and values later in the log take precedence over values for the same key earlier in the log. Apart from that, the order of key-value pairs in the file does not matter.

在图3-3中，每个日志结构化存储段都是键值对的序列。这些对按照它们被写入的顺序出现，日志中后面的值优先于日志中先前相同键的值。除此之外，文件中键值对的顺序并不重要。

Now we can make a simple change to the format of our segment files: we require that the sequence of key-value pairs is sorted by key . At first glance, that requirement seems to break our ability to use sequential writes, but we’ll get to that in a moment.

现在我们可以对我们的段文件格式进行简单更改：要求键值对的顺序按照键来排序。乍一看，这个要求似乎可能会破坏我们使用顺序写的能力，但是我们马上会解决这个问题。

We call this format Sorted String Table , or SSTable for short. We also require that each key only appears once within each merged segment file (the compaction process already ensures that). SSTables have several big advantages over log segments with hash indexes:

我们称之为排序字符串表格式，简称SSTable。我们还要求每个键在合并的段文件中只出现一次（合并过程已经确保了这一点）。SSTable比具有哈希索引的日志段有几个重要优点：

1. Merging segments is simple and efficient, even if the files are bigger than the available memory. The approach is like the one used in the mergesort algorithm and is illustrated in Figure 3-4 : you start reading the input files side by side, look at the first key in each file, copy the lowest key (according to the sort order) to the output file, and repeat. This produces a new merged segment file, also sorted by key.

   合并段落是简单高效的，即使文件大小超过了可用内存。这种方法类似于归并排序算法中使用的方法，在图3-4中有图解：你可以一边读取输入文件，一边对比每个文件的第一个键值，复制最小的键值（根据排序顺序）到输出文件中，然后重复此操作。这将产生一个新的合并段落文件，也是按键值排序的。

   

   Figure 3-4. Merging several SSTable segments, retaining only the most recent value for each key.

   What if the same key appears in several input segments? Remember that each segment contains all the values written to the database during some period of time. This means that all the values in one input segment must be more recent than all the values in the other segment (assuming that we always merge adjacent segments). When multiple segments contain the same key, we can keep the value from the most recent segment and discard the values in older segments.

   如果同一个键出现在多个输入段中怎么办？要记住，每个段都包含一段时间内写入数据库的所有值。这意味着一个输入段中的所有值必须比另一个段中的所有值更近（假设我们总是合并相邻段）。当多个段包含相同的键时，我们可以保留来自最新段的值，并且丢弃旧段中的值。 如果多个段中有相同的键，应该保留最新段的值，丢弃老段中的值。

2. In order to find a particular key in the file, you no longer need to keep an index of all the keys in memory. See Figure 3-5 for an example: say you’re looking for the key handiwork , but you don’t know the exact offset of that key in the segment file. However, you do know the offsets for the keys handbag and handsome , and because of the sorting you know that handiwork must appear between those two. This means you can jump to the offset for handbag and scan from there until you find handiwork (or not, if the key is not present in the file).

   为了在文件中查找特定的键，您不再需要在内存中保留所有键的索引。例如，假设您正在查找关键字"handiwork"，但您不知道该关键字在段文件中的确切偏移量。然而，您知道"handbag"和"handsome"的偏移量，并且由于排序，您知道"handiwork"必须出现在这两个关键字之间。这意味着您可以跳转到"handbag"的偏移量，并从那里扫描，直到找到"handiwork"（如果该键不存在于文件中，则不会找到）。

   

   Figure 3-5. An SSTable with an in-memory index.

   You still need an in-memory index to tell you the offsets for some of the keys, but it can be sparse: one key for every few kilobytes of segment file is sufficient, because a few kilobytes can be scanned very quickly. ⁱ

   你仍需一个内存索引来告诉你一些键的偏移量，但它可以是稀疏的：每几千字节的段文件只需一个键就足够了，因为几千字节可以很快地扫描。

3. Since read requests need to scan over several key-value pairs in the requested range anyway, it is possible to group those records into a block and compress it before writing it to disk (indicated by the shaded area in Figure 3-5 ). Each entry of the sparse in-memory index then points at the start of a compressed block. Besides saving disk space, compression also reduces the I/O bandwidth use.

   由于读请求需要在请求范围内扫描多个键值对，因此可以将这些记录分组并在写入磁盘之前对其进行压缩（如图3-5中的阴影区域所示）。 稀疏的内存索引的每个条目都指向一个压缩块的开头。 除了节省磁盘空间外，压缩还可以减少I / O带宽使用。

B-Trees

The log-structured indexes we have discussed so far are gaining acceptance, but they are not the most common type of index. The most widely used indexing structure is quite different: the B-tree .

到目前为止，我们讨论的日志结构化索引已经得到了认可，但它们并不是最常见的索引类型。最广泛使用的索引结构是完全不同的：B树。

Introduced in 1970 [ 17 ] and called “ubiquitous” less than 10 years later [ 18 ], B-trees have stood the test of time very well. They remain the standard index implementation in almost all relational databases, and many nonrelational databases use them too.

自1970年被引入[17]并在不到10年的时间内被称为“无处不在”， B-树经过了时间的考验。 它们仍然是几乎所有关系型数据库中的标准索引实现，许多非关系型数据库也使用它们。

Like SSTables, B-trees keep key-value pairs sorted by key, which allows efficient key-value lookups and range queries. But that’s where the similarity ends: B-trees have a very different design philosophy.

就像SSTables一样，B-树通过键对值进行排序，从而实现高效的键对值查找和范围查询。但这也是相似之处的尽头：B-树有一种非常不同的设计哲学。

The log-structured indexes we saw earlier break the database down into variable-size segments , typically several megabytes or more in size, and always write a segment sequentially. By contrast, B-trees break the database down into fixed-size blocks or pages , traditionally 4 KB in size (sometimes bigger), and read or write one page at a time. This design corresponds more closely to the underlying hardware, as disks are also arranged in fixed-size blocks.

早些时候我们看到的基于日志的索引将数据库拆分为可变大小的段，通常是几兆字节甚至更大，并且总是按顺序写入段。相比之下，B-树将数据库拆分为固定大小的块或页面，传统上为4 KB（有时更大），并一次读取或写入一个页面。这种设计更贴近底层硬件，因为磁盘也是按固定大小的块排列。

Each page can be identified using an address or location, which allows one page to refer to another—similar to a pointer, but on disk instead of in memory. We can use these page references to construct a tree of pages, as illustrated in Figure 3-6 .

每个页面都可以通过地址或位置进行识别，这使得一个页面可以引用另一个页面，类似于指针，但是在磁盘上而不是在内存中。我们可以使用这些页面引用来构建页面树，如图3-6所示。

Figure 3-6. Looking up a key using a B-tree index.

One page is designated as the root of the B-tree; whenever you want to look up a key in the index, you start here. The page contains several keys and references to child pages. Each child is responsible for a continuous range of keys, and the keys between the references indicate where the boundaries between those ranges lie.

一个页面被指定为B-tree的根；每当你想在索引中查找一个键时，你从这里开始。这个页面包含几个键和指向子页面的引用。每个子页面负责一段连续的键范围，引用之间的键指示这些范围之间的边界在哪里。

In the example in Figure 3-6 , we are looking for the key 251, so we know that we need to follow the page reference between the boundaries 200 and 300. That takes us to a similar-looking page that further breaks down the 200–300 range into subranges. Eventually we get down to a page containing individual keys (a leaf page ), which either contains the value for each key inline or contains references to the pages where the values can be found.

在图3-6的例子中，我们正在寻找键值为251的密钥，因此我们知道需要在200和300的范围内跟随页面引用。这将带我们到另一个类似的页面，进一步将200-300范围分解成子范围。最终，我们会来到一个包含单个密钥的页面（叶子页），其中每个密钥包含该值或包含对包含该值的页面的引用。

The number of references to child pages in one page of the B-tree is called the branching factor . For example, in Figure 3-6 the branching factor is six. In practice, the branching factor depends on the amount of space required to store the page references and the range boundaries, but typically it is several hundred.

B树中一个页面引用子页面的数量被称为分支因子。例如，在图3-6中，分支因子为六。实际上，分支因子取决于存储页面引用和范围边界所需的空间量，但通常为数百个。

If you want to update the value for an existing key in a B-tree, you search for the leaf page containing that key, change the value in that page, and write the page back to disk (any references to that page remain valid). If you want to add a new key, you need to find the page whose range encompasses the new key and add it to that page. If there isn’t enough free space in the page to accommodate the new key, it is split into two half-full pages, and the parent page is updated to account for the new subdivision of key ranges—see Figure 3-7 . ⁱⁱ

如果您想更新B-树中现有键的值，则需要搜索包含该键的叶页，更改该页中的值，并将该页写回磁盘（对该页的任何引用仍然有效）。如果您想添加新键，则需要找到其范围包含新键的页面，并将其添加到该页面中。如果页面中没有足够的空闲空间来容纳新键，则将其拆分为两个半满页面，并更新父页面以说明关键范围的新细分 - 请参见图3-7.ii。

Figure 3-7. Growing a B-tree by splitting a page.

This algorithm ensures that the tree remains balanced : a B-tree with n keys always has a depth of O (log n ). Most databases can fit into a B-tree that is three or four levels deep, so you don’t need to follow many page references to find the page you are looking for. (A four-level tree of 4 KB pages with a branching factor of 500 can store up to 256 TB.)

这种算法确保树保持平衡：具有n个键的B树始终具有O(log n)的深度。大多数数据库可以适应三到四层深度的B树，因此您不需要遵循许多页面引用来找到所需的页面。（具有500个分支因子的4 KB页面的四级树可存储高达256 TB。）

Comparing B-Trees and LSM-Trees

Even though B-tree implementations are generally more mature than LSM-tree implementations, LSM-trees are also interesting due to their performance characteristics. As a rule of thumb, LSM-trees are typically faster for writes, whereas B-trees are thought to be faster for reads [ 23 ]. Reads are typically slower on LSM-trees because they have to check several different data structures and SSTables at different stages of compaction.

尽管B-树实现通常比LSM-树实现更成熟，但由于性能特征，LSM-树也具有一定的吸引力。按照经验法则，LSM-树通常对写入更快，而B-树则被认为对读取更快[23]。由于它们必须检查几个不同的数据结构和不同的压实阶段的SSTables，因此LSM-树的读取通常较慢。

However, benchmarks are often inconclusive and sensitive to details of the workload. You need to test systems with your particular workload in order to make a valid comparison. In this section we will briefly discuss a few things that are worth considering when measuring the performance of a storage engine.

然而，基准测试通常不具可靠性，容易受到工作负载细节的影响。您需要使用特定工作负载测试系统，以确保有效的比较。在本节中，我们将简要探讨一些有关测量存储引擎性能的值得考虑的事情。

Other Indexing Structures

So far we have only discussed key-value indexes, which are like a primary key index in the relational model. A primary key uniquely identifies one row in a relational table, or one document in a document database, or one vertex in a graph database. Other records in the database can refer to that row/document/vertex by its primary key (or ID), and the index is used to resolve such references.

到目前为止，我们只讨论了键值索引，这类似于关系模型中的主键索引。主键唯一标识关系表中的一行，文档数据库中的一个文档，或图形数据库中的一个顶点。数据库中的其他记录可以通过它的主键（或ID）引用该行/文档/顶点，索引用于解决这些引用。

It is also very common to have secondary indexes . In relational databases, you can create several secondary indexes on the same table using the CREATE INDEX command, and they are often crucial for performing joins efficiently. For example, in Figure 2-1 in Chapter 2 you would most likely have a secondary index on the user_id columns so that you can find all the rows belonging to the same user in each of the tables.

在关系型数据库中，创建多个相同表格的次要索引是非常常见的，可以使用CREATE INDEX命令进行创建，通常这些索引对于高效地执行连接操作至关重要。例如，如果在第二章中的图2-1中，您可能会在user_id列上制定一个次要索引，以便可以在每个表格中找到所有属于同一用户的行。

A secondary index can easily be constructed from a key-value index. The main difference is that keys are not unique; i.e., there might be many rows (documents, vertices) with the same key. This can be solved in two ways: either by making each value in the index a list of matching row identifiers (like a postings list in a full-text index) or by making each key unique by appending a row identifier to it. Either way, both B-trees and log-structured indexes can be used as secondary indexes.

二级索引可以轻松地从键值索引构建。 主要区别在于键不是唯一的； 即，可能有许多行（文档，顶点）具有相同的键。这可以通过两种方式解决：要么使索引中的每个值都是匹配行标识符的列表（例如全文索引中的发布列表），要么通过附加行标识符将每个键唯一。 无论哪种方法，B树和日志结构索引都可以用作二级索引。

SELECT * FROM restaurants WHERE latitude  > 51.4946 AND latitude  < 51.5079
                            AND longitude > -0.1162 AND longitude < -0.1004;

Data Warehousing

An enterprise may have dozens of different transaction processing systems: systems powering the customer-facing website, controlling point of sale (checkout) systems in physical stores, tracking inventory in warehouses, planning routes for vehicles, managing suppliers, administering employees, etc. Each of these systems is complex and needs a team of people to maintain it, so the systems end up operating mostly autonomously from each other.

企业可能有数十个不同的交易处理系统：为客户面向的网站提供支持的系统，控制实体商店销售点（结账）系统的系统，跟踪仓库中的库存，规划车辆路线，管理供应商，管理员工等等。每个系统都很复杂，需要一个团队来维护，因此这些系统大多从彼此独立地运作。

These OLTP systems are usually expected to be highly available and to process transactions with low latency, since they are often critical to the operation of the business. Database administrators therefore closely guard their OLTP databases. They are usually reluctant to let business analysts run ad hoc analytic queries on an OLTP database, since those queries are often expensive, scanning large parts of the dataset, which can harm the performance of concurrently executing transactions.

这些OLTP系统通常被期望具有高可用性，并以低延迟方式处理事务，因为它们通常对业务操作至关重要。因此，数据库管理员严密保管他们的OLTP数据库。他们通常不愿意让业务分析师在OLTP数据库上运行即席分析查询，因为这些查询通常很昂贵，需要扫描数据集的大部分内容，这可能会损害同时执行的事务的性能。

A data warehouse , by contrast, is a separate database that analysts can query to their hearts’ content, without affecting OLTP operations [ 48 ]. The data warehouse contains a read-only copy of the data in all the various OLTP systems in the company. Data is extracted from OLTP databases (using either a periodic data dump or a continuous stream of updates), transformed into an analysis-friendly schema, cleaned up, and then loaded into the data warehouse. This process of getting data into the warehouse is known as Extract–Transform–Load (ETL) and is illustrated in Figure 3-8 .

数据仓库是一个单独的数据库，分析师可以随心所欲地查询它，而不会影响 OLTP 操作。数据仓库中包含了公司所有各种 OLTP 系统的数据的只读副本。数据是从 OLTP 数据库中提取的（使用定期数据转储或持续更新流），转换为适合分析的模式，清理并加载到数据仓库中。将数据装入仓库的过程称为 Extract-Transform-Load (ETL)，如图 3-8 所示。

Figure 3-8. Simplified outline of ETL into a data warehouse.

Data warehouses now exist in almost all large enterprises, but in small companies they are almost unheard of. This is probably because most small companies don’t have so many different OLTP systems, and most small companies have a small amount of data—small enough that it can be queried in a conventional SQL database, or even analyzed in a spreadsheet. In a large company, a lot of heavy lifting is required to do something that is simple in a small company.

数据仓库现在几乎在所有大型企业中存在，但在小型公司中，它们几乎是不为人知的。这可能是因为大多数小型公司没有太多不同的OLTP系统，并且大多数小型公司具有较少的数据量-足够小，可以在传统的SQL数据库中查询，甚至可以在电子表格中进行分析。在大型公司中，需要进行大量的工作才能完成小型公司中的简单任务。

A big advantage of using a separate data warehouse, rather than querying OLTP systems directly for analytics, is that the data warehouse can be optimized for analytic access patterns. It turns out that the indexing algorithms discussed in the first half of this chapter work well for OLTP, but are not very good at answering analytic queries. In the rest of this chapter we will look at storage engines that are optimized for analytics instead.

使用单独的数据仓库进行分析的一个巨大优势是，数据仓库可以为分析访问模式进行优化。事实证明，在本章的前半部分讨论的索引算法适用于 OLTP，但不适合回答分析查询。在本章的其余部分中，我们将研究专为分析而优化的存储引擎。

Stars and Snowflakes: Schemas for Analytics

As explored in Chapter 2 , a wide range of different data models are used in the realm of transaction processing, depending on the needs of the application. On the other hand, in analytics, there is much less diversity of data models. Many data warehouses are used in a fairly formulaic style, known as a star schema (also known as dimensional modeling [ 55 ]).

正如第2章所探讨的，事务处理领域中使用了各种不同的数据模型，具体取决于应用程序的需求。另一方面，在分析领域中，数据模型的多样性要少得多。许多数据仓库采用了一种相当公式化的样式，称为星型模式（也称为维度建模）。

The example schema in Figure 3-9 shows a data warehouse that might be found at a grocery retailer. At the center of the schema is a so-called fact table (in this example, it is called fact_sales ). Each row of the fact table represents an event that occurred at a particular time (here, each row represents a customer’s purchase of a product). If we were analyzing website traffic rather than retail sales, each row might represent a page view or a click by a user.

图3-9中的示例模式显示了一个可能在杂货零售商处找到的数据仓库。模式的中心是所谓的事实表（在本例中，它被称为fact_sales）。事实表的每一行表示发生在特定时间的事件（在这里，每一行表示客户购买产品）。如果我们分析的是网站流量而不是零售销售，每行可能表示用户的页面视图或点击。

Figure 3-9. Example of a star schema for use in a data warehouse.

Usually, facts are captured as individual events, because this allows maximum flexibility of analysis later. However, this means that the fact table can become extremely large. A big enterprise like Apple, Walmart, or eBay may have tens of petabytes of transaction history in its data warehouse, most of which is in fact tables [ 56 ].

通常情况下，事实被捕捉为单独的事件，因为这允许以后进行最大限度的灵活性分析。然而，这意味着事实表可以变得非常大。像苹果、沃尔玛或eBay这样的大企业可能拥有数十个petabytes的交易历史记录在其数据仓库中，其中大部分位于事实表中[56]。

Some of the columns in the fact table are attributes, such as the price at which the product was sold and the cost of buying it from the supplier (allowing the profit margin to be calculated). Other columns in the fact table are foreign key references to other tables, called dimension tables . As each row in the fact table represents an event, the dimensions represent the who , what , where , when , how , and why of the event.

事实表中的某些列是属性，例如产品销售的价格以及从供应商购买产品的成本（可计算利润率）。事实表中的其他列是指向其他表的外键引用，称为维度表。由于事实表中的每行代表一个事件，因此维度代表事件的谁，何物，何处，何时，如何和为什么。

For example, in Figure 3-9 , one of the dimensions is the product that was sold. Each row in the dim_product table represents one type of product that is for sale, including its stock-keeping unit (SKU), description, brand name, category, fat content, package size, etc. Each row in the fact_sales table uses a foreign key to indicate which product was sold in that particular transaction. (For simplicity, if the customer buys several different products at once, they are represented as separate rows in the fact table.)

例如，在图3-9中，一个维度是已售出的产品。dim_product表中的每一行代表一种销售产品，包括它的库存保持单位（SKU），描述，品牌名称，类别，脂肪含量，包装大小等。fact_sales表中的每一行使用外键表示在该特定交易中售出的产品。（为简单起见，如果客户同时购买多种不同产品，则在事实表中表示为单独的行。）

Even date and time are often represented using dimension tables, because this allows additional information about dates (such as public holidays) to be encoded, allowing queries to differentiate between sales on holidays and non-holidays.

日期和时间经常使用维度表来代表，因为这可以将有关日期的其他信息（例如公共假期）进行编码，从而使查询能够区别节假日和非节假日的销售。

The name “star schema” comes from the fact that when the table relationships are visualized, the fact table is in the middle, surrounded by its dimension tables; the connections to these tables are like the rays of a star.

星型模式这个名字来源于表关系的可视化，事实表位于中心，被尺寸表所包围; 这些表的连接就像一颗星的射线一样。

A variation of this template is known as the snowflake schema , where dimensions are further broken down into subdimensions. For example, there could be separate tables for brands and product categories, and each row in the dim_product table could reference the brand and category as foreign keys, rather than storing them as strings in the dim_product table. Snowflake schemas are more normalized than star schemas, but star schemas are often preferred because they are simpler for analysts to work with [ 55 ].

这个模板的一个变体称为雪花模式，其中维度被进一步分解为子维度。例如，品牌和产品类别可以有单独的表，并且dim_product表中的每一行都可以引用品牌和类别作为外键，而不是在dim_product表中将它们存储为字符串。雪花模式比星形模式更规范化，但星形模式通常更受分析师的欢迎，因为它们更简单[55]。

In a typical data warehouse, tables are often very wide: fact tables often have over 100 columns, sometimes several hundred [ 51 ]. Dimension tables can also be very wide, as they include all the metadata that may be relevant for analysis—for example, the dim_store table may include details of which services are offered at each store, whether it has an in-store bakery, the square footage, the date when the store was first opened, when it was last remodeled, how far it is from the nearest highway, etc.

在典型的数据仓库中，表通常非常宽：事实表通常拥有超过100个列，有时甚至几百个 [51]。维度表也可以非常宽，因为它们包括可能与分析相关的所有元数据 - 例如，dim_store表可能包括每个店铺提供的服务细节，是否有店内面包房，面积大小，店铺开业日期，上次翻新日期，距离最近的高速公路有多远等。

Column Compression

Besides only loading those columns from disk that are required for a query, we can further reduce the demands on disk throughput by compressing data. Fortunately, column-oriented storage often lends itself very well to compression.

除了只从磁盘加载查询所需的列之外，我们可以通过压缩数据进一步减少对磁盘吞吐量的需求。幸运的是，列式存储通常非常适合压缩。

Take a look at the sequences of values for each column in Figure 3-10 : they often look quite repetitive, which is a good sign for compression. Depending on the data in the column, different compression techniques can be used. One technique that is particularly effective in data warehouses is bitmap encoding , illustrated in Figure 3-11 .

看一下图3-10中每列的值序列：它们常常看起来非常重复，这对于压缩来说是一个好的迹象。根据列中的数据，可以使用不同的压缩技术。在数据仓库中特别有效的一种技术是位图编码，如图3-11所示。

Figure 3-11. Compressed, bitmap-indexed storage of a single column.

Often, the number of distinct values in a column is small compared to the number of rows (for example, a retailer may have billions of sales transactions, but only 100,000 distinct products). We can now take a column with n distinct values and turn it into n separate bitmaps: one bitmap for each distinct value, with one bit for each row. The bit is 1 if the row has that value, and 0 if not.

通常，列中有不同值的数量相对于行数来说很小（例如，零售商可能有数十亿的销售交易，但只有10万个不同的产品）。我们现在可以将具有n个不同值的列转换为n个单独的位图：每个不同值都有一个位图，每行一个位，如果该行具有该值，则位为1，否则为0。

If n is very small (for example, a country column may have approximately 200 distinct values), those bitmaps can be stored with one bit per row. But if n is bigger, there will be a lot of zeros in most of the bitmaps (we say that they are sparse ). In that case, the bitmaps can additionally be run-length encoded, as shown at the bottom of Figure 3-11 . This can make the encoding of a column remarkably compact.

如果n很小（例如，一个国家列大约有200个不同的值），那么这些位图可以以每行一个比特的方式存储。但是如果n更大，大部分位图中会有很多零（我们称之为稀疏）。在这种情况下，位图可以额外进行运行长度编码，如图3-11底部所示。这可以使列的编码非常紧凑。

Bitmap indexes such as these are very well suited for the kinds of queries that are common in a data warehouse. For example:

这样的位图索引非常适合数据仓库中常见的查询类型。例如：

WHERE product_sk IN (30, 68, 69):

Load the three bitmaps for product_sk = 30 , product_sk = 68 , and product_sk = 69 , and calculate the bitwise OR of the three bitmaps, which can be done very efficiently.

加载 product_sk = 30、product_sk = 68 和 product_sk = 69 的三个位图，然后高效地计算这三个位图的按位或。

WHERE product_sk = 31 AND store_sk = 3:

Load the bitmaps for product_sk = 31 and store_sk = 3 , and calculate the bitwise AND . This works because the columns contain the rows in the same order, so the k th bit in one column’s bitmap corresponds to the same row as the k th bit in another column’s bitmap.

加载 product_sk = 31 和 store_sk = 3 的位图，并计算位与。这是因为列包含的行以相同的顺序排列，因此一个列位图中的第k位对应于另一个列位图中的第k位相同的行。

There are also various other compression schemes for different kinds of data, but we won’t go into them in detail—see [ 58 ] for an overview.

还有许多不同种类数据的压缩方案，但我们不会详细介绍-请参阅[58]以获取概述。

Sort Order in Column Storage

In a column store, it doesn’t necessarily matter in which order the rows are stored. It’s easiest to store them in the order in which they were inserted, since then inserting a new row just means appending to each of the column files. However, we can choose to impose an order, like we did with SSTables previously, and use that as an indexing mechanism.

在列存储中，行的存储顺序并不重要。最简单的方法是按插入顺序进行存储，因为这样插入新行只需要将其追加到每个列文件中。然而，我们可以选择强制排序，就像之前使用SSTables一样，并将其用作索引机制。

Note that it wouldn’t make sense to sort each column independently, because then we would no longer know which items in the columns belong to the same row. We can only reconstruct a row because we know that the k th item in one column belongs to the same row as the k th item in another column.

请注意，独立对每一列进行排序是没有意义的，因为这样我们将不再知道每一列中的项目属于哪一行。我们只能重构一行，因为我们知道一个列中的第k个项目属于另一列中的第k个项目所在的同一行。

Rather, the data needs to be sorted an entire row at a time, even though it is stored by column. The administrator of the database can choose the columns by which the table should be sorted, using their knowledge of common queries. For example, if queries often target date ranges, such as the last month, it might make sense to make date_key the first sort key. Then the query optimizer can scan only the rows from the last month, which will be much faster than scanning all rows.

相反，数据需要整行排序，即使它是按列存储的。 数据库管理员可以选择按哪些列对表进行排序，利用常见查询的知识。例如，如果查询经常会针对日期范围，比如最近一个月，那么将日期键作为第一排序键可能是有意义的。然后查询优化器可以只扫描最近一个月的行，这比扫描所有行要快得多。

A second column can determine the sort order of any rows that have the same value in the first column. For example, if date_key is the first sort key in Figure 3-10 , it might make sense for product_sk to be the second sort key so that all sales for the same product on the same day are grouped together in storage. That will help queries that need to group or filter sales by product within a certain date range.

第二列可以确定在第一列具有相同值的任何行的排序顺序。例如，在图3-10中，如果date_key是第一个排序键，那么product_sk可能成为第二个排序键，以便将同一天相同产品的所有销售分组在一起存储。这将有助于需要在特定日期范围内按产品对销售进行分组或筛选的查询。

Another advantage of sorted order is that it can help with compression of columns. If the primary sort column does not have many distinct values, then after sorting, it will have long sequences where the same value is repeated many times in a row. A simple run-length encoding, like we used for the bitmaps in Figure 3-11 , could compress that column down to a few kilobytes—even if the table has billions of rows.

排序顺序的另一个优点是它有助于列的压缩。如果主排序列没有很多不同的值，那么排序后，它将有很长的序列，其中相同的值连续重复很多次。像图3-11中用于位图的简单运行长度编码可以将该列压缩到几千字节，即使表有数十亿行。

That compression effect is strongest on the first sort key. The second and third sort keys will be more jumbled up, and thus not have such long runs of repeated values. Columns further down the sorting priority appear in essentially random order, so they probably won’t compress as well. But having the first few columns sorted is still a win overall.

该压缩效应在第一个排序键上最为强烈。第二个和第三个排序键将会更加杂乱无章，因此不会有如此长的重复值序列。更靠后的排序优先级的列是基本上以随机顺序出现的，因此它们可能不会被很好地压缩。但是，总体而言，排序前几列仍然是一个胜利。

Writing to Column-Oriented Storage

These optimizations make sense in data warehouses, because most of the load consists of large read-only queries run by analysts. Column-oriented storage, compression, and sorting all help to make those read queries faster. However, they have the downside of making writes more difficult.

这些优化在数据仓库中是有意义的，因为大多数负载都是由分析师运行的大型只读查询。列导向存储、压缩和排序都有助于加快这些读查询的速度。然而，它们的缺点是使写更加困难。

An update-in-place approach, like B-trees use, is not possible with compressed columns. If you wanted to insert a row in the middle of a sorted table, you would most likely have to rewrite all the column files. As rows are identified by their position within a column, the insertion has to update all columns consistently.

压缩列不可能使用像B树那样的就地更新方法。如果您想要在排序表的中间插入一行，您很可能不得不重新编写所有列文件。由于行是通过它们在列中的位置来标识的，因此插入操作必须一致地更新所有列。

Fortunately, we have already seen a good solution earlier in this chapter: LSM-trees. All writes first go to an in-memory store, where they are added to a sorted structure and prepared for writing to disk. It doesn’t matter whether the in-memory store is row-oriented or column-oriented. When enough writes have accumulated, they are merged with the column files on disk and written to new files in bulk. This is essentially what Vertica does [ 62 ].

幸运的是，我们已经在本章早些时候看到了一个好的解决方案：LSM树。所有写操作首先都会进入内存存储，添加到一个排序结构中，并做好写入磁盘的准备。无论内存存储是面向行还是面向列都没有关系。当收集到足够的写操作后，它们会与磁盘上的列文件合并，并批量地写入新文件中。这本质上就是Vertica的做法[62]。

Queries need to examine both the column data on disk and the recent writes in memory, and combine the two. However, the query optimizer hides this distinction from the user. From an analyst’s point of view, data that has been modified with inserts, updates, or deletes is immediately reflected in subsequent queries.

查询需要同时检查磁盘上的列数据和最近在内存中的写入，并将两者结合起来。然而，查询优化器会隐藏这种区别。从分析师的角度来看，插入、更新或删除的数据在后续查询中立即反映出来。

Aggregation: Data Cubes and Materialized Views

Not every data warehouse is necessarily a column store: traditional row-oriented databases and a few other architectures are also used. However, columnar storage can be significantly faster for ad hoc analytical queries, so it is rapidly gaining popularity [ 51 , 63 ].

并非所有的数据仓库都必须是列存储：传统的行导向数据库和其他几种架构也被使用。然而，列存储对于特定于问题的分析查询可以明显地更快，因此正在快速地获得流行 [51, 63]。 并非所有数据仓库都是列式存储：也有传统的行式数据库和一些其他架构被使用。然而，列式存储对于特定的分析查询可以明显更快，因此正在迅速普及。

Another aspect of data warehouses that is worth mentioning briefly is materialized aggregates . As discussed earlier, data warehouse queries often involve an aggregate function, such as COUNT , SUM , AVG , MIN , or MAX in SQL. If the same aggregates are used by many different queries, it can be wasteful to crunch through the raw data every time. Why not cache some of the counts or sums that queries use most often?

数据仓库中值得简要提及的另一个方面是物化聚合。如早先所述，数据仓库查询经常涉及SQL中的聚合函数，如COUNT、SUM、AVG、MIN或MAX。如果许多不同的查询使用相同的聚合，每次都通过原始数据进行计算可能是浪费的。为什么不缓存一些最常用的计数或总和？

One way of creating such a cache is a materialized view . In a relational data model, it is often defined like a standard (virtual) view: a table-like object whose contents are the results of some query. The difference is that a materialized view is an actual copy of the query results, written to disk, whereas a virtual view is just a shortcut for writing queries. When you read from a virtual view, the SQL engine expands it into the view’s underlying query on the fly and then processes the expanded query.

创建这样一个高速缓存的一种方法是利用实现视图。在关系式数据模型中，它通常与标准（虚拟）视图相似：一个类似表格的对象其内容是某些查询的结果。区别在于实现视图是查询结果的实际副本并写入磁盘，而虚拟视图只是查询的一个捷径。当你从虚拟视图中阅读时，SQL引擎会实时将其扩展为视图底层的查询然后处理扩展的查询。

When the underlying data changes, a materialized view needs to be updated, because it is a denormalized copy of the data. The database can do that automatically, but such updates make writes more expensive, which is why materialized views are not often used in OLTP databases. In read-heavy data warehouses they can make more sense (whether or not they actually improve read performance depends on the individual case).

当底层数据发生变化时，需要更新物化视图，因为它是数据的非规范化副本。数据库可以自动执行此操作，但这会导致写入更加昂贵，这就是为什么物化视图在OLTP数据库中并不常用的原因。在读取密集的数据仓库中，它们可能更有意义（无论它们是否实际改善读取性能取决于不同情况）。

A common special case of a materialized view is known as a data cube or OLAP cube [ 64 ]. It is a grid of aggregates grouped by different dimensions. Figure 3-12 shows an example.

一种常见的物化视图特例称为数据立方体或OLAP立方体[64]。 它是按不同维度分组的聚合数据表格。图3-12显示了一个例子。

Figure 3-12. Two dimensions of a data cube, aggregating data by summing.

Imagine for now that each fact has foreign keys to only two dimension tables—in Figure 3-12 , these are date and product . You can now draw a two-dimensional table, with dates along one axis and products along the other. Each cell contains the aggregate (e.g., SUM ) of an attribute (e.g., net_price ) of all facts with that date-product combination. Then you can apply the same aggregate along each row or column and get a summary that has been reduced by one dimension (the sales by product regardless of date, or the sales by date regardless of product).

现在想象一下，每个事实仅有两个维度表的外键 - 在图3-12中，这些是日期和产品。您现在可以绘制一个二维表，一个轴上是日期，另一个轴上是产品。每个单元格包含具有该日期-产品组合的所有事实属性（例如净价）的聚合（例如SUM）。然后，您可以沿每行或列应用相同的聚合并获得减少一个维度的摘要（不考虑产品的销售或不考虑日期的销售）。

In general, facts often have more than two dimensions. In Figure 3-9 there are five dimensions: date, product, store, promotion, and customer. It’s a lot harder to imagine what a five-dimensional hypercube would look like, but the principle remains the same: each cell contains the sales for a particular date-product-store-promotion-customer combination. These values can then repeatedly be summarized along each of the dimensions.

通常来说，事实往往具有超过两个维度。在图3-9中，有五个维度：日期、产品、商店、促销和客户。想象一个五维超立方体是非常困难的，但原则仍然相同：每个单元格包含特定日期-产品-商店-促销-客户组合的销售额。然后可以沿着每个维度反复总结这些值。

The advantage of a materialized data cube is that certain queries become very fast because they have effectively been precomputed. For example, if you want to know the total sales per store yesterday, you just need to look at the totals along the appropriate dimension—no need to scan millions of rows.

材料化数据立方体的优点在于，某些查询变得非常快速，因为它们已经有效地预先计算过了。例如，如果你想知道昨天每个店铺的总销售额，你只需要查看沿着适当的维度的总数——不需要扫描数百万行。

The disadvantage is that a data cube doesn’t have the same flexibility as querying the raw data. For example, there is no way of calculating which proportion of sales comes from items that cost more than $100, because the price isn’t one of the dimensions. Most data warehouses therefore try to keep as much raw data as possible, and use aggregates such as data cubes only as a performance boost for certain queries.

数据立方体的劣势在于它没有像查询原始数据那样的灵活性。例如，没有办法计算销售中由成本高于100美元的商品组成的比例，因为价格不是其中一个维度。因此，大多数数据仓库尽可能地保留原始数据，仅将数据立方体等聚合方式用于某些查询的性能提升。

Language-Specific Formats

Many programming languages come with built-in support for encoding in-memory objects into byte sequences. For example, Java has java.io.Serializable [ 1 ], Ruby has Marshal [ 2 ], Python has pickle [ 3 ], and so on. Many third-party libraries also exist, such as Kryo for Java [ 4 ].

许多编程语言都配备了将内存对象编码成字节序列的内置支持。例如，Java有java.io.Serializable，Ruby有Marshal，Python有pickle等等。还有许多第三方库存在，比如Java的Kryo。

These encoding libraries are very convenient, because they allow in-memory objects to be saved and restored with minimal additional code. However, they also have a number of deep problems:

这些编码库非常方便，因为它们允许内存对象以最少的额外代码进行保存和恢复。然而，它们也存在许多深层问题：

• The encoding is often tied to a particular programming language, and reading the data in another language is very difficult. If you store or transmit data in such an encoding, you are committing yourself to your current programming language for potentially a very long time, and precluding integrating your systems with those of other organizations (which may use different languages).

  编码通常与特定的编程语言相关联，使用另一种语言读取数据非常困难。如果您以这种编码方式存储或传输数据，可能会长期限制自己使用当前的编程语言，并阻碍与其他组织（可能使用不同语言）集成系统的能力。

• In order to restore data in the same object types, the decoding process needs to be able to instantiate arbitrary classes. This is frequently a source of security problems [ 5 ]: if an attacker can get your application to decode an arbitrary byte sequence, they can instantiate arbitrary classes, which in turn often allows them to do terrible things such as remotely executing arbitrary code [ 6 , 7 ].

  为了在相同的对象类型中恢复数据，解码过程需要能够实例化任意类。这经常是安全问题的源泉：如果攻击者能够让您的应用程序解码任意字节序列，他们可以实例化任意类，这通常允许他们做可怕的事情，比如远程执行任意代码。

• Versioning data is often an afterthought in these libraries: as they are intended for quick and easy encoding of data, they often neglect the inconvenient problems of forward and backward compatibility.

  版本控制常常是这些库的边角料：由于它们的目的是快速和简单地编码数据，所以它们往往忽略了前向和后向兼容性的不方便问题。

• Efficiency (CPU time taken to encode or decode, and the size of the encoded structure) is also often an afterthought. For example, Java’s built-in serialization is notorious for its bad performance and bloated encoding [ 8 ].

  效率（编码或解码所需的CPU时间以及编码结构的大小）通常也是后来的想法。例如，Java内建的串行化因其性能差和编码过大而臭名昭著。

For these reasons it’s generally a bad idea to use your language’s built-in encoding for anything other than very transient purposes.

出于这些原因，除非是非常短暂的用途，通常不建议使用您的语言内置的编码方式。

JSON, XML, and Binary Variants

Moving to standardized encodings that can be written and read by many programming languages, JSON and XML are the obvious contenders. They are widely known, widely supported, and almost as widely disliked. XML is often criticized for being too verbose and unnecessarily complicated [ 9 ]. JSON’s popularity is mainly due to its built-in support in web browsers (by virtue of being a subset of JavaScript) and simplicity relative to XML. CSV is another popular language-independent format, albeit less powerful.

采用标准化编码，可以被多种编程语言编写和读取，JSON和XML是显而易见的竞争者。它们被广泛知晓，广泛支持，但几乎同样被人们所厌恶。XML经常因为太冗长和过于复杂而受到批评[9]。JSON之所以受欢迎，主要是因为它在网络浏览器中内置支持（由于是JavaScript的子集）并且相对于XML而言更为简单。CSV是另一种流行的独立于语言的格式，但它的功能比较有限。

JSON, XML, and CSV are textual formats, and thus somewhat human-readable (although the syntax is a popular topic of debate). Besides the superficial syntactic issues, they also have some subtle problems:

JSON、XML 和 CSV 都是文本格式，因此在某种程度上可以被人类阅读（尽管语法是热门话题，容易引发争议）。除了表面的语法问题，它们还有一些微妙的问题。

• There is a lot of ambiguity around the encoding of numbers. In XML and CSV, you cannot distinguish between a number and a string that happens to consist of digits (except by referring to an external schema). JSON distinguishes strings and numbers, but it doesn’t distinguish integers and floating-point numbers, and it doesn’t specify a precision.

  数字编码存在很多歧义。在XML和CSV中，你无法区分数字和由数字组成的字符串（除非参考外部架构）。JSON区分了字符串和数字，但它不区分整数和浮点数，并且它不指定精度。

  This is a problem when dealing with large numbers; for example, integers greater than 2 ⁵³ cannot be exactly represented in an IEEE 754 double-precision floating-point number, so such numbers become inaccurate when parsed in a language that uses floating-point numbers (such as JavaScript). An example of numbers larger than 2 ⁵³ occurs on Twitter, which uses a 64-bit number to identify each tweet. The JSON returned by Twitter’s API includes tweet IDs twice, once as a JSON number and once as a decimal string, to work around the fact that the numbers are not correctly parsed by JavaScript applications [ 10 ].

  处理大量数字时会遇到问题。例如，大于253的整数无法在IEEE 754双精度浮点数中准确表示，因此在使用浮点数（例如JavaScript）的语言中解析这些数字时，这些数字就会变得不准确。 Twitter上的数字就有大于253的情况，该网站使用64位数字来识别每个推文。 Twitter API返回的JSON包括推文ID两次，一次作为JSON数字，一次作为十进制字符串，以解决这些数字无法正确解析JavaScript应用程序的问题[10]。 处理大量数字时会遇到问题。例如，大于253的整数无法在IEEE 754双精度浮点数中准确表示，因此在使用浮点数（例如JavaScript）的语言中解析这些数字时，这些数字就会变得不准确。 Twitter上的数字就有大于253的情况，该网站使用64位数字来识别每个推文。 Twitter API返回的JSON包括推文ID两次，一次作为JSON数字，一次作为十进制字符串，以解决这些数字无法正确解析JavaScript应用程序的问题[10]。

• JSON and XML have good support for Unicode character strings (i.e., human-readable text), but they don’t support binary strings (sequences of bytes without a character encoding). Binary strings are a useful feature, so people get around this limitation by encoding the binary data as text using Base64. The schema is then used to indicate that the value should be interpreted as Base64-encoded. This works, but it’s somewhat hacky and increases the data size by 33%.

  JSON和XML对Unicode字符字符串（即人类可读的文本）有很好的支持，但它们不支持二进制字符串（没有字符编码的字节序列）。二进制字符串是一个有用的功能，因此人们通过使用Base64将二进制数据编码为文本来解决这个限制。然后使用模式来指示该值应解释为Base64编码。这可行，但它有点hacky，并且会将数据大小增加33％。

• There is optional schema support for both XML [ 11 ] and JSON [ 12 ]. These schema languages are quite powerful, and thus quite complicated to learn and implement. Use of XML schemas is fairly widespread, but many JSON-based tools don’t bother using schemas. Since the correct interpretation of data (such as numbers and binary strings) depends on information in the schema, applications that don’t use XML/JSON schemas need to potentially hardcode the appropriate encoding/decoding logic instead.

  XML和JSON都有可选的模式支持。这些模式语言非常强大，学习和实现都非常复杂。XML模式的使用相当广泛，但许多基于JSON的工具不使用模式。由于数据（例如数字和二进制字符串）的正确解释取决于模式中的信息，因此不使用XML/JSON模式的应用程序需要可能将适当的编码/解码逻辑硬编码。

• CSV does not have any schema, so it is up to the application to define the meaning of each row and column. If an application change adds a new row or column, you have to handle that change manually. CSV is also a quite vague format (what happens if a value contains a comma or a newline character?). Although its escaping rules have been formally specified [ 13 ], not all parsers implement them correctly.

  CSV 没有任何模式, 因此应用程序需要定义每行和每列的含义。如果应用程序的更改添加了一个新行或新列，则必须手动处理。 CSV 也是一种相当模糊的格式(如果一个值包含逗号或换行符会发生什么？)。 尽管其转义规则已被正式指定，但并非所有解析器都正确实现了它们。

Despite these flaws, JSON, XML, and CSV are good enough for many purposes. It’s likely that they will remain popular, especially as data interchange formats (i.e., for sending data from one organization to another). In these situations, as long as people agree on what the format is, it often doesn’t matter how pretty or efficient the format is. The difficulty of getting different organizations to agree on anything outweighs most other concerns.

尽管存在这些缺陷，JSON、XML和CSV对于许多目的来说已经足够好了。它们可能会继续流行，特别是作为数据交换格式（即用于从一个组织发送数据到另一个组织）。在这些情况下，只要人们对格式达成一致，格式的美观或效率通常并不重要。使不同组织就任何事情达成一致的难度超过了其他大多数考虑因素。

Binary encoding

For data that is used only internally within your organization, there is less pressure to use a lowest-common-denominator encoding format. For example, you could choose a format that is more compact or faster to parse. For a small dataset, the gains are negligible, but once you get into the terabytes, the choice of data format can have a big impact.

对于仅在组织内部使用的数据，使用最低公共编码格式的压力较小。例如，你可以选择更紧凑或更快速解析的格式。对于小数据集，收益微不足道，但是当你进入了以太字节时，数据格式的选择就会有很大的影响。

JSON is less verbose than XML, but both still use a lot of space compared to binary formats. This observation led to the development of a profusion of binary encodings for JSON (MessagePack, BSON, BJSON, UBJSON, BISON, and Smile, to name a few) and for XML (WBXML and Fast Infoset, for example). These formats have been adopted in various niches, but none of them are as widely adopted as the textual versions of JSON and XML.

JSON比XML更简洁，但与二进制格式相比，两者仍然使用很多空间。这个观察结果导致了大量针对JSON（如MessagePack、BSON、BJSON、UBJSON、BISON和Smile）和XML（例如WBXML和Fast Infoset）的二进制编码的开发。这些格式已被用于各种领域，但它们中没有一个像JSON和XML的文本版本那样被广泛采用。

Some of these formats extend the set of datatypes (e.g., distinguishing integers and floating-point numbers, or adding support for binary strings), but otherwise they keep the JSON/XML data model unchanged. In particular, since they don’t prescribe a schema, they need to include all the object field names within the encoded data. That is, in a binary encoding of the JSON document in Example 4-1 , they will need to include the strings userName , favoriteNumber , and interests somewhere.

其中一些格式扩展了数据类型集合（例如，区分整数和浮点数，或添加对二进制字符串的支持），但是它们保持了JSON/XML数据模型不变。特别地，由于它们不规定模式，因此它们需要在编码数据中包含所有对象字段名称。也就是说，在JSON文档的二进制编码中，它们需要在某个地方包含字符串userName、favoriteNumber和interests。

Example 4-1. Example record which we will encode in several binary formats in this chapter

{
    "userName": "Martin",
    "favoriteNumber": 1337,
    "interests": ["daydreaming", "hacking"]
}

Let’s look at an example of MessagePack, a binary encoding for JSON. Figure 4-1 shows the byte sequence that you get if you encode the JSON document in Example 4-1 with MessagePack [ 14 ]. The first few bytes are as follows:

让我们来看一个例子，MessagePack是一种用于JSON的二进制编码。图4-1显示了在MessagePack [14]中对Example 4-1中的JSON文档进行编码时所获得的字节序列。前几个字节如下：

1. The first byte, 0x83 , indicates that what follows is an object (top four bits = 0x80 ) with three fields (bottom four bits = 0x03 ). (In case you’re wondering what happens if an object has more than 15 fields, so that the number of fields doesn’t fit in four bits, it then gets a different type indicator, and the number of fields is encoded in two or four bytes.)

   第一个字节0x83表示接下来的内容是一个对象（高四位=0x80），有三个域（低四位=0x03）。如果你想知道对象有超过15个属性的情况下，没有办法用四位来编码属性的数量，那么就用不同的类型指示符，并用两个或四个字节来编码属性数量。

2. The second byte, 0xa8 , indicates that what follows is a string (top four bits = 0xa0 ) that is eight bytes long (bottom four bits = 0x08 ).

   第二个字节0xa8表示接下来的内容是一个字符串（前四位=0xa0），并且该字符串共有8个字节长度（后四位=0x08）。

3. The next eight bytes are the field name userName in ASCII. Since the length was indicated previously, there’s no need for any marker to tell us where the string ends (or any escaping).

   下一个八个字节是ASCII码格式的字段名userName。由于长度已经先前标示，因此不需要任何标记来告诉我们字符串的结尾（或任何转义）。

4. The next seven bytes encode the six-letter string value Martin with a prefix 0xa6 , and so on.

   下七个字节编码了带有0xa6前缀的六个字母字符串值Martin，以此类推。

The binary encoding is 66 bytes long, which is only a little less than the 81 bytes taken by the textual JSON encoding (with whitespace removed). All the binary encodings of JSON are similar in this regard. It’s not clear whether such a small space reduction (and perhaps a speedup in parsing) is worth the loss of human-readability.

二进制编码长66字节，比文本JSON编码（无空格）占用的81字节略少。所有JSON的二进制编码在这方面都相似。尚不清楚这样的空间减少（可能会提高解析速度）是否值得失去人类可读性。

In the following sections we will see how we can do much better, and encode the same record in just 32 bytes.

在接下来的章节中，我们将看到我们如何可以做得更好，仅使用32个字节来编码相同的记录。

Figure 4-1. Example record ( Example 4-1 ) encoded using MessagePack.

Thrift and Protocol Buffers

Apache Thrift [ 15 ] and Protocol Buffers (protobuf) [ 16 ] are binary encoding libraries that are based on the same principle. Protocol Buffers was originally developed at Google, Thrift was originally developed at Facebook, and both were made open source in 2007–08 [ 17 ].

Apache Thrift和Protocol Buffers（protobuf）是基于相同原则的二进制编码库。Protocol Buffers最初在Google开发，Thrift最初在Facebook开发，并在2007-08年开源 [17]。

Both Thrift and Protocol Buffers require a schema for any data that is encoded. To encode the data in Example 4-1 in Thrift, you would describe the schema in the Thrift interface definition language (IDL) like this:

Thrift和Protocol Buffers都需要为编码的任何数据提供模式。为了在Thrift中编码Example 4-1中的数据，您需要使用Thrift接口定义语言（IDL）描述模式，如下所示：

struct Person {
  1: required string       userName,
  2: optional i64          favoriteNumber,
  3: optional list<string> interests
}

The equivalent schema definition for Protocol Buffers looks very similar:

Protocol Buffers的等效模式定义看起来非常相似：

message Person {
    required string user_name       = 1;
    optional int64  favorite_number = 2;
    repeated string interests       = 3;
}

Thrift and Protocol Buffers each come with a code generation tool that takes a schema definition like the ones shown here, and produces classes that implement the schema in various programming languages [ 18 ]. Your application code can call this generated code to encode or decode records of the schema.

节俭和协议缓冲区都配备了一个代码生成工具，它可以采用类似于此处所示的模式定义并生成在各种编程语言中实现模式的类[18]。您的应用程序代码可以调用此生成的代码来编码或解码模式的记录。

What does data encoded with this schema look like? Confusingly, Thrift has two different binary encoding formats, ⁱⁱⁱ called BinaryProtocol and CompactProtocol , respectively. Let’s look at BinaryProtocol first. Encoding Example 4-1 in that format takes 59 bytes, as shown in Figure 4-2 [ 19 ].

使用此架構編碼的數據長什麼樣子？令人困惑的是，Thrift 有兩種不同的二進制編碼格式，分別稱為 BinaryProtocol 和 CompactProtocol。讓我們先看看 BinaryProtocol。在這種格式中，編碼示例 4-1 需要 59 個字節，如圖 4-2 所示。

Figure 4-2. Example record encoded using Thrift’s BinaryProtocol.

Similarly to Figure 4-1 , each field has a type annotation (to indicate whether it is a string, integer, list, etc.) and, where required, a length indication (length of a string, number of items in a list). The strings that appear in the data (“Martin”, “daydreaming”, “hacking”) are also encoded as ASCII (or rather, UTF-8), similar to before.

与图4-1类似，每个字段都有类型注释（用于表示它是字符串、整数、列表等），并且在必要时有长度指示（字符串的长度，列表中的项数）。出现在数据中的字符串（“Martin”、“daydreaming”、“hacking”）也被编码为ASCII（或更准确地说，是UTF-8），与以前类似。

The big difference compared to Figure 4-1 is that there are no field names ( userName , favoriteNumber , interests ). Instead, the encoded data contains field tags , which are numbers ( 1 , 2 , and 3 ). Those are the numbers that appear in the schema definition. Field tags are like aliases for fields—they are a compact way of saying what field we’re talking about, without having to spell out the field name.

与图4-1相比的重大区别在于没有字段名称（用户名、收藏数、兴趣爱好）。相反，编码数据包含字段标记，即数字（1、2和3）。这些是模式定义中出现的数字。字段标记就像字段的别名-它们是一种紧凑的方式，用于说明我们正在谈论哪个字段，而无需拼写出字段名称。

The Thrift CompactProtocol encoding is semantically equivalent to BinaryProtocol, but as you can see in Figure 4-3 , it packs the same information into only 34 bytes. It does this by packing the field type and tag number into a single byte, and by using variable-length integers. Rather than using a full eight bytes for the number 1337, it is encoded in two bytes, with the top bit of each byte used to indicate whether there are still more bytes to come. This means numbers between –64 and 63 are encoded in one byte, numbers between –8192 and 8191 are encoded in two bytes, etc. Bigger numbers use more bytes.

Thrift CompactProtocol 编码与 BinaryProtocol 在语义上是等价的，但正如图 4-3 所示，它将相同的信息压缩到仅 34 字节内。它通过将字段类型和标记号码打包成单个字节，并使用可变长度整数来实现。它不是使用完整的八个字节来表示数字 1337，而是使用两个字节进行编码，每个字节的最高位用于指示是否还有更多的字节。这意味着在 -64 和 63 之间的数字在一个字节中编码，在 -8192 和 8191 之间的数字在两个字节中编码，以此类推。更大的数字使用更多的字节。

Figure 4-3. Example record encoded using Thrift’s CompactProtocol.

Finally, Protocol Buffers (which has only one binary encoding format) encodes the same data as shown in Figure 4-4 . It does the bit packing slightly differently, but is otherwise very similar to Thrift’s CompactProtocol. Protocol Buffers fits the same record in 33 bytes.

最终，协议缓冲（只有一个二进制编码格式）对于显示的相同数据进行了编码，如图4-4所示。它稍微不同地进行了位包装，但与Thrift的CompactProtocol非常相似。协议缓冲将相同的记录放在33个字节中。

Figure 4-4. Example record encoded using Protocol Buffers.

One detail to note: in the schemas shown earlier, each field was marked either required or optional , but this makes no difference to how the field is encoded (nothing in the binary data indicates whether a field was required). The difference is simply that required enables a runtime check that fails if the field is not set, which can be useful for catching bugs.

需要注意的一点是：在之前展示的架构中，每个字段都标记为必需或可选，但是这对字段的编码方式没有任何影响（二进制数据中没有指示一个字段是否必需的信息）。不同之处仅在于必需能够启用运行时检查，如果字段未设置，就会失败，这对于捕捉错误非常有用。

Avro

Apache Avro [ 20 ] is another binary encoding format that is interestingly different from Protocol Buffers and Thrift. It was started in 2009 as a subproject of Hadoop, as a result of Thrift not being a good fit for Hadoop’s use cases [ 21 ].

Apache Avro是另一种有趣而与Protocol Buffers和Thrift不同的二进制编码格式。它始于2009年，作为Hadoop的一个子项目，由于Thrift不适合Hadoop的用例而产生。

Avro also uses a schema to specify the structure of the data being encoded. It has two schema languages: one (Avro IDL) intended for human editing, and one (based on JSON) that is more easily machine-readable.

Avro还使用模式来指定被编码的数据的结构。它有两种模式语言：一种（Avro IDL）用于人类编辑，另一种（基于JSON的）更容易被机器读取。

Our example schema, written in Avro IDL, might look like this:

我们的示例模式，使用Avro IDL编写，可能如下所示：

record Person {
    string               userName;
    union { null, long } favoriteNumber = null;
    array<string>        interests;
}

The equivalent JSON representation of that schema is as follows:

该模式的等效JSON表示形式如下：

{
    "type": "record",
    "name": "Person",
    "fields": [
        {"name": "userName",       "type": "string"},
        {"name": "favoriteNumber", "type": ["null", "long"], "default": null},
        {"name": "interests",      "type": {"type": "array", "items": "string"}}
    ]
}

First of all, notice that there are no tag numbers in the schema. If we encode our example record ( Example 4-1 ) using this schema, the Avro binary encoding is just 32 bytes long—the most compact of all the encodings we have seen. The breakdown of the encoded byte sequence is shown in Figure 4-5 .

首先，请注意模式中没有标签号。如果使用此模式对我们的示例记录（示例4-1）进行编码，则Avro二进制编码仅为32个字节，是我们所见过的所有编码中最紧凑的。编码字节序列的分解如图4-5所示。

If you examine the byte sequence, you can see that there is nothing to identify fields or their datatypes. The encoding simply consists of values concatenated together. A string is just a length prefix followed by UTF-8 bytes, but there’s nothing in the encoded data that tells you that it is a string. It could just as well be an integer, or something else entirely. An integer is encoded using a variable-length encoding (the same as Thrift’s CompactProtocol).

如果您检查字节序列，您会发现没有东西可以标识字段或它们的数据类型。编码只是将值串联在一起。字符串只是长度前缀后跟UTF-8字节，但编码数据中没有任何东西告诉您它是字符串。它也可以是整数或其他任何东西。整数使用可变长度编码（与Thrift的CompactProtocol相同）。

Figure 4-5. Example record encoded using Avro.

To parse the binary data, you go through the fields in the order that they appear in the schema and use the schema to tell you the datatype of each field. This means that the binary data can only be decoded correctly if the code reading the data is using the exact same schema as the code that wrote the data. Any mismatch in the schema between the reader and the writer would mean incorrectly decoded data.

解析二进制数据时，按照模式中的顺序遍历各个字段，使用模式告诉你每个字段的数据类型。这意味着只有在读取数据的代码与写入数据的代码使用完全相同的模式时，二进制数据才能被正确解码。读者和写者之间模式的不匹配会导致数据解码错误。

So, how does Avro support schema evolution?

那么，Avro如何支持模式演化？

The writer’s schema and the reader’s schema

With Avro, when an application wants to encode some data (to write it to a file or database, to send it over the network, etc.), it encodes the data using whatever version of the schema it knows about—for example, that schema may be compiled into the application. This is known as the writer’s schema .

当一个应用程序想要对一些数据进行编码（写入文件或数据库，通过网络发送等），使用Avro，它会使用任何它知道的模式版本来对数据进行编码 - 例如，该模式可能已编译到应用程序中。这被称为编写者的模式。

When an application wants to decode some data (read it from a file or database, receive it from the network, etc.), it is expecting the data to be in some schema, which is known as the reader’s schema . That is the schema the application code is relying on—code may have been generated from that schema during the application’s build process.

当一个应用程序想要解码一些数据（从文件或数据库中读取，从网络中接收等等），它期望数据以某种模式存在，这被称为读取者模式。这是应用程序代码所依赖的模式，代码可能在应用程序构建过程中从该模式中生成。

The key idea with Avro is that the writer’s schema and the reader’s schema don’t have to be the same —they only need to be compatible. When data is decoded (read), the Avro library resolves the differences by looking at the writer’s schema and the reader’s schema side by side and translating the data from the writer’s schema into the reader’s schema. The Avro specification [ 20 ] defines exactly how this resolution works, and it is illustrated in Figure 4-6 .

Avro的关键思想是，编写者的模式和读者的模式不必相同-它们只需要兼容。当数据被解码（读取）时，Avro库通过并排查看编写者的模式和读者的模式并将数据从编写者的模式转换为读者的模式来解决差异。 Avro规范明确定义了这种解析方式，并在图4-6中进行了说明。

For example, it’s no problem if the writer’s schema and the reader’s schema have their fields in a different order, because the schema resolution matches up the fields by field name. If the code reading the data encounters a field that appears in the writer’s schema but not in the reader’s schema, it is ignored. If the code reading the data expects some field, but the writer’s schema does not contain a field of that name, it is filled in with a default value declared in the reader’s schema.

例如，如果写入者的模式和读者的模式具有不同顺序的字段，也不会有问题，因为模式分辨率通过字段名称将字段匹配起来。如果读取数据的代码遇到出现在写入者模式中但不在读者模式中的字段，则会被忽略。如果读取数据的代码期望某个字段，但写入者的模式中不包含该名称的字段，则会使用读者模式中声明的默认值填充。

Figure 4-6. An Avro reader resolves differences between the writer’s schema and the reader’s schema.

The Merits of Schemas

As we saw, Protocol Buffers, Thrift, and Avro all use a schema to describe a binary encoding format. Their schema languages are much simpler than XML Schema or JSON Schema, which support much more detailed validation rules (e.g., “the string value of this field must match this regular expression” or “the integer value of this field must be between 0 and 100”). As Protocol Buffers, Thrift, and Avro are simpler to implement and simpler to use, they have grown to support a fairly wide range of programming languages.

正如我们所看到的，Protocol Buffers，Thrift和Avro都使用模式来描述二进制编码格式。他们的模式语言比XML Schema或JSON Schema简单得多，但支持更详细的验证规则（例如，“此字段的字符串值必须与此正则表达式匹配”或“此字段的整数值必须在0和100之间”）。由于Protocol Buffers，Thrift和Avro更易于实现和使用，它们已经发展成为支持相当广泛的编程语言。

The ideas on which these encodings are based are by no means new. For example, they have a lot in common with ASN.1, a schema definition language that was first standardized in 1984 [ 27 ]. It was used to define various network protocols, and its binary encoding (DER) is still used to encode SSL certificates (X.509), for example [ 28 ]. ASN.1 supports schema evolution using tag numbers, similar to Protocol Buffers and Thrift [ 29 ]. However, it’s also very complex and badly documented, so ASN.1 is probably not a good choice for new applications.

这些编码所基于的想法并不是新概念。例如，它们与 ASN.1 有很多共同点，这是一种模式定义语言，于 1984 年首次标准化[27]。它被用于定义各种网络协议，其二进制编码（DER）仍然用于编码 SSL 证书（X.509）等[28]。ASN.1 支持使用标签号进行模式演化，类似于 Protocol Buffers 和 Thrift[29]。但是，ASN.1 也非常复杂，文档不完整，因此 ASN.1 对于新应用程序可能不是一个好的选择。

Many data systems also implement some kind of proprietary binary encoding for their data. For example, most relational databases have a network protocol over which you can send queries to the database and get back responses. Those protocols are generally specific to a particular database, and the database vendor provides a driver (e.g., using the ODBC or JDBC APIs) that decodes responses from the database’s network protocol into in-memory data structures.

许多数据系统还实现了某种专有的二进制编码来处理其数据。例如，大多数关系型数据库都有一种网络协议，您可以通过该协议发送查询到数据库并获取响应。这些协议通常是特定于特定数据库的，并且数据库供应商提供了一个驱动程序（例如使用ODBC或JDBC API），该驱动程序将数据库的网络协议解码为内存中的数据结构。

So, we can see that although textual data formats such as JSON, XML, and CSV are widespread, binary encodings based on schemas are also a viable option. They have a number of nice properties:

因此，我们可以看到，尽管JSON、XML和CSV等文本数据格式很常见，但基于模式的二进制编码也是一个可行的选择。它们具有许多优点：

• They can be much more compact than the various “binary JSON” variants, since they can omit field names from the encoded data.

  它们可以比各种“二进制JSON”变体更紧凑，因为它们可以在编码数据中省略字段名称。

• The schema is a valuable form of documentation, and because the schema is required for decoding, you can be sure that it is up to date (whereas manually maintained documentation may easily diverge from reality).

  图表是一种有价值的文档形式，由于解码需要使用图表，所以您可以确信它是最新的（而手动维护的文档可能很容易与现实偏差）。

• Keeping a database of schemas allows you to check forward and backward compatibility of schema changes, before anything is deployed.

  保留模式数据库可以让您在部署任何更改之前对模式进行前向和后向兼容性检查。

• For users of statically typed programming languages, the ability to generate code from the schema is useful, since it enables type checking at compile time.

  对于静态类型编程语言的用户而言，从模式中生成代码的能力是有用的，因为它可以使编译时进行类型检查。

In summary, schema evolution allows the same kind of flexibility as schemaless/schema-on-read JSON databases provide (see “Schema flexibility in the document model” ), while also providing better guarantees about your data and better tooling.

简而言之，模式演化允许与无模式/基于读取的JSON数据库提供的灵活性相同（参见“文档模型中的架构灵活性”），同时提供更好的数据保证和更好的工具。

Dataflow Through Databases

In a database, the process that writes to the database encodes the data, and the process that reads from the database decodes it. There may just be a single process accessing the database, in which case the reader is simply a later version of the same process—in that case you can think of storing something in the database as sending a message to your future self .

在数据库中，写入数据库的进程会对数据进行编码，而读取数据库的进程则会进行解码。有可能只有一个进程访问数据库，在这种情况下，读取进程只是同一进程的一个较新版本。因此，可以将将数据存储在数据库中看作是给自己未来发送一条信息。

Backward compatibility is clearly necessary here; otherwise your future self won’t be able to decode what you previously wrote.

向后兼容性在这里是明显必要的;否则，您未来的自己将无法解码您之前所写的内容。

In general, it’s common for several different processes to be accessing a database at the same time. Those processes might be several different applications or services, or they may simply be several instances of the same service (running in parallel for scalability or fault tolerance). Either way, in an environment where the application is changing, it is likely that some processes accessing the database will be running newer code and some will be running older code—for example because a new version is currently being deployed in a rolling upgrade, so some instances have been updated while others haven’t yet.

一般而言，多个不同的进程同时访问数据库是很常见的。这些进程可能是多个不同的应用程序或服务，或者只是同一个服务的几个实例（同时运行以实现可扩展性或容错性）。无论哪种方式，在应用程序变化的环境中，访问数据库的一些进程可能正在运行较新的代码，而其他进程可能运行原始的较旧的代码，例如因为正在进行滚动升级的新版本，因此某些实例已更新，而其他实例尚未更新。

This means that a value in the database may be written by a newer version of the code, and subsequently read by an older version of the code that is still running. Thus, forward compatibility is also often required for databases.

这意味着数据库中的值可能被新版本的代码写入，而后被仍在运行的旧版本代码读取。因此，对于数据库也经常需要前向兼容性。

However, there is an additional snag. Say you add a field to a record schema, and the newer code writes a value for that new field to the database. Subsequently, an older version of the code (which doesn’t yet know about the new field) reads the record, updates it, and writes it back. In this situation, the desirable behavior is usually for the old code to keep the new field intact, even though it couldn’t be interpreted.

然而，还有一个额外的问题。假设您向记录模式添加一个字段，而新代码向数据库写入该新字段的值。随后，一个不知道新字段的旧版本代码读取记录，更新它，并将其写回。在这种情况下，通常希望旧代码保留新字段的完整性，尽管旧代码无法解释新字段。

The encoding formats discussed previously support such preservation of unknown fields, but sometimes you need to take care at an application level, as illustrated in Figure 4-7 . For example, if you decode a database value into model objects in the application, and later reencode those model objects, the unknown field might be lost in that translation process. Solving this is not a hard problem; you just need to be aware of it.

之前讨论的编码格式支持未知字段的保留，但有时需要在应用程序级别上进行注意，如图4-7所示。例如，如果您在应用程序中将数据库值解码为模型对象，然后稍后重新对这些模型对象进行编码，则该未知字段可能会在翻译过程中丢失。解决这个问题并不困难，你只需要意识到这个问题即可。

Figure 4-7. When an older version of the application updates data previously written by a newer version of the application, data may be lost if you’re not careful.

Dataflow Through Services: REST and RPC

When you have processes that need to communicate over a network, there are a few different ways of arranging that communication. The most common arrangement is to have two roles: clients and servers . The servers expose an API over the network, and the clients can connect to the servers to make requests to that API. The API exposed by the server is known as a service .

当您需要通过网络进行通信时，有几种不同的方式可以安排通信。最常见的方式是有两个角色：客户端和服务器。服务器在网络上公开API，客户端可以连接到服务器以向该API发出请求。服务器公开的API称为服务。

The web works this way: clients (web browsers) make requests to web servers, making GET requests to download HTML, CSS, JavaScript, images, etc., and making POST requests to submit data to the server. The API consists of a standardized set of protocols and data formats (HTTP, URLs, SSL/TLS, HTML, etc.). Because web browsers, web servers, and website authors mostly agree on these standards, you can use any web browser to access any website (at least in theory!).

网络的工作方式：客户端（Web浏览器）向Web服务器发出请求，进行GET请求下载HTML、CSS、JavaScript、图像等，并进行POST请求提交数据到服务器。API由一组标准协议和数据格式（HTTP、URL、SSL/TLS、HTML等）组成。因为Web浏览器、Web服务器和网站作者大多数都同意这些标准，所以理论上你可以使用任何Web浏览器访问任何网站！

Web browsers are not the only type of client. For example, a native app running on a mobile device or a desktop computer can also make network requests to a server, and a client-side JavaScript application running inside a web browser can use XMLHttpRequest to become an HTTP client (this technique is known as Ajax [ 30 ]). In this case, the server’s response is typically not HTML for displaying to a human, but rather data in an encoding that is convenient for further processing by the client-side application code (such as JSON). Although HTTP may be used as the transport protocol, the API implemented on top is application-specific, and the client and server need to agree on the details of that API.

网络浏览器并非唯一的客户端类型。例如，运行在移动设备或台式计算机上的本地应用程序也可以向服务器发送网络请求，而在 Web 浏览器内运行的客户端 JavaScript 应用程序可以使用 XMLHttpRequest 变成 HTTP 客户端（这种技术称为 Ajax [30]）。 在这种情况下，服务器的响应通常不是用于向人显示的 HTML，而是以一种对客户端端应用程序代码进一步处理方便的编码形式呈现的数据（例如 JSON）。虽然 HTTP 可以用作传输协议，但在其上实现的 API 是应用程序特定的，客户端和服务器需要就该 API 的详细信息达成一致。

Moreover, a server can itself be a client to another service (for example, a typical web app server acts as client to a database). This approach is often used to decompose a large application into smaller services by area of functionality, such that one service makes a request to another when it requires some functionality or data from that other service. This way of building applications has traditionally been called a service-oriented architecture (SOA), more recently refined and rebranded as microservices architecture [ 31 , 32 ].

此外，一个服务器本身也可以作为另一个服务的客户端（例如，一个典型的Web应用服务器作为数据库的客户端）。这种方法通常用于按功能区域将大型应用程序分解为较小的服务，其中一个服务在需要另一个服务的功能或数据时向另一个服务发出请求。构建应用程序的这种方式传统上被称为面向服务的架构（SOA），最近被改进和重新品牌为微服务架构[31,32]。

In some ways, services are similar to databases: they typically allow clients to submit and query data. However, while databases allow arbitrary queries using the query languages we discussed in Chapter 2 , services expose an application-specific API that only allows inputs and outputs that are predetermined by the business logic (application code) of the service [ 33 ]. This restriction provides a degree of encapsulation: services can impose fine-grained restrictions on what clients can and cannot do.

有些方面，服务类似于数据库：它们通常允许客户端提交和查询数据。然而，尽管数据库允许使用我们在第2章中讨论的查询语言进行任意查询，但服务公开了一个特定于应用程序的API，只允许输入和输出的数据由业务逻辑（应用程序代码）预先确定[33]。这种限制提供了一定的封装：服务可以对客户端可以和不可以做的事情施加细粒度的限制。

A key design goal of a service-oriented/microservices architecture is to make the application easier to change and maintain by making services independently deployable and evolvable. For example, each service should be owned by one team, and that team should be able to release new versions of the service frequently, without having to coordinate with other teams. In other words, we should expect old and new versions of servers and clients to be running at the same time, and so the data encoding used by servers and clients must be compatible across versions of the service API—precisely what we’ve been talking about in this chapter.

服务导向/微服务架构的一个主要设计目标是通过使服务独立部署和演化来使应用程序更易于修改和维护。例如，每个服务应由一个团队拥有，并且该团队应能够频繁发布该服务的新版本，而无需与其他团队协调。换句话说，我们应该期望旧版和新版服务器和客户端同时运行，因此服务器和客户端使用的数据编码必须在服务API的各个版本中兼容 - 这正是我们在本章中谈论的内容。

Message-Passing Dataflow

We have been looking at the different ways encoded data flows from one process to another. So far, we’ve discussed REST and RPC (where one process sends a request over the network to another process and expects a response as quickly as possible), and databases (where one process writes encoded data, and another process reads it again sometime in the future).

我们一直在研究编码数据从一个进程流向另一个进程的不同方式。到目前为止，我们已经讨论了REST和RPC（其中一个进程通过网络发送请求到另一个进程，并期望尽快得到响应），以及数据库（其中一个进程编写编码数据，而另一个进程在将来的某个时候再次读取它）。

In this final section, we will briefly look at asynchronous message-passing systems, which are somewhere between RPC and databases. They are similar to RPC in that a client’s request (usually called a message ) is delivered to another process with low latency. They are similar to databases in that the message is not sent via a direct network connection, but goes via an intermediary called a message broker (also called a message queue or message-oriented middleware ), which stores the message temporarily.

在这个最后的部分，我们将简要介绍异步消息传递系统，它们介于远程过程调用和数据库之间。它们与远程过程调用相似，因为客户端的请求（通常称为消息）以低延迟交付给另一个进程。它们与数据库相似，因为消息不是通过直接的网络连接发送，而是通过一个中介称为消息代理（也称为消息队列或面向消息的中间件）暂时存储。

Using a message broker has several advantages compared to direct RPC:

使用消息代理与直接RPC相比具有以下几个优点：

• It can act as a buffer if the recipient is unavailable or overloaded, and thus improve system reliability.

  如果接收者不可用或超负荷，它可以起到缓冲作用，从而提高系统的可靠性。

• It can automatically redeliver messages to a process that has crashed, and thus prevent messages from being lost.

  它可以自动将消息重新发送给已崩溃的进程，从而防止消息丢失。

• It avoids the sender needing to know the IP address and port number of the recipient (which is particularly useful in a cloud deployment where virtual machines often come and go).

  这避免了发送方需要知道接收方的IP地址和端口号（这在云部署中尤其有用，因为虚拟机经常会出现变动）。

• It allows one message to be sent to several recipients.

  它可以将一条消息发送给多个收件人。

• It logically decouples the sender from the recipient (the sender just publishes messages and doesn’t care who consumes them).

  它逻辑上将发送者与接收者分离开来（发送者只发布消息，不关心谁消费它们）。

However, a difference compared to RPC is that message-passing communication is usually one-way: a sender normally doesn’t expect to receive a reply to its messages. It is possible for a process to send a response, but this would usually be done on a separate channel. This communication pattern is asynchronous : the sender doesn’t wait for the message to be delivered, but simply sends it and then forgets about it.

然而，与RPC相比的一个区别是，消息传递通信通常是单向的：发送方通常不希望接收其消息的回复。进程可能会发送响应，但通常会在单独的通道上进行。这种通信模式是异步的：发送方不等待消息被传送，而只是发送它并忘记它。

Synchronous Versus Asynchronous Replication

An important detail of a replicated system is whether the replication happens synchronously or asynchronously . (In relational databases, this is often a configurable option; other systems are often hardcoded to be either one or the other.)

复制系统的一个重要细节是复制是同步还是异步发生的。（在关系型数据库中，这常常是一个可配置的选项;其他系统常常是硬编码为其中的一个。）

Think about what happens in Figure 5-1 , where the user of a website updates their profile image. At some point in time, the client sends the update request to the leader; shortly afterward, it is received by the leader. At some point, the leader forwards the data change to the followers. Eventually, the leader notifies the client that the update was successful.

想想在图5-1中发生了什么，其中一个网站用户更新了其个人资料图片。在某个时间点，客户端将更新请求发送给领导者；不久之后，领导者接收到该请求。然后，领导者将数据更改转发给跟随者。最终，领导者会通知客户端更新成功。

Figure 5-2 shows the communication between various components of the system: the user’s client, the leader, and two followers. Time flows from left to right. A request or response message is shown as a thick arrow.

图5-2显示了系统各个组件之间的通信：用户客户端、领导者和两个跟随者。时间从左到右流动。请求或响应消息显示为粗箭头。

Figure 5-2. Leader-based replication with one synchronous and one asynchronous follower.

In the example of Figure 5-2 , the replication to follower 1 is synchronous : the leader waits until follower 1 has confirmed that it received the write before reporting success to the user, and before making the write visible to other clients. The replication to follower 2 is asynchronous : the leader sends the message, but doesn’t wait for a response from the follower.

在图5-2的例子中，向追随者1的复制是同步的：领导者等待追随者1确认接收到写操作，然后才向用户报告成功并使写操作对其他客户端可见。向追随者2的复制是异步的：领导者发送信息，但不等待追随者的响应。

The diagram shows that there is a substantial delay before follower 2 processes the message. Normally, replication is quite fast: most database systems apply changes to followers in less than a second. However, there is no guarantee of how long it might take. There are circumstances when followers might fall behind the leader by several minutes or more; for example, if a follower is recovering from a failure, if the system is operating near maximum capacity, or if there are network problems between the nodes.

这张图表明在跟随者2处理信息之前会有相当大的延迟。通常情况下，复制是相当快的：大多数数据库系统在不到一秒的时间内将更改应用到跟随者上。然而，无法保证需要多长时间。有些情况下，跟随者可能会落后于领导者几分钟或更长时间；例如，如果跟随者正在从故障中恢复、系统接近最大容量运行或节点之间存在网络问题。

The advantage of synchronous replication is that the follower is guaranteed to have an up-to-date copy of the data that is consistent with the leader. If the leader suddenly fails, we can be sure that the data is still available on the follower. The disadvantage is that if the synchronous follower doesn’t respond (because it has crashed, or there is a network fault, or for any other reason), the write cannot be processed. The leader must block all writes and wait until the synchronous replica is available again.

同步复制的好处是，从程序可以保证跟随者拥有与主程序一致的最新数据副本。如果主程序突然故障，我们可以确保数据仍然可用于从程序。缺点是，如果同步从程序没有响应（因为它已崩溃、网络故障或其他原因），则写操作将无法执行。主程序必须阻塞所有写入操作，并等待同步复制再次可用。

For that reason, it is impractical for all followers to be synchronous: any one node outage would cause the whole system to grind to a halt. In practice, if you enable synchronous replication on a database, it usually means that one of the followers is synchronous, and the others are asynchronous. If the synchronous follower becomes unavailable or slow, one of the asynchronous followers is made synchronous. This guarantees that you have an up-to-date copy of the data on at least two nodes: the leader and one synchronous follower. This configuration is sometimes also called semi-synchronous [ 7 ].

因此，所有的跟隨者同步是不切實際的：任何一個節點的停機都會導致整個系統停擺。實際上，如果你在一個數據庫上啟用同步複製，通常意味著其中一個跟隨者是同步的，其他的是非同步的。如果同步跟隨者變得不可用或變慢，一個非同步的跟隨者就會被設置為同步。這可以保證你在至少兩個節點上擁有最新的數據副本：領導者和一個同步跟隨者。這種配置有時候也被稱為半同步（Semi-Synchronous）。

Often, leader-based replication is configured to be completely asynchronous. In this case, if the leader fails and is not recoverable, any writes that have not yet been replicated to followers are lost. This means that a write is not guaranteed to be durable, even if it has been confirmed to the client. However, a fully asynchronous configuration has the advantage that the leader can continue processing writes, even if all of its followers have fallen behind.

通常情况下，基于领导者的复制被配置为完全异步。在这种情况下，如果领导者失败并且无法恢复，则尚未复制到追随者的任何写入都将丢失。这意味着，即使已经确认给客户端，写入也不能保证是持久的。但是，完全异步配置的优点是，即使其所有追随者已经落后，领导者也可以继续处理写入。

Weakening durability may sound like a bad trade-off, but asynchronous replication is nevertheless widely used, especially if there are many followers or if they are geographically distributed. We will return to this issue in “Problems with Replication Lag” .

耐久性的减弱可能听起来像是一个不好的权衡，但是异步复制仍然被广泛使用，特别是如果有许多追随者或者它们在地理上分布。我们将在“复制滞后问题”中回到这个问题。

Setting Up New Followers

From time to time, you need to set up new followers—perhaps to increase the number of replicas, or to replace failed nodes. How do you ensure that the new follower has an accurate copy of the leader’s data?

你需要定期设置新的跟随者，可能是为了增加副本数量，或替换故障节点。你如何确保新的跟随者有准确的领袖数据副本？

Simply copying data files from one node to another is typically not sufficient: clients are constantly writing to the database, and the data is always in flux, so a standard file copy would see different parts of the database at different points in time. The result might not make any sense.

仅仅从一个节点复制数据文件到另一个节点通常是不足够的：客户端不断地向数据库写入数据，数据始终在变化，因此标准的文件复制在不同时间可能看到不同部分的数据库。结果可能毫无意义。

You could make the files on disk consistent by locking the database (making it unavailable for writes), but that would go against our goal of high availability. Fortunately, setting up a follower can usually be done without downtime. Conceptually, the process looks like this:

通过锁定数据库（使其无法写入），您可以使磁盘上的文件一致，但这将违反我们高可用性的目标。幸运的是，通常可以在无需停机的情况下设置跟随者。从概念上讲，该过程看起来像这样：

1. Take a consistent snapshot of the leader’s database at some point in time—if possible, without taking a lock on the entire database. Most databases have this feature, as it is also required for backups. In some cases, third-party tools are needed, such as innobackupex for MySQL [ 12 ].

   在某个时间点拍摄领导数据库的一致性快照——如果可能的话，不要锁定整个数据库。大多数数据库都有这个功能，因为备份也需要这个功能。在某些情况下，需要使用第三方工具，例如 MySQL 的 innobackupex 。[12]。

2. Copy the snapshot to the new follower node.

   将快照复制到新的关注者节点。

3. The follower connects to the leader and requests all the data changes that have happened since the snapshot was taken. This requires that the snapshot is associated with an exact position in the leader’s replication log. That position has various names: for example, PostgreSQL calls it the log sequence number , and MySQL calls it the binlog coordinates .

   跟随者连接到领导者，并请求自快照拍摄以来发生的所有数据更改。这需要将快照与领导者的复制日志中的确切位置相关联。该位置有各种名称：例如，PostgreSQL称其为日志序列号，而MySQL称其为binlog坐标。

4. When the follower has processed the backlog of data changes since the snapshot, we say it has caught up . It can now continue to process data changes from the leader as they happen.

   当追随者处理完自快照之后的数据更改积压时，我们称它已经追上了。现在它可以继续处理来自领导者的实时数据更改。

The practical steps of setting up a follower vary significantly by database. In some systems the process is fully automated, whereas in others it can be a somewhat arcane multi-step workflow that needs to be manually performed by an administrator.

建立跟随者的实际步骤因数据库而异。在某些系统中，该过程完全自动化，而在其他系统中，可能需要管理员手动执行多步神秘的工作流程。

Handling Node Outages

Any node in the system can go down, perhaps unexpectedly due to a fault, but just as likely due to planned maintenance (for example, rebooting a machine to install a kernel security patch). Being able to reboot individual nodes without downtime is a big advantage for operations and maintenance. Thus, our goal is to keep the system as a whole running despite individual node failures, and to keep the impact of a node outage as small as possible.

系统中的任何节点都可能由于故障或计划维护（例如重新启动机器以安装内核安全补丁）而意外关闭。能够在不影响 downtime 的情况下重启个别节点对于操作和维护来说是一个巨大的优势。因此，我们的目标是在个别节点故障时保持整个系统运行，并尽可能减少节点故障的影响。

How do you achieve high availability with leader-based replication?

如何通过基于领导者的复制实现高可用性？

Implementation of Replication Logs

How does leader-based replication work under the hood? Several different replication methods are used in practice, so let’s look at each one briefly.

领导者基础复制如何在幕后运行？在实践中使用了几种不同的复制方法，因此让我们简要地看看每种方法。