平码五不中公式规律
  • / 25
  • 下载费用:30 金币  

使用逻辑文档日志的可扩展最终一致性系统.pdf

关 键 ?#21097;?/dt>
使用 逻辑 文档 日志 扩展 最终 一致性 系统
  专利查询网所有?#35797;?#22343;是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201580032375.9

申请日:

2015.06.16

公开号:

CN106663103A

公开日:

2017.05.10

当前法律状态:

实审

?#34892;?#24615;:

审中

法?#19978;?#24773;: 实质审查的生效IPC(主分类):G06F 17/30申请日:20150616|||公开
IPC分类号: G06F17/30 主分类号: G06F17/30
申请人: 微软技术许可有限责任公司
发明人: P·A·奥特考特; T·塞维尔?#36164;? A·卡帕迪亚; R·扬德尔
地址: 美国华盛顿州
优先权: 2014.06.18 US 14/308,510
专利代理机构: 永新专利商标代理有限公司 72002 代理人: 王英;刘瑜
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201580032375.9

授权公告号:

|||

法律状态公告日:

2017.06.06|||2017.05.10

法律状态类型:

实质审查的生效|||公开

摘要

一种可扩展最终一致性系统。该系统使用逻辑文档日志来在大规模服务中跨多个分区而提供最终一致性。该系统允许通过并行化来对大量互连的文档图进行事务性编辑而不牺牲线性可扩展性。该系统将编辑的权限与重复的存储进行分离,以允许高效的事务和线性可扩展性。所有文档写都被写入到日志中的特定于文档的分区,在这里文档写进行排队直到改变被传播至存储的基于视图的分区为止。通过不?#31995;?#26816;查日志并且尝试将任何未完成的文档写复制到存储,该系统在没有复杂的同步机制的情况下提供了最终一致性。该系统以允许将最终影响多于一个文档的文档写作为对单个文档的编辑来通过日志高效地处理的方式来对文档的隶属和包含关系进行建模。

权利要求书

1.一种用于在使得文档能够由多个用户访问的服务中提供可扩展最终一致性的方法,
所述方法包括以下操作:
接收写请求,每个写请求包括文档标识符和文档数据;
在为写请求服务的第一存储系统的所选择的分区中针对每个写请求而创建运行记录;
尝试将所述运行记录复制到为读请求服务的第二存储系统;以及
在已经成功地将所述运行记录复制到所述第二存储系统时从所述第一存储系统中删
除所述运行记录;并且
当所述第一存储系统的所述所选择的分区包含运行记录时,重复以下操作:尝试将所
述运行记录复制到为读请求服务的第二存储系统以及删除已经被成功地复制到所述第二
存储系统的所述运行记录。
2.根据权利要求1所述的方法,其中,所述所选择的分区基于所述文档标识符。
3.根据权利要求1所述的方法,其中,所述第二存储系统按照为读请求服务所需的视图
进行分区。
4.根据权利要求1所述的方法,还包括在所述第一存储系统的所述所选择的分区中针
对每个写请求而创建历史记录的操作。
5.根据权利要求1所述的方法,还包括基于相关联的文档标识符向每个写请求分配分
区键?#26723;?#25805;作,每个分区键值与所述第一存储系统中的分区相对应。
6.根据权利要求5所述的方法,还包括基于所述相关联的文档标识符的散列值来计算
所述写请求的所述分区键?#26723;?#25805;作。
7.根据权利要求1所述的方法,还包括向所述写请求分配唯一的标识符的操作。
8.根据权利要求7所述的方法,还包括基于所述相关联的文档标识符的散列值来计算
所述写请求的所述分区键?#26723;?#25805;作。
9.一种用于在使得文档能够由多个用户访问的服务中提供可扩展最终一致性的系统,
所述系统包括:
第一存储系统,所述第一存储系统用于存储来自与对文档的改变相关联的写请求的文
档记录;
第二存储系统,所述第二存储系统用于存储被用来为读请求服务的文档记录;
具有处理器和存储器的计算设备,所述计算设备用于:
接收写请求;
在第一存储系统的所选择的分区中针对写请求来创建运行记录;
将所述运行记录复制到所述第二存储系统;
从所述第一存储系统中删除已经成功地复制的运行记录。
10.根据权利要求9所述的系统,其中,所述第二存储系统按照为读请求服务所需的视
图进行分区。
11.根据权利要求9所述的系统,其中,所述计算设备还用于不?#31995;?#35835;取所述第一存储
系统的分区以定位运行记录并且将所定位的运行记录复制到所述第二存储系统。
12.根据权利要求9所述的系统,其中,所述计算设备还用于在所述第一存储系统的所
述所选择的分区中针对写请求而创建历史记录。
13.根据权利要求9所述的系统,其中,所述计算设备还用于向所述写请求分配唯一的
标识符。
14.根据权利要求9所述的系统,其中,所述唯一的标识符包括与文档版本标识符相结
合的文档标识符以及区分运行记录和历史记录的记录类型指示符。
15.一种包含计算机可执行指令的计算机可读介?#21097;?#20854;中,当由计算机执行时,所述计
算机可执行指令执?#24615;?#20351;得文档能够由多个用户访问的服务中提供可扩展最终一致性的
方法,所述方法包括以下操作:
接收写请求,每个写请求包括文档标识符和文档数据;
基于所述文档标识符的散列值来计算每个写请求的分区键值,每个分区键值与为写请
求服务的第一存储系统中的分区相对应;
将针对每个写请求的运行记录和历史记?#32487;?#21152;至与所述写请求的所述分区键?#36842;?#23545;
应的所述第一存储系统中的所述分区;
尝试将所述运行记录复制到第二存储系统,所述第二存储系统为读请求服务,并且按
照为读请求服务所需的视图来分区;
从所述第一存储系统中的所述分区中删除已经成功地复制到所述第二存储系统的每
个运行记录;并且
当读取所述第一存储系统中的记录列表时,针对在所述记录列表中所发现的每个运行
记录而重复以下操作:尝试将所述运行记录复制到第二存储系统,以及删除已经成功地复
制到所述第二存储系统的每个运行记录。

