羽殇之舞的个人博客

图数据库 NebulaGraph 对接数据访问层 OpenDAL 申请人介绍 Github: feathercyc 邮箱：feathercyc@163.com 教育经历： 2023-现今：硕士，计算机科学与技术，华中科技大学 Rust 相关经历： Rust 重写 net-tools 的 arp 命令 该项目使用 rust 语言重写 net-tools 的 arp 命令，涉及技术栈有： 使用 clap 库模仿原 C 语言版的 arp 命令的命令行行为 使用 libc、 nix 库调用 Linux 系统调用 过程宏预处理 help 文档 重构 Xline append entries Xline 可简单看作 Rust 版 etcd，该 PR 解决了一个 good-first-issue，优化了 append entries 函数的行为，减少了时间复杂度。 Rust 版区间树 该项目实现了一个高效率的、可用于异步运行时下的区间树供 Xline 项目调用，特点如下： 实现了红黑树完整的插入删除操作 使用数组模拟指针解决红黑树父子节点间需要相互引用的问题 ...

Improve Transaction Validation Project Info Repo: xline-kv/Xline Idea: Improve Transaction Validation Applicant Info Name: Yuchen Chen Github: feathercyc Email: feathercyc@163.com Tel: +86 15616326211 Related PR: refactor: improve append entries Education: 2023-Present: Huazhong University of Science and Technology, Computer Science(master) I really like Rust and Golang, especially Rust has a certain geek flavor. I have just done PingCAP’s tinykv project and am familiar with Raft an ...

如图所示： 考虑STxn-0的put操作（注意，这里的put并不包括STxn-0的子事务如GsTxn-*的put操作），它不应该与图中标为红色的del与put相交，同时，它又可以与图中标为蓝色的del与put相交（换言之，这些背景是绿色的区域需要被排除）。这是因为Then和Else的语义注定了这两个分支只会选择一个执行，所以即使它们重叠了也无所谓。 方案一 首先考虑put与del相交的问题： 最好的办法莫过于构筑一棵包含了所有的del的区间树，然后遍历put进行查询。但如上所说，有一些del是需要被排除的，若是只存区间而不存事务间的父子兄弟关系，这将无法识别该排除什么。考虑到 Xline 作为一个 metadata 数据库，他的事务不应该有很多的嵌套结构以及很多的子事务，使用额外空间存一些信息是应当被允许的。 上面那张图有些复杂，实际上put与del的父子兄弟关系可以简化如下图： 考虑属于STxn-0的Then分支的put，它仍然不能与红色区域内的del相交，但可以与蓝色区域的del相交。 笔者需要解释一下为什么可以这么简化： 目前只考虑del，因此，其他的put就可以先隐藏掉 ...

sort Golang 大体思路是： 先算出 maxDepth = logN，在递归次数不超过 maxDepth 的情况下： 数据量>12 使用快排。 快排本身取 Pivot 哨兵时不采用随机取，而是用 Tukey’s ninther 算法取数组中位数。 否则数据量小一点先使用希尔排序，再插入排序。 当递归次数超过 maxDepth 时，这时对当前数组进行堆排序。因为这种数据分布一般就是基本有序的。比如Leetcode 912.排序数组最后的几个测试用例，全 2 或者倒序，快排会达到O(N2)O(N^2)O(N2)的时间复杂度。 以上参考自 https://boilingfrog.github.io/2022/03/06/go中的sort包/ C++ STL 的 sort 算法与 Golang 基本一致，同样是： 快排递归分段。 一旦分段后的数据量<16，为避免 QuickSort 快排的递归调用带来过大的额外负荷，就改用插入排序。 如果递归层次过深，改用堆排序。 hashmap rehash 方法 渐进式 Rehash：这是一种常用的 ...

