设计键值存储（第一部分）

原文：Design a Key-Value Store (Part I)

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

由于很多人给我们发邮件说，他们想了解系统设计面试的更多内容，我们将会介绍更多这个话题。 我很高兴听到很多反馈意见，如果你有任何建议或疑问，请发表评论告诉我们。

本周，我要谈谈键值存储。 键值存储是世界上几乎所有系统都使用的非常强大的技术。 它可以像散列表一样简单，同时也可以是分布式存储系统。 例如，Cassandra 的下划线系统是一个键值存储系统，Cassandra 在苹果，Facebook 等许多公司中被广泛使用。

在这篇文章中，我将介绍基本的键值存储系统，分布式键值存储以及包括分片在内的扩展问题等，这些都可能在系统设计面试中涵盖。

基本的键值存储

如何在一台机器上设计简单的键值存储系统？

最直接的方法是使用散列表来存储键值对，这是目前大多数这类系统的工作原理。散列表允许你在常数时间内读/写一个键值对，而且使用起来非常简单。大多数语言都有内置的支持。

但是，缺点也是显而易见的。使用哈希表通常意味着你需要将所有内容存储在内存中，这在数据集很大时可能是不可能的。有两个常见的解决方案：

• 压缩你的数据。这应该是首先要考虑的事情，而且往往有一堆你可以压缩的东西。例如，你可以存储引用而不是实际的数据。你也可以使用float32而不是float64。另外，使用像位数组（整数）或向量这样的不同的数据表示也是有效的。
• 存储在磁盘中。如果不可能将所有内容都放在内存中，则可以将部分数据存储到磁盘中。为了进一步优化它，你可以把这个系统看作缓存系统。经常访问的数据保存在内存中，其余的在磁盘上。

分布式键值存储

最有趣的话题就是将键值存储扩展到多台机器。如果你想支持大数据，你肯定会实现分布式系统。让我们看看我们如何设计一个分布式键值存储系统。

如果你已经阅读过设计缓存系统，你会注意到这里的许多概念完全相同。

由于一台机器没有对所有的数据足够的存储空间，这里的总体思路是通过一些规则，将数据分割到多台机器，协调机可以将客户端引导到拥有所请求资源的机器。问题是如何将数据分割到多个机器，更重要的是，分配数据的策略是什么？

拆分

假设所有的键都是像http://gainlo.co这样的 URL，我们有 26 台机器。一种方法是基于 URL 的第一个字符（www之后），将所有键（URL）分配给这 26 台机器。例如，http//gainlo.co将存储在机器 G，而http://blog.gainlo.co将被存储在机器 B。那么这种设计的缺点是什么？

让我们忽略 URL 包含 ASCII 字符的情况。好的分片算法应该能够把流量平均平衡到所有的机器。换句话说，理想情况下每台机器都会收到相同数量的请求。显然，上面的设计不太好。首先，存储不是平均分布的。可能有更多的网址以a开始而不是z。其次，一些网址更受欢迎，例如 Facebook 和 Google。

为了平衡流量，最好确保键是随机分布的。 另一个解决方案是使用 URL 的散列，通常具有更好的性能。 要设计一个好的分片算法，你应该完全理解这个应用，并且可以估计系统的瓶颈。

总结

键值存储涵盖了太多有趣的话题，我很难把它们全部写入一篇文章。 正如你所看到的，当扩展系统时，需要考虑更多的问题，这就是许多人觉得分布式系统较难的原因。

在下一篇文章中，我们将继续讨论，并将涵盖更多扩展系统的内容。 将讨论系统可用性，一致性等事情。