Modeling for "Update if Current" strategy?

[Felix E. Klee]

I have a construction game, where people add blocks, one at a time, and
according to certain rules.

Now, when a user adds a block, I want to add it only to the database if
its position matches certain construction rules.

As a complete newbie to MongoDB, I wonder how to model that.

My idea:

* Instead of making a collection of blocks, I create a construction
collection with a single document, and an array `blocks`:

db.constructions.insert({blocks: [[1, 0, 0], [1, 1, 0]]})

* To add a new block, I use the "Update if Current" strategy [1]:

1. Get construction (there is only one):

construction = db.constructions.findOne()

2. Make a backup of the blocks:

oldBlocks = construction.blocks.slice(0)

3. Add a new block:

construction.blocks.push([3, 0, 0])

4. Check if `blocks` adheres to the game's construction rules:

// something complicated

5. If the check failed, then exit.

6. Update, unless the blocks in the database have changed:

db.constructions.update({_id: construction._id,
blocks: oldBlocks},
construction)

7. Check for status of update:

db.$cmd.findOne({getlasterror: 1});

8. If the update failed ("n": 0), then go back to step 2.

What do you think? Could I do something similar with a collection of
blocks? Isn't it ugly to have a `constructions` collection with just one
document?

[1]: http://www.mongodb.org/display/DOCS/Atomic+Operations#AtomicOperations-%22UpdateifCurrent%22

[craiggwilson]

If you are only going to have a single construction, then there might be a different way to do this, but this seems logical.  How many blocks will each construction have?

You can also use a timestamp (or version) rather than checking that blocks = oldBlocks.  Then you can just check if timestamp = oldTimestamp.  Smaller comparison most likely.  

[Felix E. Klee]

On Tue, Aug 7, 2012 at 3:33 PM, craiggwilson <craigg...@gmail.com>
wrote:

> If you are only going to have a single construction, then there might
> be a different way to do this, but this seems logical.

Yes, there will be only a single construction. Alternatively, I am
thinking about using a `construction` collection with key/value
documents:

db.construction.insert({_id: 'blocks', value: [[1, 0, 0],
[1, 1, 0]]})
db.construction.insert({_id: 'name', value: 'My Construction'})

How would you do it? Is there a standard way?

> How many blocks will [the] construction have?

Currently up to a hundred or so. But eventually there could be
thousands.

> You can also use a timestamp (or version) rather than checking that
> blocks = oldBlocks. Then you can just check if timestamp =
> oldTimestamp. Smaller comparison most likely.

Thanks - that's a good idea!

[craiggwilson]

Single construction question:  Do you mean per game, or there will always only be one construction???

[Felix E. Klee]

On Tue, Aug 7, 2012 at 4:22 PM, craiggwilson <craigg...@gmail.com>
wrote:

> Single construction question: Do you mean per game, or there will
> always only be one construction???

Only one construction in the whole app.

[craiggwilson]

I'm suspecting that mongodb might not be the right technology for this.  I mean, it will work, but it seems like just using a simple file would work much better and be way easier.  Is there any reason you are using/wanting to use mongodb for this?

[Felix E. Klee]

On Tue, Aug 7, 2012 at 6:04 PM, craiggwilson <craigg...@gmail.com>
wrote:

> I'm suspecting that mongodb might not be the right technology for
> this. I mean, it will work, but it seems like just using a simple file
> would work much better and be way easier. Is there any reason you are
> using/wanting to use mongodb for this?

Well:

* There is more data in the app. I don't want to have a new file for
each data set.

* Things need to be scalable, and performance matters, as the game
should be snappy.

* Data is used inside the app in JSON format.

* Operations on the list of blocks need to be atomic.

* etc.

If not for an app like this, then when do you need a MongoDB?

I mean, even for simple blogs or a todo list apps, people do use
MongoDB.

[craiggwilson]

Absolutely, there is a place for MongoDB and this might be it.  But what you have described is not like a simple blog or todo list.  You have described a system that has a single construction with a bunch of integers for blocks.  And every user of your system apparently works on the same construction.   You mentioned the block list could get into the thousands, this is relatively small and would fit into memory without the need of a database (and be much faster because of it).  You haven't really described a big system where you will have trouble with scale and performance yet, so...

...perhaps some more information would be helpful to use to help you model this.  You mentioned other data sets; what are they and how do they relate to the construction?  Are all these users working concurrently or do they take turns?  What is the end result?  When the game is done, does another construction begin (hence my question earlier about if there will only be one construction)?  If not and the game goes on forever, why do state only thousands of blocks?  It would seem to me that a never-ending game would have a much larger number blocks than thousands...

It is highly conceivable that you should have more than one data store, depending on the need.  If you would rather not discuss your ideas here, feel free to email me at craig....@10gen.com where we can discuss privately.

[Felix E. Klee]

On Tue, Aug 7, 2012 at 6:51 PM, craiggwilson <craigg...@gmail.com>
wrote:

> You mentioned the block list could get into the thousands, this is
> relatively small and would fit into memory

