DDIA第一部分读后感

​ 新开一个坑：阅读完DDIA并做总结。DDIA（data-intensive applications），称为数据密集型应用。这是在字节青训营时了解到的，是一本关于数据处理和数据存储技术的书籍。根据序言说，这本书更偏向于多种数据系统以及存储工具的使用以及场景，而不是具体深入到某种技术当中。我认为该书更多是介绍不同存储数据与处理技术的比较与实践，可以给应用开发提供更多的思路（感觉大多数系统都是在考虑数据存储和处理），另外要说的是，我感觉这本书的定位是一本启蒙读物，有点浅，但知识是挺全面的，适合查漏补缺。

​ 好了，接下来开始讲讲我读完第一部分之后的一个总结（或者说是读后感）吧。该部分主要是对数据库领域的一些基础概念的解释（无论单机还是分布式都适用）。

一 可靠性，可伸缩性和可维护性

​ 该章开头便提出许多程序现在大多数是数据密集型而非计算密集型的，然后描述了数据密集型所需要的标准组件：数据库，缓存，搜索索引，流处理，批处理。依我的认知，常见的对应工具也就是MySQL，Redis，Elastricsearch，Kafka，HDFS…构成一个数据系统。

1.1 关于数据系统的思考

​ 在这里，文章提出了如今数据存储工具和数据处理工具的界限越来越模糊，例如缓存Redis也可以当作消息队列适用，Kafka也可以用作数据库的持久化保证。并给出一张我认为还算全面的数据系统架构图：

​ 在这张图中，可以看由API向客户端隐藏了数据系统的实现细节。那么，如何设计一个好的API（接口），尽力提高其可靠性，可伸缩性，可维护性是本书的一大要点。

1.2 可靠性

​ 程序是否可靠首先最直观的想法认为是：程序表现功能如期望一样，不会出现崩溃以及性能满足，允许犯错，安全。

​ 有三个概念这里需要注意：造成错误的原因称为故障，能预料并且应对故障的系统特性称为容错，系统停止向用户提供服务称为失效。

​ 故障又有以下几种：

硬件故障

​ 这其实很正常…硬盘崩溃，内存出错，机房断电，网线被拔都会造成系统的不可用。为了减少这种故障率，可以有：磁盘构建RAID，双路电源和热插拔CPU，使用后备电源等，总之就是留好后路= =。

软件错误

​ 这类错误往往更容易出现并且造成更多的系统失效，例如：没有进行输入参数校验，访问不恰当的内存区域，依赖服务无响应等等。

​ 解决的方法有：在设计前仔细考虑；测试！；进程隔离；测量、监控。

人为错误

​ 也就是运维了，人是不可靠的，但要使得系统可靠，所使用的方法：精心设计系统（精心设计的抽象，限制接口个数）；解耦，提供沙箱环境进行测试；测试！；快速恢复；明确的监控。

1.3 可伸缩性

​ 可伸缩性是用于描述系统应对负载能力的。所谓负载，这是一种抽象的概念，取绝于系统架构，有可能是请求数，并发数，数据库读写比率，同时活跃用户数等。

​ 这部分讲了twitter对于发推这一操作的两种实现方式：

1. 发送推文时，将新推文插入全局推文集合。当一个用户请求自己主页的时间线，就需要查找所有其关注的人，以及关注的人发布的推文并按时间合并返回。sql如下

   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. 为每个用户的主页时间线维护一个缓存，当一位用户发布了推文，则查询关注自己的所有人，并向其缓存插入新的推文。这种方法数据已经提前计算好了，请求开销小很多

   

​ 前者是一种主动操作，如果用户关注了许多人并且关注者发布推文数大，这无疑让系统难以跟上主页时间线的负载。后者是一种被动操作，由被关注者提前向关注者推送自己的发布推文，从而减少请求时的处理量。

​ twitter采用两种的混合，大多数用户的推文会被扇出写入其粉丝主页时间线缓存中，少数拥有海量粉丝的用户则不会。用户会直接请求所关注的每位“名流”的推文，再与用户主页时间线缓存合并。

​ 如何描述性能？通常对于系统来说，最常见的两个参数也就是吞吐量和响应时间。前者是指每秒处理的记录数量；后者是指客户端发送请求到接受响应之间的时间。（这里注意延迟和响应时间的区别：响应时间会包含延迟：网络延迟和排队延迟等。延迟则是指该请求等待处理的持续时长，在此期间处于休眠状态）

​ 文章接下来讲了应该如何针对不同的情况选择不同的统计方法：

• 算数平均值
• 百分位点
• 中位数

应对负载的方法

​ 采用纵向伸缩（更强大的机器）和横向伸缩（将负载分布到多台小机器上）。

​ 弹性系统，检测到负载增加时自动增加计算资源。

1.4 可维护性

​ 系统不是设计完上线即可，通常大部分开销在持续维护阶段，例如修复漏洞，适配平台，为新场景进行修改，添加新的功能等等。

可操作性

​ 这里的意思是说要保证系统设计尽量是自动化且操作是可观测的。系统应该有良好的监控，自动化工具，避免依赖单台机器，良好的文档以及自我修复能力。

简单性

​ 不用多说，复杂的软件只会增加维护成本。消除复杂度最好的办好就是抽象。

可演化性

​ 业务场景总是在变，需求也在增加，要保证系统可以适应变化，从而出现敏捷开发，诞生了测试驱动开发，重构等。

二 数据模型与查询语言

​ 本章主要阐述数据模型的特点以及之间的比较，有一句话很好：每个层都通过提供一个明确的数据模型来隐藏更低层次中的复杂性。另外，后续也讲了些数据查询语言并比较了其用例。

