95702-Review

DS 期末复习

作者 QIFAN 日期 2016-12-12
95702-Review

Lectures

Chapter 1 Introduction

Characterization of Distributed Systems

  • 同步性:程序在不同节点同时运行。两个节点间的活动互不影响。
  • 异时性:不同节点的时间不统一
  • 独立失败:一个节点的失败与其他节点隔离,一个程序的崩溃可能并不能被其他节点发觉

Four Styles of Application Intergration

  • 分享文件
  • 分享数据库
  • 远程调用(RPC / RMI)
  • 通过第三方

Synchronous and Asynchronous Communication

同步:客户端发出以后啥也不干了,就等着了
非同步:自由的灵魂不浪费时间,客户端发出请求接着干别的事

Communication Paradigms: Interprocess Communications, Remote Invocation, Indirect Communication

Time and Space Coupling

Layered Architecture

Tiered Architecture

通常在应用层分层。client-server 就是一种典型的分层咯

Software Engineering Principle: Separation of Concerns

这是 tired 的原因吧

Architectural Patterns: Proxy Pattern, Brokerage Pattern

service provider, service requestor and service broker

Challenges in Constructing Distributed Systems

  • 多样性
    不同的节点使用不同的编程语言,或者使用不同的字符和数据结构的表示方式。
  • 开放性
    一个系统的开放性决定了这个系统能不能用多种方式进行扩展和重现。
  • 安全性
    信息资源安全的三个要素:保密性(保护不被未受认证个体取得),整体性(保护不分裂),可利用性(避免干扰)
  • 延展性
    如果在增加大量资源和用户的情况下,系统的效率仍能保持不变,则认为这个系统的是可延展的。
  • 失败处理
    通常有两种处理方式:
    • 监测失败。
    • 覆盖失败。将失败掩盖或者使它不那么剧烈。比如重新发送信息和备份资源。
    • 忍受失败
    • 从失败恢复
    • 冗余

Chapter 2 System Models

Architectural Models

Fundamentals Models

Agreement in Pepperland

将交流双方的 latency 控制在 (max - min + 1)内。
A 和 B 准备一起打 C ,但是 A B 隔太远,又没有电话,只能靠人马。就约定好,A 发出攻击指令后,等待 MIN ,然后就出发;而 B 收到攻击指令后,等待 1 秒后出发。

Failure Detection in Pepperland

双方无法同时知道交流失败了。

JEE

  • Servlets
  • JSP / Java Server Pages
  • Model View Controller

WWW

  • HTTP Protocol, including request and response headers
    request 头部一般是:
    • method:GET / PUT / DELETE / HEAD / POST 等等
    • Resource Identifier:目标 url 是啥
    • Http 版本:HTTP / 1.1
    • host,user-agent,accept
      response 头部是:
    • HTTP 版本
    • 状态:200 OK / 404 not found
    • 日期,服务器系统一些乱七八糟的
  • Safe Operations, Idempotent Operatons
    safe:不改变资源状态的操作,如 GET, HEAD(登录,缓存也算 safe)。
    idempotent:多个请求和一个的结果一样。如 safe 的,还有 PUT, DELETE。
  • URI’s
  • HTML

Chapter 3 Networking and Internetworking

DHCP, ARP

Dynamic Host Configuration Protocol:使得新连接的电脑可以动态的在可用的子网区间内获取 IP 地址。
Address Resolution Protocol / ARP:有些计算机的网络地址和 IP 地址没有直接联系,而 ARP 可以将 IP 地址和主机在本地网络的地址进行转换。

  • 每个主机上的 ARP 模块都有 (IP 地址,以太网地址)这样成对的信息。
  • 若需要的 IP 地址刚好有,那就可以马上回复
  • 若没有,ARP 就会在本地以太网发送广播问这个 IP 是哪个机子的,收到 ARP 请求的机子就会检查自己有的 IP 看是不是有符合的,有则发送自己的以太网地址给 ARP
  • 如果 ARP 收到了符合 IP 的以太网地址,就将其加入缓存。若没有,就忽略。
    因此最后每个主机里都会有本地网络所有计算机的位置,就再也不用广播了。所以 ARP 通常在有新电脑加入的时候需要。

