ARTS 第二十一周（2019.8.19~2019.8.25）

[catcuts]

ARTS 第二十一周（2019.8.19~2019.8.25）

• Algorithm 合并两个有序链表
• Review 基于事件模式构建的渐进式系统架构
• Tip 在并发处理中为异步操作加锁
• Share [极客专栏] 22 | 从亚马逊的实践，谈分布式系统的难点

Algorithm 合并两个有序链表

题目：

合并两个有序链表

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if (!l1 || !l2) return l1 || l2;
    let lh = { val: -Infinity, next: l1 }, p1 = lh, p2 = l2;
    while (true) {
        // 链表 2 已无节点可并入链表 1，则停止合并
        if (!p2) break;
        // 链表 1 已经遍历到尾部，则与链表 2 当前节点直接连接并停止合并
        if (!p1.next) {
            p1.next = p2;
            break;
        }
        // 链表 1 的下一个节点值小于链表 2 当前节点值，则不合并
        // 链表 1 指针跳到下一个节点，链表 2 的指针不变
        if (p1.next.val < p2.val) {
            p1 = p1.next;
        }
        // 链表 1 的下一个节点值大于链表 2 当前节点值，则合并
        // 合并方式：把链表 2 当前节点插入到链表 1 的当前节点和下一个节点之间
        else {
            let p1Next = p1.next;
            p1.next = p2;
            p1 = p2;
            let p2Next = p2.next;
            p2.next = p1Next;
            p2 = p2Next;
        }
    }
    return lh.next;
};

思路：
思路见注释。
一次迭代/递归，故时间复杂度 = O(n1 + n2)；
不占用额外空间，故空间复杂度 = O(1)。

对比：
与高分对比：
本代码运行 208 个测试用例花费约 92ms，平均一个测试用例约 0.44ms；
高分代码运行 208 个测试用例花费约 92ms，平均一个测试用例约 0.44ms。

最高分使用递归，代码如下：（简洁）

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if (l1 == null) {
        return l2;
    }
    else if (l2 == null) {
        return l1;
    }
    else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }
    else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

Review 基于事件模式构建的渐进式系统架构

阅读：
Using Events to build evolutionary architectures

点评：
何为事件：由系统中某个模块发出的、携带一定数据的、可以被订阅的消息。
举例：

• 系统中的订单模块发出的带有订单数据的 “订单确认” 事件
• 系统中的订单模块发出的带有订单数据的 “订单取消” 事件

事件与消息的区别：

• 事件发出无目标（广播），消息发出有目标（点对点）
• 通过事件串联起来的模块之间无耦合，无需定义接口；消息反之
• 事件是异步的，消息可以是异步的也可以是同步的

基于事件的系统架构特点：

• 包含一个事件消息调度中心
• 低耦合，模块之间或发布者和订阅者之间只需事先知道很少彼此信息
• 可变工作流，指事件发出后引发的一连串反应并不是唯一的，这意味着不可重放
  注：这种特点也被称作 orchestration style

基于消息的系统架构特点：

• 相对高耦合，模块之间需事先协商好接口
• 不可变工作流，由各种消息串联起来的工作流程是唯一的，这意味着可重放
• 相对高可控性，包括：消息确认、应答、重发、错误处理等
  注：这种特点也被称作 choreography style

因此可以说，基于事件的系统架构是一种 OCP 实现
OCP = Open-Closed Principle
= open to extension but closed to change
= 于不变中演进的思想（对变化关闭，对演进/扩展开放）

为什么：因为低耦合，扩展基于事件的系统中的一个模块，不会造成其它模块的变化

最后要注意：事件模式并非灵丹妙药，
正如它的特点所反映的，它缺少消息模式的不可变工作流和高可控的特性，
这使得它在系可靠性和可维护性上逊色于消息模式

实践中应权衡利弊，两害相权取其轻，或者二者相合取长补短。

扩展阅读：

• google-search: orchestration and choreography workflow events message
• Orchestration vs. Choreography
• The Microservices Workflow Automation Cheat Sheet
• Event-Driven Orchestration: Effective Microservices Integration Using BPMN and AMQP

Tip 在并发处理中为异步操作加锁

基于异步 I/O 的单线程程序在处理并发请求时，数据是线程安全的，但却不是异步安全的。

线程安全的：多线程对数据的访问和修改是有序的

异步安全的：多协程对数据的访问和修改是有序的

例如：并发异步对 redis 数据的访问

async function 异步对Redis数据的访问并设置() {
    let value = await redis.get('key');
    console.log(value);
    await redis.set('key', value * 2);
}
// 模拟并发
Promise.all([
    异步对Redis数据的访问并设置(),
    异步对Redis数据的访问并设置()
])

结果是打印两个相同的 value
因为协程并发，造成数据的获取和修改不可知

因此，在必要的情况下，需要对异步操作进行加锁，可使用 async-lock

一个可直接运行观察结果的使用示例：

const AsyncLock = require('async-lock');
const lock = new AsyncLock();

var value = 1;

async function getVal() {
    return await new Promise((resolve, reject) => {
        resolve(value);
    });
}

function setVal(val) {
    value = val;
}

async function noLock(key, func) {
    return await func();
}

// Promise mode
async function test({ withLock }) {
    if (withLock) {
        return await lock.acquire('key', async function () {
            console.log('meow ...');
            // return value or promise
            let val = await getVal();
            setVal(val * 2);
            console.log(value);
            return val;
        });
    } else {
        return await noLock('key', async function () {
            console.log('meow ...');
            // return value or promise
            let val = await getVal();
            setVal(val * 2);
            console.log(value);
            return val;
        });
    }
}

// 测试
(async () => {
    console.log('加锁异步并发：')
    await Promise.all([ test({ withLock: true }), test({ withLock: true }) ]);
    value = 1;  // 复原
    console.log('无锁异步并发：')
    await Promise.all([ test({ withLock: false }), test({ withLock: false }) ]);
})();

Share [极客专栏] 22 | 从亚马逊的实践，谈分布式系统的难点

分享一篇极客“左耳听风”专栏文章（据说可限10位免费阅读哦）
22 | 从亚马逊的实践，谈分布式系统的难点