2024面试复盘3

编程随想面经

字数统计: 6.3k阅读时长: 23 min

 2024/07/15   Share

前言

拼多多和b站两场面试，大概率凉凉。

“你这业务都是偏向工具类啊”。这句话一说出我也只能呵呵一笑了，确实是这样，面试越多越发现内部业务是真的垃圾啊。

真的该考虑转行了。

但是该复盘还是得复盘。

复盘

pdd

算法题

实现一颗树的序列化与反序列化，要求序列化后的字符串长度最小。树的定义如下

public class Node {
	int value;
	List<Node> children;
    
    public Node(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }
}

public class Main {
    public static void main(String[] args) {
		Node root = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        root.children.add(node2);
        root.children.add(node3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node2.children.add(node4);
        node2.children.add(node5);
        node2.children.add(node6);
        node3.children.add(node7);
    }
}

这道题目我只写出了序列化，虽然是错的，就拿代码的示例，我那时想的是1-[2-[4,5,6], 3-[7]]，给gpt解答之后发现完全可以省略-变成1[2[4,5,6],3[7]]，但其实逻辑大差不大。先写序列化的。

public static String format(Node root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        if (root.children != null && root.children.size() > 0) {
            for (int i = 0; i < root.children.size(); i++) {
                Node child = root.children.get(i);
                String childStr = format(child);
                if (!"".equals(childStr)) {
                    sb.append(childStr);
                }
                if (i != root.children.size() - 1) {
                    sb.append(",");
                }
            }
        }
        if (sb.isEmpty()) {
            return String.valueOf(root.value);
        }else {
            return root.value + "[" + sb + "]";
        }

    }

反序列化是gpt写的，我学习一下

public static Node deserialize(String data) {
        if (data == null || data.isEmpty()) return null;
        return deserializeHelper(data, new int[]{0});
    }

private static Node deserializeHelper(String data, int[] index) {
    if (index[0] >= data.length()) return null;

    // 读取节点值
    int value = 0;
    while (index[0] < data.length() && Character.isDigit(data.charAt(index[0]))) {
        value = value * 10 + (data.charAt(index[0]) - '0');
        index[0]++;
    }

    Node node = new Node(value);

    // 检查是否有子节点
    if (index[0] < data.length() && data.charAt(index[0]) == '[') {
        index[0]++;  // 跳过 '['
        while (index[0] < data.length() && data.charAt(index[0]) != ']') {
            node.children.add(deserializeHelper(data, index));
            if (index[0] < data.length() && data.charAt(index[0]) == ',') {
                index[0]++;
            }
        }
        index[0]++;  // 跳过 ']'
    }

    return node;
}

有一说一，现在AI比人强太多了。

redis的使用场景？缓存不一致怎么解决？缓存的时间是？分布式锁的场景？

内部redis的使用场景一般是缓存和分布式锁。当然业界也有很多其他用法，比如和spring session对接，存储登录信息。还有排行榜功能（zset），pv统计等等。

缓存不一致业界一般采用的是Cache Aside Pattern, 即旁路缓存方案。这种方案包括读与写两种实践，对于读请求，先读缓存再读DB，如果cache命中，返回数据，未命中则访问DB,并将数据写回缓存。对于写请求，先操作数据库修改，再删除缓存。

为什么要删除缓存？原因是因为如果是写缓存的话，与正常的缓存miss流程相冲突，无法保证时序性。

为什么先操作数据库后删除缓存？其实不管是谁先谁后，都有可能会出现并发问题，但是写数据库的操作会比读数据库的速度慢，因此当A线程读了老数据并写入cache，B线程更改了数据库数据，并删除缓存，假设先删除缓存，那么有可能是删了个寂寞，老数据依旧被A写入缓存。当然这就是一个概率问题。

数据库和缓存是很难做到强一致性的，只能退而求其次追求最终一致性。那么就可以使用双写方案，即常说的延时双删，但是具体延迟多久这个得根据业务确定，取决于读业务所需的时间。

至于缓存的超时时间，一般是由业务决定，像我一般往redis存储的数据经常是一些配置数据，这些配置数据一般不怎么会改变，我一般是存12或24小时。

分布式锁的场景一般用于资源的抢占，实现业务的幂等。

消息队列场景？除了解耦还有其他作用吗？其他优点？

消息队列一般用于异步处理，应用解耦，流量削峰，日志处理，消息通讯，延时任务，广播等。优点就是解耦、异步、削峰，缺点就是可用性降低，中间件越多，系统越可能出现单点故障；增加系统的复杂性，既然引入了消息队列，那么重复消费需要避免吧？消息丢失需要处理吧？顺序性需要保证吗？这都是一个个问题。

mysql和mongodb的场景？数据量有多少？

MongoDB适合用于大数据量、高并发的场景，特别是在需要灵活的数据模型和快速的读写操作时非常适用。

MySQL适合用于传统的关系型数据库场景，特别是在需要强一致性和复杂的事务处理时非常适用。支持SQL。

MongoDB的优点包括：灵活的数据模型、高性能的读写操作、可扩展性强、适合大数据量场景；缺点包括：不支持事务处理、对内存和磁盘的要求较高。
MySQL的优点包括：强一致性、支持复杂的事务处理、成熟的生态系统、广泛的应用领域；缺点包括：不适合非结构化数据、可扩展性较弱、性能在大数据量场景下有限，需要考虑分库分表，当然mongoDB也需要考虑分片。

数据量十亿以下吧。

es的使用场景？

内部es都用做日志存储与检索，包括应用日志，其他需要上报的文本数据。

业内es一般用来做搜索，例如电商产品搜索，视频搜索等等，也用作日志分析，如用户行为分析，运营审计日志等。

后面es集群搭建的时候，再复习下。

项目：编排流程是做什么的？流程的依赖是怎么处理的？

这个就不聊了，项目挺垃圾。

有大流量大批量执行有吗？

项目相关。没有。确实都没经历过。内部系统哪来的大流量大批量。

有了解过分库分表吗？既然你们用tidb 那节点扩容了解过吗？

之后架构之路会搭建TiDB集群，敬请期待。

这里讲讲分库分表。

分库一般是按照应用或者租户来分库，用于解决单体库并发量高的问题。而分表一般来说数据量到达一定量级需要考虑。

分库分表分为水平拆分和垂直拆分。水平拆分是将单表拆成多个数据表，例如order表拆为order1，order2等，根据不同的用户id分到不同的表中。垂直拆分则是拆字段，将不同的字段按照业务或性能拆分成不同的表。

分表算法一般有直接取模，hash取模，一致性hash等方案，前两种方法存在一个问题就是当后期需要扩容的时候，那么由于基数改变，必然涉及到数据的重新迁移。所以一般来说是使用一致性Hash方式。一致性哈希可以按照常用的hash算法来将对应的key哈希到一个具有2^32次方个节点的空间中，形成成一个顺时针首尾相接的闭合的环形。所以当添加一个新的数据库节点时，只有增加服务器的位置和逆时针方向第一个数据库节点之间的键会受影响。虽然数据会收到部分影响，但是会稍微好点。当然前期就应该规划好数据量级，提前做好分库分表。

全局id的生成一般有UUID，雪花算法，当然也有tidb使用的预先分配id方案，例如节点1插入数据id范围为1-3000，节点2为3001-6000以此类推。

市面上主流的分库分表中间件有ShardingSphere，TDDL，Mycat。ShardingSphere用的人可能会多一些。ShardingSphere包括Sharding-JDBC和Sharding-Proxy，JDBC是项目里使用的，Proxy则代理数据库连接，JDBC使用较为简单，只需在项目里引用，并添加多个数据源即可实现分库分表。Proxy 版则可以屏蔽应用层面配置多个数据源，能更好的管理数据库。

有考虑过容灾吗？

”同城双活”，“两地三中心”？想到的是这个，但是内部顶多是跨集群跨网络部署应用。这里说说我的思考。

其实以内部的基础设施建设能力的话，已经足够做容灾方案了。各个园区都有服务器集群，其实只要把服务都部署一套就可以了，然后做网关的负载均衡，但是有个点就是如果是网关故障的话，以目前内部的能力是无法做的无感切换的。一是不支持智能DNS，所以网关即便部署多套，依旧会出现瞬时不可用的场景。

所以我理解的容灾方案，不仅是服务跨集群部署，网关也要部署多套，然后必须支持智能DNS。这样才能实现初步的容灾。

当然无外乎就是成本的问题。

b站

刚开始讲项目就不说了。还被问了有没有做过业务系统。

你觉得最有挑战的项目是什么，承担的角色是什么？有没有遇到什么有意思的问题。

面试官还提醒我要把空白时间补齐，后面把项目加进去。

mysql事务四大特性，底层是如何保证这四大特性？

没答上来。。复习下。

Atomic，原子性，事务的所有SQL操作作为原子工作单元执行，要么全部执行，要么全部不执行；
Consistent，一致性，事务完成后，所有数据的状态都是一致的，即A账户只要减去了100，B账户则必定加上了100；
Isolation，隔离性，如果有多个事务并发执行，每个事务作出的修改必须与其他事务隔离；
Duration，持久性，即事务完成后，对数据库数据的修改被持久化存储。

mysql数据库事务的原子性是通过undo log实现的。

事务的所有修改操作(增、删、改)的相反操作都会写入undo log,比如事务执行了一条insert语句，那么undo log就会记录一条相应的delete语句。所以undo log是一个逻辑文件，记录的是相应的SQL语句一旦由于故障，导致事务无法成功提交，系统则会执行undo log中相应的撤销操作，达到事务回滚的目的。

mysql数据库事务的持久性是通过redo log实现的

事务的所有修改操作(增、删、改)，数据库都会生成一条redo日志记录到redo log.区别于undo log记录SQL语句、redo log记录的是事务对数据库的哪个数据页做了什么修改，属于物理日志。

隔离性是通过（读写锁+MVCC）来实现的。即常见的事务隔离级别（读未提交，不可重复读，可重复读，串行化）。不同隔离级别下，隔离性采用锁+MVCC的方式实现。

表锁：读锁（不会阻塞其他线程的读操作，阻塞写操作）；写锁（读写操作都阻塞）

行锁：需要的时候加上，并不是马上释放，等事务提交才释放，两阶段锁协议

间隙锁-gap lock：锁定区间范围，防止幻读，左开右开，只在可重复读隔离级别下生效—|—为了阻止多个事务将记录插入到同一范围内，而这会导致幻读问题的产生

记录锁-record Lock：锁定行记录，索的索引，索引失效，为表锁

临键锁-next-key Lock：record lock+gap lock 左开右闭（解决幻读）

MVCC：实现多版本并发控制，实现原理：使用版本链+Read View

读已提交和可重复读实现原理就是MVCC Read View不同的生成时机。可重复读只在事务开始时生成一个Read View，之后都用的这个；读已提交每次执行前都会生成Read View。

最后通过原子性、持久性、隔离性最终实现数据一致性。

mysql的锁？为什么读多写少使用乐观锁？死锁什么时候会出现？

mysql锁按照模式可以分类为：乐观锁与悲观锁。按粒度分可以分为全局锁、表级锁、页级锁、行级锁。按属性可以分为：共享锁、排它锁。按状态分为：意向共享锁、意向排它锁。按算法分为：间隙锁、临键锁、记录锁。

全局锁、表级锁、页级锁、行级锁

全局锁就是对整个数据库实例加锁。常用在全库逻辑备份（mysqldump）。
当前操作的整张表加锁，最常使用的 MyISAM 与 InnoDB 都支持表级锁定。MySQL 里面表级别的锁有两种：一种是表锁，一种是元数据锁（meta data lock，MDL)。