这里应该会记录单机数据库内核开发的相关面经。 LRU 算法，LRU 刷盘时一致性的保证 (考虑到宕机的情况) 参考 mysql 你是怎么实现 LRU 的，实现过程中大概用了什么数据结构？ LRU 与 LFU 的区别以及后续的优化 LRU-K 算法、Mysql 的 LRU 有 young、old 区域优化。 实现 B+ 树索引用到了什么数据结构，你能简单说说吗？ 如何从 B+ 树中删除一个节点，并保证树的平衡。 为什么要用 B+ 树而不用其它的树如红黑树？B+ 树有什么优势？什么场景下使用 B+ 树更适合？B+ 树的优缺点是什么？ 详情见 The Difference Between B-Tree, B+Tree, Red-Black Tree, LSM Tree and SkipList。 B+ 树执行操作时是如何加锁的？ 考虑节点分裂和合并 什么时候对内存中的帧 frame bitmap - 1 操作，也就是 unpin？ 看你提到了死锁避免算法，那你说说什么是死锁？ 你知道死锁出现的 4 个前提条件吗？ 回答：互斥条件、请求和保持条件、不可剥夺条件、循环和 ...

按理说，做完了 6.824 理应对 Raft 了如指掌，可那是 11 个月前了，如今的笔者只能依稀记起来 lab 中印象较深的几个坑（其实也记不太清了。 所以可证明，做完 lab ≠\not== 面经全会。 为了让面试官不阴阳怪气\委婉\盛气凌人地跟笔者说——同学，你的项目是有借鉴 Github 吗？——记录一下笔者从各大网站搜罗而来的 Raft 协议面经。 CAP 是什么？Raft 实现了 CAP 中的哪两个 CAP（Consistency, Availability, Partition tolerance）。CA 只有单机实现，毕竟分布式系统必须有 Partition tolerance。对于强调自己可无缝替代 Mysql 的 TiDB，C 是一定要实现的，只有 A 是可以舍弃的，毕竟停止服务怎么说也比转账事务出错好。 弱一致性——最终一致性 无法实时获取最新更新的数据，但是一段时间过后，数据是一致的 笔者浅薄的阅历导致只知道 Gossip 一种最终一致性算法，Consul、Cassandra、Redis、DynamoDB 等等都只是用这个算法来故障检测用的，换言之 G ...

两数之和 题目条件说答案唯一，hash 表存 target-x 即可。 时间：O(N)O(N)O(N)，空间：O(N)O(N)O(N) 三数之和 基本思路是遍历数组对每个值求两数之和，易知时间复杂度必为O(N2)O(N^2)O(N2)。 题目要求答案不可重复，但是数组中会出现重复值，如[1,2,-3,2]，使用 hash 表扫一遍还要去重，所以不使用 hash 表。 因此先排序，再使用双指针从两端遍历，双指针可以跳过重复的值。 时间：O(NlogN)O(NlogN)O(NlogN)+O(N2)O(N^2)O(N2)=O(N2)O(N^2)O(N2)，空间：O(1)O(1)O(1) 四数之和 I 四数之和 II 最大连续子序（子数组）和 给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 DP DP 最优，遍历一遍，直观理解是当前序列之和<0 就可以从下一个大于 0 的元素开始继续遍历，转移方程为： f(i)=max{f(i−1)+nums[i],nums[i]}f(i)=max\{f(i-1)+nums[i], ...

第一次整软路由，笔者正处于大创报账时期，虽然不知道能不能报上去，反正挑了个合适价位的 J1900 的软路由买回来一阵折腾。由于怀着着折腾的心思，买的是裸主机，这意味着内存和硬盘都没有自带，同时 openwrt 系统就更不用说了，肯定得自己装上去。在收货当天笔者就开始了各项工作，结果还是花了好几天踩坑才将一切搞定，故记下这次极其耗神的工作。 软路由是什么 按笔者目前理解，软路由就是一台至少带了多个网口的过时主机，CPU、内存、硬盘等基本一应俱全。笔者手里这台就是 J1900CPU、四网口的一台软路由，双十二期间价钱 720+ 就拿下来了。 拥有复数个网口后，只要在主机上装一个 openwrt 系统，再给网口分配 LAN 口和 WAN 口，这台主机就是软路由了。换言之，只要有两个网口，任何电脑都可以改成软路由，只是功耗等不尽相同罢了。 与软路由相对的就是——硬路由，也就是一般我们称呼的路由器，软路由一般应用在有线网中，至于无线网则会靠额外连接一个无线 AP 来实现，而硬路由则集成这两项功能且更简单易用，当然价钱多少会高上一点。 J1900 路由器介绍 先来张内部结构图： 图中的已经 ...