ARTS-第二周

耗子叔发起的ARTS计划,第二周。
ARTS计划简介:

https://time.geekbang.org/column/article/85839?from=singlemessage

A

leetcode题库中第692题:前K个高频单词


给一非空的单词列表,返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。

示例:
1
2
3
4
5
6
7
8
9
10
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词,均为2次。
注意,按字母顺序 "i" 在 "love" 之前。


输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词,
出现次数依次为 4, 3, 2 和 1 次。
说明:
  1. 假定 k 总为有效值, 1 ≤ k ≤ 集合元素数。
  2. 输入的单词均由小写字母组成。
解答:

思路
计算top-n分为两步:

  1. 统计: 创建一个LinkedHashMap<String, Integer>,遍历字符数组,如果字符串在map中不存在,那么添加,设置Integer为1。 如果字符串已经存在,那么取出Integer并且增加1
  2. 排序: 当遍历完毕后,对Map进行排序,取出前K个值返回。

统计过程需要的算法时间复杂度为0(N)
关键还在于排序算法的选取。

发现选的算法题有点难。。。先把排序算法过滤一遍再写。。

R

Sentinel的核心概念:

  • Resource

    任何都可以被定义为一个Resource,比如一个服务,一个方法,甚至是一个代码片段。
    如果被Sentinel的API定义为一个Resource,那么它可以使用Sentinel提供的保护方法。

  • Rules

    Sentinel通过使用Rules来定义保护资源的方法,比如流控,并发,熔断。Rules可以动态改变,并且实时生效。

流控的原则

流量控制基于以下角度:

  1. 资源的调用链路。
  2. 运行时的指标,比如QPS,系统负载,请求响应时长。
  3. 期望触发的动作,比如拒绝或者对请求进行排队。
    Sentinel理想是让用户自由选择控制角度,灵活组合,以达到想要的效果。
熔断

熔断被用来检测错误和封装一些逻辑去防止一些可能在维护期频繁出现的故障,或者是临时的系统故障,或者是一些不期望发生的故障。
为了解决这个问题,Hystrix选择使用线程和线程池来实现资源之间的隔离。使用线程池的主要好处就是隔离是很干净的。
Sentinel使用了不同的方式:

  • 控制最大的并发线程:
    为了替代使用线程此,Sentinel通过严格的限制并发线程的数量,来减少不稳定资源带来的影响。
    当资源的响应时间变长,线程将会被占据。当线程累计到一定的数量的时候,新到来的请求将会被拒绝。反而言之,当资源恢复,重新变的稳定的时候,被占据的线程将会得到释放,新的请求将会被接收。
    通过限制最大并发线程数量代替线程池,不需要再提前分配线程,也可以避免计算开销,比如排队,任务调度和线程上下文切换。。
    完全看不懂啊,这翻译的,线程池和最大的并发线程有啥区别啊?怎么就避免线程切换开销了

  • 根据响应时间来控制:
    除了限制并发线程数,根据响应时间来对不稳定资源进行降级处理也是一种有效的途径去实现熔断。当一个请求的响应时间太长,在一个指定的时间窗口内所有的请求将都会被拒绝。

    负载保护

    Sentinel可以保护我们的系统防止我们的系统负载过高。它可以帮助我们使我们的系统负载以及请求达到一个平衡,让系统保持一个比较高的处理速度。

    Sentinel如何工作?
    1. 提供API接口适配一些常用的第三方框架来定义资源。
    2. 收集运行时信息,跟踪调用资源时的路径。
    3. 定义一些实时规则。
    4. 提供实时监控,一些拓展规则的配置。

T

今天去蚂蚁金服听了泽胤大神分享的《高效推送服务的架构思考》,收货挺大的。
总结几个点:

  1. 因为系统SLA的不同,所以系统的侧重点不同。

    如果系统要求SLA高,那么必须让服务保持高稳定性,因此系统的负载不能过高。如果系统要求SLA低,那么可以让服务保持满负荷。可以通过使用MQ来实现此类系统的解耦。

  2. 引入MQ,将API与后台服务之间的调用从同步改为异步,可以大大提高API的性能,以及稳定性。

  3. 引入MQ后,只是将API的流量转接给了MQ,例如本来API要处理100W条推送,那么在接入MQ后,API仍旧要发送消息,只是会把消息发送给MQ。 MQ也不可能瞬间处理这么高的QPS,需要将消息在内存中打批,通过批处理的形式传送给MQ。因为请求会在内存中打批,所以可能会出现请求丢失的问题。这个问题他们现在也没有更好的解决方案。
  4. 因为引入MQ,所以需要考虑幂等性的处理。解决方案为每次请求有一个唯一ID,通过redis来校验消息是否重复。
  5. 因为不同业务,可能有不同的优先级,所以对不同优先级的消息推送建立不同的topic,通过订阅不同的topic来处理不同优先级的消息。
  6. 消息如果消费失败,那么不应该返回fasle,这样的话在RocketMQ中会因为会进行消息重投,导致后续消息被延迟消费。正确的做法应该是将失败消息转发到另外一个队列中,另外一个队列专门用来处理这些消费失败的消息。
  7. topic以及tag的划分应该以消息的规模,消息的大小这两个维度来进行划分。

大致回忆出了七条使用MQ要注意的点。这是一个真实的使用MQ来进行系统间解耦的案例,很值得借鉴以及学习,分享很棒。

S

简单介绍一下RocketMQ的消息过滤实现原理,参考丁威老师的《RocketMQ技术内幕》。
地址为:

http://www.xunyajie.com/2019/03/30/RocketMQ%E6%B6%88%E6%81%AF%E8%BF%87%E6%BB%A4%E5%88%86%E6%9E%90/