羽殇之舞的个人博客

聚集索引 非聚集索引：也叫 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 大体思路是： 先算出 logN，在递归次数不超过 logN 的情况下，数据量大一点使用快排，数据量小一点使用希尔排序。 快排本身取 Pivot 哨兵时不采用随机取，而是用 Tukey’s ninther 算法取数组中位数。 当递归次数超过 logN 时，这种数据分布一般就是基本有序的。比如Leetcode 912.排序数组最后的几个测试用例，全 2 或者倒序，快排会达到O(N2)O(N^2)O(N2)的时间复杂度。这时对当前数组进行堆排序。 以上参考自 https://boilingfrog.github.io/2022/03/06/go中的sort包/

这里应该会记录单机数据库内核开发的相关面经。 LRU 算法，LRU 刷盘时一致性的保证 (考虑到宕机的情况) 参考 mysql 你是怎么实现 LRU 的，实现过程中大概用了什么数据结构？ LRU 与 LFU 的区别以及后续的优化 LRU-K 算法、Mysql 的 LRU 有 young、old 区域优化。 实现 B+ 树索引用到了什么数据结构，你能简单说说吗？ 如何从 B+ 树中删除一个节点，并保证树的平衡。 为什么要用 B+ 树而不用其它的树如红黑树？B+ 树有什么优势？什么场景下使用 B+ 树更适合？B+ 树的优缺点是什么？ B-tree、B+tree 对比红黑树 核心在于缓存友好，申请内存操作是耗时的，我们希望次数尽可能少，还希望想找的几条数据最好挨在一起，因此更大节点的 B-tree 会比红黑树更好。 缓存利用率：由于 B+ 树节点较宽，单次磁盘读取可以加载较多的关键字到内存中，这样在进行查找时，每次磁盘 I/O 可以获得更高的关键字命中率，进而提高整体性能。 磁盘 I/O 效率：B 树和 B+ 树设计时考虑到了减少磁盘 I/O 操作的需求，因为它们允许每个节点 ...

按理说，做完了 6.824 理应对 Raft 了如指掌，可那是 11 个月前了，如今的笔者只能依稀记起来 lab 中印象较深的几个坑（其实也记不太清了。 所以可证明，做完 lab ≠\not== 面经全会。 为了让面试官不阴阳怪气\委婉\盛气凌人地跟笔者说——同学，你的项目是有借鉴 Github 吗？——记录一下笔者从各大网站搜罗而来的 Raft 协议面经。 CAP 是什么？Raft 实现了 CAP 中的哪两个 CAP（Consistency, Availability, Partition tolerance）。CA 只有单机实现，毕竟分布式系统必须有 Partition tolerance。 弱一致性——最终一致性（无法实时获取最新更新的数据，但是一段时间过后，数据是一致的） Gossip(Cassandra，Redis 的通信协议) 优先保证 AP 的 CouchDB，Cassandra，DynamoDB，Riak（一个都不了解） 强一致性 Paxos Raft ZAB 还有 Quorum NWR 算法，根据 N、W、R 参数不同有强一致性或者最终一致性的 ...