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

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

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

## 自動生成 ID とは？

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

具体的には

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

または

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

とすると以下のような ID のドキュメントが生成されます
<img width="276" alt="スクリーンショット 2019-06-09 20.56.51.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/199914/bb5d8d70-0a17-0ea8-5ddb-2e5a5d1bd644.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](https://github.com/firebase/firebase-ios-sdk/blob/master/Firestore/core/src/firebase/firestore/util/autoid.cc)

```c++: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](https://github.com/firebase/firebase-android-sdk/blob/master/firebase-firestore/src/main/java/com/google/firebase/firestore/util/Util.java)

```java: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](https://github.com/firebase/firebase-js-sdk/blob/master/packages/firestore/src/util/misc.ts#L23)

```typescript: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](https://www.npmjs.com/package/@google-cloud/firestore) という依存パッケージの中で生成していました

[Source](https://github.com/googleapis/nodejs-firestore/blob/master/dev/src/util.ts#L25)

```typescript: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](https://github.com/kelektiv/node-uuid) ライブラリでの実装

```javascript: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 なら `set` と `create` がある)
https://cloud.google.com/nodejs/docs/reference/firestore/1.3.x/DocumentReference#create

## ちなみに

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

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">JSのfirestoreのID生成ロジックがIDかぶりやすくてヤバいみたいな話を聞いたのですが、どこか出典があるんですかね🤔</p>&mdash; Soichi Sumi (@soichisumi) <a href="https://twitter.com/soichisumi/status/1136861691273080832?ref_src=twsrc%5Etfw">2019年6月7日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>