Open annidy opened 1 month ago
硬件故障、系统故障、人为错误都无法避免。
Feed流推和拉模式各有优缺点。拉由客户端发起，每次能拿到最新结果，缺点是流量大了很快扛不住；推事先由服务的计算，能承受高并发，缺点是有很多无谓计算。现实中往往两种模式同时结合使用。
mongodb属于文档型数据，根据分类属于关系型数据库。
查询语言分为声明式和命令式。SQL属于声明式；DOM是命令式的很好例子。
OLTP（事务处理）和数仓OLAP（在线分析）：OLTP面向终端用户，有大量的查询任务，所以索引就非常重要；数仓是内部的少量、且查询数据量特别大，数据高效存储重要。 OLTP一般是行存、OLAP一般是列存。
现代的KV数据库会使用LSM树，相比B树写入更快（B树读取更快）。 LSM树是SSTable（排序字符串表）经过压缩与合并的结构，它可以直接写到文件后面，所以写入很快。
在数据库中建立二级索引，需要在额外的空间存储。二级索引不像主键，不需要唯一性，在关系型数据库中反而对开发者透明，NoSQL一般不支持。 二级索引会导致写放大（要更新索引），不建议太多。
相比于磁盘数据库，Redis这种基于内存的能提高更复杂的数据结构（如优先级队列、集合） 磁盘数据库慢不是因为要从磁盘读，而是因为将磁盘数据序列化为内存结构有开销。
pb这种带模式协议对静态语言很友好，如果为动态语言（js）生成代码，反而不灵活。
RPC使用消息代理（Broker），也就是消息队列；
复制的优点：1. 高可用；2. 读写分离提高性能。
复制的一个重要细节是同步or异步复制（还有半同步）。同步复制会让写耗时明显增加，异步复制有数据不一致的问题（一般是秒级，但也可能很久），消除方法有：1. 在主库上读己之写；2. 不要随机读从库
复制的三种实现：基于预写（redo）日志，逻辑（bin）日志，触发器。 预写日志是页的修改，支持事务；逻辑日志记录所有更改数据的SQL语句
Key分区有两种：按范围分区和按哈希分区。按范围需要考虑读写倾斜问题。
分区对只针对主键的查询有很好的表现。对于二级索引查询需要分散/聚集操作，虽然可以并行查询，但尾部延迟放大可能会很明显。一种解决方案是将本地二级索引改为全局索引，然后对这个全局索引分区，避免索引分散/聚集操作。 开源的数据库基本都不支持全局索引
某些数据库提供分区再平衡，建议定期运行。
数据分片（注意措辞，不是分区哦）后客户端请求路由很重要，如果请求到一个错误的分片，可能会造成内网大量带宽占用。一种办法是在zookeeper这种配置中心，维护索引分区与节点映射（有点复杂了）。以上是针对KV，关系型数据库会更复杂。 MySQL等的分区还是在同一台服务器上的，它不是分布式数据库。
事务是简化编程模型而出现的，不是所有情况都需要用事务来解决（比如NoSQL数据库就不支持事务）。 事务具有隔离型，在事务未提交前，其它人看不到所有修改。 但是不是所有支持事务的数据库，都支持事务隔离。很多只是支持回滚，没有解决脏读。 脏读的定义：看到其它事物未提交的数据
MySQL支持4种事务隔离级别，默认是可重复读（Repeatable Read），最强是串行化。
~多对象事务是指更新数据时，还要更新其它。包括：外键（很少用），二级索引等。~
事务不是所有语句都使用行锁，如果需要在事务期间保持某行不可修改，需要使用显示行锁（在SELECT后面加上FOR UPDATE）。 使用ORM框架时，需要注意有没有这个选项，因为一般的ORM框架是不会考虑的。 使用行锁需要注意，锁会阻止其它SQL的读取，因此事务不宜太久。
数据库也有CAS（比较并设置，Compare And Set），在防止多个用户同时更新同一行时有用。实现也很简单，就是先获取旧值，或者在表中单独加一个版本好，在UPDATE的时候添加条件 WHERE=旧值/版本。如果失败就终止或重试，这种模式称之为乐观锁。
事务在提交时会使用两阶段锁（2PL）。2个事务有可能出现死锁，数据库引擎可以检测出这种情况并终止事务。
一切都是不可靠的。计算机科学常常是在不可靠的系统上构建可靠的系统（有点反常识）。
日历时钟通过NTP校准。系统提供的时间API基本上都是日历时钟，单调时钟一般是单调的接口（比如，go提供time.Ticker）
大多数分布式数据库只提供最终一致性，读到不是自己写人的数据通常会在高负载或网络不好时出现，使得问题不容易暴露。
线性一致是一种很强的一致性系统，它概括为当A读到了新值a，那么A后面的所有读取都应该是a。在主从读写分离的场景中，表现是只有一个副本（实际为了高可用会有多个，于是产生了不一致性）
实现线性一致，有几个点需要考虑：
实现线性一致时有代价的，大部分系统并不需要考虑线性一致，或者交给中间件保证（中间件也不一定可靠，会有极小概率事件）
CAP不可能三角：一致性、可用性、分区容忍性（指节点因故障断开后，还可以继续提供服务）。大部分系统都选择CP或AP。比如：AP - Redis；CP - Etcd；极少数使用CA，比如数据库。 BASE是对CAP理论的扩展，是指导开发在一致性和可用性做权衡。包括3个核心思想：1. 基本可用（Basically Available），出现故障后可以响应慢或不一致，但核心功能保证可用；2. 软状态（Soft State），允许数据出现中间状态；3. 最终一致性（Eventually Consistent）
Alice和Bob是两个医生，一个医生是否允许请假的前提是另一个医生是否在岗，在实现时有可能他们同时都请假成功。
线性一致性比较难在现实中应用，而因果一致性相对容易一些。因果一致性的方案有：1. 用知识有向图。这个需要深入业务，不具有普适性；2. 用有向序列号。用时间戳或其它单向向前的表示，类似版本号的东西；3. 全序广播。应用最为成功的方案，节点收到广播后存到日志，通过日志确定顺序。假定广播是按事件的顺序接受到的。
2阶段提交（2PC）是保证事务在多个节点上都成功的一种方法，整个过程分为 write data -> prepare -> commit。发送信息的称为协调者（coordinator），发起事务前，先向协调者申请一个事务ID。当所有节点都prepare后才发送commit，commit发送后不可撤销。（类比西方传统婚礼上，司仪通常是收到双方的“我愿意”后，才宣布情侣成为夫妻）。commit后必须完成提交，即使失败也要重试直到成功，协调者会保存事务ID的状态，以便某些节点崩溃后来查询。 协调者在这里扮演了很重要的角色，如果崩溃，节点会处于_存疑（in doubt）_或_待定（uncertain）_状态，要么节点间自己投票决定是否commit，要么等待超时自动结束事务。（设计难点）
现实中还有3PC、TCC等方案。TCC这种完全不依赖数据库，在业务上保证也是一种流行的解决方案。有的数据库支持分布式事务（MySQL XA），但是因为太慢很少采用。分布式事务框架使用相对易用，比如Seata，可以自动生成回滚SQL
一个共识协议需要满足以下条件：1. 全局一致性（Uniform agreement） 没有任何两个节点最终做出不同决策。2. 正直性（Integrity） 没有任何节点会做出两次决策（不会反复横跳）。3. 有效性（Validity） 如果一个节点做出了决策，该决策所对应的值一定来自系统内某个节点的提议（不能投票弃权）。4. 可终止性（Termination） 任何没有宕机的节点，最终都会给出对某个值的决策。 现实中工业可以的共识算法有 -- VSR、Paxos、Raft和Zab，这些算法的实现会考虑了很多现实中的错误，所以不是完全按学术定义来完成的。不过他们大都使用全序广播这种最基础的消息协议，来保证节点间线性一致性。
三种常见的系统类型：服务（在线系统）、批处理系统（离线系统）和流处理系统（准实时系统） MapReduce延迟比较大，所以归入批处理系统中。
Unix将一切设计为文件，除了BSD套接字。
HDFS在每台机器上允许守护进程，对外暴露网络接口，同时提供本机的存储空间（DataNode），另外还有一个名为NameNode的中央服务器，保存placement信息。 HDFS和对象存储不同点之一是前者能将计算调度到本机。 分布式任务需要把代码上传到节点，比如Jar包。作业调度是一个比执行更复杂的系统工程，类似k8s容器编排。
以KV存储Hadoop的结果，在MapReduce算子中插入数据库不是好的方法，一般是使用SST文件方式批量更新。
Spark、Flink是数据流引擎，因为直接使用MapReduce难度太大，性能不一定好（中间状态落盘。打个比方，MapReduce是Unix中shell结果保存到文件，数据流引擎用的是管道连接）。引擎将整个数据流看做一个任务，而非将其拆分成几个相对独立的子任务。
设计消息系统。1. 如果生产者发送消息的速度比消费者能够处理的速度快会发生什么？-- 取决于产品。一般有3种处理方式：丢弃、放入缓冲队列、背压。2. 如果节点崩溃或暂时脱机，是否允许丢失。
消息队列把消息分发给多个消费者，可以选择负载均衡或扇出（Fan-out）两种模式。 为保证消息不丢失，消费者需要有显示确认（使用日志进行消息存储的，可以通过定期同步偏移来跟踪已处理的消息）。当使用负载均衡模式时，消息可能有乱序。
保持系统同步，有时后用双写解决主从复制慢点问题，但注意双写带来的数据不一致问题。
数据系统的基石
1-1 可靠性、可伸缩性和可维护性
硬件故障、系统故障、人为错误都无法避免。
Feed流推和拉模式各有优缺点。拉由客户端发起，每次能拿到最新结果，缺点是流量大了很快扛不住；推事先由服务的计算，能承受高并发，缺点是有很多无谓计算。现实中往往两种模式同时结合使用。
1-2 数据模型于查询语言
mongodb属于文档型数据，根据分类属于关系型数据库。
查询语言分为声明式和命令式。SQL属于声明式；DOM是命令式的很好例子。
1-3 存储与检索
OLTP（事务处理）和数仓OLAP（在线分析）：OLTP面向终端用户，有大量的查询任务，所以索引就非常重要；数仓是内部的少量、且查询数据量特别大，数据高效存储重要。 OLTP一般是行存、OLAP一般是列存。
现代的KV数据库会使用LSM树，相比B树写入更快（B树读取更快）。 LSM树是SSTable（排序字符串表）经过压缩与合并的结构，它可以直接写到文件后面，所以写入很快。
在数据库中建立二级索引，需要在额外的空间存储。二级索引不像主键，不需要唯一性，在关系型数据库中反而对开发者透明，NoSQL一般不支持。 二级索引会导致写放大（要更新索引），不建议太多。
相比于磁盘数据库，Redis这种基于内存的能提高更复杂的数据结构（如优先级队列、集合） 磁盘数据库慢不是因为要从磁盘读，而是因为将磁盘数据序列化为内存结构有开销。
1-4 编码和演化
pb这种带模式协议对静态语言很友好，如果为动态语言（js）生成代码，反而不灵活。
RPC使用消息代理（Broker），也就是消息队列；
2 分布式数据库
2-5 复制
复制的优点：1. 高可用；2. 读写分离提高性能。
复制的一个重要细节是同步or异步复制（还有半同步）。同步复制会让写耗时明显增加，异步复制有数据不一致的问题（一般是秒级，但也可能很久），消除方法有：1. 在主库上读己之写；2. 不要随机读从库
复制的三种实现：基于预写（redo）日志，逻辑（bin）日志，触发器。 预写日志是页的修改，支持事务；逻辑日志记录所有更改数据的SQL语句
2-6 分区
Key分区有两种：按范围分区和按哈希分区。按范围需要考虑读写倾斜问题。
分区对只针对主键的查询有很好的表现。对于二级索引查询需要分散/聚集操作，虽然可以并行查询，但尾部延迟放大可能会很明显。一种解决方案是将本地二级索引改为全局索引，然后对这个全局索引分区，避免索引分散/聚集操作。 开源的数据库基本都不支持全局索引
某些数据库提供分区再平衡，建议定期运行。
数据分片（注意措辞，不是分区哦）后客户端请求路由很重要，如果请求到一个错误的分片，可能会造成内网大量带宽占用。一种办法是在zookeeper这种配置中心，维护索引分区与节点映射（有点复杂了）。以上是针对KV，关系型数据库会更复杂。 MySQL等的分区还是在同一台服务器上的，它不是分布式数据库。
2-7 事务
事务是简化编程模型而出现的，不是所有情况都需要用事务来解决（比如NoSQL数据库就不支持事务）。 事务具有隔离型，在事务未提交前，其它人看不到所有修改。 但是不是所有支持事务的数据库，都支持事务隔离。很多只是支持回滚，没有解决脏读。 脏读的定义：看到其它事物未提交的数据
MySQL支持4种事务隔离级别，默认是可重复读（Repeatable Read），最强是串行化。
~多对象事务是指更新数据时，还要更新其它。包括：外键（很少用），二级索引等。~
事务不是所有语句都使用行锁，如果需要在事务期间保持某行不可修改，需要使用显示行锁（在SELECT后面加上FOR UPDATE）。 使用ORM框架时，需要注意有没有这个选项，因为一般的ORM框架是不会考虑的。 使用行锁需要注意，锁会阻止其它SQL的读取，因此事务不宜太久。
数据库也有CAS（比较并设置，Compare And Set），在防止多个用户同时更新同一行时有用。实现也很简单，就是先获取旧值，或者在表中单独加一个版本好，在UPDATE的时候添加条件 WHERE=旧值/版本。如果失败就终止或重试，这种模式称之为乐观锁。
事务在提交时会使用两阶段锁（2PL）。2个事务有可能出现死锁，数据库引擎可以检测出这种情况并终止事务。
2-8 分布式系统的麻烦
一切都是不可靠的。计算机科学常常是在不可靠的系统上构建可靠的系统（有点反常识）。
日历时钟通过NTP校准。系统提供的时间API基本上都是日历时钟，单调时钟一般是单调的接口（比如，go提供time.Ticker）
2-9 一致性与共识
大多数分布式数据库只提供最终一致性，读到不是自己写人的数据通常会在高负载或网络不好时出现，使得问题不容易暴露。
线性一致是一种很强的一致性系统，它概括为当A读到了新值a，那么A后面的所有读取都应该是a。在主从读写分离的场景中，表现是只有一个副本（实际为了高可用会有多个，于是产生了不一致性）
实现线性一致，有几个点需要考虑：
实现线性一致时有代价的，大部分系统并不需要考虑线性一致，或者交给中间件保证（中间件也不一定可靠，会有极小概率事件）
CAP不可能三角：一致性、可用性、分区容忍性（指节点因故障断开后，还可以继续提供服务）。大部分系统都选择CP或AP。比如：AP - Redis；CP - Etcd；极少数使用CA，比如数据库。 BASE是对CAP理论的扩展，是指导开发在一致性和可用性做权衡。包括3个核心思想：1. 基本可用（Basically Available），出现故障后可以响应慢或不一致，但核心功能保证可用；2. 软状态（Soft State），允许数据出现中间状态；3. 最终一致性（Eventually Consistent）
Alice和Bob是两个医生，一个医生是否允许请假的前提是另一个医生是否在岗，在实现时有可能他们同时都请假成功。
线性一致性比较难在现实中应用，而因果一致性相对容易一些。因果一致性的方案有：1. 用知识有向图。这个需要深入业务，不具有普适性；2. 用有向序列号。用时间戳或其它单向向前的表示，类似版本号的东西；3. 全序广播。应用最为成功的方案，节点收到广播后存到日志，通过日志确定顺序。假定广播是按事件的顺序接受到的。
2阶段提交（2PC）是保证事务在多个节点上都成功的一种方法，整个过程分为 write data -> prepare -> commit。发送信息的称为协调者（coordinator），发起事务前，先向协调者申请一个事务ID。当所有节点都prepare后才发送commit，commit发送后不可撤销。（类比西方传统婚礼上，司仪通常是收到双方的“我愿意”后，才宣布情侣成为夫妻）。commit后必须完成提交，即使失败也要重试直到成功，协调者会保存事务ID的状态，以便某些节点崩溃后来查询。 协调者在这里扮演了很重要的角色，如果崩溃，节点会处于_存疑（in doubt）_或_待定（uncertain）_状态，要么节点间自己投票决定是否commit，要么等待超时自动结束事务。（设计难点）
一个共识协议需要满足以下条件：1. 全局一致性（Uniform agreement） 没有任何两个节点最终做出不同决策。2. 正直性（Integrity） 没有任何节点会做出两次决策（不会反复横跳）。3. 有效性（Validity） 如果一个节点做出了决策，该决策所对应的值一定来自系统内某个节点的提议（不能投票弃权）。4. 可终止性（Termination） 任何没有宕机的节点，最终都会给出对某个值的决策。 现实中工业可以的共识算法有 -- VSR、Paxos、Raft和Zab，这些算法的实现会考虑了很多现实中的错误，所以不是完全按学术定义来完成的。不过他们大都使用全序广播这种最基础的消息协议，来保证节点间线性一致性。
衍生数据
3-9 批处理
三种常见的系统类型：服务（在线系统）、批处理系统（离线系统）和流处理系统（准实时系统） MapReduce延迟比较大，所以归入批处理系统中。
Unix将一切设计为文件，除了BSD套接字。
HDFS在每台机器上允许守护进程，对外暴露网络接口，同时提供本机的存储空间（DataNode），另外还有一个名为NameNode的中央服务器，保存placement信息。 HDFS和对象存储不同点之一是前者能将计算调度到本机。 分布式任务需要把代码上传到节点，比如Jar包。作业调度是一个比执行更复杂的系统工程，类似k8s容器编排。
以KV存储Hadoop的结果，在MapReduce算子中插入数据库不是好的方法，一般是使用SST文件方式批量更新。
Spark、Flink是数据流引擎，因为直接使用MapReduce难度太大，性能不一定好（中间状态落盘。打个比方，MapReduce是Unix中shell结果保存到文件，数据流引擎用的是管道连接）。引擎将整个数据流看做一个任务，而非将其拆分成几个相对独立的子任务。
3-10 流处理
设计消息系统。1. 如果生产者发送消息的速度比消费者能够处理的速度快会发生什么？-- 取决于产品。一般有3种处理方式：丢弃、放入缓冲队列、背压。2. 如果节点崩溃或暂时脱机，是否允许丢失。
消息队列把消息分发给多个消费者，可以选择负载均衡或扇出（Fan-out）两种模式。 为保证消息不丢失，消费者需要有显示确认（使用日志进行消息存储的，可以通过定期同步偏移来跟踪已处理的消息）。当使用负载均衡模式时，消息可能有乱序。
保持系统同步，有时后用双写解决主从复制慢点问题，但注意双写带来的数据不一致问题。