双非本滴滴一面

来源：https://www.nowcoder.com/feed/main/detail/17e0b3985f964591a56ef9e6be68d203

Redis

1、reids中list的消息队列如何实现？

在Redis中，List数据结构被广泛用作消息队列的实现。Redis的List是一个双向链表，它可以存储多个相同或不同类型的元素，并且支持在列表的两端进行快速的插入和删除操作。在Redis中，List数据结构提供了一些操作命令，可以方便地实现消息队列的功能。

实现消息队列的基本操作：

Push操作：将一个或多个元素从列表的左端或右端插入。
- LPUSH key value1 [value2 ...]：将一个或多个值从列表左端插入。
- RPUSH key value1 [value2 ...]：将一个或多个值从列表右端插入。
Pop操作：从列表的左端或右端弹出一个元素。
- LPOP key：从列表左端弹出一个值并返回。
- RPOP key：从列表右端弹出一个值并返回。
长度操作：获取列表的长度。
LLEN key：返回列表的长度。
范围操作：获取列表的指定范围内的元素。
LRANGE key start stop：返回列表指定范围内的元素。

示例：

bash

# 将元素插入到队列尾部
> RPUSH queue 1
(integer) 1
> RPUSH queue 2
(integer) 2

# 从队列头部取出元素
> LPOP queue
"1"
> LPOP queue
"2"

使用场景：

消息队列：可以用来实现简单的消息队列，生产者通过RPUSH将消息推入队列，消费者通过LPOP或BRPOP（阻塞式弹出）从队列中取出消息。
任务队列：可以用来实现任务队列，生产者将任务推入队列，消费者从队列中取出任务并执行。

2、reids如何实现的延时队列？

在Redis中，可以利用Sorted Set和Hash数据结构来实现延时队列（Delayed Queue）的功能。延时队列通常用于需要延迟执行的任务或事件，可以根据任务的执行时间进行排序，以便及时触发和处理。

实现延时队列的基本操作：

添加延时任务：将任务添加到Sorted Set中，并设置任务的执行时间作为Score，任务的唯一标识作为Member。
- ZADD delayed_queue timestamp member
轮询待执行任务：定时轮询Sorted Set，获取当前时间之前的任务，即需要执行的任务。
- ZRANGEBYSCORE delayed_queue 0 <current_timestamp> WITHSCORES
- ZREMRANGEBYSCORE delayed_queue 0 <current_timestamp>
处理任务：根据任务的唯一标识，从Hash中获取任务的详细信息，并执行相应的操作。
HGETALL task:<task_id>

示例：

bash

# 添加延时任务
> ZADD delayed_queue 1638829200 task1
(integer) 1
> ZADD delayed_queue 1638829200 task2
(integer) 1

# 轮询待执行任务
> ZRANGEBYSCORE delayed_queue 0 1638829200 WITHSCORES
1) "task1"
2) "1638829200"
1) "task2"
2) "1638829200"

# 处理任务
> HGETALL task:task1
1) "task_id"
2) "task1"
3) "content"
4) "..."

使用场景：

延时任务调度：可以用于实现延时任务的调度和执行，如定时发送邮件、定时执行任务等。
消息重试：可以用于实现消息的延时重试，将需要延时处理的消息添加到延时队列中，到期后再进行处理。

3、redis中zset如何最早消费到数据？

添加延时任务：将任务添加到有序集合（ZSET）中，其中任务的执行时间作为分数（Score），任务的唯一标识作为成员（Member）。
```
ZADD delayed_queue <timestamp> <task_id>
```
消费最早任务：定时从有序集合中获取分数最小的任务（即最早执行的任务）。
```
ZRANGE delayed_queue 0 0 WITHSCORES
```
处理任务：根据任务的唯一标识，从存储任务数据的地方获取任务的详细信息，并执行相应的操作。
```
HGETALL task:<task_id>
```
移除已处理任务：处理完任务后，可以将已处理的任务从有序集合中移除。
```
ZREM delayed_queue <task_id>
```

在这个过程中，有序集合会根据任务的执行时间自动进行排序，每次获取最小分数的任务即为最早需要执行的任务。处理完任务后，可以通过 ZREM 命令将任务从有序集合中移除，避免重复消费。

4、redis的zset怎么实现先进先出的？

实现步骤：

使用有序集合保存元素和优先级：在有序集合中，将元素作为成员，将元素的优先级（比如时间戳或序号）作为分数。
```
ZADD queue <priority> <element>
```
使用列表保存元素的顺序：在列表中保存元素的顺序，用于实现先进先出的特性。
```
LPUSH queue_list <element>
```
获取最早添加的元素：通过列表的末尾弹出（RPOP）操作获取最早添加的元素，即先进入队列的元素。
```
RPOP queue_list
```
删除有序集合中对应的元素：根据元素的值，从有序集合中删除对应的元素。
```
ZREM queue <element>
```

示例：

假设需要实现一个先进先出的任务队列，可以按以下方式实现：

bash

# 添加任务到有序集合
> ZADD queue 1 task1
(integer) 1
> ZADD queue 2 task2
(integer) 1

# 添加任务到列表
> LPUSH queue_list task1
(integer) 1
> LPUSH queue_list task2
(integer) 2

# 获取最早添加的任务
> RPOP queue_list
"task1"

# 从有序集合中删除对应的任务
> ZREM queue task1
(integer) 1

5、缓存穿透，缓存击穿，缓存雪崩是什么，要如何解决？

缓存穿透：

缓存穿透是指查询一个不存在的数据，由于缓存不命中，每次请求都直接访问数据库，导致数据库压力过大。这种情况通常由恶意攻击或者缓存中不包含的数据导致。

解决方法：

布隆过滤器：使用布隆过滤器判断请求的数据是否存在，如果不存在，可以直接拦截请求，避免访问数据库。
空对象缓存：对于不存在的数据，也将其缓存起来，但是设置一个较短的过期时间，避免缓存层的穿透请求频繁访问数据库。

缓存击穿：

缓存击穿是指一个热点key在缓存过期的一刻，恰好有大量的请求并发访问，导致大量请求同时打到数据库上，引起数据库压力过大。

解决方法：

加锁：在缓存失效的时候，使用互斥锁（Mutex）或者分布式锁，只允许一个线程去加载数据，其他线程等待，避免同时访问数据库。
提前异步刷新：在缓存过期之前主动刷新缓存，保证缓存不会在同一时间全部失效。
热点数据永不过期：对于热点数据，可以设置永不过期，保证数据一直在缓存中。

缓存雪崩：

缓存雪崩是指在某一个时间段内，大量的缓存数据同时失效，导致数据库负载剧增的情况。

解决方法：

缓存数据过期时间随机：设置缓存数据的过期时间时，加上一个随机值，避免大量缓存同时失效。
多级缓存：使用多级缓存架构，将缓存分为多个层级，每个层级的缓存过期时间不同，减少缓存雪崩的影响范围。
限流降级：在缓存失效后，对于热点数据可以进行限流或者降级处理，避免瞬时请求量过大。

6、具体解释下布隆过滤器？

布隆过滤器（Bloom Filter）是一种用于快速检索一个元素是否属于一个集合的数据结构，它的核心思想是用一个比特数组和多个哈希函数来表示一个集合，可以高效地判断一个元素是否可能在集合中，但不能100%确定。

布隆过滤器的原理和特点：

数据结构：布隆过滤器通常由一个位数组（bit array）和多个哈希函数组成。
添加元素：当一个元素要加入集合时，通过多个哈希函数将元素映射为多个位数组上的位置，并将这些位置的比特值设为1。
查询元素：当查询一个元素是否在集合中时，同样通过多个哈希函数计算出对应的位数组位置，如果所有位置上的比特值都为1，则认为元素可能在集合中；如果有一个位置的比特值为0，则可以确定元素一定不在集合中。

布隆过滤器的优点：

空间效率高：相比于其他数据结构，布隆过滤器在存储大量数据时所需的空间很小。
查询效率高：布隆过滤器查询元素的时间复杂度是 O(k)，其中 k 是哈希函数的个数。
支持高并发：由于查询操作不需要加锁，所以支持高并发的查询。

布隆过滤器的缺点：

存在误判：由于布隆过滤器使用多个哈希函数，并且多个位置可能会同时被设置为1，所以存在一定的误判率。
无法删除元素：由于删除元素需要将对应的位数组位置设为0，但这样会影响其他元素的判断结果，所以布隆过滤器通常不支持删除操作。

布隆过滤器的应用场景：

缓存穿透预防：在查询缓存之前，先用布隆过滤器判断请求的数据是否存在，如果不存在，则直接拦截请求，避免访问数据库。
爬虫去重：在爬取网页的过程中，用布隆过滤器判断当前 URL 是否已经被访问过，避免重复爬取。
网络安全：在网络安全领域中，布隆过滤器可以用于快速判断一个 IP 地址是否为黑名单中的地址。

7、什么是表的物理存储顺序？

表的物理存储顺序指的是数据库管理系统（DBMS）在磁盘上如何存储表的数据。在数据库中，表是由行（记录）组成的，每一行又由多个列（字段）组成。表的物理存储顺序对于数据库的性能和存储空间利用率具有重要影响。

表的物理存储顺序的影响因素：

磁盘存储结构：磁盘是按照块（Block）来读写数据的，每个块的大小是固定的。表的物理存储顺序会影响到数据在磁盘上的存储位置，进而影响到数据的读取效率。
数据的访问模式：如果表的数据经常需要按照某个列进行范围查询或者排序，那么该列的物理存储顺序就显得尤为重要。

常见的表的物理存储顺序：

堆表（Heap Table）：数据以随机的方式存储在磁盘上，没有特定的顺序。这种存储方式对于插入和更新操作比较高效，但是对于范围查询和排序操作效率较低。
聚簇索引表（Clustered Index Table）：数据按照聚簇索引的顺序存储在磁盘上，聚簇索引的顺序通常是根据主键或者唯一索引来确定的。这种存储方式对于范围查询和排序操作效率较高，但是插入和更新操作的性能相对较低。
非聚簇索引表（Non-Clustered Index Table）：数据存储在磁盘上的顺序和索引无关，而是按照插入的顺序存储。这种存储方式对于插入和更新操作比较高效，但是对于范围查询和排序操作效率较低。

表的物理存储顺序的优化：

合理设计索引：根据数据的访问模式，合理设计表的索引，选择合适的聚簇索引或非聚簇索引。
分区表：对于大表，可以考虑使用分区表来优化物理存储顺序，将表按照一定的规则分成多个子表，每个子表可以单独管理存储和查询。
磁盘优化：合理规划磁盘的存储结构，如使用RAID技术、SSD等，来提高数据的读写效率。

8、索引的类型？

B-树索引：

B-树索引是最常见的索引类型之一，它是一种多路平衡查找树，通常用于实现数据库的索引结构。B-树索引适用于范围查询和等值查询，并且支持高效的插入和删除操作。在大多数数据库中，包括MySQL、PostgreSQL等，使用的默认索引类型就是B-树索引。

B+树索引：

B+树索引是B-树索引的一种变体，它在B-树的基础上做了优化，将所有的叶子节点串成一个有序链表，提高了范围查询的性能。B+树索引适用于范围查询和等值查询，并且在范围查询时性能更优。在许多数据库中，如MySQL的InnoDB存储引擎，使用的默认索引类型就是B+树索引。

哈希索引：

哈希索引使用哈希表来实现，适用于等值查询，对于范围查询效率较低。哈希索引在查询时的性能非常高，但是不支持范围查询，并且对于数据的插入和删除操作比较耗时。在某些数据库中，如MySQL的Memory存储引擎，可以使用哈希索引。

全文索引：

全文索引主要用于对文本类型的数据进行全文搜索，例如在文章内容中查找关键词。全文索引通常使用倒排索引（Inverted Index）来实现，可以快速定位到包含指定关键词的文档。在一些支持全文搜索的数据库中，如MySQL的MyISAM存储引擎和InnoDB存储引擎，都支持全文索引。

空间索引：

空间索引用于地理信息系统（GIS）中，用于快速查询空间数据，例如点、线、面等地理数据。空间索引的实现方式多种多样，包括R树、R*树等。在一些专门用于处理空间数据的数据库中，如PostGIS，都会使用空间索引来加速空间数据的查询。

复合索引：

复合索引是指对多个列组合建立的索引，可以用于支持多列的等值查询和范围查询。复合索引可以提高多列查询的性能，并且可以减少索引的数量，减小索引的存储空间。

9、加索引的原则？

选择合适的字段：

选择性高的字段：选择性指的是字段值的不重复度，选择性越高的字段适合建立索引。例如，性别字段通常只有两种取值，选择性很高，适合建立索引；而城市字段的选择性较低，不太适合建立索引。
频繁用于查询条件的字段：如果某个字段经常用于查询条件，那么这个字段就适合建立索引。

不要过度索引：

避免过多的索引：每个额外的索引都会增加写操作的开销，并占用额外的存储空间。过多的索引会增加维护成本，降低更新性能。
避免不必要的组合索引：组合索引是指联合多个字段创建的索引，过度使用组合索引可能会导致索引冗余，增加维护成本。

给经常查询的字段加索引：

给经常用于查询的字段加索引：例如，在经常进行查询的字段上加索引，可以提高查询的效率。但是，如果一个字段很少被查询，或者是只用于范围查询，那么就不适合加索引。

注意索引的覆盖查询：

考虑覆盖查询：覆盖查询指的是查询的字段都在索引中，不需要再去表中查找数据。覆盖查询可以减少IO操作，提高查询效率。

考虑查询的顺序：

根据查询的顺序添加索引：如果查询中的字段顺序是固定的，那么可以考虑按照这个顺序创建复合索引，以提高查询效率。

注意索引的维护成本：

考虑索引的维护成本：索引会增加写操作的成本，需要考虑索引的维护成本和查询效率之间的平衡。

10、最左匹配原则说一下+情景题？

