分布式数据库，NOSQL，搜索引擎

分布式数据库

MySQL通过数据库的复制,分片方法实现数据的分布式存储. 一般分分为一主和多主两种模式.



MySQL 一主多从复制



主从复制过程:



关键字：　MySQL Replication







1. 备库执行change master命令,配置主库使用的ip,端口,用户,密码等参数,连接主库,配置binlog路径及偏移量.

2. 备库执行start slave命令, 启动io_thread和sql_thread两个线程

3. 主库校验通过备考的用户密码后, 按照配备库指定的路径下的binlog发送给备库.

4. 备库拿到文件后将binlog写入到本地 中转日志 relay log中.

5. sql_thread读取 relay_log,解析命令并执行.



binlog 格式:

statement　记录语句原句，　总从环境不一致是如可能执行结果不同, 如进行delete主从使用的索引可能不一致.

row：　记录真是操作行的id, 避免上述情况

mixed:　属于前两种情况的折中，　对于可能引起主从不一致的使用row, 否则使用statement

相关问题:

• 问题：

主备延迟：原因主要有 机器性能差， 备库查询,报表较多导致压力大, 大事务的执行(归档类数据,大表)

• 解决方案：

可靠性优先:

通过SBM seconds_behind_master，记录当前备库延迟了多少秒, 可靠性备份步骤

1. 判断 备库的SBM 是否小于某一值(如 5秒)进行主库操作,否则等待;

2. 主库改为只读状态, 把readonly设置为true;

3. 等待备库的SBM值为0, 备库状态改为可读, readonly设置为false;

4. 业务切换到备库

可用性优先:

不等待主备机同步, 直接完成切换, 这时候可能会出现数据不一致. 如果binlog为mixed模式,

1. 主库收到一条数据处理请求1, 同时改为只读, 把readonly设置为true .

2. 备库切换后收到数据处理请求2, 先处理请求2, 同时从relay log里读取处理了请求1;

3. 备库通过binlog将i请求2 同步给主库, 主库执行请求2

4. 主库和备库请求执行顺序相反.



如果binlog为row模式,由于同步的时候记录rows 信息所以, 当主库和备库执行顺序相反时, 主备同步的应用线程会报错 duplicate key error错误从而防止.主备不同步.



可靠性方案的依赖seconds_behind_master, 可用性方案可能导致部分数据不一致



MySQL 主主复制



关键字：　MySQL master master Replication





Circular Replication 循环复制,两个服务器之间进行异步binlog复制, 这种情况下,一般是master节点提供读写, stand-by master提供读操作, master出现故障切换到stanby-master库.

master-standby 模式中mater节点也会有自己的slave , standby主库节点间采用半同步复制, 数据丢失的风险降到最低.

MySQL 主从复制方案

Master with Slaves (Single Replication)





主从结构,主库通过异步或半同步方式同步数据到备库, 主库发生故障从库,从库选一个节点做为主库, 从库其他节点从新的主节点复制数据.

Master with Relay Slaves (Chain Replication)



与第一个个方案相类似,为了减少主节点的复制压力, 增加了中继节点

存在问题:

• 从属中继服务器上的复制滞后将在其所有从属服务器上产生延迟。

• 从属中继服务器上的错误记录将感染其所有从属服务器。

• 如果从属中继服务器发生故障，并且未使用GTID，则其所有从属服务器都将停止复制，并且需要重新初始化它们。



Master with Active Master (Circular Replication)

主主模式循环复制

可能存在问题:

• 每台服务器上设置自动增量偏移，以避免主键冲突。

• 没有解决冲突的方法。

• MySQL复制当前不支持主服务器和从服务器之间的任何锁定协议，以保证跨两个不同服务器的分布式更新的原子性。

• 常见的做法是只写一个主机，而另一个主机充当热备份节点。如果指定的主节点失败，则必须手动切换到新主节点

Master with Backup Master (Multiple Replication)





