Thread-safe Random

היי,

יצא לי לאחרונה לטפל בבעיות ביצועים בספריה שלי. מבלי להכנס ליותר מדי פרטים, הספריה היא (בין השאר) ספריית Server המבוססת על WebSockets, וככזאת היא מטפלת בClientים מחוברים.

ברגע שהClient מצליח להתחבר לServer, הServer צריך להקצות לו מזהה ייחודי (הנקרא גם SessionId) - זהו מספר רנדומלי שלם בין 0 ל$ 2^{50} $ (לא כולל הקצוות. יכול להיות שהקצה הוא לא בדיוק $ 2^{50} $ אלא משהו שאני לא זוכר כרגע, אבל זה לא מהותי להמשך הפוסט).

אילוסטרציה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Server
{
private readonly Random mRandom = new Random();
private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer();
private const long MAX_RANDOM_SIZE = 2 >> 50;
public void OnNewClient(IConnection connection)
{
ClientProxy clientProxy = new ClientProxy(connection);
clientProxy.SessionId = mRandom.Next(MAX_RANDOM_SIZE);
mClientContainer.Add(clientProxy);
// ...
}
// ...
}

(פישטתי קצת את הסיפור, כעקרון צריך שהClientContainer יבחר את הSessionId, באופן שיצא חד-חד-ערכי. בנוסף, אין Overload לRandom שמקבל long, אבל אנחנו נתעלם מהבעיות האלה כיוון שהן לא מהותיות בהקשר של הבעיה)

הספריה כמובן מקבלת את הClientים בצורה א-סינכרונית, מה שאומר שכשClient מתחבר, מתעורר Thread מהThreadPool (באמצעות מנגנון הIOCP) ומתחיל לטפל בו. בדרך כלל הסיפור עבד בסדר גמור, אבל במקרי קיצון (מספר גדול מאוד של קליינטים או הרבה חיבורים/ניתוקים בו זמנית), יצא מצב שכל הקליינטים שהתחברו קיבלו את אותו SessionId שערכו היה 0.
(למי שקורא את מה שכתוב בסוגריים - במימוש הראשון לא וידאתי שאכן הSessionId חד-חד-ערכי. במידה והייתי מוודא זאת, במקום לקבל SessionId=0 בכל הקליינטים, השרת היה נתקע בלולאות אינסופיות)

דיבגתי את הקוד וראיתי שRandom מחזיר במקרה קיצון זה 0 תמיד. חיפשתי באינטרנט על כך, ומצאתי פוסט בבלוג של MSDN מ2009. בפוסט זה מציינים שRandom אינו Thread-safe והוא ממומש בצורה שגורמת לכך שאם הוא נקרא ממספר Threadים במקביל, הוא יחזיר 0.
בפוסט זה מציעים שני פתרונות לבעיה זו. הפתרון הראשון שהוא מאוד פשוט הוא להשתמש במנגנון נעילה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Server
{
private readonly Random mRandom = new Random();
private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer(
private readonly object mLock = new object();
private const long MAX_RANDOM_SIZE = 2 >> 50;
public void OnNewClient(IConnection connection)
{
ClientProxy clientProxy = new ClientProxy(connection);
lock (mLock)
{
clientProxy.SessionId = mRandom.Next(MAX_RANDOM_SIZE);
}
mClientContainer.Add(clientProxy);
// ...
}
// ...
}

פתרון זה אמנם קל, אבל יש לו חסרון שגורם לכך שכל פעם שאנחנו צריכים מספר רנדומלי, אנחנו צריכים לנעול, כך שהThreadים שלנו ממתינים לקבלת מספר רנדומלי.

פתרון נוסף שמציינים בפוסט זה הוא שימוש בThreadStatic - למי שלא מכיר, זהו משתנה סטטי הנוצר פר Thread הפתרון הראשוני יראה כך:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Server
{
[ThreadStatic]
private static Random mRandom = GetRandom();
private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer();
private const long MAX_RANDOM_SIZE = 2 >> 50;
public void OnNewClient(IConnection connection)
{
ClientProxy clientProxy = new ClientProxy(connection);
Random random = GetRandom();
clientProxy.SessionId = random.Next(MAX_RANDOM_SIZE);
mClientContainer.Add(clientProxy);
// ...
}
private static Random GetRandom()
{
if (mRandom == null)
{
mRandom = new Random();
}
return mRandom;
}
// ...
}

למי ששואל מדוע יצרתי פונקציה בשם GetRandom, זה מכיוון שהField Initializer לא נקרא פר Thread, אלא בפעם הראשונה בלבד.

פתרון טיפה יותר טוב הוא לשנות את הSeed פר Thread:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Server
{
[ThreadStatic]
private static Random mRandom;
private readonly object mLock = new object();
private readonly Random mSeedGenerator = new Random();
private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer();
private const long MAX_RANDOM_SIZE = 2 >> 50;
public void OnNewClient(IConnection connection)
{
ClientProxy clientProxy = new ClientProxy(connection);
Random random = GetRandom();
clientProxy.SessionId = random.Next(MAX_RANDOM_SIZE);
mClientContainer.Add(clientProxy);
// ...
}
private Random GetRandom()
{
if (mRandom == null)
{
int seed;
lock (mLock)
{
seed = mSeedGenerator.Next();
}
mRandom = new Random(seed);
}
return mRandom;
}
// ...
}

שימו לב שאנחנו נועלים רק בפעם הראשונה בכל Thread כשנוצר הRandom הפנימי.
הבעיה בפתרונות אלה שמוצעים בפוסט המדובר היא שמדובר במשתנה סטטי. עדיף לעבוד עם משתנה שהוא גם פר Instance.

למזלנו קיים בFramework טיפוס בשם ThreadLocal המאפשר את הסיפור הזה. (למי שלא מכיר, זהו טיפוס שעוטף את LocalThreadStorage בצורה נוחה)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class ThreadSafeRandom
{
private readonly ThreadLocal<Random> mRandom;
private readonly object mLock = new object();
private readonly Random mSeedGenerator = new Random();
public ThreadSafeRandom()
{
mRandom = new ThreadLocal<Random>(() => GetRandom());
}
private Random GetRandom()
{
int seed;
lock (mLock)
{
seed = mSeedGenerator.Next();
}
Random random = new Random(seed);
return random;
}
public Random Random
{
get
{
return mRandom.Value;
}
}
}
public class Server
{
private readonly ClientProxyContainer mClientContainer = new ClientProxyContainer();
private readonly ThreadSafeRandom mThreadSafeRandom = new ThreadSafeRandom();
private const long MAX_RANDOM_SIZE = 2 >> 50;
public void OnNewClient(IConnection connection)
{
ClientProxy clientProxy = new ClientProxy(connection);
Random random = mThreadSafeRandom.Random;
clientProxy.SessionId = random.Next(MAX_RANDOM_SIZE);
mClientContainer.Add(clientProxy);
// ...
}
// ...
}

ככה גם העברנו את הקוד שמטפל בRandom בצורה Thread-safe למחלקה חיצונית, כך שאנחנו יכולים לעשות לה Reuse, וגם המשתנה הוא באמת per-instance.

המשך יום עם אקראיות שהיא לא קבועה טוב

שתף