Publish/Subscribe in P2P Networks 谭茂洲 连慧娟 陆欢 黄达理

内容提要 点对点peer-to-peer技术 Publish/Subscribe研究 一个基于P2P的pub/sub系统

点对点peer-to-peer技术

对等网络(P2P网络) 对等网络(P2P网络)是分布式系统和计算机网络相结合的产物，在应用领域和学术界获得了广泛的重视和成功，被称为“改变Internet的新一代网络技术”。

Peer网络节点 行为上是自由的 功能上是平等的 连接上是互联的 任意加入、退出，不受其它结点限制，匿名 不管实际能力的差异 直接/间接，任两结点可建立逻辑链接，对应物理网上的一条IP路径

P2P网络分类 不同类型P2P网络几乎同时出现，无明确界定，大致分为以下几类 混合式P2P网络：C/S、P2P模式的混合

P2P网络的优势 提高网络工作效率 充分利用网络带宽 开发了每个网络结点的潜力 具有高可扩展性(scalability) 良好的容错性

Publish/Subscribe研究

背景（1） 传统网络的信息交互方式 缺点 请求/应答（request/reply） 须同步、紧耦合 对网络的稳定性要求高 客户端严重依赖服务器 系统的扩展能力低下

背景（2） 新一代网络计算特点 一种新的的异步通讯机制 大规模、分散控制、动态性、自治性和松耦合 参与者数量巨大，地域分散（有可能分布在世界的各个角落） 需要传递海量的信息数据。 一种新的的异步通讯机制 发布/订阅（public/subscribe）通讯模型

发布/订阅（pub/sub） 通讯模型的组成 信息生产者 以事件形式发送信息到事件通知服务 信息消费者 向事件通知服务注册订阅，表达对特定信息的兴趣 事件通知服务 充当信息生产者和消费者的中介

pub/sub的特点 优点 松耦合 匿名 多对多通信 可扩展 缺点 在表达能力、路由效率、扩展性、服务质量和安全等方面还存在着较多的问题。

pub/sub的应用前景 适合于基于信息驱动的应用场景中 适合于没有集中控制的分布式环境 适合于构建面向组件的系统 适合于创建监控环境或系统状态变化并对变化做出响应的应用程序 成为大规模分布式系统设计的重要组成部分。

pub/sub系统基本模型 Producer Consumer Notification Service Producer Consumer subscription event notification Notification Service Producer event subscription Consumer notification subscription Producer event Consumer notification

事件和通知(1) 事件（event） 现实世界中的任何数据信息、情况变化、状态变迁都可以表示为一个事件 事件还可以表示触发动作的条件，比如时间事件 所有这些事件的共同点是都可以被硬件设备或软件设施所感知 一个具体的事件实例代表现实世界中的某个数据实体或者发生的某种情况

事件和通知(2) 通知(notification) 当事件被发送到事件通知服务后，通知服务将递送事件到感兴趣的消费者。发送给消费者的信息即称为通知。 一个通知通常是对一个事件的封装，包含描述事件内容的数据或者直接包含事件实例。 通知必须如实反映事件内容的原始含义。

订阅（Subscription） 消费者向通知服务提交订阅来表达对某种事件的兴趣。 当一个事件被发布到通知服务上时 通知服务把这个事件同所有的订阅进行比较 找出其约束条件被该事件满足的订阅 然后发送事件到订阅被匹配的订阅者。

订阅模型 订阅相当于过滤条件，由通知服务负责执行过滤操作。 对订阅来说，过滤的是不匹配的操作，返回”true”或”false 订阅的过滤能力由事件模型和订阅模型共同决定，即取决于事件的数据结构和订阅的过滤模式。 最常见的订阅模型有基于通道的（channel-based）、基于主题的（topic-based）和基于内容的（content-based）模型等。

发布者和订阅者 发布者 订阅者 在发布/订阅系统中，一般称生产者为发布者，指任何产生事件并发布事件的对象 发布事件到通知服务，由通知服务决定事件的转发目的地 无需知道订阅者的具体地址信息、详细数目和有多少订阅者接收到事件 发布行为具有”fire-and-forget”的特点 订阅者 订阅者即为消费者，指任何接收事件并消费事件的对象。

订阅者接受通知模式（1） 拉（Pull） 订阅者主动到通知服务上获取事件 只能接收到注册订阅以后发布的事件，需要订阅者以一种同步的方式获取事件，与通知服务保持连接并等待事件的返回。 类似于request/reply通讯机制，订阅者与通知服务是紧耦合的 一般见于订阅模型比较简单的发布/订阅系统，不适合具有复杂订阅模型的大规模发布/订阅。

订阅者接受通知模式（2） 推（Push） 通知服务主动发送事件到订阅者 订阅者注册订阅到通知服务后，即可释放同通知服务之间的连接 当通知服务转发事件时，发起同感兴趣的订阅者之间的连接，传送事件到订阅者 减耦了订阅者和通知服务，是发布/订阅系统的主要通知模式 几乎所有的发布/订阅系统都实现了push通知模式

事件通知服务 事件通知服务（简称通知服务）即通常意义上的发布/订阅中间件，也称为事件代理，或者提供者。 作为发布者和订阅者的中介，负责管理订阅、过滤事件以及发送事件到感兴趣的订阅者。 减耦了发布者和订阅者。 最基本的通知服务必须对外提供四个功能接口，即发布（publish）、订阅（subscribe）、退订（unsubscribe）和通知（notify）。

