DEV Community: Nilesh Prasad

Monitoring AWS ECS Deployment failures

Nilesh Prasad — Thu, 26 Sep 2024 14:23:39 +0000

This post discusses how ECS state change events can be used to monitor deployment failures on ECS. To set the context, I work on a project where we use ECS to deploy containerized applications, and our CircleCI pipeline is responsible for building Docker images, pushing them to AWS ECR, and initiating the ECS deployment using the aws ecs update-service command. Our CircleCI job ends after this command, at which point we considered the deployment successful. However, the deployment isn't truly complete until the new containers are up and running, which created a gap in monitoring, as containers could fail to start due to issues like failed migrations, incorrect configurations, or resource allocation problems.

Relying solely on aws ecs update-service execution was misleading, as it didn't account for failures after the deployment was initiated. To address this, we needed to listen to ECS state change events, particularly for failed deployments. These events provide real-time insight into whether containers failed to start, allowing us to handle issues like failed migrations or resource allocation errors and notify team on Slack for further investigation.

Using EventBridge to Monitor ECS State Changes

Amazon EventBridge is a powerful event bus that can help monitor and respond to various AWS service events., including ECS deployment state changes. When you deploy containerized applications with ECS, ECS deployment state changes are automatically sent to EventBridge, specifically these:

SERVICE_DEPLOYMENT_IN_PROGRESS
The service deployment is in progress. This event is sent for both initial deployments and rollback deployments.

SERVICE_DEPLOYMENT_COMPLETED
The service deployment has completed. This event is sent once a service reaches a steady state after a deployment.

SERVICE_DEPLOYMENT_FAILED
The service deployment has failed. This event is sent for services with deployment circuit breaker logic turned on.

To track failed ECS deployments, we can set up an EventBridge rule that listens for SERVICE_DEPLOYMENT_FAILED events. This captures real-time failure information, allowing us to quickly respond to issues such as failed migrations, configuration errors, or resource limitations. Below is an example of the EventBridge rule used to listen for these failure events. When this rule matches an event, it can trigger AWS Lambda or other services to send alerts to your Slack channel, providing real-time visibility into deployment failures.

{
    "source": ["aws.ecs"],
    "detail-type": ["ECS Deployment State Change"],
    "detail": {
      "eventType": ["ERROR"],
      "eventName": ["SERVICE_DEPLOYMENT_FAILED"]
    }  
}

Here's an example of a failed deployment event that would trigger this rule. This event indicates that a task failed to start during the ECS deployment, potentially due to issues like incorrect configurations or missing dependencies.

{
   "version": "0",
   "id": "ddca6449-b258-46c0-8653-e0e3aEXAMPLE",
   "detail-type": "ECS Deployment State Change",
   "source": "aws.ecs",
   "account": "111122223333",
   "time": "2020-05-23T12:31:14Z",
   "region": "us-west-2",
   "resources": [ 
        "arn:aws:ecs:us-west-2:111122223333:service/default/servicetest"
   ],
   "detail": {
        "eventType": "ERROR", 
        "eventName": "SERVICE_DEPLOYMENT_FAILED",
        "deploymentId": "ecs-svc/123",
        "updatedAt": "2020-05-23T11:11:11Z",
        "reason": "ECS deployment circuit breaker: task failed to start."
   }
}

So, now we are able to capture failed deployment events on eventbridge rule. We now need to set target, where we want EventBridge to send any events that match the event pattern of the rule. In our case, we'll use AWS Lambda. We'll use Lambda to send slack alerts on our configured incoming webhooks. To read more on how you can setup slack webhook, read this later.

Setting Up AWS Lambda to Post Deployment Failure Alerts to Slack

This lambda function will parse the event, determine whether the failure occurred in staging or production, generate a direct URL to the affected ECS service, and send the failure details to a specified Slack channel. For detailed code, you can refer to this Lambda function code on GitHub Gist.

Conclusion and further readings

Monitoring ECS deployments is crucial to ensure that your applications are running smoothly. By using Amazon EventBridge to capture ECS state change events and integrating AWS Lambda with Slack, you can receive real-time notifications whenever a deployment fails.

For further readings, check out the following resources to deepen your understanding of ECS deployment events and the deployment circuit breaker:

These documents will help you gain a more in-depth understanding of the ECS deployment lifecycle and the circuit breaker feature that helps in rolling back failed deployments automatically.

Redis as a Message Broker: Deep Dive

Nilesh Prasad — Sat, 06 Jan 2024 11:58:22 +0000

Distributed task queues and message brokers are integral components of modern, scalable applications, helping to manage workloads and facilitate communication between different parts of a system. They help us decouple task submission from execution, i.e., they allow applications to submit tasks without worrying about when or where they will be executed. This separation enhances scalability and reliability, as the system can distribute tasks across various workers based on current load and availability, and execute them at the most opportune time.

In addition to being a super fast data store, Redis can also be used as a message broker for distributed task queues such as Celery.

Here’s how Redis and Celery interact in a distributed setup:

Task Submission: Services submit tasks to Celery with details and parameters.
Redis as Message Broker: Once a task is submitted, Celery uses Redis as the message broker to store this task. Redis holds these tasks in a queue-like structure, waiting for a worker to pick them up.
Task Queuing: Tasks wait in Redis until workers are ready, with queues organized by priority or type.
Worker Nodes: Celery workers continuously monitor the Redis queues for new tasks. They pick up tasks from Redis, distributed across various machines for scalability.
Task Execution: With Redis handling the task messages, Celery workers can focus on executing them. We can scale by running more workers or even distributing these workers across multiple machines, with Redis efficiently managing the task queue for all these workers. Workers process tasks, performing computations or interactions with databases or other components as needed, then return results.
Fault Tolerance and Retry Logic: Celery and Redis ensure no task is lost, retrying failed tasks and maintaining persistence.

This article aims to provide a comprehensive understanding of Redis as a message broker for Celery. We will develop a straightforward backend service using Django, designed to enqueue email sending tasks for Celery workers.

Deep Dive into Redis and Celery Integration

Code used in this article is hosted on Github (nileshprasad137/django-celery-redis-setup) but in order to understand this setup in detail, let's walkthrough some crucial steps to setup our Django backend to simulate sending emails asynchronously.

Setting up Django backend with Redis and Celery

Dockerise setup

We will dockerise our setup to install all the dependencies of our project includind Redis and Celery. Ensure docker.compose file have all the services defined.

Configure Django for Redis and Celery

Ensure your Django settings are configured to use Redis as the broker and backend for Celery.

settings.py

CELERY_BROKER_URL = 'redis://redis:6379/0'
CELERY_RESULT_BACKEND = 'redis://redis:6379/0'
CELERY_TASK_DEFAULT_QUEUE = 'default'

CELERY_TASK_QUEUES = {
    'low_priority': {
        'exchange': 'low_priority', # unused
        'routing_key': 'low_priority',
    },
    'high_priority': {
        'exchange': 'high_priority', # unused
        'routing_key': 'high_priority',
    },
    'default': {
         'exchange': 'default',
         'routing_key': 'default'
     }, 
}

Also, create a celery.py file next to settings.py. This file will contain the Celery instance and configuration:

celery.py

from __future__ import absolute_import, unicode_literals
import os
from celery import Celery
from django.conf import settings

# set the default Django settings module for the 'celery' program.
os.environ.setdefault('DJANGO_SETTINGS_MODULE', 'django_celery_redis.settings')

app = Celery("django_celery_redis", broker=settings.CELERY_BROKER_URL)  # App for all consumer facing tasks

# Using a string here means the worker doesn't have to serialize
# the configuration object to child processes.
# - namespace='CELERY' means all celery-related configuration keys
#   should have a `CELERY_` prefix.
app.config_from_object('django.conf:settings', namespace='CELERY')

# Load task modules from all registered Django app configs.
app.autodiscover_tasks()

Define tasks

Django is where tasks are defined. Here is a simple example of task in django for simulating sending an email.

@app.task
def send_email_simulation(email_address, subject, message):
    print(f"Sending email to {email_address} | Subject: {subject}")
    # Here, you would implement your email sending logic.
    time.sleep(2)
    return f"Email sent to {email_address} with subject {subject}"

We can then use Docker Compose to build and run your containers:

docker-compose up --build

This will start the Django development server, a Redis instance, and a Celery worker, all in separate containers.

By following these steps, we've successfully set up a Dockerized Django backend that integrates Redis as a message broker and Celery for task queue management, with Poetry for dependency handling. Our Django application is now ready to handle background tasks.

Note, this is a development setup and production setup will need some changes in order to make this secure.

Understanding Redis Internals in the Context of Celery

Lets start to delve deeper into redis data structures to understand how redis is acting as message broker.

On spinning our containers, celery tasks are autodiscovered.

Let's see what all keys are present in redis just when we spin up our container.

Here's a brief explanation of each of the keys we're seeing in your Redis instance when used with Celery:

_kombu.binding.celeryev:

This key is related to Celery Events (hence the "ev" in the name), which are special messages used for monitoring tasks within Celery.

_kombu.binding.high_priority / _kombu.binding.default / _kombu.binding.low_priority:

These particular keys represent the routing information for different queues: "high_priority," "default," and "low_priority" respectively. They define how messages (or tasks) are routed to these queues based on their bindings. Essentially, they are part of the configuration that determines where messages should be sent within the broker (Redis), helping Celery to organize and prioritize tasks by directing them to the appropriate queue based on their intended priority or category.

_kombu.binding.celery.pidbox: The pidbox is a special mailbox used by Celery for control and monitoring purposes (like inspecting worker stats or controlling worker processes).

In all cases, these _kombu.binding.* keys are part of how Kombu (the messaging library used by Celery) manages message routing and queues with Redis. They are not the queues themselves but the definitions of how messages should be routed to the appropriate queues based on their bindings. In Celery, the actual task messages are stored in Redis lists, and these bindings help ensure the messages are delivered to the correct list representing a queue.

Now, lets add a task through Django and see which keys gets added to Redis.

>>> # Trigger a low priority email
>>> send_email_simulation.apply_async(args=["user@example.com", "Hello", "This is a test email"], queue='low_priority')
<AsyncResult: 5ddc21b8-6832-4e58-83bb-c71da6a60916>

This task 5ddc21b8-6832-4e58-83bb-c71da6a60916 will first get added to low_priority redis list which will then be picked up celery worker. Once celery workers have finished executing the task, another meta key will be added in Redis.

127.0.0.1:6379> KEYS *
1) "_kombu.binding.celeryev"
2) "_kombu.binding.high_priority"
3) "_kombu.binding.celery.pidbox"
4) "celery-task-meta-5ddc21b8-6832-4e58-83bb-c71da6a60916"
5) "_kombu.binding.default"
6) "_kombu.binding.low_priority"
127.0.0.1:6379> TYPE celery-task-meta-5ddc21b8-6832-4e58-83bb-c71da6a60916
string
127.0.0.1:6379> GET celery-task-meta-5ddc21b8-6832-4e58-83bb-c71da6a60916
"{\"status\": \"SUCCESS\", \"result\": \"Email sent to user@example.com with subject Hello\", \"traceback\": null, \"children\": [], \"date_done\": \"2024-01-06T07:50:04.800480\", \"task_id\": \"5ddc21b8-6832-4e58-83bb-c71da6a60916\"}"
127.0.0.1:6379>

The keys that you're seeing in Redis starting with celery-task-meta- are the result of storing task results. These are not the tasks themselves, but metadata about the tasks that have been run, assuming you have task result backend configured to use Redis. These metadata keys store the information about task status, result, and traceback if there was an error.

Let's also try to check if our tasks get added to queues as list. If we have workers running and they are consuming tasks faster than we're enqueuing them, we might not see a build-up of tasks in Redis, as they're being taken off the queue and processed immediately. So to prevent it, we will queue up 1000 tasks at once so that we could see our tasks in list.

>>> for i in range(1000):
...     send_email_simulation.apply_async(args=["user@example.com", "Hello", "This is a test email"], queue='low_priority')
...
<AsyncResult: 7efab9a0-efa2-4898-9043-17965fd3d26b>
<AsyncResult: 57fa1346-6240-4bfb-9e90-a98a59552f5b>
.....

Let's see if low_priority key is present in redis after task has been sent to queues.

127.0.0.1:6379> KEYS *priority
1) "_kombu.binding.high_priority"
2) "low_priority"
3) "_kombu.binding.low_priority"

Here we go! Lets now check our first 3 entries of this list low_priority

Here's a brief rundown of how the task got added to low_priority:

Task Dispatch: A task is dispatched in your Django application with an indication that it should be routed to the low_priority queue. This can be done through the apply_async method or by setting the default queue for the task.
Serialization: The task's data, including arguments, execution options, and metadata, is serialized into a message. This is what we see as a long string in the Redis list. It's typically a base64-encoded representation of the task's information.
Push to Queue: Celery pushes this serialized message to the Redis list representing the low_priority queue. In Redis, this queue is simply a list, and new tasks are appended to the end.
Task Message Structure: The message contains detailed information, such as the task's unique ID, arguments, callbacks, retries, and more. When a Celery worker is ready to process tasks from the low_priority queue, it pops a message from this list, deserializes it, and executes the task.

At any point of time, we could also get waiting tasks to be picked up by celery workers,

127.0.0.1:6379> type unacked
hash
127.0.0.1:6379> hlen unacked
(integer) 4

We could see its contents using HGETALL.

Queue priority handling in Redis

Redis as a broker simplifies the queueing mechanism and doesn't use exchanges and routing keys like RabbitMQ and does not inherently support priority queueing but with careful application design, especially in conjunction with Celery, you can effectively manage task priorities. Here's how you can handle queue priorities using Redis as a broker for Celery:

Multiple Queues for Different Priorities: The most straightforward way to implement priority handling in Redis with Celery is by defining multiple queues for different priority levels, such as high_priority, medium_priority, and low_priority. You dispatch tasks to these queues based on how urgent they are.
Worker Queue Subscriptions: Workers can subscribe to multiple queues and prioritize them. A worker can listen to both high_priority and low_priority queues but check for tasks in high_priority first. This is typically managed by the order of queues provided when starting the worker:

celery -A proj worker -l info -Q high_priority,low_priority

This tells the worker to consume tasks from high_priority first, then medium_priority, and finally low_priority.

Understanding Exchanges in Celery with Redis

In messaging systems, an exchange is a concept that routes messages from producers to the appropriate queues based on various criteria. While this concept is central to more complex brokers like RabbitMQ, Redis, as used with Celery, does not inherently support the notion of exchanges due to its simpler, key-value store nature. However, understanding how Celery simulates or bypasses this functionality when paired with Redis is useful.

Simplified Routing: When using Redis as a broker with Celery, the exchange concept is simplified. Instead of a formal exchange routing messages to different queues based on bindings and rules, Celery directly pushes task messages to the specific Redis list representing a queue.

Default Exchange: Celery with Redis uses a default direct exchange type. In direct exchange, messages are routed to the queues with the name exactly matching the routing key of the message. Since Redis doesn't have a built-in exchange mechanism, the routing is handled internally by Celery.

Alternate Brokers and Comparison

Redis, with its straightforward setup and performance efficiency, serves well as a broker for many standard use cases, particularly when it's already in use for caching and pub/sub scenarios. Unlike advanced AMQP brokers like RabbitMQ, Redis does not offer complex features such as exchanges and routing keys, yet its simplicity often translates to cost-effectiveness and ease of management. The choice between Redis and more sophisticated brokers like RabbitMQ hinges on the specific demands of your application - considering task complexity, reliability needs, and scalability. For high-throughput, complex routing, or extensive scalability requirements, RabbitMQ or similar brokers might be more suitable, while Redis excels in scenarios valuing speed and simplicity.

Monitoring and Scalability

Using tools like Flower for real-time monitoring of Celery workers and tasks, and integrating Prometheus or Grafana for in-depth metrics and alerts, provides the visibility needed for robust operation. Scalability can be achieved by horizontally adding more Celery workers; for example, an e-commerce platform might increase from 10 to 50 workers during peak sales periods or a social media app might use auto-scaling to adjust worker count based on user activity.

Conclusion

In this article, we explored how Redis works as a message broker with Celery, looking into how it handles tasks and organizes them. We shed light on the journey of a task from start to finish, emphasizing Redis's essential role in making task management smooth and effective.

The supporting repository for this article is hosted at nileshprasad137/django-celery-redis-setup which can be used for further tinkering.

Happy coding!

Effective Unit Testing in Golang and Gin based projects

Nilesh Prasad — Mon, 11 Dec 2023 12:05:32 +0000

Unit testing is a critical part of building robust applications in the world of software development. Golang is known for its simplicity and efficiency, making it an ideal language for writing clean, maintainable code. In this article, we'll explore effective unit testing in Golang for projects built with Gin, Gorm, and PostgreSQL. We'll cover structuring a Golang project, testing against a real PostgreSQL database, and using Testify for testing utility.

In Golang, you could group tests per package using TestMain feature.

TestMain for Setup and Teardown

The TestMain function is a global setup and teardown mechanism provided by testify. It allows us to initialize and migrate resources before running tests and clean up afterward. This is particularly useful when there's a need for global setup or teardown actions that should be applied across all tests.

package main
import (
    "testing"
    "github.com/stretchr/testify/suite"
)

// TestMain sets up and tears down resources for all tests.
func TestMain(m *testing.M) {
    // Additional setup code here

    // Run all tests
    code := m.Run()

    // Additional teardown code here

    // Exit with the test result code
    os.Exit(code)
}

"Testify" library in Golang

The Testify (https://github.com/stretchr/testify) package extends the functionality of the standard Go testing library, making testing in Go more expressive and efficient.

Test Suites with Testify

Testify introduces the concept of test suites, allowing us to group tests into logical units. The suite package from Testify simplifies the management of test suites. This is beneficial when tests can be logically grouped together, sharing common setup or teardown logic.

package mypackage

import (
    "testing"
    "github.com/stretchr/testify/suite"
)

// MySuite is a test suite containing multiple related tests.
type MySuite struct {
    suite.Suite
}

func (suite *MySuite) SetupTest() {
    // Setup code before each test
}

func (suite *MySuite) TestSomething() {
    // Test code
}

func TestSuite(t *testing.T) {
    // Run the test suite
    suite.Run(t, new(MySuite))
}

When to Use TestMain and Test Suites

TestMain: In Go, you can have only one TestMain function per package. The TestMain function is a special function that allows you to perform setup and teardown tasks for your tests, and it is meant to be defined only once in the entire package. Use TestMain when there's a need for global setup or teardown actions that should be applied across all tests. This is especially relevant for scenarios like initializing and migrating databases or setting up external services.

Test Suites: The concept of test suites is typically associated with external testing frameworks like Testify. While you can define multiple test suites in a package using Testify, it's important to note that each test suite is essentially a separate testing entity and doesn't interact with other test suites. Each test suite may have its own setup, teardown, and test functions. Use test suites when you want to logically group tests that share common setup or teardown logic. This helps in maintaining a clean and organized test structure, making it easier to manage and execute related tests.

Project Structure and tests location

When structuring your Go projects, it's crucial to establish a well-organized layout that promotes readability, maintainability, and testability. Let's explore a sample project structure and discuss how to integrate unit tests effectively.

Sample Project Structure
Consider the following simplified project structure:

/myproject
|-- /handlers
|   |-- handler.go
|   |-- handler_test.go
|
|-- /db
|   |-- database.go
|   |-- database_test.go
|
|-- main.go
|-- go.mod
|-- go.sum

The application is structured as follows:

handlers: This contains the HTTP request handlers for the application.
db: This manages the database connections and queries.
main.go: This is the primary entry point for the application.
go.mod and go.sum: These files manage the dependencies.

When writing unit tests in Go, it's common practice to place them in the same package as the code being tested. This allows you to test internal or unexported functions, ensuring that the testing scope aligns with the implementation details. By placing the test file (handler_test.go) in the same package, you can easily access unexported functions, which can enhance the thoroughness of your tests.

Writing Unit Tests in a Global Package
While colocating tests with packages provides access to internal functions, it might be beneficial to create a global test package for testing public APIs and behaviors from a user's perspective. Here's an example with a global test package:

/myproject
|-- /tests
|   |-- main_test.go
|
|-- ...

// tests/main_test.go
package tests

import (
    "testing"

    "myproject/handlers"
)

func TestMain(t *testing.T) {
    // Your test logic here
}

This approach ensures that you validate the external APIs and behaviors as users would interact with them.

Testing PostgreSQL

When testing interactions with a PostgreSQL database, it's crucial to ensure that your data access layer functions correctly. By setting up a dedicated test database, you can conduct tests against a real PostgreSQL instance, providing more realistic scenarios.

Example.

// db_test.go
package db

import (
    "fmt"
    "os"
    "testing"

    "github.com/stretchr/testify/suite"
    "gorm.io/driver/postgres"
    "gorm.io/gorm"
)

// User represents a simple user model.
type User struct {
    ID   uint
    Name string
}

// DatabaseTestSuite is the test suite.
type DatabaseTestSuite struct {
    suite.Suite
    db *gorm.DB
}

// SetupSuite is called once before the test suite runs.
func (suite *DatabaseTestSuite) SetupSuite() {
    // Set up a PostgreSQL database for testing
    dsn := "user=testuser password=testpassword dbname=testdb sslmode=disable"
    db, err := gorm.Open(postgres.Open(dsn), &gorm.Config{})
    suite.Require().NoError(err, "Error connecting to the test database")

    // Enable logging for Gorm during tests
    suite.db = db.Debug()

    // Auto-migrate tables
    err = suite.db.AutoMigrate(&User{})
    suite.Require().NoError(err, "Error auto-migrating database tables")
}

// TestUserInsertion tests inserting a user record.
func (suite *DatabaseTestSuite) TestUserInsertion() {
    // Create a user
    user := User{Name: "John Doe"}
    err := suite.db.Create(&user).Error
    suite.Require().NoError(err, "Error creating user record")

    // Retrieve the inserted user
    var retrievedUser User
    err = suite.db.First(&retrievedUser, "name = ?", "John Doe").Error
    suite.Require().NoError(err, "Error retrieving user record")

    // Verify that the retrieved user matches the inserted user
    suite.Equal(user.Name, retrievedUser.Name, "Names should match")
}

// TearDownSuite is called once after the test suite runs.
func (suite *DatabaseTestSuite) TearDownSuite() {
    // Clean up: Close the database connection
    err := suite.db.Exec("DROP TABLE users;").Error
    suite.Require().NoError(err, "Error dropping test table")

    err = suite.db.Close()
    suite.Require().NoError(err, "Error closing the test database")
}

// TestSuite runs the test suite.
func TestSuite(t *testing.T) {
    // Skip the tests if the PostgreSQL connection details are not provided
    if os.Getenv("POSTGRES_DSN") == "" {
        t.Skip("Skipping PostgreSQL tests; provide POSTGRES_DSN environment variable.")
    }

    suite.Run(t, new(DatabaseTestSuite))
}

Conclusion

In this guide, we covered the basics of writing unit tests in Golang. The Testify library is a valuable addition to our testing toolkit, providing additional features like test suites, mocks and assertions that help create robust and reliable test suites for Golang applications. Happy coding!

Resources for Further Learning

To delve deeper into testing with Golang and Testify, consider exploring the following resources:

Golang Testing Package: Official documentation for the Golang testing package.
Testify Documentation: Comprehensive documentation for the Testify library.

Remember, writing effective tests is crucial for maintaining code quality and ensuring robust software. By embracing testing best practices and leveraging powerful tools like Testify, you can enhance the reliability of your Golang projects.

Utilizing OSRM for Efficient Location Data Preprocessing

Nilesh Prasad — Wed, 30 Aug 2023 17:19:28 +0000

In the modern era of technology, location data plays a crucial role in a vast array of applications and services. Nevertheless, real-world location data can be unreliable, imprecise, or even deceptive due to various factors. As an engineer working to enhance location-based services for an urban mobility provider in Mumbai, I have encountered various challenges caused by inaccurate GPS or OBD device locations. This blog post explores the potential of the Open Source Routing Machine (OSRM) in improving the accuracy of location data.

Understanding Real World Challenges of Location Data

Let's dive into some real-life situations that highlight the gravity of dealing with inaccurate location data in a bustling city like Mumbai.

Signal Confusion: Imagine a scenario where a bus is navigating through the busy streets of Mumbai, surrounded by tall buildings. Sometimes, the signals from GPS devices can bounce off these structures, resulting in incorrect location readings. This might make the bus appear to be on a different route or even off the road altogether. Passengers might find themselves perplexed about the bus's actual location.

Complex Crossroads: Visualize a bustling intersection like Bandra Worli Sea Link, where multiple lanes and ramps converge. If GPS inaccuracies misplace a bus even slightly off its intended route, the navigation system could misinterpret it as taking an unintended exit or lane change. Such confusion can lead to inaccurate route suggestions, delays, and even missed stops.

Lane-Based Confusion: Consider Mumbai's Western Express Highway, a road with lanes dedicated to different destinations. GPS inaccuracies might place a bus in the wrong lane, leading to incorrect navigation suggestions. The system might recommend wrong exits or turns, steering the bus onto an unintended path.

U-turn Uncertainty: Approaching a U-turn, accurate location data becomes crucial for estimating the time needed to complete the turn and rejoin the correct route. If GPS inaccuracies position the bus incorrectly before or after the U-turn, the estimated arrival time at subsequent stops could be way off. Passengers might receive misleading information, causing confusion and frustration.

These examples demonstrate the challenges that arise when dealing with location inaccuracies in Mumbai's intricate road network.

Location Preprocessing with OSRM

Relying solely on raw GPS coordinates can lead to location inaccuracies. This is where the Open Source Routing Machine (OSRM) comes into play. OSRM is a powerful open-source routing engine designed to process and enhance location data, making it more accurate and meaningful.

OSRM takes a unique approach to location data enhancement. It doesn't merely rely on individual GPS coordinates; instead, it considers the entire road network and intelligently matches incoming location data with the closest road segments. By doing so, OSRM can mitigate the effects of GPS inaccuracies, even when the reported location is slightly off the mark.

Installing and Deploying OSRM

Enhancing location accuracy using the Open Source Routing Machine (OSRM) begins with the installation and deployment of the OSRM server. The OSRM server processes location data and provides refined coordinates for improved accuracy. Here's a step-by-step guide to help you set up your OSRM environment.

Step 1: Get Geographical Data

Start by obtaining geographical data from OpenStreetMap (OSM), which includes road networks and intersections. Visit Geofabrik, select your region, and download the .osm data. For instance:

Example: wget http://download.geofabrik.de/asia/india/western-zone-latest.osm.pbf

Step 2: Run the OSRM server after preprocessing OSM data

To unlock OSRM's potential, preprocess OSM data using the OSRM Backend tool. The OSRM server can be easily run using Docker containers. Here's how:

Visit the OSRM GitHub repository for detailed instructions and tools.
Utilize Docker for easy setup. Follow the instructions at https://github.com/Project-OSRM/osrm-backend#using-docker.

In the upcoming section, we'll delve into the Nearest and Match Services, exploring how they optimize route calculations and refine location data.

API Endpoints: Nearest and Match Services

Once your OSRM server is up and running, you'll have access to powerful API endpoints from OSRM (http://project-osrm.org/docs/v5.5.1/api/#general-options) that can significantly enhance location accuracy. Two key services that play a pivotal role in this process are the Nearest and Match Services.

The Nearest Service is ideal for accurately mapping individual points to the nearest road segment, making it useful for imprecise GPS points. On the other hand, the Match Service is perfect for reconstructing vehicle routes from sequences of GPS points. It is optimized for maintaining route continuity, making it valuable for accurate navigation and travel time estimation.

To choose the right service, consider your specific application requirements. If you need accurate mapping without sequence consideration, go for the Nearest Service. If you need to reconstruct routes and ensure accurate navigation, opt for the Match Service.

In summary, the Nearest Service is for point mapping, while the Match Service excels in reconstructing routes and maintaining continuity for navigation accuracy.

For more in-depth information and practical implementation details, refer to the OSRM Nearest Service documentation and OSRM Match Service documentation.

It is very easy to get started with these services. In this blogpost, let's discuss the Match Service implementation in more details.

How the Match Service Works

The Match Service aligns a sequence of GPS points to the most likely route on the road network. It considers road geometry, direction, and nearby intersections to identify the optimal match. This process effectively "snaps" GPS points to their corresponding road segments, creating an accurate route.

Benefits of Using the Match Service

Route Continuity: The Match Service maintains route continuity, ensuring accurate navigation instructions and travel time estimates.
Navigation Precision: Snapped routes provide precise navigation guidance, reducing confusion and incorrect turns.
Accurate Travel Time Estimates: Reliable route data leads to better travel time estimates, improving operational efficiency.

Implementation Example

To use the Match Service, send a sequence of GPS points to the OSRM server. Here's a simplified example in Python:



import requests

def match_gps_points(points):

    osrm_url = "http://your-osrm-server/match/v1/driving/" + ";".join([f"{point[1]},{point[0]}" for point in points])

    response = requests.get(osrm_url)

if response.status_code == 200:
    snapped_route = response.json()
    return snapped_route
else:
    return None




  
  
  Example GPS points


gps_points = [(19.076191, 72.875877), (19.072565, 72.874377), (19.071213, 72.869145)]

  
  
  Call the function


snapped_route = match_gps_points(gps_points)

print(snapped_route)

Conclusion

Using OSRM's Nearest and Match Services can easily help in preprocessing raw location data from GPS devices.

Maximizing Ticket Allocation Efficiency with Redis Sorted Sets

Nilesh Prasad — Sat, 03 Jun 2023 09:20:29 +0000

I recently had the opportunity to work on building a ticketing allocation system. In this blog post, I would like to share my experience and discuss how the use of Redis sorted sets can be a valuable approach in achieving efficient ticket allocation.

The Challenge

Assigning tickets to the right support employees based on various criteria, such as availability, workload, and ticket priorities, can greatly impact customer satisfaction and team efficiency. The goal is to design a system that can handle dynamic ticket allocation and ensure a fair distribution of tickets among employees.

Sorted Sets to the Rescue

To address this challenge, one can turn to Redis, an in-memory data structure store, and leverage its sorted sets functionality. Sorted sets are a powerful data structure that allows for efficient sorting and retrieval of elements based on a score assigned to each element.

https://redis.io/docs/data-types/sorted-sets/

Implementation

Here's a detailed overview of how you can utilize sorted sets to build the ticketing allocation system.

Storing Employee Availability

Store the availability status of employees using Redis sets.

Assigning Scores to Tickets

Determine the priority score of each ticket by devising a scoring mechanism based on various factors such as urgency, impact on customers, and SLA requirements. Customize the formula for calculating the score based on specific business needs. For example, a ticket with high priority and a short SLA might receive a higher score than a low-priority ticket with a longer SLA.

Redis sorted sets offer a powerful solution for sorting tickets based on multiple data points. By assigning float value scores to tickets, combining priority and turnaround time (TAT), sorting becomes efficient. For example, the priority score of 1.0 and TAT score of 0.1324 can be combined as 1.1324.

Creating Sorted Sets for Tickets and Employee Queues

You can utilize Redis sorted sets for storing the tickets and maintaining employee queues based on the number of tickets assigned. Each support employee is added in an employee queue (redis sorted set) where the number of tickets assigned serves as the score of each member. This allows for efficient retrieval of employees with the least number of tickets.

Allocating Tickets

Tickets can be allocated to employees either in real-time, as soon as the ticket is raised, or periodically. In the case of real-time assignment, tickets are assigned to the employee who has been assigned the least number of tickets, which is a constant time operation (0(1)) in sorted sets as employees are always sorted based on the number of tickets assigned to them.

For tickets that are in queues due to employees being unavailable, they can be assigned to employees based on ticket priority. This ensures that employees with fewer assigned tickets are always assigned first, maintaining a fair distribution of the workload.

Updating Scores, Availability, and Employee Queues

As tickets are assigned to employees, you can remove tickets from the sorted sets. Additionally, you can update the employee queues by incrementing the number of tickets assigned to the respective employee in the employee sorted set.

Understanding Time Complexities

Redis sorted sets offer excellent time complexities that contribute to the efficiency of the ticket allocation system:

Adding a ticket to the sorted set: With Redis, adding a ticket to the sorted set has a time complexity of O(log N), where N is the number of elements in the sorted set. This operation can be achieved using the ZADD command, which allows you to add a ticket to the sorted set with its priority score.
Fetching a range of tickets based on priority: Retrieving a range of tickets from the sorted set based on priority has a time complexity of O(log N + M), where N is the number of elements in the sorted set and M is the number of tickets in the requested range. This can be done using the ZRANGEBYSCORE command, which returns a range of tickets based on their priority scores. ZRANGE can be used to fetch tickets based on their positions in the sorted set.
Pushing a ticket to an employee queue (sorted set): O(log N) This operation can be accomplished using the ZADD command, similar to adding a ticket to the main sorted set.
Updating employee availability (Redis sets): Updating the availability of employees, stored in Redis sets, has a constant time complexity of O(1). You can update the availability status of an employee using the SADD or SREM commands to add or remove the employee from the availability set.

Benefits of this Approach

Scaling with Increasing Ticket Volume: As the number of tickets in the system grows into the thousands or millions, Redis sorted sets continue to provide efficient performance for fetching and sorting tickets based on priority. The logarithmic time complexity ensures that the system can handle the increasing volume of tickets without sacrificing responsiveness.
Real-Time Ticket Updates: In a dynamic environment where ticket priorities frequently change, the ticket allocation system powered by Redis allows for real-time updates of ticket scores. This enables immediate adjustments to ticket positions within the sorted set, ensuring that the most critical tickets are always readily accessible for assignment to employees.
Concurrent Ticket Assignments: In scenarios where multiple employees are simultaneously fetching tickets for assignment, Redis sorted sets handle concurrent access gracefully. The built-in atomicity of Redis commands guarantees that each employee retrieves a consistent and accurate range of tickets based on priority, without conflicts or interference.
Efficient Load Distribution: With the ability to assign tickets based on priority scores, Redis sorted sets ensure an equitable distribution of workload among available employees. Critical tickets are promptly allocated to the most appropriate employees, preventing any single employee from being overwhelmed. This load distribution mechanism optimizes team productivity and enhances customer satisfaction.
High-Speed Ticket Retrieval: Redis excels at delivering lightning-fast response times, even as the number of tickets and employees increases. The efficient time complexities of Redis sorted sets enable sub-millisecond retrieval of tickets based on priority, allowing for rapid allocation decisions and minimizing any potential delays in ticket handling.

Conclusion

Utilizing Redis sorted sets for both ticket storage and employee queues offers a powerful and efficient approach to building a ticketing allocation system. The combination of fast retrieval, fair workload distribution, real-time updates, and scalability makes this implementation highly effective in managing and assigning tickets based on priority and employee availability.

Keeping Your Maps Accurate: Detecting Loops and Intersections in Polylines

Nilesh Prasad — Tue, 25 Apr 2023 09:54:02 +0000

Introduction

Polylines are an essential component in mapping and navigation applications, used to represent the geometry of roads and transportation networks. Each polyline is a series of connected line segments defined by consecutive points in a list of (latitude, longitude) coordinates. Polylines can be stored in encoded format, which, when decoded, yields a list of lat, lng pairs. Polylines can be stored in encoded format as explained here, https://developers.google.com/maps/documentation/utilities/polylinealgorithm

However, polylines can be subject to errors and inaccuracies. In the context of this post, the error we would be referring to would be because of incorrect stop locations of some intermediate stops in a route. These issues are indicated by the intersections or loops in the polyline, which can cause problems for applications that rely on accurate polyline data.

In this post, we'll focus on detecting intersection issues caused by incorrect stop locations using a simple algorithm. We'll examine an example of an incorrect polyline that contains an intersection due to a misplaced stop location. Finally, we'll demonstrate how to programmatically detect issues in stored polylines to ensure that mapping and navigation applications function accurately and reliably.

Understanding polyline issues

In the above image, the intersection in this polyline is clearly visible. Issue is because of the incorrect stop location of Sewri - Chembur Rd, GTB Nagar, Lalbaug, Sion East, Sion. If the location of this stop is correctly put on the other side of road, this issue would not occur.

Now, let's assume we have this polyline stored in our database and we want to detect any issues in the stored polyline. This will help us keeping our maps accurate.

When we moved the stop location to the other side of road, this issue gets resolved.

Programmatic detection of intersections in polyline

Although there are some advanced intersection detection algorithms such as Bentley-Ottmann or Sweep Line Algorithm, we'll try to detect intersections using a simple algorithm which is very easy to understand.

Algorithm:

The algorithm for detecting self-intersections and loops in a polyline involves comparing each line segment of the polyline with all the other segments to detect any intersection between them. If an intersection is found, it indicates that the polyline has a self-intersection or a loop.

We iterate over each segment of the polyline, and for each segment, we iterate over all the other segments to check for intersection. We use the equation of lines to check for intersection between two line segments. If an intersection is detected, we add the intersection point to a list of intersections.

Code:



def detect_polyline_issues(polyline):
    """
    Detects any issues (loops or intersections) in an open polyline. Returns list of intersections in a polyline
    """
    def intersect(p1, q1, p2, q2):
        """
        Returns True if the line segments p1-q1 and p2-q2 intersect.
        """
        o1 = orientation(p1, q1, p2)
        o2 = orientation(p1, q1, q2)
        o3 = orientation(p2, q2, p1)
        o4 = orientation(p2, q2, q1)

        if (o1 != o2 and o3 != o4) or (o1 == 0 and on_segment(p1, p2, q1)) or (o2 == 0 and on_segment(p1, q2, q1)) or (o3 == 0 and on_segment(p2, p1, q2)) or (o4 == 0 and on_segment(p2, q1, q2)):
            return True

        return False

    def orientation(p, q, r):
        """
        Returns the orientation of the ordered triplet (p, q, r).
        """
        val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
        if val == 0:
            return 0
        return 1 if val > 0 else 2

    def on_segment(p, q, r):
        """
        Returns True if point q lies on line segment pr.
        """
        if q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1]):
            return True

        return False
        n = len(polyline)
        if n < 4:
            return False

    n = len(polyline)
    intersections = set()
    if n < 4:
        return []

    # Check for intersections
    for i in range(n - 3):
        for j in range(i + 2, n - 1):
            if intersect(polyline[i], polyline[i + 1], polyline[j], polyline[j + 1]):
                intersections.add(polyline[i])
    if len(intersections) > 0:
        return list(intersections)

    return []

Here is a brief explanation of each function in the detect_polyline_issues method:

detect_polyline_issues(polyline) - This is the main function that takes in a polyline, which is a list of (latitude, longitude) pairs, and returns a list of intersections in the polyline.

intersect(p1, q1, p2, q2) - This function takes in two line segments defined by their endpoints, p1 and q1 for the first segment and p2 and q2 for the second segment, and determines whether they intersect. It returns True if they intersect and False otherwise.

orientation(p, q, r) - This function takes in three points, p, q, and r, and determines their orientation. Specifically, it calculates the cross product of vectors pq and qr. If this value is positive, the orientation is counter-clockwise, if it is negative the orientation is clockwise, and if it is zero, the points are collinear.

on_segment(p, q, r) - This function takes in three points, p, q, and r, and determines whether q lies on the line segment pr. It returns True if q lies on the line segment and False otherwise.

The main function first checks if the polyline has fewer than 4 points, in which case it cannot contain any intersections. If the polyline has 4 or more points, it loops through all pairs of line segments in the polyline and checks if they intersect using the intersect function. If an intersection is found, the intersections set is updated with the intersection point. Finally, the function returns a list of intersection points or an empty list if no intersections were found.

The limitation of this method is that its a little slow as compared to advanced intersection detection algorithms and this should only be used when your routes aren't too big.

Conclusion

To detect polyline issues, we have implemented a simple algorithm based on line segment intersection detection.
By running this algorithm on stored polylines, we can identify any incorrect stop locations that cause loops or intersections in the polyline, allowing us to correct these errors and ensure accurate polyline data for navigation and mapping applications.