Cache con SimpleORM

En esta entrada escribiré detalladamente sobre una característica que me encanta SimpleORM y que, en mi humilde opinión, es fundamental para la escalabilidad, estoy hablado el Cacheo de los datos. Según su definición, el Cache es la duplicación de datos a un medio más rápido para así reducir el tiempo de acceso a dichos datos, y así optimizar el rendimiento del sistema. Dicha duplicación es volátil, es decir su eliminación o alteración no afecta a los datos originales.

El gran cuello de botella de los sistemas Webs son las bases de datos, como un amigo suele decir “the fastest database applications are those that avoid accessing the database as much as possible” (las mas aplicaciones mas rápidas utilizando bases de datos son las que la evitan lo mas posible, o algo así) lo cual tiene gran sentido, ya que las bases de datos bastante lentas, pero son necesarias. Son lentas ya que detras de una simple consulta SQL existen varios pasos, como ser (solo algunos pasos, no soy un experto esta área):

  1. Conexión a la base de datos (o utilizar una existente)
  2. Autenticación
  3. Compilación del SQL (o interpretación)
  4. Se planea y optimización lo generado/interpretado, buscando índices que agilicen la ejecución de la consulta
  5. Ejecución de la consulta, leyendo datos del I/O (generalmente el disco duro).
  6. Se devuelven los resultados.

Los arriba mencionados, son solo algunos pasos genéricos que utilizan los manejadores de bases de datos, pero puede ser menos o mas dependiendo de la implementación, peor lo que no varia nunca es el exceso de trabajo por cada consulta, haciendo de esta, en la mayoría de los casos, la parte mas lenta de cualquier sistema, incluyendo la Web donde es un factor crucial el tiempo de respuesta.

¿Y como ser podría evitar?, seria insano de mi parte a estas alturas recomendar escribir códigos para acceder a los datos utilizando algún tipo de ordenamiento, seria re-inventar la rueda. Una solución, por cierto la mas simple, es utilizar algún tipo de Cache para los resultados de consultas que no cambian frecuentemente, guardando dicho cache en un medio de rápido acceso, podría ser un directorio, memoria RAM, memcached.

Un error bastante común, que vi especialmente en CMS y similares, es que aunque el resultado a la consulta está en el cache, la conexión a la base de datos es siempre realizada, ya que esta es realizada automáticamente al inicio del código, es por este motivo que SimpleORM tiene conexión de forma implícita, solo es realizada si es estrictamente necesariamente, ejemplo:

require "DB.php";
DB::setUser("root");
DB::setPass("foobar");
DB::setDB("testing");
DB::setDriver("mysql");

Esto, a pesar de la gran utilidad, tiene un pequeño defecto, no se comprueban si los parámetros de conexión son correctos (usuario, contraseña, permisos, etc) en único lugar, en realidad nada imposible para un buen programador (utilizar transacciones siempre que se modifica algo, y utilizar siempre manejo de errores para cada operación).

En realidad, lo anterior citado solo es una pequeña acotación, lo más importante es determinar si los resultados de una consulta tienen que ser guardados en cache, y por cuanto tiempo. Después de mucho pensar en una manera sencilla, mantenible y eficiente de definir si una consulta puede ser cacheada, no se me vino nada mas simple que esto, definir un método (que por defecto en la clase padre DB retorna falso) que retorna true si la consulta actual puede ser cacheada. Los parámetros que el método recibe son los siguientes, $sql que contiene la consulta a ser ejecutada, $values que contienen las variables referenciadas en la consulta SQL, y $ttl donde se puede especificar el tiempo de vida del cacheo, en segundos.

class User
{
    public $user; /* unique index */
    public $pass;
    /* otras columnas */
    public $nombre;
    public $email;

    function isCacheable($sql, $values, &$ttl) {
        if (count($values) == 1 && isset($values['username'])) {
            $ttl = 7200; /* dos horas */
            return true;
        }
        return false;
    }
}

Como lo vieron, la definición del cacheo es sencilla, en este caso seran cacheadas (por dos horas) todas las consultas que tengan como variable username, (analizar el SQL en sí no muy lento, por eso utilizo solo las variables). Esto quiere decir realizamos una selección, donde username es “foobar”, la primera vez se conectará a la base de datos y realizará la búsqueda, luego el resultado será guardado en cache y por las siguientes dos horas, para la misma búsqueda (donde username sea “foobar”) el resultado será proveida por el cache.

$user = new User;
$user->username = "foobar";
$user->load();

Pero no todo es tan sencillo, pues existe un pequeñisimo problema que sería lo siguiente, si los datos de la tabla user para username es “foobar” cambia, digamos el nombre, nuestro cache mostraría datos no actualizado por dos horas (en el peor de los casos).

