在设计软件系统时,需要将系统功能划分为若干个模块。每个模块会写在一个或者多个文件中。
为了将这些模块组合成一个可执行程序,需要使用编译器把它们编译为对象文件(.o文件)。对象文件中包含机器代码段、只读数据段等重要信息。
每个模块的对象文件都从地址0开始。为了防止地址冲突,需要对象文件链接工具来解决这个问题。
对象文件中含有符号表,记录了模块中定义与引用的全局变量和函数及其地址。未定义的符号会标注为”未定义”。
链接工具将对象文件中的代码段、数据段等联系起来,为每个模块分配独立的内存空间,从而生成一个完整的可执行文件。
库文件实际上是多个对象文件用索引信封打包而成的归档文件。库中的对象文件也会参与链接。
将多个模块的对象文件通过链接器合成一个可执行文件需要进行以下步骤:
找到每个模块中未定义符号的定义位置。
将对象文件中的代码段、数据段等链接到一起。
为每个模块分配独立地址空间,解决地址冲突问题。
生成一个完整的可运行的可执行文件。
这样就实现了软件系统的模块化设计思想。
软件模块通过过程调用来交互。过程调用会形成过程契约:
过程调用遵循栈 discipline:被调用程序必须保持调用者压栈前的栈状态不变,只能修改指定结果寄存器。这使得过程调用模型可以支持复杂的嵌套和递归调用。
但是,这种软件模块交互带来的模块性较弱,被称为软模块性。任何一个模块的错误或崩溃都可能影响其他模块。
强制模块性通过隔离错误,使模块间的错误无法传播。常见实现方式有:
客户端服务者架构:将程序划分为客户端和服务器模块。客户端仅通过接口与服务端交互,减少错误传播。
对象模块化:每个对象独立运行在自己的内存空间,错误不会影响其他对象。
进程模块化:每个模块在独立进程中运行,进程崩溃不会影响其他进程。
虚拟化:利用虚拟化技术将模块隔离到不同的环境中运行。
强制模块性可以有效防止模块错误互相影响,提高系统可靠性。但需要额外的开销来实现模块间的数据传递和通信。
如果多个模块直接共享同一内存空间,会带来几个问题:
模块间无法隔离。一个模块修改的内存地址会影响其他模块的执行。例如模块A可以随意写入模块B的内存,导致B工作不正常。
错误难以排查。如果A模块将B模块的某条指令改写,B模块执行时可能会发生非法指令异常,但错误出现时A模块可能已经结束,难以定位问题原因。
调试困难。比如错误10,000条指令之后才出现,需要跟踪A和B模块在很长时间内的状态变化才能定位问题。
为每个模块建立自己的虚拟地址空间。模块通过虚拟地址访问内存,内存管理系统会将虚拟地址转换为实际物理内存地址。
每个模块拥有一个32位虚拟地址空间。
虚拟地址空间中的地址仅在模块内有意义,通过内存管理系统映射到实际物理内存地址。
不同模块之间虚拟地址可能对应不同物理内存,实现地址空间隔离。
内存管理系统对每个模块内存访问进行检查,验证访问地址是否合法,防止非法访问其他模块内存。
通过地址空间隔离,在程序级别实现模块间的安全隔离。
系统会运行一个内核程序,负责管理所有虚拟机和实际物理资源,对每个模块内存访问进行检查和映射管理。内核可以看做一个管理虚拟化环境的“监督者”。
线程是执行执行单元,用来描述程序在某个特定时间点的状态。线程包含:
使用线程可以实现多任务处理。多个线程可以共享进程内存,但每个线程都有自己单独的运行环境(如寄存器和栈)。
线程主动调用yield()函数来放弃CPU,让其他线程运行。但一个线程如果不主动放弃,其他线程就得不到运行机会。
操作系统内核定期逼迫当前运行线程放弃CPU,让 scheduler 选择下一个运行线程。保证每个线程都有公平运行机会。
如一个游戏程序可能包含多个线程:
这些线程共享进程地址空间内的全局变量。但每个线程都有自己的运行环境。
yield()函数实现线程上下文的保存和恢复:
通过不断地在不同线程间进行上下文切换,实现了在单核CPU上实现虚拟多处理器的效果。
之前多线程Web服务器程序中,HTML线程和磁盘线程使用共享队列进行通信,但是直接使用while循环可能导致资源浪费。
为此,可以使用事件计数和等待/通知机制进行同步协调:
wait会检查事件计数的值,如果小于等于给定值,线程就进入等待状态不再被调度,直到被通知恢复运行。notify会唤醒等待在该事件计数上的一个或多个线程恢复运行。这样,HTML线程可以等待事件计数used大于0,磁盘线程等待free大于0。磁盘线程写入队列后,通知free让HTML线程运行。实现了while循环的等待效果,但避免了资源浪费。
为了使计算系统运行效率高,主要有三种技术:
并发性:允许系统同时执行多个操作,例如读写磁盘和生成HTML页面。
缓存:保存先前计算或读写结果,以便后续重用,避免重复工作。
调度:根据请求的特点合理安排它们的处理顺序,提高整体利用率。
这三种技术将通过Web服务器示例进行说明和应用。
上次课介绍了分级Web服务器系统,包含网络模块、HTML模块和磁盘模块三个阶段。
为提高磁盘模块性能,可以使用缓存技术。
缓存满时需要驱逐数据:
LRU策略较符合局部性原理,更合理。
计算机网络将多台计算机相互连接起来,方便资源共享。下一步将介绍网络基础知识。
最佳努力网络如互联网中的分组交换网络通常不保证:
会出现延迟。这主要包括信息在网络中传播的时间以及通过网络传输信息的时间。
可能会丢包。这主要由于拥堵或者网络中设备故障导致。
可能会重新排序包。由于不同包可能通过不同路径,所以接收顺序与发送顺序可能不同。
可能会重复包。比如为了解决丢包问题,网络可能会重新发送某些包,从而导致重复。
网络拥堵很难预测,这必然导致链路之间的队列。
网络通常采用分层模型来简化复杂性:
每一层针对下层提供简单的接口,上层无须了解下层的复杂细节。
每一层完成特定的工作,不同层之间通过标准接口进行交互,这样可以独立developed和optimized每一层。
如果某一层出现问题,只需要修复该层,不会影响其他层。
新技术可以加入现有层级,或者添加新层级,从而实现向下兼容。
网络通信可以分为以下几个层次:
物理层:负责如何在链路上发送和接收比特流。
数据链路层:负责在局域网内如何发送帧并进行错误检测。
网络层:负责如何在多个网络之间进行路由和转发数据包。
运输层:负责如何提供可靠数据传输服务和端到端流量控制。
应用层:提供各种网络应用服务。
不同层通过标准接口进行交互,各层实现的协议定义了不同层的通信规则。这种分层设计简化了问题,并提供向下兼容性。
链路层主要负责以下工作:
帧传输。链路层向下传输数据帧,将数据划分为帧进行传输。
框架。链路层需要为每一个帧添加头部和尾部,以标识帧的开始和结束。一种常用的方法是在头部和尾部添加特定符号。
曼彻斯特编码。链路层采用曼彻斯特编码将数字信号转换为适合传输的电信号。
错误检测。链路层通过添加校验和信息检测传输错误。
网络层主要负责两项工作:
转发。网络层根据目的地址决定向哪个接口转发数据包。每个节点会维护一个路由表,根据目的地址查找下一跳接口。
路由。网络层通过路由算法和协议确定不同节点之间的最佳通路。
具体来说:
转发决定将数据包送往下一跳节点。每个节点通过路由表进行转发。
路由确定不同节点之间最优路径,将信息输入到各节点的路由表中。
路由表记录不同目的地地址的下一跳接口。
数据包在源、中间和目的节点之间通过封装传递,进行多层互操作。
仅网络层和链路层参与中继节点的转发处理,而终端节点只参与应用层和传输层。
数据包从应用层下送到链路层,每层都可能添加头部和尾部,但不查看上层数据。
今天主要讲解网络层中的结束层(end-to-end layer)。
结束层的作用有:
2.提供数据分片功能。网络层的数据大小可能有限制,结束层可以将大数据分割成小段分片,然后单独通过网络层传输。
3.提供可靠数据传输服务。结束层为应用层提供一个流(stream)的抽象概念。在这个流里,数据可以保证顺序传输,且不会丢失分段。这意味着应用层收到的数据的顺序和发送的顺序一致,没有遗漏。
4.处理网络的“尽最大努力传输”特性所带来的问题。如:
mensagem丢失:结束层采用“至少一次传输”和“最多一次传输”机制来解决。
消息重排:结束层后续会介绍如何处理这个问题。
延迟和拥塞:后续会详细介绍。
结束层通过以下两种机制来实现“至少一次传输”:
接收端在接收到消息后,会发送一个确认报文(ACK)回送端,以确认收到该消息。
发送端在发送消息时,会对消息加上一个唯一的随机号(nonce)。接收端在ACK报文中回送这个nonce,以识别是确认哪条消息。
这种机制可以保证,只要网络不完全崩溃,则消息几乎可以确定送达。如果消息没有送达,接收端也知道发送端可能没有收到ACK。
后续会详细介绍“最多一次传输”机制,以解决“至少一次传输”可能引起的重复传输问题,同时实现了“确切一次传输”的要求。
如果每个电脑通过独立的链路相连,网络建设成本将极高。网络的高效运行需要各节点共享链路资源。
共享带来问题:如何合理地共享带宽资源,使各数据流总带宽不超过链路容量。
发送者根据接收者反馈调整发送率,避免拥堵。关键是如何获得实时资源拥塞信息以做出正确决策。
网络共享面临的核心问题是如何合理分享链路资源。拥堵控制方案需要考虑大规模、动态性与异地控制三大困难。
DNS(域名系统)是用于将便于记忆的主机名和难以记忆的IP地址进行映射的系统。它主要解决以下问题:
使用IP地址进行通信较为不便,主机名更容易记忆。
允许主机资源位置变化而不影响通信,如网站服务器搬迁时不需要更改通信地址。
为分布式系统提供模组化,不同组件可以独立变更而互不影响。
DNS的主要设计目标是可扩展性和可靠性:
可扩展性。采用分布式数据库模型,每个组织管理自己名称空间部分,人工和技术资源得以分散,系统整体资源消耗增长较慢。
可靠性。通过技术如副本保持等保证系统整体可用性,不能成为因解析失败引起的单点故障。
DNS通过以下步骤实现主机名与记录的映射:
将域名空间分为等级结构,每个组织管理自己域下主机名与记录的对应关系。
当需要查询某主机名时,先在本地缓存中查找,没有再向上级DNS服务器查询。
若上级服务器没有条目,会向更高层级服务器查询,层层传播直到顶级域名服务器。
各层级服务器都可能保有其他服务器的资料副本,实现冗余以提高可靠性。
最终得到记录后,本地 DNS 缓存并向请求主机返回,完成一次解析。
DNS定义了多种记录类型用于映射不同信息,常见类型包括:
这些记录通过DNS协议实现分布式数据库,支持主机名与网络资源的高可用低耦合对应关系。
故障是系统组件或子系统中的任何缺険,如果故障没有被触发则不会产生错误。当故障被激活后可能会产生错误。如果错误没有被妥善处理,可能会导致系统故障。
故障分为暗在故障和主动故障。暗在故障如程序bug,不会立刻产生影响。主动故障发生时会导致错误。
错误如果没有被隐藏或纠正,可能会导致系统故障。系统设计目的是尽量避免此情况的发生。
有两种方法构建不容易发生故障的系统:
确保系统每个组件都永远不会故障。这种方法实现难度大,成本高。
利用不稳定组件构建健壮系统。系统应当可以容忍下层组件的故障。
后一种方法是较现实的选择。系统必须能够隐藏或纠正错误,避免错误进一步引起系统故障。
以模块M1调用M2和M3为例:
M2内部有个M4模块。如果M4内部硬件发生故障导致错误,可能会传导给M2 observed。
M2需要隐藏此错误,否则错误会传导给M1。
如果M2也无法隐藏错误,错误就会让M1 observed一个故障。
我们的目标是设计使得顶层系统M1不会发生故障,尽管下层模块可能会出现错误。
许多我们学习过的例子都运用了一些容错方法:
同步、冗余路由、重传机制、CNAME记录复制等都是基于模块/链接的冗余设计的。
流量控制避免拥塞也是一种方式。
这些方法的共同点都是利用一定程度的冗余来增强系统的弹性。我们需要系统地学习这些容错设计原则。
可恢复性指一个操作或者动作的执行,无论成功还是失败,应该让系统最终呈现出完全执行成功或者完全未执行的状态。
具体来说,如果操作失败,系统需要有能力回退已经执行的部分,让系统的状态看起来就像这个操作从来没有开始执行一样。
比如银行间转账操作,操作会读取原账户余额,减去金额,再写入目标账户增加金额。如果执行过程中间发生失败,系统需要有回滚机制,回滚已经执行的部分,让系统状态回到操作开始前。
隔离性是指多个并发执行的操作,其结果应与某个顺序执行结果相同。
举例来说,如果有两个银行转账操作同时进行,一个从A户转100元到B户,一个从A户转200元到C户。操作结果应该等同于这两个操作按某个顺序执行。如A转100元到B户后,再转200元到C户,或者反过来。
满足恢复能力和隔离性,可以防止部分状态和并发冲突问题。
具体来说,恢复能力强调操作必须全成功或全失败,隔离性强调多个操作结果应等同于顺序执行。二者都力求避免系统处于半成功半失败的状态。
将具体实现方案放在下一节介绍。
本次讲授将讨论如何实现更大规模的原子操作。在上次讲课中,通过保持两个版本的方式(“d0”和”d1”),实现了单个扇区读写的原子操作。
但是,在实际应用中,数据量通常远远大于一个扇区。需要定义程序员需要遵循的规则,以实现复杂操作的原子性。
程序员需要调用begin_recoverable_action()开始一个可恢复操作。在操作中,可以读取和修改数据,但只能在中间状态下操作数据,不能将结果暴露出去。
调用commit()后,表示要将结果持久化下来。此后才允许对外暴露结果。如果在commit()前发生错误,需要将所有数据还原。
调用abort()可主动回滚操作。系统也可能会因死锁等原因自动调用abort()。
为了遵守“永不修改唯一副本”原则,版本存档方案下,每次写入数据都不直接覆写,而是创建新版本。通过指针链接所有版本。
每次write()实际上是向版本链表添加新节点,而不是直接覆写。commit()是将当前版本标记为可读版本。
abort()需要回溯版本链,将数据还原。两种存储方式比较:
本次课介绍了可恢复操作的编程模型,以及基于版本链实现原子操作的原理。为后续讨论锁机制和隔离性奠定基础。
原子性需要满足两个属性:可恢复性和隔离性。
可通过日志记录实现。当操作失败时,通过倒叙日志回滚未完成操作。
日志包含两种操作:
撤销操作(undo log),记录修改前的值。用于回滚未提交操作。
重做操作(redo log),记录提交操作,用于完成部分写入缓存但未写入数据库的操作。
若数据库同步写入,只需要撤销日志。若数据库异步写入,同时需要撤销日志和重做日志。
检查点技术可以优化恢复速度。系统定期将已提交结果写入检查点日志,恢复时仅需回溯到检查点日志位置开始。
隔离性保证多个并发操作之间不会互相影响。下节课将详细介绍隔离性实现方法。
日志 和 检查点机制为实现隔离性和可恢复性提供了基础支持。两者在实际操作中也存在交互影响。
为了解决故障,我们提出模块必须保持原子性。原子性具有两个方面:
一次完成或不完成(Recoverability)。这意味着操作要么全部成功,要么全部失败。
隔离多个并发操作(Isolation)。这让多个操作看起来是独立的。
我们提出一个“永不修改唯一副本”的金牌法则,来保证recoverability。然后利用这个法则构建可恢复的存储块,提出两个方案:
使用版本历史。为每个变量创建多个版本,而不是直接修改。
使用日志记录。发现版本历史低效,采用记录操作日志的方式。
我们的目标是保证行为顺序一致性(serializability)。也就是允许操作以任意顺序运行,但结果与某个顺序运行相同。
通过加锁来实现隔离性。关键是锁能形成的行为图没有成环,这样就能保证行为顺序一致性。
我们具体介绍了两相锁定协议。它规定:
通过这种方式,两相锁定能够保证行为图没有成环,从而实现行为顺序一致性。
两相锁定存在死锁问题。当多个操作互相等待对方释放锁时,就会发生死锁。
我们提出一个办法是设置行为定时器。如果操作长时间无法进行,就视为死锁,主动把一个操作中断。这能解决死锁问题。
原子操作意味着这个操作要么全部完成,要么全部不完成。多机房原子操作指操作包含在多个不同机房中的多个子操作,要求整体看做一个原子操作。
举个例子,一个旅行网站既可以在捷蓝航空网站预订机票,也可以在美国航空网站预订机票。用户想一次性预订这两家航空的航班,要求整个预订过程作为一个原子操作。
如果没有特殊支持,当捷蓝航空网站预订成功后,美航无法预订时就会出现问题,捷蓝航空的预订无法撤销。为实现多机房原子操作,需要捷蓝航空和美航与旅行网站协作。
如果所有操作位于同一台机器,就成为嵌套原子操作。如用A和B代表两家航空的预订操作,有如下要求:
为解决这个循环依赖问题,引入一个监督节点S。S负责决定整个操作是否提交。
A和B先进入“暂定提交”状态,将控制权交给S。S可以同时决定A和B是否真正提交。通过这种方式,可以保证A和B同时决定是否提交。
操作如何进行撤销和恢复也是一个关键问题。日志记录协议可以解决这个问题。
其思路是:每个操作都记录必要的元数据到日志文件中,称为“前向日志”。如果操作成功完成,再记录一个“提交记录”。
如果系统崩溃,下次启动时按日志中的顺序,将未提交的操作进行回滚,已提交的操作不做任何事。通过这种方式可以保证一致性。
版本历史也可以实现操作的撤销与恢复。将每个操作产生的状态保存成一个“版本”。系统崩溃后找最新版本还原状态。
为隔离并发运行的操作,常用方法有:
总的来说,通过监督节点、日志记录、版本控制等技术可以实现多机房范围内的原子操作,同时兼顾一致性与可恢复性。
保护包括容错性和可恢复性,是系统的一个重要属性。设计可靠和安全的系统会影响整个系统的设计,是一种横切各个模块的问题。
安全的主要目标是保护用户数据不被恶意用户访问或篡改。同时也要保证好人可以正常访问数据。安全依赖于具体应用,不同应用的数据访问权限和私密性要求不同。
随着互联网商业化和规模扩大,计算机安全问题也日益严重。许多企业和组织的数据被黑客攻击窃取,例如个人信息、学术记录、银行数据等。这类攻击手段很多,包括破解网站、入侵计算机、发送钓鱼邮件等。
安全机制的目的是实施安全策略,如数据加密保护数据不被未经授权用户访问,认证授权控制访问等。这与现实生活中的锁和法律类似。
计算机系统与现实世界有以下不同:
计算机技术更新速度快,不断出现新攻击手段。
计算机攻击可以很快和低成本地下达成,如蠕虫病毒很快就能感染大量计算机。
法律法规滞后于技术更新,新事物法律地位未明。
学习计算机安全,需要了解安全概念和原理,以及各种安全机制在系统各个层次的应用,从而设计出可靠安全的系统。
我们先回顾上节课关于RSA协议的内容:
RSA协议是一种公钥加密算法。它使用两个密钥:公钥和私钥。公钥包含模数N和指数e,私钥包含模数N和指数d。
消息通过公钥加密,只能通过私钥解密。而通过私钥加密的消息,只能用公钥解密。
RSA的安全性依赖于将大整数分解成质数的难度。随着数字长度的增加,利用目前最好的算法分解一个数字需要的时间以指数方式增长。
密码学可以用来构建三类基本原语:
签名和验证(sign and verify):用于实现身份验证。通过私钥签名,公钥验证消息来源。
加密和解密(encrypt and decrypt):用于保密性。通过公钥加密,私钥解密,只允许特定接收者读取消息。
哈希(hash):用于数据完整性。用于检验消息是否被篡改。
将消息使用私钥签名,别人使用公钥验证后才能确定消息来源。这就实现了身份验证。
例如:Alice 用私钥对消息进行RSA签名。Bob收到消息后用Alice的公钥验证通过,就能确定消息确实来自Alice。
将消息使用公钥加密,只有持有对应私钥的接收者才能解密读取消息,达到保密的目的。
例如:Alice 用Bob的公钥对消息进行RSA加密。Bob用自己的私钥解密后才能读取消息内容。
但实际操作中,还需要对原始消息进行格式处理,避免直接使用RSA对太短消息进行加密,才能确保安全性。
通过利用以上密码学基本原语,我们可以构建出更高层次的安全协议来实现身份验证、数据完整性和保密通信等安全目标。
继续讨论保护措施,主要包括身份验证、授权和机密性。
身份验证用来确认用户的身份。授权用来决定用户是否有权限执行某些操作。机密性用来隐藏信息内容,使得未授权用户无法知道通信细节。
主要包含签名和验证、加密与解密。
签名接受消息和密钥,生成数字签名。验证接受消息、签名和另一个密钥,判断签名是否有效。
加密接受消息和密钥,生成加密后的消息。解密接受加密消息和密钥,还原原始消息。
如果密钥相同,为对称加密。如果密钥不同,一般为非对称加密。
利用身份验证建立安全通信通道。
步骤一:利用数字证书完成身份验证。
步骤二:利用非对称加密交换对称密钥,再用对称密钥加密实际通信。
Denning-Sako 协议遇到了适当性问题。
具体来说,Alice 只对加密后的共享密钥签名,而没有对整个消息签名。这可能导致其他人伪造身份。
改进之处是:
不再单独对密钥进行签名与加密,而是对整个消息进行数字签名和加密操作。
在消息中明确标注发送方和接收方,以保证消息正确传达对象。
数字签名确保只有Alice能产生该消息,防止他人伪造。
以上修正解决了Denning-Sako协议的适当性问题。
老师给出了几项关于下一节课的通知:
讲设计项目的简短报告。学生需要准备项目设计简报,在实验室课上进行报告。
提供了一份指导页,阐述报告内容需要包含什么。报告时间短,不需要准备太多内容。
如果对于报告内容不清楚,可以查看网络页面查询。
老师使用TCP Dump命令监测了上课期间学生电脑的网络流量。其操作过程如下:
使用sudo命令以管理员权限运行TCP Dump命令。
TCP Dump命令监视指定网卡(en1, 即无线网卡)上的所有网络包。
分析收集到的网络包,提取其中的HTTP请求信息。
通过请求页面发现学生浏览的网站。
大部分流量平淡无奇,但也发现有几个网站比较有趣:
有学生在搜寻USB存储产品,并找到了Micro Center网站。
有学生多次搜索电影信息。
有学生研究了即时通讯软件Gaim的加密插件GM Encryption,并最终下载并使用该插件。
GM Encryption可以对Gaim进行对话加密。它通过生成公私密钥对,使用RSA算法实现消息加密与数字签名。
监测结果显示,一个学生下载并安装了GM Encryption,但后来与不支持该插件的人进行对话时,话中内容并未加密保护。
这点出网络安全很难把控的原因:即使措施已就位,但与不兼容设备进行通信时,信息难免外泄。体现出安全通常难直接验证,只能通过被 penetrating 攻击时才能暴露问题。
老师结束致意,提醒学生在网络上传递隐私信息时需要更加小心。网络安全需要长期维护,不容疏忽。
讲师通过一个简单的源-目的地-网络模型,解释如何在互联网中控制某些言论。
美国宪法第一修正案规定,国会不得制定限制言论自由的法律。
但是,第一修正案并不意味着任何言论都受保护:
高校如MIT制定的言论规则,不等同于政府机构的规则:
视频概括了互联网言论管制的一些法律概念,解释了第一修正案及其对不同主体的约束力,以及言论自由的一些限制范畴。通过一个简单模型,说明了互联网上控制信息流的不同路径。