The practice of consistent Hash algorithm in database sub-tables

has a project recently, in which a certain function single-table data reaches 100 million in the predictable future, and the initial estimate is about 9 billion. After a detailed discussion with colleagues, it was decided to use the consistent hash algorithm to complete the automatic expansion and data migration of the database. The details of the whole process were completed by my colleagues. I just understood and documented them for reference by peers with the same questions.

See the brother of this article, by default you are already familiar with the consistency hash algorithm. This article only elaborates on the code details. The implementation language is Java

项目背景

  1. The project is a laboratory project
  2. . There is a table called the test table, which is used to store the test data of the model. There are 6,000 data
  3. in the beginning, there are about 20,000 models, and each model contains more than 50 tests at the beginning. In the later period, the data in the test table will be dynamically increased.
  4. The data in the test table only needs to be taken out according to the model test ID. There is no other more complicated business logic

计划决定

The project is officially launched, the data volume is not It will directly expand to 9 billion, which requires accumulation of time (gradual experimentation), and may eventually reach 9 billion data, or even more than 9 billion data.

According to our actual situation, when the amount of oracle storage data reaches 10 million, the performance is good. Oracle officially said that if a single table storage 1g has a partition (approximately 5 million data), the query efficiency is very high. There are only four fields in the test table, and the amount of data per data is small. So we finally decided to open the table horizontally with 10 million nodes. When the table data reaches 10 million, the next wave table is added. Automatic data migration.

According to the total amount of 9 billion, the division of 10 million data in one table will eventually produce about 900 tables. So we ended up using 4 databases. One table for storing other business modules, and three for storing this big data table. There are roughly 300 tables per database. Both performance and quantity can meet our requirements.

相关表结构

试验信息表(EXPERIMENT_MESSAGE), the relationship between the model and the test. Test data table (EXPERIMENT_DATA), store test data

试验信息 table:

意思
ID 主键, use UUID to generate
EXPERIMENT_ID ID in the test table
CAR_ID ID
... in the model table, the remaining dozens of fields are omitted

试验数据表:

meaning
ID 主键, using UUID to generate experimental information corresponding to
EXPERIMENT_MESSAGE_ID Id
X_VALUE 试验数据X值
Y_VALUE 试验数据Y值

We use the key for consistency hash, which is the EXPERIMENT_MESSAGE_ID field in the test data table. That is to say, each test data table does not exist, and there are roughly 6,000 pieces of data at a time. Take the same reason. The

consistency Hash algorithm implements the hash part of the

consistency hash algorithm, using the famous ketama algorithm. Here, we will not discuss the details of the ketama algorithm. If you are interested, please check the ketama algorithm

    public long hash(String key) {
        if (md5 == null) {
            try {
                md5 = MessageDigest.getInstance("MD5");
            } catch (NoSuchAlgorithmException e) {
                throw new IllegalStateException("no md5 algorythm found");
            }
        }

        md5.reset();
        md5.update(key.getBytes());
        byte[] bKey = md5.digest();

        long res = ((long) (bKey[3] & 0xFF) << 24) | 
                         ((long) (bKey[2] & 0xFF) << 16) | 
                         ((long) (bKey[1] & 0xFF) << 8) | 
                         (long) (bKey[0] & 0xFF);
        return res & 0xffffffffL;
    }

with the Hash algorithm, and then construct the Hash ring. The Hash ring is implemented by the SortedMap data structure.

private final SortedMap<Long, T> circle = new TreeMap<Long, T>();

The node is added and the node is removed. The location of the node on the ring needs to be obtained according to the hash algorithm. The specific code is as follows:

/**
     * Add virtual node
     * numberOfReplicas is the number of virtual nodes. When the hash ring is initialized, we use 300 virtual nodes.
     * @param node
     */
    Public void add(T node) {
        For (int i = 0; i < numberOfReplicas; i++) {
            Circle.put(hashFunction.hash(node.toString() + i), node);
        }
    }

    /**
     * Remove node
     * @param node
     */
    Public void remove(T node) {
        For (int i = 0; i < numberOfReplicas; i++) {
            Circle.remove(hashFunction.hash(node.toString() + i));
        }
    }

and the node part of the hash ring is special. According to the introduction of the consistent hash algorithm, the node in the hash ring is obtained, which is actually the first node that the calculated hash value is found clockwise.

