NEC Corporation · TSE:6701

NEC — Technical Presentation

29 slides from NEC's technical presentation

  1. Slide 1: Feliss: Flexible distributed computing framework with light-weight checkpointing

    Slide 1: Feliss: Flexible distributed computing framework with light-weight checkpointing

    Feliss: Flexible distributed computing framework with light-weight checkpointing Takuya Araki, Kazuyo Narita and Hiroshi Tamano NEC Corporation 1

  2. Slide 2: Background

    Slide 2: Background

    Background Big Data analysis is becoming common • sensors, the Web, business transactions, etc. • Hadoop / MapReduce is commonly used Distributed analysis with Hadoop Collected Result “Big Data” 2

  3. Slide 3: Motivation

    Slide 3: Motivation

    Motivation Hadoop / MapReduce is: • efficient if it fits well with the problem • not efficient, otherwise Fast Slow Hadoop Hadoop MapReduce MapReduce Complex analysis Simple analysis e.g. machine learning 3

  4. Slide 4: Why Hadoop / MapReduce is slow?

    Slide 4: Why Hadoop / MapReduce is slow?

    Why Hadoop / MapReduce is slow? • Many MapReduces need to be combined to implement complex analysis – e.g. iterative computation • They need to communicate through HDFS file I/O, which causes large overhead Complex analysis Simple analysis (e.g. machine learning) MapReduce MapReduce MapReduce … MapR

  5. Slide 5: Why HDFS file I/O is needed?

    Slide 5: Why HDFS file I/O is needed?

    Why HDFS file I/O is needed? For fault-tolerance! • If a fault occurs, the system re-computes lost data from the input data on HDFS – input data need to be on “stable storage” re-computation using the input data fault! Map Reduce Map Reduce HDFS Map Reduce HDFS Map Reduce Map Reduce Map Reduce 5

  6. Slide 6: Any other fault-tolerance methods?

    Slide 6: Any other fault-tolerance methods?

    Any other fault-tolerance methods? Checkpointing! • Saves execution state periodically • Loads it when a fault occurs Replace with a spare fault! save load saved state execution state and resume execution No need to use HDFS for communication between MapReduces 6

  7. Slide 7: What is the problem of checkpointing?

    Slide 7: What is the problem of checkpointing?

    What is the problem of checkpointing? • Saving entire memory – Takes long time: • 10GB memory & 100MB/s disk bandwidth: 100 seconds • Saving variables specified by a programmer – Error prone: • If he/she forgets to save a variable, it does not work memory memory a[0] saved a[1] Saving whole memory b

  8. Slide 8: Our proposal: continuation-based checkpointing

    Slide 8: Our proposal: continuation-based checkpointing

    Our proposal: continuation-based checkpointing Programs are written as follows: (continuation is similar to “task”) Continuation Pool System takes one continuation Initial continuation is execute it (short exec. time) put into pool Rest of computation is converted to “continuation” and put into pool

  9. Slide 9: Rest of this talk

    Slide 9: Rest of this talk

    Rest of this talk Implementation of continuation-based checkpointing Feliss: distributed computing framework with continuation-based checkpointing Distributed checkpointing Improved MapReduce and MPI Evaluation and related work 9

  10. Slide 10: Implementation of continuation-based checkpointing

    Slide 10: Implementation of continuation-based checkpointing

    Implementation of continuation-based checkpointing Feliss: distributed computing framework with continuation-based checkpointing Distributed checkpointing Improved MapReduce and MPI Evaluation and related work 10

  11. Slide 11: Implementation of continuation-based checkpointing (1/2)

    Slide 11: Implementation of continuation-based checkpointing (1/2)

    Implementation of continuation-based checkpointing (1/2) Rest of the computation is converted to continuation • Example: Convert function call g void sample(int a) { void sample(int a) { f(); f(); g(a); put_pool (make_cont(g,a)); } } put the created continuation create continuation of into the pool

  12. Slide 12: Implementation of continuation-based checkpointing (2/2)

    Slide 12: Implementation of continuation-based checkpointing (2/2)

    Implementation of continuation-based checkpointing (2/2) • In C++ on Linux • Data structure of continuation is simple: pointer to function argument 1 argument 2 argument 3 ... • Continuations are saved after “serialization” – Serialization converts data with pointers into contiguous data – Boost::se

  13. Slide 13: Feliss: distributed computing framework with continuation-based checkpointing

    Slide 13: Feliss: distributed computing framework with continuation-based checkpointing

    Implementation of continuation-based checkpointing Feliss: distributed computing framework with continuation-based checkpointing Distributed checkpointing Improved MapReduce and MPI Evaluation and related work 13

  14. Slide 14: Feliss: distributed computing framework with continuation-based checkpointing

    Slide 14: Feliss: distributed computing framework with continuation-based checkpointing

    Feliss: distributed computing framework with continuation-based checkpointing • Implemented distributed computing framework using continuation-based checkpointing • Features: – distributed checkpointing – RPC (remote procedure call) – non-blocking (callback based) synchronization – Improved MapReduc

  15. Slide 15: Distributed checkpointing

    Slide 15: Distributed checkpointing

    Implementation of continuation-based checkpointing Feliss: distributed computing framework with continuation-based checkpointing Distributed checkpointing Improved MapReduce and MPI Evaluation and related work 15

  16. Slide 16: Distributed checkpointing (1/3)

    Slide 16: Distributed checkpointing (1/3)

    Distributed checkpointing (1/3) Three kinds of servers: – master, worker, spare Workers do actual distributed computation – by sending and receiving continuations using RPC Initialize Initialize client master worker 1 worker 2 worker 3 spare 1 spare 2 16

  17. Slide 17: Distributed checkpointing (2/3)

    Slide 17: Distributed checkpointing (2/3)

    Distributed checkpointing (2/3) Master orders workers to take checkpoints periodically Checkpoints are sent to other workers for preparing fault checkpoint client master worker 1 checkpoint worker 1 worker 3 checkpoint worker 2 checkpoint worker 2 worker 1 checkpoint worker 3 checkpoint worker 3 wor

  18. Slide 18: Distributed checkpointing (3/3)

    Slide 18: Distributed checkpointing (3/3)

    Distributed checkpointing (3/3) Master checks if workers are running correctly When a fault occurs, it restarts workers from checkpoint – if the worker is still working, a local checkpoint is used – otherwise, a spare reads a checkpoint from a worker that has it checkpoint client master worker 1 che

  19. Slide 19: Improved MapReduce and MPI

    Slide 19: Improved MapReduce and MPI

    Implementation of continuation-based checkpointing Feliss: distributed computing framework with continuation-based checkpointing Distributed checkpointing Improved MapReduce and MPI Evaluation and related work 19

  20. Slide 20: Improved MapReduce

    Slide 20: Improved MapReduce

    Improved MapReduce Similar to original MapReduce – map, reduce, partition and combine functions Difference: – MapReduces can be connected through memory – these functions can access to arbitrary distributed variables, which leads to more flexible computation Map Reduce Map Reduce HDFS Map Reduce Map

  21. Slide 21: MPI (Message Passing Interface)

    Slide 21: MPI (Message Passing Interface)

    MPI (Message Passing Interface) • With MPI, matrix operations can be efficiently written, which are commonly used in machine learning algorithms • Continuation of the top level MPI function is sent to all the workers to realize SPMD – the function is same as the usual MPI program • Can be used with

  22. Slide 22: Evaluation and related work

    Slide 22: Evaluation and related work

    Implementation of continuation-based checkpointing Feliss: distributed computing framework with continuation-based checkpointing Distributed checkpointing Improved MapReduce and MPI Evaluation and related work 22

  23. Slide 23: Evaluation (1/2)

    Slide 23: Evaluation (1/2)

    Evaluation (1/2) • Compared checkpointing time and size with BLCR, which saves entire memory image (one server) • The program holds std::map with 20 million data • 5.3 times faster and 5.6 times smaller than BLCR 23

  24. Slide 24: Evaluation (2/2)

    Slide 24: Evaluation (2/2)

    Evaluation (2/2) Compared speed of Feliss with other frameworks (18 servers/72 CPU) Application Input used functionality compared with Word Count (WC) English Wikipedia MapReduce Hadoop Logistic Regression (LR) 20GB of vector RPC Spark LU decomposition (LU) 4320 x 4320 MPI Latent semantic analysis (

  25. Slide 25: Related work

    Slide 25: Related work

    Related work • Checkpointing – BLCR, Libckpt, Condor, etc. save entire memory – Method proposed by Cores et al. saves only live variables with the help of a compiler • Our method does not require special compiler • Distributed computing framework – Haloop, Twister, and Spark only support limited com

  26. Slide 26: Conclusion

    Slide 26: Conclusion

    Conclusion • Proposed continuation-based checkpointing – only saves necessary memory without specifying variables explicitly • Implemented distributed computing framework called Feliss using it – confirmed that Feliss is much faster than existing frameworks • Future work – improve checkpointing perf

  27. Slide 27: Backup

    Slide 27: Backup

    Backup 27

  28. Slide 28: Performance of checkpointing and restarting

    Slide 28: Performance of checkpointing and restarting

    Performance of checkpointing and restarting • Checkpointing time: time to take one checkpoint • Restarting time: time to restart from failure Both are short enough with these applications 28

  29. Slide 29: Scalability

    Slide 29: Scalability

    Scalability • WC, LR and LDA shows good scalability • Scalability of LU and LSA was lower, because they hit the hardware limit of network bandwidth – would be improved with better network like 10G Ethernet or InfiniBand, instead of Gigabit Ethernet 29

Source: Internet Archive copy of jpn.nec.com

More decks from NEC Corporation

All 25 NEC decks