DEV Community: gbenga fagbola

Building a Distributed Search Engine in Go

gbenga fagbola — Fri, 31 Jan 2025 18:25:15 +0000

Introduction

Searching through large datasets efficiently is a common problem in distributed systems. This article demonstrates how to build a distributed search engine using Go’s concurrency features, allowing multiple workers to process and search data simultaneously.

Understanding the Concept

A distributed search engine divides the dataset into chunks, assigns each chunk to a worker, and runs multiple workers in parallel to perform the search. This improves performance by reducing the time needed to find a match, especially for large datasets.

In our example, we will:

Simulate a distributed search across a user database.
Use multiple worker goroutines to search concurrently.
Use channels for communication between workers and the main process.

Code Implementation

Below is the complete Go implementation of a distributed search engine:

package main

import (
    "log"
    "os"
    "strings"
    "time"
)

// User struct represents a user with an email and name
type User struct {
    Email string
    Name  string
}

// DataBase is a slice of User representing stored user data
var DataBase = []User{
    {Email: "adebayo.olu@example.com", Name: "Adebayo Olu"},
    {Email: "chioma.okafor@example.com", Name: "Chioma Okafor"},
    {Email: "ibrahim.abubakar@example.com", Name: "Ibrahim Abubakar"},
    {Email: "ngozi.uchenna@example.com", Name: "Ngozi Uchenna"},
    {Email: "chinedu.ekene@example.com", Name: "Chinedu Ekene"},
    {Email: "toyin.adebayo@example.com", Name: "Toyin Adebayo"},
    {Email: "uche.nwosu@example.com", Name: "Uche Nwosu"},
    {Email: "bola.johnson@example.com", Name: "Bola Johnson"},
    {Email: "femi.ogunleye@example.com", Name: "Femi Ogunleye"},
    {Email: "damilola.ogun@example.com", Name: "Damilola Ogun"},
    {Email: "amaka.nnamdi@example.com", Name: "Amaka Nnamdi"},
    {Email: "segun.olawale@example.com", Name: "Segun Olawale"},
    {Email: "bisi.adewale@example.com", Name: "Bisi Adewale"},
    {Email: "kunle.akintola@example.com", Name: "Kunle Akintola"},
    {Email: "funke.adebisi@example.com", Name: "Funke Adebisi"},
    {Email: "nkechi.okonkwo@example.com", Name: "Nkechi Okonkwo"},
}

// Worker struct represents a worker that processes a subset of users
type Worker struct {
    users []User  // Slice of users assigned to the worker
    ch    chan *User  // Channel for sending found users
    name  string  // Worker name identifier
}

// NewWorker initializes a new Worker instance
func NewWorker(users []User, ch chan *User, name string) *Worker {
    return &Worker{users: users, ch: ch, name: name}
}

// Find searches for a user email within the worker's assigned users
func (w *Worker) Find(email string) {
    for i := range w.users {
        user := &w.users[i]
        if strings.Contains(user.Email, email) { // Check if email contains search term
            w.ch <- user // Send found user to the channel
        }
    }
}

// DistributeWorkload creates workers dynamically based on database size
func DistributeWorkload(data []User, ch chan *User) {
    numWorkers := 3 // Define number of workers
    batchSize := len(data) / numWorkers

    for i := 0; i < numWorkers; i++ {
        start := i * batchSize
        end := start + batchSize
        if i == numWorkers-1 {
            end = len(data) // Assign remaining users to last worker
        }
        go NewWorker(data[start:end], ch, "Worker"+string(i+1)).Find(os.Args[1])
    }
}

func main() {
    if len(os.Args) < 2 {
        log.Fatal("Usage: go run main.go <email>")
    }

    email := os.Args[1] // Get the email argument from command line
    ch := make(chan *User) // Create a channel for user search results

    log.Printf("Looking for %s", email)

    // Distribute workload dynamically
    DistributeWorkload(DataBase, ch)

    // Listen for user results or timeout if no result is found
    for {
        select {
        case user := <-ch:
            log.Printf("The email is %s owned by %s", user.Email, user.Name)
        case <-time.After(100 * time.Millisecond):
            log.Printf("The email %s was not found", email)
            return // Exit loop after timeout
        }
    }
}

Explanation of the Code

