阿里一面复盘


Java定时器

Timer schedule

多个任务可以共用一个定时器。

demo

class Task extends TimerTask {

    @Override
    public void run() {
        System.out.println("do work...");
    }
}

class Solution {
    public static void main(String[] args) {
        Timer timer = new Timer();
        Task task = new Task();
        // task, firstTime, period
        timer.schedule(task,new Date(),1000);
    }
}

输出:

do work...
do work...
do work...
do work...
...

函数

Timer.schedule(TimerTask task,Date time) 安排在制定的时间执行指定的任务。
Timer.schedule(TimerTask task,Date firstTime ,long period) 安排指定的任务在指定的时间开始进行重复的固定延迟执行.
Timer.schedule(TimerTask task,long delay) 安排在指定延迟后执行指定的任务.
Timer.schedule(TimerTask task,long delay,long period) 安排指定的任务从指定的延迟后开始进行重复的固定延迟执行.
Timer.scheduleAtFixedRate(TimerTask task,Date firstTime,long period) 安排指定的任务在指定的时间开始进行重复的固定速率执行.
Timer.scheduleAtFixedRate(TimerTask task,long delay,long period) 安排指定的任务在指定的延迟后开始进行重复的固定速率执行.

源码解析

image-20220411223838245

Timer类有一个任务队列(一个最小堆)和一个线程对象。

其中一个最完整的构造函数:

image-20220411224041771

新开了一个线程,可以设置成守护线程。

java里面线程分两种:

守护线程:比如垃圾回收线程。

用户线程:应用里自定义的线程。

守护线程专门服务于其他线程,如果其他线程都执行完毕,连main都执行完毕,那么jvm就会退出停止运行。

在之前的demo里面,改为延迟执行一次。

timer.schedule(task,1000);

但是执行过一次后并没有退出,而是一直卡着。改为timer deamon试试:

Timer timer = new Timer(true);
Task task = new Task();
// delay
timer.schedule(task,1000);

结果什么都没打印,直接退出了,因为main执行完了,只剩守护进程,就结束了。

延迟两秒试试:

public static void main(String[] args) throws InterruptedException {
    Timer timer = new Timer(true);
    Task task = new Task();
    // delay
    timer.schedule(task,1000);
    Thread.sleep(2000);
}

打印do work...之后退出,符合意料。

TimerThread

private void mainLoop() {
    while (true) {
        try {
            TimerTask task;
            boolean taskFired;
            synchronized(queue) {
                // Wait for queue to become non-empty
                while (queue.isEmpty() && newTasksMayBeScheduled)
                    queue.wait();
                if (queue.isEmpty())
                    break; // Queue is empty and will forever remain; die

                // Queue nonempty; look at first evt and do the right thing
                long currentTime, executionTime;
                task = queue.getMin();
                synchronized(task.lock) {
                    if (task.state == TimerTask.CANCELLED) {
                        queue.removeMin();
                        continue;  // No action required, poll queue again
                    }
                    currentTime = System.currentTimeMillis();
                    executionTime = task.nextExecutionTime;
                    if (taskFired = (executionTime<=currentTime)) {
                        if (task.period == 0) { // Non-repeating, remove
                            queue.removeMin();
                            task.state = TimerTask.EXECUTED;
                        } else { // Repeating task, reschedule
                            queue.rescheduleMin(
                                task.period<0 ? currentTime   - task.period
                                : executionTime + task.period);
                        }
                    }
                }
                if (!taskFired) // Task hasn't yet fired; wait
                    queue.wait(executionTime - currentTime);
            }
            if (taskFired)  // Task fired; run it, holding no locks
                task.run();
        } catch(InterruptedException e) {
        }
    }
}

里面是一个循环,队列按照下一次执行时间进行堆排序,每次取堆中时间和当前系统时间进行比较,如果大于执行时间就执行。如果是单词任务,将任务移出最小堆。否则更新下次执行时间。

单线程+最小堆+不断轮询。

ScheduleThreadPoolExecutor

对应Timer中的TaskQueue,ScheduledThreadPoolExecutor用自定义延迟队列DelayedWorkQueue来替代。也是轮询,不过解决了Timer的单线程串行阻塞问题。多个定时任务互不影响。

时间轮

例如游戏里每个玩家身上有很多buf,每一个tick(最小时间段)都要去检查buf是不是过期,那么就会造成每一个tick都要去遍历list,明显不好。

原始模型

image-20220411231924643

优化1

image-20220411232027379

找到它起效果的tick,加入到这个tick对应的list。就不用遍历全部了。

如果时间超出了轮的大小,要记录要额外转的圈数。

问题:占用空间大。

优化2

image-20220411232634474

初始化一个三层的时间轮:秒、分、时。

就是时钟的思想。节省空间。

原理

它可能会安装一个2分4秒300ms处timeout事件。首先安装2min,当2分钟发生时,它检查还有4.3s的事件才能timeout,所以它又安装了4s的timeout事件槽,当4s过去后,检查到还有300ms才能timeout,又安装了一个300ms事件,再过300ms,真正的timeout才会被执行。

