2

私のサイトでは、人々が私のサイトへのサブスクリプションをまとめて購入できるようにしています (バウチャーと呼んでいます)。これらのバウチャーを入手したら、誰にでも渡し、そのコードをアカウントに入力してアップグレードします。

現在、4つの英数字コード(大文字、小文字、数字)を実行することを考えており、次のようなものになります

var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
var stringChars = new char[4];
var random = new Random();

for (int i = 0; i < stringChars.Length; i++)
{
    stringChars[i] = chars[random.Next(chars.Length)];
}

var finalString = new String(stringChars);

今のところ、これで十分な組み合わせが得られると思います。不足した場合は、いつでもコードの長さを増やすことができます。ユーザーが巨大な数字を入力する必要がないので、短くしたいと思います。

また、より洗練されたソリューションを作成する時間もありません。おそらく、メール内のリンクまたは何かをクリックしてアカウントがアクティブになり、もちろんこれにより、バウチャー番号をランダムに推測しようとする人が削減されます.

これらは、サイトの人気が高まった場合に私が対処することです.

同じバウチャーの重複生成の可能性をどのように処理できるか疑問に思っています。私が最初に考えたのは、バウチャーが作成されるたびにデータベースをチェックし、存在する場合は新しいバウチャーを作成することでした。

ただし、それは遅くなる可能性があるようです。そのため、最初にすべてのキーを取得してメモリに保存し、そこでチェックすることも考えましたが、リストが大きくなり続けると、メモリ不足の例外やその他すべての素晴らしいことが発生する可能性があります。

誰にもアイデアはありますか?それとも、上記の 2 つの方法のいずれかを実行するのに行き詰まっていますか?

nhibernate、asp.net mvc、および C# を使用しています。

編集

 static void Main(string[] args)
        {
            List<string> hold = new List<string>();
            for (int i = 0; i < 10000; i++)
            {
                HashAlgorithm sha = new SHA1CryptoServiceProvider();
                byte[] result = sha.ComputeHash(BitConverter.GetBytes(i));
                string hex = null;

                foreach (byte x in result)
                {
                    hex += String.Format("{0:x2}", x);
                }

                hold.Add(hex.Substring(0,3));

                Console.WriteLine(hex.Substring(0, 4));
            }


             Console.WriteLine("Number of Distinct values {0}", hold.Distinct().Count());
        }

上記は、ハッシュを使用しようとする私の試みです。ただし、予想よりもかなり多くの重複があるように見えるため、何かが欠けていると思います。

編集 2

欠けていたものを追加したと思いますが、これが彼の意図したものかどうかはわかりません. また、移動できる限り移動した場合にどうすればよいかわかりません(移動できる場所の長さが40になるようです)。

  static void Main(string[] args)
        {
            int subStringLength = 4;
            List<string> hold = new List<string>();
            for (int i = 0; i < 10000; i++)
            {
                SHA1CryptoServiceProvider sha = new SHA1CryptoServiceProvider();
                byte[] result = sha.ComputeHash(BitConverter.GetBytes(i));
                string hex = null;

                foreach (byte x in result)
                {
                    hex += String.Format("{0:x2}", x);
                }

                int startingPositon = 0;
                string possibleVoucherCode = hex.Substring(startingPositon,subStringLength);

                string voucherCode = Move(subStringLength, hold, hex, startingPositon, possibleVoucherCode);
                hold.Add(voucherCode);
            }


             Console.WriteLine("Number of Distinct values {0}", hold.Distinct().Count());
        }

    private static string Move(int subStringLength, List<string> hold, string hex, int startingPositon, string possibleVoucherCode)
    {
        if (hold.Contains(possibleVoucherCode))
        {
            int newPosition = startingPositon + 1;
            if (newPosition <= hex.Length)
            {
                if ((newPosition + subStringLength) > hex.Length)
                {
                    possibleVoucherCode = hex.Substring(newPosition, subStringLength);
                    return Move(subStringLength, hold, hex, newPosition, possibleVoucherCode);
                }
                // return something
                return "0";
            }
            else
            {
                // return something
                return "0";
            }
        }
        else
        {
           return possibleVoucherCode;
        }

    }
}
4

