Application level distributed read/write lock for mongoDB

Question

I have a distributed application that uses mongoDB as a backend. The application has two collections (C1 and C2) with a M:1 relationship, so that if I delete a document in C1, I need to search C1 for any other documents that point to the same doc in C2, and if there are no matches, then delete the related doc in C2.

This obviously has the problem of race conditions that could insert new documents into C1 while the search is going on that point to the soon-to-be-deleted document in C2, resulting in DB inconsistency. Deletes can be delayed such that they could be batched up and performed once a week, say, during low load, so I'm considering writing a distributed locking system for mongo to solve the RC problem.

Questions:

1. Is there a better approach than distributed locking?
2. Does software like this already exist for Mongo? I've seen single document examples of locks, but not database level distributed locks.

UPDATE

I left this out to avoid confusing the issue, but I need to include it now. There's actually another resource (R) (essentially a file on a remote disk) that needs to be deleted along with with C2 document and C2:R is M:1. R is completely outside the mongodb ecosystem, which is why my mind jumped to locking the application so I can safely delete all this stuff. Hence the reversing links idea mentioned below won't work for this case. Yes, the system is complicated, and no, it can't be changed.

UPDATE2

My attempts to abstract away implementation details to keep the question succinct keeps biting me. Another detail: R is manipulated via REST calls to another server.

Answer 1

1. This type of problem is usually solved by embedding. So essentially C1 and C2 could be a single collection and C2 doc would embed itself into C1. Obviously this is not always possible or desirable and one of the downsides of this is data duplication. Another downside is that you would not be able to find all C2s without going through all C1s and given M:1 relationship it's not always good thing to do. So it depends if these cons are a real problem in your application.

2. Another way to handle it would be to just remove links from C1 to C2 thus leaving C2 documents to exist with no links. This could have low cost in some cases.

3. Use Two Phase Commit similar to as described here: http://docs.mongodb.org/manual/tutorial/perform-two-phase-commits/.

4. Yet another option could be to reverse your links. C2 would have an array of links that point to C1s. Each time you delete C1 you $pull from that array a link to deleted C1. Immediately after you delete from C2 with a condition that array of links is empty and its _id is what you got back from update. If race condition happens when you insert a new document into C1 and trying to update C2 and you got back result that you didn't update anything then you can either fail your insert or try to insert a new C2. Here is an example:

// Insert first doc
db.many.insert({"name": "A"});

// Find it to get an ID to show.
db.many.find();
{ "_id" : ObjectId("52eaf9e05a07ef0270a9eccc"), "name" : "A" }

// lets add a tag to it right after
db.one.update({"tag": "favorite"}, {$addToSet: {"links": ObjectId("52eaf9e05a07ef0270a9eccc")}}, {upsert: true, multi: false});

// show that tag was created and a link was added
db.one.find();
{ "_id" : ObjectId("52eafaa77365653791085540"), "links" : [  ObjectId("52eaf9e05a07ef0270a9eccc") ], "tag" : "favorite" }

// Insert one more doc which will not be tagged just for illustration
db.many.insert({"name": "B"});

// Insert last document, show IDs of all docs and tag the last document inserted: 
db.many.insert({"name": "C"});

db.many.find();
{ "_id" : ObjectId("52eaf9e05a07ef0270a9eccc"), "name" : "A" }
{ "_id" : ObjectId("52eafab95a07ef0270a9eccd"), "name" : "B" }
{ "_id" : ObjectId("52eafac85a07ef0270a9ecce"), "name" : "C" }

db.one.update({"tag": "favorite"}, {$addToSet: {"links": ObjectId("52eafac85a07ef0270a9ecce")}}, {upsert: true, multi: false});

// Now we have 2 documents tagged out of 3
db.one.find();
{ "_id" : ObjectId("52eafaa77365653791085540"), "links" : [     ObjectId("52eaf9e05a07ef0270a9eccc"),   ObjectId("52eafac85a07ef0270a9ecce") ], "tag" : "favorite" }

