Last week I posted the Java code that identifies TPCC schema as a constrained tree schema. I also explained why the constrained tree schema is important for an OLTP application. However a little more on the subject is in order, so as to make it easier to understand. First, for those who may not have looked at TPCC schema before, following is an ER diagram showing table relationships.
Figure 1. TPCC schema
Warehouse table has w_id as a primary key while District table has a composite primary key that includes d_id and d_w_id. The d_w_id column is a foreign key pointing to the warehouse table. This pattern continues on to other tables like Customer where its composite primary key consists of c_id, c_d_id and c_w_id where c_d_id and c_w_id are foreign keys pointing to District and Warehouse table respectively.
For those who have used any kind of object relational mapping architecture, this type of relationship may look totally out of ordinary. Typically, ORM tools including Hibernate are proponents of using natural key (like a sequence number) as a primary key of a table. Having a composite primary key on a table, makes it difficult to code Hibernate and java, as you have to create a separate java class for the primary key. But for the extreme OLTP applications, the use of composite primary keys make perfect sense.
In applications that process millions of transactions per minute, it's quite likely that its performance, throughput and latency will diminish as tables in which transaction data is kept start filling up rapidly. Throwing additional hardware at this problem works to an extent. Application redesign through various mechanisms including horizontal and vertical partitioning of the relational tables is used when adding hardware doesn't provide proportionate performance boost.
Many applications use range paritioning to improve performance. It works somewhat like this. Let's say a company, ABC Inc, sells customer durable goods in Unites States and has 4 operational units, one each for its 4 regions - east,west, north and south.
It's customer order entry application generates order number based on the region the order originated from. ABC Inc has built an application logic where an order generated from east region will get a number between 1 and 1 million, the one in west gets a number between 1 and 2 million. To provide better performance, ABC's IT department has partitioned the order table into 4 partitions and has hosted each partition on different servers. For many companies this works without much of a problem. However this scheme has some inherent weakness in dealing with situations such as equal load distribution. If, in case of ABC Inc, one of its region is doing twice as good as others (in terms of of its sales numbers), the server meant to capture the order of that region will be twice as active as others providing inconsistent user response time from different regions. Another factor to consider while creating table paritioning is co-location of related data. If orders table is paritioned, what do we do about other tables? Do your queries often join partioned & non-partitioned tables? Why is this important?
Continuing with ABC Inc. example - the IT department decides to partition payments table too. While it's very likely that a sales person from ABC, would like to see orders from his customers, he or she would also like to see if his or her's customers paid for the items sold to them or not. Just so the application continues to provide best scalability and latency, it is imperative that the partitions of payment table are co-located with partitions of order tables on the same server. The co-location of a customer's order and payment information on the same server is the key, but that adds to the complexity of your application. Add another related table and you could imagine how complex the design is going to be.
Hash partioning solves one of the problems, that of uneven load on different servers. What server particular data resides is decided by some hash algorithm which guarantees more even load on the server. The other problem of co-location of data is solved by the constrained tree schema architecture and hash algorithm together. Going back to our TPCC schema, the tables such as district, customer and stock all have warehouse id in their primary key. So, including warehouse id in the hash algorithm of partioning of all the tables automatically guarantees co-location of data. Which means, data related to one warehouse and its related districts, customers and stock are located on the same server. You may really want to read the "The End of Architecture Era" document for further details. It's a great read for any one remotely interested in database design and improving performance. The low-latency.com is another great resource for those interested in extreme performing financial applications.
I hope this helps clear some of the concepts behind extreme scaling and performing application/database design. Don't forget to make comments if you have any.
In applications that process millions of transactions per minute, it's quite likely that its performance, throughput and latency will diminish as tables in which transaction data is kept start filling up rapidly. Throwing additional hardware at this problem works to an extent. Application redesign through various mechanisms including horizontal and vertical partitioning of the relational tables is used when adding hardware doesn't provide proportionate performance boost.
Many applications use range paritioning to improve performance. It works somewhat like this. Let's say a company, ABC Inc, sells customer durable goods in Unites States and has 4 operational units, one each for its 4 regions - east,west, north and south.
It's customer order entry application generates order number based on the region the order originated from. ABC Inc has built an application logic where an order generated from east region will get a number between 1 and 1 million, the one in west gets a number between 1 and 2 million. To provide better performance, ABC's IT department has partitioned the order table into 4 partitions and has hosted each partition on different servers. For many companies this works without much of a problem. However this scheme has some inherent weakness in dealing with situations such as equal load distribution. If, in case of ABC Inc, one of its region is doing twice as good as others (in terms of of its sales numbers), the server meant to capture the order of that region will be twice as active as others providing inconsistent user response time from different regions. Another factor to consider while creating table paritioning is co-location of related data. If orders table is paritioned, what do we do about other tables? Do your queries often join partioned & non-partitioned tables? Why is this important?
Continuing with ABC Inc. example - the IT department decides to partition payments table too. While it's very likely that a sales person from ABC, would like to see orders from his customers, he or she would also like to see if his or her's customers paid for the items sold to them or not. Just so the application continues to provide best scalability and latency, it is imperative that the partitions of payment table are co-located with partitions of order tables on the same server. The co-location of a customer's order and payment information on the same server is the key, but that adds to the complexity of your application. Add another related table and you could imagine how complex the design is going to be.
Hash partioning solves one of the problems, that of uneven load on different servers. What server particular data resides is decided by some hash algorithm which guarantees more even load on the server. The other problem of co-location of data is solved by the constrained tree schema architecture and hash algorithm together. Going back to our TPCC schema, the tables such as district, customer and stock all have warehouse id in their primary key. So, including warehouse id in the hash algorithm of partioning of all the tables automatically guarantees co-location of data. Which means, data related to one warehouse and its related districts, customers and stock are located on the same server. You may really want to read the "The End of Architecture Era" document for further details. It's a great read for any one remotely interested in database design and improving performance. The low-latency.com is another great resource for those interested in extreme performing financial applications.
I hope this helps clear some of the concepts behind extreme scaling and performing application/database design. Don't forget to make comments if you have any.
No comments:
Post a Comment