5 に答える 5

1

バウチャーをランダムに生成してから、生成されたすべてのコードについてデータベースをチェックするため、処理が遅くなります。

vouchersID、コード、およびis_used列を使用してテーブルを作成します。そのテーブルに十分なランダムコードを1回入力します。これは別のプロセスで実行できるため、パフォーマンスはそれほど大きな問題にはなりません。夕方に実行すると、翌日、完全に満たされたバウチャーテーブルが手に入ります。

重複するバウチャーの生成を防ぎたい場合、それは問題にはなりません。とにかくそれらを生成し、System.Collections.Generic.HashSet(例外をスローせずに重複を追加しないようにする)に配置するか、LinqメソッドDistinct()を呼び出してから、それらをvouchersテーブルに追加できます。

于 2012-07-25T12:12:59.397 に答える
1

このような大量のデータ操作については、NHibernate を使用せず、そのまま ADO.NET を実行することをお勧めします。

一括チェック

一度に大量のコードのバッチを生成することが予想されるため、複数のコード チェックをデータベースへの 1 回のラウンドトリップにまとめる必要があります。SQL Server 2008 以降を使用している場合は、テーブル値パラメーターを使用してこれを実行し、コードのリスト全体を一度にチェックできます。

SELECT DISTINCT b.Code
FROM @batch b
WHERE NOT EXISTS (
    SELECT v.Code
    FROM dbo.Voucher v
    WHERE v.Code = b.Code
);

同時実行

では、並行性の問題についてはどうでしょうか。2 人のユーザーがほぼ同時に同じコードを生成するとどうなるでしょうか? それとも、コードの一意性をチェックするときと、それを Voucher テーブルに挿入するときのちょうど中間でしょうか?

次のようにクエリを変更することで、これを処理できます。

DECLARE @batchid uniqueidentifier;
SET @batchid = NEWID();

INSERT INTO dbo.Voucher (Code, BatchId)
SELECT DISTINCT b.Code, @batchid
FROM @batch b
WHERE NOT EXISTS (
    SELECT Code
    FROM dbo.Voucher v
    WHERE b.Code = v.Code
);

SELECT Code
FROM dbo.Voucher
WHERE BatchId = @batchid;

.NET 経由で実行する

次のテーブル値ユーザー タイプを定義していると仮定します...

CREATE TYPE dbo.VoucherCodeList AS TABLE (
    Code nvarchar(8) COLLATE SQL_Latin1_General_CP1_CS_AS NOT NULL
    /* !!! Remember to specify the collation on your Voucher.Code column too, since you want upper and lower-case codes. */
);

... 次のような .NET コードを介してこのクエリを実行できます。

public ICollection<string> GenerateCodes(int numberOfCodes)
{
    var result = new List<string>(numberOfCodes);

    while (result.Count < numberOfCodes)
    {
        var batchSize = Math.Min(_batchSize, numberOfCodes - result.Count);
        var batch = Enumerable.Range(0, batchSize)
            .Select(x => GenerateRandomCode());
        var oldResultCount = result.Count;

        result.AddRange(FilterAndSecureBatch(batch));

        var filteredBatchSize = result.Count - oldResultCount;
        var collisionRatio = ((double)batchSize - filteredBatchSize) / batchSize;

        // Automatically increment length of random codes if collisions begin happening too frequently
        if (collisionRatio > _collisionThreshold)
            CodeLength++;
    }

    return result;
}

private IEnumerable<string> FilterAndSecureBatch(IEnumerable<string> batch)
{
    using (var command = _connection.CreateCommand())
    {
        command.CommandText = _sqlQuery; // the concurrency-safe query listed above

        var metaData = new[] { new SqlMetaData("Code", SqlDbType.NVarChar, 8) };
        var param = command.Parameters.Add("@batch", SqlDbType.Structured);
        param.TypeName = "dbo.VoucherCodeList";
        param.Value = batch.Select(x =>
        {
            var record = new SqlDataRecord(metaData);
            record.SetString(0, x);
            return record;
        });

        using (var reader = command.ExecuteReader())
            while (reader.Read())
                yield return reader.GetString(0);
    }
}