Protocols

进程间为了交流而制定的一系列规则。

  • 消息序列中的某一部分一定被交换了
  • 消息含有特定格式的数据

Protocol Layers

信息在传递过程中会经过很多不同的模块,方便起见,可以把每一个模块看成是一个 layer 。同层 layer 才能在网络中相互交流。但是不同计算机的模块间也不能直接交流,而需要通过和其上方或下方的模块传递。如下图(以 OSI 为例)。

在发送方,信息由上而下在模块间传送,每过一层根据不同协议就对数据进行一层打包。在接收方,信息自下而上在模块间传送并逐层解包,最终接收信息的模块得到完整消息。

每一层 layer 里都有不同的协议。

Ports and Port Assignment

端口(port)可以看做信息传送时主机的一个终点。这是的信息能够指定信息发送到某个目标节点的特定程序。
端口号的区间是 0 ~ 65535 ($2^16 - 1$ 。但是 1023 以下为 著名端口,不能使用。1024 ~ 49151 是 已注册端口,一般也能用。其他的随便用。

Addressing (MAC, IP and ports)

IP:网络中的每个主机都分配了一个 IP 号码,可以用来识别特定主机以及其连接的子网。下面两张图分别表示了十进制与二进制的 IP 地址分类。

  • A 类的每个子网可以有 $2^24$ 个主机,属于国家级别的网络。1 ~ 127
  • B 类通常分配给运行超过 255 个电脑的组织或公司。128 ~ 191
  • C 类随便分。192 ~ 223
  • D 类用于广播。224 ~ 239
  • E 类防患于未然。240 ~ 255

MAC:每个机子都有一个唯一的 MAC 地址,由厂家分配。

Datagrams

  • 包交换网络中传输的最小单位。只能传输字母或者电码。
  • 最大特点为 one-shot 过程:不用任何设置,一旦发送了就不管了。所以是 unreliable

Routing

路由是除了 LANs 所有网络都需要的提供两点之间连接的功能。(就是找路径啦)
路由器里会存储路径表,包含了网络中本地到网络中所有节点的距离(成本)

RIP Algorithm

Routing Information Protocol Algorithm,一种用于更新路由器的路径表的简单算法。

  • 每当自己的路径表改变了,就把表发送到所有邻居。
  • 当从附近路由器收到一张表,如果出现了一个新终点,或者出现了比现有成本更小的路径,则更新表。

TCP and UDP Compared

TCP:面向连接的协议。打电话,一头连另一头。速度慢。有顺序。有很多头部信息。可靠。
UDP:面向数据的协议,不管连接。寄信一样,写了地址仍邮筒我们就无法掌控它了。速度快。没顺序。
没啥头要包起来的。不可靠,容易丢包。

Common Application Protocols

Chapter 11 Security and Cryptography

RSA

维基

Cryptographic Protocols

加密协议。如 Bitcoin,SSL, HTTPS, Kerberos

Cryptographic Notation

$K_A$ Alice’s secret key
$K_B$ Bob’s secret key
$K_{AB}$ Secret key shared between Alice and Bob
$K_{Apriv}$ Alice’s private key (known only to Alice)
$K_{Apub}$ Alice’s public key (published by Alice for all to read)
${M}_K$ Message M encrypted with key K
$[M]_K$ Message M signed with key K

Symmetric Key Crypto

对称加密。A 和 B 都用同一个 key 来加密,交流双方共享 symmetric key ,$K_{ab}$

Asymmetric Key Crypto

非对称加密。A 用 B 的 public key 加密发送给 B,B 用自己的 private key 解密

💡 非对称加密一般比对称加密慢 100 到 1000 倍,既然非对称钥匙加密这么慢,为什么还要用?

  • 为了加密 symmetric key
  • 为了提供一个长期的数字签名

Scenario 1 (Like TEA and WWII Enigma)

场景类似于二战时的交流与 TEA 算法,交流双方通过一个共享的 secret key 交流,是对称加密。

A 用 $K_{AB}$ 加密信息 i,发送给 B ,B 通过 $K_{AB}$ 解密得到信息 i

潜在问题:

  • 怎么传输 symmetric key ?
  • 如何知道 ${M_i} K_{ab}$(用 $K_{ab}$ 加密后的信息 i )不是旧信息的再次发送?

Scenario 2 (Like Needham-Schroeder, Like Kerberos)

场景类似于Kerberos
A 想要获取 B 提供的某项服务,S 是一个受信任的第三方。

  1. A 向 S 寻求一个可以与 B 交流的 ticket
  2. S 是受信任的,知道 $K_A$
  3. S 向 A 发送了 $\{\{Ticket\}K\_B, K\_{AB}\}K\_A$,用 A 的私有钥匙加密的信息串,其中包括了用B的私有钥匙加密的 ticket 和 $K_{AB}$
  4. A 通过解密可以得到 $\{Ticket\}K\_B, K\_{AB}$ ,A 不能解密 ticket,因为他没有 $K_B$
  5. A 向 B 发送了请求内容 $\{Ticket\}K\_B$ ,Alice,Read
  6. B 可以通过 $K\_B$ 获取 ticket 的内容为 $K\_{AB}$ , Alice,于是 B 也拿到了 $K_{AB}$
  7. A 和 B 可以开开心心的用这个 session key $K_{AB}$ 进行对称交流啦!

潜在问题:

  • 坏人可以从A的缓存中获取 $K_{AB}$ 从而伪装成 A 与 B 通信
  • 由于 S 需要有所有用户的private key,所以规模化不是很方便
  • S 是一个单点失败点,存有所有的关键信息,一旦失守,就回不去了。

Scenario 3 (Authentication)

身份认证
A 想要让 B 相信是他发送了信息 M

  1. A 先将 M digest(比如MD5)
  2. A 将 Digest(M) 用 $K_{Apriv}$ 加密,这就是数字签名
  3. A 将 $M, \{Digest(M)\}K_{Apriv} $ 发送给 B
  4. B 得到签名后的信息后,将 M digest 并与解密数字签名得到的 Digest(M) 比较
  5. 若结果一致,则签名有效

Scenario 4 (Like SSL)

SSL
B 想要与 A 建立联系生成 $K_{AB}$

  1. A 得到 B 的 $K_{Bpub}$,这个 key 由一个受信任的第三方 T 生成,即这个 public key 是被 T 签名的
  2. A 首先确认是 T 签名的这个 $K_{Bpub}$
  3. A 生成 $K_{AB}$ 并用 $K_{Bpub}$ 加密
  4. A 发送信息: $keyname, \{K\_{AB}\}K\_{Bpub} $
  5. B 通过 keyname 来选择相应的 $K\_{Bpriv}$ 来解密 $\{K\_{AB}\}K\_{Bpub} $

潜在问题:

  • A 收到的可能不是 B 的 public key,而是来自另一个坏人的同样由 T 签名的 key 。

MACs

Message Autentication Codes。数字签名的一种。

Programming Java SSL Sockets

client 端:truststore
keytool -genkey
keytool -export
keytool -import
server 端:keystore

Digital Signatures

就是 scenario 3 说的情况。

Chapter 9 Web Services

可参考小明这篇文章。CMU 95702 - Service Design

Web Service Design Pattern

  • request-reply 模式
  • event-reply 模式

Binary Schemes and Performance

Coupling in Space and Time

Separation of Concerns and Examples

tiers / layers

Jon Postel’s Law

鲁棒性原则。
Be liberal in what you accept. 收到就开心,少点也没事,多点也无妨。
Be conservative in what you send. 要啥就请求啥。

Productivity and Adaptability

Web Service API Styles

RPC

有个部分叫做 service descriptor,它用来在 client 端生成一个 proxy 。decriptor 可以用 WSDL XSDL.

  • considerations:
    • 若一个请求里的参数过多,会造成系统耦合程度太高。就像改一个参数就要两边都改。single message argument 就好很多。
    • 默认是 request/response 协议,但是也可以是 request/acknowledge 。这样时间耦合度小。

Message

Message API 通常用的是 request/acknowledge,service 充当了一个 dispatcher 的角色,因为 Message 里不带方法名或参数,所以 service 就通过 message 的内容来选择要调用的方法。有且只有一个参数。

Resource

resource API 可以是 RESTful 的

Style Considerations

REST Archetectural Princeiples

REST 是一种架构,是在协议之上的,并不针对某种特定协议。HTTP/JMS/MOM/SQL
有以下一些 principles:

  • Addressibility:well-format URI 。每个资源都有一个唯一的 URI。
  • uniform interface:统一接口,使用有限的方法来操作资源。
  • representation oriented。格式多样化。像 request 返回的格式可以是 XML/JSON/YAML…
  • 不用在意交流双方的状态,他们有多少数据都没关系。容易扩展。
  • HATEOAS,就是下面的 linked services pattern 的一种。

Linked Services Pattern

一个request 请求里面包含另一个请求。

Client Server Interaction Styles

Odata

Open Data Protocol: RESTful 但是在 HTTP 之上,接口也很少,无状态,一开始得到的是 XML 或 JSON 的消息。

Chapter 4 Interprocess Communications

这章主要就是说不同平台的沟通是怎么弄的。详细英文版

Middleware

中间件直白的说就是协调整合不同 server 上的应用或者系统的一个助手,让他们彼此可以相互交流。

External Data Representations

一种表示数据结构和 primitive type 的一种标准。比如下面的 CORBA’s CDR, Java Serialization, XML。将原数据通过这些方式转变的过程叫做 marshalling ,而转回来的过程就叫做 unmarshaling 。

CORBA’s CDR

CORBA(Common Object Request Broker Architecture) ,是用于创造、分布、管理分布式系统中对象的一种架构。不同地点不同平台可通过一个“接口中转站”(interface broker)来进行沟通。

CORBA’s common data representation 则是一种能使各种数据结构或者原始型可以以远程方法的参数和结果在 CORBA 中进行传递的一种 external representation 。(很绕)

Java Serialization

使得 Java 对象能够以信息方式传递或存储在硬盘中的一种 external representation 。

XML and JSON

用一种格式化的文本来表示对象,用于信息传递。

UDP Based Request Response Protocol

这个例子感觉就是 RMI 了。。

顺便这是一个 Request-Reply 消息的结构

Fault Tolerance Measures for the UDP Request Response

  1. 上图中(黄色那张),doOperation 可能会超时,可能服务器端好久不传消息回来。
    解决方式:

    • 返回 error 消息
    • 或者可能因为消息丢失(毕竟UDP),所以不停的尝试直到确认另一端是挂掉了。
  2. 重复消息
    解决方式:

    • 如果是 idempotent 操作,则重新计算回复。
    • 从上次回复里返回一个一样的。

RPC Exchange Protocols(R, RR, RRA)

R1 = request,R2 = reply,A = acknowledge
R:适用与没有返回值的操作,或者 client 端不需要知道操作是否已在远端执行
RR:适用于多数的 client-server 信息交换。不需要额外的“知道了(acknowledgement)”消息,一条 reply 就以足够。
RRA

The End-to-end Argument

友链到小明。CMU 95702 - End to End Arguments in System Design

Android and MObile Devices

The Rise of Mobile Platforms

Why Mobile?

  1. 移动设备联网趋势 (据ITU 2015年报告,全球将近97%的网络连接是通过2G及以上网络)
  2. 移动宽带比固话建设成本更低

Why Android?

  1. 基于linux
  2. 可用Java(iOS需要Object C和swift),群众基础强大

Building a Native Application

Android Archetecture

  • 基于linux的小型计算机
  • 联网
  • 特定硬件(如手机,GPS,相机)
  • 支持程序写入的软件栈?

Flow of Control

Java -> Any POJO -> main() -> None
Web Application -> Extend HttpServlet -> doGet(), init(), doPost() -> web.xml
Android Application -> Extend Activity -> onCreate(), onPause(), -> AndriodManifest.xml
(参考小明)

Android UI Definition

一个Android的UI在xml文件和res目录下被定义。
两种编辑模式:

  • Design(WYSIWYG)
  • Text(xml)

Network Latency and AsyncTask

由于网络延时,手机发送了请求以后不能一直待在那,所以就有了一种 AsyncTask 可以在后台进行处理,拿到结果了再展示到眼前。

Chapter 5 Remote Method Invocation

Interface Definition Language (IDL)

为了让不同编程语言的进程可以相互调用的一种语言。

Goals of Java RMI

RPC(remote procedure call):远程过程调用。
RMI(remote method invoke):远程方法调用。

  • 充分运用面向过程语言的特点,比如对象、类、接口。
  • 基于 RMI 系统中的每一个对象,不论是本地或者是远程的,都有一个唯一的引用。同时这些对象也可以作为参数传递,比 RPC 的适用场景更多。

Remote Object References

可以用来引用某个特定远程对象的标识符。

EJB Remote and Local Interfaces

每个远程对象都由一个远程接口来表示其可以被调用的方法。
EJB 是一种基于组件的中间件技术。

Generic RMI Component Interactions

下图展示了一个常规的 RMI 过程。

  • communication module 通过 request-reply protocol 在 client 与 server 间传送消息。client 端的交流模块箱 server 发送 request 消息,其中包括了消息类型,requestId 和想要调用的对象的远程引用地址。server 端的交流模块收到 request 消息后,为要被调用的类选择一个分发器(dispatcher),并把要调用类的本地引用发过去。
  • remote reference module 用于本地和远程对象引用的翻译以及创造远程对象引用。
  • servant 是一个远程对象的一个实例,在 server 端。各种远程方法的请求最终都由它完成。它在远端对象被初始化是创造,当不再需要了就回收。
  • proxy 可以看出远程对象在本地的一个映射。它将调用的过程都打包了起来,让 RMI 过程像在本地发生一样。
  • dispatcher & skeleton:每个 server 上的每一个类都各有一个 dispatcher 和一个 skeleton 。 skeleton 就是远程对象的类。dispatcher 从 communication module 中收到 request 消息,通过 operationId 到 skeleton 中选择合适的方法,并一起加到 request 消息里。

Registries

这是 Java RMI 的粘合剂(binder)。用于存放远程对象地址,每一个基于 RMI 的服务器上都应该有一个。

Java RMI Code Examples

Chapter 12 Distributed File Systems

NFS / Network File System

下图为 NFS 架构。

  • NFS 支持 NFS 协议,将外部请求转化为 RPC 在服务器端调用来处理相应的文件,在 TCP 和 UDP 之上
  • VFS(virtual file system)虚拟文件系统整合了本地和远端的操作,实现了访问透明:用户可以对本地和远端的文件进行无差别的操作。

NFS 目标:

  • 可以进行 UNIX FS 的所有操作
  • 实现所有 POSIX API。
  • 文件在任何一台机器上都可以获取
  • 分布式存放分拣,不再需要实现新的协议

AFS / Andrew File System

  • AFS 与 NFS 最大的不同便是可扩展性(scalability)。AFS 有着比其他分布式文件系统大得多的活跃用户量(试想一下期末考试时大家都在查邮件,但是放假时几乎没有人看邮件)。
  • 为了实现可扩展性,AFS 的主要策略就是将整个文件的缓存都放在 client 端,这个缓存即使重启了也不会删除。这样是为了让 client 本地工作(work locally)。
  • client 端的文件在修改了以后才会传回 server

Chapter 21 Google Case Study

GFS, MapReduce, HDFS

Chapter 6,9 Indirect Communication and Naming

Indirect Messaging

发送者与接收者通过某种介质(如第三方),使得时间与空间都解耦(time uncoupling and space uncoupling)的一种信息交流方式。
使用场景:

  • 环境变化十分频繁:如手机网络
  • 不可靠的接收者:如新闻订阅,接收者的数量和对象一直在变化

时间解耦与异步交流的区分:

  • 异步交流中,发送者发送了一条消息后并没有堵塞(blocking),而是继续发送其他消息给别的接收者。但是发送消息时,接收者必然是存在的。
  • 时间解耦意味着发送者和接收者不需同时存在。

Point-to-point

点对点模式,也就是发送者发出的所有消息都会被某个潜在接收者收到。

Publish Subscribe

发布-订阅模式。点对多。发布者发布所有事件,订阅者可以选择自己感兴趣的主题进行接收。

Java’s JMS API

全称为 Java 消息服务(Java Message Service)。

  • 是一个用于非直接信息的 API
  • 是个抽象 API,类似于 JNDI 和 JDBC
  • 与一些 MOM(Message Oriented Middleware)(如Apache ActiveMQ, Oracle Weblogic)交互
  • 面向客户的接口
  • javax.jms

下图展示的是一个 JMS 运行的模型。首先 JMS 与 Message 建立连接,然后建立 Session(一个 Session 代表了一个逻辑任务中的一系列操作包括消息的创造,生产与消费),之后便是向 Producer 发送消息存入 Destination ,Consumer 再从 Destination 中消费。

JMS Queues and Topics

点对点中,消息存入 Queue ,接收者拿一条少一条,分完就没了。
发布-订阅模式中,消息按照 Topic 来分,订阅者通过各自的兴趣订阅了不同的 Topic。订了什么就收到什么。

Queue 和 Topic 都是被 MOM 创造和销毁的,而并非客户。

JMS Message Types

  • Stream
    Java primitive 数据类型的流
  • Map
    • 键值对的集合(key是 String,值是 primitive)
    • 可以一个一个拿,或者通过 key 拿
  • Text
    • String 字符串:可以使纯文本消息或者 XML 格式的
  • Object
    • 序列化的 Java 对象。
  • Bytes
    • 比特流

Message Driven Beans

为间接交流而生。可以异步地处理 Queue 或 Topic 来的消息。

Chapter 14 Time and Global State

都写了,看这篇吧。Time and Global State

1 Internal and External Synchronization

2 The Network Time Protocol (NTP)

3 Global State Terminologies

histories
happens-before relation
cuts
linearization

4 Lamport clocks

5 Chandy and Lamport Snapshot Algorithm

Chapter 16,17 Local and Distributed Transactions

1 ACID Transactions

原子性(atomic): All or nothing.
一致性(consistent):类似于看成能量守恒。无论怎么交易,系统总量不变。
隔离性(isolated):两个交易相互独立,互不影响。即使它们是同时发生的,但实际操作时也是会有一定的顺序。
持久性(durable):对一个对象操作后,若再无其他操作,该对象的所有属性都保持不变。为了防止操作发生而实际对象没有更新的意外,日志会存储一些必要数据用于回滚。

2 Concurrency Control

  • lost update
    B 客户和 C 客户同时读取了 A 账户的余额,并以此来计算下一步的操作的存钱额度。
  • inconsistent rereivals
    计算所有账户总额时,在已经加过 A 账户以后, A 账户取了钱,那最后算出来的总额就会与实际总额不一致。

3 Conflicting Operations

假设有俩操作,1 和 2,先做 1 再做 2 与 先做 2 再做 1 的结果不一样,那 1 和 2 就是矛盾的。比如先读后写和先写后读。

4 Serial Equivalence

如果交易 A 和交易 B 中所有相矛盾的操作都按照唯一的顺序执行,那这两个交易就是 serial equivalence 。
比如:$r_A(x)w_A(x)r_B(x)w_B(x)$($r_A(x)$ 表示交易 A 对 x 进行读取(read)操作)。例子中所有操作的顺序都不能改变($r_A(x)w_A(x)$ 矛盾,$w_A(x)r_B(x)$ 矛盾,$r_B(x)w_B(x)$ 矛盾),否则就会对结果产生影响。它们必须按照顺序一个一个(serial)执行才能保证最后结果相同(equivalence)。

5 Recoverable Objects

  • 黄金规则:“永远不要只修改一个副本。”
  • 通常除了在挥发性存储(如内存)里备份,为了防止进程中途 crash ,也会在持久性存储(如硬盘)中备份一些。
  • 通过恢复,可以将对象的状态恢复到之前的版本。
  • 在一个交易内的对象的状态改变都是存储在一个临时版本里,而不是本地副本,只有在交易结束(commit)后才将对象状态写入本地。这样保证了万一交易失败,对象可以回到交易最初的“无害”状态。

6 Locks and Deadlock

锁(lock)是指系统将某一对象锁起来不给访问的一种状态。通常发生在冲突操作时,为了保持一致性,暂时性的锁住对象,其他交易的操作只能等待直到解锁。
死锁(deadlock)是指两个交易互相等待对方解锁而陷入死循环的一种状态。比如,交易 A 想从账户 x 取钱打给 y ,A 先锁定了账户 x。这时交易 B 想从账户 y 取钱打给 x,B 于是锁定了账户 y。然后 A 准备给 y 打钱发现 y 锁了,于是等待 y 解锁,而 B 想给 x 打钱时发现 x 被锁了,于是也在等待 x 解锁。最后这俩都只能等到天荒地老。

7 Eventual Consistency

如果对某一个对象没有新的更新操作,那最终所有对这个对象的读取操作(包括分布式系统中对副本的)都会返回最新的值。大统一呀。

8 Synchronized Keyword

Java 中为了保证每次只有一个线程能对某个对象进行访问的关键字。等于是起了这个对象。

9 Wait and Notify

wait()notify() 也是 Java 中的方法,它们只能放在加了 synchronized 关键字的方法中。这套组合拳实现了操作(线程)间的交流,可以解决某一些需要先行操作的行为。调用 wait() 时,该线程自动释放了锁,并暂停等待合适时机(被其他线程 notify())。调用 notify() 时,该进程释放了锁,通知其他等待着的进程可以开始了,之后先抢到锁的进程开始执行,其他进程又进入了 wait() 状态,直到下一次被 notify()

10 2PL / Two-phase Locking

在 serial equivalent 的交易中,为了实现任何矛盾的操作都按照唯一的顺序执行,要求在一个交易中,一旦开始解锁就不能再有产生新的锁。这样就将一个交易的执行过程划分成了两个明显的阶段:

  • 增长阶段(growing phase):在这阶段锁的数量不断增加,没有锁释放。
  • 收缩阶段(shrinking phase):在这阶段锁开始释放,数量减少,且没有新锁生成。
    简单说,就像解连环锁的过程。解法是唯一的(保证顺序唯一),一锁套一锁,解开了上一个锁才能去解开下一个锁。

strict two-phase locking:这个要求更严格,一个交易对某个对象的锁只能在交易执行且将更新写入永久存储中后(commit)才可以解锁。

11 2PC / Two-phase Commit Protocol

两相提交协议使得分布式系统中的各个服务器可以通过交流实现对某一个交易的共同决定(提交或放弃),从而保持整个系统内的交易都可以 serialized 。

2PC 内的操作

  • canCommit?
  • doCommit
  • doAbort
  • haveCommitted
  • getDecision

第一阶段(投票)

  1. coordinator 询问所有参与的服务器是否要提交交易 doCommit?(Yes or No)。
  2. 当一个参与者收到询问会向 coordinator 回复。若回复 Yes ,则立即将对象存储到永久存储以完成准备。如果要回复 No ,则立刻终止(对对象的操作)。

第二阶段(完成):

  1. coordinator 收集所有投票getDecision,如果都是 Yes ,则发送一个 doCommit 请求到每一个参与者。如果有一个 No ,则发送doAbort请求到回复了 Yes 的参与者。
  2. 投了 Yes 的参与者等待 coordinator 的下一步指令并作出相应反应。如果是doCommit,最后还会发一个haveComitted回给 coordinator 。

潜在失败原因:

  • 信息丢失
  • 某个服务器崩溃

12 CAP Theorem

一致性(consistency):所有节点持有的所有对象的值都是最新的(一致)
可用性(availability):每个节点上的对象都可以实现更新
分区容差(partition tolerance):即使部分网络崩溃了,系统仍然可以正常运转。
以上三点不可同时兼得,只能实现其中的任意两个,这就是 CAP 定理。

Chapter 19 Mobile and Ubiquitous Computing

Association

Sensing and Context Awareness

Location Sensing

Adaption

Device Awareness / Browser Detection

Feature Detection

Graceful Degradation

Progressive Enhancement

Responsive Web Design

Mobile First

Mobile Depoyment Strategies

Labs

Projects