1. Algorithm: 每周至少做一个 LeetCode 的算法题

题目

61. Rotate List



Given a linked list, rotate the list to the right by k places, where k is non-negative.



Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL



公用链表

公用链表定义，方便打印入参和结果

package common;
public class ListNode {
    public int val;
    public  ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
    static public ListNode listNodeWithIntArray(int[] input) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        for (int i: input) {
            ListNode newNode = new ListNode(i);
            node.next = newNode;
            node = node.next;
        }
        return head.next;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode node = this;
        while (node != null) {
            sb.append(node.val).append("-->");
            node = node.next;
        }
        return sb.append("Null").toString();
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        return false;
    }
}



顺着思路解决

由于n可能比列表的长度大。所以我们需要知道链表的长度，然后将第（ln％l）个节点后的链表移到最前面以完成旋转。



例如：{1,2,3} k = 2将列表从第一个节点移到最前面



例如：{1,2,3} k = 5，在这种情况下，将第（3-5％3 = 1）个节点之后的列表移到最前面。



因此，代码包含三个部分。



1. 得到长度

2. 移至第（ln％l）个节点

3. 做旋转



public class RotateList {
  public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) {
      return head;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    int len = 0;
    // get the length
    for (; fast.next != null; len++) {
      fast = fast.next;
    }
    // step = len - k / len
    for (int step = len - k % len; step > 0; step--) {
      slow = slow.next;
    }
    // rotation
    fast.next = dummy.next;
    dummy.next = slow.next;
    slow.next = null;
    return dummy.next;
  }
  public static void main(String[] args) {
    RotateList obj = new RotateList();
    int[] input = {1, 2, 3, 4, 5};
    //int[] input = {1};
    ListNode initNode = ListNode.listNodeWithIntArray(input);
    System.out.println(initNode.toString());
    ListNode resultNode = obj.rotateRight(initNode, 2);
    //ListNode resultNode = obj.rotateRightWithCircle(initNode, 2);
    System.out.println(resultNode.toString());
  }
}



最后转换哪里有点烧脑，画图就很清晰了：

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
dummy         slow      fast



把链表头尾相连形成环状解决

我的解决方案具有O（n）时间复杂度和O（1）内存。

基本思想是将列表连接成一个圆圈。首先，在遍历列表以查找列表末尾时计算列表的长度。将尾巴连接到头部。问题要求旋转k个节点，但是，现在尾部位于列表的末尾，并且很难向后移动，因此请沿列表移动（k-len）个节点。“K = K％LEN”节省不必要的移动，因为旋转的与长度列表= len个由LEN倍不改变在所有列表。

public class RotateList {
  public ListNode rotateRightWithCircle(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) {
      return head;
    }
    ListNode tail = head;
    int len = 1;
    // count length
    while (tail.next != null) {
      tail = tail.next;
      len++;
    }
    // form a circle
    tail.next = head;
    int step = len - k % len;
    while (step > 0) {
      tail = tail.next;
      step--;
    }
    head = tail.next;
    tail.next = null;
    return head;
  }
  public static void main(String[] args) {
    RotateList obj = new RotateList();
    int[] input = {1, 2, 3, 4, 5};
    //int[] input = {1};
    ListNode initNode = ListNode.listNodeWithIntArray(input);
    System.out.println(initNode.toString());
    ListNode resultNode = obj.rotateRightWithCircle(initNode, 2);
    System.out.println(resultNode.toString());
  }
}



控制台打印入参，和结果

1-->2-->3-->4-->5-->Null
4-->5-->1-->2-->3-->Null



2. Review: 阅读并点评至少一篇英文技术文章

robot-framework-tutorial

https://medium.com/edureka/robot-framework-tutorial-f8a75ab23cfd



这篇文章讲述了如何做手机App自动化测试，用robot框架。笔者翻译成中文博客如下：



您需要了解的有关使用Python的Robot Framework框架的所有信息, Appium



3. Tips: 学习至少一个技术技巧

笔者写的博客：



推荐两款iOS手机debug工具 Flex 和 啄木鸟(阿里巴巴开源)



说明