/**
     * Get a recent clockwise node
     * @param key takes the hash for the given key and gets the actual node corresponding to the nearest virtual node in the clockwise direction.
     * @return
     */
    Public T get(Object key) {
        If (circle.isEmpty()) {
            Return null;
        }
        Long hash = hashFunction.hash((String) key);
        If (!circle.containsKey(hash)) {
            / / Returns a partial view of this map, its key is greater than or equal to the hash
            SortedMap<Long, T> tailMap = circle.tailMap(hash);
            Hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        Return circle.get(hash);
    }

Single table split practice

completed the implementation of the consistent hash algorithm, including the implementation of the hash algorithm and hash loop. Next, we need to deal with the specific business, how to use this hash ring and algorithm.

In our business, we mainly operate the data of this table, that is, add and delete. Then our database is split into three, so the operations that need to be added and deleted are basically the same. First, the library is obtained through the consistency hash, and then the table is obtained through the consistency hash.

The operation of obtaining the database name is as follows. After obtaining the database, the connection is obtained according to the database name to the corresponding connection pool.

/**
     * Get the name of the library in which it is based on the test information id
     * DatabaseType is an enumeration of our data
     * @return name of the database
     **/
    Private String getDataBase(String experimentMessageId) {
        / / Get the data source
        DatabaseType[] databasetype = DatabaseType.values();
        List<String> dataBaselist = new ArrayList<>();
        Map<String, DatabaseType> map = new HashMap<>();

        For (DatabaseType d:databasetype) {
            If (!d.equals(DatabaseType.KC)) {
                dataBaselist.add(d.toString());
                Map.put(d.toString(), d);
            }
        }
        / / Get the data source hash
        ConsistentHash<String> dataBaseCon = getConsistentHash(dataBaselist);

        / / Get the data source of the id
        String dataBase = dataBaseCon.get(experimentMessageId);
        Return dataBase;
    }

The operation of obtaining the table name is as follows. After obtaining the database, find the required table in the corresponding database, and then query the data from the table.

/**
     * Obtain the table of test data based on the test information id
     * @return
     **/
    Public String getTableName(String experimentMessageId) {
        String dataBase = getDataBase(experimentMessageId);
        / / Query all test data sheets
        List<String> tables = experimentDataEODao.queryTbaleNames(dataBase, tableName);
        ConsistentHash<String> consistentHash = getConsistentHash(tables);
        String tableName = consistentHash.get(experimentMessageId);
        Return tableName;
    }

The rest of the additions, deletions, and changes are consistent and unanimous.

Data Migration Practice

Consistency hash is bound to involve data migration. The data migration method we adopt is a timed task, which is scanned once a day for each database. Check if there is a table with more than 10 million data. If there is such a table, double the number of existing tables. Data migration will only be migrated between the same libraries and will not involve cross-database situations. This program is a preliminary plan, and the subsequent improvements will be more intelligent, adding different numbers of tables according to the number of tables. Rather than simply doubling the number of tables. After the table is created, the table data that needs to be migrated is migrated one by one.

After connecting to the data source, we did the following things for data migration. 1. Get all the tables in the library

 List<String> tables = getTables(connection, p, d.toString());

2. Traverse the table, check if the data in the table exceeds the boundary line (we are 10 million)

for (int i = 0; i < tables.size(); i++) {
    / / Query the amount of data in the table
    Int num = countByTableName(connection, p, tables.get(i));
    //finalNum is the boundary value, here 10 million
    If (num > finalNum) {
        ......
    }
    ......
}

3. Calculate the existing virtual node

ConsistentHash<String> consistentHashOld = getConsistentHash(tables);

4 according to all the tables. Double the table

List<String> tablesNew = deepCopy(tables); //Be sure to use deep copy
Int tableSize = tablesNew.size();
For (int y = 0; y < tableSize; y++) {
    String tableNameNew = tableName + (tablesNew.size() + 1);
    / / Create a table
    createTable(connection, p, d.toString(), tableNameNew);
    tablesNew.add(tableNameNew);
    tableDelete.add(tableNameNew);
}

5. Calculate the virtual node

ConsistentHash<String> consistentHashNew = getConsistentHash(tablesNew);

6. Data migration

for (int z = 0; z < tableSize; z++) {
    String tableNameOld = tablesNew.get(z);
    / / Query test information id does not repeat the test data information
    List<String> disData = selectExperimentIdDis(connection, p, tableNameOld);
    List<String> deleteList = new LinkedList<>();
    For (String experimentId : disData) {
        //If the data hash calculation is inconsistent with the new table, perform the transfer
        If (!consistentHashNew.get(experimentId).equals(consistentHashOld.get(experimentId))) {

            //Add to new table data
            insertHash(connection, p, experimentId, consistentHashOld.get(experimentId),
            consistentHashNew.get(experimentId));

            / / Delete the data collection
            deleteList.add(experimentId);
            / / Delete old table data
            Final int defaultDelNum = 1000;
            If (deleteList.size() == defaultDelNum) {
                deleteInbatch(connection, p, deleteList, tableNameOld);
                deleteList.clear();
            }
        }
    }

    / / Delete old table data
    If (deleteList.size() > 0) {
        deleteInbatch(connection, p, deleteList, tableNameOld);
    }
}

summary

The above is the consistent hash practice we have done, there are still many problems, such as the single thread of the migration process leads to slow migration, the automatic expansion mechanism is not intelligent, and the data access is unstable during the migration process. Waiting for the situation.

We will gradually improve and improve in the subsequent development.

The above is our practice for consistent hash in the Oracle sub-table

参考