阅读

• 1: 技术
• 1.1: 架构师修炼之路
• 1.2: 深入理解Java虚拟机
• 1.3: 数据密集型应用系统设计
• 1.4: 微服务设计
• 2: 心理学
• 2.1: 这就是心理学
• 2.2: 敏捷思考
• 2.3: 思考，快与慢

1 - 技术

1.1 - 架构师修炼之路

软件架构导论

架构师

@startmindmap
+ 架构师
-- 技术
-- 用户
-- 业务
++ 从工程角度定义问题
++ 分解系统，分配职责
++ 关注大局
++ 在质量属性之间进行取舍
++ 管理技术债务
++ 提升团队架构能力
@endmindmap

架构

@startmindmap
+ 架构
++ 元素
+++ 模块 module
+++ 组件连接器 component & connector
+++ 分配 allocation
++ 关系：比如调用、订阅、管理、发布、返回、使用、依赖以及存储等等
@endmindmap

项目回顾

• 利益相关方是谁，主要业务目标是什么
• 项目的整体解决方案是什么样的
• 涉及到哪些技术
• 最大风险是什么，你是如何克服的
• 如果有机会重新做一遍，你会如何改进

设计思维 HART原则

1. 以人为本 human

设计的本质是社交

利益相关方关系图

2. 推迟决策 ambiguity

推迟不确定的决策

3. 善于借鉴 redesign

所有设计都是在已有设计基础上重新设计和调整创新

4. 化虚为实 tangibility

让想法具体化、有形化，以便于沟通交流

思维模式

@startmindmap
+ 思维模式
++ 理解问题
++ 探索想法
++ 展示想法
++ 评估适用性
@endmindmap

TDC循环

@startuml
node "思考 Think" as t
node "动手 Do" as d
node "检查 Check" as c
t -up-> d
d -> c
c -left-> t
@enduml

• 思考 Think：工程风险、业务目标、质量属性、权衡取舍
• 动手 Do：模型、原型、计划、备选方案
• 检查 Check：场景演练、方案比较、直接检验、理解核查

架构设计原理

架构设计时间的最佳平衡点

项目总工期 = 开发 + 架构设计 + 返工(弥补缺陷、重写代码、改正错误)

其中，随着架构设计时间的增加，返工量会逐步减少；存在一个最佳平衡点，使得项目总工期最小

• 千万行代码的大型软件系统，最佳平衡点取37%
• 一万行代码的小型软件系统，最佳平衡点取5%

关键架构需求 Architecturally Significant Requirement

约束：给定或选定的不可更改的设计决策，分为技术约束和业务约束

质量属性：外部可见特性，表征系统在特定环境下的运行情况

分为设计属性(可维护、可复用等)、运行属性(可用、性能、安全等)和感知属性(简单、指导等)

质量属性场景的六个元素：刺激、来源、软件部件、响应、响应度量和环境背景

@startuml
:来源: as source
note top of source : 刺激的来源\n可以是人或系统.
(软件部件) as software
(响应) as response
source -right-> software: 刺激\n(需要系统以某种方式做出响应的事件)
software -> response
note top of response : 响应度量\n\
定义响应成功的标准和条件\n必须是具体、明确和可衡量的.

@enduml

影响较大的功能需求：需要特别注意的特性和功能

其他影响因素：时间、知识、经验、技术、办公司政治等影响决策的东西

架构选择

决策矩阵 decision matrix

架构模式

针对特定问题的可复用解决方案。相比于设计模式，架构模式常涉及软件系统的多个组件，关注更宽泛的质量属性与抽象粒度

分层模式 Layers

层间低耦合，层内高内聚，提升可维护性。依赖上只有上层允许使用下层

端口适配器模式 Port and Adapters

使用输入源的可插拔适配器，以提供对事件和数据的访问，方便切换输入设备

管道过滤器 Pipe-and-Filter

松耦合的过滤器通过各种方式进行组合和复用，从而创建出新管道

面向服务架构模式 Service-Oriented Architecture

用独立的组件提供特定功能的服务，各种服务在运行时整合在一起，决定了系统的行为

发布订阅模式 Publish-Subscribe

生产者和消费者通过消息总线间接通信

共享数据模式 Shared-Data

多个组件通过共用的数据库访问数据

多层模式 Multi-Tier

系统运行时的结构被组织成逻辑组，逻辑组分配到特定的物理组件。Tier是组件连接器结构或分配结构，处理运行时元素，layer是模块结构，处理设计时元素

CSC迭代

创建 Create

提出设计想法(画图或建模)，5-7min

分享 Share

组内游说(pitch)，解释自己的设计如何满足目标，3-5min

评判 Critique

评判设计与目标的关系，指出好的方面和可以改进的方面

优秀的软件架构师

• 与团队一起选择架构模式和技术
• 设计文档模板，与团队一起起草和评审文档
• 共同决策，及时评审，提供反馈
• 帮组团队组织工作，划分任务
• 接受变化，让架构易于调整
• 让大家就技术决策达成共识

结对设计

设计下放

• 告知：由你做设计决策，然后告知团队结果
• 贯彻：由你做设计决策，然后向团队说明设计理由
• 咨询：在做设计决策前咨询团队的意见，最终仍由你决策
• 商定：与团队就设计决策达成共识，平等话语权
• 建议：通过观点、见解影响团队，但是由其他团队成员做设计决策
• 审查：由团队做决策，并且由他们说明设计理由
• 委托：委托另外一位成员做决策，由他负全责。你作为辅助，帮助团队收集信息

经验不足的团队，建议采用前三级权限

