大数量流式总括模型

数据流管理系列:固定查询、ad hoc查询

大数据流式总结:Twitter Storm、Yahoo S4

  上边是代码实现:

大数额的概念

Volume(数据容量)、Variety(数据类型)、Viscosity(价值密度)、Velocity(速度)、维拉city(真实性)

   txt[] = "AAAAAAAAAAAAAAAAAB"
   pat[] = "AAAAB"

   txt[] = "ABABABCABABABCABABABC"
   pat[] =  "ABABAC" (not a worst case, but a bad case for Naive)

HDFS

预处理的插画(或构建lps [])

大数额的性质

非结构性、不完备性、时效性、安全性、可靠性

注意: lps
[i]也可以定义为最长的前缀,也是天经地义的后缀。大家需要在一个地点接纳科学的,以保证整个子字符串不被考虑。

HDFS容错

1.心跳检测:NameNode和DataNode之间

2.文书块完整性:记录新建文件所有块的校验和

3.集群载重均衡:自动从负载重的DataNode上迁移数据

4.文书删除:存放在/trash下,过一段时间才正式删除。在hdfs-site.xml中安排

 

多少解析的目的

对杂乱无章的数量开展汇总、萃取、提炼,进而找出所啄磨对象的内在规律,发现其价值。

  • 我们先导与j = 0的pat [j]与当前文件窗口的字符举办比较。
  • 我们维持匹配字符txt [i]和pat [j],并在p​​at [j]和txt
    [i]保持匹配的再就是不断增添i和j 。
  • 当咱们来看不匹配的时候

    • 俺们了解,字符pat [0..j-1]与txt [i-j + 1 …
      i-1]匹配(注意,j从0起先还要只有在分外时才扩充)。
    • 咱俩也精通(从地点的概念中)lps [j-1]是pat [0 …
      j-1]的字符数,它们都是没错的前缀和后缀。
    • 从地方两点我们可以得出结论,我们不需要将这个lps [j-1]字符与txt
      [ij …
      i-1]拓展匹配,因为大家清楚那个字符无论如何将匹配。让大家考虑地点的例证来了然那一点。

    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    lps[] = {0, 1, 2, 3}

    i = 0, j = 0
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j[ match, do i++, j++

    i = 1, j = 1
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j[ match, do i++, j++

    i = 2, j = 2
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    pat[i] and pat[j[ match, do i++, j++

    i = 3, j = 3
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j[ match, do i++, j++

    i = 4, j = 4
    Since j == M, print pattern found and resset j,
    j = lps[j-1] = lps[3] = 3

    Here unlike Naive algorithm, we do not match first three
    characters of this window. Value of lps[j-1] (in above
    step) gave us index of next character to match.
    i = 4, j = 3
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j[ match, do i++, j++

    i = 5, j = 4
    Since j == M, print pattern found and reset j,
    j = lps[j-1] = lps[3] = 3

    Again unlike Naive algorithm, we do not match first three
    characters of this window. Value of lps[j-1] (in above
    step) gave us index of next character to match.
    i = 5, j = 3
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j] do NOT match and j > 0, change only j
    j = lps[j-1] = lps[2] = 2

    i = 5, j = 2
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j] do NOT match and j > 0, change only j
    j = lps[j-1] = lps[1] = 1

    i = 5, j = 1
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j] do NOT match and j > 0, change only j
    j = lps[j-1] = lps[0] = 0

    i = 5, j = 0
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j] do NOT match and j is 0, we do i++.

    i = 6, j = 0
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j] match, do i++ and j++

    i = 7, j = 1
    txt[] = “AAAAABAAABA”
    pat[] = “AAAA”
    txt[i] and pat[j] match, do i++ and j++

CAP选择

1.遗弃分区容错,导致可扩充性不强:MySQL、Postgres

2.丢弃可用性,导致性能不是特意高:Redis、MongoDB、MemcacheDB、HBase、BigTable、Hypertable

3.放弃一致性,对一致性要求低:Cassandra、Dynamo、Voldemort 、CouchDB

  • 1))。在最坏的情形下,KMP算法的岁月复杂度是O(n)。

探寻引擎

KMP算法背后的为主考虑是:每当大家检测到一个不般配(在部分匹配之后),我们曾经知道下一个窗口文本中的一些字符。我们利用那个音信避免匹配我们领略无论咋样将匹配的字符。让大家考虑下边的例子来精晓这一点。

函数式编程的特性

1.不曾副功用:没有改动过函数在其功效域之外的量并被其他函数使用

2.无状态的编程:将情状保存在参数中,作为函数的附赠品来传递(不是很懂)

3.输入值和输出值:在函数式编程中,只有输入值和输出值。函数是着力的单位。在面向对象编程中,将对象传来传去;在函数式编程中,是将函数传来传去。

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

MapReduce流程图(图来自圣彼得(Peter)堡大学黄宜华先生的课件)

图片 1

