How to change primary key's data type from int to bigint in a huge transactional database under tremendous load?
Assuming your current table is something like

CREATE TABLE YourTable
  (
     Id           INT IDENTITY PRIMARY KEY,
     OtherColumns VARCHAR(10)
  )


And that your existing code that references the table just performs basic DQL and DML commands against the table (i.e. SELECT/UPDATE,MERGE,INSERT,DELETE)

And that YourTable(Id) isn't referenced by a foreign key anywhere.

Then possibly the best way of getting up and running quickly (if you can't afford the downtime of rebuilding the whole table in one go) would be to rename that table (e.g. as YourTableInt) and create a new table

CREATE TABLE YourTableBigInt
  (
     Id           BIGINT IDENTITY(2147483648, 1) PRIMARY KEY,
     OtherColumns VARCHAR(10)
  )


You could then create a view with the same name as your original table name.

CREATE VIEW YourTable
AS
  SELECT Id,
         OtherColumns
  FROM   YourTableInt
  UNION ALL
  SELECT Id,
         OtherColumns
  FROM   YourTableBigInt 


You would need to write INSTEAD OF triggers that route the Inserts/Updates/Deletes to the appropriate table. This could initially be based on whether Id was &lt;= 2147483647 or not but that isn't going to work if you try and migrate rows in the background from the legacy table to the new one so probably best to do the following.

Delete trigger
    Apply deletes against both tables by joining on id

Update trigger
    Apply updates to both tables by joining on id

Insert trigger
    Route all inserts into the new "YourTableBigInt" table. It shouldn't be possible for an insert through the view to enter an explicit identity that might clash with anything in the original table as any attempt to set identity_insert YourTable will fail now that is actually a view.    

You could then have a background process that deletes batches of rows from YourTableInt and outputs them into YourTableBigInt. Once the original table is empty you can drop it and the view and rename YourTableBigInt to YourTable.