翻转链表算法、自动化测试框架 robot-framework、两款 iOS 在手机端 debugging 工具 Flex、啄木鸟、加密技术 高可用系统的度量 高可用系统的架构 高可用系统的运维 John 易筋 ARTS 打卡 Week 15

用户头像
John(易筋)
关注
发布于: 2020 年 08 月 30 日

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 的时候,当前可能整天系统都处于一种极限的高并发访问压力之下,这时候就可以将确认收货、评价这些非核心的功能关闭,将宝贵的系统资源留下来,给正在购物的人,让他们去完成交易。



异地多活

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



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



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



发布于: 2020 年 08 月 30 日 阅读数: 134
用户头像

John(易筋)

关注

问渠那得清如许?为有源头活水来 2018.07.17 加入

工作10+年,架构师,曾经阿里巴巴资深无线开发,汇丰银行架构师/专家。开发过日活过亿的淘宝Taobao App,擅长架构、算法、数据结构、设计模式、iOS、Java Spring Boot。易筋为阿里巴巴花名。

评论 (1 条评论)

发布
用户头像
标题还是简短些比较好
2020 年 08 月 31 日 09:56
回复
没有更多了
翻转链表算法、自动化测试框架robot-framework、两款iOS 在手机端debugging 工具Flex、啄木鸟、加密技术 高可用系统的度量 高可用系统的架构 高可用系统的运维 John 易筋 ARTS 打卡 Week 15