内容来源：万方 / 知网 / 爱学术
作者：邓璐
1
背景介绍
随着我国互联网技术的飞速发展，我国网民规模已达到5.91亿，电子商务、网上交流已经成为一种重要的生活方式，人类社会活动正在从传统的的物理空间延伸到网域空间。近些年来中国网站数量增长迅速，如下图所示。
图1 近年中国网站数量增长图
本次选取分析的论文是基于 863 重大项目——网络身份管理与应用技术中的子课题中的虚拟身份管理，随着虚拟身份应用数据的巨大增长，它针对电子商务、社会化媒体等互联网应用中存在的大量用户虚拟身份，这些用户与这些身份之间存在一对多的关系。系统通过多种途径获取用户的虚拟身份信息，并进行有效的存储和管理,形成虚拟身份管理的数据基础——虚拟身份库。虚拟身份库与多种互联网应用系统存在数据更新及查询接口，支持各类信息的实时更新及虚拟身份查询请求，可以为上层互联网应用如舆情分析、电子商务欺诈追溯等应用提供身份查询支撑。
虚拟身份管理主要研究以下两方面内容：虚拟身份管理技术与系统，它为整个系统提供基础数据及其管理功能和基于虚拟身份的虚假、不良信息追溯技术及示范应用。以下内容围绕论文中的虚拟身份数据的存储子系统的设计与实现部分内容展开讨论。
2
相关技术
第一，数据模型的选择。传统的关系数据库不满足虚拟身份数据的特点，故选择 NoSQL 数据库中的经典代表Cassandra 数据库。它以键值对存储，结构不固定，每行可以根据需要，动态增加或减少自己的键值对，也可出现不一样的字段，这样就不会局限于固定的结构，可以减少空间和时间上的一些开销。
第二，数据结构及存储机制。Cassandra 数据库存储采用的是 Memtable 和 SSTable 相结合的方式。选择 Cassandra 数据库来存储海量虚拟身份数据。它是易扩展的，拥有灵活的 schema, 可以任意改变字段，具有多个数据复本，支持对多条记录同时的查找。
第三，数据划分方法。数据划分的目的是将相关的数据尽可能的划分到同一节点。数据划分可分为垂直划分和水平划分。垂直划分是为了减少目标表的宽度，使某些特定的列被划分到特定的分区，每个分区都包含了其中的列所对应的行。水平划分，为了减少目标表的长度，使某些特定的行（对象）被划分到特定的分区，每个分区都包含了其中的行所对应的列。
第四，hash 算法函数，任何可以将各种长度的二进制值映射为固定长度的二进制值的算法。一致性hash算法是一种特殊hash算法。目的是尽可能让对象映射到相同的缓冲节点，这意味着当增加一个缓冲节点，它从所有的其它缓冲节点中得到共享数据，当删除一个缓冲节点时，它其中的数据会被共享到其它剩下的缓冲节点。改进一致性 hash 算法是在一致性 hash 算法的基础之上增加了对虚拟节点的考虑。其目的是把哈希的结果尽可能平均地分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
3
虚拟身份数据存储子系统设计
第一，存储子系统的整体设计。首先要分析虚拟身份数据的特点，只有知道数据的特点之后，才能制定合适的、切实可行的存储设计方案。虚拟身份数据是海量的，可能是 TB 级别甚至是 PB 级别，导致无法一次性载入内存或者无法在较短时间内处理完成。此外，还有如下特点：1）易扩展；2）数据类型繁多；3）不具有统一格式；4）多处理。它区别于一般应用数据的显著不同在于，虚拟身份数据没有明确的边界，而是会随着用户使用的应用服务增多而动态扩展。下图给出虚拟身份数据存储设计所考虑的主要技术路线。
图2 虚拟身份数据存储设计的技术路线图
第二，存储子系统的数据模型设计。数据库以用户唯一标识为主键，设多个列族，各列族存储唯一标识用户在一个服务应用中使用的账号信息，包括虚拟账号，账号属性，相应的注册时间与最后登录时间。虚拟身份数据库数据模型的构架为下图所示：
图3 虚拟身份数据库的数据模型框架
第三，存储子系统的数据划分设计。数据划分在维基百科的定义是：数据划分对数据库进行分割或者将构成的元素划分成不重复的独立部分，而数据划分的目的是为使具有相关性的行或列尽量能够一起存储，从而可以减少在查询处理中网络传输的数据量。具体研究方向分为节点能力划分和节点内部划分。
第四，存储子系统的数据副本设计。数据副本是分布式存储系统中必须要考虑的问题。从副本数量上来说，创建太少容易产生数据热点问题，延长访问时间太多则会造成无谓的存储空间浪费。虚拟身份的数据模型中 Column Family 是用来存储唯一标识的，故以唯一标识 Column Family 为数据单位考虑副本数量问题。具体的细分知识点为初始副本和动态副本。
有关存储子系统的实现过程，按照以上设计流程，可分为数据模型的实现，数据划分的实现和数据副本的实现三类。
总结需要用到的相关技术，首先需要了解虚拟身份数据的特点；在此基础上进一步分析 Cassandra 数据库以及 MySQL 数据库的数据模型；设计针对虚拟身份数据的 Cassandra 数据库和 MySQL 数据库相结合的数据模型；然后设计加权改进一致性hash算法和基于虚拟账号相似度相结合的数据划分方法来合理分配数据；针对数据副本，从初始副本和动态副本两个方面分别进行了研究；最后对它们实现中的重要算法做了说明，对虚拟身份数据存储的核心分析为虚拟身份的存储提供了切实的保障。
4
实验展示
第一，在数据划分方面。Cassandra 数据库采用的是改进一致性 hash 算法来决定数据存储于哪个节点，而本文针对虚拟身份管理的实际情况，提出了加权改进一致性 hash 算法，就是充分考虑了节点机器的实际性能，不将超负荷任务分配给节点。为了测试加权改进一致性 hash 算法相对于改进一致性 hash 算法的性能，我们将机器分为 3 组，每一组的分配情况如下表所示：
表1 分组节点配置
分别对上表所示的3组机器配置情况，以 50000 条查询请求为例做测试，横轴表示数据库中数据量规模，实验分别选取：100GB、200GB、300GB、400GB 和 500GB。纵轴表示这 50000 条查询请求总共需要的查询响应时间，得到的测试结果如下图所示：
图4 节点间数据划分对查询的作用
通过实验，第1组改进 hash 算法与加权改进 hash 算法的时间是相同的，因为不存在机器节点性能的差异，而第2组和第3组就可以明显的看出加权改进 hash的优势。
第二，除节点选择外，还需考虑节点内部数据存放问题。对于同个唯一标识下的数据，将虚拟账号相同或相近的平台数据接连存放。下面测试存放的性能。全部的30个机器节点分布来存放数据库数据，来测试内部数据划分的影响。在测试 50000 条查询请求中有15%左右是关于虚拟账号的查询。横轴表示的是数据库中数据量规模，这里分别选取：100GB、200GB、300GB、400GB和 500GB。纵轴表示的是这50000条查询请求总共需要的查询响应时间。
图5 节点内部数据划分对查询的作用
实验表明，随着数据库规模变大，两种情况的查询响应时间虽然都上升较大，但考虑内部相关的情况时间上升幅度明显较小，所以基于虚拟账号相似度的考虑对减少查询响应时间具有一定作用。
第三在数据副本方面，考虑了初始副本以及动态副本。初始副本考虑了数据片的规模，以与它的规模平方根成正比。最少副本为1，最多副本为4。测试这种模型对查询的影响，先不考虑动态副本，即不随着热点的变化而动态增加或减少副本的数量。对比模型中，采用的是统一的数据副本数量，其值为4。同样是对于30个机器节点，50000条查询请求来测试，横轴仍然表示的是数据库中数据量规模，这里分别取了：100GB、200GB、300GB、400GB和500GB。纵轴也表示的是这50000条查询请求总共需要的查询响应时间。测试结果如下图所示：
图6 初始副本对查询的作用
实验表明，随着数据规模的增大，按规模分配的副本方法和固定副本数量4的方法的查询时间都有比较明显的升高，但是同规模下比较，按数据规模分配比固定副本数量4的方法上升高一点，但整体上没有太大影响。而同时按规模分配的副本方法比固定副本数量4节省了大量存储空间，所以时间代价可以接受的。
最后，在此初态副本的基础之上增加对动态热点的考虑，就是说随着查询是热点的变化将影响副本的数量。对于 30 个机器节点，500G 数据库规模来做测试，其中横轴表示的是数据查询请求的数量，单位是万条，这里分别取了：1 万条、2 万条、3 万条、4 万条和 5 万条。纵轴表示的是在数据库规模为 500G 的情况下，不同查询请求数量总共需要的查询响应时间。其测试结果变化为下图所示：
图7 动态副本对查询的作用
实验表明，随着查询请求数的增多，动态副本上升的幅度比固定副本要小的多，动态副本弥补了只考虑初始副本时的劣势。在性能上，与固定副本数量为4的方法相比，查询请求数越多，它的优势就越明显。
关于 天 方 夜 “谈”
天方夜谈原意讲不切实际的东西，而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。
方班人有自己的浪漫，
我们探讨知识，谈论理想，
采摘科研的繁星，
脚下是星辰大海。
天：代表我们的理想犹如天空般浩荡
方：代表方班
夜：代表代码人的冷静与静谧
谈：代表方班愿与您，就领域内的经典思想和前沿成果“秉烛夜谈”
