快手主站后端面经

时间点如下：8.3投递 -> 8.10一面 -> 8.19二面

一点思考

    快手一二面对算法比较重视，也会问JAVA语言层面的知识点，这次重点问了AQS。二面重点问系统设计，当时二面的面试官在家隔离，感觉很随意。目前面试还在进行中，希望有个好的结果。

    今年找工作十分不易，市场候选人很多，能过就是钱给不到位！希望这篇面经能帮到大家～

快手主站一面（8.10）

1. 算法题："[]{}()"是否是合法的字符串。
2. AQS的同步队列，为啥要用双向链表。

   acquireQueued时，会判断自己的上一个节点是不是头指针，如果是则尝试获取资源，如果不是，会看看（在方法实现：shouldParkAfterFailedAcquire）上一个节点是否是signal状态，如果是则park；如果是cancelled则把所有的前继的cancel节点，直接移除掉；如果是0，则设置上一个节点为signal状态，然后继续循环，最后park。每个节点都会这么做。另外，链表里可能会有取消的节点（超时或者interrupt了，已经返回了，但是在cancel没有修改prev指针，懒惰操作？），需要往前遍历，取消掉。

• 等待（同步）队列使用Node节点里prev/next，双向链表，非循环链表。使用head/tail保存头尾指针，添加第一个节点时，会先设置head为一个假的节点，然后再调用acquireQueued，由于state没有被占用，所以调用tryAcquire()会返回成功。此时nextWaiter存储共享模式还是互斥模式。

• release时，会释放state，并唤醒当前head指针的第一个后继<=0节点。下一个后继节点判断前一个节点是head，如果资源释放了，则获取锁成功。成功后，会把head设置为自己，老的head移除出队，等待gc

• head <-> a <-> b <-> tail，head一般表示持有锁的线程，所以队列中排队的，不包含head。当head != tail，则至少有一个在排队。

• 条件队列是在ConditionOjbect（非静态类）中实现的，用的是Node节点里nextWaiter，就是单链表，但是会保存firstWaiter/lastWaiter。firstWaiter -> a -> b -> lastWaiter，包含first/last。状态为Node.CONDITION。

• 条件队列由业务自己创建一个Condition，字段保存在业务代码中，底层是ConditionObject实现。signal时，是先把当前node的condition改为0，转移到sync队列的队尾，把前置节点改为signal，如果前置节点取消了或者设置signal状态失败，直接唤醒。

• AQS为什么是线程安全的？基于volatile+while/for(死循环)+CAS实现

• 第一个节点是怎么唤醒的？一般在releae时调用lockSupport.unpark唤醒。

• 从后往前遍历，prev指针肯定是准确的，next指针不一定准确，next=null，不表示一定是tail

• 为什么要从后往前遍历？

  prev指针是准确的，可以遍历到所有。next指针不一定准，可能是null，但是实际可能并不为null，如果从头到尾遍历，是否会死循环？。当next == null时，还需要进一步判断。

    private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize
            // 第一个节点会设置dummpy节点，哑节点。
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

• waitStatus > 0表示取消，头节点的waitStatus一定是<=0，也就是不可能是取消。

• head节点的prev一定是null，所以head节点重新设置时，设置prev=null即可，方便从后往前遍历，当老的head出队，则把老的head的next指针设置为null即可。

第二个回答比较准确：https://www.zhihu.com/question/50724462

• AQS主要有三个字段，state/prev node/next node，以及父类的exclusiveOwnerThread，state的语义由子类自己定义

• CountDownLatch是一组线程等待另外一组线程，而CyclicBarrier是一组线程之间相互等待。

• AQS自己不包含公平与不公平的实现，由子类实现tryAcquire看看是否要排队（hasQueuedPredecessors方法，队列中是否有在排队的），还是直接占有资源。

• 有5个可以覆盖的方法，默认实现的unsupportedOperation，其他的方法均是final。tryAcquire/tryRelease/tryAcquireShare/tryReleaseShare/isHeldExclusively。前两个用于实现独占式，后两个用于实现共享式，前四个都是调用setState/compareAndSetState等基本方法，根据返回时是否为true表示是否占用资源成功，共享的还会看看是否唤醒后继，isHeldExclusively在需要用到condition时实现。按需覆盖即可，也可以同时使用来实现两种功能模式，例如ReentrantReadWriteLock。tryLock不保证公平。

3. threadlocal内存泄漏的本质原因是什么？

   主要原因是跟线程绑定，线程不会回收，但是业务使用不当，未调用remove

4. 如果做群聊，需要做什么样的改造

5. 如果要直播直播发消息，需要怎么做？

6. 对于大主播发消息，如何保证都收到。

7. java/go有什么区别？gpm怎么实现的。

8. consul/zk作为注册中心有什么区别？

zk并不是严格意义上的CP模型，CAP中，C指的是线性一致性，也就是A写了后，B操作会读取到A操作的数据或者更新的数据，要达到这种效果，在读取之前，必须使用sync() API。zk的C是串型（顺序）一致性，读取时可能读取到老的数据，不能客户端读取到的可能也不一样，但是比最终一致性强。写入是线性一致性，读取是顺序一致性，因为写入是到一个leader节点进行写，分配一个自增的zxid，读取是所有节点都可以读取。
如果也只从leader节点读取，则读取也是线性一致性，但是这里增加节点没法扩展读能力，仅仅做同步。https://stackoverflow.com/questions/35387774/is-zookeeper-always-consistent-in-terms-of-cap-theorem
事实上，服务发现更适合用AP模型，而不是zk的强一致性，因为服务发现即使数据不是最新的，也会有一定的容错机制。
用分布式系统的CAP原则来分析Zookeeper
（1）C（一致性）: Zookeeper保证了顺序一致性（满足最终一致性），在十几秒可以Sync到各个节点
（2）A（可用性）: Zookeeper保证了可用性，数据总是可用的（没有锁）。并且有一大半的节点所拥有的数据是最新的、实时的。 如果想保证取得是数据一定是最新的，需要手工调用Sync()
（3）P（分区容错性）: 有两点需要分析
节点多了会导致写数据延时变大，因为更多的节点需要同步
节点多了Leader选举耗时变长，从而会放大网络的问题， 可以通过引入 observer（不参与选举）节点缓解这个问题.
https://zhuanlan.zhihu.com/p/143012915

快手主站二面（8.19）

1. 做中台跟做普通业务有什么区别，要注意什么？

2. 如何及时发现线上问题？

3. 算法：n个有序链表，合成一个有序链表

4. go里的锁跟java里的锁有什么区别？

5. synchronized如何实现可重入？锁升级是怎么做的？

6. 设计题：有3亿的用户，访问1百万件作品，请求量会很大，想要做一个过去24h的访问量前200的作品榜单，如何实现？

7. 双机房容灾是怎么做的，中间件多机房容灾是怎么做的？

   任何时候，都只有一个主节点，全部写入到主机房的节点，如果发生了切换，可能会导致数据丢失、数据重复等问题。因为主从机房有一定的延迟。对于同步，可以是异步复制、半同步复制、同步复制等，但是对性能有影响。另外切换时，可能导致一些分布式的问题，例如分布式事务，如何回滚？