[C++] Equality preservation

Reference:
Equality preservation

Equality Preservation is a rule that says a function (or expression) must be "well-behaved" and "predictable."

It essentially means: If you give it the same inputs, you should get the same outputs.

• The Core Idea: "No Surprises"

If we have two objects, a and b, and they are equal (a == b), then doing the same thing to both of them should result in the same outcome.

Equal Inputs -> Equal Results: If f(a) returns 5, and a == b, then f(b) must also return 5.

Equal Inputs -> Equal Side Effects: If calling f(a) changes a to 10, then calling f(b) must change b to 10.

• The Requirement of "Stability"

The standard also requires equality-preserving expressions to be stable. This means if we haven't changed the object ourselves, calling the function twice on the same object must give the same result both times.

Example of something NOT stable:
A function that returns a random number or a function that uses a global counter that increments every time you call it. i.e. has no Referential transparency

    int counter = 0;

    int bad_function(int x) { return x + (counter++); } // NOT equality-preserving

By requiring concepts to be equality-preserving, C++ guarantees that:

• The algorithm can trust the values it reads.
• The algorithm can safely make copies of objects and expect the copies to behave exactly like the originals.

Unless noted otherwise, every expression used in a requires expression of the standard library concepts is required to be equality preserving, and the evaluation of the expression may modify only its non-constant operands. Operands that are constant must not be modified.

In the standard library, the following concepts are allowed to have non equality-preserving requires expressions:

• output_iterator
• indirectly_writable
• invocable
• weakly_incrementable
• range

[system design] Lesson learned from Optimising Data Building In Game Development

Optimising Data Building In Game Development - Dominik Grabiec - ACCU 2025
https://www.youtube.com/watch?v=KNAyUjeNewc

As for GPU resource clean up:

i.e. CUDA: cudaDeviceReset()

[software design][functional programming] Referential transparency

Referential transparency

An expression is referentially transparent if it can be replaced with its corresponding value without changing the program's behavior.

This means that for a function to be referentially transparent, it must be a pure function, which has two key properties:

• It always returns the same output for the same inputs.
• It has no side effects. (It doesn't modify global variables, print to the console, read from a file, make a network request, etc.)

DoD and ECS

Reference:
Data Storage in Entity Component Systems - Mathieu Ropert - Meeting C++ 2023
https://www.youtube.com/watch?v=b9hNKFj5R3Y
https://en.wikipedia.org/wiki/Entity_component_system

https://skypjack.github.io/2019-02-14-ecs-baf-part-1/
https://github.com/skypjack/entt

[system design] Scalable and Reliable Logging at Pinterest (DataEngConf SF16)

Reference:
https://youtu.be/DphnpWVYeG8?t=2250

Although this talk was back in 2016, there are several points to take away:

1. the way project 'merced' operates reminds me of paper 'Sparrow'

https://cs.stanford.edu/~matei/papers/2013/sosp_sparrow.pdf

And their use of zk as message delivery is fun.

2. back then Kafka doesn't support exactly once delivery and transaction commit;

thus they've spent quite of efforts for that.

3. back then K8S an't popular/feature rich enough which addresses HA issues~

[monitoring] Book: Monitoring Distributed Systems

Book:
Monitoring Distributed Systems

Monitoring

Collecting, processing, aggregating, and displaying real-time quantitative data about a system, such as query counts and types, error counts and types, processing times, and server lifetimes.

• White-box monitoring (k8s readiness probe)
  Monitoring based on metrics exposed by the internals of the system, including logs, interfaces like the Java Virtual Machine Profiling Interface, or an HTTP handler that emits internal statistics.
• Black-box monitoring (k8s liveness probe)
  Testing externally visible behavior as a user would see it.
• Dashboard
  An application (usually web-based) that provides a summary view of a service’s core metrics. A dashboard may have filters, selectors, and so on, but is prebuilt to expose the metrics most important to its users. The dashboard might also display team information such as ticket queue length, a list of high-priority bugs, the current on-call engineer for a given area of responsi‐ bility, or recent pushes.
• Alert
  A notification intended to be read by a human and that is pushed to a system such as a bug or ticket queue, an email alias, or a pager. Respectively, these alerts are classified as tickets, email alerts, and pages.
• Root cause
  A defect in a software or human system that, if repaired, instills confidence that this event won’t happen again in the same way. A given incident might have multiple root causes: for example, perhaps it was caused by a combination of insufficient process automation, software that crashed on bogus input, and insuffi‐ cient testing of the script used to generate the configuration. Each of these factors might stand alone as a root cause, and each should be repaired.
• Node (or machine)
  Used interchangeably to indicate a single instance of a running kernel in either a physical server, virtual machine, or container. There might be multiple services worth monitoring on a single machine. The services may either be:
• Related to each other: for example, a caching server and a web server
• Unrelated services sharing hardware: for example, a code repository and a master for a configuration system like Puppet or Chef
• Push
  Any change to a service’s running software or its configuration.

Why Monitor?

• Analyzing long-term trends
• Comparing over time or experiment groups
• Alerting
• Building dashboards (“The Four Golden Signals”: latency, traffic, errors, and saturation.)
• Conducting ad hoc retrospective analysis (i.e., debugging)

Monitoring and alerting enables a system to tell us when it’s broken, or perhaps to tell us what’s about to break. When the system isn’t able to automatically fix itself, we want a human to investigate the alert, determine if there’s a real problem at hand, mitigate the problem, and determine the root cause of the problem.

In general, Google has trended toward simpler and faster monitor‐ ing systems, with better tools for post hoc analysis. We avoid “magic” systems that try to learn thresholds or automatically detect causality.

To keep noise low and signal high, the elements of your monitoring system that direct to a pager need to be very simple and robust.

Rules that generate alerts for humans should be simple to understand and represent a clear failure.

Your monitoring system should address two questions: 

• what’s broken,
• and why?

“What” versus “why” is one of the most important distinctions in writing good monitoring with maximum signal and minimum noise.

In Google’s experience, basic collection and aggregation of metrics, paired with alerting and dashboards, has worked well as a relatively standalone system.

When creating rules for monitoring and alerting, asking the following questions can help you avoid false positives and pager burnout:

• Does this rule detect an otherwise undetected condition that is urgent, actionable, and actively or imminently user-visible?
• Will I ever be able to ignore this alert, knowing it’s benign? When and why will I be able to ignore this alert, and how can I avoid this scenario?
• Does this alert definitely indicate that users are being negatively affected? Are there detectable cases in which users aren’t being negatively impacted, such as drained traffic or test deployments, that should be filtered out?
• Can I take action in response to this alert? Is that action urgent, or could it wait until morning? Could the action be safely automated? Will that action be a long-term fix, or just a short-term workaround?
• Are other people getting paged for this issue, therefore rendering at least one of the pages unnecessary?

These questions reflect a fundamental philosophy on pages and pagers:

• Every time the pager goes off, I should be able to react with a sense of urgency. I can only react with a sense of urgency a few times a day before I become fatigued.
• Every page should be actionable.
• Every page response should require intelligence. If a page merely merits a robotic response, it shouldn’t be a page.
• Pages should be about a novel problem or an event that hasn’t been seen before.

[cli][note] design / Command Line Interface Guidelines

Reference:
https://github.com/cli-guidelines/cli-guidelines

Page:
https://clig.dev/

Basics

• C++: 3rd party lib; e.g. https://github.com/CLIUtils/CLI11
• Return zero exit code on success, non-zero on failure.
• Beware of bash exit code 128.
• Send output to stdout.
• Send messaging to stderr.

Help

• Display help text when passed no options, the -h flag, or the --help flag.
• Display a concise help text by default.
• Show full help when -h and --help is passed.
• Provide a support path for feedback and issues.
• Lead with examples.
• Display the most common flags and commands at the start of the help text.
• Use formatting in your help text.
• *If the user did something wrong and you can guess what they meant, suggest it.
• If your command is expecting to have something piped to it and stdin is an interactive terminal,
  display help immediately and quit.

Output

• Human-readable output is paramount.
• Have machine-readable output where it does not impact usability.
• If human-readable output breaks machine-readable output, use
  --plain
  to display output in plain, tabular text format for integration with tools like grep or awk.
• Display output as formatted JSON if --json is passed.
• Display output on success, but keep it brief.
• If you change state, tell the user.
• Make it easy to see the current state of the system.
• Suggest commands the user should run.
• Actions crossing the boundary of the program’s internal world should usually be explicit. 
• By default, don’t output information that’s only understandable by the creators of the software.
• Don’t treat stderr like a log file, at least not by default.
• Don’t print log level labels (ERR, WARN, etc.) or extraneous contextual information, unless in verbose mode.
• Use a pager (e.g. less) if you are outputting a lot of text.

Errors

• Catch errors and rewrite them for humans.
• Signal-to-noise ratio is crucial.
• Consider where the user will look first. 
• If there is an unexpected or unexplainable error,
  provide debug and traceback information, and instructions on how to submit a bug.
• Make it effortless to submit bug reports.

Arguments and flags

• Prefer flags to args.
• Have full-length versions of all flags. For example, have both -h and --help.
• Only use one-letter flags for commonly used flags
• If you’ve got two or more arguments for different things, you’re probably doing something wrong.
• Make the default the right thing for most users.
• Confirm before doing anything dangerous.
• Do not read secrets directly from flags.
• If possible, make arguments, flags and subcommands order-independent

Subcommands

• Be consistent across subcommands. 
• Use consistent names for multiple levels of subcommand.
• Don’t have ambiguous or similarly-named commands. For example, having two subcommands called “update” and “upgrade” is quite confusing.

Robustness

• Validate user input.
• Responsive is more important than fast. Print something to the user in <100ms. If you’re making a network request, print something before you do it so it doesn’t hang and look broken.
• Show progress if something takes a long time.
• Do stuff in parallel where you can, but be thoughtful about it.
• Make things time out.
• Make it recoverable.
• Make it crash-only.
• This is the next step up from idempotence. If you can avoid needing to do any cleanup after operations, or you can defer that cleanup to the next run, your program can exit immediately on failure or interruption. This makes it both more robust and more responsive.

Future-proofing

• Keep changes additive where you can. Rather than modify the behavior of a flag in a backwards-incompatible way.
• Warn before you make a non-additive change.

Signals and control characters

• If a user hits Ctrl-C (the INT signal), exit as soon as possible.
• If a user hits Ctrl-C during clean-up operations that might take a long time, skip them. Tell the user what will happen when they hit Ctrl-C again, in case it is a destructive action.

Configuration
Environment variables
Naming

Distribution

• If possible, distribute as a single binary.
• Make it easy to uninstall.

[scale] maxim

QCON 2017 Scaling Instagram Infrastructure 

[Go] Design

Reference:
https://dave.cheney.net/2016/08/20/solid-go-design

Bad code

Old fashion articles

• Rigid. Is the code rigid? Does it have a straight jacket of overbearing types and parameters, that making modification difficult?
• Fragile. Is the code fragile? Does the slightest change ripple through the code base causing untold havoc?
• Immobile. Is the code hard to refactor? Is it one keystroke away from an import loop?
• Complex. Is there code for the sake of having code, are things over-engineered?
• Verbose. Is it just exhausting to use the code? When you look at it, can you even tell what this code is trying to do?

SOLID

• Single Responsibility Principle
• A class should have one, and only one, reason to change.
• Coupling & Cohesion
• Package names, don't use name like 'common', 'util' which are too broad.
• Unix philosophy; small, sharp tools which combine to solve larger tasks.
• Open / Closed Principle
  Software entities should be open for extension, but closed for modification.
• Liskov Substitution Principle
• Two types are substitutable if they exhibit behaviour 
• such that the caller is unable to tell the difference.
  Require no more, promise no less.
• Interface Segregation Principle
• Clients should not be forced to depend on methods they do not use.
• A great rule of thumb for Go is accept interfaces, return structs.
• Dependency Inversion Principle
• High-level modules should not depend on low-level modules. Both should depend on abstractions.
• Abstractions should not depend on details. Details should depend on abstractions.
• In Go, import graph must be acyclic.
• All things being equal the import graph of a well designed Go program should be a wide, and relatively flat, rather than tall and narrow.
• If you have a package whose functions cannot operate without enlisting the aid of another package,that is perhaps a sign that code is not well factored along package boundaries.

Focus        

• Go programmers need to start talking less about frameworks, and start talking more about design. 
• We need to stop focusing on performance at all cost, and focus instead on reuse at all costs.
• What I want to hear is people talking about how to design Go programs in a way that is well engineered, decoupled, reusable, and above all responsive to change.

[Beam] Timely (and Stateful) Processing

The main (or even the only) reason for using Java based Beam is for it's time + stateful batch records processing.

Beam provides to some extend Go API to call with, but unfortunately it's run-time is in JVM.

Look beyond the language part, the design and idea is based on Tyler Akidau's book as well as 2 articles noted here:
https://vsdmars.blogspot.com/2019/12/streaming-notes.html 

And in this article uses Beam to realize(or Beam is based on above idea) the design.

Timely (and Stateful) Processing with Apache Beam : https://beam.apache.org/blog/timely-processing/

[Go][design] high through-put low contention in memory cache

Project https://github.com/dgraph-io/ristretto as example

Fast Access:

batching:

• use ring-buffer for each lock and update the global cache.

generate a fast hash:

• use runtime.memhash from Go Runtime.

High Concurrency and Contention Resistance:

Get (tinyLFU):

• use sync.Pool to implement striped, lossy ring-buffers that have great performance with little loss of data to update frequency. 
• Use with channel for async update.

Set (tinyLFU + Count–min sketch): 

• use a channel to capture the Sets, dropping them on the floor if the channel is full to avoid contention.    

Memory Bounding:

• An infinitely large cache is practically impossible.
• A cache must be bounded in size. Many cache libraries would consider cache size to be the number of elements, this is naive and only works in a workload where values are of identical size. Most workloads, however, have variable-sized values. One value could cost a few bytes, another a few kilobytes and yet another, a few megabytes.Treating them as having the same memory cost isn't realistic.

Idea:

• Attach a cost to every key-value.
• Users can specify what that cost is when calling Set. 
• When the cache is operating at capacity, a heavy item could displace many lightweight items.

Admission Policy:

• What should we let into the cache when the capacity is hit?
  The goal, obviously, is to let in new items if they are more “valuable” than the current items. (there is overhead)
• Using LFU, not LRU:
  Paper: TinyLFU: A Highly Efficient Cache Admission Policy
• The main idea is to only let in a new item if its estimate is higher than that of the item being evicted. 
• Use count-min sketch.
• After N key increments, the counters get halved.
• Use TTL. A key that has not been seen for a while would have its counter get reset to zero.
• To find a key with low ɛ, use randomness sampling, which provided by iterating through Go's map key.
• If the incoming key's ɛ is higher than ɛ from randomness sampling, reject the incoming key, otherwise, incoming key is stored.
• Note that the cost of the incoming key does not play a factor in choosing the eviction keys.

DoorKeeper:

• When capacity hits, use a bloom filter to first check if the key has been seen before. 
• Only if the key is already present in the bloom filter, is it inserted into the TinyLFU.

Metrics:

• When using atomic counters for metrics, be ware of false sharing between caches among CPU cores.
• While cache line size, on my thinkpad is 64-bytes, use atomic.AddUint64 as atomic counter.

Reference:

Design Of A Modern Cache (Benjamin Manes)
http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html

BP-Wrapper: A System Framework Making Any Replacement Algorithms (Almost) Lock Contention Free
https://dgraph.io/blog/refs/bp_wrapper.pdf

Adaptive Software Cache Management
https://dgraph.io/blog/refs/Adaptive%20Software%20Cache%20Management.pdf

TinyLFU: A Highly Efficient Cache Admission Policy
https://dgraph.io/blog/refs/TinyLFU%20-%20A%20Highly%20Efficient%20Cache%20Admission%20Policy.pdf

The State of Caching in Go
https://dgraph.io/blog/post/caching-in-go/

Count–min sketch
https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch

[Streaming] notes

Reference:
https://www.oreilly.com/ideas/the-world-beyond-batch-streaming-101
https://www.oreilly.com/ideas/the-world-beyond-batch-streaming-102


Event time vs. processing time
Event time:
which is the time at which events actually occurred.

Processing time:
which is the time at which events are observed in the system.

• Time-agnostic
• All relevant logic is data driven.
• Filtering
  
  
• Inner-joins
  
  
• Approximation
  
• https://pkghosh.wordpress.com/2014/09/10/realtime-trending-analysis-with-approximate-algorithms/
• https://databricks.com/blog/2015/01/28/introducing-streaming-k-means-in-spark-1-2.html
• Windowing by processing time
  
  
• Fixed windows
• Sliding windows
• Sessions
• Windowing by event time
  
  

Watermarks:

• A watermark is a notion of input completeness with respect to event times.
• A watermark with a value of time X makes the statement: “all input data with event times less than X have been observed.”
• As such, watermarks act as a metric of progress when observing an unbounded data source with no known end.

Triggers:

• A trigger is a mechanism for declaring when the output for a window should be materialized relative to some external signal.
• Triggers provide flexibility in choosing when outputs should be emitted.
• They also make it possible to observe the output for a window multiple times as it evolves.
• This in turn opens up the door to refining results over time, which allows for providing speculative results as data arrive as well as dealing with changes in upstream data (revisions) over time or data which arrive late relative to the watermark
  (e.g., mobile scenarios, where someone’s phone records various actions and their event times while the person is offline, then proceeds to upload those events for processing upon regaining connectivity).

Accumulation:

• An accumulation mode specifies the relationship between multiple results that are observed for the same window. Those results might be completely disjointed, i.e., representing independent deltas over time, or there may be overlap between them.
• Different accumulation modes have different semantics and costs associated with them, and thus find applicability across a variety of use cases.

[Concurrency] Optimistic concurrency control

Optimistic concurrency control (sometimes referred to as optimistic locking) is a method where instead of locking a piece of data and preventing it from being read or updated while the lock is in place, the piece of data includes a version number. 

In C++ memory model, which is referred in transactional memory as implementation detail.

Every time the data is updated, the version number increases.

Since version number can be used with the scalar type, which can be add/minus with single instruction without lock.

When updating the data, the version number is checked to see if it has increased between the time the client read the data and the time it submits the update.

(perfect use case for atomic compare and exchange)

If this happens, the update is rejected and the client must re-read the new data and try to update it again.

The result is that when two clients try to update the same data entry, only the first one succeeds.

All k8s resources include a metadata.resourceVersion field, which clients need to pass back to the API server when updating an object.
If the version doesn’t match the one stored in etcd, the API server rejects the update.

[structure concurrency][Go][design] Graceful Shutdown

Recently I'm working on Actor design utilizing with Golang's channel.

Link: https://github.com/vsdmars/actor

While bumped into Martin Sústrik's blog post:
Graceful Shutdown: http://250bpm.com/blog:146
Along with the discussion: https://trio.discourse.group/t/graceful-shutdown/93
Structured concurrency resources: https://trio.discourse.group/t/structured-concurrency-resources/21

It's a nice summary, touched the well known concept of pthread cancellation point as well as Golang's context.Done()/Cancel() pattern.

Notes:
In-band cancel:
through application level channel

out-of-band cancel:
through language run-time

Sending a graceful shutdown request cannot possibly be a feature of the language. It must be done manually by the application.


POSIX C thread:
Reference:
https://stackoverflow.com/a/27374983
http://man7.org/linux/man-pages/man7/pthreads.7.html (Cancellation points)

The rules of hard cancellation are strict:
Once a coroutine has been hard-canceled the very next blocking call will immediately return ECANCELED.
In other words, every single blocking call is a cancellation point.

As an additional note, if looking at the POSIX requirement for cancel points, virtually all blocking interfaces are required to be cancel points.
Otherwise, on any completely blocked thread (in such call), there would be no safe way to terminate that thread.

Graceful shutdown can terminate the coroutine only when it is idling and waiting for a new request.

Reasoning:

If we allowed graceful shutdown to terminate the coroutine while it is trying to send the reply, it would mean that a request could go unanswered.

And that doesn't deserve to be called "graceful shutdown".
(e.g. Golang, context.Done() pattern)

Definition summarize:

Hard cancellation:

- Is triggered via an invisible communication channel created by the language runtime.

- It manifests itself inside the target coroutine as an error code (ECANCELED in libdill) or an exception (Cancelled in Trio).

- The error (or the exception) can be returned from any blocking call.

- In response to it, the coroutine is not expected to do any application-specific work. It should just exit.

Graceful shutdown:

- Is triggered via an application-specific channel.

- Manifests itself inside the target coroutine as a plain old message.

- The message may only be received at specific, application-defined points in the coroutine.

- In response to it, the coroutine can do arbitrary amount of application-specific work.

Hard cancellation is fully managed by the language.

Graceful shutdown is fully managed by the application.

Golang library reference:

go-resiliency/deadline: https://github.com/eapache/go-resiliency/tree/master/deadline

Godoc: https://godoc.org/github.com/eapache/go-resiliency/deadline#example-Deadline

[Note] design principle

While researching into LMAX found Martin Thompson's video,
although it's cliche
(in the way that senior engineers should have known),
still worth jotting down a note here.

Design Principle

1. Clear separation of concerns
2. Garbage free in steady state running
3. Lock-free, wait-free, and copy-free in data structures in the message path
4. Repsect the Single Writer Principle
5. Major data structures are not shared
6. Don't burden the main path with exceptional cases
7. Non-blocking in the message path

Succint into 3 things:

1. System Architecture
2. Data structures
3. Protocols of interactions

Data structures:

• Map
• IPC Ring Buffers
• IPC Broadcast Buffers
• ITC Queues
• Dynamic Arrays
• Log Buffers

[distributed system][design] Real-Time Delivery Architecture at Twitter

• nothing is stable, embrace and deal with it.
• keep it simple.
• LRU for Redis.
• CQRS Always consider separately from read and write design.
• Event-based 'router'
• Fan-out :-) It's been used back in the day Jesus was born :-P ext4 files system/inode, fanout with another indirection.
  Prof. David Wheeler : "All problems in computer science can be solved by another level of indirection" (the "fundamental theorem of software engineering")