パフォーマンス

これらすべてを実装した後 (コマンドとパラメーターの作成をループの外に移動して、バッチ間で再利用できるようにしました)、500 のバッチ サイズを使用して 10,000 のコードを一貫して約 1 秒で挿入することができました。0.5 ~ 2 秒、またはミリ秒あたり 5 ~ 20 コード。

コード密度/衝突/推測可能性

フィールドは、コードの_collisionThreshold密度を制限します。これは 0 から 1 の間の値です。実際には、1 未満でなければなりません。そうしないと、4 桁のコードが使い果たされたときに無限ループに陥ることになります (おそらく、コードにこれに対するアサーションを追加する必要があります)。0.5パフォーマンス上の理由から、決して上に回さないことをお勧めします。50% を超える衝突は、実際に新しいコードを生成するよりも、既に使用されているコードのテストにより多くの時間を費やしていることを意味します。

衝突のしきい値を低く保つことは、コードの推測の難しさを制御する方法です。に設定_collisionThresholdする0.01と、誰かがコードを推測する可能性が約 1% になるようなコードが生成されます。

衝突が頻繁に発生する場合、CodeLength(メソッドによって使用されGenerateRandomCode()ます) が増分されます。この値はどこかに永続化する必要があります。を実行した後、変更されているかどうかをGenerateCodes()確認CodeLengthしてから、新しい値を保存します。

ソースコード

完全なコードはhttps://gist.github.com/3217856から入手できます。私はこのコードの作成者であり、MIT ライセンスの下でリリースしています。この小さな課題を楽しんで、テーブル値パラメーターをインラインのパラメーター化されたクエリに渡す方法も学びました。私は今までそれをしたことがありませんでした。私はそれらを本格的なストアド プロシージャに渡したことがあります。

于 2012-07-26T01:05:46.657 に答える
1

ショートコードを主張する場合:

GUID を主キーとして使用し、乱数を 1 つ生成します。これをどのように英数字に変換するかはあなた次第です。

guid の最後の 1 バイトまたは 2 バイトと乱数を使用します。1234-684687 これにより、クーポンのブルートフォース攻撃が少し難しくなります。また、(まれな) 衝突を例外で処理します。

int を短くする簡単な方法は、基数を (10 から 62 に) 変更します。"2lkCB1"(VBで、これは古いコードです)Int32.MaxValue

''//given intValue as your random integer
Dim result As String = String.Empty
Dim digits as String = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
Dim x As Integer
While (intValue > 0)
   x = intValue Mod digits.Length
   result = digits(x) & result 
   intValue = intValue - x
   intValue = intValue \ digits.Length
End While
Return result

しかし今、私たちはすでに複数の質問に答えています。

于 2012-07-25T18:15:39.917 に答える
0

考えられる解決策は次のようなものです:
バウチャーの最大 ID (整数) を見つけます。次に、任意のハッシュ関数を実行し、最初の 32 ビットを取得して、ユーザーに表示する文字列に変換します (または、Jenkins ハッシュ関数などの 32 ビット ハッシュ関数を使用します)。これはおそらくうまくいくでしょう。ハッシュの衝突は非常にまれです。しかし、このソリューションは、ランダム性の点であなたのものと非常に似ています。

最初の 10 個または 100 個の衝突 (これで十分なはずです) を検出し、アルゴリズムにそれらを「スキップ」させて別の開始値を使用させるテストを実行できます。次に、データベースをまったくチェックする必要はありません (少なくとも、約 4294967296 バウチャーに到達するまでは...)。

于 2012-07-19T16:53:58.547 に答える
0

nHibernate の HiLo アルゴリズムを利用するのはどうですか?
の値を取得する方法の例を次に示します (DB アクセスなし)。

于 2012-07-19T19:00:32.023 に答える