10

I'm stuck in a concurrency problem.

Is a typical problem where the user sends 2 o 3 transactions to persists some data that SHOULD NOT BE duplicated in the DB, in case of a duplicate record you should return an error.

This problem is easy when you can just add an index (unique) to a column where you store a hash.

But in this case, I have a huge table (probably millions of records) and I can't just modify the table.

In fact, we have a column where we store a hash of the data that should not be duplicated but a unique index was not set .

I'm trying on my java code to check if exists just before the flush, still getting duplicates.

My possible solutions for this are:

  • Create a trigger that checks if the hash that I'm trying to inserts already exists on the table.
  • Create another table to store unique indexes for this table and add a foreign key to the main table.
  • Sit on fetal position and cry
  • Is your check of the hash failing because of hash collisions or a bug in the check? – candied_orange Dec 13 '17 at 23:44
  • 4
    I didn't get your question. So instead of indexing once for all your huge table with millions of records, you prefer to read for each of the next million of records that you will add, the existing millions to look for doubles ? or duplicate some information and add joins to make your check ? – Christophe Dec 13 '17 at 23:45
  • The problem is , for making this change I've been warned that we need a lot of space and a long downtime for our service, in order to acomplish some requirements our service can't be down for more than 2 hours monthly . I know the best way is to perform a maintance on this table, but is something I can't do at this moment, so we need a workaround. – rafuru Dec 13 '17 at 23:56
  • 4
    I don't get it - why does adding a trigger or adding another table for "emulating" an index take less downtime than just adding an index to the existing table? – Doc Brown Dec 14 '17 at 7:24
  • 2
    @rafuru: who said you need to create a unique index? A standard, non-unique index will probably all you need to quickly find all rows with the same hash value. – Doc Brown Dec 14 '17 at 21:31
3

There are a couple of possible scenarios which are easy to solve, and a pernicious one that isn't.

For a user that enters a value, then enters the same value some time later a simple SELECT before the INSERT will detect the problem. This works for the case where one user submits a value and some time later another user submits the same value.

If the user submits a list of values with duplicates - say {ABC, DEF, ABC} - in a single invocation of the code the application can detect and filter the duplicates, perhaps throwing an error. You'll also need to check the DB does not contain any of the unique values before the insert.

The tricky scenario is when one user's write is inside the DBMS at the same time as another user's write, and they're writing the same value. Then you have a race a condition between them. Since the DBMS is (most likely - you don't say which one you're using) a preemptive multitasking system any task can be paused at any point in its execution. That means user1's task can check there's no existing row, then user2's task can check there's no existing row, then user1's task can insert that row, then user2's task can insert that row. At each point the tasks are individually happy they're doing the right thing. Globally an error occurs, however.

Ordinarily a DBMS would handle this by putting a lock on the value in question. In this problem you're creating a new row so there is not yet anything to lock. The answer is a range lock. As it suggests this locks a range of values, whether they currently exist or not. Once locked that range cannot be accessed by another task until the lock is released. To get range locks you have to specify and isolation level of SERIALIZABLE. The phenomenon of another task sneaking in a row after your task has checked is knows as phantom records.

Setting the isolation level to Serializable across the whole application will have implications. Throughput will be reduced. Other race conditions which worked well enough in the past may start to show errors now. I would suggest setting it on the connection which executes your duplicate-inducing code and leaving the remainder of the application as is.

A code-based alternative is to check after the write rather than before. So do the INSERT, then count the number of rows that have that hash value. If there are duplicates rollback the action. This can have some perverse outcomes. Say task 1 writes then task 2. Then task 1 checks and finds a duplicate. It rolls back even though it was first. Similarly both tasks may detect the duplicate and both rollback. But at least you'll have a message to work with, a retry mechanism and no new duplicates. Rollbacks are frowned on, much like using exceptions to control program flow. Note well that all work in the transaction will be rolled back, not just the duplicate-inducing write. And you'll have to have explicit transactions which may reduce concurrency. The duplicate check will be horribly slow unless you have an index on the hash. If you do you may as well make it a unique one!

As you have commented the real solution is a unique index. It seems to me like this should fit into your maintenance window (though of course you know your system best). Say the hash is eight bytes. For one hundred million rows that's about 1GB. Experience suggests a reasonable bit of hardware would process these many rows in a minute or two, tops. Duplicate checking and elimination will add to this, but can be scripted in advance. This is just an aside, though.

2

In fact, we have a column where we store a hash of the data that should not be duplicated but a unique index was not set.

Checking hash collisions is a good first step, but beware, you cannot guarantee the same program will produce the same hash on the same data if it is restarted. Many "fast" hash functions use an inbuilt prng which is seeded at program start time. Use a cryptographic hash if the hash needs to always be the same no matter what, as you do in this application. Note you don't need a good or secure cryptographic hash.

The second step is to actually check data equality, since even the best hash functions will sometimes result in collisions, since you are (usually) reducing the entropy of your data.

So:

Step 1: check if you get a collision on a cryptographic hash

Step 2: if the hashes match, check the actual data is the same

  • I fail to see how this answers the question. Let's assume for a moment the available hash column is filled by a deterministic hash function (otherwise any attempt to utilize it would make no sense). To my understanding, the problem is there is no index on that hash column in the database, so even the first step in your answer - checking if there is a collision - would still require a full table scan for each new record on a table with several million records, which will probably become way too slow. – Doc Brown Dec 14 '17 at 16:10
  • It is the best you can do without creating an index, which is what the question was asking. A hash scan at least means you only have to check one column, which is much faster than checking however many columns they would otherwise have to check. – Turksarama Dec 14 '17 at 22:06
  • I am pretty sure, even when creating an index is not possible (which in this case probably is), the OPs original suggestion to "create another table to store unique indexes for this table and add a foreign key to the main table" makes much more sense. – Doc Brown Dec 14 '17 at 22:18
  • Deterministic hash and cryptographic hash are two orthogonal concepts are they not ? a cryptographic hash may not be deterministic and vice-versa a deterministic hash could very well not be of cryptographic strength. – Newtopian Jan 23 '18 at 22:54
  • They're not the same thing, but they aren't orthogonal either. Cryptographic hashes are a subset of deterministic hashes, but nobody really bothers making non cryptographic deterministic hashes unless you specifically want it to be reversible for some reason. – Turksarama Jan 25 '18 at 0:37
2

Make a new table with a unique primary key

On the client side start generating GUIDs for each record so you can detect simple resends.

Put new records into the new table so at least you are good for new data coming in.

Have a column in the new table "CheckedAgainstOldData"

Have a backend task which does whatever you current slow hash check is to see if it can find a duplicate in the old data and set the flag accordingly, reject duplicates at this point, Sending a notification back to the client.

Meanwhile have another backend task which moves data from the old to the new table, checking for duplicates with your hash check and generating the GUID.

You can leave this task running for several days (if required), transferring the data across with no downtime.

Once the transfer is complete you can switch off the slow "CheckedAgainstOldData" process. and transfer all the data to a single table.

Frankly though if the problem is as bad as you describe and the software is old, then you are going to have thousands of duplicates.

1

Assuming that the data coming from the "user" means someone sitting at a keyboard and that the dupes arise from two users entering the same data at the same moment. Try adding in a function that causes a random delay at the start of the trigger. Give it a minimum of however long it takes to write a new record to the table and probably a maximum of no more than a nanocentury or so. That way when you get dupe requests the first one should be done and the existence trigger should kick back the correct result. (Clarification: each call should have its own unique random delay time, along the same principals as the ALOHA protocol)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.