TreeMap

可以实现元素的自动排序。通过红黑树实现。默认按照key的自然顺序排序。

TreeMap<String,Integer> map = new TreeMap<>();
map.put("abc",3);
map.put("zzzz",5);
map.put("cdf",2);
System.out.println(map);

输出:

{abc=3, cdf=2, zzzz=5}

自定义key

class Node {
    String phone;
    int level;
    String name;
    public Node(String p,int l,String n) {
        phone = p;
        level = l;
        name = n;
    }
}

class Solution {
    public static void main(String[] args) {
        TreeMap<Node,Integer> map = new TreeMap<>();
        map.put(new Node("12345",2,"kang"),3);
        map.put(new Node("62345",1,"kong"),5);
        map.put(new Node("52345",3,"keng"),2);
        System.out.println(map);
        // 报错:Exception in thread "main" java.lang.ClassCastException: 
        // leetcode.Node cannot be cast to java.lang.Comparable
    }
}

直接运行会报错,没有比较。

需要自定义比较器:

TreeMap<Node,Integer> map = new TreeMap<>((o1,o2)->{
    if(o1.level!=o2.level) {
        return o1.level-o2.level;
    }
    return o1.name.compareTo(o2.name);
});
map.put(new Node("12345",2,"kang"),3);
map.put(new Node("62345",1,"kong"),5);
map.put(new Node("52345",1,"heng"),2);
map.put(new Node("52345",3,"keng"),2);

输出:

{Node{phone='52345', level=1, name='heng'}=2, 
 Node{phone='62345', level=1, name='kong'}=5, 
 Node{phone='12345', level=2, name='kang'}=3, 
 Node{phone='52345', level=3, name='keng'}=2}

红黑树定义

是一个满足红黑性质的二叉搜索树:

  • 结点黑或者红
  • 根结点黑色
  • 叶结点黑色(NULL)
  • 如果一个结点为红色,则子结点为黑色
  • 每个结点从该结点到它所有后代叶结点的简单路径上,含有相同数目的黑色结点。

通过对各个结点的颜色进行约束,确保没有一条路径会比其他路径长出2倍,近似于平衡。

线程进线程池

流程

image-20220411222052090

一个任务被提交到线程池之后。

  • 判断核心线程池是否已满,不满就执行任务
  • 如果核心线程池满了,判断队列是否已经满了,不满的话将任务放入到任务队列里面
  • 如果任务队列也满了,那就判断最大线程是不是也满了,没有就创建最大线程,执行任务
  • 如果最大线程也满了,没地方放了,就按照拒绝策略执行

为啥先添加队列而不是创建最大线程

线程池创建线程需要获取一个全局锁,影响并发效率。引入阻塞队列,是为了执行任务时,尽可能避免获取全局锁。

AQS条件队列及中断

条件队列

ReetrantLock + Condition

await()signal() 进行线程间的阻塞和唤醒。

一个AQS有多个条件队列,一个同步队列。

image-20220411233903340

调用了await()方法的线程,会被加入到ConditionObject的等待队列中,并且唤醒同步队列的head结点的下一个结点。

线程在ConditionObject调用signal()之后,firstWaiter会被加入同步队列,等待被唤醒。

线程unlock之后,同步队列的head结点的下一个结点会被唤醒。

线程中断

java线程中断依靠中断标志实现,调用interrupt方法之后,设置中断标志。

轮到这个线程执行了,就会判断这个线程是否被中断,如果这个线程拿到锁,就会会执行selfInterrupt()方法,将当前线程中断。

zookeeper CAP

CAP:

C:数据一致性。分布式系统中所有数据备份,在同一时刻具有相同的值

A:服务可用性。一部分节点故障之后,集群能否响应客户端读写请求。

P:分区容错性。Partition tolerance。分布式系统在遇到某节点或网络分区故障的时候,仍然能够对外提供满足一致性和可用性的服务。

这三个特性在分布式系统中最多满足两个。

一个分布式系统,节点组成的网络本该联通,然而可能因为故障,有些节点不连通了,整个网络分成了几个区域,数据散布在不连通的区域中,叫做分区。

当一个数据只在一个节点中保存,分区出现后,和这个节点不连通的部分就访问不到这个数据了,这时分区无法容忍。解决办法就是将一个数据项复制到多个节点上。但是,要将数据复制到多个节点上,就会带来一致性的问题,多个节点的数据可能不一致。要想一致,每次写操作就要等到全部节点写入成功,这个等待又会带来可用性的问题。

数据存在的节点越多,分区容忍性越高,但要复制更新的数据就越多,一致性就越难保证。为了保证一致性,更新所有节点数据所需要的时间就越长,可用性就会降低。

zookeeper是CP的,不能保证每次服务请求的可用性。在极端环境下,zookeeper会丢弃一些请求,消费者程序需要重新请求才能获取结果。如master节点因为网络问题和其它节点失去联系时,需要重新进行leader选举,时间比较长,整个期间zk集群都是不可用的。

注册中心应当是AP比较好。

一致性:客户端请求写入leader进程,leader同步到其它follower。

image-20220412000250154