Sunday, September 22, 2013

MySQL 5.7: Monitoring Replication with the Performance Schema tables

In the previous post, we had a look at the Performance Schema tables to monitor MySQL replication. We discussed why these were needed, what advantages they have to offer and what each table stands for. We also did a small exercise to see how one can select a particular table given the data that is needed. We will now dive deeper and look at the individual tables to understand what fields they are made of. We will also go through different scenarios to see how the different pieces of data can be used.

Note that these tables report the status/configuration of a replication slave. So, these are empty at the master server or at a standalone server. All the SELECTs we will talk of, are done at the slave. Lets take the tables one by one and go through them.

REPLICATION_CONNECTION_CONFIGURATION:

This table shows the configuration parameters used by the slave server for connecting to the master server. Lets set up replication with the following CHANGE MASTER TO command executed on a slave server. The  CHANGE MASTER TO command adds/changes the parameters that the slave server uses for connecting to the master server. To see the definition of all the fields in this table, please visit our official documentation.

mysql> change master to master_host='127.0.0.1', master_port=13000 ,
master_user='rpluser', master_password='secret', master_connect_retry=40, 
master_retry_count=10, master_ssl=1, master_ssl_verify_server_cert=1, 
master_auto_position=1; 
Query OK, 0 rows affected, 2 warnings (0.51 sec)

We can now look up the connection parameters set in our table for replication connection configuration. Lets do a SELECT * on this table to see what we get:

mysql> select * from performance_schema.replication_connection_configuration\G
*************************** 1. row ***************************
                         HOST: 127.0.0.1
                         PORT: 13000
                         USER: rpluser
            NETWORK_INTERFACE:
                AUTO_POSITION: 1
                  SSL_ALLOWED: YES
                  SSL_CA_FILE:
                  SSL_CA_PATH:
              SSL_CERTIFICATE:
                   SSL_CIPHER:
                      SSL_KEY:
SSL_VERIFY_SERVER_CERTIFICATE: YES
                 SSL_CRL_FILE:
                 SSL_CRL_PATH:
    CONNECTION_RETRY_INTERVAL: 40
       CONNECTION_RETRY_COUNT: 10
1 row in set (0.00 sec)

You can see that the changes made by CHANGE MASTER TO command can be seen in this table. These values are preserved here until the next CHANGE MASTER TO or RESET SLAVE ALL command. A row in this table represents a connection between the slave and its master. Since we have only one master here, we see only one row. If MySQL supported multi-source, then this table would have information about multiple sources- one row per source.

Note that a START SLAVE is not done yet. The CHANGE MASTER TO command makes changes to the internal data structures regarding the connection parameters (if you know the internals, the "active_mi" variable is what I am talking about) and this table just picks up values from this data structure. So, the values shown in the table just reflects the state of the this data structure at the moment the SELECT was done.

Lets now move to the next table "replication_connection_status".

REPLICATION_CONNECTION_STATUS:

This table shows the current status of connection between the slave and its master. Technically, it talks about the IO thread's status. To view the definition of all the fields in this table, please visit our official documentation. Now, we need a START SLAVE because this command establishes the connection between slave and its master. So, lets execute a START SLAVE/ START SLAVE IO_THREAD command followed by a SELECT* from "replication_connection_status" table.

mysql> start slave; Query OK, 0 rows affected (0.05 sec)

mysql> select * from performance_schema.replication_connection_status\G
*************************** 1. row ***************************
             SOURCE_UUID: 1766a057-10cd-11e3-b06a-0021cc72bfc3
               THREAD_ID: 2
           SERVICE_STATE: ON
RECEIVED_TRANSACTION_SET:
       LAST_ERROR_NUMBER: 0
      LAST_ERROR_MESSAGE:
    LAST_ERROR_TIMESTAMP: 0000-00-00 00:00:00

So, we can see from here that, at the moment SELECT was done:

  1. The slave was reading from a master with UUID= 1766a057-10cd-11e3-b06a-0021cc72bfc3,
  2. The thread that handles this connection (IO thread) has an id=2. The thread_id field is very useful if you want to join this table with other Performance Schema/Information Schema tables. As an example, you can join this table with the table performance_schema.threads to extract a lot more information about this connection (IO thread). Likewise, there is a lot more  thread-wise statistics you can collect with the other existing Performance Schema tables. Note that there is a bug here  but thankfully there is an easy workaround.
  3. Further, we see that our connection (the IO thread) is ready for service (SERVICE_STATE: ON). 
Note that the service state shows one of (ON/OFF/CONNECTING):
  • ON: meaning ready to serve i.e. if there is an event that is executed on master, you can assume      that it will be read by the slave via this connection.
  • OFF: meaning the connection (IO thread) is not serving i.e. it is not ready to read from the master or killed.
  • CONNECTING: meaning the connection (IO thread)is not established yet but the slave is trying to connect.
It is important to note here that the names and semantics of thread_id and service_state is extended to all the status tables and they all mean exactly the same. Hence, going forward lets skip explaining these two columns in the following tables.

Lets now execute a couple of queries on the master server and see if we can get the set of received transactions on our slave server.

mysql>create table test.t(a int primary key); Query OK, 0 rows affected (0.61 sec)
mysql>insert into test.t values(1); Query OK, 1 row affected (0.06 sec)

Lets turn back to our slave server and see what the field "received_transaction_set" has.

mysql> select received_transaction_set from performance_schema.replication_connection_status\G
*************************** 1. row ***************************
RECEIVED_TRANSACTION_SET: 1766a057-10cd-11e3-b06a-0021cc72bfc3:1-4
1 row in set (0.00 sec)

Lets now cause an error in the connection (IO thread) and look at the error related fields in this table. To cause an error in the connection, we will provide a wrong password in our CHANGE MASTER TO command.


mysql>stop slave; Query OK, 0 rows affected (0.10 sec)mysql>change master to master_password='abcd'; Query OK, 0 rows affected, 2 warnings (0.29 sec)
mysql> start slave;Query OK, 0 rows affected (0.05 sec)


mysql> select last_error_number, last_error_message, last_error_timestamp from 
performance_schema.replication_connection_status\G
*************************** 1. row ***************************                   
  LAST_ERROR_NUMBER: 1045                                                         
  LAST_ERROR_MESSAGE: error connecting to master 'rpluser@127.0.0.1:13000' - retry-time: 40 retries: 2                                                           
LAST_ERROR_TIMESTAMP: 0000-00-00  
1 row in set (0.00 sec)


The names and semantics of the error related fields(number, message and timestamp) are again exactly same across all the tables, wherever applicable. Hence, going ahead, lets skip monitoring error related fields in the following tables.

Lets now clean-up the error we caused to move ahead and work with other tables.

mysql> stop slave; Query OK, 0 rows affected (0.06 sec)mysql> change master to master_password='secret'; Query OK, 0 rows affected, 2 warnings (0.25 sec)mysql> start slave; Query OK, 0 rows affected (0.08 sec)

mysql> select last_error_number, last_error_message, last_error_timestamp from 
performance_schema.replication_connection_status\G
*************************** 1. row ***************************                   
  LAST_ERROR_NUMBER: 0                                                         
  LAST_ERROR_MESSAGE:                                                           
LAST_ERROR_TIMESTAMP: 0000-00-00  
1 row in set (0.00 sec) 

Great! We are done with monitoring the connection specific parameters between a slave and its master. Lets now move to the other half of replication module- execution of events received from the master on the slave server.

REPLICATION_EXECUTE_CONFIGURATION/STATUS:

This table shows the configuration parameters that affect execution of transactions by the slave server. Parameters stored in the table can be changed with the CHANGE MASTER TO command. Lets setup a delayed replication now and see how the same can be read from the tables replication execute configuration.


mysql> stop slave; Query OK, 0 rows affected (0.11 sec)mysql> change master to master_delay=150; Query OK, 0 rows affected (0.29 sec)mysql> start slave; Query OK, 0 rows affected (0.06 sec)

mysql> select desired_delay from performance_schema.replication_execute_configuration\G
*************************** 1. row ***************************
DESIRED_DELAY: 150
1 row in set (0.00 sec)

Lets now execute an event at our master to see if the event is executed at the slave or not.

mysql> insert into test.t values(1); Query OK, 1 row affected (0.06 sec)

Lets move to slave and make sure our slave has not elapsed the 150 second delay yet.

mysql> select remaining_delay from performance_schema.replication_execute_status\G
*************************** 1. row ***************************
REMAINING_DELAY: 147
1 row in set (0.00 sec)

Now we should be able to see that although the insert(2) is received at slave it is not executed yet. The last time we saw our received_transaction_set (before insert(2)), it was 1766a057-10cd-11e3-b06a-0021cc72bfc3:1-4. So insert(2) should be assigned a GTID 1766a057-10cd-11e3-b06a-0021cc72bfc3:5.

mysql> select received_transaction_set from performance_schema.replication_connection_status\G
*************************** 1. row ***************************
RECEIVED_TRANSACTION_SET: 1766a057-10cd-11e3-b06a-0021cc72bfc3:5
1 row in set (0.00 sec)

Ok, we have received the event. Now lets see if this insert(2) with GTID 1766a057-10cd-11e3-b06a-0021cc72bfc3:5 is executed yet.

mysql> select @@global.gtid_executed\G
*************************** 1. row ***************************
@@global.gtid_executed: 1766a057-10cd-11e3-b06a-0021cc72bfc3:1-4
1 row in set (0.00 sec)

Lets now wait until, our delay is elapsed.

mysql> select remaining_delay from performance_schema.replication_execute_status\G
*************************** 1. row ***************************
REMAINING_DELAY: 0
1 row in set (0.00 sec)

And check if the insert(2) has been executed.

mysql> select @@global.gtid_executed\G
*************************** 1. row ***************************
@@global.gtid_executed: 1766a057-10cd-11e3-b06a-0021cc72bfc3:1-5
1 row in set (0.00 sec)

Executed. Great!

Before going ahead to have a look at the other goodies in store, lets revise a couple of things:
  • SQL THREAD: Executes the events received from the master at slave.
  • MULTI-THREADED SLAVE (MTS): With only one thread (SQL thread) reading and applying events that are applied by multiple clients concurrently on the master, the slave starts lagging behind the master. In this case, one can chose to opt for MTS. Simply put, we have a buffer (relaylog) on slave server that stores the events executed on the master server. The coordinator thread reads the relaylog and assigns these to worker threads which execute the events assigned to them parallely on the slave. The coordinator thread is the scheduler and the worker threads are responsible for executing the events.

REPLICATION_EXECUTE_STATUS_BY_COORDINATOR:

This table is used in two ways depending on whether the slave is operating with one applier (MTS disabled) or multiple appliers executing events in parallel(MTS enabled). When operating with one applier, this table reports the status of this applier. When multiple appliers, the same table reports the status of the scheduler (coordinator thread). Lets explore the single applier use case.

mysql> select * from performance_schema.replication_execute_status_by_coordinator\G
*************************** 1. row ***************************
           THREAD_ID: 13
       SERVICE_STATE: ON
   LAST_ERROR_NUMBER: 0
  LAST_ERROR_MESSAGE:
LAST_ERROR_TIMESTAMP: 0000-00-00 00:00:00
1 row in set (0.00 sec)

We see that the applier's (SQL thread) id is 13 and it is alive (SERVICE_STATE: ON). For now there are only two states that we show- ON/OFF. The semantics of error fields are exactly similar to the explanations earlier. Hence we skip them here.

The Multiple applier case (MTS enabled) is similar except that this table will show the scheduler's (coordinator) thread id. Hence we will skip the explanations and move to the next table. To read more about this table, please visit our official documentation for this table.

REPLICATION_EXECUTE_STATUS_BY_WORKER (Single Applier Case):

When the slave server is operating in the single applier mode, lets see what the table replication_execute_status_by_worker shows us. Conceptually, we don't have a scheduler and multiple appliers. so the table should be empty.

mysql> select * from performance_schema.replication_execute_status_by_worker\G
Empty set (0.00 sec)

And it is empty :)

REPLICATION_EXECUTE_STATUS_BY_WORKER (Multiple Appliers Case):

Lets now set up our slave to use multiple appliers (MTS enabled) and then see how we can monitor the replication status concerned with our scheduler and appliers (coordinator and worker threads). Lets call our multiple appliers "worker".

mysql> stop slave; Query OK, 0 rows affected (0.10 sec)
mysql> SET GLOBAL slave_parallel_workers=2; Query OK, 0 rows affected (0.00 sec)

Note that a START SLAVE is necessary to have the workers ready for action. Just setting slave_parallel_workers=2, doesn’t spawn the 2 workers.

mysql> start slave; Query OK, 0 rows affected, 1 warning (0.14 sec)

mysql> select * from performance_schema.replication_execute_status_by_worker\G
*************************** 1. row ***************************
            WORKER_ID: 0
            THREAD_ID: 16
        SERVICE_STATE: ON
LAST_SEEN_TRANSACTION:
    LAST_ERROR_NUMBER: 0
   LAST_ERROR_MESSAGE:
 LAST_ERROR_TIMESTAMP: 0000-00-00 00:00:00
*************************** 2. row ***************************
            WORKER_ID: 1
            THREAD_ID: 17
        SERVICE_STATE: ON
LAST_SEEN_TRANSACTION:
    LAST_ERROR_NUMBER: 0
   LAST_ERROR_MESSAGE:
 LAST_ERROR_TIMESTAMP: 0000-00-00 00:00:00
2 rows in set (0.00 sec)

So, we see that we have two rows to represent the two workers. The worker_id field here is same as the id field in slave_worker_info table, so you can again join the two tables to know more about a worker thread. The service_state(ON/OFF) has nothing new to add.
The interesting parts here are:
  1. You get the per worker error. So, if two of your workers have errored out in a group, you can identify both the errors as opposed to only one through SHOW SLAVE STATUS.
  2. last_seen_transaction is the new field we have added to help detect MTS failures better. This helps you find the GTID of all the transactions being executed by the all the workers at the moment the error happened. These values are preserved in case of an error and in the idle state of the worker after executing the transactions.
To read more about this table and field-wise descriptions, please visit our official documentation for this table.

CONCLUDING REMARKS:

The goal of this post was to help you familiarize with the Performance Schema tables relating to replication. Please try out this new interface for monitoring MySQL replication and let us know your feedback. To read more on these Performance Schema tables, you can visit the blog on multisource replication by Rith. These Performance Schema tables look really powerful with multisource replication. The motive behind this feature was to make it easier to monitor the health and performance of MySQL replication. We hope this new interface to monitor MySQL replication makes our user's life easier.

Finally a "software developer" !

It was the summer of 2007. I was a a class X student whose only interaction with a computer had been having played Mario once kind of 5 years ago. I was offered to choose between one of biology and computer science. Mathematics or Hindi Language being the other choice I had to make. Though I used to write poems, stories, give lecture in Hindi (believe me, I was quite famous in school for these), Mathematics was my darling (Alas, this changed at college!) and it was easy to chose Mathematics. The choice between Biology and Computer science was a difficult one and it ended up in the favor of computer science just because I was terrible at drawing a heart or a kidney. Some of my friends would remember that I took 3 hours to draw a heart in my biology class ;)

So I ended up being a computer science geek and thankfully so, for I am thoroughly enjoying the experience every single day. The next two years the only interaction I had with a computer was the blue turboC screen, yes the horrible old compiler but I have very fond memories of it, so I still don't call it stupid :) The OOPs concepts two years later was better than it is today, thanks to Nancy Madam. Ma'm, if you are reading this, you deserve a big thanks. And the choice of branch when I got into engineering was a no brainer.

Thanks to all those, whose names appear in the acknowledgement section of this blog and more, I am a proud open source contributor working for the most popular database on web- MySQL. I am a part of MySQL replication development team and working with these guys here is a looooooot of fun. Being a part of MySQL Replication for an year, I feel the best part has been the amount of learning that has come talking to the MySQLers, not to forget the NCGs 2012 (Well, we are a bunch of people, new college grads who joined MySQL in July 2012). NCGs you rock \o/.

Lets now return to the title and motivation for this post. It was a dream since 2007 when I had no interaction with computers- to develop a lot of features, to contribute to the this golden age of technology as much as I can. And the first tiny (well, tiny in terms of years of contributing to software development which I aim at) step into this world, my first design and implementation for a MySQL replication feature is now released. And while people check out the blogs on this feature, browse the source I have written, I will sit and enjoy motivating myself to do a lot more into this huge IT world. I am a software developer by choice, nothing very very big as of now, but I am confident I will make it really really big one day. For now, for the first time in my life, I feel I have become a software developer and its time to start on the journey.

And finally some advertisement :D. Please check out:

  1. My blog about this feature

  2. The official documentation

  3. Download mysql-5.7.2, try it out & let us know your feedback and

  4. The source code too, if you feel interested enough :)


[UPDATE]:

My second blog on this feature- http://shivjijha.blogspot.com/2013/09/Monitoring-Replication-with-the-NEW-performance-schema-tables.html

Enjoy!

Saturday, September 21, 2013

MySQL 5.7: Introducing the Performance Schema tables to monitor Replication


MySQL-5.6 was our best release ever and we are happy to see people praising it. This motivates us to work even harder for our next release. MySQL-5.7.2 DMR is out and we have already got a number of MySQL replication features. Below is a list of these features:

    - mysqlbinlog idempotent mode
    - mysqlbinlog --rewrite-db option
    - Dump thread does not take binary log lock
    - Lossless semisync
    - intra-schema multi-threaded slave
    - Performance Schema tables for replication monitoring (this post :) )

We want to make MySQL-5.7 huge and these are tiny steps towards the same.

This post introduces the Performance Schema tables to monitor MySQL replication. You can find the official documentation for the same here. This post gives a brief overview of these Performance Schema tables in an attempt to prepare you to dive deeper into the details. Please follow my second blog post on this topic to know the details on the individual tables.

Why Performance Schema Tables:

Replication is a delicate module of MySQL and people want to know its status frequently. To monitor the MySQL replication health, we have been using the SHOW SLAVE STATUS command for long. But replication is growing fast and this static command is not able to match up to people's expectations. SHOW SLAVE STATUS does not scale in the sense that there are multiple parts of the slave server: receiver part, applier part, intermediate queues, etc, in cases, multiple instances of each part. It has 54 fields, as of now, interleaving different information together. It has now reached such a point where we foresee that not having an SQL interface to query exactly what is required from the replication status would make monitoring tedious. So, we decided to have tables to monitor replication and we have put all our tables in the performance_schema database.

The motivation behind having tables is:

  • To make it easier to access exactly what is required, through an SQL interface,
  • Pieces of data can be assigned to variables and thus used in stored procedures etc,
  • Easier testing with SELECT item from Performance Schema tables,
  • Split the logically unrelated information into different tables,
  • Cross-reference monitoring data seamlessly by joining with other Performance Schema tables, Information_Schema tables etc,
  • Easier to extend and
  • More flexibility to accommodate a lot of replication information but still be organized and easy to use.

Additionally, we noted that SHOW SLAVE STATUS used a lot of technical jargons(words like IO, SQL, Relay_log etc). In order to make it easier to monitor replication, we decided to hide these implementation specific details so that it is easier to understand the names. We have tried our best to make it convenient for everyone to understand the names of the tables and the fields.

Why 6 tables? What does each stand for:

The idea is to come up with a better organized and an easy to extend interface. To start with, we have split the information under SHOW SLAVE STATUS into different parts based on:

  1. Connection information or execute information
  2. In each of (1), we further have configuration and status related fields put into different tables.

Based on the above classifications, we have got four tables:

    a)    replication_connection_configuration,
    b)    replication_connection_status,
    c)    replication_execute_configuration and
    d)    replication_execute_status

Note that all replication applier module status information under (d) would become confusing again and it makes more sense to have them split based on overall stats, coordinator's status or worker's status. So, we have two more tables namely,

    e)    replication_execute_status_by_coordinator and
    f)     replication_execute_status_by_worker.

Note that (d) is responsible for showing the overall status of the applier module in replication, (e) relates to the coordinator thread and (f) refers to the worker thread.

See the tree diagram below for the basis of division of data into different tables as discussed above:


To make it easier to select a table when you have a configuration/status parameter in mind, just ask yourself the following questions:

  • Is it relating to the  connection between the slave and its master?
  • If yes, you have narrowed down your scope to only (a) and (b).
  • If not, the others (c, d, e or f).
  • Suppose, the data you are looking for is relating to the connection (not status), now just ask yourself if it is a configuration parameter or relating to the status of connection between slave and its master. And there you are- you know which table to look at.
  • If the data you are looking for is relating to the execution of events received at your slave (c, d, e, f) are the tables you have. Now ask yourself the same question. Is this data you need relating to a configuration parameter (c)or relating to the status of execution of events at the slave(d, e or f).

For those who know the internals and have been using SHOW SLAVE STATUS, the names might look new and it could take a little time to get used to them. So, lets now see how these tables relate to the different replication threads. If you are not familiar with the threads and buffers, you don't really need to understand them. This new replication monitoring interface is designed to make sure you don't have to and hence you can skip this section. If you are familiar with the replication threads and want to understand the tables in terms of threads, you can use the table below to map these tables to the replication thread you want to monitor. But before we move ahead lets revise a couple of things:

  • IO THREAD: Responsible for the connection between master and slave, also gets queries   executed on the master onto the slave.
  • SQL THREAD: Executes the events received from the master at slave.
  • MULTI-THREADED SLAVE (MTS): With only one thread (SQL thread) reading and applying events that are applied by multiple clients concurrently on the master, the slave starts lagging behind the master. In this case, one can chose to opt for MTS. Simply put, we have a buffer (relaylog) on slave server that stores the events executed on the master server. The coordinator thread reads the relaylog and assigns these to worker threads which execute the events assigned to them parallely on the slave. The coordinator thread is the scheduler and the worker threads are responsible for executing the events.

With the background set, lets now look at the table below to understand the mapping between the Performance Schema tables and the replication threads they monitor.













To end with, it may interest you to note that these Performance Schema tables not only give you an easier way to monitor replication but also allow you to easily obtain all the information available about replication threads and coordinates through a join with the other Performance Schema tables, Information Schema tables, mysql.slave_worker_info etc.

Go check it out and let us know if it allows you to know more about the replication status. We want to have your valuable feedback to improve this and add a lot more information to this interface.

Want to read more and explore the fields, how-to, what fields etc ? Here is the deep-dive in the next post :) Enjoy!

Tuesday, September 17, 2013

z-algorithm for pattern matching

String algorithms are a traditional area of study in computer science and there is a wide variety of standard algorithms available. The more algorithms you know, the more easier it gets to work with them :) As the title of the post says, we will try to explore the z-algorithm today. Lets first formulate the problem statement and a couple of definitions. To start with lets look at the below mentioned question (from interviewstreet):

QUESTION

For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings “abc” and “abd” is 2, while the similarity of strings “aaa” and “aaab” is 3.

Calculate the sum of similarities of a string S with each of it’s suffixes.

Sample Input:
2
ababaa
aa

Sample Output:
11
3

Explanation:
For the first case, the suffixes of the string are “ababaa”, “babaa”, “abaa”, “baa”, “aa” and “a”. The similarities of each of these strings with the string “ababaa” are 6,0,3,0,1,1 respectively. Thus the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.

For the second case, the answer is 2 + 1 = 3.

SOLUTION 1:

The most intuitive way (brute force)  to solve this problem is simple, take out every suffix of the given string and match it with the given string to find the number of matching characters.Now add all such numbers for every suffix and there you have it solved.

[sourcecode language="cpp"]
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
long long similarity(string s, int k){
long long i;
for(i=0;k+i<s.size();i++){
if(s[i]!=s[k+i]) break;
}
return i;
}

int main() {
string s; long long sum;
getline(cin,s);
sum=s.size();
for(long long i=1;i<s.size();i++){
sum+=similarity(s,i);
}
cout<<sum<<endl;
return 0;
}

[/sourcecode]

But this is costly as we are not using one result to calculate the next one.  So we are throwing away some valuable info and calculating things from scratch everytime. If you try the above solution, it will get you a TLE (time limit exceeded). To get this in time, we need to come up with a better algorithm. Lets discuss this better algorithm to solve this- the Z-algorithm.  The z-algorithm gives you a Z-array which is exactly what we need in this question to sum up and print the answer- The similarity of each suffix to the prefix. A tutorial for the z-algorithm can be found in video at:

  1. http://www.youtube.com/watch?v=MFK0WYeVEag   and

  2. http://www.youtube.com/watch?v=NVJ_ELSbbew


The algorithm is explained quite nicely in these videos.

SOLUTION 2:

 Once you understand the z-algorithm, its easy to guess that the solution to this question is nothing but sum of all the z values. Lets see the code now:

[sourcecode language="cpp"]

#include <string>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

long long compute_z(string s){
long long sum=0;
int n = s.length();
vector<int> z(n,0);

long long L = 0, R = 0;
for (long long i = 1; i < n; i++) {
if (i > R) {
L = R = i;
while (R < n && s[R-L] == s[R]) R++;
z[i] = R-L; R--;
}

else {

int k = i-L;
if (z[k] < R-i+1) z[i] = z[k];
else {
L = i;
while (R < n && s[R-L] == s[R]) R++;
z[i] = R-L; R--;
}
}
sum+=z[i];
}
return sum;
}

int main() {
int t; string s; long long sum;
cin>>t;getchar();
while(t--){
getline(cin,s);
cout<<compute_z(s)+s.size()<<endl;
}
return 0;
}

[/sourcecode]

And yes this code is accepted :)

In case you didn't notice yet,

  • Z-algorithms can be used to find a given pattern (P) in a given text (T) in linear time. To do the same,  you need to pass the string(P+S) to the function compute_z(). If you have a z-value>=pattern at an index 'i' . the pattern exists in the text at that index 'i'.  So, the z-algorithm helps you find all occurances of of pattern in the text.

  • Another advantage of Z-algorithm is that though KMP has same time complexity as Z-Algorithm, Z-algorithm is a lot more easy to understand, remember and code :)

Tuesday, September 10, 2013

Hello World...

Hello,

I am Shivji Kumar Jha (shiv), a graduate from BIT Mesra who fell in love with MySQL sometime ago. I am one of those lucky ones who got to work at MySQL as well and I thoroughly enjoy the experience every single day. I believe this is the golden age of technology and I aim to  contribute my bit to it affecting millions of people through an open source software – the most popular open source database on web – MySQL ! At MySQL I am currently working as a software developer with the replication team, which provides high-availability solution built into MySQL server. My area of expertise revolves around analyzing and enhancing performance Database replicas, enhancing the replication monitoring tools. This blog is an attempt to reach out to people and share the tiny details I know about MySQL Replication. The views expressed on this blog are my own and do NOT necessarily reflect the views of Oracle Corporation. 


I do not claim that all information available on this blog is perfectly correct. So, if you find something that is wrongly published, please let me know of the same. Also, in case of doubts please use the comments section of this blog. Together lets talk MySQL Replication :)