ARTS-13-分布式系统入门和实践笔记

ARTS的初衷

Algorithm: 主要是为了编程训练和学习。

Review：主要是为了学习英文

Tip：主要是为了总结和归纳在日常工作中所遇到的知识点。学习至少一个技术技巧。在工作中遇到的问题，踩过的坑，学习的点滴知识。

Share：主要是为了建立影响力，能够输出价值观。分享一篇有观点和思考的技术文章

https://www.zhihu.com/question/301150832

一、Algorithm

Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]

Output: [1,2,4]

Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]

Output: [4,3,2,2]

Explanation: The array represents the integer 4321.

class Solution {
      public int[] plusOne(int[] digits) {
          if(digits==null || digits.length==0) {
              return digits;
          }
          //123 => 124,999=>1000
          int tmp = 1;
          for(int i=digits.length-1;i>=0;i--) {
              int digit = (digits[i]+tmp)%10;
              tmp = (digits[i]+tmp)/10;
              digits[i] = digit;
              if(tmp==0) {
                  return digits;
              }
          }
          int[] res =  new int[digits.length+1];
          res[0] = 1;
          return res;
      }
  }

二、Review

分布式系统设计的基础-CAP理论，描述的是在异步网络中的读写存储系统中无法同时满足下面的三个条件

1、一致性，所有节点看到的读写操作结果都是一样的（Consistency – all executions of reads and writes seen by all nodes be atomic or linearizably consistent） 2、可靠性，请求总能获取正常响应（Availability – a request made to the data store always eventually complete） 3、分区容忍性，允许网络中的消息丢失(Partition tolerance – the network is allowed to drop any messages）

出于可靠性的考虑，数据通常会被复制为多个副本，所以还需要强一致性保证读写行为

一致性里面还有一种形态是最终一致性。无法做到强一致性时，采用适合的方式达到最终一致性，这其实就是BASE理论，ES和Kafka都是最终一致性系统

然而异步网络并不总是可靠的，一致性和可靠性必须二选一，在这种情况下你只能返回一个不是最新的值，或者拥塞等待(长时间等待potentially forever)同步,后者不可取

异步网络是指存在系统时钟差异(Your nodes have clocks that may drift apart)和消息延迟传递(System processes may arbitrarily delay delivery of a message (due to retries, or GC pauses)

三选二组合模型有，CA模型，它不能容忍网络错误或者节点错误，比如两阶段提交(2PC)；CP模型，它关注的是保证大多数节点数据一致，比如Paxos共识算法；AP模型，它关注的可用性和分区容忍性

分布式系统中还有一种常常被相提并论的FLP不可能性理论(FLP result)，它描述的是：在网络可靠，并且允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法。FLP理论与CAP理论的区别是它是静默失败的，同时不允许消息丢失(FLP permits the possibility of one ‘failed’ node which is totally partitioned from the network and does not have to respond to requests。Otherwise, FLP does not allow message loss; the network is only asynchronous but not lossy。FLP deals with consensus, which is a similar but different problem to atomic storage)

分布式系统实践笔记： 1、Distributed systems are different because they fail often。分布式系统并不是将数据传输到多台主机中，失败时简单地一直重试直到成功。有可能仅仅是部分失败，也有可能是成功将数据写入领导者，由于GC导致无法将数据复制给追随者，所以分布式系统中需要充分考虑好失败设计 2、Writing robust distributed systems costs more than writing robust single-machine systems。资源使用更多 3、Robust, open source distributed systems are much less common than robust, single-machine systems。健壮性不如单机应用 4、Coordination is very hard。Paxos共享算法应该是从知道到放弃最经典的诠释了，少有工程师能实现这个算法，可想而知CP模型实现是有多困难 5、If you can fit your problem in memory, it’s probably trivial,将单机应用的问题排查技巧生搬硬套到分布式系统中是徒劳的 6、 “It’s slow” is the hardest problem you’ll ever debug。Dapper和Zipkin链路跟踪系统为此而生 7、 Implement backpressure throughout your system。数据流从上游生产者向下游消费者传输的过程中，上游生产速度大于下游消费速度，导致下游的Buffer溢出，这种现象就叫做Backpressure出现，这种现象出现时我们需要将部分数据扔掉或者将错误直接返回，避免雪崩。另外在进行RPC连接时实现超时设计和指数补偿是完全有必要的，当连接失败时，睡眠一段时间后再重试，每失败一次睡眠的时间就延长一些 8、Find ways to be partially available。大部分搜索系统设计都满足部分可用原则，当超时时间到达时，无论检索出什么结果都先返回给用户 9、Metrics are the only way to get your job done。监控 10、Use percentiles, not averages，监控指标衡量使用百分比(50th, 99th, 99.9th, 99.99th)而不是平均数\中位数,因为它能让我们更好地了解真实分布 11、Learn to estimate your capacity，学会估算系统的承载力，感兴趣的读者自行阅读http://bigocheatsheet.com/和http://www.cs.cornell.edu/projects/ladis2009/talks/dean-keynote-ladis2009.pdf 12、Feature flags are how infrastructure is rolled out. 通过AB测试获取功能反馈 13、Choose id spaces wisely 保证序列号标识ID充足，不推荐使用DB默认的自增生成，容易暴露业务如一天订单情况 14、Exploit data-locality。每当CPU要读取内存的时候，它会读取一整个缓存页，你能把越多你可能用到的数据挤到这个数据页里面，你就跑得更快，所以尽可能地提高数据的局部性 15、Writing cached data back to persistent storage is bad。If the implementers talk about “Russian-doll caching”, you have a large chance of hitting highly visible bugs，一种称为「俄罗斯套娃」的缓存机制(缓存嵌套)有潜在的可见性bugs,和标题好像不相关啊？我认为它描述的是更新数据时，如果处理缓存和DB才能保证可见性吧。我的理解是，读请求，不要求强一致性的读缓存，要求强一致性的直接从DB读取。写请求，数据首先都写到数据库，之后更新缓存（先写缓存再写DB的话，写入失败后事务回滚可能会造成缓存与DB数据不一致）。删除操作，先删除DB再删除缓存 16、Computers can do more than you think they can。嗯嗯，CPU处理能力确实以火箭的速度在提升，IO处理能力则是以火车的速度 17、Use the CAP theorem to critique systems. 使用CAP原则重构系统 18、Extract services。分层设计，隐藏内部实现，对外提供服务API，类似七层计算机模型，只需要关注下一层的实现而不用关心更低层的实现

参考英文文章： https://www.the-paper-trail.org/page/cap-faq/ https://www.the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/ https://www.somethingsimilar.com/2013/01/14/notes-on-distributed-systems-for-young-bloods/ https://en.wikipedia.org/wiki/Exponential_backoff https://www.dynatrace.com/news/blog/why-averages-suck-and-percentiles-are-great/

三、Tip

1、618大促要来临了，友商开始蠢蠢欲动,开屏广告和点击弹窗跳转，流量劫持一般是修改js文件。网上找到一个前端神器Subresource Integrity,它是通过生成文件的唯一hash值进行对比校验的，它能有效减少劫持

2、JAVA8中的Stream是如何高效遍历集合的？

List<String> names = Arrays.asList(" 张三 ", " 李四 ", " 王老五 ", " 李三 ", " 刘老四 ", " 王小二 ", " 张四 ", " 张五六七 ");

String maxLenStartWithZ = names.stream()
                    .parallel()
                    .filter(name -> name.startsWith(" 张 "))
                    .mapToInt(String::length)
                    .max()
                    .toString();

从大的设计方向上来说，Stream将整个操作分解为了链式结构，不仅简化了遍历操作，还为实现了并行计算打下了基础。从小的分类方向上来说，Stream将遍历元素的操作和对元素的计算分为中间操作和终结操作，而中间操作又根据元素之间状态有无干扰分为有状态和无状态操作，实现了链结构中的不同阶段

在串行处理操作中，Stream在执行每一步中间操作时，并不会做实际的数据操作处理，而是将这些中间操作串联起来，最终由终结操作触发，生成一个数据处理链表，通过Java8中的Spliterator迭代器进行数据处理；此时，每执行一次迭代，就对所有的无状态的中间操作进行数据处理，而对有状态的中间操作，就需要迭代处理完所有的数据，再进行处理操作；最后就是进行终结操作的数据处理

在并行处理操作中，Stream对中间操作基本跟串行处理方式是一样的，但在终结操作中，Stream将结合 ForkJoin框架对集合进行切片处理，ForkJoin框架将每个切片的处理结果Join合并起来

作者BLOG：www.liangsonghua.me

作者介绍：京东资深工程师-梁松华，在稳定性保障、敏捷开发、JAVA高级、微服务架构方面有深入的理解