MQTT学习笔记简介写给那些已经学习过消息队列的人（）或者间接连接。比如移动网络，卫星网络等。协议非常轻量header只有2字节。MQTT只有一种通信模型Publisher → Broker → Subscriber例如temperature/sensor1 temperature/sensor2设备只关心topic，topic是层级字符串，支持通配符订阅。如temperature/+ temperature/#不同于消息队列mqtt有统一的开源标准化协议。由OASIS 维护。通信模式MQTT支持多种模式如点对点：每个消息只消费一次Producer → Queue → Consumer发布订阅：每个订阅者都收到消息。流处理MQTT的Qos从高到低依次为Qos 0：至多依次（at most once1）发布者发送消息后不等确认，直接发送下一条消息。代理收到消息后直接转发给订阅者，同样不等待订阅者确认。Qos 1：至少一次（at least once）这是中等级别，确保消息至少被送达一次，但可能重复。发布者发送消息后，会等待代理返回一个 PUBACK（发布确认）包。如果超时未收到确认，发布者会重新发送消息，直到收到确认为止。代理收到消息后，会存储消息，并确保将其发送给订阅者（同样需要订阅者的确认）。消息不会丢失知道重试成功。Qos 2：恰好一次（exaclly once）最高的级别。确保消息仅有一次被送达。这个机制通过四次握手实现（four way handshake）PUBLISH：发布者发送消息。PUBREC：代理收到后回复“已接收”。PUBREL：发布者收到确认后，发送“释放”信号。PUBCOMP：代理回复“完成”，此时双方才确认消息处理完毕。Qos机制只是传输层的机制，只负责消息物理上从生产者到消费者，但无法感知消费者应用层代码是否执行成功。PUBREC/PUBCOMP 由 MQTT client library 自动发送。而不是等你业务处理完成后再发。MQTT没有类似消息队列中的DLQ（死信队列）的实现。MQTT语义是传递保证，而不是处理保证。因此broker不会感知业务是否处理成功。QoS2保证的是“协议层 exactly-once”，不是“业务 exactly-once”。这里的ack和kafka不同的是收到消息就ack，而不是完成处理才ack。MQTT 本身只是一个消息传输协议，是否把消息保存到磁盘、保存多久、是否清理，取决于具体的 MQTT Broker 实现和配置。不同 Broker（如 Eclipse Mosquitto、EMQX、HiveMQ）策略会不同。可以从几个机制来理解。如果要保证消费成功可以通过应用层ackProducer → MQTT → Consumer ↓ 处理成功 ↓ publish ack message例如topic: order/create topic: order/create/ack和消息队列的区别mqtt 出现的更早，是1999年的，kafka是2011年。并且一般kafka的生产者都是内网的机器有单独的稳定的IP。而mqtt生产者可能只有NAT的IP，并且无法固定。以EMQX距离，吞吐量能来到50w到100w。kafka在100w-1000w。由于许多应用层消费逻辑都只适配了kafka的。你甚至可以把MQTT消息桥接到kafkaIoT Device / Client │ ▼ MQTT Broker (EMQX / HiveMQ / Mosquitto) │ │ MQTT → Kafka Bridge / Connector ▼ Kafka Cluster │ ├── Stream processing (Kafka Streams / Flink / Spark) ├── Storage (Data lake / DB) └── MicroservicesMQTT为极低带宽+不稳定网络设计。最初为IOT、传感器网络设计。适用于设别算力弱。网络延迟高的场景。MQTT协议甚至不强制要求持久化。直接进行实时转发。MQTT的设计重点通常不是吞吐，而是轻量级通信。如EMQX默认所有数据都存储在内存中。通过规则引擎（Rule Engine）和数据桥接（Data Bridge），可以将消息、客户端上下线事件等数据持久化到外部数据库（如 MySQL、PostgreSQL、Redis、MongoDB 等）。这种方式通常用于业务数据归档或与外部系统集成。总的来说MQTT是无状态的。MQTT的顺序消费还要结合Qos来保证。无论是Qos1还是2都不保证严格顺序。这个顺序更像是TCP的顺序，业务层要自己控制执行顺序（毕竟ack是自动回复的，而不是业务层实现的）。
分布式事务https://www.bilibili.com/video/BV1U341157BX事务ACID在分布式场景下ACID特性含义会被扩展。原子性（Atomicity）一个事务内涉及到的分布式多个节点的操作要么一起成功，要么一起失败一致性（Consistency）：跨节点场景下也不能出现中间状态。隔离性（Isolation）：一个分布式事务在一个节点哪怕完成了，在整个分布式事务完成之前，也不能被其他事务读取使用持久性（Durability）事务提交完成后的数据不仅要在当前节点保存，还应该在分布式场景下有备份高克yognxing早期分布式事务的三个方向分别是俩阶段模型，XA事务模型TCC事务模型Saga事务模型常见的方案俩阶段提交一个直接的思路就是三个系统都等到整个交易快照完成时再一起提交。根据这个思路就诞生了俩阶段提交的方法，阶段1协调器收到客户端commit命令，决定提交T。然后协调器向各节点发送prepare T消息，各节点决定该节点上T是提交还是中止并返回给协调器。第二阶段协调器收到各个节点的ready或don't commit响应，如果都是ready，那么就决定提交T，并向所有节点发送commit消息；如果收到来自一个节点或多个节点的don't commit T的消息，就决定丢弃T，并向所有节点发送abort的消息。XA事务就是把俩阶段提交标准化后形成指定的数据库接口，再由一个事务管理器作为协调者统一管理俩阶段提交，相当于标准化的俩阶段提交。很多单机数据库，如oracle、DB2、Mysql支持XA接口，应用程序实现的一个事务管理器，然后跳读下面数据库的接口实现俩阶段提交，从而实现分布式事务。XA事务允许各个系统选择不同类型的数据库，只要它们都支持XA接口。TCC事务TCC将整个业务逻辑分为三块Try、comfirm，和cancel三个操作Try就是尝试扣除用户月、尝试扣除库存；confirm就是Try的结果都成功，可以证实把订单状态状态改为已支付，通知仓库发货；而cancel则是try失败，那么就要取消教育，回复月，回复库存。TCC是业务逻辑补偿的应用层设计实现。TCC的一个关键点是，Try阶段如果完成，那么很多状态就已经保存起来，再出现故障也不会影响事务的晚餐，也就是说，哪怕confirm阶段或cancel阶段失败，也会通过不断重试完成交易，而不是回滚。TCC的过程类似于俩阶段提交，Try过程和俩阶段prepare比较相似。但TCC没有事务管理的抽象，Try、confirm、cancel和业务场景密切绑定，要考虑具体业务来实现。SATA事务模型Saga本来是为解决长事务而出现的分布式事务模型，长事务的是需要太长时间而不允许它们保持其他事务所需要的锁的事务。电商交易如果采用俩阶段提交，则订单系统的子系统要等到用户确认收货交易完成才能提交，而物流的时间一般比较长，这个时间可能需要几天。而订单系统事务可能会拖住一些资源，如用户的余额，这个锁维持几天的时间，会导致用户无法消费，这显然是不可行的。Saga是把分布式事务看做一个个单机事务的合集，对每一个单机事务A，Saga都有一个补偿事务$A^{-1}$。如果我们执行A，又执行$A^{-1}$，那么锁产生的数据库状态同A和$A^{-1}$都未执行前一样。同样都是需要业务逻辑接入，其中TCC适用于对一致性要求高、性能敏感的场景。SAGA的核心的回滚，像一个执行-如失败反向补偿的厂业务流程，适用于执行流程长，业务流程复杂的场景。体现在分布式整体上，只要我们能确认一个单机事务都执行成功，那么整个分布式事务就是成功的，可以提交。如果任意一个单机事务不成功，那么就要把它和它之前的单机事务回滚掉，但它之前的单机事务已经提交过了，无法回滚，这时候就需要执行它们的补偿事务。电商交易系统的例子可以通过设计补偿事务，把库存和用户余额加回，来实现分布式事务。分布式事务模型传奇基地交易 ：： ShardingSphere在单机数据库的基础上是心爱一个中间层（proxy），中间层基于单机事务加saga来实现分布式事务。高可用通过单机数据库的主备复制实现。如ShardingSphere-Proxy中，可以通过配置将分布式事务管理委托给Seata。当ShardingSphere-Proxy接收到一个跨多个数据库节点的事务请求时，它会将事务信息发送给Seata的全局事务协调器。全局事务协调器根据事务类型（如Base事务）和配置规则，对事务进行协调和管理。在事务执行过程中，ShardingSphere-Proxy会负责将事务操作路由到相应的数据库节点，并监控事务的执行状态。一旦事务执行完成，Seata会根据事务的执行结果，进行全局的提交或回滚操作，确保分布式事务的原子性和一致性。原生数据库：它们基于俩阶段提交实现分布式事务，不存在单机事务。比如蚂蚁的oceanbase和TIDB。SAGA生成补偿事务的思想是通用的，分布式数据库可以通过解析单机事务的SQL，从而生成逆SQL，从而生成补偿事务（比如AT模式）实现这一点要满足俩个条件要有一个标志把同一个分布式事务的所有单机事务联系起来，以便在需要执行补偿事务的时候能找到它们有的单机事务已提交，但它所在的分布式事务未提交，这时它提交的结果在分布式的角度仍处于脏数据，通常不允许其他事务对其进行读取。要单独进行处理。（通常使用分布式锁来实现）TCC的一致性比SAGA更强。SAGA是可以直接提交和直接回滚，但TCC要先try。前面介绍的俩阶段提交原型，可以看出，俩阶段提交对事物管理器的抽象天然适合封装在分布式数据库内部，这也是大部分原生数据库选择俩阶段提交的原因。俩阶段提交有一个显著的特点：事务只有在prepare阶段才会在数据行上锁，整个执行过程都是无锁的，这意味着并行的事务很有可能修改了同一行的数据。也就是说俩阶段提交是first commit win，是一种乐观事务模型（假设事务没有冲突发生）。目前一些商业的原生分布式数据库对俩阶段提交的加锁进行了改造，支持了悲观锁（即在事务执行阶段就加锁），这一步拓展原生数据库的支持能力。此外最新版本的俩阶段提交有严重的问题：协调及存在高可用问题，一旦宕机，在恢复或者新的协调器被选举出来之前，整个系统是不可用的。google的percolator事务模型对俩阶段提交问题做出了优化：把收到分布式事务请求的第一个节点作为俩阶段提交的协调者节点，一存储节点的高可用保证了协调节点的高可用，同时也不会出现些调整宕机了整个系统都不用的开启，因为任何一个节点都可以是协调者节点了。此外Percolator在事务开始时和事务提交时都会取一个时间戳并写入数据库中，这个时间戳可以很便捷的支持分布式MVCC的实现。数据库锁所是用来管理共享资源的访问的机制。在数据库中除了用户数据要上锁，还会对缓冲池中LRU列表、数据库元数据等其他资源上锁。不同数据库对锁实现差异很大。Oracle、Mysql大部分都是采用行锁设计。单机数据库的行锁会分为俩中：共享锁（S）和排它所（X），只有贡献锁之间才兼容。以mysql为例slect ... lock in share mode上的是S锁，不会阻塞后续的其他share mode。update/select... for update上的是X锁会阻塞读的操作，包括其他的share mode锁。事务中的锁还有很重要的概念，交俩阶段锁理论（2Phase lock）加锁阶段和解锁阶段是俩个独立的阶段，不能有重叠。俩阶段锁理论和事务的原子性以及隔离性关系，密切，是保证并发调度准确性的必要条件。加锁是执行阶段，解锁是提交阶段。在单机事务中大家很少考虑加锁和解锁的过程与代价。所资源默认堆所有事务是可见的，一行数据的加锁和解锁都可以看做原子操作。在分布式数据库中，数据行分布在多台机器上，因为跨节点网络传输的不可靠性，加锁和解锁不在是实时切原子的了。那么保证分布式上锁的正确性，需要在分布式事务中维持一个中心节点来记录所信息。加锁与解锁的成功和失败都以中心节点为准。在编排式SAGA中，有一个中央协调者（Saga协调器）负责管理和控制整个事务的执行流程。协调者按照预定义的顺序依次触发每个本地事务，并在事务失败后处理补偿事务。这种方式逻辑清晰、易于管理，但存在单点故障风险。而在协同式SAGA中，没有中央协调者，各个服务通过事件驱动的方式进行协调。每个服务自己决定何时开始下一个本地事务，通过订阅和发布事件来触发后续操作。这种方式去中心化、服务间耦合度低，但事务流程相对复杂，难以追踪。SAGA：独立中心节点俩阶段提交：协调者节点任何情况下出现了中心节点就要考虑高可用，通常使用共识算法来实现对于锁表和协调者的高可用性。Percolator直接把俩阶段提交的协调者放在了分布式事务的一个随机的数据节点，把协调者的高可用问题转换成了数据节点高可用问题。分布式锁通常只有X锁，因为实现分布式锁的代价本来就很大，如果还要实现分布式S锁就会增加非常多的维护和调度代价，并且S锁的使用本来就很少，因此一般没有实现分布式S锁的方案。对于select ... lock in share mode语句分布式数据库一般不支持（原生分布式数据库）或选择只在单机节点上S锁。隔离级别现在大部分关系型数据库都是基于MVCC的，要引入一个针对快照的新的隔离级别。SI（snapshot Isilation，SI）SI隔离级别会去读书屋开始时间点的数据快照，从而避免不可重复读，但又不像用锁实现的可重复读隔离级别那样要阻塞写。（如果始终读最新的快照，则相当于RC，但我们将SI，一般是事务开始的时候的快照）SI和RR的区别就是幻读和排序写。我们把点查询成为item查询，非点查询（范围聚合等），称为predicate查询因此我们可以把幻读定义为不可重复读的predicate版本。幻读和不可重复读都需要在一次事务中进行俩次读操作。不可重复读指的是俩次item查询到了不同的内容，而幻读指的是俩次predicate查询到了不同的结果。
X-Engine背景笔记来自 https://www.bilibili.com/video/BV1rS4y1N7YKX-Engine是阿里云数据库PolarDB的OLTP存储引擎（基于Mysql），主要针对电商 平台的工作负载开发，双11期间的工作负载有以下特征。活动开始时每秒交易量激增（TPS）称之为海啸问题（The tsunami problem）海啸问题：双十一零点时的TPS增加到原来的122倍，在2018年双十一的最高峰时间段，每秒钟同事进行491000笔交易，这意味着数据库同时在处理的事务达到了七千万，阿里团队希望这样的压力下依旧能维持稳定的响应时间。我们可以看到蓝色的线在红色的线夸张的涨幅下，仍旧维持了一个相对稳定的表现。缓存（Buffer）很快会被大量数据填满，我们称之为泄洪问题（the flood discharge problem）泄洪问题：随着写入量的迅速增加，存储引擎的内存缓存会被大量数据迅速填满。这时，我们就需要对新增的数据进行泄洪，也就是尽快把数据转移到持久化内存中。这也意味着我们需要一个写入能力很强的存储结构。随着促销活动的转变，数据的冷热会发生迅速的切换，称之为访问热点急速变化问题（The fast-moving current problem）数据访问局部性是缓存能够生效的关键，但是双十一中大量的整点秒杀活动，会让一些非常冷的数据变成热点数据。这时候一般数据库的存储引擎很难对这种快速的切换做出反应。从而造成缓存命中率的大幅度下降。X-Engine就是需要能够快速从持久化存储中取出新的热点数据，并且放到缓存中来解决这个问题。访问热点急速变化问题：双十一会有各种促销活动，比如整点秒杀（seckill）活动，会使当前数据的冷热急速变化。此时数据引擎需要对数据热点的变更做出反应，快速持久化存储中取出新的热点数据。LSM因为电商业务涉及到大量数据的插入和修改，所以X-Engine采用了有杰出性能的LSM-Tree。其写入的操作不做原地更新，而是以追加的方式写入内存。每一次写到一定程度，即冻结一层，写入持久化存储。一条数据->写入memtable->flush到持久化存储->经compaction操作进入持久化存储的更下层->覆盖同意key的老版本数据/同一key的新数据到来时丢弃。真正删除老数据是在后台的compaction（合并）过程中完成的。当多个SSTable文件合并时，系统和会保留最新版本的数据，删除旧版本的数据和墓碑标记，从而释放磁盘空间。compaction操作不断地把相邻的层次数据合并，并写入更低的层次。合并的过程实际上是吧相邻俩层数据读出，按key排序，想通的key之保留更新的版本。LSM-Tree的特点是写强而读弱，我们可以简单理解为LSM-Tree的写入能力比B+ Tree搞一个数量级，读能力弱一个数量级。这是因为LSM-Tree的数据可能存在多个版本。PceanBase和Tidb底层都是用的LSM-Tree。整体架构图中上面的数据方方框就是内存，下面的数据方框就是磁盘。内存中的数据都是红色的，表示热数据，橙色表示温数据，浅黄色表示冷数据。越热的数据会越往上层放。写入：写入中x-engine会和其他数据库一样做一个redo log落盘操作。然后把数据写在active memtable里面。这里是一个脏页的概念，一个active memtable写满后，他会变成一个Immutable memtable。这时候Memtable就不会做改变了，Immutable memtable 会等待一个Flash操作，进入磁盘中变成持久化存储。持久化存储越上面就是越昂贵的磁盘。比如最上面是NVMe，下层是SSD，下层是HDD。磁盘的价格是由贵到便宜，价格也是由高到底。下层之后就是依次往下合并变成一个冷数据。读取：首先我们要读取磁盘里面的active memtable和immutable memtable。X-Engine总体可以分为内存中的热数据层和持久化存储的 温、冷数据层。内存中有active memtable和多个Immutable memtable以及Read Cache和Index。硬盘中的数据分为多层，不同层的数据通过不同的存储设备存储，每一层数据以Extent为单位组织。X-Engine通过MVCC和2PL（二阶段锁）实现了SI（Snapshot Isolation 快照隔离）和RC隔离级别。SI的核心特点是：事务启动时获取一个数据库快照，该事物的所有操作都基于这个快照，不会看到其他事物的修改。提交时，只有当机遇该快照的任何并发修改与该事物的修改没有冲突时才会成功提交。SI避免了ANSI SQL-92标准定义的三种并发异常：脏读、不可重复读、幻读。读操作不会被阻塞，对于读多些少的应用场景性能表现优异。以mysql为例，有四个标准的隔离级别：读未提交，读已提交、可重复读、串行读。其中可重复读是默认隔离级别。SI是一种实现机制，mysql在可重复读隔离级别下，通过MVCC实现了快照隔离的特性，具体来说，事务启动时会创建一个一致性快照，事务内的所有读操作都基于这个快照，不会看到其他事务提交的修改，从而保证了可重复读。海啸问题面对海啸问题，一个常见的思路是增加服务器的数量，横向扩展服务器集群。但这个方案在双十一场景下有俩个问题：一是成本太高，双十一零点时TPS会激增122倍，服务器数量不可能也增加这么多倍。而是增加服务器的效果也不会很高，因为海啸问题面对的主要是写和读的混合压力，读压力比较容易扩展，写压力很难扩展，增加机器也不能很好的散开写压力。各个阶段还是要提高CPU、线程、内存、IO等资源的利用率，在数据引擎层面提供更高的事务并发和吞吐量，来加快流转效率，避免堆积。X-Engine主要采用了俩个措施来解决海啸问题，一个是交易的异步写入，第二个是多阶段生产线。交易异步写入我们把事务分为执行阶段和提交阶段。执行阶段：查看要更新的数据是否在buffer pool中如果不在的话，读取到buffer pool中生成redo log修改数据页提交阶段把redo log写到log buffer中把log buffer中的log落盘把数据也放入active memtable中，表示可查返回提交成功。这就是我们常说的write ahead log（WAL）操作，redo log落盘意味着事务完成了持久化。但是我们还需要做一个操作，把数据爷放到active memtable中，表示事务已经完成了可以被查到。为了实现简单，大部分存储引擎，比如innodb，都会采用一个事务一条线程的方法，这种方法写入日志IO存在长时间等待。X-Engine首先把任务分成了多种无锁写入队列。此后，大部分线程可以异步返回并处理其他交易，每个队列今流一个线程来参加多阶段流水线提交写入任务。为什么要这样节省线程？通常IO阶段需要线程等待较长的时间。因此我们可以执行到提交阶段后，线程就去干自己的事情。每个队列留一个线程执行提交写入任务就ok了。在抄告并发情况下，机器线程数也是一个限制。交易的一部写入避免了线程等待IO，可以增加线程的流转效率，从而减少甚至避免用户事务等待分配线程的情况。 redo log落盘的动作一定是要有序的。队列这种数据结构，先进先出，天然保证有序。但多个队列之间的顺序如何保证呢？在执行阶段或者说读写阶段，我们还是一个事务一条线程来执行的。但是到提交阶段就分成了多个写入者。然后再进入了多条无锁写入队列里面，等待去进行多阶段流水线的提交过程。那么多个写入队列的顺序如何保证呢，猜想分库或分用户，反正就是在业务层面确保写入的不相干。也可能是，一次只有一个队列写入，队列间流转。经过验证在32核的时候，每个队列分配8个线程是表现最优的。多阶段生产线提交阶段分为四个独立的更细的阶段X-Engine为了进一步提高事务处理的吞吐，在事务Group Commit的基础上，采用了一种流水线技术。通过合理配置这四个阶段的线程数，来减少或避免对资源（如CPU、内存、IO）的等待时间从而实现，最大吞吐量。也就是避免有的阶段IO利用率高，CPU利用率低，而有的阶段则相反。有些对多阶段生产线的解读是：事务到了提交阶段后，就可以自由选择执行流水线任意一个阶段。这样事务提交的四个阶段就可以并行起来。我认为这样是不正确的，因为这四个阶段顺序并不能颠倒X-Engine分别限制了每个阶段的线程数。因为前俩个阶段数据和罗技的强相关新，复用第一第二个线程可以提高内存和磁盘的利用率，统一时间之允许一个线程分别执行第一第二阶段time图中只有a线程执行1,2阶段.其他b,c,d线程争抢完成1,2阶段的任务。图中的x箭头可能是不合理的，因为按照文中的描述，不应该会有一个线程在执行完第三个阶段之后去执行第二个阶段。测试部分论文的测试主要针对mysql的三个存储引擎，Innodb，rocksdb，还有X-engine进行了横向对比。因为海啸问题主要关注存储引擎的巅峰吞吐量。所以说这个测试主要是对JV接口的一个吞吐量的测试。因为Innodb没有KV接口，所以没有列入比较，因为B+相对于X-engine写入量肯定是非常弱的。（右上角）左下角中测试交易异步写入的作用和配置多少线程数比较合适。其中紫色，粉色，橙色和绿色是异步写入，只有线程数的差别。下面重合的三条都是同步写入。可以看到哪怕同步写入的线程数配置的再多也影响不了吞吐量。而异步的。所以X-engine选择了每个队列八条线程的方式来进行异步写入。泄洪问题面对泄洪问题，大促的时候瞬时的写压力向洪水一样冲击内存，内存肯定是撑不住的，要快速的把内存中的数据向下层存储转移。这个问题在一般的系统中，DBA除了增大缓冲池，没有很好的解决方法。但是在X-Engine中，数据的向下转移表现为immutable memtable存储到硬盘和硬盘中LVM-Tree的操作。然而这里硬盘中的LSM-Tree的compaction操作依旧是一个硬伤。所以X-Engine主要通过优化compaction操作来解决泄洪问题。X-engine设计了多层存储结构。第0层的快速FlushImmutable memtable的数据会直接flush到L0层，所以L0层的数据是乱序的。那么在查找L0时，就要扫描整个L0层，这个代价是比较大的，会消耗很多IO。如果没有任何处理（所以L0层理的数据就是一个乱序的状态），那么L0层的数据会见到一定程度后直接和L1层合并。会造成大量的重复（冗余）的温数据进入更深层。尽管L0层可能只占珍格格持久化层的百分之一都不到。但他的数据是从刚刚immutable memtable中的flash下来的，仅仅比最近添加到memtable中的数据老一点点。根据电子商务的抢时间局部性原则，L0的数据是极有可能再次被使用到的。所以说X-Engine吧L0层定义为了一个温数据层。所以X-Engine引入了intra-L0 compaction，即只针对L0进行compaction。就是把L0层数据仅一个单独的合并操作，并排序去重，并且不写入下一层（原样写入L0层）。因为这部分数据很小，损耗也少，我们可以经常进行这个操作。这不操作可以保证L0的温数据不会向下转移的同时，高效率降低成本（因为L0的数据很少，所以这步操作的损耗很小。数据复用对于非L0层的compaction，X-engine主要做了三个方面的优化L0的数据达到阈值后，就会和L1层进行一个compaction操作向更下层去转移。data reuse：对于没有重叠的快，不进行merge 而只改变变meta。可以从三个粒度进行reuse，没有重叠的extent可以reuse，没有重叠的data block可以reuse，data block可以被拆分来促成reuse。extent就是X-Engine中的数据块，每个数据块是2MB，每一层都有许多元数据索引，指向数据块，然后他们一起再去构成一个metadata snapshot，一个元数据的快照。它指向所有的数据构成一个全局的索引。这个时候我们进行一个compaction操作，这是compaction操作后的结果。对于0层，即可用复用的extent，我们并不需要在磁盘上把它拷贝到level1层，而是可以直接修改meta index。然后生成一个全局的元数据快照即可。extent级别的复用并不需要在磁盘上覆盖extent，而是直接修改metadata index。而data block的复用只能拷贝，即便如此也可以节省大量CPU。绿色的块表示extent可以直接复用，紫红色表示extent需要进行分割，来支持更细力度的复用，黄色的块表示extent需要进行一个copy操作.图中L1层和L2层要进行compaction操作，compaction操作的结果被放到L2中。如果没有数据复用，compaction操作就会取出L1，L2的所有数据按key排序，key相同的则merge，即L1，L2的所有块都是红色。使用 data reuse的情况下，只有部分重叠的块会merge，Data Reuse会按三级粒度进行compaction。extent粒度：L1的[210,280]和L2的[50,70]，都是俩层没有发生重合的部分，可以直接复用。即只改变元数据索引即可data block粒度：L1的[1,35]和L2的[1,30]块重叠了。然而，重叠的仅仅是[1,25]这部分data block。所以[32,35]这部分 data block可以复用。拆分data block 粒度：L1的[80,200]和L2的多个extent重叠了。然而，这个data block的key是很稀疏的，可以看到没有在135和180之间的key。那么就可以将其拆分为[106,135][180,200]俩个data block，然后将他们和L2的[100,130][190,205]块合并，L2的[150,170]块则可以直接复用。Extent级别的复用不需要在磁盘上拷贝覆盖extent，而是直接修改meta index。而data block的复用只能拷贝，即便如此也可节省大量的CPU。对于数据复用的过程是在朱行迭代的过程中完成的，不过这种精细的数据复用带来的一个副作用，即数据的碎片化，所以在实际的操作的过程中也需要根据实际情况进行折中。这种精细的数据复用带来的弊端是，数据的碎片化有可能会消耗我们查询时候更多的计算资源。异步IOX-Engine将compaction分成Read-Merge-Write三个阶段，通过实现异步IO，来提升效率。在Extent层次，一个compaction操作包含三个独立的阶段从持久化存储中取出俩个extent合并把合并的extent写入持久化存储其中1,3俩步都是IO操作，2啧是计算铭感的操作。X-engine在1,3使用异步IO请求，2作为1的回调函数来执行。当多个compaction操作并发执行时，2会被其他步骤覆盖来隐藏IO。FPGA offloading将compaction offload到FPGA中执行，从而降低了Compaction对CPU的资源消耗。随着IO性能的不断提高，很多传统的一IO为瓶颈的设计的数据库算法主键转变为计算资源的限制；反之亦然。阿里团队发现LSM-Tree存储引擎中的compaction操作正是由IO瓶颈转换为计算瓶颈的例子。所有对compaction的操作都放在一个优先级队列里。一个具有频繁删除操作的案例中，对删除的compaction放在最高优先级，其他的compaction由上到下优先级依次递减。删除案例是案例的一个实例，每当要被删除的记录数达到阈值，就会触发一次针对删除这些记录的compaction操作。而且这个compaction操作是最高优先级的，为了防止垃圾数据对存储空间的浪费。（查看源码，实际上X-Engine定制化了一个专用于删除的compaction，作为一个参数传入的compaction函数。）实验解决泄洪问题主要是对compaction的优化。FPGA提升了27%的吞吐量并且大大提升了稳定性。电子上午的热点数据很集中，data reuse在记录重复率搞的情况下效果非常好。访问热点急速变化结构面对访问热点急速变化问题，通常DBA是没有任何优化方法的，数据突然变热到数据完全进入缓存的期间，必然出现响应时间的上涨。访问热点急速变化是一个纯粹的读方面问题，是LSM-Tree的弱项，因此要对整个读方法进行优化。X-Engine对数据块、索引、缓存进行了一系列定制化的设计，来保证读效率。对于LSM-Tree中影响非常大的compaction操作，X-Engine还涉及了增量缓存替换来减少其对缓存命中的影响。Extent和其他LST-Tree的SSD，sorted string table非常像。在电子商务中存在非常多更新DDL的操作，比如最常见的新增栏位。在有了schema中的这个version之后，我们可以在新增栏位的时候不需要去修改每个老extent中的schemadata block 以行的形式存储数据schema中存储的是各个column的属性index存储每个data block的偏移量scheme带有一个version，为了在更新scheme的时候不需要修改旧数据。每个extent 2MB，每个Data block约16KBextent越小，就越容易调度和复用，但管理成本也会随之上升。设为2MB，是综合考虑compation中数据复用和后面要介绍的增量缓存替换的最优解。X-Engine的每层都划分了固定大小的Extent，存放每层数据中连续片段（key Range）。为了快速定位extent，为每层建立了一套索引（Meta Index），所有这些索引加上所有的memory table（active immutable）一起组成了一个元数据树，root节点为metadata snapshotX-engine中除了当前正在写入的active memtable以外，其他结构都是只读的，不会被修改。X-engine的所有读都是以快照的结构为入口。优化缓存X-Engine针对但记录查询引入了Row Cache，在所有持久化的层次数据上做了一个缓存，在memory table中没有命中的单行查询，在Row cache中也会被捕获。Row Cache负责单行查询，Block Cache负责 Row cache的漏网之鱼。俩类缓存在不同的维度上面劲量的去保证数据的命中率，着重保证单行数据查询。多版本元数据索引X-Engine的meta Index用来记录LSM tree结构的变化。LSM-Tree中每个subtable都有meta index，它起始于一个根节点，并在每次更新后创建新的节点。如右图L0的extenti，它对应meta snapshotv，当extenti被compaction之后创建新的meta snapshotv+1，snapshotv+1只需要指向原来的extenti而不需要产生实际的I/O（extenti的位置也不需要改变），同时cache的数据也不需要变化。同时这样的copy on write结构使得事务可以访问任意版本的数据，避免了锁的开销。X-Engine中有GC机制类清理过期的snapshot。增量缓存替换X-Engine的增量缓存替换降低compaction对cache的影响。原LSM-Tree中，当SST发生compactio时，对应内存中的数据会失效，造成突然的Cache missX-engine的增量缓存替换会在compaction的时候检查一个block是否被cache，如果是，则将chache中的内容替换为merge之后的block，可以有效缓解compaction 对cache命中率带来的影响。多版本memtableX-Engine对memtable做了一点简单的优化。未优化时，如果多次更新同一个key，那么这个key会以<key,sequence_number>的形式存在memtable中存储，如果要查找最新的key，可能需要读取多个旧值。X-Engine中所有内存数据结构是一个跳表并且不进行整理，因此多次频繁更新同一个key的话，那么这个key会存在多个版本的数据，虽然查找内存中的数据是非常快的，但是存在多个版本数据的时候我们可能依旧要的是读到多个旧值。X-Engine的multi-version memtable会将同一个key的不同版本单独链起来。这样skiplist中就不会出现一个key的多个版本，同一个key的多个版本按照旧组织排序，最新的key可以被最快访问到。总结范围查找X-engine是要弱于Innodb的，所以选用LSM-Tree放弃范围查找的部分性能是X-Engine的可以接受的折中方案。
Linux socketsockethttps://www.bilibili.com/video/BV1VWtyeVEsVhttps://blog.valiantcheng.com/misc/socket-intro.html如果发送数据包要从HTTP到数据链路封包全部构建一遍，这样的操作成本无疑是非常高的。操作系统的构建者为我们提供了很好的支持，他们屏蔽了底层的细节，抽象出一个统一的网络操作接口。 来便于上层用户使用网络。这个统一的接口就是socket。socket直译是插槽，我们只需关心如何插入，而不需要关心内部的实现。socket是一套抽象接口体系，可以理解为一套使用协议或者是一套API。因为是操作系统聪明封装提供的机制，因此具体使用需要以系统调用的形式来实现。socket接口提供了非常多种类的socket，没种都有其使用场景。这是所有socket操作的第一步，create socket。getsocket和setsocket相对于查看获取和设置socket选项。很多和socket交互的细节都通过这个方法来进行控制。接下来是bind，绑定操作，相当于把电器插头插入插槽。也就是将机器上的某个IP地址和端口组合进行绑定。其他操作者无法使用这个组合，时一种声明网络所有权的操作类型。listen传输层语义的监听操作，被动等待某个其他的网络实体向自身（bind过的IP和端口组和）发起通讯（通常是connect操作）accept，传输层的确认操作：确认某个尝试建立连接的网络实体和自身之间的关系。一旦accept正式的传输就已经建立，可以开始后续的数据交互connect：传输层语义的连接操作，连接某个传输层实体（也就是协议+IP+端口号）协议可能是TCP、UDP或其他四层协议（对于TCP就是经典的三次握手过程）shutdown、close：传输层语义的关闭操作send、sendto：传输层语义的发送操作recvfrom：传输层语义的接收操作上述系统调用相当多都是传输层的，这说明socket很大一部分功能是提供四层接口、也就是传输层网络之上的接口。但是并非所有操作都是四层的。这些是常见的socket类型。socket逐渐从网络通信层面发展演变成了一个数据通信操作的标准接口体系。对大部分开发者来说有许多我们常用TCP的选项，如SOL_SOCKET，SO_REUSEADDR其他类型的socket也可以设置很多针对性的选项，比如广播和多播的可设置选项就非常多TCP常见场景机器正常下线哪怕是kill -9操作系统也会自动释放tcp连接。如果此时已经建立连接，正在写入数据，会收到EOF相关字样的报错如果还未成功收到连接会收到connection refused类报错连接被拒绝了。正常情况出现在对端机器正常，但对应的服务已经挂掉了，这种情况下收到了发向不可用服务短口的数据，这是宿主机就会为不可用的服务进程对应socket链接发送一个RST（reset）数据包通知对端本地服务不存在或终止了。机器异常下线如果机器网线被拉断了。由于对端服务所在的机器对我们来说已经不可用了。所以此时不会有任何响应发回。此时发送端会按照socket选项的默认配置，也就是keepAlive以及timeout相关的socket选项，进行发送的等待和重试。如果超过一定的发送次数和时间，会报错并中断连接。在 不设置socket timeout选项的情况下，发送后等待的默认重传次数一般是15次，时间大概是900秒左右。每次重试的中间间隔会依次按照指数退避算法进行而不是固定的重试频率。如果在日常遇到了这样的时间间隔，要足够敏感。如果想要尽快失败，可以调整内核参数tcp_retries2来修改这里的行为。这种情况下报错分为俩种情况，如果路由器没有替代应答本地会直接报timeout错误，如果路由器替代应答，会发回一个ICMP包，告知destination is unreachable，那么我们最终收到的是unreachable类的错误。如果在这个过程中机器又恢复了，恢复的机器后已经丢失了原先的信息（可能是被强制断电然后重启）因此会直接发送reset包。告知我们对端的机器拒绝接收当前发起或正在进行的连接。类似进程挂掉的情况。UDP对端不可用一般来讲默认的UDP通信在对端服务故障、不存在或丢包时是会无限阻塞住的。所以一般底层库都是会提供默认的超时值设置的。比如DNS解析是2S，如果没有，在编程时要注意自己控制超时。UDP发送的数据包目的端口被对端判断为无效（目标机器上没有这个端口对应的服务）或是其他不可达场景，对端通常会回复ICMP错误消息（不回复RST是因为UDP协议没有RST报文）。类似我们在上一部分提到的路由器代答错误。UDP本身可以不调用connect方法直接发送数据的，这一点和TCP有本质上的差异。所以机器上不会有连接信息。UDP sento判定标准是只要数据从缓冲区发送出去了，这个操作就是成功的，它不会管数据是否返回或者有报错信息。因此有ICMP返回的化，原来的UDP是接受不到的（这被称为一步ICMP错误问题）。因此要解决这类问题通常需要通过一个守护进程来代为接受ICMP包通知，或者是UDP发送数据前都确保了connect再进行后续其他操作。通过socket发送的数据被机器内部或外部设置的防火墙规则拦截了，如果本地网络有网络过滤处理，比如ipvs，iptable等可能会收到EPERM或Operation not permitted类报错。遇到这一类报错要注意很可能是本地协议栈中的的netfilter框架drop掉了我们的数据包。如果是外部防火墙，有俩种可能一种是直接丢包，这时我们感觉就像是对方机器挂了一样。还有一种是发送reset包拒绝我们的连接发起。
Docker与K8s笔记https://www.bilibili.com/video/BV13GmDY9EtVDocker问题在容器之类的技术出现前，用户直接将程序部署到物理机上运行。主要用ystemd类的守护程序管理业务程序。这种方式可以很方便的查看每个业务程序的运行效率，并进行手动自动化操作。但是很多时候程序可能伴随着各种依赖。比如动态链接库某个命令行工具第三方依赖特殊配置文件等在多台机器规模化的情况下，通过下发部署脚本来实现。然而业务程序的依赖是复杂容易变动的。同一个程序的多个版本的依赖可能是不同的。我们还要管理多个程序在同一个服务器上运行的情况，程序之间的依赖可能产生冲突。最简单的方式就是每个程序独占一个机器。当时虚拟机技术发展已经较为成熟了。这样做的本质就是把程序放在虚拟机中，但虚拟机过于庞大，启停速度过慢，虚拟化性能损耗大。解决方案镜像大小虚拟机之所以那么大，是因为存储了操作系统运行所需要的所有文件。对于同一系列操作系统的不同版本来说，往往存在大量相同的文件，比如动态链接库，内核等等。如果相同的文件只存一份就可以大大减少镜像大小。如果多个虚拟机同时修改文件怎么办，那么就拷贝一个文件副本给新的镜像。其实就是copy-on-write的思想。同样，物理机和虚拟机上也存在大量重复的文件。因此这个优化思路不仅限于虚拟机，也适用于物理机和部署在其上的镜像。该思想实现的具体技术就是UnionFS或UFS，在容器出现之前的2004年，这个技术就已经出现了。它的初衷是希望在多个文件系统上提供一个统一的文件系统视图。启动速度虚拟机启动慢因为把珍格格操作系统的流程都包含了进去。理论上如果我们只关心程序运行本身的化 ，启停是不需要的。因此就可以去掉操作系统的启停。因此必须要实现一个轻量化的虚拟机，把操作系统相关的启停开销去掉。Linux就是在这样的背景下，逐渐发展出了实现上述需求的技术。namespace和cgroup。要实现一个程序的隔离，主要是以下方面。文件系统进程，线程管理进程线程通信网络用户权限硬件资源使用如果一个运行的程序在以上几方面都有自己的转述隔离空间和配额。那么实际上就实现了我们所说的轻量化隔离目标。这也就可以称为容器了。我们把程序放在容器中运行，保持隔离的前提下，只运行程序本身。那么其启动速度显然会比虚拟机快很多，这就满足了我们对隔离后启停速度的要求。namespace和cgroup。在2008年基本发展成型。这早于docker的出现。Namespace和Cgroup是Linux内核提供的两项关键技术，它们共同构成了容器技术的基石。简单来说，Namespace主要负责提供隔离性，为进程创建一个独立的运行环境；而Cgroup主要负责提供限制性，对进程组可以使用的资源进行约束和管理这样我们解耦了操作系统本身冗余的部分，而只关注进程本身的启停。这样容器的速度就和进程本身没什么不同了。性能损耗虚拟机是一个完整的操作系统，例如linux有很多内核进程来协助内核做系统管理工作。如果有多个内核，每个内核都会有自己的一套内核管理进程运行。从整体的角度来看，这些重复工作的进程就是额外损耗。容器隔离相关的技术就解决了这个问题。因为本质上所有容器内部的进程都是直接使用共用内核的，不需要维护独立内核。此外，硬件损耗也是一部分，早期虚拟化技术对于硬件的损耗较大，不过随着虚拟化技术的发展，CPU，内存已经被降到很低了。但是GPU io设备的损耗依然存在。最后docker就是把上述方案都打包到一起，并提供了一个用户友好的使用界面的系统。Docker依赖容器基础技术，UFS，和轻量化隔离能力。在此之上，docker设计了容器镜像和运行的标准,提供了完整的易用工具。让程序和依赖进行绑定，作为独立单元来进行管理。docker的命名是集装箱，很符合其实现的功能。即软件的标准化交付，将程序本身和依赖打包为一个标准单元。外部的使用者不需要关心docker镜像中到底有什么。K8s简介在docker诞生和流行后，带来了相当大的技术红利。随着docker被大规模用于生产实践。单机上的容器可以使用docker很轻松的进行管理，但有一定规模的企业往往会有很多个应用，很多台机器。一旦应用机器的数量急剧增长。管理这些容器就变得非常麻烦了。如果没有任何手段，那么就只能编写运维脚本，然后批量下发到每台机器进行管理了。这种方案操作效率低：大规模重复的劳动，人为容易出错缺失全局记录信息：部署后无法感知多个机器的运行情况，需要自己建设一个系统来进行监视精细化控制成本高：比如实现一组应用程序受控分批逐步升降级、根据资源使用针对应用程序所申请的各类计算资源进行扩缩容等调整，一台机器宕机后对上面运行的应用程序进行恢复故障转移等。难以进行高效的资源管理使用，分配不高效。服务难以高效管理和治理：应用服务如何在大规模之间高效的互相感知协作。我们更多的将k8s叫做容器编排系统而不是管控系统。不管理实现细节。K8s是一个面向终态的系统。例如空调冰箱关注对象的温度达到指定值，否则会一直改变温度来尝试达到指定值。面向中台的关键就在于让控制逻辑感知到某种状态（现状），然后根据状态调整现状，达到目标状态。而目标状态也不是一成不变的。问题解决K8s要真正解决的问题是：大规容器化程序应用在大规模机器集群内的高效部署管理问题。其中部署挂历可以分为操作目标状态和最终目的三部分通过操作来改变目标状态实现目的。K8s将达成目标状态的操作自动化。声明式API是一种现代编程和系统设计范式，其核心思想是用户只需定义期望的系统目标状态，而不必关心实现该状态的具体步骤。系统会自动负责将当前状态调整到期望状态。这种模式与强调逐步执行命令的命令式API形成鲜明对比这种面向终态的思想有一个行业内的专业术语叫做 声明式API。k8s中使用的yml就是我们能直接看到的体现，我们把对yml写入终态，k8s就能帮我们自动实现，所以这里写yaml就好像变成了调API一样。我们只需要声明一下就可以达成效果。业内k8s工程师也经常被调侃为yml工程师。有了面向终态的思想带来了以下好处自动化、标准化操作流程：如重启升级等操作，基本操作流程都是不变的，会变的只是外部参数版本号。消除了人工介入的成本天然重试机制：面向终态带来了一个结果就是重试，比如进行某个操作时出现了偶然的出错，程序就可以重试来最终达成目标状态。全局状态记录：面向终态要时刻比较当下和目标状态的差异，因此对当下目标状态信息的记录成为了必要条件。所有的机器的信息都在管理机构中统一保存（ETCD）降低门槛：由于所有的操作都被自动化标准化了，运维人员的关注点从关注过程变成了关注结果。接下来就是剩下的俩个问题难以进行高效的资源管理使用，分配不高效。服务难以高效管理和治理：应用服务如何在大规模之间高效的互相感知协作。K8s解决资源分配调度问题进程线程调度，CDN网络流量，物流中多地仓库，内存管理或GC都可以试做调度问题：资源如何分配能达成某些条件下的最优效果。这个最优可能是全局最优或者局部最优。k8s面对的调度场景就是：如何将多个具备不同特点和规格的应用程序，安置到由多个不同特点和规格的机器所组成的集群内才能达成最高的资源利用率.一般来说资源录用率往往和服务质量（如实时性）是不可兼得的。一般都是在俩者之间做取舍。如果大部分调度对象对执行时间有较为严格的要求，调度侧重点就会变成平均时间开销，而不是资源录用率。k8s提供了一个通用的调度框架，帮使用者实现不同的调度需求目标。这里先介绍默认的调度策略。调度最重要的过程是过滤和打分过滤阶段调度器会将所有满足pod调度需求的节点筛选出来，过滤函数会检查所有候选节点的可用资源是否满足pod要求。在过滤之后得出一个节点列表，里面包含所有可调度的节点。通常情况下这个列表不止一个节点，列表为空则不可调度。在打分阶段调度器会根据当前启用的打分规则对调度列表中的每个节点进行打分。最终得到一个得分最高最合适的节点，如果存在多个得分一样的节点，调度器会随机选择一个。因此我们可以将调度理解为打分。打分结果是由多种策略加权求和得来的。K8s1.30默认策略包括（括号内是权重，以下分数为**加权求和后计算）Kubernetes调度器中“加权”的“权”主要来源于三个层面：Kubernetes项目内置的默认权重、管理员通过配置文件显式设置的权重，以及Pod配置中声明的权重。在 Kubernetes 中，污点是应用于节点（Node）上的一种特殊标记，它的核心作用是 “排斥” Pod。你可以把它想象成节点设立的一个“门禁”规则，明确告知调度器：“只有携带特定通行证（即容忍度）的 Pod，才能被我接纳。污点容忍情况（3）：节点打上了污点后，除非容器显式声明容忍，否则都不会调度到污点节点上。节点亲和性情况（2）：容器组声明的更倾向于希望所处的机器节点的条件可用资源情况（1）：节点上可供使用的计算资源的情况容器组拓扑分布情况（2）：相同的容器组希望或不希望出现在同一类机器节点上。比如希望在不同机房上分散开容器组亲和性情况（2）某些容器组希望或不希望处于同一或不同的节点节点资源分配情况（1）：节点当前已经分配出自愿的情况节点上存在镜像的情况（1）：机器是否有需要的容器镜像了（不需要重新下载拉取镜像）其中1,2,4,5可以分为一类，它们都是用户主动指定的调度偏好。即我想让这些应用运行在哪些地方，这里都给了相对较高的权重。因此K8s的默认策略是更照顾用户的主观需求的。3,6,7这三个条件则是客观资源条件。即吧应用放在哪里可以达成最好的资源录用率。这些权重是比前一种主观性要求低的。这些是默认策略，如果有具体需求，这些调度策略，权重，甚至是计算方法都是可以用户完全自定义的。例如一般的调度策略仅会将CPU和内存作为计算资源考量，事实上，除此之外的磁盘，网卡，GPU，各类设备硬件都可能成为调度对象。服务管理治理问题微服务在k8s火的时间也非常流行。俩者的理念模式存在非常多的相同点。微服务核心是把庞大的单体服务拆分成多个独立灵活小巧的微型服务。在拆分完服务之后，多个微服务的部署管理治理都变得更加复杂和棘手。而容器和k8s技术恰恰能够帮助解决这些问题。以下是微服务相关的技术栈配置中心k8s提供了俩类存在于集群中的资源ConfigMap和secret来实现配置的管理，前者用于保存配置数据，后者用于保存敏感数据。所有需要使用配置的容器化应用都可以通过挂在的方式，讲一个或多个configmap、secret放到与文件中，实现应用对配置的感知，同时多个实例也可以挂在同一个configmap、secret。用户对于configmap以及secret的修改也会实时的同步到挂载这些对象的应用实例上。这样k8s就实现了对服务配置的统一管理。注册中心、服务发现K8s可以将某个服务的一组实例抽象成一类集群中的资源。通过service来进行管理，service作为集群资源，会被保存到k8s的全局记录中，这样可以通过K8s API轻易获取集群中存在哪些可访问的应用。不同的服务间可以通过某个特定的Service，其具备固定的域名和虚拟IP，称为ClusterIP来实现互访，而无需感知实际要访问哪一个地址。负载均衡在上一层service上 k8s有一个名为kube-proxy的组件，通过os内核提供的（iptable和ipvs）实现了应用在发起端的负载均衡。这样当访问某个Service，流量基本能够均匀按照要求分布在服务的多个实例副本之间。实现负载均衡网关K8s抽象了Ingress ，getway等资源来一声明的方式提供网关实例。K8s自身没有强制绑定某一个网关的实现，而是定义il网管需要支持的基本语义规范（协议、接口）来提供给用户使用 。可以根据具体需求选择网管来进行使用。RPC由于RPC是一个和语言密切相关的操作，K8s没有提供具体的Rpc框架，K8s不强制绑定某个实现限流和熔断也是在网管和RPC层进行实现。总结K8s对应springcloud提供的能力，K8s均做了对应的实现。无法实现的提供了接口进行嵌入适配。k8s因为语言中立带来了普适性，以及面向协议，接口兼容的扩展性。应用程序应当且仅需管理应用程序自身。应用程序开发者应该更专注于业务程序本身 。
复制、容错原子存储翻译自：Replicated/Fault-tolerant atomic storage零基础入门分布式系统 7.2 Linearizability-腾讯云开发者社区-腾讯云云计算设计在这些日子里展示了对复制容灾的喜爱。例如在在数据中心级别进行赋值存储的是GFS，Dynamo，Cassandra。在广域网级别有PNUTS，COPS和Walter。我一直在寻找这个主题的基础分布式算法, 发现了在复制原子存储的很好的论文: Reconfiguring Replicated Atomic Storage: A Tutorial, M. K. Aguilera, I. Keidar, D. Malkhi, J-P Martin, and A. Shraer, 2010.复制提供了对崩溃故障的屏蔽.然而这是一个有限的容错能力,除非你重新配置存储服务拉埃添加新的副本替换掉崩溃的节点.事实证明,由于设计并发性和容错性问题,复制存储服务的动态重新配置是一个微妙/复杂的问题. MSR@Slicon Valley的这个团队已经研究复制存储中的重新配置问题一段时间了。但是在这篇文章中我不会谈论重配置工作，只会关注，复制、容错原子存储部分。多数复制算法这是一个用于复制容错原子存储的优雅算法，我认为每一个分布式系统的学者和开发者都应该知道。他简单强大并且有趣。我承诺你学习这个多数复制算法后大脑中会感觉良好。这个原算法发表在 Sharing memory robustly in message-passing systems, H. Attiya, A. Bar-Noy, and D. Dolev, 1995。在这里，我将根据教程论文中的讨论总结算法。算法使用了多数复制来提供在同步模型下，崩溃故障下原子读取和写入操作。（当然，FLP结果表明在这种模型下不可能解决共识，但这是一个比解决共识更弱的问题。）这里原子意味着系统提供线性化，强一致性，保证读取返回最新版本的数据。这种单拷贝一致性比Amazon Dynamo的最终一致性更强.在CAP定理中这个算法在CP测；当大部分副本不可达时，可用性在这里被牺牲了。写操作每个存储节点保存起客户端存储的最新值的本地副本，一级指示该新鲜度的时间戳。一个vt-pair表示(value,timestamp)的一对，存储节点保存该数据。为了执行write(v)操作，客户端执行俩个阶段，他执行俩个操作：首先执行get阶段，然后执行set阶段。get 阶段：vt-set=从大多数存储节点读取kv对。选择唯一的t'让t'>max(t在vt-set中)set阶段：write_request(v,t')在存储节点。如果t'>他存储的t，存储节点存储vt'。存储节点发送ack，当大部分节点回复收到，返回OK通过将客户端id与时间戳相邻，可确保t'的唯一性，因此，时间戳由一对数字和客户端id组成，按字典顺序排列。读操作read()操作非常类似写请求。客户端还背靠执行get和set阶段。唯一的区别是，在设置阶段，客户端写会在它在获取阶段学习到的最大时间的vt对。get 阶段：vt-set=从大部分存储节点读取vt对set阶段：write_request(v,t')在存储节点。如果t'>他存储的t，存储节点存储vt'。存储节点发送ack，当大部分节点回复收到，返回 Vread()中的set阶段是必须的，用来防止由于存储节点故障导致的震荡读取，在这种情况下，在写入过程中，连续的读取会在新旧值之间震荡，这违反了原子性原则。set阶段确保后续的read()返回的值至少是当前的read().这里的关键直觉是，任何两个多数存储节点总是至少有一个共同的存储节点。因此，如果某个客户端将值v存储在大多数存储节点上，那么另一个客户端在查询任何多数节点时都可以看到v。与 Paxos的关系多数复制算法似乎与 Paxos 共识算法密切相关。vt-pair 中的 t 对应于 Paxos 中的选票编号。Get 和 Set 阶段对应于 Paxos 的 phase1 和 phase2。（当然，由于多数复制不是为了共识，所以没有与 Paxos 的 phase3：commit 对应的东西。最后，读取作对应于 Paxos 中的学习作。现在是差异。在多数复制中，客户端不协调写入作，而在 Paxos 中，领导者被限制重新提议/重写具有最高 t 的值。同样为了避免领导者决斗问题，Paxos 依赖于领导者选举服务，以便系统最终收敛到一个领导者，该领导者可以安全地锚定/最终确定一个值作为决策值。（Paxos 中的领导人选举服务需要一些部分同步才能取得进展，因此只有到那时才能达成共识。总之，多数复制是 Paxos 共识的基石。结束语这种优雅算法的好处是它可以容忍/屏蔽少数存储节点和任意数量的客户端节点的崩溃，并且它可以在“异步”系统中工作。该算法的正确性不依赖于同步系统，因此该算法非常适合在分布式系统（尤其是广域网系统）中部署。基于共识/Paxos 的算法可以使复制服务的重新配置成为可能。示例包括 RAMBO 算法和 FAB：从商品组件构建分布式企业磁盘阵列，它提供了一个实现这些想法的化。但是，重新配置教程论文解释说，在异步模型下实现复制的重新配置也是可能的（没有共识）！！其他ABD算法确保线性一致性的操作被称为blind write盲写：它只是覆盖了一个数据项的值，而不考虑它之前的值。它只是覆盖了一个数据项的值，而不考虑它之前的值。如果多个客户端同时写入同一个项目，它将使用last-writer-wins最后写入者获胜的策略冲突解决。也就是说，其中一个写法将最终成为 "赢家"，其他的值将被默默地丢弃。在某些应用中，我们希望决策更加谨慎，同时只在一个值没有被另一个节点修改的情况下才覆盖它。这可以通过一个atomic compare-and-swap (CAS)操作来实现。问题是我们如何在一个分布式多副本系统中实现线性一致化的CAS操作？ABD算法无法实现CAS，因为不同的副本可能会以不同的顺序观察到操作，从而对某一CAS操作是否成功得出不一致的结论。然而，使用全序广播可以实现线性一致化且多副本的CAS操作。我们简单地广播每一个我们想要执行的操作，并在操作被递交时执行。这种算法可以确保一个操作在每个副本上有相同的作用和结果，就像在状态机副本中一样。版本号ABD算法需要一个机制来生成单调递增且全局唯一的标识符，以充当数据版本的逻辑时间戳。他必须满足俩个关键属性：单调递增：每次成功的写操作都必须产生一个比之前所有时间戳都更大的时间戳。全局唯一：不同客户端并发产生的写操作，其时间戳也不能相同，必须能够区分先后顺序。结构：时间戳通常不是一个简单的数字，而是一个二元组 (序列号, 客户端ID)。比较规则：采用字典序进行比较。即先比较序列号，序列号大的时间戳更大；如果序列号相同，则比较客户端ID，ID大的获胜（只要保证客户端ID唯一，任何比较规则都可以，目的是打破平局）。客户端在执行写操作的 Get阶段，会从多数派节点收集当前已存在的时间戳。客户端找出其中最大的时间戳，记为 max_ts。在 Set阶段，客户端生成的新时间戳其序列号部分必须大于 max_ts的序列号（例如，max_ts.seq + 1），然后附上自己的客户端ID。通过这种方式，每个新的写操作都“站在巨人的肩膀上”，确保自己的时间戳能超越之前所有已知的版本，从而满足单调递增的要求。客户端ID的引入确保了即使两个客户端并发地基于同一个 max_ts生成新时间戳，它们也会产生不同的时间戳（客户端ID不同），从而避免了冲突，满足了全局唯一性。
对称加密和非对称加密的应用简介对称加密加密和解密使用同一把秘钥。特点：速度快效率高，适合加密大量数据。但核心问题是如何安全地将秘钥分发给通信双方。常见算法：AES（标准最常用）, DES（已经淘汰）, 3DES, ChaCha20。AES主要有三种秘钥长度AES-128、AES-192和AES-256。这里的数字代表密钥的比特数。以AES128为例使动用地球上所有的计算机进行数十亿年的暴力破解（尝试每一个可能的密钥），成功的机会也几乎为零。AES 算法通过对数据块（16字节）进行多轮重复的变换来实现加密。密钥越长，需要的“搅拌”轮数就越多，以确保其安全性：AES-128：使用 128 位密钥，需要执行 10 轮加密。AES-192：使用 192 位密钥，需要执行 12 轮加密。AES-256：使用 256 位密钥，需要执行 14 轮加密。从 10 轮增加到 14 轮，意味着 AES-256 需要比 AES-128 多进行 40% 的加密运算。优点速度快效率高，加密和解密过程的计算量小，算法简单。这使得它非常适用于大量数据，如整个硬盘，大文件，数据库内容加密强度高：在秘钥长度相同的情况下，对称加密比非对称加密更难以被暴力破解（例如，256位的AES被认为在可预见的未来都是极其安全的）。资源消耗低：对CPU和内存需求较小，适合资源受限的环境，如移动设备，嵌入式系统。缺点秘钥分发问题：如何将秘钥安全的传递给通讯的一方？如果被拦截怎么办？如果与N个不同对象通信，就需要管理和维护N个不同的秘钥。随着通信对象的增加，秘钥管理复杂度和成本会急剧上升。由于通信双方拥有相同的密钥，接收方可以伪造一条消息并声称来自发送方，发送方也可以否认自己发送过某条消息。无法提供法律意义上的数字签名功能。非对称加密简而言之可以公钥加密私钥解密。也可以私钥解密公钥加密。使用一对秘钥，即公钥和私钥。公钥可以公开，用于加密；私钥必须保密用于解密。优点解决了秘钥分发问题。公钥公开传播无需保密。只要确保私钥的安全，通信的机密性就能得到保障。通过数字签名（私钥签名，公钥验证），可以确认消息发送者的身份，并且发送方事后无法否认其签名过的行为。秘钥管理简单：每个用户只需要保管好自己的一个私钥，并将公钥公即可。与N个人通信，也只需要一对密钥。缺点速度非常慢：加密和解密过程涉及复杂的数学运算（如大数分解、离散对数），计算开销比对称加密大几个数量级。不适合用于加密大量数据。资源消耗大：对CPU和内存的需求较高。对称加密应用领域主要用于对大量数据进行保密性保护的场景。全盘加密：BitLocker (Windows), FileVault (macOS), VeraCrypt 等。需要加密整个硬盘分区。数据量巨大，对称加密（如 AES）的高速度是关键。文或者文件夹加密。压缩软件，WinRAR，7-Zip的加密功能数据库加密：对数据库中敏感字段进行加密存储。VPN通信IPsec VPN, SSL/TLS VPN（在握手成功后）。无线网络加密：接入点（路由器）和客户端设备使用非对称机制完成身份验证后，会协商出一个对称的会话密钥，用于加密所有的无线数据。非对称加密应用领域数字签名：发送方用自己的私钥对消息的摘要进行加密，生成签名。接收方用发送方的公钥解密签名，并与自己计算的消息摘要对比。SSL/TLS握手安全电子邮件PGP/GnuPG协议加密货币：用户钱包地址本质是公钥的hash值当用户要花费加密货币时,需要用自己的私钥对交易进行签名,网络中其他节点可以用该用户的公钥来验证交易的合法性.私钥是拥有资产的唯一证明SSH认证前向问题假如和朋友邪心你们都从这本密码本里查找对应的密码来加密信息。如果有一天小偷偷走了这本密码本，他不仅能解密未来的所有信息，还能把过去窃听并记录下来的所有加密信息全部解密。SSH工作原理如今通常用非对称加密进行对称加密秘钥交换，用非对称加密进行实际通讯。如何对server的公钥进行认证？在https中可以通过CA来进行认证，可是SSH的公钥和私钥都是自己生成的，没法公正。没法公证。只能通过Client端自己对公钥进行确认。通常在第一次登录的时候，系统会出现下面提示信息：The authenticity of host 'ssh-server.example.com (12.18.429.21)' can't be established. RSA key fingerprint is 98:2e:d7:e0:de:9f:ac:67:28:c2:42:2d:37:16:58:4d. Are you sure you want to continue connecting (yes/no)?之所以用fingerprint代替key，主要是key过于长（RSA算法生成的公钥有1024位），很难直接比较。所以，对公钥进行hash生成一个128位的指纹，这样就方便比较了。输入yes后会出现以下信息Warning: Permanently added 'ssh-server.example.com,12.18.429.21' (RSA) to the list of known hosts. Password: (enter password) SSH 默认设计无法完全避免首次连接的 MITM 风险，但通过提前验证指纹、部署证书认证或结合其他安全措施，可显著降低威胁。企业环境中推荐使用 SSH 证书认证，个人用户则应严格遵循指纹验证流程。*Diffie-Hellman 不能够安全的交换服务端的非对称加密的公钥吗 可以通过HTTPS等其他手段来交换。直接使用基础的 Diffie-Hellman 协议来安全交换服务端的非对称公钥是不可行的，因为它缺乏身份认证环节。在实践中，我们通过一个已经可信的公钥基础设施（PKI） 来首先安全地获取服务端的公钥（通过数字证书），然后：
南京大学操作系统课程学习4计算机安全在操作系统API上，我们可以构建命令行工具、编译器、数据库，浏览器等丰富应用。在8086时代，每次的访问都是直接映射到地址空间中，任何程序可以访问任何硬件。百度可以复制自己，然后感染更多的计算机程序。我们希望计算机有confidentiality，integrity，availability。有一些软件硬件的协同设计。分页机制和进程隔离系统调用和访问控制鉴权和授权加密审计与日志机密计算（TEE）理论上应用程序如果不信任操作系统，硬件也提供了特权来执行应用程序的代码。访问控制进程+虚拟内存已经实现了隔离。进程只能以ELF规定的权限访问自己的虚拟空间地址。系统是唯一访问操作系统对象的途径。（前提是内核没有被漏洞攻破）操作系统还有一些虚拟化机制、容器。 访问控制：限制程序对操作系统对象的访问。拒绝越权访问和修改。理论上可以直接用一张表来做访问控制。然而表可能特别大。unix用整数表示身份uid=0就是root用户，gid是完全自由的，虽然一般0是root，mode规定了rwx的权限。操作系统没有用户名的概念，操作系统也不负责验证用户名。有个程序叫做login负责进行密码的验证。现在系统通常使用shadow文件存储密码的hash。chsh，passwd只是直接修改了文件。操作系统只管uid不管如何解读用户。如今的操作系统有很多uid：real uid（ruid）saved uid（suid）effective uid（euid）filesystem uid（uid） 如今已经没人用了。操作系统还有非常多的访问控制的方法access control list（ACL）SELinux、AppArmorcapabilities攻防假设我们运行这样一段程序会发生段异常。这个叫做undefined behavior。容器、虚拟机、微服务进程一直以来都是操作系统中的核心抽象。作为应用程序的主题，运行它的方式在多年的发展中经历了许多变化。操作系统理论上是可以无限套娃的，比程序完成整个操作系统。取指令，编译代码，执行但是它的性能，不及原生的10%。full system emulation1997年 brings back an idea popular in the 1970s： virtual machine monitorVMware在1998年把这个技术做成了产品。VMware会把应该在系统内部调用的程序放在操作系统直接运行。但是系统调用会被VMware程序劫持变成一个软件模拟的系统调用。wsl在windows下模拟了linux地址空间，如果发现systemcall来自linux，就用linux子系统完成。之后intel提供了许多虚拟化指令集。 VT-x 2005->VT-d 2006 ->EPT 2008一些特权指令没法直接执行，比如关闭中断。可以让虚拟机来控制中断。VT-d提供了堪比物理机一样的高效的IO：IO虚拟化。EPT提供页表，8级页表其中4级给操作系统用，4级给虚拟机用。Intel 的 EPT（Extended Page Tables，扩展页表） 是硬件辅助虚拟化技术的一部分，主要用于优化虚拟机（VM）中客户机物理地址（GPA）到宿主机物理地址（HPA）的转换。在没有 EPT 的情况下，虚拟机监控器（VMM/Hypervisor）需要通过软件模拟页表，处理客户机的内存访问请求（GPA → HPA），导致大量性能开销（称为“影子页表”问题）。EPT 在硬件层面提供第二层页表（EPT 页表），直接由 CPU 的 MMU（内存管理单元）完成 GPA 到 HPA 的转换，避免了 Hypervisor 的软件介入，大幅降低内存访问延迟。最早的时候通过虚拟机进行超卖。虚拟机导致更容易的管理状态了。最早的系统的版本休眠是可以掉电的。掉电之后打开还是可以继续之前的状态的。但是在物理机上实现这个功能是很复杂的，需要把所有进程都停下来。遍历设备程序驱动。dump到磁盘里。但是虚拟机很容易实现这个功能，因为虚拟机就是一个进程，直接做一个core dump就可以了。另一个技术叫做空间转移的技术：optimizing migration of virtual computers还可以使用虚拟化技术做操作系统内核的热更新。不同虚拟化技术的实现差异全虚拟化（Full Virtualization）：使用二进制翻译（如早期VMware）动态替换特权指令，或依赖硬件虚拟化扩展。Guest OS无需修改，但性能开销较大。半虚拟化（Paravirtualization）：Guest OS被修改，主动调用Hypervisor提供的API（如Xen的hypercall）代替特权指令，避免陷入开销。容器（Container）：共享主机内核，通过命名空间（namespace）和cgroups隔离资源，直接调用主机系统调用，无虚拟化层。容器但理论上操作系统自己就能虚拟化自己。操作系统理论上可以假装自己在虚拟机中执行一个系统调用。pid可以不再是整个系统唯一的，给每一个进程增加一个osid，增加系统调用vos(fs_root)，这个系统调用会创建一个新的虚拟机。新的树的osid就是2。但是os2的getpid就可以由操作系统控制。然后准备俩个不一样的文件系统。创建一个新的osidpid从1开始分配fork()继承父进程的osid每一次systemcall都是在当前的osid下执行，对其他osid屏蔽。但是由于增加了osid，要确认操作系统的哪些资源是可以被虚拟化的。piduser：用户和组mnt：文件系统和设备ipc：信号量、消息队列、共享内存net：网络设备、协议栈、端口（localhost:5000）time：系统时间和时区uts主机名和域名.在操作系统中可以看到自己的namespace，linux: /proc/[pid]/ns在这个基础上我们还想进一步实现资源的调度，圈一些进程，使用特定的资源策略Control Groups (cgroups) 是 Linux 内核提供的一种机制，用于限制、记录和隔离进程组的资源使用情况（如 CPU、内存、磁盘 I/O、网络等）Cgroup是于2.6内核由Google公司主导引入的，它是Linux内核实现资源虚拟化的技术基石，LXC(Linux Containers)和docker容器所用到的资源隔离技术，正是Cgroup。那么你发明了cgroups，这是一个和namespaces正交的机制。共同使用，你就得到了容器。例子：只有busybox的系统中的系统到这里你就发明了docker（2013）。在2008年就有了Linux containers，通过整合内核的 cgroups（控制资源）和 namespaces（隔离进程、网络等），首次在 Linux 上实现了完整的容器功能。但配置复杂，需手动管理。由IBM工程师开发，得到了linux社区的广泛贡献。Google 的 Borg 系统（2004年内部使用，2015年发布）​​：大规模使用容器技术（基于 cgroups）管理集群资源，但未开源，仅限于 Google 内部。如果只需要linux，容器就和虚拟机一样。开销比虚拟机低很多，安全性略低。如果操作系统有资源没有很好的被namespace隔离开，就可能产生安全问题。比如机器的总端口可能是有限的。Kubernetes：容器编排，跨主机、弹性自动伸缩。这是云厂商最爱看到的。每个容器可能非常小，比如rust写的，几十mb就能跑起来了。云原生，serverless直接将函数最为服务，进行按量付费。serverless连容器保活都不需要了。function as a service。嵌入式和移动操作系统embedded计算机系统是嵌入到设备中的。人造卫星，工业控制、家用电器、医疗器械、穿戴设备。体积小、计算第、可靠性高，操作系统通常更简单（领域固定）；但linux也是可以的例如PLC（programmable logic controller）和工控。通常有实时保障。在严格的时间内对外部事件做出可预测响应。比如我们希望某个程序一毫秒执行一次，但是linux就难以做到这样的事情（特别是当程序运行的越来越多的时候）无论车机多花哨，最终实时控制仍然是MCU。比如FreeRTOS。支持抢占式调度，按照优先级执行任务，确保高优先级的任务及时响应。内核仅需几KB ROM和RAM，适合资源受限的MCU。高优先级的任务可以实现更高优先级的时间片分配。但是优先级也会带来麻烦，比如低优先级的任务拿到了锁，导致高优先级的任务被阻塞。高优先级任务只能让出执行时间片给低优先级的任务先执行。这叫做优先级反转（priority inversion）。应用程序的依赖可能形成等待链，导致系统变卡。 到系统出现不稳定时，重启系统总是能解决问题，是因为重启能恢复状态机的状态。Android最早的手机不能安装软件，只能收发信息和打电话。甚至只能显式三四行的文字。之后诺基亚的5310可以执行一些复杂的任务。支持彩色的显示，并且能够播放音乐，运行可安装的java程序。j2ME时代，甚至可以用java渲染网页。320x240的屏幕。之后乔布斯发布了ios。谷歌2005年收购了Android inc。安卓是完全基于linux开发的，Linux+Full JVM+Framework API开放平台。一开始用java发现程序非常卡。当时是32位的armv6@528mhz（1cpu，TSMC）塞班系统当时暴毙于C++，windows phone 暴毙于C#。当时java有很大的市场。现在看起来这是一个很高瞻远瞩的决定，赌摩尔定律生效（同年 i7865，4c8t）存在一个推理，在未来存在一个临界点，能实现实时推理无处不在。在安卓5.0的时候支持将所有程序从原来的.class编译到.out安卓之间应用程序经常需要进行写作。安卓提供了remote.transact()。这是在优化和易用之间的权衡。 安装也提供了丰富的开发者工具。比如android studio。DDMS。android debug bride（ADB）。还有android shell。比如可以监听系统的所有事件。简单来说我们可以将硬件操作挂在到一个设备上，和之前提到的一样，读取硬件的操作，然后捕捉对应的事件。我们写一个程序定期拍照，然后将点积事件传回给手机，就有了电脑控制手机的功能（scrcpy）。甚至可以任意改变APP的行为。如何杀死一个android进程？android每个app都有独立的uid，遍历进程表，找到属于uid的进程。遍历进程表来杀死进程的时候，可能出现杀不干净。安卓默认间隔5ms，连续杀死40次，防止偶然杀不干净。
南京大学操作系统课程3设备和驱动程序插入u盘后会发现/dev下会发生变化/dev/下的对象不会凭空创建udisks2才是真正执行mount的程序实际上我们看到的计算机设备都是输入输出设备。有些设备既能做输入也可以做输出，比如u盘。输入输出设备是能够与CPU交换数据的接口、控制器。给寄存器一个内存地址（address docider），CPU就可以直接使用质量（in/out/MMIO）和设备交换数据。我们可以预先定义好寄存器中每个值被写入会触发什么动作，然后用io设备写入寄存器，触发预先设定的动作。比如一根线、一条质量（树莓派上就有），GIPO（general purpose input/output）极简的模型 memory-mapped I/O 直接读取电平信号。串口（Serial Port）是一种用于串行通信的硬件接口，常用于计算机与外部设备（如传感器、单片机、工业设备等）之间的数据传输。现在的键盘都是软件完成的，但是早期cpu性能受限，需要其他硬件来帮忙做一些事情。比如每按下一个键盘，都会给CPU发送一次中断操作。8042负责安排以什么频率将键盘上的信号发给cpu。最早的打印机有个小的解释器。把所有用来划线的指令都物理写出来。将回边语言翻译成机械部件动作的设备。如果cpu想要更多的IO设备。我们想要兼容位置的设备，因此就出现了总线。总线提供了设备的虚拟化。总线上会有许多设备。如芯片控制器，核显，独显，温度控制器，usb接口。usb总线上还会挂在许多设备。如鼠标，麦克风，键盘。如今pcie6.0 x16带宽达到了128GB/s。总线自带DMA。现代的告诉设备都是直插PCIE的。程序不能直接访问寄存器，设备可以在程序之间共享的。仔细想想CPU和内存也都是设备。因此我们需要有个新的机制实现设备的虚拟化。这个机制就是文件。对于硬件设备，它们都是文件和控制接口。操作系统可以直接用文件的API来操作这些设备。代码会将读写操作翻译成设备能够看懂的指令。这个程序就叫设备驱动程序。目前操作系统能帮忙自动安装驱动，但更早的时候设备驱动都需要自己安装。对于linux系统来说，如果想实现设备驱动程序，只需要实现file_operation的结构体即可。用来吧系统调用翻译成设备能听懂的数据。比如/dev/null这个目录写入的所有数据都会被吞掉。读取任何数据都读取不到。即丢弃所有写入它的数据。它底层实现方式就是读取直接返回0，写入直接返回count（收到字节什么都不做）。设备对应的文件都是虚拟的。 设备不仅仅是数据还有配置。有俩种实现的方法：控制最为数据流的一部分（ANSI Escape code）提供一个新接口（request-response）因此设备最复杂的部分，设备是通过IO ctl来控制的。每个设备都有自己的IO ctl。对于一个io设备来说，非数据的功能全部靠这个系统调用。设备的复杂性是无法降低的，就是有那么多功能.UNIX的复杂：复杂的hidden specification和procfs。linux /dev/kvm是干什么的/dev/kvm是 Linux 系统中用于硬件虚拟化加速的字符设备文件，主要作用是为 KVM（Kernel-based Virtual Machine）提供直接访问 CPU 虚拟化扩展（如 Intel VT-x 或 AMD-V）的能力。io ctl是一个万能接口，用于处理设备特定操作，这些操作无法通过标准文件I/O实现。由于不同设备控制需求千差万别，ioctl必须高度定制化，导致七参数和用法高度依赖具体驱动实现。存储设备原理持久设备需要能够寻址+用电路改写。最早的存储设备是磁带。纸袋（今天是塑料）上均匀黏上铁磁性颗粒只需要一个机械部件转动定位。读取：放大感应电流，写入：电磁头（电磁铁）改变磁畴磁化方向。通过电磁感应写入读取数据。通过切割磁感线得到感应电流。因为这是一维的结构因此卷起来存储很多数据。比如磁带正反面可以都印刷数据，这样就不需要进行倒带了，直接翻一下磁带即可。但是磁带不能够随机访问，需要通过转轴遍历数据。磁带价格低，容量高，可靠性高。顺序读写需要等待定位，随机读写完全不行。因此应用场景是冷数据的存档和备份。比如为了数据合规合法，需要保存这个数据。磁带在计算机早期是主力存储设备。之后出现了磁鼓。用旋转的二维平面存储数据（无法内卷，容量变小）读写延迟不会超过旋转周期。 磁盘在二维平面上防止许多磁带。因此磁头只需要一个自由度就可以了。磁盘是很稳定的，哪怕近距离用强磁铁都很难磁化。内部有屏蔽和保护机制。磁道的大小可以做到微米级。可以做到每秒5400转。只要bit排布的足够，磁盘就可以进行良好的随机读取。工程优化，把bit竖起来排布。磁盘正面反面都存数据磁盘：价格低：高密度，低成本，容量高（2.5d上万个磁道） 顺序读写较高，随机读写勉强。在剧烈震动等情况下，可能会导致数据丢失。读写需要到对应的磁道，7200rpm->120rps->寻道时间8.3ms。转轴将盘片旋转到读写的位置，读写头的移动时间通常也需要几个ms。软盘计算机上的软盘驱动程序，可移动的盘片。最初的成本很低，就是个纸壳子。3.5英寸软盘为了提升可靠性，已经是硬的了。A盘和B盘就是为软盘所用的。最早的硬盘都是需要冷插拔，因此需要软盘可以热插拔。最早的程序甚至没有用户态和内核态，都完整的执行在操作系统上。最早的游戏是通过多张软盘发行的。价格低：极低成本容量低：裸露介质，密度受限。可靠性低，不要抱有太大的期望。顺序读写：低，随机读写低。光盘通过激光扫过表面，就能读出坑的信息来。光盘最有趣的特性：容易复制。光盘的坑是挖在透明塑料膜上的，压盘后上反射膜。3s生产一张blue ray 100GB（33，000MB/s）写入速度。他的复制速度比任何存储介质来得快。光盘价格低，容量高上百G（没有那么高），可靠性高（不能划伤有数据的那面）顺序读硬盘，随机读低（很难写入）。最早光盘的大小是贝多芬的第九交响曲（74分钟） 。因为是在空气中旋转，无法以较高的速度旋转。可以通过相变材料控制光盘是否可写。现在甚至有技术可以在玻璃中间挖坑，实现上千年的存储。固态存储介质的致命缺陷磁：机械部件（无法避免ms 机延迟）坑（光）：挖坑效率低，填坑困难。存储特性：价格低（大规模集成电路）。容量高，可靠性高：集成电路封装，不怕摔。SSD没有机械运动部件。读写性能极高，且有极高的扩展性。（电路天然是必行的）。而且容量大，速度快。买的容量越大速度就越快。ssd开启了u盘时代。当flash memory越做越小的时候，可能会导致放电放不干净。这是一个致命的问题，比如充放电的次数过多时，电子可能永远无法被释放。因此在上千次的操作下就会发生损坏。但是一个文件保存几千次，现在通常不会造成损坏。这是因为SSD、u盘甚至tf卡里都藏了完整的操作系统。每次写入擦除次数较少的那块区域。类似虚拟内存。因此随着时间的推移，整个硬盘会变的越来越慢。u盘在这个问题上尤为明显。u盘，sd卡，ssd都是NAND flash。但是软件硬件的复杂程度不同，效率和寿命也不同。因此不要买过渡便宜的硬盘。设备是可以伪造的，可以伪造乘另一个厂商的设备。甚至可以伪造容量。存储系统经过多年的变化在操作系统中的抽象没有发生变化。寻址能力需要付出代价，无论是磁盘还是电路。解决方法就是按块访问。blocks devices也快要是普通的文件，可以直接mmap到进程地址空间。如果做透明的抽象，就会导致读放大和写放大。因此linux做了BIO抽象Request/Response接口。多个系统访问硬盘需要向BIO队列提交请求。下层BIO+驱动负责调度。一次请求可以读取很多块。block io会将请求转发给设备。目录树管理在存储器上，操作系统（文件系统）实现了目录树结构的文件系统，使我们能以直观的方式有序的操作数以万计的持久化对象。磁盘=块（字节）序列一本书：每一页纸存储了数据，支持随机访问。（翻到某一页）文件是虚拟的磁盘看不到一页纸的概念，支持read，write，lseek，ftruncate。那么如何彩礼操作系统众多文件。信息的局部性：将磁盘文件组织成层次结构。分层索引就可以利用信息的局部性。所有以.开头的文件默认情况下ls都不展示，是隐藏文件。实际上隐藏.开头的行为不是操作系统的行为，只是为了偷懒。因此就有了约定俗成的目录HFS filesystem Hierarchy standard。macos有完整的poxis兼容层，因此不依赖linux特性则有可能在macos上运行起来。目录树api支持增删改查mkdir 创建目录rmdir：删除目录getdents：读取目录硬链接：系统中可能有同一个运行库的多个版本。可以理解为，一个数据起多个不同的名字。允许一个文件被多个文件引用。比如.是指向自己的，·..·是指向上级目录的。软链接（符号链接），在文件里存储一个提示跳转，软连接也是一个文件，当引用这个文件时，去找另一个文件。类似windows的快捷方式。甚至可以用软链接来做状态机的状态迁移。软连接可以用来伪造文件系统。Nix操作系统把所有的所有版本都集中存储。然后用符号链接构建完全虚拟的环境。完全确定性的构建任意环境。文件系统文件描述符返回的就是文件。文件是操作系统中的对象ls -l可以查看对象的属性，包含类型，权限，引用计数等。 有一个好用不火的操作系统特性叫做向量索引vectorfs。这是后加的特性，不是所有文件系统都支持。兼容性奇差，当cp文件时xattrs就会消失。需要cp --preserve=xattr。UNIX/Linux一切都在/。windwos下一个驱动器一棵树。linux的目录都在mount下，可以把块上的目录树放到已有的目录中。每次进行挂在的时候操作系统会创建一个新的回环设备。Btrfs（B-tree File System，通常念作 "Butter FS"或 "B-tree FS"）是一种现代的高级文件系统，最初由 Oracle 开发，现已成为 Linux 内核的一部分。它被设计用于解决传统文件系统（如 ext4）的局限性，提供更强的数据管理功能、容错能力和可扩展性。OverlayFs也叫UnionFS 联合挂载看到的每个linux目录可能都是假的，在OverlayFS中lowerdir：只读层（修改会被丢弃）upperdir：可写层（修改会被保留）worker：操作系统用的临时目录常用于容器场景，当修改下层文件时，OverlayFS会先将文件复制到上层（upperdir），再修改副本，原始文件保持不变。我们可以用一个ubuntu的文件基础，来用overlayFS创建多个系统的复制。文件系统可以看做是一个有向图。文件系统实现文件系统实现了树或图的目录结构，提供了丰富的API。让我们进行增删改查。实际上文件系统就是在存储系统之上实现一恶搞支持修改查询的数据结构，实现它是理所应当的。块设备上的数据结构Abstract DataType（ADT）。就像我们在内存里做的一样。只不过不是随机访问内存。但是直接将磁盘映射到内存中，就会造成读放大写放大。Logical volume manager（LVM）Logical Volume Manager (LVM) 是Linux环境下的一种磁盘管理机制，它提供了比传统分区更灵活的磁盘管理方式。LVM允许将多个物理磁盘或分区组合成逻辑卷组，然后在这些卷组上创建逻辑卷，这些逻辑卷可以像普通分区一样使用。LVM可以在原有磁盘上扩展逻辑卷。LVM还支持快照功能。5.25软盘单面160kib。有320个512B扇区。在这样的系统上选择什么文件系统呢？这样的情况下任何复杂的结构都会造成浪费。文件实现方式 struct block *的链表，任何复杂的高级数据结构都显得浪费。目录就是一个普通的文件，操作系统会把文件内容解读乘struct dentry[]在每个数据块后放置指针：实现简单，无需单独开辟存储空间，但是数据大小不是$2^k$ 2的整数倍，lseek无限放大。（比如要定位最后一部分数据，需要重新从头扫描文件）将指针存放在文件系统中的某个区域：局部性更好lseek更快。集中存放的数据损坏将导致数据丢失。160K的软盘，有512字节的扇区。320个扇区，12bit entry，480B。只需要同一个扇区就能存下next[]，即便容量翻倍也就俩个扇区。因此这个next方案也叫做，File allocation table：集中保存所有指针。在内存里缓存一份FAT（天生一次也要读完512B）延迟写回，读写放大的问题就全解决了。因此采用将指针放在文件系统的某个区域的方案。集中存储的指针容易损坏？那存n份就行！延迟写会，写放大就不那么严重了。（存俩份FAT指针。）在文件分配表（FAT）文件系统中，簇（Cluster）是磁盘空间管理的基本单位，也是操作系统分配存储空间的最小单元。簇由一组连续的扇区（Sector）组成，大小由文件系统格式化时决定（如4KB、8KB等）。FAT表通过记录簇的分配状态（空闲/占用）和文件占用的簇链（Cluster Chain）来管理文件存储。FAT表中每个指针，在FAT12的时候是12个bit，16的时候是16个bit，FAT32是32个bit。FAT表本质是一个簇（cluster）链表，记录了每个簇的使用状态以及文件数据的存储位置。FAT表是一个链表。隐式链表：FAT 通过簇号串联文件占用的物理簇，形成逻辑上的链表结构。例如：文件 A 占用簇 2 → 簇 5 → 簇 8，则 FAT 表中：FAT[2]=5, FAT[5]=8, FAT[8]=EOF。类似数组形式，但是数组的value中会写着下一个索引号，来形成类似链表这种设计允许文件数据在磁盘上非连续存储，通过 FAT 表动态追踪簇链。FAT的目录就是个普通的文件。目录下面有很多目录项，每个entry都是固定长度的，前8个字节是文件名后三个字节是扩展名。之后还要一些扩展信息，比如最后修改时间，最后访问时间，创建时间。文件大小。还有最重要的first cluster指向的是FAT表。访问目录，按照目录中的文件名定位到，FAT表的起始位置，通过FAT表的类似在数组中存链表的结构，按照自己的偏移量进行读取。最后按照fat表的块地址访问自己需要的文件。但是如今看来8+3的文件名已经不够用了。还希望老系统能够兼容新系统就做出了调整。FAT适合小文件，大大文件的随机访问就不太行了。4gb的文件跳到末尾有$2^{20}$次next操作，缓存能部分解决这个问题在FAT时代，磁盘连续访问性能更佳，使用时间久了会产生磁盘碎片。维护若干个FAT副本防止元数据的损坏可能造成轻微写放大。如今的UEFI分区文件格式还是FAT。 更号的文件系统：观察统计数据大部分文件是2KB的小文件(配置文件)平均文件大小上涨到了200K大的文件越来越大文件系统文件树越来越多文件通常比较小,可能有20个文件或更小然而FAT文件系统不支持硬链接。我们想支持任意大小文件的随机访问。因此我们需要结构化的nodeiNode (index node）保存ls -l里的各种metadata。它会在磁盘上专门的区域上划出一块空间来，存放inode，每个inode对应文件系统里的文件或者目录。inode保存了文件持有者，访问时间，创建时间，组编号，最后修改时间等。在minix中就已经存在inode了。除此之外还有一个非常重要的数据结构。将文件的偏移量映射到了块idmap<int,int>(file offset->block id)如何设计这个map引入了ext2数据结构。SuperBlock 文件系统的块级元数据。inode数量，block_per_block以第一个superblock为准。每个文件都有一个inode。比如小于等于40kb的文件可以直接查表，得到文件的位置。文件变大后可以做多级索引，类似b-tree的结构。越大的文件数量越小，中等大小的文件只需要用多1层索引，1层不够用用俩层。因此它兼顾了所有大小的文件。这个设计考虑了实际数据访问的概率分布。ex2的目录文件，是在文件上的数据结构map<string,int>(name->inode)基本定位流程从根目录开始：每个文件系统有一个固定的根inode（通常是inode 2）逐级解析路径读取目录文件内容（目录也是文件，有对应的inode）在目录条目中查找下一级目录或文件名对应的inode编号根据inode编号访问目标inodeext2不是固定长度的文件。ext2性能可靠性：bitmap,inode都有集中存储的局部性，通过内存缓存来减少读写放大。通过将inode放在近似的位置，有很好的局部性。通过内存缓存可以减少读写放大。大文件支持O(1)的随机读写。支持链接（一定程度上减少空间浪费）inode在磁盘上连续存储，便于缓存、预取。依然有碎片问题.但可靠性依然是很大的问题。文件系统本质就是数据结构。因此数据结构可以不用实现在操作系统内核中。比如fuse filesystem in userspace。任何数据结构都是可以的，比如B-Tree FileSystem。安卓使用的f2fs（flash firendly），就是针对随机读写进行优化变成顺序读写。还有华为的enhanced read -only FileSystem（erofs）数据库系统raid能用便宜的磁盘做可靠的存储系统。数据结构的multi-write在崩溃时导致不一致状态。崩溃一致性：数据结构的multi-write在崩溃时导致不一致的状态，通过flush机制和journaling实现崩溃的一致性。当写入磁盘时会社区复杂数据结构。 当写入的时候需要更新inode，size，time，index，bwrite。实际上会有多个块操作。所有的写请求都会先到达缓存，计算机系统会按照它认为最佳的顺序写入。HDD磁头的动态规划就是一个例子。如果只有一部分数据落盘，文件系统就会陷入不一致的状态。因此有一个File System Checking的机制FSCK，根据磁盘上已有的G(V,E)恢复出最可能的数据结构。操作系统提供了sync命令，用于让所有的数据刷盘后才会进行下一个操作。fsync其中有很多更细粒度的api，比如fsync去刷新指定文件描述符关联的数据和元数据。sync>syncfs>fsync>fdatasync在 Unix/Linux 中，若目标文件已存在，rename会原子性地替换它（前提是权限允许）。Windows 的 ReplaceFileAPI 也提供类似保证。若进程在 rename前崩溃，原始文件保持完好；若在 rename后崩溃，新内容已原子生效。但是跨卷的操作可能是非原子的。数据库在单个文件中我们可以继续抽象。将所有数据写入一个文件中。但是文件系统并不可靠，需要fsync等API进行直接交互，还会存在效率问题。一个简单的想法是利用目录树。这样我们就可以利用unix世界中所有的工具了。比如find，grep。甚至还可以做符号链接做数据关联。文件系统可以用flock做并发操作。数据故障时，数据不能丢。我们希望并发性，持久性，原子性。我们想要比目录和文件更好用的API。关系型数据库relational database。一个非常简单的模型：a relational model of data for large shared data banks。每一行对象，都可以用id索引其他对象。ACID数据库atomicity，consistency，Isolation，durability。在很长一段时间内，数据库+raid是一种绝对可靠的设计。数据库还能额外支持事务，这个对原子性的支持非常重要。实现实现查询=实现编译优化。Raid没有一个绝对可靠谱的存储设备。比如内核panic，不分失效，ecc纠错失败。fail slow。小概率事件的大量重复必然发生。我们想用软件来实现高可靠。A Case for redundant arrays of inexpensive disk(RAID)，后来也有人解读乘independent把多个不可靠的磁盘虚拟成一个非常可靠而且性能高的磁盘。这是一个反向的虚拟化，把很多个资源虚拟为一个资源。Raid成就了计算机系统的黄金时代。Raid（虚拟化）=虚拟块到（磁盘，块号）的映射。虚拟磁盘块可以存储在任何物理磁盘上，物理磁盘可以读并行；存储>1份即可实现容错。Raid-0：更大的容量、更快的速度读速度x2；写速度x2，quizRAID-1镜像（容错）保持俩块磁盘完全一样读速度x2；写速度保持一致。如果我们假设不会有俩块盘不会同时发生故障。比如机柜中一般有多个硬盘，当板卡发现磁盘故障时，会自动切换盘。我们可以做到100块盘里，99块都是数据。可以用异或对数据进行恢复。这样子任意的数据盘损坏都可以算出来，包括奇偶盘。但是奇偶计算会成为瓶颈。任何数据的写入都会导致partity的改变。因此我们要让parity均匀分布在各个磁盘。至此Raid杀死了IBM 3380这样走可靠性的盘。磁盘fail-stop：如何感知磁盘下线。软件会定期对磁盘的健康状态做检查。raid物理磁盘不能完美同步，如果遇到断点了，可能会导致潜在的数据不一致。因此现在的raid卡都有电池。GFS在上面做了更高层的抽象。谷歌做了个疯狂的事情，存下整个互联网的数据。(某种意义上谷歌的出现是必然的)分布式RAID。阿里云elastic block storage（EBS fast 24）。磁盘可能出现fail-slow，对于特定负载或者所有负载，或者周期性的变慢。bflush（Buffer Flush)fsync 将文件数据和元数据（如 inode）从内核缓冲区强制写入物理磁盘，并等待磁盘确认完成。磁盘上的数据通常是按块读写，而不是随机写。磁盘提供的接口。磁盘提供了接口。bwrite,bread,bflush。磁盘可以在任何情况下出问题，但是我们可以检查理论上所有崩溃时的可能性。来做出对应的调整。FSCK可以用来恢复出最可能的数据结构。最早的时候，windows在突然断电后第一次启动都要这样做。
南京大学操作系统课程2多处理器编程c程序的状态机模型初始状态为main(argc,argv,envp)状态迁移：执行一条语句（指令）多线程的状态机模型增加一个特殊系统调用：spawn()增加一个状态机，有独立的栈，但共享全局变量。在spawn后，一个进程就出现了俩个线程。可以随时让其中一个状态机执行下一条指令。并发是逻辑上的同时执行，可以由操作系统运行库模拟出轮流执行。（也可以是真正同时执行）并行：丧失确定性，顺序性，一致性真正意义上的同时执行，有共享内存的多个处理器。同时执行指令(load/store访问共享内存)。简化的线程apispawn(fn)创建一个入口函数是fn的线程，并立即开始执行。join()等待所有运行线程返回，main线程返回的时候默认会join所有线程。多线程并发会导致确定性丧失。除了系统调用，程序的行为是确定性的。并发每次可能选一个程序运行，非确定性的程序理解起来相当困难。在单线程时，程序通常假设没人能干涉程序的状态。编译器可以对一段顺序的程序做出任何它觉得合理的优化，但是多线程下这个优化可能就会成为问题。如果想控制编译器的行为，可以通过插入不可优化的代码块来实现。比如while(!flag){ asm volatile("":::"memory") } //或者 标记变量不可优化 int volatile flag; while(!flag)顺序性并发编程会失去全局顺序性。实际上这样的顺序性是不存在的。比如想象一个有多个cpu的主板，根据相对论每个cpu对其他cpu的操作实际顺序都有不同的看法。为了性能，会选择宽松的内存模型，存储写入本地内存，再慢慢同步给其他处理器。允许load到local memory的旧值。共享内存对其他处理器的可见时间点可能不同。处理器内部也会乱序，对同一个地址的store/load允许bypass不同地址的load/store允许重排。乱序执行（out-of-order excution）是现代高性能处理器最值得骄傲的特性之一。处理器本质上也会做类似的事情（改变指令执行的顺序）。现在处理器当发现俩个指令是没有绝对顺序的时候会乱序进行执行。cpu中有个叫分支预测期的东西，会猜到底会执行哪条指令（超过百分之99的准确率）。CPU设计者面临了难题x86把所有的写都排好顺序。arm的实现更简单，性能更好。因此在ARM上模拟x86是很困难。互斥用lock和unlock标记一个代码块，标记的代码块multually exclusive。被秒级的代码块的执行可以理解为一次状态迁移。按照悲观的版本， 加入一半的代码不能被并行，即便有1万个处理器，也就加速了一倍。任何操作都不能超过光速，所以局部性原理很重要。最早的dekker的算法就是错的（证明有问题） 。还有Peterson算法，它们都非常复杂。model checker能自动遍历状态机空间。是一个形式化验证的工具，核心思想是通过穷举状态空间来证明或者证反系统的正确性，无需人工构造证明。但是直接实现peterson算法，因为指令重排序（关闭内存屏障），会出现错误。在加了内存屏障后，编译器会阻止一些指令重排等优化行为。比如x86的mfencearm的dmb ishrisc-v的fence rw，rw但是peterson算法只能解决俩个线程的访问。实际上我们实现互斥是通过硬件解决方案。计算机系统也是我们造的，我们可以在load和store上实现互斥。这是computer science和自然科学不同，许多游戏规则是我们定的。有没有stop the world指令呢？有的兄弟有的，最早单线程cpu就是用cli（x86）指令来陷入内核。eflags里有一个bit是IF(0x200)，对于单机处理系统，死循环=计算机卡死。默认操作系统的中断是不允许关闭的。不然容易单线程死循环。但是对于多处理器的情况来说，事情变得复杂。这时就需要硬件的帮忙。因此实际上只需要实现can_go=√，然后设置为x的原子操作，就完成了stop the world现代操作系统中，许多CPU都提供了原子的CAS指令，无需切换到内核态。这就叫做原子指令。一个不会被打断的load+计算+store。同样的我们可以实现多把锁。自旋锁的scalability问题：除了获得锁的线程，其他线程都在空转，一核有难，八核围观。如果代码执行很久，不如把处理器让给其他线程。应用程序，不能中断，持有自旋锁的线程被切换，导致100%的资源浪费。java的synchronized的底层锁升级为重量级锁的时候，使用了systemcall。在jvm中mutex的底层在linux的环境下就使用了pthread mutex lock。但要注意这个锁默认是不可重入的。而atomicinteger等原子变量使用的是死循环。public final int getAndAddInt(Object o, long offset, int delta) { int v; do { v = getIntVolatile(o, offset); } while (!weakCompareAndSetInt(o, offset, v, v + delta)); return v; }因此简单的实现是将锁的实现放到systemcall就好了因此提供了pthread mutex lock编程的时候直接用这个即可，没有争抢的时候性能很好，甚至都不需要trap进操作系统内核更多线程争抢的时候也有相当好的scalability。一般来说atomic相比mutex更快，但是mutex可以锁住更多的代码。其中spin是一个自旋锁。futex（Fast Userspace muTEXes）是Linux内核提供的一种高效同步原语，用于实现用户空间的锁和同步机制。它结合了用户空间的快速路径和内核空间的慢速路径，在无竞争情况下完全在用户空间操作，有竞争时才进入内核。同步，条件变量synchronization同步的定义为，俩个或俩个以上岁时间变化的量在变化过程中保持一定的相对关系。我们希望控制事件发生的先后顺序比如a->b->c互斥锁能确保分开abc，做不到顺序控制我们希望形成受我们控制的happens-before关系。一个简单的例子是合唱团。什么是事件，什么是顺序。每个乐手都是一个线程（状态机）事件：发出节拍、演奏节拍顺序：发出节拍i->演奏节拍i这个模型允许一个节拍的演奏时间过长同一线程内的事件天然存在happends-bnefore的关系，在多处理器系统中可以并行执行。那么如何在并发的情况下实现happends-before呢？实现A->Bvoid T_player(){ for(int i=0;i<n;i++){ while(current_beat<i); play_beat(i); } }大致可用，但current_beat存在和sum++类似的问题。因此我们想让操作系统替代自旋的循环。while(!can_proceed)发明条件变量机制。一个理想的APIwait_unit(cond)//把代码编译到内核里条件不满足是等待（让出cpu），操作系统提供了以下api。wait直接等待signal/broadcast唤醒所有等待的线程。我们可以让b先等待，等到a执行完成了，让a来唤醒b。条件变量通常需要和互斥锁一起使用。通常要先上锁在给条件变量。条件变量（Condition Variable）是 C++ 中用于线程间同步的重要机制，它允许线程在某些条件不满足时挂起等待，直到其他线程改变了条件并通知它。一个经典的同步问题是生产者消费者问题。99%的问题都可以用生产者消费者问题来解决。生产者：如果缓冲区有空位，放入，否则等待如果管抽取有数据，取走，否则等待。一个等价的描述是先打印左括号，再打印右括号。生产=打印左括号，消费=打印右括号。括号嵌套的深度等于缓冲区的数量。pthread_cond_signal唤醒至少一个正在等待该条件变量的线程（具体唤醒哪个取决于调度策略）。pthread_cond_broadcast:唤醒所有正在等待该条件变量的线程。消费者的代码是类似的。只不过++变成了--。总的来说流程是获得锁，判断条件是否成立。如果成立就做自己事情（消费或者生产）。最后唤醒其他线程。 计算图(Computational Graph)是描述计算任务的有向无环图(DAG)，其中节点表示操作或变量，边表示数据依赖关系。在分布式系统和深度学习框架中，计算图的并发执行与控制是关键优化技术。在计算图中，上一个节点就是生产者，下一个节点就是消费者。信号量互斥锁实际上也是happens-before。互斥锁的原语实际上是可以进入临界区当且仅当没有人持有这个锁。实际上实现了加锁和解锁的happens-before一个奇妙的想法是，创建锁时，立即获得它（总是成功）其他人需要获得锁的时候就会等待，此时release就实现了happens-before。比如先有一个锁，A线程进行解锁操作，B线程进行上锁操作。B线程必须等待A线程解锁了才能上锁。这样就能实现类似join的语义用互斥锁也可以实现计算图。可能当前线程加的锁需要在别的线程进行解锁。会让人觉得很奇怪。在paxos线程库中的锁，必须同一个线程加锁和解锁。Acquire-relise实现计算图过程如下每一条边都飞陪一个互斥锁初始时，全部处于锁定状态对于一个节点它，需要获得所有入边的所才能继续。可以直接计算的节点立即开始计算计算完成后，释放所有出边对应的锁。因此我们实现了用release-acquire实现了happens-beforeAcquire是等待信号，release是发出信号信号可以理解为现实中的资源许可。信号量(Semaphore)是操作系统提供的一种进程/线程同步机制，由荷兰计算机科学家Dijkstra在1965年提出，用于解决并发环境下的互斥与同步问题。信号量分为P（prolaag）和V（Verhoog），其中P必须消耗一个信号量才能继续，而V则可以创建一个信号量。信号量是互斥锁的扩展，因此信号量可以直接当做互斥锁来用。sem_t sem = SEM_INT(1); //声明并初始化一个名为 sem的 POSIX 信号量，初始值为 1 void lock(){ P(&sem); } void unlock(){ V(&sem); }信号量可以用来方便的管理计数型的资源。信号量是一个整型计数器，用于控制对共享资源的访问。主要操作：P操作（Proberen，测试/等待）：尝试获取资源，若信号量值≤0则阻塞。V操作（Verhogen，释放/发送）：释放资源，唤醒等待的进程/线程。技术上可以多次调用v，但会改变信号量的语义，每次V都会+1。public class SemaphoreDemo { private static final int THREAD_COUNT = 30; private static ExecutorService threadPool = Executors.newFixedThreadPool(THREAD_COUNT); private static Semaphore semaphore = new Semaphore(10); // 允许10个并发 public static void main(String[] args) { for (int i = 0; i < THREAD_COUNT; i++) { threadPool.execute(() -> { try { semaphore.acquire(); // 获取许可 System.out.println("save data"); Thread.sleep(2000); semaphore.release(); // 释放许可 } catch (InterruptedException e) { e.printStackTrace(); } }); } threadPool.shutdown(); } }java中使用信号量。用途Semaphore：用于控制对共享资源的访问线程数量（限流）CountDownLatch：用于等待一个或多个线程完成操作计数机制：Semaphore：可以动态增减许可证数量（通过acquire/release）CountDownLatch：计数只能减少不能增加（countDown()）重用性：Semaphore：可以重复使用（获取和释放许可证）CountDownLatch：一次性使用，计数到0后不能再重置信号量可以优雅的实现生产者和消费者问题。从生产者消费者的角度来看，信号量比条件变量更好用。信号量，干净，优雅，的解决了生产者消费者问题。但count不总是能代表很好地同步条件条件变量更加万能:适用于任何同步条件,代码里还会存在spin loop。条件变量中的判断表达式可以是任何的代码。信号量不太好表达二选一。信号量能解决哲学家问题（死锁）。信号量通过确定能上桌吃饭的人的数量来解决这个问题的。另一个解决问题的方式是，给叉子编号，总是先拿小的。或者创建一个服务员线程，给这些哲学家发叉子。这就又把问题简化为了一个生产者消费者问题。其实也可以用信号量实现一个条件变量。操作系统底层用的是futex。因此信号量难以解决更多的问题。编发变成更多的是使用绝对正确的模型，然后直接使用。信号量是互斥锁的推广，通过计数实现同步。符合这个抽象的时候能够带来优雅的代码。信号量不是万能的。真实的并发理论上对于一个数学中的函数，输出是确定的。但是并发编程打破了这一点。比如不同的线程访问同一内存，并只少有一个是写。这就构成了数据竞争（data race）weak memory model允许不同观测者看到不同的结果。通过mutex锁就可以避免对一个变量的同时的访问。c++11开始data race 是未定义行为。实际系统内存可以是全部变量，可以是栈可以是队。访问可能发生在任何代码。有序上锁能解决死锁的关键逻辑是因为，当有节点可以获得锁时，那么它一定可以向后执行。防止出现循环的资源等待问题。一个简单的想法是，每次acquire/release都printf打一个日志。如果一个线程既有A->B也有B->A就报告死锁。但这是程序巨大的心智负担，必须避免LockDep:另一个方法是动态维护以来图和环路检测。如果在有向图中检测到环路，那么就代表可能出现死锁。（但是可重入锁可能得用其他方法解决）。97%的非死锁并发bug都是原子性问题。如何避免在没有锁的情况下，访问相同的变量呢？还可以用lockDep解决这个问题。比如每次访问变量时都输出当前有的锁，不允许访问内存时有不相交的锁。c语言有个工具-fsanitize=thread。是GCC和Clang编译器提供的用于检测多线程中数据竞争的工具。模拟物理的相同具有embarrassingly parallel特性。javascript中不允许并行，但允许并发。允许网络访问请求和sleep在后台执行。嵌套中嵌套代码会导致回调地狱。现在可以通过promise来描述计算图来解决这个问题。js还可以定义async和await来等待promise的返回值。CPU和GPUCPUCPU之间的所有程序都是并行的。CPU在能效和性能之间选择了后者。CPU中每个电路门的翻转都会产生热量。CPU里编译器会消耗巨量的能量，这些能量能够使计算快速完成。但不等同于单位时间内完成尽可能多的计算。现在CPU进入了dark silicon，暗硅时代。功耗墙：纵使有更大的电路，热功耗限制了性能上限。一条指令浪费的大量大致是定数，处理的数据越多浪费越少。或者用更多更简单的处理器。多处理器系统、异构多处理器，同等面积，处理器越简单数量越多。SIMD（single instruction，multiple data）可以让一条指令对连续操作做相同的运算。比如对四个float做4次乘法。之后这个数越来越大被扩展到了128,258bit的操作。MMX->SSE->AVX->AVX51264（mm）->128(xmm)->256(ymm)->512(zmm)比如512就可以放多个float64。著名的avx512中的512就是寄存器的宽度。SIMD指令依然是在CPU里调度的，因此不能做的太宽。并行度有限。因为单cpu运行受限，因此引入了多CPU。后面还引入了大小核。GPU同等面积，处理器越简单，数量越多。我们甚至不需要处理器有CPU指令集的计算能力。因此有专用领域的 加速器ISP image signal Processing（手机相机）GPU: Graphics processing unit（图形渲染）DPU:data processsing Unit（网络、数据处理）DMA就是一个很好的例子。这个cpu的一部分只有很小的功能，就是进行内存拷贝。在早期的计算机中DMA通常是主板上的独立芯片如intel8237现代的DMA控制器通常集成在CPU/Soc的内部。但是对于CPU来说渲染画面是不可能完成的任务。比如NES中有256x240=61K个像素（256色）60FPS-> 10K跳指令完成61K像素级的渲染。因此它的设计是不允许屏幕上所有像素运动。以8x8的贴块为绘制的基本单位。背景画布+动态前景之后我们有了2d的渲染管线。允许把一个图片拉伸到不同的位置然后进行投影等渲染。无论如何CPU只负责描述，让专用处理器来负责绘制。由于任何一个面都可以绘制为三角形。然后经过fixed -function pipline。本质上openGL这样的标准定义了一个函数，可以接受对当前图形的描述，这个描述中有顶点的关系，贴图，材质纹理，光照信息。然后就可以把图像算出来。然后rendering pipline逐渐从固定功能到了可编程。可以单独为每个像素进行编程。还有函数可以对每一个顶点来调用。这样就可以做出一些爆炸效果。英伟达在99年的时候实现了第一个着色器。然后我们发现可以将俩个像素点通过矩阵进行叠加。可以叠加俩个图片。SIMT那么为什么不把shader实现为线程呢？然而cpu去做shared memory很难实现，但是英伟达做到了。在GeForce 8800中首个cuda GPU（首个支持cuda的cpu）有128个cores此时桌面端的intel只有2C4T。The frist GPU to utilize a scalar thread processor, eliminating the need for programmers to manually manage vector register.5080现在有10752个cuda核心。GPU底层是通过single instruction multiple threads做到的。CPU中每个CPU核心都有自己的缓存。它们每个的程序计数器和register都可能是不一样的。它们在并行执行的时候可能还需要访问共享内存。所有的核心执行相同的代码ALU（算术逻辑单元，Arithmetic Logic Unit）是计算机CPU的核心组件之一，负责执行所有的算术运算（如加、减、乘、除）和逻辑运算（如与、或、非、异或等），是处理器完成实际计算的关键部分。如果想要并ALU就不能省,寄存器也不能省。但是程序计数器可以省略，或者说要求所有的线程执行同样的代码。假设row和col都在寄存器里，我们可以通过给每个gpu核心运行自增当前索引的值。就能得到不一样的结果。虽然程序计数器同步了，但是gpu核心中的值是不一样的。其实底层就是转换成了单指令，多线程。这个操作变成了天生的向量运算。显卡中内存的带宽可以比cpu大很多。cpu经常要做缓存行和内存的交换。类似神经网络，就很适合用GPU进行计算。