TCP listening socket shared by2processes #mcast

Common IV question: In what scenarios can a listening socket (in memory) be shared between 2 listening processes?

Background — a socket is a special type of file descriptor (at least in unix). Consider an output file handle. By default, this “channel” isn’t shared between 2 processes. Similarly, when a packet (say a price) is delivered to a given network endpoint, the kernel must decide which process to receive the data, usually not to two processes.

To have two processes both listening on the same listening-socket, one of them is usually a child of the other. The webpage in [1] and my code in https://github.com/tiger40490/repo1/blob/py1/py/sock/1sock2server.py show a short python code illustrating this scenario. I tested. q(lsof) and q(ss) commands both (but not netstat) show the 2 processes listening on the same endpoint. OS delivers the data to A B A B…

https://bintanvictor.wordpress.com/2017/04/29/so_reuseport-socket-option/ shows an advanced kernel feature to let multiple processes bind() to the same endpoint.

For multicast (UDP only) two processes can listen to the same UDP endpoint. See [3] and [2]

A Unix domain socket can be shared between two unrelated processes.

See

[1] http://stackoverflow.com/questions/670891/is-there-a-way-for-multiple-processes-to-share-a-listening-socket

[2] http://stackoverflow.com/questions/1694144/can-two-applications-listen-to-the-same-port

[3] http://www.tldp.org/HOWTO/Multicast-HOWTO-2.html

Advertisements

joining/leaving a multicast group

Every multicast address is a group address. In other words, a multicast address identifies a group.

Sending a multicast datagram is much simpler than receiving…

[1] http://www.tldp.org/HOWTO/Multicast-HOWTO-2.html is a concise 4-page introduction. Describes joining/leaving.

[2] http://ntrg.cs.tcd.ie/undergrad/4ba2/multicast/antony/ has sample code to send/receive. Note there’s no server/client actually.

 

2 Active connections on 1 TCP server IP/port

This is not the most common design, but have a look at the following output:

remote          local        state
*:*           - 4.3.2.1:5000 LISTENING
1.2.3.4:12345 - 4.3.2.1:5000 CONNECTED
4.5.6.7:83247 - 4.3.2.1:5000 CONNECTED

What needs to be unique, is the 5-tuple (protocol, remote-ip, remote-port, local-ip, local-port)… so this situation can exist. [[tcp/ip sockets in C]] P100 has a full section on this topic.

http://stackoverflow.com/questions/11129212/tcp-two-different-sockets-sharing-a-port also says “Multiple worker-sockets on the same TCP server can share the same server-side IP/Port pair as long as they are associated with different client-side IP/Port pairs”. This “accept, move the connection to a dedicated server socket, then go back to accept()” is the common design — On each incoming connection, the listening TCP server will start a new thread/task/process  using a new “worker” socket on the server side. Note the new worker socket shares server ip:port with the original listening socket

https://github.com/tiger40490/repo1/blob/py1/py/sock/1sock2server.py is my experiment. It pushes the concept of “sharing” further  — two TCP serves sharing a single socket not just a single ip:port endpoint!

poll()as timer]real time C : industrial-strength #ST-mode

See also http://www.sourcexr.com/articles/2013/11/12/timer-notifications-using-file-descriptors

RTS Xtap (and earlier framework? probably) use a C timer based on the Linux syscall epoll(). It has millisecond precision [1], good enough for our real time feed parsers that consume all of NYSE, Nasdaq, OPRA etc. I won’t say how many clients we support, but some of the world’s top sites use our feeds.

There’s also a version using poll(). It’s used by default when epoll is unavailable, but linux supports epoll. For simplicity, I will say “poll” from now on.

[1] The millisec resolution is due to the tick length in Linux kernel, described on P 195 [[Linux kernel]]

I guess one advantage of poll() to implement timer is the integration with sockets. A parser is fundamentally event driven. Timer and socket are the two primary event sources.

It looks like the poll() syscalls are capable of supporting both requirements, together, which is our situation.

I call it “industrial-strength” solution because it has powered one of the most reliable, most widely used market data dissemination systems for decades, the unsung hero behind most of the financial data web sites. It has been in use for decades and handles 300 “exchanges feeds”

Concurrency? xtap is single-threaded mode. In the poll() solution, incoming packets AND timer events are inherently processed serially. No synchronization required. When the receiver socket is busy, timer events are .. delayed. Exactly what we want.

–The timer/event loop structure

while(1){ //pseudocode
  check_timers(); //roughly this gets called every 1 ms
  epoll_wait(timeout=1ms);
}

 

##study subjects I enjoyed as student(+professional)

(You don’t have to read this lengthy blog post.)

All my examples below required a long period of persistent effort. My son is unwilling to put in even 30% of my effort, so he wouldn’t find any enjoyment.

After the initial few hours of curiosity, learning any subject was always challenging, boring, or repetitive. The mental workload always wears us down, so we always needed conscious effort to stick to it I.e. stay focused and apply ourselves. The joy comes as a light at end of the tunnel. No exception.

In contrast, watching TV, playing electronic games, eating, sight-seeing, shopping … don’t require any effort. When we get bored with it, we are free to break away — there’s no measurable progress to worry so give-up has absolutely no consequence. We choose to stick to it (say, a game) only because we enjoy it. Therefore no effort required.

If a teenager takes on professional gaming as a paid job, he will invariably find it monotonous, repetitive, uninteresting, dull, tiring, before he can earn any money. Those gamers who do earn money are able to earn money precisely because they put up with the boring stuff — persistent effort.

— Now the study subjects I enjoyed, ranked by amount of effort:

I enjoyed blogging on technical subjects. My QnA interviews directly benefit from my blogging but this is not the biggest reason for the enjoyment. In fact, most of my technical blog content is not required for interviews. I can see my blog improving in quality (and quantity) as I revise and expand each article progressively. Blogging let’s me achieve deeper understanding on many tough topics like sockets, reflection, c++template, move-semantics, quant, complex SQL, … I call it "真本事". I then notice the superficial knowledge in fellow programmers, who studied only 20% of what I read.

I enjoyed memorizing English words, in my teenage years. I developed my own method. I was able to memorize 30 – 100 words a day for a few months (I refresh each word 20 to 40 times spaced out over 6 months). The fast progress was "breathtaking". Self-confidence grew. I actually learned some words my English-educated Singapore classmates didn’t know!

I enjoyed Chinese composition in my secondary Year 2-3, when I found my literary "voice", my style of writing. For about 2 years before that break-through, I was always in the bottom 10% in my class in terms of composition and every assignment was a pain like giving birth to a short, boring baby. The pain, self-despise, self-pity was one of the deepest in my childhood. I felt inadequate almost like crippled. The breakthrough was a liberation. I achieved it by writing daily essays for a few months. My output slowly improved from very dry, simple "流水账" to have some meaning, some color, some personality, some nice expressions. It became creative expression.

(Paradoxically, as a student I was very strong in math/physics, but I never had the same enjoyment as I had learning English and Chinese composition. I think my joy was in overcoming highly visible personal limitations — sense of breakthrough and liberation.)

I enjoyed piano playing after years of repetitive, boring, tough practice. In my life I never again put up with this much practice — 5000 repeated practices x 2 minutes/repetition in some cases.

2H life-changing xp#Pimco#income,home location,industry…

Here’s a real story in 2010 — I was completely hopeless and stuck in despair after my Goldman Sachs internal transfer was blocked in the last stage. I considered moving my whole family back to Singapore without any offer, and start my job search there. I was seriously considering a S$100k job in a back office batch programming job. Absolutely the lowest point in my entire career. After licking the would for 2 months, tentatively I started looking for jobs outside Goldman and slowly found my foothold. Then in early 2010, I passed a phone screening and attended a Citigroup “superday”. I spent half an hour each with 3 interviewers. By end of the day, recruiter said I was the #1 pick. I took the offer, at a 80% increment. In the next 12 months, I built up my track record + knowledge in

  1. real time trading engine components, esp. real time pricing engine
  2. fixed income math,
  3. c++ (knowledge rebuild)

I have never looked back since. Fair to say that my family won’t be where we are today, without this Citigroup experience. With this track record I was able to take on relatively high-end programming jobs in U.S. and Singapore. I was able to live in a convenient location, and buy properties and send my kids to mid-range preschools (too pricey in hind sight). Obviously I wanted this kind of job even in 2009. That dream became reality when I passed the superday interview. That interview was one of the turning points in my career.

Fast forward to Apr 2017 — I had a 20-minute phone interview with the world’s biggest asset management firm (Let’s call it PP), then I had a 2-hour skype interview. They made an offer. I discussed with my recruiter their proposal —

  • I would relocate to California
  • I would get paid around 200k pretax and possibly with an increment in 6 months. PP usually increase billing rate after 12 months if contractor does well.
  • recruitment agency CEO said he would transfer my visa and sponsor green card.

