【2024秋招】腾讯云智武汉后端开发一面 2023-9-20

1 java

1.1 hashMap

1.2 哈希冲突的解决方法

1.3 讲解一下CAS的aba问题

1.4 concurrentHashMap的并发方案为什么要使用cas

ConcurrentHashMap 是 Java 并发包 java.util.concurrent 中的一个重要组件，用于提供高并发、高性能、线程安全的哈希映射。为了达到这样的性能，ConcurrentHashMap 在其内部实现中使用了多种并发策略，其中 CAS (Compare-And-Swap) 是其关键技术之一。以下是使用 CAS 的原因：

1. 无锁操作：CAS 是一种无锁操作，它允许多个线程在没有互斥量或锁的情况下对数据进行并发更新。这提高了整体性能，因为线程不需要等待锁，也不会因为锁竞争而上下文切换。

2. 精细化锁定：尽管 ConcurrentHashMap 使用了分段锁技术（在 Java 8 之前）和 Node 级别的锁定（在 Java 8 及以后）来降低锁的竞争，但某些操作，如计数器增加或某些节点状态的更新，可以通过 CAS 完成，以避免使用传统锁。

3. 性能优势：相对于重量级锁，CAS 在高并发情况下通常提供更好的性能，尤其是当锁竞争较低时。CAS 的开销相对较小，这使得在高并发场景下，ConcurrentHashMap 的吞吐量和响应时间都有所提高。

4. 线程安全的延迟初始化：ConcurrentHashMap 中的某些结构，如 table 数组，可以使用 CAS 进行线程安全的延迟初始化，这确保了只有一个线程可以成功地初始化数组，而其他线程则会看到已经初始化的版本。

5. 实现无锁读：ConcurrentHashMap 允许完全无锁的读取操作。为了实现这一点，并保持数据的一致性，CAS 操作在更新数据时发挥了关键作用。

需要注意的是，尽管 CAS 提供了许多优势，但它并不是万能的。CAS 操作可能会因为其他线程的干扰而失败，导致自旋。但在实际应用中，由于 ConcurrentHashMap 的数据结构和策略选择，CAS 失败的次数通常很少，所以它仍然是一个非常高效的机制。

总的来说，CAS 是 ConcurrentHashMap 达到高并发性能的关键技术之一。

1.5 java里面有没有cas这个相关的类

是的，Java中有与CAS（Compare-and-Swap）操作相关的类，它位于java.util.concurrent.atomic包中。这个包提供了一些原子类，它们使用无锁的机制（通常是基于CAS操作）来支持线程安全的加法、递增、递减等操作。

以下是一些常用的原子类：

1. AtomicInteger: 一个整数值，可以被多个线程原子地更新。

   • 主要方法：get(), set(int newValue), getAndIncrement(), getAndDecrement(), compareAndSet(int expect, int update)等。

2. AtomicLong: 类似于AtomicInteger，但用于长整数。

3. AtomicBoolean: 一个布尔值，可以被多个线程原子地更新。

4. AtomicReference: 一个对象引用，支持原子性更新。

例如，使用AtomicInteger的CAS操作：

import java.util.concurrent.atomic.AtomicInteger;