说明书

使用逻辑文档日志的可扩展最终一致性系统

背景技术

大规模服务允许跨海量数据的事务(transaction)并且经常保存数据的多个复
本。基础?#35797;?#20855;有有限限度,这限制了能够在任意单个事务中处理的数据的量。作为结果,
大规模服务通常被设计为具有固定的规模单位(scale unit)。当服务上的负载超过规模单
位时,可以添加额外的规模单位并且数据可以跨多个规模单位进行分区。尽管这允许服务
容?#31245;?#21152;的量的数据,但是事务不再能够跨已经被分区的数据来执行。

针对该问题的传统的解决方案包括使用同步机制来调和数据、迫使?#20801;?#25454;进行的
人工划分?#35270;?#35813;规模单位、或者放弃事务。同步机制经常非常复杂并且具有多方主导的问
题。如果针对文档进行了冲突的编辑,则需要用户?#31245;?#26469;解决该冲突。由于传播延迟,冲突
可能在用户已经得到事务成功的确认并且登出服务之后才会发生。因此,冲突可能长时间
无法解决。

使得未解决的冲突最小化的一种机制是具有负责特定的记录的权限,但是这在记
录被复制并存储在多个地方时不能够得到高效地处理。传统的解决方案使用诸如Paxos之
类的一致性协议来在存储复本的顶端构建人工权限。然而,当一致性系统中的节点由于网
络运行中断而不可用或者无法进行通信时,该一致性系统存在问题。

关于这些和其他考虑而进行了本发明。尽管已经?#33268;?#20102;相对具体的问题,但是应
当理解的是,在本文中所公开的实施例不应该限于解决在背景技术中所标识的具体的问
题。

发明内容

提供了该发明内容以用简化的形式引入了在下文的具体实施方式部?#31181;?#25152;进一
步描述的概念的选择。该发明内容不旨在标识所要求保护的主题的关键特征或本质特征,
也不旨在用来帮助确定所要求保护的主题的范围。

一种可扩展最终一致性系统的实施例包括事务对象模型,其允许针对大规模服务
的高效且可扩展的最终一致性。在可扩展最终一致性系统内,由分离的层来处理写请求和
读请求。日志服务写请求(例如,对文档的写入)在分区方案中与写动作相一致。存储服务读
请求(即,视图的读取)在分区方案中与读动作相一致。该日志包括用于存储文档的至少一
个基于文档的分区。该存储包括用于存储文档的至少一个基于视图的分区。

当用户执行诸如创建、修改、或删除文档之类的动作时,写请求被传送至可扩展最
终一致性系统。在接收之后,该可扩展最终一致性系统首先将该写请求保存至日志。在已经
将该写请求保存至日志之后,对文档的改变被认为是将要接受的。该可扩展最终一致性系
统的实施例可以在接收之后在至少两个不同的位置中将该写请求保存至日志。可以将该写
请求的一个副本作为运行记录来保存,所述运行记录充当标识还没有与存储完全融合的写
请求的动作项。该写请求的另一个副本可以作为示出了不同版本之间的对文档的改变的历
史记录来保存。

改变提交层负责将写请求从日志传播至存储。文档写从日志流至存储从而没有复
杂的同步机制。在各个实施例中,可扩展最终一致性系统可以当运行记录在日志中被创建
时进行首次尝试以将所述运行记录复制到存储。一旦已经成功地复制了运行记录,就将该
运行记?#21363;?#26085;志中删除。

一致性恢复层负责改变提交层的循环操作并最后提供最终一致性。一致性恢复层
?#20013;?#22320;提示改变提交层以通读由日志所保存的现有的记录并且将任何运行记录复制到存
储。

附图说明

通过参考以下附图,本公开的进一步的特征、方面、和优点将变得更好地被理解,
其中,元素不是按比例绘制的,以便更为清楚地示出?#38468;冢?#24182;且其中,相同的附图标记在多
个视图通篇中指示相同的元素:

图1示出了在大规模服务中所实现的可扩展最终一致性系统的一个实施例的系统
架构;

图2是表示针对日志的一个分区的运行和历史记录的一个实施例的图示;

图3是由可扩展最终一致性系统所采用的最终一致性方法的一个实施例的高?#35835;?br />程图;

图4是可扩展最终一致性系统的一个实施例的流程图;

图5A至5D示出了在可扩展最终一致性系统内如何对涉及具有各种关?#26723;?#25991;档的
各种事务(即,编辑)进行处理;

图6是示出了利用其可?#20801;导?#26412;发明的实施例的计算设备的物理组件的一个实施
例的框图;和

图7A和7B是利用其可?#20801;导?#26412;发明的实施例的移动计算设备的简化框图。

具体实施方式

参考形成本发明的一部分并示出?#21496;?#20307;的示例性实施例的附图以在下文中更加
充分地描述各种实施例。然而,实施例可以以许多不同的形式来实现,并且不应该被理解为
限于在本文中所阐述的实施例;相反,提供了这些实施例以使得该公开将是透彻的和完整
的,并且将会向本领域技术人员完全传达实施例的范围。实施例可以被实践为方法、系统、
或设备。从而,实施例可以采取硬件实现、完全软件实现、或者组合了软件和硬件方面的实
现的形式。因此,以下详?#35813;?#36848;将不被理解为限制意义。

