1. Estimate count of records in result sample: $n = 1000;
2. Estimate count of records in "primar" sample: $p = $n * 100;
3. Generate array of byte positions @pos, uniformly distributed in interval [1, length of file], satisfying condition $p == @pos;
4. If it is worth for seeking in the file, sort @pos.
5. my @res; my %res;
6. foreach @pos
6.1 read the record starting behind $_-th byte and remember $start, which is position of the first byte of the record in the file
6.2 next if exists $res{$start};
6.3 $res{$start} = 1;
6.4 my $rand = some_uniform_rand()/($start - $_). It is crucial step - IF ordering of records is somehow dependent on record length, it can normalize it. Records following longer records have lowered probability to be inserted into @res.
6.5 if $n < @res
       insert {weight => $rand, rec => $record} into @res, keeping ascending order by weight
6.6 elsif $rand > $rec[0]{weight}
       shift @rec and insert {weight => $rand, rec => $record} into @res, keeping ascending order by weight
7. you have @res