paralelismo: python e twisted

4 05 2009

parent-childExecutar algumas tarefas em paralelo no python, usando threads, pode ser problemático, especialmente quando há I/O envolvido.

Apesar do interpretador do python usar as threads nativas do sistema operacional (na maioria dos *nix, pthreads), ele não é 100% thread-safe. Isso não é um bug, mas sim um recurso usado para evitar travamento ou computação incorreta de valores.

Do texto original:

The Python interpreter is not fully thread safe. In order to support multi-threaded Python programs, there’s a global lock, called the global interpreter lock or GIL, that must be held by the current thread before it can safely access Python objects. Without the lock, even the simplest operations could cause problems in a multi-threaded program: for example, when two threads simultaneously increment the reference count of the same object, the reference count could end up being incremented only once instead of twice.

Therefore, the rule exists that only the thread that has acquired the global interpreter lock may operate on Python objects or call Python/C API functions. In order to support multi-threaded Python programs, the interpreter regularly releases and reacquires the lock — by default, every 100 bytecode instructions (this can be changed with sys.setcheckinterval()). The lock is also released and reacquired around potentially blocking I/O operations like reading or writing a file, so that other threads can run while the thread that requests the I/O is waiting for the I/O operation to complete.

Do outro lado, temos o Twisted. Para mim, o Twisted é uma super biblioteca de I/O, com todos os recursos necessários para tratar tarefas de modo assíncrono (non-blocking), considerando ainda aquelas que bloqueiam a execução por determinado tempo (blocking).

Internamente, o Twisted mantém um thread pool para executar as tarefas síncronas, como por exemplo executar um INSERT em banco de dados. Para tal, existem as funções threads.deferToThread e reactor.callInThread.

Porém, se considerarmos o GIL, mencionado acima, temos como resultado um belo problema: enquanto uma tarefa que necessita I/O síncrono está sendo executada em uma thread, o interpretador do python fica bloqueado naquela operação e todo o resto fica parado. Isso causa uma perda de desempenho sem tamanho, e diversos outros efeitos colaterais (como time-out em sockets, etc).

Solucionar o problema de paralelismo no python não é tão complicado, mas também não é tão simples. Existem dois módulos que conheço, que fazem isso: pyprocessing e multiprocessing.

Ambos usam uma API similar à do módulo threading, mas ao invés de threads, criam processos usando fork(), que por sua vez, executam outro interpretador do python e se livram dos efeitos do GIL em um único processo. Mas, quando usados em conjunto com o Twisted, necessitam diversas adaptações para a comunicação entre os processos pai e filhos, pois essa comunicação é feita através de pipes.

Com tudo isso junto, o GIL começa a se tornar um problema e a coisa toda já se parece com uma grande confusão, que para muitos já parece não ter solução decente. Em suma, é o seguinte: escrever programas que necessitam parelelismo em python exige usar pyprocessing ou multiprocessing, mas quando o programa é inteiro assíncrono usando Twisted, tudo fica complicado.

Isso obviamente aconteceu comigo em um sistema relativamente grande, que precisava executar a classificação de alguns dados em paralelo, e quando usava o thread pool do Twisted, o processo inteiro ficava lento devido à grande quantidade de I/O para ler e gravar arquivos no disco. Era o GIL me atrapalhando.

Para solucionar esse problema, escrevi um módulo que usa a função spawnProcess do próprio Twisted, e automaticamente trata do pipe entre os processos pai e filho. Ainda, escrevi um protocolo de comunicação entre eles que permite transmitir e receber dados entre os processos de modo transparente, de maneira assíncrona.

Ainda, esse módulo possui uma classe que cria um pool de processos (não threads) para onde é possível despachar dados para serem processados em paralelo, e aguardar pelo resultado em um deferred, seguindo todo o padrão do Twisted.

Depois de executar todos os testes necessários e deixar o código estável, implementei isso no meu sistema e resolvi todo o problema do paralelismo de maneira simples e elegante, sem nenhuma gambiarra nem esquisitisse.