架构师工具

二选一 Choose One Thing

难以取舍时做决策(功能性需求应当进行公平评估)

移情图 Empathy Map

描绘利益相关方(比如客户，用户，维护人员)的任务，想法，感受，理解对方的目标

GQM研讨会 Goal-Question-Metric Workshop

目标-问题-指标讨论，用于确定质量属性的响应度量

架构决策记录 Architecture Decision Records

架构决策记录(ADR)

决策矩阵 Decision Matrix

1.2 - 深入理解Java虚拟机

1.3 - 数据密集型应用系统设计

数据系统基础

1. 可靠、可扩展和可维护的应用系统

可靠性 Reliability

发生硬软件故障、人为失误等意外情况，系统应可以继续正常运转：虽然性能可能有所降低，但确保功能正确

• 磁盘故障：对磁盘配合 RAID (独立硬盘冗余阵列)
• 人为失误：快速恢复如滚动更新，性能指标和错误率的监控

可扩展性 Scalability

随着数据量、流量或复杂性等规模的增长，系统应以合理的方式来匹配这种增长

• 吞吐量：每秒处理的记录条数，一般批处理系统更关系该指标
• 响应时间：对于一段时间内的响应时间数据，取平均值和各取样点相对于平均值的百分比，再用中位数等指标来衡量

可维护性 Maintainability

随着时间的推移，许多新的人员参与到系统开发和运维，以维护现有功能或适配新场景等，系统都应高效运转

• 可运维性：自动化运维
• 简单性：抽象设计
• 可演化性：敏捷开发

2. 数据模型与查询语言

文档模型与关系模型

MapReduce查询

PostgresSQL

select date_trunc('month', observation_timestamp) as observation_month,
sum(num_animals) as total_animals
from observations
where family = 'Sharks'
group by observation_month;

MongoDB

db.observations.mapReduce(
    function map() {
        var year = this.observationTimestamp.getFullYear()
        var month = this.observationTimestamp.getMonth() + 1;
        emit(year + ':' + month, this.numAnimals)
    },
    function reduce(key, values) {
        return Array.sum(values)
    },
    {
        query: {family: 'Sharks'},
        out: 'monthlySharkReport'
    }
)

db.observations.aggregate([
    {$match: {family: 'Sharks'}},
    {$group: {
        _id: {
            year: {$year: '$observationTimestamp'},
            month: {$month: 'observationTimestamp'}
        },
        totalAnimals: {$sum: '$numAnimals'}
    }},
])

属性图与Cypher查询

• 每个顶点包括：唯一的标识符、出入边的集合以及键值对属性的集合
• 每条边包括：唯一的标识符、头部和尾部顶点、描述两个顶点间的关系类型的标签以及键值对属性的集合

create table vertices (
    vertex_id integer primary key ,
    properties json
);

create table edges (
    edge_id integer primary key ,
    head_vertex integer references vertices(vertex_id),
    tail_vertex integer references vertices(vertex_id),
    label text,
    properties json   
);

Cypher

create
    (NAmerica:location {name: 'North America', type: 'continent'}),
    (USA:location {name: 'United States', type: 'country'}),
    (Idaho:location {name: 'Idaho', type: 'state'}),
    (Lucy:person {name: 'Lucy'}),
    
    (Idaho) -[:within]-> (USA) -[:within]-> (NAmerica)
    (Lucy) -[:born_in]-> (Idaho)

match
    (preson) -[:born_in]-> () -[:within*0..]-> (us:location {name: 'United States'}),
    (preson) -[:live_in]-> () -[:within*0..]-> (eu:location {name: 'Europe'})
return person.name

:within*0.. 沿着一条within边，遍历零次或多次

三元存储与SPARQL

三元组 (主语，谓语，宾语)

• 主语为顶点
• 宾语为值，则谓语为属性中的键值，此时表示顶点的属性键值对
• 宾语为顶点，则谓语为边

资源描述框架 RDF

全网数据交换通用格式

SPARQL

采用RDF数据模型的三元存储查询语言

prefix : <uln:exmpale>

select ?presonName where {
    ?preson :name ?presonName.
    ?preson :bornIn / :within* / :name "United States".
    ?preson :liveIn / :within* / :name "Europe".
}

3. 数据存储与检索

日志结构的最简单的数据库

追加式顺序写

#!/bin/bash

db_set() {
  echo "$1,$2" >> database
}