If I were to take this offer, my life would be transformed. (I would also have a better chance to break into the  high tech industry in nearby silicon valley, because I would have local friends in that domain.) Such a big change in my life is now possible because … I did well [1] in the interview.

Stripped to the core, that’s the reality in our world of contract programmers.  Project delivery, debugging, and relationship with boss can get you promoted, but those on-the-job efforts have much lower impact than your performance during an interview. Like an NBA playoff match. A short few hour under the spot light can change your life forever.

This is not a rare experience. There are higher-paying contract job offers that could “change your life”, and you only need to do well in the interviews to make it happen.

I feel this is typical of U.S. market and perhaps London. In Singapore. contract roles can’t pay this much. A permanent role has a few subtle implications so I feel it’s a different game.

[1] The 7 interviewers felt I was strong in c++ (not really), java and sql, and competent in fixed income math (I only worked with it for a year). Unlike other high-end interviews, there are not many tough tech questions like threading, algorithms, or coding tests. I feel they liked my interview mostly because of the combination of c++/java/fixed income math — not a common combination.

technical advantages of c# over java #XR

Hi XR,

Based on whatever little I know, here are some technical advantages of c# over java.

(Master these c# feature and mention them in your next java interview 🙂

  • C# has many more advantages on desktop GUI, but today let’s focus on server side.
  • [L] generics —- c# generics were designed with full knowledge of java/c++ shortcomings. Simpler than c++ (but less powerful), but more complete than java (no type erasure). For example see type constraints.
  • [L] delegates —- Rather useful. Some (but not all) of its functionalities can be emulated in java8.
  • [L] c# can access low-level windows concurrency constructs such as event wait handles. Windows JVM offers a standardized, “reduced-fat” facade. If you want optimal concurrency on windows, use VC++, or c#.
  • [L] reflection —- is more complete than java. Over the years java reflection proved to be extremely powerful. Not sure if c# has the same power, but c# surely added a few features such as Reflection.Emit.
  • concurrency —- dotnet offers many innovative concurrency features. All high level features, so probably achievable in java too.
  • tight integration with COM and MS Office. In fact, there are multiple official and unofficial frameworks to write Excel add-ins in c#
  • tight integration with high-level commercial products from Microsoft like MSSQL, sharepoint
  • tight integration with windows infrastructure like Windows Services (like network daemons), WCF, Windows networking, Windows web server, windows remoting, windows registry, PowerShell, windows software installation etc
  • c# gives programmers more access to low-level windows system API, via unmanaged code (I don’t have examples). In contrast, Java programmers typically use JNI, but I guess the java security policy restricts this access.
  • probably higher performance than JVM on windows
  • CLR offers scripting languages VB.net, F#, IronPython etc, whereas JVM supports scripting languages javascript, scala, groovy, jython etc.

[L = low-level feature]

If you want highest performance on Windows, low-level access to windows OS, but without the complexity of VC++ and MFC, then c# is the language of choice. It is high-level, convenient like java but flexible enough to let you go one level lower when you need to.

Another way to address your question — listen to the the complaints against java. (Put aside the complaints of GUI programmers.)

Even if a (rational, objective) architect doesn’t recognize any of these as important advantages, she may still favor c# over java because she is familiar and competent ONLY in the Microsoft ecosystem. She could point out countless features in Visual Studio and numerous windows development tools that are rather different from the java tool set, so different that it would take months and years to learn.

Also, there are many design trade-off and implementation techniques built on and for Dotnet. If she is reliant on and comfortable in this ecosystem, she would see the java ecosystem as alien, incomplete, inconvenient and unproductive. Remember when we first moved to U.S. — everything inconvenient.

On a more serious note, her design ideas may not be achievable using java. So java would appear to be missing important features and tools. In a nutshell, for her java is a capable and complete ecosystem theoretically, but in practice an incomplete solution.

%%offers 2017

All confirmed offers.

$c2c co where primary tech other tech domain nlg duration
100 pimco Burak NPB[1] c++11 🙂 🙂 🙂 java, possibly Hadoop 🙂 FI accrual math 🙂 3+
100 Pimco Zoltan NYC java framework 🙂 🙂 flexible
100+ bgc Alexi NYC java minimal cpp FX.. trading to perm 😦 😦 😦
below 100 😦 😦 Ravi Chgo 😦 😦 Qz 😦 😦 😦 java FI trading again flexible
perm Nitin Shanghai java perm
perm Tradeweb JC VC++ FI ECN perm
85 baml NYC VC++ repo 😦 12M?

[1] A bit hard to get next job in NY, but helps me get a next job in West Coast. However, in terms of buying a home, I just don’t know.

global^file-scope variables]c++ #extern

(Needed in coding tests and GTD, not in QnA interviews.)

Any object declared outside a block has “static duration” which means (see MSDN) “allocated at compile time not run time”

“Global” means extern linkage i.e. visible from other files. You globalize a variable by removing “static” modifier if any.

http://stackoverflow.com/questions/14349877/static-global-variables-in-c explains the 2+1 variations of non-local object. I have added my own variations:

  • A single “static” variable in a *.cpp file. “File-scope” means internal linkage i.e. visible only within the file. You make a variable file-scope by adding “static”.
  • an extern (i.e. global mutable) variable — I used this many times but still don’t understand all the rules. Basically in one *.cpp it’s defined, without “static” or “extern”. In other *.cpp files, it’s declared (via header) extern without a initial value.
  • A constant can be declared and defined in one shot as a static (i.e. file-scope) const. No need for extern and separate definition.
  • confusing — if you (use a shared header to) declare the same variable “static” in 2 *.cpp files, then each file gets a distinct file-scope mutable variable of the same name. Nonsense.

https://msdn.microsoft.com/en-us/library/s1sb61xd.aspx

http://en.wikipedia.org/wiki/Global_variable#C_and_C.2B.2B says “Note that not specifying static is the same as specifying extern: the default is external linkage” but I doubt it.

I guess there are 3 forms:

  • static double — file-scope, probably not related to “extern”
  • extern double — global declaration of a var already Defined in a single file somewhere else
  • double (without any modifier) — the single definition of a global var. Will break ODR if in a shared header

Note there’s no special rule about “const int”. The special rule is about const int static FIELD.

//--------- shared.h ---------
#include 
#include 
void modify();

extern std::string global; //declaration without storage allocation
static const int fileScopeConst1=3; //each implementation file gets a distinct copy of this const object
static double fileScopeMutable=9.8; //each implementation file gets a distinct copy of this mutable object
//double var3=1.23; //storage allocation. breaks compiler due to ODR!

// ------ define.C --------
#include "shared.h"
using namespace std;
string global("defaultValue"); //storage allocation + initialization
int main(){
  cout<<"addr of file scope const is "<<&fileScopeConst1<<std::endl;
  cout<<"addr of global var is "<<&global<<std::endl;
  cout<<"before modify(), global = "<<global<< "; double = "<<fileScopeMutable<<endl;
  modify();
  cout<<"after modify(), global = "<<global<< "; double (my private copy) = "<<fileScopeMutable<<endl;
}
// ------ modify.C --------
#include "shared.h"
void modify(){
  global = "2ndValue";
  fileScopeMutable = 700;
  std::cout<<"in modify(), double (my private copy) = "<<fileScopeMutable<<std::endl;
  std::cout<<"in modify(), addr of file scope const is "<<&fileScopeConst1<<std::endl;
  std::cout<<"in modify(), addr of global var is "<<&global<<std::endl;
}

##NYSE in/out data feeds

Good knowledge for my interviews ..

Incoming feeds from NYSE, Bats etc, since they all contribute to the CTS/CQS.

–outgoing [1=Level1…]

  • NYSE Bonds feed — TCP
  • [2] NYSE classic/American/Arca openbook,
  • [12] NYSE classic/American/Arca integrated
  • [1] NYSE (containing classic/American/Arca) BQT i.e. Best-Quote-n-Trade
  • [1] NYSE RealTime-Reference-Prices, last updated 2012
  • NYSE-Trades
  • NYSE-Alerts
  • [2] NYSE-MKT-openbook-ultra is new as of 2018
  • NYSE-Arca-bond-trade
  • NYSE-Arca-bond-quote
  • CTS/CQS

## 5 idioms of python (vs other dynamic lang)

I feel elegant techniques/idioms are usually non-OO, because OO code is too verbose to write quickly.

I feel best-practice cookbooks would showcase the most useful idioms.

# I feel perl is the first language to put the “hash” on center stage, as the most versatile apparatus (or “construct”). Ditto in Python. I guess the same data structure is at the heart of py/perl/javascript OO

# list comprehension and generator expressions. Until you start thinking in terms of these constructs, you aren’t truly a python practitioner.

# list processing functions — map() reduce() filter() zip(). I feel these are very popular in real  projects.

# decorators

