10000 缓存的设计 · Issue #121 · xinglie/xinglie.github.io · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

缓存的设计 #121

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
xinglie opened this issue Oct 14, 2024 · 0 comments
Open

缓存的设计 #121

xinglie opened this issue Oct 14, 2024 · 0 comments
Labels
前端技术 思考 方案 算法

Comments

@xinglie
Copy link
Owner
xinglie commented Oct 14, 2024

缓存在我们平时的开发中有意或无意的都在使用，如果我们要开发一个缓存模块，需要如何去做？

缓存的效率

缓存应该是高效的。

无论是引入缓存模块的代价还是缓存的执行都应该是非常优秀，否则因缓存模块的引入，程序的性能瓶颈(业务代码)转移到另一个地方(缓存模块)，则缓存的引入是失败的。

当然，只要引入缓存模块一定会带来系统的复杂性及额外的代码执行，但前提是准备好优秀的缓存模块，才能去考虑引入缓存是否能缓存应用程序中的性能瓶颈

缓存的读写

缓存的读要远多于写或写入的数据是经过昂贵的代价换来的，才适合使用

缓存的写

缓存的写入允许有一定的性能开销(相比读)，比如可以在写入数据时进行旧数据的淘汰

缓存的读

缓存的读应该是非常高效的，通常读操作要多于写操作，因此应该尽可能少的在读的时候进行其它操作，比如淘汰数据

缓存的设计

我们使用双向链表设计缓存，带缓存区，比如容量100，带20个缓冲区

我们把链表节点存入hashmap中，确保读的时候是O(1)

读的时候，我们仅记录链表节点的访问时间及使用频率，以供在淘汰数据的时候使用。读的时候要尽可能少操作

写的时候我们只向链表尾写入数据以确保高效

同时在写入时，我们进行数据淘汰，同时为了确保缓存模块更智能，我们可以判断在一定时间内的数据写入量

如果某个时间内写入的数据已经超过缓存的上限要淘汰数据，我们不一定要去淘汰数据，而是开发者大概率给出的缓存容量偏小导致的，此时缓存模块自动扩容

如果正常进入数据淘汰阶段

我们从链表头进行所有数据遍历，以记录所有节点的使用频率及最后使用时间O(n)

从低频率及较早时间的节点中找出缓冲大小个节点O(x)

再从头进行缓存数据遍历，淘汰掉缓部区大小的节点O(n)

总体算法复杂度为O(2n+x)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
前端技术 思考 方案 算法
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@xinglie
0