Help us understand the problem. What is going on with this article?

【Firestore】ドキュメントの自動生成 ID って被らないの?

Firestore の自動生成 ID がどうやって生成されているのか気になったので、分かる範囲で調査してみました
擬似乱数あたりの話は詳しくないので補足などいただけるとうれしいです

TL;DR

  • 各クライアント SDK で乱数を元に alphanumeric な20文字を生成
  • ただの疑似乱数生成関数を使っている SDK もある
  • UUID よりは安全でないと言えそう

自動生成 ID とは?

Firestore は .add(...).doc().set(...) メソッドを呼び出すと自動的に ID を生成してくれます

具体的には

db.collection('cities').add({
  name: 'Tokyo',
  country: 'Japan'
})

または

db.collection('cities').doc().set({
  name: 'Tokyo',
  country: 'Japan'
})

とすると以下のような ID のドキュメントが生成されます
スクリーンショット 2019-06-09 20.56.51.png

参考: https://firebase.google.com/docs/firestore/manage-data/add-data?hl=ja#add_a_document

コードを見るほうが早いと思うので載せていきます

iOS

iOS の Firebase SDK は主に Objective-C や C++ で書かれていて、ID 生成部分は C++ でした

Source

autoid.cc
namespace {

const int kAutoIdLength = 20;
const char kAutoIdAlphabet[] =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

SecureRandom shared_random;

}  // namespace |

std::string CreateAutoId() {
  std::string auto_id;
  auto_id.reserve(kAutoIdLength);

  // -2 here because:
  //   * sizeof(kAutoIdAlphabet) includes the trailing null terminator
  //   * uniform_int_distribution is inclusive on both sizes
  std::uniform_int_distribution<int> letters(0, sizeof(kAutoIdAlphabet) - 2);

  for (int i = 0; i < kAutoIdLength; i++) {
    int rand_index = letters(shared_random);
    auto_id.append(1, kAutoIdAlphabet[rand_index]);
  }
  return auto_id;
}

Android

Java です

Source

Util.java
public class Util {
  private static final int AUTO_ID_LENGTH = 20;

  private static final String AUTO_ID_ALPHABET =
      "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

  private static final Random rand = new Random();

  public static String autoId() {
    StringBuilder builder = new StringBuilder();
    int maxRandom = AUTO_ID_ALPHABET.length();
    for (int i = 0; i < AUTO_ID_LENGTH; i++) {
      builder.append(AUTO_ID_ALPHABET.charAt(rand.nextInt(maxRandom)));
    }
    return builder.toString();
  }
}

JavaScript

Web アプリなどで使うクライアント SDK の方です

Source

misc.ts
import { assert } from './assert';

export class AutoId {
  static newId(): string {
    // Alphanumeric characters
    const chars =
      'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
    let autoId = '';
    for (let i = 0; i < 20; i++) {
      autoId += chars.charAt(Math.floor(Math.random() * chars.length));
    }
    assert(autoId.length === 20, 'Invalid auto ID: ' + autoId);
    return autoId;
  }
}

Node.js

Admin SDK の方では @google-cloud/firestore という依存パッケージの中で生成していました

Source

utls.ts
export function autoId(): string {
  const chars = 
    'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
  let autoId = '';
  for (let i = 0; i < 20; i++) {
    autoId += chars.charAt(Math.floor(Math.random() * chars.length));
  }
  return autoId;
}

おまけ

ちなみに Realtime Database では Push ID という「タイムスタンプ+ランダムな値」を生成しているようです

参考
https://firebase.googleblog.com/2015/02/the-2120-ways-to-ensure-unique_68.html
https://gist.github.com/mikelehen/3596a30bd69384624c11

衝突しないの?

考えられる ID の総数を 122 ビットの UUID v4 と比較してみると

UUID v4 autoID
$$ 2^{122} = 5.3 * 10^{36} $$ $$ 62^{20} = 7.4 * 10^{35} $$

ということで、

同様に確からしい (= 乱数が安全である) 場合わずかに UUID の方が衝突しにくい

という結果となりました

安全なの?

例えば Admin SDK (Node.js) で使われている Math.random() はただの疑似乱数生成関数なので偏りが生じるらしく、
乱数生成部分に暗号論的疑似乱数生成関数を使っているような ID の実装よりは衝突しやすいと言えそうです

例) node-uuid ライブラリでの実装

lib/rng.js
var crypto = require('crypto');

module.exports = function nodeRNG() {
  return crypto.randomBytes(16);
};

参考:https://qiita.com/gakuri/items/27cca8f0fa28b78ddeca

まとめ

UUID と比較して衝突しやすい実装ではありますが
普通に使っている分には心配しなくていいのかなとも思いました

Firestore ではオフラインでも書き込めてしまうため RDB の auto_increment 的な戦略はとれないですが
どうしても気になるようであれば Admin SDK 経由で DocumentReference.create() を使うと良さそうです
(クライアント SDK には set しかないが Admin SDK なら setcreate がある)
https://cloud.google.com/nodejs/docs/reference/firestore/1.3.x/DocumentReference#create

ちなみに

@soichisumi さんと @kahirokunn さんの tweet をきっかけに、以前調査して下書きに溜めていたものを加筆して投稿しました
大変参考になったので引用させていただきます:bow:

yukin01
iOS → Firebase → インフラ/SRE 見習い
globis
グロービスは 1992 年の創業以来、社会人を対象とした MBA、人材育成の領域で Ed-Tech サービスを提供し、現在は日本 No.1 の実績があります。これらの資産と、さらに IT や AI を活用することで、アジア No.1 を目指しています。
http://www.globis.co.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした