Joe, This is what I use for a related problem, using pure HDFS [no HBase]:
1. Run a one-time map-reduce job where you input your current historical file of hashes [say it is of the format <hash-key, hash-value> in some kind of flat file] using IdentityMapper and the output of your custom reducer is <key, value> is <hash-key, hash-value> or maybe even <hash-key, dummy value> to save space. The important thing is to use MapFileOutputFormat for the reducer output instead of the typical SequenceFileOutputFormat. Now you have a single look-up table which you use for efficient lookup using your hash keys. Note down the HDFS path of where you stored this mapfile, call it dedupMapFile. 2. In your incremental data update job, pass the HDFS path of dedupMapFile to your conf, then open the mapfile in your reducer configure(), store the reference to the mapfile in the class, and close it in close(). Inside your reduce(), use the mapfile reference to lookup your hashkey; if there is a hit, it is a dup. 3. Also, for your reducer in 2. above, you can use a multiple output format custom format, in which one of the outputs is your current output, and the other is a new dedup output sequencefile which is in the same key-value format as the dedupMapFile. So in the reduce() if the current key value is a dup, discard it, else output to both your regular output, and the new dedup output. 4. After each incremental update job, run a new map reduce job [IdentityMapper and IdentityReducer] to merge the new dedup file with your old dedupMapFile, resulting in the updated dedupMapFile. Some comments: * I didn't read your approach too closely, so I suspect you might be doing something essentially like this already. * All this stuff is basically what HBase does for free, where your dedupMapFile is now a HBase table, and you don't have to run Step 4, since you can just write new [non-duplicate] hash-keys to the HBase table in Step 3, and in Step 2, you just use table.exists(hash-key) to check if it is a dup. You still need Step 1 to populate the table with your historical data. Hope this helps.... Cheers, jp -----Original Message----- From: Joseph Stein [mailto:crypt...@gmail.com] Sent: Thursday, March 25, 2010 11:35 AM To: common-user@hadoop.apache.org Subject: Re: DeDuplication Techniques The thing is I have to check historic data (meaning data I have already aggregated against) so I basically need to hold and read from a file of hashes. So within the current data set yes this would work but I then have to open a file, loop through the value, see it is not there. If it is there then throw it out, if not there add it to the end. To me this opening a file checking for dups is a map/reduce task in itself. What I was thinking is having my mapper take the data I wasn to validate as unique. I then loop through the files filters. each data point has a key that then allows me to get the file that has it's data. e.g. a part of the data partions the hash of the data so each file holds. So my map job takes the data and breaks it into the key/value pair (the key allows me to look up my filter file). When it gets to the reducer... the key is the file I open up, I then open the file... loop through it... if it is there throw the data away. if it is not there then add the hash of my data to the filter file and then output (as the reduce output) the value of the unique. This output of the unique is then the data I aggregate on which also updated my historic filter so the next job (5 minutes later) see it, etc. On Thu, Mar 25, 2010 at 2:25 PM, Mark Kerzner <markkerz...@gmail.com> wrote: > Joe, > > what about this approach: > > using hashmap values as your keys in MR maps. Since they are sorted by keys, > in reducer you will get all duplicates together, so that you can loop > through them. As the simplest solution, you just take the first one. > > Sincerely, > Mark > > On Thu, Mar 25, 2010 at 1:09 PM, Joseph Stein <crypt...@gmail.com> wrote: > >> I have been researching ways to handle de-dupping data while running a >> map/reduce program (so as to not re-calculate/re-aggregate data that >> we have seen before[possibly months before]). >> >> The data sets we have are littered with repeats of data from mobile >> devices which continue to come in over time (so we may see duplicates >> of data re-posted months after it originally posted...) >> >> I have 2 ways so far I can go about it (one way I do in production >> without Hadoop) and interested to see if others have faced/solved this >> in Hadoop/HDFS and what their experience might be. >> >> 1) handle my own hash filter (where I continually store and look up a >> hash (MD5, bloom, whatever) of the data I am aggregating on as >> existing already). We do this now without Hadoop perhaps a variant >> can be ported into HDFS as map task, reducing the results to files and >> restoring the hash table (maybe in Hive or something, dunno yet) >> 2) push the data into Cassandra (our NoSQL solution of choice) and let >> that hash/map system do it for us. As I get more into Hadoop looking >> at HBas is tempting but then just one more thing to learn. >> >> I would really like to not have to reinvent a wheel here and even >> contribute if something is going on as it is a use case in our work >> effort. >> >> Thanx in advance =8^) Apologize I posted this on common dev yesterday >> by accident (so this is not a repost spam but appropriate for this >> list) >> >> Cheers. >> >> /* >> Joe Stein >> http://www.linkedin.com/in/charmalloc >> */ >> > -- /* Joe Stein http://www.linkedin.com/in/charmalloc */