使用半同步方式保证了主节点和备份主节点之间数据同步, 当主节点发生故障时，执行主节点故障转移时，此拓扑效果很好。 备用主服务器充当热备份服务器，因为与其他从属服务器相比，备用主服务器具有最新数据的可能性最高。



Multiple Masters to Single Slave (Multi-Source Replication)



多源复制可用于将多个主服务器备份到单个服务器，合并表分片



MySQL和MariaDB具有不同的多源复制实现，其中MariaDB必须具有配置了gtid-domain-id的GTID，以区分原始事务，而MySQL为从属服务器复制的每个主服务器使用单独的复制通道。 在MySQL中，可以将多源复制拓扑中的主服务器配置为使用基于全局事务标识符（GTID）的复制或基于二进制日志位置的复制。



Galera with Replication Slave (Hybrid Replication)



混合复制是Galera提供的MySQL异步复制和虚拟同步复制.



数据分片



• 分片的目标 : 并行处理,减少读写压力

• 分片的特点 : 水平扩展,减少故障影响.

• 分片的原理 : 通过硬编码或映射表方式将数据分散到不同数据库中.



硬编码实现数据分片: 根据业务数据特点, 通过具体应用的属性来设置分片

映射表外部存储： 解耦一种方式防止,应用字段调整导致,重新分片处理

数据分片的挑战:



• 需要大量的额外代码，处理逻辑因此变得更加复杂。

• 无法执行多分片的联合查询。

• 无法使用数据库的事务。

• 随着数据的增长，如何增加更多的服务器。



分布式数据库中间件



• MyCat

• Amoeba

• Cobar



部署方案



• 单一服务

• 主从复制

• 多应用多数据库

• 综合部署: 分库分表分片



CAP原理



概念



• 一致性 Consistency：每次读取数据都应该是最近写入数据或反馈一个错误。

• 可用性 Availabiliby：每次请求都应该得到一个响应而不是返回一个错误或者无响应。

• 分区耐受性 Partition tolerance：因为网络原因，部分服务节点之前消息丢失或者延时， 系统仍然可以操作。



对于一个分布式系统而言，网络失效一定会发生， 分区耐受性P存在情况下， 一致性和可用性必须二选一。



最终一致性



最终一致性：通过各种解决方式最终达到一致。



最终一致写冲突解决方案:



• 时间戳覆盖：后来的覆盖之前的。

• 客户端解决冲突：客户端拿到数据后处理 。

• 投票解决冲突（Cassandra）



实例

• Cassandra

• Hbase



ACID和BASE



ACID:传统数据库

• A(Atomicity)：事务要么全部完全，要么全部取消

• I(Isolation): 事务T1和T2同时运行最终结果是相同的，通过锁来实现

• D(Durability): 一旦事务提交，数据要保存到数据库

• C(Consistency): 只有合法的数据才能写入数据库



BASE： NoSQL

• B(Basically Available):允许部分可用

• S(Soft state):允许出现中间状态， 允许系统在不同节点数据副本之间进行数据同步存在延时。

• E(Eventually consistent): 系统中所有副本通过一段时间同步后， 最终达到一致的状态。



分布式一致性



Zookeeper 和分布式一致性架构

脑裂: 一次故障由于网络调整导致两个数据库集群的, 虚拟IP互通导致,数据库无法启动.



数据库主主备份：

zookeeper的分布式一致性保证。



一致性算法Paxos算法。

投票选举模式

• Proposer

• Acceptor

• Learner



三个阶段：

1 Prepare阶段：Propser 向Acceptors发出Prepare请求。 Acceptors针对收到Prepare进行Promise承诺。

1. Accept阶段：Proposer收到Accept.的Promise，向Acceptors发出Propose请求。

2. Learn阶段：



投票要有顺序， Proposal ID 全局递增



Zab 协议

zookeeper使用协议



Zookeeper API



• String create(path, data, acl, flags)

• void delete(path, expectedVersion)

• Stat setData(path, data, expectedVersion) (data, Stat)

• getData(path, watch)

