DynamoDBでデータの順序管理に双方向リスト構造を使ってみた

はじめに

CX事業本部の佐藤智樹です。

今回の記事は、フロントエンドとDynamoDBで順序構造を同期する際に双方向リストを使えば処理を減らせるかと思ったので記事にしました。 またDynamoDBでマスタ管理をしている場合に、任意の順序を持たせる方法で悩んだ方にも一例として参考になるかと思います。

考えた発端

例えばバックエンドがサーバーレスでフロントエンドをSPAで作成している場合に、以下のサイトの「KANBAN DEMO」のようにマスタデータを上下に入れ替えれる実装をしたいとします。

DB側で任意の順序を管理する簡単な方法としては、連番の属性を作って管理することが考えられます。データの順序を更新する場合は、全データの連番用属性を更新するパターンです。ただこのパターンは、カードの移動に合わせてリアルタイムにサーバーと通信する場合だと全てのデータの連番用属性を毎回修正する必要があります。

これはデータが1000件、10000件と更新データが多くなると比例して処理回数が増えるのでいずれ処理が遅延しないか気になります。

そこで双方向リスト構造を持たせればデータの更新回数を減らせないかと考えました。次章以降は、実際のデータ構成と試してみた簡単な実装について紹介します。

データ構成

データの1レコードには双方向リストを作るため最低限以下の構成を持たせます。

項目	概要
id	属性を一意に識別するid
prev	1つ前のデータのidを記録する属性
next	次のデータのidを記録する属性
value	マスタデータ

上記の構成にすれば、基本的にデータ構造でいう双方向リストと同じになるので削除や更新の処理が少なくなります。例えばデータを別の位置に挿入する場合は、元のデータとその前後にあるデータ、移動後位置の前後のデータだけ更新すれば良いので最大5レコードの更新だけで済みます。削除する場合も元データと前後のデータだけ更新すれば良いので最大3レコードで済みます。

データ量がどれだけ増えても上記の動きは変わらないので、マスタが大量にある場合の順序変更でも対応できます。

AWSのコンソールで見ると以下のようなデータになります。idは今回実装が画面に収まるように「AAA」,「BBB」などにしていますが本来はuuidなど重複しない値にすると良いです。

実装

実際に上記のデータ構造のレコードをDynamoDBに作成してJavaScriptを使って更新処理をかけて順序が変わることを確認します。 「MASTER_SAMPLE」というテーブルをハッシュキーがidで作成してから下記のコードを試してみます。

const AWS = require('aws-sdk');
AWS.config.update({region: 'ap-northeast-1'});

const DOC_CLIENT = new AWS.DynamoDB.DocumentClient({apiVersion: '2012-08-10'});
const MASTER_TABLE_NAME = 'MASTER_SAMPLE';
const TABLE_PARAMS = {
    TableName: MASTER_TABLE_NAME,
}

const main = async() =>{
    // 変更前データ
    const beforeItems = [
        {'id' :'AAA','prev' :'','next' :'BBB', 'value':'SAP'},
        {'id' : 'BBB','prev' :'AAA','next' :'CCC', 'value':'DOP'},
        {'id' :'CCC','prev' :'BBB','next' :'DDD','value':'SAA'},
        {'id' :'DDD','prev' :'CCC','next' :'EEE','value':'SOA'},
        {'id' :'EEE','prev' :'DDD','next' :'FFF','value':'DVA'},
        {'id' :'FFF','prev' :'EEE','next' :'GGG','value':'SCS'},
    ]

    // データ投入
    await Promise.all(
        beforeItems.map(async (elm) => {
            const params = {
                TableName: MASTER_TABLE_NAME,
                Item: elm
            };
            await DOC_CLIENT.put(params).promise();
        })
    );

    // 変更前
    const beforeData = await DOC_CLIENT.scan(TABLE_PARAMS, () => {}).promise();
    const beforeResolve = await BidirectionalLinkedListDescribe(beforeData);
    console.log(beforeResolve);

    const changeItems =[
        {'id' : 'AAA','prev': '','next': 'CCC', 'value': 'SAP'},
        {'id' : 'BBB','prev': 'CCC','next': 'DDD', 'value': 'DOP'},
        {'id' : 'CCC','prev': 'AAA','next': 'BBB', 'value': 'SAA'},
        {'id' :'DDD','prev' :'DDD','next' :'EEE','value':'SOA'},
    ]

    //データ変更
    await Promise.all(
        changeItems.map(async (elm) => {
            var params = {
                TableName: MASTER_TABLE_NAME,
                Item: elm
            };
            await DOC_CLIENT.put(params).promise();
        })
    );

    // 変更後
    const afterData = await DOC_CLIENT.scan(TABLE_PARAMS, () => {}).promise();
    const afterResolve = await BidirectionalLinkedListDescribe(afterData);
    console.log(afterResolve);
}

/**
 * 双方向リストを表示するメソッド
 * @param  bidirectionalLinkedListData
 */

const BidirectionalLinkedListDescribe = async (bidirectionalLinkedListData) =>{
    let valueMap = new Map();
    let nextNodeMap = new Map();
    let sortedData = [];
    let nowItem;
    Promise.all(
        await bidirectionalLinkedListData.Items.map((element) => {
            valueMap.set(element.id,element.value);
            nextNodeMap.set(element.id,element.next)
            // 今回はprevが空文字のデータを先頭のデータと判断しています
            if(element.prev === "") nowItem = element.id;
        })
    );
    valueMap.forEach(() => {
        sortedData.push(valueMap.get(nowItem));
        nowItem = nextNodeMap.get(nowItem);
    });
    return sortedData;
};

main();

上記のコードを実行して変更前のデータと変更後のデータを確認してみます。2行目が変更前のデータで3行目が変更後のデータです。 出力からDynamoDB内部のデータが更新されて、順序が変わっていることが確認できます。

% node main.js
[ 'SAP', 'DOP', 'SAA', 'SOA', 'DVA', 'SCS' ]
[ 'SAP', 'SAA', 'DOP', 'SOA', 'DVA', 'SCS' ]

今回の例ではデータ量が少ないので対して変わらないですが、1000件、10000件とデータが増えても上記の更新回数+-1程度で済むので大幅に処理回数を減らすことができます。

実際に使う場合は、フロントエンド側で双方向リストのデータを追加・削除・リスト化などするための実装が必要になりますのでご注意ください。

感想

今回の内容はニッチな話ですがSPA+サーバーレスの構成が普及していけば、いずれ需要がでるかもしれない話なので書いてみました。 すぐ使うことはないかもしれないですが参考までに見てもらえると幸いです。もし他に良さそうなやり方あればTwitterなどで書いてもらえると嬉しいです。

最近体調悪くてベッドで資格勉強ぐらいしか出来なかったのですが、回復してきたので徐々に考えていた記事上げてきたいなと思ってます。

参考資料

双方向リストなどの計算量が見やすくまとまっています。

アルゴリズムとデータ構造 第４回 バケットソート，基数ソート