探索C#之微型MapReduce

MapReduce近几年比较热的分布式计算编程模型,以C#为例简单介绍下MapReduce分布式计算。

阅读目录

  1. 背景
  2. Map实现
  3. Reduce实现
  4. 支持分布式
  5. 总结

背景

某平行世界程序猿小张接到Boss一项任务,统计用户反馈内容中的单词出现次数,以便分析用户主要习惯。文本如下:

        const string hamlet = @"Though yet of Hamlet our dear brother's death
The memory be green, and that it us befitted
To bear our hearts in grief and our whole kingdom
To be contracted in one brow of woe,
Yet so far hath discretion fought with nature
That we with wisest sorrow think on him,
Together with remembrance of ourselves.
Therefore our sometime sister, now our queen,
The imperial jointress to this warlike state,
Have we, as 'twere with a defeated joy,--
With an auspicious and a dropping eye,
With mirth in funeral and with dirge in marriage,
In equal scale weighing delight and dole,--
Taken to wife: nor have we herein barr'd
Your better wisdoms, which have freely gone
With this affair along. For all, our thanks.
Now follows, that you know, young Fortinbras,
Holding a weak supposal of our worth,
Or thinking by our late dear brother's death
Our state to be disjoint and out of frame,
Colleagued with the dream of his advantage,
He hath not fail'd to pester us with message,
Importing the surrender of those lands
Lost by his father, with all bonds of law,
To our most valiant brother. So much for him.
Now for ourself and for this time of meeting:
Thus much the business is: we have here writ
To Norway, uncle of young Fortinbras,--
Who, impotent and bed-rid, scarcely hears
Of this his nephew's purpose,--to suppress
His further gait herein; in that the levies,
The lists and full proportions, are all made
Out of his subject: and we here dispatch
You, good Cornelius, and you, Voltimand,
For bearers of this greeting to old Norway;
Giving to you no further personal power
To business with the king, more than the scope
Of these delated articles allow.
Farewell, and let your haste commend your duty.";