• consider about edge cases.
• Technology makes lives, better, keep on!

[goto 2018] The Robustness of Go • Francesc Campoy

https://www.youtube.com/watch?v=40d26ZGfhR8

Define robust

Memory safety

• Pointers for convenience, but no pointers arithmetics.
• Escape analysis for automated allocation on heap/stack.
• Garbage collection: no dangling pointers.
• Automatic bound checks for slices and arrays.

 

Make go unsafe

• Use unsafe.
• Use cgo.
• Bug in compiler(runtime).

 

Fragility

• Mutable shared state.
• Check data race. (Always enable this!)
  # go run -race test.go
• Use monads to handle error...
  But go doesn't have generic. Thus don't think about it...

 

System Runs Forever Self-heal and Scale

Talk:
https://www.infoq.com/presentations/self-heal-scalable-system

6 rules:

• Isolation
• Concurrency (Actor model, Erlang)
• Failure detection
• Fault identification
• Live code upgrade
• Stable Storage

k8s provides what golang doesn't provide.
Use k8s. XD

[C++][book][elements of programming][note] regular type

Reference:
Fundamentals of Generic Programming - Alex Stepanov
[C++11] C++11 Library Design

Reading notes for:
Titus Winters - Revisiting Regular Types

Define Regular types (quoted):
The term Regular is meant to describe the syntax and semantics of built-in types in a fashion that allows user-defined types to behave sensibly.