我们在眼前的稿子中现已商讨过Naive格局搜索算法。Naive算法的最坏意况复杂度是O(m(n-m

Storm特征

1.编程简单

2.襄助多语言

3.作业级容错

4.品位增加

5.底层使用Zero音讯队列,快

pat[] = "AAACAAAA"

len = 0, i  = 0.
lps[0] is always 0, we move 
to i = 1

len = 0, i  = 1.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 1, lps[1] = 1, i = 2

len = 1, i  = 2.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 2, lps[2] = 2, i = 3

len = 2, i  = 3.
Since pat[len] and pat[i] do not match, and len > 0, 
set len = lps[len-1] = lps[1] = 1

len = 1, i  = 3.
Since pat[len] and pat[i] do not match and len > 0, 
len = lps[len-1] = lps[0] = 0

len = 0, i  = 3.
Since pat[len] and pat[i] do not match and len = 0, 
Set lps[3] = 0 and i = 4.

len = 0, i  = 4.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 1, lps[4] = 1, i = 5

len = 1, i  = 5.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 2, lps[5] = 2, i = 6

len = 2, i  = 6.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 3, lps[6] = 3, i = 7

len = 3, i  = 7.
Since pat[len] and pat[i] do not match and len > 0,
set len = lps[len-1] = lps[2] = 2

len = 2, i  = 7.
Since pat[len] and pat[i] match, do len++, 
store it in lps[i] and do i++.
len = 3, lps[7] = 3, i = 8

We stop here as we have constructed the whole lps[].

科学商量范式

第一范式(科学实验)、第二范式(科学理论)、第三范式(系统模拟)、第四范式(数据密集型总括)

KMP匹配算法使用该格局的落后性质(在格局中有所相同子情势现身不止三次的格局),并将最坏情况复杂度进步到O(n)。

大数量技术的表征

1.剖析宏观的数量而非随机取样

2.尊重数量的复杂,弱化精确性

3.关爱数据的相关性,而非因果关系

// C++ program for implementation of KMP pattern searching
// algorithm
#include<bits/stdc++.h>

void computeLPSArray(char *pat, int M, int *lps);

// Prints occurrences of txt[] in pat[]
void KMPSearch(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    // create lps[] that will hold the longest prefix suffix
    // values for pattern
    int lps[M];

    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);

    int i = 0;  // index for txt[]
    int j  = 0;  // index for pat[]
    while (i < N)
    {
        if (pat[j] == txt[i])
        {
            j++;
            i++;
        }

        if (j == M)
        {
            printf("Found pattern at index %d n", i-j);
            j = lps[j-1];
        }

        // mismatch after j matches
        else if (i < N && pat[j] != txt[i])
        {
            // Do not match lps[0..lps[j-1]] characters,
            // they will match anyway
            if (j != 0)
                j = lps[j-1];
            else
                i = i+1;
        }
    }
}

// Fills lps[] for given patttern pat[0..M-1]
void computeLPSArray(char *pat, int M, int *lps)
{
    // length of the previous longest prefix suffix
    int len = 0;

    lps[0] = 0; // lps[0] is always 0

    // the loop calculates lps[i] for i = 1 to M-1
    int i = 1;
    while (i < M)
    {
        if (pat[i] == pat[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else // (pat[i] != pat[len])
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar 
            // to search step.
            if (len != 0)
            {
                len = lps[len-1];

                // Also, note that we do not increment
                // i here
            }
            else // if (len == 0)
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}

// Driver program to test above function
int main()
{
    char *txt = "ABABDABACDABABCABAB";
    char *pat = "ABABCABAB";
    KMPSearch(pat, txt);
    return 0;
}

格雷(格雷(Gray))法则

1.科学统计数据爆炸式增长

2.解决方案为横向增加的连串布局

3.将统计用于数据而不是数额用于统计(把程序向数据迁移。以总计为着力转变为以数量为主旨)

图片 2

数码解析的含义

在纷纷扬扬的数额中分析出有价值的情节,得到对数码的认知。

输出:

寻找引擎的工作经过

爬行 -> 抓取存储 -> 预处理 -> 排行

预处理算法:
在预处理局部,大家计算lps
[]中的值。为此,我们跟踪前一个目录的最长前缀后缀值(我们采用len变量用于此目标)的尺寸。我们将lps
[0]和len开始化为0.假若pat [len]和pat
[i]配合,我们将len加1,并将加码的值赋给lps [i]。如果pat [i]和pat
[len]不匹配,len不为0,我们将len更新为lps
[len-1]。有关详细音信,请参阅下边的代码中的computeLPSArray()。

大数量应用趋势

分开市场、推动公司发展、大数目解析的新形式出现、大数额与云总计中度融合、大数据总体设施陆续出现、大数目安全

Matching Overview
txt = "AAAAABAAABA" 
pat = "AAAA"

我们对比txt和pat:
txt = "AAAAABAAABA" 
pat = "AAAA"  初始位置
我们找到了一个和原始字符串相同的匹配。

下一步,我们比较txt中接下来的字符串和pat字符串
txt = "AAAAABAAABA" 
pat =  "AAAA" [初始位置的下一个位置]
这就是KMP算法优于基本模式匹配算法的地方了。在第二次比较中,我们只比较了pattern的前4个'A',然后我们决定当前是否匹配,我们已经知道前三个匹配,我们直接跳过前三个即可。

需要预处理吗? 
上述解释产生了一个重要问题,如何知道要跳过多少字符。要知道为此,我们预处理模式并准备一个整数数组。告诉我们要跳过的字符数。

函数式编程优点

1.逻辑可证

2.模块化

3.组件化

4.容易调试

5.易于测试

6.更高的生产率

预处理概述:

HDFS写文件

图片 3

例子:

流式数据的特点

实时性、易失性、突发性、无序性、无限性、准确性

给定一个文本txt [0..n-1]和一个情势pat
[0..m-1]
,写一个搜索函数*search(char pat [],char txt
[]),在txt中打印所有出现的pat [] []。可以假诺n>
m*。

Storm缺点

1.资源分配没有考虑任务拓扑的结构特征,不可以适应数据负载的动态变化

2.采用集中式的作业级容错,限制了系统的可扩展性

Found pattern at index 10

MapReduce

 

大数额流式总结

搜索算法:
与Naive算法不同的是,大家将形式依次匹配一个,然后比较每一遍匹配中中的所有字符,我们选择来源lps
[]的值来决定下一个要配合的字符。那个想法是不配合我们知晓无论怎么样将匹配的字符。

数量解析的品类

1.革命性数据解析(为了形成值得假如的检查)

2.定性数据解析(非数值型数据)

3.离线数据解析(先存于磁盘,批处理)

4.在线数据解析(实时)

格局寻找是电脑科学中的一个重大问题。当我们在记事本/
word文件或浏览器或数据库中找寻字符串时,使用情势搜索算法来突显搜索结果。

大数据解析

ok,假诺有问题,随时提问

Storm总体架构

主节点Nimbus:负责全局资源分配、任务调度、状态监控、故障检测

从节点Supervisor:接收任务,启动或截至工作过程Worker。每个Worker内部有多少个Executor。每个Executor对应一个线程。每个Executor对应一个或七个Task。

Zookeeper:协调、存储元数据、从节点心跳音讯、存储整个集群的有着情状信息、所有配置信息

什么使用lps []来决定下一个岗位(或知道要跳过的字符数)?

大数据的关键技术

流处理、并行化、摘要索引、可视化

Examples of lps[] construction:
For the pattern “AAAA”, 
lps[] is [0, 1, 2, 3]

For the pattern “ABCDE”, 
lps[] is [0, 0, 0, 0, 0]

For the pattern “AABAACAABAA”, 
lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

For the pattern “AAACAAAAAC”, 
lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4] 

For the pattern “AAABAAA”, 
lps[] is [0, 1, 2, 0, 1, 2, 3]

HDFS首要组件(图来源金沙萨医科大学大数目课程李先生的课件)

图片 4

KMP(克努特莫Rhys(Maurice)普拉特)情势寻找的Naive形式搜索算法并不在在这种情状下很好的行事:许多匹配字符,随后是不兼容的字符的图景下。以下是一对例子。

CAP定理

一个分布式系统不可以还要知足一致性、可用性、分区容错性六个系统要求,最两只好同时满足六个。

  • KMP算法对pat
    []展开预处理,并协会一个尺寸为m(与形式大小一样)的帮带lps
    []
    ,用于匹配时跳过字符。
  • 名称lps意味着最长的没错前缀,也是后缀。。一个恰如其分的前缀是前缀与所有字符串恐怕。例如,“ABC”的前缀是“”,“A”,“AB”和“ABC”。正确的前缀是“”,“A”和“AB”。字符串的后缀是“”,“C”,“BC”和“ABC”。
  • 对于里边i = 0到m-1的每个子格局pat [0..i],lps
    [i]存储最大匹配正确前缀的尺寸,其也是子形式pat [0..i]的后缀。

    lps[i] = the longest proper prefix of pat[0..i]

              which is also a suffix of pat[0..i]. 
    

追寻引擎的褒贬目的

查全率、查准率、响应时间、覆盖范围、用户方便性

大数目简介

寻找引擎的定义

按照早晚的策略、运用特定的处理器程序、从互联网上采访音讯,对音信举办公司和拍卖未来,将这么些信息展现给用户的系列叫搜索引擎。

探寻引擎的构成

搜索器:搜集音信

索引器:抽取索引

检索器:在库中寻觅,排序。

用户接口:呈现

大数目处理的全经过

数据收集与记录 –>  数据抽取、清洗、标记  –> 
数据集成、转换、简约  –>  数据解析与建模  –>  数据表明

CAP理论

Consistency(一致性)、Availability(可用性)、Partition
Tolerance(分区容错性)

HDFS读文件

图片 5


 

图片 6

HDFS目标

1.兼容廉价的硬件配备

2.流数量读写

3.大数据集

4.简约的文书模型

5.精锐的跨平台包容性