WizardLQ’s | 魔法师の小茶馆

Keep moving, never give up. | 锲而不舍,金石可镂.

R介绍

前言

书籍这里使用的是Robert IKabacoff著王小宁,刘撷芯等译的的《R语言实践(第二版)》。

编程环境使用的Rstudio, R的版本是R3.5.1。

教程:swirl

它太神奇了,满载珍宝,可以让那些狡猾聪明和粗野胆大的人得以充分满足;但并不适合胆小者。

——Q. “Q Who”, 《星际迷航》

Lesson 1: Basic Building Blocks

  • 赋值<-
  • 打印print()
  • 帮助
    • ?
  • 变量:接在赋值符号的左边
  • 数组c()
    • c()中参数可以依然是向量
    • 对向量可以直接进行看起来像对标量进行的数值运算,例如:+, -, /, ^sqrt(), abs()等, 运算结果是逐元素的,类似于Numpy中的广播。
  • 向量运算
    • 两个向量进行运算,若二者长度是相等的,则R会对向量进行著逐个元素计算(element-by-element)
    • 若连个向量长度不等,则会使用短的向量来填充,直到二者长度相等后,两者再进行和相等长度向量相同的运算
    • 向量和标量的运算,将标量视作长度是一的向量,然后将其循环填充至与向量长度相等的向量,再进行运算

  • 补全:tap
  • 历史输入:
  • 关于swirl assignment token
    • 去Coursera上选修约翰霍普金斯大学的R学习课程
    • 第一周的作业是关于swirl提交的,网页右边栏会有提交码
    • 在swirl完成的时候输入提交码,作业就提交成功

Lesson 2: Workspace and Files

  • 获取当前工作区路径:getwd()

    • 返回原来的工作路径:getwd(old.dir)
  • 查看当前工作区下有哪些对象:`ls()(和Linux命令类似)
  • 产看有哪些文件:

    • list.files()
    • 查看帮助:?list.files()
  • 查看函数的参数有哪些:例如args(name = list.files )

  • 保存旧路径:old.dir <- getwd()
  • 创建新路径:dir.creat()
  • 设置(新的)工作路径:setwd(), 例如setwd("testdir")
  • 创建新文件:file.create(),例如file.create("mytest.R")
  • 查看当前工作路径文件:list.files()
  • 产看当前工作路径某文件是否存在:file.exists(), 例如file.exists("mytest.R")
  • 查看文件信息:file.info(), 例如file.info("mytest.R")
  • 重命名文件:file.rename(from, to), 例如file.rename("oldname.R", "newname.R"),将原来叫做oldname.R的文件重命名为newname.R
  • 删除文件:file.remove()
  • 复制文件:file.copy(from, to), 例如file.copy("mytest2.R", "mytest3.R"), 将文件mytest2.R复制成为mytest3.R
  • 相对路径:
    • 查看文件的相对路径:file.path(),例如file.path("mytest.R")
    • 配合dir.create()创建想对路径的多层文件夹
  • 创建路径:dir.crate(),举例dir.create(file.path("testdir2", "testdir3"), recursive = TRUE), 在当前工作路径下以递归方式创建文件路径testdir2/testdir3

Lesson 3: Sequences of Numbers

  • :
    • 例如1:10, 输出的是1 2 3 4 5 6 7 8 9 10, 即步长为1的[1,10]升序的闭区间的数
    • 例如pi:10,输出的是3.141593 4.141593 5.141593 6.141593 7.141593 8.141593 9.141593, 从pi开始每次步长为1,直到小于10的那个点的序列
    • 例如10:1, 输出的是10 9 8 7 6 5 4 3 2 1, 即步长为1,[10, 1]倒序的闭区间的数
  • 获取关于符号的帮助文档
    • ?`:` ,将符号阔在` 对中,前面加上问号
  • seq()创建序列
    • 例如seq(1, 20),输出的是1 2 3 4 5 6 7 8 9 10, 和:作用类似,步长为1。
    • 例如seq(0, 10, by=0.5), 输出的是0.0 0.5 1.0 ... 9.5 10.0, 步长0.5的序列
    • 例如seq(5, 10, length=30),输出的是5.000000 5.172414 ... 9.827586 10.000000共30个数的序列
  • 查看序列长度length()
  • 创建和某个已知序列等长的序列
    • 例如1:length(my_seq), 将符号:length()合用
    • 使用along.with参数,例如seq(along.with=my_seq)
    • 使用内置函数seq_along(), 例如seq_along(my_seq)
  • rep()
    • replicate: 重复
    • 创建全零(n)序列, 例如rep(0, times=30)
    • 创建重复的向量组成的序列,例如rep(c(1, 2, 3), times=10)
    • 创建向量逐元素重复一定次数的序列,例如rep(c(1, 2, 3), each=10)

