Friday, December 16, 2011

Basic movement game AI

I really love to play video games, and for a while I’ve been wanting to learn a bit about video game programming mainly AI and physics.
I have just read the first 20 or so pages of the good book on AI Artificial Intelligence for Games

and I though I was going to try the first easy algorithms that are explained there. So here I will introduce a little bit of the simplest way to develop the seek and arrive algorithm.
I will develop the example in Ruby using the gosu library to draw some simple characters.

The idea of the seek algorithm we are going to implement is very easy, we will control a character in the screen and another computer controlled character will seek our character on the screen and destroy him when he arrives to our character.

So the first thing to know is what is involved in a very simple movement. In the example we will not consider acceleration forces so we will have what is known as Kinematic movement. We will need 3 variables to express the characters static data at moment in time. So we can start with a Ruby module like this:

module Kinematic
 attr_reader :velocity, :orientation, :position
end
 

where all three elements are vectors. The velocity vector will give us the direction and speed of the characters, the orientation vector, in our case will simply be oriented towards the direction, so it will be the velocity vector normalized, and the position is the place where our characters are.

The orientation will also be expressed as a angle in radians using the atan2(-x,y) formula, where y and x are the corresponding coordinates in the velocity vector.

So the position and orientation will be both a function of the velocity like this:

orientation = velocity.normalize
position = velocity * time

where time is a small unit of time that will be a function of the frame rate we have. When the frame rate is bigger, the update time is smaller. It is calculated in our case something like this:

Let’s suppose our character travels at 2 meters per second, and let the frame rate be 60fps in a particular moment. then our time multiplier will be 1/60 which multiplied by 2 will be 1/30 that will be the length of our vector to be summed to the position vector in each frame. However we will change the value and adjusted to some value that makes the movement look good.

Ok so that is the basic movement, but now we need to implement the seek behaviour. The AI character will need to chase our own character in the screen, in the algorithm terminology we’ll be the target of the seek and arrive algorithm. So logically for implementing this algorithm we need both the character and the target kinematic data. We also need to specify a radius of contact (where the character catches the target) and a speed for our velocity vector.

So to our module we add this max_speed

module Kinematic
 attr_reader :velocity, :orientation, :position, :max_speed
end

We create now two classes that include this module

class Target
 include Kinematic
end
 
class Character
 include Kinematic
end

Both character and target include the module, but only the character will be AI controlled, the target will be controlled by ourselves.

So we will create the seek_and_arrive algorithm on the character, in a method that receives the character it is chasing.

First the seek part will be simply to create a velocity of speed ‘max_speed’ and direction pointing to the target’s position. Now for the arrive part we will use a ’radius of impact’ that determines when the character has actually reached the target. We will include this radius as information on the target character. So modifying the algorithm we now have:

def seek_and_arrive(target)
  @position += @velocity * @time_update
  @velocity =  target.position - position
  if  @velocity.magnitude < target.radius
 EventHandler::add_event(:capture,self,target)
end
@velocity = @velocity.normalize
@velocity *= @max_speed
@orientation = @velocity.normalize
end

As we see we are simply adding a condition and then sending an event saying that the target has been captured by the character. This event will be handled in the main loop of the game where it will show Game Over.

We will now create the graphics for the game with Gosu, I won’t explain much here as it is not the focus of the post.

The first thing, we create a character wrapper for our characters that will know about gosu, that way our original class remains graphics framework independent:

class DrawableCharacter
 attr_reader :character
 def initialize(character,window,character_img)
    @image = Gosu::Image.new(window, character_img, false)
    @character = character
 end
 
 def draw
    @image.draw_rot(@character.position[0], @character.position[1], 1, @character.orientation_in_radians)
 end
end

then we create a class for the controlled character and one for the AI Character:

