Challenges with Key with Gaps? I had a mistake with a trigger which resulted in errors in PostgreSQL 9.4.3 on x86_64-unknown-linux-gnu, compiled by gcc (Debian 4.9.2-10) 4.9.2, 64-bit. 
Each time during the error, the primary key of SERIAL increased. 
After fixing the bug, the table measurements is 

 measurement_id | measurement_size_in_bytes |             time              
----------------+---------------------------+-------------------------------
              1 |                     77777 | 2015-07-14 18:29:56.858703+03
              2 |                       888 | 2015-07-14 18:29:56.882552+03
              3 |                       888 | 2015-07-14 18:30:15.505957+03
              4 |                       888 | 2015-07-14 18:41:01.878106+03
             39 |                     77777 | 2015-07-15 12:11:21.21391+03
             40 |                     77777 | 2015-07-15 12:11:59.551973+03
             41 |                     77777 | 2015-07-15 12:12:05.48982+03
             42 |                     77777 | 2015-07-15 12:13:02.402053+03
             43 |                     77777 | 2015-07-15 12:13:02.419412+03
             44 |                       888 | 2015-07-15 12:13:02.434728+03
         ...


where the amount of error statements has been 35 (= 39-4). 
This jump in IDs may become a challenge later when I want to integrate this table with a partial index where order matters. 

Table

CREATE TABLE measurements
    (
        measurement_id SERIAL PRIMARY KEY NOT NULL,
        measurement_size_in_bytes INTEGER NOT NULL,
        time TIMESTAMP WITH TIME ZONE NOT NULL DEFAULT CURRENT_TIMESTAMP,
        CONSTRAINT no_duplicate_measurements UNIQUE (time)
    );    


What are the challenges of keys with gaps?
What you see is completely normal and expected.


  Note: Because smallserial, serial and bigserial are implemented using sequences, there may be "holes" or gaps in the sequence of
  values which appears in the column, even if no rows are ever deleted.
  A value allocated from the sequence is still "used up" even if a row
  containing that value is never successfully inserted into the table
  column. This may happen, for example, if the inserting transaction
  rolls back.


Unless you really need a gapless series of values, you don't have to worry about it.  This is how most (well over 99%, I guess) database tables work.

If you need it, be careful if you have concurrent inserts on the table - you will need some locking to exclude the possibility of choosing the same value by two or more sessions running in parallel.