public class CASDemo {
    public static void main(String[] args) {
        AtomicInteger atomicInt = new AtomicInteger(0);

        // CAS操作
        boolean updated = atomicInt.compareAndSet(0, 1);  // 如果当前值为0，那么更新为1
        System.out.println(updated);  // 输出: true
        System.out.println(atomicInt.get());  // 输出: 1

        updated = atomicInt.compareAndSet(0, 2);  // 由于当前值为1，这个CAS操作将失败
        System.out.println(updated);  // 输出: false
        System.out.println(atomicInt.get());  // 输出: 1
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这些原子类可以在高并发环境中提供性能优势，因为它们通常不需要使用重的锁。然而，它们的使用必须小心，以确保算法的整体正确性。

1.6 java里的cas如何解决aba问题

是的，您触及了一个非常关键的点。compareAndSet操作确实是受到所谓的ABA问题的影响。ABA问题是指在一个线程读取某个值A、在另一个线程修改了这个值并将其设置为B然后又设置回A后，第一个线程再执行compareAndSet操作时，仍然会认为值没有变化。

但在上面的示例中，我们没有实际遇到ABA问题，因为这是一个简单的例子，仅展示了compareAndSet的基本使用。但在真实的多线程环境中，确实需要考虑ABA问题。

为了解决ABA问题，Java提供了AtomicStampedReference类，它使用一个"stamp"（类似于版本号）来跟踪变量的更改。每次变量被修改时，stamp都会递增。这样，即使值回到了之前的状态，stamp也会是不同的，因此线程可以知道在它读取值之后发生了多少次修改。

例如：

import java.util.concurrent.atomic.AtomicStampedReference;

public class CASDemo {
    public static void main(String[] args) {
        AtomicStampedReference<Integer> atomicRef = new AtomicStampedReference<>(0, 0);

        int stamp = atomicRef.getStamp();
        boolean updated = atomicRef.compareAndSet(0, 1, stamp, stamp + 1);
        System.out.println(updated);  // 输出: true
        System.out.println(atomicRef.getReference());  // 输出: 1

        // 模拟ABA问题
        stamp = atomicRef.getStamp();
        atomicRef.compareAndSet(1, 2, stamp, stamp + 1);
        stamp = atomicRef.getStamp();
        atomicRef.compareAndSet(2, 0, stamp, stamp + 1);

        stamp = atomicRef.getStamp();
        updated = atomicRef.compareAndSet(0, 3, stamp - 2, stamp + 1);  // 尝试使用旧的stamp
        System.out.println(updated);  // 输出: false
        System.out.println(atomicRef.getReference());  // 输出: 0
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

在上面的例子中，即使值回到了0，由于stamp的改变，我们仍然可以知道在这之前发生了其他的操作，因此可以避免ABA问题。

2 mysql

2.1 innodb和myIsam的区别

3 redis

3.1 你用过redis的什么数据结构

实现限流器时，可以选择不同的数据结构和策略，具体选择哪种取决于所需的限流策略和具体场景。以下是一些常见的限流策略和对应的推荐数据结构：

1. 固定窗口限流：

   • 数据结构: 计数器 (通常使用 String 或 Hash in Redis)
   • 实现: 每当有一个请求进来，都会将对应的计数器加一，并设置一个固定的过期时间。如果计数器超过了限制值，则拒绝请求。适合简单场景，但可能在窗口边界时出现请求高峰。

2. 滑动窗口限流：

   • 数据结构: 列表 (List in Redis) 或时间序列
   • 实现: 记录每次请求的时间戳。当请求进来时，移除早于当前时间窗口的时间戳，并检查列表/时间序列中的条目数量。如果超过了限制，则拒绝请求。这种方法相对平滑，不会在窗口边界时突然放行或拒绝大量请求。

3. 漏桶限流：

   • 数据结构: 队列
   • 实现: 将请求视为进入一个有固定容量的“桶”。如果桶满了，则拒绝新的请求。请求以固定的速率从桶中“漏出”。这种方法可以很好地应对突发流量。

4. 令牌桶限流：

   • 数据结构: 计数器
   • 实现: 有一个令牌生成器，以固定速率生成令牌，并放入令牌桶。当请求进来时，尝试从桶中取出一个令牌。如果桶中没有令牌，则拒绝请求。这种方法允许一定程度的突发流量，因为令牌可以累积到一定数量。

如果使用 Redis 来实现限流器，INCR、EXPIRE、LIST 和 ZSET 等操作都很有用。例如，使用 INCR 和 EXPIRE 可以轻松实现固定窗口限流；使用 LPUSH、LTRIM 和 EXPIRE 可以实现滑动窗口限流。

在选择数据结构和策略时，需要考虑应用的具体需求，例如限流的精度、是否允许突发流量、限流器的性能要求等因素。

3.2 redis的hash和string的区别是什么呢？不都是key-value嘛hash结构什么时候会用到呢

确实，Redis 的 String 和 Hash 都是基于 key-value 的数据结构，但它们的用途和特点有所不同。

1. String 类型:

   • 是最简单的类型，每个 key 只对应一个 value。
   • value 可以是字符串、整数或浮点数。
   • 可以进行数学操作，例如增加、减少值。
   • 适用于存储简单的 key-value 数据，例如计数器、配置项、会话信息等。

2. Hash 类型:

   • 每个 key 对应一个内部的 key-value 映射。这意味着 Hash 在 Redis 中实际上是一个嵌套的 key-value 结构，即 “field1” -> “value1”, “field2” -> “value2”。
   • 适用于存储对象或者多个相关的数据点。例如，一个用户对象可能有多个属性（如 “name”、“age”、“email”），这些都可以作为一个 Hash 的字段存储。
   • 对于部分更新或读取场景，Hash 更为高效。例如，你可以仅更新用户的 “email” 字段，而不需要获取和重新设置整个对象。
   • Hash 结构在存储小数据对象时，更为存储高效。

Hash 的应用场景:

1. 存储对象: 例如，用户的属性、商品信息、文章的元数据等。
2. 部分更新: 当需要经常更新某个对象的部分字段时，Hash 是一个很好的选择。
3. 存储关联数据: 如果你有一系列相关的数据点，可以将它们存储为 Hash，这样你可以一次性取回所有相关数据。
4. 存储小数据量的字段: Hash 在存储少量字段时，相对于其他数据结构，如 JSON 字符串存储在 String 类型中，更为存储高效。

总之，虽然 String 和 Hash 都是 key-value 结构，但 Hash 提供了一种更复杂的、嵌套的 key-value 结构，非常适合存储和管理对象或多个相关的数据点。

4 秒杀

4.1 etcd解决超卖问题，能说一下吗

4.2 如果db那边处理扣减失败怎么办呢（重要）

答：秒杀场景中，高并发和数据一致性是两个关键的挑战。当在扣减真实库存时数据库操作失败，可以采取以下策略和措施来处理：

1. 重试机制:

   • 如果数据库操作失败是由于临时的网络波动或其他瞬时原因，可以考虑重试机制。
   • 但需要注意，过于频繁的重试可能会加剧系统的压力。因此，重试策略需要有最大重试次数和适当的延迟策略。

2. 回滚库存:

   • 如果库存扣减失败，那么之前对预扣减的库存（例如在缓存中的预扣减）应当进行回滚，使其重新可用。
   • 这需要确保整个操作是原子性的，要么都成功，要么都失败。

3. 异步补偿机制:

   • 使用消息队列或事件驱动的方法，将失败的扣减操作放入队列，后续通过异步补偿任务来重试。
   • 这样即使实时操作失败，后续也有机会保持数据的一致性。

4. 告警机制:

   • 当库存扣减失败时，应立即触发告警，通知相关人员介入处理。
   • 监控系统和日志分析是在这种场景中的关键工具。

5. 限流和降级:

   • 如果数据库压力过大导致操作失败，可以考虑启动限流策略，限制进一步的请求流量。
   • 同时，启用服务降级，例如临时关闭秒杀活动，或者将用户引导到一个简化的流程。

6. 数据库优化:

   • 使用更高效的数据库操作，如批量更新，减少单点操作的数量。
   • 考虑数据库的分区、分片等策略，以便更好地扩展并处理大量请求。

7. 使用分布式锁:

   • 在扣减库存的操作中使用分布式锁，确保在给定时刻只有一个操作在进行。
   • 这可以避免并发操作导致的数据不一致，但可能会降低系统的并发处理能力。

8. 备份方案:

   • 如果主要的数据库操作持续失败，可以考虑启用备份方案，例如将请求转发到备用的数据库或服务。

秒杀场景下，应确保系统的韧性和可恢复性，以应对各种意外和故障。预期的失败和应对策略应在系统设计阶段就进行详细考虑。

4.3 我觉得可以将重试和回滚库存这两个策略结合起来

当然可以。将重试机制与库存回滚策略结合在秒杀场景中是一个很实用的做法。以下是一个结合两者的策略示例：

1. 预扣减库存:

   • 当用户尝试购买时，首先在缓存或其他高速存储中预扣减库存。
   • 预扣减成功后，进行后续的数据库扣减操作。

2. 数据库扣减与重试:

   • 尝试在数据库中扣减真实的库存。
   • 如果操作失败（可能是因为瞬时的网络问题、数据库繁忙等原因），则进入重试逻辑。
   • 在重试逻辑中，设置最大的重试次数，例如3次，每次重试之间设置适当的延迟，如500ms。
   • 如果在最大重试次数内仍然失败，则进入库存回滚策略。

3. 库存回滚:

   • 对于刚刚预扣减的库存，在缓存或其他高速存储中进行库存的回滚操作，将其恢复到之前的数量。
   • 在这一步，也需要确保操作的原子性，确保数据的一致性。

4. 用户反馈:

   • 如果经过重试仍然失败并执行了库存回滚，需要及时通知用户操作失败，并给出相应的错误信息和建议。

结合重试机制与库存回滚策略，不仅可以提高成功处理的概率，还可以在真正的失败时，确保系统的数据一致性。但需要注意，这种策略在高并发的场景下需要确保高效的执行，避免不必要的延迟和系统压力。

5 mini-spring

5.1 讲一讲你怎么实现aop的

5.2 一级缓存怎么实现你的aop

5.3 为什么spring创建bean时需要三级缓存而不是二级，不是一级

确实，三级缓存设计的目的在于解决特定的问题，而这些问题在只有一级或二级缓存的情况下可能无法得到满足。让我们更深入地探讨为什么三级缓存和二级缓存不能融合，以及为什么两者都是必要的。

为什么需要三级缓存？

1. singletonFactories（三级缓存） 的存在是为了防止属性注入过程中的循环依赖。这是一个工厂方法，可以返回原始对象的早期引用，而这个对象可能还没有完全初始化。这种方法允许Spring在A依赖B，而B又依赖A的情况下，获取到A的早期引用，以完成B的初始化。

2. earlySingletonObjects（二级缓存） 存放已经实例化但还没有完成完整初始化的bean。这是一个中间步骤，确保其他bean可以引用它，即使它还没有被完全初始化。但这只是一个引用，不能用于创建新的bean实例。

3. 使用三级缓存的一个重要原因是Spring的AOP和其他后处理机制。这些机制可能会在bean完全初始化之前，对其进行修改或包裹。所以，为了保证能够获取到正确的对象版本，而不仅仅是原始的、未经处理的bean实例，Spring引入了ObjectFactory来实现延迟解析，只有当真正需要时才会触发真正的bean创建。

为什么不能融合？

两者的主要区别在于其目的和内容：

• 三级缓存（singletonFactories）中存储的是创建bean实例的工厂对象，它可以产生bean实例，尤其是代理实例，因为bean有多个扩展点，后面的扩展点可能会包装前面的旧代理，生成新的代理，这就需要三级缓存中存的工厂对象生成新代理对象。
• 二级缓存（earlySingletonObjects）中存储的是已经部分初始化的bean实例本身。

当我们尝试解决循环依赖问题时，我们首先从三级缓存中获取bean工厂，用它来创建一个早期版本的bean，并存储在二级缓存中。这样，当其他bean试图在其初始化过程中引用这个早期bean时，它可以从二级缓存中直接获取，而不需要再次创建。

如果我们尝试融合这两个缓存，就会失去分离"如何创建bean"（三级缓存）和"早期的bean引用"（二级缓存）的能力，这是解决循环依赖的关键。

综上所述，为了有效地处理循环依赖，并确保bean的创建和引用都是高效和正确的，Spring选择了使用三级缓存而不是仅仅融合为一个或两个缓存。

5.4 循环依赖的解决过程

你的描述确实准确地描述了循环依赖的解决过程，而且是在只涉及一级和二级缓存的情况下。但三级缓存的作用在特定情况下是必要的，特别是在涉及bean工厂对象（即ObjectFactory）时。

为了更加准确地理解三级缓存的角色，我们要考虑到bean的生命周期和AOP代理的创建。考虑以下情景：

1. A开始被初始化，但在完成前，它被放入三级缓存，即singletonFactories，作为一个ObjectFactory。
2. 在A的初始化过程中，B开始被初始化。
3. B需要A。但A还没有完全初始化。此时，B可以从singletonFactories（三级缓存）中获取到A的ObjectFactory，并通过这个工厂对象获得A的早期引用。
4. 这个早期引用随后被放入二级缓存（earlySingletonObjects）。
5. B完成其初始化，并被放入一级缓存。
6. A接着完成其初始化，并被放入一级缓存。

这种情况经常发生在涉及Spring AOP时。例如，当A是一个需要被代理的bean（可能因为事务、安全等原因），其实际的bean实例会被一个代理包裹。在这种情况下，singletonFactories缓存中存放的ObjectFactory能够生产出正确的代理对象，而不仅仅是原始的bean实例。

所以，虽然在简单的循环依赖情况下，你可能只看到了一级和二级缓存的作用，但在涉及复杂的bean生命周期和AOP代理的场景下，三级缓存是必要的。

5.5 如果A不是一个代理对象，在早期直接放入二级缓存就可以了对吧

是的，你是对的。如果A不是一个代理对象或不需要经过其他复杂的生命周期处理，它的早期引用可以直接放入二级缓存（earlySingletonObjects）。但如果A需要被代理或有其他后处理操作，那么使用ObjectFactory（放在三级缓存singletonFactories中）是有用的，因为这个工厂能够在被触发时生产出正确的对象（例如代理对象）。

6 rpc

6.1 讲讲rpc框架的调用流程

7 算法题

7.1 写一个滑动窗口的限流器，每秒限流100次，返回true或者false就行（带测试用例）

答：我每一秒产生一个限流器，限流的大小是100，这样会产生最多1s的误差；同时使用ConcurrentHashMap保证并发安全

class LimitFlowObject{
    Integer flowNum;
    Timestamp timestamp;


    public final static Integer THRESHOLD_FLOW=100;
    // 存放限流窗口
    static ConcurrentHashMap<String, LimitFlowObject> mp=new ConcurrentHashMap<>();
    static boolean limitFlow(String user,String interfaceName){
        String key=user+":"+interfaceName;
        long curTimeStamp= System.currentTimeMillis();

        if(mp.containsKey(key)&&mp.get(key).timestamp.getTime()>curTimeStamp){
            LimitFlowObject limitFlowObject=mp.get(key);
            limitFlowObject.flowNum+=1;
            mp.put(key, limitFlowObject);
        }else{
            LimitFlowObject limitFlowObject=new LimitFlowObject();
            limitFlowObject.flowNum=1;
            limitFlowObject.timestamp=new Timestamp(curTimeStamp+1000);
            mp.put(key, limitFlowObject);
        }

        if(mp.get(key).flowNum>THRESHOLD_FLOW){
            return false;
        }
        return true;
    }

    public static void main(String[] args) {

        Thread t1=new Thread(new Runnable() {
            @Override
            public void run() {

                for (int i = 0; i < 50; i++) {
                    boolean f=limitFlow("a","b");
                    if(!f)
                        System.out.println("ith call:"+i+", "+"res:"+f);
                }


                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                for (int i = 50; i < 153; i++) {
                    boolean f=limitFlow("a","b");
                    if(!f)
                        System.out.println("ith call:"+i+", "+"res:"+f);
                }
            }
        });

        t1.start();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

7.2 gpt4的改进

首先，我看到了您试图实现一个基于滑动窗口的限流器。但这个实现有一些问题，这里列举一些问题和提议：

1. 线程安全性: ConcurrentHashMap 本身是线程安全的，但当您执行 mp.containsKey(key) 后 mp.get(key) 的操作时，之间存在的时间间隔可能导致数据不一致。可能的解决方案是使用 compute() 或 computeIfAbsent() 方法。

2. 滑动窗口的设计: 目前的实现并不是真正的滑动窗口，因为它只考虑了1秒内的请求数量。真正的滑动窗口会在窗口范围内滑动，可能需要更复杂的数据结构来实现。

3. 时间戳的处理: 使用 Timestamp 是可以的，但直接使用 System.currentTimeMillis() 作为long类型可能会更直观一些。

4. 流控计数: 当窗口过期后，你应该重置计数。

考虑上述问题和建议，我为您提供了一个简化的实现（基于滑动窗口的精确实现通常更为复杂）：

import java.sql.Timestamp;
import java.util.concurrent.ConcurrentHashMap;

class LimitFlowObject {
    Integer flowNum;
    long timestamp;

    public final static Integer THRESHOLD_FLOW = 100;
    static ConcurrentHashMap<String, LimitFlowObject> mp = new ConcurrentHashMap<>();

    static boolean limitFlow(String user, String interfaceName) {
        String key = user + ":" + interfaceName;
        long curTimeStamp = System.currentTimeMillis();

        return mp.compute(key, (k, limitFlowObject) -> {
            if (limitFlowObject == null || limitFlowObject.timestamp <= curTimeStamp) {
                limitFlowObject = new LimitFlowObject();
                limitFlowObject.flowNum = 1;
                limitFlowObject.timestamp = curTimeStamp + 1000;
            } else {
                limitFlowObject.flowNum++;
            }
            return limitFlowObject;
        }).flowNum <= THRESHOLD_FLOW;
    }

    public static void main(String[] args) {
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 50; i++) {
                boolean f = limitFlow("a", "b");
                if (!f)
                    System.out.println("ith call:" + i + ", " + "res:" + f);
            }

            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            for (int i = 50; i < 153; i++) {
                boolean f = limitFlow("a", "b");
                if (!f)
                    System.out.println("ith call:" + i + ", " + "res:" + f);
            }
        });

        t1.start();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

这个实现简化了一些逻辑，并确保了操作的原子性。但需要注意，这并不是滑动窗口的完整或最优实现，仅仅是一个起点。