一杯西瓜汁er🍉
0%

发表于
本文字数： 191 阅读时长 ≈ 1 分钟

需要准备：

Linux系统 （本文使用的是Ubuntu 18.04）

一个拥有sudo权限的账号user

  1. 创建账号
1
sudo adduser zsx

同时会创建用户主目录/home/zsx/

  1. 为用户增加sudo权限
1
sudo vim /etc/sudoers

增加权限

1
2
3
# User privilege specification
root    ALL=(ALL:ALL) ALL
zsx ALL=(ALL:ALL) ALL

发表于
本文字数： 357 阅读时长 ≈ 1 分钟

写在前： 本小白使用的是Hexo和NexT主题搭建的博客 版本说明：hexo 5.4.0、hexo-theme-next 8.6.1

NexT初步

NexT安装

🔗 https://github.com/next-theme/hexo-theme-next

  • 提倡使用npm安装
1
2
cd hexo-site
npm install hexo-theme-next

NexT配置

🔗 https://theme-next.js.org/docs/getting-started/configuration

1
2
# 通过 npm 安装
cp node_modules/hexo-theme-next/_config.yml _config.next.yml

其他设置

中文设置

在站点配置文件中， 

1
2
3
# Site
author: Christy
language: zh-CN

发表于
本文字数： 281 阅读时长 ≈ 1 分钟

参考： https://blog.csdn.net/carfge/article/details/79691360

首先，进入本地仓库

  1. 将本地仓库与远程仓库建立链接
1
git remote add origin [email protected]:user/repo.git
  1. 远程分支拉取到本地
1
git fetch origin dev-op(远程分支名称)
  1. 在本地创建新分支dev并切换到该分支
1
git checkout -b dev-op(本地分支名称) origin/dev-op(远程分支名称)
  1. 把远程分支dev-op上的内容拉取到本地仓库
1
git pull origin dev-op(远程分支名称)

发表于
本文字数： 932 阅读时长 ≈ 1 分钟

记录专业实践过程中踩的坑

在订单表里添加记录的时候，显示报错如下：

1
2
3
4
5
6
7
8
cause: java.sql.SQLSyntaxErrorException: You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'order (order_no, `uid`, addr_id, 
      amount, `type`, freight, 
      `status`' at line 1
; bad SQL grammar []; nested exception is java.sql.SQLSyntaxErrorException: You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'order (order_no, `uid`, addr_id, 
      amount, `type`, freight, 
      `status`' at line 1v
...

经过排查，发现order是sql的保留字段（在排序的时候用到）；

由于订单表的名字也为order，再加上mapper是由mybatis自动生成的，所以这个冲突需要手动解决一下。

在OrderMapper.xml文件中，找到 

1
2
3
4
5
insert into order (order_no, `uid`, addr_id, 
     amount, `type`, freight, 
     `status`, payment_time, delivery_time, 
     finish_time, close_time, updated, 
     created)
