No F*cking Idea

Common answer to everything

Designing Todo App Backend Using Redis and Mongodb

| Comments

side note

Upgrading octopress is a @!#!@pain! :>

What is this post about :)

Long time nothing new here so i will glue something together about stuff that we were talking about today with my friend Jarek. We talked about building backend for Todo app :). Yes simple todo app. How to build scalable backend. So my initial thought was “how i would design it in different databases”. (i’m taking only about data model)

Requirements

What we know:

  • User has some sort of id. (number, email, hash of something)
  • We need to be able to have different todo lists
  • User can choose his todo list and see tasks ( obvious )
  • User can tag tasks!
  • User can query tasks in list by tags
  • User can see all tags.

Design using Redis

How to do it with redis ? :)

First few facts i assumed at start. Single todo task has body and timestamps [created_at, updated_at] and base for key will be phrase “todoapp”.

So lets start with user and his list of todo lists :). This gives us first key

1
2
3

todo:<user_id>:todolist:next => auto incrementing counter for lists id
todo:<user_id>:todolists => [LIST]
todo:<user_id>:todolist:<todo_list_id>:name => list name

Here we have two keys, first is list id counter that we will bump to get new list counter :), second is list of todolists ids. Why do it this way ? Well people can add and remove todo lists.

Ok so how to create new list ?

example
1
2
3
4
5
6
7
8

redis 127.0.0.1:6379> INCR todo:kuba:todolist:next
(integer) 1
redis 127.0.0.1:6379> RPUSH todo:kuba:todolists 1
(integer) 1
redis 127.0.0.1:6379> LRANGE todo:kuba:todolists 0 -1
1) "1"
redis 127.0.0.1:6379> SET todo:kuba:todolist:1:name "things to do"
OK

Hey ! we just added id of our first list to list of our todo lists (lots of list word here!). Ok so now lets add a task.

list:

1
2

todo:<user_id>:todolist:<todo_list_id>:next => auto incrementing counter for tasks id
todo:<user_id>:todolist:<todo_list_id> => [LIST]

and task:

1
2
3

todo:<user_id>:task:<task_id> => content of task eg. "finish blog post"
todo:<user_id>:task:<task_id>:created_at => epoch time when it was created handled by app
todo:<user_id>:task:<task_id>:updated_at => epoch time when it was last updated handled by app

Ok so how to i add task to my list

adding task
1
2
3
4
5
6
7
8
9
10

redis 127.0.0.1:6379> INCR todo:kuba:todolist:1:next
(integer) 1
redis 127.0.0.1:6379> LPUSH todo:kuba:todolist:1 1
(integer) 1
redis 127.0.0.1:6379> SET todo:kuba:task:1 "finish blog post"
OK
redis 127.0.0.1:6379> SET todo:kuba:task:1:created_at  1343324314
OK
redis 127.0.0.1:6379> SET todo:kuba:task:1:updated_at  1343324315
OK

And we have our first task in. How do we get tasks from out todo list simple!

peeking task
1
2
3
4
5
6

redis 127.0.0.1:6379> LRANGE todo:kuba:todolist:1 0 -1
1) "1"
redis 127.0.0.1:6379> GET todo:kuba:task:1
"finish blog post"
redis 127.0.0.1:6379> GET todo:kuba:task:1:created_at
"1343324314"

Ok so now we have very simple todo lists with tasks, well at least overview. Ofc you can use sets for todo lists or zsets but lets stay with lists to keep it simple for now.

How ro remove task from the list ?

removing task
1
2
3
4

redis 127.0.0.1:6379> LREM todo:kuba:todolist:1 -1 1
(integer) 1
redis 127.0.0.1:6379> LRANGE todo:kuba:todolist:1 0 -1
(empty list or set)

Good, now we can add tasks, remove tasks, same sotry with adding todo lists and removing todo lists. One last thing is to add tags!. Simply here each task will have list of tags and each tag will have list of tasks related with.

1
2

todo:<user_id>:task:<task_id>:tags => [LIST]
todo:<user_id>:tag:<tag>:tasks => [LIST]

So how we will add tags to tasks ? Simple!

tagging
1
2
3
4
5
6
7
8
9
10
11
12
13

redis 127.0.0.1:6379> LPUSH todo:kuba:task:1:tags "redis"
(integer) 1
redis 127.0.0.1:6379> LPUSH todo:kuba:task:1:tags "design"
(integer) 2
redis 127.0.0.1:6379> LPUSH todo:kuba:tag:redis:tasks 1
(integer) 1
redis 127.0.0.1:6379> LPUSH todo:kuba:tag:design:tasks 1
(integer) 1
redis 127.0.0.1:6379> LRANGE todo:kuba:tag:design:tasks 0 -1
1) "1"
redis 127.0.0.1:6379> LRANGE todo:kuba:task:1:tags 0 -1
1) "design"
2) "redis"