表锁实现：lock tables … read/write。

MDL作用是防止DDL和DML并发的冲突 ，保证读写的正确性MDL 不需要显式使用，在访问一个表的时候会被自动加上。MDL 的作用是，保证读写的正确性。当对一个表做增删改查操作的时候，加 MDL读锁；当要对表做结构变更操作的时候，加 MDL 写锁.

MDL比较复杂，后面我把网上找的资料补上。
页级锁是 MySQL 中锁定粒度介于行级锁和表级锁中间的一种锁。表级锁速度快，但冲突多，行级冲突少，但速度慢。因此，采取了折衷的页级锁，一次锁定相邻的一组记录。BDB 引擎支持页级锁。
行级锁是粒度最低的锁，发生锁冲突的概率也最低、并发度最高。但是加锁慢、开销大，容易发生死锁现象。

MySQL中只有InnoDB支持行级锁，行级锁分为共享锁和排他锁。在MySQL中，行级锁并不是直接锁记录，而是锁索引。索引分为主键索引和非主键索引两种，如果一条sql语句操作了主键索引，MySQL就会锁定这条主键索引；如果一条语句操作了非主键索引，MySQL会先锁定该非主键索引，再锁定相关的主键索引。在UPDATE、DELETE操作时，MySQL不仅锁定WHERE条件扫描过的所有索引记录，而且会锁定相邻的键值，即所谓的next-key locking。