It would need to be synced to disk in real-time. Data loss (e.g. in case
the server goes down) would be problematic.

> You mentioned other data sets; what are they and how do they relate to
> the construction?

First of all, there is more data associated with a block, other than
just its coordinates.

Then there are various configuration options, which can be changed in
real-time from an admin-interface.

> Are all these users working concurrently or do they take turns?

Users work concurrently.

> If not and the game goes on forever, why do state only thousands of
> blocks?

Yes it could be more. The limit is configurable, and the plan is to
start small, then scale up. In the end there could be hundreds of
thousands of blocks, but not now. Now there will be only some hundred or
so blocks.

> It is highly conceivable that you should have more than one data
> store, depending on the need.

For later. I'm just starting out with MongoDB...

> If you would rather not discuss your ideas here, feel free to email me
> at craig....@10gen.com where we can discuss privately.

Actually, the current version of the game is Open Source. So no need to
keep things private. ;-)

Demo: http://www.RealityBuilder.com

Source, WIP: http://code.google.com/p/realitybuilder

If there are several constructions, then several apps will have to be
run.

[craiggwilson]

Cool.  Ok, so let's plan for the future a little bit instead of hamstringing at the beginning.  Documents can only store 16MB of space.  This is actually a lot of space and you probably wouldn't run out, even with hundreds of thousands of blocks, but to be safe, we should probably store the blocks elsewhere.  So here is my suggestion:

Use a mongodb collection like an event log:  When a user puts a new block up, then you store it on the blocks collection.  ObjectId's already timestamped and sort in ascending order by default.  To ensure concurrency, you'll need to use some sort of lock.  Another collection called lock would do.  It would contain a single document with a single field in it.  you'd use findAndModify (which is an atomic operation) to set that value to "locked" if it is not already in the "locked" state.  Hence, you have not retrieved a global lock.  In your application, you'd ensure that you have the lock before updating the blocks collection with a new block.  Furthermore, before placing the new block, you'll need to ensure that the aggregated value is still the same as it was when the user started placing the block (and this needs to happen after acquiring the lock).  For reading, I don't know how you are storing the aggregated blocks for the image, but likely you'd use another collection that stores that aggregated blocks current state (which gets updated when a new block is added inside the lock).

This is getting relatively complicated quickly, so just to reiterate some of my earlier statements, I think your statements about performance and scalability only relate to the reading of the data.  MongoDB can help with this.  However, if only a single person across the world can update the construction at a given time, then there is nothing scalable about the write-side.  By the rules of the game, you only need to be able to handle 1 writer.  Even if you incorporate the ability for multiple users to update the construction simultaneously if their updates do not confict, the requirements still dictate the 1 writer at a time rule because you have to handle conflicts based on committed blocks.

I'd encourage you to look at some patterns called CQRS and EventSourcing as they might help you model your business logic.

[Felix E. Klee]

On Tue, Aug 7, 2012 at 7:36 PM, craiggwilson <craigg...@gmail.com>
wrote:
> Use a mongodb collection like an event log [...] To ensure

> concurrency, you'll need to use some sort of lock. Another collection

> called lock would do. [...]

This looks like a smart solution, and it gives me quite some insight on
how to design things with MongoDB - thanks for that! However, I plan to
keep this solution for later. At the moment I want to avoid premature
optimization.

> For reading, I don't know how you are storing the aggregated blocks
> for the image

The image handling is all done separately. In fact the Reality Builder
is just a web-widget with transparent background that you may put on top
of anything you like, be it a live stream or prerecorded images.

> [...] Even if you incorporate the ability for multiple users to update

> the construction simultaneously if their updates do not confict,

My proposal *does* allow for multiple users to update the construction
simultaneously. The check in step 3 (see below) just checks that the
construction *as a whole* matches the rules.

> the requirements still dictate the 1 writer at a time rule because you
> have to handle conflicts based on committed blocks.

Naturally, one writer at a time. It's MongoDB + Node.js after all. :-)

> I'd encourage you to look at some patterns called CQRS and
> EventSourcing as they might help you model your business logic.

This is cool - thanks for the suggestions!

Finally, my original proposal updated for better efficiency:

* Initialization (block data is simplified!):

db.construction.insert({_id: 'blocksData',
version: 0,

blocks: [[1, 0, 0], [1, 1, 0]]})

* To add a new block:

1. Get blocks data:

blocksData = db.construction.findOne({_id: 'blocksData'})

2. Add a new block (e.g. `newBlock = [3, 0, 0]`):

blocksData.blocks.push(newBlock)

3. Check if `blocksData.blocks` adheres to game's rules:

// something complicated

4. If the check failed, then exit.

5. Update, unless the blocks in the database have changed:

db.construction.update({_id: 'blocksData',
version: blocksData.version},
{$inc: {version: 1},
$push: {blocks: newBlock}})

6. Check for status of update:

db.$cmd.findOne({getlasterror: 1});

7. If the update failed ("n": 0), then go back to step 1.