Lesson 4: Vectors

  • 关于向量
    • 是R中最简单也是最常见的数据结构
    • 向量包含两种类型,一种是原子的(atomic)向量,其中只包含单一一种数据类型;另一种是列表(list)形式, 其中可以包含两种及以上种数据类型, 类型包括布尔型的TRUE, FALSE以及NA(not available)
    • 例如num_vect <- c(0.5, 55, -10, 6)
  • 向量中元素和标量比较

    • 例如tf <- num_vect<1, 将比较num_vect中每个元素和1的大小,返回的是一个布尔型向量,TRUE FALSE TRUE FALSE
  • 逻辑运算
    • &
    • |
    • !
  • 字符串向量
    • 字符串使用双引号括起来, 例如my_char <- c("My", "name", "is")
    • 将字符串数组合成长字符串,paste(), 例如paste(my_char, collapse=" "), 得到结果"My name is"
    • 字符串连接,例如c(my_char, "Leo"),得到向量"My" "name" "is" "Leo"
  • paste()

    • 连接两个字符串为一个长字符串,例如paste("Hello", "world!", sep=" "), 得到"Hello world!"

    • 连接两个等长的向量,例如paste(1:3, c("X", "Y", "Z"), sep=""),得到"1X" "2Y" "3Z"

    • 配合内置字母向量使用,例如paste(LETTERS, 1:4, sep="-"), 得到"A-1" "B-2" "C-3" "D-4" "E-1" ... "Y-1" "Z-2"。 其中LETTERS是预定义数组,表示英文的26个字母。这里的1:4向量数据类型被强制转换成字符串类型。

Lesson 5: Missing Values

  • 关于缺失值
    • 统计学中缺失值有重要的意义
    • 不能🙅‍无视缺失值的存在,而是要研究缺失值背后潜在的模式或者导致值缺失的原因
    • R中使用NA表示缺失值,代表not available或者称为missing
  • 创建含有缺失值的向量
    • 例如c(44, NA, 5, NA)
    • NA运算依然是NA
  • 从标准正态分布随机抽样n个样本
    • rnorm(1000)
  • 创建含1000个缺失值的序列
    • rep(NA, 1000)
  • 数据抽样sample()
    • 例如my_data <- sample(c(rnorm(1000), rep(NA, 1000)), 100), 表示从长度为2000的序列中随机抽样100个值
  • 获取缺失值位置
    • is.na(), 例如is.na(my_data), 返回一个大小为输入数据的布尔型数组,对应位置的TRUE和FALSE分别代表是否是缺失值
  • 统计缺失项
    • sum(), 例如sum(is.na(my_data))
  • NaN
    • 代表not a number
    • 使用0/0, Inf/Inf, Inf-Inf可以生成