This example shows what we need to do to tag a task with something and how to peek tasks tagged with it. Why we have both lists ? To make it fast while searching. If user will click on particular tag like “redis” you want to get it O(1) time not O(N) after searching all keys. And same the other way, normal ui will pull task test, when it was created and tags to display so we want to have this data ready.

This is whole design for the todo app. We have 8 types of keys. Things like pagination, calculating time are all left to app layer. Important thing is that i scope everything to user key / id. This is because i want to isolate each user space easy. Each user in his own space will have short lists, there is no danger of “ultimate” non splittable lists.

Design using Mongodb

Well this case upfront is easier to grasp because for each list we can use single document or collection of documents lets talk about both solutions.

Todolist = Document

In this example we will use built in “array” operators

creating
1
2
3
4
5
6
7

> db.todolists.save({name: "House work", tasks: []})
"ok"
> db.todolists.find({name: "House work"})
[
  {   "name" : "House work",   "_id" : {   "$oid" : "50118742cc93742e0d0b6f7c"   },
      "tasks" : [   ]   }
]

So lets add a task :)

1
2
3
4
5
6
7
8
9

db.todolists.update({name: "House work"},{$push:{"tasks":{"name":"finish blog post", "tags":["mongo"] } } })
"ok"
> > db.todolists.find({name: "House work"})
[
  {   "name" : "House work",   "_id" : {   "$oid" : "50118742cc93742e0d0b6f7c"   },
      "tasks" : [
       {   "name" : "finish blog post",   "tags" : [   "mongo" ]   }
      ]   }
]

this will create empty todo list with name “House work” of course this way we will not omit building sub lists of tags etc, we have to build in a same way like in redis but as part of document. The story is exactly the same like above in redis. Mongodb lets us query nested documents and this will enable us to skip some of the extra “lists” while doing search.

Lets try it out how to find out mongo tagged entries?

find by tag
1
2
3
4
5
6
7
8

> db.todolists.find({"tasks.tags": { $in : ["mongo"] } })

[
  {   "name" : "House work",   "_id" : {   "$oid" : "50118742cc93742e0d0b6f7c"   },
      "tasks" : [
        {   "name" : "finish blog post",   "tags" : [   "mongo" ]   }
      ]   }
]

This way we can find whole todolist with task that contains tag “mongo” but after that we will have to work out from the document in app the task that we are interested int. Using it like this we will have a document with structure like this

todo list structure
1
2
3
4
5
6
7
8
9
10
11
12
13
14

{
 user: "user id",
 name: "<name>",
 tasks: [
   {
    text : "todo text",
    tags : [
      "Tag1", "Tag2"
    ]
    created_at : Time,
    updated_at : Time
   }
 ]
}

Using redis we could wrapp stuff into MULTI command while using mongodb “array” command we are a bit cowboishing. They could remove wrong stuff in we will not be cautious :). (well same in redis!) Big plus of Mongodb is native time type!

Todolist = many documents

Using this approach we can leverage more of our stuff on mongodb search in this approach each task will be a different document. With structure like this

task structure
1
2
3
4
5
6

{
  todo_list: "todo list id",
  user: "user id",
  text: "todo text",
  tags: ["Tag1", "Tag2"]
}

This way we will have a lot of documents, more disk space consumption and still we will have to have second collection with with objects with structure like this

structure of todolist
1
2
3
4
5
6

{
  todo_list: "todo list id",
  name: "todo list name",
  user: "user id",
  // tasks: [Tasks OBjectID Array] you could have this and remove todo_list id from tasks choice is yours :)
}

And this way we can use find tool very easy and get documents fast.

Summary

All of this solutions have some pros and cons, mongodb excels better when documents are bigger (limit is set on 16 mb per document) than loads of small documents (massive waste of space). Solution in redis is really fast and if you will implement lazy loading it will be very fast. You can adjust this designs to your situation by changing lists to sets etc. The place where redis OWNS mongodb in this context is “strucutres” and we use a lot of them to store data like this, lists sets, zsets. Implementing priority list in mongodb will be totally custom solution while in redis we can just use zset.

This is just my point of view on this. I will supply some code to cover it more in part two. This is next problem, i’m sure solution in mongodb using things like mongoid http://mongoid.org will be much more developer friendly then building things “rawly” in redis hiredis client.

btw i jsut wrote this from “top of my head” so it may contain typos and i’m sure keys, structures can be optimized :) This is just to open discussion with my friend :)

Cheers!

Comments