The C++ programming language allows the use of built-in type operator syntax for user-defined types.
This allows us to make our user-defined types look like built-in types.
Since we wish to extend semantics as well as syntax from built-in types to user types, we introduce the idea of a Regular type, which matches the built-in type semantics, thereby making our user-defined types behave like built-in types as well.

Thus, define customize type as 'do as the ints do'.

Regular definition:
Both definitions focus heavily on semantics not just syntax.

The reasoning about code is much easier if the code consists of Regular types, instead of non-Regular ones, using the existing understanding of how built-in types work.


Four of the most basic semantic requirements on Regular types from Stepanov's early paper:

// comparison follows from copy
T a = b; assert(a==b);

// copy and assignment are the same
T a1; a1 = b; T a2 = b; assert(a1 == a2);

// copy/assignment is by value, not reference
T a = c; T b = c; a = d; assert(b==c);

// zap always mutates, unmutated values are untouched
T a = c; T b = c; zap(a); assert(b==c && a!=b);

Reference:
Identity of indiscernibles : https://en.wikipedia.org/wiki/Identity_of_indiscernibles

Logicians might define equality via the following equivalence:
x == y ⇔ ∀ predicate P, P(x) == P(y)

This is true:
x == y ⇒ ∀ predicate P, P(x) == P(y)