Lesson 6: Subsetting Vectors

  • 正整数索引

    • R中的索引是从1开始的
    • 使用方括号中加数字,可以访问数字索引位置的向量元素,例如x[1:10]表示向量x位置1到10上的元素
  • 索引是逻辑值(布尔值)

    • 例如x[is.na(x)], 得到全NA数组,个数是x种NA的个数。(is.na(x)返回时布尔型数组,大小和x相同,在相应位置是TRUE或者是FALSE)
    • 筛选数组中非NA的数,x[!is.na(x)]
    • 筛选数组中大于0的数, y[y>0]; 注意,若数组中有NA,则该语句返回也会包含NA,在于NA属于占位符, NA>0,得到的同样是NA。
    • 若要从包含NA的数组中筛选出大于零的元素,使用x[x>0&!is.na(x)]
  • 传入向量作为索引

    • 例如x[c(3, 5, 7)]
  • 越界访问

    • 访问x[0], 不报错返回numeric(0)
    • 访问越界的索引,例如x[Inf],不报错,返回NA
  • 负整数索引

    • x[c(-2, -10)],表示访问除了索引为2和10位置上的数之外的全部元素
  • 带有命名元素的数字向量

    • 创建含有命名元素的数字向量

    • 创建匿名的数字向量后使用names()赋予名称

    • 判断两个带名称的向量是否相等

      • 例如使用identical(x=vect, y=vect2), 判断vect和vect2是否相等
    • 通过名称索引

      • 例如vect["bar"], vect[c("bar", "foo")]

Lesson 7: Matrices and Data Frames

关于矩阵和数据帧

  • 都是矩形的数据类型,来存储表格状的(tabular)数据
  • 都有行和列
  • matrix只包含一种单一的数据类型,而data frame可以包含不同种的数据类型

查询维度

  • dim()
  • vector没有dim属性,dim(my_vector)返回值是NULL

向量变矩阵

  • 例如dim(my_vector) <- c(n, m),若my_vector是$n \times m$长度的vector,这样相当于将my_vector进行如Numpy中的reshape,转换为n, m的矩阵
  • class(),查询数据类型,例如class(dim(my_vector)<-c(n, m)), 得到的是matrix类型

创建矩阵

  • matirx()来创建矩阵
  • matrix(data = NA, nrow = 1, ncol = 1, byrow = FALSE, dimnames = NULL)

判断两个矩阵是否相等

  • 例如identical(my_matrix1, my_matrix2)

通过行和列来结合R对象

  • cbind()
  • rbind()
  • 字符串类型和数字类型结合会发生将数字隐式强制转换(implicit coercion, 也就是没有显式声明后台自动完成的)成为字符串的现象
  • 有多种数据类型要结合,应使用dataframe

创建data-frame

  • 通过data.frame()创建data-frame

定义data-frame列名称

  • colnames()
  • 类似于向量转矩阵中的dim()的用法,例如colnames(my_data) <- cnames

Lesson 8: Logic

关于逻辑

  • R中有两种逻辑值,也叫做布尔值(Boolean values),即真(TRUE)和假(FALSE)

可参与逻辑运算的算术运算符

  • ==
  • >, >=
  • <, <=
  • !=, !(==)

逻辑运算符

  • 合取(与), &, &&

  • 析取(或), |, ||

  • 不仅可以对一个数或者表达式进行运算,也可以就多个数或者向量进行运算

  • &&&的区别

  • |&&却别类似,单个布尔值和向量运算,前者是逐元素进行与运算,后者只和向量的第一个元素运算

  • 符号优先级,与运算的符号优先级高于或运算符号优先级

  • 逻辑表达式可以通过组合,加括号等形式来组合

逻辑函数

  • 判断是否为真,isTRUE()
  • 判断是否相等identical()
  • 异或,xor()
  • which()
    • 返回向量中值为TRUE位置索引
    • 随机采样函数sample()
    • 例如ints <- sample(10), 返回1~10之间的10个无重复的整数
    • 例如which(ints > 7),返回ints中大于7的索引
  • any()
    • 判断是否至少有一个元素符合条件
    • 例如any(ints < 0), 返回一个布尔值,若任何一个元素小于零则返回TRUE,否则返回FALSE
  • all()
    • 判断是否所有元素都符合某周条件
    • 例如all(ints > 0),只有当所有元素均满足大于零的条件,才返回TRUE, 否则返回FALSE

Lesson 9: Functions

To understand computations in R, two slogans are helpful:

  1. Everything that exists is an object.
  2. Everything that happens is a function call.

@John Chambers, the creator of R

函数形式

1
2
3
4
function_name <- function(arg1, arg2){
# Manipulate arguments in some way
# Return a value, 不需要显式地使用return 来声明。R会自动返回函数中最后一行的值
}