db_get() {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

SSTable 排序字符串表 Sorted Strings Table

储存有序不重复的键值对，只读文件，可以经过合并产生新的SSTable来减少总体的大小

LSM-Tree 日志结构合并树 Log-Structured Merge Tree

执行分级压缩

星型模式 维度建模

模式中心是一个事实表。事实表的每一行表示在特定时间发生的事件。事实表中的列包含属性和外键，这里外键引用的表称作维度表

数据立方体：由不同维度分组的聚合网格

列式存储

• 将每列中的所有值存储在一起
• 列压缩时，对于离散度低的列可以采用位图压缩

列存储格式：Parquet、Google的Dremel

4. 数据编码与演化

@startmindmap
* 编码格式
** 语言特定格式
*** Java的`java.io.Serializable`，Kryo
*** Python的`pickle`
*** Ruby的`Marshal`
** Json/XML与二进制变体
** Thrift
** Protocol Buffer
** Avro
@endmindmap

Avro

record Person {
    string username;
    union {null, long} favor = null;
    array<String> interests;
}

{
  "type": "record",
  "name": "Person",
  "fields": [
    {"name": "username", "type": "string"},
    {"name": "favor", "type": ["null", "long"], "default": "null"},
    {"name": "interests", "type": {"type": "array", "items": "string"}}
  ]
}

分布式数据系统

5. 数据复制

主从复制

主节点写入，从节点只读

@startmindmap
* 复制时机
** 同步复制：副本强一致性
** 半同步复制：配置部分副本为同步复制
** 全异步复制
@endmindmap

处理节点失效

• 新的从节点加入：在某个时间点对主节点的数据副本产生一个一致性快照，复制快照到新的从节点。从节点连接到主节点并请求快照点之后所发生的的数据更改日志
• 从节点失效：追赶式恢复
• 主节点失效：节点切换

复制日志

• 基于语句的复制：主节点记录每个写请求并将该操作语句作为日志发送给从节点。不适用的场景：非确定性函数、依赖执行顺序的语句以及有副作用的语句
• 预写日志WAL：记录哪些磁盘块的哪些字节发送了变化。主要缺点：和储存引擎耦合
• 基于行的逻辑日志的复制：行插入记录相关列的新值；行删除记录记录唯一标识或所有列的旧值；行更新记录唯一标识或所有列的旧值以及至少所有已更新列的新值。该技术也称为变更数据捕获
• 基于触发器的复制：触发器支持注册自己的应用层代码，使得当数据库系统发生数据更改(写事务)时自动执行上述自定义代码，进而将数据更改记录到一个单独的表中

复制滞后

写后读

同一用户能读到之前自己写入的数据

• 用户访问可能修改的内容，则从主节点读取
• 跟踪最近最新更新时间，最近更新过的数据从主节点读取；并监控从节点的滞后程度，避免从滞后的从节点读取
• 客户端记录最新更新时间，并附带在读请求中。系统可以确保对该用户提供读服务时都应该至少包含了该时间戳的更新。如果不够新，则转发给另一个副本来处理，或等待直至副本接收到了最近的更新
• 副本跨数据中心，则转发给主节点所在的数据中心

单调读

同一用户多次读取，只会读到更新的值而不会看到回滚的情况

• 同一用户总是从固定的同一副本执行读取

前缀一致读

对于一系列按照某种顺序发生的写请求，在读取这些内容时也会按照当时写入的顺序

多主节点复制

多个数据中心都配置一个主节点。可以提供写性能，容忍数据中心失效，但是需要处理写冲突

避免冲突

特定用户路由到特定的数据中心，数据中心切流或用户漫游到另一数据中心时，此方法失效

一致性收敛

确保所有的副本最终一致性

• 给每个写入分配唯一ID，挑选最高ID作为胜利者。如果基于时间戳，则称为最后写入者获胜 LWW Last Write Wins。这种方法容易丢失数据
• 给每个副本分配唯一ID，指定副本优先级写入，如序号高的副本写入优先。这种方法也容易丢失数据
• 以某种方法合并冲突值，如字符串拼接
• 利用预定义好的格式记录和保留冲突相关的所有信息，依靠应用层的逻辑，事后解决冲突

@startmindmap
* 冲突解决
**: 无冲突的复制数据类型 CRDT
Conflict-free Replicated Datatypes
可以由多个用户同时编辑的数据结构;
**: 可合并的持久数据结构
Mergeable Persistent Data
跟踪变更历史，并提出三向合并功能 three-way merge function
CRDT 为二向合并;
**: 操作转换 Oerational Transformation
专为可同时编辑的有序列表而设计;
@endmindmap

多节点模型的拓扑结构

@startuml
frame "环形拓扑" {
database a1
database b1
database c1
database d1
a1 -down-> b1
b1 -> c1
c1 -> d1
d1 -> a1
}

frame "星形拓扑" {
database a2
database b2
database c2
database d2
b2 -down-> a2
c2 -right-> a2
d2 -left-> a2
a2 -> b2
a2 -> c2
a2 -> d2
}

frame "全部-至-全部型拓扑" {
database a
database b
database c
database d
a -> b
b -> a
a -down-> c
c -up-> a
a -> d
d -> a
b -> c
c -> b
b -> d
d -> b
c -> d
d -> c
}
@enduml

无主节点复制

节点失效后的写

• 读修复：客户端并发读取多个副本，检测过期的返回值，然后将新值写入到过期的副本中。适用于被频繁读取的场景
• 反熵：后台进程查找副本之间的差异，将任何缺少的数据从一个副本复制到另一个副本。此反熵过程会有明细同步滞后的问题

Quorum 法定票数读/写

n个副本，写入需要w个节点确认，读取需要查询r个节点，则 w + r > n 可读取到最新值

常见设置 w = r = (n+1) / 2

宽松的冲裁 sloppy quorum：集群节点数量N > n，写入和读取的节点可以不是同一批n个副本所在的节点

版本矢量

所有副本的版本号集合称为版本矢量。当多个副本同时接受写入时，为每个副本和每个主键均定义一个版本号。每个副本在处理写入时增加自己的版本号，并跟踪从其他副本看到的版本号，进而指示要覆盖和要保留的并发值

6. 数据分区

基于关键字区间分区

为每个分区分配一段连续的关键字或关键字区间范围 缺点是某些访问模式会导致热点问题，如基于时间戳的分区，这时可以以时间戳以外的其他内容作为关键字的第一项

基于关键字哈希值分区

处理数据倾斜并使其均匀分布，比如 MD5、Fowler-Noll-Vo

对于少数关键字的热点读写的问题，一种可能的解决方案是：为关键字的头部或尾部附加随机串比如两位随机数，这样可以分散到100个不同分区，写入减轻了，但是读取需要从所有的100个分区读取并进行合并；此外需要额外的元数据来标记哪些关键字进行了上述处理

基于文档分区的二级索引

在每个分区上维护当前分区数据的一个二级索引。这样读取的时候仍需要从所有的分区中读取并进行合并

基于词条分区的二级索引

全局维护所有数据的一个二级索引，并将该索引进行分区。这样读取只需要读特定分区，但是写入会写入多个分区

分区再平衡

• 固定数量分区：创建远超实际节点数的分区数，为每个节点分配多个分区。添加新节点时，可以从每个现有节点匀走部分分区，直至再平衡
• 动态分区：当分区数据增长超过一个可配的参数阈值时，拆分分区。数据缩减，则合并分区
• 按节点比例分区：每个节点有固定分区数，即分区数与集群节点数成正比。数据集大小不变，则节点数增加时，分区会调整变得更小：数据集大小 = 节点数 * 分区大小。新节点加入，随机选择固定数量的现有分区进行分裂，并拿到这些分区的一半数量。此算法要求采用基于哈希分区

7. 事务

ACID的含义

事务所提供的安全保证即：原子性 Atomicity、一致性 Consistency、隔离性 Isolation、持久性 Durability

原子性 Atomicity

在出错时中止事务，并将部分完成的写入全部丢弃

一致性 Consistency

对数据有特定的预期状态，任何数据更改必须满足这些状态约束或恒等条件。本质要求应用层来维护状态一致，非数据库本身的属性

隔离性 Isolation

并发执行的多个事务相互隔离，即可串行化

持久性 Durability

事务一旦提交成功，事务所写入的数据不会丢失。写入非易失性存储设备即可，比如磁盘或SSD

读-提交 Read-Committed

读时只能看到已成功提交的数据(防止脏读)；写时只能会覆盖已成功提交的数据(防止脏写)

脏写

• 行级锁：一个事务在修改该行的时候，以独占锁的方法持有，直至事务结束才释放

脏读

• 读锁：独占锁
• 多版本并发控制 MVCC：对于每个待更新的对象，都会维护其旧值和所有事务设置的新值，在事务提交之前所有操作都读取旧值，仅当事务提交之后，才会切换到读取新值

快照级别隔离与可重复读 Repeatable-Read

读时只能看到事务开始之前提交的数据(防止不可重复读/读倾斜)

一般采用 多版本并发控制 MVCC 来实现快照级别隔离。当事务开始时，首先赋予一个唯一单调递增的事务ID，每当事务写入数据时，所写数据都会被标记写入者的事务ID

更新丢失

并发的读-修改-写操作序列，出现了其中一个覆盖另一个的写入

• 原子写操作: update ... set v = v + 1 ...
• 显示加锁：select ... for update

串行化 Serializable

写倾斜：并发事务的写入改变了事务的写入，广义的更新丢失，可以发生在不同记录

幻读：一个事务的写入改变了另一个事务查询的结果

实际串行执行

在一个线程上按顺序逐一执行。适用场景：事务简短高效，活动数据集可以完全加载到内存，写入吞吐量足够低，且几乎无跨分区事务

两阶段加锁 2PL

被其他正在运行的事务读取过的对象，写入时需要等待该事务结束；被其他正在运行的事务修改过的对象，读取时同样需要等待该事务结束

读写锁的2PL实现：

• 读取对象，先获取共享锁，若已被其他事务获取了独占锁，则必须等待
• 修改对象，先获取独占锁，若已被其他事务获取了共享或独占锁，则必须等待
• 若首先读取对象，然后尝试写入对象，则需要将共享锁升级为独占锁，此时等同于需要竞争独占锁
• 事务获取锁之后，一直持有直至事务结束

出现的死锁需要自动检测，并强行中止其中的一个以大破僵局

谓词锁与索引区间锁 next-key locking

谓词锁：读取时，使用共享锁锁定满足where条件的所有行数据。

索引区间锁：扩大锁定范围，锁定一个区间或者整张表

可串行化的快照隔离 Serializable Snapshot Isolation, SSI

乐观并发算法，如果可能发生潜在冲突，事务也继续执行，直至事务提交之前，进行冲突检查

• 检测是否读取了过期的MVCC对象
• 检查写入是否影响了之前的读

8. 分布式系统的挑战

不可靠的网络

超时检测

• 网络阻塞与排队：TCP流量控制、网络交换机阻塞或丢包，CPU满载，虚拟机管理器切换

不可靠的时钟

墙上时钟

比如Linux的 clock_gettime(CLOCK_REALTIME) 或Java的 System.currentTimeMillis()。返回当前时间，可以与NTP进行网络同步。高精度(比如100us)可以采用GPS接收机和PTP(精确时间协议)

• 计算机中的石英钟可能发生时钟漂移(运行速度加快或减慢)，漂移主要取决于机器温度。谷歌假设其服务器漂移为200ppm(ppm为百万分之一)，即30s的误差为6ms
• 与NTP时间差别过大时，可能会拒绝同步或被强制重置
• 与NTP服务器连接失败或延迟(可能至少产生35ms的偏差)
• NTP服务器故障
• 闰秒会产生一分钟59秒或61秒的现象
• 虚拟机数十毫秒的暂停切换导致的时钟跳跃
• 在未完全可控的设备如移动或嵌入式设备，用户设置的硬件时间

单调时钟

比如Linux的 clock_gettime(CLOCK_MONOTONIC) 或Java的 System.nanoTime()。保证返回的时间总是向前而不会往后拨，更适合测量持续时间段

时钟的置信区间

Google Spanner 的TrueTime API 会明确报告本地时钟的置信区间，即[不早于，不晚于]，该范围主要取决于本地时钟与高精度时钟源同步后经历的时间间隔。可以在每个数据中心部署一个GPS接收器或原子钟，保证所有时钟同步在约7ms之内完成。

Spanner确定事件因果关系的方法：观察两个事件A和B，如果A的置信区间与B没有重叠且早于B，则可以断定B一定发送在A之后；如果重叠了，则等待置信区间的长度

9. 一致性与共识

可线性化

现已证明：如果想要满足线性化，那么读写请求的响应时间至少要与网络中延迟成正比

可线性化是读写寄存器(单个对象)的最新值的保证，也称为原子一致性，强一致性。不要求将操作组合到事务中，因此无法避免写倾斜等问题。同时支持可串行化时，称为严格的可串行化，或强的单副本可串行化，实际串行化和2PL都是可线性化

需要可线性化的场景：

• 加锁与主节点选举
• 约束与唯一性保证：唯一性本质上和加锁类似
• 跨通道的时间依赖：比如可线性化的文件存储服务

复制方案下的线性化

• 主从复制：从主节点或同步更新的从节点读，则可以满足线性化；快照隔离和脑裂的主节点不满足
• 共识算法；可线性化，实现系统比如Zookeeper, etcd
• 多主复制：不可线性化
• 无主复制：可能不可线性化，在网络延迟下会发生读旧值情况。使用同步执行读修复可以满足线性化读和写操作，但是不支持线性化比较和设置操作

CAP理论

不要求线性化的应用更能容忍网络故障

• 要求线性化，但是由于网络问题，某些副本与其他副本断开连接后无法继续处理请求，必须等待网络修复或直接返回错误，导致服务不可用
• 不要求线性化，出现网络问题时，每个副本可以独立处理请求，此时服务可用，但是不符合线性化

CAP也可以描述为：在网络分区情况下，选择一致性还是可用

因果一致性

因果关系定义系统中的因果顺序，即某件事应该发生在另一件事之前。因果一致性可以认为是，不会由于网络延迟而显著影响性能，又能对网络故障容错的最强的一致性模型。

全序和偏序

• 可线性化：存在全序关系(支持任何两个元素之间的比较)。系统行为就好像只有一个副本，且每个操作都是原子的
• 因果关系：至少是偏序关系。如果两个事件都没有发生在对方之前，那么就是并发关系。如果两个事件是因果关系(一个发生在另一个之前)，则可排序。可线性化强于因果关系

兰伯特时间戳 Lamport timestamp 可以产生与因果关系一致的序列号。用于确保全序关系

首先每个节点有一个唯一ID和一个计数器记录各自已处理的请求总数。Lamport时间戳为键值对 计数器值，节点ID 。节点和客户端追踪最大的计数器值，并在请求上附带该值，如果收到的请求中的计数器值大于自身的计数器值，则把自身的计数器值修改为该最大值

全序关系广播(原子广播)

• 可靠发送：没有消息丢失。如果消息发送到了某一个节点，则它一定要发送到所有节点
• 严格有序：消息总是以相同的顺序发送给每个节点

全序关系广播算法必须保证上述两条，当网络中断时，要继续重试，直至网路修复，消息发送成功

状态机复制：每个副本都按相同的顺序处理写请求，那么所有副本都可以保持一致

全序关系广播可用于实现可串行化事务，采用实际串行执行。

采用全序关系广播实现线性化存储

• 线性化的原子比较-设置操作：用户名唯一性约束，在日志追加一条消息，指明要插入的用户名；读取日志，将其广播给所有节点，并等待回复；检查是否有任何消息声明该用户名已被使用，有其他节点响应则中止操作
• 线性化读取
  • 广播读请求，进行quonum读
  • 获取消息在当前最新日志中消息的位置，查询位置等待直至该位置之前的条目都已接收，然后再读取，类似于zookeeper的sync
  • 从同步更新的副本读取

采用线性化存储实现全序关系广播

对于每个通过全序关系广播的消息，原子递增并读取该线性化的计数，作为序列号附加在消息上，而接收者也严格按照序列号来发送回复消息

原子提交与两阶段提交

原子提交：所有节点必须对跨节点或跨分区事务的结果达成一致，要么全部成功提交，要么中止或回滚

两阶段提交 Two-Phase Commit (阻塞式原子提交协议)

• 准备阶段：协调者(事务管理器)发送一个准备请求给所有节点，询问是否可以提交，参与者回复是/否
• 确认阶段：根据参与者的回复，协调者发送确认提交/确认回滚的请求给所有节点

事务开始时，协调者提供一个全局事务ID，日志持久记录，并返回给应用程序；协调者发送准备请求时，有任一请求失败，即通知所有节点放弃事务；参与者回复协调者之前，持久化变更，记录回复答案；协调者发送确认请求之前，持久化最终决定；协调者需一直重试确认请求，直至所有节点都成功响应为止

共识

• 协商一致性：所有节点都接受相同的决议
• 诚实性：所有节点不能反悔，即对一项提议不能有两次决定
• 合法性：如果决定了值v，则v一定是由某个节点所提议的
• 可终止性：节点如果不崩溃，则最终一定可以达成决议(强调容错，属于活性问题，其他三种属于安全性问题)

@startmindmap
* 容错式共识算法
** VSR
** Paxos
** Raft
** Zab
@endmindmap

全序关系广播相当于多轮共识

• 协商一致性：所有节点以相同顺序发送相同消息
• 诚实性：消息不能重复
• 合法性：消息不会损坏，也不会凭空捏造
• 可终止性：消息不会丢失

派生数据

10. 批处理系统

数据系统

• 在线系统：等待用户请求或指令的到达，当收到请求或指令后，服务试图尽可能快地处理它，并发回响应 响应时间通常是服务性能的主要衡量指标，而可用性同样非常重要
• 批处理系统(离线系统)：接收大量的输入数据，运行一个作业来处理数据，并产生输出数据。批处理作业的主要性能衡量指标是吞吐量
• 流处理系统(近实时系统)：处理输入并产生输出，但是是在事件发生后不久即对事件进行处理

使用Unix工具进行批处理

访问次数最多的五个URL

# sort -r -n 按照数字反向排序
cat /var/log/nginx/access.log |
  awk '{print $7}' |
  sort             |
  uniq -c          |
  sort -r -n       |
  head -n 5

counts = Hash.new(0)
File.opne('/var/log/nginx/access.log') do |file|
    file.each do |line|
        url = line.split[6]
        counts[url] += 1
    end
end
top5 = counts.map{|url, count| [count, url]}.sort.reverse[0..5]
top5.each{|count, url| puts "#{count} #{url}"}

MapReduce的Join与分组

排序-合并join

一种reduce端join，通过关键字对mapper的输出进行分区，然后对键值对进行排序，最后reducer将两侧排好序的记录列表合并在一起

广播哈希join

一种map端join，将小数据集全部加载到内存或保存至磁盘的只读索引(可以驻留在操作系统的页面缓存上)，每个分区的mapper都对于每条大数据集中的数据，都去小数据集中查找并合并

分区哈希join

一种map端join，两个join的输入具有相同数量的分区，则可以根据相同的关键字和哈希函数，将记录分配到相同分区，并在各自分区上进行合并

超越MapReduce

MapReduce将中间状态实体化，即写入到HDFS,可以容错，但是会造成延迟放大(必须等到中间状态全部输出之后下一个子任务才开始运行)，数据冗余和IO过多

@startmindmap
* 高级编程模型
** Pig
** Hive
** Cascading
** Crunch
@endmindmap

@startmindmap
* 数据流引擎
** Spark
** Flink
** Tez
@endmindmap

图与迭代处理

Pregel处理模型

@startmindmap
* Pregel处理模型
** Apache Giraph
** Spark的GraphX API
** Flink的Gelly API
@endmindmap

计算的批量同步并发模型，源自Google的Pregel论文

11. 流处理系统

消息系统

消息代理(消息队列)，本质是一种针对处理消息流而优化的数据库

@startmindmap
+ 消息代理
++ RabbitMQ
++ ActiveMQ
++ HornetQ
++ Qpid
++ Google Cloud Pub/Sub
-- JMS
-- AMQP
@endmindmap

消息传递模式

• 负载均衡式：每条消息传递给一个消费者，即共享订阅
• 扇出式：每条消息传递给所有的消费者，即主题订阅/交换绑定

基于日志的消息存储

Apache Kafka

对日志进行分区，然后将主题定义为多组分区，为每个消息分配一个单调递增的偏移量

数据库与流

变更数据捕获 Change Data Capture, CDC

读取数据库日志变更记录，比如MongoDB的oplog、MySQL的binlog

事件溯源

将所有对应用程序状态的更改保存为更改事件的日志，类似于编年史数据模型

流处理

复杂时间处理 CEP

Esper, Apama, SQLstream, TIBCO StreamBase

指定规则，在流中搜索特定模式的事件

流分析

Storm, Spark Streaming, Flink, Concord, Samza, Kafka Streams, Google Cloud Dataflow, Azure Stream Analytics

维护物化视图

流式join

流流join(窗口join)

维护窗口期的状态，对于每个事件，检查另一事件源的数据是否已到达

流表join

对于每个事件，在数据库中查找需要join的数据

表表join(物化视图维护)

缓存join，每当底层表发生变更时进行更新

1.4 - 微服务设计

微服务

微服务的定义

协同工作的小而自治的服务

1. 代码量和功能集足够小

高内聚，低耦合：因相同原因而变化的东西聚合在一起，而把因不同原因而变化的东西分离开来

2. 自治性

可独立部署，可独立修改，使用API进行通信

微服务的优点

1. 技术异构

2. 弹性

3. 扩展

4. 简化部署

可以更快对特定的代码进行部署

5. 匹配组织架构

避免过大的代码库

6. 可组合

7. 提升可替代性

方便删除或重写服务

2 - 心理学

2.1 - 这就是心理学

科学方法

• 科学采用系统的实证主义方法

• 以获取可公开验证为目标

  可重复性 同行评审

• 寻求可实证解决的问题并进而发展出可验证的理论

可证伪性标准：从科学理论中得出的预测都有可能被证明是错误的

操作主义

与本质主义相反，科学理论的概念必须以某种方式建立在可观察事件的基础之上，或与之相关联，而这些可观察事件是可以被测量的

• 信度

测量工具的一致性，对同一概念的多次测量，得到一致的测量结果

• 效度

测量工具测量了本应测量的内容

安慰剂效应

无论一种治疗方法是否有真正的治疗成分，人民都倾向于报告治疗对他们有帮助

如果在一组病人身上测试新药，就要组建一个患有相同病症的对照组，给他们服用不含该药的药剂，两组都不知道自己是哪一组

鲜活性效应

当面临问题解决或决策情境时，人们会从记忆提取与当前情境有关的信息。即人们倾向于利用更容易获取的鲜活的信息

心理加工

作为认知吝啬者，在处理问题时，使用最不费力的心的I型加工

• I型加工

先天思维，显著受到个案研究和见证叙述的影响

• II型加工

科学和统计思维

巴纳姆效应

绝大数人会认为泛化的个性总结是对自己准确而独特的描述

选择效应：自我选择偏差

主动选择进入一个特定的群体而不是随机分配

• 临床医生的错觉

临床医生倾向于将他们看到的极端病例的特征过度推广到人数多得多的轻微患者中，而临床医生较少接触到轻微患者

• 随机分配

将被试分配到实验组和控制组，且每个被试被分配到其中一组的概率相同

随机取样是指如何选择被试进行研究，要确保总体中的每一个成员都有同等机会被选为样本，被抽中的样本便成为研究的被试

随机分配是真实验的必要条件，如果没有使用随机分配则是相关研究

聚合性证据原则

得出结论之前，将多个研究综合起来，评估它们是否具有聚合性，即一致支持某个理论，而又共同地排除了最重要的竞争解释

元分析

把针对同一假设所进行的多项研究的结果，在统计学上进行整合。用一个通用的统计指标，来表示两个实验组比较时得到的效应。然后对不同研究的效应进行比较，再用一些标准方法对结果进行统计学上的合并。如果合并过程通过了一定的统计标准时，就得到了一个关于效应量的结论

赌徒谬误

人们倾向于将过去的事件和未来的事件联系起来，而实际上两者是独立的

相关错觉

当人们相信两类事件通常应该在一起发生时，会认为两类事件同时发生的频率很高

控制错觉

人们倾向于相信个人能力可以影响偶然事件的结果

接收错误以减少错误

为了减少总体的错误，接收小概率事件预测的失败。即，依靠一般性原则来做出比较准确的预测，同时承认不可能在每件具体事件上都预测准确

• 临床预测

即个案预测，对特定的个体所做的预测

• 统计预测

依据从统计资料中得到的群体趋势所做的预测，统计预测优于临床预测

2.2 - 敏捷思考

@startmindmap

* 就业的十条技巧
**: 沟通
口头和书面的沟通技巧，能够清除准确表述自己的想法;
**: 数字推理
算术演算，能够解释和使用数据;
**: 逻辑推理
能够连贯一致地推理;
**: 概念思考
能够分析概念和观点，能够把想法整合为概念，创造新概念;
**: 团队合作
能够有效地与他人协作;
**: 计划和组织
能够分析任务，制定有效计划，并付诸实施;
**: 创新思考和解决问题
能够分析问题，收集信息，创造性地使用信息;
**: 领导力
能够组建高效的团队，激发成员的斗志;
**: 灵活性
能够根据实际情况转换思想，改变工作方式，不受想法局限;
**: 主动性、自我激励和自觉意识强
具有主动性，能够激励自己跟上新想法，找到新的解决方法，能够自我反思，即找到自己的弱点和可以自我提高;
@endmindmap

@startmindmap
* 敏捷思考者具备的认知技巧和能力
** 能够适应特殊情况
** 能够抓住机遇
** 能够在混乱中找到秩序
** 能够正确地处理新信息
** 能够跨越学科的限制，找到相似性
** 产生的新想法数量更多，速度更快，绝不拾人牙慧
** 能够分析概念，创造新概念，能够变具体为抽象，也能在特殊性中找出一般性
** 能够用原创方法整合迥然不同的想法，从不同的视角看待问题
@endmindmap

2.3 - 思考，快与慢

序言

办公室饮水机旁的闲谈

可得性法则：依靠记忆作出判断

系统1和系统2

无意识运作的系统1

通过联想记忆不断地对世界所发生的的事作出连贯性解释

自主发生且毫不费力

视觉错觉和认知错觉

系统1产生的成见，可以由系统2识别。在风险很高的决策场景，尽力避免这些错误

受控制运作的系统2

脑力工作，需要刻意，努力并且有序进行。需要集中注意力，如若注意力分散，运作也会随之中断

系统1不断为系统2提供印象，直觉，意向，感觉等信息。如果系统2接收了这些信息，则会将印象，直觉等转变为信念，将冲动转化为自主行为

看不见的大猩猩

观看一部两队分别穿黑色和白色球衣的篮球队的比赛视频，并数出白队的传球次数，中途有一个套着大猩猩服装的女人穿过球场，这个大猩猩出现了足足9秒。但是最终有一半人未察觉到那只猩猩

当人们太过关注某件事时，就会屏蔽掉其他事情，即使平时很感兴趣也不例外

瞳孔-大脑运转情况的灵敏指示器

在解决费脑问题时会扩散，并且问题越难，扩散得越大。最大扩散50%，心跳+7，超过此极限，就会自动放弃，此时瞳孔就会停止扩散或收缩

四位数逐位加一和加三

惰性思维与延迟满足

惰性思考和做不到延迟满足的人：系统2的监测功能往往较弱

自我控制需要集中注意力，需要付出努力，即需要用到系统2

心流

将大脑注意力毫不费力地集中起来的状态

可以使人忘却时间的概念，忘掉自己，也忘掉自身问题

自我损耗 ego depletion

自我控制(也包括其他活动如审慎的选择，主动性行为等)，在短期内只能进行有限次，消耗后就会很不情愿或根本无法进行自我控制。自我损耗的影响可以通过注射葡萄糖得到缓解

实验：抑制自己的感情去看一部感情共鸣的电影，然后做耐力测试，会表现很差

理性和反思性思维

系统2的两个部分智力和理性

算法思维：负责要求很高的计算活动，智力体现 理性思维：相较于算法思维，理性思维可以消除成见

连贯性联想

联想激活

事物在大脑中唤起的想法激发出许多其他的连贯性的想法，其中每个环节都是紧密相连，相互支持的，形成一种认知、情感和生理反应的自我强化模式

启动效应

由于之前受某一刺激的影响而使得之后对同一刺激的知觉和加工变得容易的记忆现象

John Bargh实验：从单词中组句，组句有一半都含有老年相关词汇的的小组，在紧接着走路时步速会变慢，反之亦然，即先慢慢走路，然后能更快辨识老年相关词汇

关于钱会滋生个人主义的实验：在桌子上放仿制纸币或美钞壁纸的环境下，要求解决问题。脑海有钱这一概念的小组，会更独立，实在迫不得已才会向研究人员求租，表明其自力更生能力的提升；也会更自私，不愿花时间帮助另外一位假装不会做的学生，研究人员的铅笔掉地上，也更少帮忙捡起，帮过一会儿要交谈的对象摆放椅子时，也会摆放得远一点

有可能只是错觉的直觉

认知放松度

认知紧张：存在某种问题需要不断调度系统2参与其中。认知紧张更有可能激发系统2来抑制系统1的直觉性答案

@startmindmap
+ 放松
-- 反复的体验
-- 清楚的示范
-- 预知的想法
-- 好心情
++ 熟悉
++ 真实
++ 良好
++ 不费力
@endmindmap

曝光效应 Mere Exposure Effect

个体接触一个刺激的次数越频繁，个体对该刺激就越喜欢

一个刺激的的重复曝光并没有产生不好的影响，这样的刺激最终变成安全的信号，即能使机体鉴别出安全的物品和栖息地

远隔联想测验 Remote Association Test

创新是极佳的联想记忆。好心情，直觉，创造力、轻信以及对系统1不断增强的依赖性形成了一个关联群集。悲伤、警觉、怀疑、分析方法以及不断增强的努力程度等因素之间也是相互联系的

实验：给三个词在15s内想出与之都有关的词，以及2s内判断两个词是否有关联

意料之外与情理之中

因果性直觉

人们总是很不恰当地将因果性思考用于需要统计论证的情景中。统计性思维总是根据事物的不同类别和总体性质得出个案的结论。系统1并不具备这样的推理能力，而系统2通过学习可以进行统计性思考

直觉的一致性

光环效应 Halo Effect

在人际知觉中所形成的以点概面或以偏概全的主观印象。光环效应注重第一印象

Solomon Asch 所罗门阿希实验：要求对两个人的个性进行描述，艾伦 聪明-勤奋-冲动--爱挑剔-固执-忌妒心强，本 忌妒心强-固执-爱挑剔--冲动-勤奋-聪明

群体的智慧 The Wisdom of Crowds

一群没有系统性偏见的相互独立的观察者作出的判断进行平均之后得到的平均值会趋近于准确值

独立判断原则和解除错误关联，可以直接应用于群体会议

眼见即为事实 What you see is all there is

系统1基本上对引起印象和直觉的信息的质量和数量都不敏感。信息的前后一致性胜于其完整性

直觉性判断

系统1通过原型或一组典型事例来代表不同事物分类

系统1更容易比较两个物品的长宽高和估计平均值，以及强度等级匹配，而需要调度系统2来算总数总长

思维的发散性：系统1任何时候都可以同时进行多种估算，其中有些估算是持续不间断的常规评估。大脑会对视觉范围内呈现出的立体事物进行评估，对形状、空间位置和特性等因素的全方位评价

启发性问题

用简单问题替代复杂问题来作出判断

启发式问题：绕开原来的目标问题去回答的那个更简单的问题

立体启发式

立体大小替代平面大小是自主发生的：走廊内的人左侧的是否比右侧的高

情感启发式

因为喜欢，所以认同

启发法和偏见

大数法则与小数定律

系统1可以自动且毫不费力地识别事物之间的因果关系，即使有时这种关系根本不存在

统计学事实：

• 大样本比小样本更精确(小样本出错风险可能高达50%)
• 小样本比大样本产生极端结果的概率大

信任多于质疑的普遍性偏见

系统1不擅于质疑

对随机事件作出因果解释

对偶发事件作出因果关系的解释必然是错误的

锚定效应 Anchoring Effect

是指当人们需要对某个事件做定量估测时，会将某些特定数值作为起始值，起始值像锚一样制约着估测值。在做的时候，会不自觉地给予最初获得的的重视

幸运轮盘实验：转轮盘，停下后只停留在10或65，紧接着问联合国非洲国家的比例，转到大数的人回答的比例的平均值比小数的要大

对锚定值的调整常常是不足的：从锚定值开始，估测过高还是过低，接着开始调整，并且调整通常会过早结束

暗示是一种锚定效应

一种启动效应，会有选择地找到相应的证据

锚定指数

两组锚定值分别为y1和y2，受试者给出的平均评估分别是x1和x2，则锚定指数为 (x1-x2) / (y1-y2)

现实世界上锚定指数50%比较常见

可得性启发法

跟着系统1走的人更容易受可得性偏见的影响

某件事发生频率的印象是如何受到列举实例的具体数目这一要求的影响的

• 能回想起的事例数量
• 事件在脑中呈现的轻松程度

列举果断事例的实验

• 列举6个果断事例：果断
• 列举6个不果断事例：不果断
• 列举12个果断事例：不果断
• 列举12个不果断事例：果断