$user = new User;
$user->username = "foobar";
if ($user->load()->valid()) {
    $user->nombre = "nuevo nombre";
    $user->save();
}

La solución más eficiente que pude imaginarme fue la siguiente. Creé una función que es ejecutada cuando una actualización es realizada (a futuro lo haré para inserciones y datos borrados), y ahí proveo una simple manera de reconstruir el cache. Solo miren el siguiente código, que deberíamos agregar a la clase User.

    protected function onUpdate ($changes, $sql, $params)
    {
        /* obtener los parametros de la consulta original */
        $values = $this->getQueryParams();
        /* crear un objeto con del mismo tipo del objeto actual */
        $class   = get_class($this);
        $table   = new $class( $values );
        if (count($values) == 1 && isset($values['username'])) {
            /* deshabilitar el cacheo temporalmente y hacer la consulta */
            /* así, los datos serán traídos de la base de datos, y luego */
            /* será guardado en el cache, así actualizaremos nuestro cache */
            $table->disableQueryCache();
            $table->load();
        }
    }

Como vieron (el código es auto-explicado) , a cada cambio de los datos lo que hago es, previa verificación si la consulta es cacheada, deshabilitar temporalmente el cacheo para las selecciones y realizar la misma consulta, que posterior a su ejecución sobre-escribe el cache, actualizándolo de esta forma. No soluciona todos los casos, pero ayuda bastante, ya que esta soluciona combinada con la creatividad del programador puede hacer un sistema que dependa del cache lo más posible.

Finalmente, solo falta elegir cual método de cacheo que será el utilizado, lo cual se realizado simplemente incluyendo uno de los Cache drivers, en la distribución viene para simples archivos y memoria RAM o pero no obstante cualquier persona puede crear su propio Cache driver extendiendo esta clase base.

Twitter (+OAuth) desde PHP (PECL/OAuth)

Con el aumento de la popularidad de Twitter, a cada día vemos miles de nuevas aplicaciones, por cierto algunas muy útiles, debido probablemente a su amplia API. En este post describiré como autenticarse utilizando OAuth (en mi ejemplo con PECL/OAuth), y como hacer algunas operaciones básicas. Antes que nada, en mis códigos (utilizado en algunos proyecto que aun no han visto la luz) he utilizado lo escritor por Rasmus en su blog, por lo cual esto podría ser similar (pero no igual).

Para el ejemplo, utilizaré la siguiente table (en MySQL):

CREATE TABLE `user` (
  `id` bigint(20) NOT NULL auto_increment,
  `user` varchar(100) NOT NULL,
  `password` varchar(32) default NULL,
  `tw_stage` tinyint(1) not null default 0,
  `tw_user` varchar(100) default NULL,
  `tw_token` varchar(64) default NULL,
  `tw_secret` varchar(64) default NULL,
  `tw_followers` int(11) default NULL,
  `tw_following` int(11) default NULL,
  `tw_description` text,
  `tw_avatar` varchar(250) default NULL,
  `tw_location` varchar(250) default NULL,
  `tw_created_at` datetime default NULL,
  PRIMARY KEY  (`id`),
  UNIQUE KEY `user` (`user`)
) ENGINE=InnoDB;

Y el siguiente código (utilizando SimpleORM) para manejar la tabla de arriba:

class User extends DB
{
    /* Informaciones del usuario, del sistema en si */
    public $user;
    public $password;
    /* Informaciones de Twitter */
    public $tw_stage;
    public $tw_user;
    public $tw_token;
    public $tw_secret;
    public $tw_avatar;
    public $tw_following;
    public $tw_followers;
    public $tw_description;
    public $tw_location;
    public $tw_created_at;
}

La parte mas complicada del API es la autenticación en si, ya que tiene varios pasos.

define("KEY", "clave");
define("SECRET_KEY", "clave-privada");

$twitter = new OAuth(KEY,SECRET_KEY,OAUTH_SIG_METHOD_HMACSHA1,OAUTH_AUTH_TYPE_URI);
$twitter->enableDebug();  

$user = new User;
$user->ID  = $_SESSION['user_id'];
if (!$user->load()->valid()) {
    die("invalid user");
}

La primera parte es muy sencilla, donde solicitamos a Twitter las claves (tokens) para la autenticación, luego guardamos en la base de datos (o podría ser $_SESSION). Luego con redirigimos a Twitter para que nuestro usuario se puede autenticar y autorizarnos el acceso.

    $token_info      = $twitter->getRequestToken('https://twitter.com/oauth/request_token');
    $user->tw_token  = $token_info['oauth_token'];
    $user->tw_secret = $token_info['oauth_token_secret'];
    $user->tw_stage  = 1;
    $user->save();
    header('Location: https://twitter.com/oauth/authenticate?oauth_token='.$user->tw_token);
    exit();

Luego si el usuario nos dio el acceso, Twitter redigirá a nuestro `callback URL` (que para comodidad debería ser el mismo script). Ahora tendremos que verificar si el usuario nos autorizó, y pedir los nuevos tokens para guardalos, ya que esos tokens serán los utilizados para autenticarnos, haciendo una analogía simple seria como usuario y contraseña.

    $twitter->setToken($_GET['oauth_token'],$user->tw_secret);
    $access_token_info = $twitter->getAccessToken('https://twitter.com/oauth/access_token');
    $user->tw_token    = $access_token_info['oauth_token'];
    $user->tw_secret   = $access_token_info['oauth_token_secret'];
    $user->tw_stage    = 2;
    $user->save();

Si hasta aquí todo fue bien (no hubo ninguna excepción lanzada) el usuario ya está autenticado y ya podemos realizar todas las operaciones que requieran autenticación para el actual usuario. Este proceso solo debe realizarse una vez, ya que los tokens no expiran. Ahora, esta porción de código extrae informacion referente al perfil del usuario, generalmente también lo incluyo en la autenticación.

    $twitter->setToken($user->tw_token,$user->tw_secret);
    $twitter->fetch('https://twitter.com/account/verify_credentials.json');
    $response = json_decode($this->getLastResponse());
    $user->tw_followers   = $response->followers_count;
    $user->tw_following   = $response->friends_count;
    $user->tw_description = $response->description;
    $user->tw_avatar      = $response->profile_image_url;
    $user->tw_name        = $response->name;
    $user->tw_location    = $response->location;
    $user->tw_created_at  = $response->created_at;
    $user->save();

Y poniendo todo lo arriba mencionado en un solo lugar obtendríamos algo así:

require "DB.php";
require "model.php";

define("KEY", "clave");
define("SECRET_KEY", "clave-privada");

$twitter = new OAuth(KEY,SECRET_KEY,OAUTH_SIG_METHOD_HMACSHA1,OAUTH_AUTH_TYPE_URI);
$twitter->enableDebug();  

$user = new User;
$user->ID  = $_SESSION['user_id'];
if (!$user->load()->valid()) {
    die("invalid user");
}

/* Previniendo errores */
if ($user->tw_stage == 1 && !isset($_GET['oauth_token'])) {
    $user->tw_stage = 0;
}

try {

switch ($user->tw_stage) {
    case 0:
        $token_info = $twitter->getRequestToken('https://twitter.com/oauth/request_token');
        $user->tw_token  = $token_info['oauth_token'];
        $user->tw_secret = $token_info['oauth_token_secret'];
        $user->tw_stage  = 1;
        $user->save();
        header('Location: https://twitter.com/oauth/authenticate?oauth_token='.$user->tw_token);
        exit();
    case 1:
        $twitter->setToken($_GET['oauth_token'],$user->tw_secret);
        $access_token_info = $twitter->getAccessToken('https://twitter.com/oauth/access_token');
        $user->tw_token    = $access_token_info['oauth_token'];
        $user->tw_secret   = $access_token_info['oauth_token_secret'];
        $user->tw_stage    = 2;
        $twitter->setToken($user->tw_token,$user->tw_secret);
        $twitter->fetch('https://twitter.com/account/verify_credentials.json');
        $response = json_decode($this->getLastResponse());
        $user->tw_followers   = $response->followers_count;
        $user->tw_following   = $response->friends_count;
        $user->tw_description = $response->description;
        $user->tw_avatar      = $response->profile_image_url;
        $user->tw_name        = $response->name;
        $user->tw_location    = $response->location;
        $user->tw_created_at  = $response->created_at;
        $user->save();
        header("location: go-some-where.php");
        break;
}

} catch (Exception $e) {
    var_dump($e);
    die("error");
}

Una vez autenticado, podemos realizar todas las acciones que un usuario puede hacer, como leer y enviar tweets, ver los tweets de sus amigos, y otras cosas

function sendTweet($text)
{
    $twitter = new OAuth(KEY,SECRET_KEY,OAUTH_SIG_METHOD_HMACSHA1,OAUTH_AUTH_TYPE_FORM);
    $twitter->setToken($user->tw_token, $user->tw_secret);
    $args = array('status'=> $text);
    try {
        $twitter->fetch('http://twitter.com/statuses/update.json',$args);
        $json = json_decode($twitter->getLastResponse(),true);
     } catch (Exception $e) {
         return false;
     }
    return isset($json['id']) ? $json['id'] : false;
}

Espero que les sea de utilidad, no duden en comentar si tienen dudas.

RFC: Simple-Storage

As you might know, days ago I released a new (still in beta) project named Simple-ORM, which is a very basic (but efficient) database abstraction. It’s major feature are:

  1. Easy iteration and data update inspired by ActiveRecords
  2. Built on top of PDO
  3. Implicit database connection, connecting only when it’s necessary
  4. Native query cache support.
  5. Support single-level transactions (limited by PDO)
  6. Data filtering with callback functions per column