第一个函数:

1
2
3
4
boring_function <- function(x) {
# 原样返回函数
x
}

调用函数

1
boring_function("My first function!")

结果:

1
"My first function!"

查看函数源代码

直接输入函数名称,不带括号,即可查看函数的源程序以及字节码。

Lesson 10: lapply and sapply

*apply家族

  • *apply函数将数据SPLIT UP(劈)成一系列小的数据

  • 然后对这些数据片段进行APPLY, 紧接着使用COMBINE,来整合成结果

  • 更多策略请看文章《’The Split-Apply-Combine Strategy for Data Analysis’》

数据集操作

lapply

  • 接收一个list作为输入
  • 对于list中的每个元素apply一个函数
  • 返回和原始list等长的list
  • 举例:cls_list<-list(flags, class), 表示对flags数据集(data-frame)中的每一列使用class函数处理。最后得到一个具有和数据集列数相同长度的list。使用as.character(cls_list)可以将cls_lis转换成字符串类型的数组

sapply

  • sapply()在内部自动调用lapply(),并对结果进行简化(这就是s的意义,即simplify,简化)
  • 举例:使用cls_vect<- list(flags, class)得到和之前相同的结果
  • 举例,df[, 11:17],获取df的第11列到17列的全部记录
  • 举例,使用sapply(flag_colors, mean),对datafram的每一列求均值。
  • 举例:shape_mat <- sapply(flag_shapes, range)
  • unique(),查看非重复的值有几种
  • sapply也有无法简化的时候,即当使用lapply产生的list都是不等长的,那么这时候使用sapply产生的结果和lapply()一样。

*apply更多使用

  • 使用匿名函数进行apply, 例如lapply(unique_vals, function(elem) elem[2]), 会返回unique_vals中第二列。

Lesson 11: vapply and tapply

vapply

  • vapply可以指定格式,若返回值不符合格式要求,抛出异常
  • 例如,vapply(flags, unique, numeric(1)), 指定结果是长度1的向量,由于结果并非如此,所以会抛出异常;而使用sapply(flags, class, numeric(1)), 由于结果符合格式,所以正常返回
  • vapply()sapply(), 由于检查格式 是否正确,因此更加安全。此外还更快一些,特别是用来处理较大的数据集。

tapply

  • 作用:将数据根据某变量的值来划分成不同的组,然后对每个组的成员应用某个函数。

Lesson 12: Looking at Data