PIMCO(accrual account`)c++/java/sql IV

Q: (no good answer) You said users sometimes don’t know what they are requesting so their requirements actually don’t make sense. We as developers need good knowledge to discuss with them and solve the problem, not just take their instructions. Give an example where you challenged a user to understand better what she wants and then proposed a solution that better solves her problem.

Q: bond with sinking fund provision?

Q: suppose you bought at $104.5 with the $4.5 premium (or discount), how do you amortize that amount over the remaining 23 years of the bond? I guess the book value changes over time unlike stocks.

Q: compare a stock and a bond on the same company
%%A: coupon payments follow a predetermined schedule, not discretionary
%%A: bond has an end of life
%%A: future cashflow of the bond is known in advance
%%A: creditor vs partial owner, in the event of bankruptcy
A: bonds (esp. long-duration bonds) are more sensitive to interest rate changes

Q: what’s a bullet bond?
AA: Most bonds repay the principal as a single payment at the end of its maturity, which is known as a bullet payment. For this reason, conventional bonds are also known as bullet bonds. Amortizing bonds, on the other hand, repay the principal over a series of payments rather than all at once on the maturity date, so some or all of the periodic payments will consist of both interest and principal.

Q: how would you describe OO to a procedural programming student
%%A: use a real yet simple example like students/projects/grades/classes/labs/semesters/events/teams to illustrate the essential OO features

Q: how would you describe the spring framework?

q: java vs c++ for a concurrency system like a basic consumer/producer design?

q: java vs c++ for hadoop

%%Q: could I say std::transform() is a swiss army knife?

Q: a SAM interface in c++? Makes sense?

q: describe factory method pattern in c++?

q: bridge pattern implemented in pimpl?

q: can you use scoped_ptr or unique_ptr as class fields?
%%a: scoped doesn’t make sense
AA: wrong interpretation of “scope”. It can be a class field!

q: enable_shared_from_this ? I guess this has to do with the common scenario of two shared_ptr “clubs” each thinking it has sole ownership of a raw pointer

q: how do you declare an interface in c++?
%%A: no field. All methods are pure virtual. No ctor but dtor should be virtual

q: if you don’t declare a copy ctor what does the default copy ctor do?
%%A: bit-wise copy

q: can move ctor be synthesized if you don’t declare one?
%%A: some times it can, but I don’t think it’s always possible.
AA: Correct. for some classes, the standard forbids synthesized move ctor

q: what’s martingale
%%a: a process whose expected value at any future time is equal to the last realized or observed value. No drift.

q: what’s hitting time
%%a: expected time the process will hit a certain level

q: what if my join query produces duplicates, and those tables I join are not my table so I can’t redesign them?
%%a: use distinct or order by.
A: now I think it can happen if you select nothing but “gender”

q: what access modifiers can apply to a java interface?
%%a: private and protected doesn’t make sense. If it’s only used within a package and should not be exposed outside, then the default access may do.
AA: correct

big4 of a payload object in a std::vector

There are various claims on what specific big4 requirements a vector would impose on the payload objects.

Q: can no-arg ctor be private?
%%A: I doubt it. I remember [[essential c++]] or another well known author said when you create a vector or array of N instances, those instance are default-constructed.

Q: Can copy ctor be deleted or private?
AA: No. Reallocation requires copy ctor

Q: can dtor be private?
%%A: No. At reallocation time, old instances must be destructed.

[[optimized c++]] introduced the unofficial, unenforceable "framework" of value object vs entity object. Vector obviously hold value objects, so by right they should be copyable, with no shared ownership.

c++nested class accessing host private member

Recurring in stupid on-line MCQ interviews!

P185 ARM says a nested class NC can access static members of the enclosing class EC, and also local types of EC, all without fully qualified name.

However, NC can’t access EC’s non-static members. Java took a bold departure.

In c++11, a nested class is an implicit friend of the enclosing class. See https://stackoverflow.com/questions/5013717/are-inner-classes-in-c-automatically-friends

stale (replicated) orderbook

This page is intended to list ideas on possible ways of improving the orderbook replication system so that it can better determine when an instrument or instruments are stale. It further lists possible ways of automating retransmission of lost and/or stale data to improve the recovery time in the event of an outage.

The current system is largely “best effort”; at each level of the ticker-plant and distribution network components are capable of dropping data should a problem arise. There are few processes capable of correlating what was lost in a format that is useful to a customer. To account for the possibility of lost data, the orderbook replication components constantly generates “refresh” messages with the most up-to-date state of an instrument.

Although this system works well in practice, it leaves open the possibility that a customer may have a cache with “stale” data for an unbounded length of time. This inability to track staleness can be a point of concern for customers.

= Recovery types =

When a downstream component loses one or more update messages for an instrument it is generally safe to assume the instrument is stale. However there can be two different kinds of recoveries:

== Retransmit the latest snapshot ==

This method of retransmission and stale detection revolves around keeping the current tick snapshot database up to date. It is useful for customers that need an accurate tick cache. It may not be a full solution to customers that need an accurate time and sales database.

== Retransmit all lost ticks ==

It is also possible to retransmit all lost ticks after an outage. This is typically useful when trying to repair a time-and-sales database.

Although it is possible to build an accurate “current” snapshot record when all lost ticks are retransmitted, it is a very tedious and error-prone process. It is expected that customers will, in general, be unwilling to rebuild the “current” from the retransmission of lost ticks.

So, a scheme that involves retransmission of lost ticks will still likely require a scheme that retransmits the latest snapshot.

Most of the following discussions are centered around the concept of latest snapshot recovery.

= Gap prevention =

There may be simple ways to reduce the number of times gaps occur. This process could be called “gap prevention”.

In general, it is not possible to eliminate gaps, because severe outages and equipment failure can always occur. The process of gap prevention may be useful, however, where the alternative gap recovery solution is expensive or undesirable. It is also useful in systems that need full lost tick recovery.

There are two possible ways of preventing gaps from occurring. Both trade bandwidth and latency for increased reliability during intermittent outages.

== Wait for retransmit ==

The simplest form of gap prevention involves retransmitting any packets lost on the network. The sender keeps a buffer of recently sent messages, and the receiver can request retransmissions. In the event of packet loss, the receiver waits for the retransmissions before processing data.

This form of gap recovery is a basic feature of the TCP/IP transmission protocol.

== Forward error correction ==

It is also possible to prevent gaps by sending additional data on the feed.

The most basic form of this is used in the “best-of-both” system. It sends two or more copies of the data, and the receiver can fill lost ticks from the additional copies.

It is not necessary to send a full additional feed. For example, one could send a block of parity codes on every tenth packet. A receiver could then theoretically recover from up to ten percent packet loss by using the parity code packets.

Although the forward error correction scheme uses additional bandwidth, additional bandwidth may be available due to line redundancy.

= Snapshot recovery types =

In order to correct a stale instrument, it may be necessary to send the full contents of the instrument. When doing so, one may send them serialized in the real-time feed or out of order.

== In sequence snapshots ==

The simplest form of snapshot transmission involves using the same socket or pipe as the real-time feed itself. In this case, the receiver can simply apply the snapshot to its database; it does not need to handle the cases where the snapshot arrives after/before a real-time update arrives.

The downside of this scheme, however, is that a single upstream supplier of snapshots might get overloaded with requests for retransmissions. If additional distributed databases are used to offload processing, then each additional component will add latency to the real-time feed.

== Out of sequence snapshots ==

It is also possible to send snapshot transmissions using sockets and/or pipes separate from the real-time feed. The advantage of this scheme, is it is relatively cheap and easy to increase the number of distributed snapshot databases from which one can query. However, it requires the receiver of the snapshot to work harder when attempting to apply the response to its database.

One way to apply out of order snapshots is to build a “reorder buffer” into the receiver. This buffer would store the contents of the real-time feed. When a snapshot response arrives, the receiver could locate where the sender was in the real-time stream when it generated the snapshot (possibly by using sequence numbers). It can then apply the snapshot and internally replay any pending updates from the reorder buffer. In the case where a snapshot arrived that was based on real-time traffic that the receiver has yet to receive, the receiver must wait for that traffic to arrive before applying the snapshot.

This scheme is thought to be complex, resource intensive, and error-prone.

If, however, the feed were changed to eliminate the distributed business rules, it may be possible to implement a much simpler out-of-order snapshot application system. See [[Out of sequence snapshots idea]] for a possible implementation.

= Gap detection =

In order to accurately determine when an instrument is “stale”, it is necessary to be able to determine when one or more update messages have been lost. The following sections contains notes on various schemes that can provide this information.

Note that some of the schemes may be complementary. That is, a possible future solution might use parts of several of these methods.

== Sequence numbers with keep-alive on idle ==

The most common method to detect a gap involves placing a monotonically incrementing number on all outgoing messages or message blocks. The receiver can then detect a gap when a message (or message block) arrives with a sequence number that is not one greater than the last sequence number.

In order to account for the case where all messages from a source are lost, or where a source goes idle just after a message loss, the sender needs to arrange to transmit a “keep alive” indicator periodically when the source is otherwise idle. With knowledge of the keep-alive period, the receiver can detect a gap by timing out if it does not receive a message from a source within the specified period. The larger the period, the less keep-alive messages need to be sent when idle. However, it also increases the worst case time to detect a message gap.

It is possible for the sender to generate multiple sequence number series simultaneously by separating instruments into multiple categories. For example, the outgoing feed currently generates an independent sequence number for each “exchange”. At the extreme, it is possible to generate a sequence number stream per instrument; however this would increase the bandwidth due to larger number of keep-alive messages necessary. (One would also not be able to optimize bandwidth by sequencing only message blocks.)

When a sequence number gap is detected, the receiver must consider all instruments using the sequence series as suspect.

Only a single source can reliably generate a sequence number. If multiple ticker-plants generate a feed, they need to use different sequence series. If an upstream ticker-plant switch occurs, the receiver needs to mark the full range of affected instruments as suspect.

Finally, some exchanges provide sequenced data feeds. However, there are [[issues with exchange provided sequence numbers]]. Due to this, it may be difficult to rely on exchange sequencing as a basis for a distribution network sequencing.

== Sequence number of last message ==

A variant of the basic sequencing scheme involves the sequence number of the last message (SNLM) that updates an instrument. This field would be kept by both sender and receiver, and included with real-time messages. If SNLM matches the receiver’s record, implying that the receiver has not missed any updates for this instrument, then the instrument can transition from “suspect” to “clean”. Conversely, a non-match should force the instrument to “stale”.

An advantage of this scheme is that ordinary real-time traffic could reduce the number of suspect records after an outage. It may also make using exchange provided sequence numbers more practical.

As a disadvantage, however, it would require that both a sequence number and SNLM be provided on every real-time update. This might significantly increase bandwidth.

== Periodic message count checks ==

It is also possible to detect gaps if the sender periodically transmits an accounting of all messages sent since the last period. This scheme may use less bandwidth than sequence numbers, because it is not necessary to send a sequence number with every message (or message block).

The scheme still has the same limitations as sequence numbers when ticker-plant switches occur and when trying to determine what was lost when a gap occurs.

== Periodic hash checks ==

Another possible method of detecting gaps is by having the sender generate a hash of the contents of its database. The receiver can then compare the sender’s hash to the same hash generated for its database. If the two differ, a gap must have occurred. (If the two match, however, a gap may have occurred but already been corrected; this method is therefore not useful when full tick recovery is necessary.)

This scheme may be beneficial when ticker-plant switches occur. If two senders have identical databases and no data is lost during a network switch, then the hash checks should still match at the receiver. This scheme, however, still faces the problem of determining which instruments from the set are actually stale when a gap is detected.

Technically, it is possible that two databases could differ while sharing the same hash key. However, it is possible to choose a hash function that makes the possibility of this extremely small.

Finally, this system may face challenges during software upgrades and rollouts. If either the sender or the receiver change how or what they database, it may be difficult to maintain a consistent hash representation.

== Sender tells receiver of gaps ==

If a reliable transmission scheme (eg, tcp) is in use between the sender and receiver, then it may be possible for the sender to inform the receiver when the receiver is unable to receive some portion of the content.

For example, if a sender can not transmit a block of messages to a receiver because the receiver does not have sufficient bandwidth at the time of the message, then it is possible for the sender to make a note of all instruments that receiver was unable to receive. When the receiver has sufficient bandwidth to continue receiving updates, the sender can iterate through the list of lost instruments and inform the receiver.

The scheme has the advantage that it allows the receiver to quickly determine what instruments are stale. It may also be useful when a component upstream in the ticker-plant detects a gap – it can just push down the known stale messages to all components down-stream from it. (For example, an exchange parser might detect a gap and send a stale indicator downstream while it attempts to fill the gap from the exchange.)

As a disadvantage, it may significantly complicate data senders. It also does not help in cases where a receiver needs to change to a different sender.

== Receiver analyzes gapped messages ==

In some systems, the receiver may need to obtain all lost messages (eg, to build a full-tick database). If the receiver knows the contents of messages missing earlier in the stream it can determine which messages are stale. Every instrument that contains an update message in the list of missing messages would be stale; instruments that did not have update messages would be “clean”.

An advantage of this system is that it is relatively simple to implement for receivers that need full tick retransmissions.

However, in the general case, it is not possible to implement full tick retransmissions due to the possibility of hard failures and ticker-plant switches. Therefore this scheme would only be useful to reduce the number of stale instruments in certain cases.

Also, the cost of retransmitting lost ticks may exceed the benefits found from reducing the number of instruments marked stale. This makes the scheme less attractive for receivers that do not need all lost ticks retransmitted.

= Stale correction =

This section discusses possible methods of resolving “suspect conditions” that occur when it is detected that an instrument may have missed real-time update messages.

There are likely many other possible schemes not discussed here. It is also possible that a combination of one or more of these schemes may provide a useful solution.

These solutions center around restoring the snapshot database. Restoration of a tick history database is left for a separate discussion.

== Background refresh ==

The simplest method of clearing stale records is to have the ticker-plant generate a periodic stream of refresh messages. This is what the system currently does.

This system is not very good at handling intermittent errors, because it could take a very long time to refresh the full instrument database. However, if enough bandwidth is allocated, it is a useful system for recovering from hard failures where the downstream needs a full refresh anyway. It is also possible to combine this with one of the gap prevention schemes discussed above to help deter intermittent outages.

Advantages:

* simple to implement at both receiver and sender

Disadvantages:

* time to recovery can be large

* can be difficult to detect when an instrument should be deleted, or when an IPO should be added

== Receiver requests snapshot for all stale instruments ==

In this system, the receiver would use one of the above gap detection mechanisms to determine when an instrument may be stale. It then issues a series of upstream requests until all such instruments are no longer stale.

In order to reduce the number of requests during an outage, the instruments on the feed could be broken up into multiple sets of sequenced streams (eg, one per exchange).

Advantages:

* could lead to faster recovery when there is available bandwidth and few other customers requiring snapshots

Disadvantages:

* could be complex trying to request snapshots for instruments where the initial create message is lost

Notes:

* see discussion on [[#Snapshot recovery types]]

* see discussion on [[#Gap detection]] for possible methods of reducing the universe of suspect instruments during an outage

== Sender sends snapshots ==

This is a variant of [[#Sender tells receiver of gaps]]. However, in this scheme, the sender would detect a gap for a receiver and automatically send the snapshot when bandwidth becomes available. (It may also be possible to send only the part of the snapshot that is necessary.)

Advantages:

* Simple for receiver

Disadvantages:

* Could be complex for sender

* Isn’t useful if receiver needs to change upstream sources.

== Receiver requests gapped sequences ==

This method involves the receiver detecting when an outage occurs and making an upstream request for the sequence numbers of all messages (or message blocks) not received. The sender would then retransmit the lost messages (or blocks) to the receiver.

The receiver would then place the lost messages along with all subsequently received messages into a “reorder” buffer. The receiver can then internally “play back” the messages from the reorder buffer to rebuild the current state.

Advantages:

* Useful for clients that need to build full-tick databases and thus need the lost messages anyway.

Disadvantages:

* Thought to be complex and impractical to implement. The reorder buffer could grow to large sizes and might take significant resources to store and apply.
* The bandwidth necessary to retransmit all lost messages may exceed the bandwidth necessary to retransmit the current state of all instruments.
* Doesn’t help when a ticker-plant switch occurs.

== Sender analyzes gapped sequences ==

This scheme is a variant on [[#Receiver requests gapped sequences]]. The receiver detects when an outage occurs and makes an upstream request for the sequence numbers of all messages (or message blocks) not received.

Upon receipt of the request the sender would generate a series of snapshots for all instruments that had real-time updates present in the lost messages. It can do this by analyzing the contents of the messages that it sent but the receiver did not obtain. The sender would also have to inform the receiver when all snapshots have been sent so the receiver can transition the remaining instruments into a “not stale” state.

Advantages:

* May be useful in conjunction with gap prevention. That is, the sender could try resending the lost messages themselves if there is a good chance the receiver will receive them before timing out. If the receiver does timeout, the sender could fall back to the above snapshot system.

* May be simple for receivers

Disadvantages:

* May be complicated for senders
* Doesn’t help when a ticker-plant switch occurs.

Notes:

* Either in-sequence or out-of-sequence snapshot transmissions could be used. (See [[#Snapshot recovery types]] for more info.) The receiver need not send the requests to the sender – it could send them to another (more reliable) receiver.

== Receiver could ask if update necessary ==

This is a variant of [[#Receiver requests snapshot for all stale instruments]], however, in this system the receiver sends the sequence number of the last message that updated the instrument (SNLM) with the request. The sender can then compare its SNLM with the receiver’s and either send an “instrument okay” message or a full snapshot in response.

Advantages:

* Reduces downstream bandwidth necessary after an outage

Disadvantages:

* Doesn’t work well in cases where instruments are updating, because the receiver and sender may be at different points in the update stream
* Lost create messages – see disadvantages of [[#Receiver requests snapshot for all stale instruments]]

== Receiver could ask with hash ==

This is a variant of [[#Receiver could ask if update necessary]], however, in this system the receiver sends a hash value of the current instrument’s database record with the request. The sender can then compare its database hash value with the receiver’s and either send an “instrument okay” message or a full snapshot in response.

Advantages:

* Works during tp switches

Disadvantages:

* Doesn’t work well in cases where instruments are updating, because the hash values are unlikely to match if sender and receiver are at a different point in the update stream.

* Rollout issues – see [[#Periodic hash checks]]

* Lost create messages – see disadvantages of [[#Receiver requests snapshot for all stale instruments]]

= Important considerations =

In many stale detection and correction system there are several “corner cases” that can be difficult to handle. Planning for these cases in advance can simplify later development issues.

The following is a list of “corner cases” and miscellaneous ideas:

== Ticker plant switches ==

It can be difficult to handle the case where a receiver starts obtaining messages from a different ticker-plant. Our generated sequence numbers wont be synchronized between the ticker-plants. Many of the above schemes would need to place any affected instruments into a “suspect” state should a tp switch occur.

Even if one could guarantee that no update messages were lost during a tp switch (for example by using exchange sequence numbers) there might still be additional work. The old ticker-plant might have been sending incorrect or incomplete messages — indeed, that may have been the reason for the tp switch.

== Lost IPO message ==

When the real-time feed gaps, it is possible that a message that would have created a new instrument was lost. An automatic recovery process should be capable of recovering this lost information.

There are [[schemes to detect extra and missing records]].

== Lost delete message ==

Similar to the IPO case, a real-time gap could have lost an instrument delete message. An automatic recover process should be able to properly handle this.

A more strange, but technically possible situation, involves losing a combination of delete and create messages for the same instrument. The recovery process should be robust enough to ensure that full resynchronization is possible regardless of the real-time message update content.

There are [[schemes to detect extra and missing records]].

== Exchange update patterns ==

Some exchanges have a small number of instruments that update relatively frequently (eg, equities). Other exchanges have a large number of instruments that individually update infrequently, but have a large aggregate update (eg, US options).

Schemes for gap detection and correction should be aware of these differences and be capable of handling both gracefully.

== Orderbooks ==

Recovering orderbooks can be a difficult process. However, getting it right can result in dramatic improvements to their quality, because orderbooks are more susceptible to problems resulting from lost messages.

The key to getting orderbooks correct is finding good solutions to all of the above corner cases. Orderbooks have frequent record creates and deletes. They also have the peculiar situation where some of the orders (those at the “top”) update with very high frequency, but most other orders (not at the “top”) update very infrequently.

== Sources can legitimately idle ==

Many exchanges follow a pattern of high traffic during market hours, but little to no traffic on off hours. Ironically, the traffic near idle periods can be extremely important (eg, opens, closes, deletes, resets).

It is important to make sure a detection scheme can handle the case where a gap occurs around the time of a legitimate feed idle. It should also be able to do so in a reasonable amount of time. (An example of this is the “keep alive” in the above sequence number scheme.)

== Variations of stale ==

A record is sometimes thought to be either “clean” or “stale”. However, it is possible to graduate and/or qualify what stale means. That is, it is possible to be “suspect” or “suspect for a reason” instead of just being “stale”.

Possible per-instrument stale conditions:

  • ; clean : the instrument is not stale
  • ; possible gap : gap in sequence number that could affect many instruments
  • ; definite gap : some recovery schemes can determine when an instrument has definitely lost updates
  • ; upstream possible gap : the tp might have seen a sequence gap from the exchange
  • ; upstream definite gap : the tp might have deduced which instruments actually gapped from exchange
  • ; stale due to csp startup : the csp was recently started and has an unknown cache state
  • ; suspect due to tp switch : a ticker-plant switch occurred
  • ; pre-clean : possible state in out-of-order snapshot recovery schemes
  • ; downstream gap : in some schemes a sender can inform a receiver that it lost updates

## RDBMS performance boostS to compete with noSQL

  • In-memory? I think this can give a 100X boost to throughput
  • memcached? “It is now common to deploy a memory cache server in conjunction with a database to improve performance.”, according to [1]. Facebook has long publicized their use of memcached.
  • most important indices are automatically cached
  • mysql was much faster than traditional RDBMS because no ACID transaction support

[1] https://community.rackspace.com/products/f/data-services/7379/comparing-relational-databases-memory-cache-and-nosql-databases says

Single-Threaded^STM #jargon

SingleThreadedMode means each thread operates without regard to other threads, as if there’s no shared mutable data with other threads.

Single-Threaded can mean

  • no other thread is doing this task. We ensure there’s strict control in place. Our thread still needs to synchronize with other threads doing other tasks.
  • there’s only one thread in the process.

q[grep]-F -o -P -r -C –color

-P

Use perl regex. Absolutely necessary if you want non-greedy match like .*?

Without -P, the question mark would be treated as literal.

-F, –fixed-strings

Interpret PATTERN as a list of fixed strings, separated by new-lines, any of which is to be matched. See http://stackoverflow.com/questions/3242873/grep-for-literal-strings for examples. Useful if your needle contains meta-characters you want to treat as literals

-x, –line-regexp

Select only those matches that exactly match the whole line.

-o … output only the matched substring.

-C … context

-r … recursive

Does inline really make a difference@@ Yes

MSVS and g++ debug build both disable inline (presumably to ease debugging). The performance difference vis-a-vis release build is mostly due to this single factor, according to [[optimized c++]]

The same author asserts that inlining is probably the most powerful code optimization.

Stroustrup singled out inline as a key feature of c++.

In his low-latency seminar, Martin Thompson also quoted a computer scientist saying “Inline is THE optimization”.

Pimpl effectively disables inline.

However, c++faq gives many reasons for and against inline.

SDI: design Uber

Q: Design Uber or Lyft (a ride sharing service)

While designing a ride-sharing service, discuss things like:

  • The most critical use case — when a customer requests a ride and how to efficiently match them with the nearby drivers?
  • How to store millions of geographical locations for drivers and riders who are always moving.
  • How to handle updates to driver/rider locations (millions of updates every second)? Comparable to market data systems, but less latency sensitive.
  • How to scale out (or scale up)?
  • What data store? See below
    • sharding policy? by location?
  • Any MOM?
  • Any multicast?
  • Any queuing/buffering? I doubt it.
  • –secondary features
  • payment? I feel is less challenging in terms of performance and data volume. It’s like a post-trade system.

–minimize location update messaging volume

If a rider app is in the background, then the location should not be monitored. Server would ignore any location data on this rider. When a rider app goes foreground, then a rider is possibly looking at the Uber app screen, then the app will send a msg to the server and server will start tracking its location.

Driver would log in to start receiving requests.  we can log her out after a timeout like not responding to any requests, or staying background. By default, we could log out a driver after a configured time. Driver app can also have a feature to stay always-on.

Driver location updates should be 10 times more frequent than rider.

–Data store for driver movement (static data will go to a separate, slower data store)

Let’s stick to something we know well — RDBMS. I feel a single big database is enough for any country including U.S. A traditional SQL table can hold 200 million rows (drivers) easily and support concurrent updates like

  • location update — most common, perhaps 10 times/minutes for each driver
  • driver logout, when she decides not to receive booking requests
  • driver login

(It’s possible to upgrade to a in-memory database or a noSQL.)

We need to have at least an index on DriverId and an index on Location i.e. latitude/longitude/zipcode

RTS c++IV

One of the less challenging (but not easy) c++ interviews. No coding test.

  • Q: what editors do you use in your current c++ project
  • Q: function returning pointer to a local object — spot the bug and to fix it.
  • Q: implement a simple singleton class.
  • Q: something about overflow in integer data types
  • Q: non-virtual member function inherited by subclass but problematic when you call it on a subclass instance. It can’t access the subclass field
  • Q: spot the memory leak
  • Q: swap 2 integer variables without using a temp variable.
  • Q: implement sqrt(int) without using the math library.

generate paths in ternary matrix #Promethean TomJerry

–Requirement:

Similar to binary-matrix cluster count #DeepakM #DST+fullScan but the connection is modeled differently.

–Original requirements: Input matrix has an object in each cell

  • 1 means wall or barrier
  • 0 means passage
  • 2 means cheese station

Jerry is [x][y]. Tom starts at [0][0] and must collect all cheese and deliver to Jerry. Find shortest path. Tom can only move one (U/D/L/R) step at a time.

https://github.com/tiger40490/repo1/blob/cpp1/cpp1/2d/TomJerry.cpp is my half-finished code. It builds a graph connecting all the cells (each a Node object). It’s able to check feasibility. Todo:

  • breadth-first walk from Tom to Jerry, without revisiting any node. Hopefully we can discover all possible paths (i.e. collecting all cheese)
  • determine the shortest.

 

tokens shared among friends #Promethean

See also NxN matrix for graph of N nodes

Requirement: There are N friends numbered from 1 to N. There are M pairs of links, where each (x , y ) pair is connected by a shared integer token described by tokenId. Any two friends, x and y , can be connected directly by multiple tokens, or indirectly (without directly shared token) because if friends x and y share token t and friends y and z also share token t , then x and z are also said to share token t.

Note if x/y shares t and u/v share t, then x and u may be unconnected!

Find the maximal product of x and y for any directly or indirectly connected (x , y ) pair such that x and y share the maximal number of tokens with each other. If x/y have 3 tokens connecting them, and u/v also have 3 tokens, then we compare x*y vs u*v.

https://github.com/tiger40490/repo1/blob/cpp1/cpp1/miscIVQ/tokenLinked_Friend.cpp showcasing nested containers like map<int, list<set<int>>>. I believe STL is harder than java, python etc.

c++base class method accessing subclass field #RTS IV

Surprisingly, the non-virtual base class method can Never know that it’s actually operating within a subclass instance. It always behaves as a strictly-baseclass method and can’t access subclass data. The non-virtual method getId() is compiled into base class binary, so it only knows the fields of the base class. When a subclass adds a field of the same name, it is not accessible to the getId(). A few workarounds:

  1. curiously recurring template pattern
  2. virtual function in subclass
  3. down cast the pointer and directly access the field
#include <iostream>
using namespace std;
struct B {
	char id = 'B';
	virtual ~B() {}
	char getId() {
		return id;
	}
} b;
struct C: public B{
	char id = 'C';
} c;
int main() {
	B* ptr = new C();
	C* ptr2 = dynamic_cast<C*>(ptr);

	cout << "base class nonref: " << b.getId() << endl;
	cout << "sub class nonref: " << c.getId() << endl; //still base class method. 
	// The fact that host object is subclass doesn't matter.

	cout << "base class ptr to subclass instance: " << ptr->getId() << endl; 
	cout << "downcast ptr non-virtual method: " << ptr2->getId() << endl; //B
	cout << "downcast ptr direct access: " << ptr2->id << endl; //C
	return 0;
}

 

big bright world behind heavy door

(Was so hard to get over U.S. barriers in the form of h1b and later GC …)

Was so hard to overcome the English barrier[1] … I struggled so very hard. Slowly I was able to express myself, with a barely enough vocab…. Once the door cracked open, I got my first glimpse of a big, bright world[1] Behind the door. Immediately I could see myself thriving in that world.

With a safe retreat always available, there’s no real risk [2] to me so I boldly jumped in as soon as possible.

So which items in the 5advantages post make the “big bright world”? Biggest item is Job pool i.e. the age-friendly and huge job pool with premium salary + lower stress.

[1] Some people don’t need English and can do well using Chinese as primary language … I’m different.
[2] there’s indeed some risk to wife and to kids…

I know more c++than c#(spent X years full time)

Action: spend enough (30?) hours revisiting my 1000+ cpp (including socket, stream..) blog posts and explore just a little beyond them.

(I blogged about exactly the same observation before …) Here’s a paradox — i spent 2 years in a full time c# job, arguably longer than my full time c++ experience. However, sometimes I feel I understand dotnet less than C++.

Reason? Many aspects of the languages are never used in-depth on work projects, so length of experience != depth of experience. We need spare time self-exploration to learn those aspects like:

– template meta programming
– custom operator new/delete
– memory tuning
– memory leak detection
– threading
– async communications
– pure virtual
– ++i vs i++

(… not a complete list by any measure.) Interviewers are notorious for testing these obscure or advanced, theoretical topics.

simple implementation of memory allocator#no src

P9 [[c++game development primer]] has a short implementation without using heap. The memory pool comes from a large array of chars. The allocator keeps track of allocated chunks but doesn’t reuse reclaimed chunks.

It showcases the header associated with each allocated chunk. This feature is also part of a real heap allocator.

reinterpret_cast is used repeatedly.

concurrency complexity/learn`curve c++imt java

C++ concurrency learning curve has lower /leverage/ higher effort.

* well-established — Java is designed with concurrency at its core so its memory model is mature and sound. There are a few very well-respected books on java concurrency (and some secondary books). As a result, concurrency best practices are more established in java than arguably any other language as of 2017.

* templates — Many concurrency constructs use templates with possibly specializations.

* C — Java developers never need to deal with the system-level concurrency library (invariably in C), the c++ developer may need to descend to the C level.

* multiple libraries — See post on c++ concurrency libraries. https://bintanvictor.wordpress.com/2017/04/05/common-cconcurrency-libraries/

* Low-level — C++ is a lower-level language than java.
** The concurrency classes must deal with the big 4.
** Memory management also complicate concurrency.
** Not only heap objects, but primitives on the stack are also accessible from multiple threads thanks to pointers.
** The atomic class templates are also more low-level than java’s, and much harder to get right.

* There are many mutex constructs.

pointer/itr as field: a G3 implementation pattern

common interview question.

This mega-pattern is present in 90% of java and c# classes, and also very common in c++. Important data structure classes  relying on pointer fields include vectors, strings, hashtables and most STL or boost containers.

Three common choices for a pointer member variable:

  • Raw pointer — default choice
  • shared_ptr — often a superior choice
  • char pointer, usually a c-str

In each case, we worry about

  • construction of this field
  • freeing heap memory
  • RAII
  • what if the pointee is not on heap?
  • copy control of this field
  • ownership of the pointer
  • when to return raw ptr and when to return a smart ptr

shared_ptr field offers exception safety, automatic delete, default synthesized dtor, copier, op=

 

UBS java IV 2017

Q: How could you get short theta?

Q: For a double-linked list, what if the prev pointer field is final?

Q1b: Can you construct such a list?

Q1c: What operation can you perform on it?

Q: How do you tell if a java app (or part thereof) is live-locked?

Q: How do you know if a jvm is short of memory, without seeing OOM error?

%%A: GC log would show much higher activity than the “baseline”.

Q: if a java app has hundreds of threads but most of them are not doing work, then what thread states would they have?

%%A: they must be blocked

Q: what do you look for in a job

Note this answer is completely unrelated to my true “10Y direction”.

I don’t want to spend too much time on this behavior question since this is one of the easiest behavior questions. Stock answers would suffice, as many candidates prepare stock answers.

Some other candidates would tailor an answer to the specific employer. I tend to go impromptu along :

  • mental engagement
    • math, statstics
    • analytical, data complexity
    • theoretical
    • complexity, not only theoretical
    • low-level challenges, like optimization
    • data volume — performance or analytics challenges
  • impact
    • in terms of number of people in downstream
    • in terms of influence at a higher level
    • helping team members?
  • work-life balance
  • remote
  • direct interaction with users
  • learn something new and strategic??? not worth mentioning.. Too misleading and complicated
  • Note I never mention “team” until prompted

c++ for-loop header flexibilities

size_t countLinkedNodes(){
  size_t ret=0;
  for (Node * i=head; ; 
       ++ret, i=i->next){ //<-- different data types
    if (i == NULL) return ret; //<-- more control+clarify to move part 2 out of header!
  }
}

pimco java IV onsite

Hint 81: fib(a,b, N) can be implemented as fib(b, a+b, N-1). For example, 8th Fibonacci number would be fib(0,1, 8), which would call fib(1,1,7), which would call fib(1,2,6)… This is related
to http://stackoverflow.com/questions/310974/what-is-tail-call-optimization

Q: can CMS ever stop the world?
AA: yes

Consider Fibonacci sequence. Write a function fib(N) that returns the N’th number in the sequence. fib(0) := 0, fib(1) :=1, fib(N) := fib(N-2) + fib(N-1).

Q1a: write a recursive version. What’s the time complexity and space complexity?
Q1b: write a non-recursive version. What’s the time complexity and space complexity?
Q1c: write a non-recursive version with space complexity of O(1) Q1d: write a tail-recursive version with time complexity O(N) and space complexity O(1). If no clue, look for the hint hidden nearby:)