Right now, it helps developer with some very basic standard SQL (insert, update, delete and a very limited select) and it is really simple to extend just with “raw” SQL. Another pretty cool feature is that it supports cache natively. Just visit the examples dir (I’ll add more samples ASAP).

It’s main disadvantage is that it is not a ORM properly, you still need to know SQL in order to make it usable for real life situations, I did it in that way because perform normal tasks (query based on objects, relationships or anything else that a proper ORM offers) at run-time is not efficient, it requires a lot of RAM, and is not that scalable. As much easier for the developer, harder for the server (me, right now)

In order to fix that (for me it’s okay, right I’m composing by hand all my SQL) I’m creating a project called Simple-Storage that will generate code, using Simple-ORM as base-code, to manipulate data. Additionally it would generate tables schemes, indexes (when it’s necessary), validation, relations, data-migration and several other features (when I would need something else I’ll add). Simple-storage would be a compiler (finally something useful where I can apply my knowledge from University) that will generate PHP (or any other if someone wants to extend it) code to manipulate the tables. By the fact that it wouldn’t perform any sort of checking/validation/generate-SQL/etc at run time and it has cache, it will be very scalable, and useful (IMHO).

Right now I’m sharing (expecting a feedback) about its possible syntax (I’d to have something clear, easy to learn/read and useful):

/**
 *  Simple table definition, we create a table called
 *  "posts".
 *
 */
(set default length 100)
table posts
    title:    string
    uri:      string
    abstract: text
    content:  text
    lang:     langs

/**
 *  Tag table.
 *
 */
table tags
    tag: string(50)
    lang: langs

/**
 *  This is the simplest table, it just contains
 *  a language list.
 *
 */
table langs:
    lang string(20)

/**
 *  Many-to-many relations ships, a post might
 *  has several tags, and a tag might has several posts.
 */
posts has many tags
tags  has many posts

/**
 *  we create a "hook" on table "posts" in order to
 *  recreate cache when a give post is updated.
 */
onUpdate: posts
    delete cache getPostByUri uri

/**
 *  Queries
 */

/**
 *  Create a method into the "posts" model that will retrieve three columns
 *  (title, lang.lang and uri) from posts that has some tag or set of tags.
 */
getPostByTag: posts
    columns:
        title
        lang.lang
        uri
    filters:
       posts in tags
    cache: 1h

/**
 *  Create a method that retrieves the entire post from based on its
 *  "uri", this query is cached for 1 hour
 *
 */
getPostByUri: posts
    uri equalto $1
    cache: 1h

/**
 *  Another query
 */
getPostByLang: posts
    lang equalto langs

This is a sample script that will create three tables (posts, tags and lang), relationships and some method to read data from the table. I’d like to get your thoughts about the language and idea in general.

Modelado de datos — A mi estilo :)

Siguiendo a mi post sobre MVC hecho en casa, que en mi humilde opinión fue útil, ya que hubo muchos comentarios y correos electrónicos sobre el tema, esta vez vengo con algo relacionado, que es sobre una clase sencilla para manejar los datos sin escribir SQL (o escribiendo lo menos posible), siempre teniendo en cuenta eficiencia, simpleza y extensiblidad.

Seguramente se preguntaran porque implementar algo que ya hay bastante, y la verdad que probé casi todos los existentes (no puedo dar nombre ni criticas porque conozco personalmente a algunos miembros de esos proyectos) y ninguno lleno mis expectativas, principalmente porque eran muy complicados a la hora de hacer consultas complicadas (varias consultas anidas, consultas con varias tablas, etc). Otra cosa que no me gustó es que crea todas las tablas en base a la definiciones en algún formato, en realidad es una característica muy útil, pero tiene un costo muy alto, que son muchas consultas (imagínese tener 100 tablas, realizar 100 consultas solo para hacer diffs). Todas esas características, tienen un costo bastante algo, que es mucho código en memoria por cada consulta, aunque exista métodos para alivianar de alguna manera esta ultima desventaja.

Mientras navega leyendo códigos, tratando de tener un idea de que hacer algo mas sencillo, de pronto al leer (para fines educativos) los fuentes de Menéame (donde tengo algunos mínimos e insignificantes aportes), pareció muy práctica la abstracción de la base de datos, por ejemplo la manera de como se abstrae la tabla user, no solo el acceso/modificación de la tabla User estan ahí, sino también todo lo relacionado con el usuario, lo cual hace todo bastante ordenado.

Tomando como base las clases de acceso de datos, más que nada el API en general, ninguna porción de código fue copiado ya que no podría por cuestiones legales (soy fanático de las licencias mas liberales, BSD o similares) comencé un proyecto llamado Simple ORM. Básicamente es un ORM bastante simple, no crea las tablas en base de una definición, tampoco hace lo inverso (osea generar codigo en base a tablas existentes), simplemente es una abstracción de los datos con un plus muy importante que es el cacheo de los mismo para optimizar (totalmente opcional). Esta construida sobre PDO, que agrega otra interfaz hacia la base de datos en sí, la cual al ser nativa (escriba en C) es bastante eficiente, y además emula transacciones y SQL preparadas con variables (útil para evitar SQL injections).

La verdad que hablar/escribir mucho no me gusta, así que vamos a la parte divertida, el código. La conexión   es bastante sencilla, casi como lo haríamos normalmente:

<?php
require "DB.php";

DB::setUser("root");
DB::setPass("foobar");
DB::setDB("testing");
DB::setDriver("mysql"); //Por defecto

Como vieron, nada de otro mundo, además nótese que la conexión no es realizada en este punto, sino que al ser necesitado, esto es así porque existe la probabilidad que la consulta a realizar ya este en el Cache. Ahora supongamos que contamos con la siguiente tabla SQL:

Simple DB example

Simple DB example

A continuación una simple representación de la base de datos utilizando SimpleORM:

<?php
class SessionModel extends DB
{
    public $startdate;
    public $endate;
    public $user;

    function user_filter(&$user)
    {
        if (!$user InstaceOf User) {
            $user = $user->ID;
        } else {
             $uobj = new User;
             $uobj->ID = $user;
             if (!$uobj->load()->valid()) {
                 throw new Exception("Invalid user");
             }
        }
    }

    function getTableName()
    {
        return "session";
    }
}

class User extends DB
{
    public $username;
    public $passwd;

    function passwd_filter(&$pass)
    {
        $pass = md5($pass);
   }

    function username_filter(&$username)
    {
        $oUsername = $this->getOriginalValue('username');
         if ($oUsername && $username != $oUsername) {
             throw new Exception("You can't modify your username");
         }
    }
}

Como vieron las clases son sencillas, solo necesitan declararse explícitamente las propiedades con el mismo nombre de las columnas (no necesariamente, esto puede cambiarse re-implementando el método relations — no está muy probado todavía) y nada mas. El filtrado/validación de los datos se realiza mediante la declaración de nuevo métodos con un nombre especial (nombre propiedad del objeto + “_filter”). Al ser de esta manera los filtros son bastante maleables, solo miren los métodos SessionModel::user_filter(), User::username_filter() y User::password_filter(), donde notamos que los filtros pueden modificar el dato a ser guardado o pueden detener la ejecución lanzando una excepción. También por defecto las clases tienen que tener el mismo nombre que las tablas o de lo contrario hay que redefinir el método getTableName().

Para realizar consultas, la clase en sí es muy limitada, ya que no provee ordenamiento, ni limitaciones (por ahora) de ningún tipo. Simplemente provee una interfaz amigable para las iteraciones, alteraciones e inserciones de datos.

$user = new User;
$user->username = "foobar";
/* "password" es transformado a su md5 antes del select [usea load()] */
$user->password = "password";
if ($user->load()->valid()) {
     /* Inserta un nuevo campo en la tabla session */
     $session = new SessionClass;
     $session->user = $user;
     $session->startdate = date("Y-m-d H:i:s");
     $session->save();
}

/* Ejemplo sencillo de Iteracion */
$sessions = new SessionClass;
$sessions->user = $user;
/* de este modo */
$sessions->load();
foreach ($sessions as $session) {
    /* hacer algo con la sesion */
}
/* o */
foreach ($sessions->load() as $session) {
    /* hacer algo con la sesion */
}

Hasta aquí nada fuera de lo común, y la verdad poco útil, ya que en la vida real se necesitan mucho mas que simples operaciones, y he aquí la parte que me gusta, como hacer cosas complicadas, y la verdad que la mejor manera (mas sencillo, mas eficiente) de hacer las cosas complicadas es usando SQL en sí, nada de otros sub-lenguajes de manipulación de datos, ni tantos objetos y métodos para formar una consulta. Hablando en ejemplos prácticos, supóngase que necesita un listado de los usuarios con más de 5 sesiones en un rango variable de fechas, ¿como lo haríamos?

/* Agregamos este método a la clase User */
function & getMostActivedUsers($min, $max) {
     $sql = <<<EOT
SELECT u.* FROM users u WHERE u.id in (
     SELECT id FROM session WHERE startdate > :idate && enddate < :edate
     GROUP BY id HAVING count(*) > 5
)
EOT;
     $this->setDataSource($sql, array("idate" => $min, "edate" => $max), true);
     return $this; /* opcional para ahora una linea al iterar */
}