将其中的order加上 `即可 即 
1
2
3
4
5
insert into `order` (order_no, `uid`, addr_id, 
     amount, `type`, freight, 
     `status`, payment_time, delivery_time, 
     finish_time, close_time, updated, 
     created)

发表于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

记录一次Anaconda+VSCode+PyTorch的配置

操作系统为macOS Catalina 10.15.7

更新：

由于需要GPU，在下载Anaconda和PyTorch中，也会附带说明了在windows10的操作。

其他地方都是按照MacOS来记录的。

下载Anaconda

先去官网或者清华镜像站下载Anaconda或者Miniconda

官网链接

https://www.anaconda.com/products/individual#Downloads

有win、mac、linux的版本选择，操作系统是什么就选择对应的就好啦~

例如 Windows10：

我直接在官网上下载的，也可以去清华镜像站找对应的版本。

注意：在安装过程中，有一步需要将“添加到PATH”勾选上！

一定要勾选上（尽管勾选之后说明文字会标红），不然后面配置稍有些麻烦。

通过镜像下载

如果在官网的下载速度较慢，可以去清华镜像站下载。下面以anaconda的安装为例。（安装miniconda也是同样操作） https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/ 找自己对应的操作系统，和需要的版本，进行下载。

例如 Mac OS： 我用到的是Anaconda3-2020.11-MacOSX-x86_64.pkg，https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/Anaconda3-2020.11-MacOSX-x86_64.pkg（点击即可下载）。也推荐下载miniconda。

macOS上安装没有什么需要注意的地方。下载好之后，双击进行安装，一直点“继续”，直到完成。

检测是否安装好

输入conda -V，查看版本号，出现conda版本号就是安装好了。

打开终端的有(base)字样

macOS里遇到的问题

新版的Anaconda会在每一个新开的terminal里面自动进入虚拟环境base。看着有些强迫症犯了。 使用如下命令就能把默认进入base虚拟环境关掉了。 

1
conda config --set auto_activate_base false

另外，如果需要进入base虚拟环境

1
conda activate

退出当前虚拟环境

1
conda deactivate

为PyTorch新建虚拟环境

  1. 新建虚拟环境，命名为pytorch，指定python版本为3.6。
1
conda create --name pytorch python=3.6
  1. 安装好之后，进入pytorch虚拟环境。
1
conda activate pytorch

安装PyTorch

在pytorch虚拟环境中安装PyTorch。要注意，先进入pytorch虚拟环境。 附上官网的链接：

https://pytorch.org

根据官网，安装PyTorch。

MacOS

1
conda install pytorch torchvision torchaudio -c pytorch

Win

要选择对应的cuda版本的，如果没有GPU就要选择None

1
conda install pytorch torchvision torchaudio cudatoolkit=11.0 -c pytorch

VSCode配置python

参考官方链接 https://code.visualstudio.com/docs/python/python-tutorial#_prerequisites

下载安装VSCode

官网下载，附上链接 https://code.visualstudio.com

下载python插件

在VSCode的应用商店中搜索Python，并下载 vscode下载python插件

下载Python解释器

这里的python解释器使用pytorch虚拟环境中的，见上文中“为PyTorch新建虚拟环境”。

验证python是否安装

python3 --version

由于我使用pytorch环境下的python，需要先进入该环境。

conda activate pytorch

验证python的安装

后来换了一台电脑下载的是miniconda，无所谓啦~

设置python解释器

使用快捷键shift + command + P ，或者点击菜单栏中的查看里的命令面板， 打开命令面板。 输入python:select interpreter 选择python解释器。这里选择我要用的pytorch里的python3.6.2就好了。 vscode设置python解释器

Note：代码补全要用IntelliCode，不要用Pylance（要卸掉）

VSCode代码自动补全

下载插件：Visual Studio IntelliCode 注意：VS Code会在右下角推荐Pylance，不要下载

在全局的setting.json中，找到以下有关editor.suggest设置为false的代码删掉

  "editor.acceptSuggestionOnCommitCharacter": false,
    "editor.suggest.showClasses": false,
    "editor.suggest.showConstructors": false,
    "editor.suggest.showEvents": false,
    "editor.suggest.showFields": false,
    "editor.suggest.showFunctions": false,
    "editor.suggest.showVariables": false,
    "editor.suggest.showValues": false,
    "editor.suggest.showUnits": false,
    "editor.suggest.showTypeParameters": false,
    "editor.suggest.showSnippets": false,
    "editor.suggest.showReferences": false,
    "editor.suggest.showOperators": false,
    "editor.suggest.showModules": false,
    "editor.suggest.showProperties": false,
    "editor.suggest.showIssues": false,
    "editor.suggest.showMethods": false,
    "editor.suggest.showIcons": false,
    "editor.suggest.showInterfaces": false,
    "editor.suggest.showFolders": false,
    "editor.suggest.showFiles": false,
    "editor.suggest.snippetsPreventQuickSuggestions": false,
    "editor.suggest.showWords": false,
    "editor.suggest.showKeywords": false,
    "editor.suggest.showEnums": false,
    "editor.suggest.showEnumMembers": false,
    "editor.suggest.showConstants": false,
    "editor.suggest.filterGraceful": false,
    "editor.suggest.showStructs": false,
    "editor.suggest.showUsers": false,

将下面这行的null改为true，即将

"editor.quickSuggestions": null,

改为

"editor.quickSuggestions": true,
如何打开全局的setting.json

点击 code => 首选项 => 设置，随便找一项设置，点击在setting.json中编辑，（再删掉新加的代码就好了），不知道有什么其他的好方法。

其他

当然啦，PyCharm也是很好的选择~也推荐~

用conda安装opencv

1
conda install opencv3 -c anaconda

c是channel的意思，要指定anaconda或者menpo做channel才行。

发表于
本文字数： 621 阅读时长 ≈ 1 分钟

记录专业实践使用SpringBoot后端开发遇到的问题

报错显示

1
2
3
4
5
6
7
8
9
10
11
Description:

A component required a bean of type 'com.cs.actionmall.mapper.UserMapper' that could not be found.


Action:

Consider defining a bean of type 'com.cs.actionmall.mapper.UserMapper' in your configuration.


Process finished with exit code 1

首先检查，@Mapper注解

1
2
3
4
@Mapper
public interface UserMapper {
  ...
}

考虑缺少依赖，发现pom.xml文件中没有写如下部分

1
2
3
4
5
<dependency>
            <groupId>org.mybatis.spring.boot</groupId>
            <artifactId>mybatis-spring-boot-starter</artifactId>
            <version>2.1.1</version>
</dependency>

用的是mybatis不是mybatisplus，要用mybatis的依赖而不是mybatisplus的依赖

发表于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

为专业课复习用

介绍

Amazon Web Service（AWS）

Amazon云的提出

IaaS：将硬件设备等基础资源封装成服务供用户使用

Amazon提供的服务主要包括

  • 弹性计算云EC2
  • 简单存储服务S3
  • 简单数据库服务Simple DB
  • 简单队列服务SQS
  • 弹性MapReduce服务
  • 内容推送服务CloudFront
  • 电子商务服务DevPay
  • 灵活支付服务FPS

🌿基础存储架构Dynamo

🌿Amazon平台基础存储架构：Dynamo

Amazon平台的架构是完全的分布式、去中心化

需求——Amazon平台中有很多服务对存储的需求只是读取、写入，（满足简单的键/值式存储）

🌿Dynamo

  • 简单的键/值方式存储数据，不支持复杂的查询
  • 存储的是数据值的原始形式（bit），不解析数据的具体内容、不识别任何数据结构，这使得它几乎可以处理所有的数据类型

🌿Dynamo需要解决的主要问题及解决方案

问题 采取的相关技术
数据均衡分布 改进的一致性哈希算法
数据备份 参数可调的quorum机制
数据冲突处理 向量时钟Vector Clock
成员资格及错误检测 基于Gossip协议的成员资格和错误检测
临时故障处理 Hinted handoff（数据回传机制）
永久故障处理 Merkle哈希树

Dynamo的存储节点

Dynamo中的存储节点呈无中心的环状分布。

Dynamo存储架构
Dynamo存储架构

两个基本概念

  1. preference list

    存储与某个特定键值相对应的数据的节点列表

  2. coordinator

    执行一次读或写操作的节点

通常，coordinator 是 preference list 上的第一个节点

Dynamo架构的主要技术

数据均衡分布的问题

Dynamo采用了分布式的数据存储架构，均衡的数据分布可以保证负载平衡和系统良好的扩展性。

因此，各个节点上数据的均衡性是影响Dynamo性能的关键问题。

取模分配方式：如果增加一台主机，会有大量的数据进行迁移

🌿🌿🌿一致性哈希算法

一致性哈希算法是目前主流的分布式哈希表（Distributed Hash Table，DHT）协议之一

一致性哈希算法除了能够保证哈希运算结果充分分散到整个环上外，还能保证在添加或删除设备节点时只会影响到其在哈希环中的前驱设备节点，而不会对其他设备节点产生影响。

dynamo一致性hash
dynamo一致性hash

一致性哈希算法可以大大降低在添加或删除节点时引起的节点间的数据传输开销

改进的一致性哈希算法

Dynamo中引入了虚拟节点的概念

每个虚拟节点都隶属于某一个实际的物理节点，一个物理节点根据其性能的差异被分为一个或多个虚拟节点。

各个虚拟节点的能力基本相当，并随机分布在哈希环上。

dynamo虚拟节点
dynamo虚拟节点

Dynamo将整个哈希环划分成Q等份，每个等份称为一个数据分区（Partition）

在存储数据时，每个数据会被先分配到某个数据分区，再根据负责该数据分区的虚拟节点，最终确定其所存储的物理节点。

dynamo数据分区
dynamo数据分区
数据分区的好处
  1. 减小数据分布不均衡的可能性
  2. 添加或删除设备节点时引起较小的数据传输
改进的一致性哈希算法的优势
  • 负载均衡
  • 屏蔽节点处理能力差异

数据备份

可以参照上面的数据分区的图来看

  • 在Dynamo中，每个数据的副本备份存储在哈希环顺时针方向上该数据所在虚拟节点的后继节点中。
  • 数据备份在存储数据的同时进行，会使每次写操作的延时变长。
  • Dynamo中对写操作进行了优化，保证一个副本必须写入硬盘，其他副本只要写入节点的内存即返回写成功。
  • 每个虚拟节点上实际存储了分配给它以及分配它的前N-1个前驱虚拟节点的数据。

参数可调的弱quorum机制

读写参数W、R、N

N：系统中每条记录的副本数

W：每次记录成功写操作需要写入的副本数

R：每次记录读请求最少需要读取的副本数。

满足R+W>N，用户即可自行配置R和W

数据冲突问题

分布式系统架构中通常考虑的三个因素

  1. 可靠性 Reliability
  2. 可用性 Availability
  3. 一致性 Consistency

Why数据冲突？

  • Dynamo选择通过牺牲一致性来保证系统的可靠性和可用性，没有采用强一致性模型而采用了最终一致性模型。
  • 由于Dynamo中可能出现同一个数据被多个节点同时更新的情况，且无法保证数据副本的更新顺序，这有可能会导致数据冲突。

How解决数据冲突？

采用向量时钟技术。

dynamo向量时钟技术
dynamo向量时钟技术

Dynamo中的向量时钟通过[node, counter] 对 来表示。

node表示操作节点 counter是其对应的计数器，初始值为 0节点每进行一次更新操作则计数器加 1

成员资格及错误检测

由于Dynamo采用了无中心的架构，每个成员节点都需要保存其他节点的路由信息。

为了保证每个节点都能拥有最新的成员节点信息，Dynamo中采用了一种类似于Gossip（闲聊）协议的技术

Dynamo中还通过Gossip来实现错误检测。任何节点向其他节点发起通信后，如果对方没有回应，则认为对方节点失效

为了避免新加入的节点之间不能及时发现其他节点的存在，Dynamo中设置了一些种子节点（Seed Node）。种子节点和所有的节点都有联系。当新节点加入时，它扮演一个中介的角色，使新加入节点之间互相感知。

成员资格及错误检测
成员资格及错误检测
  • 自底向上每一层代表一次随机通信
  • 第一层节点1将信息交换给节点2
  • 第二层节点1和2同时开始随机选择其他节点交换信息
  • 直到N个节点全部传遍

容错机制——临时故障处理机制

为了处理临时失效的节点，Dynamo中采用了一种带有监听的数据回传机制（Hinted Handoff） 当虚拟节点A失效后，会将数据临时存放在节点D的临时空间中，并在节点A重新可用后，由节点D将数据回传给节点A。

Dynamo临时故障处理机制
Dynamo临时故障处理机制

容错机制——永久性故障处理机制

Dynamo采用Merkle哈希树技术来加快检测和减少数据传输量

dynamo-merkle-tree
dynamo-merkle-tree

发表于
本文字数： 8.2k 阅读时长 ≈ 7 分钟

为专业课复习用

简介

GFS

  1. Google File System
  2. 支持海量存储

MapReduce

  1. 用于大规模数据集的并行运算。
  2. 主要功能：是提供了一个简单强大的接口，可以将计算自动的并发和分布执行。
  3. 从两方面提升了系统：
    • 失效的计算机问题。
    • MapReduce之间传输的数据都是经过压缩的，节省了带宽

BigTable

用来管理大规模结构化数据的分布式存储系统

Google文件系统GFS

系统架构

  • Google GFS是一个基于分布式集群的大型分布式文件系统，为MapReduce计算框架提供低层数据存储和数据可靠性支撑
  • GFS是一个构建在分布节点本地文件系统之上的一个逻辑文件系统，它将数据存储在物理上分布的每个节点上，但通过GFS将整个数据形成一个逻辑上整体的文件。
04Google云计算技术_pic1
04Google云计算技术_pic1

GFS的3个假设

  1. 硬件出错是正常而非异常
    • 大量廉价、易损的硬件
    • 必须保持文件系统整体的可靠性
  2. 主要负载是流数据读写
    • 主要用于程序处理批量数据，而非用户的交互或随机读写
    • 主要是追加写（插入写非常少）
  3. 需要存储大尺寸的文件
    • GB或TB量级

GFS的设计思想🌿🌿

  1. 将文件划分为若干块（Chunk）存储
    • 固定大小64M
  2. 通过冗余来提高可靠性
    • 3个数据块服务器上存储副本
  3. 通过单个master来协调数据访问、元数据存储
    • 结构简单，容易保持元数据一致性

系统架构

GFS系统架构
GFS系统架构

⚠️Client与Master之间只有控制信息，无数据信息，减少主服务器的负载。

系统节点分为三类角色🌿🌿🌿

Client 客户端

  • 提供给App的访问接口
  • 以库文件的形式提供

Master 主服务器

  • GFS的管理节点
  • 负责整个文件系统的管理
  • 🐰逻辑上只有一个

Chunk Server 数据块服务器

  • 负责具体的存储工作
  • 🐰创建冗余，避免服务器崩溃

GFS的实现机制

  1. 客户端首先访问Master节点，获取交互的Chunk Server信息，然后访问这些Chunk Server，完成数据存取工作。这种设计方法实现了控制流和数据流的分离。
  2. Client与Master之间只有控制流，而无数据流，极大地降低了Master的负载。
  3. Client与Chunk Server之间直接传输数据流🌿，同时由于文件被分成多个Chunk进行分布式存储，Client可以同时访问多个Chunk Server，从而使得整个系统的I/O高度并行，系统整体性能得到提高。

GFS的读操作/数据访问的过程 🌿

可以通过系统架构图来理解

  1. 在程序运行前，数据已经存储在GFS文件系统中；程序执行时，App告诉Master文件名或数据块索引是什么
  2. Master根据文件名或数据块索引在其文件目录空间中查找和定位该文件或数据块，并找到数据块在具体哪些Chunk Server上；将位置信息返回给App
  3. App根据返回的具体Chunk数据块位置信息，直接访问相应的CS
  4. App根据返回的具体Chunk数据块位置信息，直接读取指定位置的数据进行计算处理

GFS的特点🌿

  1. 采用中心服务器模式
    • 可以方便地增加Chunk Server
    • Master掌握系统内所有Chunk Server的情况，方便进行负载均衡
    • 不存在元数据的一致性问题
  2. 不缓存数据
    • 文件操作大部分是流式读写，不存在大量重复读写，使用Cache对性能提高不大
    • Chunk Server上数据存取使用本地文件系统
    • 从可行性看，Cache与实际数据的一致性维护也极其复杂
  3. 在用户态下实现
    • 用户态下有多种调试工具,利于开发
    • Master和Chunk Server都以进程方式运行，单个进程不影响整个操作系统
    • GFS和操作系统运行在不同的空间，两者耦合性降低

容错机制

Master容错🌿🌿🌿

三类元数据
  1. 命名空间，即整个文件系统的目录结构 --- 日志
  2. Chunk与文件名的映射表 --- 日志
  3. Chunk副本的位置信息
    • 一个Chunk默认有3个副本
    • 直接保存在各个Chunk Server上
Master故障

当Master发生故障时，在磁盘数据保存完好的情况下，可以迅速恢复以上元数据

为了防止Master彻底死机的情况，GFS还提供了Master远程的实时备份

Chunk Server容错

  1. GFS采用副本的方式实现Chunk Server的容错
  2. 每一个Chunk有多个存储副本（默认为三个）
  3. 对于每一个Chunk，必须将所有的副本全部写入成功，才视为成功写入
  4. 相关的副本出现丢失或不可恢复等情况，Master自动将该副本复制到其他Chunk Server

  5. GFS中的每一个文件被划分成多个Chunk，Chunk的默认大小是64MB

    系统管理技术

    • 大规模集群安装技术
      • GFS集群中通常有非常多的节点，需要相应的技术支撑
    • 故障检测技术
      • GFS构建在不可靠廉价计算机之上的文件系统，由于节点数目众多，故障发生十分频繁
    • 节点动态加入技术
      • 新的Chunk Server加入，只需裸机加入，大大减少GFS维护工作量
    • 节能技术
      • Google采用了多种机制降低服务器能耗，如采用蓄电池代替昂贵的UPS

分布式数据处理MapReduce

产生背景

  • Google拥有海量数据，并且需要快速处理。
  • 大数据分而治之
    • 任务划分
    • 结果合并

MapReduce

  • 一个软件架构，一种处理海量数据的并行编程模式。
  • 与传统的分布式程序设计相比，MapReduce封装了并行处理、容错处理、本地化计算、负载均衡等细节，还提供了一个简单而强大的接口。
  • MapReduce把对数据集的大规模操作，分发给一个主节点管理下的各分节点共同完成，通过这种方式实现任务的可靠执行与容错机制。

编程模型

Map函数

对一部分原始数据进行指定的操作。每个Map操作都针对不同的原始数据，因此Map与Map之间是互相独立的，这使得它们可以充分并行化。

Reduce操作

对每个Map所产生的一部分中间结果进行合并操作，每个Reduce所处理的Map中间结果是互不交叉的，所有Reduce产生的最终结果经过简单连接就形成了完整的结果集.

编程模型

两个主要的函数🌿🌿🌿

Map: (in_key, in_value) -> {(keyj, valuej) | j = 1…k}
Reduce: (key, [value1,…,valuem]) -> (key, final_value)
Map
  • 输入参数：in_key, in_value，指明了Map需要处理的原始数据
  • 输出结果：一组k-v对，中间结果
Reduce
  • 输入参数：key, [value1,…,valuem]
  • 工作：对这些对应相同key的value值进行归并处理
  • 输出结果：（key, final_value），所有Reduce的结果并在一起就是最终结果
04Google云计算技术_pic2
04Google云计算技术_pic2

实现机制

04Google云计算技术_pic3
04Google云计算技术_pic3

Google MapReduce并行处理的基本过程

  1. 有一个待处理的大数据，被划分为大小相同的数据块(如64MB),及与此相应的用户作业程序
  2. 系统中有一个负责调度的主节点(Master),以及数据Map和Reduce工作节点(Worker)
  3. 用户作业程序提交给主节点
  4. 主节点为作业程序寻找和配备可用的Map节点，并将程序传送给map节点
  5. 主节点也为作业程序寻找和配备可用的Reduce节点，并将程序传送给Reduce节点
  6. 主节点启动每个Map节点执行程序，每个map节点尽可能读取数据进行计算
  7. 每个Map节点处理读取的数据块,并做一些数据整理工作(combining, sorting等)并将中间结果存放在本地；同时通知主节点计算任务完成并告知中间结果数据存储位置
  8. 主节点等所有Map节点计算完成后，开始启动Reduce节点运行；Reduce节点从主节点所掌握的中间结果数据位置信息，远程读取这些数据
  9. Reduce节点计算结果汇总输出到一个结果文件即获得整个处理结果

容错机制🌿

MapReduce通过重新执行失效的地方来实现容错。

Master失效

Master会周期性地设置检查点（checkpoint），并导出Master的数据。一旦某个任务失效，系统就从最近的一个检查点恢复并重新执行。

由于只有一个Master在运行，如果Master失效了，则只能终止整个MapReduce程序的运行并重新开始。

Worker失效

Master会周期性地给Worker发送ping命令，如果没有Worker的应答，则Master认为Worker失效，终止对这个Worker的任务调度，把失效Worker的任务调度到其他Worker上重新执行。

案例分析

案例一----单词排序

怎样通过MapReduce完成排序工作，使其有序（字典序）呢？

步骤

  1. 对原始的数据进行分割（Split），得到N个不同的数据分块 。

  2. 对每一个数据分块都启动一个Map进行处理。

    采用桶排序的方法，每个Map中按照首字母将字符串分配到26个不同的桶中。

  3. 对于Map之后得到的中间结果，启动26个Reduce。

    按照首字母将Map中不同桶中的字符串集合放置到相应的Reduce中进行处理。

案例二----单词计数

给定一个巨大的文本（如1TB），如何计算单词出现的数目？

步骤

定义Map和Reduce函数

Map(K, V){    
    For each word w in V       
        Collect(w, 1);
}

Reduce(K, V[]){
    int count = 0;
    For each v in V
        count += v    
    Collect(K, count);
}
  1. 自动对文本进行分割
  2. 在分割之后的每一对<key,value>使用用户定义的Map进行处理，再生成新的<key,value>对
  3. 对输出的结果集归拢、排序(系统自动完成）
  4. 通过Reduce操作生成最后结果

分布式结构化数据表Bigtable

设计动机与目标

设计动机

  1. 需要存储的数据种类繁多
  2. 海量的服务请求
  3. 商用数据库无法满足需求

基本目标

  • 广泛的适用性 —— 为了满足一系列Google产品而并非特定产品的存储要求
  • 很强的可扩展性 —— 随时可以加入或撤销服务器
  • 高可用性 —— 确保几乎所有的情况下系统都可用
  • 简单性 —— 底层系统的简单性既可以减少系统出错的概率，也为上层应用的开发带来便利

数据模型

Bigtable数据的存储格式

Bigtable是一个分布式多维映射表，表中的数据通过一个行关键字（Row Key）、一个列关键字（Column Key）以及一个时间戳（Time Stamp）进行索引🌿🌿🌿🌿🌿

🐰Bigtable可以看成key-value的形式，其中的key是行关键字+列关键字+时间戳

Bigtable的存储逻辑可以表示为：

(row:string, column:string, time:int64)→string

04Google云计算技术_pic4
04Google云计算技术_pic4
  • 行(Row)
    • 大小不超过64KB的任意字符串。表中的数据都是根据行关键字进行排序的。
    • com.cnn.www就是一个行关键字，指明一行存储数据。URL地址倒排可以使同一地址域的网页将被存储在表中连续的位置,便于查找
    • 🐰倒排？ 域名层次划分
  • 子表(Tablet)
    • 一个大表可能太大，不利于存储管理，将在水平方向上被分为多个子表
04Google云计算技术_pic5
04Google云计算技术_pic5
  • 列(Column)
    • 特定含义的数据的集合。
    • BigTable将列关键字组织成为“列族”(column family),每个族中的数据属于同一类别,如anchor是一个列族，其下可有不同的表示一个个超链接的列关键字。
    • 一个列族下的数据会被压缩在一起存放。
    • 一个列关键字可表示为: 族名：限定词(family:qualifier)
    • content、anchor都是族名；而cnnsi.com和my.look.ca则是anchor族中的限定词。
  • 时间戳(time stamp)
    • 很多时候同一个URL的网页会不断更新，而Google需要保存不同时间的网页数据，因此需要使用时间戳来加以区分。
    • 🐰时间戳 int64，两种生成方式：
      • 系统默认（创建）
      • 用户定义（要求唯一）
    • 为了简化不同版本的数据管理，BigTable提供给了两种设置：
      • 保留最近的n个版本数据
      • 保留限定时间内的所有不同版本数据

小结——行、列、时间戳

行
  • Bigtable的行关键字可以是任意的字符串，但是大小不能够超过64KB
  • 表中数据都是根据行关键字进行排序的，排序使用的是词典序
  • 同一地址域的网页会被存储在表中的连续位置
列
  • 将其组织成所谓的列族（Column Family）
  • 族名必须有意义，限定词则可以任意选定
  • 组织的数据结构清晰明了，含义也很清楚
  • 族同时也是Bigtable中访问控制（Access Control）的基本单元
时间戳
  • Google的很多服务比如网页检索和用户的个性化设置等都需要保存不同时间的数据，这些不同的数据版本必须通过时间戳来区分。
  • Bigtable中的时间戳是64位整型数，具体的赋值方式可以用户自行定义
无数据校验
  • 每行都可存储任意数目的列
    • BigTable不对列的最少数目进行约束
  • 任意类型的数据均可存储
    • BigTable将所有数据均看作为字符串

  • 数据的有效性校验由构建于其上的应用系统完成

    🐰BigTable不进行数据的有效性校验

系统架构

Bigtable的基本架构

04Google云计算技术_pic6
04Google云计算技术_pic6

Bigtable中Chubby的主要作用🌿

  1. 选取并保证同一时间内只有一个主服务器（Master Server）。
  2. 获取子表的位置信息。
  3. 保存Bigtable的模式信息及访问控制列表。

子表服务器

SSTable格式的基本示意

**_SSTable_是Google为Bigtable设计的内部数据存储格式。**🌿🌿🌿🌿🌿

所有的SSTable文件都存储在GFS上，用户可以通过键来查询相应的值。

04Google云计算技术_pic7
04Google云计算技术_pic7
04Google云计算技术_pic8
04Google云计算技术_pic8

子表实际组成

  • 不同子表的SSTable可以共享

  • 每个子表服务器上仅保存一个日志文件

    🐰共享日志，每个子表服务器上的日志是共享日志的一个片段

  • Bigtable规定将日志的内容按照键值进行排序

  • 每个子表服务器上保存的子表数量可以从几十到上千不等，通常情况下是100个左右

04Google云计算技术_pic9
04Google云计算技术_pic9

子表地址组成

Bigtable系统的内部采用的是一种类似B+树的三层查询体系

04Google云计算技术_pic10
04Google云计算技术_pic10

🐰元数据表：

根子表（保存其他子表的位置） + 其他元数据子表（保存用户子表的位置信息）

Bigtable 数据存储及读/写操作

较新的数据存储在内存中一个称为内存表（Memtable）的有序缓冲里，

较早的数据则以SSTable格式保存在GFS中。

04Google云计算技术_pic11
04Google云计算技术_pic11

🐰内存表（SSTable的缓存），达到阈值后冻结，经过次压缩变成SSTable，Bigtable再创建一个新的内存表

三种形式压缩之间的关系

04Google云计算技术_pic12
04Google云计算技术_pic12

🐰

内存表的空间有限，达到阈值后 ---- 次压缩

合并压缩 --- 定期进行

主压缩 --- 定期进行

主压缩成一个SSTable后，前面被压缩的都会被删除

性能优化

局部性群组(Locality Group)

Bigtable允许用户将原本并不存储在一起的数据以列族为单位，根据需要组织在一个单独的SSTable中，以构成一个局部性群组。

04Google云计算技术_pic13
04Google云计算技术_pic13

用户可以只看自己感兴趣的内容。 对于一些较小的且会被经常读取的局部性群组，明显地改善读取效率。

压缩

压缩可以有效地节省空间，Bigtable中的压缩被应用于很多场合。

压缩可以被用在构成局部性群组的SSTable中，可以选择是否对个人的局部性群组的SSTable进行压缩。

两步压缩

  1. 利用Bentley & McIlroy方式（BMDiff）在大的扫描窗口将常见的长串进行压缩
  2. 采取Zippy技术进行快速压缩，它在一个16KB大小的扫描窗口内寻找重复数据，这个过程非常快

压缩的本质：寻找重复数据，用少的字节代替

布隆过滤器

一个很长的二进制向量和一系列随机映射函数

优点
  • 布隆过滤器的速度快，省空间
  • 不会将一个存在的子表判定为不存在
缺点
  • 在某些情况下它会将不存在的子表判断为存在

小结

Google的云计算应用均依赖于四个基础组件

  • 分布式文件存储，GFS
  • 并行数据处理模型MapReduce
  • 分布式锁Chubby
  • 结构化数据表BigTable
04Google云计算技术_pic14
04Google云计算技术_pic14

Chubby的作用

  • 为GFS提供锁服务，选择Master节点；记录Master的相关描述信息
  • 通过独占锁记录Chunk Server的活跃情况
  • 为BigTable提供锁服务，记录子表元信息（如子表文件信息、子表分配信息、子表服务器信息）

GFS的作用

  • 存储BigTable的子表文件

    子表：SSTable和日志文件

  • 为第三方应用提供大尺寸文件存储功能
  • 文件读操作流程
    • API与Master通信，获取文件元信息
    • 根据指定的读取位置和读取长度，API发起并发操作，分别从若干ChunkServer上读取数据
    • API组装所得数据，返回结果

BigTable的作用

  • 为Google云计算应用（或第三方应用）提供数据结构化存储功能

    结构化 --- 字符串的形式存储

  • 类似于数据库

    没有事务处理的能力

  • 为应用提供简单数据查询功能（不支持联合查询）

  • 为MapReduce提供数据源或数据结果存储

MapReduce的作用

  • 对BigTable中的数据进行并行计算处理（如统计、归类等）
  • 使用BigTable或GFS存储计算结果

应用场景分析

应用场景分析1—— Google网站流量分析

基本功能

  • 统计网站的基本数据，包括会话、综合浏览量、点击量和字节流量等等
  • 分析网站页面关注度，帮助企业调整或增删页面
  • 分析用户浏览路径，优化页面布局
  • 分析用户访问来源链接，提高广告投资回报

应用的特征

海量数据 --- 需要存储海量的用户行为数据（如点击时间、位置等） 海量用户 --- 需要为任意多的网站提供流量分析

技术路线

使用BigTable存储和检索数据，使用MapReduce统计数据

BigTable中的表设计

原始点击数据表

行键：点击时间

列键：网站URL、网站名称、用户IP地址、来源URL、目标URL…… 目前尺寸约200TB

04Google云计算技术_pic15
04Google云计算技术_pic15

统计数据表

行键：网站URL（倒排）

列键：点击次数（如记录最近一个月每日的访问次数等）、页面关注度（如记录网站页面的访问比率）、来源网站（如记录TOP10）、目标网站（如记录TOP10）…

每个列中记录的内容是字符串，Analytics在查询后需要解析字符串获得统计结果

可根据统计内容的增多来增加新的列

目前尺寸约20TB

业务流程分析

04Google云计算技术_pic16
04Google云计算技术_pic16

数据采集

  • 数据来源
    • 页面内嵌脚本
    • 点击行为脚本
  • 应用服务器获取到数据后，存入BigTable

  • 数据存储流程

    04Google云计算技术_pic17
    04Google云计算技术_pic17

数据处理

  • 例如，统计网站(如xxx.com)过去一周网页访问比例

  • 数据处理流程

    04Google云计算技术_pic18

  • Map操作

    假设过去一周查询结果文件在GFS中包含M个Chunk，那么Master寻找M个空闲的Worker，分别处理这M个Chunk，得到每个网站中页面的访问次数

  • 自动排序

    对M个中间结果进行排序

  • Reduce操作

    假设含N个网站，那么可以分配N台Worker分别处理单个网站的数据
  • 写入数据

  • 应用程序将分析结果写入统计数据表

数据查询

从数据统计表中查询xxx.com行 获取对应列的数据，解析，得到并展示最终结果

应用场景分析2——Google搜索

Google搜索的总体业务流程

  1. 数据采集: Spider
  2. 数据整理
    • 生成各类子表，如音乐表、生活搜索表、学术搜索表等
    • 压缩数据表，清洗失效数据
  3. 数据检索

数据采集

  • 通过若干Spider在网络上搜集数据
  • 使用BigTable存储数据 行键：倒排的URL 列键：网站名称、语言、HTML描述、图片、链接…… 时间戳：记录不同时刻的网页快照

数据整理（Google学术搜索）

  • 数据抽取
    • 寻找包含学术（论文）信息的网页数据，并结构化存储
    • 学术（论文）信息抽取（分析参考文献、摘要等）
    • 可能的技术方案：MapReduce+BigTable
  • 数据统计
    • 基于抽取的数据进行统计分析（如分析被引用次数等）
    • 可能的技术方案MapReduce+BigTable
  • 学术信息BigTable 行键：论文标题 列键：作者、主题词、摘要、参考文献、期刊信息、被引用次数、下载链接……

  • 如何获取论文统计数据（如论文引用次数）

    步骤
    • 分析论文信息表，MapReduce
    • 归纳排序
    • Reduce操作

发表于
本文字数： 325 阅读时长 ≈ 1 分钟

为专业课复习用

信息科技为大数据时代提供技术支撑

  1. 存储设备容量不断增加
  2. CPU处理能力大幅提升
  3. 网络带宽不断增加

定义

海量数据或巨量数据，其规模巨大到无法通过目前主流的计算机系统在合理时间内获取、存储、管理、处理并提炼以帮助使用者决策。

特点4V

  1. 价值密度低（Value）
  2. 数据量大（Volume）
  3. 快速（Velocity）
  4. 多样（Variety）

大数据的影响

图灵奖获得者、著名数据库专家Jim Gray博士观察并总结人类自古以来，在科学研究上，先后历经了实验、理论、计算和数据四种范式

在思维方式方面，大数据完全颠覆了传统的思维方式：

  • 全样而非抽样

  • 效率而非精确

  • 相关而非因果

大数据的关键技术

两大核心技术

  1. 分布式存储
    • GFS/HDFS、BigTable等
  2. 分布式处理
    • MapReduce

发表于
本文字数： 930 阅读时长 ≈ 1 分钟

为专业课复习用

🌿云计算概念

Wikipedia上对云计算的定义

云计算是一种能够将动态伸缩的虚拟化资源通过互联网以服务的方式提供给用户的计算模式，用户不需要知道如何管理那些支持云计算的基础设施。

国外云计算的先行者

Amazon、Google、Microsoft

🌿Google发表学术论文的形式公开其云计算三大法宝：GFS、MapReduce和Bigtable。

🌿云计算的分类

按服务类型分

  1. SaaS
    • Software as a Service
    • 将软件作为服务

    • 针对性更强，它将某些特定应用软件功能封装成服务

      🌰Gmail
  2. PaaS
    • Platform as a Service
    • 将平台作为服务

    • 对资源的抽象层次更进一步，提供用户应用程序运行环境

      🌰Google App Engine 、Microsoft Windows Azure
  3. IaaS
    • Infrastructure as a Service
    • 将基础设施作为服务

    • 将硬件设备等基础资源封装成服务供用户使用

      🌰 Amazon EC2/S3

从SaaS到PaaS到IaaS，依次：专用性减弱、通用性增强

假设系统的实现如下图：

基础设施是指包括服务器、网络、数据中心

平台是指包括支撑软件及以下的

软件是指全部的部分

按服务方式分

  1. 共有云
  2. 混合云
  3. 私有云

🌿云计算的特征

  • 硬件和软件都是资源
  • 资源可以根据需要进行动态扩展和配置
  • 资源物理上分布式共享，逻辑上单一整体呈现
  • 用户使用资源按量付费、无需管理

🌿云计算的优势

  1. 优化产业布局
  2. 推进专业分工
  3. 提升资源利用力
  4. 减少初期投资
  5. 降低管理开销

云计算与其他类型的计算

  • 云计算与并行计算
    • 并行计算：一群同构处理单元的集合，这些处理单元通过通信和协作来更快地解决大规模计算问题
  • 云计算与网格计算
    • 网格计算：将分散在网络中的空闲服务器、存储系统和网络连接起来，形成一个整合系统，为用户提供功能强大的计算及存储能力来处理特定的任务
  • 云计算与效用计算
    • 效用计算：IT资源能够根据用户的要求按需提供，并根据使用情况付费

云计算的产生动力

  1. 宽带的发展为云计算提供了硬件基础
  2. 互联网用户的新需求为云计算提供了服务基础
    • 接入能力：可以从任何地点、任何设备接入服务和数据
    • 共享能力：数据的建立和存储共享 容易方便
    • 自由：不希望受数据的影响
    • 简单：容易学会, 容易使用
    • 安全：相信数据不会丢失或不会被不允许的人看到