1. Structure 1.1 设计目标： 实现一个基于Raft集群的“分布式的，拥有分片功能的，能够加入退出成员的，能够根据配置同步迁移数据的，Key-Value数据库服务” Client：向ShardCtrler请求获得最新的Config，Config中有”数据存在哪“的信息;然后向目标分片ShardKV server发送Put Appand Get请求。 ShardCtrler：管理Config数组，保存有历史版本的配置信息，并且能够根据ShardClient的请求构建新配置，接受请求包括: Query：查询某个版本或者最新版本; Leave：让某些Group离开集群 Join：让某些Group加入集群; Move：强制让某个shard分片移动到指定Group中 ShardServer：由多个Group组成，每个Group保存数据库中的一部分数据分片，所有Group构成一整个数据库。每个组通过RPC向ShardCtrler轮询获取新配置，组与组之间通过RPC按照新配置交换数据分片管理权。 每个Group和ShardCtrler都是分布式的，有底层Raft节点保证 ...

lab3是一个基于Raft的容错KV存储服务 Clerk向k/v service发送三个RPC：Put Append Get，Clerk通过RPC与servers交互。这三种操作都要经过raft层共识添加到log后，再通过applyCh返回给上层的KV server, server再根据applyMsg作出相应动作就可以了。 Get/Put/Append 方法需要是线性的，对外表现是一致的，我理解就是说并发情况下 对外表现的线性一致性： 后一次请求必须看到前一次的执行后端状态；并发请求选择相同的执行顺序，避免不是最新状态回复客户端；在故障之后保留所有确认的客户端更新的方式恢复状态 3A-Key/value service without snapshots基本思路 每个kv service有一个raft peer，Clerks把Get/Put/Append RPC发送给leader的kv service，进一步交给Raft，Raft日志保存这些操作，所有的kv service按顺序执行这些操作，应用到kv数据库，达到一致性 ...

Raft1. Raft简介一种分布式集群内的共识算法 • 相比于Paxos，Raft最大的特性就是易于理解（Understandable）。为了达到这个目标，Raft主要做了两方面的事情： 问题分解：把共识算法分为三个子问题，分别是领导者选举（leader election）、日志复制（log replication）、安全性（safety） 状态简化：对算法做出一些限制，减少状态数量和可能产生的变动。 2. 复制状态机的实现 复制状态机（Replicated State Machine，简称RSM）是一种分布式系统的设计模式。在该模式下，一个服务或应用程序的状态机被复制到多个节点上并行处理，以提高可用性和性能。具体地说，采用复制状态机的系统中，对于某个特定的客户端请求，它将被发送到所有复制的状态机或者其中的一组。然后，每个状态机独立地执行相同的操作序列，并生成相同的结果。最终，生成的结果将会被汇总并返回给客户端。通过这种方式，复制状态机可以将单点故障风险降至最低并提高系统的可靠性。此外，由于并行执行相同的操作序列，该模式还能够提供更好的性能和可伸缩性。 复制状态机是一种常见 ...

GFSCAP理论①Consistency 一致性：所以节点访问同一份最新的数据副本。 ②Availability 可用性：所有读写请求在一定时间内得到非错响应，不会一直等待（但不能保证数据是最新的数据）。 ③Partition tolerance 分区容忍性：在网络分区的情况下，被分隔的节点仍然能够正常对外服务 对于一个分布式系统来说，三者只能取其二。 考虑对于分布式环境，P一定是存在的，没有网络分区和网络波动情况下，正常CAP，当出现网络分区的时候，那么一致性和可用性就要抛弃一个。 PA：存在网络分区，那么网络中的节点之间就有可能数据不一致；比如往节点A中写入数据，B节点由于网络原因没有同步数据过去，如果此时往B节点读取数据是不能读到数据的，所以在存在网络分区的情况下，这个时候如果系统可用，那么数据是不可能保持一致的。 PC：两个节点网络隔离了，想要保证数据一致性只能等待网络恢复，将数据同步，才能读取到数据；也就是说如果想要保证数据强一致性，那么在等待网络恢复的过程中，是不能对外提供服务的，这个时候系统就不可用。 高容错的实现难点： 高性能的要求 导致需要 跨机器对数据分片 大量计算 ...

MapReduce问题理解：过去，处理大量数据的计算时，通常依赖于一台“超级电脑”，但机器计算能力仍然是有限的，这种方式无法解决无限大规模的数据。 MapReduce作为一种分布式并行计算的框架，它主要从分治的角度出发，能够高容错地组织许多一般性能的机器，将大规模问题进行拆解，在并行计算后再做整合，解决了大规模运算的问题。 现实生活中通常应用于一些分治问题： 词频统计 网页抓取 日志处理 查询请求汇总 Hadoop架构中，包含三大组件:分布式文件系统HDFS, 分布式计算组件MapReduce， 资源调度管理系统YARN 组成部分：输入一组kv，生成一组kv。 MAP函数获取一个输入，并且生成一组中间的KV， MapReduce库把与同一中间键i相关联的所有中间值组合在一起，通过迭代器传递给Reduce函数。 Reduce函数接受中间键i和键对应的一组值，把值合在一起，形成一个key更小的值集。一般每次只生成0或1个输出值。 M-R工作基本步骤： 输入文件，MapReduce库分割成M个片段，每个片段16-64MB，然后在一群机器上启动程序的副本 其中一个副本是Maste ...

