毕业设计（论文）外文翻译-基于Android平台的联系人同步算法的评价翻译.doc

本科毕业设计外文翻译Evaluation of contact synchronization algorithms for the Android platformVincent Segu Pascual a, Fatos Xhafa b基于Android平台的联系人同步算法的评价Vincent Segu Pascual a, Fatos Xhafa b13摘要：针对分布式系统的同步协议已经得到了广泛的调查，实现实时性和可扩展的属性。随着大规模的快速发展分布式系统，以及由于其异质性，涉及有线，无线，移动节点，同步又开始发挥作用。在这项工作中，我们所研究的联系人同步和处理，是一个企业的重要特征环境。事实上，它已通过随时随地访问共享联系人数据而成为支持移动用户团队协作非常重要的方式。我们将问题表征为一个分布式系统的问题，找出它的优良特性，并概述其主要特点。一个简单的算法提出了一个联系人同步时有效的解决方案，系统中的一些节点被认为是移动下Android操作系统的手机。我们还分析了算法耦合Android平台的实施和SugarCRM的服务器，并提供对实验性能提出方法的评价。关键词：数据通信数据同步 移动计算 内联网/外联网/VPN1 引言在传统的分布式系统的不同的情况下的同步已经调查很久。这样的一个背景是数据同步。随着快速发展的大规模分布式系统，以及由于其异质涉及有线，无线和移动节点的性质，同步又开始发挥作用。虽然已知的数据同步算法，可以应用到移动节点的分布式系统，由于间歇性的互联网连接，有限的计算资源，电池的限制，等等这样的几个特点，再次学习他们和有效地实施大规模异构分布式系统已非常迫切。在这工作中，我们侧重于与移动节点的分布式系统的数据同步问题。移动通信系统的作用经历了企业IT基础设施的巨大增长。地理上分散的团队需要即时通讯，再加上无处不在，虽然不可靠，宽带互联网的存在，带来了新的业务流程的范式（因此商业应用软件）在传统的客户机/服务器架构需要间歇性的连接，因此数据同步是一个基本特征，以允许移动通信系统直接连接到中央服务器的情况下给用户服务。重要使用场景，包括移动社交网络，支持“永远可用”的特点和流动工作队，即一群人，地理分布和配备移动设备，为实现共同的项目合作（例如，虚拟校园的用户组，在灾害领域的医生队伍，等等），以支持“随时随地”共享数据同步。Android操作系统已经成为一个在智能手机领域的主要参与者，因此它具有围绕它为重点的应用软件生态系统。在企业市场，Android提供了开箱，联系同步交流的平台。具有讽刺意味的是，留下了很多公司，因为他们使用的Unix / Linux服务器平台。然而，谷歌提供了一个强大的框架，允许第三方开发插件的内容同步和管理多个账户，同步联系人API的形式的接触源。SugarCRM的同时，已成为开源CRM解决方案市场的领导者，使得成为整合许多应用程序和企业这两个系统的一个有趣的选择。同步器是很难指定和建立解决冲突的问题。虽然有一些例子同步适配器，在野外，以及在AndroidSDK，其中不少是致力于单用户接触名单和只读适配器（例如，用户是不能够修改联系人数据，通过Android接口），在这个意义上说，他们是但使用有限。添加共享联系人，并在与智能手机游戏相当的接触数据的读/写访问：它不再是一个从时间服务器中的数据读取时间，并相应地更新我们的名单的问题，但是，因为我们会看到，建立类似的文档库或一个版本控制系统分布式系统之一。从这个意义上说，已经在几个标准的形式做了很多工作，最突出的是SyncML的2。这是一个复杂但非常完整的协议，专门面向移动通信系统，提供多种同步模式，尤其是对同步移动设备和服务器之间的联系人和日历信息。虽然它提供了一个完整的解决方案，但许多同步的需求，通常需要在系统集成和存在的第三个服务器在一个集中的方式管理所有不同的数据源。这种设计可实现复杂的设置，而是代表着一种在一台服务器上负担更简单的数据源，我们要允许安装简单共享。此外，第三个服务器设置，可以从系统管理员和企业政策面临的反对面。在这方面，建设的一个特设的解决方案可能是一个更好的选择。3假设特定的格式，如XML的一些其他作品树结构。厂商也在推动云服务联系人的同步使用。一个小的比较，可以发现Funambol的网站（同步供应商）套餐4。而使用这种类型的系统事实上是让许多企业都沉默寡言使用云服务来保存敏感数据而使得该解决方案被采取。什么可以被认为是另一种极端的规模，我们发现对等（P2P）的方法5尝试解决P2P网络中的问题。科恩6提出了一个对象存储在移动设备上的P2P同步的Java框架。虽然这些方法是在他们自己的权利之内（例如建立一个P2P的社会网络）有趣的，他们是不是一个好适合自然集中的企业IT基础设施。目前使用的其他战略包括使用如Microsoft Sync Framework的专有框架7或使用分布式移动数据库（这样的工具可以发现8）。无论这些解决方案怎样，但是需要系统设计明确架构的优势，因而难以适用于现有系统。在这方面，我们发现，很少有允许与现有服务器系统的同步算法。这种算法通常是专有的，仍然需要某种程度在服务器端的变化。在这方面，在算法提出定义了一个明确的先决条件和小集，服务器系统必须提供，以确保正确的同步。一套这样的先决条件是尽量减少在客户端提供的解决冲突，反对常用的服务器执行和其他分布式控制系统的设计模式。本文的其余部分安排如下：我们给的第2节中的联系人同步问题的说明我们还分析了分布式系统的类，并确定我们的联系人同步的优良特性问题。联系人同步问题，并分析其性能的建议方法在第3节。一些结论，并为今后的工作方向，我们最终在第4节的分析。2 问题描述正如很容易地看到的我们已经在引进先进的，可分为接触双向同步作为一个分布式系统。我们有效地从两个或两个以上的节点（一台中央服务器和一个或多个电话系统），访问相同的数据（联系人列表），以实现一些接触信息的有效传播以及在通过网络等数据变化传播的目标。2.1测作为分布式系统的同步联系布鲁尔的著名猜想9后来的证明赛斯吉尔伯特10所明确指出，不能在同一时间满足分布式网络服务三个属性，即一致性，可用性和分区容忍性。这样的结果，通常称作为第定理，一个可以实现分布式系统的理论极限。这是值得重新定义11的一致性，可用性和分区容忍性是指在分布式系统中，因为某些情况下可能会给予不同的语义相同的解释。一致性是所有节点在同一时间看到相同的数据的属性。可用性的属性，通过对系统提出的任何要求将收到一个响应。分区容忍的财产，由该系统继续运作，即使任何丢失的消息。应当指出的是，吉尔伯特和林奇的结果存在一个异步网络模型中举行，以及同步网络模型的存在。第定理的重要性所在的洞察力和理论框架，它给了分布式系统设计师当谈到建立这样的系统，培育了一个全新的设计（和不那么新），拥抱等一个定理，目的是最大限度地提高这些属性，在一些这样或那样（例如新一代爆炸NoSQL的旗帜下的数据库系统）。而代表第定理的理论依据的理解是资本的重要性在设计复杂的系统，它是我们不打算过于复杂的联系人同步的声明通过使用这种理论的问题。我只想说，这是一个分布式系统，我们的工作作为解决方案的设计师是选择最好的权衡。2.2分布式系统中的类目前分布式系统的一个简要概述，可以给我们以模式设计一些见解，可以权衡发现在目前的系统，可以帮助我们决定哪些最适合我们的要求。让我们开始在表1中一目了然。该表列出了几个分布式系统的第属性。请注意我们不谈论具体的系统，但许多这样的系统使有关选择。例如，一些的NoSQL数据库实际上可能不宽容所有的分区，有些VCS中可能会提供一些有限的支持脱机工作时，等等。还注意到，一些系统提供有限意义上的一致性，通常被称为最终的一致性，即使在存在第黑社会性质的另一对。虽然普通的一致性，是指财产，所有的节点看到相同的数据（或在一些定义相同的操作集），所有的时间，最终的一致性，是指财产所有节点会看到在某个时间点的操作或相同的数据集，因此为最终的名称。这种设计一直创造具有的缩写基地，基本上可用，软房地产普里切特12eBay和构成，最终一致从由布鲁尔定理提供了理论框架的一个重要的实际结果。然而，普里切特工作是，大量面向庞大的网络骨干和复杂系统的设计。下一个列表，我们可以看到定期（例如，集中）的版本控制系统（VCS）。这类系统通常采取的形式集中的客户机/服务器系统，基本上是不宽容的网络分区。他们最终是一致的，这一点很重要，不是因为任何固有的局限性（毕竟，如果他们不分区宽容，他们可能是作出一致和可用的），而是因为这种系统的用户通常只想要分享的变化，一旦考虑他们完成（在某个时间点）。传统视觉密码中添加分区宽容会使我们的DVCS。在这个设计中，每个用户都承载一个完整的信息库和改变传播，在许多方面，有时使用一个中央资料库，或有时发送给同行;设计允许许多不同的工作流程。这些系统的一个特定的属性是，扩大后缺乏集中式VCS的一致性，没有一个DVCS甚至目标最终一致。有效的优势之一一个DVCS索赔是所有用户的能力，有自己的分公司，补丁，和库的历史。这显然意味着，一般来说，DVCS的用户数据有不同的看法，因此数据是从来没有一致的，所有的节点。显然，这并不意味着所有数据都没有一致的（发展在这样一个有用的东西环境不太可能），而是只有一些数据是最终一致。通常这种集的数据是公共分行开发整合和宣传他们的变化。因此，如果最终一致性放宽时间上的一致性属性的约束，DVCSs进一步放宽在这样一种方式，只有部分数据将数据约束最终一致的，或简短，部分一致。其他的例子是NFS和P2P系统。前者通常假设下的一个可靠的网络和设计后者承担作为平等的所有用户的操作，避免使用中央服务器。这些条件都不过由于移动通信系统有限的网络连接和企业环境，为我们的系统造成不良通常设计的一组服务器。 2.3联系人同步的理想特性我们已经看到的几个分布式系统例子和他们的设计师所作的选择和权衡。这些教训应该证明是有用的联系人同步系统的设计。显然，我们的要求，包括分区耐受性和可用性：用户期望，即使没有网络连接访问他们的联系人名单，并希望它是甚至当其他节点可能。我们主要的设计决策，将是什么样的一致性保证我们要履行我们的系统。乍一看，人们可能会认为，最终的一致性是可取的，但在这样一个模型，在接触的缺失手机会导致删除服务器中的第一接触，这会慢慢地传播到所有手机客户端。显然，这可能会导致严重的安全事故，如果手机丢失或由攻击者，谁可以删除从系统中的所有联系人。部分的一致性，可以解决这个问题，忽略两侧删除的联系人系统。有其他用途的情况下，这部分的一致性，可能是价值：例如，用户可能要附加不同的元数据，以相同的接触（在哪一个组接触，应在手机显示）。我们可以得出结论，那么，我们的系统的优良特性，将成为分区宽容，可用部分一致。 表一：分布式系统和它们的属性至于执行Web应用负载测试的困难，也可以考虑类似的性能测试。负载测试发现故障，主要是在运行环境上。3 解决联系人同步我们已经看到DVCS的设计显然适合我们的设计选择，但是，它也确实DVCSs提供像两个节点之间同步的能力，无需使用服务器的功能。虽然这个功能肯定是有用的，跟踪了什么样的变化传播和人可以是一项复杂的工作，可以构成一种负担用户在数据冲突的形式，改变跟踪，和其他问题，使一个DVCS方面的意识，但不棘手的问题。我们真正想要的扭曲，像在DVCS，并不是所有的数据更像是一个VCS系统应该是同步的。这显然更容易比一个完全成熟的DVCS系统来实现。另一个重要的灵感来源显然是SyncML协议。该协议定义了一组七个不同数据同步的算法。其中，只有两个提供双向同步，首先是“双向同步”第二个是“慢同步”。双向同步的SyncML的版本，开始为他们发送到服务器处理客户端的变化。服务器处理这种变化，然后将一套自身的变化公认的或最终的变化客户端。该算法明显效果很好，但需要一个智能的服务器能够自动解决冲突和其他数据处理。然而，我们的制度设计的假设下，该服务器没有专门执行接触同步任务。在此约束下，解决冲突必须在客户端上执行，因为我们服务器可能不能够执行这样的功能。“慢速同步”算法是在这两个数据库中的所有元素都对每一个比较昂贵的算法其他。我们不会在本文提供的详细描述，但它遭受了同样的问题，普通的“双向”算法。3.1一个简单的算法正如我们已经看到过，VCS设计也许是最适合我们的问题。作为给出的算法1，不应该作为一个惊喜。事实上，我们模仿通常的工作流程和算法，对于CVS，Subversion用户，和其他传统视觉密码的日常使用。该算法采用类似概念的“锚”，可以发现在SyncML的，即一个对象，它代表在一次成功的同步操作。留给了如何表示时间（日期，版本号等）不同的SyncML服务器系统方法1，但是，最后成功地锚保存在客户端，而不是在表现服务器。该算法的工作原理如下。客户端的请求，因为目前的锚所有修改的接触已储存。如果没有锚被发现，从服务器中检索所有联系人。在下一步中，它得到所有本地修改的联系人，自上次成功同步操作。在Android中，此信息存储接触每一个标志，它标志着作为“脏用户任何时间修改这种接触。一旦我们拥有了一套在服务器上修改联系人和修改接触客户端，我们获得了两个集合的交集。这个集合中的元素是冲突的候选人;元素，这一套非冲突。四套接触，然后计算。算法1synContacts（lastSync：锚）表2 测试配置从这些四套，CCS和CCL提出解决冲突的用户（见图1），和一项决议，将CR创建，然后加入与CS和CL。然后我们发送新CL服务器（它被成功地发送到服务器后，CL是标记为干净）。最后，CS被存储在本地（在同一进程中的清洁标记）。3.2性能分析正如我们可以看到，算法是有效的，在这个意义上，一般来说，只传送需要两个系统之间的接触，以及更重要的是相当低的服务器和客户端之间的往返（2个或3HTTP往返取决于会话是否是积极的，或必须重新开始）。测量的性能，但是这是困难的，由于该平台的异构性和网络连接。挂钟时间变化很大，模拟器或与实际电话（同样可以说，不同的手机之间的运行时）运行时，运行时。作为一个经验法则，200个联系人同步可以采取壁时间为270秒（0.77接触/S），当在模拟器中进行。这包括模拟器作为SugarCRM的是在虚拟机上运行在同一台物理机器上运行时的网络和存储时间。相比之下，HTC Desire HD的手机中执行相同的操作时，墙上的时间大约是45秒，产生4.6联系人/ S或六倍加速。 由于不同的性能特点，测试的目的，我们将使用Android模拟器，因为这是最简单的设置来重现。表2中可以看出，我们的测试配置。 我们将测试的算法尺度如何与联系人的号码（我们将执行一个接触的完全同步范围从200到4000联系人名单）。我们也将尝试找出潜在的瓶颈，将指向我们未来优化。Fig 1 解决冲突的用户界面表三：时序结果这些性能数据包括股票SugarCRM的安装产生大约200个联系人。这些数据已被复制，需要实现整套的接触。表3中我们可以看到墙上的挂钟时间几个接触同步操作的结果。两种不同的操作，为每个列表的大小。首先是质朴的完全同步操作。二是强制的完全同步操作，一旦数据已经在Android手机数据库被加载。对于这两项操作两种结果的衡量和报告：墙上的时间过去了，每接触时间的平均金额。两个图表与结果还给出了这两个指标，总的平均时间（四舍五入第二精度），如可以可以看到在图2和3。Fig.2 华人街时间性能 Fig.3 平均性能我们要检查的字段是否存在，并发出相应的更新或插入命令。应当指出，虽然SQLite数据库支持“UPSERT”行动，不标准的内容提供商的API，使得这些操作繁琐的，比他们真正需要的是。这意味着，实际上有充分被迫同步执行许多比普通的作战命令，混读，写操作的操作，从而降低性能。有这几个修复。例如，插入空行，为每个空场时，首先创建一个接触。一旦完成后，我们可以随时发出更新命令，更新联系人时避免实地查找。这是有代价的持续性的空间，所以仔细分析权衡作出，因为Android设备可以在空间不足。另一个解决办法是得到一批非改性等领域，并比较他们的服务器列表，从更新列表中取出那些都是平等的。再次，仔细分析，必须作出权衡使用更多的内存来保存两份名单，可以在移动通信系统有限的资源。当上述战略思考，我们还必须考虑到被迫完全同步操作，应该是一个特殊的操作，并定期同步将只涉及修改，而不是整个列表的联系人列表，使问题小得多。今后的工作和分析因此，在这方面的保证，以便做出正确的决定。为算法的缩放特性，我们可以看到，它的行为与联系人列表的大小线性（如预期），直到我们打除1000 200大小的联系人列表中的原始同步联系人列表的大小，2。这种差异或许可以归结到Android的GC踢，但为何有需要进一步调查就是这样一个退化之间的200和400的联系人列表的大小。在这一点上，有两个问题需要解决。首先，股票SugarCRM和PHP的安装进行修改，以允许更多的内存，为了避免内部服务器错误。VM堆在Android方面，要增加，以避免内存错误时，解析响应。“问题仍然存在或多或少直到4000联系人列表的大小线性。为了算法正确执行，仿真设备，应给予更多的RAM。可以同步两种类型的性能退化观察，虽然这是很难确定这是否是由于测量误差，气相色谱仪，甚至是服务器端的问题。虽然算法并不严重扩展，可以看出，它患有需要调整堆的大小与大接触列表Android的终端和服务器。可以用两种方法来解决这个问题。第一，将使用一个流API解析输入，因为它是在内存中缓冲，而不是读。然而，这将需要一个不同的程序架构和可能的第三方库，以便为JSON流解析。第二种方法将下载批几百个实例的接触和解析之前下载的休息。这以后的做法有缺点需要更多的往返，但它似乎可行的，如果采取特别的照顾，在下载的接触正确的顺序，保证不丢失更新。 Fig.4 丢失更新问题3.3算法的正确性虽然不是一个正式的证明，但有趣的是那些功能服务器和客户端必须以支持算法正确的行为。没有太多的分析我们可以看到，在该算法中有缺陷可能导致的损失数据。例如，考虑在图中所描述的序列。4。在这种情况下，用户修改联系，建立联系A1在客户端后，服务器已要求修改联系人列表（以及锚标记为DATA1）。这种接触也进行了修改，在客户端创建一个“1，但接触A1还没有被发送到客户端，因此客户端是无法检测到冲突。然后，客户端发送服务器，盲目地覆盖这个修改过的联系人A1接触“1接触，造成的数据丢失。显然，我们需要从服务器的支持，以避免这个问题。请注意，任何算法都不可能工作正确只要服务器不提供任何支持检测冲突或锁定。这一要求是不作为强，因为它可能似乎：服务器必须支持某种机制，以避免这个问题，因为它可以发生时，客户访问服务器通过Web或桌面界面（也请注意，此功能是不是冲突的要求轻得多决议，这是我们丢弃的SyncML算法服务器必须提供此功能）的原因之一。在SugarCRM的，乐观锁定的情况下被使用，而服务器将检查是否存在冲突时犯下的变化。这种设置是为我所用的情况下（低数据争）绝配：如果SugarCRM的管理，以提醒我们的错误当我们把它的变化我们可以取消操作，并稍后重试（很像是一个失败的交易试在稍后的时间）。这是可能的，因为在这一点上，算法还没有意识到任何副作用（例如，它并没有改变无论是本地或远程数据库）。但不幸的是，SugarCRM的不似乎通过乐观锁定当被调用REST或SOAP调用。这已报告44316错误13在SugarCRM的bug跟踪系统。类似的问题可能会影响当地的联系人数据库;然而，这些都可以很容易被锁定的数据来解决。这是可能的因为，在Android平台，接触的编辑必须提供同步开发，因此我们可以选择禁用它，而同步。有了这个设置，我们就能避免在客户端的更新丢失问题。 一旦我们致力于服务器的数据，我们如何能保证将完成该操作吗？答案是：它其实并不重要。假如我们失败了，下一次我们尝试同步，锚将仍然是旧的，我们将撤出所有的新变化（包括那些我们发送给服务器），加上所有的旧的变化。由于我们的算法是足够的智能来区分真正的冲突，比较实际的接触，我们不会得到这些接触任何冲突。应当指出，应采取特殊照顾本地创建已发送的联系人和远程创建但是，由于故障或其他原因，而不是与本地创建的联系人。在这种情况下，新创建的发送之前接触中，我们检查，如果它们已经存在在服务器列表中，若有相应的链接他们。然而，这是透明的它为用户由resolveConflicts操作是自动完成的。从用户的角度来看，一切都将正常工作即使一些带宽将浪费不必要的数据由重传需要采取往常一样，并没有特别的行动。最后，还有一个问题是一个删除的联系人会发生什么。我们可以看到从算法，似乎没有特别的行动要采取。这是因为删除的联系人在这两个系统的工作方式（SugarCRM和Android的）。当接触删除它没有真正从数据库中删除在任何平台上，而是标记为删除的联系人。选择不同步表示的标志，我们完成删除的接触不会传播整个系统的要求。这可以很容易地扩展到任何其它数据或元数据，我们不妨保持一致的数据集，例如组成员或所属公司可能被排除在同步过程。4 结论和未来工作移动计算是一种很强的现实，在今天的IT基础设施和共享数据的需要下，并使其随处可见，在任何时间，跨越多个设备运行不可靠的条件下是可以解决的一个挑战不同的方法。 我们已经介绍了一起涉及的理由，导致移动通信系统的分布式系统的一个例子这个设计，通过观察其他系统和应用在第定理所体现的原则（一致性，可用性和分区容忍）及相关的工作。我们也归入这种设计，它自己的类别，有部分作为一个理想的功能的一致性。我们已经表明，该系统可以只要正确和可靠的一些基本工作提供支持的服务器系统，即使在网络或设备发生故障的事件。这来自于一些成本失败后的数据传输时的冗余。 对今后的工作将面向两个不同的方向。首先将测量的实际表现和在跨越多个设备当前系统的瓶颈。这将允许我们优化的真正的瓶颈，无论设备怎样。第二，将有关同步日历数据，不同的是，接触的数据，可以从中受益一个完全成熟的分布式设计，使用户的情况下发送事件在不同的网络（短信，电子邮件等）需要有与服务器的连接，这可能是很难实现的，例如（漫游用户可能只有短信作为一种可行的运输）。参考文献：1 J. Nathan Foster, Michael B. Greenwald, Christian Kirkegaard, Benjamin C. Pierce, Alan Schmitt, Exploiting schemas in data synchronization, Journalof Computer and System Sciences 73 (2007) 669689.2 D.-W.K. Byung-Yun Lee, Tae-Wan Kim, H. Choi, Data synchronization protocol in mobile computing environment using syncml, in: 5th IEEEInternational Conference on High Speed Networks and Multimedia Communications, 2002, pp. 133137.3 T. Lindholm, XML three-way merge as a reconciliation engine for mobile data, ACM Symposium on Document Engineering (2004) 110.4 Funambol Inc., Evaluating Mobile Cloud Sync Solutions: From Apple MobileMe to Vodafone Zyb.5 J. Vogel, W. Geyer, Li-Te Cheng, M. Muller, Consistency control for synch