2024面试复盘2

编程随想面经

字数统计: 4k阅读时长: 15 min

 2024/06/24   Share

复盘

快排原理，时间空间复杂度

原理

选择基准元素
分区操作（Partition）。通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小。这个过程称为分区操作。
递归排序。递归地（recursive）把小于基准值元素的子数组和大于基准值元素的子数组排序。
合并。通常，这个步骤并不需要实际的合并操作，因为在分解和递归排序阶段已经完成了排序。

时间复杂度O(nlogn)。空间复杂度O(logn)。
代码实现：

public static void quickSort(int[] arr, int left, int right) {
	if (left < right) {
		log.info("开始排从【arr[{}]】到【arr[{}]】数据", left, right);
		int pivot = partition(arr, left, right);
		log.info("返回的基准位置是：{},分区排序后的结果：{}", pivot, arr);
		// 基准元素一定比左边的数大，所以左边分区最大值是：pivot - 1，分区范围是[left, pivot - 1]
		quickSort(arr, left, pivot - 1);
		// 基准元素一定比右边的数小，所以右边分区最小值是：pivot + 1，分区范围是[pivot + 1, right]
		quickSort(arr, pivot + 1, right);
	}
}

public static int partition(int[] arr, int left, int right) {
	// 定义基准元素
	int pivotValue = arr[left];
	// 遍历（条件就是分区左边索引小于右边索引）
	while (left < right) {
		// 从右边right开始遍历，找到一个数比基准数小
		while (left < right && arr[right] >= pivotValue) {
			// 未找到，继续往前找
			right--;
		}
		// 找到了，则把找到小值放到此时左边索引的位置
		// 第一次进入时,基准元素已存放到临时值pivotValue了，第一次就相当于放到基准位置了，同时，arr[right]也腾出了一个位置
		arr[left] = arr[right];
		// 从左边left开始遍历，找到一个数比基准数大
		while (left < right && arr[left] <= pivotValue) {
			// 未找到，继续往后找
			left++;
		}
		// 找到了，则把找到大值放到此时右边索引的位置（也就是腾出的位置）
		// 同时，arr[left]也腾出了一个位置
		arr[right] = arr[left];
	}
	// left等于right说明遍历结束了，把基准元素插入到腾出的位置，也就是arr[left]或者arr[right]
	arr[left] = pivotValue;
	// 返回基准元素插入的位置
	return left;
}

mysql innodb索引的结构？

InnoDB使用B+树作为其索引结构的基础。

聚簇索引
InnoDB的主键索引被称为聚簇索引。聚簇索引的特点是表中的数据行按照主键的顺序进行物理存储。这意味着主键查询非常快，因为数据库可以直接定位到数据行。聚簇索引的另一个优点是它可以有效地支持范围查询，因为数据行在磁盘上是连续存储的。
二级索引
除了聚簇索引外，InnoDB还支持二级索引（也称为非聚簇索引）。二级索引的叶子节点包含相应的主键值，而不是实际的数据行。当通过二级索引查询数据时，InnoDB首先定位到二级索引的叶子节点，获取对应的主键值，然后再通过聚簇索引定位到实际的数据行。因此，相对于聚簇索引，二级索引的查询性能会有所降低。

b+和b树的区别？

B树（B树、BTree、B-Tree都是同一个概念，都称为BTree），B树是一种多路自平衡搜索树，它类似普通的二叉树，但是B树允许每个节点有更多的子节点（二叉树一个节点下最多两个节点，而B树下一个节点可以有超过两个的节点），特点是：

所有节点中即包含记录的索引key值和这条记录的所有数据，以及指向下一个节点的指针；
任何一条记录出现且只出现在一个节点中；
搜索可能在非叶子节点时就结束了（因为节点中包含这条记录的所有数据，查到某条记录可以直接返回）；

B+树是对B树的升级，非叶子节点只存储索引列和下一个节点的指针（不再存储数据了），叶子节点存储索引列和数据以及下一个节点的指针（叶子节点是相连的），以现实中的树木比喻说明就是，BTree更加繁茂，而B+树相对精简
B+树相对于B树：

B+树非叶子节点只存储索引键和指针，相对B树来讲可以存储更多的索引键，这样的话B+树的深度也会更低，一次性读入内存的索引键也会更多，IO的次数也会变少，查询效率更高
B+树的所有数据都存储在叶子节点上，如果要取数据的话，那么每次查询IO的次数都是相同的，也就是说查询是稳定的
B+树叶子节点之间通过双向链表连接，可以很方便的进行范围查询总结就是B+树比B树查询效率更高更稳定，而且方便范围查询。

B+树相对于平衡二叉树或红黑树：

平衡二叉树追求绝对平衡，条件比较苛刻，而红黑树是对平衡二叉树的弱实现，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单，然而不管是平衡二叉树还是红黑树它们的任一节点最多有两个子节点，假设使用平衡二叉树或红黑树作为索引结构，那么一个节点只能存储一个索引键和指针，在数据量非常大的情况下，平衡二叉树或红黑树的深度会变的更深，这就意味着查询需要更多的IO，这显然不能被接受。