乐观锁与悲观锁

乐观锁是相对悲观锁而言的，乐观锁假设数据一般情况下不会造成冲突。适用于读多写少，因为如果出现大量的写操作，写冲突的可能性就会增大，业务层需要不断重试，会大大降低系统性能。一般使用数据版本（Version）或时间戳记录机制实现，在数据库表中增加一个数字类型的“version”字段来实现。当读取数据时，将version字段的值一同读出，数据每更新一次，对此version值加一。

悲观锁，每次去拿数据的时候都认为别人会修改，对数据被外界修改持保守态度。适用于并发量不大、写入操作比较频繁、数据一致性比较高的场景。在MySQL中使用悲观锁，必须关闭MySQL的自动提交，set autocommit=0。共享锁和排它锁是悲观锁的不同的实现，它俩都属于悲观锁的范畴。

共享锁和排他锁

死锁的出现

比如表级锁死锁，这个好理解。

行级锁死锁可能的原因是因为锁的膨胀，比如事务中执行了一条没有索引条件的查询，进行了全表扫描，膨胀为表级锁。

mysql的innoDb采用了一种叫作等待图(wait-for graph)的方法来自动检测死锁，如果发现死锁，就会自动回滚一个事务。

redis使用场景？redisson的原理？线程递归使用锁？