class ControllableCharacter < DrawableCharacter
 def move(side)
    @character.move_ahead if side==:front
    change_velocity_according_to_side(side)
 end
 
 def change_velocity_according_to_side(side)
    return if side == :front
    if side == :right
     sin_radians = Math::sin 0.1
     cos_radians = Math::cos 0.1
    else
    sin_radians = Math::sin -0.1
    cos_radians = Math::cos -0.1
    end
    velocity_x = @character.velocity[0]*cos_radians - @character.velocity[1]*sin_radians
    velocity_y = @character.velocity[0]*sin_radians + @character.velocity[1]*cos_radians
    @character.velocity = Vector[velocity_x,velocity_y]
    @character.velocity = @character.velocity.normalize * (@character.max_speed+1)
 end
end
 
class AICharacter < DrawableCharacter
 def seek_and_arrive(target)
    @character.seek_and_arrive(target)
 end
end

The Controllable character will move depending on input from the keyboard that is captured on the main Game class. The AICharacter delagates its movement to the Character class that contains the seek_and_arrive algorithm.

Now the main Game class:

class Game < Gosu::Window
 
 def initialize
    super 1024, 768, false
    self.caption = "Seek and Arrive"
    @target = ControllableCharacter.new(Target.new(10, 10), self, 'target.gif')
    @character1 = AICharacter.new(Character.new(500, 500), self, 'character.gif')
    @game_state = :game_started
 end
 
 def manage_ai_characters
    @character1.seek_and_arrive(@target.character)
 end
 
 def manage_controllable_character
    if button_down? Gosu::KbLeft or button_down? Gosu::GpLeft then
     @target.move :left
    end
    if button_down? Gosu::KbRight or button_down? Gosu::GpRight then
     @target.move :right
    end
    if button_down? Gosu::KbUp or button_down? Gosu::GpButton0 then
     @target.move :front
    end
 end
 
 def manage_events
    EventHandler::each do |event|
     if event[0]==:capture
       @game_state = :game_over
     end
    end
 end
 
 def update
    manage_events
    if @game_state != :game_over
     manage_ai_characters()
     manage_controllable_character()
    end
 end
 
 def draw
    if @game_state != :game_over
     @target.draw
     @character1.draw
    else
     Gosu::Image.new(self, "game_over.gif", true).draw(0, 0, 0);
    end
 end
end
 
window = Game.new
window.show

The main details to get out from this code are the ‘update’ and ‘draw’ methods. The update method is called 60 times per second by default, and then the show method is called.

The full source code of the example is in github, just download and run the game.rb ruby file.

Of course this introduction is the simplest of the simplest in Game AI, but it is important information to have and very entertaining to learn.

Also of course there are libraries and frameworks that do most of the work for us, but I did this example (and hopefully some following ones) to learn the basics of how it works.

Sunday, September 11, 2011

Alternatives to Multi Threading for concurrency in Java. STM and Actors

In the Java world we are used to work with concurrency dealing directly with Threads, Synchronization and Shared Data.

Java introduced a great deal of improvement in version 5 with the new concurrency facilities it provided, and had built on it in subsequent versions of the language.

These facilities are great and powerful, but they still can sometimes be hard to use correctly. I will cover concurrency in the traditional (and concurrency utilities) way in another post. This post is just about introducing a couple of alternatives to these.

In this post I’ll introduce the Software Transactional Memory (STM) model for concurrency. In a later post I’ll introduce the Actors model in Java.

STM: Very much like the transactions we are use to in DBs but working with objects in memory, keeping the ACI properties of transactions.

In this model we separate identity from state. This basically means that we have some entities that hold an inmutable state that can change over time. We’ll understand this better with the example that will follow.

The main advantage of this separation is that there is no need to block or synchronize as the state doesn’t change.

I’ll write a piece of code now and explain how it works. For the example I will use Akka and its support for STM with Multiverse.

Let’s assume we want to create a very simplistic kind of Stack (No validations, no anything) that only supports push, peek and pop and it should be thread safe. The simplistic code would be something like the following (No thread safe).

 
public class StmStack {
 