But reverse might not be true:
∀ predicate P, P(x) == P(y) ⇒ x == y


Programming languages inherently contain predicates that don't exist in pure math, because the execution on computing hardware is a somewhat leaky abstraction.
(Consider X, Y refer to same memory address but might has it's value changed.)

In general, we focus on predicates that observe 'the value' rather than the identity of the instance.

Objects which are naturally variable sized must be constructed in C++ out of multiple simple structs, connected by pointers. In such cases, we say that the object has remote parts. For such objects, the equality operator must compare the remote parts...


Definition of equality:
Two objects are equal if their corresponding parts are equal (applied recursively), including remote parts (but not comparing their addresses), excluding inessential components, and excluding components which identify related objects.

When designing our own Regular type:

• how to compare two instances of our type (by value, focusing on the logical state, not comparing by identity/memory location)
• If our type implements all the syntactic/semantic requirements for Regular

P0898(r2) Standard Library Concepts
Definition of concept (in general, including philosophy)

UDT considered Regular type iff has these member functions:

• DefaultConstructible, 
• CopyConstructible, 
• Destructible,
• Movable, 
• Swappable,
• Assignable, 
• EqualityComparable

Consider const member function thread safe.
i.e

• concurrent (non-synchronized) calls to const methods are allowed,
• if any concurrent call is made to a non-const method, there is the chance for a data race.

(ref CppCon 2014: Herb Sutter "Lock-Free Programming note )

• On the C++ abstract machine there is no such thing as a safe data race. 
• The C++ standard specifically calls this out: data races are undefined behavior. 
• No correct program has undefined behavior. 
• const means const contract. If internal state changes, violates the const contract.

Classify types as either 'thread-safe', 'thread-compatible', or 'thread-unsafe', based on the conditions under which use of its API may result in a data race.

• Thread-safe:
  No concurrent call to any API of this type causes a data race.
  This is useful for things like a Mutex.
  Generally speaking, thread-safe types are easiest to work with, but you pay for some of that usability in performance or API restrictions or both.
  (Reference: [C++] Always consider function thread safeness drags performance in single thread code. )
• Thread-compatible:
  No concurrent call to any const operation on this type causes a data race.
  Any call to a non-const API means that instance must be used with external synchronization.
  C++ guarantees that standard library types are at least thread-compatible.
  This follows from the general pattern of Regular design, and 'do as the ints do' as int is thread-compatible.
  In most cases, this is in-line with the philosophy of C++ - you do not pay for what you do not use.
  If you operate on an optional<int>, you can be sure that it isn't grabbing a mutex.
  On the other hand, thread-compatible may have overhead in some cases: shared_ptr<> is unnecessarily expensive in cases where there is no sharing between threads, because of the use of atomics to synchronize the reference count.
  (GCC's shared_ptr detects whether the executable is linked to libpthread and uses non-atomic updates when possible.)
• Thread-unsafe: Even concurrent calls to const APIs on this type may cause data races - use of an instance of such a type requires external synchronization or knowledge of some form to be used safely.
  These are generally either used with a mutex or are used with knowledge like 'I know that this instance is only accessed from this thread' or 'I know that my whole program is only single threaded.'
  Types like this may be because of mutable members, or because of non-thread-safe data that is shared between instances.

When using a function, or a Regular type instance, ALWAYS consider precondition.

Consider about int* type instance.
It's precondition can only be checked during run-time,
and there's no member function of int* type can check the precondition of int* type instance.
i.e
Invoking int* operation safely requires structural knowledge of the program. A type that has dependent preconditions has one or more such APIs; these are often (but not always) about properties of non-owned objects/external memory/etc.

APIs that have dependent preconditions are more complicated to use - they fundamentally require knowledge about the rest of the program in order to use safely.

Race-Free + Regular

When operates on a type instance, consider it race-free iff:

• Thread-compatible and not shared with other threads for writing.
  If been handed a (non-racing) const T& you can operate on this in const fashion.
  If necessary, you can copy it to ensure there are no lurking references and perform any computation / mutation safely (but inefficiently).
  With minor knowledge (the instance isn't shared), a T& can be used safely as if it were T.
• It has dependent-preconditions, but for a particular instance + any dependent data, the program structure guarantees safe usage.
• Single-threaded usage - There is only one thread in the program and thus all instances of the type are safe to use, or a given instance is known to not be shared among threads.

With above 3 options, we have these definitions:

• Thread-compatible + Regular is what we really want for user-defined types that mimic built-ins.
  This lets us reason about an instance in the expected fashion and use it efficiently in conjunction with generic algorithms.
  Types that have mutable data may have some overhead to support this.
• Dependent-preconditions with knowledge that an instance + its dependent data are safe to use.
  This is the common usage for string_view when we use it as a non-owning parameter type: the underlying buffer will outlive the function call and is immutable for the duration of the call. (reference: https://github.com/jeaye/value-category-cheatsheet/blob/master/value-category-cheatsheet.pdf)
  Given that external knowledge of that underlying buffer, string_view behaves as if it were Regular. This makes sense, given that string_view was designed to be a drop-in replacement for const string&, and although references are not Regular types (Reference: [C++] Union/StandardLayoutType can not have reference data member), std::string types are.
• Single-threaded usage - This is easy to misuse, but can be an important area for optimization.
  Consider the discussions to provide a shared_ptr analogue that does not synchronize its reference count - if we know something about program structure, or can guarantee particular usage for an instance, we can design a more efficient type in this fashion. Given that knowledge, such a shared_ptr can still behave as if it were Regular.

Use this to verify if the type is regular type:

using T = UDT;
void DoSomething(const T& t);

const T a = SomeT();  // Assume SomeT() is providing a
                      // long-lived and stable buffer.
const T b = SomeT();

if (a == b) {
  DoSomething(a);
  assert(a == b);
}

//Stepanov’s axioms about assignment and comparison.
// comparison follows from copy
T a = b; assert(a==b);

// copy and assignment are the same
T a1; a1 = b; T a2 = b; assert(a1 == a2);

// copy/assignment is by value, not reference
T a = c; T b = c; a = d; assert(b==c);

// zap always mutates, unmutated values are untouched
T a = c; T b = c; zap(a); assert(b==c && a!=b);

The point of having string_view, std::span is to make the API interface consistent, which is,
instead of using

• const char* 
• const string& // reference itself is NOT regular type, which is not owning.

We could simply use

• const std::span  // using const to ensure it's member function called is thread safe.
• const std::string_view  // using const to ensure it's member function called is thread safe.

[LMAX][ACTOR MODEL][Note] A bit about LMAX

Reference:
[AKKA] How the Actor Model Meets the Needs of Modern, Distributed Systems
[AKKA] What problems does the actor model solve?



[Video] The Actor Model (everything you wanted to know...)

• Processing
• Storage
• Communication

One actor is no actor

Actor comes in system

Actor has address

Everything is an actor

When actor receives messages, it can

• Create more actors
• Send messages to other actors that it has the addresses to send to
• Designate what to do with the next message it receives

Future

They are actors can be send around(like a lambda expression/closure)

Address

Address : Actor is many-to-many arch.

Message

Messages are received NO guarantee in order.

It's like the IP(not TCP) model.
IP sequence without considering order(upper layer will do the check).

Sender persists message.

There's NO channels.

Same message can be send at MOST 1 time. No duplicate.

Message sent is not time-bounded. Which can take a long time to arrive to another actor.

Message being handled one at a time, which gives us synchronization.

non-deterministic vs. in-deterministic

Nondeterministic (turing) vs Indeterministic (actors)

E.g: A message that increments a number and then sends the same message again.
Another message, to stop and report the number is on its way. How many increments can happen before the stop message arrives.

arbiter

• Not something you can make out of just (and gates/or gates) and other boolean components.
• Equal number of outputs to inputs. 
• The output order is not determined by the order of input. 
• Unbounded by processing time but the probability of output goes down exponentially as time goes on. 
• Mutated state isn't for the current message.
  Mutated state is for the next message.

LMAX

Paper:

Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads
(neat paper touch the basic idea of MESI / false sharing / prefetch etc.)


The LMAX Architecture

• Event sourcing (log, RAFT)
• snapshot (RAFT, taking snap shot with commited log)
• unlike RAFT, Business Logic Processor keep multiple active node, each input event is processed by multiple active node.

Concurrent execution of code is about two things:

• mutual exclusion and
• visibility of change.

CAS approach is significantly more efficient than locks because it does not require a context switch to the kernel for arbitration.

However CAS operations are not free of cost.
(Details can be read from book: The art of multiprocessor programming)

The processor must lock its instruction pipeline to ensure atomicity and employ a memory barrier to make the changes visible to other threads.

The ideal algorithm would be one with only a single thread owning all writes to a single resource with other threads reading the results.

To read the results in a multi-processor environment requires memory barriers to make the changes
visible to threads running on other processors.


Solution:
Ensuring that any data should be owned by only one thread for write access, therefore eliminating write contention.


When designing a financial exchange in a language that uses garbage collection, too much memory allocation can be problematic. (golang, and the benefit of using C++)

The LMAX Architecture
https://martinfowler.com/articles/lmax.html

The best programmers prefer profilers and test cases to speculation.

reference:
https://en.wikipedia.org/wiki/Little%27s_law
Ring buffer basics
Circular Buffers in C/C++

[accu2018][design] Read/Write thinking would be harmful for system design

Read and write considered harmful - Hubert Matthews [ACCU 2018]

Could be the best presentation in this year's ACCU talk.

Also reference:
Mike Acton's Data-oriented Design cppcon 2014 presentation

Notes below:

Basics of Read/Write

• Business processes, rules and schemas
• Performance, scaling, concurrency
• Six questions about data
• Asynchrony and queues
• Structure changing
• State management

Reads

• Can be cached, at multiple levels (e.g CPU)
• Caching is transparent(mostly)
• Idempotent (can be retried without side-effects)
• Can be partitioned easily (routing, i.e load balancer, API gateway etc.)
• Access control rules only
• Synchronous and blocking
• Scalable bandwidth - fanout reduces contention

Writes

• Caching is horrible for writes
• writeback/through, eviction policy, coherence, etc.
• Scaling writes is horrible - fan-in creates contention
• Sharding works well only for primary key writes
• Access control rules plus update rules
• Can be delayed or asynchronous (write back cache, i.e store buffer)
• Idempotent is a design issue/choice

Dependencies

• Even simple code has dependencies caused by read and write
• Asymmetric - caller object doesn't know who calls it
• Makes testing difficult
• Substitution
• Mocks, etc
• Introduces notion of push and pull

REST APIs and rules

• REST = getters/setters on steroids
• Industrial-scale anti-pattern
• Separates code and data
• Opposite of encapsulation
• Very non-OO
• Duplicated logic/rules in every client
• e.g stock_level >= 0
• If rule is broken

Tradeoffs: early/late validation failure, schema migration, versioning, code/rule duplication

REST = CRUD

• statechart has one state and four transitions
• OK for metadata
• Real processes have multiple states
• Have different entities per state
• (Possiblly sub-entities)

Typical system scaling path (important!)

Think it in the WRONG WAY.

• Application is too slow
• Get more front-end boxes(scale R + W)
• Application is still too slow
• Get bigger DB box(scale R + W)
• Run out of read bandwidth
• Replicate or cache data(Scale R)
• Run out of write bandwidth
• Shard/Partition data on primary key(scale R + W)
• Create separate services per entity/component
• Cross-service joins done in client(scale entities)

Scaling problems

• Partitioning or sharding works to an extent
• If access is strongly biased around primary key
• 例如: access flight dates(平均平坦) vs. access every days meal(sequential even if hashed keys)
• Nasty to scale cross-partition operations
• Particularly for write (usually not idempotent)
• Partial failure on write, cross-box transactions, concurrency, latency, etc.
• Service boundaries aligned with operations boundaries and failure boundaries
• Bulk access to multiple records can cause N+1 access problems
  (get primary keys then N single-row accesses:
  beware of REST and ORMs) 可用batch access解決.

Avoid sharing mutable data

• Shared mutable data is the evil of all computing
• Read-only data can be shared safely without locks
• Const is our friend!
• Pure message-passing approach avoids this

Shared writes don't scale

• In memory programming
• 0 scalability!

Why shared writes don't scale?

MESI / Cores

• Caches have to communicate to ensure coherent view
• MESI protocol passes messages between caches
• Shared writes limited by MESI communication
• JUST DON'T DO SHARE WRITE!

6 questions about data access

Primary key: hashing, partitioning, op==

• Most common from of access
• database primary key
• std::map/unordered_map
• Can use hashing [O(1)], binary search [O(logN)] or linear search for small N [O(N)]
• Requires only operator ==
• Partition on PK into multiple parts that can operate in parallel or to avoid contention
  e.g Product catalogue, customer records, sticky web sessions, NoSQL, memcache, REST

Non-Primary key: search, secondary indexes, full-text search

• Finding items by value, not by key
• Need for secondary indexes(e.g database indexes)
• Search on parts of a record
• Metadata search (data/time, etc)
• Full-text search
• May require substantially more work to build compared to PK-based access
• Usually slower than PK access for lookup

Range scans: ordering, iteration, bulk vs. single values, op<

• Requires ordering, i.e operator<, (ordering costs)
• Requires iterators/cursors/traversal state
• Seek then scan - first find is slow, then fast
• Dense linear access and prefetch
• Watch out for read/write amplification
• Bulk, not single record, access - may require bulk aggregate operations rather than N times single record operations for speed (DB N+1 problem)

R/W ratio: caching, cost of lookups vs. cost of updates

• Not all data in a system has similar R/W ratios
• e.g metadata is often read-heavy
• High reads
• caches are effective
• cache writethrough/back
• cache eviction policy
• cache coherency
• index structures useful
• High writes
• caches don't help much (except for metadata)
• locking overhead
• index structure require updating

Working set: how big is the commonly accessed set of data(RAM)

• How much of the common data will fit in main memory, the L1/L2/L3 cache
• Will the index structures fit but not the main data
• Index data tends to be 'HOT', main data may be 'COLD'
• Depends on data access patterns - 80/20 rule

Consistency: exact results vs. fast approximations, eventual consistency, replication, batched updates

• Do all copies of the data need to be exactly up-to-date right now
• ACID, 2-phase commit, centralised, locking, slow
• How often are copies updated
• Batch updates (e.g overnight)
• Data vs. metadata (transactions vs. reference data)
• ACID vs. BASE(eventual consistency)
• BASE allows for decoupled asynchronous systems

Read or write, pull or push?

• How to read a diagram?
• Is X reading Y or writing to it?
• Or both at different times?
• Is X pushing or Y pulling?
• Where is the THREAD of control?
• Is this a full batch update or a partial incremental change?
• Is this an asynchronous push (fire and forget) or a synchronous blocking call?
• When? Who? What?
• Horizontal dataflow thinking!

Full vs. incremental change

• Full changes allow the state to be reset on a regular basis
• Prevents build-up of errors or divergence from base data
• Slow, long latency, partial failure problems
• One big transaction
• Incremental changes are fast but don't guarantee to keep state changes synchronised
• lost messages because of unavailability
• transactionality only on each update

Lambda architecture

Reader/writer vs. data flow

• Readers and writers view hides inherent data flow in systems
• Split R and W into micro-services
  i.e Command Query Responsibility Segregation(CQRS)
• separates rules, performance,  scaling, access control, etc.
• Often W and R are very different
• W usually reads from somewhere

Sync vs. async systems

• ACID is hard to scale, partition, get right, can promote failures, makes for a more fragile system as everything has to be up all the time(brittle)
• 10 sync systems with 99% uptime => 90% uptime
• 10 async systems => 99% uptime for end system
• Can maybe delay writes or cover them up
  (lambda arch, i.e layer by layer)
• Reads are sync but recent data may be sufficient, particularly for metadata(caching helps lots!)

Data flow and sync/async

• Data flows can be point-to-point or broadcast
• Can be synchronous or asynchronous
• message queues provide simple sync intermediary
• flat file batch transfer is popular for a reason
• Queues can also be event stores with reread!!(RAFT)
• Makes queue reads idempotent

Content management example

• Keep two APIs separate
• security, clarity of purpose
• separation of concerns
• horizontal not vertical thinking!!

Larger example

• Data flow makes us think about where data comes from and goes to
• Who is actually going to read the data I'm writing?
• Micro-services may have two APIs for sending and receiving
• 'Vertical' thinking may lead to trying to fit both into one API

When? Who? What?

Horizontal dataflow thinking!

Command Query Representation Separation (CQRS)

• Need to change the data structure from the form that best suits the write API to the structure that best suits the read API
• Can be synchronous or asynchronous transformation
• Think as READ and WRITE separately

CQRS examples

• Structure change can be on read or on write
• Twitter does it on read for high-value users, not write
• Log-structured merge systems do this internally and asynchronously (e.g HBase, RocksDB)
• Other examples:
• time-series db
• event sourcing
• struct-of-arrays vs. array-of-structs(e.g non-OO, data oriented)
• Columnar analytics db(e.g BigQuery)

State management

• Read and write focus doesn't help manage state across a complex system
• State management needs to address:
• transactions vs. eventual consistency
• failure management
• availability and MTTR (Mean Time To Repair)
• MTBF(Mean Time Between Failure)
• immutability
• Align boundaries with failure and aggregate boundaries
• REST API: /resourceA/1/resourceB/2
• Fragmentation and transactionality problems

Failure management

• Distributed systems can suffer from partial failures on writes
• Writes in distributed are inherently concurrent
• Recovery and re-sync state is 'fun'
• Idempotent writes allow for replay and deduping
• Make deduping easy: serial number, timestamp, etc.
• Repeatable queues are useful (e.g Kafka, flat files)
• Check-pointing of known good state
• Point-in-time recovery
• Full vs. incremental update problem again

Bell-LaPadula and Biba models

• Bell-LaPadula: confidentiality
• Biba: integrity

You CANNOT have BOTH.

Immutability (makes things simpler)

• Functional programming languages have immutable data
• Make sharing and reasoning about data easier
• Russian Doll caching, MVCC
• Change the key not the value
• Pets vs. cattle - infrastructure
• SSA - compilers and CPI reservation stations
• Lambda architecture - immutable master data

Availability

• Availability = MTBF / (MTBF + MTTR)
  (where MTBF = mean time between failures
  MTTR = mean time to repair)
• Maximise software practices, hardware failover, reliable well-known technology choices
• Minimise MTTR by making systems easier to understand, debug and restart
• minimise state management(redo logs, fsck, etc)
• use immutability where possible

Read and write are too low level

• They don't help us to design or analyse systems
• they are the assembler-level of data (CRUD)
• They don't relate to the larger picture
• It is too easy to deal with them in isolation
• REST APIs are an all-too common example
• Looking at data flow, push vs. pull, sync/async, business processes, operational profiles, state management, etc. are much more fruitful approaches