Forem: William Spader

Go Channels: Creating the Simplest TCP Chat only w/ STD

William Spader — Tue, 12 Dec 2023 17:02:21 +0000

I strongly believe that the best way to learn a new programming language is by doing side projects.

In this article we will write the simplest TCP Chat only using STD in Go, after that you can improve and add features as you want.

We can start talking about the imports needed for this project

imports, types and structs

import (
    "log"
    "net"
    "time"
)

type MessageType int

type Message struct {
    Conn net.Conn
    Type MessageType
    Text []byte
}

const (
    NewClient MessageType = iota
    DisconnectedClient
    NewTextClient
)

log: add time information for each printed log and writes to os.Stderr by default.
net: will help us to listen to TCP protocol and to stablish a connnection.
time: for throttling implementation, don't need to worry right now.

main()

func main() {
    ln := startServer()

    channel := make(chan Message)
    go Chat(channel)

    for {
        conn, err := ln.Accept()
        if err != nil {
            log.Println("Could not accept connection. ", err)
        }

        channel <- NewMessage(conn, NewClient, nil)
        log.Println("connection accepted. ", conn.RemoteAddr())

        go HandleConnection(conn, channel)
    }
}

Now we can talk about each line to better understand and adding code as needed.
The line ln := startServer() calls a method that returns a TCP listener.

startServer()

func startServer() net.Listener {
    ln, err := net.Listen("tcp", ":9595")
    if err != nil {
        log.Fatalf("Could not listen on port %s. Shutting down ...\n", Port)
    }

    log.Printf("Listening on port %s\n", Port)
    return ln
}

We call net.Listen("tcp", ":9595") to create a TCP listener on port 9595. Then, if something goes wrong there isn't much we can do, so we log and exit the app.
log.Fatalf() writes to stderr and exit the app.
If the listener worked, we return to main().

go Chat(channel)

Our application will have 1 go routine for each connected user, so we need a channel to communicate between go routines. When a user sends a message, we need to send that message to all users.

func Chat(broadcastChan chan Message) {
    clients := make(map[string]net.Conn)
    lastNewTextClient := make(map[string]time.Time)
    for {
        msg := <-broadcastChan
        if msg.Type == NewClient {
            clients[msg.Conn.RemoteAddr().String()] = msg.Conn
            log.Println("New client = ", msg.Conn.RemoteAddr().String())
        } else if msg.Type == DisconnectedClient {
            delete(clients, msg.Conn.RemoteAddr().String())
            msg.Conn.Close()
            log.Println("Client disconnected. Connection closed.")
        } else if msg.Type == NewTextClient {
            lastTime := lastNewTextClient[msg.Conn.RemoteAddr().String()]
            if !lastTime.IsZero() && lastTime.After(time.Now().Add(-time.Second*5)) {
                msg.Conn.Write([]byte("The time elapse between messages is 5 seconds."))
            } else {
                lastNewTextClient[msg.Conn.RemoteAddr().String()] = time.Now()
                for _, conn := range clients {
                    if conn.RemoteAddr().String() == msg.Conn.RemoteAddr().String() {
                        continue
                    }
                    conn.Write(msg.Text)
                }
            }
        } else {
            log.Println("Unknown message type received = ", msg.Type)
        }
    }

This function has another infinite for-loop, so we can keep the connection alive with the user.
We create a map of users to add and remove users from the app as needed.
We also create a map to keep track of the last message from a user, so each user can only send a new message after 5 seconds.
The line msg := <-broadcastChan await for the next message from the channel.
If it is a NewClient, then add this client to the map of users.
If it is a DisconnectedClient, then remove this client from the map of users and close the connection.
If it is a NewTextClient, then we iterate over the users and send the message to all other users except the one who sent it.

infinite for-loop

We open a infinite for-loop so the server stay alive indefinitely. Inside the for-loop we call ln.Accept(), this function blocks the routine until a new connection arrives and return this connection to us i.e. the conn variable

channel <- NewMessage(conn, NewClient, nil)

If the ln.Accept() worked, we send a message to the channel to inform that a new user has arrived.
Now, the NewMessage function is defined as

func NewMessage(conn net.Conn, msgType MessageType, buffer []byte) Message {
    if msgType == NewClient {
        return Message{Conn: conn, Type: NewClient}
    } else if msgType == DisconnectedClient {
        return Message{Conn: conn, Type: DisconnectedClient}
    } else if msgType == NewTextClient {
        return Message{Conn: conn, Type: NewTextClient, Text: buffer}
    } else {
        return Message{Conn: conn}
    }
}

go HandleConnection(conn, channel)

Finally, we have the implementation of the last function from main()

func HandleConnection(conn net.Conn, channel chan Message) {
    for {
        buffer := make([]byte, 512)
        _, err := conn.Read(buffer)
        if err != nil {
            channel <- NewMessage(conn, DisconnectedClient, nil)
            break
        }

        channel <- NewMessage(conn, NewTextClient, buffer)
    }
}

If there is any errors to read the user message, we disconnect the client and break the connection after close it.
If we successfully read the message, we send the message to the channel.
Don'f forget, all messages sent to the channel will be handled by the Chat(channel) function, as is the only moment in the app that read from the channel.

Now, you can improve this code and add new features. This app has only one chat for all users, so one idea can be to add users to groups.

Hope this article helps to better understand the usage of channels in practice!

Spring Data & MongoDB — Pagination+Sorting w/ Aggregation and Lookup

William Spader — Tue, 12 Dec 2023 15:56:08 +0000

Problem: Need to perform pagination+sorting with nullable filters and properties from two collections.

One collection holds the ID of the document from another collection that has the property we need to retrieve.

For those using reactive mongodb, the ReactiveMongoRepository only extends from ReactiveSortingRepository and we also want the following behavior:

a: { otherCollectionId: 1, info: 2}
b: { otherCollectionId: 1, info: 3}
c: { otherCollectionId: 2, info: 1}
findByOtherCollectionIdAndInfo(1, 2) //returns document a
findByOtherCollectionIdAndInfo(1, null) //returns documents a and b

Solution

Consider you have the following two collections where collection A has the id from collection B through otherCollectionId property.

Collection A
{
  "_id": ObjectId("..."),
  "otherCollectionId": "...",
  "info": "Some info",
  "anotherInfo": "Some other info"
}

Collection B
{
  "_id": ObjectId("..."),
  "label": "Some label"
}

Your API needs to respond to the client containingcollectionA infos + the label property from collectionB, and it must be paginated with the possibility of sorting through the label property.

To get the chunk of data, we can use the following code

mongoTemplate.aggregate(aggregation, "collectionA", Result.class)
return Aggregation.newAggregation(
  Aggregation.match(getCriteria(filter)),
  projectionOperation,
  getLookupOperation(),
  getUnwindOperation(),
  addLabelField(),
  projectionOperationWithLabel,
  Aggregation.sort(pageable.getSort()),
  Aggregation.skip((long) pageable.getPageNumber() * pageable.getPageSize()),
  Aggregation.limit(pageable.getPageSize())
);

The getCriteria(filter) method may be

private Criteria getCriteria(BusinessObject.Filter filter) {
  List<Criteria> criterias = new ArrayList<>();

  Optional.ofNullable(filter.getInfo())
    .ifPresent(info-> criterias.add(Criteria.where("info").is(info)));

  Optional.ofNullable(filter.getOtherCollectionId())
    .ifPresent(otherCollectionId -> criterias.add(Criteria.where("otherCollectionId").is(otherCollectionId)));

  return new Criteria().andOperator(
    criterias.toArray(Criteria[]::new)
  );
}

The projectionOperation may be

ProjectionOperation projectionOperation = Aggregation.project(
  "info", "anotherInfo"
).and(ConvertOperators.ToObjectId.toObjectId("$otherCollectionId")).as("convertedId");

In the project operation above, we need to convert otherCollectionId property to ObjectId before the lookup, so we can compare same data type.

Then, getLookupOperation() method may be

private LookupOperation getLookupOperation() {
  return LookupOperation.newLookup()
          .from("collectionB")
          .localField("convertedId")
          .foreignField("_id")
          .as("joinedData");
}

The convertedId property is the otherCollectionId but as ObjectId.

Then, depending on the situation, you can flat the resulting array from the lookup operation like this

private UnwindOperation getUnwindOperation() {
  return Aggregation.unwind("$joinedData");
}

Now, we add the label property from the collectionB

private AddFieldsOperation addLabelField() {
  return AddFieldsOperation.addField("label").withValue("$joinedData.label").build();
}

Then, we can perform another project operation containing the label property and remove the joinedData to get only the data we need. We also perform another conversion to get otherCollectionId property.

ProjectionOperation projectionOperation = Aggregation.project(
  "info", "anotherInfo", "label"
).and(ConvertOperators.ToObjectId.toObjectId("$convertedId")).as("otherCollectionId");

Finally, if you need the total count to return something like PageImpl from the API, you can perform a count query on the collectionA.

Then, you’ll have something like this to return from the repository, where it.getT1() is the list of items and it.getT2() is the total of elements:

return new PageImpl<>(it.getT1(), pageable, it.getT2())

Hope this article helps!

HashTable — A Ciência da Estrutura de Dados Key-Value

William Spader — Mon, 14 Feb 2022 01:47:03 +0000

Uma das coisas mais comuns em programação é realizar uma pesquisa por um item que pode estar armazenado em alguma estrutura.

Será apresentada a ideia da implementação interna de estruturas como Dict em Python, HashMap em Java, Map ou Object em JavaScript, entre outras.

Arrays de Acesso Direto - arr[i]

Arrays estáticos de acesso direto possuem complexidade de busca O(1), então se meu usuário precisa pesquisar por uma chave que representa um número inteiro, basta pesquisar diretamente arr[chave].

O que acontece quando o usuário precisa armazenar 10^9 itens? Vamos alocar um array com tamanho 10^9? Seria um uso exacerbado de memória.

Hashing & HashTable

É possível manter a busca em O(1) usando menos espaço em memória? Podemos armazenar itens em um array menor para continuarmos com os benefícios do array estático, mas precisamos de uma técnica de mapeamento de chaves para pesquisar em um índice diferente nesse array. Essa técnica é chamada de hashing e o array menor é chamado de hashtable. Esse array menor pode diminuir ou aumentar de tamanho conforme necessidade, por exemplo em muitas operações de inserção e deleção.

Quando recebermos a chave de um item, passaremos ela por uma função chamada de hash function. O resultado dessa função de hash será o índice que devemos acessar na hashtable. Porém, essa função de hash pode causar um problema conhecido como colisão, que é quando duas chaves possuem o mesmo resultado após passar pela função de hash.

No caso abaixo, as chaves são nomes de pessoas. Os nomes Rose e Zig após passarem pela função de hash resultaram no mesmo índice da hashtable.

Se cada posição da hashtable pode armazenar apenas um item, como resolveremos isso?

Chaining

Chaining é uma estratégia onde as posições da hashtable armazenam um ponteiro para uma estrutura de dado sequencial, essa estrutura sequencial pode ser um array dinâmico ou uma lista encadeada.

Após a chave passar pela hash function, é necessário efetuar uma busca linear na estrutura sequencial daquele índice da hashtable e comparar as chaves que estão na lista.

Essa busca linear não é um problema desde que a lista encadeada permaneça muito pequena. Para isso, a função de hash precisa evitar ao máximo as colisões.

Open Addressing

Não considero uma solução muito adequada, pois precisamos garantir que todas chaves terão um lugar próprio na hashtable. Isso significa que se o usuário necessitar de 10^9 chaves, nossa hashtable terá 10^9 índices.

Mas como se resolve o problema de colisões em open addressing? Uma das técnicas é chamada de linear probing. Se o retorno da função de hash é de um índice já utilizado, simplesmente executamos a função até que um índice vazio seja encontrado.

A próxima seção será especificamente sobre hash functions, mas por agora considere M como o tamanho atual da hashtable e hash(chave) como sendo a chamada da função de hash.

Sendo assim, para buscar um índice vazio utilizando linear probing podemos fazer:

Se hash(chave) % M não está vazio, tentamos (hash(chave) + 1) % M.

Se (hash(chave) + 1) % M não está vazio, tentamos (hash(chave) + 2) % M, e assim por diante.

Existem outras estratégias para lidar com o problema de colisões em open addressing, algumas delas podem ser encontradas nas referências. Geralmente não é uma técnica utilizada pela dificuldade de implementação de acordo com a técnica para escapar de colisões e por quase sempre não conhecermos previamente o total de chaves.

Hash Functions

Após visto duas técnicas para implementação de hashtable, precisamos saber como implementar efetivamente a função de hash. Afinal, essa implementação é o coração da estrutura de dado, pois precisa praticamente evitar colisões distribuindo as chaves pela hashtable.

Método da Divisão — Hash Function

É o método mais simples para mapear um inteiro que pertence a um domínio de dados grande para um domínio menor.

h(k) = k mod m — (k % m) — , onde k é a chave original que está sendo buscada ou inserida e m é o tamanho atual da hashtable. Sendo assim, todo inteiro k será mapeado para algum índice dentro do domínio da nossa tabela hash.

Porém, teremos muitas colisões se muitas chaves por mod m começarem a ter o mesmo resto de divisão.

Hash Universal

Se quisermos que a performance da estrutura seja independente das chaves. O problema mencionado no método da divisão pode ocorrer com qualquer função de hash escolhida, mas há uma fórmula que gera uma família de funções de hash boas o suficiente para grande parte.

h(k) = (((ak + b) mod p) mod m)

A fórmula acima é uma geradora de funções de hash. Os valores a e b são escolhidos de forma aleatória, desde que a seja diferente de zero. O valor p é um número primo maior do que m. Por fim, m é o tamanho atual da hashtable.

Os valores acima não mudam a cada chave que vamos mapear na hashtable, eles são escolhidos e utilizados de forma fixa para distribuir os dados na estrutura. O único momento que esses valores mudam é quando precisamos realocar o tamanho da hashtable.

Realocação da Tabela de Hash

Pode ser necessário quando há muito espaço livre na tabela, e para economizar espaço resolvemos diminuí-la ou quando a quantidade de chaves está perto do tamanho total da tabela, nesse caso precisamos aumentá-la.

Além de escolher uma nova função de hash a partir da fórmula geradora, também precisamos pegar todos os itens que estavam na tabela antiga e passar eles pela nova função da hash para inserirmos na nova tabela. Essa operação custa O(n) tempo e é comum em estruturas que encapsulam arrays estáticos.

Referências

MIT OCW 6.006 - Hashing

Open Addressing - GeeksForGeeks

Complexidade de Algoritmos — Big O

William Spader — Wed, 02 Feb 2022 18:43:11 +0000

Determinar a complexidade de um algoritmo é importante para conhecermos a performance de um código. Em Ciência da Computação, é utilizado o método de notação assintótica para definirmos a eficiência dos algoritmos.

Será abordado a notação Big O com a liberdade de retirar formalismos matemáticos, para que o assunto seja abordado e entendido com maior facilidade intuitiva. Python é a linguagem de programação dos exemplos.

Big O

É uma notação assintótica para analisar a eficiência de um algoritmo conforme os valores de entrada crescem, considerando sempre o pior cenário. Em outras palavras, quão rápido cresce o tempo que meu algoritmo demora para resolver o problema em relação ao tamanho do input recebido?

O(1)

Chamado de tempo constante, é o menor poder computacional gasto.

Como na figura acima, atribuições à variáveis e cálculos aritméticos são exemplos de O(1).

O(n)

Significa que o código cresce de forma linear.

A função linear_time é O(n), pois realiza uma iteração em um vetor e as operações dentro do for são de tempo constante O(1). Sempre teremos nos nossos códigos várias notações para cada bloco ou linha, nesse caso sempre levamos em consideração a notação com a maior grandeza.

Portanto, embora a linha 4 realize uma operação O(1), iremos desconsiderá-la no cálculo pelo fato de possuir impacto muito menor comparada a notação O(n). Caso queira ser um pouco mais preciosista, não há erro em dizer que a função linear_time cresce na grandeza O(n) + O(1) + O(1) + O(1), agora estamos considerando cada operação computacional para determinar a grandeza da função.

O(n^2)

Como você ja sabe que um código O(n) é como um loop contendo operações constantes dentro, então O(n^2) são dois loops aninhados com operações constantes.

Portanto, sempre que há dois loops aninhados é como se estivéssemos percorrendo uma matriz. No exemplo acima é uma matriz 3x3 (3^2), ou seja, 9 elementos. Logo, O(n^2).

O(log(n))

Nesse contexto, considere log na base 2. A partir dessa definição, dizemos que um código é O(log(n)) quando divide pela metade o tamanho do problema a cada etapa.

A busca binária é um algoritmo bastante conhecido e possui como notação assintótica O(log(n)). Considere um vetor com 16 elementos, e agora vamos aplicar a busca binária nesse vetor para verificar/encontrar um número.

Se o algoritmo divide o problema pela metade a cada etapa, significa que na primeira execução teremos o vetor com 16 elementos, na segunda 8 elementos, na terceira 4 elementos e assim por diante.

Considerando log na base 2, temos Log(16) = 2 * 2 * 2 * 2 = 2^4. Isso significa que para um vetor de 16 elementos, a função demorará 4 etapas para cumprir com o objetivo proposto.

O(2^n)

Com certeza uma das piores complexidades que nossos algoritmos podem ter, pois cresce exponencialmente baseado na entrada.

A função de fibonacci é um exemplo que cresce nessa grandeza, abaixo está a árvore de fibonacci criada quando utilizamos a ingênua fórmula F(n + 2) = F(n + 1) + F(n) como algoritmo.

A árvore acima é criada quando tentamos calcular o quinto número de fibonacci. Percebe que tivemos que calcular o terceiro número de fibonacci duas vezes? Agora pense, quão ruim ia ficar essa árvore se estivéssemos calculando o sexto número de fibonacci? E o sétimo?

Cada vez que vamos aumentando em apenas 1 número a nossa entrada, o número de operações computacionais cresce exponencialmente.

Claro que estamos considerando calcular fibonacci de forma recursiva, utilizando a fórmula apresentada anteriormente.

Considerações

Sempre realize o exercício de descobrir quão eficiente é o algoritmo que você acabou de criar para solucionar um problema.

Em talvez contrapartida, tome cuidado para não demorar muito para entregar suas tarefas sendo perfeccionista e sempre buscando a melhor performance possível. Se estiver com dificuldade em visualizar uma forma eficiente, resolva o problema de um jeito simples e depois procure por formas de otimizá-lo.

Referências e Links Úteis

Introduction to Algorithms

Geeks for Geeks - Analysis of Algorithms