   private static int SIMPLISTIC_BIG_SIZE = 1024;
   private Object[] elements = new Object[SIMPLISTIC_BIG_SIZE];
   private int top=0;
 
   public Object pop() {
      Object value =  elements[top];
      top --;
      return value;
   }
 
   public Object peek() {
       return  elements[top];
   }
 
 
   public void push(Object value) {
       elements[top+1] = value;
       top++;
   }
}

It is very simple to see that there exist a thread safety problem with the state variable ‘top’. The problem is simply that this variable is shared mutable state. A variable that can be accessed, read and changed concurrently by mutliple threads. And of course the elements array itself has the same problem.

The common solution to this problem, would be to synchronize the access to the three methods. This approach is not hard to follow here in this very simple example, but even here it has a couple of drawbacks. One of them is that synchronizing and lock acquiring affects performance. Other can be that for example the peek method is not changing state, and in an application that will use peek more than any other method (more reading and moderate writing) no more than one thread will be able to peek. Also we need to remember to synchronize every method that we put in this class that will either read or write. When things start to get a little complicated (more locks, more granularity, more mutable shared state) understanding synchronization and locking logic is not very easy, and debugging synchronization and concurrency problems is hard to say the least.

We’ll see now the code using STM. This will look a bit complex

public class StmStack {
 
    private Ref<Elements> elements = new Ref<Elements>(new Elements());
    private Ref<Integer> top = new Ref<Integer>(-1);
 
    public Object pop() {
       final TransactionFactory factory =
               new TransactionFactoryBuilder().setBlockingAllowed(true).setTimeout(new DurationInt(6).seconds()).build();
 
       return new Atomic(factory) {
 
           @Override
           public Object atomically() {
               System.out.println("poping ");
               if (top.get() < 0) {
                   StmUtils.retry();
               }
               Object value = elements.get().get(top.get());
               top.swap(top.get() - 1);
               return value;
           }
       }.execute();
    }
 
    public Object peek() {
       final TransactionFactory factory =
               new TransactionFactoryBuilder().setBlockingAllowed(true).setTimeout(new DurationInt(6).seconds()).build();
 
       return new Atomic(factory) {
 
           @Override
           public Object atomically() {
               System.out.println("peeking ");
               if (top.get() < 0) {
                   StmUtils.retry();
               }
               return elements.get().get(top.get());
           }
       }.execute();
    }
 
    public void push(final Object value) {
       new Atomic() {
 
           @Override
           public Object atomically() {
               System.out.println("pushing " + value);
               elements.swap(new Elements(elements.get(), value, top.get()));
               top.swap(top.get() + 1);
               return "";
           }
       }.execute();
    }
 
    public int elements() {
       return top.get()+1;
    }
}
 
class Elements {
 
    private static int SIMPLISTIC_BIG_SIZE = 1024;
    private final Object[] elements;
 
    Elements(Elements elements, Object newElement, int top) {
       this.elements = elements.elements;
       this.elements[top + 1] = newElement;
    }
 
    Elements() {
       elements = new Object[SIMPLISTIC_BIG_SIZE];
    }
 
