8 ms·

"and the real contribution from Google in this area was arguably GFS, not Map-Reduce" This, a million times over. Map-reduce is not difficult to implement. I

by timr 12y ago

"and the real contribution from Google in this area was arguably GFS, not Map-Reduce" This, a million times over. Map-reduce is not difficult to implement. Implementing a distributed, petabyte-scale filesystem to hold the data being accessed by thousands of workers is what's difficult. It's just a shame that Hadoop (and HDFS) are what we're saddled with in the outside world. They're a total disaster area, from configuration difficulty to memory usage to speed to monitoring. But since HDFS is the only commonly used distributed FS, you're pretty much bound to Hadoop (and the rest of the horrible Apache ecosystem). The world needs a good, stable, well-written distributed filesystem (ideally, one not written in a bloated language designed for remote controls and set-top boxes).

wyager 12y ago
>ideally, one not written in a bloated language designed for remote controls and set-top boxes I don't know what you'd have to be smoking to use Java in a remote control.
- riffraff 12y ago
  java was designed for that http://en.wikipedia.org/wiki/Oak_(programming_language) http://en.wikipedia.org/wiki/Oak_(programming_language)
  - e12e 12y ago
    Indeed. And it runs today (on among other things) sim cards. See eg: "Defcon 21 - The Secret Life of SIM Cards" https://www.youtube.com/watch?v=31D94QOo2gY https://www.youtube.com/watch?v=31D94QOo2gY
  - wyager 12y ago
    I know. My comment still stands.
    - tptacek 12y ago
      It really doesn't, in that it doesn't actually build an argument of any sort.
      - wyager 12y ago
        Didn't think I needed to! Seemed self-evident enough. How's this: Java is a high-level language designed for heavy usage of dynamic allocation and related features (like GC). Remote controls, being very simple devices that benefit strongly from low power consumption, tend to be designed with low-resource microcontrollers. These devices are not generally capable of managing the entire java feature set. Therefore, to use java on a remote control, you must either use an unnecessarily complex microcontroller, or a crippled subset of Java, in which case you might as well use C or something.
        tptacek 12y ago
        Java is not "designed for heavy usage of dynamic allocation". You're confusing the language, the runtime, and the reference JVM. The HotSpot-derived reference JVM is certainly not an embedded design, but the reference JVM looks nothing like (for instance) Javacard.
        wyager 12y ago
        > Java is not "designed for heavy usage of dynamic allocation". How, exactly, would you port the entire java core language to a platform without dynamic allocation? There exist subsets of java that work without it, but they're essentially not the same language at that point.
        tptacek 12y ago
        That's silly. A huge fraction of all C libraries rely on dynamic allocation, and so following your logic, C isn't an embedded programming language, despite being the lingua franca of embedded programming. As for "how you'd 'port' Java to such an environment", again, look at Javacard.
EdwardDiego 12y ago
> (ideally, one not written in a bloated language designed for remote controls and set-top boxes). Oh cool, subjective language argument time!
- deleted 12y ago
  [deleted]
staunch 12y ago
I think MogileFS is closest to being what most people need. I'd love to see a Go version with all the lessons learned from that project. https://code.google.com/p/mogilefs/ https://code.google.com/p/mogilefs/
- deleted 12y ago
  [deleted]
- qohen 12y ago
  What about Nokia's Disco project, which uses Erlang and Python? http://discoproject.org/ http://discoproject.org/ From http://disco.readthedocs.org/en/develop/intro.html http://disco.readthedocs.org/en/develop/intro.html What is Disco? Disco is an implementation of mapreduce for distributed computing. Disco supports parallel computations over large data sets, stored on an unreliable cluster of computers, as in the original framework created by Google. This makes it a perfect tool for analyzing and processing large data sets, without having to worry about difficult technicalities related to distribution such as communication protocols, load balancing, locking, job scheduling, and fault tolerance, which are handled by Disco. Disco can be used for a variety data mining tasks: large-scale analytics, building probabilistic models, and full-text indexing the Web, just to name a few examples. Batteries included The Disco core is written in Erlang, a functional language that is designed for building robust fault-tolerant distributed applications. Users of Disco typically write jobs in Python, which makes it possible to express even complex algorithms with very little code.
  - deleted 12y ago
    [deleted]
