如何设计缓存系统？
缓存系统是目前几乎所有应用中广泛采用的技术。
另外，它适用于技术栈的每一层。
例如，在网络区域中，高速缓存用于DNS查找，Web服务器高速缓存用于频繁请求。
简而言之，缓存系统存储常用资源（可能在内存中），当下次有人请求相同的资源时，系统可以立即返回。
它通过消耗更多的存储空间来提高系统效率。
LRU
最常用的缓存系统之一是LRU（最近最少使用）
事实上，另一个常见的面试问题是讨论LRU缓存的数据结构和设计。
我们从这个方法开始。LRU缓存的工作方式非常简单。
当客户端请求资源A时，发生如下情况：
- 如果缓存中存在A，我们只需立即返回。
- 如果没有，并且缓存具有额外的存储插槽，则我们获取资源A并返回给客户端。
另外，将A插入缓存。 - 如果缓存已满，我们将最近使用最少的资源剔除，并将其替换为资源A.
这里的策略是最大限度地提高请求资源存在于缓存中的机会。
那么我们怎样才能实现一个简单的LRU？
LRU设计
一个LRU缓存应该支持这些操作：查找，插入和删除。
显然，为了实现快速查找，我们需要使用散列。
同样的道理，如果我们想要快速插入/删除，链接列表就会出现在你的脑海里。
由于我们需要有效地查找最近最少使用的项目，所以我们需要按顺序排列队列，堆栈或排序数组。
为了结合所有这些分析，我们可以使用由双向链表实现的队列来存储所有的资源。
此外，还需要一个哈希表，其中资源标识符为key，相应队列节点的地址为value。
这是如何工作的。
当请求资源A时，我们检查哈希表以查看缓存中是否存在A.
如果存在，我们可以立即找到相应的队列节点并返回资源。
如果不是的话，我们将A添加到缓存中。
如果有足够的空间，我们只需在队列的末尾添加一个哈希表就可以了。
否则，我们需要删除最近最少使用的条目。
要做到这一点，我们可以很容易地从哈希表中删除队列的头部和相应的条目。
驱逐政策
当缓存已满时，我们需要删除现有项目以获取新资源。
实际上，删除最近最少使用的项目只是最常用的方法之一。
那么还有其他方法可以做到吗？
如上所述，策略是尽可能地将请求资源存在于缓存中。
我将在这里简要提一下几种方法：
- 随机替换（RR） - 如术语所示，我们可以随机删除一个条目。
- 最不经常使用（LFU） - 我们保持每个项目被请求频率的次数，并删除最不经常使用的项目。
- W-TinyLFU - 我也想谈谈这个现代驱逐政策。
简而言之，LFU的问题在于，有时候一个项目只是经常使用，而LFU仍然会保留这个项目很长一段时间。
W-TinyLFU通过计算时间窗内的频率来解决这个问题。
它也有各种存储优化。
并发
为了讨论并发性，我想谈谈为什么高速缓存存在并发问题，我们如何解决这个问题。
它落入了经典的读写器问题。
当多个客户端同时尝试更新缓存时，可能会有冲突。
例如，两个客户端可能竞争相同的缓存槽，而最后一个更新缓存的客户端将获胜。
当然，常见的解决方案是使用锁。
缺点是显而易见的 - 它会影响性能很多。
我们如何优化呢？
一种方法是将缓存分成多个分片，并为每个分片分配一个锁，这样如果客户端从不同的分片更新缓存，客户端就不会相互等待。但是，由于热门作品更有可能被访问，某些碎片将比其他碎片更频繁地被锁定。
另一种方法是使用提交日志。
要更新缓存，我们可以将所有突变存储到日志中，而不是立即更新。
然后一些后台进程将异步执行所有的日志。
数据库设计中通常采用这种策略。
分布式缓存
当系统达到一定规模时，我们需要将缓存分配给多台机器。
一般的策略是保留一个哈希表，将每个资源映射到相应的机器上。
因此，当请求资源A时，从这个哈希表中我们知道机器M负责高速缓存A并将请求指向M.在机器M，其工作方式类似于上面讨论的本地高速缓存。
如果A不存在于内存中，则机器M可能需要获取并更新A的缓存。
之后，它将缓存返回到原始服务器。
如果您对此主题感兴趣，可以查看更多关于Memcached的信息
。
