2024面试复盘10

编程随想面经

字数统计: 4.5k阅读时长: 17 min

 2024/08/05   Share

前言

滴滴面试，面试官人很亲切。除了netty相关，其他都回答的七七八八，奈何人家就是用netty去做业务的，估计也是凉凉。

复盘

分布式锁场景?怎么实现

复盘过好多次了，就是redis去实现。

场景：

分布式锁是一种用于在分布式系统中协调对共享资源访问的技术，确保在多个节点同时访问某一资源时不会出现竞争和数据不一致问题。

分布式缓存一致性：当多个应用实例需要更新同一个缓存数据时，使用分布式锁可以确保只有一个实例可以进行更新操作，避免缓存不一致问题。

任务调度：在分布式任务调度系统中，为了防止同一个任务被多个节点重复执行，可以使用分布式锁来确保任务只会被一个节点执行。

限流控制：在高并发系统中，使用分布式锁可以限制同时处理的请求数量，避免系统过载。

分布式事务：在分布式事务中，使用分布式锁可以确保多个节点在执行跨数据库或跨服务的事务时，能够按照预期的顺序进行，避免数据不一致。

资源协调：在分布式系统中，多个节点可能需要访问共享资源（如文件、数据库记录等）。使用分布式锁可以确保每次只有一个节点能访问这些资源，避免竞争条件。

锁的自动续期

watchdog大部分回答出来了，后续再复习下。

redisson中如何解决主从同步问题

在使用 Redisson 实现分布式锁时，如果 Redis 处于主从模式（master-slave replication），可能会遇到主从同步问题。主从同步问题主要体现在以下几个方面：

主节点崩溃和故障转移：当主节点崩溃时，从节点会接管成为新的主节点。在这个过程中，可能会出现锁状态丢失或不一致的问题。
数据复制延迟：主节点和从节点之间的数据复制存在延迟，在这种情况下，从节点上的锁状态可能会滞后，导致数据不一致。

redLock

其实就是类似 redLock，通过将所有节点视为主节点。

Redlock 需要部署 N （N >= 2n+1）个独立的 Redis 实例，且实例之间没有任何的联系。也就是说，只要一半以上的 Redis 实例加锁成功，那么 Redlock 依然可以正常运行。

使用独立实例是为了避免 Redis 异步复制导致锁丢失。

Redlock 加锁失败有两种情况：

加锁成功的实例数量未超过半数。
加锁过程花费时间超过锁的有效时间。

强制主节点读取锁

config.useMasterSlaveServers()
      .setMasterAddress("redis://127.0.0.1:6379")
      .addSlaveAddress("redis://127.0.0.1:6380", "redis://127.0.0.1:6381")
      .setReadMode(ReadMode.MASTER);

其他方式实现分布式锁

除了数据库方式还有其他方式？

基于Zookeeper：

在zookeeper中创建一个锁节点
检查在锁节点的兄弟节点中是否自己创建的节点是最小的。如果是，说明获取到了锁；否则，监听前一个节点的删除事件。
删除自己创建的锁节点，释放锁。

基于etcd:

在 etcd 中创建一个带有租约的键，作为锁的标识。
通过原子操作（如 PUT 请求）确保只有一个客户端能够创建该键。
保持租约的有效性，避免锁过期。
删除创建的键，释放锁。

当然这两种方式比较少用。

布隆过滤器？实现？设计的hash值和函数有什么要求？

布隆过滤器（Bloom Filter）是一种高效的概率数据结构，用于判断一个元素是否存在于一个集合中。它有很高的空间效率和查询效率，但有一定的误判率，即可能会误认为某个不在集合中的元素存在于集合中。布隆过滤器不存储实际的元素，只存储元素的哈希值。

布隆过滤器的基本原理

初始化：创建一个位数组，初始时所有位都设为0。
添加元素：使用k个不同的哈希函数将元素映射到位数组的k个位置上，并将这些位置的值设为1。
查询元素：使用同样的k个哈希函数将查询元素映射到位数组的k个位置上。如果所有这些位置上的值都是1，则认为该元素可能在集合中；如果有任意一个位置上的值为0，则可以确定该元素不在集合中。

优点：

空间效率高：相比于直接存储元素集合，布隆过滤器使用的空间要少得多。
插入和查询速度快：时间复杂度为O(k)，k是哈希函数的数量。

缺点：

存在误判率：查询结果为“存在”时，可能是误判，但查询结果为“不存在”时一定是准确的。
无法删除元素：标准布隆过滤器不支持删除操作，删除元素可能会影响其他元素的存在判断。

下面实现代码是GPT写的

import java.util.BitSet;
import java.util.Random;

public class BloomFilter {
    private BitSet bitSet;
    private int size;
    private int[] hashSeeds;
    private Random random;

    public BloomFilter(int bitSetSize, int hashCount) {
        this.size = bitSetSize;
        this.bitSet = new BitSet(size);
        this.hashSeeds = new int[hashCount];
        this.random = new Random();

        // Initialize hash seeds with random values
        for (int i = 0; i < hashCount; i++) {
            hashSeeds[i] = random.nextInt();
        }
    }

    // Simple hash function
    private int hash(String value, int seed) {
        int result = 0;
        for (char c : value.toCharArray()) {
            result = result * seed + c;
        }
        return (size - 1) & result; // Modulo size to ensure it is within the range
    }

    // Add an element to the Bloom filter
    public void add(String value) {
        for (int seed : hashSeeds) {
            int hash = hash(value, seed);
            bitSet.set(hash);
        }
    }

    // Check if an element might be in the Bloom filter
    public boolean mightContain(String value) {
        for (int seed : hashSeeds) {
            int hash = hash(value, seed);
            if (!bitSet.get(hash)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter(1024, 3);
        bloomFilter.add("hello");
        bloomFilter.add("world");

        System.out.println(bloomFilter.mightContain("hello")); // True
        System.out.println(bloomFilter.mightContain("world")); // True
        System.out.println(bloomFilter.mightContain("bloom")); // False
        System.out.println(bloomFilter.mightContain("filter")); // False
    }
}

Netty线程模型

Netty 基于 NIO （NIO 是一种同步非阻塞的 I/O 模型，在 Java 1.4 中引入了 NIO），使用 Netty 可以极大地简化 TCP 和 UDP 套接字服务器等网络编程，并且性能以及安全性等很多方面都非常优秀。

NIO 是一种同步非阻塞的 I/O 模型，于 Java 1.4 中引入，对应 java.nio包，提供了 Channel , Selector，Buffer 等抽象。NIO 中的 N 可以理解为 Non-blocking，不单纯是 New。它支持面向缓冲的，基于通道的 I/O 操作方法。 NIO 提供了与传统 BIO 模型中的 Socket 和 ServerSocket 相对应的 SocketChannel 和 ServerSocketChannel 两种不同的套接字通道实现,两种通道都支持阻塞和非阻塞两种模式。对于高负载、高并发的（网络）应用，应使用 NIO 的非阻塞模式来开发

netty不用 NIO 主要是因为 NIO 的编程模型复杂而且存在一些 BUG，并且对编程功底要求比较高。而且，NIO 在面对断连重连、包丢失、粘包等问题时处理过程非常复杂。Netty 的出现正是为了解决这些问题，更多关于 Netty 的特点可以看下面的内容。

Reactor 是一种经典的线程模型，Reactor 模式基于事件驱动，特别适合处理海量的 I/O 事件。

单线程 Reactor

所有的 IO 操作都由同一个 NIO 线程处理。

单线程 Reactor 的优点是对系统资源消耗特别小，但是，没办法支撑大量请求的应用场景并且处理请求的时间可能非常慢。

多线程 Reactor

一个线程负责接受请求,一组 NIO 线程处理 IO 操作。

大部分场景下多线程 Reactor 模型是没有问题的，但是在一些并发连接数比较多（如百万并发）的场景下，一个线程负责接受客户端请求就存在性能问题了。

为了解决这些问题，演进出了主从多线程 Reactor 模型。

主从多线程 Reactor

一组 NIO 线程负责接受请求，一组 NIO 线程处理 IO 操作。

在 Netty 主要靠 NioEventLoopGroup 线程池来实现具体的线程模型的。

我们实现服务端的时候，一般会初始化两个线程组：

bossGroup :接收连接。
workerGroup ：负责具体的处理，交由对应的 Handler 处理。

从一个主线程 NIO 线程池中选择一个线程作为 Acceptor 线程，绑定监听端口，接收客户端连接的连接，其他线程负责后续的接入认证等工作。连接建立完成后，Sub NIO 线程池负责具体处理 I/O 读写。

// 1.bossGroup 用于接收连接，workerGroup 用于具体的处理
EventLoopGroup bossGroup = new NioEventLoopGroup(1);
EventLoopGroup workerGroup = new NioEventLoopGroup();
try {
    //2.创建服务端启动引导/辅助类：ServerBootstrap
    ServerBootstrap b = new ServerBootstrap();
    //3.给引导类配置两大线程组,确定了线程模型
    b.group(bossGroup, workerGroup)
            // (非必备)打印日志
            .handler(new LoggingHandler(LogLevel.INFO))
            // 4.指定 IO 模型
            .channel(NioServerSocketChannel.class)
            .childHandler(new ChannelInitializer<SocketChannel>() {
                @Override
                public void initChannel(SocketChannel ch) {
                    ChannelPipeline p = ch.pipeline();
                    //5.可以自定义客户端消息的业务处理逻辑
                    p.addLast(new HelloServerHandler());
                }
            });
    // 6.绑定端口,调用 sync 方法阻塞知道绑定完成
    ChannelFuture f = b.bind(port).sync();
    // 7.阻塞等待直到服务器Channel关闭(closeFuture()方法获取Channel 的CloseFuture对象,然后调用sync()方法)
    f.channel().closeFuture().sync();
} finally {
    //8.优雅关闭相关线程组资源
    bossGroup.shutdownGracefully();
    workerGroup.shutdownGracefully();
}

具体流程如下：

1、首先你创建了两个 NioEventLoopGroup 对象实例：bossGroup 和 workerGroup。

bossGroup : 用于处理客户端的 TCP 连接请求。
workerGroup ：负责每一条连接的具体读写数据的处理逻辑，真正负责 I/O 读写操作，交由对应的 Handler 处理。

这里要注意使用 NioEventLoopGroup 类的无参构造函数设置线程数量的默认值就是 CPU 核心数 *2 。

2、接下来我们创建了一个服务端启动引导/辅助类： ServerBootstrap，这个类将引导我们进行服务端的启动工作。

3、通过 group() 方法给引导类 ServerBootstrap 配置两大线程组，确定了线程模型。

4、通过channel()方法给引导类 ServerBootstrap指定了 IO 模型为NIO

NioServerSocketChannel ：指定服务端的 IO 模型为 NIO，与 BIO 编程模型中的ServerSocket对应
NioSocketChannel : 指定客户端的 IO 模型为 NIO，与 BIO 编程模型中的Socket对应

5、通过 childHandler()方法给引导类创建一个ChannelInitializer ，然后指定了服务端消息的业务处理逻辑 HelloServerHandler 对象。

6、调用 ServerBootstrap 类的 bind()方法绑定端口。

TCP 粘包/拆包

1.使用 Netty 自带的解码器

LineBasedFrameDecoder : 发送端发送数据包的时候，每个数据包之间以换行符作为分隔，LineBasedFrameDecoder 的工作原理是它依次遍历 ByteBuf 中的可读字节，判断是否有换行符，然后进行相应的截取。
DelimiterBasedFrameDecoder : 可以自定义分隔符解码器，实际上是一种特殊的 DelimiterBasedFrameDecoder 解码器。
FixedLengthFrameDecoder: 固定长度解码器，它能够按照指定的长度对消息进行相应的拆包。如果不够指定的长度，则空格补全
LengthFieldBasedFrameDecoder：长度域解码器，它能够根据发送的数据中消息长度相关参数（比如长度域偏移量 lengthFieldOffset）来进行拆包。

Netty其他知识后面再梳理下。

Java锁的实现方式

一个是synchronized另一个是ReentrantLock(AQS).

还有个乐观锁(AtomicInteger).

CAS 是一种原子操作，用于确保在多线程环境中，某个值在更新时不会被其他线程修改。Java的 java.util.concurrent.atomic 包提供了一些基于 CAS 的类，这些类实现了乐观锁机制。

例如AtomicInteger, AtomicReference, AtomicStampedReference

AtomicInteger就不说了。
AtomicReference 是用于原子操作引用类型的类。它允许原子地更新对象引用，适用于需要保证对象的线程安全的场景。例如AtomicReference<String> reference = new AtomicReference<>("Initial");
AtomicStampedReference 提供了对引用类型的原子操作，并结合了一个整数戳（通常是版本号），用于解决ABA问题。这个我还没用过。

AtomicStampedReference<String> stampedReference =
            new AtomicStampedReference<>("Initial", 0);
int[] stamp = new int[1];
        String oldValue = stampedReference.get(stamp);
        stampedReference.set(newValue, stamp[0] + 1);

限流了解吗

令牌桶算法（Token Bucket Algorithm）

令牌桶算法使用一个“桶”来控制数据的流入速率。

桶里有令牌，令牌以固定速率生成。

每次请求需要获取一个令牌，令牌桶中的令牌数量不足时，请求会被拒绝或等待。

令牌桶算法允许突发流量，但总流量受限于桶的大小和令牌生成速率。

import java.util.concurrent.Semaphore;

public class TokenBucket {
    private final Semaphore tokens;
    private final long refillInterval;
    private final int maxTokens;
    private long lastRefillTime;

    public TokenBucket(int maxTokens, long refillInterval) {
        this.maxTokens = maxTokens;
        this.refillInterval = refillInterval;
        this.tokens = new Semaphore(maxTokens, true);
        this.lastRefillTime = System.currentTimeMillis();
    }

    public synchronized boolean acquire() {
        refill();
        return tokens.tryAcquire();
    }

    private void refill() {
        long now = System.currentTimeMillis();
        long elapsed = now - lastRefillTime;
        if (elapsed >= refillInterval) {
            int newTokens = (int) (elapsed / refillInterval);
            if (newTokens > 0) {
                int availableTokens = Math.min(newTokens, maxTokens - tokens.availablePermits());
                tokens.release(availableTokens);
                lastRefillTime = now;
            }
        }
    }
}

漏桶算法（Leaky Bucket Algorithm）

漏桶算法通过一个“桶”来控制请求流量。

请求以任意速度到达桶中，但桶中的请求以固定速率“漏出”。

当桶满时，多余的请求会被丢弃。

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class LeakyBucket {
    private final BlockingQueue<Object> bucket;
    private final long leakRate;

    public LeakyBucket(int capacity, long leakRate) {
        this.bucket = new LinkedBlockingQueue<>(capacity);
        this.leakRate = leakRate;
        startLeak();
    }

    public boolean add(Object item) {
        return bucket.offer(item);
    }

    private void startLeak() {
        new Thread(() -> {
            while (true) {
                try {
                    Thread.sleep(leakRate);
                    bucket.poll();
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    break;
                }
            }
        }).start();
    }
}

滑动窗口算法（Sliding Window Algorithm）

滑动窗口算法维护一个时间窗口，在该窗口内控制请求数量。

当请求超出窗口内的最大允许数时，新的请求会被拒绝。

import java.util.LinkedList;
import java.util.Queue;

public class SlidingWindow {
    private final int maxRequests;
    private final long windowSize;
    private final Queue<Long> requests = new LinkedList<>();

    public SlidingWindow(int maxRequests, long windowSize) {
        this.maxRequests = maxRequests;
        this.windowSize = windowSize;
    }

    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();
        while (!requests.isEmpty() && now - requests.peek() > windowSize) {
            requests.poll();
        }
        if (requests.size() < maxRequests) {
            requests.add(now);
            return true;
        }
        return false;
    }
}

固定窗口计数器（Fixed Window Counter）

固定窗口计数器维护一个固定时间窗口内的请求计数。

每个窗口开始时计数器被重置，新的请求会增加计数器。

当计数器超出最大允许请求数时，新的请求会被拒绝。

import java.util.concurrent.atomic.AtomicInteger;

public class FixedWindowCounter {
    private final int maxRequests;
    private final long windowSize;
    private long windowStart;
    private final AtomicInteger requestCount = new AtomicInteger();

    public FixedWindowCounter(int maxRequests, long windowSize) {
        this.maxRequests = maxRequests;
        this.windowSize = windowSize;
        this.windowStart = System.currentTimeMillis();
    }

    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();
        if (now - windowStart > windowSize) {
            windowStart = now;
            requestCount.set(0);
        }
        if (requestCount.incrementAndGet() <= maxRequests) {
            return true;
        }
        return false;
    }
}