Q2: Consider a simplified shared shopping cart. It contains any number of orders. Each order has {id, productName, quantity}. Only id is immutable; other fields are writable by multiple threads. Implement the following methods without locking (you could use atomic or other solutions to ensure thread safety):

int addOrder(productName, quantity);
boolean modifyOrder(id, productName, quantity); // two threads could modify the same order concurrently.
[Optional feature] boolean deleteOrder(id);
[Optional feature] boolean isOrderCompleted(id);

To keep requirements simple, It’s tolerable to have two orders both for the same productName.

Q3: At a high level, list all the common approaches to thread safety %%A: Read-Copy-Update; thread local; immutable objects; copy-on-write; mutex; CAS

Q4: how do you implement an immutable class with only primitive fields? %%A: make all fields private; provide no setter

Q4b: the fields need to be final?
%%A: I think unnecessary.

Q4c: class should be final?
A: I said yes but Now I think subclassing can be allowed since my fields will not be writable by subclasses. For example, a ImmutablePerson{SSN, DOB} can be sub-classed by Student{nationality, department}

Q5: what kind of classes can be a key in a map?
%%A: I feel the relevant fields should be primitive, string and enums only. Any other field I want to be careful about.
%%A: key class is effectively immutable — after the key goes into a map, the relevant fields should not change because the position of the key will not be updated.