Denominado Twisted-Parallels, o módulo foi liberado sob a GPL v2 e está disponível no Google Code, com alguns exemplos de utilização.





consulta geográfica de endereço ip

26 03 2009

Google AppEngineQuem nunca precisou nem procurou por isso, é porque não sabe que é possível. Um tempo atrás, precisei desse tipo de consulta mas não encontrei nada gratuito, que fosse “ilimitado”. Normalmente, os sites que possuem esse serviço, gratuito, colocam cotas diárias e oferecem um plano pago.

Esses dias o Gleicon me passou um link, de um cara que teve a mesma necessidade, o mesmo problema, mas arrumou a solução: sabe-se lá como, ele “criou” uma base com todas as informações. No blog dele, tornou disponível gratuitamente, em dois formatos.

Um deles, é um dump do MySQL que qualquer um pode importar; o outro, é um arquivo ZIP contendo diversos arquivos em formato similar ao CSV (ele usa ponto-e-vírgula como delimitador, e coloca o conteúdo de cada campo entre aspas duplas).

Além de publicar essa base, cara (Marc) também provê um serviço gratuito para executar essas consultas; porém, quando fui usá-lo, estava fora do ar.

Pensei que isso pudesse ser interessante, se rodasse no App Engine do Google, que não custa nada, e é “ilimitado” pra qualquer um.  Fiz o seguinte:

  1. Criei o app lá, com nome free geoip
  2. Juntei os dados de IP por cidade, lista de países e regiões
  3. Importei tudo pro datastore, usando o bulk loader que vem no SDK
  4. O iWeb criou um frontend “bonito”

O resultado foi esse aqui:

http://freegeoip.appspot.com

Se alguém quiser fazer um favicon.ico, me avise!





pergunta: editor de texto ou ide?

13 03 2009




postgresql: fast full text search

12 03 2009

Atendendo a pedidos por comentários e e-mails que recebi sobre este assunto, decidi colocar aqui um esquema simples para demonstrar o que tenho usado para realizar busca em texto com postgresql.

O resultado é impressionante! Quando há muitos dados na base, é necessário particionar a tabela para diminuir o tamanho dos índices e manter a velocidade na busca – porém, este é um outro assunto que vou guardar para outro artigo.

O lance agora é apenas mostrar de maneira bem básica a construção de uma tabela, função plpgsql e trigger para usar o fast full text search.

Primeiro, alguns dados: crie um arquivo chamado data.txt com apenas duas colunas, separadas por ponto-e-vírgula, contendo nomes e endereços. Exemplo:

maria josé;rua um s/n
josé maria;rua dois s/n
pedro silva;rua um 5782
joaquim silva;rua dois 3030
maria pereira;rua 5, número 10
josé pereira;rua 5, número 15

Depois, é necessário criar uma nova base no postgresql e já importar esses dados nela. O arquivo que preparei pro exemplo já faz todo o trabalho, e provavelmente deverá ser ajustado para as suas necessidades.

Ai vai:


-- zz.sql 20090310 AF
-- fast full text search

-- create table for the data
DROP TABLE IF EXISTS data CASCADE;
CREATE TABLE data (
    id      SERIAL PRIMARY KEY,
    name    VARCHAR(32),
    addr    VARCHAR(64),

    name_ts TSVECTOR,
    addr_ts TSVECTOR
);
CREATE INDEX name_ts_idx ON data USING gin(name_ts);
CREATE INDEX addr_ts_idx ON data USING gin(addr_ts);

-- create function and trigger for setting tsvectors
DROP LANGUAGE IF EXISTS plpgsql CASCADE;
CREATE LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION tsv_update()
RETURNS TRIGGER AS $$
BEGIN
    NEW.name_ts := to_tsvector('portuguese', NEW.name);
    NEW.addr_ts := to_tsvector('portuguese', NEW.addr);
    RETURN NEW;
END
$$
LANGUAGE plpgsql;
CREATE TRIGGER tsv_update_trigger BEFORE INSERT OR UPDATE ON data
    FOR EACH ROW EXECUTE PROCEDURE tsv_update();

-- import data from csv-like into the database
\COPY data (name, addr) FROM 'data.txt' WITH DELIMITER AS E';'

Ao executar este arquivo pelo postgresql, toda a estrutura será automaticamente criada e os dados devidamente importados, inclusive preenchendo as colunas name_ts e addr_ts, que são do tipo tsvector e possibilitam o fast full text search.

Depois disso, basta se conectar no banco e executar a busca. Veja aí (ubuntu):

$ sudo su postgres -c psql
Welcome to psql 8.3.5, the PostgreSQL interactive terminal.

Type:  \copyright for distribution terms
\h for help with SQL commands
\? for help with psql commands
\g or terminate with semicolon to execute query
\q to quit

postgres=# CREATE USER zz WITH PASSWORD 'zz';
postgres=# CREATE DATABASE zz OWNER zz;
postgres=# \c zz
You are now connected to database "zz".
zz=# \i zz.sql
...

zz=# SELECT * FROM data WHERE plainto_tsquery('portuguese', 'maria') @@ name_ts;
id |     name      |       addr       |      name_ts       |            addr_ts
----+---------------+------------------+--------------------+--------------------------------
1 | maria josé    | rua um s/n       | 'jos':2 'mar':1    | 'rua':1 's/n':3
2 | josé maria    | rua dois s/n     | 'jos':1 'mar':2    | 'rua':1 's/n':3 'dois':2
5 | maria pereira | rua 5, número 10 | 'mar':1 'pereir':2 | '5':2 '10':4 'rua':1 'númer':3
(3 rows)

zz=# \q

O grande lance é que na busca comum por texto (full text search), o tsvector seria criado em tempo de execução usando a função to_tsvector. Nesse exemplo, já deixei uma função e um trigger para executar esse trabalho e armazenar o resultado na própria tabela, nos campos previamente mencionados, name_ts e addr_ts, que são indexados por um algoritmo diferente, especial para busca em texto, chamado gin.

Assim, a busca é feita direto neles, o que possibilita o fast full text search.





freeswitch, eventsocket, twisted!

27 02 2009

freeswitchApós meses tentando resolver problemas ridículos com meu discador automático baseado em Asterisk, acabei mudando totalmente o rumo do sistema e re-escrevi todo o código para o FreeSWITCH.

A versão anterior se conectava no manager do Asterisk, originava as chamadas, e naquela completa bagunça sem padrão ia controlando o fluxo da chamada com auxílio de um AGI. Funções como transferência e gravação com detecção de caixa postal geravam diversas complicações devido à maneira como o Asterisk funciona, e o resultado era muita dor de cabeça.

Agora, a bagunça é assíncrona, tem padrão, e controla totalmente o FreeSWITCH através do Event Socket. Ao se conectar no Inbound Socket, o sistema origina as chamadas com destino ao Outbound Socket, onde cada uma é controlada individualmente e todos recursos funcionam perfeitamente, inclusive as várias maneiras de realizar transferência (bridge).

O FreeSWITCH está próximo da perfeição no quesito funcionamento, pecando apenas na documentação e alguns detalhes relacionados ao retorno (erro, etc) na originação de chamadas. Porém, esses detalhes são totalmente contornáveis com soluções simples, sem gambiarras e maracutaias como era com o Asterisk.

Em uma máquina comum, consigo manter 60 ligações simultâneas consumindo apenas 3% de cpu time. E o FreeSWITCH, que faz todo o controle das chamadas – conversão de mídia, gravação, detecção de caixa postal, de fax, etc etc etc, consome apenas 30% de cpu time.

Tudo isso é feito usando um protocolo do Twisted pro Event Socket do FreeSWITCH, que escrevi no último final de semana – entre carnaval, rock, etc. E pra felicidade geral da nação, tornei público pela lisença GPLv2, disponível no Google Code com exemplos.





