长短链

学习的一个项目，长链接转短链接，主要是hash，缓存，Ip限流

如果分布式部署话，redis就需要用一致性hash算法，避免缓存雪崩

技术栈

springboot + thymeleaf

存储层：MySQL

缓存层：LRUCache，redis，布隆过滤器

布隆过滤器主要用于优化存储，LRUCache，redis主要用于优化查询

业务：302重定向，MurmurHash计算hash，MurmurHash 就是一种非加密型哈希算法，与 MD5、SHA 等常见哈希函数相比，性能与随机分布特征都要更佳。MurmurHash 有 32 bit、64 bit、128 bit 的实现，32 bit 已经足够表示近 43 亿个短链接

采用302而不是301的原因在于301 为永久重定向、302 为临时重定向，因为302便于统计网站的访问次数。

一致性hash减少缓存雪崩

参考 https://hardcore.feishu.cn/docs/doccnAfY0f35ZgnrFg7jSTQmOOf

https://github.com/Naccl/ShortURL

技术设计

1. 读与写 这个项目是一个少写多读的项目，那么需要对读写进行优化。

目前对于写，采用布隆过滤器，减少写的次数

对于读，采用LRUCache或者LFUCache以及redis进行优化。

测试过，写大概200ms，读100ms不到。

TODO

• ip黑白名单
• 支持自定义格式

知识点

hash

1. 一致性哈希算法
2. Murmur哈希
3. MD5

缓存

缓存的重要指标是命中率，也就是我的key在缓存中的次数/key访问的次数

1. 布隆过滤器
2. FIFO
3. LRU
4. LFU
5. TinyLFU
6. window-TinyLFU

LRU：面对突发的流量比较方便，因为不需要去记录数据频率，但它是通过历史的数据去预测未来的数据，是有局限性的，它认为最后到来的数据是可能被再次访问，从而给它最高的优先级。实际上，对于本场景，不太适合。

LFU：在 LFU 中只要数据访问模式的概率分布随时间保持不变时，其命中率就能变得非常高。但是对于一个数据，是存在时效性的，热点key是随着时间发生变化的，过几天这个key过气了，但频率太高了，LFU缓存了几亿次，其他热点key就无法具备更高的优先级。所以在这种模式下是有局限性

TinyLFU：

当数据的访问模式不随时间变化的时候，LFU的策略能够带来最佳的缓存命中率。但存在问题：

（1）首先，它需要给每个记录项维护频率信息，每次访问都需要更新，这是个巨大的开销；

（2）其次，如果数据访问模式随时间有变，LFU的频率信息无法随之变化，因此早先频繁访问的记录可能会占据缓存，而后期访问较多的记录则无法被命中。

tinyLFU解决了这个问题：①用更小的空间去维护频率②时间衰减设计机制，但是tiny-lfu和lfu对于稀疏流量控制不好

后期扩展

希望实现一致性hash算法，因为读是很多的，可能存在redis多机部署，那么就设置对于ip进行分流，采用一致性hash算法，均匀达到每一台机器的redis上。

一致性hash是分布式系统组件负载均衡的首选算法，比如分库分表