// START DELETE PROCEDURE
// Let's delete first tagged document
db.many.remove({"_id" : ObjectId("52eaf9e05a07ef0270a9eccc")});
// remove the "dead" link
db.one.update({"tag": "favorite"}, {$pull: {"links": ObjectId("52eaf9e05a07ef0270a9eccc")}});
// just to show how it looks now (link removed)
db.one.find();
{ "_id" : ObjectId("52eafaa77365653791085540"), "links" : [  ObjectId("52eafac85a07ef0270a9ecce") ], "tag" : "favorite" }
// try to delete a document that has no links - it's not the case here yet, so the doc is not deleted.
db.one.remove({"tag" : "favorite", "links": {$size: 0}});
db.one.find();
{ "_id" : ObjectId("52eafaa77365653791085540"), "links" : [  ObjectId("52eafac85a07ef0270a9ecce") ], "tag" : "favorite" }
// DELETE OF THE FIRST DOC IS COMPLETE, if any docs got added with
// links then the tag will just have more links

// DELETE LAST DOC AND DELETE UNREFERENCED LINK
db.many.remove({"_id" : ObjectId("52eafac85a07ef0270a9ecce")});
db.one.update({"tag": "favorite"}, {$pull: {"links": ObjectId("52eafac85a07ef0270a9ecce")}});
// no links are left
db.one.find();
{ "_id" : ObjectId("52eafaa77365653791085540"), "links" : [ ], "tag" : "favorite" }
db.one.remove({"tag" : "favorite", "links": {$size: 0}});
// LAST DOC WAS DELETED AND A REFERENCING DOC WAS DELETED AS WELL

// final look at remaining data
db.one.find();
// empty
db.many.find();
{ "_id" : ObjectId("52eafab95a07ef0270a9eccd"), "name" : "B" }

If upsert happens after you delete from one then it will just create a new doc and add a link. If it happens before then old one doc will stay and links will be updated properly.

UPDATE

Here is one way to deal with "delete file" requirements. It assumes you have POSIX compliant filesystem like ext3/ext4, many other FSs would have same properties too. For each C2 you create you should create a randomly named hard link which points to the R file. Store the path to that link in C2 doc for example. You'll end up with multiple hard links pointing to a single file. Whenever you delete a C2 you delete this hard link. Eventually when link count goes to 0 OS will delete the file. Thus there is no way you can delete the file unless you delete all hard links.

Another alternative to reversing C1<->C2 links and using FS hard links is to use multiphase commit which you can implement in any way you want.

Disclaimer: whatever mechanisms I described should work, but might contain some cases that I missed. I didn't try exactly this approach myself, but I used similar "transactional" file deletion scheme in the past successfully. So such solution I think will work but requires good testing and thinking it through will all possible scenarios.

UPDATE 2

Given all the constraints you will have to implement either multi stage commit or a some sort of locking/transaction mechanism. You can also order all your operations through a task queue which will naturally be free of race conditions (synchronous). All of these mechanisms will slow the system down a bit but you can pick granularity level of a C2 document id which is not so bad I suppose. Thus you'll still be able to run stuff in parallel with isolation on C2 id level.

One of the simple practical approaches is to use a message bus/queue.

Answer 2

If you are not using sharding, you can use TokuMX instead of MongoDB, which has support for multi-document, multi-statement transactions with atomic commit and rollback, among other nice things. These transactions work across collections and databases, so they seem like they would work for your application without many changes.

There is a full tutorial here.

Disclaimer: I am an engineer at Tokutek

Answer 3

Alek,

Have you considered moving the relationships to a different collection. You can have a collection that maps all the relationships from C1 to C2. Each document can also store a boolean indicating it is marked for collection. You can write a background task that will periodically scan this table and look for collections that have been deleted. The advantage of this model is that it is easy to detect when the collections are out of sync.

E.g. { C1_ID, [C2_ID_1, C2_ID_2....], true/false }