可重复读会什么情况？实现原理

会有幻读的情况。
针对快照读（普通 select 语句），是通过 MVCC 方式解决了幻读，因为可重复读隔离级别下，事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，即使中途有其他事务插入了一条数据，是查询不出来这条数据的，所以就很好了避免幻读问题。
针对当前读（select … for update 等语句），是通过 next-key lock（记录锁+间隙锁）方式解决了幻读，因为当执行 select … for update 语句的时候，会加上 next-key lock，如果有其他事务在 next-key lock 锁范围内插入了一条记录，那么这个插入语句就会被阻塞，无法成功插入，所以就很好了避免幻读问题。
这两个解决方案是很大程度上解决了幻读现象，但是还是有个别的情况造成的幻读现象是无法解决的。

对于快照读， MVCC 并不能完全避免幻读现象。因为当事务 A 更新了一条事务 B 插入的记录，那么事务 A 前后两次查询的记录条目就不一样了，所以就发生幻读。
对于当前读，如果事务开启后，并没有执行当前读，而是先快照读，然后这期间如果其他事务插入了一条记录，那么事务后续使用当前读进行查询的时候，就会发现两次查询的记录条目就不一样了，所以就发生幻读。

并发包锁的实现原理，AQS原理，数据结构？

Java中的大部分同步类（Lock、Semaphore、ReentrantLock等）都是基于AbstractQueuedSynchronizer（简称为AQS）实现的。

AQS核心思想是，如果被请求的共享资源空闲，那么就将当前请求资源的线程设置为有效的工作线程，将共享资源设置为锁定状态；如果共享资源被占用，就需要一定的阻塞等待唤醒机制来保证锁分配。这个机制主要用的是CLH队列的变体实现的，将暂时获取不到锁的线程加入到队列中。

AQS使用一个Volatile的int类型的成员变量来表示同步状态，通过内置的FIFO队列来完成资源获取的排队工作，通过CAS完成对State值的修改。
这里引用下美团的图片：

具体可以参考文章.

synchronized关键字实现方式？

Monitorenter和Monitorexit指令，会让对象在执行时，使其锁计数器加1或者减1。每一个对象在同一时间只与一个monitor(锁)相关联，而一个monitor在同一时间只能被一个线程获得，一个对象在尝试获得与这个对象相关联的Monitor锁的所有权的时候，monitorenter指令会发生如下3中情况之一：

monitor计数器为0，意味着目前还没有被获得，那这个线程就会立刻获得然后把锁计数器+1，一旦+1，别的线程再想获取，就需要等待
如果这个monitor已经拿到了这个锁的所有权，又重入了这把锁，那锁计数器就会累加，变成2，并且随着重入的次数，会一直累加
这把锁已经被别的线程获取了，等待锁释放

JVM中monitorenter和monitorexit字节码依赖于底层的操作系统的Mutex Lock来实现的，但是由于使用Mutex Lock需要将当前线程挂起并从用户态切换到内核态来执行，这种切换的代价是非常昂贵的。不过在jdk1.6中对锁的实现引入了大量的优化，如锁粗化(Lock Coarsening)、锁消除(Lock Elimination)、轻量级锁(Lightweight Locking)、偏向锁(Biased Locking)、适应性自旋(Adaptive Spinning)等技术来减少锁操作的开销。

锁粗化(Lock Coarsening)：也就是减少不必要的紧连在一起的unlock，lock操作，将多个连续的锁扩展成一个范围更大的锁。

锁消除(Lock Elimination)：通过运行时JIT编译器的逃逸分析来消除一些没有在当前同步块以外被其他线程共享的数据的锁保护，通过逃逸分析也可以在线程本的Stack上进行对象空间的分配(同时还可以减少Heap上的垃圾收集开销)。

轻量级锁(Lightweight Locking)：这种锁实现的背后基于这样一种假设，即在真实的情况下我们程序中的大部分同步代码一般都处于无锁竞争状态(即单线程执行环境)，在无锁竞争的情况下完全可以避免调用操作系统层面的重量级互斥锁，取而代之的是在monitorenter和monitorexit中只需要依靠一条CAS原子指令就可以完成锁的获取及释放。当存在锁竞争的情况下，执行CAS指令失败的线程将调用操作系统互斥锁进入到阻塞状态，当锁被释放的时候被唤醒(具体处理步骤下面详细讨论)。

偏向锁(Biased Locking)：是为了在无锁竞争的情况下避免在锁获取过程中执行不必要的CAS原子指令，因为CAS原子指令虽然相对于重量级锁来说开销比较小但还是存在非常可观的本地延迟。

适应性自旋(Adaptive Spinning)：当线程在获取轻量级锁的过程中执行CAS操作失败时，在进入与monitor相关联的操作系统重量级锁(mutex semaphore)前会进入忙等待(Spinning)然后再次尝试，当尝试一定的次数后如果仍然没有成功则调用与该monitor关联的semaphore(即互斥锁)进入到阻塞状态。

