Posts

Raft篇-1 raft库只实现核心的raft算法部分，使用raft库时，用户需要自己实现其中的网络传输以及存储，以分别支持raft节点内部的通信和raft log的持久化等。 raftexample是etcd库中一个使用raft库的例子，其中实现了上述所需的网络传输和存储能力，以及提供了http服务给外部调用，包括读写数据等。 从raftexample的实现来看etcd是怎么设计和实现raft协议的。 启动结构 newRaftNode(*id, strings.Split(*cluster, ","), *join, getSnapshot, proposeC, confChangeC) newKVStore(<-snapshotterReady, proposeC, commitC, errorC) serveHttpKVAPI(kvs, *kvport, confChangeC, errorC) newRaftNode：启动raft node节点，raft算法核心实现部分 newKVStore：每个节点的存储实现 serveHttpKVAPI：提供给外部的http接口，提供读写数据，增删节点能力（这个不是raft node节点之间的通信实现） 写入数据 首先在raftexample文档中可以看到写入数据是通过PUT请求实现的 curl -L http://127.0.0.1:12380/my-key -XPUT -d foo PUT实现如下： // contrib/raftexample/httpapi.go#L36 case r.Method == "PUT": h.store.Propose(key, string(v)) // Propose函数实现 // contrib/raftexample/kvstore.go#L70 s.proposeC <- buf.String() 最终是往 kvstore 的 proposeC channel中写入了数据，这个proposeC就是在启动时同时给raft node和kvstore用于初始化的channel。因此粗略得到如下关系图 处理proposeC的流程 // contrib/raftexample/raft.go#L402 func (rc *raftNode) serveChannels() { // ... for rc.proposeC != nil && rc....

MySQL undo日志实验 背景：在学习undo日志时，看到一个观点： 对于update操作的undo日志，不更新主键的情况下： 如果被更新的列占用的存储空间未发生变化，则就地更新 如果被更新的列占用的存储空间发生改变，变大或变小，则先删除后插入，并且该删除时直接删除，而不是标记删除 因此本文浅浅实验下，在上述两种情况下的表空间变化，以及undo日志，并看下回滚是如何操作的。 环境 MySQL版本： mysql> select version(); +-----------+ | version() | +-----------+ | 8.0.29 | +-----------+ 1 row in set (0.00 sec) 实验步骤概述 创建表使用varchar字段 添加记录，查看表空间该行数据 更新该记录，但是长度相同 查看表空间该行数据 查看undo日志内容 回滚更新操作，再次查看表空间 删除表重建 添加记录，查看表空间该行数据 更新该记录，但是长度变大 查看表空间该行数据 查看undo日志内容 回滚更新操作，再次查看表空间 删除表重建 添加记录，查看表空间该行数据 更新该记录，但是长度变小 查看表空间该行数据 查看undo日志内容 回滚更新操作，再次查看表空间 数据准备 create table test_undo( id int, name varchar(10), primary key (id) )engine=innodb charset=utf8 row_format=dynamic; 使用utf8编码，使用默认的dynamic行格式。 insert into test_undo values (1,'aaa'),(2,'xxx') 插入两条数据，这里为了区分先删除再插入和原地更新，需要插入两条数据，然后我们操作第一条。 mysql> select TABLE_ID from information_schema....

