【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 的原因：
-
无锁操作：CAS 是一种无锁操作，它允许多个线程在没有互斥量或锁的情况下对数据进行并发更新。这提高了整体性能，因为线程不需要等待锁，也不会因为锁竞争而上下文切换。
-
精细化锁定：尽管
ConcurrentHashMap使用了分段锁技术（在 Java 8 之前）和Node级别的锁定（在 Java 8 及以后）来降低锁的竞争，但某些操作，如计数器增加或某些节点状态的更新，可以通过 CAS 完成，以避免使用传统锁。 -
性能优势：相对于重量级锁，CAS 在高并发情况下通常提供更好的性能，尤其是当锁竞争较低时。CAS 的开销相对较小，这使得在高并发场景下，
ConcurrentHashMap的吞吐量和响应时间都有所提高。 -
线程安全的延迟初始化：
ConcurrentHashMap中的某些结构，如 table 数组，可以使用 CAS 进行线程安全的延迟初始化，这确保了只有一个线程可以成功地初始化数组，而其他线程则会看到已经初始化的版本。 -
实现无锁读：
ConcurrentHashMap允许完全无锁的读取操作。为了实现这一点，并保持数据的一致性，CAS 操作在更新数据时发挥了关键作用。
需要注意的是，尽管 CAS 提供了许多优势，但它并不是万能的。CAS 操作可能会因为其他线程的干扰而失败，导致自旋。但在实际应用中，由于 ConcurrentHashMap 的数据结构和策略选择，CAS 失败的次数通常很少，所以它仍然是一个非常高效的机制。
总的来说，CAS 是 ConcurrentHashMap 达到高并发性能的关键技术之一。
1.5 java里面有没有cas这个相关的类
是的，Java中有与CAS（Compare-and-Swap）操作相关的类，它位于java.util.concurrent.atomic包中。这个包提供了一些原子类，它们使用无锁的机制（通常是基于CAS操作）来支持线程安全的加法、递增、递减等操作。
以下是一些常用的原子类：
-
AtomicInteger: 一个整数值，可以被多个线程原子地更新。
- 主要方法：
get(),set(int newValue),getAndIncrement(),getAndDecrement(),compareAndSet(int expect, int update)等。
- 主要方法：
-
AtomicLong: 类似于
AtomicInteger，但用于长整数。 -
AtomicBoolean: 一个布尔值，可以被多个线程原子地更新。
-
AtomicReference<V>: 一个对象引用，支持原子性更新。
例如，使用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.6 java里的cas如何解决aba问题
是的，您触及了一个非常关键的点。compareAndSet操作确实是受到所谓的ABA问题的影响。ABA问题是指在一个线程读取某个值A、在另一个线程修改了这个值并将其设置为B然后又设置回A后，第一个线程再执行compareAndSet操作时，仍然会认为值没有变化。
但在上面的示例中，我们没有实际遇到ABA问题，因为这是一个简单的例子，仅展示了compareAndSet的基本使用。但在真实的多线程环境中，确实需要考虑ABA问题。
为了解决ABA问题，Java提供了AtomicStampedReference<V>类，它使用一个"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
}
}
在上面的例子中，即使值回到了0，由于stamp的改变，我们仍然可以知道在这之前发生了其他的操作，因此可以避免ABA问题。
2 mysql
2.1 innodb和myIsam的区别
3 redis
3.1 你用过redis的什么数据结构
实现限流器时，可以选择不同的数据结构和策略，具体选择哪种取决于所需的限流策略和具体场景。以下是一些常见的限流策略和对应的推荐数据结构：
-
固定窗口限流：
- 数据结构: 计数器 (通常使用 String 或 Hash in Redis)
- 实现: 每当有一个请求进来，都会将对应的计数器加一，并设置一个固定的过期时间。如果计数器超过了限制值，则拒绝请求。适合简单场景，但可能在窗口边界时出现请求高峰。
-
滑动窗口限流：
- 数据结构: 列表 (List in Redis) 或时间序列
- 实现: 记录每次请求的时间戳。当请求进来时，移除早于当前时间窗口的时间戳，并检查列表/时间序列中的条目数量。如果超过了限制，则拒绝请求。这种方法相对平滑，不会在窗口边界时突然放行或拒绝大量请求。
-
漏桶限流：
- 数据结构: 队列
- 实现: 将请求视为进入一个有固定容量的“桶”。如果桶满了，则拒绝新的请求。请求以固定的速率从桶中“漏出”。这种方法可以很好地应对突发流量。
-
令牌桶限流：
- 数据结构: 计数器
- 实现: 有一个令牌生成器，以固定速率生成令牌，并放入令牌桶。当请求进来时，尝试从桶中取出一个令牌。如果桶中没有令牌，则拒绝请求。这种方法允许一定程度的突发流量，因为令牌可以累积到一定数量。
如果使用 Redis 来实现限流器，INCR、EXPIRE、LIST 和 ZSET 等操作都很有用。例如，使用 INCR 和 EXPIRE 可以轻松实现固定窗口限流；使用 LPUSH、LTRIM 和 EXPIRE 可以实现滑动窗口限流。
在选择数据结构和策略时，需要考虑应用的具体需求，例如限流的精度、是否允许突发流量、限流器的性能要求等因素。
3.2 redis的hash和string的区别是什么呢？不都是key-value嘛hash结构什么时候会用到呢
确实，Redis 的 String 和 Hash 都是基于 key-value 的数据结构，但它们的用途和特点有所不同。
-
String 类型:
- 是最简单的类型，每个 key 只对应一个 value。
- value 可以是字符串、整数或浮点数。
- 可以进行数学操作，例如增加、减少值。
- 适用于存储简单的 key-value 数据，例如计数器、配置项、会话信息等。
-
Hash 类型:
- 每个 key 对应一个内部的 key-value 映射。这意味着 Hash 在 Redis 中实际上是一个嵌套的 key-value 结构，即 “field1” -> “value1”, “field2” -> “value2”。
- 适用于存储对象或者多个相关的数据点。例如，一个用户对象可能有多个属性（如 “name”、“age”、“email”），这些都可以作为一个 Hash 的字段存储。
- 对于部分更新或读取场景，Hash 更为高效。例如，你可以仅更新用户的 “email” 字段，而不需要获取和重新设置整个对象。
- Hash 结构在存储小数据对象时，更为存储高效。
Hash 的应用场景:
- 存储对象: 例如，用户的属性、商品信息、文章的元数据等。
- 部分更新: 当需要经常更新某个对象的部分字段时，Hash 是一个很好的选择。
- 存储关联数据: 如果你有一系列相关的数据点，可以将它们存储为 Hash，这样你可以一次性取回所有相关数据。
- 存储小数据量的字段: Hash 在存储少量字段时，相对于其他数据结构，如 JSON 字符串存储在 String 类型中，更为存储高效。
总之，虽然 String 和 Hash 都是 key-value 结构，但 Hash 提供了一种更复杂的、嵌套的 key-value 结构，非常适合存储和管理对象或多个相关的数据点。
4 秒杀
4.1 etcd解决超卖问题，能说一下吗
4.2 如果db那边处理扣减失败怎么办呢（重要）
答：秒杀场景中，高并发和数据一致性是两个关键的挑战。当在扣减真实库存时数据库操作失败，可以采取以下策略和措施来处理：
-
重试机制:
- 如果数据库操作失败是由于临时的网络波动或其他瞬时原因，可以考虑重试机制。
- 但需要注意，过于频繁的重试可能会加剧系统的压力。因此，重试策略需要有最大重试次数和适当的延迟策略。
-
回滚库存:
- 如果库存扣减失败，那么之前对预扣减的库存（例如在缓存中的预扣减）应当进行回滚，使其重新可用。
- 这需要确保整个操作是原子性的，要么都成功，要么都失败。
-
异步补偿机制:
- 使用消息队列或事件驱动的方法，将失败的扣减操作放入队列，后续通过异步补偿任务来重试。
- 这样即使实时操作失败，后续也有机会保持数据的一致性。
-
告警机制:
- 当库存扣减失败时，应立即触发告警，通知相关人员介入处理。
- 监控系统和日志分析是在这种场景中的关键工具。
-
限流和降级:
- 如果数据库压力过大导致操作失败，可以考虑启动限流策略，限制进一步的请求流量。
- 同时，启用服务降级，例如临时关闭秒杀活动，或者将用户引导到一个简化的流程。
-
数据库优化:
- 使用更高效的数据库操作，如批量更新，减少单点操作的数量。
- 考虑数据库的分区、分片等策略，以便更好地扩展并处理大量请求。
-
使用分布式锁:
- 在扣减库存的操作中使用分布式锁，确保在给定时刻只有一个操作在进行。
- 这可以避免并发操作导致的数据不一致，但可能会降低系统的并发处理能力。
-
备份方案:
- 如果主要的数据库操作持续失败，可以考虑启用备份方案，例如将请求转发到备用的数据库或服务。
秒杀场景下，应确保系统的韧性和可恢复性，以应对各种意外和故障。预期的失败和应对策略应在系统设计阶段就进行详细考虑。
4.3 我觉得可以将重试和回滚库存这两个策略结合起来
当然可以。将重试机制与库存回滚策略结合在秒杀场景中是一个很实用的做法。以下是一个结合两者的策略示例：
-
预扣减库存:
- 当用户尝试购买时，首先在缓存或其他高速存储中预扣减库存。
- 预扣减成功后，进行后续的数据库扣减操作。
-
数据库扣减与重试:
- 尝试在数据库中扣减真实的库存。
- 如果操作失败（可能是因为瞬时的网络问题、数据库繁忙等原因），则进入重试逻辑。
- 在重试逻辑中，设置最大的重试次数，例如3次，每次重试之间设置适当的延迟，如500ms。
- 如果在最大重试次数内仍然失败，则进入库存回滚策略。
-
库存回滚:
- 对于刚刚预扣减的库存，在缓存或其他高速存储中进行库存的回滚操作，将其恢复到之前的数量。
- 在这一步，也需要确保操作的原子性，确保数据的一致性。
-
用户反馈:
- 如果经过重试仍然失败并执行了库存回滚，需要及时通知用户操作失败，并给出相应的错误信息和建议。
结合重试机制与库存回滚策略，不仅可以提高成功处理的概率，还可以在真正的失败时，确保系统的数据一致性。但需要注意，这种策略在高并发的场景下需要确保高效的执行，避免不必要的延迟和系统压力。
5 mini-spring
5.1 讲一讲你怎么实现aop的
5.2 一级缓存怎么实现你的aop
5.3 为什么spring创建bean时需要三级缓存而不是二级，不是一级
确实，三级缓存设计的目的在于解决特定的问题，而这些问题在只有一级或二级缓存的情况下可能无法得到满足。让我们更深入地探讨为什么三级缓存和二级缓存不能融合，以及为什么两者都是必要的。
为什么需要三级缓存？
-
singletonFactories（三级缓存） 的存在是为了防止属性注入过程中的循环依赖。这是一个工厂方法，可以返回原始对象的早期引用，而这个对象可能还没有完全初始化。这种方法允许Spring在A依赖B，而B又依赖A的情况下，获取到A的早期引用，以完成B的初始化。
-
earlySingletonObjects（二级缓存） 存放已经实例化但还没有完成完整初始化的bean。这是一个中间步骤，确保其他bean可以引用它，即使它还没有被完全初始化。但这只是一个引用，不能用于创建新的bean实例。
-
使用三级缓存的一个重要原因是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代理的创建。考虑以下情景：
- A开始被初始化，但在完成前，它被放入三级缓存，即
singletonFactories，作为一个ObjectFactory。 - 在A的初始化过程中，B开始被初始化。
- B需要A。但A还没有完全初始化。此时，B可以从
singletonFactories（三级缓存）中获取到A的ObjectFactory，并通过这个工厂对象获得A的早期引用。 - 这个早期引用随后被放入二级缓存（
earlySingletonObjects）。 - B完成其初始化，并被放入一级缓存。
- 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();
}
}
7.2 gpt4的改进
首先，我看到了您试图实现一个基于滑动窗口的限流器。但这个实现有一些问题，这里列举一些问题和提议：
-
线程安全性:
ConcurrentHashMap本身是线程安全的，但当您执行mp.containsKey(key)后mp.get(key)的操作时，之间存在的时间间隔可能导致数据不一致。可能的解决方案是使用compute()或computeIfAbsent()方法。 -
滑动窗口的设计: 目前的实现并不是真正的滑动窗口，因为它只考虑了1秒内的请求数量。真正的滑动窗口会在窗口范围内滑动，可能需要更复杂的数据结构来实现。
-
时间戳的处理: 使用
Timestamp是可以的，但直接使用System.currentTimeMillis()作为long类型可能会更直观一些。 -
流控计数: 当窗口过期后，你应该重置计数。
考虑上述问题和建议，我为您提供了一个简化的实现（基于滑动窗口的精确实现通常更为复杂）：
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();
}
}
这个实现简化了一些逻辑，并确保了操作的原子性。但需要注意，这并不是滑动窗口的完整或最优实现，仅仅是一个起点。