CT Wu

Software Architect · Backend · Data Engineering

Posted on In

Three approaches to speed up string comparison

In the previous article, we briefly talked about how B-tree-based databases use partial indexes to improve performance. In this article, we will talk about another story of indexing.

Generally speaking, B-tree-based database indexes have one characteristic, which is leftmost matching. Take MySQL for example, if the WHERE condition is a = 1 AND b = 2 AND c = "Hello" then the index must be built in this order, i. e. (a, b, c).

In addition, if the index is (a, b, c, d), then the same query can be applied based on the leftmost match principle.

Furthermore, if the condition we want to query is a string match in the c field, for example, WHERE a = 1 AND b = 2 AND c LIKE "Hello%", such a condition can still apply to the (a, b, c) index. Because of the leftmost match rule, even if LIKE is used, the leftmost edge of the string is already specified, so it still meets the rule.

On the contrary, if the query condition becomes WHERE a = 1 AND b = 2 AND c LIKE "%World", then only the a and b fields can be indexed, while the c field must compare all rows matched (a, b) values, which will use a lot of CPU computation of the database, in other words, very resource consuming.

How to improve?

The simplest solution to improve this situation is to drop the percentage sign in the middle and after the string. Nevertheless, there must be a use case for using it this way in the first place, so this article will not ask you to simply drop it, but to provide some alternatives.

Modify the outermost client

Modify the original string pattern so that the index order is reversed.

For instance, the original query needs to match the string pattern "PREFIX_ABC_SUFFIX" with a query like a LIKE "%ABC%".

Then reverse the original string pattern and change it to "ABC_PREFIX_SUFFIX". With this change, you can remove the top percentage sign and change the query to the leftmost match.

Modify the database schema

Add a new boolean field, abc_matched, to the original database table. When the database client writes data, it determines in advance whether the original field meets the conditions and sets the corresponding flag.

That is to say, the original query a LIKE "%ABC%" can be changed to abc_matched = 1.

By doing so, the database computation can be transferred to the database client, thus effectively reducing the database overhead.

Such a practice is also common in data science and is called data preprocessing. It replaces the N operations of subsequent queries with a single operation.

Modify the indexing type

In MySQL there is no way to do this kind of query.

However, in both Postgres and MongoDB there are corresponding index types that can effectively deal with fuzzy string comparisons.

Postgres uses GIN indexes instead of the default Bitmap type, while MongoDB uses text indexes instead of regular indexes.

By modifying the indexing type, even fuzzy comparisons of strings can be done with good performance. Nevertheless, all technical selections have advantages and disadvantages; indexes of GIN or text type take up a lot of space, several times the cost of the default type, and the process of building indexes is time consuming.

Therefore, in the case of limited resources, even if the solution looks very easy to implement, I do not recommend it that much.

Conclusion

In software development, there are always many approaches to solving an existing problem, and each approach comes with pros and cons.

Take the three approaches mentioned in this article.

The cost of modifying the outermost client is the highest, but the cost of designing a new feature is the lowest.

Because the modification of the client is followed by the compatibility of the old and new versions, besides, the outermost client may be a mobile application, which is not only difficult to deploy but also hard to rollout.

However, if the design is correct at the very beginning, the implementation cost is very low because it is just a reverse order of the original string.

The cost of modifying the database schema is the second highest, although it does not necessarily need to change the client at the outermost tier, but it also needs to change the client of the database.

The modification of the database schema requires the migration of the old data, which also requires time and human effort.

However, preprocessing of the data offers additional benefits beyond the improved query performance, such as more explicit feature matrix, which can effectively improve the accuracy of the model during machine learning.

The implementation cost of modifying the index type is the lowest, just change the index once, basically no need to modify the implementation of the application.

But this is the highest cost for the system.

Firstly, such an index type takes up a very large amount of memory space, which cannot be ignored when the data volume is large.

Secondly, when the indexes are too large to fit the database memory size or have to be swapped frequently, it will affect the performance of other queries as well.

Moreover, the complexity of the indexes can affect the performance of writes, which is an overhead that must be carefully considered if this is a high-frequency writing system.

Therefore, although there are three approaches, there is a trade-off as to which one is suitable and the answer will not be the same for each system.

Originally published on Medium

Posted on In

Understanding Partial Indexing

When and how to use partial indexing

A few days ago, a team member asked me a question about partial indexing, and I feel it’s a good topic, so today we’ll talk about partial indexing:

  1. What are the benefits of partial indexing?
  2. When should I use a partial index?

Before we talk about the above two questions, let’s have a basic understanding of partial indexing.

The purpose of database indexing is to speed up query performance by placing data in memory through special data structures in order to avoid long access latency on the hard drive.

The current mainstream RDBMS MySQL and PostgreSQL, they use B+ tree, while the document-based MongoDB uses B tree.

Most of the database indexes do not treat each row in the database as a separate leaf node, but use the “value” as the leaf and record the primary key in it, so after finding the leaf, it is necessary to pull the other data from the primary key.

Partial indexes only create nodes for “values” that meet certain conditions. Currently MongoDB and PostgreSQL both support partial indexes, but InnoDB, which is often used by MySQL, does not. After MySQL 8.0, there is support for functional indexes, which can be used to achieve the effect of partial indexes.

What are the benefits of partial indexing?

After understanding the background of partial indexing, it should be no wonder that the biggest advantage of partial indexing is to reduce the memory size occupied by the index. Compared to creating nodes for all values, partial indexing only creates nodes for some values, so the percentage of reduction depends on the criteria used.

For example, if I have a single-field (a) index with values from 0 to 9, I can save about 50% of the space overhead if I set the partial index condition to a >= 5. Note that this is not related to the amount of data, but only to the value ranges. Even if the a = 0 data has only one row, it will still have an index node as well as the a = 1 data with 1000 rows.

In addition to saving space, the query performance will also be improved. The query efficiency of B tree is O(log N), where N refers to the number of index nodes, not the number of rows.

After partial indexing, we can get a more compact tree, let’s say it has M nodes. Due to M < N, so O(log M) < O(log N), we thus know that partial indexing can improve the query performance. However, the benefit is small, because after log, unless the difference between N and M is significant, the effect on query performance is not much.

To sum up, the biggest advantage of partial indexing is to reduce the space overhead for indexing and to improve some of the query performance.

When should I use a partial index?

To figure out the time to use it, we first need to know what will happen when the “query results” will contain nodes that don’t meet the partial indexing criteria.

A bit abstract, right? Let’s use MongoDB as an example.

First, there is a partial index built on a compound index of the user list, in order to make indexing adults faster.

1
2
3
4
db.users.createIndex(  
   { name: 1 },  
   { partialFilterExpression: { age: { $gte: 18 } } }  
)

However, if our scenario is likely to require a query for a name without an age limit, then such a query will not use the index.

1
db.users.find({name: "Tom"})

For instance, if there are three Toms aged 8, 18 and 28, then ("Tom", 18) and ("Tom", 28) will both be created but not ("Tom", 8), so the MongoDB optimizer knows this is the case and will not use partial indexes, but will use full table scans instead.

Yes, that’s the price. As soon as the scenario contains a condition that is not in the value range of the partial index, then it becomes a full table scan.

Therefore, what kind of scenario is suitable for partial indexing? In my opinion, two conditions need to be satisfied.

  1. The value range is large, but the common range of data is small.
  2. Even without index, the query will not impact the database too much, e.g., query frequency, collection size, etc.

The second point is simpler to understand, but what does the first point exactly mean?

From the previous section, we know the biggest advantage of partial indexing is to reduce the space of indexes rather than to improve the performance of queries, so the most effective scenario is when data is scattered and only a fraction of the common data is used by the application.

Take a practical example of a membership system.

From registration to membership, a user may need to go through many procedures until finally becoming a member after email verification. But this system, for non-members basically does not care, it only focuses on processing the verified member data.

Then, the partial index can be designed in this way.

1
2
3
4
db.users.createIndex(  
   { name: 1 },  
   { partialFilterExpression: { email: { $exists: true } } }  
)

Because this membership system only cares about member information, i. e., users must have email. There may be a large number of users who go through the partial registration process at the beginning but do not pass the verification process at the end, then there will be a large amount of data that does not need to be indexed. In this way, the index space can be reduced as much as possible, and the efficiency of the member’s query can be improved.

Conclusion

After all, there is not a perfect solution. Partial indexing saves index space and improves query performance, but there is a corresponding price to pay for a full table scan.

Therefore, it is important to understand the principle of partial indexing and the scenario of using it.

The effectiveness of an indexing mechanism depends entirely on the data distribution and the characteristics of the application, whether it is a regular index or a partial index. Therefore, this article can’t tell you a one size fits all solution, it can only offer you a guideline, and it’s up to you to take the trade-off.

Originally published on Medium

Posted on In

Building Ruby on Rails from Scratch, Day 3

Pros and Cons of Rails

This is the last article in this series. Instead of building an application from scratch, in this article I’d like to talk about some of my thoughts on Ruby on Rails over the past few weeks.

First, I’ll start with a brief ranking of the programming languages I’ve experienced on multiple aspects, including C++, Python, Node, Golang, and Rails, and since I haven’t worked with Java or .NET Core, perhaps you can consider C++ as an alternative.

These language comparisons are mainly qualitative rather than quantitative. After all, I don’t really measure anything, it’s mostly “how I feel”.

Next, I’ll describe the benefits I’ve experienced in Rails. I’ll give a reasonable rating for both extensibility and ease of use.

Finally, of course, there will be the shortcomings that I feel.

But what I feel is not the same as what you feel is a pain point. The size of the application, the amount of organizational resources, and other factors can affect how you feel. So I’m only commenting on Rails based on my own experience and understanding of the evolution of the system.

Ranking

Performance

First, let’s compare performance. As I said earlier, I didn’t do any measurements, I simply did some comparisons based on the nature of the language and my feelings.

C++ > Golang > Node > Python = Rails

Ruby and Python are the slowest, I believe, no doubt, because of GIL, which makes these two languages less efficient. I want to emphasize that Python here means CPython, and in fact, GIL-removed implementations like pypy or IronPython perform very well.

Although Node does not have GIL implementation and is event-driven by nature, Node can still only execute all events through a single process, which is still a gap compared to Golang’s goroutine. C++ has a natural advantage due to its closer implementation to the kernel.

Portability

The portability here is not about cross-platform porting, after all, these languages are cross-platform, and C++ can also be cross-platform as long as it has a corresponding toolchain.

So what is the comparison here? I think we can compete in terms of how easy it is to run an application. For example, Python requires the installation of an interpreter, not to mention the dependency on packages like pip install, and the same applies to Node. But Rails, in addition to Ruby itself, sometimes even Node is part of the dependency, and that’s where it loses out.

Therefore,

C++ > Golang > Node = Python > Rails

In addition to judging by the number of package dependencies, we can also compare the container image sizes created with best practices, and the results are the same.

Ease of coding

The first two comparisons I feel there should be no debate about the results, not much difference with the facts, but the next one is more subjective, the ease of coding.

Python = Rails > Node > Golang > C++

First of all, I am a fan of weak typed languages, so Golang and C++ must be at the bottom of the list. Golang is a bit easier than C++, with fewer keywords.

Although Node is a weak typed language, its event-driven nature makes it a bit difficult for people who are new to it to understand when to async/await and when to synchronize, which takes time to get used to. In addition, Node has a lot of difficulties with object-oriented implementation, and honestly, Node is not easy to get objects right.

As for Python and Rails, they are really easy to code, with a procedural language base and rich syntactic sugar that makes everything possible. If I had to decide between the two, I’d probably vote for Python!

Extensibility (including packages and ecosystems)

Excluding C++, all the other languages have relatively good package management tools, and all have active ecosystems, so it’s a little hard to tell the difference.

But if I have to say so, Python can do a little more than the other languages, so Python is in the front of my list.

Python > Rails = Node = Golang > C++

Benefits of Rails

The above comparison is mostly based on my experience, which may not be the same as yours, but in general Rails is still outstanding.

In particular, as you can see from the descriptions in my first two articles, it can be really fast to build an application with Rails.

Especially since Rails provides excellent ERb templates that make frontend pages easy to develop, and there are many helpers in Rails that integrate well with the frontend to make things even easier.

Furthermore, one of the most amazing features of Rails is the ActiveRecord and resource-based routing paradigms that are developed in accordance with the Active Record Pattern mentioned in Patterns of Enterprise Application Architecture, which shows the author’s ingenuity.

In Rails, you don’t need to care about the database underlying the ActiveRecord. The application is basically written the same way, whether it’s MySQL or MongoDB. More importantly, ActiveRecord can also automatically generate schema for database migration, both in whole and in part, and it can be both up and down, which is really convenient.

Even when we were developing Node, we used Rails to create the schema for the database migration.

Finally, Rails has a lot of built-in features that are necessary for the backend development, such as caching through CacheStore, messaging through ActiveMailer, and job scheduling through ActiveJob. Basically, all the tools for backend development are available, and the underlying infrastructure can be modified with a simple setup, without the need to modify the application.

All of these advantages make Rails the best candidate for a fast development and quick launch.

Shortcomings of Rails

Nevertheless, Rails has some shortcomings.

First, due to the resource-based routing design, all domain knowledge is built around resources. This may not be a problem in a small to medium-sized application, but when the application becomes large, the resource-to-resource constraints increase significantly and resource-based routing is obviously not sufficient.

Let me use the most common e-commerce website as an example.

Suppose there are three resources, order, payment, and transaction history. A typical Rails routing design would generate three routes, all with CRUD capabilities.

/api/orders/{oid}
/api/payments/{pid}
/api/transactions/{tid}

When a user places an order, the operation is performed through /api/orders/{oid}, either to update the status or to get the status. The user then proceeds to make a payment, so a transaction is created and managed through /api/transactions/{tid}. But at the same time, the status of the order will need to be changed to in progress, and a payment will need to be inserted but indicated as unconfirmed.

Based on the above description, we need three API calls.

POST /api/transactions
PUT /api/orders/{oid}
POST /api/payments

Question, how do we ensure that all API calls are correct in such a situation? This is a typical distributed transaction, and I have already written several articles on the difficulties of distributed transactions.

As resource-to-resource connectivity grows with the complexity of the domain, it becomes obvious that Rails’ most classic routing design is overburdened. In addition, all the domain knowledge is fragmented by the resources, which is a common problem in system design, the anemic model.

Moreover, when actually doing a code review, I found that Rails was not as readable as I expected. Even though it’s a resource-based routing design, I often couldn’t find a specific route, especially in a config/routes.rb with thousands of lines. I was always confused by the various combinations of concern, resource and namespace.

In addition to not finding routes, method calls are often not found. Because a class can get the ability of other modules by include, but this include doesn’t require any “declaration” at all. Here the declaration refers to from x import y in Python or import { y } from x in Node, but in Rails there is no need, you can just include y.

So when a method is used in a class, I have to look through include, extend and pretend, and again, when the application is huge, this process really kills me. When there are methods with the same name, it can be several times worse.

One more point is that Rails wraps a lot of implementation behind a layer of objects, making the whole thing feel like a black box. Without a clear understanding of the underlying implementation, it’s easy to code something that seems to work, but actually performs horribly, like N + 1 queries.

If it is a simple object this can save a lot of implementation efforts, such as CacheStore.

I like Rails’ CacheStore, because it provides a lot of common functionality for caching. But when it comes to ActiveRecord, I honestly don’t have confidence that it will work very well. I’d rather write my own database queries, at least I can be sure that the performance of the queries will be good enough.

Conclusion

Although Rails can quickly generate an application skeleton through scaffold, it is very adaptable to fast launch requirements. But I have to say that this advantage can be replaced very easily, especially nowadays when the ecosystems of various languages are so well organized that it is not difficult to do so.

In the case of Node, there are now many MERN generators that can do similar or even better things.

For example,

https://docs.dhiwise.com/knowledgehub/build-node.js-app/Build-app

An e-commerce site can be built at a mouse click and is production ready. So there are few advantages left in Rails, and the design of ActiveRecord, as mentioned in the previous section, is not an advantage but a disadvantage when the application becomes large.

Even so, I would rate ActiveRecord very highly. For those who want to move from procedural languages into the object-oriented world, the design offers plenty of perspective, and once you get used to ActiveRecord, I believe that anyone can build elegant objects.

Besides, I personally like the design of the CacheStore. In addition to the built-in expiration mechanism :expires_in, there is also the elegant :race_condition_ttl to avoid Dog-pile Effect, which is definitely a benefit for people who used to build their own wheels. But I haven’t been in Rails long enough to study what the underlying implementation is, so I’ll leave that for later.

Overall, I feel that Rails is amazing, has a lot of design wisdom in it, and is very classic.

But maybe Rails was originally intended for people who wanted to build applications quickly, and when applications became large, most of the original design became useless and ineffective. This takes us back to the basics of Ruby as a language. For Ruby, the ecosystem is complete and the syntax is flexible enough to build large applications.

But if Rails has to rely on Ruby in the end, why don’t I just use Python? The ecosystem is more complete and the syntax is more flexible.

Anyway, these are my thoughts on Ruby on Rails, and my next goal is to decompose these legacy large Rails applications into microservices. The next article will introduce the classic approach to decompose microservices.

Originally published on Medium

Posted on In

Building Ruby on Rails from Scratch, Day 2

More Things about Relations, Tests, etc.

In the previous article, our application has almost finished building the user model. In this article, we will proceed to build a model of each user’s corresponding store, i.e., one-to-one mapping.

In addition, user-related unit tests will be created to practice RSpec.

So, let’s get started.

Establish a one-to-one mapping

First of all, the same store model is created by scaffold, but the difference is that the store must be assigned to a user at the end.

$ bin/rails generate scaffold shop name user:belongs_to

In this way, the controller and routes of stores will be created. But this is not enough, because it is a one-to-one mapping relationship, so we must also modify the original user model, as follows Github commit.

It has to be specified as has_one in app/models/user.rb, otherwise it becomes a one-to-many mapping. In addition, Rails has an inborn problem when dealing with mapping relationships, which is N + 1 queries.

In this example, N + 1 queries is not a serious impact because it is a one-to-one mapping, but if it is a one-to-many mapping, then it will have a performance impact. The solution is also very simple, and is provided in the above mentioned commit.

Change the original Shop.all generated by scaffold to Shop.includes(:user). Then the user model will not be searched for one record at a time, but will be listed at once.

Create nested routing

Since users and stores have an ownership relationship, we can also create a nested route to get the stores under users.

Just modify config/routes.rb to add the store resources under the user’s resources, as shown in the Github commit.

Setup unit tests

Nowadays the most popular test framework on Rails is RSpec, so I also did some exercises with RSpec.

The installation is very simple, just add a new line gem 'rspec-rails' at Gemfile, and it is recommended to add it under the development and test groups. Next, install and configure.

$ bundle install
$ bin/rails generate rspec:install

We have generated various models by scaffold before, so we continue to generate corresponding tests by scaffold as well. Let’s take the user model as an example.

$ bin/rails generate rspec:scaffold user

Normally, all test cases created can be executed directly at this time.

$ rspec

However, on the M1 system, we will encounter problems.

Rails bootstrap puts selenium-webdriver in by default, but selenium-webdriver is compiled for the x86 platform, so an error occurs when running rspec.

I didn’t have to run end-to-end tests, so I just unplugged the irrelevant dependencies from Gemfile and rspec ran correctly.

The result of this section is as follows, Github commit. From the commit, you can see that scaffold generates many user model related test cases.

Start testing

Let’s test the model first. There are several constraints that must be tested.

  1. first_name and last_name must have values.
  2. gender must be one of male, female and others.
  3. age must be a natural number.
  4. address field is an object and only the three keys country, address_1 and address_2 are allowed.

The full test is listed in the link below.
https://github.com/wirelessr/Hello-RoR/commit/55fca06899d60256345c9d5ec5f14a2aa51a8b3f

Then we proceeded to test the controller. Fortunately, rspec:scaffold already has the basic framework set up, so we just need to fill in the details.

The native test file is in spec/requests/users_spec.rb, and there are a few places where the skip function skips, and all we have to do is follow the instructions in skip to replace it with a legal or illegal user model.

The Github commit is attached.

My reflections on RSpec

In fact, the syntax of RSpec is very familiar to me because of my experience in writing mocha on top of Node. Whether it’s describe or it or even expect, it’s all similar, so I didn’t encounter any difficulties.

In the process of practicing, I referred to an RSpec best practice document. I used to write mocha very casually, without referring to any rules, so this document also provides good advice. In the future, whether it’s Ruby’s RSpec or Node’s mocha, it should be able to be written in a more beautiful way.

The reference link is directly attached, Better Specs.

My reflections on Ruby

After practicing Rails for a few days, I didn’t encounter too many difficulties because I could see more or less the shadow of other languages in Ruby, among which I think the closest should be Python, and many concepts are shared.

However, there are some Ruby-specific behaviors that took me a while to study.

Symbol

It is common to see variables starting with a colon in Ruby, such as :abc, which actually refers to the string abc. Unlike a string, however, this string is immutable.

This has the advantage that the comparison between symbols does not need to be done character by character, but can be done directly to the memory address, so it is faster than a string comparison.

This concept is also found in Python, which places common words and numbers at fixed memory addresses to speed up references. In the Python example below, the addresses of a and b are the same, and both come from the object of 1, which has been predefined.

1
2
3
4
5
6
>>> a = 1  
>>> b = 1  
>>> id(a)  
5777693336  
>>> id(b)  
5777693336

Parentheses can be omitted

In Ruby, both parentheses and braces can be omitted, so a bunch of behaviors appear that are difficult for first-time users to understand. For example.

  • When formatting a string, "#{abc} is good", it’s hard to know if the abc refers to a variable or the function abc() is called.
  • When calling the function foo a=> 1, b => 2, c => 3 how many arguments does foo have when written in this way? The answer is that we don’t know, we need to see the signature of foo to know.

There are also various variants, such as this omission of parentheses really made me suffer a lot in reading other people’s code.

Class definition

The definition of an attribute within an object is @, so @abc is equivalent to Python’s self.abc.

But if we define a function using self, it means something completely different, def self.bar(), which in Python terms means bar is a classmethod.

Poor performance

In CPython, the performance of the entire application is limited by the implementation of GIL, and even with multi-threaded execution, all operations must still be performed sequentially.

This is also true for Ruby, which also has GIL, and usually uses pre-fork in order to fully utilize the machine’s resources, and the Gunicorn used in Python is actually derived from Ruby’s Unicorn.

Afterword

Although the process of practicing Rails went smoothly, I actually encountered a lot of difficulties while doing the code review, both related to the Ruby features I mentioned in the previous section, and from the Rails features.

I’ll describe my thoughts on Ruby on Rails in the next article, which should be the last in this series.

Originally published on Medium

Posted on In

Building Ruby on Rails from Scratch

Day 1: From Nothing to Something

I have changed my job a while ago, so I will take some time to pick up the architecture and services of the new organization. However, in order to practice my English and take notes, I will still try to post as often as possible once a week, but the content will be different from the past, from an introduction to software architecture to my Ruby learning experience.

Because the programming language used in my new job is Ruby, and I have no experience with Ruby before. Therefore, this series will focus on the perspective of someone who already knows multiple languages and how to quickly get started with Ruby on Rails, not to write perfect Ruby, but to be able to quickly build a workable application. By the way, it’s a bit like how I learned English, there’s no structure at all, it just works and can be communicated anyway.

Installation

My work machine is a MacPro M1, so all operations will be Mac-based. M1 is also a very important keyword, and I stepped on several traps on M1, which will be described in a later article.

Because I need to install many versions of Ruby, I use a similar solution to nvm, rvm.

To install rvm on a Mac, we first have to install gnupg.

$ brew install gnupg

Then just follow the steps on the official website.

$ gpg — recv-keys 409B6B1796C275462A1703113804BB82D39DC0E3 7D2BAF1CF37B13E2069D6956105BD0E739499BDB
$ curl -sSL https://get.rvm.io | bash
$ rvm install 2.7
$ rvm 2.7 — default

Finally, just install Rails. I know there are newer versions of Rails already available, but the resources I have on hand are based on 5.x, so I chose to install 5.2.8.

$ gem install rails -v 5.2.8

Start building a Rails application

First, let me describe my goal. I want to make a simple web store with two objects, user and store, where the relationship between these two objects is a one-to-one mapping. Also, using MongoDB instead of the built-in SQLite.

Building a Rails application can be done easily with scaffold, which provides a fully resource-based, standard RESTful API.

Start by creating a project.

$ rails new hello_rails
$ cd hello_rails
$ bin/rails server

At this point, the application has been created and is working on the 3000 port. Connect directly to http://localhost:3000 and you will see the welcome page.

Next, we create the first model, starting with the user’s first and last name.

$ bin/rails generate scaffold User first_name last_name
$ bin/rails db:migrate

The user model has been created so far, and if you connect directly to http://localhost:3000/users you will find out not only the API but also the basic UI has been generated.

We haven’t even written a single line of code yet!

Create new routes

Since we already have the basic API, I’d like to generate a few new API routes. Let’s take non-resource-based routes and resource-based routes as an example each.

First, a non-resource-based route. I want to create a user count function, so I need /users/count. I’ll attach the specific process directly at Github commit.

Generally speaking, what we need to do is to modify config/routes.rb and create a count of the corresponding controller and view.

Further is the resource-based routing, the concept is similar, also attached commit link.

The only difference between the two is in config/routes.rb, where non-resource-based routes are built on top of collection, while resource-based routes are built on member.

Create new fields

Now we have two fields in the user model, first_name and last_name, and we will add more fields, such as gender and age, and we will add some constraints to each field.

For example, first_name and last_name must be present and cannot be blank. And gender must be one of male, female or others. Finally, age must be a natural number.

Let’s start by adding the gender field, i.e. Github commit.

The most important change is in app/models/user.rb. In addition to the new fields, we also add the constraints of the existing fields. Of course, remember to run migration after modifying the model.

$ bin/rails db:migrate

As you can see, adding an age is as simple as Github commit.

From SQLite to MongoDB

We have implemented a user model in SQLite, but SQLite is a local database and cannot be used for distributed systems. Therefore, we will adopt a standalone database and use MongoDB, which is more flexible in terms of schema, for the subsequent development.

The whole migration process follows the official documentation.

I also attach the full Github commit.

First rewrite the model by removing ApplicationRecord and adding Mongoid with its fields. Next, we completely remove all the places where active_record and active_storage are used in the source code (which is not much).

Afterword

There should be a few more articles to come on expanding this application, which is my first step into Rails.

I’ve experienced many different backend languages before, including Python, Golang, and Node, but none of them are as friendly as Ruby on Rails.

From this article, it’s easy to see that building a “standard” RESTful API with Rails is very simple, and if you don’t have any special needs, you don’t even have to write a single line of code.

Why emphasize standard RESTful APIs?

In fact, the APIs I have written in the past are not so RESTful, such as ${resource}/${id}, and then provide GET, POST and DELETE operations, such strict routing if not generated by the framework itself, I believe few people will fully follow.

But Rails provides a simple scaffold to make things easy, and even unit tests are built in, as described in a later article.

Although I took a few days to get familiar with Ruby and Rails, it still takes a bit of time to digest and organize, so let me take a few weeks to finish my thoughts on Ruby. But I have to say, Rails is amazing to me. I can see brilliant ideas everywhere, and there are a lot of design patterns in it. Although it was a bit painful to learn a new language and framework, I still got some insights out of it.

Originally published on Medium

Posted on In

Consistency between Cache and Database, Part 2

This is the last article in the series. In the previous article we introduced why caching is needed and also introduced the Read Aside process and potential problems, and of course explained how to improve the consistency of Read Aside. Nevertheless, Read Aside is not enough for high consistency requirements.

One of the reasons why Read Aside can cause problems is because all users have access to the cache and database. When users manipulate data at the same time, inconsistencies occur due to various combinations of operation order.

Then we can effectively avoid inconsistency by limiting the behavior of manipulating data, which is the core concept of the next few methods.

Read Through

Read Path

  • Reading data from cache
  • If the cache data does not exist
  • Read from database by cache
  • Cache returns to the application client

Write Path

  • Don’t care, usually used in combination with Write Through or Write Ahead.

Potential Problems

The biggest problem with this approach is that not all caches are supported, and the Redis example in this article does not support this approach.

Of course, some caches are supported, such as NCache, but NCache also has its problems.

First, it does not support many client-side SDKs. .NET Core is the native support language and there are not many options left.

Besides, it is divided into open source version and enterprise version, but you should know that if the open source version is not used by many people, then it is a tragedy when something goes wrong. Even so, the Enterprise version requires a license fee, not only for the infrastructure, but also for the software license.

How to Improve

Since NCache has its high cost, can we implement Read Through ourselves? The answer is yes.

For the application, we don’t really care what kind of cache is behind it, as long as it provides us with data fast enough, that’s all we need. Therefore, we can package Redis as a standalone service called Data Access Layer (DAL), with an internal API server to coordinate the cache and database.

The application only needs to use the defined API to get data from the DAL, and doesn’t need to care about how the cache works or where the database is.

Write Through

Read Path

  • Don’t care, the actual work is usually done through Read Through.

Write Path

  • Data only written for caching
  • Updated database by cache

Potential Problems

As with Read Through, not every cache is supported and must be implemented on your own.

In addition, caching is not designed to be used for data manipulation. Many databases have capabilities that caching does not have, especially the ACID guarantee for relational databases.

More importantly, caching is not suitable for data persistence. When an application writes to a cache and considers the update to be finished, the cache may still lose the data for “some reason”. Then, the current update will never happen again.

How to Improve

As with Read Through, a DAL had to be implemented, but the ACID and persistence problems were still not overcome. So, Write Ahead was born.

Write Ahead

Read Path

  • Don’t care, the actual work is usually done through Read Through.

Write Path

  • Data only written for caching
  • Updated database by cache

Potential Problems

Similarly, Write Ahead is not supported by many caches. Even though the read path and write path look the same as Write Through, the implementation behind it is very different.

Write Ahead was created to solve the problem of Write Through, so let’s introduce it first.

We will also implement a DAL, but unlike Write Through, it is actually an internal message queue rather than a cache. As you can see from the diagram above, the entire DAL architecture becomes more complex. To use the message queue correctly requires more domain knowledge and more human resources to design and implement.

How to Improve

By using message queues, the persistence of changes can be effectively ensured, and message queues also guarantee a certain degree of atomicity and isolation, which is not as complete as a relational database, but still has a basic level of reliability.

Moreover, message queues can merge fragmented updates into batches. For example, when an application wants to update three caches so it sends three messages, the DAL worker can merge the three messages into a single SQL syntax to reduce access to the database.

It is important to note the message queue must be used to ensure the order of messages, because for database updates, inserting and then deleting has a very different meaning than deleting and then inserting. The way to ensure message order is slightly different for each message queue, and in the case of Kafka it can be achieved by using the correct partition keys.

Nevertheless, the complexity of implementing Write Ahead is very high. If you cannot afford such complexity, then Read Aside is a better choice.

Double Delete

We have already talked about two major types of cache patterns, which are

  • Read Aside
  • Read Through, Write Through, Write Ahead

The most fundamental difference between these two types is the complexity of implementation. In the case of Read Aside, it is very easy to implement, and it is also very simple to do right. However, Read Aside can easily generate various corner cases under many interactions.

On the other hand, corner cases can be avoided by implementing DAL, but it is very difficult to implement DAL correctly, and it requires extensive domain knowledge to implement correctly, which further makes DAL difficult to achieve.

So, is DAL the only way to reduce the number of corner cases? No, not really.

This is what the Double Delete pattern is trying to solve.

Read Path

  • Reading data from cache
  • If the cache data does not exist
  • Read from the database instead
  • and write back to the cache

The process is exactly the same as Read Aside.

Write Path

  • Clear the cache first
  • Then write the data into the database
  • Wait for a while, then clear the cache again

Potential Problems

The purpose of Double Delete is to minimize the time spent in disaster due to Read Aside corner cases.

The entire inconsistency depends entirely on the waiting time, which is equal to the maximum time waiting.

But how to wait is also a difficult practical problem. If we let the client originally started to deal with it, then the killed scenario in corner case 2 would still not be solved. If someone else performs it in an asynchronous way, then the communication contract and workflow control in between will be complicated.

How to Improve

The same corner case 2 as Read Aside, but again, it can be reduced by a graceful shutdown.

Conclusion

In this article, we introduce many ways to improve consistency. In general, when consistency is not a critical requirement, Cache Expiry is sufficient and requires a very low implementation effort. In fact, the widely used CDN is just one of the cases where Cache Expiry is used.

As the scenario becomes more and more critical and requires higher and higher consistency, then consider using Read Aside or even Double Delete to achieve it. The correct implementation of these two methods is sufficient for consistency to satisfy most scenarios.

However, as consistency requirements continue to increase, more complex implementations such as Read Through and Write Through or even Write Ahead become necessary. Although this can improve consistency, it is also costly. First, it requires sufficient manpower and domain knowledge to implement. In addition, the time cost of implementation and the maintenance cost afterwards are significantly higher. Furthermore, there are additional expenses to operate such an infrastructure.

To further improve consistency, it is necessary to use more advanced techniques, such as consensus algorithms, to ensure the consistency of cache and database content by majority consensus. This is also the concept behind TAO, but I am not going to introduce such a complex approach, after all, we are not Meta, at least, I am not.

In a general organization, the requirements for consistency are not as strict as, let’s say, 10 or more nines, and a general organization cannot operate such a complex and large architecture.

Therefore, in this article, I have chosen practices that we can all achieve, but even if they are simple practices, there is already a high enough level of consistency if they are implemented correctly.

Originally published on Medium

Posted on In

Consistency between Cache and Database, Part 1

Today we are going to talk about consistency, especially the consistency of data between cache and database. This is actually an important topic, particularly as the size of an organization increases, the requirements for consistency will grow and so will the implementation of consistency.

For example, a startup service will not have a higher Service Level Agreement, aka SLA, than a mature service. For a startup service, a data consistency SLA of four nines (99.99%) might be considered high, but for a mature service like AWS S3, the data SLA is as high as 11 nines.

We all know that for every nine, the difficulty and complexity of the implementation will increase in an exponential way, so for a startup service, there are basically no resources to maintain a very high SLA.

Thus, how can we use the resources as effectively as possible to improve consistency? That’s what this article will introduce. Again, the consistency mentioned here refers specifically to the consistency between cache and database data.

Why Caching?

I believe we all agree that inconsistencies are inevitable when we put data in two different storages. So what makes us put data into cache rather than risking inconsistency?

  1. The price of databases is high. In order to provide data persistence and as high availability as possible, even the relational database provides ACID guarantee, which makes the database implementation complex and also consumes hardware resources. Regardless of hard drives, memory or CPU, the database must be supported by good hardware specifications in order to work well, which also leads to the high price of the database itself.
  2. The performance of the database is limited. In order to persist the data, the data written to the database must be written to the hard drives, which also causes the performance bottleneck of the database, after all, the read and write efficiency of hard drives is much worse than memory.
  3. The database is far away from the user. Here, the far means the physical distance. As mentioned in the first point, because of the high cost of databases and the need to centralize data as much as possible for further analysis and utilization, a global service database is not placed in all over the world. The most common practice is to choose a fixed location. In Asia, for example, because AWS’s Singapore data center is lower priced, it is often chosen for Asian users, but for Japanese users, the network distance increases and the transfer rate decreases.

For the above three reasons, the need for caching arises.

Because a cache does not need to be persistent, it can use memory as the storage medium, so it is inexpensive and has excellent performance. Because of the low price, caches can be placed as close to the user as possible, for instance, caches can be placed in Tokyo so that users in Japan can use them nearby.

Caching Patterns

It seems that caching is necessary, so how do we use caching for the consistency as much as possible?

To keep this article from losing focus, the caches mentioned are all based on Redis and the database is MySQL, and our goal is to improve consistency as much as possible with limited resources, both hardware and manpower, so the complex architectures of many large organizations are out of our scope, such as Meta’s TAO.

TAO is a distributed cache and has a very high SLA (10 nines). However, to operate such a service, there is a very complex architecture behind it, and even the monitoring of caching is extremely large, which is not affordable for an ordinary organization.

Therefore, we will focus on the following patterns, highlighting their problems and how to avoid them as much as possible.

  • Cache Expiry
  • Read Aside
  • Read Through
  • Write Through
  • Write Ahead (Write Behind)
  • Double Delete

The following sections will follow the below procedure.

  1. read path
  2. write path
  3. potential problems
  4. how to improve

Cache Expiry

Read Path

  • Reading data from cache
  • If the cache data does not exist
  • Read from the database instead
  • and write back to the cache

We add a TTL to each data when writing back to the cache.

EXPIRE key seconds [ NX | XX | GT | LT]

Write Path

  • Write data to the database only

Potential Problems

When updating data, inconsistencies occur because the data is only written back to the database. The inconsistency time depends on the TTL settings, nevertheless, it is difficult to choose a suitable value for the TTL.

If the TTL is set too long, the inconsistency time will be increased and, on the contrary, the cache will not be effective.

It is worth mentioning that caching is built to reduce the load on the database and to provide performance, and a very short TTL will make caching useless. For example, if the TTL of a certain data is set to 1 second, but no one reads it within 1 second, then the cached data will be no value at all.

How to Improve

The read path seems to be the usual practice, but when the database is updated, there should also be a mechanism for updating the cached data. And this is also the concept of Read Aside.

Read Aside

Read Path

  • Reading data from cache
  • If the cache data does not exist
  • Read from the database instead
  • and write back to the cache

This process is the same as Cache Expiry, but the TTL can be set long enough. This allows the cache to have as much play time as possible.

Write Path

  • Write the data into the database first
  • Then clean cache.

Potential Problems

Such read and write paths look fine, but there are a few corner cases that can’t be avoided.

A wants to update the data, but B wants to read the data at the same time. Individually, both A and B have the right process, but when both of them happen together, there may be a problem. In the above example, B has already read the data from the cache before A clears the cache, so the data that B gets at that moment will be old.

When A is updating the data, the database is already finished updating, but it is killed due to “some reason”. At this moment, the data in the cache will remain inconsistent for a while until the next time the database is updated or a TTL occurs.

Getting killed may sound serious and rare, but it’s actually more likely to happen than you might think. There are several scenarios where a kill can occur.

  1. When changing versions, either through containers or VMs, the old version of the application must be replaced with the new version, and the old version will be killed.
  2. When scale-in, the redundant application will be recycled and will also be killed.
  3. Lastly, it is the most common, when the application crashes, it will inevitably be killed.

When A wants to read the data and B wants to update the data, again, both of them have the right individual process, but the error occurs.

First A is trying to read data because no corresponding result is found in the cache, so he reads from the database; at the same time, B is trying to update the data so he clears the cache after the database operation. Then, A writes the data to the cache, and the inconsistency occurs, and the inconsistency will remain for a while.

How to Improve

Case 1 and Case 3 can be minimized when the application manipulates data correctly. Take Case 1 as an example, don’t do anything extra after updating the database and clean up the cache right away, while in Case 3, after reading data from the database, don’t do too much format conversion and write the result to the cache as soon as possible. In this way, the chance of occurrence can be reduced, but even so, there are still some unavoidable situations, such as the stop-the-world generated by garbage collection.

Case 2, on the other hand, can reduce the chance of artificial occurrences by implementing a graceful shutdown, but there is nothing that can be done for an application crash.

Read Aside Variant

In order to solve Case 1 and Case 2, some people will try to modify the original process.

Read Path

  • Reading data from cache
  • If the cache data does not exist
  • Read from the database instead
  • and write back to the cache

This process is exactly the same as the original Read Aside.

Write Path

  • Clean cache first
  • Then write the data into the database.

This process is the opposite of the original Read Aside.

Potential Problems

Although the original Case 1 and Case 2 are solved, a new problem is created.

When A tries to update the data, and B wants to read the data, A clears the cache first; then B cannot read the data, so it reads from the database instead, and A continues to update the database. Finally, B writes the read data back to the cache. The inconsistency is occurred.

How to Improve

In fact, Case 1 and Case 2 are much less likely to occur than the corner cases of this variant, especially when the correct implementation of Read Aside has significantly reduced the occurrence of Case 1 and Case 2. On the other hand, the corner cases of the variant cannot be effectively improved.

Therefore, it is not recommended to use such a variant.

Conclusion

In general, a relatively high level of consistency can be achieved by Read Aside, even if it is only a simple implementation, but it can also have a very good reliability.

Nevertheless, if you would like to improve consistency further, Read Aside alone is not enough, and a more complex approach is required, but also at a higher cost. Therefore, I will leave these approaches for the next article. In the next article, I will describe how to make the best use of the resources at hand to achieve as much consistency as possible.

To emphasize again, although Read Aside is very simple, it is reliable enough as long as it is implemented correctly.

Originally published on Medium

Posted on In

Explain combining Domain-Driven Design and Databases

A while ago, we explained how to design software in a clean architecture way. At that time, although we provided the design and implementation of the domain objects and also implemented the unit tests, we did not describe how to integrate with the database.

Therefore, this article will present another example of how domain-driven design and database can be put together. Next, we will provide a real-world design of a common street-level gashapon store with a MySQL database.

User Stories

As we’ve done before, we start by describing the user story, and we understand our needs through that story.

  • There will be a lot of machines, each with different combinations of items.
  • In order to allow “generous” customers to buy everything at once, we offer the option to draw a lot of items at once.
  • When we run out of items, we need to refill them immediately.
  • If a person who draws a lot of items at one time runs out of items, we will refill the items immediately so that they can continue to draw.

Such a story is actually a scenario that happens in every gashapon store, and after a clear description, we will know how to build the domain model.

Generally speaking, we will need to model a gashapon machine and a gacha entity.

Use Cases

Then, we define more precise use cases based on user stories. Unlike a story, the use case will clearly describe what happened and how the system should react.

  • Because this is an online gashapon store, it is possible for multiple people to draw at the same time. But just like the physical machine, everyone must draw in order.
  • In the process of refilling the gacha, the user is not allowed to draw until all the gacha have been refilled.
  • When A and B each draw 50 at the same time, but there are only 70 in the machine, one of them will get the 50 in the batch, while the other will draw 20 first, and then wait for the refill before drawing 30.

With the use case, we can either draw a flowchart or write a process based on it. In this example, I chose to write the process in Python as follows.

1
2
3
4
5
6
7
8
def draw(n, machine):  
    gachas = machine.pop(n)  
      
    if len(gachas) < n:  
        machine.refill()  
        gachas += draw(n - len(gachas), machine)  
      
    return gachas

In the user story, we mentioned that we will model a gashapon machine and a gacha. So the machine in this example code is the gashapon machine, which provides both pop and refill methods. On the other hand, gachas are a list with gacha in it.

Before we go any further, there is one very important thing that must be stated. Both the pop and refill methods must be atomic. To avoid racing conditions, both methods must be atomic and cannot be preempted, while there will be multiple users drawing simultaneously.

Database Modeling

We already have machine and gacha, and these two objects are very simple for developers who are familiar with object-oriented programming, but how should they be integrated with the database?

As mentioned in the book Patterns of Enterprise Application Architecture, there are three options to describe the domain logic on the database.

  1. Transaction Script
  2. Table Module
  3. Domain Model

The book explains the pros and cons of these three choices individually, and in my experience, I prefer to use Table Module. The reason is, the database is a standalone component, and to the application, the database is actually a Singleton. To be able to control concurrent access on this Singleton, it is necessary to have a single, unified and public interface.

With Transaction Script, access to the database is spread all over the source code, making it almost impossible to manage when the application grows larger. On the other hand, Domain Model is too complex, as it creates a specific instance for each row of the table, which is very complicated in terms of implementation atomic operations. So I chose the compromise Table Module as the public interface to interact with the database.

Take the above machine as an example.

Since we have finished building the domain object, let’s define the schema of the table GachaTable.

In the table, we can see there are two machines, one with the theme Jurassic Park and the other Ice Age, both of which have two individual gachas. The Jurassic Park machine looks like three, but one has actually been drawn already.

Gacha’s domain model is straightforward, which is gacha_id or more detailed, which may be the theme plus items, such as: Jurassic Park and T-Rex.

A more interesting topic to discuss is machine. machine needs to define several attributes. First, it should be able to specify an id in the constructor, and second, there are two atomic methods, pop and refill. We will focus on these two methods in the following sections.

Atomic Pop

It is not difficult to implement an atomic pop: first sort by sequence number, then take out the first n rows, and finally set is_drawn to true. Let’s take the Jurassic Park machine as an example.

1
2
3
4
START TRANSACTION;  
SELECT * FROM GachaTable WHERE machine_id = 1 AND is_drawn = false ORDER BY gacha_seq LIMIT n FOR UPDATE;  
UPDATE GachaTable SET is_drawn = true WHERE gacha_seq IN ${resultSeqs};  
COMMIT;

As mentioned in my previous article, in order to avoid lost updates, MySQL has three approaches. In this example, to achieve atomic updates, it is easiest to add FOR UPDATE to the end of SELECT to preempt these rows.

When the update is complete, the result of SELECT can be wrapped into Gacha instances and returned. This way the caller will be able to get the gachas drawn and know how many were drawn.

Atomic Refill

Another atomic method is refill. It is simple to not get interrupted in the middle of the fill process. Because MySQL transactions are not read by the rest of clients until COMMIT under the Repeatable Read condition.

1
2
3
4
5
START TRANSACTION;  
for gacha in newGachaPackage():  
    INSERT INTO GachaTable VALUES ${gacha};  
      
COMMIT;

Is that all? No, not really.

This problem occurs when both users draw n, but there are not enough n gachas to draw.

The sequential diagram above shows when A and B draw at the same time, A will draw r gachas and B will not, as we expected. However, both A and B will refill together, resulting in the same batch of gachas being filled twice.

Usually, this does not cause any major problems. Because we arrange the pop by sequence number, we can guarantee that the second batch will be drawn only after the first batch is drained. But if we want to change the item, then the new items will be released later than we expected.

On the other hand, two people are refilling at the same time so the redundancy becomes twice as much, and if the system has a very large number of simultaneous users, then the redundancy may become several times as much and take up a lot of resources.

How to solve this problem? In the article Solving Phantom Reads in MySQL, it is mentioned that we can materialize conflicts. In other words, we add an external synchronization mechanism to mediate all concurrent users.

In this example, we can add a new table, MachineTable.

This table also allows the original machine_id of GachaTable to have an additional foreign key reference target. When we do refill, we have to lock this machine first before we can update it.

1
2
3
4
5
6
7
8
START TRANSACTION;  
SELECT * FROM MachineTable WHERE machine_id = 1 FOR UPDATE;  
SELECT COUNT(*) FROM GachaTable WHERE machine_id = 1 AND is_drawn = false;  
if !cnt:  
    for gacha in newGachaPackage():  
        INSERT INTO GachaTable VALUES ${gacha};  
      
COMMIT;

At first, we acquire the exclusive lock, then we re-confirm whether GachaTable needs refill, and finally, we actually insert the data into it. If it is not reconfirmed, then it is still possible to repeat refill.

Here are a few extended discussions.

  1. Why do we need an additional MachineTable? Can’t we lock the original GachaTable? Due to phantom reads, MySQL’s Repeatable Read cannot avoid write skew from phantom reads in the case of new data. The detailed process is explained in my previous article.
  2. When locking MachineTable, don’t you need to lock GachaTable when getting the count from GachaTable? Actually, it is not necessary. Because it will enter the refill process, it must be because the gachas have been drawn and everyone is waiting for the refill, so don’t worry about the pop.

Conclusion

In this article, we explain the issues to be considered when combining a domain-driven design with a database design through a real-world example.

The final result will contain two objects, Gacha and Machine, and the database will also contain two tables, GachaTable and MachineTable. All methods within Machine are atomic in nature.

As we described in the design steps before, we need to first define the correct user stories and use cases, then start the modeling, and finally the implementation. Unlike normal application implementations, the database exists as a large Singleton, so we need to better integrate the database design into our domain design as well.

In order to minimize the impact of the database on the overall design, it is crucial to build the domain model correctly. Of course, in this article we adopt the Table Module approach to domain design, which has its advantages and disadvantages.

The advantage is by using the Machine domain model, we are able to simulate the real appearance of a gashapon machine and provide a common interface for all users to synchronize their processing. By encapsulating the gashapon behavior into Machine, future gashapon extensions can be easily performed. All the operations of GachaTable and MachineTable will also be controlled by a single object.

The downside is that Machine actually contains the gashapon machine and the gacha table inside, which is too rough for a strict object-oriented religion. When more people are involved in the project, everyone’s understanding of the objects and the data tables begins to diverge, leading to a design collapse. For a large organization, the Table Module has its scope, and better cross-departmental collaboration relies on complete documentation and design reviews, which can affect everyone’s productivity.

In this article we do not take too much time to explain the design process, but rather focus on how to integrate the database design in the domain objects. If you want to learn more about the details mentioned in this article, I have listed my previous articles below.

Originally published on Medium

Posted on In

Message Queue in Redis, Part 2

A while ago, I mentioned that I’m in a budget-constrained organization, so we can’t afford to use a true message queue. Instead, we have chosen to use a second-best approach to meet our immediate needs and a simple solution to implement, using Redis.

Nevertheless, there are still many different ways to implement Redis as a message broker. At that time, we chose the option which was the fastest to get up and running with the least implementation effort: lists. However, as the system evolved and new feature requests were made, the original solution no longer worked.

The advantages of the list are

  1. easy to implement
  2. support for consumer groups
  3. the ability to decouple producers and consumers

The disadvantages are also obvious.

  • At-most-once guarantee

Now, we need at-least-once guarantee, and lists don’t cover this need. The Redis Stream mentioned in the previous article was not adopted because of the large implementation effort. So we started looking for a new alternative.

Bull.js

After some comparisons, we finally chose Bull.js.

The reasons are as follows.

  1. support at-least-once guarantee.
  2. it has a lower implementation effort and provides many monitoring tools, e.g., Bull Exporter.
  3. full-featured, including retry, time delay, etc.
  4. even support rate limit.

However, in the working process, I have to say that the official document is not detailed enough and it took us some time to try it successfully. In this article I will show the two most important issues we encountered and explain the solutions.

Redis Cluster

Bull is supported for Redis clusters. Unfortunately, the description is scattered in several places in the document.

First, the description from the constructor’s document needs to provide the parameter createClient, and the rule is

(type: ‘client’ | ‘subscriber’ | ‘bclient’, config?: Redis.RedisOptions): Redis.Redis | Redis.Cluster;

Redis.Redis and Redis.Cluster at the end of the rule actually refer to the ioredis constructors, so to set them up, we must use the ioredis constructors.

1
2
3
const Redis = require("ioredis");  
Redis.Redis  
Redis.Cluster

Even so, I don’t understand what kind of format createClient needs to provide, is it an object? What are the keys to Redis.Redis and Redis.Cluster?

Finally, I found out from another section of the document, Reusing Redis Connections I realized that it was a function. Anyway, put the pieces together.

1
2
3
const Redis = require('ioredis');  
let client;  
let subscriber;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const opts = {  
  // redisOpts here will contain at least a property of connectionName which will identify the queue based on its name  
  createClient: function (type, redisOpts) {  
    switch (type) {  
      case 'client':  
        if (!client) {  
          client = new Redis.Cluster(REDIS_URL, redisOpts);  
        }  
        return client;  
      case 'subscriber':  
        if (!subscriber) {  
          subscriber = new Redis.Cluster(REDIS_URL, redisOpts);  
        }  
        return subscriber;  
      case 'bclient':  
        return new Redis.Cluster(REDIS_URL, redisOpts);  
      default:  
        throw new Error('Unexpected connection type: ', type);  
    }  
  },  
  prefix: '{myprefix}'  
}
1
const queueFoo = new Queue('foobar', opts);

In this way, Redis clusters can be used as brokers.

Memory Leakage

Once we got over the cluster issue, we pulled Bull online and started testing. Then we ran into a serious problem where the underlying Redis started leaking memory.

As you can see from the figure, Redis memory usage has been skyrocketing since it was enabled.

So we took a closer look at the document to find out what we missed, and finally found a hint in the tutorial.

A job begins as Job Added and ends up as Job Finished, regardless of whether it succeeds or fails. In other words, as soon as the job enters Redis, it stays there, regardless of whether it succeeds or fails. How do we solve this?

Specify the parameters removeOnComplete and removeOnFail in add to ensure jobs do not stay in the last finish state. I believe that removeOnComplete can definitely be set, but removeOnFail depends on the needs of each user, e.g., whether they want a failure count, whether they want a manual recovery from failure, etc. In our case, we don’t need to keep the job even if it fails, so both parameters are true.

What about the jobs left online? Bull also provides a way to clean jobs.

1
2
3
4
//cleans all jobs that completed over 5 seconds ago.  
await queue.clean(5000);  
//clean all jobs that failed over 10 seconds ago.  
await queue.clean(10000, 'failed');

After running online, you will see an extremely significant drop in usage.

The first half remains horizontal because we have already added removeOnComplete and removeOnFail, so no more increases are made. The vertical line in the middle is the process of clean.

It is worth mentioned that the clean process locks the entire message queue, so it may affect the online functions and is not recommended to perform it under production environment. The duration of the lock depends on the number of jobs to be cleaned.

Conclusion

I always talked about the evolution of systems. As you should have noticed from my previous articles, in a limited organization, we do not always have enough manpower, budget or even knowledge to build the perfect system, or to be more precise, no system is perfect.

Every time we design a system, we choose the relatively acceptable solution among many factors, which means we have to face the potential problems. For me, I always take the most achievable implementation, but with the understanding that such choices are not static and retain the flexibility to meet future requirements.

For many people, the replacement of the message queue is a very huge exercise. But for my organization, it’s a simple implementation by a few people, and then it’s done. The reason why I always mention domain-driven design and decoupling is to make it easier to do system evolution when needed.

Bull currently meets all of our needs, is reliable enough, and even offers a monitoring solution. I believe we will probably be able to stop worrying about message queues for a long time.

Originally published on Medium

Posted on In

Explain Redlock in Depth

Previously, I introduced two types of locks, mutex locks and barriers, and I used Redis as an example to explain the differences between the two types of locks. Shortly after that, I received a reply saying that if you want to implement distributed locks, the Redis approach is not enough and you should refer to Redlock.

Well, his opinion is basically right.

Although Redlock is implemented through Redis, it can achieve a very high level of consistency and is one of the best paradigms for implementing distributed locking. However, Redlock has a very high cost behind it and is not suitable for all organizations and services.

Nevertheless, I will introduce Redlock and present my thoughts on why Redlock is impractical.

Redis is not reliable

Before getting started, I should emphasize that Redis persistence is unreliable, even with the most strict settings.

However, in a cluster environment, a Master may have a number of Slave redundancies. Is Redis still unreliable under these conditions? The answer is yes.

In Redis implementation, data replication is performed by the background process, not the master thread, so when a client writes successfully, it does not mean the data is replicated successfully. One of the procedures leading to the problem is as follows.

When Client 1 successfully locks via the original Master, but the Master dies before the data is replicated, then Client 2 can still successfully lock via the original Slave (the new Master).

This is the reason why Redis clusters are still unreliable.

Redlock Concept

As we have seen, a single Redis is not reliable, even in a cluster of multiple Redis. So how do we use Redis to implement a reliable Redlock?

The answer is through majority consensus. Since one Redis is not reliable, we form a committee of multiple Redis. If and only if more than half of the committee members agree, the lock will take effect; otherwise, the lock is invalid. The members can be single, master-slave, or even clusters, but nevertheless, they are independent of each other, in other words, they are not duplicates of each other, not to mention the same cluster.

According to the majority consensus algorithm, the committee should have an odd number of members and be approved when a majority of the members (N/2 + 1) agree. N indicates the total number of members.

The detailed process is written in the official Redis documentation on distributed locking, so I’ll briefly describe the process below.

Suppose our committee is composed of three Redis.

The following is the process of successfully locking up and doing the task and unlocking successfully.

  1. The client who wants to obtain the lock generates a globally unique ID, and the official document selects the system time to use.
  2. Try to use this ID to get the consent of all committee members. Use the command SETNX to do this.
  3. 2 members agree, then the lock is successfully in place.
  4. After getting the lock, the user can do what desired.
  5. The next step is to unlock on every member, whether or not the lock is successfully getting.

The process for unsuccessful locking is similar, as long as Redis1 or Redis2 also fails to respond, then the lock cannot be acquired, that is to say, you cannot do anything, but you still have to perform the process of unlocking all the members.

Redlock Issues

After describing the Redlock process above, I’d like to explain why I rarely consider such an approach.

Firstly, the entire Redlock implementation process, as mentioned in the previous section, is very time-consuming. Particularly if you want to lock for 3 seconds, but actually only 2 seconds or less are left after the locking process. Because the application must be initiated to all Redis first, even with parallel processing, the network delay and packet loss still make the communication chaotic and complicated.

Secondly, in order to make unreliable Redis reliable, many independent Redis must be launched. In the context of site reliability engineering, the maintenance effort for so many Redis is very high, and it is also a problem to make the participating clients aware of the existence of so many Redis. Such a approach is impractical in terms of cost, maintenance effort, and complexity of implementation.

Furthermore, the core of this approach is GUID. If IDs are duplicated, both locking and unlocking may result in false positives and unpredictable results. When this happens, the difficulty of detecting it is also significant. Nevertheless, the system time, as officially documented, is a very weak guarantee. In a distributed system, it is difficult to ensure that all instances have the same time, which is known as clock skew in system design.

To sum up, Redlock is an expensive approach with a lot of technical depth. Although many people have implemented packages in various programming languages based on official documents, does each user understand the potential risks behind the simple use of the packages?

Conclusion

The main reason I don’t use Redlock is because making unreliable Redis reliable is putting the cart before the horse. I always tell my team members, “Data in Redis needs to be aware that it will disappear without warning”. If you want to keep the data persistent, you should consider a more persistent database rather than a cache.

When implementing distributed locking, instead of using Redis, we should use a more reliable database, such as MySQL, which is strongly consistent, or MongoDB, which is my personal preference. But even if we use a database, we should pay attention to the implementation details of the database. Take MongoDB as an example, if we want to implement a lock, then we need to be aware of read-after-write consistency.

There are many aspects to consider behind the system design, and it is not enough to just make the function work. How to control the budget? How to allocate manpower? How to maintain day-to-day? How to troubleshoot? All of these factors involve the capacity of the team, which I believe is far more important than the actual functionality.

When considering the use of distributed locks, I first ask myself, “Do we really need locks? Is there a way to avoid possible race conditions through architecture design?” It is far more effective to avoid locking by improving the architecture than to seek synchronization in a distributed system. If we really have to use a distributed lock, and we need to keep the usage to a minimum, then we don’t need to use Redis but can use a relatively slow database to implement it.

Complexity is killing software developers

And Redlock is one of the most complicated approaches. In my opinion, it should be avoided.

Originally published on Medium

0%