在本文中描述并且在附图中示出了可扩展最终一致性系统的实施例。该可扩展最
终一致性系统使用逻辑文档日志以在大规模服务中提供跨分区的最终一致性。该系统允许
通过并行化来对文档的大量互连的图进行事务性编辑而并不牺牲线性可扩展性,只要没有
文档写需要事务性地跨越多个文档。该系统将编辑的权限与重复的存储分离,以允许高效
的事务和线性可扩展性。将所有文档写都写至日志中的特定于文档的分区,在这里将文档
写进行排队直到改变被传播至存储的基于视图的分区为止。一旦当未完成的文档写被成功
地复制到存储,就将其从日志中移除。通过?#20013;?#22320;检查日志并且尝试将任何未完成的文档
写复制到存储,该系统在没有诸如一致协议(例如,Paxos)之类的复杂的同步机制的情况下
提供最终一致性。该系统以这样的方式来对文档的隶属和包含关系进行建模:允许将最终
影响多于一个文档的文档写作为对单个文档的编辑来通过日志进行高效地处理而不用求
助于人工分区。

图1示出了可扩展最终一致性系统的一个实施例的系统架构。可以在向用户102提
供对大量信息的访问和存储的大规模(例如,大数据)服务中实现可扩展最终一致性系统
100。用户可以经由网络106从各种客户端设备104a-d访问大规模服务,所述网络例如但不
限于互联网、广域网、局域网、及其组合。合适的客户端设备的示例包括但不限于台式计算
机104a、膝上?#22270;?#31639;机104b、平板计算机104c、移动电话104d、个人数?#31181;?#29702;、智能?#30452;懟?#20197;
及智能电器(例如,智能电视)。

可扩展最终一致性系统包括提供对大规模服务的入口点的前端层108。在各种实
施例中,该大规模服务可以提供基于网络的用户接口,所述用户接口能够通过诸如浏览器
之类的用户代理而由客户端设备所访问。在一些实施例中,用户代理可?#20801;?#25552;供用户接口
并且处理与大规模服务的通信的专用客户端应用。