Q6: for an overnight batch program, what GC algorithm is good for throughput?
%%A: long pauses are tolerable.
AA: Use parallel GC. See my blog
post https://bintanvictor.wordpress.com/2017/04/05/two-gc-algos-for-latencyt hroughput/

Q7: how frequent is the minor GC in your app?

Q8: how do you deal with OOM in production?
%%A: use jconsole, or somehow print a memory “report” to the log.

Q10: compare vector and linked list data structures
%%A: vector is random-access. Appending at the end is usually fast but can cause reallocation; linked list can insert anywhere but each node is too big.

Vector takes smaller space and is more cache-friendly.
See https://bintanvictor.wordpress.com/2017/04/05/contiguous-memory-data-str uctures-page-faultscache-miss/

BGC IV – c++ and Java

Q: how do you mark a memory region as always resident?
A: See mlock() : prevent paging ] real time apps

—socket
Q: is select() blocking or non-blocking?
A: Yes select() takes a timeout argument to specify the blocking interval!
A: More interestingly, https://stackoverflow.com/questions/5351994/will-read-ever-block-after-select/5352634#5352634 says after select(), you should use read() which normally won’t block.

Q: server uses socket() listen() bind() accept(). How about client side?

Q1: if a producer thread uses select to send packets to 22 receivers via 22 tcp sockets and a single receiver has very low capacity, what would happen? See tcp: one of 3 client-receivers is too slow

