ARTS （第64周）

故障流程：

故障现象->导致原因->解决方案->优化建议

Algorithm 算法

加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/plus-one
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

从末位开始计算进位，如果有进位就继续，没有进位了就直接返回

class Solution {
    public int[] plusOne(int[] digits) {
        if(digits == null )
        {
            return digits;
        }
        int carry = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
            if(carry == 0)//不用进位了 直接返回
                return digits;
        }
      	//要扩展位数
        int[] b = new int[digits.length + 1];
        b[0] = carry;
        System.arraycopy(digits, 0, b, 1, digits.length);
        return b;
    }
}

二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

从末位开始计算进位，记录进位信息，直到计算完成.

class Solution {
     public String addBinary(String a, String b) {
         if(a.length()==0  && b.length()==0 ){
            return "0";
        }
        StringBuilder res = new StringBuilder();
        int idx1 = a.length() - 1;
        int idx2 = b.length() - 1;
        int carry = 0;
        while (idx1 >= 0 ||  idx2>= 0 || carry != 0) {
            int v1 = (idx1 >= 0 ? a.charAt(idx1--) -'0' : 0);
            int v2 = (idx2 >= 0 ? b.charAt(idx2--) -'0': 0);
            res.append((v1 + v2 + carry) % 2);
            carry = (v1 + v2 + carry) / 2;
        }
        return res.reverse().toString();
    }
}

删除排序链表中的重复元素

 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2

输出: 1->2

示例 2:

输入: 1->1->2->3->3

输出: 1->2->3

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

逐个节点遍历，遇到相同数据就断开指针。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
   public ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            while(next != null && next.val==cur.val ){//一直到不一样 或者为空
                cur.next =  next = next.next;
            }
            cur = next;
        }
        return head;
    }
}

Review 英文文章

https://spring.io/guides/gs/service-registration-and-discovery/ spring使用注册中心和服务发现

Tip 技巧

线程池线程数量配置

CPU密集型（ CPU核心数+1）个线程
IO密集型方案1（ CPU核心数*2）个线程
IO密集型方案2 CPU核心数/（1-阻塞系数）个线程阻塞系数可以理解为阻塞时间的占比一般在0.8~0.9之间

幂等性方案

1、唯一索引，防止新增脏数据。

2、token机制，防止页面重复提交。

3、锁机制

3.1、悲观锁

获取数据的时候加锁获取，比如行锁。

3.2、乐观锁

乐观锁可以通过版本号，或者只是在更新数据那一刻锁表，其他时间不锁表，相对于悲观锁，效率更高。

3.3、分布式锁

在业务系统插入数据或者更新数据，获取分布式锁，然后做操作。

4、select + insert

并发不高的后台系统可以这么做。

5、状态机幂等（有限状态机）

在设计单据相关的业务，或者是任务相关的业务，肯定会涉及到状态机(状态变更图)，就是业务单据上面有个状态，状态在不同的情况下会发生变更，一般情况下存在有限状态机。

6、调用方保证幂等

如银行等接口，对外提供接口为了支持幂等调用，接口一般有两个字段必须传，一个是来源source，一个是来源方序列号seq，这个两个字段在提供方系统里面做联合唯一索引，这样当第三方调用时，先在本方系统里面查询一下，是否已经处理过，返回相应处理结果；没有处理过，进行相应处理，返回结果。

————————————————
版权声明：本文为CSDN博主「抽离的心」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u011635492/java/article/details/81058153

高并发方案

1、垂直分层

DNS层、跨机房部署、LVS+Nginx负载均衡，vanish+共享存储实现动静分离，Nginx后挂载N台服务器集群，服务器集群后挂载微服务化、微服务后挂载数据库分库分表+消息队列+任务调度，最后端挂载数据集群负责数据的统一归档+流计算+异步批处理

2、水平分区

根据业务划分业务线，每个业务线中设计分区键，根据userNo设计用户隔离，根据IP地址设计地区隔离，根据用户级别设计级别隔离，根据操作日期设计时间隔离，根据关键key进行hash散列，然后考虑一下分区的扩容、缩容、灾备、监控

3、数据同步

跨机房跨集群的困难点在于数据同步，有三种做法：

3.1）不同步，任由各子集群在自己的业务范围内运行

