Scalability Notes

Implementing Consistency - Protocols for Data Replication and Cache Coherence

• Suppose each data item has N replicas
  
• To read a value, client must contact with at least Nr replicas
• To write a data item, client must contact with at least Nw replicas
• To ensure no WW and WR conflicts, Nr + Nw > N and Nw + Nw > N should be statisfied

Consistency Model - A Survey

Part I - What's Data Consistency Model and Why Should We Care?

Data Consistency Model - it is a Semantic Contract between a data storage system and its user. Here, data storage system may refer to hardware system ( for example : memory sub-system inDSM, SMP, CMP computers) , or software systems (for example: distributed file system, web caching or distributed database).

Essentially, Consistency Model defines what value to return in a read operation.

The most natural semantic for storage system is - "read should return the last written value". It is intuitive in memory system with uniprocessor associated, where no concurrent access and no data replication exist.

But when concurrent client access and multiple replica exist, it's not easy to identify what "last write" means, mainly due to the lack of global time clock in parallel/distributed system.

So various data models are proposed to define various data semantic when Contention and Replication exists:
- Data Contention - In memory sub system of parallel computers, there may be multiple processors that access the same memory location at the same period of time, what's the semantic each processor should expect? (different process access the same data item)
- Data Replication - In distributed file/database system, each data block is replicated at multiple places, even access(read/write/modify) requests from the same client may involve more than one replicas, what's the semantic in client's perspective? (data item is replicated)
- Both Contention & Replication : What if multiple clients access replicated data blocks? What if there is a local cache for each processor in SMP system? (many processes access replicated data items)

Part II - The Various Models

There are many consistency models exist in computer architectures and distributed storage community. Why people invent so many semantics between storage and its clients? The reason is the trade off between Strict Semantic VS Available Optimization Space - strict (also simple and easy to understand, use and implement) semantic will limit the space that we can use to improve availability and do performance optimization. So each model has its advantages and drawbacks.

Before describe various models, we should clarify some concepts first:

Program Order - the order of operations (on data items) that is implied by the order of program statements(or assembly instructions). It's the issuing order of operations that are from the same thread/process.

Write Atomicity - write operation performs as no concurrent/overlapped operations can occur. So the meaning of "Atomicity" here differs from that in DBMS field, where "Atomicity" means that all ops in a transaction will be performed or none of them will be performed.

Consistency VS Coherence/Replication, Consistency focus on the semantic of data store (a set of data item) for multiple client accessing, while Coherence/Replication only deal with the semantic (and how to implement it) of a replicated data item (multiple replica exist) when it is accessed by multiple clients. Coherence/Replication is just part of the Consistency Model. Coherence / Replication Protocol only describes how to implement part of the semantic of some specific data consistency model.

[Update@07/23: Coherence and Replication are very similar and deal with the same problem, but the former is used in hardware system (for example, cache coherence) and the later is used in software system (for example, in distributed files system and database system]

Following are various Consistency Model descriptions:

1. Atomic Consistency/Strict Consistency

It means that for a particular data item (byte, cache block and file region etc.), each read will return the latest update. I.E. events are visible to all clients as they occurs/issues. As we already said, due to the lack of global time clock in distributed/parallel system, it is very hard to implement if not impossible.

2. Sequential Consistency

This model is defined as - "The result of any execution is the same as if the operations of all the processors were executed in some sequential order and the operations of each individual processor appears in this sequence in the order specified by its program." - Leslie Lamport

This definition implies:
1. Events/Operations from the same process are executed in program order
2. Every client sees the same order of all events/updates, which is a sequential one

Goods:
- Ensures every body sees the same order, very good for data replication
- Preserves causality

Bads:
- Many interleavings are valid (two independent program with M mem ops and N mem ops will have (M + N)!/(M!N!) valid interleavings)
- Different runs of a program might act differently
- Execution order may be very different from issuing order

3. Causal Consistency

Events that are causally related must be seen by everybody in the same order. Unrelated ("concurrent") events can be seen in different orders.

The challenge in implementing this model lies in how to identify "causally related" events.

4. Eventual Consistency

If no updates take place for a long time (inconsistency window), all replicas will gradually become the latest version of the value.

In this model, if client reads data from different replica, it's hard to define a clear semantic about the return value. To resolve this problem, client-centric consistency is introduced. These models focus on the semantic in a single client's perspective.

Monotonic Reads - If a process reads the value of an object, any successive read operations on that object by that process will always return the same or more recent value.

Monotonic Writes - A write operation by a process on a data item x is completed before any successive write operation on x by the same process.

Read Your Writes - The effect of a write operation by a process on data item x will always be seen by a successive read operation on x by the same process. A closely related model is "Session Consistency". In this model, Read Your Write semantic only works within a session context and not cross session boundary.

Write Follow Reads - Any successive write operation by a process on a data item x will be performed on a replica of x that is up-to-date with the value most recently read by that process.

5. Weak Consistency

A storage system is said to support weak consistency if:

1. All synchronization operations are seen by all processors in the same sequentially order.
2. All data operations may be seen in different order on different processors. (But order of ops on the same data item is preserved)
   
3. The set of both read and write operations in between different synchronization operations is the same in each processor.

An alternative definition is as:

1. Accesses to synchronization variables are sequentially consistent.
2. No access to a synchronization variable is allowed to be performed until all previous writes have completed everywhere.
3. No data access (read or write) is allowed to be performed until all previous accesses to synchronization variables have been performed.

This model is weaker than sequential consistency model, since no order assumption can be made on data operations between consecutive synchronization operations.

The weak consistency leverage the fact that - between consecutive sync operations, no other process can use the data being written. So it's safe to reorder write operations on different mem locations. But the order of operations on the same location must be preserved to ensure a reasonable memory semantic.

6. Release Consistency

Release consistency is an extension of weak consistency that exploits the information about acquire, release, and nonsynchronization accesses.

1. Before an ordinary LOAD or STORE access is allowed to perform with respect to any other processor, all previous acquire accesses must be performed, and
2. Before a release access is allowed to perform with respect to any other processor. all previous ordinary LOAD and STORE accesses must be performed, and
3. Special accesses are processor consistent with respect to one another.

In Release Consistency Model, all write operations by a certain node are seen by the other nodes after the former releases the object and before the latter acquire it, but a node must call acquire to get up-to-date values.

There are two kinds of coherence protocols that implement release consistency:
- eager, where all coherence actions are performed on release operations, and
- lazy, where all coherence actions are delayed until after a subsequent acquire

7. Entry Consistency

Like all variants of Release Consistency, it requires the programmer to use acquire and release at the start and end of each critical section, respectively. However, entry consistency requires each ordinary shared variable to be associated with some synchronization variable such as a lock or barrier.

- An acquire access of a synchronization variable S is not allowed to perform with respect to process Pi until all updates to the guarded shared data Ds have been performed with respect to process Pi.

- Before an exclusive mode access to a synchronization variable S by processor Pi is allowed to perform with respect to Pi, no other processor may hold S in non-exclusive mode.

- After an exclusive mode access to S has been performed, any processor's next non-exclusive mode access to S may not be performed until it is performed with respect to the owner of S.

8. Processor Consistency

- Writes done by a single processor are received by all other processors in the order in which they were issued, but
- Writes from different processors may be seen in a different order by different processors

The motivation behind this model is to better reflect the reality of networks in which the latency between different nodes can be different.

This model is also known as FIFO Consistency and Pipeline Random Access Memory Consistency.

Notes on Nex Steps:
1. Why People Invent Each Model?
2. What's Good and What's Bad for Each Model?

[Reference]
[1] Wiki on Consistency Model
[2] Summary on Consistency Model by CTO@Amazon
[3] Shared Memory Consistency Models: A Tutorial
[4] Memory Consistency Models
[5] Notes On Consistency
[6] Entry Consistency, Midway : Shared Memory Parallel Programming with Entry Consistency for Distributed Memory Multiprocessors
[7] Release Consistency, Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors
[8] Weak Consistency, Memory Access Buffering in Multiprocessors
[9] Memory Ordering in Modern Microprocessors (Part I, Part II)
[10] Wiki on Cache Coherence

Scalable I/O Models - In Sync & Async Way

Time and Order of Events in Distributed System

1. Each process set a initial clock value(arbitary) on start up;
   
2. A process increments its counter between two consecutive events in that process; (Send message and Receive message are all events)
   
3. When a process sends a message(after doing step 2), it includes its counter value with the message;
4. On receiving a message(after doing step 2), the receiver process sets its counter to be greater than the clock value in received message AND greater than or equal to its present clock value;
5. If two events have the same clock value, use its associated process ID to determine the order between them.
   

1. Initially all clock values are set to zero;
2. Before a process experiences an internal event, it increments its own clock value in the vector by at least one.
3. Each time a process prepares to send a message, it conducts Step 2 and then sends its entire vector along with the message being sent.
4. Each time a process receives a message, it conducts Step 2 and updates each element in its vector by (suppose the sending process is Ps):

Memory Management in Native Code

Memory management is a core task in native world, careless usage of dynamic memory may cause the following problems:

- 1. Heap Fragment, this will introduce performance penalty since it breaks data locality
- 2. Memory Leak, it's a prgm correctness problem and a horrible defect for long-run software

Here I summarized some tips related to the two issues: Mem Optimization & Mem Correctness


Part I - Mem Optimization

General Principles
1. Ensure mem layout cohesion (aka. improve data locality)
2. Avoid frequent alloc/free (aka. batch mem ops, prefer few & bulk over large & small mem ops)

How to implement them?
- Redesign your data structure to make them live in large blocks
- Make unrelated data structure in different region
- Use memory pool to manage mem


Part II - Mem Correctness

One of the challenges when doing native code development is avoiding memory leak. It's so easy (also difficult to avoid) to forget releasing each memory block/object that has been allocated explicitly.

Types of Mem Leaks
1. Constant Leak, allocated mem are totally forgotten to release
2. Casual Leak, allocated mem are not release under some conditions
3. One-Time Leak , allocated mem is not released but that line of code only get executed once (for example, mem allocated in ctor of singleton objec)
4. Implicit Leak, mem blocks are hold too long (released too late in application life cycle, this kind of mem leak happens even in GC enabled language such as Java/.Net, for example, unused objects are still reachable through Root Set in GC)

To deal with Mem Leak problem, you have two choices:
- Avoid it
- Detect & Fix it

Sec. I - How to Avoid Mem Leak?

1. Adopt Resource Acquisition Is Initialization (RAII) Mechanism in C++

std::auto_ptr is a good choice if RAII is semantic right for your problem. If you want to ensure your object/mem get released whenever the control goes out of some scope (for example, multiple exit path, potential exception etc.), RAII can be used to solve your problem.

But it can't be passed as return value, can't be put in STL containers.

2. stack based allocation

_alloca() will allocated mem from stack rather than heap. The mem returned will be released when function returns.

But there is potential stack overflow exceptions, since stack is far more smaller than heap.

3. Reference Counting (aka, share/smart pointer)

Use some data structure to track how many owners are referencing the mem block or objects. When reference counting is zero, the mem/object is released.

std::tr1::shared_ptr and boost::shared_ptr are all based on Reference Counting and RAII concepts. They resolved the problem of not being able to be put in container, can't be passed as parameter and return value etc.

But, if your objects have cyclic reference, this mechanism doesn't work. The fundamental problem behind is that - the semantic of "useless", should be defined as "Can't Be Reached", not "No One References".

Another draw back of smart pointer style reference counting is that, it can't handle pointers that should be put into a union structure. Because union can't consists of any member fields that has user defined ctor/non-trivial default ctor/dtor/copy ctor etc.

4. Garbage Collection (yes, gc for C/C++)

Most modern GC uses Mark & Sweep algorithm to implement GC. The idea behind is that, GC has pointer list for all heap-allocated objects and a Root Set object pointer list. When garbage collection is triggered, it traverse from root set to find all reachable objects and mark them. Those unmarked objects are garbage that can be deleted. GC for C/C++ is a huge topic, [7] is a very good reference doc.

General purpose GC for C/C++ is difficult, but for your specific application requirement, it may not that challenge. According to my own GC implementation experience, the most difficult part is define your object ownership policy.

GC is great, but it still can't handle some "semantic garbage objects". That is to say, if you hold references to some objects that are in fact you will never use again, GC won't collect mem and other resources owned by these objects.

Essentially, Memory Management is all about Consistency of Ownership.
- Each mem block should have an owner
- Each mem block should have only 1 owner
- Only the owner of the mem block is responsible for its life cycle

So, the most important design principle about C/C++ memory management is - consider carefully about the ownership of an object/mem block: when and who should be responsible for releasing it.

Sec. 2 - How to Detect Mem Leak

1. Use Debug Version C RunTime library

1.1 Use _CrtDumpMemoryLeaks()

Step 1. include the following directives into each cpp source file
#define _CRTDBG_MAP_ALLOC
#include "crtdbg.h"
#include "stdlib.h"

Step 2. call _CrtDumpMemoryLeaks() at the line where you want to check memory leaks.

This method has a drawback that mem objects that are released after _CrtDumpMemoryLeaks() invocation will be treated as leaked mem. (This happens when mem is released in global object's dtor) It's a false negative.

1. 2 Use _CrtSetDbgFlag()

Add the following code at the entry point of your application

int nFlag = _CrtSetDbgFlag( _CRTDBG_REPORT_FLAG );
nFlag |= _CRTDBG_LEAK_CHECK_DF;
_CrtSetDbgFlag( nFlag );

This method don't have the drawback of 1.1, but you have no control when the mem leak action performs.

1. 3 Use CrtMemState

_CrtMemState cms1, cms2, cms3;
_CrtMemCheckpoint(&cms1);

/* code to check */

_CrtMemCheckpoint(&cms2);
if(_CrtMemDifference(&cms3, &cms1, &cms2))
{
_CrtMemDumpStatistics(&cms3);
}

This code will dump heap statistics info about the changes happened in the "code to check".

_CrtSetReportMode() can be used to control where to output these diagnose information.

_crtBreakAlloc / {,,msvcrtd.dll}_crtBreakAlloc / _CrtSetBreakAlloc() can be used to control the debug break condition.

More info on CRT mem debug routines, please see reference [1] and [2]

2. Monitor Process Working Set

The Win32 API GetProcessMemoryInfo() can query process working set size. You can use this api to check whether the working set size is changed after calling some suspicious functions.

It can't tell you where mem leak happens, but it a good way to write unit test to track mem leak problems.

3. Use Professional Tools

BoundsChecker
IBM Purify
LeakTracer(Linux)
Windows Leaks Detector
Valgrind(Linux)
MemWatch
Insure++
Visual Leak Detector
User Mode Dump Heap

Part III - Other Tips

1. use "#define SAFE_DELETE(ptr) if (ptr != NULL) { delete ptr; ptr = NULL; }" to avoid redeleting the same object.
2. remember to delete objects pointed by elements in container that contains pointers.
3. pair delete/new delete[]/new[] malloc/free correctly.
4. use "new (std::nothrow)" to eliminate exceptions raising in low mem situation.


NOTE: (Lessons learned from topic investigating)

When solving hard problems, Be Sure To:
1. Use well-known idioms and well-understood mechanisms
2. Keep things as simple as possible

Memory Management:
1. It's another subsystem/component of your whole system
2. Design this component with care
3. Avoid using new/delete directly

Techniques discussed here apply to not only memory blocks, but also any type of "resource" that needs explicit requesting/releasing.

[Reference]

Mem Leak
1. Mem Leak Detection http://www.ddj.com/cpp/204800654
2. Microsoft CRT Debug Routines http://msdn.microsoft.com/en-us/library/1666sb98(VS.71).aspx
3. Microsoft CRT Debug Tech http://msdn.microsoft.com/en-us/library/zh712wwf.aspx
4. Mem Debugger List http://en.wikipedia.org/wiki/Memory_debugger
5. Purify from IBM - Use Purify for C code
6. Mem Leak in Java/.Net http://www.agiledeveloper.com/articles/MemoryLeak092002.pdf

Garbage Collection
7. C/C++ GC from HP http://www.hpl.hp.com/personal/Hans_Boehm/gc/
8. GC for C/C++ http://blog.codingnow.com/2008/06/gc_for_c.html
9. How .Net GC works, GC in OO Language, Auto GC

Understanding Mem Management
10. C++ Mem Management http://www.slideshare.net/reachanil/c-memory-management
11. Inside Mem Management http://www.ibm.com/developerworks/linux/library/l-memory/
12. C++ Memory Management: From Fear to Triumph (Part 1, Part 2, Part 3)
13. http://www.cantrip.org/wave12.html
14. Mem Optimization http://www.codingnow.com/2008/memory_management.ppt
15. Mem Mgmt 4 Sys Coder http://www.enderunix.org/simsek/articles/memory.pdf

Misc
16. C++ smart pointers http://www.onlamp.com/lpt/a/6559
17. Mem Leak Definition
18. Is Mem Leak Ever OK?

Windows, Unix and ANSI C API Comparison

Subject	Windows	UNIX	Comments
Security	AddAccessAllowedAce	chmod, fchmod	C library does not support security
Security	AddAccessDeniedAce	chmod, fchmod
Security	AddAuditAce	N/A
Security	CreatePrivateObjectSecurity	N/A
Security	DeleteAce	chmod, fchmod
Security	DestroyPrivateObjectSecurity	N/A
Security	GetAce	stat*, fstat*, lstat
Security	GetAclInformation	stat*, fstat*, lstat
Security	GetFileSecurity	stat*, fstat*, lstat
Security	GetPrivateObjectSecurity	N/A
Security	GetSecurityDescriptorDacl	stat*, fstat*, lstat
Security	GetUserName	getlogin
Security	InitializeAcl	N/A
Security	InitializeSecurityDescriptor	Umask
Security	LookupAccountName	getpwnam, getgrnam
Security	LookupAccountSid	getpwuid, getuid, geteuid
Security	N/A	getpwend, setpwent, endpwent
Security	N/A	getgrent, setgrent, endgrent
Security	N/A	Setuid, seteuid, setreuid
Security	N/A	Setgid, setegid, setregid
Security	OpenProcessToken	getgroups, setgroups, initgroups
Security	SetFileSecurity	chmod*, fchmod
Security	SetPrivateObjectSecurity	N/A
Security	SetSecurityDescriptorDacl	Umask
Security	SetSecurityDescriptorGroup	chown, fchown, lchown
Security	SetSecurityDescriptorOwner	chown, fchown, lchown
Security	SetSecurityDescriptorSacl	N/A

SOA programming model on Windows Hpc Server

Conventionally, HPC/Parallel problems can be roughly divided into the following three categories[1][2]:

- Embarrassingly Parallel, for these applications, little or no effort is required to separate the problem into a number of small tasks that runs on one CPU core. No or very lightweight post processing is needed.

- Parametric/Data Parallel, these applications divides the input data into a number of completely independent parts. The same computation is undertaken on each part. And some kind of post processing after the computations is needed.

- Message Passing, these are those jobs that there are dependencies among various tasks and there are communications among these tasks. These jobs are not easy to be parallelized.

On Windows Hpc Server 2008, programming model for Embarrassingly Parallel(especially web based) applications is referenced as SOA Model, in which, client send requests to service broker, and service broker forward these requests to service instances. Service instance never talks to each other, and communication among these components are all service oriented(more specifically, WCF based).

[SOA Programming Model Workflow, from Microsoft]

How to Read Source Code

Part I - General Steps and Principles

1. Define a Clear Goal
- what's the purpose? to know how, to own components, to modify and extend?
- results driven, what's the final outcome?

2. Know it as Client User
- read user manual
- get an overall big picture
- know what it can do and what can't
- what is it suitable for and what not

3. Thinking Before Reading
- what if you design the whole system?
- what's the core challenge?
- write down your questions and concerns
- read with questions

4. Know the Architecture/Components
- know the overall architecture first
- devide the whole system into components
- identify what to focus, what to ignore
- use build file to identify component dependencies
- try building it

5. Read Specific Detail
- make a SMART plan
- focus on core logics
- ignore trivial parts
- start from entry point: main/wmain funtion
- identify thread creation/termination
- identify the main loop (server application)
- identify core data structure
- identify operations on core DS
- noting/documenting/charting down while reading

6. Producing Results
- big picture from user's perspective
- big picture from dev's perspective
- arch/logic for individual component
- summerize core data structure
- practice: build/deploy/use/debug/modify/hack the system
- comments on the implementation(what's good, what's bad, what learned)

7. Misc Tips
- read doc(user manual, design doc) before code
- get core data structure doc first if possible
- read the code in both static and dynamic(debug) way
- debug/step into a particular execution scenario
- read code iteratively, don't deep into detail in the beginning
- use interface/contract to separate concerns
- overall -> detail, but just detail on small areas
- leverage code comprehension tools to get static information
- print out core code and read them on real papers
- you can write unit test / use case for the software
- consider refactoring the code(kind of active reading) if unit tests are given
- if it's really hard to read, rewrite it!

Part II - Tools

One of the most frequent activities when reading code is navigating among those source codes. So tools that help navigating are important to improve the reading efficiency. Here are some popular tools for this purpose:

1. Source Code Index Generator
cscope http://cscope.sourceforge.net/
ctags http://ctags.sourceforge.net/

2. GUI Frontend for Index Generator
kscope http://kscope.sourceforge.net/
cbrowser http://cbrowser.sourceforge.net

3. Code Index Generating and Navigating
Source Navigator http://sourcenav.sourceforge.net/
Source Insight http://www.sourceinsight.com/
LXR http://lxr.linux.no/

4. For C Language ONLY
CXRef http://www.gedanken.demon.co.uk/cxref/
cflow http://www.gnu.org/software/cflow/

[Reference]
1. Code Comprehension Tool http://www.cs.ubc.ca/~murphy/cs319/index.html
2. Code Doc Generating Tool http://www.stack.nl/~dimitri/doxygen/links.html
3. Survey on Code Comp. Tools http://www.grok2.com/code_comprehension.html
4. Tips for Code Reading http://c2.com/cgi/wiki?TipsForReadingCode
5. Read VS Rewrite http://www.joelonsoftware.com/articles/fog0000000069.html

Scalability in Online Game and Virtual World

The Beauty of Windows HPC Server 2008

1. Components of Windows HPC Server
- an x64 version based Windows Server 2008 Core
- a new and faster MS-MPI, which is based on MPICH2
- a scalable job scheduler for creation, execution and monitoring
- windows deployment service based provisioning service
- UI, cmd utilities and PowerShell cmdlets for cluster managing and monitoring

2. Architecture of Windows HPC Server