两个指针缩小范围算法,CQRS 命令查询职责分离模式 John 易筋 ARTS 打卡 Week 09

发布于: 2020 年 07 月 19 日

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

167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

  • Your returned answers (both index1 and index2) are not zero-based.

  • You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

两个指针解法

左右指针两头分别往中间靠近,当然这里还有优化的空间,比如发现两头的和大于目标值,看看left + mid是否也超过,这可以直接折半查找。两头的和小于目标值,看看mid + right 是否也小于,这也可以折半查找。

package binarysearch;
public class TwoSumIIInputArrayIsSorted {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length < 2) {
throw new IllegalArgumentException("numbers array size is less than 2");
}
int left = 0;
int right = numbers.length - 1;
while (left < right) {
if (numbers[left] + numbers[right] == target) {
break;
} else if (numbers[left] + numbers[right] > target) {
right--;
} else {
left++;
}
}
return new int[]{left + 1, right + 1};
}
}

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

CQRS

https://martinfowler.com/bliki/CQRS.html

CQRS的全称是 Command Query Responsibility Segregation. 指的是 .

Martin Fowler 大神在2011年对这个概念的这篇博文,引起了行业内对其关注,并逐渐融合到了DDD的理念之中: https://martinfowler.com/bliki/CQRS.html

CQRS的核心理念就是把查询服务和命令处理做分拆,和DB的读写分离有异曲同工之妙。

那么在应用程序层面做读写的分离,有什么好处呢? 首先我们分析一下查询操作和命令处理操作有什么区别:

查询操作没有副作用,具有幂等性;命令操作会修改状态,其中新增操作若不加约束则不具有幂等性.

查询操作发起同步请求,需要实时返回查询结果,因而往往是阻塞式的 Request/Response 操作;命令操作可以发起异步请求,甚至可以不用返回结果,即采用非阻塞式的 Fire-and-Forget 操作.

查询结果往往需要面向 UI 表示层,命令操作只是引起状态的变更,无需呈现操作结果.

查询操作的频率要远远高于命令操作,而领域复杂性却又要低于命令操作.

既然命令操作与查询操作存在如此多的差异,采用一致的设计方案就无法更好地应对不同的客户端请求。

一个典型的CQRS的架构图是这样的:

使用CQRS之前,也一定要搞清楚是否适用当前的场景。不要乱用。

一般来说,普通的比较简单的业务场景下,乱用CQRS反而徒增系统的复杂度,得不偿失。

如果命令和查询重叠较多,共用一个CRUD的模型反而更简单些。

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

博客:

Charles 4.2 HTTPS抓包,乱码设置,证书信任,证书安装

经常有同学来问笔者如何配置Charles,索性就写个博客,SOP standard Operation Procedure提供给同学就好。从此这个问题解决。

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

极客大学架构师训练营 系统架构 分布式数据库 Zookeeper 第12课 听课总结

说明

讲师:李智慧

架构师要有设计、并开发出分布式数据库。仅仅是会用的话,竞争力是不够的。像阿里巴巴、腾讯、京东都有自己的分布式数据库开发团队,要想进入这个团队当架构师,就要有这种视野。

在公司里面,你要是听别人的,那么基本上都是把重复的、没有技术含量的活分配给你。人生的机会,都是自己去争取的。

作为架构师,要传递一个信息,打动公司,让公司支持你不赚钱的项目。你要有技术影响力,争取说服领导支持去你做这个事情,并且能够说服团队跟你一起干。

分布式一致性 ZooKeeper

分布式系统脑裂

在一个分布式系统中,不同服务器获得了互相冲突的数据信息或者执行指令,导致整个集群陷入混乱,数据损坏,统一称作分布式系统脑裂。

数据库主主备份

分布式一致性算法 Paxos

三个角色

  • Proposer

  • Acceptor

  • Learner

  1. 第一阶段:Prepare阶段。Proposer向Acceptors发出Prepare请求,Acceptors针对收到的Prepare请求进行Promise承诺。

  2. 第二阶段:Accept阶段。Proposer收到多数Acceptors承诺的Promise后,向Acceptors发出Propose请求,Acceptors针对收到的Propose请求进行Accept处理。

  3. 第三阶段:Learn阶段。Proposer在收到多数Acceptors的Accept之后,标志着本次Accept成功,决议形成,将形成的决议发送给所有Learners。

Proposer生成全局唯一且递增的Proposal ID(可使用时间戳Server ID),向所有Acceptors发送Prepare请求,这里无需携带提案内容,只携带Proposal ID即可。

Acceptors收到Prepare和Propose请求后

  1. 不再接受Proposal ID小于等于当前请求的Prepare请求。

  2. 不再接受Proposal ID小于等于当前请求的Propose请求。

ZooKeeper 架构

ZooKeeper 树状记录结构

ZooKeeper API

String create(path, data, acl, flags);
void delete(path, expectedVersion);
Stat setData(path, data, extectedVersion);
(data, Stat) getData(path, watch);
Stat exists(path, watch);
String[] getChildren(path, watch)
void sync(path)
List multi(ops)

配置管理

  • Administrator:setData("/config/param1", "value", -1)

  • Consumer:getData("/config/param1", true)

选 Master (Leader)

1. getdata("/servers/leader", true)

2. if successful follow the leader described in the data and exit

3. create("/servers/leader", hostname, EPHEMERAL)

4. if successful lead and exit

5. goto step 1

选 Master/ Leader (Python)

handle = zookeeper.init("localhost:2181", my_connection_watcher, 10000, 0)
(data, stat) = zookeeper.get(handle, "/app/leader", True);
if (stat == None)
path = zookeeper.create(handle, "/app/leader", hostname:info, [ZOO_OPEN_ACL_UNSAFE], zookeeper.EPHEMERAL)
if (path == None)
(data, stat) = zookeeper.get(handle, "/app/leader", True)
# someone else is the leader
# parse the string path that contains the leader address
else
# we are the leader continue leading
else
# someone else is the leader
# parse the string path that contains the leader address

集群管理(负载均衡与失效转移)

Monitoring process:

  1. Watch on/nodes

  2. On watch trigger do getChildren(/nodes, true)

  3. Track which nodes have gone away

Each Node:

  1. Create /nodes/node-${i} as ephemeral nodes

  2. Keep updating /nodes/node-${i} periodically for node status changes (status updates could be load/iostat/cpu/others)

ZooKeeper 性能

  • 读的能力要远远高于写的能力。这是因为写的时候要最终选举一个结果,读的时候,随便读一个服务器就好。

  • 服务器越多,写的时候投票数就越大,写速度就越慢。

  • 服务器都是基数台服务器部署,投票容易产生最大数。

Zab 协议

商用都是简化版的ZooKeeper协议 - Zab协议。更简单,性能更高。

当Leader宕机以后,会有一段时间没有响应,Follower中会重新选举一位Leader,投票给服务器id最大的服务器。

发布于: 2020 年 07 月 19 日 阅读数: 7
用户头像

John(易筋)

关注

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

架构师,前阿里巴巴资深无线开发,汇丰银行专家。擅长算法、数据结构、设计模式、iOS、Java、 Spring Boot、Spring Cloud、Docker

评论

发布
暂无评论
两个指针缩小范围算法,CQRS 命令查询职责分离模式 John 易筋 ARTS 打卡 Week 09