Q1b: select() would show that one sender socket as writable or failed?

Q1c: what if producer keeps sending? What happens next?
%%A: the producers function stack will get an error code.  Wrong!

Q1d: what if UDP rather than TCP
%%A: then no error would occur in the producer system. The slow consumer would be left unnoticed.  There’s no flow-control in UDP

%%Q: can a socket specify a wild card for its local port?
%%A: no. Wildcard is only for local IP
—IPC
Q: fastest IPC method between producer and consumer? OK you said shared memory, so how do you synchronize the producer and consumer?
%%A: use a named sys-V semaphore in the kernel
A: See boos::interprocess documentation. This is a common requirement addressed in boost.

Q: how does the producer/consumer actually use the shared memory?
%%A: memory mapped file

—brain teasers:
Q: Only a 5L and a 3L pail and a running tap. How to get exactly 4L water in the 5L pail?

Q: you are given a bag of coins (like 1c 1c 1c 5c 5c 10c 25c). Tell me whats the smallest exact payment thats impossible. Every payment must be exact. Hint: sort the coins first, then a clever O(1) single-pass will do.
AA: coin problem #all large-enough amounts are decomposable

Q: given a list of integers, find if any pair adds up to 18
%%A: in one pass, build a hashset of brown items i.e. every item processed so far. For every new (i.e green) item, compute the partner, and look for it in the hashset. If not there, then add the green item as a brown item.
AA: https://bintanvictor.wordpress.com/2015/07/21/locate-a-pair-whose-diff55/ is a clever solution.