事务对象模型110允许针对大规模服务的高效且可扩展的最终一致性。由该可扩
展最终一致性系统所处理的事务包括但不限于写请求和读请求,它们允许用户读取、查看
(即,?#20801;?、创建、复制、删除、操纵(即,编辑或修改)、分享、协同、或保存(即,写)由大规模
服务所处理的文档和视图。术语“文档”宽泛地涵盖了由大规模服务所处理的任何数据对
象。作为示例,针对基于办公或生产力应用的大规模服务而言,文档可以包括但不限于文字
处理文档、邮件项目、任务项目、日历项目、联系人项目、演示、电子表格、或数据库。术语“视
图”宽泛地涵盖了用来向用户呈现文档的基于常见属性?#26723;?#25991;档的任何索引、分组、或类
别。作为示例,视图可以允许由任务所有者或者由与该任务相关联的项目来?#20801;?#20219;务项目
的集合。

在可扩展最终一致性系统内,由分离的层来处理写请求112和读请求114。日志116
以与写动作一致的分区方案来为写请求(例如,对文档的写入)服务。存储118以与读动作一
致的分区方案来为读请求(例如,视图的读取)服务。在所图示的实施例中,将日志和存储表
示为通过对应的应用程序接口(API)(日志API 120、和存储API 122)来访问的虚拟化的存
储?#35797;?例如,云存储)。

日志包括用于存储文档的至少一个基于文档的分区124。基于分配给单个?#35797;?#25110;
查询的数据的最大分组来设置每个分区的大小。随着由大规模服务所处理的数据的量的增
加,可以线性地扩展日志并且添?#26377;?#30340;分区。无论日志分区的数量如何,可扩展最终一致性
系统都将与任何给定的文本相关联的所?#34892;?#35831;求全部存储在同一日志分区中。具有与每个
文档相关联的单个日志分区允许针对每个文档而保存事务编辑队列。

存储包括用于存储文档的至少一个基于视图的分区126。按视图对存储进行分区
允许文档高效地被多个用户同时进行访问。如果文档与多于一个视图相关联,则每个视图
通常保存文档的其自己的副本(即,复本)。在该存储内,文档的各种复本/视图形成跨多个
分区分布的文档的大量互连的图。尽管一些文档除了该文档的复本之外可以独立于所有其
他文档,但是其他文档可以凭借包含关系或隶属关系而进行互连。例如,单个的个人任务可
以独立于存储内的其他文档。一个文档也可以涉及存储中的另一个文档,例如,分配给项目
的任务。该项目可以充当多个任务的容器。类似地,文档可以涉及存储中?#20801;?#22270;有影响的其
他实体,例如,分配给项目的人员。就如日志一样,可以线性地扩展存储并且添?#26377;?#30340;分区
以处理额外的文档或视图。

当用户执行诸如创建、修改、或删除文档的动作时,将写请求传送至可扩展最终一
致性系统。在接收之后,该可扩展最终一致性系统首先将该写请求保存至日志。在已经将该
写请求保存至日志之后,对文档的改变被认为是将要接受的,但是在该写请求中所?#20174;?#30340;
改变通常不是对所有用户可见的,直至它?#19988;?#32463;融入存储中为止。当日志包括多个分区时,
该可扩展最终一致性系统可以确定指示该写请求应当被写入的分区的分区标识符。在各种
实施例中,该分区标识符可以基于与该写请求相关联的文档的文档标识符。

可扩展最终一致性系统使用日志作为用于保存写请求直到它?#19988;?#32463;融入合适的
视图为止的暂存区域(staging area)。当检测到针对文档的冲突编辑?#24065;?#21487;以使用该日
志。为了实?#32456;?#20123;功能,可扩展最终一致性系统的实施例可以在接收写请求之后,在至少两
个不同的位置将该写请求保存至日志。可以将该写请求的一个副本保存为运行记录128,其
充当标识还没有与存储完全融合的写请求的动作项。无法将写请求复制到存储可?#20801;?#20998;区
或者日志与存储之间的通信信道(例如,互联网)暂时无法访问(例如,?#35797;垂收?#25110;停机)的
结果。可以将该写请求的另一个副本保存为历史记录130。可以出于诸如检测对文档的冲突
编辑或维护审计日志之类的目的来使用历史记录。

改变提交层132负责以并行化的方式将写请求从日志传播至存储。文档写从日志
流动至存储,因此不存在复杂的同步机制。换句话说,对每个视图/复本的更新独立于受到
文档写影响的对其他视图/复本的更新。这进而允许文档写以及每个更新作为单个的文档
事务来进行而并不求助于人工划分(即,将文档图细分为人工的规模单位或区)。在各种实
施例中,该可扩展最终一致性系统可以当在日志中创建运行记录时首次尝试将其复制到存
储。一旦已经成功地复制了运行记录,就将该运行记?#21363;?#35813;日志中删除。

一致性恢复层134负责该改变提交层的循环操作并最后提供最终一致性。一致性
恢复层提示改变提交层通读由日志所保存的现有的记录并且将任何运行记录复制至存储。
在各种实施例中,该改变提交层以最老的运行记录开始,按照编辑被该可扩展最终一致性
系统所接收的顺序来对文档进行事务性编辑。该一致性恢复层可以基于各种事件的发生
和/或定期地(例如,每N?#31181;印?#23567;时、或天)发起改变提交层的操作。可以用来触发改变提交
层的操作的事件的示例包括但不限于:系统启动、错误恢复、以及接收写请求。

图2是表示针对日志的一个分区的运行和历史记录的一个实施例的图示。所示出
的代表性日志分区包含针对每个写请求的历史记录130a-c。文档“doc1”的版本2和文档
“doc4”的版本1还具?#24615;?#34892;记录128b-c。运行记录的存在表示写请求还没有被完全复制到
存储。针对文档“doc1”的版本1的运行记录不存在表示已经用针对版本1的写请求更新了所
有复本。在对日志的下一次检查时,该可扩展最终一致性系统将尝试将针对文档“doc1”的
版本2和文档“doc4”的版本1的写请求传播至存储。

针对每个基于文档的日志分区124的队列200是指可扩展最终一致性系统中未完
成的写请求。换句话说,该队列宽泛地?#22797;?#36824;没有成功地复制到存储的运行记录的集合。日
志和存储的实施例是键值存储系统。在各种实施例中,与运行和历史记录相关联的基本信
息包括但不限于:分区键值202、行键值204、和文档数据206。可以针对每个记录所存储的额
外的信息可以包括但不限于:充当文档的离线副本的源的文档的版本(即,针对其生成编辑
的版本)、接收到写请求的日期、接收到写请求的时间、以及提交写请求的用户的用户标识
符。

分区键值202标?#26029;?#20854;分配文档的分区。在各种实施例中,分区键值是文档标识符
210(例如,文档名称)的散列值208,这与将文档标识符用作分区键?#36842;?#27604;允许更为高效的
最终一致性。散列值允许通过将文档标识符一般化来将具有一系列唯一的文档标识符的文
档分组到相同的分区中。例如,在所示出的实施例中,文档标识符“doc1”和“doc4”的散列值
是“ABC?#20445;?#24182;且“doc1”和“doc4”的运行和历史记录被分配给对应于散列值“ABC”的相同的日
志。

行键值204是日志内唯一的记录标识符。在各种实施例中,行键值是附加有记录的
版本212的文档标识符210。可以利用类型标识符214来修改行键值从而在历史记录和运行
记录之间进行区分。例如,可以在行键值前加上诸如“H”之类的?#22336;?#20197;指示该记录是历史记
录、或者在行键值前加上“R?#24065;?#25351;示该记录是运行记录。

文档数据206包括被写的文档的内容216。在一些实施例中,内容可以仅包括改变
而不是该文档的完整副本。

图3是由可扩展最终一致性系统所采用的最终一致性方法的一个实施的高?#35835;?#31243;
图。最终一致性方法300以其中接收到写请求的文档写操作302开始。键值操作304计算写请
求的键值。该键值可以包括如关于图2所描述的分区键值和行键值。分区键?#24403;曄断?#20854;分配
文档的分区。行键值是唯一的记录标识符。在各种实施例中,该行键值是附加有记录的版本
的文档标识符。

历史操作306将写请求作为历史记录存储在使用键?#26723;?#26085;志中。更加具体而言,将
该写请求写入到由分区键值所标识的分区的日志中。历史记录是使用利用历史记录指示符
所修改的行键值而唯一地标识的。例如,可以该历史记录的在行键值前加上诸如“H”之类的
?#22336;?#20197;指示该记录是历史记录。

运行操作308将写请求的副本作为运行记录存储在使用该键?#26723;?#26085;志中。更加具
体而言,将该写请求写入到由分区键值所标识的分区的日志中。运行记录是使用利用运行
记录指示符所修改的行键值而唯一地标识的。例如,可以在该运行记录的行键值前加上诸
如“R”之类的?#22336;?#20197;指示该记录是运行记录。

运行记?#21363;?#29702;操作310将写记录(即,运行记录中的编辑)复制到存储。运行记录可
以通过运行记录指示符与其他记录区分开来。运行记?#21363;?#29702;操作的各种实施例在每个运行
记录被创建时对其进行作用。如果存在未经处理的运行记录(即,未完成的写请求),则复制
操作312将该写请求复制到文档存储。

复制成功检查操作314验证已经将写请求成地功复制到存储中的合适的分区。在
一些实施例中,可以通过从存储接收成功或失败响应而指示成功或失败。在其他实施例中,
可以通过将存储中的分区的内容与写请求的内容进行比较来确定成功。可以将该比较实现
为元数据比较(例如,验证每个复本的版本号与所处理的写请求相同)或内容比较(例如,散
列或逐?#32440;?#27604;较)。

删除操作316在复制操作成功完成之后将运行记?#21363;?#26085;志中删除。删除运行记录
?#19988;?#32463;成功地将文档编辑并入存储中的信号。尽管运行记录被删除,但保留历史记录以用
于在标识冲突编辑以及对冲突解决进行帮助时使用。在各种实施例中,可以将历史记录无
限期地保留在日志中。

在可选的历史清理操作318中,可以有条件地清理历史记录以?#26723;?#26085;志的大小。在
一些实施例中,针对每个文档可以仅保留所选择的数量的历史记录(例如,最后五个)。可替
代地,可以在指定时间段(例如,两周或三个月)之后删除历史记录。在一些实施例中,可以
将历史记录保留链接至与文档相关联的活动。换句话说,基于文档的属性可以保留更多的
历史记录,所述文档的属性例如但不限于最近或频繁地编辑的文档。

如果该复制成功检查操作确定复制失败,则该复制成功检查操作可以用于发起调
度操作320,该调度操作320使得在所选择的标准发生时再次尝试重复操作。可以以多种方
式来确定成功或失败。例如,可以由与存储API建立连接的功能或者由接收到从存储API所
发送的成功/失败响应来指示,但不限于此。在各种实施例中,该调度操作可以被配置为使
得该复制操作按照调度(例如,每天、每小时等)、在经过时间之后(例如,在失败后60?#31181;?、
或者在事件(例如,接收到新的写请求)之后进行重试,但不限于此。

重试操作322读取日志文档分区并且将存在于该日志中的任何未经处理的运行记
录收集到队列中。运行记?#21363;?#29702;操作310对该队列中的每个运行记录进行重复。在各种实施
例中,该重试操作从最旧的记录到最新的记录来处理该日志。这确保了文档编辑以它们被
接收的顺序而被处理,这促成了冲突编辑检查以及可以?#35272;?#20110;按顺序接收写请求的其他功
能。

图4是可扩展最终一致性系统的一个实施例的流程图。流程在流程A处以用户对文
档402进行编辑开始。该文档可?#20801;?#30001;用户所创建的新的文档或者?#19988;?#32463;从大规模服务所
读取的现有文档(例如,离线副本)。当用户保存针对文档的改变时,流程在B处以创建写请
求112继续。该写请求可以包含经改变的文档和额外的信息,例如但不限于:提交写请求的
用户的用户标识符、提交写请求的日期、提交写请求的时间、以及充当离线副本的源的文档
的版本(即,离线副本的基线版本)。在流程C处,确定与经改变的文档的文档标识符相对应
的分区键值。在流程D处,将运行记?#32487;?#21152;至经改变的文档的合适的日志。在流程E处,可以
将历史记?#32487;?#21152;至经改变的文档的合适的日志。在流程F处,在存储了用户记录之后,根据
用户(per-user)的一致视图系统向用户发送确认404。该确认向用户指示已经接收并接受
了对文档的改变。

在各种实施例中,在流程G处,将新添加的运行记录发送至改变提交层以供复制到
存储。在流程H处,该改变提交层将运行记录发送至存储API,在这里该运行记录被传播至针
对对应的视图的合适的存储分区。在流程I处,基于运行记录中的改变来对存储分区中针对
各种视图的复本406a-n进行更新。流程在流程J处以将成功或失败报告回日志API而继续。
成功/失败指示408可以源自于存储API并且可以由该存储API直接报告给日志API或者通过
改变提交层而间接地报告。在其他实施例中,成功/失败指示408可以由改变提交层来确定
并且直接地报告至日志API。如果运行记录的复制成功,则流程在K处以删除成功地复制的
运行记录128r而继续。

流程在L处随着一致性恢复层从日志中读取运行记录并形成队列200而继续。在流
程M处,将经排队的运行记录发送至改变提交层以用于以它们被接收的顺序来处理。流程针
对队列中的每个运行记录而从流程H处继续,并且继续直到该队列中的所?#24615;?#34892;记录都已
经被处理为止。

图5A至5D示出了如何在可扩展最终一致性系统内对涉及具有各种关?#26723;?#25991;档的
各种事务(即,编辑)进行处理。该可扩展最终一致性系统对隶属(例如,处于多个项目中的
用户)和包含(例如,作为项目一部分的任务)进行建模,并且允许在那些边界之间移动文
档,而不必将文档图(即,数据集)细分成人工规模单位或区。

图5A示出了日志和存储的初始状态。出于?#33268;?#30340;目的,所涉及的文档包括经复制
的任务502、两个项目504e、504f、以及两个用户506a、506b。日志116被示为具有单个分区
124,其假定所涉及的所有文档的分区键值(例如,散列值)都?#25104;?#33267;同一分区;然而,如之前
所描述的,一个或多个文档可以由键值指向不同的日志分区而对操作没有任何显著的影
响。存储118被分区成各种视图分区,包括个体项目分区126e、126f、根据分配的用户来索引
的任务的分区126t、以及用于高效的文档取回的根据名称来索引的用户的分区126u。例如,
可以在存储中给不同的容器(例如,项目)提供有分离的视图分区,以允许在单个事务中取
回表示与特定的项目相关联的任务、?#35797;?例如,用户)、以及其他对象的各种文档。文档可
以包括各种独立的简单值字段510,例如标题或名称。

一些文档还可以包括容器关系字段512,例如项目标识符,其将任务链接至另一个
文档(例如,项目)。项目标识符可以充当指向该任务所属的项目(即,容器)的指针,从而定
义了容器关系。通常而言,容器关系被局限于一对一(例如,任务属于一个项目)或一对无
(例如,项目不属于一个项目)关系。出于说明性目的,将项目示出为具有对文档标识符进行
镜像的项目标识符以为索引提供公共字段。

一些文档可以包括隶属关系字段514,例如被分配至项目的人员(即,来自分组侧
的隶属)或者用户与其相关联的项目(即,来自成员侧的隶属)。通常而言,隶属关系除了允
许一对一和一对无关系之外,还允许一对多(例如,项目可以具有多个经分配的人?#34987;?#32773;用
户可以具有多个角色)。

图5B示出了在该可扩展最终一致性系统内对发生改变的独立字段的处理。在这
里,对任务的离线副本502o进行工作的用户102提交了写请求(即,编辑)112,以将标题字段
510的值从“Fix A/C”改变为“Fix HVAC”。该编辑被存储在与该任务相关联的日志分区中
(即,基于键值)。如在本文中所描述的,该标题改变最终从日志传播至存储的各个分区中的
该任务的每个复本502。从日志的角度而言,这样的事务能够容易地被识别为单个文档事
务。由于该改变限于对单个文档进行,因此所以该事务无需跨日志中的多个分区。

图5C示出了该可扩展最终一致性系统内对包含关系字段改变的处理。在该实例
中,对任务的离线副本502o进行工作的用户102提交了写请求112,以通过将项目标识符字
段512的值从“Echo”改变为“Foxtrot”而将该任务移动至不同的项目。同样,该编辑被存储
在与任务相关联的日志分区中。尽管该编辑涉及包含关系,但是仅仅任务(即,所包含的文
档)是必须改变的。该编辑最终被传播至每个视图/复本,这可以涉及从一个或多个分区中
移除复本、将任务添加至一个或多个分区、以及在一个或多个分区中修改任务。在这里,从
项目E(例如,针对项目E所指定的视图分区)中移除复本,并且将复本添加至项目F(例如,针
对项目F所指定的视图分区)。此外,?#20801;?#22270;分区中针对根据受托者来索引的任务的复本进
行更新。然而,不需要对项目(即,容器)进行改变。从而,从日志的角度而言,该事务是单个
文档事务,这?#19988;?#20026;仅仅需要针对单个文档来记录改变。换句话说,仅尽需要将改变写入到
单个日志分区。

图5D示出了该可扩展最终一致性系统内对隶属关系字段改变的处理。在该实例
中,对项目F的离线副本504o进行工作的用户102提交了写请求112,以通过将“Alice”添加
至人员字段514而向与该项目相关联的用户分组中添加成员。该编辑被存储在与该项目相
关联的日志分区中。尽管改变最终可以被传播至存储中受该隶属改变所影响的其他文档,
但是从日志的角度而言,对该隶属关系字段的隶属的更新仅仅是对项目的编辑。因此,即使
最终结果可?#20801;?#23545;多个文档进行更新(例如,可以对用户A的隶属字段进行更新),但是将该
写请求作为单个文档事务来高效地处理。

该申请的主题可以以多种系统、设备、和其他制品来实?#21482;?#32773;被实践为方法。实施
例可以被实现为硬件、软件、计算机可读介质或者其组合。在本文中所描述的实施例和功能
可以经由多种计算系统来操作,所述计算系统包括但不限于:台式计算机系统、有线和无线
计算系统、移动计算系统(例如,移动电话、上网本、平板或板式计算机、以及膝上?#22270;?#31639;
机)、手持式设备、多处理器系统、基于微处理器的或可编程的消费型电?#30828;?#21697;、小?#22270;?#31639;
机、以及大?#22270;?#31639;机。

各种类型的用户界面和信息可以经由板载计算设备?#20801;?#22120;或者经由与一个或多
个计算设备相关联的远程?#20801;镜?#20803;来?#20801;尽?#20363;如,各种类型的用户界面和信息可以在各种
类型的用户界面和信息所透射到的墙面上?#20801;?#24182;且与这样的墙面进行交互被投射在其上。
与本发明实施例可以利用其实践的多种计算系统的交互包括:键击输入、触摸屏输入、语音
或其他音频输入、在相关联的计算设备装备有用于捕捉和解译用户?#36136;?#30340;检测(例如,相
机)功能以用于控制计算设备的功能等的情况下的?#36136;?#36755;入。

图6至7B以及相关联的描述提供了对其中可?#20801;导?#26412;发明的实施例的多种操作环
境的?#33268;邸?#28982;而,所图示和?#33268;?#30340;设备和系统是出于示例和说明的目的,而不限于可以用于
实践在本文中所述的本发明的实施例的大量计算设备配置。

图6是示出了利用其可?#20801;导?#26412;发明的实施例的计算设备600的物理组件(即,硬
件)的框图。在下文中所描述的计算设备组件可?#20801;?#29992;于实施计算设备,其包括但不限于:
个人计算机、平板计算机、平面计算机和智能电话、或者在文本中所?#33268;?#30340;任何其他计算设
备。在基本配置中,计算设备600可以包括系统存储器604以及至少一个处理单元602。取决
于计算设备的配置和类型,系统存储器604可以包括但不限于:?#36164;?#24615;存储(例如,随机存取
存储器)、?#19988;资?#24615;存储(例如,只读存储器)、?#20102;?#23384;储器、或者这样的存储器的任何组合。
系统存储器604可以包括操作系统605和适用于运行软件应用620的一个或多个程序模块
606,例如可扩展最终一致性系统100的组件。例如,操作系统605可?#20801;?#29992;于控制计算设备
600的操作。此外,本发明的实施例可结合图形库、其他操作系统或任何其他应用程序来实
践,并且不局限于任何特定的应用或系统。由虚线608内的那些组件示出了该基本配置。计
算设备600可以具有额外的特征或功能。例如,计算设备600还可以包括诸如例如?#25490;獺?#20809;盘
或磁带之类的额外的数据存储设备(可移动的和/或不可移动的)。由可移动存储设备609和
不可移动存储设备610示出了这样额外的存储。

如上所述,可以将多个程序模块和数据文件存储在系统存储器604中。当在处理单
元602上执行时,软件应用620可以执行包括但不限于最终一致性方法300的一个或多个阶
段的过程。可以根据本发明的实施例而使用的其他程序模块可以包括以下应用,例如电子
邮件及联系人应用、文字处理应用、电子表格应用、数据库应用、幻?#30772;?#28436;示应用、画图或计
算机辅助应用程序?#21462;?br />

此外,可以在包括分立电子元件的电路、包含逻辑门的封装或集成的电?#26377;?#29255;、利
用微处理器的电路、或者在包含电子元件或微处理器的单个芯片上实?#30452;?#21457;明的实施例。
例如,可以经由其中所示出的每个或许多组件可以集成在单个集成电路上的片上系统
(SOC)来实践本发明的实施例。这样的SOC设备可以包括一个或多个处理单元、图形单元、通
信单元、系统虚拟化单元、以及各种应用功能,其全部作为单个集成电路而被集成(或“烧”)
到芯片基底上。当经由SOC进行操作时,可以经由在单个集成电路(芯片)上与计算设备600
的其他组件集成的专用逻辑来对在本文中所描述的关于应用620的功能进行操作。还可以
使用能够执行逻辑操作(例如AND、OR和NOT)的其他技术来实践本发明的实施例,所述其他
技术包括但不限于机械、光学、流体、和量子技术。另外,可以在通用计算机内或在任何其他
任何电路或系统中实践本发明的实施例。

计算设备600还可以具有一个或多个输入设备612,例如键盘、鼠标、笔、语音输入
设备、触摸输入设备?#21462;?#36824;可以包括输出设备614,例如?#20801;?#22120;、扬声器、打印机?#21462;?#21069;述设备
是示例并且也可以使用其他设备。计算设备600可以包括允许与其他计算设备618进行通信
的一个或多个通信连接616。合适的通信连接616的示例包括但不限于:RF发射机、接收机
和/或收发机电路;通用串行总线(USB)、并行和/或串行端口。

如在本文中所使用的术语计算机可读介质可以包括计算机存储介质。计算机存储
介质可以包括以任何用于存储信息(例如,计算机可读指示、数据结构、或程序模块)的方法
或技术来实现的?#36164;?#24615;的和?#19988;资?#24615;的、可移动的和不可移动的介质。系统存储器604、可
移动存储设备609、和不可移动存储设备610都是计算机存储介质的示例(即,存储器存储)。
计算机存储介质可以包括RAM、ROM、电可擦只读存储器(EEPROM)、?#20102;?#23384;储器或其他存储器
技术、CD-ROM、数字通用盘(DVD)或其他光存储、盒式磁带、磁带、?#25490;?#23384;储器或其他磁存储
设备、或者可用于存储信息且可以由计算机设备600访问的任何其他制品。任何这样的计算
机存储介质都可?#20801;?#35745;算设备600的一部分。

图7A和7B图示了利用其可?#20801;导?#26412;发明的实施例的移动计算设备700。合适的移
动计算设备的示例包括但不限于:移动电话、智能电话、平板计算机、平面计算机、以及膝上
?#22270;?#31639;机。在基本配置中,移动计算设备700是具有输入元件和输出元件两者的手持式计算
机。移动计算设备700通常包括?#20801;?#22120;705以及允许用户将信息输入到移动计算设备700中
的一个或多个输入按钮710。移动计算设备700的?#20801;?#22120;705也可以充当输入设备(例如,触
摸?#26009;允?#22120;)。如果被包括在内,则可选的侧输入元件715允许进一步的用户输入。侧输入元
715可?#20801;?#26059;转开关、按钮、或任何其他类型的手动输入元件。在可替代的实施例中,移动计
算设备700可包含更多或更少的输入元件。例如,在一些实施例中,?#20801;?#22120;705可以不是触摸
屏。在另一个可替代的实施例中,移动计算设备700是诸如蜂窝电话之类的便携式电话系
统。移动计算设备700还可以包括可选的小键盘735。可选的小键盘735可?#20801;?#29289;理小键盘或
者是在触摸?#26009;允?#22120;上生成的“软”小键盘。在各种实施例中,输出元件包括用于示出图形
用户界面(GUI)的?#20801;?#22120;705、视觉指示器720(例如,发光二极管)、和/或音频换能器725(例
如,扬声器)。在一些实施例中,移动计算设备700包含用来向用户提供触觉反馈的振动换能
器。在另一个实施例中,移动计算设备700包含用于向外?#21487;?#22791;发送信号或者从外?#21487;?#22791;接
收信号的输入和/或输出端口,例如音频输入端(例如,麦克风插孔)、音频输出端(如耳机插
孔)、以及视频输出端(例如,HDMI端口)。

图7B是示出了移动计算设备的一个实施例的架构的框图。即,移动计算设备700可
以包含用于实现一些实施例的系统(即,架构)702。在一个实施例中,系统702被实现为能够
运行一个或多个应用(例如浏览器、电子邮件、日历、联系人管理器、消息传送客户端、游戏、
以及媒体客户端/播放器)的“智能电话”。在一些实施例中,将系统702集成为诸如集成的个
人数?#31181;?#29702;(PDA)和无线电话之类的计算设备。

一个或多个应用程序765可被加载到存储器762中,并且在操作系统764上运行或
者结合操作系统764运行。应用程序的示例包括电话拨号程序、电子邮件程序、个人信息管
理(PIM)程序、文字处理程序、电子表格程序、互联网浏览器程序、消息传?#32479;?#24207;?#21462;?#31995;统702
还包括存储器762内的?#19988;资?#24615;存储区768。?#19988;资?#24615;存储区768可以用于存储如果系统702
?#31995;?#32780;不应该丢失的?#20013;?#30340;信息。应用程序765可以使用?#19988;资?#24615;存储区768中的信息并将
信息存储在?#19988;资?#24615;存储区768中,所述信息例如由电子邮件应用等所使用的电子邮件或
其他消息。同步应用(未示出)也驻留在系统702上并且被编程为与驻留在主机计算机上的
对应的同步应用进行交互,以保持存储在?#19988;资?#24615;存储区域768中的信息与存储在主机计
算机处的对应的信息相同步。应当理解的是,包括在本文中所描述的软件应用620在内的其
他应用也可被加载到存储器762中并且在移动计算设备700上运行。

系统702具有可以被实现为一个或多个电池的电源770。电源770还可以包括外置
电源,例如交流的(AC)适配器或给电池供电或充电的加电对接托架。

系统702还可以包括执行发送和接收射频通信的功能的无线电设备772。无线电设
备772经由通信载波或服务供应商来促成系统702与外部世界之间的无线连通性。来往无线
电设备772的传输是在操作系统764的控制下进行的。换句话说,可以将由无线电设备772所
接收的通信经由操作系统764散播至应用程序765,反之亦然。

视觉指示符720可以用于提供视觉通知和/或音?#21040;?#21475;774可以用于经由音频换能
器725产生能够听到的通知。在所示出的实施例中,视觉指示符720是发光二极管(LED),而
音频换能器725是扬声器。这些设备可直接地耦合至电源770,使得当被激活时,即使处理器
760和其他组件可以关闭以节省电池电量,这些设备也能保持通电并?#20013;?#30001;通知机制所指
示的一段时间。LED可被编程为无限期地保持通电,直到用户采取动作来指示该设备的通电
状态为止。音?#21040;?#21475;774用于向用户提供能够听到的信号并且从用户处接收能够听到的信
号。例如,除了耦合至音频换能器725之外,音?#21040;?#21475;774还可耦合至麦克风以接收能够听到
的输入,例如,促进电话会话。根据本发明的实施例,麦克风还可以充?#24065;?#39057;传感器以促进
对通知的控制,如在下文中描述的。系统702还可以包括支持用于记录静止的图像、视频流
等的板载相机730的操作的视?#21040;?#21475;776。

实现系统702的移动计算设备700可以具有额外的特征或功能。例如,移动计算设
备700还可以包括额外的数据存储设备(可移动的和/或不可移动的),例如?#25490;獺?#20809;盘、或磁
带。由?#19988;资?#24615;存储区768示出了这样额外的存储设备。

如在上文中所描述的,可以将由移动计算设备700所生成或捕获的数据/信息以及
经由系统702所存储的数据/信息本地地存储在移动计算设备700上,或者可以将数据存储
在可以经由无线电设备772或经由移动计算设备700和与移动计算设备700相关联的单独的
计算设备(例如,分布式计算网络(例如,互联网)中的服务器计算机)之间的有线连接由设
备来访问的任何数量的存储介质上。应当理解的是,可以经由移动计算设备700、经由无线
电772、或经由分布式计算网络来访问这样的数据/信息。类似地,根据公知的数据/信息传
输和存储方式(包括电子邮件和协同数据/信息共享系统),这样的数据/信息可以容易地在
计算设备之间传输以供存储和使用。

在该公开中所提供的一个或多个实施例的描述或图示旨在向本领域技术人员提
供对主题的完整范围的完全彻底和完整的公开,而不旨在以任何方式限制或约束所要求保
护的发明的范围。在该公开中所提供的实施例、示例、和?#38468;?#34987;认为足以传达所有物,并且
使得本领域技术人员能够制造并使用所要求保护的发明的最佳模式。被认为是对本领域技
术人员公知的对结构、?#35797;础?#25805;作、和行为的描述可?#20801;?#31616;要的或者被省略,以避免使得该
申请的主题的较少人知道的或者独特的方面难以理解。所要求保护的发明不应该被解释为
限于在该申请中所提供的任何实施例、示例、或?#38468;凇?#26080;论是共同地还是单独地示出或描
述,(结构上和方法上两者的)各种特征旨在选择性地包括或省略,以产生具有特定组的特
征的实施例。此外,可以以任何顺序或者同时地执行所示出或描述的功能和行为中的任何
一个或全部。在已经提供有本申请的描述和图示之后,本领域技术人员可以预想落入在该
申请中所实施的一般的发明概念的更宽泛的方面的精神内的变型、修改和替代实施例,而
不脱离所要求保护的发明的更宽泛的范围。

关于本文
本文标题:使用逻辑文档日志的可扩展最终一致性系统.pdf
链接地址:http://www.pqiex.tw/p-6091675.html
关于我们 - 网?#26087;?#26126; - 网站地图 - ?#35797;?#22320;图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 七星彩开奖直播现场南国 白山棋牌游戏手机 下载陕西11选5开奖结果 宁夏十一选五游戏规则 黑龙江11选5开奖结果zhw 辉煌棋牌输了 福利彩票3d走势图 彩票篮球赚钱的方法 股票涨跌跟什么有关系 61分布图