MySQL必知必会 1. 概述数据库：保存有组织的数据的容器 DBMS：数据库管理系统 表：某种特定类型数据的结构化清单 表名：唯一性， 模式：关于数据库和表的布局及特性的信息； 列：表的一个字段； 数据类型：每个表列都有相应的数据类型； 行：表中的一个记录； 主键：一列，其值能区别表的每个行；一个总是定义主键；唯一性；非空；不更新，不重用，常量 SQL(Structured Query Language)：机构化查询语言，专门用来与数据库通信的语言； 15.联结 外键：表的一列，包含另一个表的逐渐值，定义了两个表之间的关系 关系数据库的可伸缩性好：能适应不断增加的工作量而不失败 联结：机制，用来在一条select语句中关联表，存在在查询的执行中 笛卡尔积 没有联结条件的表关系返回结果为笛卡尔积，没有where限定联结关系 内部联结(等值联结)SELECT vend_name,prod_name,prod_priceFROM vendors,productsWHERE vendors.vend_id = products.vend_idORDER BY vend ...

MySQl是怎么运行的 1.初始部分mysqld 可执行文件 服务器程序服务器相关的mysqld mysqld_safe客户端相关mysql mysqladmin 默认InnoDB 外键支持的功能的事务存储引擎 MyISAM 主要的非事务处理存储引擎 Memory 至于内存的表 CS进程间通信方式 TCP/IP方式： mysql -h127.0.0.1 -uroot -P3306 -p windowOS 的一台主机：命名管道和共享内存 类Unix的一台主机：套接字 服务器处理客户端的查询请求流程连接管理：S端创建线程处理交互； 1.限制连接C端数量；2.断开后线程不销毁，另一个C端连接时分配；3，携带主机各类信息发起连接 ，用SSL通信保证数据传输安全性 解析与优化 查询缓存：MySQL8.0删除，因为维护缓存开销 语法解析：编译过程：词法解析 语法解析 语义分析（编译原理） 查询优化：优化语句，提高效率（类似以扁平化） 存储引擎功能：物理上如何存储、读取、写入、表示记录； 向上提供存储引擎API 默认的存储引擎InnoDB，主要还有MyIS ...

Linux服务器 网络编程 1. Linux系统编程入门GCCgcc和g++都是GCC组织的编译器 ，套件和库；一般用gcc和g++两个编译器 gcc不能自动和cpp程序库链接，一般编译和链接都用g++，因为g++会调用gcc gcc编译c文件 gcc test.c -o app 然后./app其中-o 指明输出文件名 预处理 编译 汇编 链接 -c 只是汇编不链接,生成目标文件“.o” test.o -S 只是编译不汇编,生成汇编代码 test.s -E 只进行预编译,不做其他处理 test.i 后置 ： -D 指定宏 配合#ifdef DEBUG #endifg++ test.cpp -o test -DDEBUG 指定宏DEGUB -I 指定include包含文件搜索目录 -L 指定编译时 库 的路径 -l 指定编译时 使用的 库 库 代码仓库，保存一些变量、函数、类等；编写差不多，但不能单独运行； 静态库在程序的链接阶段被复制到程序中；动态库在程序运行时，加载到内存中供程序调用 好处：1. 代码保密（cpp反汇编还原度低）；2. 方 ...

基础算法1. 快排分治，选一个数，左边都小于等于数，右边都大于等于数，换完之后x不一定在分界点 难点是划分 scanf比流输入快 123456789101112131415161718192021222324252627282930import java.util.Scanner;import java.util.stream.IntStream;public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] arr = IntStream.range(0, n).map(i -> in.nextInt()).toArray(); quick_sort(arr, 0, n-1); IntStream.range(0, n).mapToObj(i -> arr[i] + " " ...

网络是怎样连接的探索浏览器内容生成HTTP请求消息URL(uniform resource locator)统一资源定位符FTP (file transfer protocol)文件传送协议HTTP(hypertext transfor protocol) 超文本传送协议TCP（transmission control protocol）传输控制协议UDP（user datagram protocol）用户数据报协议IP（internet protocol）网络互联协议 浏览器是综合性的客户端软件，需要不同的URL来判断使用哪个功能URL开头部分指明了访问方法 (协议 )； HTTP定义了客户端与服务器之间交互的消息内容和步骤：内容包括：URI(identifier)：存放网页数据的文件名或者CGI程序的文件名 其中CGI(common gateway iterface)通用网关接口 ：web服务器调用其他程序的规则方法：GET POST HEAD OPTIONS PUT DELETE TRACE CONNECT Web服务器对其中内容进行解析，完成工作后，结果存放在响应消息中，包括状 ...