Many web applications such as TEAMMATES deal with large amount of user data to process user requests. A datastore is used to keep all these data persistent, but a single datastore might not be enough to deal with a larger volume of data if there are too many users. Thus, more datastores will be required to handle user requests. In such a case, data stored on all the datastores must be consistent as a user request might be handled by different datastores, and inconsistency in the datastores will result in wrong data to be returned to the user.

However, datastores can be located at different geographic locations. Hence, time will be required for data to be exchanged between datastores.

Eventual Consistency refers to the situation where some time is required for the creation or update of any data in the datastore to be consistent throughout all datastores. In contrast, strong consistency means all data in all datastores are always consistent, which is the scenario we strive to achieve.

This report aims to:

Demonstrate how eventual consistency arise
Highlight the concerns caused by eventual consistency
Analyze existing solutions to eventual consistency
Provide alternative ways to deal with eventual consistency

Causes of eventual consistency

The Google App Engine (GAE) stores data on multiple servers to improve performance and scalability. As such, multiple copies of the same data item is replicated across the servers. Since the same data is stored on more than one server, changes to the data must be propagated to all replicas of the data on other servers. This process takes time as there are many server and they might be locate at different geographical locations. Thus the datastore is "eventually" consistent for all data to be updated. The following figure shows an example of eventual consistency:

Here, a user writes new data 'X' to server (denoted as a node) A. As copies of data 'X' are also stored on servers B and C, those data are now obsolete. Thus, server A will need to replicate the updated data to these servers. In this scenario, data was successfully replicated to server B, but server C has yet to receive the new data. Thus, any reads to server C will access the old ‘X’ data.

Possible problems caused by eventual consistency

Temporary inconsistency in data

As highlighted in the previous section, a server requires some time to propagate the new data over to other servers. When users tries to read data during this time, there is a possibility to read old data. The following figure shows an example of this scenario.

Here, the user tries to update data ‘X’ to ‘Y’, which is received by server 1. A read query follows immediately, and if the read query is received by server 2 at this instant, the server will return the user with the old data. It is only after data has propagated over that read queries returned from all servers will obtain the most updated data.

In the context of TEAMMATES, we want to minimize such a case as displaying inconsistent will confuse users. An example will be when a user creates a new feedback session, but when the user returns to the home page, due to eventual consistency, the feedback session is not shown to the user.

Race conditions

A race condition refers to a situation where 2 users access the same piece of data at the same time. As data can be stored on more than 1 datastore, there are situations where it is possible for users to concurrently modify the same data that is stored on 2 different datastores. This might cause data to be lost or overwritten by other users.

Fortunately, the GAE always ensure the latest changes are made to the data before it attempts to commit another change. The GAE by perform 2 operations when a change is made to the data to enforce this:

Performing a synchronous update to majority of the datastores when a change is made. This ensures that most datastores are already consistent.

Performing an on-demand update for inconsistent datastores when it makes a change to these datastores. This ensures that data in a datastore is always checked for consistency and updated before a new change is made to the data.

These 2 steps ensures that every time a change is made, consistency is enforced before new changes are made.

However, these operations only apply when changes to the data are made. This means that if a user tries to access some data but does not modify it, old data can still be accessed. This problem was highlighted in the previous section.

Existing solutions provided by GAE

The GAE provides several solutions to enforce consistency of entities within the datastore. In this section, we will discuss the strengths and weaknesses of these solutions and whether they can be applied to TEAMMATES.

Ancestor entity groups

An ancestor entity group allows us to enforce consistency within a group of entities through the following steps:

Define an entity to be an ancestor and another entity as the child.
These 2 entities form a group with an ancestor-child relationship.
The grouping signals to the datastore that strong consistency must be enforced within this group.
A query known as ancestor entity group query can be performed by using the ancestor as part of the query. This query will always return the most updated results.

Benefits of ancestor entity groups

One benefit of this mechanism can be given in the context of TEAMMATES:

An instructor enrolls a class of students
A normal query is then performed to get the students enrolled.
Due to eventual consistency, there are scenarios where the list returned by the datastore is not complete.
Suppose we have established an ancestor-child relationship, with the instructor as the ancestor and students as the child.
We are now able to perform an ancestor query via the instructor, which guarantees the most updated list of students.

Example of using ancestor queries

The main difference between traditional queries and ancestor queries is that we can now include an entity’s ancestor as part of the query. Based on the previous example, if we add a new student to an instructor ancestor whose name is “instructorA” and try to query for the student.

A traditional query will look like the following:

SELECT * FROM student

This query will return all student entities, which we can then perform a search for the student entity that was recently added. However, due to eventual consistency, it is possible that the student is not found.

Using an ancestor query, we are now able to use the ancestor as part of the query and it will look something like:

SELECT * FROM student WHERE ANCESTOR IS instructorA

which will return all student entities whose ancestor is called “instructorA”. Here, the ancestor query will definitely return the student entity based on the guarantee of strong consistency.

Limitations of ancestor entity groups

Ancestor entity groups seem to be a feasible solution to eventual consistency, but we are unable to use this mechanism in TEAMMATES due to the following limitations:

Structure of the TEAMMATES entities.
Entity group relationship cannot be changed after entity creation
Limit of 1 update per second for an entity group

Due to the number of entities types we have (account, instructor, student etc), ancestor-child relationships are difficult to define as there might be multiple ancestors for a single child, which cannot be defined in an ancestor entity group. A scenario based on the above example is a student might be attached to many instructors as the student is enrolled in different course. This results in multiple ancestors, which is not acceptable.

Also, since we are unable to modify the ancestor-child relationship after creation, we will be unable to make changes in future, which is undesirable as changes are made to TEAMMATES regularly.

Lastly, the number of entities we process for user requests can be large. One example is that the class size of students in a course can be a few hundred students. Trying to update all of these students at once will easily exceed the time limit of 60 seconds as we can perform 1 operation on the entity group per second.

Transactions

Transactions ensure a set of datastore operations are run atomically. This means all datastore operations in the transaction either succeed, or no changes are committed.

The general flow of using a transaction is as follows:

Enclose a set of operations within a transaction
Perform the transaction
Check for success
In the case of failure, rollback and take necessary measures to re-perform the operations

Benefits of transactions

Transactions are useful in TEAMMATES as there are many operations that need to be run atomically. One such example is to delete a course. In this action, we are required to delete many entities (evaluations, feedback, students etc), and these deletes are performed by the respective logic component. Suppose a particular delete operation failed; this would mean some entities are not deleted, and a possible outcome is a user still has access to some parts of the deleted course, which will most definitely cause an error in the application. Therefore, a transaction can be used to ensure that if a delete fails, all the previous deletes are rollbacked as if the operation was never performed. We can then take measures to re-perform the operation.

Limitations of transactions

Some limitations of transactions are:

Requires the use of entity groups
Transactions are limited to 5 entity groups

A condition to use transactions is entities must be part of an entity group. As mentioned in the section of Ancestor Entity Groups, TEAMMATES is unable to use entity groups at the moment.

However, it would be possible to simply group every type of entity as it’s own entity group, for example students will belong to a student entity group. Given this, we will be able to use transactions. But due to the second condition, since every entity group is now distinct, transactions will involve multiple groups of entities, but this is limited to 5 entity group. This has a large impact on scalability as it is possible to have operations that can easily involve more than 5 entity groups, and in such cases we will be unable to apply transactions.

Memcache

A memcache is a feature provided by the GAE that allows us to store data temporarily in a cache for faster read / write access. This cache is global and is accessible by all instances of the application.

Benefits of Memcache

Read and write access to the memcache is much faster than to the datastore. As the data is not written to the datastore, there are no write operations to the disk. This results in faster write operations. Therefore, the memcache can potentially increase the responsiveness of the application.

The high speed of writing to the memcache also means there will be no effect of eventual consistency on the data. We can therefore access data that was recently updated or written without the risk of accessing stale data.

Limitations of Memcache

One drawback of memcache is that data stored is transient, meaning that after the cache runs out of space, older data stored on the memcache will be evicted. If this data is not stored in the datastore yet, it will be lost forever.

Thus, there is a need to ensure all data written to the memcache is also written to the datastore at some point. However, this poses another problem as we will need to ensure data in the memcache is not stale. In some cases, data in the datastore is more updated then the data in the memcache, and if we access the data in the memcache instead, this causes another problem in consistency.

Approaches to handling eventual consistency

Currently, 3 methods are used to resolve the effects of eventual consistency: show status messages to the user, display placeholder data in place of actual data and reduce the amount of reads and writes within the code. This section discusses the 3 implementations in detail.

Status messages

This solution displays status messages to the user when we detect the user tries to access some data that might be affected by eventual consistency. This is the minimal solution required at all locations of the application as it provides information of the problem instead of simply showing an error page. Therefore, the solution also acts as a contingency method in case other solutions fail.

The strength of this solution is its simplicity as these messages can be placed easily at the entry point to each page. However, the this solution escalates the problem of eventual consistency to the user. Therefore, another solution is required to hide eventual consistency from the user.

An example of the placeholder message is shown in the following figure:

Placeholder data

This solution extracts data the user has recently modified, and creates a placeholder based on the extracted data. This placeholder will then be shown to the user as though the data had already been successfully persisted in the database. Hence, this solution aims to create an illusion of strong consistency to the user.

This solution is able to provide instant feedback to the user by showing visually the action the user performed was already processed by the system. It also capitalizes on the fact users will need time to perform another action to view or make any changes to the data. Therefore, this extra time required for the user to perform another action might be enough for the data to propagate throughout the other datastores.very

However, this does not guarantee the data will be persisted within the extra time. Also, the implementation can be tedious as we need to determine which data to be used as the placeholder. If the wrong data is shown to the user, this might result in allowing the user access to data which they are not authorized to view.

Reducing read and writes in close proximity

In most cases, eventual consistency is caused by code that modify and read the same data in quick succession. For example, some actions create certain entities and immediately read them for some data. Such cases are vulnerable to eventual consistency as the data is not guaranteed to be propagated to all datastores.

One solution is the following:

Create a local entity.
Perform all modifications to this local entity.
Write this local entity to the datastore.
Any read operations can be performed on the local entity instead of querying for the entity on the datastore.

This solution is difficult to implement due to 2 reasons. First, not every read and write can be combined, as there may be situations whereby an extra read is required. Second, identifying the actual number of read and writes is tough since the codebase is very large.

However, this solution provides the highest success rate at reducing eventual consistency as it directly deals with the source of the problem.

Future work

Implement test suite for eventual consistency in TEAMMATES

Resources

A detailed video on the high replication datastore of Google App Engine

https://www.youtube.com/watch?v=xO015C3R6dw

A Google App Engine article comparing master/slave and high replication datastore

https://developers.google.com/appengine/docs/java/datastore/usingmasterslave

An explanation about Paxos algorithm, an algorithm used to ensure consistency in Google’s high replication datastore

http://css.csail.mit.edu/6.824/2014/papers/paxos-simple.pdf

References

[1] Structuring for Strong Consistency

https://developers.google.com/appengine/docs/java/datastore/structuring_for_strong_consistency

[2] Transactions

https://developers.google.com/appengine/docs/java/datastore/transactions

--- end of report ---