Parallelize blocking (Fingerprinter)

[fjsj]

AFAIK, Fingerprinter.__call__ is embarrassingly parallel: you just need to partition your records by the number of CPUs you have, call Fingerprinter.__call__ for each partition, then reduce write results to single blocking_map table.

Currently that's left for the implementer to do. Isn't that something the library could do, considering it already has a num_cores parameter? I could help with this.

I've found #305 but it's too old. That issue mentions message passing costs. But for DB-based "big dedupe" applications, that's not an issue since data isn't at main memory. Each worker process can read its own partition of data from the DB.

Even if we decide the library won't do that by default, maybe we should update "big dedupe" DB-based examples like pgsql_big_dedupe_example.py to parallelize blocking?

[fgregg]

i'd welcome a PR that showed substantial improvement.

In the exploration in #305, the message passing has to do with the way that multiprocessing typically works in python.

some process has to pass data to worker processes to work on. the way this is typically done is through the feeder process pickling the data objects and the worker process unpickling it. the workers output is similarly sent to the collector process.

that pickling and unpickling can have a lot of overhead.

you are very right that if you have a DB, then you could dispense with this and have every worker both read and write to the DB independently.

That's a good idea, but the dedupe library doesn't know anything about databases.

So, tldr, I'd welcome a PR that parallelizes the dedupe library's fingerprinting. I'd need to see evidence of improvement.

If there's not improvement (or even if there is), I'd welcome a PR against big_dedupe_example.

[fgregg]

as an aside, it would be very interesting to make a new library specifically work databases that subclassed the dedupe library, maybe backed by sqlalchemy but with method that could be specialized to the database engine.

[fjsj]

RE: PRs
Your concerns make sense to me. I'll explore both ideas: first I'll try parallelizing at the library level. In case that doesn't prove to be general enough, I'll make a PR against big_dedupe_example only. Thanks for the input!

RE: new DB-based library, that sounds great.

[fjsj]

About parallelizing at library level, a problem I had forgot about: index predicates.
Each process will need it's own copy of the indexes. This can easily blow memory up.
Also, I think one cannot pass the index predicates right now to other processes because they overwrite __getstate__ to clear the indexes.

I'm successfully using parallel blocking on Postgres-based projects, but I don't use index predicates on them.

I can try a middle-ground solution: parallelize only non-index predicates, and run index predicates in the main process. Please LMK if that sounds not worthy to try.

[fgregg]

#856 would be a good way around that.

[fgregg]

anyway, as a next step, you plan makes sense, Flávio

[fjsj]

Confirmed again the serialization and message passing costs make the parallel version slower than the sequential one. Tested with pgsql_big_dedupe_example.py with the original 700k records. Even with 2x and 3x that number, the parallel version is still slower.

Here's the Proof of Concept code: vintasoftware@2fde5f3

IMHO it's not worth to implement this in main library. I'll work on a version for the pgsql_big_dedupe_example.py to support the future DB-specialized Dedupe version. By having each process read, process, and write in parallel, it should be faster.

[fjsj]

PR ready: dedupeio/dedupe-examples#114

[fgregg]

@fjsj, there are two points of inteprocess communication

1. move the the records to the child process to block
2. move the block keys to the parent process

if the record and blocks keys are both stored on disk or on a database, then there's a good path to having the child worker be responsible for reading records, blocking, and writing the blocking keys out. that's definitely the best case for taking advantage of parallelization

but, in the general case, in the library, we have a stream of records, and, so we must have some degree of interprocess communication to shift those records to a child blocking process

however, right now we are using sqlite to store the blocking keys. i wonder if we could have an interprocess communication of records, but have the child process be responsible for both blocking and writing.

In that world, is parallelization beneficial, or is that still too much IPC?

[fgregg]

i looked at this in a spike 5926046

it was still slower than not.

[fjsj]

@fgregg I made some comments on 5926046.

I agree reading and writing from child/blocker workers seems the best. But unless all records are already saved on the DB, I think parallelization will be slower when streaming. When streaming records, probably the writer process won't be able to write as fast as all child process reads, especially when using several cores.

[nrajasek1]

About parallelizing at library level, a problem I had forgot about: index predicates.
Each process will need it's own copy of the indexes. This can easily blow memory up.
Also, I think one cannot pass the index predicates right now to other processes because they overwrite __getstate__ to clear the indexes.

I'm successfully using parallel blocking on Postgres-based projects, but I don't use index predicates on them.

I can try a middle-ground solution: parallelize only non-index predicates, and run index predicates in the main process. Please LMK if that sounds not worthy to try.

Can you expalin a bit on "but I don't use index predicates on them." means? can you able to share the prototype how you implemented successfully?

Thanks in Advance
Naga

[fjsj]

@nrajasek1 Check: dedupeio/dedupe-examples#114