Google云计算原理与应用(四)

简介: Google云计算原理与应用(四)


七、海量数据的交互式分析工具Dremel

(一)产生背景

  Google 的团队结合其自身的实际需求,借鉴搜索引擎和并行数据库的一些技术,开发出了实时的交互式查询系统 Dremel。

Dremel支持的典型应用:

  • Web 文档的分析
  • Android 市场的应用安装数据的跟踪
  • Google 产品的错误报告
  • Google 图书的光学字符识别
  • 欺诈信息的分析
  • Google 地图的调试
  • Bigtable 实例上的 tablet 迁移
  • Google 分布式构建系统的测试结果分析
  • 磁盘 I/O 信息的统计
  • Google 数据中心上运行任务的资源监控
  • Google 代码库的符号和依赖关系分析

(二)数据模型

两方面的技术支撑:

一方面:统一的存储平台

  实现高效的数据存储,Dremel使用的底层数据存储平台是GFS。

另一方面:统一的数据存储格式

  存储的数据才可以被不同的平台所使用。

面向记录和面向列的存储:

  Google 的 Dremel 是第一个在嵌套数据模型基础上实现列存储的系统。

  • 好处一:处理时只需要使用涉及的列数据
  • 好处二:列存储更利于数据的压缩

嵌套模型的形式化定义:

τ=domA1:τ[?],,An:τ[?]⟩

原子类型(Atomic Type): 原子类型允许的取值类型包括整型、浮点型、字符串等。

记录类型(Record Type): 记录类型则可以包含多个域。记录型数据包括三种类型:必须的(Required)、可重复的(Repeated)以及可选的(Optional)。

嵌套结构的模式和实例:

  文档的模式(Schema)定义,利用该数据模型,可以使用 Java 语言,也可以使用 C++ 语言来处理数据,甚至可以用 Java 编写的 MapReduce 程序直接处理 C++ 语言产生的数据集。这种跨平台的优良特性正是 Google 所需要的。

(三)嵌套式的列存储

1、数据结构的无损表示

  如下图示,带有重复深度和定义深度的r1与r2的列存储。

  重复深度主要关注的是可重复类型,而定义深度同时关注可重复类型和可选类型(optional)。每一列最终会被存储为块(Block)的集合,每个块包含重复深度和定义深度且包含字段值。

2、高效的数据编码

 Dremel 利用图中算法创建一个树状结构,树的节点为字段的 writer,它的结构与模式中的字段层级匹配。核心的想法是只在字段 writer 有自己的数据时执行更新,非绝对必要时不尝试往下传递父节点状态。子节点 writer 继承父节点的深度值。当任意值被添加时,子 writer 将深度值同步到父节点。

 下图是计算重复和定义深度的基础算法。

3、数据重组

  Dremel 数据重组方法的核心思想是为每个字段创建一个有限状态机(FSM),读取字段值和重复深度,然后顺序地将值添加到输出结果上。

当前FSM 写入值 下一个重复深度值 动作
DocId(开始) 10 0 跳转至Links.Backward
Links.Backward NULL 0 跳转至Links.Forward
Links.Forward 20 1 停留在Links.Forward
Links.Forward 40 1 停留在Links.Forward
Links.Forward 60 0 跳转至Name.Language.Code
Name.Language.Code en-us 2 跳转至Name.Language.Country
Name.Language.Country us 2 跳转至Name.Language.Code
Name.Language.Code en 1 跳转至Name.Language.Country
Name.Language.Country NULL 1 跳转至Name.Url
Name.Url http://A 1 跳转至Name.Language.Code
Name.Language.Code NULL 1 跳转至Name.Language.Country
Name.Language.Country NULL 1 跳转至Name.Url
Name.Url http://B 1 跳转至Name.Language.Code
Name.Language.Code en-gb 0 跳转至Name.Language.Country
Name.Language.Country gb 0 跳转至Name.Url
Name.Url NULL 0 结束

  如果具体的查询中不是涉及所有列,而是仅涉及很少的列的话,上述数据重组的过程会更加便利,下图中仅仅涉及 DocId 和 Name.Language.Country 的有限状态机。

核心的思想如下:

  设置t为当前字段读取器的当前值f所返回的下一个重复深度。在模式树中,找到它在深度 t 的祖先,然后选择该祖先节点的第一个叶子字段 n。由此得到一个 FSM 状态变化 (f,t)->n。

有限状态机的构造算法

(四)查询语言与执行

  Dremel 的 SQL 查询输入的是一个或多个嵌套结构的表以及相应的模式,而输出的结果是一个嵌套结构的表以及相应的模式。

  Dremel 的类 SQL 语言支持嵌套子查询、记录内聚合、top-k、joins、自定义函数等操作类型。

  Dremel 利用多层级服务树(multi-level service tree)的概念来执行查询操作。

  • 根服务器:接受客户端发出的请求,读取相应的元数据,将请求转发至中间服务器。
  • 中间服务器:负责查询中间结果的聚集。
  • 叶子服务器:负责执行数据来源。


  Dremel 中的数据都是分布式存储的,因此每一层查询涉及的数据实际都被水平划分后存储在多个服务器上。Dremel 是一个多用户系统,因此同一时刻往往会有多个用户进行查询。查询分发器有一个很重要参数,它表示在返回结果之前一定要扫描百分之多少的 tablet。

(五)性能分析

  由于 Dremel 并不开源,我们只能通过 Google 论文中的分析大致了解其性能。Google 的实验数据集规模如下图:

  MR 从面向记录转换到列状存储后性能提升了一个数量级(从小时到分钟),而使用 Dremel 则又提升了一个数量级(从分钟到秒)。

(六)小结

Dremel 和 MapReduce 并不是互相替代,而是相互补充的技术。在不同的应用场景下各有其用武之地。

Drill 的设计目标就是复制一个开源的 Dremel,但是从目前来看,该项目无论是进展还是影响力都达不到 Hadoop 的高度。

希望未来能出现一个真正有影响力的开源系统实现 Dremel 的主要功能并被广泛采用。

八、内存大数据分析系统PowerDrill

(一)产生背景与设计目标

两个假设结论:

(1)绝大多数的查询是类似和一致的;

(2)存储系统中的表只有一小部分是经常被使用的,绝大部分的表使用频率不高。

考虑两方面的内容:

(1)如何尽可能在查询中略去不需要的数据分块;

(2)如何尽可能地减少数据在内存中的占用,占用越少意味着越多的数据可以被 加载进内存中处理。

PowerDrill整个系统实际分为三个部分:

(1)Web UI

(2)一个抽象层

(3)列式存储

(二)基本数据结构

  下图阐述了 PowerDrill 采用的数据结构,简单来说就是一个双层数据字典结构。

  • 全局字典表:存储全局id和搜索关键字的对应关系
  • 3个块的数据:块字典记录的是块 id(chunk-id)和全局 id 的映射关系;块元素记录的是块中存储数据的块 id(注意不是全局id)。

(三)性能优化

1、数据分块

(1)背景

  传统的索引对于 PowerDrill 的查询场景作用不是很大,因此一个很自然的考虑就是对数据进行分块,过滤查询中不需要的数据块来减少数据量。

(2)方法

  常见的分区方法有范围分区、散列分区等。PowerDrill 实际采用的是一种组合范围分区方法。

(3)步骤

  领域专家确定若干个划分的域 → 利用这几个域对数据进行划分 → 每个块的行数达到阈值时就停止划分。

(4)局限

  PowerDrill 采用的数据分块方法简单实用,但是由于域的确定需要领域专家,因此这种方法在实际使用中还有一定的局限性。

2、数据编码的优化

  • 对于不同的块,如果我们可以确定块中不同值的数量,那么就可以根据这个数量值来选择可变的比特位来记录块 id。
  • 统计一组数中不同值的个数有一个专有名词,称为 “基数估计”。
  • 对于小规模的数据集,可以比较容易地统计出精确的基数。但是在大数据的环境下,精确的基数统计非常耗时,因此能保证一定精度的基数估计就可以满足实际的需求。
  • 基数估计的方法很多,大多利用了散列函数的一些特性,Google 内部使用的是一种称为 Hyperloglog 的基数估计方法的变种。

3、全局字典优化

优化中主要利用两个特性:

(1)全局字典是有序的

(2)排序后的数据常常有共同的前缀

  实际使用中为了进一步减少查询中需要加载到内存的全局字典,对全局字典又进行了分块。对每个全局字典块还会维护一个布隆过滤器(bloom filter)来快速确定某个值是否在字典中。

