昨天，我们跟大家分享了印象笔记在新年万象更新的第一个好消息，同步速度提升4倍。今天，我们的首席技术官(CTO) Dave Engberg和高级软件工程师Ed Roskos就将这同步提速背后的故事，也就是后台服务器所进行的重新设计和升级详情，为大家逐一呈现，希望每位用户都能清楚的知道自己每天最信赖的同步服务，如何有效运行，如何不断提升。
(本文翻译自印象笔记首席技术官(CTO) Dave Engberg和高级软件工程师Ed Roskos联合撰写的Synchronization Speedupification。)
历史回顾
2007年，设计印象笔记同步协议(synchronization protocol)之初，我们希望每个客户端能用最少的网络请求(network requests)找到用户帐户里的全部内容，或者上次同步后的相关修改。我们选择了一种无锁的基于对象状态的复制模型，这是一种在我们的多相、时而循环的数据模型(data model)中，基于每个对象特定帐户的更新序列号(USN)的一种数据模型。客户端只要发出指令：“嘿，有什么更新？”服务器就会返回用户笔记、标签、笔记本和资源等的全部相关修改，通常这些都包含在一个HTTPS响应里。
这个数据传输协议一直正常运行，但是，过去六年中，从2008年2月的两个空shards服务器，发展到今天存储了几十亿条笔记的400多个shards服务器，我们最初的服务器执行确实遇到了一些可扩展性方面的挑战。单单是向客户端发送下一个SyncChunk对象集，就需要占用大量的输入输出操作才能查找到准确信息。
在我们最初的设计中，每个shard服务器在一个MySQL数据库中存储约100,000个帐户的元数据，运行于每分钟15000转的机械硬盘RAID1上。每个对象类型存储在各自的表里，使用一个主索引和一个次级索引，以便高效地按用户查找记录，并按更新序列号排序。例如，以下就是我们的“notes”表的部分相关结构。
CREATE TABLE notes (
id int UNSIGNED NOT NULL PRIMARY KEY,
guid binary(16) NOT NULL,
user_id int UNSIGNED NOT NULL,
notebook_id int UNSIGNED NOT NULL,
title varchar(255) NOT NULL,
update_sequence_number int UNSIGNED NOT NULL,
...
KEY user_id_usn_idx (user_id, update_sequence_number),
UNIQUE guid_idx (guid)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
上述表里的三个索引都有可能在短时间(对数级)内找到单个记录或者多个记录的范围。但实际的数据记录在磁盘上按主键聚集存放(clustered)。要通过次级索引查找多个记录(例如：user_id, above)，数据库必须先遍历全部次级索引，再跟随指针到达各个独立记录所在的实际磁盘页。
当一个客户端对服务器发出指令：“请给出我的帐户里更新序列号高于8476的最多100个对象”，用户的shard服务器就需要在多达9个不同表中查找相关记录，再把这些结果整合到一起，并返回更新序列号最低的100个匹配结果。以上操作是由一个巨大的SQL联合操作(UNION)来执行的，会在每个表里查找user_id 这个次级索引，再为每个符合条件的记录加载初选结果页。在最坏情况下，满足一个请求可能就需要从磁盘加载上千个非连续页。
以上这些操作会涉及大量代价高昂的输入输出操作，导致客户端的响应缓慢。随着个人和企业共享笔记本的剧增，问题会更严重，因为每个共享笔记本都需要独立的客户端查询。于是，我们的运维团队通过把数据库从机械硬盘转移到固态硬盘(transitioning our database from spinning disks to SSDs)，有效缓解了问题，但从根本上解决问题必须对软件程序进行优化。
引入同步索引
为了提高同步效率，我们希望避免访问十多个不同的表才能确定放进每个SyncChunk的信息。为了支持共享笔记本和企业用户使用量的增长，同时实现新功能，例如内容类(contentClass)同步，我们希望把足够充分的信息放进一个表里，以使MySQL返回Java中间层的不必要数据最小化。
进一步考虑，实际上，我们从数据库的表(笔记、标签等)中查询出的记录是多于要返回给用户的。要从笔记本和标签返回3个记录，我们就需要查询3个<note ID, USN>对和3个<tag ID, USN>对，再以USN排序，找到要返回的记录。读取数据库的操作代价高昂，所以，仅仅为了读取你需要的数据而逐行查询会增加成本。在MySQL中对表的数据值进行过滤时，还经常需要对表做额外的连接(join)操作。
因此，我们开始探索，设计一个表来索引所有需要的数据，这就是同步索引(sync index)表。通过查询这一个表，就可以确定下一步需要读取的候选NoteStore实体的主键。通过访问单个表，并且让各记录不必依赖于数据库的其他数据值，就可以在MySQL内高效地筛选实体了。
我们选择<user_id, USN>作为主键，这样用户的同步索引记录就可以按同步需要的次序存放于磁盘上。读取一页数据库数据，就会返回多种类型的有效筛选的结果。我们将数据库的记录所占用的空间设计得尽量小，以便在一次输入输出操作中封装尽可能多的结果。每条记录需要的信息包括以下这些：
- 删除状态(Expunged status)：在给出的更新序列号下，实体是否已经从服务上删除？
- 活动状态(Active status)：共享笔记本或企业笔记本(linked notebook)同步时会隐藏非活动笔记(inactive notes)。如果一条笔记未产生任何活动，我们就会发送“expunge”，如果在chunk里不包含删除的(expunged)GUIDs就跳过这条笔记。
- 实体类型和对象ID：我们需要知道记录所指向的类型(标签、笔记等)和对象标识符，这样我们才能查询相应的表。一个实体在任意时刻可能是活动的(active)、非活动的(inactive)或者删除的(expunged)。因此,我们把实体类型(笔记、标签等)和一个“标识符(modifier)”(active, inactive, expunged等)组合到一起，并压缩到1字节的字段。
- 包含笔记本ID：印象笔记里的大部分权限是针对笔记本级别的。对于共享笔记本和企业笔记本的同步，笔记本标识符使我们无需访问那些查询表，就能够筛选大部分笔记和资源。
- 内容类(Content class)：部分应用程序，例如印象笔记•人脉和印象笔记•食记，在笔记里定义一个内容类(contentClass)，就可以只同步符合相同前缀的笔记。为了节约空间，我们使用32位的哈希值来大致匹配前32个字符，而不是存储整个内容类。
以上涵盖了一个实体的“当前(current)”状态。我们同样还需要一些历史状态。在允许访问某个帐户的适量笔记本的前提下，同步时，如果一条笔记从允许访问的笔记本移动到未授权访问的笔记本中，服务将发送一个“expunge”活动。我们在同步索引中把这种状态记录为“moved”，并把“moved”添加到上面提到的实体类型标识符(modifier)，再增加一个字段来记录移动之前的笔记本ID。
我们还增加了一个之前没有的新状态。目前我们的很多客户端对企业帐户一次只同步一个共享笔记本或企业笔记本。这样，就可以使这些客户端重复利用现有的、且行之有效的共享笔记本或企业笔记本同步逻辑来同步、检测一个笔记本的访问权限，但是，会随着用户加入企业笔记本的数量增加而相应增加对服务的请求次数。同步索引会记录接受者对笔记本“失去访问权限”的历史记录。现在，服务会发送一个“expunge”指令来通知客户端已经失去访问权限。我们就可以再次使用实体类型标识符来记录“失去访问权限”，为失去访问权限的接收者的用户ID添加一个字段。印象笔记客户端以后将切换成一次查找同步所有企业笔记本。
因此，结果表如下所示。当值为空时，可空字段只占一比特。
CREATE TABLE IF NOT EXISTS sync_index (
user_id int UNSIGNED NOT NULL,
update_sequence_number int UNSIGNED NOT NULL,
entry_type tinyint NOT NULL,
notebook_id int UNSIGNED,
grave_notebook_id int UNSIGNED,
object_id int UNSIGNED,
guid binary(16),
content_class_hash int UNSIGNED,
recipient_id int UNSIGNED DEFAULT NULL,
service_updated TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
PRIMARY KEY (user_id, update_sequence_number),
KEY objectid_entrytype_idx (object_id, entry_type)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 ;
对于读到这里的程序员而言，你可能已经想到一个很明显的问题：sync_index的状态从多个服务实体表中自我复制，那么如何和那些表保持同步更新呢？答案就是，用Hibernate拦截器。对服务实体的所有修改都要经过Hibernate。我们写的拦截器代码会处理反规范化(denormalization)和哈希算法(hashing)。如果你修改了一个笔记属性，拦截器就会检查它是不是内容类(contentClass)，并以此更新同步索引中的笔记和资源记录。如果你把笔记从一个笔记本移动到另一个笔记本， 拦截器就会判断是否要为先前的笔记本创建新的“moved”历史记录，是否要删除现在的“当前笔记本”之前的历史记录，并更新全部笔记的笔记本标识符和同步索引中的相关资源记录，以允许共享笔记本和企业同步中对笔记本ID的高效筛选。修改共享笔记本记录的结果是创建或删除“失去访问权限”记录。当我们的工程师编写服务API代码时，以上的这一切就在幕后默默进行着。无需考虑怎么做，一切自动实现。
大规模数据迁移
当完成了有效地在sync_index中存储和更新记录的代码后，我们就要找到一个方法把之前六年的历史加载到sync_index中，以允许新客户端同步旧帐户。在不影响用户，又不引入不正确记录的前提下完成这件事，比我们预计的还要难。经过几周的试错，我们得出以下方法：
- 对于每个表(笔记、笔记本等)，为同步索引所需字段执行SELECT … INTO OUTFILE
- 使用LOAD DATA INFILE将表加载到sync_index。
- 重新检查每个表，以便找到第1步和第2步之间的实时修改所引起的过期插入记录。把它们的主键存储到磁盘里，再加载进一个(小)临时表。
- 使用一个MySQL multi-table DELETE，把临时表连接到sync_index，并仅移除符合条件的表。
第1、2步比更明显的INSERT … SELECT语句至少快3倍，还能避免锁定记录，从而避免应用程序运行时出现讨厌的超时问题。第3、4步在非事务性插入后进行清除，而相对于更直接的删除来说，它还避免了大资源表令人痛苦的锁定问题。
到底有用吗？
验证我们的工作成果有多种形式。我们开发并使用了一个全新的单元测试框架来验证同步索引中的正确值和同步结果。这一系列综合测试运行在我们所有的持续集成版本(continuous integration builds)上。我们的系统测试团队在测试平台上反复进行回归测试。在代码中，添加了大量完备性检验，例如在把同步索引记录添加到sync chunk时，对照服务实体验证它的状态。我们还通过同时运行先前和现在的同步算法来验证最终结果的正确性。最后，我们重新构架了数据中心的基本设施和服务器配置，以便掌控这项新技术在产品使用中的成功引入。
在这里，我们举个特别的例子。我们测试了自己的一个帐户同步时间，这个帐户中有2456条私人笔记和保存在31个企业笔记本的2861条企业笔记。在我们的测试中，引入全新同步索引的同步速度比之前快了大约99%。（注：这里的同步速度提升的99%，仅针对这个用来做测试的帐户，包括2456条私人笔记和保存在31个企业笔记本的2861条企业笔记。）
用户可以感觉到的速度提升，反映在各个同步函数的运行时间中值上。例如，下面的图表显示了在一个shard服务器上调用 getLinkedNotebookSyncChunk函数的响应时间中值，在引入sync_index前后的变化：
除了减少用户的笔记同步时间以外，我们所作的修改还显著降低了shards服务器对输入输出操作和CPU的使用率。下面图表显示的是在上周(蓝色)和2013年11月份随机抽取的一周(绿色)中一个八核服务器的平均负载：
这将会给服务器留出更多资源来支持印象笔记未来开发的新功能，以及随着用户上传数据增加而不断变大的帐户。
我们还在流程上做了一些其他优化，来进一步提升性能，但我们对目前获得的进步已经感到非常激动。感谢你一路的支持，我们也将不断扩大印象笔记的规模，为你永久珍藏所有记忆！