小张作为蓝翔高材生,很快就实现了:

   var content = hamlet.Split(new[] { " ", Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
            var wordcount=new Dictionary<string,int>();
            foreach (var item in content)
            {
                if (wordcount.ContainsKey(item))
                    wordcount[item] += 1;
                else
                    wordcount.Add(item, 1);
            }

作为有上进心的青年,小张决心对算法进行抽象封装,并支持多节点计算。小张把这个统计次数程序分成两个大步骤:分解和计算。 第一步:先把文本以某维度分解映射成最小独立单元。 (段落、单词、字母维度)。 第二部:把最小单元重复的做合并计算。 小张参考MapReduce论文设计Map、Reduce如下:

Map实现

Mapping

Mapping函数把文本分解映射key,value形式的最小单元,即<单词,出现次数(1)>、<word,1>。

    public IEnumerable<Tuple<T, int>> Mapping(IEnumerable<T> list)
        {
            foreach (T sourceVal in list)
                yield return Tuple.Create(sourceVal, 1);
        }

使用,输出为(brow, 1), (brow, 1), (sorrow, 1), (sorrow, 1):

            var spit = hamlet.Split(new[] { " ", Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
            var mp = new MicroMapReduce<string>(new Master<string>());
            var result= mp.Mapping(spit);

Combine

为了减少数据通信开销,mapping出的键值对数据在进入真正的reduce前,进行重复键合并。也相对于提前进行预计算一部分,加快总体计算速度。 输出格式为(brow, 2), (sorrow, 2):

 public Dictionary<T, int> Combine(IEnumerable<Tuple<T, int>> list)
        {
            Dictionary<T, int> dt = new Dictionary<T, int>();
            foreach (var val in list)
            {
                if (dt.ContainsKey(val.Item1))
                    dt[val.Item1] += val.Item2;
                else
                    dt.Add(val.Item1, val.Item2);
            }
            return dt;
        }

Partitioner

Partitioner主要用来分组划分,把不同节点的统计数据按照key进行分组。 其输出格式为: (brow, {(brow,2)},(brow,3)), (sorrow, {(sorrow,10)},(brow,11)):

public IEnumerable<Group<T, int>> Partitioner(Dictionary<T, int> list)
        {
            var dict = new Dictionary<T, Group<T, int>>();
            foreach (var val in list)
            {
                if (!dict.ContainsKey(val.Key))
                    dict[val.Key] = new Group<T, int>(val.Key);
                dict[val.Key].Values.Add(val.Value);
            }
            return dict.Values;
        }

 Group定义:

    public class Group<TKey, TValue> : Tuple<TKey, List<TValue>>
    {
        public Group(TKey key)
            : base(key, new List<TValue>())
        {
        }

        public TKey Key
        {
            get
            {
                return base.Item1;
            }
        }

        public List<TValue> Values
        {
            get
            {
                return base.Item2;
            }
        }
    }

Reduce实现

Reducing函数接收,分组后的数据进行最后的统计计算。

 public Dictionary<T, int> Reducing(IEnumerable<Group<T, int>> groups)
        {
            Dictionary<T, int> result=new Dictionary<T, int>();
            foreach (var sourceVal in groups)
            {
                result.Add(sourceVal.Key, sourceVal.Values.Sum());
            }
            return result;
        }

封装调用如下:

 public IEnumerable<Group<T, int>> Map(IEnumerable<T> list)
        {
            var step1 = Mapping(list);
            var step2 = Combine(step1);
            var step3 = Partitioner(step2);
            return step3;
        }

  public Dictionary<T, int> Reduce(IEnumerable<Group<T, int>> groups)
        {
            var step1 = Reducing(groups);
            return step1;
        }
  public  Dictionary<T, int> MapReduce(IEnumerable<T> list)
        {
            var map = Map(list);
            var reduce = Reduce(map);
            return reduce;
        }

整体计算步骤图如下:

支持分布式

小张抽象封装后,虽然复杂度上去了。但暴露给使用者是非常清晰的接口,满足MapReduce的数据格式要求,即可使用。

            var spit = hamlet.Split(new[] { " ", Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
            var mp = new MicroMapReduce<string>(new Master<string>());
            var result1= mp.MapReduce(spit);

小张完成后脑洞大开,考虑到以后文本数据量超大。 所以fork了个分支,准备支持分布式计算,以后可以在多个服务器节点跑。

数据分片

数据分片就是把大量数据拆成一块一块的,分散到各个节点上,方便我们的mapReduce程序去计算。 分片主流的有mod、consistent hashing、vitual Buckets、Range Partition等方式。 关于consistent hashing上篇有介绍(探索c#之一致性Hash详解)。在Hadoop中Hdfs和mapreduce是相互关联配合的,一个存储和一个计算。如果自行实现的话还需要个统一的存储。所以这里的数据源可以是数据库也可以是文件。小张只是满足boss需求,通用计算框架的话可以直接用现成的。

模拟分片

public List<IEnumerable<T>> Partition(IEnumerable<T> list)
        {
            var temp =new List<IEnumerable<T>>();
            temp.Add(list);
            temp.Add(list);
            return temp;
        }

Worker节点

小张定义了Master,worker角色。 master负责汇集输出,即我们的主程序。 每一个worker我们用一个线程来模拟,最后输出到master汇总,master最后可以写到数据库或其他。

 public void WorkerNode(IEnumerable<T> list)
        {
            new Thread(() =>
            {
                var map = Map(list);
                var reduce = Reduce(map);
                master.Merge(reduce);
            }).Start();
        } 
 public class Master<T>
    {
        public Dictionary<T, int> Result = new Dictionary<T, int>();
        public  void Merge(Dictionary<T, int> list)
        {
            foreach (var item in list)
            {
                lock (this)
                {
                    if (Result.ContainsKey(item.Key))
                        Result[item.Key] += item.Value;
                    else
                        Result.Add(item.Key, item.Value);
                }
            }
        }
    }

分布式计算步骤图:

总结

MapReduce模型从性能速度来说并不是非常好的,它优势在于隐藏了分布式计算的细节、容灾错误、负载均衡及良好的编程API,包含HDFS、Hive等在内一整套大数据处理的生态框架体系。在数据量级不是很大的话,企业自行实现一套轻量级分布式计算会有很多优点,比如性能更好、可定制化、数据库也不需要导入导出。从成本上也节省不少,因为hadoop开发、运维、服务器都需要不少人力物力。

文中例子代码

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JavaEdge

放弃 Calender优雅地使用Joda-Time吧Joda 大型项目Joda 简介Joda 和 JDK 互操作性Joda 的关键日期/时间概念

2927
来自专栏恰同学骚年

设计模式的征途—2.简单工厂(Simple Factory)模式

  工厂模式是最常用的一种创建型模式,通常所说的工厂模式一般是指工厂方法模式。本篇是是工厂方法模式的“小弟”,我们可以将其理解为工厂方法模式的预备知识,它不属于...

994
来自专栏大数据挖掘DT机器学习

用通俗易懂的大白话讲解Map/Reduce原理

Hadoop简介 Hadoop就是一个实现了Google云计算系统的开源系统,包括并行计算模型Map/Reduce,分布式文件系统HDFS,以及分布式数据库Hb...

3448
来自专栏我是攻城师

Java时间处理神器之Joda-Time

4365
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(八)No.60

今天跟小伙伴们聊聊另外一个统计算法, Roaring BitMaps。 这个该怎么翻译呢??咆哮的位图?s?我翻译不出来,但是小蕉头一歪,就给它起了一个狂拽酷霸...

2447
来自专栏NetCore

[原创]Fluent NHibernate之旅(四)-- 关系(下)

最近一直忙着准备去旅行的东东,所以进度慢下来了,明天就要出发了,嘿嘿,在出发前,把多对多给写完吧。如果你第一次看这个系列,可以先看看先前几篇,了解下。 一、开篇...

21310
来自专栏程序猿DD

并行化:你的高并发大杀器

想必热爱游戏的同学小时候,都幻想过要是自己要是能像鸣人那样会多重影分身之术,就能一边打游戏一边上课了,可惜漫画就是漫画,现实中并没有这个技术,你要么只有老老实实...

1963
来自专栏木东居士的专栏

MapReduce 编程模型极简篇

2174
来自专栏跟着阿笨一起玩NET

采用左右值编码来存储无限分级树形结构的数据库表设计

该设计方案的优点是:只用一条查询语句即可得到某个根节点及其所有子孙节点的先序遍历。由于消除了递归,在数据记录量较大时,可以大大提高列表效率。但是,这种编码方案由...

2831
来自专栏一名叫大蕉的程序员

简约的JAVA版本MapReduce和日常No.25

昨天做了一个小调查,说看看想看些啥。大概的分布是这样的,一个1代表一个投票。看来还是2、3比较多。 11111 希望看到"算法"回复1。 111...

1945

扫码关注云+社区

领取腾讯云代金券