InnoDB索引 单机InnoDB InnoDB磁盘相关介绍 InnoDB-架构图 InnoDB存储引擎是基于磁盘存储的，并将其中的记录按页的方式管理。InnoDB在内存中创建一个缓冲池，当进行读取页操作时，首先将从磁盘读到的页存放在缓冲池中。下一次再读到相同的页时，首先判断该页是否在缓冲池中。若在缓冲池中，则在缓冲池中直接读取该页即可；否则，读取磁盘上的该页。当进行修改操作时，首先修改在缓冲池中的页，然后再以一定的频率刷新到磁盘上。页从缓冲池中被刷回磁盘的操作并不是在每次页发生更新时触发，而是通过checkpoint的机制触发刷回。 InnoDB表空间结构 InnoDB-逻辑存储结构 在innodb存储引擎中，表都是根据主键顺序组织存放的，这种存储方式的表称为索引组织表。在innodb存储引擎中，每张表都有个主键，如果在创建表时没有显示地定义主键，则innodb存储引擎会使用表中非空的唯一索引或自动创建一个6字节大小的指针。 innodb存储引擎中，所有数据都被逻辑地存放在表空间（tablespace）中，表空间由段（segment）、区（extent）、页（page）组成。 表空间只存放数据、索引和插入缓冲bitmap页，其他比如回滚信息、插入缓冲索引页等存放在共享表空间中。 段包括数据段、索引段、回滚段等。数据段即为B+树的叶子节点，索引段即为B+树的非叶子节点。 区是由连续页组成的空间，每个区的大小都为1MB。默认情况下，innodb存储引擎页的大小为16KB，即一个区有64个连续的页。 页是innodb磁盘管理的最小单位，常见有数据页、undo页等。 ibd文件分析 表文件结构 FSP_HDR/XDES 在idb文件的第一个页的类型为FSP_HDR，该page主要用于存储表空间的一些关键信息。 FSP_HDR结构 与其他所有页一样，FSP_HDR也是页，因此同样存在页头FIL_HEADER以及页尾FIL_TRAILER FIL Header/Trailer 页头、页尾结构 名称(fil0types.h) 含义 FIL_PAGE_SPACE_OR_CHKSUM 表示页的校验和 FIL_PAGE_OFFSET 页号 FIL_PAGE_PREV 逻辑上前一个页.在page0中，该字段为FIL_PAGE_SRV_VERSION FIL_PAGE_NEXT 逻辑上后一个页.在page0中，该字段为FIL_PAGE_SPACE_VERSION FIL_PAGE_LSN 该页最后被修改时的LSN FIL_PAGE_TYPE 页类型 FIL_PAGE_FILE_FLUSH_LSN 仅在系统表空间的第1页定义，代表文件至少被刷新到该LSN值 FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID 页所在表空间id FIL_PAGE_END_LSN_OLD_CHKSUM 前4个字节表示检验和，后4个字节应当与FIL_PAGE_LSN后4个字节相同 FSP Header FSP Header结构 名称(fsp0fsp.h) 含义 FSP_SPACE_ID 表空间id FSP_SIZE 当前表空间拥有的页面数 FSP_FREE_LIMIT（？） 尚未被初始化的最小页号,大于等于该页号的区对应的XDES Entry结构都没有加入到FREE链表中.在小于64个页的表空间中，该值为64 FSP_SPACE_FLAGS 存储标志 FSP_FRAG_N_USED FSP_FREE_FRAG链表中已使用的页面数量 FSP_FREE 空闲extents的基节点，该链上的extent所有page均未被使用，可以整个extent分配给segment，或使用部分碎片页并移动到FSP_FREE_FRAG链 FSP_FREE_FRAG FREE_FRAG链表的基节点，该链上的extent存在空闲页，通常这样的extent中的page，会分配到不同的segment，挂在segment的FSEG_FRAG_ARR上。比如每个带了FSP_HDR页或XDES页的extent就是FSP_FREE_FRAG的 FSP_FULL_FRAG FULL_FRAG链表的基节点，该链上的extent没有空闲page，当该extent上有page被释放后，可以移回FSP_FREE_FRAG链 FSP_SEG_ID 当前表空间中下一个未使用的SegementID,即下次待分配的SegmentID FSP_SEG_INODES_FULL SEG_INODES_FULL链表的基节点，该链上的INODE页已经没有空闲INODE Entry了，一个INODE页最多存放85个INODE Entry。在独立表空间中，当为一个表创建超过42个索引，才会出现FULL的INODE页 FSP_SEG_INODES_FREE SEG_INODES_FREE链表的基节点，该链上的INODE页存在空闲的INODE Entry XDES Entry XDES 指一个page...

