Reservoir sampling is really cool - a slightly optimized version (algorithm L) let's you skip over every record that will not be sampled and it is still pretty simple. If your records are fixed size this can be an awesome speedup.

(* S has items to sample, R will contain the result )

ReservoirSample(S[1..n], R[1..k])

  // fill the reservoir array
  for i = 1 to k
      R[i] := S[i]

  (* random() generates a uniform (0,1) random number *)
  W := exp(log(random())/k)

  while i <= n
      i := i + floor(log(random())/log(1-W)) + 1
      if i <= n
          (* replace a random item of the reservoir with item i *)
          R[randomInteger(1,k)] := S[i]  // random index between 1 and k, inclusive
          W := W * exp(log(random())/k)

https://en.m.wikipedia.org/wiki/Reservoir_sampling