Welcome to Borui's Blog!
时间无多,疾步前行-
Java Concurrency in Practice(2)
线程安全性
线程安全性的核心在于对状态访问操作需要管理,尤其是对共享的和可变状态的访问.
对象的状态还会包括依赖对象的域,例如容器的状态还包括容器装载的对象状态.
Java中的同步机制包括:
- synchronized
- volatile
- 显示锁
- 原子变量
修复多线程问题主要有三个方向:
- 不在线程之间共享状态变量: 不存在多线程,那么也就不存在多线程问题了.
- 将状态修改为不可变的变量: 不可变变量无论怎么访问,都是正确的.
- 在访问状态变量时使用同步: 当状态是共享的,且可变的时候,那么就只有采用同步机制了.
程序的状态封装的越好,越容易实现程序的线程安全性.
正确的编程理念是:
首先使得代码正确运行,再考虑性能问题.而且一定要有足够的证据证明必须提高性能.
2.1 什么是线程安全性
最核心的概念是正确性.对于某个类来说,正确性意味着符合规范规定.规范通常会定义各种不变性条件来约束对象状态和后验条件来描述结果.当多个线程访问某个类时,这个类始终表现出正确行为,那么这个类就是线程安全的.
无状态对象一定是线程安全的.
2.2 原子性
竞态条件(和数据竞争不是一回事):
- 先检查后执行: 常见例如延迟初始化(饱汉模式)
- 读取-修改-写入: 递增计数器.
复合操作: 包含了一组必须以原子方式执行的操作以确保线程的安全性.
线程安全问题主要是竞态条件导致的,原子性是解决多线程安全问题的基本策略.
2.3 加锁机制
要保持状态的一致性,就需要在单个原子操作中更新所有相关的状态变量.
内置锁-synchronized同步代码块:
- 锁对象的引用.
- 锁保护的代码块.
可重入-内置锁是可重入的,因此内置锁的粒度是线程而不是调用.
可重入锁的一种实现方式是,每个锁关联一个计数器和所有者线程.
2.4 用锁来保护状态
如果需要协调对某个变量的访问,那么所有访问的入口都需要使用同步.如果采用了加锁机制,那么要使用同一个锁.
2.5 活跃性和性能
简单粗粒度的锁会导致性能问题.
简单性和性能往往有冲突,因此需要权衡同步代码块的大小范围.
执行时间较长的操作一定不能持有锁,这会带来活跃性或性能问题.
-
Java Concurrency in Practice(1)
Introduction
1.1 并发简史
- 早期计算机不包含操作系统,只能从头到尾执行一个程序,程序访问全部资源.
- 操作系统使得程序在单独的进程里运行.
- 操作系统为进程分配各种独占的资源.
- 进程之间通过粗粒度的通信机制来通信.
- 进程出现的原因:
- 资源利用率: 当一个程序等待外部操作时,可以使得另一个程序运行.
- 公平性: 使用粗粒度时间分片,使得用户平等的使用计算机.
- 便利性: 计算多个任务,采用多个程序要比一个计算计算全部任务要容易实现.
- 每个进程相当于一台虚拟的冯诺依曼计算机.
- 存储指令和数据的内存空间.
- 根据机器语言指令以串行的方式执行.
- 通过I/O指令与外部设备通信.
- 线程允许在同一个进程内存在多个程序控制流.
- 线程共享进程内资源.
- 独立拥有程序计数器,栈以及局部变量.
- 可以同时被调度到多个cpu上运行.
- 线程是基本的调度单位.
- 线程之间共享进程内堆空间,采用比进程间共享数据更细粒度的数据共享机制.
1.2 线程的优势
- 发挥多处理器的强大能力(系统角度)
- 多处理器成为计算机的主流趋势.
- 多线程程序可以同时在多个处理器上执行,提高处理器资源的利用率,从而提高系统吞吐.
- 即使在单处理器系统上,针对I/O密集型程序也能提供系统吞吐.
- 建模的简单性(客户端角度)
- 单一任务的编写要比多任务的编写要简单.
- 每个任务分配到一个线程里,简化每个任务的编写.
- 任务在特定的同步位置进行交互.
- 将请求管理,线程创建,负载平衡等功能交给框架实现,用户只需要当做单线程程序来进行实现.
- 异步事件的简化处理(服务器端角度)
- 单线程应用在处理请求过程中,无法响应其他请求.
- 非阻塞I/O较为复杂
- 每个客户端分配一个线程在某些平台也是可行的.
- 响应更灵敏的用户界面
- 单线程gui框架主要依赖poll方法和主事件循环.
- 现代gui框架采用事件分发线程.长时间运行任务在单独线程执行.
1.3 线程带来的风险
- 安全性问题
- 没有合理同步的情况下,由于线程运行不恰当的顺序导致不可预测的结果,这称之为竞态条件
- 多线程共享内存地址空间,因此会出现并发
- 安全性含义:永远不会发生错误的事情.即正确性.
- 活跃性问题
- 正确的事情一定会发生.
- 死锁
- 饥饿
- 活锁
- 性能问题
- 线程上线文切换带来的开销
- 保存和恢复上下文.
- 局部性丢失.
- cpu时间用于调度而非运行.
- 共享数据采用同步机制会抑制编译器优化,使内存缓冲区无效.
- 线程上线文切换带来的开销
1.4 线程无处不在
框架在应用程序里引入的并发性,并不只局限于框架,因为框架本身会回调应用程序的代码,因此线程安全性会在应用程序中蔓延.
- Timer类
- Servlet
- RMI
- Swing和AWT
-
Distributed Systems: Concepts and Design, First Edition(1)
分布式系统的特征
- 分布式系统是组件分布在通过网络相连接的计算机上,组件之间通过消息传递来进行通信和协调动作的系统.
- 分布式系统重要特征:
- 组件的并发性
- 全局时钟的缺失
- 组件故障相互独立.
- 资源共享是构造分布式系统的主要动机.
- 资源可以被服务器管理,被客户端访问,或者被encapsulate成对象,被其他的客户端对象访问.
- 构建分布式系统的挑战在于:
- 组件的异构性(hetero|geneity[异性的|通用性])
- 开放性(允许增加或替换组件)
- 安全性
- 可扩展性(当负载或者用户量增加时,良好工作的能力)
- 故障处理
- 组件并发性
- 透明性(transparency)
- 提供的服务质量
-
scala tips
scala: classes and objects
- 可以将singleton object视为依附于某个object的命名tag.
- 当singleton object继承父类或者特征时,singleton object就是该父类或者特征的实例,因此可以调用这些父类或特征的方法.
- class可以传递参数,但singleton object不可以.singleton object被实现为synthetic class的实例,类似java静态类的初始化过程.
校验泛型参数的类型
abstract class RDD[T: ClassTag] { if (classOf(RDD[_]).isAssignableFrom(classTag[T].runtimeClass)) { ...... } }简化函数
我们可以使用下划线作为一个或多个参数的占位符,只要在函数常量的内部,每个参数只被使用一次. 这里下划线可以代替一个参数,也可以代替整个参数列表.
闭包
scala的闭包能够追踪自由变量的变化.
var num = 1 val a = num + (_:Int) a(1) // result is 2 num = 33 a(1) // result is 34
-
spark paper read
Spark: Cluster Computing with Working Sets
Abstract
分布式计算领域的map reduce模型已经获得巨大的成功，但该模型更适用于非循环数据流模型。有一类应用则是需要重用跨多个并行操作的工作集数据：比如迭代机器学习算法和交互式数据分析工具。Spark在保留Map reduce的可扩展性和容错性的基础上，提出RDD
-
Designing Data-Intensive Applications读书笔记(9)
Consistency and Consensus
分布式环境里很多故障都会发生,最简单的做法就是整个服务失败,然后告诉用户错误信息.但在web环境中这是不可接受的,因此需要我们进行容错处理.这里我们将描述一些分布式容错算法,面临的故障包括包丢失,乱序,重发和任意延迟,包括时钟最多只是近似的环境,还包括节点暂停(可能是gc导致的)或故障.
建立容错机制最好的方法,就是能找到提供有用保证的通用抽象,然后让应用程序运行在这层抽象上.就像通过事务,应用程序无需关心节点故障A,并发I和存储问题D.分布式系统中,最重要的抽象就是一致性,这里一致性的含义是使得所有节点就某项决定达成共识,这样我们就不用考虑网络故障和节点失败问题了.
和事务类似,我们需要知道抽象的边界在哪里,什么能做什么不能做,提供的保证包含哪些,一致性的局限在哪里.这里的一致性分为内部一致性和外部一致性,内部一致性是系统内部达成一致,外部一致性是应用看到的视图(就算内部数据并不一致,可以通过某些手段返回给外部一致的结果).并且和事务的一致性都不一样.
一致性保证
大部分复制数据库都提供了最终一致性,这意味着如果你停止写入然后等不知道多久的时间,最终所有的读取操作都会返回一样的结果.也就是说不一致是暂时,最终都会达成一致.最终一致性更好的叫法是收敛,它并不保证什么时候这些副本会一致.
更强的一致性模型会有性能损失和较差的容错性.但是更易于使用.分布式一致性模型和事务里的隔离级别有些相似,但除了有些重叠大部分概念还是相互独立的.事务隔离性主要是为了避免并发执行事务时的竞态条件.而分布式一致性主要是为了协调副本的状态,在延迟和错误存在的条件下.
线性一致性
线性一直性,又叫做原子一致性,强一致性,瞬时一致性或者外部一致性.基本思路就是使得系统看起来好像只有一份数据,并且所有操作都是原子的.这样的话即使实际上有多份副本,但应用层并不需要了解.
简而言之.线性一致性就是能够看到最新的数据.
线性一致性和可串行化
可串行化是事务的一种隔离级别,每个事务都会读写多个对象.事务保证事务的执行行为就像按照某种线性顺序执行结果一样(每个事务在下一个事务开始前结束).即使事务实际执行的顺序和线下顺序并不一致.
线性一致性是针对读写的最新保证,它并不将所有操作都封装到事务里,所以不能避免写倾斜问题,除非采用其他的手段.
一个数据库可能提供两种保证,这被称为严格可串行化或者强单一副本可串行化.基于两阶段锁和实际串行执行实现的可串行化是典型的线性一致的.但是ssi就不是线性一致的.因为读取操作都是从快照读取的,不包含最新写入的值.
依赖线性一致性
锁和选主
单主复制系统需要确保系统有且只有一个主.常用的选主方法就是使用一个锁,无论锁怎么实现都必须是线性一致的,所以节点必须统一某个节点获取了锁.协调服务例如zk和etcd都被用来选主和实现分布式锁,还可以使用fencing令牌实现选择和锁.
约束和唯一性保证
唯一性约束在数据库里很常见,这时也需要线性一致性.
实际中,有时候可以放宽约束.这时候就不一定需要线性一致性了.
跨渠道的时间依赖
不同的信息交互渠道存在时,就需要线性一致性.
实现线性一致性系统
- 单主节点(有可能线性一致):如果读写都发送到主上,或者同步更新副本,则有可能是线性一致的.但是这取决于设计方式.
- 共识算法(线性一致):和单主复制结构类似,但能够避免脑裂和损坏副本.
- 多主复制(不能线性一致):并发写在多个节点上而且是异步复制,还会因此产生冲突,这种冲突就是缺乏单一数据副本的产物.
- 无主架构(可能不是线性一致的):版本向量+WRN看起来是强一致的,但是LWW里的时钟并不能保证和实际发生的时间是一致的,而且Sloppy quorums也会破坏线性一致性.
线性一致性和quorums
尽管看起来严格的quorum读写是线性一致的,但由于网络延迟的存在,仍然会有不一致出现:
这种情形下可以通过牺牲性能来获取线性一致性:读者必须执行读修复,写者必须读取最新的数据.Cassandra进行读时修复,但是由于采用lww解决冲突因此在并发写入时会丢失线性一致性.线性一致性的代价
CAP
- 如果应用需要线性一致性,而当部分副本因为网络问题无法和其他副本连接,那么这些副本不能处理任何请求,只能等待网络恢复或者返回用户错误信息,换句话说,它们是不可用的.
- 如果应用不提供线性一致性,每个副本都可以单独处理请求.当出现网络问题时,仍然能够可用,但无法保持线性一致性了.
不需要线性一致性的应用能够更容忍网络的问题,这个观点就是众所周知的CAP理论.CAP理论最好的解释应该是:在网络分区问题存在的情况下,是选择一致性还是可用性?
线性一致性和网络延迟
线性一致性很有用,但是很少系统会在实际上实现线性一致性.就算多核cpu上的RAM也不是线性一致性的.因为线性一致性对性能损耗太大.线性一致性已经被证明,读写请求响应的时间至少是正比于不确定的网络延迟时间的.
顺序保证
- 在单主拓扑结构里,的主要目的就是决定副本日志里的写入顺序,如果没有leader就会出现写入写入冲突
- 在事务中的可串行化隔离级别保证事务之间,按照某种序列顺序在执行.
- 时间戳和时钟在分布式系统中的应用,是另一种顺序定义方式.
事实证明,在顺序,线性一致性和一致性有着很深的关联.
顺序和因果
顺序很重要的一个原因,就是要保护因果关系:
- 在一致性读问题中,用户还没看到问题,就看到了回答就很奇怪.
- 在更新一条数据请求之前,必须要有创建这条数据的请求.
- happen-before关系.
- 在一致性的快照里,所有的因果关系都是被保证的.
- SSI通过追踪事务之间的因果关联来检测写倾斜.
因果加强了事件中顺序的重要性,如果一个系统服从因果导出的顺序关系,我们称之为因果一致性.
因果顺序不是全序
- 线性一致性:如果一个系统表现的如同只有一份数据拷贝,并且每个操作都是原子的,这意味着每个操作我们都能分辨出谁先于谁发生.
- 因果:因果中存在既不是你先于我也不是我先于你的并发操作,这意味着因果是部分有序的.
因此,在线性一致性的数据库里,是没有并发操作的,所有的操作都必须有序的按照单一时间线发生.因此多个请求需要等待处理,但是数据库在某个时刻只会原子的处理一个请求.
线性一致性强于因果一致性
线性一致性就意味着因果一致性,但是线性一致性的系统损害了性能和可用性,尤其是系统由明显的网络延迟时(比如系统按照地理位置分布).因此分布式系统一般放弃的线性一致性以获取更好的性能,但比较难使用.
当然线性一致性也不是保证因果的唯一方式,一个系统可以在实现因果一致性的基础上不损害系统性能.实际上,因果一致性是不因网络延迟而变慢,面对网络故障仍可用的最强可能的一致性模型.在很多情况下,系统实际上需要的并不是线性一致性而是因果一致性.
找出因果依赖
为了保持因果关系,我们需要找出因果依赖的操作.在无主拓扑结构中,我们通过版本向量来洞察单key的并发写操作来防止丢失更新.因果一致性需要获悉整个数据库的因果依赖,因此需要扩展版本向量.
序列号排序
我们可以使用序列号或者时间戳来排序事件,时间戳来自逻辑时钟(一般是自增长计数器).在单主结构中的数据库里,副本日志使用单调递增的序列号来绑定每个操作,从而保证了因果一致性.
无关联的序列号生成器
对于多主或者无主的数据库里,或者数据被分区了,怎么生成序列号呢?
- 每个节点独立生成自己的序列号,并且不同的节点生成的序列号不重复.
- 使用物理时钟来产生时间戳.
- 预先申请一批序列号给各个节点单独使用.
但是由于这些序列号并不能说明不同节点间的顺序关系.
lamport时间戳
lamport时间戳可以简化成一个数对(counter,node ID).每个节点和客户端负责追踪最大的counter数值,一旦节点发现来自客户端的counter数值大于当前维护的最大数值,就会立即更新最大值.
lamport和版本向量不同.版本向量是为了区分是否两个操作是并发的还是因果依赖的.而lamport时间戳总是强制全序的.而且也能够分辨并发和因果依赖.
不过时间戳有序还是不够的,因为你是在所有操作都获取的情况下,你可以进行比较排序.但是当其他节点发生的操作你不知道时,是没有办法获取最终的排序结果的.
全序广播
分区的数据库无法跨分区提供一致性保证.所有分区的全序是可能的,但需要额外的调度.全序的广播通常描述为一种交换节点间信息的协议,需要两个安全性条件被满足:
- 可靠分发:消息不能丢失,如果消息被分发到一个节点上,那么需要分发到所有节点上.
- 全序分发:分发到每个节点上的消息是同样的顺序.
使用全序广播
全序广播和一致性之间有很强的的关联.state machine replication是一种全序广播.全序广播可用于实现