Chapter 2 Deepdive

2.1 Tricky bug

2.1.1 GRPC Carsh after pointer conversion in some platform

Ref: https://gcc.gnu.org/ml/gcc-bugs/2000-03/msg00155.html

C99 - http://www.coding-guidelines.com/C99/html/6.3.2.3.html

# A pointer to an object or incomplete type may be converted to a
# pointer to a different object or incomplete type. If the resulting
# pointer is not correctly aligned for the pointed-to type, the
# behavior is undefined. Otherwise, when converted back again, the
# result shall compare equal to the original pointer.

C17: Programming languages — C Page 41

Fix alignment issue in gpr_murmur_hash3 This function cast a void* to a uint32_t*. This is invalid, since a uint32_t* must be 32-bit-aligned, while the input key clearly isn't. Even though the function later uses memcpy to access the memory, by that point the compiler is allowed to assume that the pointer is aligned, and so it can output code that does an unaligned memory access. In practice, this resulted in a crash on some devices when this code is compiled with optimizations for 32-bit ARM with the Android NDK r14.

Ref: https://developercommunity.visualstudio.com/content/problem/296739/memcpy-on-unaligned-chunk-of-memory-results-in-acc.html

https://stackoverflow.com/questions/13696218/converting-a-pointer-to-different-type-in-c
http://blog.qt.io/blog/2011/06/10/type-punning-and-strict-aliasing/

  • Strict Alias

https://blog.csdn.net/dbzhang800/article/details/6720141
https://blog.csdn.net/liaofengjun/article/details/52743452

2.2 TimerWheel

2.2.1 Goal

  • insert message O(1)
  • delete message O(1)
  • time wheel progressing O(1)
  • 10 milliseconds precision
  • 1 million message 8 bytes on average

2.2.2 Workflow/MegaWatch

Data Structure: blocking queue,

Thread 1 - TimerWheelInserter (main thread)

Thread 2 - InterrupteableSleeper (Producer)

Thread 3 - Dispatcher (consumer)

API:

  • getClosestMsgBucket() return { starting time of the cell, unorder vector of message and scheduled time}

  • advance(time_t)

At time 0, we inserted a,b,c,d for message with delayed delivery time.

Global var sleepUntil;

Thread 2 - InterrupteableSleeper:

  • getClosestMsgBucket() return {32 seconds, {a:35, b:39}} // insert?
  • sleepUntil=32
  • sleep until 32 seconds
    // TODO - message(e:17) inserted

Thread 1 - TimerWheelInserter:

called by other threads to insert message, if delayed time is less than sleepUntil, wake up Thread 1 and update sleeping time

Thread 2 - InterrupteableSleeper:

  • at time 32, wake up

  • coz 32!=35, advances time by 32 seconds, moving a to (0,3), b to (0,6).

  • getClosestMsgBucket() return {35 seconds, {a:35}}

  • sleepUntil=35, sleep until 35 seconds

  • wake up and remove msg a

  • getClosestMsgBucket() return {39 seconds, {b:39}}

  • sleepUntil=39, sleep until 39 seconds

  • wake up and remove msg b

  • getClosestMsgBucket() return {192 seconds, {c:195, d:252}}

  • sleepUntil=192, sleep until 192 seconds

Thread 2 - InterrupteableSleeper:

  • If no new younger messager, at time 192, InterrupteableSleeper wakes up

  • advances time by 192 seconds, moving c to (0,3), d to (1,7).

  • getClosestMsgBucket() return {192 seconds, {c:195}}

  • sleepUntil=195

  • sleep until 195 seconds

  • wake up and remove msg c

  • getClosestMsgBucket() return {248 seconds, {d:252}}

  • sleepUntil=248

  • sleep until 248 seconds

  • wake up
  • coz 248!=252, advance 248 seconds, moving d to (0,4)
  • getClosestMsgBucket() return {252 seconds, {d:252}}
  • sleepUntil=252 , sleep until 252 seconds

  • wake up and remove msg d

  • After wake up:

if max(scheduled time in the cell) > cell starting time:
  advance(cell starting time)
else
  process_msg()
  • How to get cell starting time?

use tick to represent time. the following is starting time of different cells:

tick = [0,0,0]  is time 0
tick = [0,4,0]  is time 0+32+0
tick = [3,4,0]  is time 3+32+0=35
tick = [0,0,3]  is time 19
tick = [0,7,3]  is time 192+56+0=248

2.2.3 API Implementation

  • advance by time and promote messages in cell, the time is the starting time of the cell
advance(cell){
  tick_arry = get_tick_array(cell.starting_time) // assuming current time is at cell.starting_time
  for (message in cell)
    i,j = find_position(messge.scheduled_time)
    cell[i][j] = message
  cell.clear()
}
getClosestMsgBucket()
  REP(i,0,8)
    REP(j,0,3)
      if (!megawatch[i][j].messages.empty()){
        return get_cell_starting_time(i,j);
      }
int get_cell_starting_time(x,y,watch_tick[3]){
  sum=0
  for(i=2;i>=x;i--){
    if(x==i)
      sum+=time_bitmap[i][y];
    else
      sum+=time_bitmap[i][watch_tick[i]];
  }
  return sum;
}
// x/*=2*/,y/*=3*/,watch_tick[3]/*0,7,3*/ => 192
// x/*=1*/,y/*=7*/,watch_tick[3]/*0,7,3*/ => 192+56
// x/*=1*/,y/*=6*/,watch_tick[3]/*0,7,3*/ => 192+56