2.1 关系模型与文档模型

SQL,NOSQL,阻抗不匹配

​ 关系模型也就是我们常说的SQL，数据被组织成关系（表），其中每个关系是元祖（行）的无序集合。

​ 而NoSQL被解释为Not Only SQL，这是由于其可以支持多态的数据模型，有着更好的伸缩性。

​ 这里有一个概念：阻抗不匹配，也就是指模型之间的不连贯。在关系型数据库中，通常需要一个转换层来为业务实现提供帮助，熟悉Java的人可能都会建一个convert的包，或使用MyBatis之类框架来辅助转换。

​ 当然，这里并不是说NoSQL模型就完全减少了应用程序代码和存储层之间的阻抗不匹配，后续会看Json作为数据编码格式也存在问题。

多对一和多对多的关系

​ 这里，有一个有意思的问题：为什么一些业务字段都用ID标识，而不是纯字符串的形式给出（例如地区要记录其ID，而非具体到字符串）？

​ 首先，如果用户界面使用一个文本框输入其信息，使用纯字符串是合理的。但是，对于给出一个地区列表让用户选择，这其实有着一定优势：规范化；更好搜索；易于更新；本地化支持。

​ 在这里，使用ID的好处就体现出来了，ID 可以保持不变，即使它标识的信息发生变化。但是直接存储文本时，对人类有意义的信息会复制在每处使用记录中。使用ID虽然会导致写入开销，但会更加规范化（文章似乎没有具体阐明规范化与非规范化）

文档型数据库与关系型数据库

​ 只阐述数据模型的差异

简化应用代码

​ 如果应用程序的数据具有类似文档的结构，那么使用文档模型会是一个好主意。但文档模型有一定的局限性：例如，不能直接引用文档中的嵌套的项目，而是需要说 “用户 251 的位置列表中的第二项”（很像层次模型中的访问路径）。另外，对于多对多模型，文档模型就不是那么好了。

模式灵活性

​ 文档数据库支持 读时模式（即 schema-on-read，数据的结构是隐含的，只有在数据被读取时才被解释），相应的是 写时模式（即 schema-on-write，传统的关系数据库方法中，模式明确，且数据库确保所有的数据都符合其模式）。

​ 读时模式类似于编程语言中的动态（运行时）类型检查，而写时模式类似于静态（编译时）类型检查。

​ 这里讲了一个点：MySQL它执行 ALTER TABLE 时会复制整个表，这可能意味着在更改一个大型表时会花费几分钟甚至几个小时的停机时间。

查询的数据局部性

​ 文档通常以单个连续字符串形式进行存储，编码为 JSON、XML 或其二进制变体（如 MongoDB 的 BSON）。如果应用程序经常需要访问整个文档（例如，将其渲染至网页），那么存储局部性会带来性能优势。如果将数据分割到多个表中，则需要进行多次索引查找才能将其全部检索出来，这可能需要更多的磁盘查找并花费更多的时间。

2.2 数据查询语言

​ 该种语言分为：声明式查询语言（SQL）和命令式查询语言（IMS，CODASYL）。

​ 命令式告诉计算机以特定顺序执行某些操作，如遍历代码，评估条件，更新变量，并决定是否再循环一遍。

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

​ 在声明式查询语言（如 SQL 或关系代数）中，你只需指定所需数据的模式 - 结果必须符合哪些条件，以及如何将数据转换（例如，排序，分组和集合） - 但不是如何实现这一目标。数据库系统的查询优化器决定使用哪些索引和哪些连接方法，以及以何种顺序执行查询的各个部分。

SELECT * FROM animals WHERE family ='Sharks';

2.2.1 web上的声明式查询

​ 这里举了修改html界面颜色的例子，阐述使用js进行修改和css进行修改，可以发现使用声明式 CSS 样式比使用 JavaScript 命令式地操作样式要好得多。

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

2.2.2 MapReduce查询

​ 这个在6.824第一个lab就有涉及到。MapReduce 是一个由 Google 推广的编程模型，用于在多台机器上批量处理大规模的数据。这里只是讨论了一下MongoDB使用的模型。

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

​ 举例来解释 MapReduce 模型。假设你是一名海洋生物学家，每当你看到海洋中的动物时，你都会在数据库中添加一条观察记录。现在你想生成一个报告，说明你每月看到多少鲨鱼。

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

• 可以声明式地指定一个只考虑鲨鱼种类的过滤器（这是 MongoDB 特定的 MapReduce 扩展）。
• 每个匹配查询的文档都会调用一次 JavaScript 函数 map，将 this 设置为文档对象。
• map 函数发出一个键（包括年份和月份的字符串，如 "2013-12" 或 "2014-1"）和一个值（该观察记录中的动物数量）。
• map 发出的键值对按键来分组。对于具有相同键（即，相同的月份和年份）的所有键值对，调用一次 reduce 函数。
• reduce 函数将特定月份内所有观测记录中的动物数量相加。
• 将最终的输出写入到 monthlySharkReport 集合中。

​ 例如，假设 observations 集合包含这两个文档：

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

​ 对每个文档都会调用一次 map 函数，结果将是 emit("1995-12",3) 和 emit("1995-12",4)。随后，以 reduce("1995-12",[3,4]) 调用 reduce 函数，将返回 7。

三 存储与检索

​ 本章主要讲了：数据库如何存储提供的数据；如何在需要时重新找到数据。这里将研究两大类存储引擎：日志结构的存储引擎，面向页面的存储引擎。

3.1 驱动数据库的数据结构

3.1.1 简单用Bash命令构建的结构

#!/bin/bash
db_set () {
  echo "$1,$2" >> database
}