使用场景同pdd。

redission原理

通过lua脚本来实现加锁的操作

判断lock键是否存在，不存在直接调用hset存储当前线程信息并且设置过期时间,返回nil，告诉客户端直接获取到锁。
判断lock键是否存在，存在则将重入次数加1，并重新设置过期时间，返回nil，告诉客户端直接获取到锁。
被其它线程已经锁定，返回锁有效期的剩余时间，告诉客户端需要等待。

加锁的代码如下

<T> RFuture<T> tryLockInnerAsync(long waitTime, long leaseTime, TimeUnit unit, long threadId, RedisStrictCommand<T> command) {
    return evalWriteAsync(getRawName(), LongCodec.INSTANCE, command,
                          "if (redis.call('exists', KEYS[1]) == 0) then " +
                          "redis.call('hincrby', KEYS[1], ARGV[2], 1); " +
                          "redis.call('pexpire', KEYS[1], ARGV[1]); " +
                          "return nil; " +
                          "end; " +
                          "if (redis.call('hexists', KEYS[1], ARGV[2]) == 1) then " +
                          "redis.call('hincrby', KEYS[1], ARGV[2], 1); " +
                          "redis.call('pexpire', KEYS[1], ARGV[1]); " +
                          "return nil; " +
                          "end; " +
                          "return redis.call('pttl', KEYS[1]);",
                          Collections.singletonList(getRawName()), unit.toMillis(leaseTime), getLockName(threadId));
}

释放锁的流程:

如果lock键不存在，通过publish指令发送一个消息表示锁已经可用。
如果锁不是被当前线程锁定，则返回nil
由于支持可重入，在解锁时将重入次数需要减1
如果计算后的重入次数>0，则重新设置过期时间
如果计算后的重入次数<=0，则发消息说锁已经可用