unix time na sexta feira 13

6 02 2009

friday13th1Direto do Wikipedia:

“A Era UNIX teve início no dia 1 de janeiro de 1970. O nome se deve ao fato de esta data, 01/01/1970 00:00:00 UTC, ser o marco zero do sistema de calendário usado pelo sistema operacional UNIX. Também pode ser chamada de era POSIX.”

E finalmente, o unix time 1234567890 está chegando. Isso ocorrerá na próxima sexta-feira 13, às 21:31:30 (GMT -2 pelo horário de verão em São Paulo).

Para confirmar, pode usar o console do python:

>>> import time
>>> time.asctime(time.localtime(1234567890))
‘Fri Feb 13 21:31:30 2009′

fonte: br-linux.org





paulistão 2009

27 01 2009

palmeirasAproveitando que meu time está em primeiro, aproveitei pra colocar mais um crawler com BautifulSoup, só que desta vez usando twisted.

A fonte de informação é o Globo Esporte, e pela leve bagunça que há no HTML e CSS, o código ficou meio feioso. Além disso, consegui deixar ainda mais feio pra poder imprimir bonito no terminal.

#!/usr/bin/env python
# coding: utf-8
# 20090127 AF - paulistão 2009, crawler

import re
from sys import stdout
from twisted.internet import reactor
from twisted.web.client import getPage
from BeautifulSoup import BeautifulSoup

crlft = re.compile(r'[\r\n\t]*')
URL = 'http://globoesporte.globo.com/Esportes/Futebol/Classificacao/0,,ESP0-9839,00.html'

def failure(err):
    print(err)
    reactor.stop()

def parser(contents):
    current = 1
    columns = 10

    f = lambda m: crlft.sub('', m.contents[0]+' ')
    soup = BeautifulSoup(contents, convertEntities='html')
    classes = ['borda borda-forte', 'borda semborda', ' borda-forte',
                ' semborda', 'time borda', 'borda', 'time ', '']

    stdout.write('% 18s' % 'TIME')
    for label in ['P', 'J', 'V', 'E', 'D', 'GP', 'GC', 'SG', '(%)']:
        stdout.write('% 5s' % label)
    stdout.write('\n')

    for item in soup.findAll('td', {'class':classes}):
        if item.find('span'):
            temp = '%02d. % 15s' % ((current / columns)+1,
                item.span.find('a') and f(item.span.a) or f(item.span))
            stdout.write(temp.encode('utf-8'))
        else:
            stdout.write('% 5s' % f(item))
            if not current % columns: stdout.write('\n')
        current += 1
    reactor.stop()

if __name__ == '__main__':
    deferred = getPage(URL)
    deferred.addCallback(parser)
    deferred.addErrback(failure)
    reactor.run()

E o resultado, no terminal:

$ python paulista.py
              TIME    P    J    V    E    D   GP   GC   SG  (%)
01.      Palmeiras    9    3    3    0    0    7    0    7  100
02.         Santos    6    2    2    0    0    4    1    3  100
03.    São Caetano    6    2    2    0    0    3    0    3  100
04.        Guarani    6    2    2    0    0    2    0    2  100
05.       Mirassol    4    2    1    1    0    5    3    2   66
06.      São Paulo    4    2    1    1    0    3    1    2   66
07.    Corinthians    4    2    1    1    0    3    2    1   66
08.    Ponte Preta    4    3    1    1    1    2    1    1   44
09.     Bragantino    3    2    1    0    1    4    3    1   50
10.       Paulista    3    2    1    0    1    2    2    0   50
11.    Santo André    3    3    1    0    2    1    2   -1   33
12.        Barueri    2    2    0    2    0    4    4    0   33
13.          Oeste    2    2    0    2    0    2    2    0   33
14.         Ituano    1    2    0    1    1    1    2   -1   16
15.    Botafogo-SP    1    2    0    1    1    4    6   -2   16
16.  Guaratinguetá    1    2    0    1    1    2    4   -2   16
17.        Marília    1    3    0    1    2    3    8   -5   11
18.       Noroeste    0    2    0    0    2    1    4   -3    0
19.     Portuguesa    0    2    0    0    2    0    3   -3    0
20.     Mogi Mirim    0    2    0    0    2    0    5   -5    0