db_get () {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

​ 这种结构的存储格式是：一个文本文件，每行包含一个逗号分隔的健值对。使用db_set会在其后面追加记录，而db_get会顺序查询直到某个健的出现。可以发现，对写友好但读效率不高。另外，在真正的数据库中，还需要处理并发控制，回收硬盘空间以避免日志无限增长，处理错误与部分写入的记录，建立索引等。

3.1.2 散列索引

​ 其实就是哈希表的思想。在文章讲了字典都是用 散列映射（hash map） 或 散列表（hash table） 实现的。如果数据存储是一个仅追加的文件，那么最简单索引策略就是：保留一个内存中的散列映射，其中每个键都映射到数据文件中的一个字节偏移量，指明了可以找到对应值的位置。

​ 当要将新的键值对追加写入文件中时，还要更新散列映射，以反映刚刚写入的数据的偏移量（这同时适用于插入新键与更新现有键）。当要查找一个值时，使用散列映射来查找数据文件中的偏移量，寻找（seek） 该位置并读取该值即可。

​ 要注意的是，这种方式需要所有的键必须能放入可用内存中，因为散列映射完全保留在内存中。这对于每个键有很多的写操作，但健不多的场景是很友好的。

​ 接下来，考虑如何避免最终用完硬盘空间？文章提出了将日志分段，当日志增长到特定尺寸时关闭当前段文件，就开始写入一个新的段文件，然后对这些段进行 压缩。（压缩意味着在日志中丢弃重复的键，只保留每个键的最近更新）

​ 有几个压缩时的细节要说：

• 由于压缩经常会使得段变得很小（假设在一个段内键被平均重写了好几次），我们也可以在执行压缩的同时将多个段合并在一起；
• 冻结段的合并和压缩可以在后台线程中完成，这个过程进行的同时，我们仍然可以继续使用旧的段文件来正常提供读写请求
• 合并过程完成后，我们将读取请求转换为使用新合并的段而不是旧的段 —— 然后旧的段文件就可以简单地删除掉了。

​ 另外还有些问题：

1. 文件格式：使用二进制格式更快，更简单：首先以字节为单位对字符串的长度进行编码，然后是原始的字符串
2. 删除记录：如果要删除一个键及其关联的值，则必须在数据文件中追加一个特殊的删除记录（逻辑删除，有时被称为墓碑，即 tombstone）。当日志段被合并时，合并过程会通过这个墓碑知道要将被删除键的所有历史值都丢弃掉。（在cmu15445有讲过，扩展hashmap就是这么做的）
3. 崩溃恢复：将每个段的散列映射的快照存储在硬盘上来加速恢复，可以使散列映射更快地加载到内存中。
4. 部分写入记录：数据库随时可能崩溃，包括在将记录追加到日志的过程中。 Bitcask 文件包含校验和，允许检测和忽略日志中的这些损坏部分。
5. 并发控制：由于写操作是以严格的顺序追加到日志中的，所以常见的实现是只有一个写入线程。也因为数据文件段是仅追加的或者说是不可变的，所以它们可以被多个线程同时读取。

​ 为什么仅追加是一个好的设计？而不是直接用新值覆盖旧值。

​ 首先，追加是顺序写入，通常比随机写入要快的多；合并旧段的处理可以避免数据文件随着时间的推移而碎片化的问题；如果段文件是仅追加的或不可变的，并发和崩溃恢复就简单多了。

​ 该种索引的缺点是：散列表必须能放进内存，如果有非常多的键，那是不行的；范围查询效率不高。

3.1.3 SSTables和LSM树

​ 首先来讲SSTables，称作排序字符串表（Sorted String Table）。其和之前的散列索引大同小异，但他会要求键值对的序列按键排序。这有着几个好处：

• 合并文件在文件大于可用内存时也是高效简单的。使用的方法类似多路归并，并排读取多个输入文件，查看第一个键，复制最低的到输出文件即可。（和lc的合并k个子数组思想差不多）。注意的是，几个输入段出现相同的键时应该保留最近段的值。
• 不需要在内存中保存所有键的索引。由于存在单调性，就可以通过二分手段找到。
• 可以将多个段记录为块，并在其写入磁盘时对其进行压缩。

​ 那么，如何构造和维护SSTables呢？

1. 为了保证有序性，在新写入时，需要将其添加到一个平衡树数据结构中。这个内存树有时被称为内存表
2. 当内存表大于某个阈值，将其作为SSTable文件写入硬盘。
3. 收到读请求时，首先在内存表中找到对应的键，没有则去硬盘中寻找，再没有就去下一个旧段中继续寻找。
4. 定时在后台运行一个合并和压缩的进程，以合并段文件并将已覆盖或已删除的值丢弃

​ 这里还要注意系统崩溃的问题，需要维护一个单独的日志，每个写入会被立即追加到这个日志上。这个日志没有按排序顺序，但这并不重要，因为它的唯一目的是在崩溃后恢复内存表。每当内存表写出到 SSTable 时，相应的日志都可以被丢弃。

​ 这里讲到了用SSTables制作LSM树，但这里似乎只是简单提了几句，其实还是有些失望的，因为自己对这东西并不了解，还希望在这里学习下LSM树，只好后续再开篇博文讲讲了。另外，这里还讲了BigTable论文，后面也得看看…

​ 文章这里指出LevelDB 和 RocksDB本质上都用了这种存储结构。Cassandra 和 HBase这种大数据组件也是。并且还说了Lucene是Elastricsearch和Solr使用的一种全文搜索的索引引擎。

性能优化

​ 如果查找数据库中不存在的键，LSM树算法会很慢，可以使用额外的布隆过滤器进行优化。

​ 选择SSTables被压缩和合并的顺序和时间。最常见的选择是 size-tiered 和 leveled compaction。对于 sized-tiered，较新和较小的 SSTables 相继被合并到较旧的和较大的 SSTable 中。对于 leveled compaction，key 范围被拆分到较小的 SSTables，而较旧的数据被移动到单独的层级（level），这使得压缩（compaction）能够更加增量地进行，并且使用较少的硬盘空间。

3.1.4 B树

​ B树保持按键排序的键值对，将数据库分解成固定大小的块（block）或页面（page），传统上大小为 4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为硬盘空间也是按固定大小的块来组织的，每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面 —— 类似于指针，但在硬盘而不是在内存中。

​ 一图以蔽之。例如我们要找251，就需要从200和300之间的一个引用向下搜索，最终，我们将到达某个包含单个键的页面（叶子页面，leaf page），该页面或者直接包含每个键的值，或者包含了对可以找到值的页面的引用。

​ B 树的一个页面中对子页面的引用的数量称为分支因子。分支因子取决于存储页面引用和范围边界所需的空间量，但通常是几百个。

​ 更新：搜索包含该键的叶子页面，更改该页面中的值，并将该页面写回到硬盘（对该页面的任何引用都将保持有效）

​ 添加：找到其范围能包含新键的页面，并将其添加到该页面。如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并更新父页面以反映新的键范围分区

​ 删除：需要牵扯到合并页表等估计。

可靠性

​ 处理异常崩溃：B 树实现通常会带有一个额外的硬盘数据结构：预写式日志（WAL，即 write-ahead log，也称为 重做日志，即 redo log）。这是一个仅追加的文件，每个 B 树的修改在其能被应用到树本身的页面之前都必须先写入到该文件。当数据库在崩溃后恢复时，这个日志将被用来使 B 树恢复到一致的状态。

​ 并发问题：如果多个线程要同时访问 B 树，则需要仔细的并发控制 —— 否则线程可能会看到树处于不一致的状态。这通常是通过使用 锁存器（latches，轻量级锁）保护树的数据结构来完成。

优化

​ 文章中只说了几例

• 使用写时复制方案，而不是覆盖页面并维护 WAL 以支持崩溃恢复。修改的页面被写入到不同的位置，并且还在树中创建了父页面的新版本，以指向新的位置。
• 不存储整个键，而是缩短其大小，来节省页面空间。特别是在树内部的页面上，键只需要提供足够的信息来充当键范围之间的边界。如此，就可以在页面中包含更多的键允许树具有更高的分支因子，因此也就允许更少的层级
• 尽量使叶子页面按顺序出现在硬盘上。但是，随着树的增长，要维持这个顺序是很困难的。相比之下，由于 LSM 树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在硬盘上彼此靠近。
• 额外的指针已被添加到树中。例如，每个叶子页面可以引用其左边和右边的兄弟页面，使得不用跳回父页面就能按顺序对键进行扫描。
• B 树的变体，如B+树。

比较B树和LSM树

LSM树

优：

1. 写入速度更快，因为有着较低的写放大，因为它们顺序地写入紧凑的 SSTable 文件而不是必须覆写树中的几个页面；
2. 可以被压缩得很好，因此通常能比B树产生更小的文件，因为LSM 树不是面向页面的，并且会通过定期重写 SSTables 以去除碎片，所以它们具有较低的存储开销，特别是当使用分层压缩；

缺点：

1. 压缩过程有时会干扰正在进行的读写操作。尽管存储引擎尝试增量地执行压缩以尽量不影响并发访问，但是硬盘资源有限，所以很容易发生某个请求需要等待硬盘先完成昂贵的压缩操作。
2. 压缩的另一个问题出现在高写入吞吐量时：硬盘的有限写入带宽需要在初始写入（记录日志和刷新内存表到硬盘）和在后台运行的压缩线程之间共享。写入空数据库时，可以使用全硬盘带宽进行初始写入，但数据库越大，压缩所需的硬盘带宽就越多。

B树

优：

1. B 树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。这个方面使得 B 树在想要提供强大的事务语义的数据库中很有吸引力：在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在 B 树索引中，这些锁可以直接附加到树上

缺：

1. B 树索引中的每块数据都必须至少写入两次：一次写入预先写入日志（WAL），一次写入树页面本身（如果有分页还需要再写入一次）。在数据库的生命周期中每次写入数据库导致对硬盘的多次写入 —— 被称为 写放大

3.1.5 其他索引结构

​ 前面讲的都是键值索引，类似关系模型中主键索引，用于标识一行。但通常次级索引也很常见，这些索引通常对于有效地执行联接（join）。

​ 次级索引主要的不同是键不是唯一的，即可能有许多行（文档，顶点）具有相同的键。这可以通过两种方式来解决：或者将匹配行标识符的列表作为索引里的值（就像全文索引中的记录列表），或者通过向每个键添加行标识符来使键唯一。无论哪种方式，B 树和日志结构索引都可以用作次级索引。

将值存储在索引中

​ 索引中的键是查询要搜索的内容，而其值可以是以下两种情况之一：它可以是实际的行（文档，顶点），也可以是对存储在别处的行的引用。

​ 在后一种情况下，行被存储的地方被称为 堆文件（heap file），并且存储的数据没有特定的顺序（它可以是仅追加的，或者它可以跟踪被删除的行以便后续可以用新的数据进行覆盖）。堆文件方法很常见，因为它避免了在存在多个次级索引时对数据的复制：每个索引只引用堆文件中的一个位置，实际的数据都保存在一个地方。

​ 在某些情况下，从索引到堆文件的额外跳跃对读取来说性能损失太大，因此可能希望将被索引的行直接存储在索引中。这被称为聚集索引。

​ 在 聚集索引（在索引中存储所有的行数据）和 非聚集索引（仅在索引中存储对数据的引用）之间的折衷被称为 覆盖索引。

多列索引

​ 连接索引，通过将一列的值追加到另一列后面，简单地将多个字段组合成一个键。

​ 多维索引，（没有概念，感觉🌰更好理解）。例如，餐厅搜索网站可能有一个数据库，其中包含每个餐厅的经度和纬度。当用户在地图上查看餐馆时，网站需要搜索用户正在查看的矩形地图区域内的所有餐馆。这需要一个二维范围查询。

​ 这种一个标准的 B 树或者 LSM 树索引不能够高效地处理这种查询。可以使用空间填充曲线将二维位置转换为单个数字，然后使用常规 B 树索引。但通常，，使用特殊化的空间索引，例如 R 树。

全文搜索和模糊索引

​ 目前讲到的索引都是精确查询的，如果需要进行模糊查询。可以使用全文搜索引擎，其允许允许搜索一个单词以扩展为包括该单词的同义词，忽略单词的语法变体，搜索在相同文档中彼此靠近的单词的出现，并且支持各种其他取决于文本的语言分析功能。

​ Lucene 为其词典使用了一个类似于 SSTable 的结构。这个结构需要一个小的内存索引，告诉查询需要在排序文件中哪个偏移量查找键。在 LevelDB 中，这个内存中的索引是一些键的稀疏集合，但在 Lucene 中，内存中的索引是键中字符的有限状态自动机，类似于 trie。这个自动机可以转换成 Levenshtein 自动机，它支持在给定的编辑距离内有效地搜索单词。（我感觉类似于字典树？）

3.2 事务处理还是分析？

​ 事务的概念可以去谷歌= =，一大堆八股讲的更好。有意思的是，这里在引言里说：事务不一定具有 ACID（原子性，一致性，隔离性和持久性）属性。事务处理只是意味着允许客户端进行低延迟的读取和写入 —— 而不是只能定期运行（例如每天一次）的批处理作业。

​ 接下讲了下OLTP和OLAP

​ 在线事务处理（OLTP, OnLine Transaction Processing）：这是指应用程序是交互式的，比如博客文章的评论，游戏中的动作，地址簿中的联系人等等，基本的访问模式仍然类似于处理商业交易。应用程序通常使用索引通过某个键查找少量记录。

​ 在线分析处理（OLAP, OnLine Analytice Processing）：这是就是更多用作数据分析。例如统计一月份每个商店的总收入是多少；在最近的推广活动中多卖了多少香蕉等。

文章给出了下表对比

属性	事务处理系统 OLTP	分析系统 OLAP
主要读取模式	查询少量记录，按键读取	在大批量记录上聚合
主要写入模式	随机访问，写入要求低延时	批量导入（ETL）或者事件流
主要用户	终端用户，通过 Web 应用	内部数据分析师，用于决策支持
处理的数据	数据的最新状态（当前时间点）	随时间推移的历史事件
数据集尺寸	GB ~ TB	TB ~ PB

数据仓库

​ 这一部分是大数据的内容了…我不太懂，就强行理解一波了。

​ 文章说，OLTP数据库和数据仓库是相互独立的。为什么要有数据仓库？因为通常OLTP数据库要求高可用和低延迟，所以一般不会业务分析人员在 OLTP 数据库上运行临时的分析查询，因为这些查询通常开销巨大，会扫描大部分数据集，这会损害同时在执行的事务的性能。

​ 所以就出现数据仓库，从 OLTP 数据库中提取数据（使用定期的数据转储或连续的更新流），转换成适合分析的模式，清理并加载到数据仓库中。将数据存入仓库的过程称为 “抽取 - 转换 - 加载（ETL）”

OLTP数据库和数据仓库之间的分歧

​ 一个数据仓库和一个关系型 OLTP 数据库看起来很相似，因为它们都有一个 SQL 查询接口。然而，系统的内部看起来可能完全不同，因为它们针对非常不同的查询模式进行了优化。现在许多数据库供应商都只是重点支持事务处理负载和分析工作负载这两者中的一个，而不是都支持。

星型和雪花型：分析的模式

​ 在分析型业务中，数据模型的多样性则少得多，许多数据仓库都以相当公式化的方式使用，被称为星型模式。例如在食品零售商处找到的数据仓库。在模式的中心是一个所谓的事实表（在这个例子中，它被称为 fact_sales）。事实表的每一行代表在特定时间发生的事件（这里，每一行代表客户购买的产品）。

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

3.3 列式存储

​ 列式存储背后的想法很简单：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。这种存储有什么好处呢？试想，对于OLTP数据库，存储大都是以面向行的方式进行布局的，在读取大量数据时，存储引擎仍然需要将所有这些行（每个包含超过 100 个列）从硬盘加载到内存中，解析它们，并过滤掉那些不符合要求的列。这可能需要很长时间。

​ 而使用列式存储则可以获取需要的列，可以节省很多工作。

3.3.1 列压缩

​ 除了查询时的工作简化，还可以使用压缩数据进一步降低对硬盘吞吐量的需求。

​ 通常情况下，一列中不同值的数量与行数相比要小得多。可以拿一个有 n 个不同值的列，并把它转换成 n 个独立的位图：每个不同值对应一个位图，每行对应一个比特位。如果该行具有该值，则该位为 1，否则为 0。如果 n 非常小（例如，国家 / 地区列可能有大约 200 个不同的值），则这些位图可以将每行存储成一个比特位。但是，如果 n 更大，大部分位图中将会有很多的零（我们说它们是稀疏的）。

这里讲到了列式存储和列族，其实我一直以为是一样= =，但这是不对的。在每个列族中，它们将一行中的所有列与行键一起存储，并且不使用列压缩。

可以将列族想象成下图

​ 附参考链接五分钟轻松了解Hbase列式存储

3.3.2 列式存储中的排序顺序

​ 在列式存储中，存储行的顺序并不一定很重要。按插入顺序存储它们是最简单的，因为插入一个新行只需要追加到每个列文件。

​ 注意，每列独自排序是没有意义的，因为那样我们就没法知道不同列中的哪些项属于同一行。我们只能在知道一列中的第 k 项与另一列中的第 k 项属于同一行的情况才能重建出完整的行。

​ 这里两句话提了两个排序的技巧吧，只提下栗子：如果查询通常以日期范围为目标，例如上个月，则可以将 date_key 作为第一个排序键。这样查询优化器就可以只扫描上个月的行了，这比扫描所有行要快得多；对于第一排序列中具有相同值的行，可以用第二排序列来进一步排序。

​ 排序顺序的另一个好处是它可以帮助压缩列。

3.3.3 写入列式存储

​ 使用LSM树是一个很好解决方案。所有的写操作首先进入一个内存中的存储，在这里它们被添加到一个已排序的结构中，并准备写入硬盘。内存中的存储是面向行还是列的并不重要。当已经积累了足够的写入数据时，它们将与硬盘上的列文件合并，并批量写入新文件。

​ 查询需要检查硬盘上的列数据和最近在内存中的写入，并将两者结合起来。但是，查询优化器对用户隐藏了这个细节。从分析师的角度来看，通过插入、更新或删除操作进行修改的数据会立即反映在后续的查询中。

3.3.4 聚合：数据立方体和物化视图

​ 数据仓库的另一个值得一提的方面是物化汇总。数据仓库查询通常涉及一个聚合函数，如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果相同的聚合被许多不同的查询使用，那么每次都通过原始数据来处理可能太浪费了。为什么不将一些查询使用最频繁的计数或总和缓存起来？

​ 创建这种缓存的一种方式是物化视图（Materialized View）。在关系数据模型中，它通常被定义为一个标准（虚拟）视图：一个类似于表的对象，其内容是一些查询的结果。（这在MySQL也有吧）

​ 但是当底层数据发生变化时，物化视图需要更新，因为它是数据的非规范化副本。数据库可以自动完成该操作，但是这样的更新使得写入成本更高，这就是在 OLTP 数据库中不经常使用物化视图的原因。在读取繁重的数据仓库中，它们可能更有意义（它们是否实际上改善了读取性能取决于个别情况）。

​ 这里提到一个数据立方体的概念，说实话，这里讲的我没看懂= =。但在数据立方体（Data Cube）里讲的还可以。似乎是前面的数据仓库的星型模型的一种说法…

四 编码与演化

​ 该章开篇说了当数据格式或模式发生变化时，对代码变更通常不会立即完成（如果是在大型应用上），对于服务端可能需要进行滚动升级等，客户端就需要看客户心情了。所以在系统开发要保持双向兼容性：

• 向后兼容：新代码可以读旧数据（好处理，新代码作者肯定知道之前代码咋写的）
• 向前兼容：旧代码可以读新数据（棘手，通常旧版程序忽略数据格式新增部分）

​ 下面说说几种编码数据的格式，格式如何应对模式变化，格式如何为新旧数据提供支持，格式之间如何进行数据通信。

4.1 编码数据的格式

​ 这部分说的还挺有用的，程序通常使用两种形式的数据：

1. 内存中，数据通常保存在对象，结构体，列表，二叉树等常见数据结构中，通过指针进行索引，良好的数据结构也为CPU的高效访问和操作提供了优化
2. 如果要将数据写入文件，或者通过网络发送，需要对数据进行编码为某种字节序列。 由于每个进程都有自己独立的地址空间，一个进程中的指针对任何其他进程都没有意义，所以这个字节序列表示会与通常在内存中使用的数据结构完全不同。

​ 值得注意的是，编码、反序列化、编组都是指到字节序列的转换，解码、反序列化、反编组则相反

4.1.1 语言特定的格式

​ 这是指一些语言自带的编码库或工具，例如Java有序列化器java.io.Serializable，Go也有自己Marshal库等。使用这些库或类很方便，但也会导致一些问题：

• 编码与语言绑定，如果进行数据传输或编码存储，则需要另一个平台的语言与其兼容，相当于和语言绑死了
• 具有安全问题，由于为了恢复相同对象类型的数据，解码过程需要实例化任意类的能力
• 忽略了前向后向兼容性带来的问题
• 效率不高

4.1.2 JSON、XML和二进制编码

​ 对于JSON和XML前者我还用的比较多，毕竟http框架的请求或响应很多都与这个有关，后者我只在配置文件中接触过。JSON，XML和CSV属于文本格式，具有很好人类可读性，但也存在一些问题：

• XML和CSV不能区分数字和字符串。JSON能区分数字和字符串，但不区分整数和浮点数，而且无法指定精度
• JSON在处理大精度数字会存在问题，大于 2^23的整数无法使用 IEEE 754 双精度浮点数精确表示，因此在使用浮点数（例如 JavaScript）的语言进行分析时，这些数字会变得不准确。 twitter用的雪花算法就是这样的，但其采用的策略是 返回的 JSON 包含了两种推特 ID，一种是 JSON 数值，另一种是十进制字符串，以避免 JavaScript 程序无法正确解析数字的问题
• JSON、XML对Unicode字符串有很好的支持，但不支持二进制格式
• JSON、XML有可选的模式支持（这里我没太理解模式是啥意思，感觉大概是数据格式模板？）
• CSV没有任何模式，因此每行和每列的含义完全由应用程序自行定义。如果应用程序变更添加了新的行或列，那么这种变更必须通过手工处理

二进制编码

​ 这种编码的好处就在于占用空间小。这些格式中的一些扩展了一组数据类型（例如，区分整数和浮点数，或者增加对二进制字符串的支持），另一方面，它们没有改变 JSON / XML 的数据模型。特别是由于它们没有规定模式，所以它们需要在编码数据中包含所有的对象字段名称。

​ 下面将JSON和二进制编码对比我觉得还是有点意思的，复制下来吧- -

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

​ 前几个字节如下：

1. 第一个字节 0x83 表示接下来是 3 个字段（低四位 = 0x03）的 对象 object（高四位 = 0x80）。 （如果想知道如果一个对象有 15 个以上的字段会发生什么情况，字段的数量塞不进 4 个 bit 里，那么它会用另一个不同的类型标识符，字段的数量被编码两个或四个字节）。
2. 第二个字节 0xa8 表示接下来是 8 字节长（低四位 = 0x08）的字符串（高四位 = 0x0a）。
3. 接下来八个字节是 ASCII 字符串形式的字段名称 userName。由于之前已经指明长度，不需要任何标记来标识字符串的结束位置（或者任何转义）。
4. 接下来的七个字节对前缀为 0xa6 的六个字母的字符串值 Martin 进行编码，依此类推。

​ 二进制编码长度为 66 个字节，仅略小于文本 JSON 编码所取的 81 个字节（删除了空白）。

4.1.3 Thrift和Protocol Buffers

​ 两者都需要一个模式来编码任何数据。也就是用IDL描述模式

Thrift：

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

Protocol Buffers：

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

​ Thrift 有两种不同的二进制编码格式 ，分别称为 BinaryProtocol 和 CompactProtocol。

​ 先来看前者的

​ 与前面常规二进制编码的区别是：没有字段名 (userName, favoriteNumber, interests)，通过指定字段标签来标识。

​ 再来看CompactProtocol

​ 编码在语义上等同于BinaryProtocol，不同的是通过将字段类型和标签号打包到单个字节中，并使用可变长度整数来实现。数字 1337 不是使用全部八个字节，而是用两个字节编码，每个字节的最高位用来指示是否还有更多的字节。

​ Protocol Buffers

​ 与Thrift 的 CompactProtocol 非常相似

​ 值得注意的是，每个字段被标记为必需或可选，但是这对字段如何编码没有任何影响（二进制数据中没有任何字段指示某字段是否必须）。区别在于，如果字段设置为 required，但未设置该字段，则所需的运行时检查将失败，这对于捕获错误非常有用。

如何应对模式演变？

字段标签

​ 我们知道，每个字段由其标签号码（样本模式中的数字 1,2,3）标识，并用数据类型（例如字符串或整数）注释。

​ 向前兼容性：由于每个字段都有一个号码，如果旧的代码（不知道你添加的新的标签号码）试图读取新代码写入的数据，包括一个新的字段，其标签号码不能识别，它可以简单地忽略该字段。数据类型注释允许解析器确定需要跳过的字节数。这也就是保证了旧代码可以读取由新代码编写的记录。

​ 向后兼容性：只要每个字段都有一个唯一的标签号码，新的代码总是可以读取旧的数据，因为标签号码仍然具有相同的含义。（但要注意，添加一个新的字段，不能设置为必需，如果你要添加一个字段并将其设置为必需，那么如果新代码读取旧代码写入的数据，则该检查将失败，因为旧代码不会写入你添加的新字段，所以，设置为可选的或具有默认值）。

数据类型

​ 这里也就是指改变数据类型（例如int32转int64）如何适应。这里没有讲普遍的解决方案，感觉这也很难做到吧，除非用泛型

​ 对于如果将一个 32 位的整数变成一个 64 位的整数。新代码可以轻松读取旧代码写入的数据，因为解析器可以用零填充任何缺失的位。但是，如果旧代码读取由新代码写入的数据，则旧代码仍使用 32 位变量来保存该值。如果解码的 64 位值不适合 32 位，则它将被截断。

​ 另外关于列表，Protobuf它没有列表或数组数据类型，而是有一个字段的重复标记（repeated），这样的好处是可以将可选（单值）字段更改为重复（多值）字段。读取旧数据的新代码会看到一个包含零个或一个元素的列表（取决于该字段是否存在）。读取新数据的旧代码只能看到列表的最后一个元素。

​ 对于Thriftt 有一个专用的列表数据类型，它使用列表元素的数据类型进行参数化。这不允许 Protocol Buffers 所做的从单值到多值的演变，但是它具有支持嵌套列表的优点。

4.1.4 Avro

​ 之前的我在开发中还多少接触过，这个概念还是第一次见。

​

4.1.5 模式的优点

​ Protocol Buffers、Thrift 和 Avro 都使用模式来描述二进制编码格式。他们的模式语言比 XML 模式或者 JSON 模式简单得多，而后者支持更详细的验证规则（例如，“该字段的字符串值必须与该正则表达式匹配” 或 “该字段的整数值必须在 0 和 100 之间 “）。

​ 尽管 JSON、XML 和 CSV 等文本数据格式非常普遍，但基于模式的二进制编码也是一个可行的选择。他们有一些很好的属性：

• 可以比各种 “二进制 JSON” 变体更紧凑，因为它们可以省略编码数据中的字段名称。
• 模式是一种有价值的文档形式，因为模式是解码所必需的，所以可以确定它是最新的
• 维护一个模式的数据库允许你在部署任何内容之前检查模式更改的向前和向后兼容性。
• 对于静态类型编程语言的用户来说，从模式生成代码的能力是有用的，因为它可以在编译时进行类型检查。

4.2 数据流的类型

​ 只要想将某个数据发送到不共享内存的另一个进程，例如，只要你想通过网络发送数据或将其写入文件，就需要将它编码为一个字节序列。

​ 下面是三种数据在进程之间流动的常见方式：

• 通过数据库
• 通过服务调用
• 通过异步消息传递

4.2.1 数据库中的数据流

​ 在数据库中，写入数据库的过程对数据进行编码，从数据库读取的过程对数据进行解码。

​ 向前兼容性是十分有必要的：因为不同程序服务有的可能运行的是新代码，有的是老代码（这有可能是因为本当前正在部署滚动升级，所以有些实例已经更新，而其他实例尚未更新），这意味着数据库中的一个值可能会被更新版本的代码写入，然后被仍旧运行的旧版本的代码读取。

​ 向后兼容性也是，否则你未来的自己将无法解码你以前写的东西。

​ 这里有一个问题，当较旧版本的应用程序更新以前由较新版本的应用程序编写的数据时，如果不小心，数据可能会丢失。如下图

​ 下面讲了在不同时间写入不同的值，大概就是说数据库对于五年前的数据来说，除非对其进行显式重写，否则它仍然会以原始编码形式存在。也成为：数据的生命周期超出代码的生命周期。

​ 还有归档存储，为数据库创建一个快照，例如备份或加载到数据仓库。在这种情况下，即使源数据库中的原始编码包含来自不同时代的模式版本的混合，数据转储通常也将使用最新模式进行编码。既然你不管怎样都要拷贝数据，那么你可以对这个数据拷贝进行一致的编码。

​ 说实话，这里我没看懂它如何解决上述哪个问题的- -

4.2.2 服务中的数据流：REST和RPC

​ 这大多数人都应该挺熟吧，服务端编写接口，客户端调用。注意到这里说：

• Web 浏览器不是唯一的客户端类型。例如，在移动设备或桌面计算机上运行的本地应用程序也可以向服务器发出网络请求，并且在 Web 浏览器内运行的客户端 JavaScript 应用程序可以使用 XMLHttpRequest 成为 HTTP 客户端
• Web 服务不仅在 Web 上使用，而且在几个不同的环境中使用。如运行在用户设备上的客户端应用程序；一种服务向同一组织拥有的另一项服务提出请求，这些服务通常位于同一数据中心内，作为面向服务 / 微服务架构的一部分；一种服务通过互联网向不同组织所拥有的服务提出请求。这用于不同组织后端系统之间的数据交换。

web服务

​ 这里讲了两种Web服务方法：REST和SOAP，后者没了解过其实。

​ REST 不是一个协议，而是一个基于 HTTP 原则的设计哲学，强调简单的数据格式，使用 URL 来标识资源，并使用 HTTP 功能进行缓存控制，身份验证和内容类型协商。简单来说，这更像是说一种请求风格，通过url进行的。

​ SOAP 是用于制作网络 API 请求的基于 XML 的协议 ，SOAP Web 服务的 API 使用称为 Web 服务描述语言（WSDL）的基于 XML 的语言来描述。 WSDL 支持代码生成，客户端可以使用本地类和方法调用（编码为 XML 消息并由框架再次解码）访问远程服务。

​ 由于 WSDL 的设计不是人类可读的，而且由于 SOAP 消息通常因为过于复杂而无法手动构建，所以 SOAP 的用户在很大程度上依赖于工具支持，代码生成和 IDE。

RPC

​ 这里似乎没有讲明白RPC的思想，反正我是没看懂QAQ。说到底，RPC应该是一个使用网络服务发出请求，让其看起来像是在调用本地方法的一种请求方式吧，感觉RPC的好处在可定制化。

​ 这里突然讲到网络请求与本地函数调用的不同- -，有点懵，虽然RPC和本地函数调用扯上些关系，但说到底也是网络请求调用吧..这里放到前面讲感觉更好。我这里不想抄了，感觉很八股.

​ 不过下面有句话挺好： RPC 框架的主要重点在于同一组织拥有的服务之间的请求，通常在同一数据中心内。这也符合我对RPC和HTTP的认识，前者对内，后者对外。

​ 至于下面数据编码与RPC演化，RPC 方案的前后向兼容性属性从它使用的编码方式中继承。

4.2.3 消息传递中的数据流

​ 与 RPC 类似，因为客户端的请求（通常称为消息）以低延迟传送到另一个进程。它们与数据库类似，不是通过直接的网络连接发送消息，而是通过称为消息代理（也称为消息队列或面向消息的中间件）的中介来临时存储消息。

​ 优点如下：

• 充当缓冲区，提高系统可靠性
• 自动将消息重新发送到已经崩溃的进程，从而防止消息丢失
• 避免发件人需要知道收件人的 IP 地址和端口号
• 允许将一条消息发送给多个收件人
• 将发件人与收件人逻辑分离

消息代理

​ 也就是使用像RabbitMQ，ActiveMQ，Kafka这样的开源组件。消息代理的使用方式如下：一个进程将消息发送到指定的队列或主题，代理确保将消息传递给那个队列或主题的一个或多个消费者或订阅者。在同一主题上可以有许多生产者和许多消费者。

​ 一个主题只提供单向数据流。但是，消费者本身可能会将消息发布到另一个主题上，或者发送给原始消息的发送者使用的回复队列。

​ 消息代理通常不会执行任何特定的数据模型 —— 消息只是包含一些元数据的字节序列，因此你可以使用任何编码格式。如果编码是向后和向前兼容的，可以灵活地对发布者和消费者的编码进行独立的修改，并以任意顺序进行部署。

​