最左匹配原则是指在复合索引中，如果查询条件是复合索引的一部分，那么查询时会从复合索引的最左边的列开始匹配，直到遇到不满足条件的列为止。这个原则在查询时决定了索引的使用情况，对于复合索引的查询非常重要。

最左匹配原则的情景举例：

假设有一个表 user，包含字段 id、name、age，现在在 name 和 age 上建立了一个复合索引 (name, age)。那么按照最左匹配原则，以下查询将如何使用索引：

查询条件包含两个字段：

sql

SELECT * FROM user WHERE name = 'Alice' AND age = 25;

这个查询条件包含了索引的全部字段，并且顺序与索引的顺序一致，因此可以完全利用索引。

查询条件只包含部分字段：

sql

SELECT * FROM user WHERE name = 'Alice';

这个查询条件只包含了索引的第一个字段 name，按照最左匹配原则，可以利用索引，但是只能利用到索引的第一个字段，对于索引的第二个字段 age 将不会使用索引。

查询条件包含索引的第二个字段：
sql
```
SELECT * FROM user WHERE age = 25;
```

这个查询条件只包含了索引的第二个字段 age，按照最左匹配原则，无法使用索引。

最左匹配原则的应用和优化：

在设计复合索引时，应该将最常用于查询条件的字段放在最左边，以便最大程度地利用索引。
避免在复合索引中过多地使用不必要的字段，这样会增加索引的大小和维护成本，降低查询效率。

11、算法：

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

思路：

使用两个指针 left 和 right 表示滑动窗口的左右边界，初始化为字符串 s 的开头。
移动 right 指针扩张窗口，直到窗口中包含了字符串 t 中的所有字符。
记录当前窗口的长度和起始位置。
移动 left 指针缩小窗口，直到不能再缩小为止，同时更新记录的最小窗口长度和起始位置。
重复步骤 2 和 4，直到 right 指针到达字符串 s 的末尾。

参考代码：

c++

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        // 使用哈希表 target 记录字符串 t 中的字符及其出现次数
        unordered_map<char, int> target, window;
        for (char c : t) {
            target[c]++;
        }

        int left = 0, right = 0; // 定义左右指针
        int minLen = INT_MAX, start = 0; // 记录最小窗口长度及起始位置
        int match = 0; // 记录匹配的字符个数

        while (right < s.size()) {
            char c1 = s[right];
            if (target.count(c1)) {
                window[c1]++;
                if (window[c1] == target[c1]) {
                    match++; // 如果当前字符的数量满足要求，则匹配数加一
                }
            }
            right++; // 右指针右移

            while (match == target.size()) {
                if (right - left < minLen) {
                    minLen = right - left; // 更新最小窗口长度和起始位置
                    start = left;
                }
                char c2 = s[left];
                if (target.count(c2)) {
                    window[c2]--;
                    if (window[c2] < target[c2]) {
                        match--; // 如果左边界出现不满足条件的字符，则匹配数减一
                    }
                }
                left++; // 左指针右移
            }
        }

        return minLen == INT_MAX ? "" : s.substr(start, minLen); // 返回最小窗口子串
    }
};

int main() {
    Solution solution;
    string s1 = "ADOBECODEBANC";
    string t1 = "ABC";
    string result1 = solution.minWindow(s1, t1);
    // 输出："BANC"
    cout << result1 << endl;

    string s2 = "a";
    string t2 = "a";
    string result2 = solution.minWindow(s2, t2);
    // 输出："a"
    cout << result2 << endl;

    string s3 = "a";
    string t3 = "aa";
    string result3 = solution.minWindow(s3, t3);
    // 输出：""
    cout << result3 << endl;

    return 0;
}

微服务

文档

基础

双非本滴滴一面 ​

Redis ​

1、reids中list的消息队列如何实现？ ​

2、reids如何实现的延时队列？ ​

3、redis中zset如何最早消费到数据？ ​

4、redis的zset怎么实现先进先出的？ ​

5、缓存穿透，缓存击穿，缓存雪崩是什么，要如何解决？ ​

6、具体解释下布隆过滤器？ ​

7、什么是表的物理存储顺序？ ​

8、索引的类型？ ​

9、加索引的原则？ ​

10、最左匹配原则说一下+情景题？ ​

11、算法： ​

双非本滴滴一面

Redis

1、reids中list的消息队列如何实现？

2、reids如何实现的延时队列？

3、redis中zset如何最早消费到数据？

4、redis的zset怎么实现先进先出的？

5、缓存穿透，缓存击穿，缓存雪崩是什么，要如何解决？

6、具体解释下布隆过滤器？

7、什么是表的物理存储顺序？

8、索引的类型？

9、加索引的原则？

10、最左匹配原则说一下+情景题？

11、算法：