锁膨胀方向：无锁 → 偏向锁 → 轻量级锁 → 重量级锁 (此过程是不可逆的)

锁	优点	缺点	使用场景
偏向锁	加锁和解锁不需要CAS操作，没有额外的性能消耗，和执行非同步方法相比仅存在纳秒级的差距	如果线程间存在锁竞争，会带来额外的锁撤销的消耗	适用于只有一个线程访问同步块的场景
轻量级锁	竞争的线程不会阻塞，提高了响应速度	如线程始终得不到锁竞争的线程，使用自旋会消耗CPU性能	追求响应时间，同步块执行速度非常快
重量级锁	线程竞争不适用自旋，不会消耗CPU	线程阻塞，响应时间缓慢，在多线程下，频繁的获取释放锁，会带来巨大的性能消耗	追求吞吐量，同步块执行速度较长

分布式锁的实现原理？setnx的缺点？watchdog的实现机制？

redis分布式锁主要依靠setnx实现。

redis在 2.6.12 版本开始，为 SET 命令增加一系列选项.

1	SET key value[EX seconds][PX milliseconds][NX\|XX]

EX seconds: 设定过期时间，单位为秒
PX milliseconds: 设定过期时间，单位为毫秒
NX: 仅当key不存在时设置值
XX: 仅当key存在时设置值

缺点

超时时间不好设置。如果锁的超时时间设置过长，会影响性能，如果设置的超时时间过短会保护不到共享资源。
redis 主从复制模式中的数据是异步复制的，这样导致分布式锁的不可靠性

watchdog源码解析

private <T> RFuture<Long> tryAcquireAsync(long waitTime, long leaseTime, TimeUnit unit, long threadId) {
    if (leaseTime != -1) {
        return tryLockInnerAsync(waitTime, leaseTime, unit, threadId, RedisCommands.EVAL_LONG);
    }
    //当leaseTime = -1 时 启动 watch dog机制
    RFuture<Long> ttlRemainingFuture = tryLockInnerAsync(waitTime,
                                            commandExecutor.getConnectionManager().getCfg().getLockWatchdogTimeout(),
                                            TimeUnit.MILLISECONDS, threadId, RedisCommands.EVAL_LONG);
    //执行完lua脚本后的回调
    ttlRemainingFuture.onComplete((ttlRemaining, e) -> {
        if (e != null) {
            return;
        }

        if (ttlRemaining == null) {
            // watch dog 
            scheduleExpirationRenewal(threadId);
        }
    });
    return ttlRemainingFuture;
}

private void scheduleExpirationRenewal(long threadId) {
    ExpirationEntry entry = new ExpirationEntry();
    //将线程放入缓存中
    ExpirationEntry oldEntry = EXPIRATION_RENEWAL_MAP.putIfAbsent(getEntryName(), entry);
    //第二次获得锁后 不会进行延期操作
    if (oldEntry != null) {
        oldEntry.addThreadId(threadId);
    } else {
        entry.addThreadId(threadId);
        
        // 第一次获得锁 延期操作
        renewExpiration();
    }
}

// 进入 renewExpiration()
private void renewExpiration() {
    ExpirationEntry ee = EXPIRATION_RENEWAL_MAP.get(getEntryName());
    //如果缓存不存在，那不再锁续期
    if (ee == null) {
        return;
    }
    
    Timeout task = commandExecutor.getConnectionManager().newTimeout(new TimerTask() {
        @Override
        public void run(Timeout timeout) throws Exception {
            ExpirationEntry ent = EXPIRATION_RENEWAL_MAP.get(getEntryName());
            if (ent == null) {
                return;
            }
            Long threadId = ent.getFirstThreadId();
            if (threadId == null) {
                return;
            }
            
            //执行lua 进行续期
            RFuture<Boolean> future = renewExpirationAsync(threadId);
            future.onComplete((res, e) -> {
                if (e != null) {
                    log.error("Can't update lock " + getName() + " expiration", e);
                    return;
                }
                
                if (res) {
                    //延期成功，继续循环操作
                    renewExpiration();
                }
            });
        }
        //每隔internalLockLeaseTime/3=10秒检查一次
    }, internalLockLeaseTime / 3, TimeUnit.MILLISECONDS);
    
    ee.setTimeout(task);
}

//lua脚本 执行包装好的lua脚本进行key续期
protected RFuture<Boolean> renewExpirationAsync(long threadId) {
    return evalWriteAsync(getName(), LongCodec.INSTANCE, RedisCommands.EVAL_BOOLEAN,
            "if (redis.call('hexists', KEYS[1], ARGV[2]) == 1) then " +
                    "redis.call('pexpire', KEYS[1], ARGV[1]); " +
                    "return 1; " +
                    "end; " +
                    "return 0;",
            Collections.singletonList(getName()),
            internalLockLeaseTime, getLockName(threadId));
}