• Stat exists(path, watch) String[] getChildren(path, watch)

• void sync(path) List multi(ops)



配置管理



Administrator • setData(“/config/param1”, "value” ,-1)

Consumer • getData("/config/param1", true)



选主



1. getdata(“/servers/leader”, true)

2. if successful follow the leader described in the data and exit

3. create(“/servers/leader”, hostname, EPHEMERAL)

4. if successful lead and exit

5. goto step 1



集群管理



Monitoring process:

1. Watch on /nodes

2. On watch trigger do getChildren(/nodes, true)

3. Track which nodes have gone away



Each Node:

1. Create /nodes/node-${i} as ephemeral nodes

2. Keep updating /nodes/node-${i} periodically for node status changes (status updates could be load/iostat/cpu/others)



搜索引擎



1. 通过爬虫系统爬到内容,内容去重存储;

2. 基于内容构建倒排索引计算每个页面间的链接关系;

3. 对每个页面进行打分, 基于倒排索引和链接关系进行检索;

4. 构建出一个排序后的页面内容

5. 根据搜索词将页面展示给客户



• 爬虫系统:　

　　爬虫禁爬协议



• 文档矩阵与倒排索引



哪些文档中包含关键词,通过文档矩阵构建倒排索引, 词和文档列表

• 带词频的倒排索引

• 带词频和位置的倒排索引



• Lucene和ElasticSearch



Doris – 海量 KV Engine



产品设计介绍

1. 当前现状:

存在的问题:　

证明设计的产品必要性对现有工作有帮助.

1. 产品针对现状问题的解决

2. 产品目标:

功能目标

非功能目标.

约束

1. 技术指标

集群:

容量:

可用性:

伸缩性,平滑扩容

高性能:



逻辑架构

• 两层架构 Client , DataServer+Store

• 四个核心组件: Client ,DataServer, Store, Administration



概念模型:

• Machine :物理机

• Node: 分区单元,

• Namespace:数据逻辑划分未Tag, Client可识别, 数据管理无需识别.



数据分区：

• 客户端程序自己进行数据分片的选择:

• 解决海量数据存储

• 客户端计算分区

• 分区算法（Partition Policy）

• Client 向 Config Server 抓取分区配置



基于虚拟节点的分区算法



   /**
     * 映射关系算法主要算法过程，构造物理节点到虚拟节点的映射关系
     * 客户端路由一般不需要该方法，server端迁移的时候若以虚拟节点为单位迁移需要调用该方法
     * @param physicalNodesNum 映射关系中物理节点的数目
     * @param virtualNodesNum 映射关系中虚拟节点的数目
     * @return List方式的二维数组，第一维（级）物理节点，第二维（级）是虚拟节点
     */
    public static List<List<Integer>> makeP2VMapping(int physicalNodesNum, int virtualNodesNum) {
        List<List<Integer>> h = new ArrayList<List<Integer>>();
        List<Integer> t = new ArrayList<Integer>();

        for (int i = 0; i < virtualNodesNum; i++) {
            t.add(i);
        }
        h.add(t);
        if (physicalNodesNum == 1) {
            return h;
        }
        for (int k = 2; k <= physicalNodesNum; k++) {
            List<List<Integer>> temp1 = new ArrayList<List<Integer>>();
            List<Integer> temp3 = new ArrayList<Integer>();
            int y[] = new int[k];
            for (int i = 1; i <= k; i++) {
                y[i - 1] = (virtualNodesNum - sumY(y, i - 1)) / (k + 1 - i);// 初始化物理节点内虚拟节点数目
            }
            for (int j = 0; j < (k-1); j++) {
                List<Integer> temp2 = new ArrayList<Integer>();
                
                for (int x = 0; x < h.get(j).size(); x++) {
                    if (x < y[j]) {
                        temp2.add(h.get(j).get(x));
                    } else {
                        temp3.add(h.get(j).get(x));
                    }
                }
                temp1.add(temp2);
            }
            temp1.add(temp3);
            h = temp1;
        }
        return h;

    }

        private static int sumY(int[] y, int i) {
            int sum = 0;
            for (int k = 0; k < i; k++) {
                sum += y[k ];
            }
            return sum;
    }



迭代处理，每一次迭代新增一个物理节点, 从已分配的物理节点取出排在后面的虚拟节点， 将其放到新增的物理节点里 .



如10个虚拟节点映射到3个物理节点。 一共循环三次:

1. 一个物理节点分配 10个, [1..10];

2. 两个物理节点分配各5个 , 从一个节点取出后5个 [1,2,3,4,5] [6,7,8,9,10]

3. 三个物理节点分配3,3,4 个分别从第1,2 个节点取出2个, [1,2,3], [6,7,8], [4,5,8,9,10]



@@add 2020/12/11

对应的数学公式

from http://www2.soopat.com/Patent/201110294092

N: 虚拟节点的个数

M：物理节点的个数

x ： 对应物理节点M从1 开始计数的一个索引。 用于初始化物理节点内虚拟点的值。 通过运算式（M+1-x）标识当前剩余物理节点的数目。

Yx = 存放物理节点中存放虚拟节点的数目.



physicalNodesNum个物理节点分配虚拟节点，依赖physicalNodesNum-1个物理节点的的分配状态。所以是从2个节点开始推导。



初始化： h二维数组， 存放物理节点中虚拟节点的序号。初始化为一个物理节点，其包含所有虚拟节点， 当前只有一个物理节点，直接返回。

        List<List<Integer>> h = new ArrayList<List<Integer>>();
        List<Integer> t = new ArrayList<Integer>();

        for (int i = 0; i < virtualNodesNum; i++) {
            t.add(i);
        }
        h.add(t);
        if (physicalNodesNum == 1) {
            return h;
        }

1. 每次都是从新开始计算分配规则， 减少虚拟节点在物理节点中移动，而且物理节点的数量也是均匀的。

for (int k = 2; k <= physicalNodesNum; k++) {

1. 先计算每个物理节点存放的虚拟节点的个数， 就是把虚拟节点均分到各个物理节点上。 多余的一个放到最后一个节点。

            for (int i = 1; i <= k; i++) {
                y[i - 1] = (virtualNodesNum - sumY(y, i - 1)) / (k + 1 - i);// 初始化物理节点内虚拟节点数目
            }

1. 重新分配物理节点中虚拟节点，保留已分配物理节点中虚拟节点个数存放到temp2，并通过temp1合并到二维数组，按照虚拟节点索引小于虚拟节点数的保留， 大于等于虚拟节点数的部分的放入temp3，存入二维数组的最后。

            for (int j = 0; j < (k-1); j++) {
                List<Integer> temp2 = new ArrayList<Integer>();
                
                for (int x = 0; x < h.get(j).size(); x++) {
                    if (x < y[j]) {
                        temp2.add(h.get(j).get(x));
                    } else {
                        temp3.add(h.get(j).get(x));
                    }
                }
                temp1.add(temp2);
            }



1. 更新映射后的h， h中保留最新的对应关系。



基本访问架构



对等 Node 访问

双写保证可用性（W=2， R=1）

基于分区算法查找两个 Node

• Copy 1 Node

• Copy 2 Node

数据恢复和数据同步

• Redo Log

• Update Log



健康检查和配置抓取

关键技术点



• 临时失效的fail over

• 永久失效额的fail over

• 扩容数据迁移



数据可识别功能 - 逻辑数据结构



数据分组



• Namespace：一个业务实体数据的集合

• Data Definition Namespace的MetaData数据结构定义，满足“数据定义可描述“的需求。



参考及引用



架构师训练营作业-李智慧老师相关讲义

Photo by Vlad Chețan from Pexels

https://medium.com/swlh/zero-downtime-master-slave-replication-4f2814138edf

Mysql实战45讲

https://severalnines.com/resources/database-management-tutorials/mysql-replication-high-availability-tutorial