示例数据集:Agriculture’s PLANTS Database
| (http://plants.usda.gov/adv_search.html).

查看数据集的类型:class(data_name)

(加入是数据框的类型)查看数据的行还有列数是多少。dim(data_name)

分别查看行数还有列数:nrow(), ncol()

查看数据集的大小:object.size(), 返回数据集的大小,字节为单位。

查看列名称,names(),返回数据集的列名称

当数据集过长过大时,一次无法查看完所有数据,使用head(),从自己制定的头几行来查看,默认是显示头6行。使用head(x = dat, n = 10),表示查看前10行。

查看数据的后几行,tail(x = dat, n = 10)

使用summary可以粗略地查看数据集中各个列的信息,例如最小值,最大值,平均值,3/4点。要特别注意factor类型,注意和数字类型区分。

当要查看数据集中某一列的summary时,使用table(dat$col), 返回的是列的统计值。

str()则可以显示很多简略信息,特别是了解数据集/函数等的结构。

Lesson 13: Simulation

使用随机数进行仿真在统计中很重要。

sample()

Random Samples and Permutations

Description

sample takes a sample of the specified size from the elements of x using either with or without replacement.

Usage

sample(x, size, replace = FALSE, prob = NULL)

sample.int(n, size = n, replace = FALSE, prob = NULL,
​ useHash = (!replace && is.null(prob) && size <= n/2 && n > 1e7))

模拟四个六面的🎲, sample(1:6, 4, replacement = TRUE),其中replacement为TRUE,表示可以有放回的,即每次采样之后 将采样的数放回到远原来的集合中,接着进行重新采样。

sample(1:20, 10), 表示生成有放回抽样10个范围为[1, 20]的数。

LETTERS时内置的26个英文字母,sample(LETTERS),对字母进行混洗。

现在模拟概率不均匀的抽样,比如模拟投一枚不均匀的硬币,硬币正面的概率为0.7, flips <- sample(c(0, 1), 100, replace = TRUE, prob = c(0.3, 0.7)), 通过sum(flips)查看结果在70左右。

每次投硬币都属于只有两项的独立重复试验,对于这种情况,可以使用rbinom()(binomial distribution)。

R中,r***函数,表示randomd***,表示density,密度。p***probability,概率。q***,表示 quantile,分位数,分位点。

flips2 <- rbinom(100, 1, 0.7), 等价之前的模拟。

正态分布,标准正态分布,rnorm(10),表示从标准正太分布,即平均值为0, 标准差为1的正态分布中随机采样10个点。

rnorm(10, mean = 100, sd = 25), 表示从平均值为100, 标准差为25的正态分布中抽样10个点。

从平均值为10的泊松分布中抽样5个点,rpois(5, lambda = 10)

my_pois <- replicate(100, rpois((5, 10))), 创建一个矩阵,矩阵的每列包含5个随机生成的点,点服从平均值为5的泊松分布。

cm <- colMeans(my_pois)用来计算上述矩阵每一列的均值。

hist(cm),显示cm的直方图。

更多随机分布:

指数exponential分布: rexp()

卡方chi-squared分布:rchisq()

伽马gamma分布:rgamma()

Lesson 14: Dates and Times

Lesson 15: Basic Graphics

FAQ

Warning in system(“sh ./configure.win”) : ‘sh’ not found ERROR: configuration failed for package ‘stringi’

Windows下安装swirl(一个统计学习,R学习等教程学习的R包,访问),发现一个依赖的包stringi一直装不上去,后来查明是stringi的包版本过低,和最新版的R以及Rsutdio不匹配所致,所以去https://cran.r-project.org/web/packages/stringi/index.html,选择下载合适的新版本的stringi包(我下载的是windows,r-release: stringi_1.1.7,适合R3.5使用Windows版),并解压到R\R-3.5.1\library下。

在markdown中如何在短引用着重号(backtick)中输入着重号,例如输入 ?`:`

总的来说在就是单着重号对, 引用其他的。双着重号对,引用单着重号对引用的东西,本身靠三着重号对引用。对引用双着重号引用的东西,本身靠连着的四引用号引用。以此类推:

英文里常见的赞叹/夸人表述有哪些

  • You are really on a roll!:你真走运
  • You nailed it!
  • Good job!
  • You are quite good my friend!
  • You are amazing!
  • You are the best!
  • Your dedication is inspiring!
  • Your dedication is inspiring!

最后更新时间:2018年10月23日

补充

创建全零向量

来源: https://stackoverflow.com/questions/33119406/how-to-declare-a-vector-of-zeros-in-r

  • integer(1000)
  • numeric(1000)
  • rep(100)
  • rep(0L, 3)
  • seq(0, 0, length.out=3)
  • as.vector(matrix(0,nrow=3))

创建全零矩阵

1
2
> matrix(0, n, m)
>

结合字符串和数字

使用paste()

例如:

1
2
> for (i in 1:10) print(paste("hello", i))
>

>

R中使用dict?

  • 最直接,install.packages("hash")。更多查看:这篇
    • 接着使用library(hash)
    • 创建hash对象,h <- hash()
    • 创建时添加属性,h <- hash(keys=c("2", "4", "6"), values=(0, 0, 0))

整数类型

x <- 10, 然后class(x),会发现R将数字存储为numeric即数字类型。

若要强调数字是整数,则在赋值的时候在后面加上大小的L。例如,x <- 10L

对数据框进行排序

https://stackoverflow.com/questions/1296646/how-to-sort-a-dataframe-by-multiple-columns

对数据框行进行求平均

https://stackoverflow.com/questions/10945703/calculate-row-means-on-subset-of-columns

生成factor水平

?gl

对字符串进行拆分

split

求方差、标准差

var(), 求的是样本的方差,即自由度是样本的个数n-1。

sd(), 样本标准差。

字符串切分

strsplit()

unlist(),将切分后的结果展开

关于安装R-studio server版时报错

1
2
> error while loading shared libraries: libssl.so.1.0.2: cannot open shared object file: No such file or directory
>

解决方法,sudo apt-get install libssl-dev

之后在按照官网上的指示,重新安装。

保存文件

write.table {utils}

多元线性回归

回顾

一元线性回归

多元线性回归

多元线性回归的假设

n>p, 样本个数要大于自变量的个数

多元线性回归参数的最小二乘估计

分情况讨论:

  • x逆矩阵是否存在:直接带入$\hat\beta=(X^TX)^{-1}X^Ty$,$\hat y=X(X^TX)X^Ty;\hat y=Hy$,H矩阵具有等幂性。

  • 逆矩阵不存在:偏最小二乘估计

  • 奇异矩阵

$\beta$服从正态分布

标准化偏回归系数

不能直接由偏回归系数大小对于因变量线性影响的大小,需要计算标准化偏回归系数,即标准化偏回归系数。

推导过程

在解释的时候还是保留非标准化的的回归系数

假设检验

多元回归模型的检验

  • t检验
  • F检验,p值
  • 矛盾,整体通过,单个不通过

多重共线性

自变量之间存在多重共线性

  • 产生原因
  • 问题:
    • 参数估计不稳定
    • 回归结果不稳定
  • 识别:
    • 计算各对自变量之间的相关系数
    • 特征值判别

多重共线现象

相关性的假设检验

  1. 特征根分析
  2. 条件数condition index
消除
  1. 变量筛选
  2. 增大样本容量
  3. 回归系数的有偏估计:岭回归,主成分分析,偏最小二乘

虽然均值不是无偏的,但是方差比较小,分布比较集中,则可能比无偏估计效果更好

变量选择逐步回归

选择方法

全局择优法

  • 在残差平方和RSS上添加惩罚项
  • $C_p$准则
  • AIC准则&BIC准则:评判指标,取值越小越好

缺点

  • 组合爆炸

逐步回归

向前引入,向后剔除,逐步回归法

引入和剔除都是单向的。比较早剔除的变量在之后加入可能更好。

逐步回归,搜索空间加大。

岭回归

接近奇异,加入K指,使得接近奇异的程度减小。K=0时候,就是最小二乘法。

通过分析岭迹曲线选择K值。

性质

  1. 性质1:有偏估计

岭迹分析

用来解释自变量间的相关关系。

参数k的选择

方差扩大因子

残差平方和来确定k

k值得选择有一些人为的因素在其中。

其他

如何在R中出图的时候单独弹窗

windows();plot(…)

https://stackoverflow.com/questions/46534643/make-r-studio-plots-only-show-up-in-new-window?rq=1

Data mining 2018-11-16 Note

回顾

调查设计(统计学上的小例子)

  • 互斥
  • True/False

云计算

  • 多:浪费;少,数据洪峰
  • pay as you go
  • 软件,平台,基础infrastructure设施即服务

并行计算

串行$\to$并行

  • aim:快
  • CPU$\to$GPU
  • 适合图像$\to$通用计算

要有敏感性。

可以适度了解GPU编程。

release vs debug模式

xx实验室,xx公司人均有多少GPU卡

  • “智能”芯片
  • 嵌入式计算设备:摄像头,MIC,等
  • 并行也有代价
  • 并非所有任务都要用并行

大数据

  • MapReduce
    • map: 隐射(放)
    • reduce: 规约(收)

数据+算法+计算=数据挖掘

没有免费的午餐原则

  • 没有哪个算法始终是比别的好
  • 考虑的因素:可解释性,计算复杂度,可用性
  • 从简单到复杂
  • 能做什么不能做什么
    • 例如,预测股票,彩票

分布式存储

回顾

  • 基于Linux,“table-like”数据操作

  • 命令行操作,正则表达式,awk, sort

  • 单机能力不够,推广到多台服务器

  • 缺陷:需要有管理者。但是我们希望是异步的。

    • 使用常驻进程,agent,每隔一段时间执行若干命令
    • 将以前的controller push变成现在的分布式的pull命令
  • 性能分析

    • 性能瓶颈:IO,计算
    • 分布式IO和计算

大纲

  • 文件系统

  • 布式文件系统

  • GFS 和 HDFS

  • 其他方案

Building Blocks

Type Size Speed
resisters thousands of bytes 1 CPU circle
Cache MB level
Main memory GB level 一般
Disk storage TB level`

功能

  • write
  • read
  • append
  • delete
  • modify

文件系统

准测

  • 能存大量的信息,理论上没有上限
  • information must survive the processed using it
  • concurrent access to multiple processes

文件系统解决方案

  • storage information on disks in units called files
  • files are persistent(持久化)
  • files are managed by the OS

Naming 命名

  • 创建文件并命名

  • 不同OS有不同的规则

Structure 结构

  • 序列结构(遍历),但是Byte Sequence: unstructured

  • 复杂的结构:例如树形结构

    • 变长记录
    • OS specific meaning of each file

文件系统的实现

如何实现文件系统呢?

  • 包含以下方面
    • volumes/partitions(磁盘规划)
    • directories(link filenames to file “structure”)
    • list of blocks
    • 高级需求,例如权限管理等

Structure to data

  • 创建文件
    • find space in the filesystem, add directory entry
  • writing in a file
    • write pointer
  • reading a file
    • read pointer

Data layout

  • file system is stored on disks

    • disk is divided into 1 or more partitions

    • sector 0 of disk called Mater Boot Record(MBR)

    • end of MBR has partition table(start & end address of partitions)

数据存储

  • 连续存储:优点,简单,读写性能比较好;缺点,改动效率不高,碎片太多,用户需要知道文件大小。
  • Linked List Allocation
    • Each file is stored as linked list of blocks
      • first word of each block points to next block
      • rest of disk block is file data
    • 优点
      • 只需要维护第一个block信息
    • 缺点
      • 随机访问开销大
      • overheads of pointers
使用
  • 根据情况使用,永久存储适合连续存储结构
  • 经常变更:列表结构
  • 索引结构:一个指针能够指向多个blocks

Linux 文件系统

Directory Tree

  • /
    • bin
      • pwd, cd, ls
    • sbin: root
      • ifup
      • ifconfig
      • ifdown
    • home
      • home directory
    • var
      • log files
      • spools
    • tmp
      • temp files
    • root
      • root’s home
    • usr
      • user program files
    • opt
      • optional

linux文件系统

Distributed File System

DFS Goals

  • location transparency
  • concurrency(并发性) transparency
  • failure transparency
  • heterogeneity(异构性)
  • scalability(可扩展性)

DFS structure

结构

  • meta server/name node:维护结构,命名
    • data node:负责存储
    • data node
    • ….

File VS. Chunk

  • 对外提供文件名访问
  • 文件对应chunk的id
  • 定义replication(冗余)
  • 整个DFS就是构建映射

可能的过程

  1. client请求
  2. 通过协议,client收到block/chunk信息
  3. client请求要访问的block/chunk
  4. 返回哪些name node的那些地方存在有相应的block/chunk
  5. client请求name node上的block/chunk
  6. 通过网络(socket)返回文件(流)

“Rack” awareness

  • core switch
    • core switch
      • rack switch
      • datanode (最容易访问的位置)
      • datanode
    • core switch

Read

  • 随机读
  • 并行读
  • throughput awareness
  • smart client

删除

  • 删除映射
  • 定期垃圾回收

优点和局限

  • fault tolerance, namenode在线热备份
  • custom designed(例如,定义chunk,减少访问次数)

缺点:只在特定的条件下有用。安全机制。

FS DFS
organized with a structure same as FS
index+data namenode+datanode
smart FS simple DFS+smart client

相当于把FS中的“聪明的”工作搬到client上了。

阅读任务

DHT(分布式哈希表)

GFS

阅读材料。(pipeline, reduplication)