羽殇之舞的个人博客

简单版简历 Github: feathercyc 邮箱：feathercyc@163.com 教育经历： 2023-现今：硕士，计算机科学与技术，华中科技大学 项目基本信息 项目名称：图数据库 NebulaGraph 对接数据访问层 OpenDAL 项目导师：Suyan 项目描述：OpenDAL 是一个数据访问层，允许用户以统一的方式轻松有效地从各种存储服务中检索数据。目前 OpenDAL 尚未对接图数据库 NebulaGraph，希望通过这个项目完成 NebulaGraph 和 OpenDAL 的对接，让 OpenDAL 能直接访问 NebulaGraph 存储的数据。 项目链接：https://summer-ospp.ac.cn/org/prodetail/241190422 关于 OpenDAL 社区 OpenDAL 是一个数据访问层，其支持以相同的方式访问多种存储后端，旨在减轻开发人员要为每个服务重新实现访问各种存储后端的工作量。 关于 NebulaGraph 社区 NebulaGraph 是图数据库，其以 vertex，edge 和 tag 的形式 ...

聚集索引 非聚集索引：也叫 Secondary Index。指的是叶子节点不按照索引的键值顺序存放，叶子节点存放索引键值以及对应的主键键值。 聚集索引：也称 Clustered Index。是指关系表记录的物理顺序与索引的逻辑顺序相同。由于一张表只能按照一种物理顺序存放，一张表最多也只能存在一个聚集索引。与非聚集索引相比，聚集索引有着更快的检索速度。 非聚集索引与聚集索引应当是要与 Innodb 引擎绑定的，从简易的 CMU15445 数据库以及 Miniob 数据库设计来看，最基本的索引应当是 key 是 col 的值，value 是数据库自己管理的 page index 以及 offset，这里的 value 也可称为行指针。同样的，MyISAM 引擎和简单的 memory 引擎用的都是这种行指针。 在很多地方能看到——MyISAM 引擎用的是非聚集索引——这种奇妙的话。按叶子节点存放索引键值以及对应的主键键值这一定义来看，这显然会导致一个问题——那么主键键值又该怎么访问呢？这句话仅仅考虑了非聚集索引叶子节点不按照索引的键值顺序存放的特点，未免有失偏颇。 MyISAM 这 ...

What I have done add some doc feat: add ci [chore] change some fn’s and variable’s name add some iter type chore: add example and correct README feat: add tests.rs feat: add intervalmap tests chore: change crate name to prepare for cargo publish I have extracted the interval map impl from Xline, refined this part into a crate, added detailed documentation and testing, and published it as rb-interval-map on crates.io. fix: correct request validation chore: transfer utils’s interval map impl i ...

来使用 Nas 搭建一个自动化娱乐设备罢。 购买背景 由于笔者现在电脑设备有好几台，最近出于优化工作流的想法，想把自己的个人资料和一些工作文件丢到一起方便管理；而且笔者去年买的 1TB 和 2TB 固态剩余空间现在都有些捉襟见肘了，想把一些 galgame 和正经游戏丢到机械硬盘里存起来；再而且，笔者也需要一台 24h 运行的性能还过得去的设备来跑一些百度云下载、自己写的爬虫等等的简单任务。 综上所述，奖励自己一台 2k 元的威联通 Nas TS-464c 情有可原。 在此之前，笔者有组过 OpenWrt 软路由和使用树莓派 + 外挂硬盘当文件服务器使用的经历。踩的坑太多了，最近也没什么时间捡垃圾回来自组一台 Nas，索性就买一次成品 Nas。 威联通与群晖是 Nas 老牌厂商了，大家对于群晖的评价是简单易用、高价低配，那么威联通自然就是难用、买硬件送软件的性价比代名词。当然，笔者阅读了大量文章后能感觉出威联通所谓的难用也只是对于计算机小白来说的，对于笔者这种软件开发者而言没什么难度，所以威联通很合笔者口味，当即下单。 实际上，笔者想下单之时（2024 年 6 月 2 日）正好遇上 ...

图数据库 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就可以先隐藏掉 ...

近些年兴起的 NewSQL，Google 在 2012 年发表的 Spanner[8]和 2013 年发表的 F1[9]两篇论文，提出将关系模型和 NoSQL 的扩展性相结合，使之既支持关系模型，又具备高可扩展性。Spanner 和 F1 的出现标志着 NewSQL 的兴起，PingCAP 的 TiDB[10]、CockroachLabs 的 CockroachDB[11]和已经闭源的 OceanBase 都是 NewSQL 的典型产品。TiDB 和 CockroachDB 底层都是基于 RocksDB[12]实现，而 RocksDB 又是在 LevelDB[13]基础上发展的单机 KV 存储引擎。 KV 数据库种类繁多，以 DBEngine 上面列出的为例，就包含 60 多种，虽然种类繁多，但按照其底层的存储模型基本分为四大类，LSM-Tree[14]模型、B/B+Tree 模型、哈希模型和一致性哈希模型。 以 LSM-Tree 为存储模型的 KV 数据库主要有 LevelDB[14]、RocksDB[12]、Badger[15]，以 Btree 为存储模型主要有 LMDB[16]、 ...

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 个前提条件吗？ 回答：互斥条件、请求和保持条件、不可剥夺条件、循环和 ...