记录两款iOS 在手机端debugging 工具, 可以查看日志，UI控件查看，调试等。 Flex（开源）， [啄木鸟（阿里巴巴开源）](https://github.com/alibaba/youku-sdk-tool-woodpecker)



Flex

FLEX（Flipboard Explorer）是用于iOS开发的一组应用程序内调试和探索工具。出现时，FLEX显示一个工具栏，该工具栏位于应用程序上方的窗口中。通过此工具栏，您可以查看和修改正在运行的应用程序中的几乎每个状态。



!在这里插入图片描述



功能简介

• 检查和修改层次结构中的视图。

• 查看任何对象的属性和错误。

• 动态修改许多属性和错误。

• 动态调用实例和类方法。

• 查看详细的网络请求历史记录以及时间，标题和完整响应。

• 添加您自己的模拟器键盘快捷方式。

• 查看系统日志消息（例如来自NSLog）。

• 通过扫描堆访问任何活动对象。

• 查看应用程序沙箱中的文件系统。

• 浏览文件系统中的SQLite / Realm数据库。

• 使用控制键，Shift键和Command键在模拟器中触发3D触摸。

• 探索您的应用程序和链接的系统框架（公共和私有）中的所有类。

• 快速访问有用的对象，例如[UIApplication sharedApplication]，应用程序委托，键窗口上的根视图控制器等等。

• 动态查看和修改NSUserDefaults值。



与许多其他调试工具不同，FLEX完全在您的应用程序内部运行，因此您无需连接到LLDB / Xcode或其他远程调试服务器。它在模拟器和物理设备上都能很好地工作。



啄木鸟



功能简介

1.UI检查：快速查看页面布局、UI控件间距、字体颜色、UI控件类名、对象属性/成员变量、图片URL等。

2.JSON抓包：便捷JSON抓包工具，通过监听系统json解析抓包。

3.方法监听：Bug听诊器，可监听App中任意OC方法的调用，输出调用参数、返回值等信息，可以通过屏幕日志输入监听、KVC取值等命令，支持后台配置命令。

4.po命令：执行类似LLDB的po命令，在App运行时执行po命令，调用任意方法。

5.系统信息：查看各种系统名称、版本、屏幕、UA等信息，支持外部添加信息。

6.SandBox：查看沙盒文件，导出文件等。

7.Bundle：查看、导出Bundle目录中的内容。

8.Crash：查看Crash日志，需先打开一次Crash插件以开启Crash监控。

9.Defaults：查看、新增、删除User Defaults。

10.清除数据：清除所有沙盒数据、User Default。

11.触点显示：显示手指触控。

12.UI对比：支持将设计图导入到App中进行对比，并可画线、标注需修改的地方，方便UI走查。

13.查看图片资源：查看、导出App中的资源图片。

14.CPU：查看CPU占用。

15.内存：查看内存占用。

16.FPS：查看App帧率。

17.网络流量：查看发送、接收网络流量。



架构图



参考

https://github.com/FLEXTool/FLEX



https://github.com/alibaba/youku-sdk-tool-woodpecker



4. Share: 分享一篇有观点和思考的技术文章

笔者写的博客链接



极客大学架构师训练营 加密技术 高可用系统的度量 高可用系统的架构 高可用系统的运维 第22课 听课总结



高可用系统的度量

可用性指标



业界通常用多少个9来衡量网站的可用性，如 QQ 的可用性是4个9，即 QQ 服务99.99% 可用，这意味着 QQ 服务要保证其在所有运行时间中，只有0.01% 的时间不可用，也就是一年中大约53分钟不可用。



网站年度可用性指标 = （1 - 网站不可用时间 / 年度总时间）x 100%

网站不可用时间（故障时间）= 故障修复时间点 - 故障发现（报告）时间点



对可用性的定性描述，两个9是基本可用，年度停机时间小于88小时；3个9较高可用，年度停机时间 小于 9小时；4个9是具有自动恢复能力的高可用，年度停机时间小于 53 分钟； 5个9是极高可用性，年度停机时间小于 5 分钟。由于可用性影响因素很多，对于网站整体而言，达到4个9，乃至5个9的可用性，除了过硬的技术、大量的设备资金投入和工程师的责任心，还要有个好运气。



淘宝、支付宝、微信一般都宣称是99.99%。 如果更高一个成本太高，一个是技术上也比较难达到。一年53分钟不可用。更多是应用某个功能不可用，一般不会是全网站不可用。

Twitter 之前可用性是在 98% 是比较低的。



故障分类管理

故障处理流程及考核





引起故障的原因

• 硬件故障

• 软件 bug

• 系统发布

• 并发压力

• 网络攻击

• 外部灾害



高可用系统架构

解耦

• 高内聚、低耦合的组件设计原则

• 面向对象基本设计原则

• 面向对象设计模式

• 领域驱动设计建模



隔离

• 业务与子系统隔离

• 微服务与中台架构

• 生产者消费者隔离

• 虚拟机与容器隔离



异步

• 多线程编程

• 反应式编程

• 异步通信网络编程

• 事件驱动异步架构



备份

• 集群设计

• 数据库复制：CAP原理

任何情况下都不能只用一台服务器提供服务，任何服务都要提供2个以上的服务器。

都要考虑当一台服务器不可用的时候，其它服务器可以替代使用。架构师在系统架构设计的时候，都要考虑这种异常情况。



Failover （失效转移）

• 数据库主主失效转移。

• 负责均衡失效转移。



如何确认失效，需要转移？



设计无状态的服务。



幂等

应用调用服务失败后，会将调用请求重新发送到其它服务器，但是这个失败可能是虚假的失败。比如服务以及处理成功，但是因为网络故障应用没有收到响应，这时应用重新提交请求就导致服务重复调用，如果这个服务是一个转账操作，就会产生严重的后果。



服务重复调用有时候是无法避免的，必须保证服务重复调用和调用一次产生的结果相同，即服务具有幂等性。有些服务天然具有幂等性，比如将用户性别设置为女性，不管设置多少次，结果都一样。但是对于交易等操作，问题就会比较复杂，需要通过交易编号等信息进行服务调用有效性校验，只有有效的操作才继续执行。



事务补偿

• 传统事务的 ACID：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation，又称独立性）、持久性（Durability）。

• 分布式事务的 BASE：基本可用（Basic Availability）、软状态（Soft-State）、最终一致性（Eventual Consistency）。



事务补偿：通过执行业务逻辑逆操作，使事务回滚到事务前状态。



重试

远程服务可能会由于线程阻塞、垃圾回收或者网络抖动，而无法及时返还响应，调用者可以通过重试的方式修复单词调用的故障。

• 上游调用者超时时间要大于下游调用者超时时间之和。



熔断

当某个服务出现故障，响应延迟或者失败率增加，继续调用这个服务会导致调用者请求阻塞，资源消耗增加，进而出现服务级联失效，这种情况下使用断路器阻断对故障服务的调用。

• 断路器三种状态：关闭，打开，半开。

• Spring Cloud 断路器实现：Hystrix



限流

在高并发场景下，如果系统的访问量超过了系统的承受能力，可以通过限流对系统进行保护。限流是指对系统的用户请求进行流量限制，如果访问量超过了系统的最大处理能力，就会丢弃一部分的用户请求，保证整个系统可用，保证大部分用户是可以访问系统的。这样虽然有一部分用户的请求被丢弃，产生了部分不可用，但还是好过整个系统崩溃，所有的用户都不可用要好。



限流的几种方法：

• 计数器算法（固定窗口，滑动窗口）

• 令牌桶算法

• 漏桶算法

计数器（固定窗口）算法

使用计数器在周期内累加访问次数，当达到设定的限流值时，触发限流策略。下一个周期开始时，进行清零，重新计数。

固定窗口算法的临界点问题：假设1min 内服务器的负载能力为100，一次一个周期的访问量限制在100，然而在第一个周期的最后5秒和下一个周期的开始5秒时间段内，分别涌入100的访问量，虽然没有超过每个周期的限制量，但是整体上10秒 内达到200的访问量，以远远超过服务器的负载能力。

计数器（滑动窗口）算法

将时间周期分为N个小周期，分别记录着每个小周期内访问次数，并且根据时间滑动删除过期的小周期。

假设时间周期为1min， 将1min 再分为2个小周期，统计每个小周期的访问数量，则可以看到，第一个时间周期内，访问量为75，第二个时间周期内，访问数量为100，超过100的访问则被限流掉了。



令牌桶算法

以固定的速度向令牌桶中增加令牌，直到令牌桶满，请求到达时向令牌桶请求令牌，如获取到令牌则通过请求，否则触发限流策略。

漏桶算法

访问请求到达时直接放入漏桶，如当前容量已达到限流值，则进行丢弃。漏桶以固定的速率进行释放访问请求，直到漏桶为空。

自适应限流

没有提前的人工评估，便没有提前的评估过时与人的评估疏漏/错误！

• 实时自动评估QPS

• 业务流量的不确定性与技术方案的自适应天上一对！

淘宝2019年双十一上线了自适应限流。

降级



有一些系统功能是非核心的，但是它也给系统产生了非常大的压力，比如说在电商系统中又确认收货这个功能，即便我们不去确认收货，系统也会超时自动确认收货。



但是实际上确认收货这个操作是一个非常重的操作，因为它会对数据库产生很大的压力：它要进行更改订单状态，完成支付确认，并进行评价等一系列操作。如果在系统高并发的时候去完成这些操作，那么会对系统雪上加霜，使系统的处理能力更加恶化。



解决办法就是在系统高并发的时候，比如说像淘宝双11 的时候，当前可能整天系统都处于一种极限的高并发访问压力之下，这时候就可以将确认收货、评价这些非核心的功能关闭，将宝贵的系统资源留下来，给正在购物的人，让他们去完成交易。



异地多活

如果整个数据中心都不可用，比如说数据中心所在城市遭遇了地震，机房遭遇了火灾或者停电，这样的话，不管我们的设计和系统多么的高可用，系统依然是不可用的。



为了解决这个问题，同时也为了提高系统的处理能力和改善用户体验，很多大型互联网应用都采用了异地多活的多机房机构策略，也就是说数据中心分布在多个不同地点的机房里，这些机房都可以对外提供服务，用户可以连接任何一个机房进行访问，这样每个机房都可以提供完整的系统服务，即使某一个机房不可使用，机房也不会宕机，依然保持可用。



异地多活的难点是数据一致。