4、压缩算法

  Google 曾经对一些主流的压缩算法做过简单的测试,如下图:

  • 不管压缩算法的解压速度多快,总会消耗一定的物理资源与时间。对此PowerDrill采用了一种冷热数据分别对待的策略。
  • 在冷热数据切换策略中,比较常用的是LRU算法。PowerDrill开发团队采用了启发式的缓存策略来代替原始的LRU算法。

5、行的重排

  数据压缩的算法有很多,比较常用的一种称为游程编码(Run-Length Encoding,RLE),又称行程长度编码,其好处是压缩和解压缩都非常快。

  数据重排的过程等效于著名的 TSP(旅行商)问题。两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。PowerDrill 在实际生产环境中对数据分块时选定的那几个域按照字典序进行排序来得到重排的结果。

(四)性能分析与对比

我们比较关注的两组数据:

(1)在查询过程中,平均92.41%的数据被略去,5.02%的数据会直接被缓存命中,一般仅须扫描2.66%的数据即可得到查询结果。

(2)超过70%的查询是不需要从磁盘访问任何数据的,这些查询的平均访问延迟大约是25,96.5%的查询需要访问的磁盘量不超过1GB。

性能分析与对比:

PowerDrill与Dremel的对比:


PowerDrill
Dremel
设计目标 处理非常大量的数据集 分析少量的核心数据集
设计理念 处理的数据来自外存 处理的数据尽可能地存于内存
未进行数据分区,分析时要扫描所有需要的列 使用了组合范围分区,分析时可以跳过很多不需要的分区
数据通常不需要加载,增加数据很方便 数据需要加载,增加数据相对不便

九、Google应用程序引擎

(一)Google App Engine简介

什么是 Google App Engine:

  Google App Engine是一个由 Python 应用服务器群、Bigtable 数据库及 GFS 数据存储服务组成的平台,它能为开发者提供一体化的可自动升级的在线应用服务。

Google App Engine 可以让开发人员在 Google 的基础架构上运行网络应用程序。

在 Google App Engine 中,用户可以使用 appspot.com 域上的免费域名为应用程序提供服务,也可以使用 Google 企业应用套件从自己的域为它提供服务。

可以免费使用 Google App Engine。注册一个免费账户即可开发和发布应用程序,而且不需要承担任何费用和责任。

Google App Engine的整体架构:

应用管理节点 :主要负责应用的启停和计费。

前端和静态文件 :负责将请求转发给应用服务器并进行负载均衡和静态文件的传输。

应用服务器 :能同时运行多个应用的运行时(Runtime)。

服务器群 :提供了一些服务,主要有Memcache、Images、URLfetch、E-mail和Data Store等。

(二)应用程序环境

应用程序环境的特性:

(1)动态网络服务功能。能够完全支持常用的网络技术。

(2)具有持久存储的空间。在这个空间里平台可以支持一些基本操作,如查询、分类和事务的操作。

(3)具有自主平衡网络和系统的负载、自动进行扩展的功能。

(4)可以对用户的身份进行验证,并且支持使用 Google 账户发送邮件。

(5)有一个功能完整的本地开发环境,可以在自身的计算机上模拟 Google App Engine 环境。

(6)支持在指定时间或定期触发事件的计划任务。

沙盒的限制:

(1)用户的应用程序只能通过 Google App Engine 提供的网址抓取 API 和电子邮件服务 API 来访问互联网中其他的计算机,其他计算机如请求与该应用程序相连接,只能在标准接口上通过 HTTP 或 HTTPS 进行。

(2)应用程序无法对 Google App Engine 的文件系统进行写入操作,只能读取应用程序代码上的文件,并且该应用程序必须使用 Google App Engine 的 Data Store 数据库来存储应用程序运行期间持续存在的数据。

(3)应用程序只有在响应网络请求时才运行,并且这个响应时间必须极短,在几秒之内必须完成。与此同时,请求处理的程序不能在自己的响应发送后产生子进程或执行代码。

(三)Google App Engine服务