—whiteboard coding challenge
Q: given a singly linked list with a start node and null-end node, print each node in reverse, without using any “new” implicitly/explicitly
A: reverse the list first (tail recursion or iteratively), then print normally.

Q: Given an arbitrary directed graph where each parent node has 0 to K children, write a function hasCycle() to check for existence of cycle, visiting each node and each edge once only..
%%A: My verbal algorithm — use breadth-first traversal to trace every branch from root to a leaf node. Detect cycle in each branch. But I wonder whether two parent nodes can have the same descendant node.

Whenever we branch out to 2 child branches, duplicate the parent branch, so that each child branch object has a full path from root.

Each branch object could be a (possibly linked[1]) hashset.
[1] for instrumentation.

Q: given a blackbox utility function String convert(String), write a parallelized Collection parellelConvert(Collection theSequence)
Requirement: theSequence need to be maintained. Size of input is preserved Requirement: Out of 100 items in theSequence, #3 and #5 might be identical, but they still need to show up as “converted” in the output
Requirement: converter uses a very slow and expensive remote system, so we don’t want to send it the same string twice.

—-
%%Q: is countdown latch and join() implemented using wait/notify? %%Q: readResolve vs readObject
%%Q: can CMS ever stop the world?
%%Q: CMS is used in which region of the heap?
Q: what if you suspect theres leak?
Q: what can cause mem leak in java?
%%A: registered listeners; static variables pointing to a collection

Q: why is swing memory footprint so bad?
Q: array blocking queue — when would it block?
%%A: I think a circular array is the underlying.

tcp client bind()to non-random port: j4

TCP client doesn’t specify local endpoint. It only specifies the remote endpoint.

  • The local port is random. It’s conceptually an “outgoing” port as the client reaches out to the remote server.
  • The local IP address is probably chosen by the kernel, based on the remote IP address specified.

See http://stackoverflow.com/questions/11129212/tcp-two-different-sockets-sharing-a-port

A Barclays TCP interview asked

Q: When a tcp client runs connect(), can it specify a client-side port rather than using a random port assigned by the system?
A: use bind() — http://stackoverflow.com/questions/4118241/what-client-side-situations-need-bind

Motivation?
* I feel the client port number can work like a rudimentary tag for a “special” client thread
* similarly, debugging — http://stackoverflow.com/questions/347636/determining-the-tcp-port-number-to-which-client-got-bound
* firewall filtering on client port — http://stackoverflow.com/questions/4118241/what-client-side-situations-need-bind
* some servers expect client to use a low port — http://stackoverflow.com/questions/4118241/what-client-side-situations-need-bind

Note client bind() can also specify a particular client ip address (multihoming). Client side bind() defines the local port and interface address for the connection. In fact, connect() does an implicit bind(“0.0.0.0”, 0) if one has not been done previously (with zero being taken as “any”). See http://stackoverflow.com/questions/12763268/why-is-bind-used-in-tcp-why-is-it-used-only-on-server-side-and-not-in-client.

pimco java IV#Zoltan

Hint 81: fib(a,b, N) can be implemented as fib(b, a+b, N-1). For example, 8th Fibonacci number would be fib(0,1, 8), which would call fib(1,1,7), which would call fib(1,2,6)… This is related
to http://stackoverflow.com/questions/310974/what-is-tail-call-optimization

Q: can CMS ever stop the world?

Consider Fibonacci sequence. Write a function fib(N) that returns the N’th number in the sequence. fib(0) := 0, fib(1) :=1, fib(N) := fib(N-2) + fib(N-1).

Q1a: write a recursive version. What’s the time complexity and space complexity?
Q1b: write a non-recursive version. What’s the time complexity and space complexity?
Q1c: write a non-recursive version with space complexity of O(1) Q1d: write a tail-recursive version with time complexity O(N) and space complexity O(1). If no clue, look for the hint hidden nearby:)

Q2: Consider a simplified shared shopping cart. It contains any number of orders. Each order has {id, productName, quantity}. Only id is immutable; other fields are writable by multiple threads. Implement the following methods without locking (you could use atomic or other solutions to ensure thread safety):

int addOrder(productName, quantity);
boolean modifyOrder(id, productName, quantity); // two threads could modify the same order concurrently.

[Optional feature] boolean deleteOrder(id);
[Optional feature] boolean isOrderCompleted(id);

To keep requirements simple, It’s tolerable to have two orders both for the same productName.

Q3: At a high level, list all the common approaches to thread safety %%A: CAS; mutex; Read-Copy-Update; immutable objects; copy-on-write; thread local

Q4: how do you implement an immutable class with only primitive fields? %%A: make all fields private; provide no setter

Q4b: the fields need to be final?
%%A: I think unnecessary.

Q4c: class should be final?
A: I said yes but Now I think subclassing can be allowed since my fields will not be writable by subclasses. For example, a ImmutablePerson{SSN, DOB} can be sub-classed by Student{nationality, department}

Q5: what kind of classes can be a key in a map?
%%A: I feel the relevant fields should be primitive, string and enums only. Any other field I want to be careful about.
%%A: key class is effectively immutable — after the key goes into a map, the relevant fields should not change because the position of the key will not be updated.

