algorithm - グローバルに一意ではない識別子の生成

Question

UID の生成に関するさまざまな質問をいくつか見つけましたが、私が知る限り、ここでの要件はやや独特です (ha)。

要約すると、「ローカル」で一意の非常に短い ID を生成する必要がありますが、「グローバル」または「ユニバーサル」で一意である必要はありません。制約は単に美的またはスペースの問題に基づいているのではなく、これが本質的にハードウェアタグとして使用されており、ハードウェアの制約の対象であるという事実によるものです。仕様は次のとおりです。

ハード要件

ID には 10 進数のみを含める必要があります (基になるデータは BCD です)。
ID の最大長は 12 文字 (数字) です。
オフラインで生成する必要があります - データベース/Web 接続が常に利用できるとは限りません!

ソフト要件

暦年および/または月から開始したいと考えています。これは多くのエントロピーを浪費するので、これについて妥協したり、完全に廃棄したりすることは気にしません (必要な場合)。
特定のマシンから生成された ID は連続して表示されます。
ID はマシンごとに並べ替える必要はありません。たとえば、マシン 1 が [123000、124000、125000] を吐き出し、マシン 2 が [123500、123600、124100] を吐き出してもまったく問題ありません。
ただし、集合的な意味でシーケンシャルに見えるほど優れています。[200912000001, 200912000002, 200912000003, ...] のような ID のセットは完璧ですが、これは明らかに複数のマシン間で拡張できません。

使用シナリオ:

このスキームの範囲内の ID は、10 台、多くても 100 台の異なるマシンから生成されます。
生成される ID は合計で数百万を超えることはありません。
同時実行性は非常に低いです。1 台のマシンが ID を生成する頻度は、5 分ごとほどではありません。また、ほとんどの場合、一度に 5 台以下のマシンが同じ時間または同じ日に ID を生成します。特定のマシンで 1 日以内に生成される ID は 100 未満であり、すべてのマシンで 500 未満であると予想しています。
少数のマシン (3 ～ 5) が、ID の 80% 以上を生成する原因となる可能性が最も高いでしょう。

12 桁未満の 10 進数を使用して 100 ミリ秒または 10 ミリ秒の精度までタイムスタンプをエンコードできることを私は知っています。私が SO でこれを尋ねている理由は、人間が読める年/月をそこに組み込むか、ソースマシンに関する情報の一部をエンコードするか、またはその両方を行いたいからです。

誰かがこれらのソフト要件の妥協を手伝ってくれることを望んでいます...または、他の要件を考慮してそれらのどれも不可能な理由を説明してください。

(PS 私の「ネイティブ」言語は C# ですが、素晴らしいアイデアがあれば、どの言語のコードでも擬似コードでも問題ありません。)

アップデート：

これで寝る機会ができたので、実際にやろうとしていることは、デフォルトでタイムスタンプエンコーディングを使用し、個々のインストールが独自の 2 または3 桁のマシン ID。そうすれば、ID をいじり、人間が読み取れる情報を詰め込みたい顧客は、一意性を保証する独自の方法を整理することができ、誤用については責任を負いません。たまたますべてのオンラインインストールを行っている場合は、マシン ID を処理するためのサーバーユーティリティを提供することで、私たちが支援するかもしれません。

score 4 · Accepted Answer

「私が SO でこれを尋ねている理由は、人間が読める年/月をそこに組み込むか、ソースマシンに関する情報の一部をエンコードするか、またはその両方を行いたいからです。」

私は以前にこれに対処したことがあり、有用な情報をシリアル番号に保存しようとすることは、長期的には悪い考えであると言うことから始めましょう. デバイスのシリアル番号は無意味であるべきです。データベースレコードの主キーが無意味であるように。

実際のデータをシリアル番号に入力しようとすると、BUSINESS LOGIC がそれに投入され、他のコードと同じように維持する必要があります。あなたが過去に憎む未来。これで私を信頼してください。;o)

日付/時刻の値を保存しようとすると、無効な時刻/日付で数値スペースが無駄になります。たとえば、月のフィールドには 12 を超える値はありません。

単純なエポック/ユニット時間カウンターの方が優れていますが、1 分あたり数個の ID しか生成しないマシンの場合、依然として多くのスペースが無駄になります。

12 桁は多くのスペースではありません。ウィキペディアの VIN ページを見てください。わずか数メーカー、数千台の車のためのスペース。VIN に意味を詰め込んでスペースを使い果たしたため、VIN を再利用しています。

http://en.wikipedia.org/wiki/VIN

シリアル番号のすべての意味が悪いと言っているわけではありません。番号が衝突しないように厳密に制限してください。

このようなもの...

1位～3位：999台
4-12 桁目: 連番

衝突を避けるために必要なのはそれだけです。場所の数字を追加すると、11 の場所に到達するとめちゃくちゃになります。

これが暴言のように聞こえる場合は申し訳ありません。私は、電子機器やさまざまな機械加工部品を製造するために、これを多く扱っています。利用可能なスペースがたくさんある場合、またはセカンダリタグ（前述の必要なIDスペースを提供する-うわー-を提供する）がない限り、長期的にうまく終了することはありませんでした。

score 3 · Accepted Answer

ソフトウェアをインストールするときは、一意の数値 ID を含むマシン ID ファイル/レジストリキーもインストールしてください。数台のマシンしかないため、これには 3 桁または 4 桁しか必要ありません。これらを MS 桁として使用します。残りの桁を 1 から順番に生成します。

score 3 · Accepted Answer

どうyyMMddhhmmIDですか？

yy = two-digit year
MM = two-digit month
dd = two-digit day
hh = two-digit hour (24-hour time)
mm = two-digit minute
ID = machine-specific ID

例:0912113201のマシンからID = 01。

別の方法として (2 桁の年が苦手な場合 (Y2K 笑))、どうyyyyMMIDxxxxですか?

yyyy = four-digit year
MM = two-digit month
ID = machine-specific ID
xxxx = sequentially-incremented integer

例:200912010001のマシンからID = 01。

あなたが言ったように、各マシンは 5 分ごとに最大 1 つの識別子のみを生成しxxxxます。ここで、シーケンスまたはマシン IDyyyに余分な数字が必要な場合は、年を 3 桁の年 (009 など) に絞り込むことができます。xxxx

これらは両方とも、要求どおりにタイムスタンプ/マシン ID に適合します。

私たちは皆、具体的なコードが好きです:

class Machine {
    public int ID { get; private set; }
    public Machine(int id) {
        ID = id;
    }
}

 class IdentifierGenerator {
    readonly Machine machine;
    int seed;
    const int digits = 4;
    readonly int modulus;
    readonly string seedFormat;
    public IdentifierGenerator(Machine machine) {
        this.machine = machine;
        this.modulus = (int)Math.Pow(10, digits);
        this.seedFormat = new string('0', digits);
    }

    public string Generate() {
        string identifier = DateTime.Now.ToString("yyyyMM") 
                                + machine.ID.ToString("00") 
                                + seed.ToString(seedFormat);
        seed = (seed + 1) % modulus;
        return identifier;
    }
}

Machine m = new Machine(1);
IdentifierGenerator gen = new IdentifierGenerator(m);
Console.WriteLine(gen.Generate());
Console.WriteLine(gen.Generate());

出力:

200912010000
200912010001

score 1 · Accepted Answer

私はあなたがWindows用に開発していることを集めています（再：ジェイソンの答えに対する「MSI / EXE」についてのあなたのコメント）。そのため、WMIなどを使用して、一意のハードウェア属性（プロセッサまたはHDDのシリアル番号、NICのMACアドレスなど）を取得し、一意のマシンIDを基にすることができます。別の方法として、開発しているハードウェアの一意のシリアル番号（ある場合）を使用することもできます。

それはおそらく必要以上に長くなるので、潜在的にそれを切り捨てるかハッシュして（たとえば）16ビット程度に減らし、それをマシンIDとして使用することができます。明らかに、これは衝突を引き起こす可能性がありますが、マシンの数が少ない（〜100）ことは、これが起こりそうにないことを意味し、暗号化ハッシュ（MD5など）の切り捨てられた出力を使用すると、これはさらに少なくなります。

次に、（おそらく一意の）マシンIDがあるため、他の回答にリストされているアプローチを使用して、本質的に一意のIDを生成できます。

score 0 · Accepted Answer

24 時間で 864000 の 100 ミリ秒の目盛りがあるため、これを日付に追加すると 09.12.24.86400.0 となる可能性がありますが、12 桁に収まるように世紀を失う必要があり、マシン ID 用のスペースがありません。

score 0 · Accepted Answer

アイデアその1：

YYMMDDmmnnnn

どこ

YY is two digit year
MM is two digit month
DD is two digit day
mm is a two digit code unique to that machine (00 - 99)
nnnn is a sequential four digit code for that machine on that day.

~~

アイデアその2：

mmmmnnnnnnnn

どこ

mmmm is four digit code unique to the machine
nnnnnnnn is a sequential number.

score 0 · Accepted Answer

私の提案は、単一の ID で複数のアプローチを組み合わせることです。例: 年の 2 桁、月の 2 桁から始めて、次の数桁のシードとして時間を使用して乱数を生成し、最後の 2 桁の一意のマシン ID を生成します。またはそのようなもの。

score 0 · Accepted Answer

各マシンは DDNNN の開始 ID を取得します。ここで、DD は一意のマシン識別子であり、NNN はそのマシンによってその日に生成された現在の識別子です。各マシンは、特定の日付に生成した ID を追跡し、新しい ID が必要になったときに最後の ID を 1 ずつ増やして次の ID を割り当てます。毎日の開始時にカウンターを 0 にリセットします。日付 YYYYDOY は、各マシンによって生成された数値の先頭に追加されます (4 桁の年、3 桁の日)。マシン識別子が一意であるため、番号は一意であることが保証されます。

より多くのマシン用にさらにスペースが必要な場合は、年からミレニアムを削除して、マシン ID の数字を追加することができます: YYYDOYDDDNNN.

score 0 · Accepted Answer

"A single machine will not generate IDs more often than every 5 minutes or so"

Assuming this is true, then just use the timestamp. (32 bit Unix time has 10 decimal digits but will run out in 2038)

But I think its rather optimistic to assume there won't be a collision.

"IDs generated from a particular machine should appear sequential."

Then your only option is to use a sequence number.

Which doesn't really seem to match what you say in later constraints?

Concatenate a padded version of the node id to get unique values across the cluster.

score -1 · Accepted Answer

本機の MAC アドレスを MACHINE ID として使用します。これを使用して、タイムスタンプを XOR 経由でエンコードしたり、生成されたシリアル化されたコードに追加/先頭に追加したりできます。

algorithm - グローバルに一意ではない識別子の生成

ハード要件

ソフト要件

使用シナリオ:

10 に答える 10

Related

Reference