目录
相关文章
|
26天前
|
存储 监控 关系型数据库
Google云计算原理与应用(三)
Google云计算原理与应用(三)
64 3
|
9天前
|
监控 搜索推荐 数据可视化
Google Analytics是如何帮助网站和应用所有者理解用户行为的?
【6月更文挑战第8天】Google Analytics是如何帮助网站和应用所有者理解用户行为的?
13 4
|
16天前
|
机器学习/深度学习 安全 网络安全
云端防御:云计算环境中的网络安全与信息保护策略深度学习在图像识别中的应用与挑战
【5月更文挑战第31天】 在数字化转型的浪潮中,云计算已成为企业及个人存储和处理数据的首选平台。然而,随着云服务的广泛采用,网络安全威胁也随之增加,使得信息安全成为亟待解决的挑战。本文聚焦于云计算环境特有的安全风险,探讨了多层次、多维度的防御策略,旨在为读者提供一套综合的云安全解决方案蓝图。通过分析当前云服务中的安全缺陷,并提出相应的防护措施,文章不仅强调了技术层面的对策,还涉及了管理与合规性方面的重要性。
|
18天前
|
存储 安全 网络安全
云端防御战线:云计算环境下的网络安全与信息保护策略未来交织:新兴技术趋势与跨界应用探索
【5月更文挑战第30天】 随着企业数字化转型的加速,云计算作为支撑现代业务架构的关键技术之一,其安全性已成为业界关注的热点。本文深入探讨了在动态且复杂的云环境中,如何通过多层次、多维度的安全措施确保数据的保密性、完整性与可用性。我们将从云服务模型出发,分析不同服务层次上的安全挑战,并结合最新的网络威胁情报,提出一系列创新的防御机制。这些机制包括基于行为分析的入侵检测系统、加密技术的最新进展以及人工智能在安全事件响应中的应用。文章旨在为云服务提供商和使用者提供一套综合性的网络安全解决方案,以增强云计算环境的整体安全性。
|
18天前
|
机器学习/深度学习 人工智能 运维
自动化运维在云计算环境中的应用与挑战
随着云计算技术的快速发展,自动化运维在云计算环境中扮演着越来越重要的角色。本文将探讨自动化运维在云计算环境中的应用现状和所面临的挑战,分析其对云计算技术发展和运维管理的影响,以及未来可能的发展方向。
|
20天前
|
机器学习/深度学习 存储 安全
构筑防线:云计算环境下的网络安全策略与实践深度理解变分自编码器:理论与应用
【5月更文挑战第27天】 随着企业和个人日益依赖云计算提供的便捷服务,云平台已成为数据存储、处理和交换的关键枢纽。然而,这种集中化的数据管理方式也带来了前所未有的安全挑战。本文将深入探讨在动态且复杂的云计算环境中,如何通过一系列创新策略和最佳实践来强化网络和信息安全。我们将分析当前云服务中的安全隐患,并提出相应的解决方案,以保障用户和企业的资产安全。 【5月更文挑战第27天】 在深度学习的丰富研究领域中,生成模型因其能够学习数据分布并生成新样本而备受关注。变分自编码器(Variational Autoencoders, VAEs)作为一类生成模型,不仅在无监督学习任务中表现出色,而且在半监督
|
4天前
|
存储 安全 网络安全
云计算与网络安全:技术融合的未来
【6月更文挑战第12天】本文探讨了云计算和网络安全的交叉点,分析了云服务、网络安全和信息安全等技术领域的发展趋势。文章强调了在云环境下保护数据和系统的重要性,并讨论了如何通过技术和策略来实现这一目标。
16 4
|
8天前
|
安全 网络安全 云计算
云计算与网络安全:技术挑战与解决方案
【6月更文挑战第8天】在信息技术飞速发展的今天,云计算作为一种新兴的计算模式,已经广泛应用于各个领域。然而,随着云计算的普及,网络安全问题也日益突出。本文将探讨云计算与网络安全之间的关系,分析云服务、网络安全和信息安全等技术领域的挑战,并提出相应的解决方案。
|
1天前
|
存储 安全 网络安全
云计算与网络安全:一场技术与安全的较量
【6月更文挑战第15天】随着云计算的普及,网络安全问题日益凸显。本文将探讨云计算与网络安全的关系,重点关注云服务、网络安全和信息安全等技术领域。我们将分析云计算面临的安全挑战,并提出相应的解决方案,以期在这场技术与安全的较量中取得胜利。
|
2天前
|
存储 安全 网络安全
云计算与网络安全:技术、挑战与未来
【6月更文挑战第14天】本文深入探讨了云计算与网络安全的交叉领域,包括云服务、网络安全和信息安全等技术领域。我们将分析云计算的基本概念、主要优势和潜在风险,同时探讨网络安全的关键技术和策略,以及信息安全的重要性。此外,我们还将讨论云计算与网络安全的未来趋势,以及如何在这个快速发展的领域中保持领先地位。

热门文章

最新文章