以下是 N 为 5 时上述函数递归调用树状图： ? 显然，在调用过程中，有多次重复计算。...本节只研究 LRU 是如何在其中实现的，所以，下面的源码中移除了无关的代码。...缓存命中 假设此时缓存命中 K2，则会定位到 K2 节点，并返回该节点的值，同时会调整环形链表，将 K2 移动到 root 节点的右侧（即链表的前边），则更新的示意图如下： ?...总结 functools.lru_cache 中巧妙使用了环形双向链表来实现 LRU 缓存，通过在缓存命中时，将节点移动到队列的前边的方式，从而间接地记录了最近经常访问的节点。...当缓存空间满了后，会自动“移除”位于环形队列尾部最近命中频率最低的节点，从而为新增缓存节点腾出了空间。
解决：更新数据时不更新缓存，而是删除缓存中的数据。在读取数据时，来触发预热填充。 可以采用类似于juc中的ReadWriteLock，读写锁来控制并发，但是性能会比较差。...一般来说，消息刚刚写入到MQ server端就会被消费，按照 LRU 的“优先清除最近最少使用的页”这种策略，消费端拉取消息时，对于这种刚刚写入的 PageCache，命中的几率会非常高。...业务：计数器、扣减库存，也可以考虑使用这种策略，多次请求合并。 ? 有 Cache 的地方就必然存在失效问题。保证数据的一致性。 ?...在增加和删除节点时，只有少量的 Key 会“漂移”到其它节点上，大部分的 Key 命中的节点还是会保持不变。可以有效解决因扩容问题带来的大量的缓存失效。...缺点：缓存节点在圆环上分布不平均，会造成部分缓存节点的压力较大；当某个节点故障时，这个节点所要承担的所有访问都会被顺移到另一个节点上，会对后面这个节点造成压力，如果流量水位较高时，很容易压垮，进而引发连锁反应
素 可能需要搬移元素，效率低O(N) 只需修改指针指向 插入 动态顺序表，空间不够时需要扩 容 没有容量的概念 应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁 缓存利用率 高 低 1.1插入...需要注意的是扩容存在的两个问题还是相互影响的，我们一般按照二倍扩容其实是通过概率学计算希望减少扩容次数，避免异地扩容的消耗,但是这样扩容大了，又会造成浪费的问题；反过来，为了节省空间，扩容小了，就会需要多次扩容...但是链表有个比较大的缺陷是不支持随机访问（用下标访问），如果大家学过C++的STL,就会发现链表的排序比起顺序表来说没有优势，此外如二分查找等场景都需要使用顺序表或者说数组。...，那么就会将第一个数据连同后面一大段数据加载到缓存中（数组不同数据存储的物理地址是连续的），之后我们连续访问多个数据都会出现缓存命中的前情况，我们将这称为缓存命中率高， 但是链表不同节点的物理地址极大概率是不连续的...，这时将第一个节点连同后面一大段数据加载到缓存中时，极大概率是无法加载第二个节点到缓存中的（可能加载部分节点），这时内存中就会加载进很多无用数据，因为缓存大小是固定的，根据最近最少用原则（LRU）,这些无用数据会把缓存中之前早期的数据挤走
B+ 树中，数据对象的插入和删除仅在叶节点上进行。 B+树有2个头指针，一个是树的根节点，一个是最小关键码的叶节点。 3....由于是一次定位数据，不像BTree索引需要从根节点到枝节点，最后才能访问到页节点这样多次IO访问，所以检索效率远高于BTree索引。 索引设计的原则？...这种特性使得B树在特定数据重复多次查询的场景中更加高效。 使用B+树的好处 由于B+树的内部节点只存放键，不存放值，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。...（通过索引访问数据），在内存中直接搜索索引，然后通过索引找到磁盘相应数据，这也就是为什么索引不在key buffer命中时，速度慢的原因。...在联合索引中，如果想要命中索引，需要按照建立索引时的字段顺序挨个使用，否则无法命中索引。
②高一致性业务可以结合使用超时剔除和主动更新，这样即使主动更新出了问题，也能保证数据过期时间后删除脏数据。...通常可以在程序中分别统计总调用数、缓存层命中数、存储层命中数，如果发现大量存储层空命中，可能就是出现了缓存穿透问题。造成缓存穿透的基本原因有两个。...检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了： 如果这些点有任何一个 0，则被检索元素一定不在；如果都是 1，则被检索元素很可能在。...无底洞问题分析： ①客户端一次批量操作会涉及多次网络操作，也就意味着批量操作会随着节点的增多，耗时会不断增大。 ②网络连接数变多，对节点的性能也有一定影响。 如何在分布式条件下优化批量操作？...重建缓存不能在短时间完成，可能是一个复杂计算，例如复杂的SQL、多次IO、多个依赖等。在缓存失效的瞬间，有大量线程来重建缓存，造成后端负载加大，甚至可能会让应用崩溃。
当我们将数据或请求分布到多个节点时，我们希望数据在各个节点之间分布均匀，以避免某个节点成为瓶颈，同时我们需要确保当节点发生故障或增加时，数据迁移的成本最小化。...这个范围可以表示一个环形的哈希环 2.2 节点映射 分布式系统中的节点（如缓存服务器、数据库节点等）也映射到这个哈希环上，通常使用节点的唯一标识（如IP地址或名称）经过哈希函数计算得到一个位置，放置在环上...每个节点在环上都有一个唯一的位置 2.3 数据定位 当需要定位一个数据时，首先通过哈希函数计算数据的哈希值，然后沿着哈希环顺时针找到第一个大于等于该哈希值的节点位置，即为数据所在的节点。...2.4 增加或删除节点 当增加或删除一个节点时，只有受影响的部分数据需要迁移。具体来说，当节点离开时，它的数据会被分配给其后继节点，当新节点加入时，它会接管其后继节点的部分数据。 3....每个请求的关键字经过哈希计算，根据一致性哈希算法找到对应的缓存节点，如果缓存命中，则返回缓存数据，否则请求后端数据源。 3.2 负载均衡 一致性哈希也广泛应用于负载均衡中。
） 只演示了插入的过程，其中可以通过 delete、find 执行删除和查找操作。...在 “问题 1 - 方案 3” 的基础上，由于所有数据行都存储在叶子节点，B 树的叶子节点本身也是有序的，可以增加一个指针，指向当前叶子节点按主键顺序的下一叶子节点；查询时先查到左界，再查到右界，然后从左界到有界线性遍历...这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。 ️...原因很简单，如何在节点中查找到对应 key？如果线性扫描，则每次都需要重新计算，成本太高；如果二分查找，则需要针对 from_unixtime 方法确定大小关系。 因此，索引列不能参与计算。...如，用性别作索引，那么索引仅能将 1000w 行数据划分为两部分（如 500w 男，500w 女），索引几乎无效。
//medium.com/@dgryski/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8 一致性哈希算法权衡 一致性哈希是用来解决缓存节点删除增加或者微服务架构中的粘性负载均衡后端节点删除增加时...which cache an object goes in, we move clockwise round the circle until we find a cache point)，这样当新增和删除节点时并不会改变原来所有的命中规则...1和4会命中A、2会命中B、3会命中C 当C节点crash和新增D节点时，只会影响3和4的object缓存失效 import java.util.Collection; import...，所以需要引入虚拟节点(virtual nodes),一般是主机名加编号,数据定位方式不变，只不过命中后要将虚拟节点转换成真实节点(To add the list of nodes to the ring...It doesn’t support arbitrary bucket names),另外只能增加或者删除最后的节点，不支持任意节点删除，也就是说中间节点失效时，失效节点的数据并不会重新平均分配(you
只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。 代码实现 python已经有相关的实现如lru_cache。...如果缓存命中key，那么将命中节点移到双向循环链表的结尾，并且返回结果（571~581 行）这里通过字典加双向循环链表的组合数据结构，实现了用O(1)的时间复杂度删除给定的节点。...如果没有命中，并且缓存满了，那么需要将最久没有使用的节点（root 的下一个节点）删除，并且将新的节点添加到链表结尾。...在实现中有一个优化，直接将当前的root 的key 和result 替换成新的值，将root 的下一个节点置为新的root，这样得到的双向循环链表结构跟删除root的下一个节点并且将新节点加到链表结尾是一样的...，但是避免了删除和添加节点的操作（591~611 行） 如果没有命中，并且缓存没满，那么直接将新节点添加到双向循环链表的结尾（root[PREV]）（613~619 行） 性能测试 我们以斐波拉契数的计算为例
AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。...当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。...但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转。...B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。...此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。
多路查找树 二叉树与 B 树 二叉树的问题分析 二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如 1 亿)， 就 存在如下问题: 问题 1：在构建二叉树时...，需要多次进行 i/o 操作(海量数据存在数据库或文件中)，节点海量，构建二叉树时， 速度有影响 问题 2：节点海量，也会造成二叉树的高度很大，会降低操作速度 多叉树 在二叉树中，每个节点有数据项...有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层， 拆后仍然需要满足上面 3 个条件。...对上图的说明: B+树的搜索与 B 树也基本相同，区别是 B+树只有达到叶子结点才命中（B 树可以在非叶子结点命中），其性 能也等价于在关键字全集做一次二分查找 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点...,如查找goodbye Good 找到前缀字符,但是此时字典树遍历完成,而单词并没有完成,结果任然不存在 删除规则 先要遍历出当前字符串路径,从叶子节点向上删除,除去叶子节点外的节点,如果有其他节点,此节点保留
缓存风险4.1 缓存穿透缓存风险问题也是面试常考的八股文题目，这里还是简单说明下缓存穿透：查询的数据在数据库里根本不存在，缓存里也不会有，这样的请求每次都不会命中缓存，会请求到末端数据库。...解决办法：存数据的过期时间设置随机，防止同一时间大量数据过期现象发生启用透明多级缓存，多个服务节点因为加载一级缓存的时间不一样，也能分散过期时间4.4 缓存污染概念：缓存中的数据与真实数据源中的数据不一致的现象解决办法...：使用更新缓存时遵循的设计模式，如：Cache Aside，Read/Write Through，Write Behind Caching这些Cache Aside模式的工作方式：读数据时，先读缓存，如缓存中没有...，则读数据库，再将数据写入缓存中；写数据时，先写数据库，然后失效缓存（删除缓存数据）；面试可能遇到的两个关于Cache Aside的问题：1.更新先后顺序，为什么先更新数据库再删除缓存？...和上面一样，更新过程中，如果有其他更新请求进来更新数据库，缓存就会面临多次修改赋值的复杂时序问题。所以直接删除缓存就行。
第二层：MySQL的核心服务功能层，包括查询解析、分析、查询缓存、内置函数、存储过程、触发器、视图等，select操作会先检查是否命中查询缓存，命中则直接返回缓存数据，否则解析查询并创建对应的解析树。...当保存CHAR值时，在它们的右边填充空格以达到指定的长度，当检索到CHAR值时，尾部的空格被删除掉。VARCHAR类型用于存储可变长字符串，存储时，如果字符没有达到定义的位数，也不会在后面补空格。...InnoDB 引擎下，主要使用的是 B+Tree 索引，每个索引其实都是一颗B+树，B+树是为了磁盘及其他存储辅助设备而设计的一种平衡查找树(不是二叉树)，在B+树中，所有的数据都在叶子节点，且每一个叶子节点都带有指向下一个节点的指针...聚簇索引的叶子节点存的是整行数据，当某条查询使用的是聚簇索引时，只需要扫描聚簇索引一颗B+树即可得到所需记录，如果想通过二级索引来查找完整的记录的话，需要通过回表操作，也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的记录...不可重复读（Non-Repeatable Reads)：事务 A 多次读取同一数据，事务B在事务A多次读取的过程中，对数据作了更新并提交，导致事务A多次读取同一数据时，结果不一致。
在社区中，有不少使用云开发的小伙伴反馈遇到了“CDN流量消耗如流水”的情况。...有一觉醒来超额的： 1.jpeg 有被高质量图片的加载“吓”到不敢用的： 2.jpeg 那么问题来了，如何在云开发中优雅地管控 CDN 流量消耗呢？本文就来和你详细聊聊！...CDN又称内容分发网络，通俗来讲就是将你主存储（源站）中的文件，复制给各地的存储点（CDN节点），当有用户访问这个资源时，直接从就近的存储点（CDN节点）获取即可。...当我们的存储中有文件更新时，存储在 CDN 节点的旧文件又该如何处理呢？在这里引入一个知识点——缓存时间。...这里的缓存时间其实就是文件副本在各地存储点（CDN节点）的有效时间，比如默认是两小时，那么每次文件副本在各地存储点的有效时间就是两小时，超过这个时间之后再收到请求时，存储点（CDN节点）就会丢弃过期的旧文件
优化方案： 及时清理单推消息，如果用户已经收到单推消息，收到puback回执，直接删除Redis消息。如果单推消息被管控等原因限制发送，直接删除单推消息体。...对于相同内容的消息，进行聚合存储，相同内容消息存储一条，消息id做标识推送时多次使用。 经过这个优化后，缩容效果较明显。全量上线后容量缩小了2090G，原最高容量为3650G，容量缩小了58%。...方案二：把消息体从老集群拆分出来 所有连接msg Redis的节点替换新地址重启，推送节点进行双读，等到老集群命中率为0时，直接切换读新集群。...cache1缓存clientInfo经常变更的信息，如：在线状态、cn地址等。 cache2缓存ci加密部分参数，这部分缓存只在需要加密时使用，变更频率没那么高，只有连接时才会变更。...优化后推送节点操作缓存和client Redis流程图： [图片] 优化后效果： 1）新增cache1缓存命中率52%，cache2缓存命中率30%。
但是插入数组如[15，17，13，12，9，7]，二分搜索树就暴露了缺点，将树退化成线性表，查找的时间复杂度达到最坏时间复杂度O(n)。...删除任意元素算法需要先进行命中查找，若查找命中，则将右子树的最小值替换掉待删除元素，然后将右子树进行删除最小元素的算法。 2-3-4树虽满足二分搜索树的性质，但不是一颗二分搜索树。...红黑树删除算法 红黑树删除算法也需要进行旋转和颜色转换操作，在插入算法中为了待插入元素所在的节点不是4-节点，所以在沿着左右链接向下进行变换时将4-节点分解成3个2-节点，中间的2-节点与父节点合并；而在删除算法中为了待删除元素所在的节点不是...2-节点，所以在沿着左右链接向下进行变换时将2-节点向其它不是2-节点的节点（兄弟节点或父节点）借一个元素过来，合并成3-节点。...删除任意元素算法需要先进行命中查找，在命中查找的过程中会进行沿着左右链接向下变换，如果查找命中则将右子树的最小元素替换掉待删除元素，然后进行右子树的删除最小元素算法；如果查找未命中，则直接返回balance
解决方案： 方案一：查存DB 时，如果数据不存在，预热一个特殊空值到缓存中。这样，后续查询都会命中缓存，但是要对特殊值，解析处理。...分布式缓存设计一般选择一致性Hash，当有部分节点异常时，采用 rehash 策略，即把异常节点请求平均分散到其他缓存节点。...所以我们在设计缓存的时候，要注意缓存的粒度，既不能过大，如果过大很容易导致网络拥堵；也不能过小，如果太小，查询频率会很高，每次请求都要查询多次。...解决方案： 方案一：设置一个阈值，当value的长度超过阈值时，对内容启动压缩，降低kv的大小 方案二：评估大key所占的比例，由于很多框架采用池化技术，如：Memcache，可以预先分配大对象空间。...解决方案： 方案一：引入一把全局锁，当缓存未命中时，先尝试获取全局锁，如果拿到锁，才有资格去查询DB，并将数据预热到缓存中。
解决方案： 方案一：查存DB 时，如果数据不存在，预热一个 特殊空值 到缓存中。这样，后续查询都会命中缓存，但是要对特殊值，解析处理。...分布式缓存设计一般选择 一致性Hash ，当有部分节点异常时，采用 rehash 策略，即把异常节点请求平均分散到其他缓存节点。...所以我们在设计缓存的时候，要注意 缓存的粒度 ，既不能过大，如果过大很容易导致网络拥堵；也不能过小，如果太小，查询频率会很高，每次请求都要查询多次。...解决方案： 方案一：设置一个阈值，当value的长度超过阈值时，对内容启动压缩，降低kv的大小 方案二：评估 大key 所占的比例，由于很多框架采用 池化技术 ，如：Memcache，可以预先分配大对象空间...解决方案： 方案一：引入一把 全局锁 ，当缓存未命中时，先尝试获取全局锁，如果拿到锁，才有资格去查询 DB ，并将数据预热到缓存中。
页面静态化缓存，如FreeMaker、Thymeleaf等。 文件管理，如FastDFS等。 01 缓存的命中率 缓存的命中率指的是“缓存查询的次数”与“总查询次数”的比值。...在多级缓存下，可以调研每一级缓存的命中率，以便调整代码。若某缓存命中率过低，则很可能是缓存穿透问题。 02 缓存回收方式 基于时间：当某缓存超过生存时间时，则进行缓存回收。...04 缓存的设计模式 （1）Cache Aside模式：首先读取缓存中的数据，若缓存没有命中，则读取DB。当DB需要更新时，直接删掉缓存中的数据。...（7）缓存是否能够被手动删除或刷新，若遇到紧急状况是否能够进行可逆性操作。 （8）缓存的回收策略、回收方式等内容是否正常生效。...第9章讲解如何通过Prometheus和Grafana监控MySQL节点。 第10章和第11章讲解如何通过堆内缓存、堆外缓存（MapDB）和磁盘缓存解决MySQL数据库性能不佳的问题。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