    Object get(Integer index) {
       return elements[index];
    }
 

The first thing to notice is that we changed the elements array of objects to a Ref object to an object of the new class Elements. We can also see that the Elements objects created are immutable. Noone has direct access to mutate its state. It never changes after created. This is one of the ideas that need to be encouraged. The use of immutable objects.

As we talked before the use of Ref helps to separate the ID of the reference to its state so in this case we have a Ref that will point to a different Elements object in different moments of time, but will not modify the one it has currently directly, it will just replace it. We do the same with the ‘top’ variable, making it a Ref instead of an Integer.

The next thing is the implementation of the different methods. As we can see we are wrapping each method content in an Atomic object, and putting the content inside the atomically method. This will ensure that the operation runs inside in a transaction.

The transaction ensures that all the values in the Ref variables are consistently changed or rolled back in case some other transactions modify them in the meantime, retrying automatically if that is the case. We can also observe the ‘retry’ method call. This method help us retry the transaction in the case a pre-condition is not met to run the transaction in the first place.

I’ll show a couple of running examples now(Just the relevant code):

first we run 7 push operations in different threads:

final StmStack stack = new StmStack();
push(stack);
push(stack);
push(stack);
push(stack);
push(stack);
push(stack);
push(stack);
sleep();
System.out.println(stack.elements());

The output:

pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
pushing asdad
Number of elements: 7

Event though we called the push on the stack only 7 times, we can see that the push method (actually just the transaction part) was executed more than 20 times. This is because of all the retrying when multiple threads collide in the transaction execution. We can see that maybe for heavily writing applications STM transactions might not be the best solution because of all the retrying.

Now we run just 1 push, and then 6 peeks.

push(stack);
sleep(2000);
peek(stack);
peek(stack);
peek(stack);
peek(stack);
peek(stack);
peek(stack);
sleep(8000);
System.out.println(stack.elements());

And the output

pushing asdad
pushing asdad
peeking
peeking
peeking
peeking
peeking
peeking
Number of elements: 1

We can see that no retry is needed for the peeking. We can see that STM is better suited for multiple reads, low-to-moderate writes.

So with STM we have a model that avoids the use of explicit locking, offers great concurrency performance, helps encourage the use of immutable types and just mutable References, makes explicit the parts that we expect to be executed atomically.
It also dynamically and automatically handles threads and contention, and can help mitigate or entirely remove deadlocks as we don’t deal with locking or lock orders anymore.

STM is an alternative worth considering if we have requirements for concurrency that adjust to this model.

A lot more information in:

AKKA Documentation

And

Sunday, July 3, 2011

Understanding the event driven model for concurrency

For some time now there’s been this idea that the normal concurrent model for web applications that many of us are used to is not the best way to do things for large amounts of concurrent clients.

The model I’m talking about is of course the One Request - One Thread model . I started to read about it and the main concern show towards this model, is that it can’t scale very well to many requests (really really many) because of the cost of threads. The cost of threads is reflected mainly in memory consumption and context switching. Other concern is the complexity associated with thread programming.

I started to look then at the alternative way that was being all talked about on the web (mainly because of Node.js) which is the Evented, or Event Driven model.

So here I will try to introduce how this model works in an easy way.

The general idea is the utilization of the Reactor Pattern.

The Reactor Pattern works normally as a single threaded service loop, which in every iteration of the loop checks for I/O events in its registered handles and dispatches these events to suitable handlers.

The loop must be continually running without blocking operations. The only moment the loop blocks is when no I/O Events are received, but the moment there is one, it must handles it in a fast way and continue.

Let’s now show an example of EventMachine (A Ruby implementation of the Reactor Pattern), and then we show how the Reactor looks like.

The example is a Server, that when receiving one connection makes a query call to MongoDB and send the query result back to the calling client:

Module Server
  def receive_data(received)
       db = EM::Mongo::Connection.new.db('db')
       collection = db.collection('test')
 
