跳到主要内容

设计 Memcached 或内存中的 KV 存储

· 阅读需 2 分钟

需求

  1. 高性能,分布式键值存储
  • 为什么分布式?
    • 答:为了存储更大规模的数据
  1. 用于小数据对象的内存存储
  2. 简单的服务器(将复杂性推给客户端),因此可靠且易于部署

架构

大局:客户端-服务器

  • 客户端
  • 给定一组 Memcached 服务器
  • 根据键选择服务器
  • 服务器
  • 将 KV 存储到内部哈希表中
  • LRU 驱逐

键值服务器由固定大小的哈希表 + 单线程处理程序 + 粗粒度锁组成

哈希表

如何处理冲突?主要有三种解决方法:

  1. 分离链:发生冲突的桶链表中包含相同索引的多个条目,您可以始终将新发生冲突的键值对附加到列表中。
  2. 开放寻址:如果发生冲突,转到下一个索引,直到找到可用的桶。
  3. 动态调整大小:调整哈希表的大小并分配更多空间;因此,冲突发生的频率会降低。

客户端如何确定查询哪个服务器?

请参见 数据分区与路由

如何使用缓存?

请参见 键值缓存

如何进一步优化?

请参见 Facebook 如何扩展其社交图存储?TAO

References: