Sharding and IDs

Posted on August 6, 2018  •  2 minutes  • 354 words

So I was going through this post from Instagram Engineering blog while researching for some sharding solutions.

The solution is quite elegant and I decided to port this to MySQL.

Turns out, it’s harder than I thought since we’re using a pretty dated MySQL version at work. There is no sequence, just AUTO_INCREMENTAL. In order to use the code snippet for PL/PGSQL, I would have to find a way to mimic nextval function.

CREATE TABLE `sequence` (
    `name` VARCHAR(100) NOT NULL,
    `increment` INT(11) NOT NULL DEFAULT 1,
    `min_value` INT(11) NOT NULL DEFAULT 1,
    `max_value` BIGINT(20) NOT NULL DEFAULT 9223372036854775807,
    `cur_value` BIGINT(20) DEFAULT 1,
    `cycle` BOOLEAN NOT NULL DEFAULT FALSE,
    PRIMARY KEY (`name`)
) ENGINE=MyISAM;

INSERT INTO sequence
    ( NAME, increment, min_value, max_value, cur_value )
VALUES
    ('my_sequence', 1, 0, 100, 0);


DROP FUNCTION IF EXISTS nextval;
DELIMITER $$
CREATE FUNCTION `nextval` (`seq_name` VARCHAR(100))
RETURNS BIGINT NOT DETERMINISTIC
BEGIN
    DECLARE cur_val BIGINT;

    SELECT
        cur_value INTO cur_val
    FROM
        sequence
    WHERE
        NAME = seq_name;

    IF cur_val IS NOT NULL THEN
        UPDATE
            sequence
        SET
            cur_value = IF (
                (cur_value + increment) > max_value OR (cur_value + increment) < min_value,
                IF (
                    cycle = TRUE,
                    IF (
                        (cur_value + increment) > max_value,
                        min_value,
                        max_value
                    ),
                    NULL
                ),
                cur_value + increment
            )
        WHERE
            NAME = seq_name;
    END IF;
    RETURN cur_val;
END;
$$

So the snippet above is what we use to mimic the nextval function. Quite troublesome huh? you can now call SELECT nextval('my_sequence') if you want to get next val of the sequence .

Now, onto the generating id function. It’s a pretty straight forward port from PL/PGSQL version.

DROP FUNCTION IF EXISTS f_unique_id;
DELIMITER $$
CREATE FUNCTION f_unique_id() RETURNS BIGINT
BEGIN
    DECLARE our_epoch BIGINT;
    DECLARE seq_id BIGINT;
    DECLARE now_millis BIGINT;
    DECLARE shard_id INT;
    DECLARE result BIGINT;

    SET our_epoch = 1314220021721;
    SET shard_id = 5;

    SELECT nextval('my_sequence') % 1024 INTO seq_id;
    SELECT UNIX_TIMESTAMP() INTO now_millis;
    SET result = (now_millis - our_epoch) << 23;
    SET result = result | (shard_id << 10);
    SET result = result | (seq_id);

    RETURN result;
END;
$$
DELIMITER ;

In order to generate an unique id with sharding info, you can do just this select f_unique_id()