G家VO挂经

alpaca1234 发表于 2020-7-23 22:30
第四轮task scheduler 我猜要的是conditional variable,

一个thread run task，while True: check priot ...

这题面试官说不用考虑多线程，没搞太懂

alpaca1234 发表于 2020-7-23 21:45
第三题感觉是dijistra变体

[010101E,

你这个想法里，这句话“下一步走离狮子最远的，maintain一个global min”的意思是：
从start开始，每次都走四个方向里面数值最大的那个（数值就是这个点到最近的狮子的距离），同时记录从S到E的路径上遇到过的最小的点？每次选数值最大的方向是因为这是最安全的？（感觉这个地方是这个题目最隐晦的point）

感觉第三天就是那个建立邮局，遍历每个狮子，把每个点到每个狮子的距离加起来， 然后bfs 起点到终点，保存一个最大？

楼主，你每轮多长时间啊，recruiter 告诉我45 分钟一轮，这些题的难度➕讨论时间，怎么可能45 分钟搞两个题呢

旧未来 发表于 2020-7-24 07:35
你这个想法里，这句话“下一步走离狮子最远的，maintain一个global min”的意思是：
从start开始，每次 ...

是这个意思

Wu_kong 发表于 2020-7-24 07:41
楼主，你每轮多长时间啊，recruiter 告诉我45 分钟一轮，这些题的难度➕讨论时间，怎么可能45 分钟搞 ...

45分钟，所以需要反应很快同时写得很快

f0rest77 发表于 2020-07-23 21:01:18
45分钟，所以需要反应很快同时写得很快

这个太厉害了，这重hard 就是写也得写 10-15 分钟吧， 还得bug free

scheduler那个设计其实蛮常规的，做过的自然是知道。
首先最简单的方法就是一个job一直跑着，可以用daemon thread做，定期去poll数据库里全部记录，到时间了就取出来。

其次就是用java delay queue，具体API自己查一下，如果需要多线程的话还有给你封装好了的库，叫DelayedExecutorService (好像是这个名字），直接创建thread pool就行了 （如果你这个开始就都不知道，那基本就挂了）
、
第三种方式是使用时间轮， 这是我个人最喜欢的一个数据结构，非常优雅。英文叫TimingWheel，不知道的也是自己查一下。

第四种方式是用rabbitMQ的TTL加delivery Queue机制，维护两个message queue，用户产生schedule的时候把job放进第一个queue，过期时间设置为用户的timing，这样用户的job过期（到时间）以后会自动转移到第二个queue（注意这个功能只有RabbitMQ提供），你通过设置可以让rabbitMQ直接push给你的worker达到实时启动的目的。


最后一种方式是多线程，分布式，大数据环境下常用的，Redis Zset，加分布式锁。

刘爱华 发表于 2020-7-24 21:32
scheduler那个设计其实蛮常规的，做过的自然是知道。
首先最简单的方法就是一个job一直跑着，可以用daemon ...

赞一个! 我个人非常喜欢时间轮，尤其是多层级时间轮可以处理其他几种方式处理不了的场景。

补一个关于TimeWheel的blog：
https://blog.acolyer.org/2015/11 ... ical-timing-wheels/

再讨论一下层主说的几种design的tradeoff，有不对的地方也欢迎层主指正：

1.前两种方式不适用于load number很大同时又要求delayed time精度很高的场景

2. 时间轮很好用，但是因为一般需要自己造轮子或者用定制现有的message queue/distributed cache作为时间轮的载体。开发和维护的时间空间成本相对于其他选项来说偏高，因此需求不复杂的情况下可能不是top choice

3. rabbitmq 最长delay time是2天，aws sqs是15分钟，delay time超过这个时间的话没有办法用这两个（或者其他任何开源的）delay queue 机制

4. zset 加分布式锁需要考虑场景是否需要100% exactly once ，如果需要的话怎么配置Redis

其实设计scheduler的时候有一个比较critical的需求需要clarify，就是 用户输入的时间是绝对时间还是相对时间，以及 （相对）时间可以是任意值 还是 只能从提前定义好的值域里面选择（比如只有15分钟，30分钟，1小时，12小时 这四个选项，用户只能4选一）。 如果可以提前定义值域的话可能就不需要轮子或者sorted set(zset)这种order matters的数据结构，直接根据值域定义几个线性的mq即可

arcovitcher 发表于 2020-7-24 23:13
赞一个! 我个人非常喜欢时间轮，尤其是多层级时间轮可以处理其他几种方式处理不了的场景。

补一个关于 ...

tradeoff的话
第一个肯定是最naive的做法，但是非常有效，在每天就几千个job的层面完全没有问题，比如公司内部的report scheduler。

第二个的问题是它跑在一个JVM里面，你可以用多线程，但是依然是跑在一台机器上，扩展性收到限制。

时间轮你说的很多了，有个需要注意的地方是时间轮基本都是单线程，因此schedule job的时候一定要采用异步模式，否则直接阻塞下一秒了。

rabbitmq这个实现方式其实不是用delay queue，而是exchange，ttl理论上可以设成很大，因此不存在两天这种限制：
https://www.cloudamqp.com/blog/2 ... %20routing%20agents,a%20queue%20to%20an%20exchange.

最后一个直接用queryWithScore就行了，取出来schedule以后要remove掉。取和删两个操作放一起就不是原子的，因此需要分布式锁来保证不会有两个worker取到同一个任务。