protected RFuture<Boolean> unlockInnerAsync(long threadId) {
    return evalWriteAsync(getRawName(), LongCodec.INSTANCE, RedisCommands.EVAL_BOOLEAN,
                          "if (redis.call('hexists', KEYS[1], ARGV[3]) == 0) then " +
                          "return nil;" +
                          "end; " +
                          "local counter = redis.call('hincrby', KEYS[1], ARGV[3], -1); " +
                          "if (counter > 0) then " +
                          "redis.call('pexpire', KEYS[1], ARGV[2]); " +
                          "return 0; " +
                          "else " +
                          "redis.call('del', KEYS[1]); " +
                          "redis.call('publish', KEYS[2], ARGV[1]); " +
                          "return 1; " +
                          "end; " +
                          "return nil;",
                          Arrays.asList(getRawName(), getChannelName()), LockPubSub.UNLOCK_MESSAGE, internalLockLeaseTime, getLockName(threadId));

watchlog实现机制可以参考之前的复盘。

redis集群模式了解过吗？怎么保证高可用？

下一期架构之路会搭建redis集群模式，这个我早上醒来就在想啥时候搭建一个，没想到下午面试就遇到了。

redis共有三种集群模式，主从复制模式（Master-Slave）、哨兵模式（Sentinel）和Cluster模式。

主从复制是Redis的一种基本集群模式，它通过将一个Redis节点（主节点）的数据复制到一个或多个其他Redis节点（从节点）来实现数据的冗余和备份。

主节点负责处理客户端的写操作，同时从节点会实时同步主节点的数据。客户端可以从从节点读取数据，实现读写分离，提高系统性能。

主从复制模式适合数据备份、读写分离和在线升级等场景，但在主节点故障时需要手动切换，不能自动实现故障转移。如果对高可用性要求较高，可以考虑使用哨兵模式或Cluster模式。

哨兵模式（Sentinel）是在主从复制基础上加入了哨兵节点，实现了自动故障转移。哨兵节点是一种特殊的Redis节点，它会监控主节点和从节点的运行状态。当主节点发生故障时，哨兵节点会自动从从节点中选举出一个新的主节点，并通知其他从节点和客户端，实现故障转移。

哨兵模式在主从复制模式的基础上实现了自动故障转移，提高了系统的高可用性。然而，它仍然无法实现数据分片。如果需要实现数据分片和负载均衡，可以考虑使用Cluster模式。

Cluster集群通过分片（sharding）模式来对数据进行管理，并具备分片间数据复制、故障转移和流量调度的能力。

Redis集群的做法是将数据划分为 16384（2的14次方）个哈希槽（slots），如果你有多个实例节点，那么每个实例节点将管理其中一部分的槽位，槽位的信息会存储在各自所归属的节点中。

Cluster模式适用于以下场景：

大规模数据存储：通过数据分片，突破单节点内存限制。
高性能要求场景：通过负载均衡，提高系统性能。
高可用性要求场景：通过自动故障转移，确保服务的持续可用。

Cluster模式在提供高可用性的同时，实现了数据分片和负载均衡，适用于大规模数据存储和高性能要求的场景。然而，它的配置和管理相对复杂，且某些复杂的多键操作可能受到限制。

spring事务的传播机制有哪几种，什么情况下事务会失效？

Propagation.REQUIRED：默认的事务传播级别，它表示如果当前存在事务，则加入该事务；如果当前没有事务，则创建一个新的事务。
Propagation.SUPPORTS：如果当前存在事务，则加入该事务；如果当前没有事务，则以非事务的方式继续运行。
Propagation.MANDATORY：（mandatory：强制性）如果当前存在事务，则加入该事务；如果当前没有事务，则抛出异常。
Propagation.REQUIRES_NEW：表示创建一个新的事务，如果当前存在事务，则把当前事务挂起。也就是说不管外部方法是否开启事务，Propagation.REQUIRES_NEW 修饰的内部方法会新开启自己的事务，且开启的事务相互独立，互不干扰。
Propagation.NOT_SUPPORTED：以非事务方式运行，如果当前存在事务，则把当前事务挂起。
Propagation.NEVER：以非事务方式运行，如果当前存在事务，则抛出异常。
Propagation.NESTED：如果当前存在事务，则创建一个事务作为当前事务的嵌套事务来运行；如果当前没有事务，则该取值等价于 PROPAGATION_REQUIRED。

事务失效的场景

抛出检查异常，如果@Transactional 没有特别指定，Spring 只会在遇到运行时异常RuntimeException或者error时进行回滚。需要配置rollbackFor`属性。
业务方法本身捕获了异常。这个没啥好说的，当内部嵌套特别多的时候非常容易犯这种错误。
同一类中的方法调用。这个也容易犯错，加入A是@Transactional注解的方法，同类的B方法没有注解，但是内部调用了A方法，导致事务失效。很简单，原因就是方法没有被动态代理。
方法使用 final 或 static关键字。如果Spring使用了Cglib代理实现，而你的业务方法恰好使用了final或者static关键字，那么事务也会失败。更具体地说，它应该抛出异常，因为Cglib使用字节码增强技术生成被代理类的子类并重写被代理类的方法来实现代理。如果被代理的方法的方法使用final或static关键字，则子类不能重写被代理的方法。如果Spring使用JDK动态代理实现，JDK动态代理是基于接口实现的，那么final和static修饰的方法也就无法被代理。
方法不是public。Spring的事务管理源码AbstractFallbackTransactionAttributeSource中有判断computeTransactionAttribute()。如果目标方法不是公共的，则TransactionAttribute返回null。
错误使用传播机制。假设两个方法都使用REQUIRES_NEW，如果当前方法中没有事务，就会创建一个新的事务。如果一个事务已经存在，则当前事务将被挂起，并创建一个新事务。那么当A调用B完成后，B事务已经提交，A就算回滚了也影响不了B。
没有被Spring管理。这种情况一般来说不会发生。
多线程。我们说的同一个事务，其实是指同一个数据库连接，只有拥有同一个数据库连接才能同时提交和回滚。如果在不同的线程，拿到的数据库连接肯定是不一样的，所以是不同的事务。

总结

基础问题很多没答上来，得好好复习。面试官人挺好，感觉就是聊聊天。

原文作者：Zer0e

原文链接：https://re0.top/2024/07/15/2024-07-15-replay/

发表日期：July 15th 2024, 8:00:00 pm

更新日期：July 25th 2024, 1:27:27 pm

Next Post

2024面试复盘4
Previous Post

【架构之路4】k8s对接ceph-rbd

CATALOG

1. 前言
2. 复盘
1. 2.1. pdd
2. 2.2. b站

