Игры с map-reduce

by Michel Beloshitsky

Не так давно я узнал о существовании интересной javascript-машины – nodejs. Через него и во многом благодаря сайту nodejs.ru я узнал также о многих других баззвордах современности – nosql, libev и все такое. Nosql системы заинтересовали, хотелось чего-то более выразительного и легкого (выразительного и легкого для меня, sql тоже вполне хорош, но в некоторых случаях…).

Собственно так и родился движок assou.

Сейчас, на раннем этапе, очевидно, он не может претендовать на что-то кроме исследовательского проекта, да и вообще непонятно, сможет ли. В будущем планирую сделать его чем-то вроде sqlite для nodejs – чтобы оно хоть и не блестало гиперпроизводительностью, но работало бы более менее быстро и не хапало лишних зависимосте. Не для хайлоада, проще говоря, а так, потестить. Но особо на хорошее не надейтесь.

Assou

/** 
 * assou - toylike map-reduce engine
 *
 * 2010, Michel Beloshitsky.
 *
 * Placed in public domain.
 */

var assou = function () {

   var storage = {}, k = 0, views = {}

   /* Basic key management */

   function put(json) { storage[++k]=json }

   function del(k) {
      if (storage[k] !== undefined) {
         delete storage[k]
         return {ok:true}
      } else {
         return {ok:false, err: 'Key not found'}
      }
   }

   /* Views */

   function updateView(name) {
      var worker, intermed = {}, i
      function emitMap (k, v) {
         if (intermed[k]) { intermed[k].push(v) } else { (intermed[k] = [v]) }
      }
      function emitReduce (k, v, storage) { storage[k] = v }
      function defaultReduce (k, v, emit) { emit(v) }
      if (worker = views[name]) {
         worker[2] = {}
         worker[1] = worker[1] || defaultReduce
         for (i in storage)
            worker[0](i, storage[i], emitMap)
         for (i in intermed)
            worker[1](i, intermed[i], function (v) { emitReduce(i, v, worker[2]) })
         worker[3] = false
         return worker[2]
      } else {
         return {ok:false, err:'View "' + name + '"not found.'}
      }
   }

   function view(name, map, reduce) {
      if (typeof map == 'function' &&
          (typeof reduce == 'function' || reduce === undefined)) {
         views[name] = [map, reduce, null, false]
         return {ok:true}
      } else {
         return {ok:false, err: 'Wrong arguments. ' +
                 'Map must be a function. ' +
                 'Reduce must be a function or undefined.'}
      }
   }

   function get(vw) {
      if (views[vw]) {
         return updateView(vw)
      } else {
         return {ok:false, err:'View "'+vw+'" not found.'}
      }
   }

   /* Builtin '*' view */

   view('*', function (k, v, emit) { emit(k,v) })

   return {put: put, get: get, del: del, view: view }
}

Пара тривиальных тестов

Заполняем хранилище хоть чем-нибудь, с чем можно работать.

/**
 * assou-test - assou map-reduce engine simple test.
 */

var tst = assou()

tst.put({msg:'Hey, hey!', tags:['one', 'two']})
tst.put({msg:'Hey, hey!', tags:['one', 'two'], path:['top','leaf']})
tst.put({msg:'Nice bikini!', tags:['two']})
tst.put({msg:'Hm...', tags:['zero'], path:['top']})
tst.put({msg:'Unbelievable message.'})
tst.put({msg:'Nested message.', path:['top','nest']})
tst.put({msg:'Another nested message.', path:['top','nest']})
tst.put({msg:'Yet Another nested message.', path:['top','nest','ynest']})
    

Создаем пару видов: вид по тегам и вывод дерева (для деревьев у нас мало сообщений, так что получится не совсем наглядно).

/* Views */
tst.view('tags',
         function (k, v, emit) {
            var i;
            if (v.tags)
               for (i in v.tags)
                  emit(v.tags[i], v)
         })

tst.view('threads',
         function (k, v, emit) {
            var i;
            if (v.path && v.path.length)
               emit(v.path[0], v)
         })

Вот что из всего этого получилось. Вид ‘*’ является видом по умолчанию и просто выводит все, что есть в базе.

/* Out data */

JSON.stringify(tst.get('*'))

{
   "1": [{
      "msg": "Hey, hey!",
      "tags": ["one", "two"]
   }],
   "2": [{
      "msg": "Hey, hey!",
      "tags": ["one", "two"],
      "path": ["top", "leaf"]
   }],
   "3": [{
      "msg": "Nice bikini!",
      "tags": ["two"]
   }],
   "4": [{
      "msg": "Hm...",
      "tags": ["zero"],
      "path": ["top"]
   }],
   "5": [{
      "msg": "Unbelievable message."
   }],
   "6": [{
      "msg": "Nested message.",
      "path": ["top", "nest"]
   }],
   "7": [{
      "msg": "Another nested message.",
      "path": ["top", "nest"]
   }],
   "8": [{
      "msg": "Yet Another nested message.",
      "path": ["top", "nest", "ynest"]
   }]
}

JSON.stringify(tst.get('tags'))

{
   "one": [{
      "msg": "Hey, hey!",
      "tags": ["one", "two"]
   },
   {
      "msg": "Hey, hey!",
      "tags": ["one", "two"],
      "path": ["top", "leaf"]
   }],
   "two": [{
      "msg": "Hey, hey!",
      "tags": ["one", "two"]
   },
   {
      "msg": "Hey, hey!",
      "tags": ["one", "two"],
      "path": ["top", "leaf"]
   },
   {
      "msg": "Nice bikini!",
      "tags": ["two"]
   }],
   "zero": [{
      "msg": "Hm...",
      "tags": ["zero"],
      "path": ["top"]
   }]
}

JSON.stringify(tst.get('threads'))

{
   "top": [{
      "msg": "Hey, hey!",
      "tags": ["one", "two"],
      "path": ["top", "leaf"]
   },
   {
      "msg": "Hm...",
      "tags": ["zero"],
      "path": ["top"]
   },
   {
      "msg": "Nested message.",
      "path": ["top", "nest"]
   },
   {
      "msg": "Another nested message.",
      "path": ["top", "nest"]
   },
   {
      "msg": "Yet Another nested message.",
      "path": ["top", "nest", "ynest"]
   }]
}

Вот кстати последний случай с деревом показал, что в этот вид неплохо было бы добавить еще и reduce – для того чтобы узлы дерева выводились в строго определенном порядке.

А впереди самое интересное: я начну открывать для себя всякое интересное типа b-tree, пропускать через движок бешеные гигабайты тестов и развлекаться подобным образом. Если все это не потеряет актуальность.

Литаратура

1. Jeffrey Dean, Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, Google, Inc.