twisted, http headers

18 01 2009

Nhac. Não costumava usar o twisted pra quase nada. Normalmente, fazia tudo na mão ou usava asyncore com asynchat nativos do python.

Nos últimos meses passei a usar twisted pra algumas coisas, e nos últimos dias precisei ler os cabeçalhos provenientes do servidor web para identificar o tipo do conteúdo fornecido na resposta (content-type), usando getPage.

Descobri duas coisas:

  1. o getPage simplesmente não fornece os cabeçalhos (twisted 8.1.0)
  2. empresas fazem oferta de emprego nos cabeçalhos http de sites

O primeiro item acima foi resolvido com um hack usando o próprio código do twisted, e umas pequenas modificações. Basicamente, re-rescrevi apenas um método do HTTPClientFactory usado pelo getPage, e sobrescrevi no próprio módulo client do twisted. Uma alternativa seria copiar o código do getPage e fazê-lo usar o novo factory, mas teria que escrever muito.

Apenas um detalhe, é que depois disso feito, o comportamento do programa inteiro se torna diferente quando o getPage for chamado, e os callbacks dele retornam um tuple ao invés de uma string com o conteúdo fornecido pelo web server.

#!/usr/bin/env python
# coding: utf-8
# 20090118 - AF

from twisted.web import client
from twisted.internet import reactor

class _HTTPClientFactory(client.HTTPClientFactory):
    def page(self, page):
        if self.waiting:
            self.waiting = 0
            self.deferred.callback((self.response_headers, page))

def callback(response):
    headers, contents = response
    print headers
    reactor.stop()

if __name__ == '__main__':
    client.HTTPClientFactory = _HTTPClientFactory
    deferred = client.getPage('http://fiorix.wordpress.com')
    deferred.addCallback(callback)
    reactor.run()

Ao executar o programa, fiquei impressionado não por ele ter funcionado, mas sim pelo conteúdo nos cabeçalhos http do wordpress.com:

$ python headers.py
{’x-nananana’: ['Batcache'], ‘vary’: ['Cookie'], ‘x-hacker’: ["If you're reading this, you should visit automattic.com/jobs and apply to join the fun, mention this header."], ‘last-modified’: ['Sun, 18 Jan 2009 17:38:11 +0000'], ‘connection’: ['close'], ‘cache-control’: ['max-age=300, must-revalidate'], ‘date’: ['Sun, 18 Jan 2009 17:38:11 GMT'], ’server’: ['nginx'], ‘content-type’: ['text/html; charset=UTF-8'], ‘x-pingback’: ['http://fiorix.wordpress.com/xmlrpc.php']}

Mandaram muito bem.





unix shell

18 01 2009

O interpretador de comandos dos sistemas operacionais Unix e Unix-like é a interface tradicional para operar o computador. Por meio de comandos, o usuário direciona o sistema para tarefas específicas.

O interpretador, conhecido como shell, normalmente suporta uma linguagem de script para que os comandos possam ser executados de maneira sequencial, permitindo automatizar tarefas rotineiras.

Mas, internamente, o que faz o shell? Bem, as etapas básicas são as seguintes:

  1. imprime o prompt de comando: $ para usuário ou # para root
  2. lê a linha digitada pelo usuário
  3. remove CRLF (\r\n) e depois separa a linha em strings, onde houver espaço
  4. fork(): duplica o conteúdo do próprio processo (parent) no sistema, criando um processo filho (child)
    • no child: execvp() executa o comando digtado – tipo ls -l
    • no parent: wait(NULL) aguarda o processo filho terminar

Embora os shells mais avançados como bash e csh possuam uma enorme quantidade de funções, tais como as da biblioteca readline, um shell apenas com as etapas mencionadas acima funciona perfeitamente.

Aqui está o exemplo:

/* 20090118 - AF */
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>

static char *stripcrlf(char *line)
{
    char *p;
    for(p = line; *p; p++)
        if(*p == '\r' || *p == '\n') { *p = '\'; break; }
    return line;
}

static void split(char *line, char **args)
{
    while(*line) {
        while(*line && *line == ' ') *line++ = '\';
        *args++ = line;
        while(*line && *line != ' ') line++;
    }
}

int main()
{
    char *p, line[4096], *args[sizeof line/2];

    for(;;) {
        fprintf(stdout, getuid() ? "$ " : "# ");
        fflush(stdout);

        memset(line, 0, sizeof line);
        if(!fgets(line, sizeof line, stdin)) {
            fprintf(stdout, "\n");
            clearerr(stdin);
            continue;
        }

        p = stripcrlf(line);
        if(*p) split(p, args);
        else continue;

        if(!fork()) {
            if(execvp(args[0], args) == -1) perror("exec");
        } else wait(NULL);
    }
    return 0;
}

NOTA: a imagem no topo foi criada por Paul Bourke em 1989, encontrada neste site.





urban dictionary crawler

8 01 2009

udlogo2Algum tempo atrás, o Urban Dictionary teve uma API para que outros sistemas e sites pudessem fazer busca nos termos de lá, que são muito legais.

Hoje, o link para a API não funciona mais, e virou um termo do dicionário. Procurando no google, encontrei um link que menciona uma API de acesso via SOAP com WSDL, mas também não é muito útil porque segundo o administrador de lá (15 de setembro) o formulário que emite as chaves de acesso está quebrado.

Em outras palavras: não existe mais API pro Urban Dictionary. Apesar a API de SOAP ainda funcionar, não é possível emitir novas chaves e por isso não é possível ter novos usuários com acesso a essa API. Não apenas eu, mas um outro cara gostaria de ter acesso ao Urban Dictionary através de uma API mais simples.

Enquanto eles não se manifestam, fiz um crawler usando BeautifulSoup, que resolve esse problema de um jeito meio tosco, mas pelo menos é simples e funciona.


#!/usr/bin/env python
# coding: utf-8
# 20080108 AF

import urllib
from BeautifulSoup import BeautifulSoup

def urbandict(search, limit=5, cutafter=256):
    query = urllib.urlencode(dict(term=search))
    url = 'http://www.urbandictionary.com/define.php?' + query
    response = urllib.urlopen(url)
    soup = BeautifulSoup(response.read(), convertEntities='html')

    fix = lambda item: item.replace('\r', '').replace('\n', '')
    cut = lambda item: len(item) > cutafter and item[:cutafter] + '(...)' or item
    extract = lambda item: isinstance(item, unicode) and item or \
        (item.name == 'a' and item.contents[0] or '')

    for item, count in zip(soup.findAll('div', attrs={'class':'definition'}), range(limit)):
        yield cut(' '.join([fix(extract(k)) for k in item.contents])).encode('utf-8')

for term in urbandict('stupid'):
    print term + '\n'

O limite padrão para a quantidade de respostas retornadas é 5, embora todas elas sejam capturadas. Graças à organização do site, isso é possível de forma simples pois os resultados são agrupados em DIVs cuja classe é “definition”.

Também, as seguintes funções modificam a exposição dos resultados:

  • fix: remove CRLF, e faz com que cada resultado seja uma única linha
  • cut: corta cada resultado após cutafter bytes, e adiciona (…)

Dessa maneira, fica fácil embutir os resultados do Urban Dictionary em qualquer lugar: um site, um programa no desktop, etc.

$ python ud.py
Someone who has to look up “stupid” in the dictionary because they don’t know what it means.

1) George W. Bush.  2) Karl Rove  3) Dick Cheney  4) You get the idea!