User Data and Database:
- We define a User struct containing Email and Name fields.
- A slice of User acts as our database.
Worker Struct and Methods:
- Each Worker processes a subset of the database.
- The Find method checks if an email contains the search term and sends results to a channel.
Concurrency Using Goroutines:
- The dataset is split among three workers.
- Each worker runs concurrently to search for the provided email.
Communication with Channels:
- A channel is used to send found users from workers to the main function.
- The select statement listens for results or a timeout.
Timeout Mechanism:
- If no results are received within 100ms, the search terminates with a “not found” message.

Running the Code

To run the program, execute:

$ go run main.go miller

This will search for emails containing “miller” and return matching results.

Benefits of This Approach

Parallel Processing: Multiple workers search concurrently, reducing response time.
Scalability: More workers can be added to handle larger datasets.
Efficiency: The timeout prevents unnecessary waiting.

Conclusion

This article demonstrated how to build a simple distributed search engine using Go. By leveraging goroutines and channels, we efficiently parallelized the search process, making it scalable for larger datasets. Future improvements could include:

Using a distributed architecture like Apache Kafka or Elasticsearch.
Implementing an indexing mechanism for faster searches.
Running the system across multiple machines for even better performance.

Let me know your thoughts and how you’d optimize this approach further!

Multiple Pointers

gbenga fagbola — Mon, 02 May 2022 13:30:07 +0000

The idea of the multiple pointer pattern revolves solely around creating identifiers or pointers that correspond to an index or position, which moves towards a specific direction based on the condition set.

This pattern is quite efficient for solving problems with minimal space complexity.

Example:

Write a function that accepts a sorted array of integers. The Function in question should find the first pair of integers where the sum is 0, the expected output should return the pair of numbers whose value summed up to 0 and undefined if the pair does not exit.

function sumZero(arr) {

    let left = 0;
    let right = arr.length -1;

    while(left < right){
        let sum = arr[left] + arr[right];

        if(sum === 0){
            return [arr[left], arr[right]];
        } else if(sum < 0){
            left++
        } else if(sum > 0){
            right--
        }
    }
}

sumZero([-3, -2, -1, 0, 1, 2, 4])
returns [-2, 2]

sumZero([-4,2,1])
returns undefined

From the above block of code, we have a variable declared for pointers left and right. Such that the left pointer sweeps through the array from the first item in the list towards the ending of the list. While the right pointer starts from the end of the list and moves towards the beginning of the list. All this happens provided the left identifier wouldn't overlap with that of the right.

Frequency Counter

gbenga fagbola — Thu, 14 Apr 2022 18:44:59 +0000

This pattern employs JavaScript Object to store the frequency or rather the occurrence of data and is most useful in data comparison.

Let's jump right in with an example.

Write a function named similar such that it accepts two (2) arrays. The intended function should return true if every value in array one has its corresponding value squared in array two.

such as

similar([1,2,3],[4,1,9])   this would return true
similar([1,2,1],[4,4,1])   this would return false

Making use of the Frequency Counter Approach Below:

function similar(array1, array2) {

    if (array1.length !== array2.length){
        return false;    
    }

    let freqCounter1 = {};
    let freqCounter2 = {};

    for(let val of array1){
        freqCounter1[val] = (freqCounter1[val] || 0) +1      
    }

    for(let val of array2){
        freqCounter2[val] = (freqCounter2[val] || 0) +1      
    }


    for(let key in freqCounter1){

        if(!(key ** 2 in freqCounter2)){
            return false
        }

        if(freqCounter2[key ** 2] !== freqCounter1[key]) {
            return false;
        }
    }

   return true; 
}

Test Case:

similar([1,2,3,2,5],[4,9,4,1]) returns false
similar([1,2,3],[9,1,4]) returns true

Explanation

So let's take things in a systematic approach. Feel free to employ the intended approach we went through in the last lesson to solve the problem set yourself.

Function Declaration: declaration of a function named similar which would take a set of two distinct arrays as an input.
Edge Case: the first block of code after the function declaration. This can be referred to as a short circuit whereby it runs before the core algorithms logic and returns a set result in case of invalid or undesired input.

In this case, check if the length of the first array is not equal to that of the second array and returns an output. In this case, it just returns a false statement.

Objects declaration: you can say this is where the core logic of this approach relies on, but note it doesn’t necessarily have to be an object, such that it can also be an array, although the Big O of Object states that we have a constant rate of accessing, removing, and adding an item into it, which makes it a much-optimized choice. Empty Objects were declared to store the frequency of each character in the array respectively as named above.

The same goes for freqCounter2.

Core Objective: now let's focus on the core objective, which is to look for the presence of the square of each character in array1 within array2. From the block of code for(let key in freqCounter1){ we loop through each key within freqCounter1 in other to make comparisons, such as this resulting block of code if(!(key ** 2 in freqCounter2)){ which acts as a short circuit which checks if the square of each key in freqCounter1 is not present in freqCounter2, and return false.
Final Piece: Now the final block of code is aimed at checking if the square of each element in freqCounter2 has a corresponding equal within freqCounter1. If any is found wanting 😩, its evaluates to false, and if not we arrive at the end of the code block where our code retuns true;if all conditions were passed.

Another Example

Given two strings, write a function to determine if the second string is an anagram of the first. an anagram is a word, phrase, or name formed by rearranging the letters of another, such as RAT is an anagram of TAR

function anagrams(first, second) {

    if(first.length !== second.length){
        return false;
    }


    let freqCounter1 = {};
    let freqCounter2 = {};

    for(let val of first){
        freqCounter1[val] = (freqCounter1[val] || 0) +1
    }

    for(let val of second){
        freqCounter2[val] = (freqCounter2[val] || 0) +1
    }

    console.log(freqCounter1);
    console.log(freqCounter2);

    for(let key in freqCounter1){
        if(!(freqCounter2.hasOwnProperty(key))){
            return false
        }

        if(freqCounter1.values !== freqCounter2.values){
            return false;
        }
    }

    return true;
}

Test Case:

similar(bat, tab) returns true
similar(salt, tale) returns false

Final Example
Count unique Integers in a List

function countUnique(arr) {

    let counter = {};
    let count = [];

    for(let val of arr){

        counter[val] = (counter[val] || 0) +1;     
    }


    for(let key in counter){
        count.push(key)
    }

    return count.length;
}

countUnique([-2,-1,-3,1])
returns 4

I hope the above examples shed light on the conceptualized pattern discussed. See you in the next lecture.

Problem solving Patterns

gbenga fagbola — Tue, 05 Apr 2022 14:55:14 +0000

This is an introduction to common problem solving pattern

Hey Guys 😊,

So as discussed in the previous lecture, we would be looking at common problem solving patterns we can implement when faced with a problem set. So let’s jump right in.

Let me go through the intended approach before making a list of patterns I hope to go through.

How to Improve in Problem Solving

(i). Develop a strategic Plan:

I admit it can be really tempting to jump right into solving a problem set with little or no understanding, with hopes of navigating through it. But I propose you devise a sound enough plan for accomplishing such a task.

(ii). The mastery of common problem-solving patterns:

Of course, this would give you a grasp on the most common form which various problem sets might take. Thereby giving you foresight towards tackling these said problem sets.

Let Highlight the Problem-Solving Process

Understand the Problem.
Explore Concrete Examples.
Break the Problem-set down.
Simplify - make a proposed solution.
Implement the solution to various case study.
Refactor - optimise the solution.

Let now take a deeper look into the highlight above

Understanding the Problem set

You should try to restate the essence of the problem set according to your understanding.
Take a clear look at the intended input & expected output. Keeping in mind possible edge cases.
Determine if the expected output can be determined from the input.
Have a final glance through and ensure you have taken note of every important detail.

Explore Concrete Examples

Look through every possible edge case, such as invalid input, the presence of whitespace or special characters etcetera in other to devise a solid algorithm.
Make users' Stories to aid in a graphical are relatable presentation. Which can show a profound level of understanding and also help others understand the problem set and your intended solution.
Make simple examples, then complex ones to show mastery.

Breaking things down

There are quite a few ways to break down the problem set (the algorithmic way) such as:

Sudo code
Flow diagram et Cetera.

Simplifying the Problem Sets

After following through the above steps, it is only expected that we get to finally simplify the problem and deduce a solution that would suffice.

Implementation of the said Solution

We should ensure our solution passes all intended test cases, both easy and challenging. While envisaging possibilities of inconsistent input that might arise and possible ways out.

Having a Look-Back.

I employ you to create the habit of having a much-optimized version of your solution. Answering the questions

If there is the expected outcome
Checking out other possible approaches
How understandably is the solution (which refers us to the criteria we spoke previously about)
It adaption to a similar problem set
Can the Performance of the Solution be Improved? (in terms of time & Space Complexity)
Check if it follows basic conventions and standards.

Example

Let's Go through a Simple Problem set and implement the above steps. You can try this yourself, and kindly note that we are bound to have different answers but a similar approach.

Question Write a function that takes a string and returns the frequency of each character in the given String, considering the laid down principles above.

From 1: Understanding the Problem

In simple words, return the occurrence of each character in a given string.
We can deduce a string as the intended input.
Yes, the expected Output can be gotten from the input.

From 2: Exploring concrete examples

Ben was given the assignment to count the re-occurring characters in a list of countries. So he got fancy and employed an automated process. Via an algorithmic approach.

From 3: Breaking things down

Defining the function
Instantiation of a counter
Examination of every character in the input
Looking out for keen details such as similarities and count
Return the output or statement based on expected edge cases.

From 4: Simplifying the problem set

function countCharacter(arr){

    let countResult = {};  

    for(let i = 0; i < arr.length; i++){       
        let countIndex = arr[i].toLowerCase();       
        if(countResult[countIndex] > 0){       
            countResult[countIndex]++;    
        } else {     
            countResult[countIndex] = 1;       
        }
    }
    return countResult;
}

countCharacter("hey guy!")

result
{" ": 1, !: 1, e: 1, g: 1, h: 1, u: 1, y: 2}

from 5: Contemplate Edge-Cases

function countCharacter(arr){
    let countResult = {};  

    for(var char of arr){                
        char = char.toLowerCase();
        if(/[a-z0-9]/.test(char)){
            if(countResult[char] > 0){
                countResult[char]++
            } else {
                countResult[char] = 1;
            }
        }
    }
    return  countResult;
}

countCharacter("hey guy!")

result
{h: 1, e: 1, y: 2, g: 1, u: 1}

from 6: Refactoring - Looking Back

function countCharacter(arr){
    let countResult = {};  

    for(var char of arr){                
        char = char.toLowerCase();
        if(/[a-z0-9]/.test(char)){
        countResult[char] = (countResult[char] || 0) +1;     
        }
    }
    return  countResult;
}

countCharacter("hey guy!")

result
{h: 1, e: 1, y: 2, g: 1, u: 1}

Note, you can easily run the code blocks above in your chrome snippet to see the respective results yourself.

The above code snippet is a solution to the problem statement above, and do not worry if you don’t understand. I would start explaining line by line each code block I write from the forthcoming lectures as this is to help you understand the underlying concept first.

See you in the next part 👏🏻.

Algorithm & Data Structure

gbenga fagbola — Tue, 29 Mar 2022 13:48:52 +0000

This is a beginners guide towards understanding & mastery of data structure & algorithm using Javascript.

In a quick and well-detailed series of lectures, I would be taking you on a quest of disintegrating Algorithms & Data-Structure in JavaScript, which is solemnly aimed at beginners.

Prerequisites

Basic Knowledge of JavaScript
Patience and Time to Read Though

And for those who might have the question “Is a functional System required?” well for this stage, I would say an emphatic No and advice you to follow through, even if you make use of a pen and a piece of paper.

The overall concept and ability to tackle challenges should be your key takeaway from this tutorial.

So let's get started.
In this part of the series, I would be taking a look at the introduction to Data-Structure & Algorithm, and of course, its importance, Big O Notation, Object & Arrays in JavaScript, and finally introduce known and unknown Problem-Solving Patterns.

Data Structure & Algorithms

`Algorithms`

In computer programming terms, an algorithm in its' basic term refers to a set of well-defined instructions or processes aimed at solving a particular problem or accomplishing a certain task.

It practically takes a set of inputs and produces the desired output. For example,

Quality of an Algorithm Revolves around these key points

Its Input and output should be clearly defined.
It should be easily understandable.
It should be easily applied to solve similar problem sets.

There's a big misconception that algorithm has to be written in a particular programming language, whereas I am here to tell you it is not necessarily the case.

As defined above, an algorithm is a broken-down process toward solving a problem set or accomplishing a set task.

Let's take, for example, writing an algorithm to add up two numbers, leaving aside any possible edge case.

Algorithm to Add two numbers

Step 1: Start
Step 2: State variables for example let number1 = 5, number2 = 8.  
Step 3: Add num1 and num2; assign the result to sum to the value of num1 & num2.
Step 4: display - return the sum 
Step 5: Stop

The above might not be the most elaborate way, but I hope the message is passed.

What is the importance of an Algorithm in a real-life scenario?
To me, it simply helps complex problem-sets seem less intimidating.

`Data Structure`

Data structure can be referred to as storage that is used to store and organize the presentation of data. It is a way of representing data so that it can be accessed and implemented efficiently.

Choosing the right data Structure pattern is quite a big deal for a project's overall working schema.

Two Main Data Structure Categories

1. Linear Data Structures: In Linear data structures, elements are arranged in a sequence that is one after the other. But due to its structure, when implementing complex programs, It might not be the best solution.

Examples of Linear Data Structures

Array Data Structure
Stacked Data Structure
Queue Data Structure
Linked Data Structure

2. Non-Linear Data Structures: Unlike the linear data structures above, elements in non-linear data structures are not in any sequence. They are mainly arranged hierarchically.

Example of Non-Linear Data Structures

Graph Data Structure
Tree Data Structure
Map Data Structure

Importance of Knowing Data Structures
As highlighted earlier, Data Structures help you know when and how to select the best fit data structure pattern for your project or that of your company.

Let's Put a pin into data structures for now, till we circle back in later series.

BIG O

The Importance of this is quite as emphatic as it sounds 🙃.
Big O can be described as a approach, or way of generalizing or rather comparison of codes and their performance.

In much simpler terms, It's a way to know which algorithm approach or block of code is best by basic comparison standards.

Let's take a look at 2 different solutions to the problem set I saw from an online resource.

Example
Write a function that calculates the sum of all numbers from 1 up to and including the said number n.

METHOD A

function addUp (n) {
   let total = 0;
   for (let i = 1; i <= n; i++){
      total += i;
   }
  return total;
}

METHOD B

 function addUp(n) {
    return n * (n + 1)/2;
 }

Comparing METHOD A to METHOD B is where big O comes in, whereby it takes into account key criteria, which are

Speed (how fast is it)
Space (if it's of lesser memory intensity)
Readability (if it's non-ambiguous to read & understand.

Summary
For Method A, the runtime of the function is solemnly dependent on how large the value of n (i.e what it has to process).
This gives us a Time Complexity - Big O of O(N). ---> linear

While for** Method B*, the big O is **constant* since the operation the function has to perform is restricted to basic arithmetic operations which would take the same amount of time to run no matter the size of n.

giving us the Time complexity - Big O of O(1) ---> constant

Big O gives us the ability to discuss the impact the input of a function has on its runtime.

whereas a function of n => f(n)

f(n) = n        linear
f(n) = n^2      quadratic
f(n) = 1        constant

Simplifying Big O

Let's look at various case studies and their simplified term

1. O(2n) = O(n)
2. O(500) = O(1)
3. O(13n^2) = 0(n^2)
4. O(n + 1) = O(n)
5. O(10000n + 5) = O(n)
6. O(n^2 + 5n + 8) = O(n^2 + n) === O(n^2)

kindly note

Constant and Smaller terms don’t really matter
Arithmetic Operation is Constant
Variable assignments are constant
Accessing elements in an array is constant
For a loop, the complexity of the said loop depends on the length of the loop multiplied by the complexity of what happens in the loop.

Time & Space Complexity rule of thumb
Most primitive are constant (booleans, numbers, undefined & null)
Strings are linear ( O(n) depends on the length of the string)

Let's check out an example to further explain space complexity.
for instance, a function that triple each element in an array,

function triple(arr){
   let newArray = [];
   for (let i = 0; i < arr.length; i++){
       newArray.push(3 * arr[i]);
   }
}

In summary, the length of the input array (arr) would directly impact the length of the new array.

therefore giving us a space complexity of O(n)

Analyzing Performance of Array & Object

`The Big O of JavaScript Object`

Objects are unordered data structures that are stored in a key-value pair

Perks

It is useful in cases you don't need an order
Fast access & Insertion

Insertion O(1)
Removal   O(1)
Searching O(N)
Access    O(1)

Object Methods

Object.keys O(N)
Object.values O(N)
Object.entries O(N)
.hasOwnProperties O(1)

`The Big O of JavaScript Array`

Arrays are ordered data structures.

Perk

Useful in cases where the order is needed.

Access.   O(1)
Searching O(N)
Insertion & Removal both depends on the position or rather index in which the operation is to be performed. but for the last element, there are both O(1)

Thats why .push and .pop are primarily faster than .shift and .unshift

Some Basic Array Methods

.push O(1)
.pop O(1)
.shift O(N)
.unshift O(N)

JavaScript Array Methods

I would strongly advise you to visit the link above from time to time and get an in-depth knowledge of Javascript array.

Next Topic

`Popular Problem Solving Pattern`

In the coming lecture, we would have hands-on practice towards common problem-solving patterns in algorithms and at least have an idea of where to start form while tackling problem sets.

My goal is not to bore you or rather impress with ambiguous words but rather convey in simple terms what the said subject matter is all about. On that note, would see you in the upcoming part.

React-Redux at it's Simplest!

gbenga fagbola — Thu, 24 Mar 2022 17:20:39 +0000

Hey guys! 👋🏽.

Thanks for joining.

First and foremost, my advice would be that you should always try as much as possible to understand the underlying concept of a tool, framework, language, etcetera before using - implementing it.

Which makes learning worthwhile and sort of fun.

After all, is said and done 🙃, let's get started. This lecture will be in different parts so as not to bore you.

React can practically be considered as a group of components that are rendered in a tree-like structure. Of which is mainly centred around User-Interface.

It gives room for State Management tools to play an important role, such as Redux, Graph-Ql etcetera. Redux is a great state management tool and not just for react. Kindly note.

Concept

I would go on a limb here and assume everyone reading is conversant with the concept of a Component or a component-driven development. So let's take a look at diagram 1.0 below

This shows how each component is mapped to its respective state.

From this diagram, I would discuss the underlying problem which would arise in a big project if the said method of directly appending a component to its state.

Props Drilling: Which means passing down-state / properties between nested child components, that can be passed down through many child component layers before it finally gets to where it would be used. Even though most child components it passes through do not require it.

2.Redundant code: this refers to rewriting a bunch of code block in a repetitive manner.

Looking at the stated problem above, Redux which actually got inspiration from database design such as event sourcing and happens to be great in the follow.

Great for managing large state.
Useful for sharing data between components.
Predictably state management, using the 3 principles below;

i). Single source of truth: One big collective object of data
ii). State appears to be read only: So that it's doesn’t get modified easily
iii). Changes are made using only pure functions: This simple means a function that returns an output based on the input.

From the diagram above, we can deduce the difference from diagram 1.0. whereby each component's respective state has been removed and stored in one massive data object. Which in return describes what our application state should look like. In simple terms means no component holds any state.

Redux Operation

Components that compose our application fires actions, these fired actions set a single piece of the state which can be accessible to all components in the application. The state is what we call a reducer.

Every reducer is simply a function that takes two arguments a state and an action. Whereby the state can be referred to as the previous state it was in and would end up returning to a new state at the end of the function. Hence, it circles back to the principle listed above which states that it is immutable.

The above diagram describes the operational flow of events.

This pattern is called the Flux pattern: in simple terms an action that gets dispatched in other to update the view.

This is quite unlike the MVC Pattern (model, view, controller): whereby action is read by the controller, then the model - data is updated based on the controller input. of course, the model updates the view.

From the Action: let's say an event from a user (such as a click on the mouse or keypress). this action goes through the

Middleware: the middleware can be described as a piece of code that receives the action fired before relaying it to the reducer.

Then, the Reducer which happens to be a pure function takes an input (state & action) and creates a corresponding state output that can be referred to as the store.

And finally, the store (that is the corresponding state) updates the DOM - view.

Seems to be a lot of states here. So let's clarify with an example.

The above is an example of a reducer with a practical approach of that of a user, which consist of two arguments as discussed above.

This works with a switch case which checks if type is the same as SET_ACTION_TYPE then we would return a new object via spreading the state. and the main reason we return a new object is to make sure our component re-renders. And if there were no changes made, our component would return the current state by default.

Thanks for joining once again. Much advance implementation coming up!!!