Programming Fundamentals

Important fundamentals that do not always arise in daily work.

JVM

Multithreading

• Key implementation details of ThreadPoolExecutor:

  • Store workers in HashSet<Worker> so the pool can expand when new tasks arrive.
  • Store tasks in java.util.concurrent.BlockingQueue.
  • Workers continuously pull tasks from BlockingQueue.
  • BlockingQueue has a size limit, with a DiscardPolicy for rejection.

• ReentrantLock: An exclusive, reentrant lock. Similar to synchronized but with more features, including tryLock(timeout), ownership checks, and per-thread lock/unlock counts. Fair locks check whether longer-waiting threads exist before granting access; unfair locks compete directly without checking the queue. Normally, tryLock(timeout) places the thread in the waiting queue.

• CyclicBarrier: A reusable barrier for multiple threads. The two constructors are shown below; the second accepts a Runnable executed after all threads are released. A common use case is parallel computation followed by merging results.

1
public CyclicBarrier(int parties)
2
public CyclicBarrier(int parties, Runnable barrierAction)

• CountDownLatch: Like a rocket-launch countdown. For example, if ten threads perform preparation, the main program continues after the countdown reaches zero.

• HashMap / Hashtable / ConcurrentHashMap: Hashtable is thread-safe and locks the entire table. HashMap uses arrays and linked lists and is not thread-safe. ConcurrentHashMap partitions its array-and-list structure into segments, locks at segment granularity, and uses volatile values to avoid locks on reads.

• volatile

• mmap

• wait / notify: Must be used within a synchronized context.

• CAS (Compare And Swap): Based on optimistic concurrency.

LOCK

• Fat lock: Multiple threads compete for a resource; highest performance cost.
• Thin lock: Multiple threads access a resource, but not simultaneously, so there is no contention.
• Recursive lock: The same thread accesses the resource repeatedly.
• Biased lock: Only one thread accesses the resource.

JVM Memory Model

• Heap: The largest memory region managed by the JVM. Objects are shared across threads, requiring synchronization for concurrent access.
• Method area: Class information and constants.
• Stack: Private to each thread, holding local-variable tables, operand stacks, dynamic linking, and method return information. Each method call pushes and later pops a stack frame.
• Program counter: Private to each thread, recording its execution position.
• Native method stack: Used by native code.

GC

GC basics:

During stop-the-world (STW), all threads must reach safepoints. Ensuring consistent object operations beforehand is difficult. The actual GC pause may be short while reaching safepoints takes a long time. Relevant GC flags expose these details.

• Mark reachable objects: Starting from GC roots such as static objects, trace references and mark live objects. Marking includes STW work whose duration depends on live heap objects.
• Remove unused objects: After marking, the JVM reclaims unused objects.
  • Sweep: Leaves gaps that complicate subsequent allocation.
  • Compact: Moves surviving objects together, eliminating gaps but increasing GC pause time.
  • Copy: Copies surviving objects to another memory region.

GC types: minor-gc-vs-major-gc-vs-full-gc

GC Algorithm Implementations

• Serial GC: Mark-copy for the young generation and mark-sweep-compact for the old generation. A single-threaded, older collector that cannot exploit multiple cores and has long STW pauses.

• Parallel GC: Similar algorithms, but multithreaded.

• Concurrent Mark and Sweep (CMS): Mark-copy for the young generation and mark-sweep for the old generation, aiming to reduce pause time. It has seven stages:

  1. Initial Mark: Mark old-generation roots, potentially scanning young-generation references into the old generation. Requires STW.
  2. Concurrent Mark: Trace live old-generation objects from the marked roots without STW. Concurrent changes mean not every live object is captured.
  3. Concurrent Preclean: Revisit old-generation reachability and references modified during the previous concurrent stage.
  4. Concurrent Abortable Preclean: I do not yet understand this stage…
  5. Final Remark: STW ensures precleaning catches up with application changes.
  6. Concurrent Sweep: Remove unused objects without STW.
  7. Concurrent Reset: Reset the collector.

• G1, Garbage First: Divides Eden, Survivor, and Tenured memory into collection regions and collects by region. Users can configure targets such as maximum STW duration, which G1 tries to meet.

References

• Strong reference: Ordinary object references. Objects are collected when no references keep them reachable.
• Weak reference: If only weak references remain, GC reclaims the object and places the reference on its associated ReferenceQueue.
• Soft reference: Reclaimed under memory pressure, useful for caches.

Distributed Computing

• Data skew *

Apache Druid

Impala

MPP architectures implement data exchange through exchange nodes, somewhat like Spark’s external shuffle service? Neither MPP nor MapReduce is inherently superior. MPP lacks a separate shuffle operation, making it faster and better suited to simple queries.

Presto

Similar to Impala.

Apache Spark

• Spark Streaming backpressure: Uses a PID controller to adjust consumption steadily according to processing rates.

Apache Flink

• Blink optimizations: README.md
• FLIP-6: Adds ResourceManager and Dispatcher for finer-grained allocation after acquiring resources from systems such as YARN. This allows more flexible resource priorities across jobs.
• Flink incremental checkpoints use RocksDB’s LSM properties. Incremental means reusing previous checkpoint files and persisting only newly added data, rather than deleting files through compaction.
• Flink Exactly-Once vs. At-Least-Once: Exactly-Once uses BarrierBuffer in CheckpointBarrierHandler. A task waits for barriers from every input before proceeding and forwarding a barrier downstream, buffering data during alignment. Exceeding the configured buffer limit fails the checkpoint. At-Least-Once uses BarrierTracker without buffering or barrier alignment.
• Flink Checkpoint: (1) operatorChain.prepareSnapshotPreBarrier (2) operatorChain.broadcastCheckpointBarrier (3) checkpoint
• Checkpoints have synchronous and asynchronous modes, implemented differently in HeapStateBackend. Both create a CopyOnWriteStateTable, effectively copying state. Synchronous mode persists directly after creating a snapshot, while asynchronous mode passes a FutureTask onward for later execution.
• Flink’s network-stack transfer flow.

File Formats

• Parquet: Based on Dremel and supports structured data:

• ORC: Combines row and column organization. Files are divided into stripes, each with per-column metadata that accelerates filtering:

• RCFile: Somewhat similar to Parquet, but does not support structured data in the same way.