jjzjj

mit6.824 lab1 （2022）

thotf 2023-03-28 原文 

　lab1 要求按照论文实现一个mapReduce 框架
　lab1 ：https://pdos.csail.mit.edu/6.824/labs/lab-mr.html

　　论文：https://zhuanlan.zhihu.com/p/122571315

　　在mrsequential.go文件中有个单机版mapReduce实现很简单建议阅读。

 


 


 


整体框架流程：


　　


 


 


 


 


 


 Coordinator 是协调器，负责


　　　　　　　　　　① 给woker分发任务


　　　　　　　　　　② 合并由map任务执行产生的中间文件


　　　　　　　　　　③ 任务超时重新分配任务


 


woker 是工作器，负责


　　　　　　　　①循环申请map 或reduce任务


　　　


 


先看woker：


　　worker 向 Coordinator 发送任务申请后，判断得到的是什么样类型的任务




//申请任务
for {
   args := Args{}
   args.Signal = REQUEST_WORKER

   reply := RpcCall(args)
   switch reply.STATUS {
   case COORDINATOR_MAP:    //获得map任务
   　　MapHandle(&reply,mapf)

   case COORDINATOR_REDUCE: //获得reduce任务
　　　　ReduceHandle(&reply,reducef)


　　case COORDINATOR__MAP_END:  //没申请到任务重新获取
   　　continue

　　case END:                //结束
   　　return


　　}　　




　　


Recude任务
　　处理方式和mrsequential.go中几乎是一样的不多说了。

map任务
　　会从Coordinator 获得文件名、任务id、Nreduce（中间文件个数）



 






 


 kva是通过mapf 对文件处理得到的数据。


我开启两个任务分发器，和Nreduce 个文件写入器，进行并发处理数据。将数据写入到Nreduce个中间文件中，分发依据为ihash函数。




kva := MapMachingFile(reply.FileName, mapf)
	midFileName := "mr-out-" + reply.FileName
	chanArray := make([]chan KeyValue, 10)
	for i := 0; i < 10; i++ {
		chanArray[i] = make(chan KeyValue, 10)
	}

	//开启reduceNumber个文件写入线程
	var w sync.WaitGroup
	var mapW sync.WaitGroup
	w.Add(reply.Neduce)
	mapW.Add(2)
	for i := 0; i < 10; i++ {
		go GoMakeMidFile(midFileName+strconv.Itoa(i), chanArray[i], &w)
	}

	// 开启分发线程，分发数据到文件写入线程
	lenght := len(kva)
	go MapDistributeMidData(chanArray, kva[:lenght/2], &mapW)
	go MapDistributeMidData(chanArray, kva[lenght/2:], &mapW)

	//所有分发线程结束
	mapW.Wait()
	for cIndex := 0; cIndex < 10; cIndex++ {
		close(chanArray[cIndex])
	}

	//所有文件写入线程结束
	w.Wait()





　　


 


worker结束剩下看Coordinator 。


 


 1 type Coordinator struct {
 2     filebit                    //数据分发记录
 3     Nreduce       int
 4     midFileMergeC chan int
 5     Mergefiled             //已处理数据记录
 6     monitorC      []chan int //监听每个worker是否按时完成
 7     STATUS
 8     RedeceS
 9     *sync.Mutex
10     End            bool
11 }


 


Coordinator  结构记录的信息主要为三部分
　　　　　　　　2、3、4、5行记录map相关
　　　　　　　　6 为监听chan，监听任务是否超时
　　　　　　　　7位Coordinator 当前的状态，通过状态判断要分发map任务、reduce任务、结束



判断worker的目的，请求任务就分发任务处理，完成map任务就将所有map产生中间数据一一对应合并到Nreduce个文件中。


//信号处理
func (c *Coordinator) SignalTask (args *Args, reply *Reply) error {
    switch args.Signal {
    case REQUEST_WORKER:
        c.distributeTask(args,reply)

    //中间文件处理
    case COMPLETE:
        c.midFileMerge(args,reply)
    }

    return nil
}




 在初始化Coordinator时，还会打开一些线程。本线程会开启10个中间文件写入线程，当每个worker处理完map任务后，会将自己处理的map文件相关信息传给Coordinator，Coordinator通过chan将数据发给每个文件合并线程StartMergeFile。


举个例子


workerMap A产生了  1，2，3 个中间文件


1号文件 合并到 mr-out-m-1


2号文件 合并到 mr-out-m-2


3号文件 合并到 mr-out-m-3


 


workerMap  B 又产生1、2、3个中间文件


1号文件 合并到 mr-out-m-1


2号文件 合并到 mr-out-m-2


3号文件 合并到 mr-out-m-3


 








//开启Nreduce个中间文件写入线程
//返回文件写入chan 切片
func (c *Coordinator)runFileWorker () []chan int {
	cLi := make([]chan int,c.Nreduce)
	for i := 0 ; i < c.Nreduce ; i ++ {
		cLi[i] = make(chan int,10)
	}

	for fid := 0 ; fid < c.Nreduce ; fid ++ {
		go c.StartMergeFile(fid,cLi[fid])
	}
	return cLi
}





　　



记录信息是否已处理的结构：


　　 filebit 、ReduceS 核心是通过一个简单的bitmap实现的




type filebit struct{
	rw 		*sync.Mutex
	bitMap
	file []string
}

type RedeceS struct {
	filebit
}





　　






type bitMap struct {
	bit  int16
	size int
}

//获取一个未使用位置
func (b *bitMap) GetOne() int {
	for i := int(0) ; i < b.size ; i ++ {
		if b.isZero(i) {
			b.seTUsed(i)
			return i
		}
	}
	//这里超过size限制会直接报错
	return -1
}

//第i位是否为0
//为0未使用
func (b *bitMap) isZero (index int) bool {
	return ((1 << index) & b.bit) == 0
}

//设置index位已使用
func (b *bitMap) seTUsed (index int) {
	b.bit = (1 << index) | b.bit
}

func (b *bitMap) setEnUsed (index int) {
	b.bit = (0 << index) | b.bit
}







　　



任务超时处理：



func (c *Coordinator) monitorWorker (id int) {
    timer := time.NewTimer(time.Duration(time.Second*10))
    select {
    case <-c.monitorC[id]:
        return
    case <-timer.C:
        //超时设置为未分配，重新分配
        c.SetEnUsed(id)
    }
}


每次分发一个任务出去，就会开启一个线程监听刚发送出去的任务。


当Coordinator 接收到任务完成信号，就会给任务id对应的信号监听函数发送信息，结束监听函数。


当未在规定时间内发送信号给监听函数，则将当前监听的任务id在filebit结构中标记在为未分发，重新轮循分发给下一个到来的worker。


如果这个未按时完成任务的worker后来完成任务并且发送信号过来，当这个任务已经还是为未分发状态则舍弃这个worker请求。


如果这个任务同时分发给了其他worker，则接收这个worker，舍弃最后来的。（这里设计的不太好）










 
            

            
mit62022spanstylecolorGo
        

        

            
有关mit6.824 lab1 （2022）的更多相关文章

            
    
                
  1. 映宇宙2022年营收63亿元：同比下降三成，毛利率提升4.3个百分点 - 2
    3月26日，映宇宙（HK:03700，即“映客”）发布截至2022年12月31日的2022年度业绩财务报告。财报显示，映宇宙2022年的总营收为63.19亿元，较2021年同期的91.76亿元下降31.1%。2022年，映宇宙的经营亏损为4698.7万元，2021年同期则为净利润4.57亿元；期内亏损（净亏损）为1.68亿元，2021年同期的净利润为4.33亿元；非国际财务报告准则经调整净利润为3.88亿元，2021年同期为4.82亿元，同比下降19.6%。 映宇宙在财报中表示，收入减少主要是由于行业竞争加剧，该集团对旗下产品采取更为谨慎的运营策略以应对市场变化。不过，映宇宙的毛利率则有所提升
  2. IDEA 2022 创建 Spring Boot 项目详解 - 2
    如何用IDEA2022创建并初始化一个SpringBoot项目？目录如何用IDEA2022创建并初始化一个SpringBoot项目？0. 环境说明1.  创建SpringBoot项目 2.编写初始化代码0. 环境说明IDEA2022.3.1JDK1.8SpringBoot1.  创建SpringBoot项目        打开IDEA，选择NewProject创建项目。        填写项目名称、项目构建方式、jdk版本，按需要修改项目文件路径等信息。        选择springboot版本以及需要的包，此处只选择了springweb。        此处需特别注意，若你使用的是jdk1
  3. 2022年10月23日周赛ZZULIOJ - 2
    文章目录问题B:芝华士威士忌和他的小猫咪们代码&注释问题C:愿我的弹雨能熄灭你们的痛苦代码注释问题D:猜糖果游戏代码注释问题E:有趣的次方代码注释问题F:这是一个简单题代码&注释问题G:打印矩阵代码注释问题H:scz的简单考验代码注释问题I:完美区间代码&注释问题J:是狂热的小迷妹一枚吖~代码&注释2022年10月23日周赛ZZULIOJ问题B:芝华士威士忌和他的小猫咪们时间限制:1Sec内存限制:128MB题目描述芝华士威士忌很喜欢带着他的猫咪们一块跑着玩。但是小猫咪们很懒，只有在离他y米以内才愿意和他一块跑。这天他在坐标为x的位置，他想和他的猫咪们一块跑着玩。有n个小猫咪，第i个小猫咪在坐
  4. 【华为OD机试真题 java、python、c++】荒地电站建设【2022 Q4 100分】（100%通过+复盘思路） - 2
    代码请进行一定修改后使用，本代码保证100%通过率，本题目提供了java、python、c++三种代码。复盘思路在文章的最后题目描述祖国西北部有一片大片荒地，其中零星的分布着一些湖泊，保护区，矿区;整体上常年光照良好，但是也有一些地区光照不太好。某电力公司希望在这里建设多个光伏电站，生产清洁能源对每平方公里的土地进行了发电评估，其中不能建设的区域发电量为0kw，可以发电的区域根据光照，地形等给出了每平方公里年发电量x千瓦。我们希望能够找到其中集中的矩形区域建设电站，能够获得良好的收益。输入描述第一行输入为调研的地区长，宽，以及准备建设的电站【长宽相等，为正方形】的边长最低要求的发电量之后每行为
  5. 玩客云刷机（2022-3-19亲测） - 2
    https://cloud.189.cn/t/BJbYreYbmUj2(访问码:djz6)（网盘2022-4-1更新）一、刷入armbian。1.1使用AmlBurnTool软件烧录首选底包至固件。烧录完成后断开玩客云电源备用。(靠近hdmi的那个口子。)1.2使用WIn32diskimager软件将emmc固件写入U盘。1.3写入成功后，先将U盘插入玩客云靠近网线接口端的USB口，再接入电源。玩客云通电后指示灯会先亮绿灯，再亮蓝灯，红蓝闪烁，最后蓝灯常亮。等到确定蓝灯常亮后，再拔掉U盘、电源。(最好蓝灯常亮后，启动一次玩客云，看看ssh是否正常。)1.4使用WIn32diskimager写入
  6. AiBote 2022 新研发的自动化框架，支持 Android 和 Windows 系统。速度非常快 - 2
    Ai-Bot基于流行的Node.js和JavaScript语言的一款新自动化框架，支持Windows和Android自动化。1、Windowsxpath元素定位算法支持支持Windows应用、.NET、WPF、Qt、Java和Electron客户端程序和ie、edgechrome浏览器2、Android支持原生APP和H5界面，元素定位速度是appium十倍，无线远程自动化操作多台安卓设备3、基于opencv图色算法，支持找图和多点找色，1080*2340全分辨率找图50MS以内4、内置免费OCR人工智能技术，无限制获取图片文字和找字功能。5、框架协议开源，除官方node.jsSDK外，用户可
  7. 考勤刷卡 最大和 简单 蓝桥杯省赛 2022 - 2
    问题描述小蓝负责一个公司的考勤系统,他每天都需要根据员工刷卡的情况来确定每个员工是否到岗。当员工刷卡时,会在后台留下一条记录,包括刷卡的时间和员工编号,只要在一天中员工刷过一次卡,就认为他到岗了。现在小蓝导出了一天中所有员工的刷卡记录,请将所有到岗员工的员工编号列出。输入格式输入的第一行包含一个正整数n,表示一天中所有员工的刷卡记录的条数。接下来n行,每行包含一条刷卡记录,每条刷卡记录的格式为:HH:MM:SSID其中HH:MM:SS表示刷卡时间,HH为一个0到23之间的两位十进制整数(可能含前导0)表示时,MM为一个0到59之间的两位十进制整数(可能含前导0)表示分,SS为一个0到59之间的
  8. upload-labs通关 - 2
    最近，我有个朋友老是反映部署的网站老是被黑客攻击，我看了下就是普通的PHP框架搭建的网站，经过一番排除也清除了木马。为此我专门花1天时间研究一下文件上传漏洞，知己知彼方能百战百胜。这里我选择了一个开源的靶场upload-labs。测试环境部署游览器插件下载地址Cookie-Editor：https://chrome.google.com/webstore/detail/hlkenndednhfkekhgcdicdfddnkalmdmHackBar：https://hackbar.herokuapp.com/使用everything搜索hackbar-panel.js文件的位置，注释或删除以下代
  9. 2022年山东省职业院校技能大赛高职组“信息安全管理与评估”赛项竞赛规程 - 2
    2022年山东省职业院校技能大赛高职组“信息安全管理与评估”赛项竞赛规程一、赛项名称赛项名称：信息安全管理与评估英文名称：InformationSecurityManagementandEvaluation赛项组别：高职组赛项归属：电子与信息大类二、竞赛目的（一）引领教学改革通过大赛引领专业教学改革，实现以赛促教、以赛促学、以赛促改的产教结合格局，提升专业培养服务社会和行业发展的能力，为国家信息安全行业培养选拔技术技能型人才。2022年信息安全管理与评估赛项延续历届赛项的竞赛内容，通过赛项检验参赛选手安全网络组建、按照等保要求加固网络系统、安全架构、渗透测试、攻防实战等技术能力，检验参赛队计划
  10. 2022年度 FinClip 扩展 SDK 推荐！ - 2
    2022年，FinClip团队进行了24个产品迭代，为了丰富FinClip的平台能力，除了核心SDK之外，我们还为开发者们提供了扩展SDK，扩展SDK是一个依赖核心SDK的库，里面提供了核心SDK中所没有的各种小程序API。官方希望通过丰富的扩展SDK库可以帮助开发者减少开发工作，把更多的精力用到实现业务上。那本期，小编就为大家推荐扩展SDK库中8个功能稳定又实用的SDK！（更多详细内容请点击）以下分享以AndroidSDK文件为例，您可登录 资源下载中心下载AndroidSDK文件，扩展SDK也处于在所下载的压缩包中。1、WeChatSDK微信SDK的快捷接入，提供调起微信通过微信小程序获得
    11.             

        

        

            
随机推荐