找出数组的第 K 大和 题目描述 给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。 数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复） 返回数组的 第 k 大和 。 子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。 注意：空子序列的和视作 0 。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-the-k-sum-of-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 示例 1： 输入：nums = [2,4,-2], k = 5 输出：2 解释：所有可能获得的子序列和列出如下，按递减顺序排列： 6、4、4、2、2、0、0、-2 数组的第 5 大和是 2 。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-the-k-sum-of-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 第k小子序列 首先考虑非负数组的情况下，然后求第k小的子序列的问题。 我们定义一个二元组(sum,i)，表示和为sum，结尾为i(第i位不算)的子序列。然后维护一个小根堆，每次取出堆顶，即sum最小的元素，然后将第i位的元素，考虑第i-1位元素选或者不选，将(sum+arr[i],i+1)和(sum+arr[i]-arr[i-1],i+1)添加到堆中，操作k次，第k次取出来的堆顶就是第k小的子序列。 考虑如下序列【1,2,4,8】，我们知道他的子序列和范围为0~15 注意观察图例中的二进制表示，可以发现对于第i位，比如8，这一列产生的数字的二进制第4位都是1，表示这个数被选择，即对应sum+arr[i]。然后可以发现数字15和11是由7产生而来，而11=7+8-4，即表示第i-1个数我们不取，即对应sum+arr[i]-arr[i-1]。可以看到对于第i位数字，他产生的那列数字，对应的第i为都是1的，这是因为在其之前的数字，第i为都是0，即已经将低位全部考虑完全了。 进一步我们知道一个长度为n的数组，其子序列个数为2^n，也即对应了二进制的表示情况 考虑负数情况 上述我们已经知道如何求一个非负数组的第k小子序列了，那么我们回到本题，考虑负数的情况。 首先这题要求的是第k大子序列和，可以转化为【最大的子序列和-第k小的子序列和】 首先最大的子序列和sum，即为数组中所有非负元素的和。当需要求比最大子序列和更小的子序列和时，相当于从sum中减去一些正数或者加上一些负数，因此将负数取绝对值，统一转化成减去一些正数的做法，然后对正数的数组求第k小的子序列和。 求第k小子序列和 同理，如果这题要求的是第k小的子序列和，那么我们同样可以转化为【最小的子序列和+第k小的子序列和】，同样，当需要求比最小子序列和更大的子序列和时，相当于给sum加上一些正数或者减去一些负数，同样将负数取绝对值，统一转化成加上一些正数的做法。 code typedef long long LL; class Solution { public: long long kSum(vector<int>& nums, int k) { priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>> pq; LL sum=0; for(int i=0;i<nums....

重新排列后的最大子矩阵 题目描述 给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的 列 按任意顺序重新排列。 请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。 示例 1： 输入：matrix = [[0,0,1],[1,1,1],[1,0,1]] 输出：4 解释：你可以按照上图方式重新排列矩阵的每一列。 最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。 示例 2： 输入：matrix = [[1,0,1,0,1]] 输出：3 解释：你可以按照上图方式重新排列矩阵的每一列。 最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。 示例 3： 输入：matrix = [[1,1,0],[1,0,1]] 输出：2 解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。 示例 4： 输入：matrix = [[0,0],[0,0]] 输出：0 解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/largest-submatrix-with-rearrangements 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 对于每个单元格，从下往上统计连续1的个数 遍历数组，对于每一行，按之前统计数量降序排序 维护最小高度，遍历计算面积 code func largestSubmatrix(matrix [][]int) int { // 从下往上统计连续1的个数，作为高度 for i := 1; i < len(matrix); i++ { for j := 0; j < len(matrix[i]); j++ { if matrix[i][j] !...