通知服务实现方式 集中式 分布式 只有一个通知服务，所有的发布者和订阅者只同这个通知服务交互，订阅和事件都发往这个通知服务 优点：实现简单，易于管理和维护 缺点：随着用户数量的增加，单个通知服务容易成为性能瓶颈，不具备扩展性 分布式 把多个通知服务以一定的拓扑结构，比如星型、环型、无环型和层次型，互相连接形成一个代理覆盖网络 事件和订阅在各代理之间转发 发布者和订阅者连接到某个事件代理注册订阅兴趣、发布事件和接收事件通知

分布式通知服务示意图 Publisher Subscriber Event Broker Event Broker Publisher subscription event notification Event Broker Event Broker event subscription Publisher Event Broker Subscriber notification Event Broker Event Broker subscription Notification Service event notification Subscriber Publisher 分布式通知服务示意图

一个基于P2P的pub/sub系统

组织模型（1） 一个逻辑上的多层次系统，每一个逻辑层l是一个弱连通图，也被称为l层的通信图。 一个对等点p被称为活跃的，当存在至少一个对等点q在l层，且知道p，两个对等点p和q在l层的逻辑连接可以是以下几种情况中的一种 up向上（这两个节点在l层知道对方） down向下（p和q在l层不知道对方） forming（两个节点中至少有一方发起在l层的连接协议）。

组织模型（2） 1 2 5 4 3 节点i也许同时属于几个层 i可能在不同的逻辑层有不同的邻居节点 上图中，节点5在1层的邻居节点是2,3,4，它在2层的邻居节点是1。 1 2 5 4 3

一些重要概念（1） Vl(t) El(t) Rl State(Vl(t)) Ctl Nl(p) 时间t时逻辑层l的活跃节点 时间t时逻辑层l的逻辑连接up Rl 通信图的逻辑方向Gl(t) = (Vl(t)，El(t)) State(Vl(t)) 节点p在时刻t在l层的状态 Ctl 时刻t逻辑层l的配置 Nl(p) 对等点p的邻居节点，即所有使逻辑连接（p，q）是up的q点

一些重要概念（2） lid val x<y q->p Sink 每个对等点的标识符 每个对等点的一个整数变量 当且仅当y = (x+1) mod 3 q->p (valp<valq)或者(valp=valq且lidp<lidq) Sink 称对等点p为sink状态，当对p的任意邻居q都有，q->p

一些说明 初始状态时，系统只有一个逻辑层l0 只有sink节点才能执行任务，当结点处于non-sink时，必须等其变成sink状态才能执行任务

节点的增加和删除 增加或删除节点后，需要在sink节点处执行边的重定向，以保证系统正常运行 重定向方法为改变val，有时也需改变lid 如果sink节点的所有邻居节点都有相同的val值v 将他们的val设置成(v+1) mod 3 如果sink节点i有至少一个邻居节点j满足vali<valj 将j的val设置成jd的所有邻居节点的val的最大值 调整lidi，使lidi>lidj

两种订阅模式 基于主题的订阅模式 基于内容的订阅模式 与群组概念相似，事件的标记基于一套固定的由系统指定的主题/学科命名 每个事件被发布者发送到其中一个群组 一个用户向一个或者多个群组订阅，并接收发行给订阅组的所有事件。 基于内容的订阅模式 订阅者可以通过选择过滤多重规模来优化他们的订阅 不要求组的预定义

基于主题的pub/sub ——发布算法 Sink节点可以发送和转发系统中的任何事件，包括本地产生的和接收到的 发布算法使用两个缓冲区 输入缓存：存放接收到的消息 本地缓存：存放本地产生的消息 Receive()原语 读取输入缓存，并返回收集到的消息 Send()原语 发送用receive()接收到的消息，包括接收到的和本地产生的

基于内容的pub/sub ——订阅算法（1） 定义一个特殊层l0 ,该层包括所有节点，且全部相连 当一个节点加入系统时，该层执行联接原语 L0层的两大功能 申明一个新主题(topic) 联接另一层

基于主题的pub/sub ——订阅算法（2） 申明一个新主题 当结点p试图创建一个新主题，它须要对其他节点申明之 它使用l0发布一个消息，描述新层lnew及其主题 由于l0包含所有节点，故系统中的所有节点都知道了新层的存在 联接另一层 当结点p试图联接到l层，其须先找到一个已练到该层的结点q P在l0层上发布一个询问是否有这样的q点的消息 q收到后，停止转发，并回复一个消息通知p自己的存在 P以q为联接结点，使用联接原语连入l层

基于内容的pub/sub 超节点（Super Peer） 簇（cluster） 基于内容订阅模式的最小拓扑结构 相互联接作为多层次DAG网络中的（超）结点 作为服务器为子网中的客户节点服务 簇（cluster） 一个包含所有节点的超节点

基于内容的pub/sub ——发布算法 节点订阅 超节点订阅 客户节点可一个选择他们想要接受消息的筛选条件 超节点作为传统的C/S架构中的服务器服务 客户通知与他们相关联的服务器，他们的订阅条件 超节点订阅 在簇中，超节点看作是传统pub/sub系统中的boker 同时也是超节点网络中的对等节点 是多层次DAG基于主题订阅模式中的发布者和订阅者

基于主题的pub/sub ——订阅算法 对于结点 对于超节点 将消息发送给与之关联的超节点即可 将收到的消息发送给子网中所有满足筛选条件的结点 像基于主题的订阅算法那样，待自己成为sink时，发送给其他超节点

算法小结 本算法描述了一个基于P2P思想的sub/pub系统 采用有向无环图DAG 每个对等点都既是发布者，也是订阅者 有较高的可移植性，可扩展性 保持分布式系统的匿名性 安全分散化、模块化，自组织

谢谢观赏~~