《MizanGraph Processing System - 网络与信息系统.ppt》由会员分享,可在线阅读,更多相关《MizanGraph Processing System - 网络与信息系统.ppt(30页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Mizan:Graph Processing System,,topics,Brief introduction on PregelEuroSys13 paper: MizanOur ideas,Pregel,A System for Large-Scale Graph ProcessingMapreduce v.s. PregelHadoop v.s. Hama,Giraph.,Inside Pregel,Graph partitioning,Graph data,Worker1,Worker2,Workern,Pregel,output,Communication costLoad bal
2、ance,Inside Pregel,Problems of Pregel,Worker1,Worker2,Workern,Worker1,Worker2,Workern,Computation,Communication,Mizan,A system for Dynamic Load Balancing in Large-scale Graph Processing,Load balance,Current method for load balance:Hash partition, Giraph, PregelRange partition, Min-cut partition(Meti
3、s) Sophisticated partitioning tech.,Mizan goal,building a system that is:AdaptiveAgnostic to the graph structurerequires no a priori knowledge of algorithm behavior,Graph algorithms,Stationary Graph Algorithms:matrix-vector multiplicationPageRankfinding weakly connected componentsNon-stationary Grap
4、h Algorithms:DMST: distributed minimal spanning treegraph queriesadvertisement propagation,Mizan,MonitoringMigration planning,Monitoring,Outgoing messageIncoming messageResponse time,Migration Planning,Five-step migration planning:Identify the source of imbalanceSelect the migration objectivePair ov
5、er-utilized workers with under-utilized onesSelect vertices to migrateMigrate vertices,Step 1,Step 2,Select the migration objectiveOutgoing msg, incoming msg, response timeCompute correlation between:Outgoing msg and response timeIncoming msg and response timeDefault response time,Step 3,Step 4,Step
6、 5,Migrate verticeswhen all workers arriving at migration barrierMigrated data:vertex IDStateedge information (friends list) the received messages it will process,Mizan,Mizan implementation,Mizan implementation,Challenge 1: Vertex Ownershiphuge dataFrequent vertex migrationTechs:Each vertex has a ho
7、me_workerHDT maintain home_worker location,Mizan implementation,Challenge 2: Large Message Size,Evaluation,Experiments:Implemented Mizan using C+ and MPI12 machines with i5 processor 16GB RAM,Evaluation,Benchmarks:Static: disables any dynamic migrationWork Stealing (WS): Pregel versionMizan.,Evaluat
8、ion,Static Mizan vs. Giraph:,Evaluation,PageRank on three system:,Evaluation,Migration costs:,Evaluation,Un-stationary algorithm:,Evaluation,Migration overhead:,Really?,Some arguable parts of Mizan:Cost: migration planning, multi global information synchronization(S1,S2,S3)Especially in S3, global order maintainingLarge data transferred in migrationMigration will lead more cross-communicationCentralized management bad than decentralized?Not friendly to graph mutation ,