- rdtsc 12y ago
  I am more exited about a newer one -- LeoFS http://leo-project.net/leofs/ http://leo-project.net/leofs/ all open source. They started with S3 compatible API and are adding multi-data-center replication and NFS support.
random3 12y ago
First, I don't believe that Map-Reduce is not used inside Google anymore. Second, the map-reduce pattern is actually very useful basic, common computation. It's equivalent to the SQL JOIN and it's not something that you can really do without. Perhaps the large chunk (batch) approach is not ideal for many of the use-cases Map-Reduce is being tried with (e.g. like "interactive" querying with Pig or Hive). But that doesn't mean it's not useful. If you're optimizing for throughput you'll generally want to read/process in the batches optimized for some underlying sizes (it could be page size, it could be blocks, etc.). Also a system is a lot more than just the compute framework. It needs to deal with various inputs/outputs, do scheduling, etc. Between the distributed storage and the distributed processing, I'm not sure it's easy to decide which one could be more difficult, either. Saying that Hadoop is a disaster, is not far from saying we live in an awful world. Working with them for years doesn't make me the most objective person, however, given the huge adoption, I'd say they may not be that bad. More, using something like Cloudera Manager makes it trivial (which sometimes makes me wonder why the vanilla version hasn't been improved...) (BTW there's QFS and other distributed file systems). I wonder why is the Apache ecosystem horrible? I get it that you don't like Java. Fair enough. What would be your language of choice for the next gen, stable distributed file system? Go, Rust, JavaScript?
- deleted 12y ago
  [deleted]
- wyager 12y ago
  >What would be your language of choice for the next gen, stable distributed file system? Here's my heavily biased subjective opinion on this entirely hypothetical software: I think we should do one or both of two things: A) Do it in very clean, fast, simple C. Put an emphasis on speed and simplicity. B) Do it in very reliable, secure, simple Haskell. Put an emphasis on correctness and simplicity. With some effort, the C one could be correct and the Haskell one could be fast. I mention these two languages because they compile to native code and have very good cross-platform support. You won't have any trouble running either of these on embedded devices (which I can't say for Java or Go. Go has some weird compiler bugs on ARM platforms, and the JVM is frequently too memory intensive for embedded). C has an advantage of allowing the absolute minimal implementation, and Haskell has an advantage of allowing a massively concurrent implementation. Yada yada yada Of course, it could be that the question is completely irrelevant. Just define a spec for a DFS, and then let different implementations pop up in whatever language is best suited to that implementation's specific details.
EGreg 12y ago
Why s it difficult to build a distributed, petabyte scale filesystem? Isn't the search through indexes easily partitionable horizontally? Is it a problem of eventual consistency? I am not sure what the huge issue is and would like to learn.
- karamazov 12y ago
  Dealing with frequent machine failure is one major issue, for example. The original GFS and MapReduce papers (http://static.googleusercontent.com/media/research.google.com/en/us/archive/gfs-sosp2003.pdf http://static.googleusercontent.com/media/research.google.co... and http://research.google.com/archive/mapreduce.html http://research.google.com/archive/mapreduce.html) go into detail.
- gatehouse 12y ago
  Well, one key element of the original map-reduce paper is the way the data is spread around. Instead of building a giant NAS with specialized (expensive) systems, and then building a bunch of specialized (expensive) compute systems, and then shipping massive quantities of data around on fast (expensive) network, the map-reduce system is built on a bunch of well balanced systems in terms of CPU/ram vs. disk, and the job is designed in a way that it can be distributed to these systems and data transfer is minimized. So in a way, everything is happening in the storage nodes and they need to be much more than just a filesystem.
- vidarh 12y ago
  It's "trivial" to build a distributed, petabyte scale filesystem. It's hard to build a cost-effective, reliable and fast distributed, petabyte scale filesystem that's suitable for a wide range of workloads. Consider that you need to minimise the amount of copies of data to keep costs reasonable, yet the fewer copies of data, the lower your IO capacity for accessing that data is (since readers/writers will content for the IO capacity of a small number of storage nodes), so you want to maximise the number of copies of data to maximise throughout. Yet the higher number of copies to maintain, the more IO it takes to spread each write out through your storage network. Soon enough you start running into "fun" problems such not being able to naively push writes out to each storage server it is meant to go to for data that needs to be replicated widely, because you'll be bandwidth constrained, but instead needing a fan-out even for simple writes. You'll also want to minimise operational headaches; a disk going dead or an entire server failing needs to be handled transparently, as every additional disk or server you add increases the odds of a failure per any unit of tim. (Compare with the naive approach for just a 1PB system: I can "easily" get about 200TB per off-the shelf storage server with hardware RAID. Lets say 150TB usable space; get about 14 of them to let you replicate stuff across two servers, and put GlusterFS on it. It'll work. It'll also be expensive, horribly slow for a number of workloads, and a regular disk replacement nightmare)
dsymonds 12y ago
MapReduce is difficult to implement well. It's just ironic that the hard part is the part that's not in the name: the shuffle phase.
- srean 12y ago
  Heartily agreed ! Or at least Hadoop does it poorly. It is really that bad. I say this with hesitation and a lot of reluctance, its an open source project, I have not contributed anything towards it, so it is really unfair of me to complain. Here is my personal experience with these tools at Google and at Yahoo (lightly edited from an old comment) == I have had the opportunity to try out Google's implementation of mapreduce implemented in C++ way back in time (6 years ago). These would run on fairly impoverished processors, essentially laptop grade of that time. Have done stuff on Yahoo's Hadoop setup as well, these used high end multicore machines provisioned with oodles of RAM. If I were to be generous, Hadoop ran 4 times slower as measured by wall clock times. Not only that, Hadoop required about 4 times more memory for similar sized jobs. So you ended up requiring more RAM, running for longer and potentially burning more electricity. This is by no means a benchmark or anything like that, just an anecdote. That Hadoop would require much more memory did not surprise me, that was expected. What was really surprising was that it was so much slower. Four times might not seem like much, but I was being generous to Hadoop. It makes a big difference when you can make multiple run through the data in a single day and make changes to the code/model. Debugging and ironing out issues is a lot more efficient when your iteration loop is shorter. I think Hadoop (by virtue of its comparative crappiness) gave Google a significant competitive edge over the rest, probably still does.
- timr 12y ago
  A big part of implementing the shuffle correctly at a large scale is having a good distributed filesystem upon which to build.
  - dsymonds 12y ago
    Sure. I didn't mean to imply a good distributed FS was unnecessary or easy. Just saying that MR isn't easy.
mukundmr 12y ago
What about the Cassandra Distributed File System? It probably doesn't scale as much as HDFS though.
necubi 12y ago
Let me suggest the Quantcast File System (QFS) [0]. It's much closer to GFS as described in the paper (crucially it uses Reed-Solomon encoding to reduce storage requirements), it's highly tunable to different workloads, and it's written in C++. Quantcast uses it to store petabytes of data and for running map reduce. Unfortunately it hasn't seen much uptake outside of Quantcast, despite being a clear improvement over HDFS. [0] http://quantcast.github.io/qfs/ http://quantcast.github.io/qfs/ (Disclaimer: I used to work for Quantcast).
- jwr 12y ago
  Reed-Solomon for forward error correction, to provide redundancy? But isn't Reed-Solomon really geared towards single-bit errors, while in the real world our storage tends to fail with multiple missing blocks? I thought erasure codes were a much better approach.
  - necubi 12y ago
    It's not used for tolerating disk errors (typically in a production context you have RAID for that, and failures tend to be for the entire disk). It's used to reduce storage requirements via striping. See the QFS paper (http://db.disi.unitn.eu/pages/VLDBProgram/pdf/industry/p808-ovsiannikov.pdf http://db.disi.unitn.eu/pages/VLDBProgram/pdf/industry/p808-...) for a good description of how this works. The basic idea is that with RS you can get 3x replication by splitting the data into 6 pieces stored on different servers, plus three parity blocks. This requires 1.5x storage rather than 3x while still tolerating the loss of any three machines of the nine.
    - erikano 12y ago
      >[T]ypically in a production context you have RAID for that, and failures tend to be for the entire disk[.] Does QFS run in addition to other file systems on the storage nodes or does it manage disks directly? You see, I was thinking that maybe ZFS + QFS might be a good idea and would like to know if it's possible. Also, is QFS available for FreeBSD and/or SmartOS storage nodes and clients? How about CoreOS and Debian, are storage nodes and clients available for those?

by timr 12y ago

wyager 12y ago

>ideally, one not written in a bloated language designed for remote controls and set-top boxes I don't know what you'd have to be smoking to use Java in a remote control.

riffraff 12y ago
java was designed for that http://en.wikipedia.org/wiki/Oak_(programming_language) http://en.wikipedia.org/wiki/Oak_(programming_language)
- e12e 12y ago
  Indeed. And it runs today (on among other things) sim cards. See eg: "Defcon 21 - The Secret Life of SIM Cards" https://www.youtube.com/watch?v=31D94QOo2gY https://www.youtube.com/watch?v=31D94QOo2gY
- wyager 12y ago
  I know. My comment still stands.
  - tptacek 12y ago
    It really doesn't, in that it doesn't actually build an argument of any sort.
    - wyager 12y ago
      Didn't think I needed to! Seemed self-evident enough. How's this: Java is a high-level language designed for heavy usage of dynamic allocation and related features (like GC). Remote controls, being very simple devices that benefit strongly from low power consumption, tend to be designed with low-resource microcontrollers. These devices are not generally capable of managing the entire java feature set. Therefore, to use java on a remote control, you must either use an unnecessarily complex microcontroller, or a crippled subset of Java, in which case you might as well use C or something.
      - tptacek 12y ago
        Java is not "designed for heavy usage of dynamic allocation". You're confusing the language, the runtime, and the reference JVM. The HotSpot-derived reference JVM is certainly not an embedded design, but the reference JVM looks nothing like (for instance) Javacard.
        wyager 12y ago
        > Java is not "designed for heavy usage of dynamic allocation". How, exactly, would you port the entire java core language to a platform without dynamic allocation? There exist subsets of java that work without it, but they're essentially not the same language at that point.
        tptacek 12y ago
        That's silly. A huge fraction of all C libraries rely on dynamic allocation, and so following your logic, C isn't an embedded programming language, despite being the lingua franca of embedded programming. As for "how you'd 'port' Java to such an environment", again, look at Javacard.

EdwardDiego 12y ago

> (ideally, one not written in a bloated language designed for remote controls and set-top boxes). Oh cool, subjective language argument time!

deleted 12y ago
[deleted]

staunch 12y ago

I think MogileFS is closest to being what most people need. I'd love to see a Go version with all the lessons learned from that project. https://code.google.com/p/mogilefs/ https://code.google.com/p/mogilefs/

deleted 12y ago
[deleted]
qohen 12y ago
What about Nokia's Disco project, which uses Erlang and Python? http://discoproject.org/ http://discoproject.org/ From http://disco.readthedocs.org/en/develop/intro.html http://disco.readthedocs.org/en/develop/intro.html What is Disco? Disco is an implementation of mapreduce for distributed computing. Disco supports parallel computations over large data sets, stored on an unreliable cluster of computers, as in the original framework created by Google. This makes it a perfect tool for analyzing and processing large data sets, without having to worry about difficult technicalities related to distribution such as communication protocols, load balancing, locking, job scheduling, and fault tolerance, which are handled by Disco. Disco can be used for a variety data mining tasks: large-scale analytics, building probabilistic models, and full-text indexing the Web, just to name a few examples. Batteries included The Disco core is written in Erlang, a functional language that is designed for building robust fault-tolerant distributed applications. Users of Disco typically write jobs in Python, which makes it possible to express even complex algorithms with very little code.
- deleted 12y ago
  [deleted]
rdtsc 12y ago
I am more exited about a newer one -- LeoFS http://leo-project.net/leofs/ http://leo-project.net/leofs/ all open source. They started with S3 compatible API and are adding multi-data-center replication and NFS support.

random3 12y ago

First, I don't believe that Map-Reduce is not used inside Google anymore. Second, the map-reduce pattern is actually very useful basic, common computation. It's equivalent to the SQL JOIN and it's not something that you can really do without. Perhaps the large chunk (batch) approach is not ideal for many of the use-cases Map-Reduce is being tried with (e.g. like "interactive" querying with Pig or Hive). But that doesn't mean it's not useful. If you're optimizing for throughput you'll generally want to read/process in the batches optimized for some underlying sizes (it could be page size, it could be blocks, etc.). Also a system is a lot more than just the compute framework. It needs to deal with various inputs/outputs, do scheduling, etc. Between the distributed storage and the distributed processing, I'm not sure it's easy to decide which one could be more difficult, either. Saying that Hadoop is a disaster, is not far from saying we live in an awful world. Working with them for years doesn't make me the most objective person, however, given the huge adoption, I'd say they may not be that bad. More, using something like Cloudera Manager makes it trivial (which sometimes makes me wonder why the vanilla version hasn't been improved...) (BTW there's QFS and other distributed file systems). I wonder why is the Apache ecosystem horrible? I get it that you don't like Java. Fair enough. What would be your language of choice for the next gen, stable distributed file system? Go, Rust, JavaScript?

deleted 12y ago
[deleted]
wyager 12y ago
>What would be your language of choice for the next gen, stable distributed file system? Here's my heavily biased subjective opinion on this entirely hypothetical software: I think we should do one or both of two things: A) Do it in very clean, fast, simple C. Put an emphasis on speed and simplicity. B) Do it in very reliable, secure, simple Haskell. Put an emphasis on correctness and simplicity. With some effort, the C one could be correct and the Haskell one could be fast. I mention these two languages because they compile to native code and have very good cross-platform support. You won't have any trouble running either of these on embedded devices (which I can't say for Java or Go. Go has some weird compiler bugs on ARM platforms, and the JVM is frequently too memory intensive for embedded). C has an advantage of allowing the absolute minimal implementation, and Haskell has an advantage of allowing a massively concurrent implementation. Yada yada yada Of course, it could be that the question is completely irrelevant. Just define a spec for a DFS, and then let different implementations pop up in whatever language is best suited to that implementation's specific details.

EGreg 12y ago

Why s it difficult to build a distributed, petabyte scale filesystem? Isn't the search through indexes easily partitionable horizontally? Is it a problem of eventual consistency? I am not sure what the huge issue is and would like to learn.

karamazov 12y ago
Dealing with frequent machine failure is one major issue, for example. The original GFS and MapReduce papers (http://static.googleusercontent.com/media/research.google.com/en/us/archive/gfs-sosp2003.pdf http://static.googleusercontent.com/media/research.google.co... and http://research.google.com/archive/mapreduce.html http://research.google.com/archive/mapreduce.html) go into detail.
gatehouse 12y ago
Well, one key element of the original map-reduce paper is the way the data is spread around. Instead of building a giant NAS with specialized (expensive) systems, and then building a bunch of specialized (expensive) compute systems, and then shipping massive quantities of data around on fast (expensive) network, the map-reduce system is built on a bunch of well balanced systems in terms of CPU/ram vs. disk, and the job is designed in a way that it can be distributed to these systems and data transfer is minimized. So in a way, everything is happening in the storage nodes and they need to be much more than just a filesystem.
vidarh 12y ago
It's "trivial" to build a distributed, petabyte scale filesystem. It's hard to build a cost-effective, reliable and fast distributed, petabyte scale filesystem that's suitable for a wide range of workloads. Consider that you need to minimise the amount of copies of data to keep costs reasonable, yet the fewer copies of data, the lower your IO capacity for accessing that data is (since readers/writers will content for the IO capacity of a small number of storage nodes), so you want to maximise the number of copies of data to maximise throughout. Yet the higher number of copies to maintain, the more IO it takes to spread each write out through your storage network. Soon enough you start running into "fun" problems such not being able to naively push writes out to each storage server it is meant to go to for data that needs to be replicated widely, because you'll be bandwidth constrained, but instead needing a fan-out even for simple writes. You'll also want to minimise operational headaches; a disk going dead or an entire server failing needs to be handled transparently, as every additional disk or server you add increases the odds of a failure per any unit of tim. (Compare with the naive approach for just a 1PB system: I can "easily" get about 200TB per off-the shelf storage server with hardware RAID. Lets say 150TB usable space; get about 14 of them to let you replicate stuff across two servers, and put GlusterFS on it. It'll work. It'll also be expensive, horribly slow for a number of workloads, and a regular disk replacement nightmare)

dsymonds 12y ago

MapReduce is difficult to implement well. It's just ironic that the hard part is the part that's not in the name: the shuffle phase.

srean 12y ago
Heartily agreed ! Or at least Hadoop does it poorly. It is really that bad. I say this with hesitation and a lot of reluctance, its an open source project, I have not contributed anything towards it, so it is really unfair of me to complain. Here is my personal experience with these tools at Google and at Yahoo (lightly edited from an old comment) == I have had the opportunity to try out Google's implementation of mapreduce implemented in C++ way back in time (6 years ago). These would run on fairly impoverished processors, essentially laptop grade of that time. Have done stuff on Yahoo's Hadoop setup as well, these used high end multicore machines provisioned with oodles of RAM. If I were to be generous, Hadoop ran 4 times slower as measured by wall clock times. Not only that, Hadoop required about 4 times more memory for similar sized jobs. So you ended up requiring more RAM, running for longer and potentially burning more electricity. This is by no means a benchmark or anything like that, just an anecdote. That Hadoop would require much more memory did not surprise me, that was expected. What was really surprising was that it was so much slower. Four times might not seem like much, but I was being generous to Hadoop. It makes a big difference when you can make multiple run through the data in a single day and make changes to the code/model. Debugging and ironing out issues is a lot more efficient when your iteration loop is shorter. I think Hadoop (by virtue of its comparative crappiness) gave Google a significant competitive edge over the rest, probably still does.
timr 12y ago
A big part of implementing the shuffle correctly at a large scale is having a good distributed filesystem upon which to build.
- dsymonds 12y ago
  Sure. I didn't mean to imply a good distributed FS was unnecessary or easy. Just saying that MR isn't easy.

mukundmr 12y ago

What about the Cassandra Distributed File System? It probably doesn't scale as much as HDFS though.

necubi 12y ago

Let me suggest the Quantcast File System (QFS) [0]. It's much closer to GFS as described in the paper (crucially it uses Reed-Solomon encoding to reduce storage requirements), it's highly tunable to different workloads, and it's written in C++. Quantcast uses it to store petabytes of data and for running map reduce. Unfortunately it hasn't seen much uptake outside of Quantcast, despite being a clear improvement over HDFS. [0] http://quantcast.github.io/qfs/ http://quantcast.github.io/qfs/ (Disclaimer: I used to work for Quantcast).

jwr 12y ago
Reed-Solomon for forward error correction, to provide redundancy? But isn't Reed-Solomon really geared towards single-bit errors, while in the real world our storage tends to fail with multiple missing blocks? I thought erasure codes were a much better approach.
- necubi 12y ago
  It's not used for tolerating disk errors (typically in a production context you have RAID for that, and failures tend to be for the entire disk). It's used to reduce storage requirements via striping. See the QFS paper (http://db.disi.unitn.eu/pages/VLDBProgram/pdf/industry/p808-ovsiannikov.pdf http://db.disi.unitn.eu/pages/VLDBProgram/pdf/industry/p808-...) for a good description of how this works. The basic idea is that with RS you can get 3x replication by splitting the data into 6 pieces stored on different servers, plus three parity blocks. This requires 1.5x storage rather than 3x while still tolerating the loss of any three machines of the nine.
  - erikano 12y ago
    >[T]ypically in a production context you have RAID for that, and failures tend to be for the entire disk[.] Does QFS run in addition to other file systems on the storage nodes or does it manage disks directly? You see, I was thinking that maybe ZFS + QFS might be a good idea and would like to know if it's possible. Also, is QFS available for FreeBSD and/or SmartOS storage nodes and clients? How about CoreOS and Debian, are storage nodes and clients available for those?