       collection.find('_id' => 123) do |res|
         send_data res.inspect
      end
 end
end
 
EM.run do
 EM.start_server '0.0.0.0', 3001, Server
end

Ok so what does this code do?. Well it starts the Reactor in the EM.run call. Then it initializes an Evented Server in port 3001 (The creation of the server and registration happens before the loop starts iterating) and add it to the Reactor list of descriptors.

Now the reactor starts looping, it will go through its descriptors and wait until one of them change state. Right now there is only the server socket descriptor. So for now the event loop is in waiting state.

If we now connect for example with Telnet to port 3001, the Reactor will detect this and check the kind of I/O ready event that just happened on the server socket(in this case it will be an “accept ready” or similar) and then register a new descriptor for the new socket connection. Then the reactor is waiting again for events.

In the moment that the connection is received from the telnet session, in our code example, EventMachine will create a new instance of the Server module (more exactly an instance of an anonymous class that includes the module).

If for example we now send a text from our telnet session the reactor will detect that our last descriptor is ready for a I/O read operation and will process it accordingly. In our code example, the reactor will call the handler that in our case is the receive_data method of our new Server instance.

Next when the data is received in the receive_data method, we make a call to MongoDB. A simple query. But again this operation is non blocking. Internally the “find” method will create a EventMachine connection that will register another descriptor in the reactor. So now we have 3 descriptors registered in the reactor. When the query is ready processing and the data is available, the descriptor will signal the event, the reactor will notice it and then call the specific handler for the event. In this case the code block passed to the call to find. In this callback, we’ll send the data returned from mongo to our connected socket with the send_data method.

To better understand how the Reactor works. I include next some extracts from the EventMachine Java implementation.

The main class of the EventMachine java implementation (which is the implementation used when working with JRuby, and i understand it better than the C++ version which is the one used in normal Ruby) is the EmReactor class. and the main method on it is the run method, which is the one that runs the event loop:

 
public void run() {
       try {
           mySelector = Selector.open();
           bRunReactor = true;
       } catch (IOException e) {
           throw new RuntimeException ("Could not open selector", e);
       }
 
       while (bRunReactor) {
           runLoopbreaks();
           if (!bRunReactor) break;
 
           runTimers();
           if (!bRunReactor) break;
 
           removeUnboundConnections();
           checkIO();
           addNewConnections();
           processIO();
       }
 
       close();
   }
 

In this code we can see the main parts of the Reactor Pattern:

First the infinite loop (or until bRunReactor is false).

And if we see the last three lines of the While loop we can see the steps we have been talking about.

checkIO(): This method “listen” for I/O events in the registered descriptors. Blocking until one I/O channel is ready for something. In java it is implemented with Selector.select(timeout)

addNewConnections(): This method checks for when a new connection is registering with the looper. For example in our Mongo find call.

processIO(): This method loops to the descriptors that are in ready state, check what state they are in (write ready, read ready, etc) and dispatch to the handlers to deal with the event.

So that’s it.. That is the basics of the working of the Reactor Pattern.

Thursday, May 26, 2011

MongoDB Tutorial/Reference Essentials

The following is a quick tutorial / reference to start using the mongodb database.

We’ll start with a fast definition, and then go into the following topics, in a fast example approach:

Installing
Inserting
Querying
updating
deleting
Indexes and Explain
map reducing
drivers
distributing

MongoDB is a document oriented database built with the intention of being able to deal with very big amounts of data with good performance, to adjust to the increasing data that modern applications have to deal with, particularly when “in the cloud”. MongoDB is also intended to keep some of the great characteristics from Relational Databases, like the capacity to execute dynamic queries, so that you don't miss this great flexibility.

Installing:

Installing MongoDB for using in our testings is relly easy just go to http://www.mongodb.org/downloads and download the pertinent version (This references uses Linux and MacOSX).

After download, gunzip and untar the file and that’s it. It is installed.
To start mongo server go to the untared directory, go to bin directory and execute ./mongod (This will assume you have a /data/db directory in your system, if you don’t create one)

Inserting:

MongoDB works with Documents. In Mongo, a Document is simply a binary representation of a JSON object called BSON. you can simply think that a Document is a JSON object, and the binary thing is just the way mongo represents this object internally.

In Mongo, every document must belong to a Collection (a Collection can be though as a table of a RDBMS, but just for help understanding them, because they are different things), and every Collection should belong to a Database.

So let’s say we want to insert a car Document, into a Cars collection that belong to the Concesionary Database. We would do the following:

- From the bin directory, and with the server started, we execute ./mongo to open the interactive Shell. The interactive shell of mongo allow us to interact with the database server using Javascript.

- Next, we change to use our concesionary database (Even although the database doesn’t exist yet this command will work)

use concesionary

- Next, we insert our new Car in the cars collection (Again, the collection doesn’t exist yet, but it (and the concesionary database) will get created when inserting the first element.)

db.cars.insert({maker:'ferrari',model:'f50',acceleration:{speed100:3,speed200:9},colors:['white','black']});

As you can see we are inserting a new card, that is basically a JSON object (including simple types, subdocument types and arrays).

Let’s insert another car to use in the next session on querying:

db.cars.insert({maker:'fiat',model:'500',acceleration:{speed100:10,speed200:’NEVER’},colors:['blue','red']});

Querying:

MongoDB allows you a lot of flexibility in querying, very close to what you can do with SQL. You can use lots of filters, comparisons, etc. We just do a couple of basics queries here, to get your feet wet.

In general you query MongoDB calling the find method on the collection, and passing a JSON document with the selections you want to query on:

db.cars.find()

{ "_id" : ObjectId("4dde4d1c6eb878af72075592"), "maker" : "ferrari", "model" : "f50", "acceleration" : { "speed100" : 3, "speed200" : 9 }, "colors" : [ "white", "black" ] }

{ "_id" : ObjectId("4dde4f3d6eb878af72075593"), "maker" : "fiat", "model" : "500", "acceleration" : { "speed100" : 10, "speed200" : "NEVER" }, "colors" : [ "blue", "red" ] }

db.cars.find({maker:'ferrari'});

{ "_id" : ObjectId("4dde4d1c6eb878af72075592"), "maker" : "ferrari", "model" : "f50", "acceleration" : { "speed100" : 3, "speed200" : 9 }, "colors" : [ "white", "black" ] }

db.cars.find({'acceleration.speed200':'NEVER'});

{ "_id" : ObjectId("4dde4f3d6eb878af72075593"), "maker" : "fiat", "model" : "500", "acceleration" : { "speed100" : 10, "speed200" : "NEVER" }, "colors" : [ "blue", "red" ] }

db.cars.find({'colors':'white'});

{ "_id" : ObjectId("4dde4d1c6eb878af72075592"), "maker" : "ferrari", "model" : "f50", "acceleration" : { "speed100" : 3, "speed200" : 9 }, "colors" : [ "white", "black" ] }

Updating:

Basic updating is pretty straightforward, it needs a filter document, like find, and a parameter indicating how to modify the document:

db.cars.update({model:'f50'},{$set:{model:'f40'}});

db.cars.find({maker:'ferrari'});

{ "_id" : ObjectId("4dde54b56eb878af72075594"), "maker" : "ferrari", "model" : "f40", "acceleration" : { "speed100" : 3, "speed200" : 9 }, "colors" : [ "white", "black" ] }

Deleting

Even more starightforward than updating, just requiring the document filter (or nothing if you want to delete all the documents in the collection):

db.cars.remove({maker:'ferrari'});

db.cars.find()
{ "_id" : ObjectId("4dde4f3d6eb878af72075593"), "maker" : "fiat", "model" : "500", "acceleration" : { "speed100" : 10, "speed200" : "NEVER" }, "colors" : [ "blue", "red" ] }
db.cars.remove()
db.cars.find()
>

Creating indexes, and query explain:

Indexes, as in any other database are extremely important in MongoDB and extremely important to get them right. They work like you may expect, and allow you to accelerate the speed and performance dramatically of your queries if applied right. You can create compund indexes as well. Here we will touch the basics once again.

Let’s insert our two cars again:

db.cars.insert({maker:'fiat',model:'500',acceleration{speed100:10,speed200:'NEVER'},colors:['blue','red']});

db.cars.insert({maker:'ferrari',model:'f50',acceleration{speed100:3,speed200:9},colors:['white','black']});

MongoDB automatically creates an index for the _id property of its documents. We can query existent indexes like this:

db.system.indexes.find()

{ "name" : "_id_", "ns" : "concesionary.cars", "key" : { "_id" : 1 }, "v" : 0 }

Our application probably will make a lot of queries per car maker, so we will add an index to the maker property like this:

db.cars.ensureIndex({maker: 1})

Now when we query for existent indexes we get our new index:

{ "name" : "_id_", "ns" : "concesionary.cars", "key" : { "_id" : 1 }, "v" : 0 }
{ "_id" : ObjectId("4dde57fe6eb878af72075597"), "ns" : "concesionary.cars", "key" : { "maker" : 1 }, "name" : "maker_1", "v" : 0 }

So how can we see if some query is using our index?. Simple enough we use the explain method to do so, but before doing that, let’s remove the index and run explain without it.

db.runCommand({deleteIndexes: "cars", index: "maker_1"})

db.system.indexes.find()
{ "name" : "_id_", "ns" : "concesionary.cars", "key" : { "_id" : 1 }, "v" : 0 }

We removed the index, now let’s see explain in action:

db.cars.find({maker:'ferrari'}).explain()

{
"cursor" : "BasicCursor",
"nscanned" : 2,
"nscannedObjects" : 2,
"n" : 1,
"millis" : 0,
"nYields" : 0,
"nChunkSkips" : 0,
"isMultiKey" : false,
"indexOnly" : false,
"indexBounds" : {

}
}

The main things to take a look at when running explain (for the purposes of our discussion) is the type of cursor, the nscanned, and the n attributes.

The cursor “BasicCursor” is simply a cursor that scans through all the collection to get the query results, nscanned is the total documents scanned, and the n is the total documents returned. In an ideal world the n and nscanned should be the same.

Now let’s create the index again and rerun the explain for the query:

db.cars.ensureIndex({maker: 1})
db.cars.find({maker:'ferrari'}).explain()
{
"cursor" : "BtreeCursor maker_1",
"nscanned" : 1,
"nscannedObjects" : 1,
"n" : 1,
"millis" : 0,
"nYields" : 0,
"nChunkSkips" : 0,
"isMultiKey" : false,
"indexOnly" : false,
"indexBounds" : {
"maker" : [
[
"ferrari",
"ferrari"
]
]
}
}

We can see the different results. We are using the index (Indicated by the cursor property) and the nscanned and n properties have the same value. We are just scanning the elements we are returning.

Map Reducing:

Apart from the common grouping operations allowed by MongoDB (like sum, max, etc) we can use map reduce for more grained and customized grouping requirements, and it is built into the mongodb functionality. (For an explanation of map reduce see: http://cscarioni.blogspot.com/2010/11/hadoop-basics.html). Here we show an extremely simple map reduce:

We want to simply count all the cars per maker:
First we insert a new fiat into the collection (Do that yourself);
Then we define our map reduce in one line like this:

db.cars.mapReduce(
function(){
emit (this.maker,{number:1})
},
function(key,values){
var total = 0;
values.forEach(
function(value){
total += value.number;
});
return {total:total}},"result"
)

When runned we get this:

{
"result" : "result",
"timeMillis" : 3,
"counts" : {
"input" : 3,
"emit" : 3,
"output" : 2
},
"ok" : 1,
}

and the result of the counting is in the new result collection:

db.result.find()
{ "_id" : "ferrari", "value" : { "number" : 1 } }
{ "_id" : "fiat", "value" : { "total" : 2 } }

As we can see the mapReduce method receives a map function, a reduce function, and normally the name of the collection to store the results.

Drivers:

In this section we aren’t going to say a lot. Simply that there already exists mongodb drivers for the most common programming languages out there, they all work kind of the same (taking into account the advantages and limitations of each programming language) and they are pretty easy to start experimenting with.

Distributing:

One of the most important characteristics of MongoDB is its support for distribution, from creating Replica Sets to Sharding, I’ll cover that in a soon to write article. For now just to say that the sharding model is really powerfull and allow for transparent failover, and transparent sharding and distribution of data chunks accross the sharded cluster.

carlo scarioni