/* Iteración de ejemplo donde también se muestra un alteración de los datos */
/* (no contemplada en mi modelo) */
$users = new User;
foreach ($users->getMostActivedUsers($min, $max) as $user) {
      /* Los datos tambien pueden ser accedidos como Arrays */
      $user['level'] = 'god';
      /* Si el ultimo parametro de setDataSource es false (por defecto) */
      /* esto lanzaría una excepción (util para consultas anidadas)       */
      $user->save();
}

Como vieron, es muy sencillo de extender, y es lo mas manual posible solo se necesita conocer bastante bien de SQL, siguiente a mi frase “mientras mas fácil es para los programadores, mas difícil para el servidor”(referente a los frameworks que ya hacen todo ;) )

La limitación mas notoria que me viene a esta hora (6:24 am) a la cabeza es que la tabla necesita tener una columna “id” ($obj->ID). Este puede ser auto-incrementado (recomendado) o puede ser otro valor. Esto no limita a tener tablas sin “id” (ejemplo notorio tablas auxiliares para guardar las relaciones de tablas n:n), que pueden ser implementados como métodos de algunas clases, prometo que escribiré lo mas pronto posible ejemplos mas complicado y como representarlo con SimpleORM.

En próximas semanas estaré escribiendo mas ejemplos sobre el uso de SimpleORM, y eventualmente seguiré modificando el proyecto y agregando nuevas características.

Inteligencia artificial para sugerir amigos

Siguiendo la serie de entradas que comencé hace unos días atrás con Pensando en paralelo - Introducción a Map/Reduce, hoy voy a escribir sobre una de las maneras de sugerir amigos para una red social, o cual otra aplicación que puedan encontrar.

Antes que nada, hago una pequeña introducción hacia mi proyecto PHPCluster. Básicamente proyecto implementa (o trata) algoritmos para la clusterización de datos, que hablando mal y rápido son técnicas para encontrar elementos similares en grandes conjuntos sin tener conocimiento previo de ninguno de los datos . Hasta ahora implemente dos algoritmos, el K-means (actualmente esta en funcionamiento, y lo estoy optimizando con algunas ideas raras que me vienen a la cabeza) y el Biclustering (no esta funcionando es solo un esbozo ya que su eficiente computación es complicada).

Algunas aplicaciones practicas son, por ejemplo, buscar textos (entradas de blogs, noticias, sitios webs, etc) similares, algunas de mis ultimas y mejores pruebas pueden ser vistas en mi wiki-privado de proyectos. En este caso daré un enfoque diferente para resolver el el problema de sugerir potenciales amigos a usuarios.

require "phpcluster/k-means.php";

/**
 *  Clase descendiente de KMeans que sobre-escribe el método getFeatures,
 *  ya que la clase KMeans esta preparada para utilizar palabras como "features".
 */
final class GroupOfFriends extends KMeans
{
    protected function getFeatures($friends)
    {
        $ids = explode(" ", $friends);
        return array_combine($ids, array_fill(0,count($ids), 1));
    }
}

Ahora con su propio dataset, o podrían utilizar el que yo utilice, deberían codificar la búsqueda de usuarios similares basado en amigos. Del resultado de la búsqueda saldrán algunos grupos de usuarios (en mis pruebas fueron 42 grupos). Obj: Este programa debe ser ejecutado desde la consola, nunca jamas desde Apache o algún otro webserver ya que tarda algún tiempo

$fsuggest = new GroupOfFriends;
/* cuantos grupos de usuarios quiero buscar*/
$fsuggest->setCentroids(60);
/* porcentaje de similitud entre usuarios */
$fsuggest->setThreshold(45);

foreach(file("friendship-dataset.txt") as $line) {
    list($id, $friend) = explode("\t", trim($line), 2);
    $fsuggest->addElement($id, $friend);
}

/* a buscar los usuarios similares */
$clusters = $fsuggest->doCluster(300);

En uno de los grupos, al pertenece mi usuario, tuvo a los siguiente miembros, y me sorprendió mi idea ya que a casi todos los usuarios los conozco y todos somos informáticos (o casi todos). @pabloacastillo, @diegoplus, @crodas, @javox, @alejandroValdez, @willin64, @randallflagg, @eliaya, @bocho, @Robez, @xgurix, @chi83, @flyestudios. Dicha similitud de intereses no necesariamente significa que yo (@crodas) debería seguir a dichos usuarios, porque lo mas probable es que ya lo este haciendo (en este caso solo a 3 personas no les sigo en Twitter), sino que también a las personas que ellos siguen y que yo no son los potenciales amigos míos.

El resultado de la clusterizacion esta retornada en $cluster, que simplemente es una matriz que contiene como indice el numero de cluster (o grupo) y como valor una matriz con los usuarios que pertenecen al grupo. Como podrán notar, no todos los usuarios tienen un grupo, eso es gracias al $threshold lo cual asegura la calidad del clustering y a la vez reduce notablemente el numero de iteraciones. Como lo explicado en el párrafo anterior, esto no significa que el sistema no podrá sugerir potenciales amigos a dichos usuarios o a nuevos usuarios. El valor de $cluster debe ser guardar guardo en un medio persistente, para este ejemplo lo haré con json_* pero para la vida una base de datos MySQL o CouchDB son mejores alternativas.

Antes de guardar la informacion obtenida mediante el agrupamiento, son necesarios algunos pasos para hacer optima su lectura al momento de buscar amigos para una cierta persona. La primera es crear modelos de usuarios [1], porque es mas rápido comprar un usuario (a sugerirle amigos) contra esos modelos (en mis pruebas no pasaron de los 46) que comprarlo contra 7926 (la cantidad de usuarios en el dataset de pruebas). Los modelos de usuarios se forman a partir de los grupos de usuarios descubiertos, y tienen como amigos a todos los amigos de los usuarios en el grupo, si les parece confuso, miren el siguiente código:

function Array_Merge_ex1(&$arr, $arr1)
{
    foreach ($arr1 as $value) {
        if (!isset($arr[$value])) {
            $arr[$value] = 0;
        }
       $arr[$value] += 1;
    }
}

$knowledge = array();

foreach ($cluster as $group) {
    $data = & $knowledge[];
    $data = new stdclass;
    $following = array();
    foreach ($group as $member) {
        Array_Merge_Ex1($following, explode(" ",$member[0]) );
    }
    arsort($following);
    $data->value   = $following;
    $data->members = array_keys($group);
}

file_put_contents("knowledge.json", json_encode($knowledge));

Ahora se viene la parte interesante, el código que toma lo aprendido y sugiere posibles amigos. El algoritmo es relativamente sencillo y rápido de ejecutar (que es lo mejor), se carga en memoria lo aprendido y buscar el grupo mas similar al usuario y luego se sugieren los amigos del grupo que sean todavía sus amigos.

class FriendFinder
{
    /**
     *  distance, esta es la funcion que compara a un usuario
     *  con el modelo de usuarios.
     *
     */
    protected function distance($gfriend, $friends)
    {
        $shr = 0;
        $c1 = count($gfriend);
        $c2 = count($friends);

        foreach($friends as $item) {
            if (isset($gfriend[$item])) {
                $shr++;
            }
        }
        return 1 - ($shr/($c1+$c2 - $shr));
    }

    /**
     *  Retorna los detalles de los amigos de un usuario.
     *  (esto debe re-escrito en sitios de produccion)
     */
    final private function _getUserFriends($uid)
    {
        foreach(file("friendship-dataset.txt") as $line) {
            list($id, $friends) = explode("\t", trim($line), 2);
            if ($id == $uid) {
                return explode(" ", $friends);
            }
        }
        throw new Exception("User ($uid) not found");
    }

    /**
     *  Retorna los detalles de los un usuario
     *  (esto debe re-escrito en sitios de produccion)
     */
    final private function _getUserDetails($uname)
    {
        foreach(file("userids.txt") as $line) {
            list($id, $extra)  = explode(" ", trim($line),2);
            list($name, $user) = explode("|", $extra);
            if ($user == $uname) {
                return array($id, $user, $name, $this->_getUserFriends($id));
            }
        }
        throw new Exception("User ($uname) not found");
    }

    /**
     *  Retorna los detalles de los un usuario por ID.
     *  (esto debe re-escrito en sitios de produccion)
     */
    final private function _getUserDetailsById($uid)
    {
        foreach(file("userids.txt") as $line) {
            list($id, $extra)  = explode(" ", trim($line),2);
            list($name, $user) = explode("|", $extra);
            if ($id == $uid) {
                return $user;
            }
        }
        /* todavia no tenemos el ID del usuario, en teoria nunca pasaria */
        /* pero como no tenemos toda la DB de twitter,  por suerte existe el */
        /* YSQL para consultar */
        $q    = "?q=select%20*%20from%20twitter.user.profile%20where%20id%3D";
        $q   .= "'${uid}'&format=json&env=http%3A%2F%2Fdatatables.org%2Falltable";
        $q   .= "s.env&callback=";

       $content = file_get_contents("https://query.yahooapis.com/v1/public/yql?$q");
        $content = json_decode($content);
        return $content->query->results->item->meta[1]->content;
    }

    /**
     *  Esta funcion carga en memoria lo previamente aprendido
     *  (esto debe re-escrito en sitios de produccion)
     */
    final public function getPossibleFriends($name)
    {
        $info   = $this->_getUserDetails($name);
        $groups = json_decode(file_get_contents("knowledge.json")); 

        $distance = 20;
        foreach ($groups as $id => $group) {
            /* json_decode trata los arrays como objectos de stdclass (PHP5)*/
            $gfriend = get_object_vars($group->value);
            $d = $this->distance($gfriend, $info[3]);
            if ($d < $distance) {
                $distance = $d;
                $gmatch   = $id;
            }
        }

        $group = get_object_vars($groups[$gmatch]->value);
        $cands = array();

        foreach (array_keys($group) as $buddy) {
            if (array_search($buddy, $info[3])===false && $buddy != $info[0]) {
                $cands[] = $this->_getUserDetailsById($buddy);
            }
            if (count($cands)==15) break;
        }

        return $cands;
    }
}

$friend = new FriendFinder;
var_dump($friend->getPossibleFriends('crodas'));

A continuación los resultados para algunos amigos míos y sus recomendaciones.

pabloacastillo

array(15) {
  [0]=>
  string(8) "cleonati"
  [1]=>
  string(6) "chelun"
  [2]=>
  string(11) "grungelover"
  [3]=>
  string(8) "nambucom"
  [4]=>
  string(11) "marcoarturo"
  [5]=>
  string(10) "tipocracia"
  [6]=>
  string(10) "biblosfera"
  [7]=>
  string(9) "Mailplane"
  [8]=>
  string(13) "oscarsanchezo"
  [9]=>
  string(13) "punkgodangell"
  [10]=>
  string(6) "dsosap"
  [11]=>
  string(8) "IRONLOBO"
  [12]=>
  string(8) "sigridee"
  [13]=>
  string(10) "horaciusdr"
  [14]=>
  string(9) "wordpress"
}

piojita

array(15) {
  [0]=>
  string(8) "Kokochon"
  [1]=>
  string(10) "maxwellweb"
  [2]=>
  string(6) "eliaya"
  [3]=>
  string(7) "taguiar"
  [4]=>
  string(6) "czayas"
  [5]=>
  string(6) "pp1713"
  [6]=>
  string(10) "LadyIracix"
  [7]=>
  string(11) "manuelacuna"
  [8]=>
  string(11) "javierpreda"
  [9]=>
  string(11) "fabiojose80"
  [10]=>
  string(8) "cleonati"
  [11]=>
  string(11) "grungelover"
  [12]=>
  string(8) "nambucom"
  [13]=>
  string(7) "mharcos"
  [14]=>
  string(14) "SantiagoValdez"
}

diegoplus

array(15) {
  [0]=>
  string(4) "GLun"
  [1]=>
  string(12) "LauEsplendix"
  [2]=>
  string(11) "flyestudios"
  [3]=>
  string(8) "willin64"
  [4]=>
  string(7) "carlink"
  [5]=>
  string(4) "QLRP"
  [6]=>
  string(7) "rubuntu"
  [7]=>
  string(14) "littletiramisu"
  [8]=>
  string(5) "kirai"
  [9]=>
  string(9) "galletita"
  [10]=>
  string(8) "PoKeTiTa"
  [11]=>
  string(6) "lastfm"
  [12]=>
  string(11) "daveexplosm"
  [13]=>
  string(6) "Pk_JoA"
  [14]=>
  string(14) "pisitoenmadrid"
}

tetsumo

array(15) {
  [0]=>
  string(6) "eliaya"
  [1]=>
  string(4) "GLun"
  [2]=>
  string(7) "lettuix"
  [3]=>
  string(7) "carlink"
  [4]=>
  string(4) "QLRP"
  [5]=>
  string(14) "littletiramisu"
  [6]=>
  string(5) "kirai"
  [7]=>
  string(9) "galletita"
  [8]=>
  string(8) "PoKeTiTa"
  [9]=>
  string(6) "lastfm"
  [10]=>
  string(11) "daveexplosm"
  [11]=>
  string(6) "Pk_JoA"
  [12]=>
  string(14) "pisitoenmadrid"
  [13]=>
  string(6) "Aterea"
  [14]=>
  string(9) "Baratijas"
}

cleonati

array(15) {
  [0]=>
  string(7) "piojita"
  [1]=>
  string(14) "pabloacastillo"
  [2]=>
  string(5) "abcpy"
  [3]=>
  string(13) "sheldoncooper"
  [4]=>
  string(4) "GLun"
  [5]=>
  string(12) "LauEsplendix"
  [6]=>
  string(8) "willin64"
  [7]=>
  string(15) "ElRinconDelGeek"
  [8]=>
  string(7) "carlink"
  [9]=>
  string(4) "QLRP"
  [10]=>
  string(7) "rubuntu"
  [11]=>
  string(14) "littletiramisu"
  [12]=>
  string(5) "kirai"
  [13]=>
  string(9) "galletita"
  [14]=>
  string(8) "PoKeTiTa"
}
La calidad de los resultados solo pueden medidas mediante los “feedbacks” de los usuarios, así que veremos que dicen mis amigos arriba mencionados.

Happy coding!