3.2）汇总集群，建立一个统一的数据汇总集群（如Hadoop\Spark\Kylin等），将数据汇总到统一的大数据集群中，再进行统计、汇总、运算等。缺点是会有时间差，短须5分钟，长须一天以上

3.3）远程数据同步，通过开源框架实现多个数据库的同步，例如阿里的otter，底层为canal，模拟mysql的从库，实现日志解析并数据库入库，时间差较短，如果网络没有太大问题，可在秒级完成数据同步。数据同步冲突算法有两种：单向回环补救、时间交集补救。一般推荐使用单向回环补救，即：如果发现数据库A与数据库B的同步时间差大于某个数值，则根据pk查询最新记录同步到数据库中。而另一种算法时间交集补救，是根据“时间交集”的定义，获得双方数据库的“时间交叉的操作”清单，然后根据此清单执行单向回环补救。此方法缺点为：a)开源版本中仅有单向回环补救;b)只支持mysql->mysql同步或者mysql->oracle同步。

注意细节

集齐以上三件，基本上百万级并发就轻松搞定了。然后需要注意一些细节：

1）集群与集群之间要实现从入口开始的严格隔离，即DNS层->LVS层->Nginx层完全隔离

2）数据库的链接数是重要资源，一个mysql数据库可以提供1000链接，也就是说，按照50链接/每机器来计算，最多链接20个实例，硬上一下超不过30台。因此数据库层的分库分表一定要彻彻底底的分开。子集群之间不能互相链接数据库。

3）一些关键业务可以在缓存中操作，建议采用redis缓存。而memcache死机后数据丢失，mongodb功能尚不完善。redis的安全机制一定要做好，千万不能丢数据。缓存到数据库的存储可以采用计数形式，每隔N次操作存一次数据库，可以线性降低数据库压力

4）数据库只使用简单的存取功能，所有业务功能在代码层实现，DBA推荐的分区、分存储、存储过程等功能一般在数据仓库中是有用的，而在实时计算系统中，千万不要采用。否则你会看到你们几百人的开发团队等待一个DBA给你们排期的情况。

5）前端可以做一些小的手段，例如抽奖活动，可以在页面js中直接告诉用户未中奖，而并不通知后台，此为“基础不中奖率”，可以直接过滤掉90%以上的流量。（此功能请与产品团队好好沟通，从性价比上讲，这种小手段不提倡，但是性价比极高。）

6）消息队列系统建议采用一些堆积能力较强的系统，如:rocketmq,rabbit等，建议rocketmq，消息堆积能力之强，单机堆积上亿条。

7）日志系统建议kafka，日志系统之后可以增加storm,hdfs,logstash等配套设施

8）网卡流量问题需要严重关注，经常出现的问题是：在某个活动之间，redis网卡流量打满，导致redis无法访问，整个业务暂停。需要网络部门对公司内部的服务器路由有准确估算，出现分值之后可以妥善定位问题并修复，日常工作中也要做好规划，提前做好准备。

9）老生常谈的：断路器、限流、自动降级。断路器是指在RPC的客户端中实现如下功能：如果发现该断路器访问服务端在10秒内访问超过50次且失败率高于50%，则中断该断路器的访问10秒钟，以保护下游系统。自动降级就是：如果发生问题，自动切换到备用程序上，如报错、如访问redis失败改访问DB等。限流就是在RPC的服务端中实现如下功能：对每个IP、每个token进行限制，通过令牌桶算法，每个时间段只允许指定数量的服务通过，否则就拒绝服务调用。一般断路器使用hystrix，自动降级可以自行实现，也可以用hystrix的配套设施实现，限流比较简单自行实现即可。

来自知乎的一个大神的文章：https://zhuanlan.zhihu.com/p/38636111

https://blog.csdn.net/mmayanshuo/article/details/85010107 多任务并发：如何判断线程池中的任务都已经执行完毕？

https://www.jianshu.com/p/3c5d7f09dfbd ThreadLocal

https://blog.csdn.net/u011635492/article/details/81058153 高并发下接口幂等性解决方案

https://blog.csdn.net/boonya/article/details/64918478?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-9.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-9.nonecase 幂等性解决方案

https://blog.csdn.net/HD243608836/article/details/102735442 高并发其实挺容易的，当你明白了一万并发的原理，然后扩展到百万、千万、亿万级很easy