Q6: for an overnight batch program, what GC algorithm is good for throughput?
%%A: long pauses are tolerable.
AA: Use parallel GC. See my blog
post https://bintanvictor.wordpress.com/2017/04/05/two-gc-algos-for-latencyt hroughput/

Q7: how frequent is the minor GC in your app?

Q8: how do you deal with OOM in production?
%%A: use jconsole, or somehow print a memory “report” to the log.

Q10: compare vector and linked list data structures
%%A: vector is random-access. Appending at the end is usually fast but can cause reallocation; linked list can insert anywhere but each node is too big.

Vector takes smaller space and is more cache-friendly.
See https://bintanvictor.wordpress.com/2017/04/05/contiguous-memory-data-str uctures-page-faultscache-miss/

big data is!! fad; big-data technologies might be

(blogging)

My working definition — big data is the challenges and opportunities presented by the large volume of disparate (often unstructured) data.

For decades, this data has always been growing. What changed?

* One recent changed in the last 10 years or so is data processing technology. As an analogy, oil sand has been known for quite a while but the extraction technology slowly improved to become commercially viable.

* Another recent change is social media, creating lots of user-generated content. I believe this data volume is a fraction of the machine-generated data, but it’s more rich and less structured.

Many people see opportunities to make use of this data. I feel the potential usefulness of this data is somewhat /overblown/ , largely due to aggressive marketing. As a comparison, consider location data from satellites and cellular networks — useful but not life-changing useful.

The current crop of big data technologies are even more hype. I remember XML, Bluetooth, pen computing, optical fiber .. also had their prime times under the spotlight. I feel none of them lived up to the promise (or the hype).

What are the technologies related to big data? I only know a few — NOSQL, inexpensive data grid, Hadoop, machine learning, statistical/mathematical python, R, cloud, data mining technologies, data warehouse technologies…

Many of these technologies had real, validated value propositions before big data. I tend to think they will confirm and prove those original value propositions in 30 year, after the fads have long passed.

As an “investor” I have a job duty to try and spot overvalued, overhyped, high-churn technologies, so I ask

Q: Will Haoop (or another in the list) become more widely used (therefore more valuable) in 10 years, as newer technologies come and go? I’m not sure.

http://www.b-eye-network.com/view/17017 is a concise comparison of big data and data warehouse, written by a leading expert of data warehouse.

##real reasons I didn’t take 2011 c++job]U.S.

Reason – the salary gap between my c++ offers and java offers. I think the highest c++ offer was PIMCO, around $100/hr paid to agency (Huxley?). Most of the time, the java offers paid me (significantly) more than c++.

Reason — I also felt I could fairly easily crack the typical c++ interviews from then on. Now (2017) I doubt it.

Reason — some of the c++ jobs were not so “glamorous” less trading, less mainstream. Now (2017) I don’t care so much

##common c++concurrency libraries

Java has language-level support for concurrency + some special concurrency classes in the JDK library.

C/C++ use a library-only approach. C libraries include pthreads and winthreads. I think these are provided by the OS, because these threads are kernel threads.

Many threaded c++ projects use nothing but these C libraries.

There are also c++ thread libraries, (probably always) based on the underlying C libraries.
* c++11 thread library
* boost
* ACE
* Microsoft Foundation Classes
* RogueWave

While the lucky java developer can afford to focus on a single concurrency tool set, the unlucky c++ developer often have to juggle 2 or more.

Therefore, it’s harder to get the “halo” in c++ concurrency interviews

contiguous memory data structures : page faults+cache miss

Compared to linked data structures, I feel vectors (and array, deque, circular array…) reduce page faults and cache miss.

P124 [[art of debugging]] describes how a simple array is loaded from swap space into a real memory “page”. This is managed by the virtual memory system.

P19 [[optimized c++]] describes that L1 or L2 cache also loads vector more efficiently than a linked data structure. For example, each time main memory is read, the adjacent memory cells are loaded together into L1 cache, so contiguous memory data structures result in much fewer cache miss, in theory.

A virtual memory page is about 4KB. A cache line is about 64B.

Both page fault and cache miss are costly at runtime. In both cases the “backing store” is much slower but we have to read from it. These situations are by design and very common, but it pays to reduce their /incidence/occurrence. Even if we reduce page fault frequency or cache miss frequency by 10%, it could be helpful.

y concurrentHM.size() must lock entire map#my take

Why not lock one segment, get the subcount, unlock, then move to next segment?

Here’s my take. Suppose 2 threads concurrently inserts an item in each of two segments. Before that, there are 33 items. Afterwards, there are 35 items. So 33 and 35 are both "correct" answers. 34 is incorrect.

If you lock one segment at a time, you could count an old value in one segment then a new value in another segment.

## meaningful endeavor(Now)for20Y career#dnlg;zbs;IV

Q: what efforts go towards 20Y-career building?
A: instrumentation in c++(java is a bit more churn); socket programming; STL internals; JVM internals; shell scripting; pthreads; FIX; linux internal?

This question is slightly vague, but it’s subtly different from

Q2: what efforts create social value over 20Y?
Q3: what efforts are cumulative over 20Y?

I feel the key question in this write-up is about building a deep and broad “foundation”, upon which we can start to plan (possible) social value, retirement planning, parenting/family building etc.

  • 😦 teaching and research —- Somehow I tend to feel research creates long-term value but I suspect most research efforts are not valuable!
  • 😦 open-source software —- I tend to feel OSS projects create social value, but most of them are not successful and have no lasting influence
  • 😦 Deepening your domain knowledge such as (German’s) security lending —- It does increase your value-add to some employers and help you move up to management, but I don’t call it “foundation”.
    • MSFM and other formal training —- I feel this is less effective, more ivory-tower, but it does build a firm theoretical foundation.
  • fitness and health .. more important than I feel (as shown by my action)
  • zbs such as instrumentation skills? Yes zbs helps your KPI, and also indirectly helps you with interviews. It’s portable skill, unlike local system knowledge. Can the value last 20Y? Depends on the technology churn. c++ and java are safer.
  • IV muscle building? My favorite career building effort. 20Y? 10Y yes.
  • English/Chinese writing and vocab

[09]%%design priorities as arch/CTO

Priorities depend on industry, target users and managers’ experience/preference… Here are my Real answers:

A: instrumentation (non-opaque ) — #1 priority to an early-stage developer, not to a CTO.

Intermediate data store (even binary) is great — files; reliable[1] snoop/capture; MOM

[1] seldom reliable, due to the inherent nature — logging/capture, even error messages are easily suppressed.

A: predictability — #2 (I don’t prefer the word “reliability”.) related to instrumentation. I hate opaque surprises and intermittent errors like

  • GMDS green/red LED
  • SSL in Guardian
  • thick, opaque libraries like Spring
  1. Database is rock-solid predictable.
  2. javascript was predictable in my pre-2000 experience
  3. automation Scripts are often more predictable, but advanced python is not.

(bold answers are good interview answers.)
A: separation of concern, encapsulation.
* any team dev need task breakdown. PWM tech department consists of teams supporting their own systems, which talk to each other on an agreed interface.
* Use proc and views to allow data source internal change without breaking data users (RW)
* ftp, mq, web service, ssh calls, emails between departments
* stable interfaces. Each module’s internals are changeable without breaking client code
* in GS, any change in any module must be done along with other modules’ checkout, otherwise that single release may impact other modules unexpectedly.

A: prod support and easy to learn?
* less support => more dev.
* easy to reproduce prod issues in QA
* easy to debug
* audit trail
* easy to recover
* fail-safe
* rerunnable

A: extensible and configurable? It often adds complexity and workload. Probably the #1 priority among managers i know on wall st. It’s all about predicting what features users might add.

How about time-to-market? Without testibility, changes take longer to regression-test? That’s pure theory. In trading systems, there’s seldom automated regression testing.

A: testability. I think Chad also liked this a lot. Automated tests are less important to Wall St than other industries.

* each team’s system to be verifiable to help isolate production issues.
* testable interfaces between components. Each interface is relatively easy to test.

A: performance — always one of the most important factors if our system is ever benchmarked in a competition. Benchmark statistics are circulated to everyone.

A: scalability — often needs to be an early design goal.

A: self-service by users? reduce support workload.
* data accessible (R/W) online to authorized users.

A: show strategic improvement to higher management and users. This is how to gain visibility and promotion.

How about data volume? important to eq/fx market data feed, low latency, Google, facebook … but not to my systems so far.

multicast address 1110xxxx #briefly

By definition, multicast addresses all start with 1110 in the first half byte. Routers seeing such a destnation (never a source) address knows the msg is a multicast msg.

However, routers don’t forward any msg with destnation address 224.0.0.0 through 224.0.0.255 because these are local multicast addresses. I guess these local multicast addresses are like 192.168.* addresses.