Key-Value数据库实现Part 1:什么是Key-Value数据库

2022-04-11 00:00:00 数据 数据库 代码 自己的 项目

1.KV数据库速览

  这部分旨在简短的介绍K-V数据库,更详细的描述可以参考文章下方的引用部分。

  K-V存储系统是简单的数据库类型之一。几乎所有的编程语言都带有内置的K-V存储功能。比如C++中STL的map,Java的HashMap,Python的dictionary。K-V数据库通常包含下列接口:

  • Get(key): 获取之前以"key"作为标识存储的数据,若"key"不存在则获取失败。
  • Set(key,value): 将"value"存储内存中,其标识符为"key",以便我们之后可以用"key"来获取数据。如果在"key"下已经有数据了,那么原数据将被替换。
  • Delete(key): 删除"key"标识下的数据。 

  大多数底层的实现都使用了hash table或者是自平衡的树结构(比如B-Tree和红黑树)。有时候数据太大了无法放在内存中,或者为了防止宕机必须把数据持久化,这种情况下,就必须使用文件系统来存储。 

  K-V数据库是NoSQL运动的一部分,它重组了没有完全使用关系数据库中概念的众多数据库,Wikipedia articles on NoSQL  总结了这些数据库的主要特点:

  • 不使用SQL查询语言
  • 可能不对ACID规范提供完全支持
  • 可能提供分布式,可容错的架构

 

2.K-V数据库和关系型数据库

  不同于关系型数据库,K-V数据库并不清楚存储数据的值,而且也没有像MySQL和PostgreSQL中schema的概念。这也就意味着它不能像关系型数据库一样通过

使用带where的SQL语句来过滤并查询所存数据的部分内容。如果你不知道该从哪查询,你需要遍历所有的key值,找到对应的value,对其进行过滤,终只保留你

想要的那部分数据。这样以来计算量会非常大,同时也意味着只有在key已知的情况下,K-V数据库才能保证高性能,否则其性能明显不足。(注:有一些K-V数据库

支持结构化存储,而且有域索引)因此,虽然在访问速度方面K-V数据库优于关系型数据库,但需要已知key值的要求限制了其应用场景。

 

3.为什么要实现一个K-V数据库

  我想通过这个项目来复习一些基础且必要的后端知识。单纯看书和维基百科的文章既无聊又缺乏操作性,所以我觉得实际动手写写代码是

一个更好的方法。我想找一个可以让我复习以下内容的项目:

  • C++编程
  • 面向对象设计
  • 算法和数据结构
  • 内存管理
  • 包含多处理器和多线程的并发控制
  • 基于Server/Client模型的网络
  • 涉及磁盘存储和文件系统的I/O问题

  一个使用文件系统进行持久化存储并提供网络接口的K-V数据库可以涵盖上述的话题。这是一个接触后端领域的完美项目。

  但是现在我们要回到现实一会。目前已经有了许多K-V数据库的实现,一些还是大牛实现的,并且已经应用于大公司的生产环境了。这

包括Redis,MongoDB,memcached,BerkeleyDB,Kyoto Cabinet和LevelDB。

  除此之外,K-V数据库似乎成为了近的潮流。感觉现在每个人都自己实现了一个而且还想展示他们的实现多块多牛逼。这个情况在这里

有描述。这些项目中的大部分当前都不成熟而且真的不能用于生产,但虽然如此,人们还是爱显摆。你很容易搜到一些没名的数据库做性能比

较的幻灯片或者是blog。那些表通常真的一点用都没有,只有用你自己的硬件,你自己的数据,你自己的应用跑的测试才能告诉你哪个K-V数

据库是适合解决你的问题的。因为性能取决于:

  • 硬件
  • 使用的文件系统
  • 实际的应用以及访问key值的顺序(locality of reference)
  • 数据集,特别是键和值的长度,还有以hash table做底层实现时碰撞的概率 

  所以,编写一个真正有影响力的K-V数据库相对来讲是很难的,因为现在已经有很成熟的K-V数据库实现了,常见的结局是自己的项目根本没

人知道,或者变成了爹不亲娘不爱的烂尾项目。

  为了不同,这个项目不会像其他人的那么赶,并且会致力于填上已有解决方案留下的坑。以下是我觉得可以让一个K-V数据库与众不同的几个点:

  • 适配特定的数据形式(比如图,地质数据等)
  • 适配特定的操作(比如仅极高的读性能或仅极高的写性能等)
  • 适配特定的情景(比如自动参数匹配,因为许多K-V数据库都有许多配置选项,有时想找到合适的很麻烦)
  • 提供更多的获取数据的选项:比如在LevelDB中,数据可以通过iterators前向或是后向访问,并且对key值进行了排序,不是所有K-V数据库都做到了这点。
  • 让代码更易读:到目前为止,只有很少的K-V数据库对代码进行了完整的注释。如果你需要很快上手并且对K-V存储部分进行自定义,那文档完善的项目可能会是一个更好的选择,即使其本身不是很知名。因为人们可以真正理解代码补偿了其他方面的不足。
  • 特定的应用:许多的网络爬虫框架管理需要爬取URL的接口都写的很烂,这导致常常需要客户端使用K-V数据库去实现相应的逻辑。一个对URL管理进行了优化的K-V数据库对所有的爬虫框架都是有益处的。

4.计划

  这个项目的目标是用易懂的C++代码开发一个轻量级的K-V数据库,我打算遵循Google的C++编码规范。我会使用hash table作为底层的数据结

构,数据会被持久化到硬盘上,也会实现网络接口。我的重点不在于追求的速度,而在于设计和实现的简洁明了。我也会尽可能的减少数据库对磁

盘空间的占用。

  我不想重复造轮子,所以会先着手看一些用C或者C++实现的K-V数据库,并找出那些好的实现。我会学习他们的架构和代码,吸收之后应用在自己

的实现里。因为我是专业做后端出身,所以已经掌握了这个项目要使用的大部分知识,但是也得学一些新的东西,这也是这个项目的乐趣所在。

  我研究的结果和后的K-V数据库实现会在博客里一一记录下来。但是不要通过文章的发布日期来估计实现一个K-V数据库需要的时间:文章发布的

时间可能比它描述的内容要晚得多。

  在Part 2中,我会搜集一些的K-V数据库项目并解释为什么选它们作为模型。

  你可以在下面的引用部分找一些文章或书的部分章节来了解K-V数据库。在阅读Part 2之前,强烈推荐你至少读一下 The NoSQL Ecosystem 和

  Key Value Stores: A Practical Overview 。

5.引用

        The NoSQL Ecosystem, from the book “Architecture of Open Source Applications, Volume 1”
        NoSQL Patterns, by Ricky Ho
        NoSQL Databases, referencing all the NoSQL databases that matter at the moment
        NoSQL Data Modeling Techniques, by Ilya Katsov
        NoSQL databases benchmark: Cassandra, HBase, MongoDB, Riak, and the discussion on Hacker News
        Wikipedia article on NoSQL
        Wikipedia article on the ACID paradigm
        Key Value Stores: A Practical Overview, by Marc Seeger
        Some Notes on Distributed Key Stores, by Leonard Lin

相关文章